Analysis of punctuated equilibria in simple genetic algorithms = 단순 유전 알고리즘에서의 단속평형에 대한 분석

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 be...
Advisors
Yoon, Hyun-Sooresearcher윤현수researcher
Publisher
한국과학기술원
Issue Date
2001
Identifier
165661/325007 / 000945246
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학전공, 2001.2, [ xi, 82 p. ]

Keywords

genetic algorithms; punctuated equilibria; 단속 평형; 유전 알고리즘

URI
http://hdl.handle.net/10203/33178
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=165661&flag=t
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 216
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0