Firefly 알고리즘의 개선과 동적환경에서의 에이전트 경로계획에의 응용
An Enhancement of Firefly Algorithm and its Application to Agent Path Planning in Dynamic Environment
- 발행기관 서강대학교 일반대학원
- 지도교수 오경환
- 발행년도 2011
- 학위수여년월 2011. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000046477
- 저작권 서강대학교의 논문은 저작권 보호를 받습니다.
초록/요약
본 논문은 Xin-She Yang에 의해 소개된 Firefly 알고리즘(FA)을 개선하고, 이를 동적 환경에서의 agent의 경로 계획에 응용한다. 먼저, FA를 여러 도메인에서 성공적으로 응용되었으며, 그 작동 방식이 비슷한 Particle Swarm Optimization(PSO)과 accuracy 측면, converge time 측면, 각 particle의 움직임 측면에서 비교 분석한다. 비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다. 본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 partial mutation 휴리스틱을 가하여 설계된 개선된 FA(Improved FA)를 제안한다. 벤치마크 함수들을 최적화 하는 비교 실험 결과, Improved FA가 PSO와 Original FA보다 정확도와 수렴속도 측면에서 우수한 것으로 나타났다. 기존에 최적화 기법을 이용한 agent 경로 계획 방법들이 여럿 소개되었다. 그러나 이의 실제 응용은 agent의 장애물과의 충돌, agent의 비효율적 경로 설정 등의 case들이 많이 발견되어 그 실용성이 의심되는 상황이다. 이의 원인은 결국 agent가 처한 환경에서의 경로 계획을 위해 모델링된 함수의 최적화가 실패했기 때문이다. 이에 본 논문은 동적환경에서의 agent의 path planning을 최적화 문제로 적절히 표현하기 위한 한 가지 방법을 제안하고, Improved FA가 PSO나 Original FA보다 우수함이 여러 벤치마크 function들에서 증명된 바, 이를 바탕으로 환경 모델링 함수의 최적화를 Improved FA로 실행하여 PSO나 FA에 대비, 최적화 실패의 발생가능성의 감소를 꾀한다. 실험 결과는 이를 증명한다.
more초록/요약
In this paper, we propose a method to improve the Firefly Algorithm(FA) introduced by Xin-She Yang, recently, and apply it to the agent path planning problem in dynamic environment. First, we compare the FA with the particle swarm optimization (PSO) which work plan is similar with the FA in terms of accuracy, algorithm convergence time, the motion of each particle. The compare experiments say that the accuracy of FA is not worse than PSO’s, but the convergence time of FA is slower than PSO’s. In this paper, we consider intuitive reasons of slow convergence time problem of FA, and propose the improved version of FA using a partial mutation method based on the consideration. The experiments using benchmark functions show the accuracy and convergence time of the improved FA are better than them of PSO and original FA. There exist various agent path planning methods using the function optimization. However, using them practically is uncertain because there are many conflicts with obstacles and the agent plans its path inefficiently often. These are due to failure of optimization of the function modeling the environment of the agent. Therefore, this paper propose a environment modeling method to convert a path planning problem to optimization problem and apply Improved FA to optimization of it to reduce optimization failure probability. The experiment results prove that Improved FA is superior to PSO or original FA in terms of optimization of proposed the environment modeling function.
more