More Web Proxy on the site http://driver.im/

research-article

Complex energy landscape mapping by histogram assisted genetic algorithm

Authors:

K. Y. SzetoAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 673 - 680

https://doi.org/10.1145/1830483.1830607

Published: 07 July 2010 Publication History

Abstract

A histogram assisted adjustment of fitness distribution in standard genetic algorithm is introduced and tested on four benchmark functions of complex landscapes, with remarkable improvement in performance, such as the substantial enhancement in the probability of detecting local minima. Numerical tests suggest that the idea of histogram assisted adjustment, or the "renormalization" of the fitness distribution, is generally advantageous for multi-modal function optimization. An analysis on the effect of the bin number of the histogram has also been carried out, showing that the performance of the algorithm is insensitive to this extra parameter as long as it is an order of magnitude smaller than the size of the population (N) in the genetic algorithm. This analysis suggests that the advantage of the introduction of histogram assisted fitness adjustment is a robust feature for genetic algorithm, since the adjustment of fitness enhances exploration by broadening the diversity of the population of chromosomes. In general, the advantage of this histogram assisted adjustment more than compensates the cost of computation resource in the construction of the histogram with O(N) time complexity. Suggestions of using this technique for the mapping of complex landscape are discussed.

References

[1]

Holland, J. H. 1975. Adaptation in Natural and Artificial Systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor, MI: University of Michigan Press.

Digital Library

[2]

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

Digital Library

[3]

Li, S. P. and Szeto, K. Y. 1999. Cryptoarithmetic Problem using Parallel Genetic Algorithms. Mendl'99, Brno, Czech.

[4]

Szeto, K. Y. and Cheung, K. H. 1998. Multiple time series prediction using genetic algorithms optimizer. Proceedings of the International Symposium on Intelligent Data Engineering and Learning, Hong Kong, IDEAL'98, 127--133.

[5]

Jiang, R., Szeto, K. Y., Luo, Y. P. and Hu, D. C. 2000 Distributed parallel genetic algorithm with path splitting scheme for the large traveling salesman problems. Proceedings of Conference on Intelligent Information Processing, 16th World Computer Congress 2000, Beijing, Ed. Z. Shi, B. Faltings, and M. Musen, Publishing House of Electronic Industry, 478--285.

[6]

Szeto, K. Y., Cheung, K. H. and Li, S. P. 1998. Effects of dimensionality on parallel genetic algorithms. Proceedings of the 4th International Conference on Information System, Analysis and Synthesis, Orlando, Florida, USA, 2, 322--325.

[7]

Szeto, K. Y. and Fong, L. Y. 2000. How adaptive agents in stock market perform in the presence of random news: a genetic algorithm approach. LNCS/LNAI, Vol. 1983, Ed. K. S. Leung et al. Springer-Verlag, Heidelberg, IDEAL, pages 505--510.

Digital Library

[8]

Fong, A. L. Y. and Szeto, K. Y. 2001. Rule Extraction in Short Memory Time Series using Genetic Algorithms. European Physical Journal B 20, 569--572.

[9]

Shiu, K. L. and Szeto, K. Y. 2008. Self-adaptive Mutation Only Genetic Algorithm: An Application on the Optimization of Airport Capacity Utilization. Proceedings of the International Symposium on Intelligent Data Engineering and Learning 2008, November 2-5, at Daejeon, Korea LNCS5326, pages 428--435, Springer-Verlag.

Digital Library

[10]

Clote, P . 2005. An Efficient Algorithm to Compute the Landscape of Locally Optimal RNA Secondary Structures with Respect to the Nussinov-Jacobson Energy Model. Journal of computational biology 12-1, pages 83--101.

[11]

Šali, A., Shakhnovich, E. and Karplus, M. 1994. How does a protein fold? Nature 369, 248--251.

[12]

Flamm, C., Hofacker, I. L., Stadler, P. F. and Wolfinger, M. T. 2002. Barrier trees of degenerate landscapes. J. Phys.Chem. 216, 155--173.

[13]

Wales, D. J., Miller, M. A. and Walsh, T. R. 1998. Archetypal energy landscapes. Nature 394, 758--760.

[14]

Wales, D. J., Doye, J. P. K. and Miller, M. A. 2000. Energy landscapes: from clusters to biomolecules. Adv.Chem.Phys. 115, 1--111.

[15]

Doye, J. P. K. 2002. Network Topology of a Potential Energy Landscape: A Static Scale-Free Network. Phys. Rev. Lett. 88, 238701.

[16]

Debenedetti, P. G and Stillinger, F. H. 2001. Supercooled liquids and the glass transition. Nature 410, 259--267.

[17]

Singh, G and Deb, K. 2006. Comparison of Multi-Modal Optimization Algorithms Based on Evolutionary Algorithms Gecco'06.

Digital Library

[18]

Goldberg, D. E. and Segrest, P. 1987. Finite Markov chain analysis of genetic algorithms. Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms.

Digital Library

[19]

De Jong, K. 1975. An analysis of the behavior of a class of genetic adaptive systems. PhD, Dissertation, University of Michigan.

Digital Library

[20]

Goldberg, D. E. and Richardson, J. 1987. Genetic algorithms with sharing for multi-modal function optimization. Genetic Algorithm and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms (ICGA-87), pages 44--49.

Digital Library

[21]

Petrowski, A. 1996. A clearing procedure as a niching method for genetic algorithms. Proceedings of Third IEEE International Conference on Evolutionary Computation (ICEC'96), page 798--803. Piscataway, NJ:IEEE Press, 1996.

[22]

Petrowski, A. 1997. An efficient hierarchical clustering technique for speciation. Evolution. In Artificielle-1997, pages 22--24.

[23]

Yin, X. and Germay, N. 1991. Investigations on solving load flow problems by genetic algorithms. In Electric Power System Research, pages 151--163.

[24]

Yin, X. and Germay, N. 1993. A fast genetic algorithm with sharing scheme using cluster analysis methods in multi-modal function optimization. In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, pages 450--457.

[25]

Mahfoud, S. 1992. Crowding and preselection revisited. In Parallel Problem Solving from Nature2, pages 27--37.

[26]

Mahfoud, S. 1995. Niching method for genetic algorithms. Doctoral dissertation. Technical report, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA, Illinois Genetic Algorithms Laboratory (ILLIGAL) report No. 95001.

Digital Library

[27]

Harik, G. R. 1997. Finding multi-modal solutions using restricted tournament selection. In Proceedings of the Algorithms(ICGA-95), pages 24--31.

Digital Library

[28]

Deb, K. and Goldberg, D. E. 1989. An investigation of niche and species formation in genetic function optimization. In Proceedings of the Third International Conference on Genetic Algorithms (ICGA-89), pages 42--50.

Digital Library

[29]

Li, J. P., Balazs, M. E., Parks, G. T. and Clarkson, P. J. 2002. A species conserving genetic algorithms for multi-modal function optimization. Evolutionary Computation, 10, pages 207--234.

Digital Library

[30]

Law, N. L. and Szeto, K. Y. 2007. Adaptive Genetic Algorithm with Mutation and Crossover Matrices; Proceeding of the 12th International Joint Conference on Artificial Intelligence (IJCAI-07) January 6 - 12, 2007 (Volume II) Theme: Al and Its Benefits to Society, Published by International Joint Conferences on Artificial Intelligence, IJCAI-07. Hyderabad, India, pages 2330--2333.

Digital Library

[31]

Zhang, J. and Szeto, K. Y. 2005. Mutation matrix in evolutionary computation: An application to resource allocation problem. Advances in Natural Computation, pt 3, Proceedings, Lecture Notes in Computer Science, 3612, 112.

Digital Library

[32]

Ma, C. W. and Szeto, K. Y. 2004. Locus Oriented Adaptive Genetic Algorithm: Application to the Zero/One Knapsack Problem, Proceeding of The 5th International Conference on Recent Advances in Soft Computing, RASC2004 Nottingham, UK. pages 410--415.

[33]

Schwefel, H.-P. 1981. Numerical optimization of computer models. Chichester: Wiley & Sons.

Digital Library

[34]

Ackley, D. H. 1987. A connectionist machine for genetic hillclimbing. Boston: Kluwer Academic Publishers.

Digital Library

[35]

Bersini, H., Dorigo, M., Langerman, S., Seront, G., and Gambardella, L. 1996. Results of the first international contest on evolutionary optimisation (1st iceo). In Proceedings of IEEE International Conference on Evolutionary Computation, 1996, pages 611--615.

Cited By

Sapin EDe Jong KShehu ANeumann FSutton A(2016)A Novel EA-based Memetic Approach for Efficiently Mapping Complex Fitness LandscapesProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908829(85-92)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908829

Index Terms

Complex energy landscape mapping by histogram assisted genetic algorithm
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an ...
A dual-population genetic algorithm for adaptive diversity control

A variety of previous works exist on maintaining population diversity of genetic algorithms (GAs). Dual-population GA (DPGA) is a type of multipopulation GA (MPGA) that uses an additional population as a reservoir of diversity. The main population is ...
Niche Genetic Algorithm Based on Sexual Reproduction and Multimodal Function Optimization Problem

In this paper, a genetic algorithm with sexual reproduction and niche selection technology is proposed. Simple genetic algorithm has been successfully applied to many evolutionary optimization problems. But there is a problem of premature convergence for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 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: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
191
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sapin EDe Jong KShehu ANeumann FSutton A(2016)A Novel EA-based Memetic Approach for Efficiently Mapping Complex Fitness LandscapesProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908829(85-92)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908829

View Options

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