應用遺傳演算法新的效率編碼模式解決資源/生產分配問題; New Efficient Encoding Method of Genetic Algorithms for Resource/Production Allocation Problems

NCU Institutional Repository > 管理學院 > 資訊管理研究所 > 博碩士論文 > Item 987654321/12822

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/12822

題名:	應用遺傳演算法新的效率編碼模式解決資源/生產分配問題;New Efficient Encoding Method of Genetic Algorithms for Resource/Production Allocation Problems
作者:	張應華;Ying-Hua Chang
貢獻者:	資訊管理研究所
關鍵詞:	資源分配問題;生產分配問題;組合編碼法;動態規劃;路徑編碼法;遺傳演算法;Production Allocation Problems;Genetic Algorithms;Combination Encoding;Path Encoding;Generalized Resource Allocation Problems;Dynamic Programming
日期:	2003-06-15
上傳時間:	2009-09-22 15:15:02 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	本研究提出遺傳演算法(genetic algorithms)新的效率編碼模式來解決概化性資源分配問題(generalized resource allocation problems)。首先，我們提出一遺傳演算法的效率組合編碼法(combination encoding method)，以解決簡單資源分配問題，其中資源分配問題主要是有關於如何分派有限資源(resources)給各個活動(activities)，以使這些活動在得到資源後能夠獲取最大的報酬，而此效率組合編碼法由於可將一個限制式編入染色體中，所以可以縮小問題的解答搜尋空間，以提升遺傳演算法的效能。且當活動的個數漸漸增加時，其只需要增加一些演化代數即可得到足夠好的解答，而最普遍、通用的懲罰式編碼法(penalty encoding method)，在當活動的個數漸漸增加時，則需要比較多的演化代數，以求得相同的解答。同時，為了使遺傳演算法能夠正常的進行演化，本研究亦提出與效率組合編碼法相對應的交配(crossover)運算和突變(mutation)運算，並利用數學證明效率組合編碼法確實可以縮小簡單資源分配問題的解答搜尋空間，並利用許多不同大小實例來評估效率組合編碼法，實驗結果顯示新的染色體編碼模式可以提升遺傳演算法的演化效能，由此可見縮小解答搜尋空間確實可以減少遺傳演算法的演化代數。由於全球經濟的快速發展，在整體競爭環境下，有效率的協調各部門的生產計劃漸漸增加其重要性，對一個跨國公司而言，如何有效地管理其分散式生產工廠是一項重要的挑戰，且經常成為一策略性的議題。於是，許多跨國公司在其整體運作上皆發展出更加複雜、昂貴的生產規劃系統，這些規劃系統主要是根據工廠的生產產能限制和各市場的需求，來分派各工廠生產足夠產品的數量，以滿足各市場的需求，使得其總生產成本最小化。所以，本研究將舉例說明如何利用有效率的染色體編碼模式和適合的演化運算，能夠成功地應用在遺傳演算法上有效的減少解答搜尋空間，以求解生產分配問題(production allocation problems)，並獲取好的效能。因此，本研究提出另一新的染色體編碼方式，稱為路徑編碼法(path-encoding method)，其將動態規劃(dynamic programming)決策路徑擁有上下限的概念應用於遺傳演算法的染色體編碼上，縮小解答搜尋範圍，並結合遺傳演算法的隱含平行處理特性來演化，藉以改善動態規劃在遇到複雜的NP問題時無法保證在多項式時間內找到滿意解。亦即新的路徑編碼法可將生產分配問題的兩個條件限制式編入染色體中，以提升遺傳演算法的效能，而為了讓整個演化過程能夠正確的運行，本研究亦提出了特殊的路徑交配和突變運算，並利用屬於NP複雜的生產分配問題來評估此新方法的效能，其同時比較了四種方法---路徑編碼法、組合編碼法、懲罰式編碼法和整數規劃法(integer programming)，而實驗結果顯示本研究所提之路徑編碼法效果最好，在較少的演化代數裏即可求得滿意解，組合編碼法其次，因此法只將一個限制條件編入染色體中，所以仍需要一些額外的演化代數來處理非法染色體，懲罰式編碼法第三，其需要花費更多的演化代數來導引遺傳演算法搜尋到合法解的所在區域，再進而求得好的解答，但所找到的結果較差於由前兩種編碼法所求得之解，而整數規劃法充其量只能得到可行解，無法找出與遺傳演算法三種編碼方式相同的結果，由此可知本研究所提之路徑編碼法確實能夠有效的縮小染色體搜尋空間以提升遺傳演算法的演化效能。 This study proposes some efficient encoding evolutionary algorithms to solve the generalized resource allocation problem. First of all, we propose a novel efficient means of encoding genetic algorithms to solve the simple resource allocation problem. The problem relates to allocating limited resources across activities to maximize the return from them. The first proposed encoding method, combination encoding, can reduce the searching space of solutions because of encoding one constraint in the chromosome and thus exhibits higher performance. It need only involve a few more generations to yield sufficiently good solutions when the number of activities is increased. The penalty encoding method, however, requires many more generations to yield the same solutions. Additionally, a new simultaneous crossover and mutation operation is proposed to enable the new method of encoding chromosomes run correctly following standard genetic algorithm procedures. In addition to the mathematical certification, the performance of this approach is evaluated on some test problems of various variable sizes. Solutions obtained by this approach are always efficient. Due to the rapid worldwide economic development, global competition is increasing the importance of effectively coordinating production planning among the subsidiaries of multinationals. In a competitive global environment, managing the distributed production plants of an international company is a significant challenge and frequently becomes a strategic issue. Hence, numerous international companies have developed more complex and expansive planning systems for their global operations. These plans involve varying the location of manufacturing according to market demand, and aim to minimize costs for a multinational company subject to capacity constraints and market requirements. This paper also demonstrates the feasibility of successfully applying genetic algorithms to the production allocation problem, but requires the use of an efficient encoding method and adaptive operation mode. The new efficient encoding method can significantly reduce the search space of solutions and obtain a high performance. Therefore, this study presents another new approach, called the path-encoding method, which encodes two constraints into the chromosome and adapts the idea of dynamic programming for genetic algorithms to enhance the performance of evolutionary process. To allow correct running of the efficient encoding method through evolution procedures, a specialized path crossover and mutation operation is simultaneously proposed herein. The NP-hard production allocation problem is used to evaluate the effectiveness of the approach. This experiment compares the proposed approach to the combination-encoding method, the penalty-encoding method and integer programming. The computed results show that the proposed approach is always feasible and outperforms the others because it narrows the solution search space effectively.
顯示於類別:	[資訊管理研究所] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....