改进猴王遗传算法求解大规模组合拍卖竞胜标

摘要：用遗传算法求解大规模、不同分布下的组合拍卖的最优竞胜标问题（WDP），由于搜索空间大且约束条件复杂，容易产生不可行解，而影响了算法求解的效率和质量。针对WDP问题，设计预处理算子互换重组算子和增标算子，并采用猴王精英保存策略，提高了求解质量。实验结果表明，改进猴王遗传算法（MKGA）比基本遗传算法在计算量和群体规模上都有较大进步。对求解标含物品数较多、传统分支定界法超过最大次数而无法求解的问题，算法能在求解质量和效率的上达到更好的效果。

关键词:组合拍卖；竞胜标问题；遗传算法;猴王遗传算法；电子商务

中图分类号：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

在多任务系统中，拍卖是对资源和任务分配一种重要的机制。组合拍卖中，买家可以对多个拍卖物品打包出价。最优竞胜标问题（WDP），是在组合拍卖当中，选择卖家收益最高的一种拍卖组合，每个物品只能被拍卖一次。这种形式的拍卖已经被应用于电力市场、设备交易、通信带宽、运输交换、污染排放权拍卖和机场着陆权等应用领域[1]。但是，组合拍卖是一个难于求解的NP完全问题[2]，对于大规模组合拍卖最优竞胜标问题，除了搜索空间大，搜索空间难于自然编码，并且还要解决复杂约束条件，严重影响了算法求解的效率。目前求解大规模组合拍卖最优竞胜标问题的算法主要分为以下两类：一、精确算法：由Sandholm.T等人提出的在拍卖标上分支并结合深度优先搜索（DFS）的BOB算法[1]。二、近似算法和启发式算法：用近似解来代替最优解。陈培友等[3]引入遗传算法中单亲遗传算子和嵌入优先适合启发式的规则，给出了求解该问题的启发式遗传算法。白鉴聪等[4]在Sandholm等人研究的基础上，提出了单亲算子与免疫算子相结合的启发式算法(Heuristic algorithm,HA）等等。

第二步：在找“填1的两个个体的标组合配对矩阵”中，根据所有不等于0元素构成的矩阵（或经行或列排列顺序变换后可形成的由全部为1的元素构成的矩阵），找出对应的行和列，可逐一找出所有互换重组对，并将它们分别保存在指定的两个互换重组对存储空间RamA、RamB。

Step 3：在“两个个体的标组合配对矩阵”中找出零行，或者零列。

“两个个体的标组合配对矩阵”中的零行或者零列，表示在矩阵中，存在这样的基因（出价），它可以在互换重组后新生成的两个个体的任一个个体之中。这个基因（标）就是零行（列）对应的基因（标）。我们称互换重组中的自由基因（标）。同样保存在特定的自由基因存储空间Ram0。

Step 4:两个个体互换重组，生成新的两个个体。

在互换重组对的存储空间RamA、RamB中，取一互换重组对，随机的将互换重组对包含的两个基因组合，分别的分配在两个新个体之中。这样一直取到互换重组对存储空间为空。然后再将自由基因随机分配到两个新个体。

Step 5：将群体的其他要互换重组的个体对，做同样的工作进行互换重组，直到所有个体都互换重组完毕。

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

Step 1:先将群体内个体按适应度降序排列，将本代最优个体与上一代最优个体比较，较好的个体作为猴王个体精英保留。并将猴王个体作为新群体的第一个个体。

Step 2:次优一直到按适应度值排序第n/2位的个体保留在新群体内。

Step 3:剩下的n/2的群体位置，放置随机的单个基因（标）。

使用猴王精英保留策略，优点在于：1）它保留了从最开始进化以来最优的个体，又能使在进化在还没挣扎出早熟的时候，早熟（次优）个体不会在群体里大量复制。2）它还保留了部分本代进化的成果，也就是本代次优到适应度排序第n/2位的个体保留在新群体中。进化到第n代的时候，如果只保留最优成果，那么进化的其他成果就没法保留。

3）后一半的群体位置放置随机个体，这样做能增大跳出早熟的机率。

3实验结果与分析

程序由matlab7.3编制，运行在Intel Celeron 1.2G，内存为1G的微机上。

算法设置群体个数Population=20,只要出价组合满足数学模型的约束，问题就有解。即使所有的标都不能组成标组合形成竞胜标，那么也可以选取适应度值最大的标作为竞胜标。算法与Matlab中的采用分支定界法的Bintprog函数（求解0-1整数规划函数）做比较.因为Bintprog函数所求得的是精确解，MKGA求得的是近似解，因此定义MKGA所求得的解与bingprog函数所求的解的百分比为成熟度。根据文献[1]设置了四种不同分布的大规模组合拍卖问题。

3.1统一分布

统一分布(Uniform)：在物品中随机选择指定个数的物品，标的价格是[0,1]的随机数。

因为越到每个标分配的物品多的时候，标之间能组合的概率就越小。所以越到分配物品多的时候，越依靠在初始或前几代群体里个体的分布概况。实验是用标n=450物品m=45，每个标有u =3~12个物品计算得出。MKGA实验是在最大代数g=1000,连续10次运算求平均时间和平均最优成熟度的的数据。图1统一分布（搜索时间与成熟度）

图1可以看出，MKGA解决Uniform分布的的成熟度略有下降，但是随着u(每个标的物品个数)增加，成熟度也有所增加，并且在计算时间上也有明显减少。

3.2衰减分布

衰减分布(Decay):给定标一个随机的物品，然后以a(衰减系数)为概率不断的一个个增加物品，直到某一次没有增加增加物品。价格取0到物品个数n之间的随机数。

实验是用标n=200物品m=200，衰减系数a=0.4~0.8计算得出。a>0.8后Bintprog函数容易超过最大线形规划求解次数。MKGA实验是在最大代数g=500,连续10次运算求平均时间和平均最优成熟度的的数据。

图2可以看出衰减分布在时间上随着衰减系数a的增大，MKGA的时间减少，Bintprog的时间增大；在衰减分布MKGA的成熟度，却不断提高，求解质量也越来越好。当衰减系数小的时候，大多数的标内物品比较少，随着衰减系数增大，标内物品增多，MKGA就不断有优势。

3.3改进猴王遗传算法（MKGA）群体数量与求解质量的关系

实验是用标n=200物品m=200，a=0.8的衰减分布进行。群体数量Ps=204080160，计算10次求平均。

4结论

本文针对组合拍卖求解大规模竞胜标的问题，提出了改进的猴王遗传算法。设计了预处理算子、插标算子和互换重组算子。从计算实例说明，采用改进猴王遗传算法，群体数与求解质量没有明显联系。对于标内含物品比较多的大规模问题，比传统的分支定界法，虽然在成熟度上有牺牲，但在计算时间上有较为明显的优势，并且可以求解某些分支定界法求解超过线性规划最大次数的问题。下一步相关的工作应该是定量分析或证明改进猴王遗传算法或同类近似算法与分支定界法等精确算法的优势，研究改进猴王遗传算法求解组合问题内部机理等工作。

参考文献:

[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]陈培友,汪定伟.组合拍卖竞胜标确定问题的优化方法综述[J].管理工程学报,2004,18(3):74-77.

[6]李宇中.改进的猴王遗传算法求解组合拍卖最优竞胜标[J].电脑知识与技术,2009,5(23)：6459-6461.

[7]李宇中,刘红星,张胜.猴王遗传算法的改进[J].南京师范大学学报:工程技术版,2004,4(3):53-56.

[8]郭晨海,谢俊,刘军,等.连续非线性规划的猴王遗传算法[J].江苏大学学报:自然科学版,2002,23（4）:87-90.