본 논문에서는 최근 Xin-She Yang에 의해 소개된 반딧불이 알고리즘(FA)에 휴리스틱을 적용하여 개선하는 방안을 제안한다. 또한 이를 위하여 기존의 FA를 이와 유사한 문제영역의 알고리즘인 Particle Swarm Optimization(PSO)와 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석한다. 비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다. 본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 부분 돌연변이 휴리스틱을 적용하여 개선된 FA(Improved FA)를 제안한다. 벤치마크 함수들을 최적화 하는 비교 실험 결과, 개선된 FA가 PSO와 기존의 FA보다 정확도와 수렴속도 측면에서 우수함을 보이고자 한다.
본 논문에서는 최근 Xin-She Yang에 의해 소개된 반딧불이 알고리즘(FA)에 휴리스틱을 적용하여 개선하는 방안을 제안한다. 또한 이를 위하여 기존의 FA를 이와 유사한 문제영역의 알고리즘인 Particle Swarm Optimization(PSO)와 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석한다. 비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다. 본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 부분 돌연변이 휴리스틱을 적용하여 개선된 FA(Improved FA)를 제안한다. 벤치마크 함수들을 최적화 하는 비교 실험 결과, 개선된 FA가 PSO와 기존의 FA보다 정확도와 수렴속도 측면에서 우수함을 보이고자 한다.
In this paper, we propose a method to improve the Firefly Algorithm(FA) introduced by Xin-She Yang, recently. We design and analyze the improved firefly algorithm based on the heuristic. We compare the FA with the Particle Swarm Optimization (PSO) which the problem domain is similar with the FA in t...
In this paper, we propose a method to improve the Firefly Algorithm(FA) introduced by Xin-She Yang, recently. We design and analyze the improved firefly algorithm based on the heuristic. We compare the FA with the Particle Swarm Optimization (PSO) which the problem domain is similar with the FA in terms of accuracy, algorithm convergence time, the motion of each particle. The compare experiments show 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 heuristic 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.
In this paper, we propose a method to improve the Firefly Algorithm(FA) introduced by Xin-She Yang, recently. We design and analyze the improved firefly algorithm based on the heuristic. We compare the FA with the Particle Swarm Optimization (PSO) which the problem domain is similar with the FA in terms of accuracy, algorithm convergence time, the motion of each particle. The compare experiments show 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 heuristic 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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
개선된 FA는 반딧불이들로 하여금 목적함수 전체 영역에 상대적으로 균일하게 분포하는 시간을 길게 갖게 하므로 다양한 탐색방법을 채택할 수 있도록 함으로서, 기존의 FA보다 주어진 환경(objective function)에 대한 전역탐색 능력을 향상시키고자 한다. 제안된 방법에서는 이를 위해 반딧불이 중 일부를 돌연변이로 간주하여 그들로 하여금 또 다른 이동 규칙으로 이동하게 한다.
본 논문에서는, 자연계 기반의 확률적 최적화 방법들의 태생적 한계인 알고리즘의 느린 수렴속도의 극복 방법을 소개하고 이를 기존의 FA에 적용하여 개선된 FA (Improved FA)를 제안한다. 이를 제안하는 과정에서 실험 대조군으로서 다양한 도메인에서 그 성능이 입증된 PSO와 기존의 FA를 함수 최적화에 사용하였다.
비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다. 본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 부분 돌연변이(partial mutation) 휴리스틱을 적용하여 설계된 개선된 FA(Improved FA)를 제안하였다. 이를 분석하기 위한 벤치마크 함수들을 최적화하는 비교 실험 결과, 개선된 FA가 PSO와 기존의 FA보다 정확도와 수렴속도 측면에서 우수한 것을 확인하였고 본 연구의 타당성을 보였다.
최적화 문제는 문제영역을 목적함수로 모델링 하여 구조 탐색이나 이동로봇의 경로 계획 문제에 널리 응용되어 왔다[1]. 이러한 문제 영역에서 해결해야 할 문제는 어떤 최적화 기준을 만족하면서 주어진 환경에서 충돌 없는 경로를 생성하는 것이 목표이다. 이를 위한 접근 방법으로 미리 알려진 환경 모델에 기반한 오프라인 전역 경로 계획과 알려지지 않은 환경에서의 온라인 지역 경로 계획 방법으로 나누어 연구되어 왔다.
가설 설정
1. 모든 반딧불이들은 암수를 구별하지 않는다(unisex).
3. 반딧불이의 밝기는 목적함수의 값에 의해 결정된다.
제안 방법
본 장에서는 기존의 FA와 유사한 알고리즘인 Particle Swarm Optimization(PSO)를 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석한다 PSO는 FA처럼 집단의 정보를 공유하여 최적화/탐색을 수행하는 방법을 취하고 있으며 여러 도메인에서의 그 성능이 경험적으로 입증되었으므로 FA의 개선을 위하여 이를 비교 분석하는 것은 의미 있는 접근방법이 될 것이다.
본 장에서는 앞서 살펴본 반딧불이들의 분포 정도와 정확성, 수렴속도와의 관계를 고려하여 기존의 FA를 기반으로 휴리스틱을 적용한 개선된 FA를 제안한다.
본 논문에서는 Xin-She Yang에 의해 소개된 반딧불이 알고리즘(FA)을 휴리스틱에 의하여 개선하고 분석하였다. 이를 위하여 여러 도메인에서 성공적으로 응용되었으며, 그 작동 방식이 FA와 비슷한 Particle Swarm Optimization(PSO)를 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석하였다. 비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다.
본 논문에서는, 자연계 기반의 확률적 최적화 방법들의 태생적 한계인 알고리즘의 느린 수렴속도의 극복 방법을 소개하고 이를 기존의 FA에 적용하여 개선된 FA (Improved FA)를 제안한다. 이를 제안하는 과정에서 실험 대조군으로서 다양한 도메인에서 그 성능이 입증된 PSO와 기존의 FA를 함수 최적화에 사용하였다. 결론적으로 개선된 FA를 사용하였을 때가 PSO나 FA를 사용하였을 때보다 우수한 결과를 내놓음을 보임으로 본 연구의 타당성을 입증 하고자 한다.
개선된 FA는 반딧불이들로 하여금 목적함수 전체 영역에 상대적으로 균일하게 분포하는 시간을 길게 갖게 하므로 다양한 탐색방법을 채택할 수 있도록 함으로서, 기존의 FA보다 주어진 환경(objective function)에 대한 전역탐색 능력을 향상시키고자 한다. 제안된 방법에서는 이를 위해 반딧불이 중 일부를 돌연변이로 간주하여 그들로 하여금 또 다른 이동 규칙으로 이동하게 한다.
이론/모형
본 논문에서는 Xin-She Yang에 의해 소개된 반딧불이 알고리즘(FA)을 휴리스틱에 의하여 개선하고 분석하였다. 이를 위하여 여러 도메인에서 성공적으로 응용되었으며, 그 작동 방식이 FA와 비슷한 Particle Swarm Optimization(PSO)를 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석하였다.
성능/효과
2. 각 반딧불이의 매력도는 그것의 빛의 세기에 비례하고, 밝기가 약한 반딧불이가 밝기가 강한 반딧불이 쪽으로 이동한다. 특히, 주변에 자신보다 밝은 빛을 내는 반딧불이가 없으면 그 반딧불이는 랜덤하게 움직인다.
이를 제안하는 과정에서 실험 대조군으로서 다양한 도메인에서 그 성능이 입증된 PSO와 기존의 FA를 함수 최적화에 사용하였다. 결론적으로 개선된 FA를 사용하였을 때가 PSO나 FA를 사용하였을 때보다 우수한 결과를 내놓음을 보임으로 본 연구의 타당성을 입증 하고자 한다.
이를 위하여 여러 도메인에서 성공적으로 응용되었으며, 그 작동 방식이 FA와 비슷한 Particle Swarm Optimization(PSO)를 정확도 측면, 수렴 시간 측면, 각 입자의 움직임 측면에서 비교 분석하였다. 비교 실험 결과, FA의 정확도는 PSO보다 나쁘지 않았지만, 수렴 속도는 느린 것으로 나타났다. 본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 부분 돌연변이(partial mutation) 휴리스틱을 적용하여 설계된 개선된 FA(Improved FA)를 제안하였다.
<표 1>의 결과로부터 FA는 해(solution)를 찾는 데 있어서의 정확도(accuracy)가 뛰어난 반면, 알고리즘의 수렴속도는 PSO가 빠르다는 것을 확인할 수 있다.
본 논문은 이에 대한 직관적인 원인을 고찰하고, 이를 극복하기 위해, 기존의 FA에 부분 돌연변이(partial mutation) 휴리스틱을 적용하여 설계된 개선된 FA(Improved FA)를 제안하였다. 이를 분석하기 위한 벤치마크 함수들을 최적화하는 비교 실험 결과, 개선된 FA가 PSO와 기존의 FA보다 정확도와 수렴속도 측면에서 우수한 것을 확인하였고 본 연구의 타당성을 보였다.
후속연구
이 과정에서 사용된 목적함수를 구성하는 각 항의 가중치 변화에 따른 에이전트 이동의 성향 변화는 계속 연구 보완되어야 한다. 이동의 안정성과 속도 관계에 있어서 두 속성은 직관적으로 상충관계임을 알 수 있으며 이를 분석하여 체계화하는 것이 연구의 핵심이 될 것이다.
이동의 안정성과 속도 관계에 있어서 두 속성은 직관적으로 상충관계임을 알 수 있으며 이를 분석하여 체계화하는 것이 연구의 핵심이 될 것이다. 이는 자연계 기반의 확률적 알고리즘을 대표하고 있는 유사연구분야인 PSO와의 보다 더 체계적인 비교분석을 통하여 동적 환경에서의 에이전트 경로 계획 등에 널리 활용될 것으로 기대된다.
이 과정에서 사용된 목적함수를 구성하는 각 항의 가중치 변화에 따른 에이전트 이동의 성향 변화는 계속 연구 보완되어야 한다. 이동의 안정성과 속도 관계에 있어서 두 속성은 직관적으로 상충관계임을 알 수 있으며 이를 분석하여 체계화하는 것이 연구의 핵심이 될 것이다. 이는 자연계 기반의 확률적 알고리즘을 대표하고 있는 유사연구분야인 PSO와의 보다 더 체계적인 비교분석을 통하여 동적 환경에서의 에이전트 경로 계획 등에 널리 활용될 것으로 기대된다.
질의응답
핵심어
질문
논문에서 추출한 답변
최적화 문제는 어떠한 문제에 응용되었는가?
최적화 문제는 문제영역을 목적함수로 모델링 하여 구조 탐색이나 이동로봇의 경로 계획 문제에 널리 응용되어 왔다[1]. 이러한 문제 영역에서 해결해야 할 문제는 어떤 최적화 기준을 만족하면서 주어진 환경에서 충돌 없는 경로를 생성하는 것이 목표이다.
자연계 기반의 확률적 최적화 알고리즘은 무엇인가?
자연계 기반의 확률적 최적화 알고리즘은 곤충의 먹이 찾는 모습이나, 우수한 개체의 생존율이 더 높은 자연계의 생존 법칙, 동물의 주화성 등 자연계의 여러 모습들을 수학적으로 모델링하여 알고리즘에 응용한 것이다. 이들은 대체적으로 비교적 긴 수렴시간을 요구하지만, 계산복잡도 자체는 낮으며, 다양한 휴리스틱으로 알고리즘의 수렴속도를 줄일 수 있음이 증명되고 있다.
구조 탐색이나 이동로봇의 경로 계획 문제의 목표는 무엇인가?
최적화 문제는 문제영역을 목적함수로 모델링 하여 구조 탐색이나 이동로봇의 경로 계획 문제에 널리 응용되어 왔다[1]. 이러한 문제 영역에서 해결해야 할 문제는 어떤 최적화 기준을 만족하면서 주어진 환경에서 충돌 없는 경로를 생성하는 것이 목표이다. 이를 위한 접근 방법으로 미리 알려진 환경 모델에 기반한 오프라인 전역 경로 계획과 알려지지 않은 환경에서의 온라인 지역 경로 계획 방법으로 나누어 연구되어 왔다.
참고문헌 (11)
G. Bekey and J. Yuh, “The status of robotics,” IEEE Robotics and Automation Magazine, Vol.15, No.1, pp.80-86, 2008
A. Howard, M. Matari'c, and G. Sukhatme., “Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem,” the 6th International Symposium on Distributed Autonomous Robotics Systems (DARS02), 2002
M. Gerke, “Genetic path planning for mobile robots”, American Control Conference, 1999.
Q, Zhang, G. Gu, “Path planning based on Improved binary 입자 swarm optimization Algorithm”, Robotics, Automation and Mechatronics, 2008 IEEE Conference on, pp.462-466
T. Arei, J. Ota, “Motion Planning of Multiple Mobile Robots”, Proc. IEEE International Conference on Intelligent Robots and Automation, pp.1761-1768, 1992.
A. L. Christensen, “From fireflies to fault-tolerant swarms of robots”, Evolutionary Computation, IEEE Transactions on Vol.13, pp.754-766, 2009
A. Schworer, P. Hovey, “Newton-Raphson Versus Fisher Scoring Algorithm in Calculating Maximum Likelihood Estimates”, Electronic Proceedings of Undergraduate Mathematics Day, No.1, 2004.
A. E. Eiben, J. E. Smith, “Introduction to Evolutionary Computing”, Springer-Verlog, New York, 2003.
X.-S. Yang, “Firefly algorithms for multimodal optimization”, Stochastic Algorithms: Foundations and Applications, Lecture Notes in Computer Sciences, Vol. 5792, pp. 169-178, 2009.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.