改进型连续粒子群算法求解重叠联盟生成问题

摘要/Abstract

摘要：

采用基于整数编码方式的连续粒子群算法解决重叠联盟生成问题.设计了粒子的编码方式，给出了编码有效性检查方法和无效编码的修正算法.为提高种群多样性，提出了粒子位置的二阶段初始化方法；针对粒子易陷入局部极值问题，给出了粒子重新初始化机制.对出现停滞现象的粒子群，围绕其加权重心位置重新初始化，引导粒子突破了局部极值的限制.最后，通过实验验证了算法的有效性.

关键词: 编码修正, 重新初始化机制, 重叠联盟生成, 粒子群算法, 整数编码, 二阶段初始化

Abstract:

An improved continuous particle swarm optimization (PSO) algorithm was proposed to solve the overlapping coalition generation problem. During the process of solution, an integer based encoding strategy was proposed which could represent the resource distribution of each agent to every task coalition, and the validation and revision algorithms for particle encoding were also presented. In order to improve the diversity of the swarm, a twostage initialization method of particle position was proposed. In the evolution process, the swarm trapping at the stagnation was reinitialized around its weighted centroid position, which could guide the swarm to avoid local extremum and accelerate the convergence of the algorithm. Contrastive experiments indicate that the proposed algorithm is effective.

Key words: overlapping coalition generation (OCG), particle swarm optimization (PSO), integer encoding, encoding revise, two stage initialization, code revise, reinitialized mechanism

中图分类号:

TP 18

杜继永1, 2，张凤鸣1，惠晓滨1，李永宾1. 改进型连续粒子群算法求解重叠联盟生成问题[J]. 上海交通大学学报（自然版）, 2013, 47(12): 1918-1923.

DU Jiyong1,2,ZHANG Fengming1,HUI Xiaobin1,LI Yongbin1. Overlapping Coalition Generation Using Improved Continuous Particle Swarm Optimization[J]. Journal of Shanghai Jiaotong University, 2013, 47(12): 1918-1923.

参考文献

［1］José Guerrero, Gabriel Oliver. Multirobotcoalition formation in realtime scenarios［J］.

Robotics and Autonomous Systems, 2012（60）: 12951307.

［2］Ke Cheng. Multirobot coalition formation for distributed area coverage［D］. Omaha: University of Nebraska, 2011.

［3］Zhang Yu, Parker L E. Considering intertask resource constraints in task allocation［J］. Auton Agent MultiAgent Syst, 2013,26(3): 389419.

［4］Joel G M, Sujit P B, Beard R W. Multiple UAV coalitions for a search and prosecute mission ［J］. Intell Robot Syst, 2011(62): 125158.

［5］Majid Ali Khan, Damla Turgut, Ladislau Blni. Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects［J］. Auton Agent MultiAgent Syst, 2011(22):415438.

［6］Travis C S， Julie A A. Coalition formation for task allocation: Theory and algorithms［J］. Auton Agent MultiAgent Syst, 2011(22): 225248.

［7］Michiel Keyzer, van Wesenbeeck Cornelia. Optimal coalition formation and surplus distribution: Two sides of one coin［J］. European Journal of Operational Research, 2011(215): 604615.

［8］刘淑华,张嵛,吴洪岩,等.基于群体智能的多机器人任务分配［J］. 吉林大学学报：工学版, 2010,40(1):123129.

LIU Shuhua, ZHANG Yu, WU Hongyan, et al. Multirobot task assignment based on swarm intelligence ［J］. Journal of Jilin University： Engineering and Technology Edition, 2010, 40(1):123129.

［9］张国富，周鹏，蒋建国，等．基于虚拟联盟的重叠联盟形成算法［J］．电子学报，2012, 40(1): 121127.

ZHANG Guofu, ZHOU Peng, JIANG Jianguo, et al. An algorithm for overlapping coalition formation based on virtual coalition ［J］. Acta Electronica Sinica, 2012, 40(1): 121127.

［10］郝志峰，蔡瑞初．并行多任务环境下Agent联盟的快速生成算法［J］．华南理工大学学报：自然科学版，2008，36(9)：1114．

HAO Zhifeng, CAI Ruichu. Fast generation algorithm of agent coalition in parallel multitask environment［J］. Journal of South China University of Technology： Natural Science Edition, 2008, 36(9):1114.

［11］Engelbrecht A P.计算群体智能基础［M］.谭营译.北京:清华大学出版社,2009:225234.

［12］杜继永，张凤鸣，李建文，等．一种具有初始化功能的自适应惯性权重粒子群算法［J］.信息与控制，2012， 41(2)：165169．

DU Jiyong, ZHANG Fengming, LI Jianwen, et al. A particle swarm optimization with initialized adaptive inertia weights［J］. Information and Control, 2012, 41(2): 165169.

[1]	林森, 文书礼, 朱淼, 戴群, 鄢伦, 赵耀, 叶惠丽. 考虑碳交易机制的海港综合能源系统电-热混合储能优化配置[J]. 上海交通大学学报, 2024, 58(9): 1344-1356.
[2]	林焰1, 2, 卞璇屹1, 董宗然3. 基于改进粒子群算法的船舶管路布局优化[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(5): 737-746.
[3]	季煜恒, 李春通, 骆晓萌, 杨雪莲, 王德禹. 基于人因工程的船舶驾驶室人机界面布局优化设计[J]. 上海交通大学学报, 2024, 58(2): 201-210.
[4]	董德金, 范云锋, 蔡云泽. 一种具有必经点约束的非结构化环境路径规划方法[J]. 空天防御, 2024, 7(1): 71-80.
[5]	符杨, 丁枳尹, 米阳. 计及储能调节的时滞互联电力系统频率控制[J]. 上海交通大学学报, 2022, 56(9): 1128-1138.
[6]	李春祥，裴杨从琪，殷潇. 基于Hermite组合核EMD-WT-LSSVM的非平稳非高斯风压预测[J]. 上海交通大学学报, 2019, 53(10): 1249-1258.
[7]	李春祥,殷潇. 基于小波支持向量机的非高斯空间风压内外插预测[J]. 上海交通大学学报, 2018, 52(11): 1516-1523.
[8]	徐峰1，范春菊1，徐勋建2，李丽2，倪佳筠3. 基于变分模态分解和AMPSO-SVM耦合模型的滑坡位移预测[J]. 上海交通大学学报, 2018, 52(10): 1388-1395.
[9]	张朝飞，罗建军，徐兵华，马卫华. 基于灰色理论的新陈代谢自适应多参数预测方法 [J]. 上海交通大学学报, 2017, 51(8): 970-976.
[10]	胡新明,王德禹. 基于迭代均值组合近似模型和序贯优化与可靠性评估法的船舶结构优化设计[J]. 上海交通大学学报, 2017, 51(2): 150-.
[11]	罗华毅，王景成，杨丽雯，李肖城. 基于时差系数的城市原水需水量预测应用[J]. 上海交通大学学报, 2017, 51(10): 1260-1267.
[12]	叶礼裕, 王超, 孙文林, 张洪雨. 近似模型方法在螺旋桨优化设计中的应用[J]. 上海交通大学学报, 2016, 50(8): 1173-1179.
[13]	王学武, 严益鑫, 丁冬雁, 顾幸生. 基于Lévy-PSO算法的焊接机器人避障路径规划[J]. 上海交通大学学报, 2016, 50(10): 1517-1520.
[14]	马驰,赵亮,梅雪松,施虎,杨军. 基于粒子群算法与BP网络的机床主轴热误差建模[J]. 上海交通大学学报（自然版）, 2016, 50(05): 686-695.
[15]	姜文英，林焰，陈明，于雁云. 基于粒子群和蚁群算法的船舶机舱规划方法[J]. 上海交通大学学报（自然版）, 2014, 48(04): 502-507.