Convergence Phases, Variance Trajectories, and Runtime Analysis of Continuous EDAs
Presented at the Genetic and Evolutionary Computation Conference, London
Considering the available body of literature on continuous EDAs, one must state that many important questions are still unanswered, e.g.: How do continuous EDAs really work, and how can we increase their efficiency further? The first question must be answered on the basis of formal models, but despite some recent results, the majority of contributions to the field is experimental. The second question should be answered by exploiting the insights that have been gained from formal models. We contribute to the theoretical literature on continuous EDAs by focussing on a simple, yet important, question: How should the variances used to sample offspring from change over an EDA run? To answer this question, the convergence process is separated into three phases and it is shown that for each phase, a preferable strategy exists for setting the variances. It is highly likely that the use of variances that have been estimated with maximum likelihood is not optimal. Thus, variance modification policies are not just a nice add-on. In the light of our findings, they become an integral component of continuous EDAs, and they should consider the specific requirements of all phases of the optimization process.
|ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (acm F.2), SIMULATION AND MODELING (acm I.6)|
|Software (theme 1), Logistics (theme 3), Energy (theme 4)|
|D. Thierens (Dirk)|
|Decision Support Systems for Logistic Networks and Supply Chain Optimization|
|Genetic and Evolutionary Computation Conference|
|Organisation||Intelligent and autonomous systems|
Grahl, J, Bosman, P.A.N, & Minner, S. (2007). Convergence Phases, Variance Trajectories, and Runtime Analysis of Continuous EDAs. In D Thierens (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference (pp. 516–522). ACM Press.