Published on July 14, 2007
Population Sizing for Entropy-based Model Building in Genetic Algorithms T.-L. Yu1, K. Sastry2, D. E. Goldberg2, & M. Pelikan3 1Department of Electrical Engineering National Taiwan University, Taiwan 2Illinois Genetic Algorithms Laboratory University of Illinois at Urbana-Champaign, IL, USA 3Missouri Estimation of Distribution Algorithms Laboratory University of Missouri at St. Louis, MO, USA Supported by AFOSR FA9550-06-1-0096, NSF DMR 03-25939, and CAREER ECS-0547013.
Motivation • Facetwise population sizing in GEC – Initial supply [Goldberg et al. 2001] – Decision-making [Goldberg et al. 1992] – Gambler’s ruin [Harik et al. 1997] • EDA—Model building is essential. • Population sizing for model building [Pelikan et al. 2003] • Better explanation and modeling are needed.
Roadmap • Entropy-based model building • Mutual information • The effect of selection • Distribution of mutual information under limited sampling • Building an accurate model • The effect of selection pressure • Conclusion
Entropy-based model building & Mutual information • Entropy: measurement of uncertainty. • Loss of entropy Gain in certainty Mutual information • Bivariate: MIMIC, BMDA • Multivariate: eCGA, BOA, EBNA, DSMGA • Most multivariate model building start from bivariate dependency detection.
Mutual information • Definition • Some facts: – –
Base: Bipolar Royal Road • Additively separable bipolar Royal road u 0 k • Given the minimal signal , the most difficult for model building. • Analytical simplicity, no gene-wise bias.
The effect of selection • 00******** and 11******** increase: • 10******** and 01******** decrease: • Define – – •
Growth of schemata and M.I. • • • Growth in mutual information
Limited sampling • In GAs, finite population limited sampling • Define two random variables: – :Signal of mutual information between two independent genes under n random samples. – :Signal of mutual information between two dependent genes under n random samples. • Ideally:
Distribution of mutual information [Hutter and Zaffalon, 2004] • •
Building an accurate model • Define • Decision error • Building an accurate model • Finally
Verification of O(22k) DSMGA, m=10
Verification of O(mlogm) eCGA DSMGA
Effect of selection pressure • Quantitative, order statistics • Qualitative, consider truncation selection • Higher s – More growth of Hopt – Fewer number of effective samples
Empirical results on selection pressure Future work: Empirically, larger k larger s*
Summary and Conclusions • Refine the required population sizing for model building – From – To • Correct to • Preliminarily incorporate selection pressure into population-sizing model. – Qualitatively show the existence of s*
Population Sizing for Entropy-based Model Building in Genetic Algorithms Tian-Li Yu1, Kumara Sastry1, David E. Goldberg1, and Martin Pelikan2 1Illinois ...
Population Sizing for Entropy-based Model Building ... discrete estimation of distribution algorithms. ... Genetic Algorithms, Population Sizing, Model ...
Abstract. This paper presents a population-sizing model for the entropy-based model building in genetic algorithms. Specifically, the population size ...
Population sizing for entropy-based model building in genetic algorithms on ResearchGate, the professional network for scientists.
Population Sizing for Entropy-based Model Building in Genetic Algorithms T.-L. Yu1, K. Sastry2, D. E. Goldberg2, & M. Pelikan3 1Department of Electrical ...
内容提示： Population Sizing for Entropy-based Model Building ... Theory.KeywordsEstimation of Distribution Algorithms, Genetic Algorithms,Population ...
Population sizing for entropy-based model building in discrete estimation of distribution algorithms. ... optimization algorithm, population sizing, ...
... referred to as linkage in genetic algorithms ... as in estimation of distribution algorithms ... a representative population sizing model for discrete ...
Decision making - Goldberg et al. Genetic algorithms, noise, and the sizing of populations, ... Decision making - goldberg et al. genetic algorithms ...