진화 알고리즘

3. Types

유사한 기법들은 유전적 표현과 다른 구현 세부 사항, 그리고 적용되는 특정 문제의 성격에서 차이가 있다.

• 유전 알고리즘 – 이것은 가장 인기 있는 EA 유형이다. 문제의 해결책을 숫자들의 문자열(전통적으로는 이진수이지만, 가장 좋은 표현은 일반적으로 해결하려는 문제에 대한 정보를 반영하는 것입니다)^[2] 형태로 찾고, 재조합 및 돌연변이(때로는 하나, 때로는 둘 다)와 같은 연산자를 적용한다. 이러한 유형의 EA는 종종 최적화 문제에 사용된다.

• 유전 프로그래밍 – 여기서 해결책은 컴퓨터 프로그램의 형태이며, 그 적합성은 계산 문제를 해결하는 능력에 따라 결정된다. 카르테시안 유전 프로그래밍, 유전자 발현 프로그래밍, 문법적 진화, 선형 유전 프로그래밍, 다중 표현 프로그래밍 등 많은 유전 프로그래밍 변형이 있다.

• 진화 프로그래밍 – 유전 프로그래밍과 유사하지만 프로그램의 구조는 고정되어 있으며 수치 매개변수가 진화하도록 허용된다.

• 진화 전략 – 해결책의 표현으로 실수 벡터를 사용하며, 일반적으로 자가 적응 돌연변이율을 사용한다. 이 방법은 주로 수치적 최적화에 사용되지만, 조합 문제에 대한 변형도 있다.^[6][7]

• 차분 진화 – 벡터 차이를 기반으로 하며, 따라서 주로 수치 최적화 문제에 적합하다.

• 공진화 알고리즘 – 유전 알고리즘 및 진화 전략과 유사하지만, 생성된 해결책은 다른 해결책과의 상호 작용 결과를 바탕으로 비교된다. 탐색 과정에서 해결책은 경쟁하거나 협력할 수 있다. 공진화 알고리즘은 적합도 지형이 동적이거나 복잡하거나 경쟁적 상호 작용을 포함하는 시나리오에 자주 사용된다.^[8][9]

• 신경 진화 – 유전 프로그래밍과 유사하지만 게놈은 구조와 연결 가중치를 설명하여 인공 신경망을 나타냅니다. 게놈 인코딩은 직접적이거나 간접적일 수 있다.

• 학습 분류기 시스템 – 여기서 해결책은 분류기(규칙 또는 조건)의 집합이다. Michigan-LCS는 개별 분류기 수준에서 진화하는 반면, Pittsburgh-LCS는 분류기 집합의 모집단을 사용한다. 처음에는 분류기가 이진수였지만, 현재는 실수, 신경망 또는 S-표현식 유형을 포함한다. 적합도는 일반적으로 강도 또는 정확도 기반 강화 학습 또는 지도 학습 접근 방식으로 결정된다.

• 품질-다양성 알고리즘 – QD 알고리즘은 동시에 고품질과 다양한 해결책을 목표로 한다. 문제에 대한 최상의 해결책을 찾는 데만 집중하는 기존의 최적화 알고리즘과 달리, QD 알고리즘은 문제 공간에서 다양한 해결책을 탐색하고 고성능일 뿐만 아니라 다양하고 독특한 해결책을 유지한다.^[10][11][12]

3. 1. 종류

• 유전 알고리즘 – 가장 일반적인 EA 유형이다. 해결책을 숫자들의 문자열(주로 이진수) 형태로 찾고,^[2] 재조합 및 돌연변이 연산자를 적용한다. 주로 최적화 문제에 사용된다.

• 유전 프로그래밍 – 해결책이 컴퓨터 프로그램 형태이며, 적합성은 계산 문제 해결 능력에 따라 결정된다. 카르테시안 유전 프로그래밍, 유전자 발현 프로그래밍, 문법적 진화, 선형 유전 프로그래밍, 다중 표현 프로그래밍 등 다양한 변형이 있다.

• 진화 프로그래밍 – 유전 프로그래밍과 유사하나 프로그램 구조는 고정되고 수치 매개변수가 진화한다.

• 진화 전략 – 실수 벡터를 해결책 표현으로 사용하며, 자가 적응 돌연변이율을 사용한다. 주로 수치적 최적화에 사용되지만, 조합 문제에 대한 변형도 존재한다.^[6][7]

• 차분 진화 – 벡터 차이를 기반으로 하므로 주로 수치 최적화 문제에 적합하다.

• 공진화 알고리즘 – 유전 알고리즘 및 진화 전략과 유사하지만, 생성된 해결책이 다른 해결책과의 상호 작용 결과를 바탕으로 비교된다. 적합도 지형이 동적이거나 복잡하거나 경쟁적 상호 작용을 포함하는 시나리오에 자주 사용된다.^[8][9]

• 신경 진화 – 유전 프로그래밍과 유사하지만 게놈은 인공 신경망의 구조와 연결 가중치를 나타낸다. 게놈 인코딩은 직접적이거나 간접적일 수 있다.

• 학습 분류기 시스템 – 해결책은 분류기(규칙 또는 조건)의 집합이다. Michigan-LCS는 개별 분류기 수준에서, Pittsburgh-LCS는 분류기 집합의 모집단을 사용하여 진화한다. 초기에는 이진수 분류기였으나, 현재는 실수, 신경망 또는 S-표현식 유형을 포함한다. 적합도는 강도 또는 정확도 기반 강화 학습 또는 지도 학습 방식으로 결정된다.

• 품질-다양성 알고리즘 – QD 알고리즘은 고품질과 다양한 해결책을 동시에 목표로 한다. 기존 최적화 알고리즘과 달리, 문제 공간에서 다양한 해결책을 탐색하고 고성능이면서도 다양하고 독특한 해결책을 유지한다.^[10][11][12]

4. Theoretical background

다음 이론적 원칙은 모든 또는 거의 모든 전문가 시스템(EA)에 적용된다.

최적화의 무료 점심 정리(No free lunch theorem)는 모든 최적화 전략이 모든 최적화 문제 집합을 고려할 때 동등하게 효과적이라는 것을 말한다. 같은 조건 하에서, 어떤 진화 알고리즘도 다른 알고리즘보다 근본적으로 더 낫지 않다. 이것은 모든 문제 집합이 제한될 때만 가능하며, 실제로 불가피하게 수행되는 작업이다. 따라서 EA를 개선하려면 어떤 형태로든 문제 지식을 활용해야 한다(예: 특정 돌연변이 강도 또는 문제에 적합한 코딩을 선택). 따라서 두 개의 EA를 비교하는 경우 이러한 제약 조건이 암시된다.^[13][14] EA는 예를 들어 전체 시작 모집단을 무작위로 생성하는 대신 휴리스틱 또는 다른 절차를 통해 일부 개체를 생성하여 문제 특정 지식을 사용할 수 있다. 주어진 문제 영역에 EA를 맞춤화하는 또 다른 방법은 자손을 생성하는 과정에 적절한 휴리스틱, 국소 탐색 절차 또는 기타 문제 관련 절차를 포함하는 것이다. 이러한 형태의 EA 확장은 밈 알고리즘으로도 알려져 있으며, 탐색 프로세스를 가속화하고 더욱 강력하게 만들 수 있기 때문에 실제 응용 프로그램에서 중요한 역할을 한다.^[13][15]

자식 개체 외에 적어도 부모 세대의 최고 개체를 사용하여 다음 세대를 형성하는(소위 엘리트 EA) EA의 경우, 최적값이 존재한다는 조건 하에 수렴에 대한 일반적인 증명이 있다. 엘리트 자식 수용의 특성과 최적값의 존재로부터, 각 세대 $k$에서 해당 최고 개체 $x\text{'}$의 적합도 $F$가 $P\; >\; 0$의 확률로 개선됨을 알 수 있다. 따라서 적합도 값은 단조적으로 감소하지 않는 수열을 나타내며, 최적값의 존재로 인해 유계이다. 이로부터 최적값에 대한 수열의 수렴이 따른다. 이 증명은 수렴 속도에 대해서는 아무런 언급을 하지 않으므로, EA의 실제 응용에는 거의 도움이 되지 않는다. 하지만 엘리트 EA를 사용하는 것을 정당화한다. 그러나 일반적인 범혼합 집단 모델을 사용할 때, 엘리트 EA는 비엘리트 EA보다 조기에 수렴하는 경향이 있다.^[16] 비범혼합 집단에서는 선택이 적절히 제한되어, 더 나은 개체의 분산 속도가 범혼합 집단에 비해 감소한다. 따라서 배우자 선택을 제한하는 적절한 집단 모델을 통해 엘리트 EA의 조기 수렴의 일반적인 위험을 상당히 줄일 수 있다.^[17][18]

가상 알파벳 이론을 통해 데이비드 E. 골드버그(David E. Goldberg)는 1990년 실수 표현을 사용하는 경우, 고전적인 재조합 연산자를 사용하는 EA는 이진수 코딩과 달리 탐색 공간의 특정 영역에 도달할 수 없다는 것을 보였다.^[19] 따라서 실수 표현을 사용하는 EA에는 산술 연산자를 재조합에 사용하는 것이 좋다. 적절한 연산자를 사용하면 이전의 견해와 달리 실수 값 표현이 이진수 표현보다 더 효과적이다.^[20][21]

4. 1. 이론적 원칙

5. Comparison to other methods

5. 1. 생물학적 과정과의 비교

5. 2. 몬테카를로 방법과의 비교

6. Applications

진화 알고리즘이 실제로 사용되는 분야는 거의 무한하며(), 산업(), 공학(), 복잡한 스케줄링(), 농업(), 로봇 동작 계획(), 금융()에서부터 연구() 및 예술에 이르기까지 다양하다. 진화 알고리즘의 적용은 경험이 없는 사용자에게는 약간의 사고 전환을 요구하는데, EA를 사용하여 작업에 접근하는 방식은 기존의 정확한 방법과 다르며, 이는 일반적으로 엔지니어 또는 다른 분야의 교육 과정에 포함되어 있지 않기 때문이다. 예를 들어, 적합도 계산은 목표를 공식화할 뿐만 아니라 원래 품질 기준의 더 나은 평가로 아직 이어지지 않는 개선 사항에 보상함으로써 진화적 탐색 과정을 지원해야 한다. 예를 들어, 인력 배치나 에너지 소비와 같은 자원의 최대 활용을 피해야 하는 스케줄링 작업에서 최대 활용도를 평가하는 것만으로는 충분하지 않다. 오히려 여전히 허용 가능한 수준을 초과하는 횟수와 기간도 기록하여 실제 최대 피크 값보다 낮은 감소에 보상해야 한다.() 따라서 초보자를 위한 것으로 초보자의 실수를 피하고 응용 프로젝트를 성공으로 이끌 수 있도록 돕는 출판물이 있다.() 여기에는 EA를 사용하여 문제를 해결해야 하는 경우와 그렇지 않은 경우를 명확히 하는 기본적인 질문이 포함된다.

6. 1. 응용 분야

6. 2. 대한민국에서의 활용

7. Related techniques and other global search methods

자연에서 영감을 받은 전역 탐색 기법 중 검증되고 널리 사용되는 방법은 다음과 같다.

• 밈 알고리즘 – 리처드 도킨스의 밈 개념에서 영감을 받은 하이브리드 방법이다. 일반적으로 개체군 기반 알고리즘(자주 EA)과 국소적 개선을 수행할 수 있는 개별 학습 절차의 형태를 취한다. 문제 특정 지식의 활용을 강조하고 국소적 및 전역적 탐색을 상승적으로 조율하려고 시도한다.
• 세포적 진화 알고리즘 또는 밈 알고리즘은 개체군의 개체 간의 위상적 근접 관계를 사용하여 짝짓기 선택을 제한하고 그에 따라 평균 이상 개체의 전파 속도를 줄인다. 이는 조기 수렴의 위험을 줄이기 위해 장기간에 걸쳐 개체군의 유전형 다양성을 유지하기 위함이다.
• 개미 집단 최적화는 페로몬 통신을 통해 경로를 형성하는 개미의 먹이 탐색 아이디어를 기반으로 한다. 주로 조합 최적화 및 그래프 문제에 적합하다.
• 입자 군집 최적화는 동물 떼의 행동 아이디어를 기반으로 한다. 주로 수치적 최적화 문제에 적합하다.
• 가우스 적응 – 정보 이론을 기반으로 한다. 제조 수율, 평균 적합도 또는 평균 정보의 최대화에 사용된다. 예를 들어 열역학 및 정보 이론에서의 엔트로피를 참조한다.

• 차분 진화 - 벡터의 차이를 기반으로 하며, 최적화 문제를 해결하는 데 적합하다.
• 입자군 최적화 - 동물 무리의 행동을 기반으로 하며, 이 또한 최적화 문제를 해결하는 데 적합하다.
• 개미집단 최적화 - 개미 무리가 경로상의 페로몬으로 의사소통하는 것을 기반으로 하며, 조합 최적화 문제를 해결하는 데 적합하다.
• 시뮬레이티드 어닐링 - 생물 개체의 진화를 모방하고 있다.

7. 1. 관련 기술 및 기타 전역 탐색 방법

• 밈 알고리즘 – 리처드 도킨스의 밈 개념에서 영감을 받은 하이브리드 방법이다. 일반적으로 개체군 기반 알고리즘(자주 EA)과 국소적 개선을 수행할 수 있는 개별 학습 절차의 형태를 취한다. 문제 특정 지식의 활용을 강조하고 국소적 및 전역적 탐색을 상승적으로 조율하려고 시도한다.
• 세포적 진화 알고리즘 또는 밈 알고리즘은 개체군의 개체 간의 위상적 근접 관계를 사용하여 짝짓기 선택을 제한하고 그에 따라 평균 이상 개체의 전파 속도를 줄인다. 이는 조기 수렴의 위험을 줄이기 위해 장기간에 걸쳐 개체군의 유전형 다양성을 유지하기 위함이다.
• 개미 집단 최적화는 페로몬 통신을 통해 경로를 형성하는 개미의 먹이 탐색 아이디어를 기반으로 한다. 주로 조합 최적화 및 그래프 문제에 적합하다.
• 입자 군집 최적화는 동물 떼의 행동 아이디어를 기반으로 한다. 주로 수치적 최적화 문제에 적합하다.
• 가우스 적응 – 정보 이론을 기반으로 한다. 제조 수율, 평균 적합도 또는 평균 정보의 최대화에 사용된다. 예를 들어 열역학 및 정보 이론에서의 엔트로피를 참조한다.

• 차분 진화 - 벡터의 차이를 기반으로 하며, 최적화 문제를 해결하는 데 적합하다.
• 입자군 최적화 - 동물 무리의 행동을 기반으로 하며, 이 또한 최적화 문제를 해결하는 데 적합하다.
• 개미집단 최적화 - 개미 무리가 경로상의 페로몬으로 의사소통하는 것을 기반으로 하며, 조합 최적화 문제를 해결하는 데 적합하다.
• 시뮬레이티드 어닐링 - 생물 개체의 진화를 모방하고 있다.

참조

_[1] 논문 Evolutionary algorithms: A critical review and its future prospects
_[2] 논문 "Evolutionary Algorithms for the Physical Design of VLSI Circuits" in Advances in Evolutionary Computing: Theory and Applications https://www.ifte.de/[...] Springer Verlag
_[3] 논문 Evolutionary algorithms and their applications to engineering problems 2020
_[4] 논문 Modelling and solving grid resource allocation problem with network resources for workflow applications http://link.springer[...] 2011
_[5] 웹사이트 International Conference on the Applications of Evolutionary Computation https://www.evostar.[...] The conference is part of the Evo* series. The conference proceedings are published by Springer 2022-12-23
_[6] 논문 Constrained Combinatorial Optimization with an Evolution Strategy https://link.springe[...] Springer 1994
_[7] 논문 Hybrid Self-Adaptive Evolution Strategies Guided by Neighborhood Structures for Combinatorial Optimization Problems.
_[8] 논문 A Survey on Cooperative Co-Evolutionary Algorithms. https://ieeexplore.i[...] 2023-05-22
_[9] 논문 Coevolutionary Principles https://link.springe[...] Springer Berlin Heidelberg 2012
_[10] 논문 Quality Diversity: A New Frontier for Evolutionary Computation 2016-07-12
_[11] 논문 Evolving a diversity of virtual creatures through novelty search and local competition http://dx.doi.org/10[...] ACM 2011-07-12
_[12] 논문 Robots that can adapt like animals http://dx.doi.org/10[...] 2015-05-27
_[13] 서적 Handbook of genetic algorithms https://www.worldcat[...] Van Nostrand Reinhold 1991
_[14] 논문 An evolutionary algorithm for the routing of multi-chip modules http://link.springer[...] Springer 2022-10-18
_[15] 서적 Handbook of Memetic Algorithms http://link.springer[...] Springer Berlin Heidelberg 2012
_[16] 논문 Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis https://ieeexplore.i[...] 1997
_[17] 논문 A comparative study of global and local selection in evolution strategies http://link.springer[...] Springer Berlin Heidelberg 2022-10-21
_[18] 서적 Cellular Genetic Algorithms http://link.springer[...] Springer US 2008
_[19] 논문 The theory of virtual alphabets http://link.springer[...] Springer-Verlag 2022-10-22
_[20] 서적 Genetic algorithms in optimisation, simulation, and modelling https://www.worldcat[...] IOS Press 1994
_[21] 서적 Genetic Algorithms + Data Structures = Evolution Programs https://www.worldcat[...] Springer 1996
_[22] 논문 Creating high-level components with a generative representation for body-brain evolution
_[23] 논문 Evolving Coordinated Quadruped Gaits with the HyperNEAT Generative Encoding http://www.ofria.com[...]
_[24] 논문 How a generative encoding fares as problem-regularity decreases http://jeffclune.com[...] Springer
_[25] 논문 Gene Expression Programming: A New Adaptive Algorithm for Solving Problems http://www.gene-expr[...]
_[26] 서적 Evolution and Optimum Seeking https://www.research[...] Wiley 1995
_[27] 서적 Evolutionary Computation 1 https://www.worldcat[...] Institute of Physics Publishing 2000
_[28] 서적 Industrial Applications of Evolutionary Algorithms http://link.springer[...] Springer Berlin Heidelberg 2012
_[29] 서적 Evolutionary algorithms in engineering and computer science : recent advances in genetic algorithms, evolution strategies, evolutionary programming, genetic programming, and industrial applications https://www.wiley.co[...] Wiley and Sons 1999
_[30] 서적 Genetic Algorithms and Engineering Optimization http://doi.wiley.com[...] John Wiley & Sons, Inc. 1999-12-17
_[31] 서적 Evolutionary scheduling https://www.worldcat[...] Springer 2007
_[32] 논문 Fast Rescheduling of Multiple Workflows to Constrained Heterogeneous Resources Using Multi-Criteria Memetic Computing 2013-04-22
_[33] 서적 Evolutionary Algorithms and Agricultural Systems http://link.springer[...] Springer US 2002
_[34] 논문 Optimized Collision Free Robot Move Statement Generation by the Evolutionary Software GLEAM http://link.springer[...] Springer 2022-12-28
_[35] 논문 Application of a Memetic Algorithm to the Portfolio Optimization Problem http://link.springer[...] Springer Berlin Heidelberg 2022-12-23
_[36] 서적 Evolutionary Computation in Economics and Finance http://link.springer[...] Physica-Verlag HD 2002
_[37] 서적 IEEE Antennas and Propagation Society Symposium, 2004 2004-06
_[38] 서적 Evolutionary Computation in Bioinformatics https://linkinghub.e[...] Elsevier 2003
_[39] 서적 Applying Evolutionary Algorithms Successfully - A Guide Gained from Realworld Applications https://publikatione[...] KIT Scientific Publishing 2022-12-23
_[40] 학술지 An overview of evolutionary algorithms: practical issues and common pitfalls https://linkinghub.e[...] 2001
_[41] 서적 Introduction to Evolutionary Computing http://link.springer[...] Springer Berlin Heidelberg 2015
_[42] 뉴스 Artificial intelligence is evolving all by itself https://www.science.[...] 2020-04-16
_[43] 서적 2006 IEEE International Conference on Evolutionary Computation IEEE 2006
_[44] 서적 2006 IEEE International Conference on Evolutionary Computation 2017-01-07
_[45] 서적 Computer Aided Graphing and Simulation Tools for AutoCAD Users CRC Press