[1]卢璥.一种求解0-1背包问题的整数混沌粒子群优化算法[J].华侨大学学报(自然科学版),2013,34(5):516-520.[doi:10.11830/ISSN.1000-5013.2013.05.0516]
　LU Jing.An Integer Chaos-Particle-Swarm-Optimization Algorithm for 0-1 Knapsack Problem[J].Journal of Huaqiao University(Natural Science),2013,34(5):516-520.[doi:10.11830/ISSN.1000-5013.2013.05.0516]
点击复制

一种求解0-1背包问题的整数混沌粒子群优化算法()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第34卷
期数:
2013年第5期
页码:
516-520
栏目:
出版日期:
2013-09-20

文章信息/Info

Title:
An Integer Chaos-Particle-Swarm-Optimization Algorithm for 0-1 Knapsack Problem
文章编号:
1000-5013(2013)05-0516-05
作者:
卢璥
华侨大学 网络与教育技术中心, 福建 厦门 361021
Author(s):
LU Jing
Center for Network and Education Technology, Huaqiao University, Xiamen 361021, China
关键词:
粒子群优化;  混沌;  0-1背包问题;  遗传算法
Keywords:
particle swarm optimization;  chaos;  0-1 knapsack problem;  genetic algorithm
分类号:
TP183
DOI:
10.11830/ISSN.1000-5013.2013.05.0516
文献标志码:
A
摘要:
针对0-1背包问题(0-1 KP)的特点,以经典的速度-位移模型为基础整数编码各粒子,以混沌序列指导全局搜索,以排列的改变描述粒子的飞行.更新粒子的位置,进而提出用于求解0-1 KP的整数混沌粒子群优化(ICPSO)算法.该算法由于背包容量的限制,融入到编码和粒子飞行中,因而不会在进化中产生无效的粒子,从而提高了算法的求解效率.实验结果表明:ICPSO算法简明、有效,较典型遗传算法,及粒子群算法具有更好的收敛性能和求解速度.
Abstract:
For solving 0-1 knapsack problem(KP), an integer chaos-particle-swarm-optimization(ICPSO)algorithm is presented. In the algorithm, according to the characteristic of 0-1 KP, the classical velocity-position model is inherited; each particle is encoded with integers; a chaos sequence is employed to direct global search; and the permutation change is used to depict the flying behavior of each particle,(i.e., the update of position). Further, because the limit of pack capacity is taken into consideration in the coding and particle flying process, no invalid particles are produced in the evolutionary process, which thereby enhances the algorithm efficiency. Experimental results demonstrate that ICPSO is simple but effective, and better than genetic algorithm and particle swarm optimization at constringency and convergence speed.

参考文献/References:

[1] DANTZIG G B.Discrete variable extremum problems[J].Operations Reaserach,1957,5(2):266-277.
[2] 张生,魏忠华,何尚录,等.0-1背包问题在限额投资决策中的应用及其扰动分析[J].内蒙古师范大学学报:自然科学汉文版,2007,36(9):595-598.
[3] 徐光辉.运筹学基础手册[M].北京:科学出版社,1999:102-188
[4] 王保仓,韦永壮,胡予濮.基于随机背包的公钥密码[J].电子与信息学报,2010,32(7):1580-1584.
[5] EBERHART R,KENNEDY J.A new optimizer using particle swarm theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science.Los Alamitos:IEEE Press,1995:39-43.
[6] ZHU Jia-rui,JI Zhen,SHI Yu-hui,et al.DNA sequence compression using adaptive particle swarm optimization-based memetic algorithm[J].IEEE Transactions on Evolutionary Computation,2011,15(5):643-658.
[7] ROUT N K,DAS D P,PANDA G.Particle swarm optimization based active noise control algorithm without secondary path identification[J].IEEE Transactions on Instrumentation and Measurement,2012,61(2):554-563.
[8] 胡珀,娄渊胜.改进粒子群优化算法在服务组合中的应用[J].计算机工程,2011,37(17):130-132.
[9] 唐朝霞,章慧,徐冬梅.一种改进的粒子群算法和相关反馈的图像检索[J].计算机科学,2011,38(10):278-280.
[10] 黄润生.混沌及其应用[M].武汉:武汉大学出版社,2002:128-140.
[11] KENNEDY J,EBERHART R C.A discrete binary version of the particle swarm algorithm[C]//Proceedings of the 10th IEEE International Conference on Systems,Man and Cybernetics.Los Alamitos:IEEE Press,1997:4104-4109.
[12] 王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002:18-50.
[13] 曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004:12-18.

相似文献/References:

[1]汤龙坤.太阳黑子数时间序列的R/S分析[J].华侨大学学报(自然科学版),2008,29(4):627.[doi:10.11830/ISSN.1000-5013.2008.04.0627]
　TANG Long-kun.Rescaled Range Analysis on Time Series of Sunspot Numbers[J].Journal of Huaqiao University(Natural Science),2008,29(5):627.[doi:10.11830/ISSN.1000-5013.2008.04.0627]
[2]金相华,陈尔明.拓扑动力系统中一类集合的推广[J].华侨大学学报(自然科学版),2011,32(4):467.[doi:10.11830/ISSN.1000-5013.2011.04.0467]
　JIN Xiang-hua,CHEN Er-ming.Some Generalizations of a Class of Sets in Topological Dynamical Systems[J].Journal of Huaqiao University(Natural Science),2011,32(5):467.[doi:10.11830/ISSN.1000-5013.2011.04.0467]
[3]王秉.高速收敛混沌粒子群算法的云计算任务调度[J].华侨大学学报(自然科学版),2015,36(6):650.[doi:10.11830/ISSN.1000-5013.2015.06.0650]
　WANG Bing.Cloud Computing Task Scheduling of High-Speed Convergence of Chaotic Particle Swarm Optimization[J].Journal of Huaqiao University(Natural Science),2015,36(5):650.[doi:10.11830/ISSN.1000-5013.2015.06.0650]

备注/Memo

备注/Memo:
收稿日期: 2012-05-22
通信作者: 卢璥(1984-),女,助理工程师,主要从事智能信息处理、人工智能理论与应用的研究.E-mail:jlu@hqu.edu.cn.
基金项目: 中央高校基本科研业务费专项基金资助项目, 华侨大学科研基金资助项目(11BS210)
更新日期/Last Update: 2013-09-20