Theoretical Perspective of Convergence Complexity of Evolutionary Algorithms Adopting Optimal Mixing
Date Issued
2015
Date
2015
Author(s)
Tung, Yu-Fan
Abstract
The optimal mixing evolutionary algorithms (OMEAs) have recently drawn much attention for their robustness, small size of required population, and efficiency in terms of number of function evaluations (NFE). To fully understand their performances, in this thesis the convergence behaviors for OMEAs are studied by investigating the mechanism of optimal mixing, the variation operator in OMEAs. For the case of one-layer masks, the required population size is derived from the viewpoint of initial supply, while the convergence time is derived by analyzing the progress of subsolution growth. NFE is then asymptotically bounded with rational probability by estimating the probability of performing evaluations. Based on these results the discussion extends to multi-layer masks and overlapping structures, which can be approximated back to the case of one-layer masks with modifications reasoned by cross competition and local search. The derived analytical models indicate the following discoveries. For fully separable problems, mixing with tree-structured masks costs at most twice more evaluations than mixing with perfect models. By problem decomposition and reduction in population, tree-structured masks are more advantageous than disjoint masks on complicated problem structures and large-size subproblems. Although problems with overlapping structures may still decomposed by disjoint masks, the population becomes inefficiently large for adequate initial supply, and hence tree-structured masks usually provide as more suitable decomposition models for these cases.
Subjects
Optimal Mixing
Convergence Complexity
Population Sizing
Convergence Time
Number of Function Evaluations
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-R02921044-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):fb2c092bcb7202fb73d51a801e68f4d7