An island model for high-dimensional genomes using phylogenetic speciation and species barcoding

ABSTRACT

A new speciation method for parallel evolutionary computation is presented, designed specifically to handle high-dimensional data. Taking inspiration from the natural sciences, the Phylogenetic Relations Island Speciation Model (PRISM) uses common ancestry and a novel species barcoding system to detect new species and move them to separate islands. Simulation experiments were performed on Multidimensional Knapsack Problems with different fitness landscapes requiring 100-dimensional genomes. PRISM's performance with various parameter settings and on the various landscapes is analyzed and preliminary results show that PRISM can consistently produce optimal or near-optimal solutions, outperforming the standard Genetic Algorithm and Island Model in all the performed experiments.

REFERENCES

• 1: Mourad Bessaou , Alain Pétrowski , Patrick Siarry, Island Model Cooperating with Speciation for Multimodal Optimization, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.437-446, September 18-20, 2000
• 2: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceedings of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 3: 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]
• 4: J. P. Cohoon , S. U. Hegde , W. N. Martin , D. Richards, Punctuated equilibria: a parallel genetic algorithm, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.148-154, October 1987, Cambridge, Massachusetts, United States
• 5: Chris Ding , Xiaofeng He , Hongyuan Zha , Horst D. Simon, Adaptive dimension reduction for clustering high dimensional data, Proceedings of the 2002 IEEE International Conference on Data Mining, p.147, December 09-12, 2002
• 6: M.J. Donoghue. A critique of the biological species concept and recommendations for a phylogenetic alternative. Bryologist, 88(3):171--181, Fall 1985 1985.
• 7: A. Freville. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1--21, May 2004.
• 8: Steven Gustafson , Edmund K. Burke, The speciating island model: an alternative parallel evolutionary algorithm, Journal of Parallel and Distributed Computing, v.66 n.8, p.1025-1036, August 2006 [doi>10.1016/j.jpdc.2006.04.017]
• 9: S. Gustafson, E.K. Burke, and N. Krasnogor. The treestring problem: An artificial domain for structure and content search. In Genetic Programming, Proceedings of the 6th European Conference, volume 3447 of LNCS, pages 215--226. Springer-Verlag, 2005.
• 10: P.D.N. Hebert, A. Cywinska, S.L. Ball, and J.R. Dewaard. Biological identifications through dna barcodes. Proceedings of the Royal Society B: Biological Sciences, 270(1512):313--321, February 2003.
• 11: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 12: Jian-Ping Li , Marton E. Balazs , Geoffrey T. Parks , P. John Clarkson, A species conserving genetic algorithm for multimodal function optimization, Evolutionary Computation, v.10 n.3, p.207-234, Fall 2002 [doi>10.1162/106365602760234081]
• 13: Angel Fernando Kuri Morales , Jesús Gutiérrez-García, Penalty Function Methods for Constrained Optimization with Genetic Algorithms: A Statistical Analysis, Proceedings of the Second Mexican International Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.108-117, April 22-26, 2002
• 14: A. Petrowski and M.G. Genet. A classification tree for speciation. In In Proceedings of CEC 1999, pages 204--211. IEEE Press, 1999.
• 15: Zbigniew Skolicki , Kenneth De Jong, The influence of migration sizes and intervals on island models, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068219]
• 16: S. Via. Sympatric speciation in animals: the ugly duckling grows up. Trends in Ecology and Evolution, 16(7):381--390, July 2001.
• 17: Y. Yang, J. Vincent, and G. Littlefair. A coarse-grained parallel genetic algorithm employing cluster analysis for multi-modal numerical optimisation. In Artificial Evolution, pages 229--240, 2003.

INDEX TERMS

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

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms

Keywords:
genetic algorithms, island model, parallel evolutionary algorithms, phylogenetic species concept, speciation, species barcoding