• Articles • Previous Articles     Next Articles

Spatially-Structured Sharing Technique for Multimodal Problems

Grant Dick and Peter Whigham   

  1. Department of Information Science, University of Otago, Dunedin, New Zealand
  • Revised:2007-11-27 Online:2008-01-15 Published:2008-01-10

Spatially-structured populations are one approach to increasing genetic diversity in an evolutionary algorithm (EA). However, they are susceptible to convergence to a single peak in a multimodal fitness landscape. Niching methods, such as fitness sharing, allow an EA to maintain multiple solutions in a single population, however they have rarely been used in conjunction with spatially-structured populations. This paper introduces {\it local sharing}, a method that applies sharing to the overlapping demes of a spatially-structured population. The combination of these two methods succeeds in maintaining multiple solutions in problems that have previously proved difficult for sharing alone (and vice-versa).

Key words: conformance testing; distributed system; CEBE; concurrent TTCN;



[1] Mahfoud S W. Niching methods for genetic algorithms
[Dissertation]. University of Illinois at Urbana-Champaign, Urbana, IL, USA, IlliGAL Report 95001, May 1995. %ftp://ftp-illigal.ge.uiuc.edu/pub/papers/IlliGALs/95001.ps.Z.

[2] Goldberg D E, Richardson J. Genetic algorithms with sharing for multi-modal function optimisation. In -\it Proc. the 2nd Int. Conf. Genetic Algorithms and Their Applications}, Massachusetts, USA, 1987, pp.41--49.

[3] Goldberg D E, Deb K, Horn J. Massive Multimodality, Deception, and Genetic Algorithms. -Parallel Problem Solving from Nature}, 2, M\"-a}nner R, Manderick B (eds.), Amsterdam: Elsevier Science Publishers, B. V., 1992, pp.37--46.

[4]Tomassini M. Spatially Structured Evolutionary Algorithms. %http://infoscience.epfl.ch/search.pyrecid=76398, Springer, 2005. %isbn = -3-540-24193-0},

[5] Spears W M. Simple subpopulation schemes. In -\it Proc. the Third Annual Conf. Evolutionary Programming}, Sebald A V, Fogel L J (eds.), Singapore, World Scientific Press, 1994, pp.296--307.

[6]Holland J H. Adaptation in Natural and Artificial Systems. Cambridge, Massachusetts: The MIT Press, 2ed., 1992.

[7] Deb K, Goldberg D E. An investigation of niche and species formation in genetic function optimization, In -\it Proc. the Third Int. Conf. Genetic Algorithms}, Schaffer J D (ed.), San Mateo, CA, Morgan Kaufmann, 1989, pp.42--50.

[8] Darwen P, Yao Y. Every niching method has its niche: Fitness sharing and implicit sharing compared. In -\it Proc. Parallel Problem Solving from Nature --PPSN IV},Voigt H M, Ebeling W, Rechenberg I, Schwefel H P (eds.), Berlin, Springer, 1996, pp.398--407.

[9] Sareni B, Kr-\"a}henbuhl L. Fitness sharing and niching methods revisited. -\it IEEE Trans. Evolutionary Computation}, 1998, 2(3): 97--106.

[10] Cioppa A D, Stefano C D, Marcelli A. On the role of population size and niche radius in fitness sharing. -\it IEEE Trans. Evolutionary Computation}, 2004, 8(6): 580--592.

[11] Mahfoud S W. Niching methods for genetic algorithms
[Dissertation]. University of Illinois at Urbana-Champaign, Urbana, IL, USA, IlliGAL Report 95001, May 1995.

[12] Horn J. The nature of niching: Genetic algorithms and the evolution of optimal, cooperative populations
[Dissertation]. University of Illinois at Urbana Champaign, Urbana, Illinois, 1997.

[13] Watson J P. A performance assessment of modern niching methods for parameter optimization problems. In -\it Proc. the Genetic and Evolutionary Computation Conference}, Banzhaf W, Daida J, Eiben A E \it et al. \rm (eds.), %Max H. Garzon and Vasant Honavar and Mark Jakiela and Robert E. Smith", Orlando, Florida, USA, vol. 1, Morgan Kaufmann, July 13--17, 1999, pp.702--709.

[14] Miller B L, Shaw M J. Genetic algorithms with dynamic niche sharing for multimodal function optimization. In -\it Proc. International Conference on Evolutionary Computation}, Nayoya University, Japan, 1996, pp.786--791.

[15] P-\'e}trowski A. A clearing procedure as a niching method for genetic algorithms. In -\it Proc. the 1996 IEEE Int. Conf. Evolutionary Computation}, Nayoya University, Japan, 1996, pp.798--803.

[16] Li Jian-Ping, Balazs M E, Parks G T, Clarkson P J. A species conserving genetic algorithm for multimodal function optimization. -\it Evolutionary Computation}, 2002, 10(3): 207--234.

[17] Parrott D, Li Xiao-Dong. Locating and tracking multiple dynamic optima by a particle swarm model using speciation. -\it IEEE Trans. Evolutionary Computation}, 2006, 10(4): 440--458.

[18] Bird S, Li Xiaodong. Adaptively choosing niching parameters in a -PSO}. In -\it Proc. the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO 2006}, Keijzer M, Cattolico M, Arnold D -\it et al.} (eds.), Seattle, Washington, USA, vol 1, ACM Press, July 8--12, 2006, pp.3--10.

[19] Bird S, Li Xiaodong. Enhancing the robustness of a speciation-based -PSO}. In -\it Proc. the 2006 IEEE Congress on Evolutionary Computation}, Yen G G, Lucas S M, Fogel G -\it et al.} (eds.), Vancouver, BC, Canada, IEEE Press, July 16--21, 2006, pp.843--850.

[20] Smith R E, Forrest S, Perelson A S. Searching for diverse, cooperative populations with genetic algorithms. -\it Evolutionary Computation}, 1993, 1(2): 127--149.

[21] Forrest S, Smith R E, Javornik B, Perelson A S. Using genetic algorithms to explore pattern recognition in the immune system. -\it Evolutionary Computation}, 1993, 1(3): 191--211.

[22] Wright S. Isolation by distance. -\it Genetics}, 1943, 28(2): 114--138.

[23] Mayr E. Populations, Species and Evolution; An Abridgment of Animal Species and Evolution. Harvard University Press, 1970.

[24]De Jong K A. An analysis of the behavior of a class of genetic adaptive systems
[Dissertation]. University of Michigan, Ann Arbor, MI, 1975, -\it Dissertation Abstracts International}, University Microfilms Number 76-9381, 36(10): 5140B.

[25] Mahfoud S W. A comparison of parallel and sequential niching methods. In -\it Proc. the Sixth International Conference on Genetic Algorithms}, Eshelman L (ed.), San Francisco, CA, Morgan Kaufmann, 1995, pp.136--143.

[26] Mahfoud S W. Population size and genetic drift in fitness sharing. In -\it Proc. Foundations of Genetic Algorithms 3}, Whitley L D, Vose M D (eds.), San Francisco, Morgan Kaufmann, 1995, pp.185--224.

[27] Baker J E. Reducing bias and inefficiency in the selection algorithm. In -\it Proc. Genetic Algorithms and Their Applications $($ICGA'87$)$}, Grefenstette J J (ed.), Hillsdale, New Jersey, Lawrence Erlbaum Associates, 1987, pp.14--21.

[28] Sarma J. An analysis of decentralized and spatially distributed genetic algorithms
[Dissertation]. George Mason University, Fairfax VA, USA, 1998.

[29]Horn J, Goldberg D E. Genetic algorithm difficulty and the modality of fitness landscapes. In -\it Proc. Foundations of -G}enetic -A}lgorithms 3}, Whitley L D, Vose M D (eds.), Morgan Kaufmann, San Francisco, CA, 1995, pp.243--269.

[30] Beasley D, Bull D R, Martin R R. A sequential niche technique for multimodal function optimization. -\it Evolutionary -C}omputation}, 1993, 1(2): 101--125.

[31]Dick G. A comparison of localised and global niching methods. In -\it Proc. The 17th Annual Colloquium of the Spatial Information Research Centre}, Dunedin, New Zealand, 2005, pp.91--101.

[32] Goldberg D E. A note on -B}oltzmann tournament selection for genetic algorithms and population--oriented simulated annealing. -\it Complex Systems}, 1990, 4(4): 445--460.
[1] Zhimin Gao, Lei Xu, Lin Chen, Xi Zhao, Yang Lu, Weidong Shi. CoC: A Unified Distributed Ledger Based Supply Chain Management System [J]. , 2018, 33(2): 237-248.
[2] Xusheng Xiao, Jian-Guang Lou, Shan Lu, David C. Shepherd, Xin Peng, Qian-Xiang Wang. Roundtable: Research Opportunities and Challenges for Large-Scale Software Systems [J]. , 2016, 31(5): 851-860.
[3] Tao Liu, Yi Liu, Qin Li, Xiang-Rong Wang, Fei Gao, Yan-Chao Zhu, De-Pei Qian. SEIP: System for Efficient Image Processing on Distributed Platform [J]. , 2015, 30(6): 1215-1232.
[4] Jehad Al Dallal and Kassem A. Saleh. Synthesizing Distributed Protocol Specifications from a UML State Machine Modeled Service Specification [J]. , 2012, 27(6): 1150-1168.
[5] Jun-Ki Min, Member, ACM, and Mi-Young Lee. DICE: An Effective Query Result Cache for Distributed Storage Systems [J]. , 2010, 25(5): 933-944.
[6] Yan Li (李 研), Feng-Hong Chen (陈峰宏), Xi Sun (孙 熙), Ming-Hui Zhou (周明辉), Member, CCF| Wen-Pin Jiao (焦文品), Senior Member, CCF, Dong-Gang Cao (曹东刚) and Hong Mei (梅 宏), Senior Member, CCF. Self-Adaptive Resource Management for Large-Scale Shared Clusters [J]. , 2010, 25(5): 945-957.
[7] Anna Gutowska, Andrew Sloane, and Kevan A. Buckley. On Desideratum for B2C E-Commerce Reputation Systems [J]. , 2009, 24(5): 820-832.
[8] Chao Cai, Zong-Yan Qiu, Senior Member, CCF, Member, IEEE, Hong-Li Yang, and Xiang-Peng Zhao. Global-to-Local Approach to Rigorously Developing Distributed System with Exception Handling [J]. , 2009, 24(2): 238-249.
[9] Hua-Ming Liao and Guo-Shun Pei. Cache-Based Aggregate Query Shipping: An Efficient Scheme of Distributed OLAP Query Processing [J]. , 2008, 23(6 ): 905-915 .
[10] Ren-Yi Xiao. Survey on Anonymity in Unstructured Peer-to-Peer Systems [J]. , 2008, 23(4 ): 660-671 .
[11] Zhi-Wei Xu, Hao-Jie Zhou, and Guo-Jie Li. Usability Issues of Grid System Software [J]. , 2006, 21(5): 641-647 .
[12] Jian-Yang Zeng and Wen-Jing Hsu. Optimal Routing in a Small-World Network [J]. , 2006, 21(4): 476-481 .
[13] Ian Foster. Globus Toolkit Version 4: Software for Service-Oriented Systems [J]. , 2006, 21(4): 513-520 .
[14] WEI Xiaohui; JU Jiubin;. SFT: A Consistent Checkpointing Algorithm with Short Freezing Time [J]. , 2000, 15(2): 169-175.
[15] BI Jun; WU Jianping;. An Approach to Concurrent TTCN Test Generation [J]. , 1999, 14(6): 614-618.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved