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

1、改进猴王遗传算法求解大规模组合拍卖竞胜标Improved Monkey-king Genetic Algorithm for SolvingLarge Winner Determination in Combinatorial AuctionLI Yu-zhong(Department of Electrical and Mechanical Engineering,Huizhou Economic and Polytechnic College, 516057, China):Using GAsolve the winner determination problem with large

2、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

3、 exchange recombination, and use Monkey-king elite preservation strategy. Experimental results show that improved MKGA is better than SGAin population size and computation. the prob? lem that tranditional branch and bound algorithm hard to solve, improved MKGA can solve and achieve better effect在多任务

4、系统中，拍卖是对资源和任务分配一种重要的机希I)。组 合拍卖中，买家可以对多个拍卖物品打包出价。最优竞胜标问题(WD) P ,是在组合拍卖当中，选择卖家收益最高的一种拍卖组合，每个物品只能被拍卖一次。这种形式的拍卖已经被应用 于电力市场、设备交易、通信带宽、运输交换、污染排放权拍卖和机 场着陆权等应用领域1 0但是，组合拍卖是一个难于求 解的NP完 全问题2,对于大规模组合拍卖最优竞胜标问题，除了搜索空间大，搜索空间难于自然编码，并且还要解决复杂约束条 件，严重影响了算法求解的效率。目前求解大规模组合拍卖最优竞胜 标问题的算法主要分为以下两类：一、精确算法：由Sandholm. T等 人提出的

5、在拍卖标上分支并结合深度优先搜索(DFS的BOB算法1。二、近似算法和启发式算法：用近似解 来代 替最优解。陈培友等3引入遗传算法中单亲遗传算子和嵌入优先 适合启发式的规则，给出了求解该问题的启发式遗传算法。白鉴聪等 4在Sandholm等人研究的基础上，提出了单亲算子与免疫算子相结 合的启发式算法(Heuristic algorithm, HA )第二步：在找“填1的两个个体的标组合配对矩阵”中，根 据所有不等于0元素构成的矩阵(或经行或列排列顺序变换后可形成 的由全部为1的元素构成的矩阵)，找出对应的行和列，可逐一找出 所有互换重组对，并将它们分别保存在指定的两个互换重组对存储空 间 Ra

6、mA、 RamB。Step 3：在“两个个体的标组合配对矩阵”中找岀零行，或 者零列。两个个体的标组合配对矩阵”中的零行或者零列，表示在矩阵中，存在这样的基因（出价），它可以在互换重组后新生成 的两 个 个体的任一个个体之中。这个基因（标）就是零行（列）对应的基 因（标）。我们称互换重组中的自由基因（标）。同样 保存在特定的 自由基因存储空间RamOoStep 4:两个个体互换重组，生成新的两个个体。在互换重组对的存储空间RamARamE中，取一互换重组对，随机 的将互换重组对包含的两个基因组合，分别的分配在两个新个体之 中。这样一直取到互换重组对存储空间为空。然后再将自由基因随 机分配到两个

7、新个体。Step 5：将群体的其他要互换重组的个体对，做同样的工作进行 互换重组，直到所有个体都互换重组完毕。2. 5猴王精英保留策略78Step 1:先将群体内个体按适应度降序排列，将本代最优个体与 上一代最优个体比较，较好的个体作为猴王个体精英保留。并将猴王 个体作为新群体的第一个个体。Step 2:次优一直到按适应度值排序第n/2位的个体保留在新 群体内。Step 3:剩下的n/2的群体位置，放置随机的单个基因（标） 使用猴王精英保留策略，优点在于：1）它保留了从最开始进化以来 最优的个体，又能使在进化在还没挣扎出早熟的时候，早熟（次优） 个体不会在群体里大量复制。2）它还保留了部分 本

8、代进化的成果，也就是本代次优到适应度排序第n/2位的个体保 留在新群体中。进化到第n代的时候，如果只保留最优成果，那么进 化的其他成果就没法保留。3）后一半的群体位置放置随机个体，这样做能增大跳出早熟的 机率。3实验结果与分析程序由matlab7. 3编制，运行在Intel Celeron 1. 2G ,内存 为1G的微机上。算法设置群体个数Population=20,只要出价组合满足数学模 型的约束，问题就有解。即使所有的标都不能组成标组合形成竞胜 标，那么也可以选取适应度值最大的标作为竞胜标。算法与Mat lab中的采用分支定界法的Bintprog函数（求解0-1整数规划 函数）做比较.因

9、为Bintprog函数所求得的是精确解，MKGA求得 的是近似解，因此定义MKGA所求得的解与bingprog函数所 求的解的 百分比为成熟度。根据文献1设置了四种不同分布的大规模组合 拍卖问题。3. 1统一分布统一分布（Urdform）:在物品中随机选择指定个数的物品， 标的价格是0,1的随机数。因为越到每个标分配的物品多的时候，标之间能组合的概率就 越小。所以越到分配物品多的时候，越依靠在初始或前几代群 体里 个体的分布概况。实验是用标n=450物品m=45每个标有u二312个 物品计算得出。MKGA实验是在最大代数g=1000,连续10次运算求平均 时间和平均最优成熟度的的数据。图1统一

10、分布（搜索时间与成熟度）图1可以看出，MKGA军决Uni for m分布的的成熟度略有下 降， 但是随着u （每个标的物品个数）增加，成熟度也有所增加，并且在 计算时间上也有明显减少。3. 2衰减分布衰减分布（Decay）:给定标一个随机的物品，然后以a （衰 减系数）为概率不断的一个个增加物品，直到某一次没有增加增加 物品。价格取0到物品个数n之间的随机数。实验是用标n=200物品m二20Q衰减系数a=0. 40. 8计算得 出。 a0.8后Bintprog函数容易超过最大线形规划求解次数。MKG实验 是在最大代数萨500,连续10次运算求平均时间和平均 最优成熟度的 的数据。图2可以看出衰减分布在时间上随着衰减系数a的增大，MKGA勺时间减少，Bintprog的时间增大；在衰减分布MKGA勺成 熟 度，却不断提高，求解质量也越来越好。当衰减系数小的时候，大 多数的标内物品比较少，随着衰减系数增大，标内物品增多，MKG/就 不断有优势。3. 3改进猴王遗传算法（MKG）群体数量与求解质量的关系实验 是用标n二200物品m二200, a二0. 8的衰减分布进行。群体数量 Ps=204080160 ,计算 10 次求平均。4结论本文针对组合拍卖求解大规模竞胜标的问题，提出了改进的猴王遗传算法。设计了预处理算子、插标算子和互换重组算子。从计 算实例说明，采用改进猴王遗传算法，群体