모집단 모델(진화 알고리즘)

Population model (evolutionary algorithm)

진화 알고리듬(EA)의 모집단 모델은 구성원이 속한 모집단의 구조적 특성을 설명합니다.모집단은 한 번의 반복에서 고려된 EA의 모든 제안 솔루션 집합이며, 생물학적 역할 모델에 따라 개별이라고도 합니다.개체군의 개체는 절차의 유전자 조작자의 도움을 받아 자손으로 더 많은 개체를 생성할 수 있습니다.

EA에서 가장 단순하고 널리 사용되는 모집단 모델은 구조화되지 [1][2]않은 모집단에 해당하는 전역 또는 범유행 모델입니다.그것은 각 개인이 교차에 의한 자손 생산을 위한 파트너로서 인구의 다른 개인을 선택할 수 있게 해주며, 개인의 적합성이 중요한 역할을 하는 한 선택의 세부 사항은 관련이 없습니다.전지구적 짝짓기 선택으로 인해, 이 단계에서 더 나은 다른 자손이 나타나지 않는다면, 훨씬 더 나은 개체의 유전 정보는 몇 세대 후 개체군에서 우세할 수 있습니다(EA의 반복).이러한 방식으로 발견된 솔루션이 최적의 솔루션이 아닌 경우 [3]조기 수렴이라고 합니다.이 효과는 전염병 집단에서 [4]더 자주 관찰될 수 있습니다.

자연에서는 전역 짝짓기 풀을 거의 찾을 수 없습니다.우세한 것은 공간적 거리로 인한 확실하고 제한적인 고립입니다.그 결과 지역 이웃은 처음에는 독립적으로 진화하고 돌연변이는 몇 세대에 걸쳐 지속될 가능성이 더 높습니다.결과적으로, 유전자 풀의 유전자형 다양성은 전염병 집단보다 더 오래 보존됩니다.

따라서 이전의 세계 인구를 하위 구조로 나누는 것은 분명합니다.이를 위해 두 가지 기본 모델이 도입되었는데, 이는 인구를 때때로 개인을 교환하는 고정 하위 집단으로 나누는 것을 기반으로 하는 섬 모델과 [1][5] 개인을 겹치는 이웃에 할당하는 이웃 모델이다,[4][6] 세포 유전 또는 진화 알고리즘(cGA 또는 cEA)으로도 알려져 있다.[7][7][8]모집단의 연관된 분할은 절차의 상응하는 병렬화를 제안합니다.이러한 이유로, 인구 [1][2][4][5][9][10]모델의 주제는 EA의 병렬화와 관련하여 문헌에서도 자주 논의됩니다.

섬 모형

8개의 섬과 2개의 인접 구조물로 구성된 섬 모델의 예: 단순한 단방향 링(검은 화살표) 및 보다 복잡한 구조물(녹색 및 검은색 화살표)

이주 모델 또는 거친 입자 모델이라고도 불리는 섬 모델에서 진화는 엄격하게 분할된 하위 집단에서 발생합니다.이것들은 범유행적으로 조직될 수 있지만, 그럴 필요는 없습니다.때때로 개인의 교환이 일어나는데,[2][5] 이것을 이주라고 합니다.교환 사이의 시간을 에포크(epoch)라고 하며 교환 종료는 다양한 기준에 의해 트리거될 수 있습니다. 예를 들어 주어진 시간 또는 완료된 세대 수 또는 정체 발생 후입니다.예를 들어, 특정 세대 동안 섬에서 체력 향상이 일어나지 않았다는 사실로 정체를 감지할 수 있습니다.아일랜드 모델은 다양한 새로운 전략 [11][12][13][14]매개변수를 도입합니다.

  • 하위 모집단 수
  • 하위 모집단의 크기
  • 섬들 간의 이웃 관계: 그들은 어떤 섬들이 이웃하는 것으로 간주되는지를 결정하고, 따라서 개인을 교환할 수 있습니다. 단순한 단방향 링(검은색 화살표)의 그림과 추가적인 양방향 이웃 관계(녹색 화살표)에 의한 확장을 참조하십시오.
  • epoch, 동기 또는 비동기 마이그레이션 종료 기준
  • 마이그레이션 속도: 마이그레이션에 참여한 개인의 수 또는 비율입니다.
  • 이주자 선택:이에 대한 대안은 많이 있습니다.예: 가장 우수한 개인이 최악의 개인 또는 무작위로 선택된 개인을 대체할 수 있습니다.마이그레이션 속도에 따라 한 번에 한 명 이상의 개인에게 영향을 미칠 수 있습니다.

이러한 파라미터를 사용하면 선택 압력에 상당한 영향을 미칠 수 있습니다.예를 들어, 섬의 상호 연결에 따라 증가하고 하위 모집단의 수 또는 에포크 길이에 따라 감소합니다.

인접 모델 또는 셀룰러 진화 알고리즘

두 개의 예시적인 2차원 이웃 도형(왼쪽)이 있는 토러스 구조(오른쪽).개인 A와 B의 블록 모양 데임은 노란색으로 표시된 두 개의 공통 이웃을 가지고 있습니다.

확산 모델 또는 세분화 모델이라고도 불리는 이웃 모델은 표현형 특성과 독립적인 모집단의 개체 간의 위상적 이웃 관계를 정의합니다.이 모델의 기본 아이디어는 각 정점이 가장 가까운 이웃과 통신하는 [2][6]개체인 연결 그래프로 정의된 특수 구조를 EA 모집단에 제공하는 것입니다.특히, 개체는 개념적으로 토로이드 메시에 설정되어 있으며, 가까운 개체와 재결합만 허용됩니다.이것은 [6][7]거리에 의한 격리로 알려진 일종의 지역성으로 이어집니다.개인의 잠재적인 짝들의 집합을 그것의 이웃 또는 태도라고 합니다.인접한 그림은 노란색으로 표시된 두 개체의 두 개의 약간 겹치는 이웃을 보여줌으로써 유전 정보가 두 데임 사이에 퍼질 수 있음을 보여줍니다.이런 종류의 알고리즘에서 유사한 개인들이 군집화되고, dem 경계와 독립적이고, 특히 [6][7]dem보다 클 수 있는 틈새를 만드는 경향이 있는 것으로 알려져 있습니다.인접 그룹 간에는 명확한 경계가 없으며, 이 과정에서 경쟁 그룹에 의해 쉽게 식민지화될 수 있으며 솔루션 내용을 병합할 수도 있습니다.동시에, 더 먼 틈새는 [6][7]더 천천히 영향을 받을 수 있습니다.이러한 유형의 개체군을 가진 EA는 세포 EA(cellular EA)[8][15] 또는 세포 유전 알고리즘(cGA)[7][16]으로도 잘 알려져 있습니다.

2차원 세포 EA에서 demes라고도 불리는 이웃의 예: 선형, 소형, 다이아몬드 및...다른 어떤 것도
EA의 1차원 고리 모양 이웃 모델의 이웃(뎀)이 겹치는 두 가지 예.개체 X와 Y의 두 개의 대퇴부는 최소로 겹치는 반면, A와 B의 대퇴부는 최대로 겹칩니다.

모집단의 개체를 배열하는 데 일반적으로 사용되는 구조는 2D 토로이드 [1][2][15]그리드이지만 치수 수는 쉽게 확장(3D로)하거나 축소(예: 1D, 고리,[6][15] 오른쪽 그림 참조)할 수 있습니다.그리드에서 특정 개인의 이웃은 인구 내 다른 개인과의 맨해튼 거리로 정의됩니다.기본 알고리즘에서, 모든 이웃들은 같은 크기와 같은 모양을 가지고 있습니다.2차원 cEA에 가장 일반적으로 사용되는 두 개의 이웃은 L5와 C9입니다. 왼쪽 그림을 참조하십시오.여기서 L은 선형을, C는 압축을 나타냅니다.각각의 품행은 부모를 대체함으로써 짝을 선택하고 자손을 받아들이는 범유행적인 하위 집단을 나타냅니다.자손을 받아들이는 규칙은 본질적으로 지역적이고 이웃을 기반으로 합니다. 예를 들어, 최고의 자손은 교체되는 부모보다 더 낫거나, 덜 엄격하게는,[2][6] 태도에서 최악의 개인보다 더 나아야 한다고 지정할 수 있습니다.첫 번째 규칙은 엘리트주의이고 두 번째 비 엘리트주의 규칙보다 더 높은 선택적 압력을 만듭니다.엘리트주의 EA에서는 모집단의 최고 개체가 항상 생존합니다.이런 점에서, 그들은 생물학적 모델에서 벗어납니다.

이웃의 중첩은 유전 정보가 이웃 경계를 넘어 대부분 느리게 확산되는 원인이 되며, 따라서 확산 모델이라는 이름이 붙습니다.더 나은 자손들은 이제 인구에 퍼지기 위해서는 팬믹스보다 더 많은 세대가 필요합니다.이것은 지역 틈새의 출현과 지역 진화를 촉진하여 유전자형 다양성을 더 오랜 기간 동안 보존합니다.그 결과, 실행 중 검색 공간에 적합한 폭 검색과 깊이 검색 간의 보다 효과적이고 동적인 균형이 유지됩니다.깊이 탐색은 틈새 경계의 틈새와 폭 탐색에서 그리고 전체 [17]인구의 다양한 틈새의 진화를 통해 이루어집니다.동일한 이웃 크기의 경우, 유전 정보의 확산은 C9와 같은 블록보다 L9와 같은 길쭉한 도형에 대해 더 크며,[18] 고리에 대해서도 훨씬 더 큽니다.이는 링 이웃이 비교적 긴 실행 시간이 필요하더라도 고품질 결과를 달성하는 데 적합하다는 것을 의미합니다.반면에, 주로 빠르고 좋은 결과에 관심이 있지만 최적이 아닐 수도 있는 경우 2D 토폴로지가 더 적합합니다.

비교

두[18][19] 모집단 모델을 유전 알고리즘,[5][6] 진화 전략 [20][21]및 기타 EA에 모두 적용할 때, 전체 모집단을 하위 모집단으로 분할하는 것은 일반적으로 조기 수렴의 위험을 줄이고 전염병 EA에서 예상되는 것보다 전반적으로 더 안정적이고 빠른 결과로 이어집니다.

섬 모델은 이웃 모델에 비해 많은 수의 새로운 전략 매개 변수를 도입한다는 단점이 있습니다.문헌에서 [11][22][23]이 주제에 대한 기존 연구에도 불구하고 사용자에게 불리한 설정의 특정 위험이 남아 있습니다.반면, 이웃 모델의 경우 이웃의 크기만 지정하면 되며, 2차원 모델의 경우 이웃 도형의 선택이 추가됩니다.

병렬화

두 모집단 모델 모두 모집단 분할을 의미하기 때문에 [5][10][24]EA를 병렬화하기 위한 기준으로 적합합니다.셀룰러 EA는 각 뎀 구성원에 대한 로컬 정보에만 의존하기 때문에 이는 셀룰러 EA에 훨씬 더 많이 적용됩니다.따라서 극단적인 경우에는 각 개인에게 독립적인 실행 스레드를 할당하여 전체 cEA를 병렬 하드웨어 [6][25][26]플랫폼에서 실행할 수 있습니다.또한 섬 모델은 병렬화를 지원합니다. 예를 들어 각 섬에 프로세서를 할당합니다.섬의 하위 집단이 범유행적으로 구성되면 한 세대의 후손에 대한 모든 평가를 [9][14][27]추가로 병렬화할 수 있습니다.실제 애플리케이션에서 평가는 일반적으로 가장 많은 시간이 소요되는 부분입니다.물론, 병렬화 cEA에 대한 이전의 진술이 적용되도록 섬 하위 집단을 cEA로 설계하는 것도 가능합니다.이러한 방식으로 적절한 병렬화를 가진 계층적 모집단 구조를 [9]만들 수 있습니다.비교적 비싼 컴퓨터 클러스터뿐만 아니라 저렴한 그래픽 카드(GPU)도 [28][29]병렬화에 사용할 수 있습니다.

그러나 cEA, 즉 섬 전체에 분포하는 인구가 있는 EA는 기존 EA와 여러 면에서 다른 검색 모델을 나타낸다는 점을 강조하는 것이 중요합니다.또한 순차적 플랫폼과 병렬 플랫폼 모두에서 실행할 수 있으며, 이는 모델과 구현이 서로 다른 개념이라는 사실을 강조합니다.

서지학

  • 에릭 칸투파즈 (2001):효율적이고 정확한 병렬 유전 알고리즘(미국 일리노이 대학교 Urbana-Champaign, 박사 논문).뉴욕 스프링거입니다. ISBN978-1-4613-6964-6doi:10.1007/978-1-4615-4369-5
  • 마르티나 고르제스-슐뢰터 (1990):유전자 알고리즘과 모집단 구조 - 대규모 병렬 알고리즘.박사학위 논문, 도르트문트 대학교, Fakultät für Informatik, 독일
  • 엔리케 알바, 베르나베 도론소로 (2008):세포 유전 알고리즘.뉴욕 스프링거, 뉴욕. ISBN 978-0-387-77609-5 도이:10.1007/978-0-387-77610-1
  • 더크 서드홀트 (2015):병렬 진화 알고리즘.Janusz Kacprzyk에서 Witold Pedrycz (ed.): 병렬 진화 알고리듬.스프링거, 베를린, 하이델베르크, 929–959 ISBN 978-3-662-43504-5 도이: 10.1007/978-3-662-43505-246
  • 가브리엘 루케, 엔리케 알바 (2011):병렬 유전 알고리즘.베를린 하이델베르크의 스프링거입니다.ISBN 978-3-642-22083-8 도이:10.1007/978-3-642-22084-5

참고 항목

레퍼런스

  1. ^ a b c d Cantú-Paz, Erik (1998). "A survey of parallel genetic algorithms" (PDF). Calculateurs Paralleles. 10 (2): 141–171.
  2. ^ a b c d e f Gordon, V.S.; Whitley, D. (1993), Forrest, S. (ed.), "Serial and Parallel Genetic Algorithms as Function Optimizers" (PDF), Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, CA: Morgan Kaufmann, pp. 177–183, ISBN 978-1-55860-299-1
  3. ^ Leung, Yee; Gao, Yong; Xu, Zong-Ben (1997). "Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis". IEEE Transactions on Neural Networks. 8 (5): 1165–1176. doi:10.1109/72.623217. ISSN 1045-9227. PMID 18255718.
  4. ^ a b c Gorges-Schleuter, Martina (1990). Genetic Algorithms and Population Structures - A Massively Parallel Algorithm (PhD). Universität Dortmund, Fakultät für Informatik, Germany.
  5. ^ a b c d e Cantú-Paz, Erik (1999). Efficient and Accurate Parallel Genetic Algorithms (PhD thesis, University of Illinois, Urbana-Champaign, USA). Genetic Algorithms and Evolutionary Computation. Vol. 1. Springer, New York, NY. doi:10.1007/978-1-4615-4369-5. ISBN 978-1-4613-6964-6.
  6. ^ a b c d e f g h i Gorges-Schleuter, Martina (1991), Schwefel, Hans-Paul; Männer, Reinhard (eds.), "Explicit parallelism of genetic algorithms through population structures", Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Berlin/Heidelberg: Springer-Verlag, vol. 496, pp. 150–159, doi:10.1007/bfb0029746, ISBN 978-3-540-54148-6, retrieved 2022-12-15
  7. ^ a b c d e Gordon, V. Scott; Mathias, Keith; Whitley, Darrell (1994). "Cellular genetic algorithms as function optimizers". Proceedings of the 1994 ACM symposium on Applied computing - SAC '94. Phoenix, Arizona, United States: ACM Press. pp. 237–241. doi:10.1145/326619.326732. ISBN 978-0-89791-647-9. S2CID 6418773.
  8. ^ a b Giacobini, M.; Tomassini, M.; Tettamanzi, A.G.B.; Alba, E. (October 2005). "Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices". IEEE Transactions on Evolutionary Computation. 9 (5): 489–505. doi:10.1109/TEVC.2005.850298. ISSN 1089-778X. S2CID 3184685.
  9. ^ a b c Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02). "A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics". Proceedings of the 12th International Conference on Management of Digital EcoSystems. Virtual Event United Arab Emirates: ACM. pp. 124–131. doi:10.1145/3415958.3433041. ISBN 978-1-4503-8115-4. S2CID 227179748.
  10. ^ a b Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.), "Parallel Evolutionary Algorithms" (PDF), Springer Handbook of Computational Intelligence, Berlin, Heidelberg: Springer, pp. 929–959, doi:10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, retrieved 2023-02-13
  11. ^ a b Cantú-Paz, Erick (1999), "Topologies, Migration Rates, and Multi-Population Parallel Genetic Algorithms", Proc. of the 1st Annual Conf. on Genetic and Evolutionary Computation (GECCO), pp. 91–98
  12. ^ Belkadi, K.; Gourgand, M.; Benyettou, M. (2006-11-08). "Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem". Journal of Applied Mathematics and Decision Sciences. 2006: 1–17. doi:10.1155/JAMDS/2006/65746. ISSN 1173-9126.
  13. ^ Abdelhafez, Amr; Alba, Enrique; Luque, Gabriel (September 2019). "Performance analysis of synchronous and asynchronous distributed genetic algorithms on multiprocessors". Swarm and Evolutionary Computation. 49: 147–157. doi:10.1016/j.swevo.2019.06.003. S2CID 196193164.
  14. ^ a b Adar, N.; Kuvat, G. (2016). "Parallel Genetic Algorithms with Dynamic Topology using Cluster Computing". Advances in Electrical and Computer Engineering. 16 (3): 73–80. doi:10.4316/AECE.2016.03011. ISSN 1582-7445.
  15. ^ a b c Alba, Enrique; Troya, José Ma (2000), Schoenauer, Marc; Deb, Kalyanmoy; Rudolph, Günther; Yao, Xin (eds.), "Cellular Evolutionary Algorithms: Evaluating the Influence of Ratio", Parallel Problem Solving from Nature PPSN VI, Berlin, Heidelberg: Springer, vol. 1917, pp. 29–38, doi:10.1007/3-540-45356-3_3, ISBN 978-3-540-41056-0, retrieved 2023-02-11
  16. ^ Folino, G.; Pizzuti, C.; Spezzano, G. (1998). "Combining cellular genetic algorithms and local search for solving satisfiability problems". Proceedings Tenth IEEE International Conference on Tools with Artificial Intelligence (Cat. No.98CH36294). Taipei, Taiwan: IEEE. pp. 192–198. doi:10.1109/TAI.1998.744842. ISBN 978-0-7803-5214-8. S2CID 8048158.
  17. ^ Alba, Enrique; Dorronsoro, Bernabé (2008). Cellular genetic algorithms. New York: Springer. p. 12. ISBN 978-0-387-77610-1. OCLC 370728730.
  18. ^ a b Gorges-Schleuter, Martina (1998), Eiben, Agoston E.; Bäck, Thomas; Schoenauer, Marc; Schwefel, Hans-Paul (eds.), "A comparative study of global and local selection in evolution strategies", Parallel Problem Solving from Nature — PPSN V, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, vol. 1498, pp. 367–377, doi:10.1007/bfb0056879, ISBN 978-3-540-65078-2, retrieved 2023-02-11
  19. ^ Sprave, Joachim (1994), "Linear neighborhood evolution strategy" (PDF), Proceedings of the 3rd Annual Conference on Evolutionary Programming, Singapore: World Scientific, pp. 42–51, retrieved 2022-11-05
  20. ^ Jakob, Wilfried (2010-09-01). "A general cost-benefit-based adaptation framework for multimeme algorithms". Memetic Computing. p. 207. 2 (3): 201–218. doi:10.1007/s12293-010-0040-9. ISSN 1865-9292. S2CID 167807.
  21. ^ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). "Cellular Memetic Algorithms". Journal of Computer Science and Technology. 5 (4): 257–263. Retrieved 2022-11-04.
  22. ^ Wen-Yang Lin; Tzung-Pei Hong; Shu-Min Liu (2004). "On adapting migration parameters for multi-population genetic algorithms". 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583). Vol. 6. The Hague, Netherlands: IEEE. pp. 5731–5735. doi:10.1109/ICSMC.2004.1401108. ISBN 978-0-7803-8567-2. S2CID 31844333.
  23. ^ Hong, Tzung-Pei; Lin, Wen-Yang; Liu, Shu-Min; Lin, Jiann-Horng (2007-04-20). "Dynamically Adjusting Migration Rates for Multi-Population Genetic Algorithms". Journal of Advanced Computational Intelligence and Intelligent Informatics. 11 (4): 410–415. doi:10.20965/jaciii.2007.p0410. ISSN 1883-8014.
  24. ^ Luque, Gabriel; Alba, Enrique (2011). Parallel Genetic Algorithms. Studies in Computational Intelligence. Vol. 367. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-22084-5. ISBN 978-3-642-22083-8.
  25. ^ Luque, Gabriel; Alba, Enrique; Dorronsoro, Bernabé (July 2009). "An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization". Proceedings of the 11th Annual conference on Genetic and evolutionary computation. Montreal Québec Canada: ACM. pp. 1395–1402. doi:10.1145/1569901.1570088. ISBN 978-1-60558-325-9. S2CID 14113702.
  26. ^ Zhongwen Luo; Hongzhi Liu (2006). "Cellular Genetic Algorithms and Local Search for 3-SAT problem on Graphic Hardware". 2006 IEEE International Conference on Evolutionary Computation. Vancouver, BC, Canada: IEEE. pp. 2988–2992. doi:10.1109/CEC.2006.1688685. ISBN 978-0-7803-9487-2. S2CID 8142372.
  27. ^ Cahon, S.; Melab, N.; Talbi, E.-G. (May 2004). "ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics". Journal of Heuristics. 10 (3): 357–380. doi:10.1023/B:HEUR.0000026900.92269.ec. ISSN 1381-1231. S2CID 14972999.
  28. ^ Jähne, Paul (2016). Mayr, Heinrich Christian; Pinzger, Martin (eds.). Overview of the current state of research on parallelisation of evolutionary algorithms on graphic cards (PDF). ISBN 978-3-88579-653-4. OCLC 962381748. {{cite book}}: work=무시됨(도움말)
  29. ^ García-Calvo, Raúl; Guisado, Jl; Diaz-del-Rio, Fernando; Córdoba, Antonio; Jiménez-Morales, Francisco (January 2018). "Graphics Processing Unit–Enhanced Genetic Algorithms for Solving the Temporal Dynamics of Gene Regulatory Networks". Evolutionary Bioinformatics. 14. doi:10.1177/1176934318767889. ISSN 1176-9343. PMC 5898668. PMID 29662297.