Optimization problems are easily found in our real lives including various fields such as finance, physics, chemistry, engineering, manufacturing, and so on. Most of these problems are discontinuous or non-differentiable types that limit to be solved by the classic method in mathematics, such as a gradient descent or a quasi-Newton method, as well as complex types. Metaheuristic approaches do not need the gradient or Hessian matrix, having the advantage to optimize and being widely used and studied to solve real-life optimization problems. Metaheuristics, however, have an issue to solve of balancing between diversification and intensification, in which a metaheuristic algorithm should use some strategy to diversify the search in such a way that on the one hand it does not get stuck into local optima (diversification), on the other it is able to converge once the global optimum has been found (intensification).
There are many metaheuristic approaches inspired from nature, recently the researches based on the swarm intelligence which is inspired from the movement of a swarm such as ant colonies, bird flocking, bee colonies, and fish schooling are studied actively. As the representative optimization methods for Continuous Optimization Problems (CnOPs), there are Ant Colony Optimization for continuous domains (ACO$_\mathbb{R}$) and Artificial Bee Colony (ABC) optimization algorithms which are inspired from the foraging behavior of real ants and honeybees respectively. The excellence of these algorithms have already been proven in many earlier studies on these algorithms.
ACO$_\mathbb{R}$ appears a strength in the ability of the intensification to converge once the global optimum has been found, and the algorithm increases only a very small number of Function Evaluations (NFEs) at every iteration in comparison with other algorithms, showing stable and relatively rapid convergence. ACO$_\mathbb{R}$, however, is very sensitive about changing the control parameters, and once the algorithm get stuck into a local optimum, ACO$_\mathbb{R}$ has a strong tendency to converge into the local optimum as it is, having a weakness in the ability of the diversification to avoid a local optimum or local optima depending on a problem. In contrast, ABC algorithm has a strength in the diversification, avoiding the local optima well by basing on a greedy selection. ABC algorithm is also quite simple, robust and flexible because of the modular structure of the algorithm, and employs only two control parameters which is a small number in comparison with other algorithms. However, ABC algorithm could not guarantee the stable and rapid convergence into the global optimum because of the characteristic of greedy selection and the automatic reset function embedded in the algorithm. Hence, a variant of ABC algorithm, called as Gbest-guided ABC (GABC) algorithm, which simply modifies the solution search equation of ABC algorithm by applying the global best (Gbest) solution inspired from PSO algorithm to guide the search of new candidate solutions in order to improve the intensification. Although GABC algorithm has more stable convergence ability than the original, it does not guarantee the convergence as stable as ACO$_\mathbb{R}$.
This thesis has studied on the ways to improve the robustness of ACO$_\mathbb{R}$ algorithm while keeping its fast and stable convergence speed into the optima, by utilize ABC algorithms with the higher success rate over others so that ABC algorithms helps ACO$_\mathbb{R}$ algorithm while maintaining its own robustness. And then, based on this study, the thesis has proposed Heterogeneous Swarm Optimization (HSO) algorithm which optimizes a continuous optimization problem by using the cooperation between ants and bees. This thesis has verified the superiority of HSO algorithm through the performance comparison with the other state-of-the-art algorithms by applying to the existing hundreds of various well-known benchmark problems for continuous optimization under the stricter accuracy level than that in other studies. This thesis has also examined the practical applicability by applying to several practical continuous optimization problems. In conclusion, HSO algorithm has showed the wide applicability to many kinds of different continuous optimization problems while having the high reliability in finding an optimal solution by basing it on the balance between intensification and diversification and its high success rate.
최적화 문제는 실제 우리 생활과 밀접한 금융, 물리, 화학, 공학, 제조 등과 같은 분야에서 흔하게 찾아볼 수 있다. 이런 최적화 문제들의 대부분은 복잡한 형태일뿐만 아니라 고전적인 방법들, 예를 들면, 기울기 강하 (gradient descent)나 준뉴턴 (quasi-Newton) 방법 등을 적용하여 풀기에는 한계가 있는 미분 불가능하거나 불연속한 형태를 가진 경우가 많다. 따라서 기울기나 헤시안 행렬 (Hessian matrix)를 필요로 하지 않는 메타휴리스틱 (metaheuristic) 접근법들이 실제 문제의 해를 찾기 위해 많이 사용되고, 연구되고 있다. 하지만, 메타휴리스틱 접근법들도 전역 최적해 (global optimum)로 빠르게 수렴하도록 하는 강화 (intensification) 전략과 문제들이 가진 지역 최적해들 (local optima)을 회피하게 하는 다변화 (diversification) 전략 사이의 균형을 맞춰야 하는, 풀어야 할 문제를 가지고 있다.
메타휴리스틱 접근법들 중에는 자연으로부터 영감을 얻은 알고리즘들이 많은데, 최근에는 개미, 새, 벌, 물고기와 같은 군집의 움직임으로부터 영감을 얻은 군집 지능 (swarm intelligence)에 기반한 알고리즘들에 대한 연구가 활발히 진행되고 있다. 연속 최적화 문제 (CnOP, Continuous Optimization Problem)에 대한 대표적인 최적화 방법으로써, 각각 개미와 벌의 먹이 찾기 행동을 모사한 최적화 알고리즘인 ACO$_{\mathbb{R}}$ (Ant Colony Optimization for continuous domains)과 ABC (Artificial Bee Colony) 최적화 알고리즘이 있다. 이들의 우수성은 이미 많은 연구들에서 밝혀진 바 있다.
ACO$_{\mathbb{R}}$은 일단 전역 최적해를 찾기만 하면 강한 수렴성을 갖게 하는 강화의 능력에 강점을 보이며, 다른 알고리즘들에 비해 한 반복 (iteration) 내에서의 함수 평가의 횟수 (NFEs, Number of Function Evaluations)는 적게 증가하면서, 안정적이고, 비교적 빠른 수렴성을 보인다. 하지만, ACO$_{\mathbb{R}}$은 사용자 제어변수들 (control parameters)이 변화에 민감하며, 또 일단 한번 지역 최적해에 빠지면 그 상태로 수렴하는 경향성이 강해 지역 최적해를 회피하는 다변화 측면에 있어서는 오히려 약점을 가지고 있다. 이와는 반대로, ABC 알고리즘은 그리디 선택 (greedy selection)에 기반하여 지역 최적해에서 회피하는 다변화 측면에서 강점을 보인다. 또한 ABC 알고리즘은 비교적 단순하고 강인하며, 모듈화된 구조를 가지고 있어 변형이 용이하며, 사용자 제어변수의 수가 겨우 2개로 다른 알고리즘들에 비해 극히 적다는 장점을 가진다. 하지만, 그리디 선택의 특성과 알고리즘 내부에 내재된 자동 리셋 기능으로 인해, 전역 최적해로의 안정적이고 빠른 수렴을 보장하기는 어렵다. 이런 이유에서, ABC 알고리즘의 변형인 전역 최고해 유도 기반 ABC (Gbest-guided ABC) 알고리즘, 즉 GABC 알고리즘이 제안되었다. 이는 PSO (Particle Swarm Optimization) 알고리즘에서 전역 최고해 (global best solution)을 이용하는 방법에 착안하여, 이를 단순히 ABC 알고리즘의 해 탐색식에 적용, 새로운 다음 후보 해들이 전역 최고해로 유도 되도록 하여, 강화의 능력을 향상시켰다. 하지만, 비록 원래의 ABC 알고리즘에 비해서는 좀 더 안정적인 수렴이 가능해졌지만, 그래도 여전히 ACO$_{\mathbb{R}}$ 만큼의 안정적이고 빠른 수렴을 보장하지는 못한다.
본 논문에서는 ACO$_{\mathbb{R}}$ 알고리즘의 빠르고 안정적인 수렴 능력은 유지하면서 다른 알고리즘들보다 지역 최적해 회피에 있어 강인함을 가진 ABC 알고리즘들을 활용, ABC 알고리즘들이 가진 본연의 강인함은 유지하고 ACO$_{\mathbb{R}}$를 도와 ACO$_{\mathbb{R}}$의 강인성을 향상시키는 방법들에 대해 연구하였다. 그리고 이를 바탕으로 개미와 벌의 군집 협동을 활용한 최적화 알고리즘인 HSO (Heterogeneous Swarm Optimization) 알고리즘을 제안하였다. 본 논문에서는 현존하는 수백 가지의 연속 최적화 성능 평가 기준 문제들 (benchmark problems)을 가지고, 다른 기존의 연구들에 비해 좀 더 엄격한 해의 정확성 수준 (accuracy level)을 적용하여, 다른 최신 알고리즘들과 성능 비교를 통해 HSO 알고리즘의 우수성을 입증하였다. 또한 몇몇 실제적인 연속 최적화 문제들에 제안한 알고리즘을 적용하여, HSO 알고리즘의 적용가능성을 실제적으로 시험해 보았다. 결론적으로 HSO 알고리즘은 강화 전략과 다변화 전략 사이의 균형과 타 알고리즘보다 높은 성공률을 바탕으로 다양한 연속 최적화 문제들에 대한 폭넓은 적용가능성과 그 문제들에 대해 해를 찾을 수 있을 것이라는 높은 신뢰성을 보여주었다.
