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

關(guān)鍵詞:組合拍賣；競(jìng)勝標(biāo)問(wèn)題；遺傳算法;猴王遺傳算法；電子商務(wù)

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

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

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

Step 3：在“兩個(gè)個(gè)體的標(biāo)組合配對(duì)矩陣”中找出零行，或者零列。

“兩個(gè)個(gè)體的標(biāo)組合配對(duì)矩陣”中的零行或者零列，表示在矩陣中，存在這樣的基因（出價(jià)），它可以在互換重組后新生成的兩個(gè)個(gè)體的任一個(gè)個(gè)體之中。這個(gè)基因（標(biāo)）就是零行（列）對(duì)應(yīng)的基因（標(biāo)）。我們稱互換重組中的自由基因（標(biāo)）。同樣保存在特定的自由基因存儲(chǔ)空間Ram0。

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

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

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

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

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

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

Step 3:剩下的n/2的群體位置，放置隨機(jī)的單個(gè)基因（標(biāo)）。

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

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

3.1統(tǒng)一分布

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

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

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

3.2衰減分布

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn):

[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ìn)遺傳算法求解組合拍賣競(jìng)勝標(biāo)[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,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]陳培友,汪定偉.組合拍賣競(jìng)勝標(biāo)確定問(wèn)題的優(yōu)化方法綜述[J].管理工程學(xué)報(bào),2004,18(3):74-77.

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

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

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