Evolutionary algorithms and simulated annealing are the most frequently used stochastic optimization algorithms. The evolutionary algorithms modeled their mechanism on the natural evolution. The main concept of the evolutionary algorithms is competition among individuals. On the other hand, the simulated annealing imitated the annealing process of an object. A proper annealing gives the object the crystalline structure, the lowest energy state.
The subject of this thesis is to propose more powerful optimization algorithm through unification of these two famous stochastic optimization method. The basic structure of the proposed algorithm follows the simulated annealing, while the selection is controlled by competition among individuals.
The proposed algorithm has two merits. By using temperature at the generation probability density function, the balance between exploration and exploitation can be effectively controlled and as a result, we can avoid the premature convergence which have long been tackled the evolutionary algorithms. Also, by inducing competition, we can make the algorithm to converge more quickly than the simulated annealing.
The proposed method also can be applied to the multiobjective optimization. We prove that after a number of iterations, the random selection makes some of the found nondominated solutions to disappear and converge to a uniform one. Therefore, we introduce elitism in our algorithm as a deterministic selection rule. The repulsive mutation strategy is additionally proposed for controlling the excessively exploitive selection rule.
We completely prove the convergence of the proposed algorithm. The performance of the new algorithm is compared with the existing optimization method using test problems with various characteristics. At the experiments, the proposed algorithm shows better performance than the other algorithms. Moreover, we proposed a method for designing optimal analog filter as a real-world application of the proposed algorithm.
확률적 검색을 기반으로 하는 대표적인 최적화 알고리즘으로 진화 알고리즘과 모의 담금질 방법을 들 수 있다. 진화 알고리즘은 생명체의 진화 과정을 모형으로 하여 개체 사이의 경쟁을 통해 좋은 해를 찾도록 유도한다. 반면 모의 담금질 방법은 통계 역학에서 영감을 얻은 것으로, 물체를 담금질하는 과정에서 온도가 감소함에 따라 최소 에너지 상태로 수렴하는 모형을 최적화에 응용하는 것이다. 이 논문에서는 기존의 진화 알고리즘과 모의 담금질 방법의 독립된 특성을 하나로 조합한 다개체 모의 담금질 방법을 제안하였다.
제안된 알고리즘에서는 모의 담금질 방법의 찾기 과정을 기본으로 하였으며, 여기에 다개체 개념을 도입하여 개체간의 경쟁을 유도하였다. 곧, 개체들을 초기화 하고 각 개체가 온도를 변수로 하는 확률 밀도 함수에 따라 새로운 개체들을 생성한다. 기존의 개체와 새로운 개체간의 경쟁을 유도하여 더 우수한 개체가 다음 세대에 살아 남도록 하였으며 이 과정을 반복하여 모든 개체들이 광역 최적으로 수렴하게 하였다.
제안된 알고리즘은 크게 두 가지 장점을 갖는다. 먼저, 진화 알고리즘에서는 제한된 개체수에 따른 표본의 오차를 적절히 조절할 수 있는 방법이 없어 조성숙 현상이 쉽게 일어나는 문제점이 있었다. 제안된 알고리즘에서는 개체의 다양성과 찾은 해의 정확도를 담금질 기법을 통해 효과적으로 조절함으로써 조성숙 현상을 해결하였다. 또한 병렬의 모의 담금질 방법에서는 얻을 수 없었던 개체간의 경쟁을 유도함으로써 수렴속도를 좀더 빠르게 할 수 있었다. 제안한 알고리즘의 수렴성은 수학적으로 증명하였다.
제안된 알고리즘을 이용한 다목적 함수의 최적화 방법도 제안하였다. 다목적 함수의 최적화 문제에서 무작위 선택방법으로 인하여 파레토 영역에 있는 좋은 해를 잃게 할 수 있는 문제점을 엘리티즘으로 극복하였다. 또한 엘리티즘의 지나친 수렴성을 조절할 수 있는 방법으로 척력을 이용한 변이 방법을 제안하였다.
기존의 알고리즘과의 비교 실험에서 정확도와 속도면에서 제안한 알고리즘이 전체적으로 더 우수한 성능을 보임을 확인할 수 있었다. 다목적 함수에 최적화에 관해서는 엘리티즘과 척력변이 방법이 니치를 이용한 기존의 방법보다 더 우수함을 보였다. 또한 제안한 방법의 실세계 문제에 대한 응용으로 아날로그 필터 디자인 방법을 제안하였다.
