改进的离散粒子群优化算法及其在竞胜标确定问题中的应用

计算机应用

改进的离散粒子群优化算法及其在竞胜标确定问题中的应用

王真衣杨

中山大学信息科学与计算学院中山大学信息科学与计算学院

收稿日期:2008-04-30 修回日期:1900-01-01 出版日期:2008-10-01 发布日期:2008-10-01
通讯作者: 王真

Improved discrete PSO algorithm and its application in winner determination problem

Zhen WANG Yang Yi

Received:2008-04-30 Revised:1900-01-01 Online:2008-10-01 Published:2008-10-01
Contact: Zhen WANG

摘要/Abstract

摘要： 通过拓展标准粒子群优化算法模型，提出了一种用于解决离散最优化问题的NDPSO算法，使其仍然具备标准PSO算法相对于其他智能算法的高效性和稳定性。在NDPSO算法的基础上引入依概率随机比较的概念，并构造了进行启发式搜索的随机修补算子，实现对组合拍卖中的竞胜标确定问题（WDP）的求解。实验结果表明，该求解方案与基于其他离散化PSO算法或遗传算法的求解方案相比在达优率和收敛速度上都具有明显的优势。

关键词: 组合拍卖, 竞胜标确定, 离散粒子群算法, 随机修补算子, 人工生命计算

Abstract: A kind of discrete Particle Swarm Optimization (PSO) algorithm named NDPSO was proposed for extending the classic PSO model to solve the discrete optimization problems with high effectiveness and stability. The concept of comparison with probability was also introduced based on NDPSO, and then the stochastic repairing operator was constructed for heuristic search to solve the Winner Determination Problem (WDP) in combinatory auction. The experimental results show that NDPSO has great advantages in both success rate and convergence speed compared with other discrete PSO algorithms and genetic algorithm.

Key words: combinatory auction, winner determination, discrete Particle Swarm Optimization (PSO), stochastic repairing operator, artificial life computation

王真衣杨. 改进的离散粒子群优化算法及其在竞胜标确定问题中的应用[J]. 计算机应用.

Zhen WANG Yang Yi. Improved discrete PSO algorithm and its application in winner determination problem[J]. Journal of Computer Applications.

[1]	徐华, 张庭. 改进离散粒子群算法求解柔性流水车间调度问题[J]. 计算机应用, 2015, 35(5): 1342-1347.
[2]	蒋志强廖晓峰刘群. 基于0-1规划的异构传感器网络任务分配策略[J]. 计算机应用, 2012, 32(04): 913-916.
[3]	刘爱珍王嘉祯张西红陈立云张西红. 一种考虑Agent截止期限的CPU时间片分配算法[J]. 计算机应用, 2008, 28(3): 695-698.