[논문]콤팩트 엘리트 개미 최적화

조진선; 장형수

콤팩트 엘리트 개미 최적화
Compact elitist Ant Optimization 원문보기

조진선 (서강대학교 컴퓨터공학과) , 장형수 (서강대학교 컴퓨터공학과)

본 논문에서는 개미 집단 최적화(Ant Colony Optimization, ACO)의 시간적 공간적 효율성을 향상시키기 위해 ACO에 엘리트 콤팩트 유전 알고리즘(Elitist compact Genetic Algorithms, elitist cGAs)의 아이디어를 적용한 콤팩트 개미 최적화(Compact elitist Ant Optimization, CAO)를 제안한다. CAO는 elitist cGAs에서 각 세대마다 염색체의 수를 둘로 고정하고 우월한 염색체를 유지하여 최적의 해를 찾는 방식을 적용하여 개미의 수를 하나로 고정하고 전이 확률식과 페로몬 갱신 규칙을 변형하고 특정 문제에 적용할 수 있는 타부 규칙을 추가한 알고리즘이다. 이 알고리즘의 공간 효율성이 ACO보다 좋다는 것을 증명하고 스테이너 트리 문제(Steiner Tree Problem)에 적용하여 제안된 알고리즘의 시간 효율성이 ACO보다 좋다는 것을 보인다.

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

문제 정의

을 만족하고 모든 간선의 weight 값의 총 합이 가장 작은 minimum weight tree G_s(V_s,E_S)를 찾는 것을 목적으로 한다.
하지만 개미의 수를 증가시키거나 페로몬의 증발 정도를 작게 하면 성능은 좋아지더라도 계산 비용이나 메모리 요구량이 증가한다. 이러한 단점을 극복하기 위해서 본 논문에서는 Ahn과 Ramakrishna에 의해 제안된 엘리트 콤팩트 유전 알고리즘(Elitist compact Genetic Algorithms, elitist cGAs)[2]의 아이디어를 ACO에 적용하여 새로운 알고리즘 콤팩트 엘리트 개미 최적화(Compact elitist Ant Optimization, CAO)를 제안한다.
인 최적화 문제를 생각해보자. 문제의 목표는 min_x∈Xf(x)값을 얻게 하는 최적의 해 x*∈X를 찾는 것이다.

제안 방법

이러한 단점을 보안하면서 기존의 성능을 유지하기 위해서 제안된 알고리즘이 elitist cGAs[2]이다. Elitist cGAs는 persistent elitist cGAs와 nonpersistent elitist cGAs로 나뉘는데 본 논문에서는 nonpersistent elitist cGAs의 특징을 ACO에 적용하였다. Elitist cGAs는 GA처럼 여러 해들의 집합인 개체군을 유지하는 것이 아니라 cGAs와 마찬가지로 i번째 유전자가 1 값을 가질 확률을 i번째 값으로 가지는 확률 벡터를 통해 생성하는 두 개의 염색체만을 각 세대마다 유지한다.
모든 알고리즘은 종료 iteration을 500000으로 해서 종료 iteration까지 해를 찾도록 하였다. Tree를 구성하는 모든 간선들의 weight의 총합을 tree의 weight라고 하고 매 iteration에서 이제까지 찾은 tree의 weight 중에서 가장 작은 값의 weight를 가지는 tree를 최적의 tree라고 할 때, 매 100 iteration마다 걸리는 시간과 찾은 tree의 weight 값, 그리고 최적의 tree의 weight 값을 측정하였다.
모든 알고리즘은 종료 iteration을 500000으로 해서 종료 iteration까지 해를 찾도록 하였다. Tree를 구성하는 모든 간선들의 weight의 총합을 tree의 weight라고 하고 매 iteration에서 이제까지 찾은 tree의 weight 중에서 가장 작은 값의 weight를 가지는 tree를 최적의 tree라고 할 때, 매 100 iteration마다 걸리는 시간과 찾은 tree의 weight 값, 그리고 최적의 tree의 weight 값을 측정하였다.
본 논문에서는 ACO를 적용할 때 사용하는 파라미터 중에서 α, β 값은 다른 논문[8]에서 실험에 사용한 값과 마찬가지로 각각 5, 1로 결정하였고 ACO1과 ACO2에 동일하게 사용하였다.
이러한 단점을 보안하기 위해 elitist cGAs가 제안되었다. 이 알고리즘은 cGAs에서 매 세대마다 두 개의 염색체를 생성하는 것과 달리 이전 세대에 우월했던 염색체와 새로 생성한 하나의 염색체를 비교하는 방식을 통해 최적의 해답을 찾도록 한다. 이 알고리즘은 우월한 염색체가 항상 살아남아 결론적으로 찾은 최적의 해답을 놓치지 않는 방식으로 cGAs의 단점을 보안하면서 기존의 GA의 단점인 계산 비용과 메모리 요구량도 감소시킬 수 있었다.
하지만 이 규칙으로만 페로몬을 변화시킬 경우 빠른 속도로 페로몬을 강화하고 다양화는 없기 때문에 지역해에 빠질 가능성이 크다. 이러한 단점을 보안하기 위해 elitist cGAs에서 일정 세대마다 우월한 염색체를 랜덤하게 생성시킨 염색체로 대체 했던 아이디어를 적용하여 일정 주기로 정해진 구간동안 초기 페로몬을 유지시켜 준다.

성능/효과

그리고 마지막으로 time은 해당 iteration까지 걸린 시간이다. CAO는 비록 ACO2보다는 해가 좋지 않지만 ACO1보다는 좋고, 알고리즘의 최적의 해를 ACO1과는 비슷한 시간에 그리고 ACO2보다는 매우 빠른 시간에 찾을 수 있다는 것을 표 1을 통해 확인할 수 있다.
기존의 ACO에 이러한 elitist cGAs의 아이디어를 적용하여 ACO의 단점을 보안하는 알고리즘 CAO는 elitist cGAs에서 염색체의 수를 세대마다 둘로 고정하는 것을 적용하여 개미의 수를 하나로 고정하고 우월한 염색체를 다음 세대로 유지하여 새로 생성되는 염색체와 비교한 아이디어를 적용하여 하나의 개미에 알맞게 전이 확률식과 페로몬 갱신 규칙을 변형하고 마지막으로 특정한 문제가 주어졌을 경우 적용할 수 있는 “타부 규칙”을 추가하여 만든 알고리즘이다. CAO의 효율성을 증명하기 위해서 공간비용 측면에서 더 효율적이라는 것을 증명하고 스테이너 트리 문제(Steiner Tree Problem, STP)에 적용하고, 그 성능에 대해 기존의 ACO 방법과 비교하여 시간비용측면에서 더 나은 결과가 나온다는 것을 실험을 통하여 보인다.
이 알고리즘은 cGAs에서 매 세대마다 두 개의 염색체를 생성하는 것과 달리 이전 세대에 우월했던 염색체와 새로 생성한 하나의 염색체를 비교하는 방식을 통해 최적의 해답을 찾도록 한다. 이 알고리즘은 우월한 염색체가 항상 살아남아 결론적으로 찾은 최적의 해답을 놓치지 않는 방식으로 cGAs의 단점을 보안하면서 기존의 GA의 단점인 계산 비용과 메모리 요구량도 감소시킬 수 있었다.
하지만 개미의 수를 충분히 하거나 ρ를 0에 근접한 값으로 하게 되면 계산 비용과 필요한 메모리를 증가시키는 단점이 있다. 이러한 단점을 보안하기 위하여 GA의 단점을 보안하여 제안된 알고리즘 elitism cGAs의 기본 아이디어를 ACO에 반영하여 새로운 알고리즘 CAO를 제안하였고 본 알고리즘이 성능의 저하 없이 ACO보다 시간 효율성이 높다는 것을 실험을 통해 증명하였다. 향후에 CAO를 적용하여 조합 최적화 문제에서 최적의 해를 찾는다는 것을 이론적으로 증명하고 STP를 제외한 다른 조합 최적화 문제에도 CAO를 적용하여 그 효율성을 보이고자 한다.
이것은 ACO의 경우 각 iteration에서의 시간 비용이 CAO보다 크기 때문에 iteration이 반복될수록 그 차이가 누적되기 때문이다. 이렇게 ACO1, ACO2, ACO3 세 방식보다 CAO의 시간 비용이 효율적이라는 것을 실험을 통하여 증명하였다.

후속연구

이러한 단점을 보안하기 위하여 GA의 단점을 보안하여 제안된 알고리즘 elitism cGAs의 기본 아이디어를 ACO에 반영하여 새로운 알고리즘 CAO를 제안하였고 본 알고리즘이 성능의 저하 없이 ACO보다 시간 효율성이 높다는 것을 실험을 통해 증명하였다. 향후에 CAO를 적용하여 조합 최적화 문제에서 최적의 해를 찾는다는 것을 이론적으로 증명하고 STP를 제외한 다른 조합 최적화 문제에도 CAO를 적용하여 그 효율성을 보이고자 한다.

핵심어

질문

논문에서 추출한 답변

개미 집단 최적화는 어떤 문제를 풀기위해 제안되었는가?

조합 최적화 문제인 순회 판매원 문제(Traveling Salesman Problems, TSP)를 풀기 위해 Dorigo와 Maniezzo에 의해 처음 제안된 메타 휴리스틱 기법인 개미 집단 최적화(Ant Colony Optimization,　ACO)[1]는 실제 개미들이 집에서 먹이까지 가장 짧은 경로를 찾는 능력을 모방하여 만든 알고리즘이다.

개미 집단 최적화는 무엇을 모방한 알고리즘인가?

조합 최적화 문제인 순회 판매원 문제(Traveling Salesman Problems, TSP)를 풀기 위해 Dorigo와 Maniezzo에 의해 처음 제안된 메타 휴리스틱 기법인 개미 집단 최적화(Ant Colony Optimization,　ACO)[1]는 실제 개미들이 집에서 먹이까지 가장 짧은 경로를 찾는 능력을 모방하여 만든 알고리즘이다.

유전 알고리즘의 단점은?

ACO에서 최적의 해를 찾는데 좋은 성능을 위해서 개미 수를 증가시키거나 페로몬의 증발 정도를 작게 하는 것과 비슷하게 GA는 최적의 해를 찾는데 좋은 성능을 위해서 개체군(population)의 크기를 충분히 크게 한다. 하지만 ACO와 마찬가지로 GA 역시 개체군의 수를 증가시키면 계산 비용과 메모리 요구량이 증가한다. GA의 이러한 단점을 보안하기 위해 Compact Genetic Algorithms(cGAs)[4]는 염색체의 길이를 n으로 하면, 염색체를 {0, 1}n으로 표현하고, GA에서처럼 해들의 집합으로 개체군을 형성하는 것이 아니라 각 유전자가 1 값을 가질 확률을 유지하고 이 확률을 통해 두 개의 염색체를 생성하여 더 우월한 염색체의 성향을 따르는 방식으로 해답을 찾는다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

콤팩트 엘리트 개미 최적화
Compact elitist Ant Optimization 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

콤팩트 엘리트 개미 최적화 Compact elitist Ant Optimization 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

콤팩트 엘리트 개미 최적화
Compact elitist Ant Optimization 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper