creators_name: Whitacre, James M creators_id: jwhitacre79@yahoo.com type: confpaper datestamp: 2009-07-06 09:42:25 lastmod: 2011-03-11 08:57:23 metadata_visibility: show title: Evidence of coevolution in multi-objective evolutionary algorithms ispublished: inpress subjects: comp-sci-complex-theory subjects: bio-evo subjects: comp-sci-art-intel full_text_status: public keywords: coevolution, dual phase evolution, evolutionary algorithms, multi-objective optimization, self-organized criticality 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. date: 2009-07-13 date_type: published refereed: TRUE referencetext: [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. citation: Whitacre, Dr James M (2009) Evidence of coevolution in multi-objective evolutionary algorithms. [Conference Paper] (In Press) document_url: http://cogprints.org/6573/1/Dual_Phase_GEM.pdf