This thesis deals with the search performance enhancement techniques in genetic algorithms (GAs). Evolutionary algorithms are computational optimization techniques that use simulated evolution. In control area, especially the genetic algorithm has been widely used. Although GAs are good at finding near global optimum quickly, they are poor in the fine tuning of solutions, which may cause `premature convergence'. This thesis is aimed to improve the search performance of GAs with elitist strategy by reducing premature convergence through hybridization or appropriate modification to the algorithms. In order to accomplish the goals, three new genetic algorithms and two new local search operators are proposed. The first method, the modified genetic algorithm (MGA) consists of a fitness modification scheme and adaptive mutation operator. The second method, the adaptive genetic algorithm (AGA) determines crossover and mutation probabilities by itself according to the fitness of a solution to be crossed or mutated. The schema theorem for AGA is derived. The third method, adaptive simulated annealing genetic algorithm (ASAGA) uses simulated annealing-like mutation operator. A novel way of generating a new solution by using a gaussian random number with time-varying variance is proposed and proved to be effective. The first local search operator makes use of neural networks. The second one named SLSO (simple local search operator) uses the difference between the most recent best fitness and a newly found best solution's fitness, which is computationally simpler than the first one and proved to be powerful. The test problems considered for the performance comparison include the traditional set of test functions, system identification, neural network controller for cart-pole system, evolutionary design of a multi-agents playing a simplified soccer and nonlinear constrained optimization problems. Nine hybrid genetic algorithms are constructed using the proposed algorithms and the operator. ASAGA shows the best performance and could find a new global optimum for a nonlinear constrained optimization problem. Computation time is reduced when the SLSO is used together.
본 논문은 유전 알고리즘의 탐색 성능 향상 기법을 다루고 있다. 진화 연산이란 생물학적 진화 과정에 근거를 둔 계산적 최적화 또는 탐색 기법으로서, 최근 많은 관심을 불러일으키고 있으며 여러 분야의 다양한 문제에 성공적으로 적용되고 있다. 특히 제어 분야에서는 그 중 유전 알고리즘이 주로 사용되어왔다. 유전 알고리즘은 탐색 공간에 대한 정보를 필요로 하지 않고 근사 전역 최적해를 빨리 찾는다는 장점이 있지만, 지역 탐색 능력이 부족하여 조기 집중 현상을 일으킬 수 있는 문제가 있다. 따라서, 본 논문에서는 조기 집중 현상 감소를 통해, 엘리트 전략을 사용하는 유전 알고리즘의 탐색 성능을 향상시키고자 하였다. 이를 위해 세 가지의 새로운 유전 알고리즘과 새로운 지역 탐색 연산자를 제시하였다. 첫 번째 알고리즘은 포화된 적합도 함수와 해 집단이 정체되면 돌연변이 확률이 커지게 되는 적응 돌연변이 연산자를 사용한 변형된 유전 알고리즘이다. 두 번째 알고리즘은 교차변이 확률과 돌연변이 확률이 해의 적합도의 함수로 결정되며 적응 돌연변이 연산자가 적용된 적응 유전 알고리즘이다. 적합도가 낮은 개체일수록 교차변이 및 돌연변이 연산자 적용 확률이 커지도록 하여 해 집단의 다양성을 확보하고자 하였으며 적응 유전 알고리즘을 위한 스키마 정리도 유도되었다. 앞의 두 방법이 해 집단의 다양성에 초점을 둔 방법이라면, 세 번째 방법인 적응 근사 담금질 유전 알고리즘은 또 하나의 최적화 기법인 근사 담금질을 돌연변이 연산자에 적용시켜 두 알고리즘의 장점을 살려 탐색 성능을 개선시키고자 하는 보다 적극적인 방법이다. 또한, 분산이 근사 담금질의 냉각 스케줄에 따라 변하는 정규 분포를 갖는 난수를 사용한 해 생성 기법을 제안하였다. 한편, 새로운 지역 탐색 연산자는 신경망의 입출력 맵핑 능력을 이용하는 것과 과거세대의 해와 새로 찾은 해의 차이를 이용한 것 두 가지가 제안되었으며, 계산량과 성능 면에서 후자가 뛰어난 것으로 밝혀진다. 이상의 알고리즘들 및 새로운 연산자는 전통적인 성능 평가 문제, 시스템 동정화 문제, 역진자를 제어하는 신경망 제어기 설계, 인공 생명 분야의 한 예인 축구하는 다개체 시스템의 전략 설계, 비선형 제한 최적화 문제들을 포함하는 성능 평가 문제들을 통하여 분석되었다. 또한, 제안된 알고리즘의 특징을 파악하고 좀 더 나은 성능을 갖는 알고리즘 개발을 위하여 아홉 가지의 하이브리드 알고리즘을 새로 구성하여 분석하였다. 모의 실험 결과 적응 근사 담금질 유전 알고리즘이 전체적으로 가장 뛰어난 성능을 보였으며 특히, 비선형 제한 최적화 문제에서는 진화 프로그래밍을 이용한 기법보다 뛰어난 결과를 보였으며 새로운 최적해도 찾아내었다. 지역 탐색 연산자를 사용할 경우 계산시간을 단축시킬 수 있으나 전역 수렴성에 영향을 미치는 수도 있다.
