In the world around us it is rare for any problem to have only a single objective. We have to consider generally multiple objectives or parameters have to be met or optimized at the same time. There have been many researchers who use evolutionary algorithms to solve multiobjective problems and there have been developed many efficient algorithms. On the other hand, though the simulated annealing is a very powerful and robust search algorithm in various optimization fields, it has seldom been used for the multiobjective optimization because it conventionally uses one search agent, and thus is inadequate in finding all the
solutions of Pareto set of the multiobjective problems.
With the idea that simulated annealing has a uniform state probability over global
optimum, a new multiobjective simulated annealing method is suggested. The suggested algorithm uses population-based simulated annealing (PSA) and adapts elitism in the process of selection. We prove that after a number of iterations, the stochastic selection makes some of the found non-dominated solutions to disappear and to converge to a uniform one. Finally, we conclude that a deterministic selection rule seems to be more effective than the random selection in multiobjective optimization.
When discovered for solving a search and optimization problem, a new algorithm is necessary to be compared with other existing popular methodologies in terms of their performance on various test problems. Comparing performance requires adequate metric which reflects the goal of optimization problem. Unlike in single-objective optimization, there are two goals in a multiobjective optimization: 1) convergence to the Pareto-optimal set and 2) maintenance of diversity in solutions of the Pareto frontier. These two tasks cannot be measured adequately with one performance metric. Thus many frontier performance metrics have been suggested, but they have some problems, especially it is difficult to define proper metric for diversity. We propose a new metric for measuring diversity.
The proposed metric uses Delaunay triangulation and can be applied to even multiobjective problems which have more than 3 objectives. We show that measuring diversity with this metric is adequate and compare different algorithms in terms of diversity with this metric.
실생활에서 접하는 대부분의 최적화 문제는 2가지 이상의 상충되는 목적을 동시에 만족시키고자 하는 문제이다. 이 논문에서는 여러 개의 전역 최적점이 존재하는 경우, 모의 담금질 방법을 이용하면 균일한 확률로 모든 최적점들을 찾을 수 있다는 데에서 착안하여 엘리트주의를 도입한 다개체 기반의 모의 담금질 방법을 제안하였다. 여러 개의 알고리즘이 존재하는 경우 각각의 알고리즘의 성능 비교를 위해서는 최적화 문제의 목표를 반영한 평가지표가 필요하다. 다목적함수 최적화 문제의 경우 특히 해의 정확도와 다양성을 모두 만족시켜야 하기때문에 적절한 평가지표의 개발이 필수적이다. 앞에서 말했듯이, 다목적함수 최적화 문제는 해의 정확도와 다양성 두 가지를 모두 만족시켜야 하는데, 이 둘은 서로 상충되므로 하나의 평가지표로는 성능을 비교하기 힘들다. 정확도를 측정하기 위한 지표는 기존의 것으로 사용가능하나, 다양성을 측정하기 위해 현재 널리 사용되고 있는 평가지표는 목적함수가 3개 이상인 경우에는 적용할 수 없는 단점이 있다. 이 논문에서는 Delaunay 삼각형법을 이용하여 3개 이상의 목적함수를 가지는 문제에 대해서도 적용 가능한, 해의 다양성 평가를 위한 지표를 제안하고 여러 검사함수들을 이용한 모의 실험을 통해 정당성을 보였다. 또한 제안한 평가지표를 이용하여 다목적함수 최적화를 위해 모의 담금질 기법을 사용하여 제안한 알고리즘의 성능을 평가해보았다.
