Population sizing for entropy-based model buliding In genetic algorithms

40 %
60 %
Information about Population sizing for entropy-based model buliding In genetic algorithms

Published on July 14, 2007

Author: kknsastry

Source: slideshare.net

Description

This paper presents a population-sizing model for the entropy-based model building in genetic algorithms. Specifically, the population size required for building an accurate model is investigated. The effect of the selection pressure on population sizing is also incorporated. The proposed model indicates that the population size
required for building an accurate model scales as Θ(m log m), where m is the number of substructures and proportional to the problem size. Experiments are conducted to verify the derivations, and the results agree with the proposed model.

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] • •

Empirical verification

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*

Add a comment

Related presentations

Related pages

Population Sizing for Entropy-based Model Building in ...

Population Sizing for Entropy-based Model Building in Genetic Algorithms Tian-Li Yu1, Kumara Sastry1, David E. Goldberg1, and Martin Pelikan2 1Illinois ...
Read more

Population Sizing for Entropy-based Model Building in ...

Population Sizing for Entropy-based Model Building ... discrete estimation of distribution algorithms. ... Genetic Algorithms, Population Sizing, Model ...
Read more

Population Sizing for Entropy-based Model Building in ...

Abstract. This paper presents a population-sizing model for the entropy-based model building in genetic algorithms. Specifically, the population size ...
Read more

Population sizing for entropy-based model building in ...

Population sizing for entropy-based model building in genetic algorithms on ResearchGate, the professional network for scientists.
Read more

Population Sizing for Entropy-based Model Building in ...

Population Sizing for Entropy-based Model Building in Genetic Algorithms T.-L. Yu1, K. Sastry2, D. E. Goldberg2, & M. Pelikan3 1Department of Electrical ...
Read more

population sizing for entropybased model building in ...

内容提示: Population Sizing for Entropy-based Model Building ... Theory.KeywordsEstimation of Distribution Algorithms, Genetic Algorithms,Population ...
Read more

Population sizing for entropy-based model building in ...

Population sizing for entropy-based model building in discrete estimation of distribution algorithms. ... optimization algorithm, population sizing, ...
Read more

Population sizing for inductive linkage identification ...

... referred to as linkage in genetic algorithms ... as in estimation of distribution algorithms ... a representative population sizing model for discrete ...
Read more

Decision making - Goldberg et al. Genetic algorithms ...

Decision making - Goldberg et al. Genetic algorithms, noise, and the sizing of populations, ... Decision making - goldberg et al. genetic algorithms ...
Read more