演化式計算上篇：演化式演算法的三種理論模式

Evolutionary Computation Part 1: Three Theoretic Models of Evolutionary Algorithms

林豐澤(Feng-Tse Lin)

《智慧科技與應用統計學報》 3卷1期 (2005/06) Pp. 1-28

https://doi.org/10.29807/JTITAS.200506.0001

摘要

演化式計算是一個通用名詞，泛指以達爾文進化論“適者生存，不適者淘汰”為基礎，來模擬自然界演化過程所建立的計算模式，這些計算模式又被稱為演化式演算法。經過將近三十餘年來的努力，演化式計算已經發展成為許多不同的研究領域與不同的研究團體，然而最早出現也是最主要的演化式演算法是演化式規劃、演化策略、與基因演算法。我們分成上下兩篇論文來介紹演化式演算法，做為演化式計算入門者的介紹文章。上篇是探討這三種主要模式的理論架構，下篇是介紹最著名的基因演算法以及三種典型的應用實例。本文先就這三種主要模式的理論基礎、行為準則、個體表示法、以及群體組織做詳細的說明及討論，然後去比較與分析三者間的主要差異。這些差異乃在於所使用的：(1)個體的表示法，(2)挑選機制與適應度評估，(3)突變運算子，以及(4)重組運算子的不同。最後我們說明基因演算法是三者中最著名、應用最多的一種穩健有效率的最佳化方法。

關鍵字

演化式計算 ； 演化式演算法 ； 演化式規劃 ； 演化策略 ； 基因演算法

並列摘要

Evolutionary computation is a general term for a kind of computational model, which is based on Darwinian evolution's ”survival of the fittest” to simulate the natural evolution processes. These computational models are also called evolutionary algorithms. Over the past thirty years of endeavors, evolutionary computation has been developed into several different research fields and different research communities. Among of these, Evolutionary Programming, Evolution Strategy, and Genetic Algorithms, are the pioneers and the main streams of evolutionary algorithms. We would like to introduce evolutionary computation in two parts of papers as introductory articles for the beginners. The first part deals with theoretical frameworks of these three major models. The second part introduces the most famous Genetic Algorithms and their three typical types of applications. In this paper, first, we discuss the theoretical frameworks, behavior criteria, individual representation, and population structure of these three major models. Next we compare and analyze the main differences between them. The main differences are with respect to the components used in the model, including individual representation, selection mechanism, fitness evaluation, mutation, and recombination. Finally, we conclude that genetic algorithms are robust and efficient methods due to their popularity and have many wide applications.

並列關鍵字

Evolutionary computation ； Evolutionary algorithms ； Evolutionary Programming ； Evolution Strategy ； Genetic Algorithms