유전 알고리즘은 생물 유전학에 기본 이론을 두는 전역 탐색 알고리즘으로, 산업, 뉴럴 네트워크, 웹, 그리고 국방 등의 분야에서 활발히 사용되고 있다. 하지만 기존의 유전 알고리즘은 염색체의 개수가 고정되어 있는 형태여서 시뮬레이션 도중 초기에 주어진 상황보다 더 복잡한 상황이 주어질 수 있는 경우에는 적용이 힘들다는 한계점이 존재한다. 본 연구에서는 이를 극복하기 위해서 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 제안하였다. 그리고 염색체 수의 변화가 시뮬레이션 결과에 영향을 미치는 것을 확인하기 위하여 대 잠수함 HVU 호위 임무 시뮬레이션에 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 적용하였다. 시뮬레이션 결과 기존의 유전 알고리즘과는 달리 가변 염색체 유전 알고리즘에서는 더 복잡한 전술이 더 일찍 등장하였으며, 그에 따라 염색체 수가 증가하는 방향으로 진화가 일어나는 것을 확인할 수 있었다.
유전 알고리즘은 생물 유전학에 기본 이론을 두는 전역 탐색 알고리즘으로, 산업, 뉴럴 네트워크, 웹, 그리고 국방 등의 분야에서 활발히 사용되고 있다. 하지만 기존의 유전 알고리즘은 염색체의 개수가 고정되어 있는 형태여서 시뮬레이션 도중 초기에 주어진 상황보다 더 복잡한 상황이 주어질 수 있는 경우에는 적용이 힘들다는 한계점이 존재한다. 본 연구에서는 이를 극복하기 위해서 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 제안하였다. 그리고 염색체 수의 변화가 시뮬레이션 결과에 영향을 미치는 것을 확인하기 위하여 대 잠수함 HVU 호위 임무 시뮬레이션에 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 적용하였다. 시뮬레이션 결과 기존의 유전 알고리즘과는 달리 가변 염색체 유전 알고리즘에서는 더 복잡한 전술이 더 일찍 등장하였으며, 그에 따라 염색체 수가 증가하는 방향으로 진화가 일어나는 것을 확인할 수 있었다.
The Genetic Algorithm(GA) is a global search algorithm based on biological genetics. It is widely used in various fields such as industrial applications, artificial neural networks, web applications and defense industry. However, conventional Genetic Algorithm has difficulty maintaining feasibility ...
The Genetic Algorithm(GA) is a global search algorithm based on biological genetics. It is widely used in various fields such as industrial applications, artificial neural networks, web applications and defense industry. However, conventional Genetic Algorithm has difficulty maintaining feasibility in complicated situations due to its fixed number of chromosomes. This study proposes the Genetic Algorithm using variable chromosome with chromosome attachment. And in order to verify the implication of changing number of chromosomes in the simulation, it applies the Genetic Algorithm using variable chromosome with chromosome attachment to antisubmarine High Value Unit(HVU) escort mission simulation. As a result, the Genetic Algorithm using variable chromosome has produced complex strategies faster than the conventional method, indicating the increase of the number of chromosome during the process.
The Genetic Algorithm(GA) is a global search algorithm based on biological genetics. It is widely used in various fields such as industrial applications, artificial neural networks, web applications and defense industry. However, conventional Genetic Algorithm has difficulty maintaining feasibility in complicated situations due to its fixed number of chromosomes. This study proposes the Genetic Algorithm using variable chromosome with chromosome attachment. And in order to verify the implication of changing number of chromosomes in the simulation, it applies the Genetic Algorithm using variable chromosome with chromosome attachment to antisubmarine High Value Unit(HVU) escort mission simulation. As a result, the Genetic Algorithm using variable chromosome has produced complex strategies faster than the conventional method, indicating the increase of the number of chromosome during the process.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
각 실험에 대하여 한 번은 염색체 수의 변화가 없는 기존의 유전 알고리즘을 적용하여 실험을 하고, 다른 한 번은 본 연구에서 제안한 염색체 비분리를 적용한 유전 알고리즘을 적용하였다. 본 연구의 주요 목적은 예상보다 복잡한 상황에서 염색체 비분리를 적용함으로서 얻을 수 있는 이점을 알기 위한 것이므로, 염색체 비분리가 존재하지 않는 기존의 전통적인 유전 알고리즘과의 비교만을 수행하였다.
그렇다고 무턱대고 염색체의 개수를 늘려서 실험을 할 수 도 없었다. 이를 극복하기 위해서 본 연구에서는 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 제안하였다.
가설 설정
본 논문에서 제안하는 가변 염색체 유전 알고리즘은 세대가 지남에 따라서 하나의 개체가 가지고 있는 염색체의 개수가 변할 수 있는 유전 알고리즘이다. 설계하기에 따라서 하나의 개체가 하나의 염색체만을 가질 수도 있지만, 본 논문에서는 Fig. 1.과 같이 여러 개의 염색체를 가지도록 설계한 형태를 가정하였다.
제안 방법
시뮬레이션의 복잡도에 따른 차이를 알아보기 위하여 상대적으로 단순한 전술인 생존 우선 전술을 유도하는 시뮬레이션인 실험 1과 상대적으로 복잡한 전술인 공격 우선 전술을 유도하는 시뮬레이션인 실험 2를 수행하였다. 각 실험에 대하여 한 번은 염색체 수의 변화가 없는 기존의 유전 알고리즘을 적용하여 실험을 하고, 다른 한 번은 본 연구에서 제안한 염색체 비분리를 적용한 유전 알고리즘을 적용하였다. 본 연구의 주요 목적은 예상보다 복잡한 상황에서 염색체 비분리를 적용함으로서 얻을 수 있는 이점을 알기 위한 것이므로, 염색체 비분리가 존재하지 않는 기존의 전통적인 유전 알고리즘과의 비교만을 수행하였다.
에서 제시한 수치와 유사하게 교차율, 돌연변이율은 2%, 그리고 염색체 비분리율은 10%로 설정하였다. 그리고 한 세대 당 50개의 부모 개체를 두어 50회의 시뮬레이션을 수행하였다.
본 연구에서는 이를 개선하기 위해서 염색체 수에 가변성을 제공하는 새로운 유전 연산인 염색체 비분리가 추가된 유전 알고리즘을 제안하고, 대 잠수함 HVU 호위 임무 시뮬레이션에 적용하여 염색체 수의 변화와 생성되는 전술의 상관관계에 대해서 비교분석하였다.
시뮬레이션의 복잡도에 따른 차이를 알아보기 위하여 상대적으로 단순한 전술인 생존 우선 전술을 유도하는 시뮬레이션인 실험 1과 상대적으로 복잡한 전술인 공격 우선 전술을 유도하는 시뮬레이션인 실험 2를 수행하였다. 각 실험에 대하여 한 번은 염색체 수의 변화가 없는 기존의 유전 알고리즘을 적용하여 실험을 하고, 다른 한 번은 본 연구에서 제안한 염색체 비분리를 적용한 유전 알고리즘을 적용하였다.
이 모습이 점핑을 하는 것 같다고 해서 점핑 유전자라고 불린다. 점핑 유전자를 표현하기 위해서 복사-붙여넣기, 그리고 자르기-붙여넣기라는 유전 연산을 추가하였다. 이를 통하여 자손의 다양성을 강화할 수 있었고, 더 낮은 절대 에러율 내에서 최적해를 구할 수 있었다.
초기값으로는 유전 알고리즘 최적화를 위한 파라미터 연구[15]에서 제시한 수치와 유사하게 교차율, 돌연변이율은 2%, 그리고 염색체 비분리율은 10%로 설정하였다. 그리고 한 세대 당 50개의 부모 개체를 두어 50회의 시뮬레이션을 수행하였다.
기본적으로는 기존의 전통적인 유전알고리즘에서 제안하는 방법과 크게 다른 점이 없다. 하지만 염색체의 개수에 가변성을 주기 위하여 새롭게 제안한 염색체 비분리 연산을 위해서 교배와 자손을 만드는 과정을 세분화해서 설계하였다.
이론/모형
[3,4] 본 논문의 사례연구에서도 제안된 유전 알고리즘으로 염색체 개수 와 진화 결과의 상관관계를 알아보기 위하여 기존 연구에서 수행한 바 있는 대 잠수함 HVU 호위 임무 시뮬레이션[14]에 유전 알고리즘을 적용하였다.
전술을 표현하기 위하여 "If-then" 형식의 규칙을 사용하였다.
성능/효과
본 시뮬레이션에서는 두 가지의 전술을 표현하기 위한 형태로 규칙이 구성되어있다. 따라서 기존 연구에서 제공한 사실 집합은 적 잠수함을 무시하고 목적지로 돌진만 하는 생존 우선 전술과 적 잠수함을 우선 탐지 후 섬멸하고 이동하는 공격 우선 전술을 만들 수 있었다. 임무 시나리오는 Fig.
실험 결과, 복잡도가 높지 않거나 필요한 염색체의 수를 정확히 예측한 경우에는 기존의 유전 알고리즘과 본 연구에서 제안한 유전 알고리즘 사이에 큰 차이를 발견할 수 없었다. 하지만 상황에 따라서 스스로 염색체의 개수를 늘리거나 줄여가며 진화를 할 수 있기 때문에 최적의 염색체 개수를 모르는 경우에는 적절한 염색체 수를 스스로 찾아가며 기존의 유전 알고리즘보다 더 좋은 결과를 낼 수 있었다.
점핑 유전자를 표현하기 위해서 복사-붙여넣기, 그리고 자르기-붙여넣기라는 유전 연산을 추가하였다. 이를 통하여 자손의 다양성을 강화할 수 있었고, 더 낮은 절대 에러율 내에서 최적해를 구할 수 있었다.
(a)와 같다. 주로 아군의 생존율을 고려한 결과 기존의 고정된 개수의 유전 알고리즘과 본 논문에서 제안한 가변 염색체 유전 알고리즘 모두 적합도가 약 0.18정도인 전투 회피 전술로 최종 진화를 하였다. 전투 회피 전술은 적 잠수함을 무시하고 무조건 목표를 향해 이동하는 매우 단순한 형태의 전술이다.
기존의 고정 염색체 유전 알고리즘의 경우에는 실험 1에서와 마찬가지로 전투 회피 전술이 최종 형태로 등장하였다. 하지만 가변 염색체 유전 알고리즘의 경우에는 4세대 이후부터 적 잠수함이 나타나면 탐지 후 상황을 판단하여 공격까지 하는 형태의 공격 우선 전술이 등장하였고, 결과적으로 훨씬 높은 적합도 값을 얻을 수 있었다. 공격 우선 전술은 적 잠수함에 대한 탐지, 식별, 공격 판단, 허위 표적 판단 등의 복잡한 의사 결정 과정이 필요한 전술이다.
실험 결과, 복잡도가 높지 않거나 필요한 염색체의 수를 정확히 예측한 경우에는 기존의 유전 알고리즘과 본 연구에서 제안한 유전 알고리즘 사이에 큰 차이를 발견할 수 없었다. 하지만 상황에 따라서 스스로 염색체의 개수를 늘리거나 줄여가며 진화를 할 수 있기 때문에 최적의 염색체 개수를 모르는 경우에는 적절한 염색체 수를 스스로 찾아가며 기존의 유전 알고리즘보다 더 좋은 결과를 낼 수 있었다.
실험 1의 경우에는 목표로 하는 전술이 너무 간단한 형태여서 기존의 유전 알고리즘과 가변 염색체 유전 알고리즘의 차이가 거의 없었다. 하지만 실험 2에서와 같이 보다 복잡한 전술을 요구하는 경우에는 기존의 유전 알고리즘은 염색체 개수의 한계로 인해서 복잡한 전술로 진화하는데 어려움을 겪었지만, 가변 염색체 유전 알고리즘의 경우에는 염색체 개수를 늘려가며 더 복잡한 전술로 진화하는 데 성공을 거두었다.
후속연구
기존의 유전 알고리즘도 처음부터 적절한 수의 염색체를 설정해준다면 얼마든지 복잡한 형태로 진화할 수 있겠지만, 적절한 염색체의 개수가 몇 개인지 알 수 없는 경우에는 염색체 비분리 연산을 적용하여 염색체 개수에 가변성을 주는 것이 훨씬 유리할 것이다. 또한 가변 길이 염색체 유전 알고리즘이나 JGGA와 같은 개선된 유전 알고리즘의 유전 연산을 추가한다면 보다 낮은 에러율과 높은 확장성도 갖출 수 있을 것이다.
향후에는 환경의 복잡도에 영향을 주고 더 다양한 전술이 등장할 수 있도록 사실 집합을 구체화하여 실험을 할 예정이다. 또한 가변 염색체 유전 알고리즘을 인공 뉴럴 네트워크에 적용하는 방법에 대해서 연구를 진행할 예정이다.
향후에는 환경의 복잡도에 영향을 주고 더 다양한 전술이 등장할 수 있도록 사실 집합을 구체화하여 실험을 할 예정이다. 또한 가변 염색체 유전 알고리즘을 인공 뉴럴 네트워크에 적용하는 방법에 대해서 연구를 진행할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
기존의 유전 알고리즘의 한계점은?
유전 알고리즘은 생물 유전학에 기본 이론을 두는 전역 탐색 알고리즘으로, 산업, 뉴럴 네트워크, 웹, 그리고 국방 등의 분야에서 활발히 사용되고 있다. 하지만 기존의 유전 알고리즘은 염색체의 개수가 고정되어 있는 형태여서 시뮬레이션 도중 초기에 주어진 상황보다 더 복잡한 상황이 주어질 수 있는 경우에는 적용이 힘들다는 한계점이 존재한다. 본 연구에서는 이를 극복하기 위해서 염색체 비분리를 적용한 가변 염색체 유전 알고리즘을 제안하였다.
유전 알고리즘이란?
유전 알고리즘은 자연 선택의 원리와 자연계의 생물 유전학에 기본 이론을 두는 병렬적이고 전역적인 탐색 알고리즘이다. 최근 생물의 진화과정, 즉 자연선택과 유전법칙을 적용한 진화전략, 유전 프로그래밍 등의 여러 형태의 이론과 기법들이 활발히 연구되고 있다.
진화에서 염색체 비분리 현상이 매우 중요한 메커니즘인 이유는?
하지만 염색체 수에 변이가 발생하는 염색체 돌연변이에 해당하는 염색체 비분리 현상 또한 매우 중요한 메커니즘이다.[9] 실생활에서 염색체 비분리는 다운증후군이나 터너증후군 같은 질병을 야기하지만[10,11] 진화에서는 염색체 수의 변화를 가져다 줄 수 있기 때문이다.
참고문헌 (15)
Golberg, David E. "Genetic algorithms in search, optimization, and machine learning." Addison-Wesley (1989).
Arabali, Amirsaman, et al. "Genetic-algorithm-based optimization approach for energy management." Power Delivery, IEEE Transactions on 28.1 (2013): 162-170.
Jung, Chan-Ho, et al. "Many-to-Many Warship Combat Tactics Generation Methodology Using the Evolutionary Simulation." Journal of the Korea Society for Simulation 20.3 (2011): 79-88.
You, Yong-Jun, et al. "Simulation-Based Tactics Generation for Warship Combat Using the Genetic Algorithm." IEICE TRANSACTIONS on Information and Systems 94.12 (2011): 2533-2536.
Wright, Sewall. The roles of mutation, inbreeding, crossbreeding, and selection in evolution. Vol. 1. na, 1932.
Leigh, E. G. Natural selection and mutability. Am. Nat. 104, 301-305 (1970).
Ishii, K., Matsuda, H., Iwasa, Y. & Sasaki, A. Evolutionarily stable mutation rate in a periodically changing environment. Genetics 121, 163-174 (1989).
Taddei, F. et al. Role of mutator alleles in adaptive evolution. Nature 387 700-702 (1997).
1.Sanchez-Perez, Isabel, et al. "The DASH complex and Klp5/Klp6 kinesin coordinate bipolar chromosome attachment in fission yeast." The EMBO Journal 24.16 (2005): 2931-2943.
Hall, Heather, Patricia Hunt, and Terry Hassold. "Meiosis and sex chromosome aneuploidy: how meiotic errors cause aneuploidy; how aneuploidy causes meiotic errors." Current opinion in genetics & development 16.3 (2006): 323-329.
Li, Yun-Ying, et al. "Disruption of mitotic spindle orientation in a yeast dynein mutant." Proceedings of the National Academy of Sciences 90.21 (1993): 10096-10100.
1.Srikanth, Radhakrishnan, et al. "A variable-length genetic algorithm for clustering and classification." Pattern Recognition Letters 16.8 (1995): 789-800.
Tang, Kit Sang, et al. "A theoretical development and analysis of jumping gene genetic algorithm." IEEE Transactions on Industrial Informatics 7.3 (2011): 408-418.
Haupt, Randy L. "Optimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors." Antennas and Propagation Society International Symposium, 2000. IEEE. Vol. 2. IEEE, 2000.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.