改進猴王遺傳算法求解大規(guī)模組合拍賣競勝標

摘要：用遺傳算法求解大規(guī)模、不同分布下的組合拍賣的最優(yōu)競勝標問題（WDP），由于搜索空間大且約束條件復雜，容易產(chǎn)生不可行解，而影響了算法求解的效率和質(zhì)量。針對WDP問題，設計預處理算子互換重組算子和增標算子，并采用猴王精英保存策略，提高了求解質(zhì)量。實驗結(jié)果表明，改進猴王遺傳算法（MKGA）比基本遺傳算法在計算量和群體規(guī)模上都有較大進步。對求解標含物品數(shù)較多、傳統(tǒng)分支定界法超過最大次數(shù)而無法求解的問題，算法能在求解質(zhì)量和效率的上達到更好的效果。

關鍵詞:組合拍賣；競勝標問題；遺傳算法;猴王遺傳算法；電子商務

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2012)01-0077-04

Improved Monkey-king Genetic Algorithm for Solving Large Winner Determination in Combinatorial Auction

LI Yu-zhong

(Department of Electrical and Mechanical Engineering, Huizhou Economic and Polytechnic College, 516057, China)

Abstract：Using GA solve the winner determination problem with large bids and items,run under different distribution,because the search space is large and constraint complex and it may easy to produce infeasible solution,would affect the efficiency and quality of algorithm.this paper present improved MKGA,include three new operator:preprocessing、insert bid and exchange recombination,and use Monkey-king elite preservation strategy.Experimental results show that improved MKGA is better than SGA in population size and computation.the prob? lem that tranditional branch and bound algorithm hard to solve,improved MKGA can solve and achieve better effect.

Key words: combinatorial auction ;the winner determination problem; genetic algorithm; Monkey-king genetic algorithm; electronic commerce

在多任務系統(tǒng)中，拍賣是對資源和任務分配一種重要的機制。組合拍賣中，買家可以對多個拍賣物品打包出價。最優(yōu)競勝標問題（WDP），是在組合拍賣當中，選擇賣家收益最高的一種拍賣組合，每個物品只能被拍賣一次。這種形式的拍賣已經(jīng)被應用于電力市場、設備交易、通信帶寬、運輸交換、污染排放權(quán)拍賣和機場著陸權(quán)等應用領域[1]。但是，組合拍賣是一個難于求解的NP完全問題[2]，對于大規(guī)模組合拍賣最優(yōu)競勝標問題，除了搜索空間大，搜索空間難于自然編碼，并且還要解決復雜約束條件，嚴重影響了算法求解的效率。目前求解大規(guī)模組合拍賣最優(yōu)競勝標問題的算法主要分為以下兩類：一、精確算法：由Sandholm.T等人提出的在拍賣標上分支并結(jié)合深度優(yōu)先搜索（DFS）的BOB算法[1]。二、近似算法和啟發(fā)式算法：用近似解來代替最優(yōu)解。陳培友等[3]引入遺傳算法中單親遺傳算子和嵌入優(yōu)先適合啟發(fā)式的規(guī)則，給出了求解該問題的啟發(fā)式遺傳算法。白鑒聰?shù)萚4]在Sandholm等人研究的基礎上，提出了單親算子與免疫算子相結(jié)合的啟發(fā)式算法(Heuristic algorithm,HA）等等。

第二步：在找“填1的兩個個體的標組合配對矩陣”中，根據(jù)所有不等于0元素構(gòu)成的矩陣（或經(jīng)行或列排列順序變換后可形成的由全部為1的元素構(gòu)成的矩陣），找出對應的行和列，可逐一找出所有互換重組對，并將它們分別保存在指定的兩個互換重組對存儲空間RamA、RamB。

Step 3：在“兩個個體的標組合配對矩陣”中找出零行，或者零列。

“兩個個體的標組合配對矩陣”中的零行或者零列，表示在矩陣中，存在這樣的基因（出價），它可以在互換重組后新生成的兩個個體的任一個個體之中。這個基因（標）就是零行（列）對應的基因（標）。我們稱互換重組中的自由基因（標）。同樣保存在特定的自由基因存儲空間Ram0。

Step 4:兩個個體互換重組，生成新的兩個個體。

在互換重組對的存儲空間RamA、RamB中，取一互換重組對，隨機的將互換重組對包含的兩個基因組合，分別的分配在兩個新個體之中。這樣一直取到互換重組對存儲空間為空。然后再將自由基因隨機分配到兩個新個體。

Step 5：將群體的其他要互換重組的個體對，做同樣的工作進行互換重組，直到所有個體都互換重組完畢。

2.5猴王精英保留策略[7~8]

Step 1:先將群體內(nèi)個體按適應度降序排列，將本代最優(yōu)個體與上一代最優(yōu)個體比較，較好的個體作為猴王個體精英保留。并將猴王個體作為新群體的第一個個體。

Step 2:次優(yōu)一直到按適應度值排序第n/2位的個體保留在新群體內(nèi)。

Step 3:剩下的n/2的群體位置，放置隨機的單個基因（標）。

使用猴王精英保留策略，優(yōu)點在于：1）它保留了從最開始進化以來最優(yōu)的個體，又能使在進化在還沒掙扎出早熟的時候，早熟（次優(yōu)）個體不會在群體里大量復制。2）它還保留了部分本代進化的成果，也就是本代次優(yōu)到適應度排序第n/2位的個體保留在新群體中。進化到第n代的時候，如果只保留最優(yōu)成果，那么進化的其他成果就沒法保留。

3）后一半的群體位置放置隨機個體，這樣做能增大跳出早熟的機率。

3實驗結(jié)果與分析

程序由matlab7.3編制，運行在Intel Celeron 1.2G，內(nèi)存為1G的微機上。

算法設置群體個數(shù)Population=20,只要出價組合滿足數(shù)學模型的約束，問題就有解。即使所有的標都不能組成標組合形成競勝標，那么也可以選取適應度值最大的標作為競勝標。算法與Matlab中的采用分支定界法的Bintprog函數(shù)（求解0-1整數(shù)規(guī)劃函數(shù)）做比較.因為Bintprog函數(shù)所求得的是精確解，MKGA求得的是近似解，因此定義MKGA所求得的解與bingprog函數(shù)所求的解的百分比為成熟度。根據(jù)文獻[1]設置了四種不同分布的大規(guī)模組合拍賣問題。

3.1統(tǒng)一分布

統(tǒng)一分布(Uniform)：在物品中隨機選擇指定個數(shù)的物品，標的價格是[0,1]的隨機數(shù)。

因為越到每個標分配的物品多的時候，標之間能組合的概率就越小。所以越到分配物品多的時候，越依靠在初始或前幾代群體里個體的分布概況。實驗是用標n=450物品m=45，每個標有u =3~12個物品計算得出。MKGA實驗是在最大代數(shù)g=1000,連續(xù)10次運算求平均時間和平均最優(yōu)成熟度的的數(shù)據(jù)。圖1統(tǒng)一分布（搜索時間與成熟度）

圖1可以看出，MKGA解決Uniform分布的的成熟度略有下降，但是隨著u(每個標的物品個數(shù))增加，成熟度也有所增加，并且在計算時間上也有明顯減少。

3.2衰減分布

衰減分布(Decay):給定標一個隨機的物品，然后以a(衰減系數(shù))為概率不斷的一個個增加物品，直到某一次沒有增加增加物品。價格取0到物品個數(shù)n之間的隨機數(shù)。

實驗是用標n=200物品m=200，衰減系數(shù)a=0.4~0.8計算得出。a>0.8后Bintprog函數(shù)容易超過最大線形規(guī)劃求解次數(shù)。MKGA實驗是在最大代數(shù)g=500,連續(xù)10次運算求平均時間和平均最優(yōu)成熟度的的數(shù)據(jù)。

圖2可以看出衰減分布在時間上隨著衰減系數(shù)a的增大，MKGA的時間減少，Bintprog的時間增大；在衰減分布MKGA的成熟度，卻不斷提高，求解質(zhì)量也越來越好。當衰減系數(shù)小的時候，大多數(shù)的標內(nèi)物品比較少，隨著衰減系數(shù)增大，標內(nèi)物品增多，MKGA就不斷有優(yōu)勢。

3.3改進猴王遺傳算法（MKGA）群體數(shù)量與求解質(zhì)量的關系

實驗是用標n=200物品m=200，a=0.8的衰減分布進行。群體數(shù)量Ps=204080160，計算10次求平均。

4結(jié)論

本文針對組合拍賣求解大規(guī)模競勝標的問題，提出了改進的猴王遺傳算法。設計了預處理算子、插標算子和互換重組算子。從計算實例說明，采用改進猴王遺傳算法，群體數(shù)與求解質(zhì)量沒有明顯聯(lián)系。對于標內(nèi)含物品比較多的大規(guī)模問題，比傳統(tǒng)的分支定界法，雖然在成熟度上有犧牲，但在計算時間上有較為明顯的優(yōu)勢，并且可以求解某些分支定界法求解超過線性規(guī)劃最大次數(shù)的問題。下一步相關的工作應該是定量分析或證明改進猴王遺傳算法或同類近似算法與分支定界法等精確算法的優(yōu)勢，研究改進猴王遺傳算法求解組合問題內(nèi)部機理等工作。

參考文獻:

[1] Sandholm T.Algorithm for optimal winner determination in cmbinatiorial auctions-ArtificialIntelligence,2002,135(1-2):1-54.

[2] Rothkopf M H,A.Pekec,R.M.Harstad.Computationall manageable combinationrial aucetions.Management Science,1998,44(8):1131-1147.

[3]陳培友，汪定偉，用改進遺傳算法求解組合拍賣競勝標[J].東北大學學報:自然科學版,2004,25（4）:350-351.

[4] Bai Jiancong,Chang Huiyou, Yi Yang.Modeling and Heuristic for Winner Determination in Combinatorial Auctions.Journal of Computer Research and Development, 2005,42(11):1856-1861.

[5]陳培友,汪定偉.組合拍賣競勝標確定問題的優(yōu)化方法綜述[J].管理工程學報,2004,18(3):74-77.

[6]李宇中.改進的猴王遺傳算法求解組合拍賣最優(yōu)競勝標[J].電腦知識與技術,2009,5(23)：6459-6461.

[7]李宇中,劉紅星,張勝.猴王遺傳算法的改進[J].南京師范大學學報:工程技術版,2004,4(3):53-56.

[8]郭晨海,謝俊,劉軍,等.連續(xù)非線性規(guī)劃的猴王遺傳算法[J].江蘇大學學報:自然科學版,2002,23（4）:87-90.