Due to their comprehensive and vigorous search capabilities, Evolutionary Algorithms (EAs) have been widely used in a diversity of applications with great success. The majority of research up to now has focused on stationary type environments, in which the evaluation function and problem constraints are fixed over the period of evolution. As a matter of course, most applications of EAs deal with static optimization problems that can be solved off-line processing. However, many real-world problems involve time-varying objectives that should be dynamically optimized. Therefore, there has been a growing interest in time dependent optimization for many real-world applications.
The dynamic optimization problem demands that EAs should generate an acceptable solution within an allowable time period. To overcome this difficulty, this thesis proposes an optimization problem solving system characterized by hierarchically distributed evolutionary algorithm (HDEA). HDEA consists of a set of subpoplations and a master evolution system. The master evolution system controls the optimization processing of the subpopulations, while subpopulations evolve independently to find optimal solution using parallel computing system. This enables us to utilize fast local search operators while maintaining sufficient population diversity. The algorithm can be easily implemented using a set of general-purpose computers connected by a network. This extends the practicality of EAs to real-time problems.
The efficiency and usefulness of HDEA are analyzed using a set of benchmark problems. Through the comparison between HDEA and traditional EAs, we verify that HDEA is a particularly adaptive tool for optimizing a lot of diversified class of functions. We also apply the algorithm to optimize a nonstationary time series prediction model.
진화연산알고리즘은 광범위한 범주의 문제에 대한 적용능력과 우수한 성능으로 인해서 많은 분야에서 점차 그 중요성이 부각되어 왔다. 진화연산에 관한 대부분의 기존연구는 정적 적합도 함수를 가지는 문제의 해결에 집중되어 왔다. 그러나, 정적 최적화 문제를 해결하기 위해서 개발된 기존의 진화 연산 알고리즘은 적합도 함수의 모양 변화 및 해의 탐색 시간 제약 등 동적 환경에서만 발생하는 문제점들을 해결하는데 많은 제약점을 가진다. 실제 응용 분야에서 많은 요소들이 시간에 따라 변하는 특성을 가지고 있기때문에 동적 환경에서 진화연산을 이용한 최적화 문제 해결 기법을 개발하려는 시도가 지난 10여 년간에 걸쳐 점진적으로 이루어지고 있다.
동적 환경에서의 최적화 문제 해결 기법은 정해진 시간내에 적합한 해를 제공해야 하므로 일반적으로 탐색 시간의 제약을 받는다. 이러한 어려움을 해결하기 위해서 본 학위논문에서는 탐색 결과의 개선이 주기적으로 요구되는 동적 환경에서의 최적화 문제를 해결하는데 필요한 특성들을 고찰하고, 그 분석 결과를 바탕으로 계층적 분산 진화 알고리즘을 제안하여 동적 최적화 문제에 적용하고자 한다. 계층적 분산 진화 알고리즘은 거시적 진화 시스템과 미시적 진화 시스템으로 구성된다. 거시적 진화 시스템은 개체군의 발전과 멸종의 과정을 모사하여 개체군간의 다양성을 유지하는 역할을 담당한다. 반면, 미시적 진화 시스템은 하나의 개체군 내에서의 각 개체의 진화과정을 모사하여 경쟁을 통한 최적화 과정을 수행한다. 제안된 알고리즘은 진화 과정을 두 부분으로 구분함으로서 진화연산기법의 적용에서 문제가 되는 탐험과 활용의 균형을 유지한다. 또한, 제안된 알고리즘을 근거리망(LAN)으로 연결된 다수의 범용 컴퓨터를 이용해서 병렬처리하도록 구현, 처리 속도를 향상시켜서 실제적인 동적 최적화 문제를 해결에 적용하였다.
제안된 방법의 특성은 논문에 정리된 수치최적화 문제들을 통해서 분석되고, 기존의 방법과을 비교를 통해서 그 우수성을 입증하였다. 또한, 성능 평가에 많은 시간이 소요되는 동적 시계열 예측 모델의 최적화에 적용함으로서 제안된 방법이 지속적인 최적화를 요구하는 실제 응용 분야에서 활용될 수 있음을 보였다. 따라서, 본 논문에서 제안된 계층적 분산 진화 알고리즘은 진화 연산의 적용 분야를 다양한 동적 환경으로 확장시키는데 이바지할 수 있을것이다.
