유전 알고리즘 최적화 - yujeon algolijeum choejeoghwa

해양 오염사고를 대비한 계획으로, 최적화된 배치안들을 수집하여 분석하는 연구가 필수적이지만, 해양 오염사고 대응을 위한 최적을 배치안을 다양화하고 분석한 연구는 아직 선행되지 않았다. 이러한 필요성에 따라, 우리는 방제자원 배치 최적화를 위한 유전알고리즘을 고안하고 이를 통해 최적의 방제 자원 배치안을 10,000 개 도출하였다. k-평균 알고리즘으로 군집화한 결과, 예상 최대 유출지역인 여수, 대산, 울산에 대하여 두 개의 군집으로 확연히 구분되었다. 우리는 이러한 군집을 새몬 맵핑을 통해 이차원으로 사영하여 배치안의 분포도를 분석하였고, 군집에 포함되는 배치안들이 그렇지 않은 배치안보다 시뮬레이션의 결과가 우수함을 확인했다. 향후, 본 연구를 기반으로 성능이 우수한 근사모델을 구현하는 것이 가능할 것으로 보인다.

As a plan for oil spill accidents, research to collect and analyze optimal equipment assignments is essential. However, studies that have diversified and analyzed the optimal equipment assignments for responding to oil spill accidents have not been preceded. In response to the need for analyzing optimal equipment assignments study, we devised a genetic algorithm for optimal equipment assignments. The designed genetic algorithm yielded 10,000 optimal equipment assignments. We clustered using the k-means algorithm. As a result, the two clusters of Yeosu, Daesan, and Ulsan, which are expected to be the largest spills, were clearly identified. We also projected 16-dimensional data in two dimensions via Sammon’s mapping. The projected data were analyzed for distribution. We confirmed that results of the simulation were better than those of optimal equipment assignments included in the cluster.In the future, it will be possible to implement an approximate model with excellent performance based on this study.

이렇게 보니 GA의 알고리즘의 실행 단계가 비교적 단순하다고 볼 수 있다. 하지만 3번 단계인 자손 염색체를 생성하는 과정에서 몇 가지 다양한 기법들이 존재하는데, 다음 항목에서는 이러한 기법들에 대해 알아보자.

유전 알고리즘을 문제 해결에 적용하기 위해서는 다음과 같은 5가지 연산에 대해서 알고 있어야 한다.

1. 초기 염색체를 생성하는 연산

최초의 염색체를 생성하기 위해서는 이전의 염색체가 존재하지 않기 때문에 최초의 염색체를 생성하는 연산을 따로 정의해주어야 한다. GA에서 가장 많이 이용되는 방법은 규칙 없이 임의의 값으로 초기 염색체를 생성하는 것이다.

2. 적합도를 계산하는 연산

염색체에 표현된 정보를 토대로 적합도를 계산하는 연산이다. 이 연산은 해결하려는 문제에 따라 달라진다.

3. 적합도를 기준으로 자손 염색체를 선택하는 연산

자손 염색체를 생성할 때 흔히 적합도가 가장 높은 염색체들을 선택하는 것이 최고의 방법이라고 생각할 수 있다. 하지만 이러한 방법은 염색체의 다양성을 손상시키기 때문에 Global optimum을 찾기에는 부적합하다. 이러한 문제를 피하기 위해서 GA에서는 룰렛 휠 선택(Roulette Wheel Selection) 방법을 이용한다. 룰렛 휠 선택이란, 우리가 흔히 생각하는 원판을 돌리면서 확률에 기반해 결과가 도출되는 룰렛의 개념과 비슷하다고 생각하면 된다. 밑의 그림은 룰렛 휠 선택에 대한 확률적 수식이며 다음 그림은 수식을 룰렛 그림으로 나타낸 그림이다. 룰렛 그림에서 면적의 총 합은 1(100%)이다. 왜냐하면 각각이 확률값이며 확률의 합은 1이기 때문이다.

위와 같이 룰렛 휠 선택의 방법을 이용하게 되면 적합도가 높은 염색체가 룰렛에서 더 많은 비율의 면적을 차지할 것이고 이에 따라 높은 적합도의 염색체가 선택될 확률이 높아진다. 또 동시에 염색체의 다양성을 훼손시키지 않을 수 있다.

4. 선택된 염색체들로부터 자손 염색체들을 생성하는 연산 

방금 언급했던 룰렛 휠 선택 방법으로 선정된 두 개의 부모 염색체들로부터 하나의 자손 염색체를 생성한다. 이 때 GA에서는 자손 염색체를 생성하는 연산으로서 주로 Crossover이라는 연산을 사용한다. Crossover 연산에 대해 그림으로 설명하자면 다음과 같다.

먼저 두 개의 염색체들로부터 하나의 자손염색체를 생성하는 Crossover 연산이다.

다음은 두 개의 염색체들로부터 두 개의 division point(crossover point)를 임의로 설정하고 두 개의 자손염색체를 생성하는 그림이다.

5. 돌연변이 연산

지금까지 살펴보았던 룰렛 휠 선택을 통해 Crossover 연산만을 사용한다면 Local optimum에 빠지는 문제를 발생시킬 수 있다. 이러한 문제를 피하기 위해서 자손 염색체에 돌연변이 연산을 추가적으로 적용하는 방법이 있다.

보통은 0.1%나 0.05%등의 아주 낮은 확률로 돌연변이가 발생하도록 한다. 돌연변이를 발생시키는 연산은 매우 다양하지만 여기에서는 몇 가지 방법만 살펴보자.

우선 binary값인 0과 1에서 0을 1로, 또는 1을 0으로 바꿔주는 reverse 방법이 있다. 그리고 임의의 두 개의 유전자를 선택해서 서로의 위치를 바꾸는 exchange 방식이 있다.

다음은 각 유전자에 Gaussian(정규분포) 연산을 적용하는 것이다. 정확히 말해서 Gaussian error function을 사용한다. Gaussian 연산은 값이 작은 값들을 가장 likely하게 만들고 자주 generate하게 만들며 반면에 값이 큰 값들은 거의 generate되지 않도록 해주며 편차를 이용해 계산하게 된다. 이 방법은 다른 돌연변이 연산 방법들보다 알고리즘 종료 조건(기준=criteria)에 converge 하는 데에 더 효율적인 방법이다.

#참조 문헌

https://www.geeksforgeeks.org/mutation-algorithms-for-real-valued-parameters-ga/ 

Mutation Algorithms for Real-Valued Parameters (GA) - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

https://untitledtblog.tistory.com/110

[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm)

1. 소개 유전 알고리즘은 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 검색 방법이다. 유전 알고리즘은 이론적으로 전역 최적점을 찾을 수 있으며, 수학적으로