[논문]개미 알고리즘을 융합한 적응형 유전알고리즘

김중항; 이세영; 장형수

개미 알고리즘을 융합한 적응형 유전알고리즘
An Ant System Extrapolated Genetic Algorithm 원문보기

정보과학회논문지. Journal of KIISE. 시스템 및 이론, v.32 no.8, 2005년, pp.399 - 410

김중항 (서강대학교 컴퓨터학과) , 이세영 (서강대학교 컴퓨터학과) , 장형수 (서강대학교 컴퓨터학과)

초록
AI-Helper

본 논문에서는 개미 군 집단 알고리즘을 융합한 새로운 적응형 유전 알고리즘을 제안하고, 제안된 알고리즘이 확률적으로 최적 해에 수렴함을 증명한다. 실험을 통해서, 제안된 알고리즘은 최적 해로의 수렴이 어려운 여러 가지 대표적인 함수들에 대하여 elitist 전략을 사용한 유전 알고리즘보다 더 빠른 속도로 최적 해에 수렴하고 한 군집 내의 모든 해들이 최적 해로 수렴하며 파라미터 값에 따라 새로운 탐색이나 현 상태로의 귀착의 정도를 조절할 수 있는 유연성 있는 알고리즘인 것을 보인다.

Abstract ▼ AI-Helper

This paper Proposes a novel adaptive genetic algorithm (GA) extrapolated by an ant colony optimization. We first prove that the algorithm converges to the unique global optimal solution with probability arbitrarily close to one and then, by experimental studies, show that the algorithm converges faster to the optimal solution than GA with elitism and the population average fitness value also converges to the optimal fitness value. We further discuss controlling the tradeoff of exploration and exploitation by a parameter associated with the proposed algorithm.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는, 개미 집단을 적용한 새로운 적응 유전 알고리즘(Genetic Algorithm, GA)을 제안한다. 이미 잘 알려져 있는 기본적인 유전 알고리즘(Canonical Gene tic Algorithms, CGA)[1]은 수행 과정에서 주어친 최적화 문제에 대한 2진 비트들로 구성된 문자열(string)로 하나의 해를 인코딩시켜 각각의 비트를 고정된 확률로 변이(mutation)시킨다.
인 최적화 문제를 생각해보자. 문제의 목표는 据財S) 를 만족하는 z*wx를 찾는 것이다.

가설 설정

(2) 모든 kNO에 대하여 X = (药, ..., 或)이고 / = 侦・", s = 0, l 일 때, 만일 £;=s이면 이다.
(1) X 는 유일하다.
문제의 목표는 据財S) 를 만족하는 z*wx를 찾는 것이다. 본 논문에서는 해 ZUX의 2번째 비트의 위치를 叱로 나타낼 것이다.
, 矿1}를 생성한다. 본 알고리즘에서는 선택과 교배의 방법을 자유롭게 선택하여 PQ)로부터 m-1 개의 문자열을 생성하는 것을 가정한다. 이 때, 만약 R=0이면, 地;) = 户心)이다.

제안 방법

1로 고정한 뒤 실험을 수행하였다. ANT-GA에 추가되는 또 다른 매개 변수인 Y값에 따른 알고리즘의 성능 변화에 대해서는 뒤에서 자세히 설명하였으며, 실험에서는 ANT-GA와 EGA를 30번 수행한 후 각 세대별 최적해와 평균해의 30회의 평균값을 구하여 수치화 하였다.
각 함수는 10차원의 해, 즉 한 개체가 포함하는 문자열의 수가 10개(七, …, 们°)인 함수로 실험을 수행하였다.
않는다. 본 알고리즘은 한 군집(population) 내의 개체들의 사회적 행동(social behaviour)들에 기초하여 각 비트의 위치에 대한 변이 확률 분포를 갱신(즉, 각각의 개체들이 얼마나 최적의 개체인가에 대한 집합적인 지식을 만들어 냄)함으로써 개체군들의 조망(land scape) 을 학습하고, 다음 세대의 군집을 만들어내는 데 사용하게 된다.
이제 GA의 기본적인 선택, 교배 작용과 새롭게 결합된 변이 과정을 가진 GA를 수행함으로써 알고리즘을 GA로 확장시킨다. 짧게 요약하면, 주어진 군집(GA의 2 진 문자열의 집합에서 특정한 선택과 교배를 하여 임시의 개체군을 얻고, 얻어진 개체군의 각각의 해를 개미의 그래프상에서의 이동에 대응시킨 뒤, 개미들의 이동을 평가한 값을 가지고 그래프상의 간선에 묻혀질 페로몬 값을 갱신한 뒤, 이것을 이용하여 각각의 비트가 가지는 특정한 값들에 대한 확률 분포를 갱신한다.
이제 그래프상에서 출발점에서 도착점까지의 개미의 이동을 각각의 비트에 대응시키고 나면, 적합도 평가 함수에 따라 개미의 이동에 대한 적합도를 평가하고 평가된 값에 따라 각 간선에 묻힐 페로몬값을 계산한다. 이제 이러한 페로몬값에 의하여 해당 비트의 확률 분포가 변화하게 된다.
한 군집안에 있는 모든 해가 발견된 최적해로 수렴하지 못하는 EGA의 성질은 EGA의 다음 세대의 군집에 포함시킬 elitist의 비율을 지정하는 것에 관련되어 있는 점에 착안하여, 그림 13, 15에서는 F4의 함수를 가지고 elitist의 비율을 변화시켜가며 이러한 EGA의 성질을 실험하였다.

대상 데이터

ANT-GA의 성능을 평가하기 위하여, 시itist 전략을 사용한 유전 알고리즘(Genetic Algorithm with Eliti sm, EGA)이라 불리우는 알고리즘[13]을 평가 대상으로 삼았다. 두 가지의 알고리즘은 동일한 기계와 환경에서 실험하였다.

이론/모형

이미 잘 알려져 있는 기본적인 유전 알고리즘(Canonical Gene tic Algorithms, CGA)[1]은 수행 과정에서 주어친 최적화 문제에 대한 2진 비트들로 구성된 문자열(string)로 하나의 해를 인코딩시켜 각각의 비트를 고정된 확률로 변이(mutation)시킨다. 이에 반하여, 본 알고리즘에서의 각 비트의 변이는 2진 문자열의 각 비트에 대한 변이확률 분포와 군지능(swann intelligence)"⑵을 적용하여 이루어진다. 본 알고리즘은 선택법(s이 ection)과 교배법 (crossover)의 종류에 무관하다.
초기 군집인 R。)에서의 임의로 설정된 각 해들은 동일하게 적용하였으며, ANT-GA와 EGA에서의 매개 변수의 설정은 De Jong과 Spears가 제시한 함수 최적화에 대한 일반적인 GA의 최적 매개 변수 설정[15]을 사용하였다. ANT-GA, EGA 모두 개체군의 수는 50으로 고정하고, 토너먼트 선택법(tournament s이。ction)과 2 점 교배법을 사용하였다.
ANT-GA, EGA 모두 개체군의 수는 50으로 고정하고, 토너먼트 선택법(tournament s이。ction)과 2 점 교배법을 사용하였다. 교배의 경우, 교배된 해가 다음 세대의 전체 개체군에 포함될 비율(crossover frac- tion)을 0.
ANT-GA^- EGA를 구현하기 위한, 문제에 대한 해들의 인코딩 및 디코딩은 실수의 디지털 샘플링 기법 (quantization of real vahie)[14]을 사용하여 살수를 문자열의 길이0=30의 2진 문자열로 인코딩하였다.
ANT-GA로 불리는 본 알고리즘은 변이 연산에 있어서 Gutjahr의 GACO[기의 확장을 기본으로 한다. ACO 의 기본적인 아이디어를 설명하기 위한 가장 좋은 방법은 생물학적 은유(biological metaphor)를 참고로 하여, 생물학적인 개미 집단의 탐색 습성을 알아보는 방법이다 개미들은 주어진 환경에서 다소 임의의 길로 이곳저곳을 움직이는 것처럼 보이지만, 개미들은 다른 개미가 지나간 길을 따라가는 성향을 보인다.
6으로 설정하였다. EGA의 경우에는 변이 확률을 0.001로 고정하였으며, 변이의 종류는 비트-플립 (bit-flip)방식을 사용하였다. 이때의 변이 확률은 각 문자열별의 변이 확률이 아니라 문자 열의 각 비트별 변이확률이므로, 각 문자열별의 변이 확률로 볼 때 변이 확률이 매우 낮은 것이 아님을 염두에 두어야 한다.
게다가, 교배나 변이 모두 새로운 군집을 생성하는 과정에 포함되어 있지 않기 때문에 (교배와 변이는 PMBGA에서 기본적으로 사용되는 계산(calculation)과 추출(sampling)로 대치된다), PMBGA는 GA의 기본적인 성질을 잃어버리게 된다. 이에 반하여, 본 알고리즘은 CGA의 기본 구조에 최근에 개발된 군집 기반의 진화적 접근 방식인 개미 집단 최적화(Ant Colony Optimization, ACO)[6]의 방법론을 사용한 적응형 변이 과정을 적용하였고 전역 최적해에 수렴하는 것을 화률적으로 보장한 다. 이것에 대한 증명은 Gutjahr의 Graph-based Ant Colony Optimi- zation(GACO)[기의 증명을 확장시킴으로써 가능하다.

성능/효과

즉, "값이 클 경우에는, 이전 세대에서 갱신된 페로몬값들은 조금만 고려되고 현 세대에서의 우성 해의 2진 문자열에 대한 페로 몬 값이 크게 고려되어 군집 안의 모든 해들이 현 세대의 우성해에 귀착되는 형태가 되며(그림 7, 9), 이전 세대의 우성해에 대한 페로몬 값들은 무시한 채 현재 세대의 우성해에 대한 값들에 큰 비중을 두어 고려하게 되므로, 결과적으로는 이전에 갱신된 0또는 1에 대한 페로몬의 양과는 상관없이 현재의 우성 해로 수렴하는 형태가 된다.이 값이 만약 전역 최적 해라면 큰 문제가 되지 않지만, 실험에서와 같이 부분 최적해가 많은 복잡한 함수라면 문제는 달라진다.
1. 어떤 e>0와 고정된 卩에 대하여, 군집의 크기 m 이 충분히 큰 값을 가지고 있다고 할 때, 모든 k 그 总 (寫)는 e에 의존하는 정수값)에 대하여 4 兰 1-e이 성립한다.
그러므로 〃값이 너무 커지지 않도록 조절할 필요성이 있으며, 또한 产값이 매우 작을 경우에는 이전 세대에서의 페로몬값들의 영향이 더 많이 고려되며 이는 실제로 각 비트위치의 0또는 1의 값에 대한 페로몬 초기값인 0.5에서 시작하여 현재 세대까지 고려된 페로몬의 값들을 무시하지 않는다는 것을 뜻하기 때문에, 그림 6 와 같이 어떤 최적 해에 대한 수렴 속도는 느려 지지만 이전 세대에서 좋은 결과를 보였던 해들에 대한 페로몬값도 함께 고려되므로 결과적으로 어떤 새로운 값을 탐색하는 데 았어서는 卩값이 클 경우보다 더 좋은 결과를 내게 된다. 실험 결과에서도 나타나듯이, 이러한 작은 m 값을 사용하면 일정한 세대가 지난 후에 EGA보다 더 좋은 최적해를 찾아낼 수 있게 된다.
또한 알고리즘의 파라미터인 口값을 변경함으로써 최적 해로의 수렴 속도와 최적해의 탐색 가능성을 조절할 수 있는 유연성 있는 알고리즘임을 확인하였다.
본 논문에서의 여러 가지 전체 최적화 문제에 대하여, 새롭게 제안된 우리의 알고리즘이 EGA에 비해 최적 해로 빠르게 수렴하는 것을 실험을 통하여 확인하였으며, EGA와는 달리한 군집안의 모든 해들이 최적 해로 수렴하는 것을 확인하였다.
5에서 시작하여 현재 세대까지 고려된 페로몬의 값들을 무시하지 않는다는 것을 뜻하기 때문에, 그림 6 와 같이 어떤 최적 해에 대한 수렴 속도는 느려 지지만 이전 세대에서 좋은 결과를 보였던 해들에 대한 페로몬값도 함께 고려되므로 결과적으로 어떤 새로운 값을 탐색하는 데 았어서는 卩값이 클 경우보다 더 좋은 결과를 내게 된다. 실험 결과에서도 나타나듯이, 이러한 작은 m 값을 사용하면 일정한 세대가 지난 후에 EGA보다 더 좋은 최적해를 찾아낼 수 있게 된다. 극단적인 경우에는(卩 = 0) 초기 값인 0.
실험 결과와 같이 elitist의 비율을 높일 경우는 지역 최소의 문제가 두드러지게 나타나며, elitist의 비율을 낮출 경우는 지역 최소의 문제는 해결되나 전체 군집의 최적 해로의 수렴은 초기에 약간 나타나다가 후기에는 오히려 증가하는 경향을 보이는 것을 알 수 있다. 이는 elitist의 비율이 높아지면 그만큼 다음 세대의 군집에서 elitist들이 많이 나타나게 되고 선택이나 교배로 인하여 새로이 탐색된 해가 차지하는 비율이 적어지기 때문에, 이러한 elitist가 지역 최소일 경우 지역 최소에서 잘 벗어나지 못하기 때문이다.
여러 흥미로운 문제에 대하여, 개미 집단 최적화가 CGA보다 좋은 결과를 보이는 것은 여러 논문에서 다루어져 왔다[6, 21丄 CGA의 구조에 개미군지능 최적화의 방법론을 융합함으로써, 그 결과인 본 논문의 hybrid 알고리즘은 CGA의 약점을 보완할 수 있게 되었다.
우리는 군지능의 아이디어를 CGA의 변이 과정에 적용한 새로운 적응형 유전 알고리즘을 개발하고, 본 알고리즘이 최적 해에 수렴한다는 것을 확률적으로 증명하였다. 여러 흥미로운 문제에 대하여, 개미 집단 최적화가 CGA보다 좋은 결과를 보이는 것은 여러 논문에서 다루어져 왔다[6, 21丄 CGA의 구조에 개미군지능 최적화의 방법론을 융합함으로써, 그 결과인 본 논문의 hybrid 알고리즘은 CGA의 약점을 보완할 수 있게 되었다.
1일 때 가장 좋은 결과를 보였다. 즉 0과 1사이의 값 중에서 작은 값일 때 좋은 결과를 보였으며, 이는 [기의 Theorem 4丄2에서 페로몬 증발 상수(evaporation factor)가 0에 가까운 작은 값을 가질 때 GACO가 수렴한다는 사실과 일맥상통한다.

참고문헌 (21)

G. Rudolph, 'Convergence Analysis of Canonical Genetic Algorithms,' IEEE Trans. on Neural Networks, vol. 5, no. 1, 96-101, 1994

상세보기
R. Eberhart and J. Kennedy, Swarm Intelligence, Morgan Kaufmann, 2001
C. R. Reeves, 'Genetic Algorithms for the Operations Resercher,' INFORMS J. on Computing, vol.9, no. 3, 231-250, 1997

상세보기
H. Muhlenbein, G. Paab, 'From Recombination of Genes to the Estimation of Distributions I. Binary parameters,' Parallel Problem Solving from Nature, H. Voigt, W. Ebeling, I. Rechenberg, and H. Schwefel (eds.), LNCS, vol. 1141, 178-187, 1996

상세보기
S. K. Shakya, 'Probabilistic Model Building Genetic Algorithm(PMBGA): A survey,' Tech. Rep., School of Computing, The Robert Gordon University, UK, 2003
M. Dorigo, V. Maniezzo, A. Colorni, 'The Ant System: Optimization by a Colony of Cooperating Agents,' IEEE Trans. Systems Man Cybernet., vol. 25, 29-41, 1996

상세보기
W. J. Gutjahr, 'A Graph-based Ant System and Its Convergence,' Future Generation Computer Systems, vol. 16, no. 8, 2000

상세보기
M. Srinivas and L. M. Patnaik, 'Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm,' IEEE Trans. on Systems, Man and Cybernetics, vol. 24, no. 4, 656-667, 1994

상세보기
J. Yang, J. Horng, and C. Kao, 'A genetic algorithm with adaptive mutations and family competition for training neural networks,' Int. J. of Neural Systems, vol. 10, no. 5, 333-352, 2000

상세보기
D. Thierens, 'Adaptive mutation rate control schemes in genetic algorithms,' in Proc. of the 2002 IEEE World Congress on Computational Intelligence, 980-985, 2002
S. Baluja, 'Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning,' Tech. Rep. No. CMUCS94163, Department of Computer Science, Carnegie Mellon University, 1994
P. Larranaga, R. Etxeberria, J.A. Lozano and J.M Pena, 'Combinational optimization by learning and simulation of Bayesian networks,' in Proc. of the Conference in Uncertainty in Artificial Intelligence, 343-352, 2000
D. Bhandari, C. A. Murthy, and S. K. Pal, 'Genetic Algorithms with Elitist Model and Its Convergence,' International Journal of Pattern Recognition and Artificial Intelligence, vol. 10, 731-747, 1996

상세보기
K. Najim, A. S. Poznyak, and E. Ikonen, 'Optimization based on a team of automata with binary outputs,' Automatica, vol. 40, 1349-1359, 2004

상세보기
K. De Jong and W. Spears, 'An Analysis of the Interacting Roles of Population Size and Crossover in Genetic Algorithms,' in Proc. First Workshop Parallel Problem Solving from Nature, Springer-Verlag, 38-47, 1990
X. Yao, Y. Liu, and G. Lin, 'Evolutionary Programming Made Faster,' IEEE Trans. on Evloutionary Computation, vol 5, no. 2, 82-102, 1999

상세보기
C. Fernandes, R. Tavares, C. Munteanu, and A. Rosa, 'Using Assortative Mating in Genetic Algorithms for Vector Quantization Problems,' in Proc. of the 2001 ACM symposium on Applied computing, 361-365, 2001
F. Villegas, T. Cwik, Y. Rahmat-Samii, and M. Manteghi, 'A Parallel Electromagnetic Genetic-Algorithm Optimization (EGO) Application for Patch Antenna Design,' IEEE Trans. on Antennas and Propagation, vol. 52, no. 9, 2424-2435, 2004

상세보기
M. Brameier and W. Banzhaf, 'A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining,' IEEE Trans. on Evolutionary Computation, vol. 5, 17-26, 2001

상세보기
J. Fernandez and A. Caballero, 'A Comparison of Management Strategies for Conservation with regard to Population Fitness,' Conservation Genetics 2, 121-131, Kluwer Academic Publishers, 2001

상세보기
M. Dorigo, G. Di Caro, and T. Stutzle, Special Issue on 'Ant Algorithms,' Future Generation Computer Systems, vol. 16, no. 8, 2000

저자의 다른 논문 :

표제어: 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

연합인증