research-article

Hierarchical allelic pairwise independent functions

Author:

David IclanzanAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 633 - 640

https://doi.org/10.1145/2001576.2001663

Published: 12 July 2011 Publication History

Abstract

Current multivariate EDAs rely on computationally efficient pairwise linkage detection mechanisms to identify higher order linkage blocks. Historical attempts to exemplify the potential disadvantage of this computational shortcut were scarcely successful.

In this paper we introduce a new class of test functions to exemplify the inevitable weakness of the simplified linkage learning techniques. Specifically, we show that presently employed EDAs are not able to efficiently mix and decide between building-blocks with pairwise allelic independent components. These problems can be solved by EDAs only at the expense of exploring a vastly larger search space of multivariable linkages.

References

[1]

S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical report, Pittsburgh, PA, USA, 1994.

Digital Library

[2]

J. S. D. Bonet, C. L. Isbell, and P. A. Viola. MIMIC: Finding optima by estimating probability densities. In M. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems, volume 9, pages 424--430. MIT Press, 1996.

[3]

S.-C. Chen and T.-L. Yu. Difficulty of linkage learning in estimation of distribution algorithms. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, GECCO '09, pages 397--404, New York, NY, USA, 2009. ACM.

Digital Library

[4]

D. J. Coffin and R. E. Smith. Why is parity hard for estimation of distribution algorithms? In GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 624--624, New York, NY, USA, 2007. ACM.

Digital Library

[5]

K. Deb and D. E. Goldberg. Analyzing deception in trap functions. In L. D. Whitley, editor, Foundations of Genetic Algorithms 2, pages 93--108, San Mateo, 1993. Morgan Kaufmann.

[6]

C. Echegoyen, J. A. Lozano, R. Santana, and P. L. uaga. Exact bayesian network learning in estimation of distribution algorithms. In D. Srinivasan and L. Wang, editors, 2007 IEEE Congress on Evolutionary Computation, pages 1051--1058, Singapore, 25--28 Sept. 2007. IEEE Computational Intelligence Society, IEEE Press.

[7]

R. Etxeberria and P. Larranaga. Global optimization using Bayesian networks. In Proceedings of the Second Symposium on Artificial Intelligence (CIMAF-99), pages 151--173, 1999.

[8]

S. Forrest and M. Mitchell. What makes a problem hard for a genetic algorithm? some anomalous results and their explanation. Machine Learning, 13, 1993.

Digital Library

[9]

D. Goldberg. Genetic algorithms and Walsh functions: Part I, a gentle introduction. Complex Systems, 3(2):129--152, 1989.

[10]

D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.

Digital Library

[11]

D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002.

Digital Library

[12]

G. Harik. Linkage learning via probabilistic modeling in the ECGA. Technical Report IlliGAL Report no. 99010, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Feb. 04 1999.

[13]

G. Harik, F. Lobo, and D. Goldberg. The compact genetic algorithm. Evolutionary Computation, IEEE Transactions on, 3(4):287--297, 1999.

Digital Library

[14]

P. Larranaga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Norwell, MA, USA, 2001.

Digital Library

[15]

C. Lima, M. Pelikan, D. Goldberg, F. Lobo, K. Sastry, and M. Hauschild. Influence of selection and replacement strategies on linkage learning in BOA. In Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pages 1083--1090. IEEE, 2007.

[16]

C. Lima, M. Pelikan, K. Sastry, M. Butz, D. Goldberg, and F. Lobo. Substructural neighborhoods for local search in the Bayesian optimization algorithm. pages 232--241. Springer, 2006.

Digital Library

[17]

H. Mühlenbein and R. Höns. The estimation of distributions and the minimum relative entropy principle. Evol. Comput., 13(1):1--27, 2005.

Digital Library

[18]

H. Mühlenbein and T. Mahnig. The factorized distribution algorithm for additively decomposed functions. In P. J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, editors, Proceedings of the Congress on Evolutionary Computation, volume 1, pages 752--759, Mayflower Hotel, Washington D.C., USA, 6--9 July 1999. IEEE Press.

[19]

H. Muhlenbein and G. PaaB. From recombination of genes to the estimation of distributions: I. binary parameters. In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, Parallel Problem Solving From Nature-PPSN IV (4th PPSN'96), volume 1141 of Lecture Notes in Computer Science (LNCS) September 1996, pages 178--187. Springer-Verlag, Berlin, 96.

Digital Library

[20]

M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In L. S. et al., editor, GECCO '01:, pages 511--518, San Francisco, California, USA, 7--11 2001. Morgan Kaufmann.

[21]

M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In W. B. et al., editor, GECCO '99, volume I, pages 525--532, Orlando, FL, 13--17 July 1999. Morgan Kaufmann Publishers, San Fransisco, CA.

[22]

M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. Bayesian optimization algorithm, population sizing, and time to convergence. In L. D. Whitley, D. E. Goldberg, E. Cantú-Paz, L. Spector, I. C. Parmee, and H.-G. Beyer, editors, GECCO, pages 275--282. Morgan Kaufmann, 2000.

[23]

M. Pelikan, D. E. Goldberg, and F. G. Lobo. A survey of optimization by building and using probabilistic models. Comput. Optim. Appl., 21:5--20, January 2002.

Digital Library

[24]

M. Pelikan and H. Muhlenbein. The bivariate marginal distribution algorithm. In R. Roy, T. Furuhashi, and P. K. Chawdhry, editors, Advances in Soft Computing - Engineering Design and Manufacturing, pages 521--535, London, 1999. Springer-Verlag.

[25]

E. Radetic and M. Pelikan. Spurious dependencies and EDA scalability. In Proceedings of the 12th annual conference on Genetic and Evolutionary Computation, GECCO 2010, pages 303--310, New York, NY, USA, 2010. ACM.

Digital Library

[26]

J. Rissanen. Modelling by the shortest data description. Automatica, 14:465--471, 1978.

Digital Library

[27]

R. Santana, P. Larranaga, and J. A. Lozano. Interactions and dependencies in Estimation of Distribution Agorithms. In Proceedings of the 2005 Congress on Evolutionary Computation (CEC-2005), volume 2, pages 1418--1425, Edinburgh, U.K., 2005. IEEE Press.

[28]

K. Sastry, D. E. Goldberg, and X. Llora. Towards billion-bit optimization via a parallel estimation of distribution algorithm. In GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pages 577--584, New York, NY, USA, 2007. ACM.

Digital Library

[29]

H. A. Simon. The Sciences of the Artificial. MIT Press, Cambridge, Massachusetts, first edition, 1969.

[30]

R. A. Watson, G. Hornby, and J. B. Pollack. Modeling building-block interdependency. In PPSN V: Proc. of the 5th International Conference on Parallel Problem Solving from Nature, pages 97--108, London, UK, 1998. Springer, LNCS.

Digital Library

[31]

R. A. Watson and J. B. Pollack. Hierarchically consistent test problems for genetic algorithms: Summary and additional results. In S. Brave, editor, GECCO '99: Late Breaking Papers, pages 292--297, Orlando, Florida, USA, 13 July 1999.

[32]

P. Winward and D. E. Goldberg. Fluctuating crosstalk, deterministic noise, and ga scalability. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, GECCO '06, pages 1361--1368, New York, NY, USA, 2006. ACM.

Digital Library

[33]

H. Wu and J. L. Shapiro. Does overfitting affect performance in estimation of distribution algorithms. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, GECCO '06, pages 433--434, New York, NY, USA, 2006. ACM.

Digital Library

[34]

T.-L. Yu and D. E. Goldberg. Conquering hierarchical difficulty by explicit chunking: substructural chromosome compression. In GECCO 2006:, pages 1385--1392, NY, USA, 2006. ACM Press.

Digital Library

[35]

T.-L. Yu, D. E. Goldberg, A. Yassine, and Y.-P. Chen. Genetic algorithm design inspired by organizational theory: Pilot study of a dependency structure matrix driven genetic algorithm. In Genetic and Evolutionary Computation -- GECCO-2003, volume 2724 of LNCS, pages 1620--1621, Chicago, 12--16 July 2003. Springer-Verlag.

Digital Library

Cited By

Nikanjam AKarshenas H(2016)Multi-structure problems: Difficult model learning in discrete EDAs2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744226(3448-3454)Online publication date: Jul-2016
https://doi.org/10.1109/CEC.2016.7744226
Martins JDelbem A(2016)Pairwise independence and its impact on Estimation of Distribution AlgorithmsSwarm and Evolutionary Computation10.1016/j.swevo.2015.10.00127(80-96)Online publication date: Apr-2016
https://doi.org/10.1016/j.swevo.2015.10.001
Iclanzan DMoore J(2012)Higher-order linkage learning in the ECGAProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330202(265-272)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330202
Show More Cited By

Index Terms

Hierarchical allelic pairwise independent functions
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Hierarchical problem solving with the linkage tree genetic algorithm
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Hierarchical problems represent an important class of nearly decomposable problems. The concept of near decomposability is central to the study of complex systems. When little a priori information is available, a black box problem solver is needed to ...
Overcoming hierarchical difficulty by hill-climbing the building block structure
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

The Building Block Hypothesis suggests that Genetic Algorithms (GAs) are well-suited for hierarchical problems, where efficient solving requires proper problem decomposition and assembly of solution from sub-solution with strong non-linear ...
A linkage-learning niching in estimation of distribution algorithm
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

This work proposes a linkage-learning niching method that improves the capability of estimation of distribution algorithms (EDAs) on reducing spurious linkages which increase problems difficulty. Concatenated parity function (CPF), a class of allelic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikanjam AKarshenas H(2016)Multi-structure problems: Difficult model learning in discrete EDAs2016 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2016.7744226(3448-3454)Online publication date: Jul-2016
https://doi.org/10.1109/CEC.2016.7744226
Martins JDelbem A(2016)Pairwise independence and its impact on Estimation of Distribution AlgorithmsSwarm and Evolutionary Computation10.1016/j.swevo.2015.10.00127(80-96)Online publication date: Apr-2016
https://doi.org/10.1016/j.swevo.2015.10.001
Iclanzan DMoore J(2012)Higher-order linkage learning in the ECGAProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330202(265-272)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330202
Iclanzan DChira C(2012)Modeling and replicating higher-order dependencies in genetic algorithms2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6256648(1-8)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6256648

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents