유전 알고리즘

3. 구성

유전 알고리즘은 최적화 문제에서 후보 해(개체)를 더 나은 해로 진화시키는 방법이다. 각 후보 해는 변경 가능한 속성(염색체 또는 유전자형)을 가지며, 보통 0과 1의 문자열(이진수)로 표현되지만 다른 인코딩도 가능하다.^[4]

진화는 무작위로 생성된 개체 집단에서 시작되며, 각 반복을 '세대'라고 부른다. 각 세대에서 모든 개체의 적합도는 목적 함수 값으로 평가된다. 적합도가 높은 개체는 확률적으로 선택되어 유전자가 수정(재조합, 돌연변이)되고, 새로운 세대를 형성한다. 이 새로운 세대가 다음 반복에 사용되며, 최대 세대 수에 도달하거나 만족스러운 적합도 수준에 도달하면 알고리즘이 종료된다.

유전 알고리즘은 구현은 간단하지만, 그 동작 원리를 이해하기는 어렵다. 특히 실제 문제에서 높은 적합도의 해를 생성하는 이유를 명확히 설명하기 어렵다. 구성 요소 가설(Building Block Hypothesis, BBH)은 평균 이상의 적합도를 가진 짧고 낮은 차수의 스키마(구성 요소)를 식별하고 재결합하여 적응을 수행하는 휴리스틱 방법을 설명하며, 유전 알고리즘이 이 휴리스틱을 암시적이고 효율적으로 구현한다고 가정한다.^[9][10] 그러나 이 가설의 타당성에 대해서는 논란의 여지가 있다.^[11][12][13]

유전 알고리즘은 해(데이터)를 유전자로 표현한 여러 "개체"를 준비하고, 적응도가 높은 개체를 우선적으로 선택하여 교차 및 돌연변이 등의 연산을 반복하면서 해를 탐색한다. 적응도는 적응도 함수로 결정된다.

이 방법은 평가 함수의 미분 가능성이나 단봉성 등에 대한 사전 지식 없이도 적용할 수 있다는 장점이 있다. 필요한 조건은 평가 함수의 전순서성과 탐색 공간의 위상(topology)뿐이다. 또한, 유전자 표현 방법에 따라 조합 최적화 문제나 NP-난해 문제 등 다양한 문제에 적용할 수 있다.

3. 1. 요구 조건

• 해를 유전자 형태로 표현
• 적합도 함수를 통해 해의 적합도 계산

• 해 영역의 유전적 표현
• 해 영역을 평가하는 적합도 함수

3. 2. 연산

• 선택: 한 세대에서 다음 세대로 전달될 해의 후보를 선택한다. 균등 비례 룰렛 휠 선택, 토너먼트 선택, 순위 기반 선택 등의 방법이 있다. 어떤 해를 선택하는지는 유전 알고리즘의 성능에 큰 영향을 미치므로, 해 집단의 다양성을 유지하면서 평균적인 적합도를 높이는 것이 중요하다.
• 교차: 선택된 해들이 교배를 통해 다음 세대의 해를 생성한다. 실제 생명체의 염색체 재조합처럼, 부모 해의 유전자들을 특정 위치를 기준으로 서로 교차시켜 자식 해를 만든다. 비트 단위 교차, 블록 단위 교차 등 다양한 방법이 있으며, 우수한 해가 변형되지 않도록 교차를 확률적으로 수행하기도 한다.
• 변이: 해의 유전자 내 유전 인자 순서나 값을 임의로 변경하여 다른 해로 변형시킨다. 이는 전체 세대가 지역 최적해에 빠지는 것을 방지하고 해 집단의 다양성을 높이는 주요 기법이다.
• 대치: 교차, 변이를 거쳐 만들어진 새로운 해를 해 집단에 추가하고, 기존 해 중 열등한 해를 제외시킨다. 가장 품질이 나쁜 해를 대치하거나, 새로운 해와 가장 비슷한 부모 해를 대치하는 방법 등이 있다.

선택 알고리즘의 종류

교차 알고리즘의 종류

돌연변이돌연변이는 유전자형이 비트열인 경우, 특정 유전자좌의 0과 1을 바꾸거나, 숫자인 경우 난수로 바꾸는 방식으로 수행된다. 유전자좌의 위치를 변경하는 방법도 사용된다.

3. 3. 알고리즘 흐름

• 선택: 적합도 기반 과정을 통해 현 세대에서 개체를 선택한다. 적합도가 높은 개체가 선택될 확률이 높다.
• 교차: 선택된 두 개체의 유전자를 결합하여 새로운 개체를 생성한다. (예: 아담과 하와)
• 돌연변이: 선택된 개체의 유전자를 임의로 변경하여 새로운 개체를 생성한다. 이는 지역 최적점에 빠지지 않도록 하는 중요한 역할을 한다.

• 최소 기준을 만족하는 해결책 발견
• 고정된 세대 수 도달
• 할당된 예산(계산 시간/비용) 도달
• 최고 순위 해결책의 적합도가 정체기에 도달하여 더 나은 결과가 생성되지 않음
• 수동 검사
• 위 조건들의 조합

4. 이론

유전 알고리즘은 다른 메타휴리스틱스와 비교했을 때, 주요 탐색 수단인 교차가 국소 탐색이 아니라는 점에서 큰 차이를 보인다. 이 때문에 유전 알고리즘의 유효성에 대한 의문이 제기되기도 했다. 초기에는 실험을 통해 유효성을 검증하는 연구가 많았지만, 1980년대 후반부터는 이론적 분석이 활발해졌다.

SGA는 '''S'''imple '''G'''enetic '''A'''lgorithm(단순 GA)의 약자로, 유전 알고리즘 분석을 단순화한 모델이다. SGA는 다음과 같은 특징을 갖는다.

• 유전자 표현: 0과 1만 사용
• 룰렛 선택
• 1점 교차
• 돌연변이: 유전자좌 1개의 값을 반전

4. 1. 스키마 이론

• 정의 길이 (δ(H)): 스키마에서 가장 왼쪽의 *가 아닌 문자와 가장 오른쪽의 *가 아닌 문자 사이의 거리. 위의 예에서 δ(H) = 3이다.
• 오더 (O(H)): 스키마에서 *가 아닌 문자의 개수. 위의 예에서 O(H) = 3이다.

• *f(H)*: 스키마 *H*를 포함하는 개체의 평균 적합도
• $\backslash overline\{f\}$: 전체 개체의 평균 적합도
• *l*: 유전자형의 길이
• *p_c*: 교차율
• *p_m*: 돌연변이율

• p_c* >> *p_m* 이고, *δ(H)* > *O(H)* 이므로, *O(H)⋅p_m*는 무시할 수 있다. 따라서 스키마 정리는 다음 조건을 만족하는 스키마의 수가 지수 함수적으로 증가함을 보여준다.

• 작은 정의 길이 (*δ(H)*)
• 전체 평균보다 높은 *f(H)*

4. 2. 스키마 정리와 빌딩 블록 가설

• *f(H)*는 스키마 *H*를 포함하는 개체의 평균 적합도
• $\backslash overline\{f\}$는 모든 개체의 평균 적합도
• *l*은 유전자형의 길이
• *p_c*는 교차율
• *p_m*는 돌연변이율

• p_c* >> *p_m* 이고, *δ(H)* > *O(H)* 이므로, *O(H)⋅p_m*는 무시할 수 있다. 따라서 이 정리는 정의 길이 *δ(H)*가 작고 *f(H)*가 전체 평균보다 항상 큰 스키마의 수는 지수 함수적으로 증가함을 의미한다.

5. 문제점

유전 알고리즘(GA)은 다양한 문제에 적용할 수 있지만, 문제의 특성이나 사용 방식에 따라 효과적으로 탐색하지 못하는 경우가 있다. 자주 발생하는 문제점으로는 초기 수렴, 히치하이킹 등이 있다.

5. 1. 초기 수렴

5. 2. 히치하이킹

6. 확장

GA에는 다양한 확장 기법이 존재한다. 여기서는 유명한 몇 가지를 소개한다.

Messy GA(Messy GA)는 빌딩 블록 가설, 특히 정의 길이 δ(H)가 작아야 한다는 약점을 극복하기 위해 Goldberg가 제안한 유전 알고리즘의 확장 기법이다. 유전자 표현은 유전자좌의 위치와 그 값의 쌍으로 표현한다. 여기에 "컷"과 "슬라이스"라는 기법을 사용하여 탐색을 진행한다. Goldberg는 이를 이용하여 GA로는 매우 탐색하기 어려운 함수의 최적해 도출에 성공했다. 그러나 이 기법은 문제에 대한 상당히 자세한 사전 지식이 필요하기 때문에 실제 응용 사례는 거의 없다.

CHC는 1990년 Eshelman에 의해 제안된 GA(유전 알고리즘)의 확장 기법이다. 이 이름은 다음 세 가지의 머리글자를 딴 것이다.

• 2세대 엘리트 선택(Cross generational elitist selection)
• 이종 간 교차(Heterogeneous recombination)
• 대변동 돌연변이(Cataclysmic mutation)

7. 응용 분야

유전 알고리즘은 특정 문제를 풀기 위한 알고리즘이라기보다는 문제 해결을 위한 접근 방식에 가깝다. 유전 알고리즘으로 표현 가능한 모든 문제에 적용할 수 있다. 일반적으로 문제가 매우 복잡하여 계산이 불가능할 경우, 유전 알고리즘을 통해 실제 최적해는 아니더라도 최적해에 가까운 답을 얻을 수 있다. 이 경우, 해당 문제에 최적화된 알고리즘보다는 성능이 떨어지지만, 대부분 수용 가능한 수준의 해를 제공한다.

생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘으로 진화 전략, 유전 프로그래밍 등 다양한 형태의 이론과 기법들이 최근 활발히 연구되고 있다. 유전 알고리즘은 이 중 가장 기본적이고 대표적인 알고리즘으로, 자연과학, 공학 및 인문 사회 과학 분야에서 비선형 또는 계산 불가능한 복잡한 문제를 해결하는 데 널리 응용되고 있다.

• 개미 집단 최적화(ACO): 먹이를 찾는 개미 집단의 행동에서 영감을 얻은 기법이다.
• 담금질 기법(SA): 해를 하나만 사용한다는 점이 가장 큰 차이점이다.
• 미미틱 알고리즘: 지역 탐색 기법과 유전 알고리즘을 결합하여 빠른 시간 안에 좋은 해를 찾는 방법이다.
• 유전 프로그래밍: 교차와 변이를 사용하는 등 유전 알고리즘과 유사하며, 해를 프로그램으로 표현하는 것이 특징이다.
• 진화 연산: 생물의 진화에서 영감을 얻은 기법의 총칭이다. 최근에는 진화 연산에 속하는 기법들의 차이가 점차 줄어들고 있다.
• 진화 전략: 교차를 사용하지 않고 변이에 의존하는 탐색 기법이다.
• 진화 프로그래밍: 변이를 주로 사용하는 기법으로 진화 전략과 유사하다. 초기에는 해를 유한 오토마타로 나타냈고, 현재도 고정된 표현을 사용하지 않는 것이 특징이다.

8. 관련 기법

유전적 프로그래밍(genetic programming; GP)은 J. Koza가 제안한 유전 알고리즘을 확장한 것 중 하나이다. 유전자를 트리 구조로 함으로써 식이나 프로그램 등을 다룰 수 있도록 했다. 공학 분야뿐만 아니라 경제 분야 등에도 널리 활용되고 있다.

9. 한계

유전 알고리즘(GA)은 다양한 문제에 적용할 수 있는 기법이지만, 문제의 특성이나 사용 방식에 따라 효과적으로 탐색하지 못하는 경우가 있다. 여기서는 자주 발생하는 유전 알고리즘의 문제점들을 정리한다.

참조

_[1] 서적 Evolutionary algorithms https://books.google[...] John Wiley & Sons
_[2] 서적 Proceedings of the 2018 International Conference on Computing and Artificial Intelligence Association for Computing Machinery 2018-03-12
_[3] 학술지 Neuroevolutionary representations for learning heterogeneous treatment effects 2023
_[4] 학술지 Initialization of Feature Selection Search for Classification (sec. 3) https://www.jair.org[...] 2022
_[5] 서적 Genetic algorithms with multi-parent recombination
_[6] 서적 On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection
_[7] 서적 Handbook of Evolutionary Computation Institute of Physics Publishing
_[8] 서적 Handbook of Natural Computing Springer Berlin Heidelberg 2012
_[9] 서적 Scalable Optimization via Probabilistic Modeling 2006-01-01
_[10] 서적 BOA: The Bayesian Optimization Algorithm http://dl.acm.org/ci[...] 1999-01-01
_[11] 서적 Linkage in Evolutionary Computation 2008-01-01
_[12] 학술지 On the Taxonomy of Optimization Problems Under Estimation of Distribution Algorithms 2012-11-08
_[13] 서적 Proceedings of the 15th annual conference on Genetic and evolutionary computation 2013-01-01
_[14] 학술지 An efficient algorithm for function optimization: modified stem cells algorithm 2012-11-19
_[15] 간행물 No Free Lunch Theorems for Optimisation Santa Fe Institute
_[16] 서적 Parallel Problem Solving from Nature
_[17] 학술지 An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithms http://www.cs.umsl.e[...] 2013-07-02
_[18] 학술지 HELGA: a heterogeneous encoding lifelike genetic algorithm for population evolution modeling and simulation
_[19] 컨퍼런스 Removing the genetics from the standard genetic algorithm http://www.ri.cmu.ed[...]
_[20] 학술지 On the convergence of genetic algorithms – a variational approach
_[21] 학술지 Convergence of genetic algorithms
_[22] 학술지 Adaptive probabilities of crossover and mutation in genetic algorithms http://eprints.iisc.[...]
_[23] 학술지 Convergence enhanced genetic algorithm with successive zooming method for solving continuous optimization problems
_[24] 학술지 Clustering-Based Adaptive Crossover and Mutation Probabilities for Genetic Algorithms
_[25] 학술지 New crossover operators using dominance and co-dominance principles for faster convergence of genetic algorithms
_[26] 학술지 Flexible networked rural electrification using levelized interpolative genetic algorithm
_[27] 웹사이트 Evolution-in-a-nutshell http://www.thisurlis[...]
_[28] 학술지 Messy Genetic Algorithms : Motivation Analysis, and First Results http://www.complex-s[...]
_[29] 웹사이트 Gene expression: The missing link in evolutionary computation https://www.osti.gov[...]
_[30] PhD Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms http://portal.acm.or[...] Dept. Computer Science, University of Michigan, Ann Arbour 1997
_[31] 학술지 Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II http://www.mdpi.com/[...]
_[32] 웹사이트 A solar energy system that tracks the sun https://www.ted.com/[...] 2009-02-02
_[33] 웹사이트 Automated Antenna Design with Evolutionary Algorithms http://ti.arc.nasa.g[...]
_[34] 웹사이트 Flexible Muscle-Based Locomotion for Bipedal Creatures http://goatstream.co[...]
_[35] 학술지 Aerodynamic optimisation of a hypersonic reentry vehicle based on solution of the Boltzmann–BGK equation and evolutionary optimisation https://cronfa.swan.[...] 2017-12
_[36] 서적 The Algorithm Design Manual Springer Science+Business Media
_[37] 논문 Computing machinery and intelligence 1950-10-01
_[38] 논문 Esempi numerici di processi di evoluzione
_[39] 논문 Symbiogenetic evolution processes realized by artificial methods
_[40] 논문 Simulation of genetic systems by automatic digital computers. I. Introduction
_[41] 서적 Computer Models in Genetics McGraw-Hill
_[42] 서적 Computer Simulation in Genetics John Wiley & Sons
_[43] 뉴스 02.27.96 - UC Berkeley's Hans Bremermann, professor emeritus and pioneer in mathematical biology, has died at 69 http://berkeley.edu/[...] 1996-02-27
_[44] 서적 Evolutionary Computation: The Fossil Record IEEE Press
_[45] 논문 Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life
_[46] 서적 Evolutionsstrategie Holzmann-Froboog
_[47] 서적 Numerische Optimierung von Computer-Modellen (PhD thesis)
_[48] 서적 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie : mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie Birkhäuser
_[49] 서적 Numerical optimization of computer models (Translation of 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie Wiley
_[50] 서적 An Approach to Designing an Unmanned Helicopter Autopilot Using Genetic Algorithms and Simulated Annealing https://books.google[...]
_[51] 뉴스 What's the Best Answer? It's Survival of the Fittest https://www.nytimes.[...] 1990-08-29
_[52] 웹사이트 Fifteen years and counting http://www.futuresma[...] 2009-08-01
_[53] 웹사이트 Evolver: Sophisticated Optimization for Spreadsheets http://www.palisade.[...]
_[54] 논문 Benchmarks for Evaluating Optimization Algorithms and Benchmarking MATLAB Derivative-Free Optimizers for Practitioners' Rapid Access
_[55] 서적 Evolutionary algorithms for the physical design of VLSI circuits https://www.ifte.de/[...] Springer, pp. 683-712, 2003
_[56] 서적 BOA: The Bayesian Optimization Algorithm http://dl.acm.org/ci[...] 1999-01-01
_[57] 서적 Hierarchical Bayesian optimization algorithm : toward a new generation of evolutionary algorithms Springer 2005
_[58] 서적 Parallel Problem Solving from Nature, PPSN XI 2010-09-11
_[59] 논문 Gene Expression Programming: A New Adaptive Algorithm for Solving Problems http://www.gene-expr[...]
_[60] 서적 Genetic Algorithms and Grouping Problems John Wiley & Sons Ltd
_[61] 논문 Model-Based Search for Combinatorial Optimization: A Critical Survey 2004-10-01
_[62] 간행물 A comparison of particle swarm optimization and the genetic algorithm https://www.mit.edu/[...]
_[63] 논문 Automatic Test Case Optimization: A Bacteriologic Algorithm http://www.irisa.fr/[...] 2005-03-01
_[64] 논문 Transforming Geocentric Cartesian Coordinates to Geodetic Coordinates by Using Differential Search Algorithm
_[65] 논문 On the Efficiency of Gaussian Adaptation 1991-12-01
_[66] 웹사이트 ［CEDEC 2008＃08］生き物を相手にするようなゲームを作る～遺伝的アルゴリズム https://www.4gamer.n[...] Aetas 2008-09-11