27 September 2018 in IEEE Transactions on Cybernetics
As a typical model-based evolutionary algorithm, estimation of distribution algorithm (EDA) possesses unique characteristics and has been widely applied in global optimization. However, the commonly used Gaussian EDA (GEDA) usually suffers from premature convergence, which severely limits its search efficiency. This paper first systematically analyzes the reasons for the deficiency of traditional GEDA, then tries to enhance its performance by exploiting the evolution direction, and finally develops a new GEDA variant named EDA². Instead of only utilizing some good solutions produced in the current generation to estimate the Gaussian model, EDA² preserves a certain number of high-quality solutions generated in the previous generations into an archive and employs these historical solutions to assist estimating the covariance matrix of Gaussian model. By this means, the evolution direction information hidden in the archive is naturally integrated into the estimated model, which in turn can guide EDA² toward more promising solution regions. Moreover, the new estimation method significantly reduces the population size of EDA² since it needs fewer individuals in the current population for model estimation. As a result, a fast convergence can be achieved. To verify the efficiency of EDA², we tested it on a variety of benchmark functions and compared it with several state-of-the-art EAs. The experimental results demonstrate that EDA² is efficient and competitive.
5 September 2018 in Applied Intelligence
27 August 2018 in IEEE Transactions on Cybernetics
Cooperative coevolution (CC) has shown great potential for solving large-scale optimization problems (LSOPs). However, traditional CC algorithms often waste part of the computation resource (CR) as they equally allocate CR among all subproblems. The recently developed contribution-based CC algorithms improve the traditional ones to a certain extent by adaptively allocating CR according to some heuristic rules. Different from existing works, this paper explicitly constructs a mathematical model for the CR allocation (CRA) problem in CC and proposes a novel fine-grained CRA (FCRA) strategy by fully considering both the theoretically optimal solution of the CRA model and the evolution characteristics of CC. FCRA takes a single iteration as a basic CRA unit and always selects the subproblem which is most likely to make the largest contribution to the total fitness improvement to undergo a new iteration, where the contribution of a subproblem at a new iteration is estimated according to its current contribution, current evolution status, as well as the estimation for its current contribution. We verified the efficiency of FCRA by combining it with the success-history-based adaptive differential evolution which is an excellent DE variant but has never been employed in the CC framework. Experimental results on two benchmark suites for LSOPs demonstrate that FCRA significantly outperforms existing CRA strategies and the resulting CC algorithm is highly competitive in solving LSOPs.
27 April 2022 in IEEE Transactions on Evolutionary Computation
Decomposition plays a significant role in cooperative coevolution, which shows great potential in large-scale black-box optimization (LSBO). However, current learning-based decomposition algorithms require many fitness evaluations (FEs) to detect variable interdependencies and encounter the difficulty of threshold setting. To address these issues, this study proposes an efficient adaptive differential grouping (EADG) algorithm. Instead of homogeneously tackling different types of LSBO instances, EADG first identifies the instance type by detecting the interdependencies of a few pairs of variable subsets. Only if the instance is partially separable dose EADG further engage with it by converting its decomposition process into a search process in a binary tree. This facilitates the systematic reutilization of evaluated solutions so that half the interdependencies can be directly deduced without extra FEs. To promote the decomposition accuracy, EADG specially designs a normalized interdependency indicator that can adaptively generate a decomposition threshold according to its ordinal distribution. Theoretical analysis and experimental results show that EADG outperforms current popular decomposition algorithms. Further tests indicate that it can help cooperative coevolution achieve highly competitive optimization performance.
1 April 2018 in Knowledge-Based Systems
1 December 2021 in Knowledge-Based Systems