진화 계산

Evolutionary computation
저널에 대해서는, 진화 계산(저널)을 참조해 주세요.
시리즈의 일부
진화생물학
Darwin's finches by Gould.jpg
존 굴드의 다윈 핀치
프로세스와 결과
자연사
진화론의 역사
필드 및 응용 프로그램
사회적 영향
의 시리즈의 일부
진화 알고리즘
유전 알고리즘
유전자 프로그래밍

컴퓨터 과학에서 진화 계산은 생물학적 진화에 영감을 받은 글로벌 최적화를 위한 알고리즘의 집합이며, 이러한 알고리즘을 연구하는 인공지능과 소프트 컴퓨팅의 하위 분야입니다.기술적인 용어로, 이들은 메타 휴리스틱 또는 확률적 최적화 특성을 가진 모집단 기반 시행착오 해결사 제품군이다.

진화 계산에서는 후보 솔루션의 초기 세트가 생성되어 반복적으로 갱신된다.각각의 새로운 세대는 덜 원하는 솔루션을 확률적으로 제거하고 작은 무작위 변화를 도입함으로써 생산된다.생물학적 용어로 용액의 집단은 자연선택(또는 인공선택)과 돌연변이를 겪는다.결과적으로, 모집단은 점차적으로 적응도를 증가시키기 위해 진화할 것이며, 이 경우 알고리즘의 선택된 적응도 함수이다.

진화적 계산 기술은 광범위한 문제 환경에서 고도로 최적화된 솔루션을 생성할 수 있으며, 컴퓨터 과학 분야에서 널리 사용됩니다.보다 구체적인 문제 및 데이터 구조 패밀리에 적합한 다양한 변형 및 확장 기능이 있습니다.진화 계산은 또한 일반적인 진화 과정의 공통적인 측면을 연구하기 위한 실리코 실험 절차로서 진화 생물학에서 가끔 사용된다.

역사

문제를 해결하기 위해 진화 과정을 모방하는 개념은 1948년 [1]앨런 튜링이 유전자 검색 방법을 제안했을 때처럼 컴퓨터가 등장하기 전에 시작되었다. 튜링의 B형 u 기계는 원시적인 신경망을 닮았고, 뉴런 사이의 연결은 일종의 유전 알고리즘을 통해 학습되었다.그의 P형 u-머신은 기쁨과 고통 신호가 특정 행동을 학습하도록 기계를 지시하는 강화 학습 방법과 유사합니다.하지만, 튜링의 논문은 1968년까지 발표되지 않았고, 그는 1954년에 죽었기 때문에,[2] 이 초기 연구는 발전해야 할 진화 계산 분야에 거의 또는 전혀 영향을 미치지 않았다.

진화적 컴퓨팅은 1950년대와 [1]1960년대에 본격적으로 시작되었다.이 시기에는 컴퓨팅에서 진화 과정을 이용하려는 몇 가지 독립적인 시도가 있었으며, 이는 약 15년 동안 개별적으로 개발되었습니다.이 목표를 달성하기 위해 진화 전략, 진화 프로그래밍, 유전 알고리즘 등 세 가지 분야가 서로 다른 장소에서 출현했다.네 번째 분야인 유전자 프로그래밍은 결국 1990년대 초에 등장했다.이러한 접근법은 선택 방법, 허용된 돌연변이 및 유전자 데이터의 표현에 따라 다르다.1990년대에 이르러서는 역사적 분야 간의 구분이 모호해지기 시작했고, '진화 컴퓨팅'이라는 용어는 네 가지 패러다임 모두에 [3]걸쳐 존재하는 분야를 나타내기 위해 1991년에 만들어졌다.

1962년 로렌스 포겔은 미국에서 인공지능의 노력으로 여겨졌던 진화 프로그래밍의 연구를 시작했다.이 시스템에서는 예측 문제를 해결하기 위해 유한 상태 머신이 사용됩니다.이러한 머신은 돌연변이(상태 추가 또는 삭제, 상태 전이 규칙 변경)되며, 이러한 돌연변이된 머신의 가장 좋은 점은 미래 세대에 더욱 진화될 것입니다.최종 유한 상태 기계는 필요할 때 예측을 생성하기 위해 사용될 수 있다.진화적 프로그래밍 방법은 예측 문제, 시스템 식별 및 자동 제어에 성공적으로 적용되었습니다.결국 시계열 데이터를 처리하고 게임 [3]전략의 진화를 모델링하도록 확장되었습니다.

1964년 잉고 레첸베르크와 한스 폴 슈베펠은 독일에서 [3]진화 전략의 패러다임을 도입했다.전통적인 경사 강하 기법이 국소 최소치에 고착될 수 있는 결과를 생성하기 때문에, 레첸베르크와 슈베펠은 무작위 돌연변이(일부 솔루션 벡터의 모든 매개변수에 적용)를 사용하여 이러한 최소치를 벗어날 수 있다고 제안했다.자녀 솔루션은 부모 솔루션에서 생성되었으며, 둘 중 더 성공적인 솔루션은 미래 세대를 위해 유지되었습니다.이 기술은 유체 [4]역학에서 최적화 문제를 성공적으로 해결하기 위해 두 사람에 의해 처음 사용되었습니다.처음에, 이 최적화 기술은 컴퓨터 없이 수행되었고, 대신 무작위 돌연변이를 결정하기 위해 주사위에 의존했다.1965년까지 계산은 전적으로 [3]기계로 수행되었다.

John Henry Holland는 1960년대에 유전 알고리즘을 도입했고, 1970년대에 [5]Michigan 대학에서 더욱 개발되었습니다.다른 접근법이 문제 해결에 초점을 맞춘 반면, 홀랜드는 주로 적응을 연구하고 어떻게 시뮬레이션될 수 있는지를 결정하기 위해 유전자 알고리즘을 사용하는 것을 목표로 했다.비트열로 표현되는 염색체 집단은 비트열의 특정 '알레' 비트를 선택하는 인위적인 선택 과정에 의해 변형되었다.다른 돌연변이 방법들 중에서, 염색체들 사이의 상호작용은 다른 유기체들 사이의 DNA 재조합을 시뮬레이션하기 위해 사용되었다.이전의 방법들이 한 번에 하나의 최적의 유기체를 추적하는 데 그쳤지만(자녀가 부모와 경쟁하는 것), 네덜란드의 유전 알고리즘은 많은 개체군을 추적했다(많은 유기체가 각 세대에 경쟁하는 것).

1990년대에 이르러, 유전자 프로그래밍이라고 불리게 된 진화적 계산에 대한 새로운 접근법이 등장했고, 존 코자([3]John Koza)가 주창했다.이 알고리즘 클래스에서 진화의 주제는 그 자체로 고급 프로그래밍 언어로 작성된 프로그램이었다. 1958년 이전에 기계 코드를 사용하려는 시도가 있었지만 거의 성공하지 못했다.Koza에 있어서 프로그램은 Lisp S-expressions였는데, 이것은 하위 표현의 나무라고 생각할 수 있다.이 표현을 통해 프로그램이 하위 트리를 교환할 수 있으며, 이는 일종의 유전자 혼합을 나타냅니다.프로그램은 특정 과제를 얼마나 잘 완료했는가에 따라 점수가 매겨지고 점수는 인위적인 선택에 사용됩니다.시퀀스 유도, 패턴 인식 및 계획은 모두 유전자 프로그래밍 패러다임의 성공적인 적용이었다.

진화 컴퓨팅의 역사에서 많은 다른 인물들이 역할을 했습니다.그러나 그들의 작업은 항상 이 분야의 주요 역사적 분야 중 하나에 적합한 것은 아니었습니다.진화 알고리즘과 인공 생명 기술을 사용한 최초의 컴퓨터 시뮬레이션은 1953년에 닐스 알 바리첼리에 의해 수행되었고,[6] 1954년에 첫 번째 결과가 발표되었다.1950년대의 또 다른 선구자는 알렉스 프레이저로 그는 인공선택 [7]시뮬레이션에 관한 일련의 논문을 발표했다.학계의 관심이 높아짐에 따라 컴퓨터의 파워가 극적으로 증가하여 컴퓨터 [8]프로그램의 자동 진화를 포함한 실용적인 응용이 가능해졌습니다.진화 알고리즘은 이제 인간 설계자가 제작한 소프트웨어보다 다차원 문제를 더 효율적으로 해결하고 시스템 [9][10]설계를 최적화하기 위해 사용됩니다.

기술

진화 컴퓨팅 기술은 대부분 메타 휴리스틱 최적화 알고리즘을 포함합니다.일반적으로 이 필드에는 다음이 포함됩니다.

진화 알고리즘

주요 기사:진화 알고리즘

진화 알고리즘은 일반적으로 생식, 돌연변이, 재조합, 자연 선택 및 적자 생존과 같은 생물학적 진화에 의해 영감을 받은 메커니즘을 구현하는 기술만을 포함한다는 점에서 진화 계산의 서브셋을 형성한다.최적화 문제에 대한 후보 솔루션은 모집단에서 개인의 역할을 하며, 비용 함수는 솔루션이 "살아 있는" 환경을 결정합니다(피트니스 함수 참조).모집단의 진화는 위의 연산자를 반복적으로 적용한 후에 이루어진다.

이 과정에서 진화 시스템의 기초를 이루는 두 가지 주요 힘이 있습니다.재조합 돌연변이와 교차는 필요한 다양성을 만들어 내고, 그로 인해 참신함을 촉진하는 한편, 선택은 품질을 높이는 힘으로서 작용한다.

그러한 진화 과정의 많은 측면은 확률적이다.재조합 및 돌연변이에 의해 변경된 정보를 무작위로 선택한다.반면에 선택 연산자는 결정론적 연산자이거나 확률적 연산자일 수 있습니다.후자의 경우, 더 높은 체력을 가진 사람들은 낮은 체력을 가진 사람들보다 선발될 가능성이 더 높지만, 전형적으로 약한 사람들조차도 부모가 되거나 생존할 기회가 있다.

진화 알고리즘과 생물학

주요 기사:진화 알고리즘

유전 알고리즘은 시스템의 미래 상태를 예측하는 데 사용되기 때문에 동적 시스템의 이론과 연계된 생물학적 시스템과 시스템 생물학을 모델링하는 방법을 제공합니다.이것은 생물학의 발달의 질서 있고, 잘 통제되고, 고도로 구조화된 특징에 관심을 끌기 위한 생생한 방법일 뿐이다.

그러나 알고리즘과 정보학, 특히 계산 이론의 사용은 동적 시스템과의 유추를 넘어 진화 자체를 이해하는 데에도 관련이 있다.

이 견해는 발달에 대한 중앙 통제가 없다는 것을 인식하는 장점이 있다; 유기체는 세포 내부와 세포 사이의 국소적 상호작용의 결과로 발달한다.프로그램 개발 병행에 관한 가장 유망한 아이디어는 세포 내의 프로세스와 현대 [11]컴퓨터의 낮은 수준의 작동 사이의 명백한 유사성을 보여주는 것으로 보인다.따라서, 생물학적 시스템은 입력 정보를 처리하여 다음 상태를 계산하는 계산 기계와 같습니다. 따라서 생물학적 시스템은 고전적인 [12]동적 시스템보다 계산에 더 가깝습니다.

게다가, 계산 이론의 개념에 따라, 생물 유기체의 미세 과정은 근본적으로 불완전하고 결정 불가능한 것이다(완전성(논리)). 이것은 "세포와 [13]컴퓨터 사이의 유사성 이면에 조잡한 은유 이상의 것이 있다.

계산에 대한 유추는 또한 유전 시스템과 생물학적 구조 사이의 관계로도 확장되는데, 이것은 종종 생명의 기원을 설명할 때 가장 시급한 문제 중 하나를 드러낸다고 생각됩니다.

진화적[17][18] 튜링 기계의 일반화인 진화적[14][15][16] 오토마타는 생물학적 및 진화적 계산의 보다 정확한 특성을 조사하기 위해 도입되었다.특히, 그들은 진화적[16][19] 계산의 표현성에 대한 새로운 결과를 얻을 수 있게 해준다.이것은 자연 진화와 진화 알고리즘과 과정의 결정 불가능성에 대한 초기 결과를 확인시켜준다.단말 모드로 동작하는 진화 오토마타의 가장 단순한 서브 클래스인 진화 유한 오토마타는 비재귀적 열거 가능(예를 들어 대각화 언어) 및 재귀적 열거 가능하지만 재귀적이지 않은 언어(예를 들어 범용 튜링 기계의 [20]언어)를 포함한 주어진 알파벳 상의 임의의 언어를 받아들일 수 있다.

저명한 실무자

활동적인 연구자 명단은 본질적으로 역동적이고 지치지 않는다.커뮤니티의 네트워크 분석은 [21]2007년에 발표되었다.

회의

진화 계산 영역의 주요 컨퍼런스는 다음과 같다.

「 」를 참조해 주세요.

외부 링크

참고 문헌

  • Th. Beck, D.B. Fogel, Z. Michalewicz(편집자), 진화 계산 핸드북, 1997, ISBN0750303921
  • Th. Beck and H.-P.슈베펠.파라미터 최적화를 위한 진화 알고리즘의 개요.2018년 7월 12일 Wayback Machine Evolutionary Computation, 1 (1):1 ~ 23, 1993년에 아카이브 완료.
  • W. 반자프, P. 노르딘, R.E. 켈러, F.D.프랑콘유전자 프로그래밍 - 개요.모건 카우프만, 1998년
  • S. Cagnoni, et al., Springer-Verlag 강의 노트, Berlin, 2000.
  • R. Chiong, ThWeise, Z. Michalewicz(편집자), 실제 애플리케이션을 위한 진화 알고리즘의 변형, Springer, 2012, ISBN 3642234232
  • K. A. De Jong, 진화 계산: 통합 접근법.MIT Press, Cambridge MA, 2006
  • A. E. E. Eiben과 J.E. Smith, 진화 계산에서 사물의 진화로, Nature, 521:476-482, doi:10.1038/nature14544, 2015
  • A. E. Eiben 및 J.E. Smith, 진화 컴퓨팅 입문, Springer, 초판, 2003, 제2판, 2015
  • D. B. 포겔진화적 계산머신 인텔리전스의 새로운 철학을 향해.IEEE Press, Piscataway, NJ, 1995.
  • L.J. 포겔, A.J. 오웬, M.J. 월시이다.인공 지능 모의 에볼루션을 통해.뉴욕:JohnWiley도, 1966.
  • D. 골드버그.검색, 최적화 및 기계 학습에서 유전자 알고리즘이 있습니다.애디슨 웨슬리, 1989.
  • J.H. 네덜란드.인위 도태와 자연 시스템에 적응.미시간 대학의 앤 아버, 1975년.
  • P.Hingston, L.Barone그리고 ZMichalewicz(에디터스), 진화는 설계, 자연 컴퓨팅 시리즈 2008년, 스프링거, 아이 에스비엔 3540741097.
  • J.R. 고자.유전 프로그래밍:프로그램 컴퓨터는 자연 진화의 방법으로.MIT출판사, 메사츄 세츠주, 1992년.
  • F.J. 로보, CF. 리마, Z. Michalewicz(편집자), 진화 알고리즘 매개 변수 설정, Springer, 2010, ISBN 3642088929
  • Z. Michalewicz, 유전 알고리즘 + 데이터 구조 – Evolution Programs, 1996, Springer, ISBN 3540606769
  • Z. Michalewicz와 D.B.Fogel, 해결방법: Modern Huristics, Springer, 2004, ISBN 978-3-540-22494-5
  • I. 레첸버그진화 전략:Optimierung Technischer Systeme 나흐 Prinzipien des Biologicalischen Evolution.1973년 슈투트가르트, Fromman-Hozlboog Verlag.(독일어)
  • H.P. 슈웨펠컴퓨터 모델의 수치 최적화John Wiley & Sons, New-York, 1981. 1995 – 제2판
  • D. 사이먼진화적 최적화 알고리즘Wiley, 2013.
  • M. Sipper, W. Fu, K. Ahuja, and J. H. Moore (2018). "Investigating the parameter space of evolutionary algorithms". BioData Mining. 11: 2. doi:10.1186/s13040-018-0164-x. PMC 5816380. PMID 29467825.{{cite journal}}: CS1 maint: 작성자 파라미터 사용(링크)
  • Y. Zhang and S. Li. (2017). "PSA: A novel optimization algorithm based on survival rules of porcellio scaber". arXiv:1709.09840 [cs.NE].{{cite arxiv}}: CS1 maint: 작성자 파라미터 사용(링크)

레퍼런스

  1. ^ a b Eiben, A. E.; Smith, J. E. (2015), "Evolutionary Computing: The Origins", Natural Computing Series, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 13–24, doi:10.1007/978-3-662-44874-8_2, ISBN 978-3-662-44873-1, retrieved May 6, 2022
  2. ^ Burgin, Mark; Eberbach, Eugene (April 12, 2013). "Evolutionary Turing in the Context of Evolutionary Machines". arXiv:1304.3762 [cs.AI].
  3. ^ a b c d e Evolutionary computation : the fossil record. David B. Fogel. New York: IEEE Press. 1998. ISBN 0-7803-3481-7. OCLC 38270557.{{cite book}}: CS1 유지보수: 기타 (링크)
  4. ^ Fischer, Thomas (1986), "Kybernetische Systemanalyse Einer Tuchfabrik zur Einführung Eines Computergestützten Dispositionssystems der Fertigung", DGOR, Berlin, Heidelberg: Springer Berlin Heidelberg, p. 120, doi:10.1007/978-3-642-71161-9_14, ISBN 978-3-642-71162-6, retrieved May 6, 2022
  5. ^ Mitchell, Melanie (1998). An Introduction to Genetic Algorithms. The MIT Press. doi:10.7551/mitpress/3927.001.0001. ISBN 978-0-262-28001-3.
  6. ^ Barricelli, Nils Aall (1954). "Esempi Numerici di processi di evoluzione". Methodos: 45–68.
  7. ^ Fraser AS (1958). "Monte Carlo analyses of genetic models". Nature. 181 (4603): 208–9. Bibcode:1958Natur.181..208F. doi:10.1038/181208a0. PMID 13504138. S2CID 4211563.
  8. ^ Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press. ISBN 978-0-262-11170-6.
  9. ^ G.C. 온우볼루와 B V 바부
  10. ^ Jamshidi M (2003). "Tools for intelligent control: fuzzy controllers, neural networks and genetic algorithms". Philosophical Transactions of the Royal Society A. 361 (1809): 1781–808. Bibcode:2003RSPTA.361.1781J. doi:10.1098/rsta.2003.1225. PMID 12952685. S2CID 34259612.
  11. ^ "Biological Information". The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University. 2016.
  12. ^ J.G. Diaz Ochoa (2018). "Elastic Multi-scale Mechanisms: Computation and Biological Evolution". Journal of Molecular Evolution. 86 (1): 47–57. Bibcode:2018JMolE..86...47D. doi:10.1007/s00239-017-9823-7. PMID 29248946. S2CID 22624633.
  13. ^ A. Danchin (2008). "Bacteria as computers making computers". FEMS Microbiol. Rev. 33 (1): 3–26. doi:10.1111/j.1574-6976.2008.00137.x. PMC 2704931. PMID 19016882.
  14. ^ Burgin, Mark; Eberbach, Eugene (2013). "Recursively Generated Evolutionary Turing Machines and Evolutionary Automata". In Xin-She Yang (ed.). Artificial Intelligence, Evolutionary Computing and Metaheuristics. Studies in Computational Intelligence. Vol. 427. Springer-Verlag. pp. 201–230. doi:10.1007/978-3-642-29694-9_9. ISBN 978-3-642-29693-2.
  15. ^ Burgin, M. and Eberbach, E. (2010) Proc. 2010, 스페인 바르셀로나 진화 계산 콩그레스(CEC'2010), 1379-1386 페이지
  16. ^ a b Burgin, M.; Eberbach, E. (2012). "Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation". The Computer Journal. 55 (9): 1023–1029. doi:10.1093/comjnl/bxr099.
  17. ^ Eberbach E. (2002) 진화적 계산의 표현성에 대하여:EC 알고리즘은?, Proc. 2002 World Congress on Computational Intelligence WCCI'2002, Honolu, HI, 2002, 564-569.
  18. ^ Eberbach, E. (2005) 진화 계산 이론을 향한 바이오시스템즈, v. 82, 페이지 1-19.
  19. ^ Eberbach, Eugene; Burgin, Mark (2009). "Evolutionary automata as foundation of evolutionary computation: Larry Fogel was right". 2009 IEEE Congress on Evolutionary Computation. IEEE. pp. 2149–2156. doi:10.1109/CEC.2009.4983207. ISBN 978-1-4244-2958-5. S2CID 2869386.
  20. ^ 홉크로프트, J.E., R. Motwani, J.D.Ulman(2001) 오토마타 이론, 언어, 계산 입문 (애디슨 웨슬리, 보스턴/샌프란시스코/뉴욕)
  21. ^ J.J. Merelo and C. Cotta (2007). "Who is the best connected EC researcher? Centrality analysis of the complex network of authors in evolutionary computation". arXiv:0708.2021 [cs.CY].