진화 알고리즘은 여러 개의 상충하는 목적을 갖는 다목적 최적화 문제를 해결하기에 적합한 방법이다. 특히, 파레토 지배관계에 기초하여 개체의 적합도를 평가하는 파레토 기반 진화알고리즘들은 그 성능에 있어서 비교적 우수한 평가를 받고 있다. 그러나 일반화된 다목적 최적화 진화알고리즘은 복잡한 문제들에서 찾아진 해들의 분포가 전체 파레토 경계면에 대하여 균일하지 못하고 특정 지역에서 집중적으로 해를 생성하는 문제점을 가지고 있다. 본 논문에서 우리는 이러한 문제점을 보완하기 위한 다목적 최적화 진화알고리즘을 제안한다. 제안한 알고리즘은 현재까지 찾아진 최적해들 중 특정 지역에 관중되지 않은 해를 우수 종자로 복제 연산에 참여시킨다. 따라서 특별한 지역탐색 기법을 사용하지 않아도 종자가 되는 개체 주위에 새로운 개체를 생성할 확률이 높기 때문에 지역탐색의 효과를 가질 수 있고, 비교적 고른 분포의 파레토 최적 해를 생성한 수 있다. 5개의 테스트 함수에 대한 실험 결과, 제안한 알고리즘은 모든 문제에서 전체 파레토 경계면에 균일한 분포의 해들을 생성할 수 있었으며, 많은 지역해를 가지는 문제를 제외한 모든 문제에서 NSGA-II보다 우수한 수렴 결과를 보였다.
진화 알고리즘은 여러 개의 상충하는 목적을 갖는 다목적 최적화 문제를 해결하기에 적합한 방법이다. 특히, 파레토 지배관계에 기초하여 개체의 적합도를 평가하는 파레토 기반 진화알고리즘들은 그 성능에 있어서 비교적 우수한 평가를 받고 있다. 그러나 일반화된 다목적 최적화 진화알고리즘은 복잡한 문제들에서 찾아진 해들의 분포가 전체 파레토 경계면에 대하여 균일하지 못하고 특정 지역에서 집중적으로 해를 생성하는 문제점을 가지고 있다. 본 논문에서 우리는 이러한 문제점을 보완하기 위한 다목적 최적화 진화알고리즘을 제안한다. 제안한 알고리즘은 현재까지 찾아진 최적해들 중 특정 지역에 관중되지 않은 해를 우수 종자로 복제 연산에 참여시킨다. 따라서 특별한 지역탐색 기법을 사용하지 않아도 종자가 되는 개체 주위에 새로운 개체를 생성할 확률이 높기 때문에 지역탐색의 효과를 가질 수 있고, 비교적 고른 분포의 파레토 최적 해를 생성한 수 있다. 5개의 테스트 함수에 대한 실험 결과, 제안한 알고리즘은 모든 문제에서 전체 파레토 경계면에 균일한 분포의 해들을 생성할 수 있었으며, 많은 지역해를 가지는 문제를 제외한 모든 문제에서 NSGA-II보다 우수한 수렴 결과를 보였다.
Evolutionary a1gorithms are well-suited for multi-objective optimization problems involving several, often conflicting objectives. Pareto-based evolutionary algorithms, in particular, have shown better performance than other multi-objective evolutionary algorithms in comparison. However, generalized...
Evolutionary a1gorithms are well-suited for multi-objective optimization problems involving several, often conflicting objectives. Pareto-based evolutionary algorithms, in particular, have shown better performance than other multi-objective evolutionary algorithms in comparison. However, generalized evolutionary multi-objective optimization algorithms have a weak point, in which the distribution of solutions are not uni-formly distributed onto Pareto optimal front. In this paper, we propose an evolutionary a1gorithm for multi-objective optimization which uses seed individuals in order to overcome weakness of algorithms Published. Seed individual means a solution which is not located in the crowded region on Pareto front. And the idea of our algorithm uses seed individuals for reproducing individuals for next generation. Thus, proposed a1go-rithm takes advantage of local searching effect because new individuals are produced near the seed individual with high probability, and is able to produce comparatively uniform distributed pareto optimal solutions. Simulation results on five testbed problems show that the proposed algo-rithm could produce uniform distributed solutions onto pareto optimal front, and is able to show better convergence compared to NSGA-II on all testbed problems except multi-modal problem.
Evolutionary a1gorithms are well-suited for multi-objective optimization problems involving several, often conflicting objectives. Pareto-based evolutionary algorithms, in particular, have shown better performance than other multi-objective evolutionary algorithms in comparison. However, generalized evolutionary multi-objective optimization algorithms have a weak point, in which the distribution of solutions are not uni-formly distributed onto Pareto optimal front. In this paper, we propose an evolutionary a1gorithm for multi-objective optimization which uses seed individuals in order to overcome weakness of algorithms Published. Seed individual means a solution which is not located in the crowded region on Pareto front. And the idea of our algorithm uses seed individuals for reproducing individuals for next generation. Thus, proposed a1go-rithm takes advantage of local searching effect because new individuals are produced near the seed individual with high probability, and is able to produce comparatively uniform distributed pareto optimal solutions. Simulation results on five testbed problems show that the proposed algo-rithm could produce uniform distributed solutions onto pareto optimal front, and is able to show better convergence compared to NSGA-II on all testbed problems except multi-modal problem.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서 우리는 종자 개체를 이용한 다목적 최적화 진화알고리즘(SIEA : Seed Individual based Evolutionary Algorithms for Multi-objective Optimization Problems)을 제안한다. SIEA의 기본적인 아이디어는 농생물학의 우수종자 개량과정을 다목적 최적화 진화알고리즘에 적용한 것으로, 보다 우수한 개체를 만들기 위해 현재까지 찾아진 최우 수 개체를 우수종자로 복제 연산에 참여시키는 것이다.
본 논문에서 우리는 우수종자 개체를 중심으로 진화를 수행하는 다목적 최적화 진화알고리즘을 제안하였다. 제안한 알고리즘은 우수종자의 선택 기준을 현재까지 찾아진 최적해들 중 특정 지역에 편중되지 않은 해로 하였고, 선택된 우 수종자를 중심으로 복제연산을 수행하였다.
가설 설정
. 알고리즘의 결과로 얻어진 파레토 경계면과 최적 파레토 경계면의 거리는 최소화 되어야 한다. 즉, 최적 파레토 경계면에 잘 수렴하여야 한다.
. 찾아진 해들의 분포는 균일 분포를 가져야 한다.
제안 방법
본 논문에서 사용한 C metric과 S metrice 서론에서 제시한 다목적 최적화의 일반화된 세 가지 목적 중 첫 번째와 두 번째 목적에 대한 평가방법이다. 즉, Cmetrice 첫 번째 목적인 수렴 성능에 대한 상대적 평가방법이다.
실험은 각 문제에 대해 각각 30회 수행 하였으며, 각 알고리즘에서 사용한 공통 파라메타는 다음과 같다.
본 논문에서 우리는 우수종자 개체를 중심으로 진화를 수행하는 다목적 최적화 진화알고리즘을 제안하였다. 제안한 알고리즘은 우수종자의 선택 기준을 현재까지 찾아진 최적해들 중 특정 지역에 편중되지 않은 해로 하였고, 선택된 우 수종자를 중심으로 복제연산을 수행하였다. 따라서 특별한 지역탐색 기법을 사용하지 않더라도 종자가 되는 개체 주위에 새로운 개체를 생성할 확률이 높기 때문에 부분적인 지역탐색의 효과를 가질 수 있음을 실험적으로 보였다.
대상 데이터
제안한 SIEA의 성능을 평가하기 위해 Deb[12, 13]이 제시한 테스트 함수들을 실험대상으로 하였다. 테스트 함수들은 다목적 최적화 진화알고리즘들이 최적 파레토 경계면에 수 렴하고 균일분포의 파레토 해들을 만드는데 있어 어려움의 원인이 될 수 있는 몇 가지 특징을 가지고 있다.
이론/모형
개체집단 F내의 개체들에 대한 적합도는 개체의 순위와 같은 순위의 개체들 사이의 거리를 사용하여 계산한다. 개체의 순위는 NSGATI 에서 사용한 Nondominated sorting 방법을 사용하여 첫 번째 비지배 경계면의 개체들에는 순위 1 을, 다음 비지배 경계면의 개체들에는 순위 2를 할당하는 방법을 사용하였다. 그리고 같은 순위의 개체들 사이의 부분 순서관계를 부여하기 위해 이웃개체와의 거리 정보를 이용한다.
둘째 우수 종자보존소(seed pool)의 구성은 현 세 대의 비지배 개체집합(archive set)에서 지역편중이 되지 않은 개체들을 선택한다. 지역 편중의 정도는 41에서 설명한 개체의 이웃 거리 계산 방법을 사용한다. (그림 4)의 비지배 개체집합의 경우 가장 지역편중이 되지 않은 개체는 d이고, 다음은 e 이다.
종자 개체 선택의 효과를 입증하기 위한 사전 실험으로 우리는 Schaffer[9]에 의해 사용되었던 비교적 간단한 다목적 최적화 문제를 적용하였다. Schaffer 문제는 식 (5)와 같이 정의된다.
본 논문에서 우리는 최적화 알고리즘의 성능을 평가하기 위한 척도로서 C metric(Coverage Metric)[10]과 S metric (Spacing Metric)[ll]을 사용한다. C metrice 한 알고리즘 의 결과가 다른 알고리즘의 결과를 얼마나 지배하는가詈 보 여줄 수 있는 평가방법이다.
즉, Cmetrice 첫 번째 목적인 수렴 성능에 대한 상대적 평가방법이다. 최적 파레토 경계면을 이미 알고 있다면 절대적 평가 방법을 사용할 수 있지만, 대부분의 다목적 최적화 문제의 경우 최적 파레토 경계면을 미리 알고 있지 못하기 때문에 알고리즘의 수렴성능 평가로 C metric과 같은 상대 평가 방법을 사용하였다.
성능/효과
이 장에서는 우리가 제안하는 SEEA와 실험적 비교 대상이 되는 NSGA-HE6] 알고리즘을 설명한다. NSGA-口 는 NSGA [5]를 개선한 알고리즘으로 비지배 개체 정렬(non-dominated sorting)의 높은 연산 복잡도를 개선하고, 엘리티즘(elitism)을 보다 강화하였다. 그리고 밀도측정(density estimation) 연산자를 추가함으로서 적합도 평가에서 NSGA와 같이 공유 매개변수(sharing parameter)。血"를 정의할 필요성을 제거한 알고리즘이다.
[표 2]는 각 문제에 대한 C metric 결과이다. C metric 결과는 幻, 7% 了3문제에서 SIEA의 결과가 NSGA-Ⅱ의 결과보다 상대적으로 최적 파레토 경계면에 잘 수렴함을 보이고 있다. 특히 了5문제에서는 SIEA의 결과가 월등히 최적 파레토 경계면에 잘 수렴하는 결과를 보였다.
[표 3]은 SIEA와 NSGA-n 알고리즘의 S metric 결과이다. 두 알고리즘의 S metric 결과는 务문제를 제외한 모든 문제에서 SIEA의 해들의 분포가 비교적 고른 분포를 보이고 있음을 보여준다. ?3문제는 이산적인 파레토 경계면을 가지는 문제이기 때문에 SIEA에서는 우수종자의 선택이 이산적으로 끊어지는 각 부분의 끝에 위치한 개체가 선택되는 경향을 가진다.
제안한 알고리즘은 우수종자의 선택 기준을 현재까지 찾아진 최적해들 중 특정 지역에 편중되지 않은 해로 하였고, 선택된 우 수종자를 중심으로 복제연산을 수행하였다. 따라서 특별한 지역탐색 기법을 사용하지 않더라도 종자가 되는 개체 주위에 새로운 개체를 생성할 확률이 높기 때문에 부분적인 지역탐색의 효과를 가질 수 있음을 실험적으로 보였다. 또한 부분적인 지역 탐색의 효과로 대부분의 문제에서 전체 해집 합의 분포가 비교적 고른 분포를 가질 수 있고, 최적해로의 수렴이 우수함을 실험적으로 보였다.
따라서 특별한 지역탐색 기법을 사용하지 않더라도 종자가 되는 개체 주위에 새로운 개체를 생성할 확률이 높기 때문에 부분적인 지역탐색의 효과를 가질 수 있음을 실험적으로 보였다. 또한 부분적인 지역 탐색의 효과로 대부분의 문제에서 전체 해집 합의 분포가 비교적 고른 분포를 가질 수 있고, 최적해로의 수렴이 우수함을 실험적으로 보였다.
후속연구
그러나 제안한 알고리즘은 전체 개체집단의 다양성 유지에 약점을 가지고 있기 때문에 많은 지역해를 포함하는 문제에서는 전역 최적해로의 수렴에 어려움이 있었다. 따라서 제안된 알고리즘의 장점을 유지하면서 전체 개체집단의 다 양성을 보다 잘 유지할 수 있도록 하는 방안에 대한 연구가 추가적으로 이루어져야 할 것이다.
참고문헌 (14)
Carlos A. Coello Coello, 'An Updated Survey of GA-Based Multiobjective Optimization Techniques,' ACM Computing Surveys, Vol.32, No.2, pp.109-143, June, 2000
Frank Kursawe, 'A Variant of evolution strategies for vector optimization,' In Parallel Problem Solving from Nature. 1st Workshop, PPSN I, Vol.496 of Lecture Notes in Computer Science, pp.193-197, 1991
Carlos M. Fonseca and Peter J. Fleming, 'Genetic Algorithms for Multiobjective Optimization : Formulation, Discussion and Generalization,' In Proceedings of the Fifth International Conference on Genetic Algorithms, pp.416-423, 1993
Jeffrey Horn and Nicholas Nafpliotis, 'Multiobjective Optimization using the Niched Pareto Ganetic Algorithm,' Technical Report IlliGAl Report 93005, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA, 1993
N. Srinivas and Kalyanrnoy Deb, 'Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms,' Evolutionary Computation, Vol.2, No.3 pp.221-248, 1994
Kalyanmoy Deb, Samir Agrawal, Amrit Pratab, and T. Meyarivan, 'A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization : NSGA- II,' Proceedings of the Parallel Problem Solving from Nature VI Conference, pp.849-858, Springer, 2000
Eckart Zitzler, Marco Laumanns and Lothar Thiele, 'SPEA 2 : Improving the Strength Pareto Evolutionary Algorithm,' EUROGEN 2001, Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, pp.12-21, 2001
Carlos A. Coello Coello and Nareli Cruz Cortes, 'Solving Multiobjective Optimization Problems using an Artificial Immune System,' Technical Report EVOCINV-05-2002, Evolutionary Computation Group at CINVESTAV, Kluwer Academic, 2002
J. D. Schaffer, 'Multiple objective optimization with vector evaluated genetic algorithms,' In Genetic Algorithms and their Applications : Proceedings of the First International Conference on Genetic Algorithms, pp.93-100, 1985
Eckart Zitzler and Lothar Thiele, 'Multiobjective optimization using evolutionary algorithms - a Comparative study,' In Parallel Problem Solving from Nature V, pp.292-301, 1998
Jason R. Schott, Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1995
Kalyanmoy Deb, 'Multi-Objective Genetic Algorithms : Problem Difficulties and Construction of Test Problems,' Evolutionary Computation, Vol.7, No.3, pp.205-230, 1999
※ AI-Helper는 부적절한 답변을 할 수 있습니다.