以粒子群最佳化為基礎之混合式全域搜尋演算法於求解含凹形節線成本最小成本網路流動問題之研究; Particle Swarm Optimization-Based Hybrid Global Search Algorithms for Concave Cost Minimum Cost Network Flow Problems

NCUIR > Engineering College > Department of Civil Engineering > Research Project > Item 987654321/44823

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/44823

Title:	以粒子群最佳化為基礎之混合式全域搜尋演算法於求解含凹形節線成本最小成本網路流動問題之研究;Particle Swarm Optimization-Based Hybrid Global Search Algorithms for Concave Cost Minimum Cost Network Flow Problems
Authors:	顏上堯
Contributors:	土木工程學系
Keywords:	全域搜尋;區域搜尋;凹形節線成本;粒子群最佳化演算法;遺傳演算法;門檻值接受法;最小成本網路流動問題;土木水利工程類
Date:	2007-07-01
Issue Date:	2010-12-21 16:17:40 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	傳統上，最小成本網路流動問題的運送成本常以線性方式來定義，藉以簡化問題的複雜度。在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線為凹形。近期在求解含凹形節線成本之特殊最小成本網路流動問題上，有學者以新近鄰近搜尋法求解問題，達到較大範圍的搜尋方式，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探循全域，則不得而知。因此近期有學者發展類遺傳演算法與類螞蟻族群演算法以求解含凹形節線成本最小成本網路流動問題。另外，新近的粒子群最佳化演算法目前在各領域的問題求解上效果頗佳，甚至有發現較遺傳演算法為佳，但尚未發現有應用於含凹形節線成本最小成本網路流動問題，緣此，本研究擬針對含凹形節線成本之最小成本網路流動問題，以粒子群最佳化演算法之搜尋概念為基礎，並結合遺傳演算法、門檻值接受法與凹形成本網路啟發解法之特點，以節線及路徑為基礎發展兩種不同之混合式全域搜尋法，期能有效的求解含凹形節線成本之最小成本網路流動問題。本研究演算法的設計初擬如下：在初始解的產生上，擬以隨機方式及配合凹形成本網路特性發展二初始解法，產生初始的粒子群。在可行解的產生上：以節線為基礎之演算法，擬以前ㄧ回合伸展樹為基礎，引進遺傳演算法之輪盤法選擇策略，發展數種方式以挑選節線加入伸展樹，並透過流量推擠法產生可行伸展樹；至於以路徑為基礎之演算法，則擬發展數種供給點指派之順序選擇策略及供需節點對之路徑選取方式，以重新指派供需節點間的運送量，並藉由流量推擠法以形成可行伸展樹。另外再發展路徑集合更新策略，以加入較佳伸展樹中新的供需節點對路徑。另外，在粒子的速度更新法則上，擬參考引入連續型粒子群最佳化之貫性權重值（W）與可行伸展樹之特性，發展與以往不同的速度演算法則。在主體與個體最佳解的更新方式上，擬引入門檻值接受法之求解機制。最後在搜尋的深度上，擬結合區域搜尋能力較強的鄰近搜尋法，以提升演算績效。最後，為測試本研究演算法在不同規模及參數的網路問題之求解績效，本研究擬設計一隨機網路產生器，產生大量的隨機網路，在個人電腦上以C++語言撰寫所有相關的電腦程式，並擬測試新近發展之遺傳演算法、門檻值接受法、大洪水法及類螞蟻族群演算法，以評估本研究兩種演算法之求解績效，進而提供實務界求解此類實際的網路運送問題之參考。研究期間：9508 ~ 9607
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Civil Engineering] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	437	View/Open

社群 sharing

Loading...