Cogprints

Evidence of coevolution in multi-objective evolutionary algorithms

Whitacre, Dr James M (2009) Evidence of coevolution in multi-objective evolutionary algorithms. [Conference Paper] (In Press)

Full text available as:

[img]
Preview
 PDF - Draft Version
Available under License Creative Commons Attribution.
227Kb

Abstract

This paper demonstrates that simple yet important characteristics of coevolution can occur in evolutionary algorithms when only a few conditions are met. We find that interaction-based fitness measurements such as fitness (linear) ranking allow for a form of coevolutionary dynamics that is observed when 1) changes are made in what solutions are able to interact during the ranking process and 2) evolution takes place in a multi-objective environment. This research contributes to the study of simulated evolution in a at least two ways. First, it establishes a broader relationship between coevolution and multi-objective optimization than has been previously considered in the literature. Second, it demonstrates that the preconditions for coevolutionary behavior are weaker than previously thought. In particular, our model indicates that direct cooperation or competition between species is not required for coevolution to take place. Moreover, our experiments provide evidence that environmental perturbations can drive coevolutionary processes; a conclusion that mirrors arguments put forth in dual phase evolution theory. In the discussion, we briefly consider how our results may shed light onto this and other recent theories of evolution.

Item Type:Conference Paper
Keywords:coevolution, dual phase evolution, evolutionary algorithms, multi-objective optimization, self-organized criticality
Subjects:Computer Science > Complexity Theory
Biology > Evolution
Computer Science > Artificial Intelligence
ID Code:6573
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] M. J. Eppstein, J. L. Payne, and C. Goodnight, "Sympatric speciation by self-organizing barriers to gene flow in simulated populations with localized mating," in Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, 2006.

[2] J. M. Whitacre, R. A. Sarker, and Q. T. Pham, "The Self-Organization of Interaction Networks for Nature-Inspired Optimization " IEEE Transactions on Evolutionary Computation (accepted March, 2007), 2007.

[3] F. C. Santos and J. M. Pacheco, "Scale-Free Networks Provide a Unifying Framework for the Emergence of Cooperation," Physical Review Letters, vol. 95, p. 98104, 2005.

[4] S. A. Kauffman and S. Johnsen, "Coevolution to the edge of chaos: Coupled fitness landscapes, poised states, and coevolutionary avalanches," J. Theor. Biol., vol. 149, pp. 467-505, 1991.

[5] P. Bak, H. Flyvbjerg, and B. Lautrup, "Coevolution in a rugged fitness landscape," Physical Review A, vol. 46, pp. 6724-6730, 1992.

[6] M. Hall, K. Christensen, S. A. di Collobiano, and H. Jeldtoft Jensen, "Time-dependent extinction rate and species abundance in a tangled-nature model of biological evolution," Physical Review E, vol. 66, p. 11904, 2002.

[7] J. Maynard Smith, "Evolution and the Theory of Games," American Scientist, vol. 64, pp. 41-45, 1976.

[8] S. G. Ficici, O. Melnik, and J. B. Pollack, "A game-theoretic investigation of selection methods used in evolutionary algorithms," Proceedings of the 2000 Congress on Evolutionary Computation (CEC-2000), vol. 2, 2000.

[9] M. A. Potter, "The Design and Analysis of a Computational Model of Cooperative Coevolution," George Mason University, 1997.

[10] W. D. Hillis, "Co-evolving parasites improve simulated evolution as an optimization procedure," Physica D: Nonlinear Phenomena, vol. 42, pp. 228-234, 1990.

[11] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms: Wiley, 2001.

[12] S. G. Ficici and J. B. Pollack, "A game-theoretic approach to the simple coevolutionary algorithm," Parallel Problem Solving from Nature, PPSN-VI, vol. 1917, 2000.

[13] S. G. Ficici and J. B. Pollack, "Pareto Optimality in Coevolutionary Learning," in Advances in Artificial Life: 6th European Conference, ECAL 2001, Prague, Czech Republic, 2001.

[14] J. Noble and R. A. Watson, "Pareto coevolution: Using performance against coevolved opponents in a game as dimensions for Pareto selection," Proceedings of the Genetic and Evolutionary Computation Conference, pp. 493-500, 2001.

[15] E. D. de Jong, "Intransitivity in coevolution," in Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN-04), 2004.

[16] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, "Scalable test problems for evolutionary multi-objective optimization," Evolutionary Multiobjective Optimization, pp. 105–145, 2005.

[17] E. Alba and B. Dorronsoro, "The Exploration/Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms," IEEE Transactions on Evolutionary Computation, vol. 9, pp. 126-142, 2005.

[18] F. Herrera, M. Lozano, and A. M. Sánchez, "Hybrid crossover operators for real-coded genetic algorithms: an experimental study," Soft Computing-A Fusion of Foundations, Methodologies and Applications, vol. 9, pp. 280-298, 2005.

[19] K. A. De Jong, "An Analysis of the Behavior of a Class of Genetic Adaptive Systems," University of Michigan, 1975.

[20] K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan, "A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II," Proceedings of the Parallel Problem Solving from Nature VI Conference, pp. 849-858, 2000.

[21] D. E. Goldberg, K. Deb, and J. Horn, "Massive Multimodality, Deception, and Genetic Algorithms," Parallel Problem Solving from Nature, 2, pp. 37-46, 1992.

[22] P. Bak, C. Tang, and K. Wiesenfeld, "Self-organized criticality: An explanation of the 1/f noise," Physical Review Letters, vol. 59, pp. 381-384, 1987.

[23] P. Bak, C. Tang, and K. Wiesenfeld, "Self-organized criticality," Physical Review A, vol. 38, pp. 364-374, 1988.

[24] B. Drossel, "Biological evolution and statistical physics," Advances in Physics, vol. 50, pp. 209-295, 2001.

[25] J. M. Whitacre, R. Sarker, and Q. T. Pham, "The influence of population topology and historical coupling on Evolutionary Algorithm population dynamics," IEEE Transactions on Evolutionary Computation (submitted September, 2007), 2007.

[26] P. Bak and M. Paczuski, "Complexity, Contingency, and Criticality," Proc. Natl. Acad. Sci. USA, vol. 92, pp. 6689-6696, 1995.

[27] S. A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution: Oxford University Press, 1993.

[28] S. A. Kauffman, "Requirements for evolvability in complex systems: orderly components and frozen dynamics," Physica D, vol. 42, pp. 135–152, 1990.

[29] D. G. Green and D. Newth, "Towards a theory of everything?–Grand challenges in complexity and informatics," Complexity International, vol. 8, p. 1, 2001.

[30] D. G. Green, D. Newth, and M. Kirley, "Connectivity and catastrophe-towards a general theory of evolution," Artificial Life VII: Proceedings of the Seventh International Conference, pp. 153-161, 2000.

[31] D. G. Green, T. G. Leishman, and S. Sadedin, "Dual phase evolution–a mechanism for self-organization in complex systems," in International Conference on Complex Systems (ICCS-2006), 2006.

[32] M. Kirley and D. G. Green, "An empirical investigation of Optimization in Dynamic Environments using the cellular genetic algorithm," Proceedings of Genetic and Evolutionary Computation Conference, 2000.

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.