Parallel problem solving methods modeled from nature are introduced to solve these combinatorial optimization problems. Among these methods, genetic algorithms (GAs) are ones imitating Darwinian evolution. The GA deals with a population which is a set of individuals each of which corresponds to a point in the solution space. The goodness of an individual is measured by a fitness function and this can be visualized as a landscape on the solution space. In the fitness landscape, there can be a number of local optima which is surrounded by neighbor points with lower fitness. Like many heuristic algorithms, GAs have the problem of their population being trapped in a local optimum but, the population can escape from the local optimum thanks to phenomena called punctuated equilibria.
According to the paleontological studies, the progress of the evolution is not linear but intermittent: a long duration of metastable state followed by a sudden jump into the other stable state. This phenomenon is the punctuated equilibrium and is understood as a transition of an ecosystem from a local optimum into another in the neighborhood. The punctuated equilibria can be explained using mathematical theory of diffusion processes within the framework of neo-Darwinian theory which is the most widely accepted evolution model. The mathematical theory deals with a bistable landscape which has one local and one global optima. If a system starts from the local optimum, it remains there for an exponentially long time and, suddenly, transits into the global optimum. On the other hand, punctuated equilibria are also observed in computational ecosystems (CEs) which are simplified models of real ecosystems. The punctuated equilibria in CEs can also be explained using the mathematical theory of diffusion processes and it is suggested that the duration of metastable state is exponential in the population size, which is the number of individuals in the population, and the height of the barrier between the local and global optima.
For GAs, Vose tried to explain the punctuated equilibria observed in genetic searches by showing that the local optimum state is unstable unless it has globally maximal fitness. He made mention of the diffusion process but he did not consider such features as the duration of metastability. Recently, the similar phenomena to the punctuated equilibria were analyzed mathematically but, these fitness functions have no local optima. There was a study showing that the duration of metastability
is logarithmic when elitism is used. But the elitism is not useful when the fitness is multimodal.
This contradiction about the duration of metastability is the motivation of this thesis. In this thesis, the duration is shown to be exponential provided that there are local optima in fitness functions and the elitism is excluded. First, the dynamics of SGAs is analyzed and it is shown that the dynamics can be mathematically formalized as a diffusion process when the fitness function uses unitation codes. Although the functions of unitation represent only a small class of all possible ones,
they have been of considerable interest to GA researchers, since they are easy to analyze and understand. The analysis directly derives theoretical results that elucidate relations between the duration of metastability and GA parameters. And these theoretical results are corroborated by computer simulations. Simulation results are also obtained for other fitness functions such as Minimal Deceptive Problems and, functions using unsigned binary and Gray codes. Using these results,
it is suggested that the theoretical results can be applied under more general conditions.
자연계의 기법들을 모방하여 만든 병렬 문제해결 기법들은 이런 조합 최적화 문제에서 전역 최적치에 되도록 가까운 해답을 찾는 데에 많이 사용된다. 이런 기법 중에서도 유전 알고리즘은 다윈 이론을 모방하여 만들어졌다. 유전 알고리즘은 개체들의 집합인 하나의 개체군을 다루는데, 이때 각 개체는 해답공간에서의 한 점에 해당한다. 한 개체의 좋은 정도는 적응도 함수에 의해 측정되며 이 함수는 해답공간위에 정의된 지형도라고 볼 수 있다. 적응도 지형 위에는 상대적으로 낮은 적응도를 갖는 점들로 둘러싸인 지역 최적치가 여러 개 있을 수 있다. 다른 많은 휴리스틱 알고리즘처럼 유전 알고리즘도 개체군이 모두 하나의 지역 전역치의 영역에 갖히게 되는 문제가 있다. 하지만, 유전 알고리즘에서는 단속평형이라는 현상에 힘입어 이 지역 최적치로부터 탈출할 수 있다.
고생물에 대한 화석학 연구에 따르면, 진화는 선형적이라기 보다는 단속적인 모양으로 진행된다. 즉, 준평형상태가 오랫동안 유지되다가 갑자기 다른 평형상태로 전이되는 것이다. 이런 현상이 바로 단속평형이며 생태계가 하나의 지역 최적치에서 이웃하는 다른 지역 최적치로 전이하는 과정으로 이해된다. 확산과정에 대한 수학적 이론을 적용하면 신다윈주의 이론의 틀 안에서 이러한 단속평형을 이론적으로 설명할 수 있다. 신다윈주의는 현재 가장 널리 받아들여지고 있는 진화 모델이다. 이 확산과정에 대한 수학적 이론은 한 개의 지역 최적치와 한 개의 전역 최적치를 갖는 이중 안정 지형을 다룬다. 시스템이 지역 최적치에서 출발하면 거기에 지수 오더의 긴 시간동안 남아있다가 갑자기 전역 최적치로 옮겨간다. 한편, 단속평형은 실제 생태계를 단순화하여 만든 모델인 컴퓨터 생태계에서도 관찰된다. 컴퓨터 생태계에서의 단속평형 또한 확산과정의 수학적 이론을 적용해 설명할 수 있는데, 이 설명에 따르면 준평형상태의 지속시간은 개체군의 크기 즉, 개체들의 갯수와, 지역 최적치와 전역 최적치 사이에 있는 장벽의 높이의 지수 오더에 이른다.
유전 알고리즘에서도 단속평형이 관찰되는데, Vose 는 이를 설명하기 위해 지역 최적치는 그것이 전역 최적치가 아니라면 결국 안정한 상태가 아니라는 것을 보였다. Vose 는 확산과정에 대한 언급을 하긴 했지만 준평형상태의 지속시간에 대한 성질은 고려하지 않았다. 최근에는 단속평형과 비슷한 현상이 수학적으로 분석되기도 했는데 이것은 지역 최적치가 존재하지 않는 경우였다. 또한 엘리트주의가 적용되는 경우에 준평형상태의 지속시간이 개체군의 크기에 로그 오더라는 연구 결과가 있었다. 하지만 엘리트주의가 일반적으로 항상 좋은 결과를 가져오는 것은 아니다.
준평형상태의 지속시간에 대한 이러한 상반된 결과들은 본 논문의 동기가 된다. 본 논문에서는 단순 유전 알고리즘에서도 적응도 함수가 지역 최적치를 포함하고 있고 엘리트주의가 사용되지 않는 경우에는 준평형상태의 지속시간이 지수 오더에 이른다는 것을 보인다. 먼저, 적응도 함수가 단위화 코드를 사용하는 경우에 단순 유전 알고리즘의 동역학을 분석하고 그 동역학이 하나의 확산과정이라는 것을 수학적으로 보인다. 단위화 함수는 상당히 적은 부류의 함수를 포함하지만 분석 및 이해가 용이하기 때문에 유전 알고리즘 연구자들에게 많이 연구되어 왔다. 이러한 분석으로부터 준평형상태와 유전 알고리즘의 주요변수 사이의 지수적인 관계를 얻고, 이 이론적인 결과는 컴퓨터 시뮬레이션을 통해 확인된다. 또한, 최소 기만 문제와, 이진코드와 그레이 코드를 사용하는 함수에 대한 시뮬레이션 결과를 얻고, 이를 이용해, 앞에서 얻은 이론적 결과가 보다 더 일반화된 조건하에서 적용될 수도 있다는 것을 제안한다.
