论文部分内容阅读
随着电子商务的高速发展,拍卖市场中可供竞标者选择的物品急剧增加,拍卖方式也逐渐由单一同质物品的传统拍卖转向异质多物品的组合拍卖。组合拍卖(Combinatorial Auction,CA)允许竞标者依据物品之间的关联价值对多个物品的组合进行出价,因而能够提高拍卖的效率、降低商品流拍的风险。竞胜标确定问题(Winner Determination Problem,WDP)是组合拍卖的核心问题,其已被证明是一个NP难问题,求解WDP问题的算法性能直接影响拍卖人的最终收益。粒子群算法作为一种经典的群智能优化算法,具有模型简单、易于实现和参数少的特点,已广泛应用于NP问题,因此本文使用粒子群优化(Particle Swarm Optimization,PSO)算法求解WDP问题。为了解决PSO算法中种群多样性和收敛性之间的矛盾,本文提出了一种基于小生境的反向学习和局部学习的粒子群算法(Niche-Based Reverse-Learning and Local-Learning Particle Swarm Algorithm,NRLPSO)。主要做了以下两部分工作:(1)提出基于小生境的反向学习和局部学习的粒子群算法(NRLPSO)。首先,为提高PSO算法的种群多样性,降低其陷入局部最优的可能性,在PSO算法中引入了反向学习机制,当判定算法陷入局部最优时,启动反向学习机制。其次,为了提高算法的求解精度和收敛速度,设计局部学习机制。通过模糊聚类自适应生成不同小生境,小生境内部采用模拟退火法,强化算法的局部搜索能力,在小生境之间采用反向学习机制,强化算法的全局探索能力。最后,算法在不同维度基准函数上进行对比实验,分析算法的收敛速度、求解精度等优化性能,实验结果表明,相比于改进的对比粒子群算法,本文提出的NRLPSO具有更好的求解精度和稳定性。(2)使用所提NRLPSO算法解决WDP问题。首先,为了降低求解WDP问题的难度,依据竞标之间的价值约束关系对可行解空间进行预处理。其次,由于WDP问题的可行解空间是离散的,为保持算法在处理离散问题时的高效性和鲁棒性,采用映射粒子的位置而保持连续版本PSO的速度和位置更新公式不变的方式来求解WDP问题。最后,使用CATS 2.0软件平台生成基于L3与L4分布的不同规模的测试数据集,对比实验表明,NRLPSO算法在求解WDP问题时具有更高的求解精度。