Recently, there have been developed several promising multiobjective evolutionary algorithms such as SPEA, PAES, NSGA-II, PESA, and SPEA2. In those multiobjective evolutionary algorithms, much effort has been concentrated on the elitism and selection technique of the parent and archive solutions. Recently, most of the multiobjective evolutionary algorithms adopt the elitism to improve the efficiency and effectiveness of the multiobjective evolutionary algorithms by utilizing repeatedly the solutions with good characteristics (objective values). And also parent and archive solutions are selected based on the Pareto rank and distribution density so that the best coverage and uniformity of found solutions can be achieved. However, all of the evolutionary algorithms use the same offspring generation scheme such as crossover or mutation operator and new offspring generation schemes have not been tried.
In this thesis, I will propose new three kinds of multiobjective evolutionary algorithms to improve the efficiency and the effectiveness of the multobjective evolutionary algorithm by introducing new offspring generation schemes. In all of the multiobjective algorithms proposed in this thesis, the elitism and selection technique mentioned above are utilized with no change.
In the first offspring generation scheme, special offspring generation structure is used to extract the Pareto dominance information among the solutions and introduce an important concept, “age”, to determine the evolution distance of the solutions. Age concept is an important concept in three kinds of multiobjective evolutionary algorithms proposed in this thesis so that it will be repeatedly and widely utilized because the convergence level can be estimated to a certain extent by evaluating the age of solutions. However, this offspring generation scheme cannot be applied to the problem with high parameter dimensions due to the characteristics of the offspring generation scheme.
To cope with the problems with the high dimensional parameter space, two kinds of offspring generation schemes are proposed. In the second offspring generation scheme, offspring are generated at the position distant from the parent by evolution distance along the evolution direction. The evolution direction is determined by examine the Pareto dominance relation among the solutions, In other words, the evolution direction is the direction from the nearest dominated solution with lowest Pareto rank to itself. And the evolution distance is determined by the age of the parent solutions. In this offspring generation scheme, the evolution direction can be selected for the solutions with dominated solutions but the evolution direction cannot be selected for the solutions without dominated solutions. For the solutions without dominated solutions, the evolution direction is determined randomly. However, the number of solutions without dominated solutions is increased and the effectiveness of the offspring generation scheme becomes low as the number of iterations gets increased.
In the third offspring generation scheme, crossover operator is combined into the new offspring generation scheme to overcome the problem of increasing solutions without dominated solutions in the second offspring generation scheme. The increasing problem of solutions without dominated solutions occurs when the solutions exist near the Pareto optimal set. When crossover operator is used in generating offspring, offspring are generated near the parent solutions so that crossover shows good performance when solutions exist near the Pareto optimal set. Therefore, for the solutions without dominated solutions, the efficiency and effectiveness of the offspring generation scheme can be much improved by applying the crossover operator to them. When solutions exist at the regions distant from the Pareto optimal set, solutions approach the Pareto optimal set fast by using Pareto dominance direction and age concept. When solutions approach to the Pareto optimal set, solutions can converge to the Pareto optimal set effectively by the crossover operator.
In this thesis, three kinds of new multiobjective evolutionary algorithms proposed are compared with other promising multiobjective evolutionary algorithms such as PESA, NSGA2, and SPEA2 and show good performance. In this thesis, I will review the performance metrics, accuracy, coverage, uniformity, and speed, of the multiobjective optimization problem and point out the problems of previous coverage and uniformity metrics. I also propose new performance metrics for the coverage and uniformity to overcome the problems of previous coverage and uniformity metrics.
In this thesis, the notion of "age" is introduced and plays good role in offspring generation schemes where the evolution distance can be determined according to the various situations of complex multiobjective optimization problems. And also the age concept is a solution to the stopping criteria that is an open problem in the multiobjective evolutionary algorithm because the age can represent the maximum convergence range from the Pareto optimal set although the exact distance to the Pareto optimal set cannot be known.
이 논문에서는 새로운 다목적 진화 알고리즘 개발에 대한 연구를 내용으로 구성되어 있다. 기존의 많은 다목적 진화 알고리즘에서는 주로 부모를 잘 선택해서 알고리즘의 효용성을 높이고자 하는 측면에서 연구가 주로 진행되어 왔다. 그래서 선택기준으로 파레토 랭크와 분포 밀도를 동시에 고려하는 방법이 중심적인 선택 방법으로 일반화되어 사용되고 있다. 그리고 좋은 해들을 계속 유지시켜서 반복적으로 활용을 하는 엘리티즘도 또한 알고리즘의 효용성을 높일 수 있는 공통적인 하나의 방법으로 자리잡고 있다. 이 논문에서도 엘리티즘과 해의 선택방법으로 파레토 랭크와 분포 밀도를 고려하는 방법을 계승하여 사용한다.
자손을 발생시키는 방법은 대부분의 알고리즘들에서 공통적으로 교배와 변이만을 사용해서 자손을 발생시키는 방법을 사용하고 있다. 이 방법이 지금까지 좋은 결과를 나타내고 있지만 실제로 교배는 알고리즘이 해들을 찾는데 아주 느린 특성을 가지고 있다. 이것은 교배가 주로 부모에서 근접한 해들을 주로 발생시키기 때문에 해들이 찾고자 하는 파레토 최적해에 접근하는데 많은 시간이 걸리기 때문에 알고리즘이 해를 찾는데 많은 시간이 걸리게 된다. 따라서 이 논문에서는 기존의 자손 발생의 효율성을 높이기 위해서 새로운 자손 발생 방법을 제안해서 그 효용성을 보인다. 자손 발생에 있어서 중심적인 부분은 찾고자 하는 해 사이에서 그 지배 관계를 조사해서 해들의 진화 방향을 결정하고 새로운 “나이” 개념을 도입하여 해들의 진화 거리를 결정함으로써 보다 효율적으로 자손을 발생시켜서 정확성, 찾는 영역, 찾은 해들의 균일 분포, 그리고 속도 측면에서 우수한 특성을 얻는다. 그리고 나이는 해들의 최적해에 대한 수렴 정도를 나타낼 수 있으므로 자손을 발생시키는데 있어서 아주 좋은 정보를 제공할 수 있어서 나이가 증가함에 따라 찾는 영역을 줄일 수 있어서 전체적인 알고리즘의 효율성을 굉장히 높일 수 있는 이 논문의 중심 개념이다. 또한 수렴정도를 판단할 수 있기 때문에 다목적 진화 알고리즘의 공개적인 문제의 하나인 정지에 대한 하나의 판단 조건으로도 사용될 수가 있다.
이 논문에서는 또한 알고리즘의 성능을 평가할 수 있는 기존의 성능 평가요소들을 알아보고 그것의 문제점을 파악한다. 파악된 문제점들을 해결할 수 있는 새로운 성능 평가 요소들을 제안한다. 기존의 성능 평가요소와 문제가 있는 기존의 성능 평가 요소들을 대신할 수 있는 새로운 성능 평가 요소들을 바탕으로 제안된 다목적 진화알고리즘들과 최근의 유망한 다른 알고리즘들을 다양한 검사 함수들에 대한 수행 결과를 비교하여 제안된 알고리즘들의 우수성을 보인다.
