[논문]개미 모델 성능에서 다중 에이전트 상호작용 전략의 효과

이승관

개미 모델 성능에서 다중 에이전트 상호작용 전략의 효과
The Effect of Multiagent Interaction Strategy on the Performance of Ant Model 원문보기

이승관 (가톨릭대학교 컴퓨터정보공학부)

휴리스틱 알고리즘 연구에 있어서 중요한 분야 중 하나가 강화와 다양화의 조화를 맞추는 문제이다. 개미 집단 시스템은 최근에 제안된 조합 최적화문제를 해결하기 위한 메타 휴리스틱 기법으로, 그리디 탐색과 긍정적 보상에 의한 접근법으로 순회 판매원 문제를 풀기 위해 처음으로 제안되었다. 본 논문에서는 기존 개미집단 시스템의 성능을 향상시키기 위해 강화 전략과 다양화 전략으로 나누어진 엘리트 전략을 통해 집단간 긍정적 부정적 상호작용을 수행하는 다중 집단 개미 모델을 제안한다. 그리고, 이 제안된 엘리트 전략에 의한 다중 집단 상호작용 개미 모델을 순회판매원문제에 적용해 보고 그 성능에 대해 기존 개미집단 시스템과 비교한다.

One of the important fields for heuristics algorithm is how to balance between Intensificationand Diversification. Ant Colony System(ACS) is a new meta heuristics algorithm to solve hard combinatorial optimization problem. It is a population based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem(TSP). In this paper, we propose Multi Colony Interaction Ant Model that achieves positive negative interaction through elite strategy divided by intensification strategy and diversification strategy to improve the performance of original ACS. And, we apply multi colony interaction ant model by this proposed elite strategy to TSP and compares with original ACS method for the performance.

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

문제 정의

따라서 본 논문에서는 집단 간 강화 전략과 다양화 전략으로 나누어진 엘리트 전략을 TSP 문제에 적용해보 고, 그 성능에 대해 기존의 ACS 방법과 비교한다.
본 논문에서는 기존 ACS의 성능을 향상시키고자 엘리트 전략에 의한 다중 집단 상호작용 개미모델을 제 안하였다.
본 논문에서는 엘리트 전략에 따라 독립적 탐색 과정 을 수행하는 여러 개의 다중에 이전트를 가진 다 중 집단에 에이전트 구조를 제안한다. 이 구조는 몇 개의 독립적 ACS 집단으로 이루어져 있으며, 상호작용은 집단 간 엘리트 전략에 따라 임무를 수행한다.

제안 방법

집단의 수 M 은 10, # 은 강화 전략에 의해 긍정적 상호작용을 하는 경우(1/방문 빈도수), 다양화 전략에 의해 부정적 상호작용을 하는 경우는 (-1/방문빈도수), # 이다. 각 집단에 사용된 에이전트 수m=10이 고, 초기 위치는 에이전트들을 각 노드에 1개씩 무작위로 배정하였다.
그리고, ACS 성능 개선을 위해 강화(Intensification) 전략과 다양화(Diversification) 전략을 통해 집단 간 상호작용을 수행하는 다중 집단 개미 모델(Multi Colony Ant Model)을 제안한다.
또한 Queenl 그룹의 중심집단(C5) 과 Queen2 그룹의 중심집단(C10)간의 상호작용은 두 그룹의 지역 최적해를 서로 비교해, 우수한 해에 대해 전역갱신하는 전략을 채택한다.
본 논문에서는 순회 판매원 문제 (Traveling Salesman Problems : TSP) 문제를 풀기 위해 Colomi, Dorigo 그리고 Maniezzo6)] 의해 처음 제안된 지역 갱신과 전역갱신 과정을 거쳐 최적해를 구하는 메타휴 리스틱 기법인 개미 집단 시스템(Ant Colony System : AC5에 대하여 소개를 한다 {1, 2, 3, 4, 5].
제안된 다중 집단상호작용 개미모델은 독립적 탐색 과정을 수행하는 여러 개의 에이전트 집단으로 구성되며, 에이전트 집단 간에는 강화전략에 의한 긍정적 상호작용과 다양화 전략에 의한 부정적 상호작용으로 나누어진 엘리트 전략을 통해 최적해를 탐색한다.
제안된 다중 집단상호작용 개미모델은 서로 독립적인 탐색 과정을 수행하는 여러 개의 에이전트 집단을 가진 다 중 집단에 이전트 구조로 이루어지며, 집단 간에는 강화 전략에 의한 긍정적 상호작용과 다양화 전략에 의한 부정적 상호작용으로 나누어진 엘리트 전략을 통해 최적해를 탐색한다.

대상 데이터

제안된 다중 집단상호작용 개미모델을 실험하기 위해서 도시들의 위치는 TSP 예제로 널리 알려진 TSPLIB[9]에서 추출하여 실험을 하였다.

성능/효과

그러나, 일개 미 집단에서 다양한 탐색을 수행하고, 중심 집단에서 강화 과정을 수행하는 제안된 방법은 훨씬 빠르게 최적해에 수렴한다.
그리고, 기존 ACS 방법과 본 논문에서 제안한 다중 집단상호작용 개미모델을 이용해 10회 시행에 20, 000번 사이클을 반복하였다.
해당 결과를 살펴보면, 기존의 ACS방법보다 제안된 엘리트 전략에 의한 다중 집단 상호작용 개미모델의 성능이 향상됨을 볼 수 있다.

후속연구

향후 이러한 결과들을 기반으로 다 중 집단 개미모델 에서 강화와 다양화 조화를 위한 새로운 추가 요소에 대한 연구가 필요하겠다. 그리고 제안된 연결망 구조 이 외의 새로운 정형화된 연결망 구조에 대한 연구도 필요 하겠다.
지역 최적해 원형 교환(Circular exchange of locally best solutions) : 집단 간에 가상의 유방향 원형 연결망을 구성하고, 정보 교환 단계에서 각 집단에서의 해당 지역 최적해를 다음에 연결된 후 임 집단에 전달한다. 그리고 후임 집단에서는 그 집단에 속한 모든 에이전트들이 경로사이클을 구성 후 해당 집단에서의 지역 최적해 와 이 전 집단에서 전달된 지역 최적해와 비교를 통해 그 최적해를 저장하고 갱신한다. 이 전략에서는 이웃 집단과의 지역 최적해를 비교해 평가하는 방법을 취하고 있다.
향후 이러한 결과들을 기반으로 다 중 집단 개미모델 에서 강화와 다양화 조화를 위한 새로운 추가 요소에 대한 연구가 필요하겠다. 그리고 제안된 연결망 구조 이 외의 새로운 정형화된 연결망 구조에 대한 연구도 필요 하겠다.

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

연합인증

개미 모델 성능에서 다중 에이전트 상호작용 전략의 효과
The Effect of Multiagent Interaction Strategy on the Performance of Ant Model 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

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

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

선택된 텍스트

연합인증

개미 모델 성능에서 다중 에이전트 상호작용 전략의 효과 The Effect of Multiagent Interaction Strategy on the Performance of Ant Model 원문보기

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

Abstract ▼ AI-Helper

주제어

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

문제 정의

제안 방법

대상 데이터

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

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

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

선택된 텍스트

개미 모델 성능에서 다중 에이전트 상호작용 전략의 효과
The Effect of Multiagent Interaction Strategy on the Performance of Ant Model 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper