A novel sexual adaptive genetic algorithm based on two-step evolutionary scenario of baldwin effect and analysis of global convergence

ABSTRACT

This work presents a novel sexual adaptive genetic algorithm (NSAGA) based on two-step evolutionary scenario of Baldwin effect to overcome the shortcomings of traditional genetic algorithms, such as premature convergence, stochastic roaming, and poor capabilities in local exploring. NSAGA simulates sexual reproduction in nature and utilizes an effective gender determination method to divide the evolutionary population into two different gender subgroups. Based on the competition, cooperation, and innate differences between two gender subgroups, NSAGA adaptively adjusts the sexual genetic operators. To guide the individuals' evolution, NSAGA adopts a two-step evolutionary scenario: NSAGA guides individuals in niche to forward or reverse evolutionary learning inspired by the acquired reinforcement learning theory based on Baldwin effect, and enables the transmission of fitness information between parents and offspring to supervise the offspring's evolution. Then, the global convergence analysis of NSAGA is presented in detail. It is theoretically proved that NSAGA can converge to the global optimum and the epsilon-optimal solution with probability one. Moreover, numerical simulations are conducted for a set of benchmark test functions, and the performance of NSAGA is compared with that of some evolutionary algorithms published recently. Experiments results show that the proposed algorithm is effective and advantageous.

REFERENCES

• 1: Arnold O. Allen, Probability, statistics, and queueing theory with computer science applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 2: Anderson R. W. 1995. Learning and evolution: a quantitative genetics approach. J THEOR BIOL, 175(1): 89--101.
• 3: Andersson M. 1994. Sexual Selection. Princeton. Princeton University.
• 4: Thomas Bäck, Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms, Oxford University Press, Oxford, 1996
• 5: Baldwin J. M. 1896. A new factor in evolution. AM NAT, 30(3): 441--451.
• 6: Boers E. J. W., Borst M. V., and Sprinkhuizen-Kuyper I. G. 1995. Evolving artificial neural networks using the "Baldwin effect". In Proceedings of International Conference on Artificial Neural Nets and Genetic Algorithms. Al'es, France, pages 333--336.
• 7: Larry Bull, On the Baldwin effect, Artificial Life, v.5 n.3, p.241-246, June 1999 [doi>10.1162/106454699568764]
• 8: Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., University of Michigan, Ann Arbor, MI, 1975
• 9: Dennis C., Gallagher R. 2001. The Human Genome. London: Nature Publishing Group.
• 10: Depew D. 2000. The Baldwin effect: an archaeology. Cybernetics & Human Knowing, 7(1): 7--20.
• 11: Gadagkar R. 1997. Survival Strategies Cooperation and Conflict in Animal Societies. Cambridge: Harvard University Press.
• 12: Kai Song Goh , Andrew Lim , Brian Rodrigues, Sexual Selection for Genetic Algorithms, Artificial Intelligence Review, v.19 n.2, p.123-152, April 2003 [doi>10.1023/A:1022692631328]
• 13: Frédéric Gruau , Darrell Whitley, Adding learning to the cellular development of neural networks: Evolution and the baldwin effect, Evolutionary Computation, v.1 n.3, p.213-233, Fall 1993 [doi>10.1162/evco.1993.1.3.213]
• 14: Herrera F., Lozano M. 2001. Adaptive genetic operators based on coevolution with fuzzy behaviors. IEEE T EVOLUT COMPUT, 5(2): 149--165.
• 15: Hinton G. E., Nowlan S. J. 1987. How learning can guide evolution. Complex Systems, 1: 495--502.
• 16: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 17: Kennedy J., Eberhart R. C. 1997. A discrete binary version of the particle swarm algorithm. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics. Orlando, USA, pages 4104--4108.
• 18: Ku K. W. C. 2006. Enhance the Baldwin effect by strengthening the correlation between genetic operators and learning methods. In Proceedings of IEEE Congr Evol Comput. Vancouver, Canada, pages 3302--3308.
• 19: Lee S., Soak S., Oh S., et al. 2008. Modified binary particle swarm optimization. PROG NAT SCI, 18(9): 1161--1166.
• 20: Lis J., Eiben A. E. 1997. A multi-sexual genetic algorithm for multiobjective optimization. In Proceedings of IEEE International Conference on Evolutionary Computation. Indianapolis, USA, pages 59--64.
• 21: Stefano Nolfi , Domenico Parisi , Jeffrey L. Elman, Learning and evolution in neural networks, Adaptive Behavior, v.3 n.1, p.5-28, Summer 1994 [doi>10.1177/105971239400300102]
• 22: Pampará G., Engelbrecht A. P., and Franken N. 2006. Binary differential evolution. In Proceedings of IEEE Congr Evol Comput. Vancouver, Canada, pages 1873--1879.
• 23: Pampará G., Franken N., and Engelbrecht A. P. 2005. Combining particle swarm optimisation with angle modulation to solve binary problems. In Proceedings of IEEE Congr Evol Comput. Edinburgh, UK, pages 89--96.
• 24: Raghuwanshi M. M., Kakde O. G. 2006. Genetic algorithm with species and sexual selection. In Proceedings of IEEE Conference on Cybernetics and Intelligent Systems. Bangkok, Thailand, pages 1--8.
• 25: Sanchez-Velazco J., Bullinaria J. A. 2003. Sexual selection with competitive/co-operative operators for genetic algorithms. In Proceedings of IASTED International Conference on Neural Networks and Computational Intelligence. Cancun, Mexico, pages 191--196.
• 26: Srinivas M., Patnaik L. M. 1994. Adaptive probabilities of crossover and mutation in genetic algorithm. IEEE T SYST MAN CYB, 24(4): 656--667.
• 27: Stearns S. C, Hoekstra R. F. 2001, Evolution. Oxford: Oxford University Press.
• 28: Suzuki R., Arita T. 2004. Interactions between learning and evolution: outstanding strategy generated by the Baldwin effect. BIOSYSTEMS, 77(1--3): 57--71.
• 29: Reiji Suzuki , Takaya Arita, The Dynamic Changes in Roles of Learning through the Baldwin Effect, Artificial Life, v.13 n.1, p.31-43, Winter 2007 [doi>10.1162/artl.2007.13.1.31]
• 30: Tsoulos I. G. 2008. Modifications of real code genetic algorithm for global optimization. APPL MATH COMPUT, 203(2): 598--607.
• 31: Dana Vrajitoru, Simulating Gender Separation With Genetic Algorithms, Proceedings of the Genetic and Evolutionary Computation Conference, p.634-641, July 09-13, 2002
• 32: Wang Y. P., Dang C. 2007. An evolutionary algorithm for global optimization based on level-set evolution and Latin squares. IEEE T EVOLUT COMPUT, 11(5): 579--595.
• 33: L. Darrell Whitley , V. Scott Gordon , Keith E. Mathias, Lamarckian Evolution, The Baldwin Effect and Function Optimization, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.6-15, October 09-14, 1994
• 34: Zhao W. H., Wang W., and Wang Y. P. 2008. A novel evolutionary algorithm for global numerical optimization with continuous variables. PROG NAT SCI, 18(3): 345--351.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation, Performance

Keywords:
adaptation, baldwin effect, genetic algorithm, global convergence, niche, sexual reproduction