臺灣博碩士論文加值系統

儘管組合雙向拍賣可以使得買方和賣方更方便地交易商品，但組合雙向拍賣中的贏家決策問題（WDP）由於計算的複雜度是一個極有挑戰性的問題。差分進化（Differential Evolution, DE）是一種被廣泛採用的競爭進化演算法，用於處理複雜的優化問題。在本論文中，考慮了交易成本、供需限制條件和非負盈餘限制條件的組合雙向拍賣問題。組合雙向拍賣問題的WDP 被描述為整數規劃問題。為了處理組合雙向拍賣的WDP 的計算複雜性，我們提出了一種基於離散DE 方法的兩種變形來尋找解的演算法。我們透過幾個數值例子也驗證了所提出的演算法的有效性。

Although combinatorial double auctions make buyers and sellers trade goods more conveniently, the winner determination problem (WDP) in combinatorial double auctions poses a challenge due to computation complexity. Differential evolution (DE) is a competitive evolutionary algorithm widely adopted to deal with complex optimization problems. In this thesis, a combinatorial double auction problem with transaction costs, supply constraints and non-negative surplus constraints is considered. The WDP of combinatorial double auction problem is formulated as an integer programming problem. To deal with computational complexity of the WDP for combinatorial double auctions, we propose an algorithm for finding solutions based on two variants of discrete DE approach. The effectiveness of the proposed algorithm are also demonstrated by several numerical examples.

目錄

中文摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VIII
第一章 簡介 1
1.1 研究背景與動機 1
1.2 研究目標與方法 3
1.3 論文架構 5
第二章 文獻回顧 6
第三章 問題描述與數學模式 12
3.1 組合雙向拍賣 12
3.2 數學式 14
第四章 解決方法 17
4.1 限制式處理 17
4.2 差分進化演算法 18
4.3 鄰域搜索差分進化演算法 24
第五章 模擬與研究結果 26
第六章 結論 37
參考文獻 38

表目錄
表 2.1 常見的進化演算法的優缺點。 8
表 3.1 5個買家的投標資料範例 13
表 3.2 5個賣方的投標資料範例 13
表 3.3 投標情況 14
表 3.4 組合雙向拍賣數學模式所用到的參數說明 14
表 4.1 DE演算法參數 21
表 5.1 拍賣參數值 26
表 5.2 拍賣買方投標 27
表 5.3 拍賣賣方投標 27
表 5.4 DE主要參數說明 28
表 5.5 10個買方與10個賣方的投標參數資料 28
表 5.6 10個買方投標資料 29
表 5.7 10個賣方投標資料 29
表 5.8 人口規模為10，幾個案例的組合雙向拍賣盈餘 33
表 5.9 人口規模為20，幾個案例的組合雙向拍賣盈餘 34
表 5.10 人口規模為30，幾個案例的組合雙向拍賣盈餘 34
表 5.11 人口規模為40，幾個案例的組合雙向拍賣盈餘 35
表 5.12 人口規模為50，幾個案例的組合雙向拍賣盈餘 36

圖目錄
圖 1.1 拍賣模式 1
圖 1.2 組合拍賣模式 2
圖 1.3 組合雙向拍賣模式 3
圖 4.1 離散DE演算法 23
圖 4.2 CS虛擬碼 23
圖 4.3 離散NSDE虛擬碼 25
圖 5.1 10個買方與10個賣方的結果 30
圖 5.2 10個買方與10個賣方的結果放大圖 31
圖 5.3 10個買方與10個賣方的結果放大圖-2 31
圖 5.4 10個買方與10個賣方的結果放大圖-3 32

參考文獻

[1]Mehdi Nourinejad, Matthew J.Roorda, ”Agent based model for dynamic ridesharing,” Transportation Research Part C: Emerging Technologies , March 2016, Vol. 64, pp. 117-132.
[2]Parnia Samimi, Youness Teimouri, Muriati Mukhtar, “A combinatorial double auction resource allocation model in cloud computing,” Information Sciences, August 2016, Vol. 357, pp. 201-216.
[3]T. Sandholm, “An algorithm for optimal winner determination in combinatorial auctions,” In: Proc. IJCAI'99, Stockholm, 1999, pp. 542-547.
[4]T. Sandholm, “Algorithm for optimal winner determination in combinatorial auctions,” Artificial Intelligence, 2002, Vol. 135, No. 1-2, pp.1-54.
[5]T. Sandholm, “Approaches to winner determination in combinatorial auctions,” Decision Support Systems, 2000, Vol. 28, pp. 165-176.
[6]Rothkopf M H, Pekec A, and Harstad R M, “Computationally manageable combinatorial auctions,” Management Science, INFORMS, USA, 1995, Vol. 44, No. 8, pp.1131-1147.
[7]Jiancong Bai, Huiyou Chang, and Yang Yi, "A partheno-genetic algorithm for optimal winner determination in combinatorial auctions," Proceedings of 2004 International Conference on Machine Learning and Cybernetics, ShangHai, 2004, pp.553-557.
[8]Edo Zurel, Noam Nisan, "An efficient approximate allocation algorithm for combinatorial auctions," ACM Conference on Electronic Commerce, Tampa FL, 2001, pp.125-136.
[9]Zhenyu Yang, Xin Yao and Jingsong He, “Making a Difference to Differential Evolution,” in Advances in Metaheuristics for Hard Optimization, Z.Michalewicz and P. Siarry, Eds. Berlin, Germany: Springer, 2007, pp. 415-432.
[10]J. Kennedy, R.C. Eberhart, “A discrete binary version of the particle swarm optimization,” in: Proceedings of the world Multiconference on Systemics, Cybernetics, Informatics, 1997, pp. 4104-4109.
[11]Qiang Gao and Xinhe Xu, ”The analysis and research on computational complexity,” The 26th Chinese Control and Decision Conference (2014 CCDC), 2014.
[12]Farhad Gorbanzadeh, Ali Asghar Pourhaji Kazem, “Hybrid Genetic Algorithms for Solving Winner Determination Problem in Combinatorial Double Auction in Grid,” International Journal of Artificial Intelligence (IJ-AI) , June 2012, Vol. 1, No. 2, pp. 54-62.
[13]Zhenyu Yang, Ke Tang and Xin Yao, ”Differential Evolution for High-Dimensional Function Optimization,” 2007 IEEE Congress on Evolutionary Computation, 2007.
[14]R. Storn, and K. Price, “Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces,” J. Global Optim. , 1997, Vol. 11, No. 4, pp. 341–359.
[15]A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential Evolution Algorithm with Strategy Adaptation for Global Numerical Optimization, “IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, APRIL 2009, Vol. 13, No. 2, pp. 398-417.
[16]Jie Gao, Hong Li, Yong-Chang Jiao, “Modified Differential Evolution for the Integer Programming Problems”, 2009 International Conference on Artificial Intelligence and Computational Intelligence, 2009.
[17]Jingqiao Zhang and Arthur C. Sanderson, “JADE: Adaptive Differential Evolution with Optional External Archive,” IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, OCTOBER 2009, Vol. 13, No. 5, pp. 945-958.
[18]Akbar Banitalebi, Mohd Ismail Abd Aziz, Zainal Abdul Aziz, “A self-adaptive binary differential evolution algorithm for large scale binary optimization problems,“ Information Sciences, November 2016, Vol. 367–368, pp. 487–511.
[19]Jagdish Chand Bansal and Kusum Deep, ”A Modified Binary Particle Swarm Optimization for Knapsack Problems,” Applied Mathematics and Computation , 2012, Vol. 218, pp. 11042–11061.
[20]Zhenyu Yang, Ke Tang, Xin Yao, “Large scale evolutionary optimization using cooperative coevolution,“ Information Sciences, August 2008, Vol. 178, pp. 2985–2999.
[21]R. Gonen, and D. Lehmann, “Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics,” The Proceedings of the Second ACM Conference on Electronic Commerce (EC'00), 2000, pp. 13-20.
[22]Fu-Shiung Hsieh, Chi-Shiang Liao, “Schemes to reward winners in combinatorial double auctions based on optimization of surplus,” Electronic Commerce Research and Applications, 2015, Vol. 14, No 6, pp. 405-417.
[23]R. Kowalczyk, ”Constrained genetic operators preserving feasibility of solutions in genetic algorithms,” Second International Conference On Genetic Algorithms In Engineering Systems: Innovations And Applications.
[24]Z. Michalewicz, M. Schoenauer, “Evolutionary algorithms for constrained parameter optimization problems,” Evolutionary Computation, 1996, Vol. 4, NO. 1, pp. 1-32.
[25]Slawomir Koziel, Zbigniew Michalewicz, “Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization,” Journal Evolutionary Computation archive, Spring 1999, Vol. 7,No. 1, pp. 19-44.
[26]Kai Sedlaczek and Peter Eberhard, “Constrained Particle Swarm Optimization of Mechanical Systems,” 6th World Congresses of Structural and Multidisciplinary Optimization, 2005.
[27]P.W. Jansen, R.E. Perez, ” Constrained structural design optimization via a parallel augmented Lagrangian particle swarm optimization approach,” Computers & Structures, July 2011, Vol. 89, No. 13–14, pp. 1352-1366.
[28]G.V. Reklaitis, A. Ravindran, K.M. Ragsdell, Engineering Optimization Methods and Applications, Wiley, New York, 1983.
[29]Fatma Pinar Goksal, Ismail Karaoglan, Fulya Altiparmak ,”A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery,” Computers & Industrial Engineering, May 2013, Vol. 65, No. 1, pp. 39-53.
[30]Zhi-Hui Zhan, Jun Zhang, Yun Li and Henry Shu-Hung Chung, “Adaptive Particle Swarm Optimization,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: CYBERNETICS, 2009, Vol. 39, No. 6, pp. 1362–1381.
[31]Takeshi Matsui, Kosuke Kato, Masatoshi Sakawa, Takeshi Uno, Kenji Morihara, ”Particle swarm optimization based heuristics for nonlinear programming problems,” MultiConference of Engineers and Computer Scientists 2007, IMECS 2007, March 21-23, 2007.
[32]K. Deb, “An efficient constraint handling method for genetic algorithms,” Computer Methods in Applied Mechanics and Engineering, 2000, Vol. 186, No. 2–4, pp. 311–338.
[33]Sehoenauer, M. and S. Xanthakis, “Constrained GA optimization,” In S. Forrest (Ed.), Proceedings of the 5th International Conference on Genetic Algorithms, 1993, pp. 573-580.