This paper proposes a new evolutionary algorithm, called DSMGA-II, to efficiently solve optimization problems via exploiting problem substructures. The proposed algorithm adopts pairwise linkage detection and stores the information in the form of dependency structure matrix (DSM). A new linkage model, called the incremental linkage set, is then constructed by using the DSM. Inspired by the idea of optimal mixing, the restricted mixing and the back mixing are proposed. The former aims at efficient exploration under certain constrains. The latter aims at exploitation by refining the DSM so as to reduce unnecessary evaluations. Experimental results show that DSMGA-II outperforms LT-GOMEA and hBOA in terms of number of function evaluations on the concatenated folded cyclic trap problems, NK-landscape problems with various degrees of overlapping, 2D Ising spin-glass problems, and MAX-SAT. The investigation of performance comparison with P3 is also included.
OM was first proposed as the recombination operator of the recombinative gene-pool optimal mixing evolutionary algorithm @cite_12 . OM applies function evaluation during the recombination and take the change only if the fitness value improves. OM somewhat acts like building-block wise local search with interchangeable models. Models are usually described as the family of subsets (FOS) @cite_12 . An FOS contains subsets of a certain set @math . Each subset of FOS may appear more than once. The set @math contains all problem variable indexes, @math . An FOS @math can be written as an ordered set @math where @math , i @math . Moreover, every problem variable index is contained in at least one subset in @math to ensure that every linkage is used in mixing operators. OMEAs are superior to most GAs in many aspects. One of the noticeable properties is that a much smaller population size is required for optimization because of the noise-free decision-making in terms of the population sizing @cite_28 . Furthermore, OM operators are capable of dealing with problems with overlapping structures efficiently with certain FOS @cite_13 .
@cite_28 @cite_13 @cite_12
2278052651 2116926066
This paper considers the effect of stochasticity on the quality of convergence of genetic algorithms (GAs). In many problems, the variance of building-block fitness or so-called collateral noise is the major source of variance, and a population-sizing equation is derived to ensure that average signal-to-collateral-noise ratios are favorable to the discrimination of the best building blocks required to solve a problem of bounded deception. The sizing relation is modified to permit the inclusion of other sources of stochasticity, such as the noise of selection, the noise of genetic operators, and the explicit noise or nondeterminism of the objective function. In a test suite of five functions, the sizing relation proves to be a conservative predictor of average correct convergence, as long as all major sources of noise are considered in the sizing calculation. These results suggest how the sizing equation may be viewed as a coarse delineation of a boundary between what a physicist might call two distinct phases of GA behavior. At low population sizes the GA makes many errors of decision, and the quality of convergence is largely left to the vagaries of chance or the serial fixup of flawed results through mutation or other serial injection of diversity. At large population sizes, GAs can reliably discriminate between good and bad building blocks, and parallel processing and recombination of building blocks lead to quick solution of even difficult deceptive problems. Additionally, the paper outlines a number of extensions to this work, including the development of more refined models of the relation between generational average error and ultimate convergence quality, the development of online methods for sizing populations via the estimation of populations via the estimation of population-sizing parameters, and the investigation of populationsizing in the context of niching and other schemes designed for use in problems with high cardinality solution sets. The paper also discusses how these results may one day lead to rigorous proofs of convergence for recombinative G As operating on problems of bounded description. A key search mechanism in Evolutionary Algorithms is the mixing or juxtaposing of partial solutions present in the parent solutions. In this paper we look at the efficiency of mixing in genetic algorithms (GAs) and estimation-of-distribution algorithms (EDAs). We compute the mixing probabilities of two partial solutions and discuss the effect of the covariance build-up in GAs and EDas. Moreover, we propose two new Evolutionary Algorithms that maximize the juxtaposing of the partial solutions present in the parents: the Recombinative Optimal Mixing Evolutionary Algorithm (ROMEA) and the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA).