Cogprints

Survival of the flexible: explaining the dominance of meta-heuristics within a rapidly evolving world

Whitacre, Dr James M (2009) Survival of the flexible: explaining the dominance of meta-heuristics within a rapidly evolving world. [Preprint]

Full text available as:

[img]
Preview
 PDF - Submitted Version
264Kb

Abstract

Although researchers often discuss the rising popularity of meta-heuristics (MH), there has been a paucity of data to directly support the notion that MH are growing in prominence compared to deterministic methods (DM). Here we provide the first evidence that MH usage is not only growing, but indeed appears to have surpassed DM as the algorithm framework of choice for solving optimization problems. Motivated by these findings, this paper aims to review and discuss the origins of meta-heuristic dominance. Explanations for meta-heuristic success are varied, however their robustness to variations in fitness landscape properties is often cited as an important advantage. In this paper, we review explanations for MH popularity and discuss why some of these arguments remain unsatisfying. We argue that a more compelling and comprehensive explanation would directly account for the manner in which most MH success has actually been achieved, e.g. through hybridization and customization to a particular problem environment. This paper puts forth the hypothesis that MH derive much of their utility from being flexible. This flexibility is empirically supported by evidence that MH design can adapt to a problem environment and can integrate domain knowledge. We propose what flexibility means from a search algorithm design context and we propose key attributes that should exist in a flexible algorithm framework. Interestingly, a number of these qualities are observed in robust biological systems. In light of these similarities, we consider whether the origins of biological robustness, (e.g. loose coupling, modularity, partial redundancy) could help to inspire the development of more flexible algorithm frameworks. We also discuss current trends in optimization problems and speculate that highly flexible algorithm frameworks will become increasingly popular within our diverse and rapidly changing world.

Item Type:Preprint
Keywords:decision theory, genetic algorithms, mathematical programming, meta-heuristics, operations research, optimization
Subjects:Computer Science > Complexity Theory
Computer Science > Artificial Intelligence
ID Code:6582
Deposited By: Whitacre, Dr James M
Deposited On:06 Jul 2009 09:42
Last Modified:11 Mar 2011 08:57

References in Article

Select the SEEK icon to attempt to find the referenced article. If it does not appear to be in cogprints you will be forwarded to the paracite service. Poorly formated references will probably not work.

[1] G. S. Hornby and T. Yu, "Results of the First Survey of Practitioners of Evolutionary Computation."

[2] J. T. Alander, "Indexed bibliography of genetic algorithms papers of 1996," Romania, vol. 3, p. 0.80, 1998.

[3] C. Cotta and J. J. Merelo, "Where is evolutionary computation going? A temporal analysis of the EC community," Genetic Programming and Evolvable Machines, vol. 8, pp. 239-253, 2007.

[4] A. L. Barabási and R. Albert, "Emergence of Scaling in Random Networks," Science, vol. 286, p. 509, 1999.

[5] J. H. Holland, "Adaptation in Natural and Artificial System," Ann Arbor: The University of Michigan Press, vol. 20, 1975.

[6] D. E. Goldberg, Genetic algorithms in search, optimization and machine learning: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, 1989.

[7] Q. T. Pham, "Effect of Numerical Errors on the Performance of Optimization Methods," in Proceedings of Chemeca Brisbane, Australia, 2005.

[8] D. B. Fogel, "Introduction to evolutionary computation," Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems, p. 1, 2007.

[9] Y. Jin and J. Branke, "Evolutionary optimization in uncertain environments-a survey," IEEE-TEC, vol. 9, pp. 303-317, 2005.

[10] L. Davis, Handbook of Genetic Algorithms: Van Nostrand Reinhold New York, 1991.

[11] D. E. Goldberg and S. Voessner, "Optimizing global-local search hybrids," Urbana, vol. 51, p. 61801, 1999.

[12] P. Merz and B. Freisleben, "A Comparison of Memetic Algorithms, Tabu Search, and Ant Colonies for the Quadratic Assignment Problem," in congress on evolutionary computation, 1999, pp. 2063-2070.

[13] K. A. De Jong, W. M. Spears, and D. F. Gordon, "Using Markov chains to analyze GAFOs," Foundations of genetic algorithms, vol. 3, pp. 115-137, 1995.

[14] T. Back, U. Hammel, and H. P. Schwefel, "Evolutionary computation: comments on the history and current state," IEEE-TEC, vol. 1, pp. 3-17, 1997.

[15] Z. Michalewicz, "A hierarchy of evolution programs: An experimental study," Evolutionary Computation, vol. 1, pp. 51-76, 1993.

[16] Z. Michalewicz, Genetic algorithms+ data structures= evolution programs: Springer, 1996.

[17] P. P. Bonissone, R. Subbu, N. Eklund, and T. R. Kiehl, "Evolutionary Algorithms+ Domain Knowledge= Real-World Evolutionary Computation," IEEE-TEC, vol. 10, p. 256, 2006.

[18] D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," IEEE-TEC, vol. 1, pp. 67-82, 1997.

[19] K. De Jong, "Evolving in a changing world," Lecture notes in computer science, pp. 512-519, 1999.

[20] H. A. Simon, A Behavioral Model of Rational Choice. Santa Monica: Rand Corp, 1953.

[21] K. E. Weick, K. M. Sutcliffe, and D. Obstfeld, "Organizing and the process of sensemaking," Organization Science, vol. 16, p. 409, 2005.

[22] M. Kirschner and J. Gerhart, "Evolvability," Proc. Natl. Acad. Sci. USA, vol. 95, pp. 8420-8427, 1998.

[23] H. W. Ma and A. P. Zeng, "The connectivity structure, giant strong component and centrality of metabolic networks," Bioinformatics, vol. 19, pp. 1423-1430, 2003.

[24] M. Csete and J. Doyle, "Bow ties, metabolism and disease," Trends Biotechnol., vol. 22, pp. 446-450, 2004.

[25] S. Ciliberti, O. C. Martin, and A. Wagner, "Innovation and robustness in complex regulatory gene networks," Proc. Natl. Acad. Sci. USA, vol. 104, p. 13591, 2007.

[26] A. Wagner, "Robustness and evolvability: a paradox resolved," Proc. R. Soc. Lond., Ser. B: Biol. Sci., vol. 275, pp. 91-100, 2008.

[27] J. Whitacre and A. Bender, "Degeneracy: a design principle for achieving robustness and evolvability," Proceedings of the National Academy of Sciences, USA , (Submitted March, 2009).

[28] J. Whitacre and A. Bender, "Degenerate neutrality creates evolvable fitness landscapes," in WorldComp 2009 (accepted April, 2009), Las Vegas.

Metadata

Repository Staff Only: item control page

Cogprints is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.