運用不同演化計算方法於組合雙向拍賣問題之研究

A Study of Different Evolutionary Computation Approaches to Combinatorial Double Auction Problem

郭奕宏(YI-HONG GUO)

指導教授 ： 謝富雄

朝陽科技大學/資訊學院/資訊工程系/碩士(2018年)

摘要

儘管組合雙向拍賣可以使得買方和賣方更方便地交易商品，但組合雙向拍賣中的贏家決策問題（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.

並列關鍵字

Auction ； Winner Determination Problem ； Meta-heuristic ； Differential Evolution

參考文獻

參考文獻

[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.