This thesis proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, the evaluation function, and the population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator that drives the individuals toward better solutions. The termination condition of QEA is designed by defining a new measure on the convergence of Q-bit individuals. To analyze the characteristics of QEA, the theoretical analysis of the QEA algorithm as well as the effects of changing parameters of QEA are examined. In particular, some issues of QEA such as the analysis of changing the initial values of Q-bits, a novel variation operator $H_\epsilon$ gate, and a two-phase QEA (TPQEA) scheme are addressed to improve the performance of QEA. To demonstrate the effectiveness and applicability of QEA, experiments are carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small number of population, without premature convergence as compared to the conventional genetic algorithms. Moreover, through the experiments on numerical optimization problems, the superior performance of QEA is also verified. These results show that QEA can be applied to a class of numerical as well as combinatorial optimization problems.
본 논문에서는 새로운 진화 알고리즘인 양자 개념을 도입한 진화 알고리즘 QEA를 제안한다. QEA는 양자 비트나 상태의 중첩과 같은 양자 전산의 개념과 원리에 기반을 둔다. QEA는 다른 진화 알고리즘과 유사하게 개체의 표현법, 평가 함수, 개체들의 변화 등에 의해 특징지워진다. 하지만, QEA는 이진 표현법이나 실수 표현법 또는 기호 표현법 등이 아닌 확률적 표현법인 새로운 Q-비트 표현법을 정의하여 사용한다. Q-비트는 QEA에서의 정보의 최소 단위로 정의되며, Q-비트들로 이루어진 스트링은 Q-비트 개체로 정의된다. 이와 같이 확률적으로 존재하는 Q-비트 개체는 많은 이진 해들을 각기 다른 확률로 동시에 포함할 수 있게 된다. 이때 Q-비트 개체가 더 나은 해들을 높은 확률로 포함하도록 만들 수 있는 변형 연산자를 Q-게이트로 정의하고, 기본 Q-게이트로는 회전 게이트를 사용한다. 또한, Q-비트 수렴도를 정의함으로써 한 세대의 모든 Q-비트 개체들의 평균 Q-비트 수렴도를 이용하여 QEA의 명확한 종료 조건을 제시한다.
제안된 QEA 알고리즘의 특징을 파악하기 위해 간단한 문제에 대한 실험적, 이론적 분석을 수행한다. 특히, 이론적인 분석의 결과는 QEA 알고리즘이 진화 알고리즘에서 가장 중요하게 여겨지는 전역 검색과 지역 검색의 균형을 이루는데 적합한 구조를 가지고 있다는 사실을 입증한다. 또한, QEA의 파라메터들의 변화에 따른 영향을 분석함으로써 사용자에게 파라메터 설정에 대한 유용한 지침을 마련한다.
QEA의 성능을 더욱 향상시키기 위해 기본 알고리즘 구조의 확장에 대한 연구 주제를 추가적으로 다룬다. Q-비트의 초기 값 변화에 대한 영향을 분석하고, 초기 값에 대한 분석 결과를 바탕으로 2 단계 QEA 구조를 제안한다. 또한, 많은 국부 최적해를 갖는 수치 최적화 문제에 적합한 변형 연산자인 $H_\epsilon$ 게이트를 제안한다.
QEA의 효율성과 적용성을 검증하기 위해 조합 최적화의 대표적 문제인 주머니 문제와 다양한 수치 최적화 문제들에 대한 실험을 수행한다. 주머니 문제의 실험 결과는 QEA 알고리즘이 기존의 유전자 알고리즘에 비해 적은 수의 개체만으로도 조기 수렴 없이 우수한 성능을 보인다는 사실을 입증하였고, 수치 최적화 문제에 대한 실험 결과에서도 QEA 알고리즘의 우수한 성능이 입증되었다. 이와 같은 실험 결과는 QEA 알고리즘이 조합 최적화 뿐만 아니라 수치 최적화 문제에도 적용 가능한 진화 알고리즘이라는 사실을 입증해주고 있다.
