creators_name: Whitacre, James M creators_name: Sarker, Ruhul A creators_name: Pham, Q. Tuan creators_id: jwhitacre79@yahoo.com type: journalp datestamp: 2009-07-06 09:42:55 lastmod: 2011-03-11 08:57:23 metadata_visibility: show title: The Self-Organization of Interaction Networks for Nature-Inspired Optimization ispublished: pub subjects: comp-sci-complex-theory subjects: comp-sci-art-intel full_text_status: public keywords: Complex Systems, Evolutionary Algorithms, Network Evolution, Optimization, Self-Organization, Sustainable Diversity abstract: Over the last decade, significant progress has been made in understanding complex biological systems, however there have been few attempts at incorporating this knowledge into nature inspired optimization algorithms. In this paper, we present a first attempt at incorporating some of the basic structural properties of complex biological systems which are believed to be necessary preconditions for system qualities such as robustness. In particular, we focus on two important conditions missing in Evolutionary Algorithm populations; a self-organized definition of locality and interaction epistasis. We demonstrate that these two features, when combined, provide algorithm behaviors not observed in the canonical Evolutionary Algorithm or in Evolutionary Algorithms with structured populations such as the Cellular Genetic Algorithm. The most noticeable change in algorithm behavior is an unprecedented capacity for sustainable coexistence of genetically distinct individuals within a single population. This capacity for sustained genetic diversity is not imposed on the population but instead emerges as a natural consequence of the dynamics of the system. date: 2008 date_type: published publication: IEEE Transactions on Evolutionary Computation volume: 12 pagerange: 220-230 refereed: TRUE referencetext: [1] D. E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function optimization,” in Proc. 2nd ICGA, pp. 41-49, 1987. [2] K. A. De Jong, “An analysis of the behavior of a class of genetic adaptive systems,” Doctoral dissertation, Univ. of Michigan, 1975. [3] S. W. Mahfoud, “Niching methods for genetic algorithms,” Ph.D. dissertation, Univ. Illinois at Urbana-Champaign, Illinois Genetic Algorithm Lab., Urbana, IL, 1995. [4] Q. Lü, G. SHEN, and R. YU, “A chaotic approach to maintain the population diversity of genetic algorithm in network training,” Computational Biology and Chemistry, vol. 27, pp. 363-371, 2003. [5] Q. T. Pham, “Competitive evolution: a natural approach to operator selection,” In: Progress in Evolutionary Computation, Lecture Notes in Artificial Intelligence, vol. 956 pp. 49-60, 1995. [6] J. Maresky, Y. Davidor, D. Gitler, G. Aharoni, and A. Barak, “Selectively destructive restart,” in Proc. 6th ICGA, pp 231-239, 1995. [7] V. S. Gordon and L. D. Whitley, “Serial and Parallel Genetic Algorithms as Function Optimizers,” In Proc. 5th ICGA, pp. 177-183, 1993. [8] E. Alba and B. Dorronsoro, “The exploration/exploitation tradeoff in dynamic cellular genetic algorithms,” IEEE Transactions on Evolutionary Computation, vol. 9, no. 2, pp. 126-142, 2005. [9] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. L. Barabási, “Hierarchical organization of modularity in metabolic networks,” Science vol. 297, no. 5586, pp. 1551-1555, 2002. 12 [10] D. Watts, and S. Strogatz, “Collective dynamics of 'small-world' networks,” Nature vol. 393, no. 6684, pp. 440-442, 1998. [11] R. Albert and A. L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol. 74, no. 1, pp. 47-97, 2002. [12] J. L. Payne, and M. J. Eppstein, “Emergent mating topologies in spatially structured genetic algorithms,” In Proc 8th GECCO, pp. 207-214, 2006. [13] M. Giacobini, M. Tomassini, and A, Tettamanzi, “Takeover time curves in random and small-world structured populations,” In Proc 7th GECCO, pp. 1333-1340, 2005. [14] A. L. Barabasi, and Z. N. Oltvai, “Network biology: understanding the cell's functional organization,” Nat Rev Genet. vol. 5, no. 2, pp. 101-130, 2004. [15] M. E. J. Newman, “The structure and function of complex networks,” SIAM Review vol. 45, pp. 167-256, 2003. [16] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. Hwang, “Complex networks: Structure and dynamics,” Physics Reports, vol. 424, no. 4-5, pp. 175-308, 2006. [17] A. L. Barabasi and R. Albert, “The Emergence of Scaling in Random Networks,” Science, vol. 286, no. 5439, pp. 509-512, Oct. 1999. [18] A. Wagner, “Evolution of gene networks by gene duplications: A mathematical model and its implications on genome organization,” In Proc. Natl. Acad. Sci. USA vol. 91, no. 10, pp. 4387-4391, 1994. [19] P. Pollner, G. Palla, and T. Viczek, “Preferential Attachment of Communities: The Same Principle, But at a Higher Level,” Europhysics Letters, vol. 73, no. 3, pp. 478–484, 2006. [20] G. Caldarelli, A. Capocci, P. De Los Rios, and M. A. Munoz, “Scale-free networks from varying vertex intrinsic fitness,” Phys. Rev. Lett. vol. 89, no. 258702, 2002. [21] R. E. Amritkar and S. Jalan, “Coupled dynamics on networks,” Physica A vol. 346, no. 1-2, pp. 13-19, 2005. [22] S. Boccaletti, J. Kurths, G. Osipov, D. L. Valladares, and C.S Zhou, “The synchronization of chaotic systems,” Physics Reports vol. 366, no. 1-2, pp. 1-101, 2002. [23] M. E. Wall, W. S. Hlavacek and M. A. Savageau, “Design of gene circuits: lessons from bacteria,” Nat Rev. Genet. vol. 5, pp. 34-42, 2004. [24] J. Gómez-Gardeñes, Y. Moreno and L. M. Floría, "On the robustness of complex heterogeneous gene expression networks" Biophysical Chemistry vol. 115, no. 225, 2005. [25] M. G. Zimmermann, V. M. Eguíluz, and M. San Miguel, “Coevolution of dynamical states and interactions in dynamic networks,” Phys. Rev. E, vol. 69, no. 065102, 2004. [26] S. A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, Oxford, 1993. [27] H. Aguirre and K. Tanaka, “A study on the behavior of genetic algorithms on NK-Landscapes: Effects of selection, drift, mutation, and recombination,” Trans. IEICE vol. E86A, no. 9, pp. 2270-2279, 2003. [28] N. Geard, J. Wiles, J. Hallinan, B. Tonkes, and B. Skellett, “A comparison of neutral landscapes - NK, NKp and NKq,” In Proc. CEC2002, pp. 205-210, 2002. [29] M. E. J. Newman, and R. Engelhardt, “Effects of neutral selection on the evolution of molecular species,” Working papers 98-01-001, Sante Fe Institute. 1998. [30] B. Drossel, “Biological evolution and statistical physics,” Advances In Physics, vol. 50, no. 2, pp. 209-295, 2001. citation: Whitacre, Dr James M and Sarker, Dr Ruhul A and Pham, Dr Q. Tuan (2008) The Self-Organization of Interaction Networks for Nature-Inspired Optimization. [Journal (Paginated)] document_url: http://cogprints.org/6578/1/Self_Organizing_Topology_Evolutionary_Algorithms_Whitacre.pdf