Cheating for problem solving: a genetic algorithm with social interactions

ABSTRACT

We propose a variation of the standard genetic algorithm that incorporates social interaction between the individuals in the population. Our goal is to understand the evolutionary role of social systems and its possible application as a non-genetic new step in evolutionary algorithms. In biological populations, i.e. animals, even human beings and microorganisms, social interactions often affect the fitness of individuals. It is conceivable that the perturbation of the fitness via social interactions is an evolutionary strategy to avoid trapping into local optimum, thus avoiding a fast convergence of the population. We model the social interactions according to Game Theory. The population is, therefore, composed by cooperator and defector individuals whose interactions produce payoffs according to well known game models (prisoner's dilemma, chicken game, and others). Our results on Knapsack problems show, for some game models, a significant performance improvement as compared to a standard genetic algorithm.

REFERENCES

• 1: Grushin, A. The effects of static fitness function noise upon the performance of genetic algorithms. In Proceedings of the 7th Joint Conference on Information Sciences (JCIS'06) (Kaohsiung, Taiwan, ROC, 2006). Cheng, H. D., Chen, S. D., Lin, R. Y. Atlantis Press, 275--278.
• 2: Hillis, W. D. Co-evolving parasites improve simulated evolution as an optimization procedure, Artificial Life II, SFI Studies in the Science of Complexity, vol. X, edited by C. G. Langton, C. Taylor, J. D. Farmer and S. Rasmussen, Addison-Wesley, pp. 313--324, 1991.
• 3: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 4: P. C. Chu , J. E. Beasley, A Genetic Algorithm for the Multidimensional Knapsack Problem, Journal of Heuristics, v.4 n.1, p.63-86, June 1998 [doi>10.1023/A:1009642405419]
• 5: Vasquez, M., Hao, J.-K.: A hybrid approach for the 0-1 multidimensional knapsackproblem. In Proceedings of the International Joint Conference on Artificial Intelligence 2001, pp. 328--333 (2001).
• 6: Wolf, J., Brodie, E. D., Moore, A. J. Interacting phenotypes and the evolutionary process. II. Selection resulting from social interactions. The American Naturalist 153, 3 (March 1999), 254--266.
• 7: Guozhong An, The effects of adding noise during backpropagation training on a generalization performance, Neural Computation, v.8 n.3, p.643-674, April 1, 1996 [doi>10.1162/neco.1996.8.3.643]
• 8: Travisano, M., Velicer, G. J. Strategies of microbial cheater control. TRENDS in Microbiology 12, 2 (February 2004), 72--78.
• 9: Lenski, R. E., and Velicer, G. J. Games microbes play. Selection 1, 1-3 (2000), 89--95.
• 10: Velicer, G. J. Social strife in the microbial world. TRENDS in Microbiology 11, 7 (July 2003), 330--337.
• 11: Turner, P. E. A virus booster for game theory. ASM News 69, 6 (2003), 289--295.
• 12: Turner, P. E. Cheating viruses and game theory. American Scientist 93, (2005), 428--435.
• 13: Turner, P. E., Chao, L. Escape from Prisoner's dilemma in RNA phage 6. The American Naturalist 161, 3 (March 2003), 497--505.
• 14: Zitzler, E., Laumanns, M. (2008). Swiss Federal Institute of Technology Zurich. Systems Optimization. Test Problem Suite. http://www.tik.ee.ethz.ch/sop/download/supplementary/testProblemSuite/
• 15: Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069--1072. Also available at http://www.ms.ic.ac.uk/ info.html.
• 16: Nowak, M. A. Five rules for the evolution of cooperation. Science 314, 5805 (December 2006), 1560--1563.
• 17: Perc, M. Chaos promotes cooperation in the spatial prisoner's dilemma game. Europhysical Letters 75, 6 (September 2006), 841--846.
• 18: Hamilton, W. D. The Genetical Evolution of Social Behavior. Journal of Theoretical Biology 7, 1 (1964), 1--52.
• 19: Axelrod, R. The Evolution of Cooperation. Basic Books, New York, 1984.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
game theory, genetic algorithms, knapsack problems, social interaction