Regular PapersNo Access

EFFECTS OF ADAPTIVE SOCIAL NETWORKS ON THE ROBUSTNESS OF EVOLUTIONARY ALGORITHMS

Birmingham University, School of Computer Science, Edgbaston, Birmingham, B15 2TT, UK

University of New South Wales at the Australian Defence Force Academy, School of Information Technology and Electrical Engineering, Canberra 2600, Australia

Search for more papers by this author

, and

Q. TUAN PHAM

University of New South Wales, School of Chemical Sciences and Engineering, Sydney, 2052, Australia

Search for more papers by this author

https://doi.org/10.1142/S0218213011000322Cited by:4 (Source: Crossref)

Abstract

Biological networks are structurally adaptive and take on non-random topological properties that influence system robustness. Studies are only beginning to reveal how these structural features emerge, however the influence of component fitness and community cohesion (modularity) have attracted interest from the scientific community. In this study, we apply these concepts to an evolutionary algorithm and allow its population to self-organize using information that the population receives as it moves over a fitness landscape. More precisely, we employ fitness and clustering based topological operators for guiding network structural dynamics, which in turn are guided by population changes taking place over evolutionary time. To investigate the effect on evolution, experiments are conducted on six engineering design problems and six artificial test functions and compared against cellular genetic algorithms and panmictic evolutionary algorithm designs. Our results suggest that a self-organizing topology evolutionary algorithm can exhibit robust search behavior with strong performance observed over short and long time scales. More generally, the coevolution between a population and its topology may constitute a promising new paradigm for designing adaptive search heuristics.

Keywords:

Remember to check out the Most Cited Articles!
Check out Notable Titles in Artificial Intelligence.

References

H. Sayamaet al., Physical Review E 65(5), 51919 (2002), DOI: 10.1103/PhysRevE.65.051919. Web of Science, Google Scholar
M. C. Boerlijst and P. Hogeweg, Physica D 48(1), 17 (1991). Web of Science, Google Scholar
M. J. Eppstein , J. L. Payne and C. Goodnight , Sympatric speciation by self-organizing barriers to gene flow in simulated populations with localized mating , Proceedings of the Genetic and Evolutionary Computation Conference ( Seattle , 2006 ) . Google Scholar
J. M. Whitacre, R. A. Sarker and Q. T. Pham, IEEE Transactions on Evolutionary Computation 12(2), 220 (2008), DOI: 10.1109/TEVC.2007.900327. Web of Science, Google Scholar
F. C. Santos and J. M. Pacheco, Physical Review Letters 95(9), 98104 (2005), DOI: 10.1103/PhysRevLett.95.098104. Web of Science, Google Scholar
J. Gómez-Gardenes, Y. Moreno and L. M. Floriá, Biophysical Chemistry 115, 225 (2005). Web of Science, Google Scholar
S. A. Kauffman, Physica D 42, 135 (1990). Web of Science, Google Scholar
G. S. Hornby , ALPS: The age-layered population structure for reducing the problem of premature convergence , Proceedings of the Genetic and Evolutionary Computation Conference . Google Scholar
S. W. Mahfoud, Conference on Genetic Algorithms 136, 143 (1995). Google Scholar
E. Albaet al., Parallel Computing 30(5-6), 699 (2004). Web of Science, Google Scholar
J. Sarma and K. A. De Jong, Parallel Problem Solving from Nature 1141, 236 (1996). Google Scholar
B. Dorronsoroet al., CEC2004 Congress on Evolutionary Computation 2, (2004). Google Scholar
M. Giacobiniet al., IEEE Transactions on Evolutionary Computation 9(5), 489 (2005), DOI: 10.1109/TEVC.2005.850298. Web of Science, Google Scholar
M. Preuss and C. Lasarczyk, Lecture Notes in Computer Science 91 (2004), DOI: 10.1007/978-3-540-30217-9_10. Google Scholar
M. Giacobini , M. Tomassini and A. Tettamanzi , Takeover time curves in random and small-world structured populations , GECCO ( ACM , New York, NY, USA , 2005 ) . Google Scholar
M. Giacobini, M. Preuss and M. Tomassini, Lecture Notes in Computer Science 3906, 86 (2006), DOI: 10.1007/11730095_8. Google Scholar
E. Ravaszet al., Science 297, 1551 (2002), DOI: 10.1126/science.1073374. Web of Science, Google Scholar
D. J. Watts and S. H. Strogatz, Nature 393(6684), 409 (1998), DOI: 10.1038/30918. Web of Science, Google Scholar
R. Albert and A. L. Barabási, Reviews of Modern Physics 74(1), 47 (2002), DOI: 10.1103/RevModPhys.74.47. Web of Science, Google Scholar
H. Kitano, Nature Reviews Genetics 5(11), 826 (2004), DOI: 10.1038/nrg1471. Web of Science, Google Scholar
C. H. Waddington, Evolution 7(2), 118 (1953), DOI: 10.2307/2405747. Web of Science, Google Scholar
A. A. Agrawal, Science 294(5541), 321 (2001), DOI: 10.1126/science.1060701. Web of Science, Google Scholar
E. Alba and B. Dorronsoro, IEEE Transactions on Evolutionary Computation 9(2), 126 (2005), DOI: 10.1109/TEVC.2005.843751. Web of Science, Google Scholar
S. Boccalettiet al., Physics Reports 424(4-5), 175 (2006). Web of Science, Google Scholar
M. E. J. Newman, SIAM Review 45, 167 (2003), DOI: 10.1137/S003614450342480. Web of Science, Google Scholar
A. L. Barabási and Z. N. Oltvai, Nature Reviews Genetics 5(2), 101 (2004). Web of Science, Google Scholar
P. Erdös and A. Rényi, Publ. Math. Debrecen 6, 290 (1959). Crossref, Google Scholar
P. Erdös and A. Rényi, Bulletin of the Institute of International Statistics 38, 343 (1961). Google Scholar
A. L. Barabási and R. Albert, Science 286(5439), 509 (1999). Web of Science, Google Scholar
A. Wagner, Proceedings of the National Academy of Sciences, USA 91(10), 4387 (1994), DOI: 10.1073/pnas.91.10.4387. Web of Science, Google Scholar
G. Caldarelliet al., Physical Review Letters 89(25), 258702 (2002), DOI: 10.1103/PhysRevLett.89.258702. Web of Science, Google Scholar
A. Vazquez, Physical Review E 67(5), 56104 (2003). Web of Science, Google Scholar
P. Pollner, G. Palla and T. Vicsek, Europhysics Letters 73(3), 478 (2006), DOI: 10.1209/epl/i2005-10414-6. Google Scholar
E. Alba and M. Tomassini, IEEE Transactions on Evolutionary Computation 6(5), 443 (2002), DOI: 10.1109/TEVC.2002.800880. Web of Science, Google Scholar
Whitacre, J. M., Adaptation and self-organization in evolutionary algorithms, PhD Thesis, University of New South Wales (2007), p. 283 . Google Scholar
T. P. Runarsson and X. Yao, IEEE Transactions on Evolutionary Computation 4(3), 284 (2000), DOI: 10.1109/4235.873238. Web of Science, Google Scholar
Y. C. Lin, F. S. Wang and K. S. Hwang, Congress on Evolutionary Computation 3, (1999). Google Scholar
C. A. C. Coello, Congress on Evolutionary Computation 1, (1999). Google Scholar
S. Y. Zeng, L. X. Ding and L. S. Kang, An evolutionary algorithm of contracting search space based on partial ordering relation for constrained optimization problems, Proceedings of the Conference on Algorithms and Architectures for Parallel Processing (2002) pp. 76–81. Google Scholar
E. Sandgren, Journal of Mechanical Design 112(2), 223 (1990), DOI: 10.1115/1.2912596. Web of Science, Google Scholar
Y. Liet al., International Journal of Computer Mathematics 79(5), 523 (2002), DOI: 10.1080/00207160210947. Web of Science, Google Scholar
J. Fu, R. G. Fenton and W. L. Cleghorn, Engineering Optimization 17(4), 263 (1991). Google Scholar
B. K. Kannan and S. N. Kramer, ASME 65, 103 (1993). Google Scholar
Y. J. Cao and Q. H. Wu, Mechanical design optimization by mixed-variable evolutionary programming, Proceedings of the Conference on Evolutionary Computation (1997) (1997) pp. 443–446. Google Scholar
K. Deb, AIAA Journal 29(11), 2013 (1991), DOI: 10.2514/3.10834. Web of Science, Google Scholar
R. N. Sauer, A. R. Colville and C. W. Burwick, Hydrocarbon Processing 84(2), (1964). Google Scholar
B. V. Babu and R. Angira, Computers and Chemical Engineering 30(6), 989 (2006). Web of Science, Google Scholar
J. Bracken and G. P. McCormick , Selected Applications of Nonlinear Programming ( Wiley , New York , 1968 ) . Google Scholar
C. D. Maranas and C. A. Floudas, Computers and Chemical Engineering 21(4), 351 (1997), DOI: 10.1016/S0098-1354(96)00282-7. Web of Science, Google Scholar
C. S. Adjiman, I. P. Androulakis and C. A. Floudas, Computers and Chemical Engineering 22, 1159 (1998), DOI: 10.1016/S0098-1354(98)00218-X. Web of Science, Google Scholar
T. F. Edgar , D. M. Himmelblau and L. S. Lasdon , Optimization of Chemical Processes ( McGraw-Hill , 2001 ) . Google Scholar
C. A. Floudas and P. M. Pardalos , A Collection of Test Problems for Constrained Global Optimization Algorithms ( Springer , 1990 ) . Google Scholar
R. Angira and B. V. Babu , Evolutionary computation for global optimization of non-linear chemical engineering processes , Proceedings of International Symposium on Process Systems Engineering and Control (ISPSEC'03) – For Productivity Enhancement through Design and Optimization ( Mumbai , 2003 ) . Google Scholar
A. Belegundu and J. Arora, International Journal for Numerical Methods in Engineering 21, 1583 (1985), DOI: 10.1002/nme.1620210904. Web of Science, Google Scholar
J. S. Arora , Introduction to Optimum Design ( McGraw-Hill , 1989 ) . Google Scholar
J. M. Whitacre, R. A. Sarker and Q. T. Pham, Memetic Computing 1(2), 125 (2009), DOI: 10.1007/s12293-009-0009-8. Web of Science, Google Scholar
A. Lesne, Letters in Mathematical Physics 78(3), 235 (2006), DOI: 10.1007/s11005-006-0123-1. Web of Science, Google Scholar