改进的猴王遗传算法求解组合拍卖最优竞胜标

应用遗传算法求解第一价格封闭组合拍卖问题,编码及约束条件复杂,在交叉和变异的过程中容易产生大量不可行解,并且在选择和精英保留中,一些局部最优点(早熟点)对应的个体容易被大量复制,使群体多样性下降。该文就以上的问题,改进了原有遗传算法求解组合拍卖最优竞胜标的方法,并采用了猴王遗传算法的精英保留策略。实际计算证明本算法编码方式自然并且直观表达了个体和标的的关系。在交叉和变异算子中,产生不可行解的数量下降,更积极的保存了上一代进化的部分成果。而改进猴王遗传算法的精英保留策略,使算法能够以高概率跳出早熟,达到算法速度与准确的平衡。

Improved Monkey-king Genetic Algorithm for Solving Winner Determination in Combinatiorial Aructions

Using GA solve the first price combinatorial auction problem, first the encoding should be intuitive simplicity.second, due to the complexity of constraint conditions, the crossover and mutation process produce a large number of infeasible solutions.third , in the selection or Elite preservation strategy process, a individual of premature convergence may be more reproduced ,so that decline diversity of the population.In this paper, we propose improved monkey-king GA(MKGA).In practice, the MKGA can make the ...