演化式計算下篇：基因演算法以及三種應用實例

Evolutionary Computation Part 2: Genetic Algorithms and Their Three Applications

林豐澤(Feng-Tse Lin)

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

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

摘要

演化式計算是一個通用名詞，泛指以達爾文進化論“者生存，不適者淘汰”為基礎，來模擬自然界演化過程所建立的計算模式，這些計算模式又被稱為演化式演算法。經過將近三十餘年來的努力，演化式計算已經發展成為許多不同的研究領域與不同的研究團體，然而最早出現也是最主要的演化式演算法是演化式規劃、演化策略、與基因演算法。我們分成上下兩篇論文來介紹演化式演算法，做為演化式計算入門者的介紹文章。上篇不僅探討這三種主要模式的理論架構，並且分析與比較三者間的主要差異，下篇是介紹基因演算法的設計方法與步驟以及它的三種典型應用實例。我們針對基因演算法的設計方法分成下列四部份來討論：(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 not only the discussions of theoretical frameworks, but also the analysis and the comparison of these three major models. The second part introduces the design and the implementation of Genetic Algorithms as well as their three typical types of application. In this paper, we discuss the implementation of Genetic Algorithms in the following four parts: (1) gene coding, (2) fitness function, (3) selection mechanism, and (4) crossover and mutation mechanism. The three typical applications are the function maximization, breaking Vigenère cipher, and the optimal fuzzy profit problem. For each problem, we give its background, problem definition, detailed design method, and empirical results to support that Genetic Algorithms are a robust and an efficient optimization approach.

並列關鍵字

Evolutionary computation ； Genetic Algorithms ； Function maximization problem ； Vigenère cipher ； Optimal fuzzy profit problem