 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：27 、訪客IP：18.117.12.11
姓名 王政嵐(Cheng-Lan Wang) 查詢紙本館藏 畢業系所 土木工程學系 論文名稱 類螞蟻族群演算法於求解含凹形節線成本最小成本轉運問題之研究
(Analogous Ant Colony System Algorithm for Concave Cost Minimum Cost Network Flow Problems)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 傳統上，最小成本轉運問題的運送成本常以線性方式來定義，藉以簡化問題的複雜度。然而，在實務上，貨物運送的單位成本常隨數量的增加而遞減，其成本函數曲線呈現凹形。因此，近期有學者以新近鄰近搜尋法，如門檻值接受法與大洪水法，求解含凹形節線成本之特殊最小成本網路流動問題，以達到擴大搜尋範圍的效用，期能找到較優於傳統啟發解法的解。然而，此等鄰近搜尋法，容易面臨退化的問題，且是否可快速探循全域，則不得而知。另外，有鑑於以往許多研究凹形成本運送問題的文獻，大都侷限於特殊的網路型態。因此近有學者利用遺傳演算法發展全域搜尋法以求解含凹形節線成本一般性最小成本轉運問題。
螞蟻族群演算法為一新近風行之巨集啟發解法，其利用分散式搜尋之觀念進行求解，並在許多問題上求得頗佳的結果，在部分的應用例中發現其求解效率較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.關鍵字(中) ★ 全域搜尋
★ 鄰近搜尋
★ 凹形節線成本
★ 類螞蟻族群演算法
★ 最小成本轉運問題關鍵字(英) ★ minimum cost transshipment problem
★ analogous ant colony system algorithm
★ global search
★ concave arc cost
★ neighborhood search論文目次 摘要................................................................................................................................ I
ABSTRACT.................................................................................................................. II
目 錄..........................................................................................................................III
圖目錄...........................................................................................................................V
表目錄..........................................................................................................................VI
第一章 緒論..............................................................................................................1
1.1 研究背景與動機...............................................................................................1
1.2 研究目的與範圍...............................................................................................2
1.3 研究方法與流程...............................................................................................2
第二章 文獻回顧..........................................................................................................4
2.1 凹形成本網路流動問題....................................................................................4
2.2 新近組合最佳化啟發式解法...........................................................................5
2.3 螞蟻族群最佳化...............................................................................................7
2.3.1 螞蟻族群最佳化簡介..............................................................................7
2.3.2 螞蟻族群演算法（Ant Colony System, ACS） ....................................9
2.4 遺傳演算法.....................................................................................................13
2.5 鄰近搜尋法.....................................................................................................14
2.5.1 模擬退火法............................................................................................15
2.5.2 門檻值接受法........................................................................................15
2.5.3 大洪水法................................................................................................15
2.5.4 禁制搜尋法............................................................................................16
2.6 小結.................................................................................................................16
第三章 問題描述與求解演算法設計........................................................................17
3.1 問題描述..........................................................................................................17
3.1.1 問題定式.................................................................................................17
3.1.2 問題特性說明.........................................................................................18
3.2 求解演算法設計-類螞蟻族群演算法（AACS）.........................................20
3.2.1 初始解產生策略....................................................................................20
3.2.1.1 隨機初始解產生法....................................................................20
3.2.1.2 依據凹形特性產生起始解........................................................22
3.2.2 流量推擠法............................................................................................25
3.2.3 可行解產生策略....................................................................................26
3.2.4 狀態轉移策略（state transition rule）.................................................29
3.2.5 鄰近搜尋法之改善策略（local search）.............................................31
3.2.6 費洛蒙更新策略（pheromone update）..............................................32
3.2.7 菁英策略（elitist）...............................................................................37
3.3 小結.................................................................................................................37
第四章 實證分析........................................................................................................39
4.1 網路產生器設計.............................................................................................39
4.1.1 隨機網路產生法....................................................................................39
4.1.2 供給(需求)節點與供給(需求)量的隨機產生法..................................40
4.2 AACS求解策略測試.......................................................................................41
4.2.1 費洛蒙更新策略....................................................................................43
4.2.2 供需節點對選擇方式............................................................................44
4.2.3 狀態轉移策略公式................................................................................45
4.2.4 初始解產生策略....................................................................................47
4.2.5 小結........................................................................................................48
4.3 AACS參數分析...............................................................................................49
4.3.1 人工螞蟻數............................................................................................50
4.3.2 狀態轉移策略相關參數........................................................................50
4.3.3 費洛蒙更新策略相關參數....................................................................51
4.3.3.1 費洛蒙更新公式相關參數.................................................................51
4.3.3.2 費洛蒙更新策略V之相關參數..........................................................54
4.3.4 鄰近搜尋法相關參數............................................................................55
4.3.5 菁英解相關參數....................................................................................57
4.3.6 最佳參數測試........................................................................................59
4.3.7 初始解與最終解之相關性....................................................................60
4.3.8 AACS收斂趨勢......................................................................................61
4.3.9 小結........................................................................................................63
4.4 AACS與GA、各區域搜尋法之求解績效比較.............................................64
第五章 結論與建議....................................................................................................67
5.1 結論.................................................................................................................67
5.2 貢獻.................................................................................................................68
5.3 建議.................................................................................................................68
參考文獻......................................................................................................................70
附錄一 費洛蒙策略測試結果....................................................................................75
附錄二 供需節點對選擇方式測試結果....................................................................80
附錄三 狀態轉移公式測試結果................................................................................82
附錄四 初始解產生策略測試結果............................................................................85
附錄五 AACS各系統參數測試方案.........................................................................88
附錄六 各參數測試詳細結果....................................................................................90
附錄七 初始解與最終解目標值關係......................................................................100
附錄八 GA與各區域搜尋法輸入參數值................................................................102
附錄九 各演算法配合方案求解時間......................................................................103
附錄十 各型網路之目前最佳解..............................................................................104參考文獻 1.朱文正，「考量旅行時間可靠度之車輛途程問題 ─ 螞蟻族群演算法之應用」，交通大學交通運輸研究所碩士論文（2002）。
2.江朋南，「蟻族系統在零工型排程問題之應用」，台灣科技大學工業管理系碩士論文（2003）。
3.林依潔，「整合模糊理論與螞蟻演算法於含時窗限制之車輛途程問題」，台北科技大學生產系統工程與管理研究所碩士論文（2003）。
4.徐誠佑，「螞蟻演算法求解零壹多限制背包問題」，清華大學工業工程與工程管理研究所碩士論文（2003）。
5.陳家和、丁慶榮，「應用螞蟻演算法於時窗限制車輛途程問題之研究」，中華民國運輸學會第十九屆論文研討會論文集（2004）。
6.陳建榮，「含凹形節線成本最小成本網路流動問題之全域搜尋演算法研究」，中央大學土木工程研究所碩士論文（2002）。
7.黃敏華，「應用螞蟻演算法於多階層供應鏈配送批量和車輛途程之訂定」，台灣科技大學工業管理研究所碩士論文（2003）。
8.張嘉升，「一般化巢式羅吉模式校估方法之研究 ─ 啟發式求解法與基因演算法之比較」，成功大學交通管理研究所碩士論文（2003）。
9.詹達穎，「模擬鍛鍊法求解車輛排程之探討」，中華民國運輸學會第九屆論文研討會論文集，第185-192頁（1994）。
10.熊鴻鈞，「螞蟻族群演算法於生產排程之應用」，暨南大學資訊管理研究所碩士論文（2003）。
11.韓復華、卓裕仁，「門檻接受法、成本擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊，第九卷，第三期，第103-129頁（1996）。
12.韓復華、林修竹，「TA與GDA巨集啟發式法在VRPTW問題上之應用」，中華民國第四屆運輸網路研討會，第83-92頁（1999）。
13.韓復華、楊智凱，「門檻接受法在TSP問題上之應用」，運輸計劃季刊，第二十五卷，第二期，第163-188頁（1996）。
14.韓復華、陳國清、卓裕仁，「成本擾動法在TSP問題之應用」，中華民國第二屆運輸網路研討會論文集，第283-292頁（1997）。
15.韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計畫季刊，第二十六卷，第二期，第253-280頁（1997）。
16.顏上堯、周榮昌、李其灃，「交通建設計畫評選模式及其解法之研究─以中小型交通建設計畫的評選為例」，運輸計畫季刊，第三十一卷，第一期（2002）。
17.顏上堯、陳建榮、湯慶輝，「含凹形節線成本最小成本轉運問題鄰近搜尋法之研究」，運輸計劃季刊，第三十三卷，第二期，第277-306頁（TSSCI）（2004）。
18.蕭宗勝，「螞蟻族群演算法應用在組合問題之研究」，銘傳大學資訊管理研究所碩士論文（2002）。
19.Abuali, F. N., Wainwright, R. L., and Schoenefeld, D. A., “Determinant Factorization: A New Encoding Scheme for Spanning Trees Applied to the Probabilistic Minimum Spanning Tree Problem,” Proceedings of The Sixth International Conference on Genetic Algorithms, pp. 470-477 (1995).
20.Ahuja, R. K., Maganti, T. L., and Orlin, J. B., Network Flows, Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs (1993).
21.Alfa, A. S., Heragu, S. S., and Chen, M. “A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problem,” Computers and Industrial Engineering, Vol. 21, pp. 635-639 (1991).
22.Amiri, A., and Pirkul, H., “New Formulation and Relaxation to Solve A Concave Cost Network Flow Problem,” Journal of the Operational Research Society, Vol. 48, pp. 278-287 (1997).
23.Balakrishnan, A., and Graves S. C., “A Composite Algorithm for a Concave-Cost Network Flow Problem,” Networks, Vol. 19, pp. 175-202 (1989).
24.Beckers, R., Deneubourg, J.L., and Goss, S., “Trails and U-turns in the Selection of the Shortest Path by theAnt Lasius Niger,” Journal of Theoretical Biology, 159, pp. 397-415 (1992).
25.Blumenfeld, D. E., Burns, L. D., Diltz, J. D., and Daganzo, C. F., “Analyzing Trade-offs Between Transportation, Inventory, and Production Costs on Freight Network,” Transportation Research, Vol. 19B, pp. 361-380 (1985).
26.Booker, L. B., “Improving Search in Genetic Algorithms,” Genetic Algorithms and Simulated Annealing (L. Davis, editor), Pitman, London, pp. 61-73 (1987).
27.Bullnheimer, B., Hartl, R. F., and Strauss, C., “Applying the Ant System to the Vehicle Routing Problem.” In: Voss, S., Martello, S., Osman, I.H., Roucairol, C. (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer:Boston. (1999).
28.Charon, I., and Hurdy, O., “The Noising Method: A New Method for Combinatorial Optimization,” Operations Research Letters, Vol. 14, pp. 133-137 (1993).
29.Costa, D., and Hertz, A., “Ants Can Colour Graphs.” Journal of the Computer Science (JORBEL), Vol.34, pp 39-53 (1994).
30.Davis, L., “Genetic Algorithm and Simulated Annealing,” Morgan Kaufman Publishers, Los Altos, CA (1987).
31.Davis, L., “Adapting Operator Probabilities in Genetic Algorithms,” Proceedings of the Third International Conference on Genetic Algorithms, pp. 61-69 (1989).
32.Di Caro, G., and Dorigo, M., “AntNet: Distributed Stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research (JAIR), 9: pp. 317-365 (1998). (Also available as: Tech. Rep. IRIDIA/98-01, Université Libre de Bruxelles, Belgium.)
33.Dorigo, M., and Gambardella, L. M., “A Study of Some Properties of Ant-Q,” Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, September 22-27, 1996, Berlin, Germany, Berlin: Springer-Verlag, 656-665. (1996).
34.Dorigo, M., and Gambardella, L. M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.” IEEE Transactions on Evolutionary Computation, 1(1): pp. 53-66. (1997a).
35.Dorigo, M., and Gambardella, L. M., “Ant Colonies for the Traveling Salesman Problem,” BioSystems, 43: pp. 73-81. (1997b).
36.Dorigo, M., Maniezzo, V., and Colorni, A., “The Ant System: An Autocatalytic Optimizing Process,” Technical Report No. 91-016 Revised, Politecnico di Milano, Italy (1991).
37.Dorigo, M., Maniezzo, V., and Colorni, A., “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1): pp. 29-41 (1996).
38.Dueck, G., “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics, Vol. 104, pp. 86-92 (1993).
39.Dueck, G., and Scheuer, T., “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics, Vol. 90, pp.161-175 (1990).
40.D. Kim, and P. Pardalos, “Dynamic Slope Scaling and Trust Interval Techniques for Solving Concave Piecewise Linear Network Flow Problems,” Networks, Vol. 35, pp. 216-222 (2000).
41.Gallo, G., Sandi C., and Sodini, C., “An Algorithm for the Min Concave Cost Flow Problem,” European Journal of Operation Research, Vol. 4, pp. 248-255 (1980).
42.Gallo, G., and Sandi, C., “Adjacent Extreme Flows and Application to Min Concave Cost Flow Problems,” Networks, Vol. 9, pp. 95-121 (1979).
43.Gambardella, L.M., and Dorigo, M., “Solving Symmetric and Asymmetric TSPs by Ant Colonies,” Proceedings of IEEE Intenational Conference on Evolutionary Computation, IEEE-EC 96, May 20-22, 1996, Nagoya, Japan, IEEE Press, pp. 622-627 (1996).
44.Glover, F., and Laguna, M., “Tabu search, Kluwer Academic Publishers,” Massachusetts (1997).
45.Glover, F., “Tabu Search, PartⅠ,” ORSA Journal on Computing Vol. 1, No. 3, pp.190-206 (1989).
46.Glover, F., “Tabu Search- Part II,” ORSA Journal on Computing, Vol. 2, No. 1, pp. 4-32 (1990).
47.Gen, M., and Cheng, R., “Genetic Algorithms and Engineering Design,” Wiley Interscience Publication, MA (1997).
48.Gu, J., and Huang, X., “Efficient Local Search with Search Space Smoothing: A Case Study of the Traveling Salesman Problem (TSP),” IEEE Transaction on Systems, Man and Cybernetics, Vol. 24, pp. 728-739 (1994).
49.Guisewite, G. M., and Pardalos, P. M., “A Polynomial Time Solvable Concave Network Flow Problems,” Networks, Vol. 23, pp. 143-147 (1993).
50.Goldberg, D. E., “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley, Reading MA (1989).
51.Golden, B. L., and Skiscim, C. C., “Using Stimulated Annealing to Solve Routing and Location Problems,” Naval Research Logistic Quarterly, Vol. 33, pp. 261-279 (1986).
52.Hall, R. W., “Direct Versus Terminal Freight Routing on Network with Concave Costs,” GMR-4517, Transportation Research Dept., GM Research Laboratories (1983).
53.Jordan, W. C., “Scale Economies on Multi-Commodity Networks,” GMR-5579, Operating Systems Research Dept., GM Research Laboratories (1986).
54.Kershenbaum, A., “When Genetic Algorithms Work Best,” INFORMS Journal of Computing, Vol. 9, No. 3, pp.253-254 (1997).
55.Kirkpatrick, S., Gelatt, C. D., and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680 (1983).
56.Kuhn, H. W., and Baumol, W. J., “An Approximate Algorithm for the Fixed-Charge Transportation Problem,” Naval Res. Logistics Quarterly, Vol. 9, pp. 1-16 (1962).
57.Kuntz, P. and Snyers, D., “Emergant Colonization and Graph Partitioning.” Proceedings of the 3th International Conference on Simulation of Adaptive Behavior : From Animals to Animate, 3, The MIT Press, Cambridge, MA (1997).
58.Larsson, T., Migdalas, A., and Ronnqvist, M., “A Lagrangian Heuristic for the Capacitated Concave Minimum Cost Network Flow Problem,” European Journal of Operational Research, Vol. 78, pp. 116-129 (1994).
59.Dorigo, M., and Gambardella, L. M., “Ant Colonies for the Traveling Salesman Problem,” (1996).
60.Mathias, K. E., and Whitley, L. D., “Initial Performance Comparisons for the Delta Coding Algorithm,” The First IEEE Conference on Evolutionary Computation, Orlando, Florida (1994).
61.Nourie, F. J., and Guder, F., “A Restricted-Entry Method for a Transportation Problem with Piecewise-Linear Concave Cost,” Computer & Operations Research, Vol. 21, pp. 723-733, (1994).
62.Osman, I. H., and Kelly, J. P., “Meta-Heuristics: An overview,” Meta-Heuristics: Theory & Applications, Kluwer Academic Publishers, Boston, London, Dordrecht, pp. 1-21 (1996).
63.Palmer, C. C., and Kershenbaum, A., ”Representing Trees in Genetic Algorithms,” Proceedings of the First IEEE Conference on Evolutionary Computation, Piscataway, NJ: IEEE Service Center, Vol. 1, pp. 379-384 (1994).
64.Powell, W. B, “A Review of Sensitivity Results for Linear Networks and a New Approximation to Reduce the Effects of Degeneracy,” Transportation Science, Vol. 26, No. 3, pp. 230-245 (1992).
65.Rech, P., and Barton, L. G., “A Non-Convex Transportation Algorithm,” Applications of Mathematical Programming Techniques, E. M. Beale, ed. (1970).
66.Reeves, C. R., “Improving the Efficiency of Tabu Search for Machine Sequencing Problems,” Journal of the Operation Research Society, Vol. 44, No. 4, pp. 375-382 (1993).
67.Sheffi, M. J., Urban Transportation Networks：Equilibrium Analysis with Mathematical Programming Methods, Prentical-Hall (1984).
68.Shyu, S. J., Yin, P. Y.and Lin, B. M. T., “An Ant Colony Optimization Algorthm for the Minimum Weight Vertex Cover Problem.” Manuscript Submitted for Publicatin. (NSC-90-2213-E-130-001), (2002).
69.Suwan, R., and Sawased, T., “Link Capacity Assignment in Packet- Switched Networks: The Case of Piecewise Linear Concave Cost Function,” IEICE Trans. Commun., Vol. E82-B, No. 10 (1999).
70.Taguhi, T., Ida. K., and Gen, M., “A Genetic Algorithm for Optimal Flow Assignment in Computer Network,” Computers ind. Engng, Vol. 35, No3-4, pp. 535-538 (1998).
71.Thach, P. T., “A Decomposition Method Using A Pricing Mechanism for Min Concave Cost Flow Problems With a Hierarchical Structure,” Mathematical Programming, Vol. 53, pp. 339-359 (1992).
72.Yaged, B., “Minimum Cost Routing for Static Network Models,” Networks, Vol. 1, pp. 139-172 (1971).
73.Yan, S., Juang, D. H., Chen, C. R., and Lai, W. S., “Global and Local Search Algorithms for Concave Cost Transshipment Problems,” Journal of Global Optimization (2004). (accepted)
74.Yan, S., and Luo, S. C., “A Tabu Search-Based Algorithm for Concave Cost Transportation Network Problems,” Journal of the Chinese Institute of Engineers, Vol. 21, pp. 327-335 (1998).
75.Yan, S., and Luo, S. C., “Probabilistic Local Search Algorithms for Concave Cost Transportation Network Problems,” European Journal of Operational Research, Vol.117, pp. 511-521 (1999).
76.Yan, S., and Young, H. F., “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,” Transportation Research, Vol. 30A, pp. 379-398 (1996).
77.Zangwill, W. I., “Minimum Concave Cost Flows in Certain Networks,” Management Science, Vol. 14, pp. 429-450 (1968)指導教授 顏上堯(Shangyao Yan) 審核日期 2005-7-14 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit