[논문]유전자알고리즘에서 단성생식과 양성생식을 혼용한 번식을 통한 개체진화 속도향상

정성훈

doi:10.9708/jksci.2011.16.3.045

유전자알고리즘에서 단성생식과 양성생식을 혼용한 번식을 통한 개체진화 속도향상
Improvement of evolution speed of individuals through hybrid reproduction of monogenesis and gamogenesis in genetic algorithms 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.16 no.3, 2011년, pp.45 - 51

초록
AI-Helper

본 논문에서는 유전자알고리즘에서 단성생식과 양성생식을 혼용하여 개체진화 속도를 향상시키는 방법에 대하여 제안한다. 단성생식은 암수의 구분이 없는 세균이나 단세포 생물이 두 개의 개체로 분열되는 방법으로 유전적으로 지역적 탐색에 유리하며 양성생식은 암수의 구분이 있는 개체가 만나 생식하는 방법으로 유전적 다양성을 확보하는데 유리하다. 이러한 특성은 유전자알고리즘에서 개체의 진화속도를 향상시키는데 적절히 이용될 수 있다. 본 논문에서는 선택된 개체가 상대적으로 좋은 개체의 경우 진화를 위하여 지역적 탐색을 강화하는 단성생식을 하게 하고 상대적으로 좋지 않은 개체의 경우 유전자의 다양성을 확보하여 전역적 탐색을 강화하는 양성생식을 하게 하였다. 단성생식의 경우 지역적 탐색을 강화하기 위하여 돌연변이 확률을 기존의 유전자알고리즘 보다 낮추었으며 양성생식의 경우 유전자의 다양성 확보를 위하여 돌연변이 확률을 기존의 유전자알고리즘 보다 크게 높였다. 4가지 함수최적화 문제에 적용해본 결과 3개의 함수에서 성능이 매우 좋았으나 전역 최적해가 분산되어 있는 4번째 함수에서는 성능이 좋지 못하였다. 이는 전역최적해가 분산되어 있는 경우 안정적 진화에 혼란을 주기 때문인 것으로 판단된다.

Abstract ▼ AI-Helper

This paper proposes a method to accelerate the evolution speed of individuals through hybrid reproduction of monogenesis and gamogenesis. Monogenesis as a reproduction method that bacteria or monad without sexual distinction divide into two individuals has an advantage for local search and gamogenesis as a reproduction method that individuals with sexual distinction mate and breed the offsprings has an advantages for keeping the diversity of individuals. These properties can be properly used for improvement of evolution speed of individuals in genetic algorithms. In this paper, we made relatively good individuals among selected parents to do monogenesis for local search and forced relatively bad individuals among selected parents to do gamogenesis for global search by increasing the diversity of chromosomes. The mutation probability for monogenesis was set to a lower value than that of original genetic algorithm for local search and the mutation probability for gamogenesis was set to a higher value than that of original genetic algorithm for global search. Experimental results with four function optimization problems showed that the performances of three functions were very good, but the performances of fourth function with distributed global optima were not good. This was because distributed global optima prevented individuals from steady evolution.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

실험은 단순 유전자알고리즘과 비교하였다. 기존에 여러 가지 방법으로 성능을 향상시킨 유전자알고리즘이 존재하지만 본 논문에서는 단성생식과 양성생식을 혼용한 번식이 개체 속도 향상에 미치는 영향을 분석하기 위하여 단순 알고리즘과 비교하였다. 기존의 성능향상 방법은 본 논문에서 제안하는 것과 같은 번식방법을 혼용한 것이 아니기 때문에 단순 비교하기가 힘들다.
본 논문에서는 단성생식방법과 양성생식 방법을 혼용하여 번식을 함으로서 단성생식 방법의 장점과 양성생식 방법의 장점을 취할 수 있는 방법을 제안하였다. 즉, 낮은 등급의 개체는 양성생식과 높은 돌연변이 확률로 넓은 영역에 걸쳐서 탐색하게 하고 좋은 등급의 개체는 단성생식과 낮은 돌연변이로 안정적인 진화를 가능하게 하였다.
본 논문에서는 최적해로의 지속적인 진화에 유리한 단성생식 방법과 유전적 다양성을 확보할 수 있어서 지역최적화에 빠지는 것을 줄여줄 수 있는 양성생식을 혼용한 번식 방법을 사용하여 유전자알고리즘의 개체 진화 속도를 향상시키는 방법을 제안한다. 기존의 유전자알고리즘에서는 오로지 양성생식만을 사용하기 때문에 전역 최적해 근처에 있는 개체임에도 불구하고 다른 영역에 자식을 생성하는 경우가 있으며 전역 최적해에서 멀리 떨어져 있음에도 불구하고 유전적 다양성 형성에 크게 기여하지 못하는 문제가 발생하였다.
결국 본 논문에서 제안한 방법은 최적해가 넓게 분포되어 있는 문제보다는 비교적 좁은 곳에 분포되어 있으며 최적해 근처에 지역최적해가 많은 경우에 기존 방법보다 더 좋은 성능을 낼 수 있다. 본 논문의 핵심내용은 기존의 유전자알고리즘이 양성생식만을 수행하는데 비하여 단성생식과 양성생식을 혼용하여 전역 최적해로의 안정적 진화와 지역 최적해에서 쉽게 벗어나는 두 효과를 거둔 것에 있다 하겠다. 실험결과 이러한 효과가 있음을 확인할 수 있었다.
이를 해결하기 위하여 본 논문에서는 각 개체의 적합도에 따라서 등급을 매긴 후 선택된 부모 개체의 등급이 좋은 경우 단성생식을 하게하고 그렇지 않은 경우 양성생식을 하게 하였다. 또한 단성생식을 하는 개체는 세부적인 탐색을 가능하게 하기 위하여 돌연변이 확률을 낮추고 양성생식을 한 개체는 돌연변이를 높게 하여 다양성 확보에 도움이 되게 하였다.

제안 방법

본 논문에서 제안한 단성생식과 양성생식을 혼용한 번식방법을 적용한 유전자알고리즘은 Algorithm 1 과 같다.
본 논문에서 제안한 방법이 유전자알고리즘의 개체 진화에 끼치는 영향을 분석하기 위하여 여러 논문에서 많이 사용되어온 4개의 함수 최적화 문제를 적용하여 실험하였다 [4,8,9]. 수식 1에 주어져 있는 4개의 함수 최적화 문제는 DeJong 2 함수 (f₁), DeJong 5 함수 (f₂), Mexican Hat 함수 (f₃), Schafer 2 함수(f₄)로서 그림 1은 4개 함수의 입출력관계를 보여준다.
즉, 유전자알고리즘의 개체 중에서 어떤 임의의 개체가 최고의 적합도를 갖는 x₁과 x₂의 위치를 찾아가는 경우 그 때의 세대 수를 최적화 성공 세대수로 기록하였다. 유전자 알고리즘의 경우 초기 개체의 분포에 따라서 성능이 달라지는 특성을 고려하여 10개의 다른 무작위 개체로 실험한 후 평균을 구하였다. 표준편차도 구하였으나 간단히 나타내기 위하여 표에서 생략하였다.
기존방법과 제안방법은 번식방법을 제외하고는 모두 같은 파라미터를 사용하였다. 유전자알고리즘이 전역 최적해를 찾으면 해당 세대를 기록하여 실험하였다. 즉, 유전자알고리즘의 개체 중에서 어떤 임의의 개체가 최고의 적합도를 갖는 x₁과 x₂의 위치를 찾아가는 경우 그 때의 세대 수를 최적화 성공 세대수로 기록하였다.
표준편차도 구하였으나 간단히 나타내기 위하여 표에서 생략하였다. 일반적인 경우 큰 개체수를 사용하나 성능비교 시에는 작은 개체에서 성능차이를 확실히 볼 수 있으므로 본 논문에서는 작은 개체수를 사용하여 실험하였다. 염색체의 비트는 20비트와 24비트를 사용하였다.
제안한 알고리즘은 기존의 유전자알고리즘에서 부모 개체를 선택하는 곳과 돌연변이 하는 곳에서 차이점을 보이는데 Algorithm 1에 이러한 차이점이 기술되어 있다. 제안한 알고리즘에서 각 개체는 적합도에 따라서 등급이 매겨져있다.

대상 데이터

일반적인 경우 큰 개체수를 사용하나 성능비교 시에는 작은 개체에서 성능차이를 확실히 볼 수 있으므로 본 논문에서는 작은 개체수를 사용하여 실험하였다. 염색체의 비트는 20비트와 24비트를 사용하였다. 예를 들어, 24비트를 사용했을 경우에는 x₁, x₂축으로 각각 12비트의 염색체로 함수공간을 분할하여 최적화를 수행한 것으로서 탐색공간은 대략 10 ×10⁶이 된다.

데이터처리

실험은 단순 유전자알고리즘과 비교하였다. 기존에 여러 가지 방법으로 성능을 향상시킨 유전자알고리즘이 존재하지만 본 논문에서는 단성생식과 양성생식을 혼용한 번식이 개체 속도 향상에 미치는 영향을 분석하기 위하여 단순 알고리즘과 비교하였다.

성능/효과

이는 10개의 개체 수에서 10%는 1개의 개체로 단성생식을 하는 개체 수가 너무 작은데서 기인한 것으로 생각된다. 10개의 개체 수에서는 20%의 단성생식이 성능이 좋았고 20개의 개체 수에서는 10%의 단성생식이 좋은 것을 볼 때 단성생식을 수행할 개체 수는 전체 개체 수의 특정 %로 하는 것보다 2~3개 등의 특정 개수로 하는 것이 더 좋을 것으로 판단된다.
이렇게 함으로서 유전자알고리즘이 조숙수렴에 빠지는 확률을 줄이고 안정적으로 전역 최적해에 접근할 수 있게 되어 성능이 향상되었다. 4개의 함수최적화 문제를 이용하여 실험한 결과 본 혼용 번식방법이 매우 효과적임을 확인할 수 있었다.
결국 본 논문에서 제안한 방법은 최적해가 넓게 분포되어 있는 문제보다는 비교적 좁은 곳에 분포되어 있으며 최적해 근처에 지역최적해가 많은 경우에 기존 방법보다 더 좋은 성능을 낼 수 있다. 본 논문의 핵심내용은 기존의 유전자알고리즘이 양성생식만을 수행하는데 비하여 단성생식과 양성생식을 혼용하여 전역 최적해로의 안정적 진화와 지역 최적해에서 쉽게 벗어나는 두 효과를 거둔 것에 있다 하겠다.
즉, 낮은 등급의 개체는 양성생식과 높은 돌연변이 확률로 넓은 영역에 걸쳐서 탐색하게 하고 좋은 등급의 개체는 단성생식과 낮은 돌연변이로 안정적인 진화를 가능하게 하였다. 이렇게 함으로서 유전자알고리즘이 조숙수렴에 빠지는 확률을 줄이고 안정적으로 전역 최적해에 접근할 수 있게 되어 성능이 향상되었다. 4개의 함수최적화 문제를 이용하여 실험한 결과 본 혼용 번식방법이 매우 효과적임을 확인할 수 있었다.
또한 단성생식을 하는 개체는 세부적인 탐색을 가능하게 하기 위하여 돌연변이 확률을 낮추고 양성생식을 한 개체는 돌연변이를 높게 하여 다양성 확보에 도움이 되게 하였다. 제안한 방법을 4개의 함수최적화 문제를 적용하여 실험한 결과 본 논문에서 제안한 방법이 다양성을 확보하면서도 최적해로의 지속적인 진화가 가능하게 되어 개체 진화속도가 향상됨을 볼 수 있었다. 본 논문에서 제안한 방법은 기존의 방법에 쉽게 적용되어 성능을 높이는데 사용될 수 있다.
본 논문에서는 단성생식방법과 양성생식 방법을 혼용하여 번식을 함으로서 단성생식 방법의 장점과 양성생식 방법의 장점을 취할 수 있는 방법을 제안하였다. 즉, 낮은 등급의 개체는 양성생식과 높은 돌연변이 확률로 넓은 영역에 걸쳐서 탐색하게 하고 좋은 등급의 개체는 단성생식과 낮은 돌연변이로 안정적인 진화를 가능하게 하였다. 이렇게 함으로서 유전자알고리즘이 조숙수렴에 빠지는 확률을 줄이고 안정적으로 전역 최적해에 접근할 수 있게 되어 성능이 향상되었다.
함수 f₄에서 성능이 안 좋은 경우가 발생하는데, 아마도 최적해가 네 곳에 흩어져 있기 때문인 것으로 생각된다. 즉, 제안한 방법은 최적해로의 안정된 진화를 가능하게 하는데 최적해가 여러 곳에 흩어진 경우 최적해로의 방향이 혼란되어 성능이 저하되는 것으로 판단된다.
표에서 보듯이 제안한 방법이 기존의 양성생식만을 사용한 방법에 비하여 대부분의 경우 좋음을 알 수 있다. 특히, 함수 f₁과 f₃에서는 제안한 방법이 월등히 좋음을 알 수 있었다. 단성생식을 하는 등급을 20%로 한 경우에 10개의 개체 수에서는 10%보다 성능이 좋았으나 20개의 개체 수 에서는 10%보다 대부분 좋지 않았다.
에서 기존 제안은 기존의 방법으로 찾은 평균 세대 수를 제안한 방법으로 찾은 평균 세대 수로 나눈 것을 뜻한 것으로 1보다 크면 성능이 향상된 것을 나타낸다. 표에서 보듯이 제안한 방법이 기존의 양성생식만을 사용한 방법에 비하여 대부분의 경우 좋음을 알 수 있다. 특히, 함수 f₁과 f₃에서는 제안한 방법이 월등히 좋음을 알 수 있었다.

후속연구

제안한 방법을 4개의 함수최적화 문제를 적용하여 실험한 결과 본 논문에서 제안한 방법이 다양성을 확보하면서도 최적해로의 지속적인 진화가 가능하게 되어 개체 진화속도가 향상됨을 볼 수 있었다. 본 논문에서 제안한 방법은 기존의 방법에 쉽게 적용되어 성능을 높이는데 사용될 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	단성생식과 양성생식의 장점은?	본 논문에서는 유전자알고리즘에서 단성생식과 양성생식을 혼용하여 개체진화 속도를 향상시키는 방법에 대하여 제안한다. 단성생식은 암수의 구분이 없는 세균이나 단세포 생물이 두 개의 개체로 분열되는 방법으로 유전적으로 지역적 탐색에 유리하며 양성생식은 암수의 구분이 있는 개체가 만나 생식하는 방법으로 유전적 다양성을 확보하는데 유리하다. 이러한 특성은 유전자알고리즘에서 개체의 진화속도를 향상시키는데 적절히 이용될 수 있다.
	응용문제가 반드시 전역 최적해를 찾아야하는 경우 어떤 알고리즘을 사용해야 하는가?	첫번째로는 유전자알고리즘은 전역 최적해를 찾는다는 것을 보장하지 못한다는 것이다. 그러므로 만약 응용문제가 반드시 전역 최적해를 찾아야하는 경우라면 유전자알고리즘보다는 전역 최적해를 보장하는 다른 알고리즘을 사용해야한다. 유전자 알고리즘은 차적의 해를 빠른 시간 내에 찾는 문제에 유용하다.
	유전자알고리즘은 어느 함수 또는 방법에 유용하게 사용되었는가?	유전자알고리즘은 최적화 알고리즘의 하나로 많은 공학적 문제에 성공적으로 응용되어 왔다 [1-4]. 특히 수학적 최적화가 불가능한 미분 불가능한 함수나 여러 인자들의 조합으로 최적화되는 조합적 최적화에 유용하게 사용되었다. 그러나 유전자알고리즘이 기존의 최적화 방법에 비하여 많은 장점이 있음에도 몇 가지 단점으로 인하여 응용에 어려움이 있다.

참고문헌 (9)

D. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning". Addison-Wesley, 1989.
J. Andre, P. Siarry, and T. Dognon, "An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization," Advances in engineering software, Vol. 32, No. 1, pp. 49-60, 2001.

상세보기
M. Srinivas and L. M. Patnaik, "Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm," IEEE Transactions on Systems, Man and Cybernetics, Vol. 24, pp. 656-667, Apr. 1994.

상세보기
A. Tuson, "Adapting Operator Probabilities in Genetic Algorithms," master thesis, Dept. of Artificial Intelligence, University of Edinburgh, UK, 1995.
E. Alba and B. Dorronsoro, "The exploration/exploitation tradeoff in dynamic cellular genetic algorithms," IEEE Transactions on Evolutionary Computation, Vol. 9, No. 2, pp. 126-142, 2005.

상세보기
A. E. Eiben, Z. Michalewicz, m. Schoenauer, and J. E. Smith, "Parameter Control in Evolutionary Algorithms", Studies in Computational Intelligence, Vol. 54, pp. 19-46, 2007.
Silja Meyer-Nieberg and Hans-Georg Beyer, "Self-Adaptation in Evolutionary Algorithms," Studies in Computational Intelligence, Vol. 54, pp. 47-75, 2007.
K. DeJong, "An Analysis of the Behavior of a Class of Genetic Adaptive Systems", Ph. D. Dissertation, University of Michigan, 1975.
Marcin Molga and Czeslaw Smutnicki, "Test functions for optimization needs," http: / /www.zsd.ict.pwr.wroc.pl/ files/ docs/ functions.pdf

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증