Recently, there have been much research of robust and powerful optimization methods for solving large and difficult combinatorial problems. As a result, several effective stochastic search algorithms have shown up in the literature, for example, simulated annealing, tabu search, and evolutionary algorithms.
Evolutionary algorithms inspired by the natural process of evolution are attracting attentions for dealing with global optimization. The main feature of evolutionary algorithms is the maintenance of a set of solutions that are searched in parallel and the adoption of perturbation mechanism analogous to biological operators. Accordingly, they can be easy parallelizable compared to other methods. There have been a lot of empirical evidences indicating that evolutionary algorithms are good optimization methods, resulting in rapid enlargement of application areas.
However, most of the applications have been performed without considering how effective evolutionary algorithms are in solving the problems compared to other search algorithms.
This thesis consists of two parts. In the first part, we investigate the features of evolutionary algorithms and examine the efficacy of them by carefully controlled empirical comparisons with simulated annealing. As problem size and ruggedness of the landscape increase, the contribution of crossover to evolutionary search becomes less useful and the evolutionary search becomes less efficient than simulated annealing.
The second part of this thesis deals with two possible hybridization techniques to enhance performance of canonical evolutionary algorithms. The first hybrid incorporates independent sophisticated heuristic local search to evolutionary algorithms so as to overcome problems of evolutionary algorithms identified in the first part of this thesis. Experimental results demonstrate that the hybrid is capable of clearly outperforming canonical evolutionary algorithms and is better than simulated annealing for some classes of problems. The second hybrid approach adopts problem-specific techniques and knowledges for better performance, sacrificing robustness. We present a new hybrid evolutionary algorithm tailored to sequencing problems where the principle of branch-and-bound search is employed and apply to one of the hardest sequencing problems, job-shop scheduling problems. It is observed that the hybrid outperforms some previous evolutionary approaches and that genetic operators combined with domain-specific techniques and knowledge are very powerful. The hybrid also tends to attain better solution quality than simulated annealing when job-shop scheduling problems are rather structured.
최근에 조합 최적화 문제를 해결하기 위한 강건하고 효과적인 최적화 기법에 대한 많은 연구가 있어왔다. 그 결과로 근사 담금질, 금기 탐색, 진화 연산 등과 같은 효과적인 확률적인 탐색 알고리즘이 제시되었다.
자연계의 진화 과정을 모방한 진화 연산은 전역적 최적화를 위한 알고리즘으로 많은 관심을 끌고 있다. 진화 연산의 주요한 특징은 여러 해를 동시에 사용하며, 생물계의 연산자와 유사한 연산자를 채택하고 있다는 것이다. 또한 진화 연산은 다른 방법에 비해 병렬화가 용이하다. 이러한 진화 연산이 효과적인 최적화 방법임을 보여주는 많은 실험적 응용 사례가 제시되어 왔으며, 최근 진화 연산의 응용 분야가 확장되고 있다. 그러나, 이러한 대부분의 진화 연산의 응용은, 다른 최적화 문제와 비교하여 그 문제를 해결하기 위한 진화 연산의 상대적인 성능에 대한 검정없이 수행되어왔다. 따라서 진화 연산의 체계적인 성능 분석이 필요하다.
본 논문은 두 부분으로 구성되어 있다. 첫 부분에서, 진화 연산의 특징을 조사하고 다른 효과적인 탐색 알고리즘인, 근사 담금질과의 실험적 비교를 통하여 진화 연산의 성능을 검사한다. 진화 연산의 주요한 특징인 교체 연산자의 효과뿐만 아니라 진화 연산의 성능은, 문제가 커질수록 그리고 문제의 국소점이 많아질수록, 상대적으로 근사 담금질에 비해 점점 줄어들게 된다.
두 번째 부분에서는 진화 연산의 성능을 향상하기 위한 두 가지 형태의 하이브리드 기법을 다룬다. 첫 번째의 하이브리드 기법은 논문의 첫 부분에서 확인한 진화 연산의 문제점을 극복하기 위하여 국소적 탐색 기법을 진화 연산에 도입하는 형태이다. 실험적 분석에서, 제안한 하이브리드 진화 연산 기법이 기존의 진화 연산보다 좋은 성능을 보이며, 특정한 형태의 문제에서는 근사 담금질보다 좋은 성능을 보인다. 또 다른 형태의 하이브리드 기법으로서, 진화 연산의 성능을 향상하기 위하여 해결하고자 하는 최적화 문제만의 독특한 정보와 방법 등을 이용한다. 가장 어려운 최적화 문제중의 하나인 스케쥴링 문제를 위한 새로운 형태의 하이브리드 진화 연산 기법을 제시한다. 제시한 하이브리드 진화 연산은 기존의 진화 연산을 이용한 스케쥴링보다 우수한 성능을 보이며, 또한 특정한 클래스의 스케쥴링에서는 근사 담금질보다 좋은 성능을 보인다.
