Evolutionary algorithms (EAs) inspired from the processes of evolution in nature are based on stochastic search mechanisms. In recent studies, estimation of distribution algorithms (EDAs) using probabilistic modeling have represented the EAs instead of conventional genetic algorithms (GAs), which use crossover and mutation. Quantum-inspired evolutionary algorithm (QEA), one of the novel EDAs, is proved to be better than conventional GAs for single-objective optimization problems. Current researches in EAs are focused on simultaneous optimization problems of several objectives, which are called multiobjective optimization problems (MOPs) and multiobjective evolutionary algorithms (MOEAs) allow to obtain a set of solutions. Since MOEAs provide a set of nondominated solutions, decision making of selecting a preferred one out of them is required in real application. However, there have been a few researches on MOEA in which the user`s preferences are incorporated for this purpose i.e. multiple criteria decision making (MCDM).
This thesis proposes multiobjective quantum-inspired evolutionary algorithm (MQEA) which employs the concept and principles of quantum computing to improve the proximity to Pareto-optimal front and diversity of nondominated solutions for MOPs. MQEA employs the basic characteristic of EDAs such as offspring sampling by the probabilistic representation. It has an advantage to maintain an elitism by storing nondominated solutions of archive externally. Global random migration of nondominated solutions in the archive is adopted to preserve the diversity of solutions of each sub-population. Cooperative coevolutionary concept of MQEA based on parallel structure has robust search ability on more complex and higher-dimensional objective problems. Moreover, this thesis proposes preference-based solution selection algorithm (PSSA) by which user can select a desired one out of nondominated solutions obtained by any one of MOEAs. The PSSA, which is a kind of MCDM, gives user`s preference to multiple objectives or criteria as a degree of consideration by fuzzy measure and makes a decision by fuzzy integral. Also, MQEA with preference-based sorting (MQEA-PS) is proposed to sort the population according to the user`s degree of consideration for many-objective optimization problems. It can overcome the problem of conventional MOEAs with dominance-based sorting that the number of nondominated solutions increases exponentially as the number of objectives increases.
Experimental results on multiobjective 0/1 knapsack problems and DTLZ problems show the effectiveness of the proposed MQEA from the viewpoint of the proximity to the Pareto-optimal set and the spread of nondominated set, measured by four performance metrics such as attainment surface, size of the dominated space, coverage of two sets and diversity metric. Parametric study verifies the performance of MQEA according to variant of parameter setting. Moreover, as a real world problem, multiobjective optimization in fuzzy path planner of mobile robot is chosen and MQEA is employed to optimize the objectives such as elapsed time, heading angle error and posture angle error. Computer simulations and real experiment results show the selected solution properly reflects the user`s preference, which are carried out to demonstrate the effectiveness of the proposed PSSA.
최적화를 위해 자연계의 진화 과정을 모사한 진화 알고리즘 (evolutionary algorithm, EA)은 확률적인 탐색 메카니즘에 기반을 두고 있다. 최근에는 확률 모델링을 이용한 분포 학습 알고리즘(estimation of distribution algorithm, EDA)이 기존의 교배, 돌연변이 연산을 사용한 유전자 알고리즘을 대체하고 있다. 분포 학습 알고리즘 중의 하나인 양자 개념을 도입한 진화 알고리즘(quantum-inspired evolutionary algorithm, QEA)은 단목적 최적화 문제에서 기존 유전자 알고리즘 보다 우수하다고 증명되어왔다. 한편, 최근 진화 알고리즘은 여러 목적을 동시에 최적화 하는 다목적 최적화 문제 (multiobjective optimization problem, MOP)에 주목하고 있고 다목적 진화 알고리즘은 여러 해를 동시에 얻을 수 있다. 하지만 다목적 진화 알고리즘이 동시에 비지배 해(nondominated solution)의 집합을 제공하므로 실제 문제에서는 그 중 하나의 선호하는 해를 결정하기 위한 방법이 필요하다. 그러나 그동안 다기준 의사 결정 (multiple criteria decision making, MCDM)을 다목적 유전자 알고리즘에 적용한 연구는 거의 없었다.
본 논문에서는 양자 컴퓨팅의 개념과 원리를 이용하여 파레토 최적면 (Pareto-optimal front)에 가깝고 해의 다양성을 유지하기 위한 양자 개념을 도입한 다목적 진화 알고리즘 (multiobjective quantum-inspired evolutionary algorithm, MQEA)을 제안한다. MQEA는 확률적 모델에 의해 다음세대를 만드는 분포 학습 알고리즘의 특성을 지니고 있고 외부의 저장소에 비지배 해를 저장하므로써 엘리트주의를 유지한다. 저장소의 비지배 해를 전역 랜덤 이전하여 각 부개체군 (subpopulation)의 다양성을 유지한다. 또한 병렬 구조의 협력 공진화 (cooperative coevolution) 기법은 높은 차원의 다목적 문제에서 탐색 능력을 향상시킨다. 그리고 본 논문은 다양한 다목적 진화 알고리즘으로부터 얻은 비지배 해들 중 사용자가 원하는 하나의 해를 선택하기 위한 선호도 기반 해 선택 알고리즘 (preference-based solution selection algorithm, PSSA)을 제안한다. 다기준 의사 결정 방법의 하나인 PSSA는 퍼지 측정과 퍼지 적분으로 사용자의 고려 정도 (degree of consideration)을 측정하여 여러개의 목적 또는 기준에 사용자의 선호도를 부여할 수 있다. 그리고 기존의 지배관계 기반 정렬 (dominance-based sorting) 하는 방법 대신 선호도 기반 정렬 (preference-based sorting) 방법으로 해를 정렬하는 MQEA를 제안하여 다수의 목적 최적화 문제 (many-objective optimization problem)를 고려한다.
다목적 0/1 가방 문제와 DTLZ 문제에 대한 실험에서 도달한 표면 (attainment surface), 지배면적 (size of dominated space), 두 집합의 포함도 (coverage of two sets), 다양성 (diversity)과 같은 성능 측정 결과는 제안하는 MQEA로 구한 해가 다른 비교 알고리즘들에 비해 파레도 최적면에 더 가깝고 고르게 분포 되어있었다. 또한, 다양한 파라미터의 변화에 따른 성능 변화도 분석하였고 이동 로봇의 퍼지 경로 계획기를 최적화 하기위해 경과시간, 진행방향각 오차, 위치각 오차를 목적 함수로 설계하고 MQEA를 적용하였다. 컴퓨터 시뮬레이션과 실제 하드웨어 로봇을 이용한 실험은 제안하는 PSSA가 사용자의 선호도를 적절하게 반영하였음을 입증하였다.
