協同運算研究(Ι)-多單體基因演算法

Tunghai University Institutional Repository > 工學院 > 工業工程與經營資訊學系所 > 碩博士論文 > Item 310901/3965

Please use this identifier to cite or link to this item: http://140.128.103.80:8080/handle/310901/3965

Title:	協同運算研究(Ι)-多單體基因演算法
Other Titles:	Study of Cooperative Computing Methodology(Ι) — Multi-Simplexes Genetic Algorithms
Authors:	李漢祥 Lee, Han-Hsiang
Contributors:	曾宗瑤;張炳騰 Tseng, Tsueng-Yao;Chang, Ping-Teng 東海大學工業工程與經營資訊學系
Keywords:	協同搜尋;基因演算法;單體法 Cooperative Search;Genetic Algorithm;Simplex Method
Date:	2002
Issue Date:	2011-05-19T05:14:21Z (UTC)
Abstract:	在求解最佳化的過程中，精確度(Precision)、收斂率(Convergence Rate)以及計算時間(Computing Time)這三者的結果關係著演算法搜尋能力的好壞，一旦遇到高維度且複雜度高的問題時，不好的演算法便會使的精確度降低、收斂率及計算時間增加，如何解決這三大存在已久的問題便是本研究的重點所在。因此，本研究認為要使得搜尋的效率更高，就應導入協同搜尋(Cooperative Search)的概念。本研究認為在搜尋的過程中應強化多群體(Multi-team)的關連性，建立群體間與群體內部資訊的溝通、傳遞及協調機制，使群體間能記憶彼此的資訊並藉由持續的交換及激化(stimulate)後，快速找到最佳點的資訊，並讓群體間在適當的時機進行分合動作，以快速包圍最佳點的位置，以達快速收斂及有效搜尋的目的。為實現協同式搜尋(Cooperative Search)的概念，本研究藉由基因演算法(GA)及單體法(Simplex Method)的合併，來作為其演算法之一：混合式多單體GA協同搜尋法(HMSGA-CS)。許多文獻強調基因演算法(GA)的優點是在對於整個解空間的搜尋能力(Exploration)極佳並將它廣泛的使用在求解最佳化的問題上，但基因演算法(GA)欠缺的是探勘(Exploitation)的能力，因此便將有探勘能力的局部搜尋法(Local Search)與之混合。本研究除了利用此優點外，並導入協同搜尋的概念，以使搜尋效率更佳。在實驗驗證方面，本研究隨機選取數個範例來驗證成效。實現結果顯示HMSGA-CS確實能在所有的範例中有效且快速的找到真正的最佳解。實驗結果也將與傳統的基因演算法及Yen-Lee(Y-L)所提出的混合法比較。HMSGA-CS在所有的範例中測試結果顯著的優於其它的方法。 In the process of solution optimization, precision, convergence rate and computing time are crucial to the ability of a search methodology. Once coming across a problem with high dimensions and complexity, poor algorithms will debase the precision and convergence rate or boost up the computing time. This paper aims at these three long-existing problems. Therefore, to improve efficiency, implementing a concept of cooperative search is significant. It is also vital to enhancing the contact among multi-teams and building up the inner communication policy between teams. In this way, individuals may catch information from each other, and through exchanging and stimulating, can hit upon the allied information of the optimal solution. All these allow the multi-teams to locate the optimal solution in a most efficient and convergent way. This paper also combines genetic algorithm (GA), and simplex method as one of the algorithms for the realization of the concept of cooperative search, called hybrid multi-simplexes GA cooperative search(HMSGA-CS). Many papers have emphasized that genetic algorithms have good exploration at searching all solution space and therefore GA has been extensively applied in the area of the optimal solution searching. Nevertheless, “exploitation” is what GA lacks. Therefore, we hybridized GA with a local search that has the ability of exploitation. Above and beyond, Cooperative Search is also adopted to increase the searching competence. To demonstrate the statement above, this paper adopts random-sampling test for 15 functions. The consequence verifies that HMSGA-CS essentially discovers the supreme solution in each example. In addition, we also compared with traditional genetic algorithm and Yen-Lee’s (Y-L) hybrid methods, it shows that HMSGA-CS evidently reveals its priority in real implementations.
Appears in Collections:	[工業工程與經營資訊學系所] 碩博士論文

Files in This Item:

File	Size	Format
090THU00030003-001.pdf	2836Kb	Adobe PDF	906	View/Open

Loading...