一种求解集合组合问题的离散粒子群优化模型

doi:10.3969/j.issn.1000-565X.2010.04.026

华南理工大学学报（自然科学版） ›› 2010, Vol. 38 ›› Issue (4): 141-146.doi: 10.3969/j.issn.1000-565X.2010.04.026

一种求解集合组合问题的离散粒子群优化模型

陈自郁何中市何静媛

重庆大学计算机学院, 重庆 400030

收稿日期:2009-02-12 修回日期:2009-10-15 出版日期:2010-04-25 发布日期:2010-04-25
通信作者: 陈自郁（1976-），女，博士，讲师，主要从事计算智能、机器学习研究． E-mail:chenziyu@cqu．edu．cn
作者简介:陈自郁（1976-），女，博士，讲师，主要从事计算智能、机器学习研究．
基金资助:
国家自然科学基金资助项目（30771446）; 国家“863”计划项目（2007AA01Z423）; 国家重大专项项目（2008ZX07315-001）; 重庆市自然科学基金资助项目（2007BB2134）

Discrete Particle Swarm Optimization Model for Set-Based Combinatorial Optimization Problems

Chen Zi-yu He Zhong-shi He Jing-yuan

College of Computer Science,Chongqing University,Chongqing 400030,China

Received:2009-02-12 Revised:2009-10-15 Online:2010-04-25 Published:2010-04-25
Contact: 陈自郁（1976-），女，博士，讲师，主要从事计算智能、机器学习研究． E-mail:chenziyu@cqu．edu．cn
About author:陈自郁（1976-），女，博士，讲师，主要从事计算智能、机器学习研究．
Supported by:
国家自然科学基金资助项目（30771446）; 国家“863”计划项目（2007AA01Z423）; 国家重大专项项目（2008ZX07315-001）; 重庆市自然科学基金资助项目（2007BB2134）

摘要/Abstract

摘要： 针对变长集合组合优化问题，提出了一种离散粒子群优化模型。为了符合集合的特点，该模型将集合的概念和运算引入到粒子群优化中，定义了一个可变集合搜索空间，重新定义了粒子的位置、速度及作用于此空间的运算规则。为了验证此模型的性能，将其应用到典型的变长集合组合优化问题—背包问题中。实验结果表明，基于该模型的算法具有强的寻优能力和好的稳定性。

关键词: 群智能, 离散粒子群优化, 集合, 组合优化, 背包问题

Abstract:

Proposed in this paper is a discrete particle swarm optimization model to solve set-based combinatorial optimization problems.The model introduces set concepts and operations in the particle swarm optimization,defines a search space of variable set and redefines the velocity and location of particles as well as the operators working in the defined search space.Thus,it possesses the characteristics of both particle swarm optimization and set-based combinatorial optimization.Finally,the proposed model is applied to the knapsack problem,a typical set-based combinatorial optimization problem,and it is compared with the binary particle swarm optimization（BPSO）.The results indicate that the proposed model is of stronger searching ability and higher stability.

Key words: set, combinatorial optimization, discrete particle swarm optimization, knapsack problem

陈自郁何中市何静媛. 一种求解集合组合问题的离散粒子群优化模型[J]. 华南理工大学学报（自然科学版）, 2010, 38(4): 141-146.

Chen Zi-yu He Zhong-shi He Jing-yuan. Discrete Particle Swarm Optimization Model for Set-Based Combinatorial Optimization Problems[J]. Journal of South China University of Technology (Natural Science Edition), 2010, 38(4): 141-146.

[1]	方港, 袁珑华, 王晓明, 等. 基于集合卡尔曼-Elman网络的软测量建模方法[J]. 华南理工大学学报(自然科学版), 2023, 51(8): 126-136.
[2]	任远马智亮向星磊. 集中管理下园区设备的维护策略决策模型及算法[J]. 华南理工大学学报（自然科学版）, 2020, 48(9): 51-60.
[3]	孙苗, 吴立, 袁青, 等 . 基于 CEEMDAN 的爆破地震波信号时频分析[J]. 华南理工大学学报（自然科学版）, 2020, 48(3): 76-82.
[4]	孙苗吴立周玉纯马晨阳汪煜烽. 水下钻孔爆破地震波信号的最优降噪光滑模型[J]. 华南理工大学学报（自然科学版）, 2019, 47(8): 31-37.
[5]	管超张则强李云鹏贾林. 一种求解双层过道布置问题的离散花授粉算法[J]. 华南理工大学学报（自然科学版）, 2019, 47(10): 60-74.
[6]	赵德尊李建勇程卫东. 齿轮噪声干扰及变转速下的滚动轴承故障诊断[J]. 华南理工大学学报（自然科学版）, 2016, 44(2): 67-73.
[7]	徐华张庭. 云计算环境下基于改进离散粒子群的并行调度算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(9): 95-99.
[8]	于宏涛高立群韩希昌. 求解旅行商问题的离散人工萤火虫算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(1): 126-131,139.
[9]	刘学良胥布工. 二阶多智能体系统的跟随者-多领导者聚集控制[J]. 华南理工大学学报（自然科学版）, 2013, 41(1): 8-14.
[10]	贾连印奚建清李孟娟游进国刘勇苗德成. Dtrie-allpair: 高效的集合T- 覆盖连接算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 109-117.
[11]	邓宇乔杜明辉梁亚玲廖冰. 基于背包问题的可纠错数字签名方案[J]. 华南理工大学学报（自然科学版）, 2010, 38(6): 46-49.
[12]	鲍江宏杨启贵. 多选择背包问题的快速求解算法[J]. 华南理工大学学报（自然科学版）, 2009, 37(4): 42-45.
[13]	张志毅文福栓刘敏忠. 电力系统负荷恢复优化的并行遗传算法实现[J]. 华南理工大学学报（自然科学版）, 2007, 35(6): 38-42.
[14]	徐向民邢晓芬刘伟陈小川. 基于医学图像ROI形状估计的改进SPIHT算法[J]. 华南理工大学学报（自然科学版）, 2006, 34(6): 1-5.
[15]	罗文标杨伦标. 委托代理制度下的最优控制关系[J]. 华南理工大学学报(自然科学版), 2004, 32(9): 90-92.

一种求解集合组合问题的离散粒子群优化模型

Discrete Particle Swarm Optimization Model for Set-Based Combinatorial Optimization Problems

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价