類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究; Analogous Ant Colony System Algorithm for Concave Cost Minimum Cost Network Flow Problems

NCU Institutional Repository > 工學院 > 土木工程研究所 > 博碩士論文 > Item 987654321/1048

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/1048

题名:	類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究;Analogous Ant Colony System Algorithm for Concave Cost Minimum Cost Network Flow Problems
作者:	王政嵐;Cheng-Lan Wang
贡献者:	土木工程研究所
关键词:	全域搜尋;鄰近搜尋;凹形節線成本;類螞蟻族群演算法;最小成本轉運問題;minimum cost transshipment problem;analogous ant colony system algorithm;global search;concave arc cost;neighborhood search
日期:	2005-06-18
上传时间:	2009-09-18 17:18:52 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	傳統上，最小成本轉運問題的運送成本常以線性方式來定義，藉以簡化問題的複雜度。然而，在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線呈現凹形。因此，近期有學者以新近鄰近搜尋法，如門檻值接受法與大洪水法，求解含凹形節線成本之特殊最小成本網路流動問題，以達到擴大搜尋範圍的效用，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探循全域，則不得而知。另外，有鑑於以往許多研究凹形成本運送問題的文獻，大都侷限於特殊的網路型態。因此近有學者利用遺傳演算法發展全域搜尋法以求解含凹形節線成本一般性最小成本轉運問題。螞蟻族群演算法為一新近風行之巨集啟發解法，其利用分散式搜尋之觀念進行求解，並在許多問題上求得頗佳的結果，在部分的應用例中發現其求解效率較GA為佳。由於以往未發現有文獻利用螞蟻族群演算法求解凹形成本網路流動問題，因此本研究針對含凹形節線成本之最小成本轉運問題特性，以螞蟻族群演算法之搜尋觀念為基礎，並結合文獻上求解含凹形節線成本之最小成本網路流動問題之遺傳演算法、門檻值接受法及凹形成本網路啟發解法之特點，發展一類螞蟻族群演算法，以有效得求解含凹形節線成本之最小成本網路流動問題。為評估此演算法的求解績效，本研究亦參考門檻值接受法、大洪水法與遺傳演算法，進行測試比較分析，以提供實務界求解此類實際的網路運送問題之參考。在求解的方法上，本研究首先設計數個初始解法，並在可行解產生的過程中，發展數種狀態轉移法則產生多條路徑，並透過流量推擠法產生可行伸展樹。在費洛蒙的更新法則上，本研究結合區域與全域費洛蒙更新方式，並引進門檻值接受法部分之求解機制，發展數種與以往不同之費洛蒙更新方式。此外，本研究引進遺傳演算法之菁英策略，以提升演算績效。為測試本研究演算法在不同規模及參數的網路問題的求解績效，本研究設計一隨機網路產生器，產生大量的隨機網路，並以C++語言撰寫所有相關的電腦程式，在個人電腦上測試分析，以評估本研究類螞蟻族群演算法之績效。 Traditionally, the minimum cost transshipment problems are formulated as a linear cost problem, in order to reduce problem complexity. In reality, the unit cost decreases as the amount transported increases, resulting in a concave cost function. Recently, a research started to use advanced neighborhood search algorithms, such as threshold accepting (TA) and great deluge algorithm (GDA), to solve concave cost network problems in order to find better solutions than traditional heuristics. However, such neighborhood search algorithms easily encounter degeneracy problems, resulting in decreased solution efficiency. It is wondered if such algorithms can explore the whole domain area to find better solutions. In addition, most past research on solving concave cost network problems is confined to specific network problems. Therefore, a global search algorithm, based on genetic algorithm (GA), was recently developed to solve minimum concave cost transshipment problems. Ant colony system algorithm (ACS) is a new popular heuristic which searches feasible solutions by using spread exploration. In some cases, its efficiency was found to be better than GA. Since there has not yet ACS developed to slove minimum cost transshipment problems with concave arc costs, in this research we developed an analogus ant colony system algorithm (AACS) to solve minimum cost transshipment problems with concave arc costs, based on ACS, incorporating the merits of GA, TA and concave cost network heuristics, that were applied for solving minimum cost transshipment problem with concave arc costs in literature. In order to evaluate this AACS, we referred to TA, GDA and GA to perform tests and comparison. The results can hopefully be useful reference for practitioners to solve their real problems. The preliminary idea of our algorithm development was as follows: We first design several initial solution methods. In the feasible solution generation process, we developed several state transition rules to generate several paths, which did then be modified as feasible spanning trees by using a flow argumentation algorithm. For updating arc pheromones, we combined local and global pheromone updating rules, incorporating the TA search strategy, to develop several new pheromone updating rules. Besides, we referred to the elite strategy typically used in GA to speed up computations. In order to evaluate AACS for different problem scales and parameters, we designed a randomized network generator to produce many test problems. Finally, the tests were performed on personal computers with the assistance of C++ computer language for coding all necessary programs.
显示于类别:	[土木工程研究所] 博碩士論文

文件中的档案:

档案	大小	格式	浏览次数

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....