以訊息理論引導之遺傳演算法

Information Guided Evolutionary Algorithm

葉真瑋(Chen-Wei Yeh)

指導教授 ： 鄭西顯

國立清華大學/工學院/化學工程學系/博士(2006年)

摘要

遺傳演算法（evolution algorithm）已被廣泛地運用在處理最適化問題（optimization），應用的領域涵蓋：數學、工程、生化(bio-chemistry)、分子模擬(molecular simulation)、…等各式問題。尤其，在處理高維度的全域最適化（global optimization）問題上，遺傳演算法相較於傳統以梯度運算為基礎的數值方法（gradient based），更能避免搜尋過程中，侷限於區域解（local optima）、方程式微分及猜測初始值（initial value）的困擾。多族群（multi-population）遺傳演算法的發展，更進一步地提高了遺傳演算法在搜索解空間的過程中，搜尋到全域最適解（global optima）的機率。然而，無論是傳統的單族群（single population）遺傳演算法或多族群的遺傳演算法，在處理全域最適化問題時，仍然有機會面臨可能的早熟問題（probable premature convergence problem）。

本文的目的在於處理遺傳演算法演算過程中，面臨可能的早熟問題時，經由在演算過程中加入可用於偵測早熟的機制，在發現可能的早熟狀況時，進一步透過訊息理論(information theory)，計算搜尋過程中，已搜尋過的資料點在解空間（solution space）中分布情形，並提供一個引導的機制，以有效地處理遺傳演算法在演算過程中，可能面臨的早熟問題。

文中並嘗試處理幾個經常用於測試演算法效率上，高維度的測試問題，並模擬處理多成份蒸餾塔之成份參數預測、線性系統識別(linear system identification)及代謝網路（metabolic network）之最適化問題，用以討論經由訊息理論導引遺傳演算法引導突變(mutation)操作的可行性。

關鍵字

遺傳演算法 ； 訊息理論 ； 訊息熵 ； 直交設計 ； 早熟

並列摘要

Evolutionary algorithm (EA) has become popular in global optimization with applications widely used in many industrial areas. However, there exists probable premature convergence problem when rugged contour situation is encountered. As to the original genetic algorithm (GA), no matter single population or multi-population cases, the ways to prevent the problem of probable premature convergence are to implement various selection methods, penalty functions and mutation approaches. This work proposes a novel approach to perform very efficient mutation to prevent from premature convergence by introducing the concept of information theory. Information guided mutation is implemented to several variables, which are selected based on the information entropy derived in this work. The areas of search are also determined on the basis of the information amount obtained from previous searches.

Several benchmark problems are solved to show the superiority of this information guided EA. An industrial scale problem is also presented in this work.

並列關鍵字

Evolutionary Algorithm ； Information Theory ； Information Entropy ； Orthogonal Design ； Premature

參考文獻

1. Adeli, H. and Cheng, N. T. (1994), Augmented lagrangian genetic algorithm for structural optimization, Journal of Aerospace Engineering, 7, 104-118.

2. Alavi, S. and Thompson, D. L. (2004), A molecular-dynamics study of structural and physical properties of nitromethane nanoparticles, Journal of Chemical Physics, 120, 10231-10239.

4. Barbosa, H. J. C., Lemonge A. C. C. (2003), A new adaptive penalty scheme for genetic algorithms , Information Sciences, 136, 215..

6. Bursulaya, B. D., Totrov, M., Abagyan, R. and Brooks, C. L. (2003), Comparative study of several algorithms for flexible ligand docking, Journal of Computer-Aided Molecular Design, 17, 755-763.

7. Chen, J. H., Wong, S. H., and Jang, S. S. (1998), Product and process development using artificial neural-network model and information analysis, AIChE Journal, 44, 876-887.