Please wait a minute...
浙江大学学报(工学版)
J4  2013, Vol. 47 Issue (10): 1722-1730    DOI: 10.3785/j.issn.1008-973X.2013.10.004
自动化技术、电信技术     
混沌模拟退火粒子群优化算法研究及应用
刘爱军1,2, 杨育1, 李斐1, 邢青松1, 陆惠3, 张煜东4
1.重庆大学 机械传动国家重点实验室,重庆 400030; 2. 西安电子科技大学 经济与管理学院,陕西 西安 710071; 3.上海师范大学 天华学院,上海 201815; 4.哥伦比亚大学 脑图像实验室,美国 纽约 10032
Chaotic simulated annealing particle swarm optimization algorithm research and its application
LIU Ai-jun1,2, YANG Yu1, LI Fei1, XING Qing-song1, LU Hui3, ZHANG Yu-dong4
1. State Key Laboratory of Mechanical Transmissions, Chongqing University, Chongqing 400030, China|
2. Economy and Management School, Xidian University, Xi’an 710071, China|3. Tianhua College, Shanghai Normal University, Shanghai 201815, China|4. Brain Imaging Laboratory, Columbia University, New York 10032, USA
 全文: PDF  HTML
摘要：

针对粒子群优化算法容易陷入局部极值点、进化后期收敛速度慢、精度较差等缺点,提出混沌模拟退火粒子群优化(PSO)算法.引入混沌理论对粒子群优化算法的参数进行自适应调整,提高了算法的全局收敛性能|采用模拟退火(SA)算法,依据概率性的劣向转移,以一定概率接受劣解,使算法具有跳出局部最优而实现全局最优的能力.引入自适应温度衰变系数,使模拟退火算法能够根据当前环境自动调整搜索条件,从而提高算法的搜索效率.通过7个经典函数测试混沌模拟退火粒子群优化算法的性能,并将其应用于Job Shop调度问题.仿真实验结果表明,采用新算法有效地克服了停滞现象,增强了全局搜索能力,与遗传算法、粒子群优化算法相比寻优性能更佳.
Abstract:

A chaotic simulated annealing particle swarm algorithm was proposed to
deal with the deficiencies of particle swarm optimization (PSO) algorithm, such as easily being lost in local optimum, the slow evolutionary convergence speed and poor search accuracy and so on. The chaos theory was introduced to adjust the parameters of PSO algorithm adaptively, which improved the global convergence property. The simulated annealing(SA) algorithm, accepting inferior solutions at a certain probability based on probabilistic interior transfer, was adopted to make the algorithm has capability to jump out of local optimization and achieve global optimization. The adaptive temperature decay factor was introduced to make the SA algorithm adjust the search conditions automatically based on the current environmental conditions. Then the search efficiency of the algorithm was improved. The property of chaotic simulated annealing particle swarm algorithm was tested by seven classic functions and it was applied in job shop scheduling. Simulation results demonstrated that the stagnation was effectively overcome and the global search capability was enhanced through the proposed algorithm whose performance of global searching was superior to genetic algorithms and particle swarm optimization algorithms.
出版日期: 2013-10-01
:  TP 278  
基金资助:

国家自然科学基金资助项目(71071173,71301176)|新世纪优秀人才支持计划资助项目(NCET-07-0908)|教育部高等学校博士学科点科研基金资助项目(20120184120040,20090191110004)|中央高校基本科研业务费科研专项资助项目(K5051306006,CDJZR10110012)|教育部人文社会科学研究青年基金资助项目(13XJC630011)|西安电子科技大学新教师创新资助项目(K5051306013).
通讯作者: 杨育,男,教授,博导.     E-mail: yuyang@cqu.edu.cn
作者简介: 刘爱军(1980—),男,博士生,讲师,从事生产调度与仿真、企业建模、人工智能等研究.E-mail: liuaijun@cqu.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

刘爱军, 杨育, 李斐, 邢青松, 陆惠, 张煜东. 混沌模拟退火粒子群优化算法研究及应用[J]. J4, 2013, 47(10): 1722-1730.

LIU Ai-jun, YANG Yu, LI Fei, XING Qing-song, LU Hui, ZHANG Yu-dong. Chaotic simulated annealing particle swarm optimization algorithm research and its application. J4, 2013, 47(10): 1722-1730.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2013.10.004    或    http://www.zjujournals.com/eng/CN/Y2013/V47/I10/1722


［1］ 王凌. 智能优化算法及其应用［M］. 北京: 清华大学出版社, 2004.

［2］ 王万良,唐宇.微粒群算法的研究现状与展望［J］.浙江工业大学学报, 2007, 35(2): 136-141.

WANG Wan-liang, TANG Yu. The state of art in particle swarm optimization algorithms ［J］. Journal of Zhejiang University of Technology, 2007, 35(2): 136-141.

［3］ CHEN Ting-yu, CHI Tzu-ming. On the improvements of the particle swarm optimization algorithm ［J］. Advances in Engineering Software, 2010, 41(2): 229-239.

［4］ 何利,刘永贤,谢华龙,等.基于粒子群算法的车间调度与优化［J］.东北大学学报:自然科学版,2008, 29(4): 565-568.

HE Li, LIU Yong-xian, XIE Hua-long, et al. Job shop scheduling and its optimization based on particle swarm optimizer ［J］. Journal of Northeastern University: Natural Science, 2008, 29(4): 565-568.

［5］ 白俊杰,王宁生,唐敦兵.一种求解多目标柔性作业车间调度的改进粒子群算法［J］.南京航空航天大学学报, 2010, 42(4): 447-453.

BAI Jun-jie, WANG Ning-sheng, TANG Dun-bing. Improved PSO algorithm for multi-objective optimization flexible job shop scheduling problems ［J］. Journal of Nanjing University of Aeronautics and Astronautics, 2010, 42(4): 447-453.

［6］ 雷德明,吴智铭.基于粒子群优化的多目标作业车间调度［J］.上海交通大学学报, 2007, 41(11): 1796-1800.

LEI De-ming, WU Zhi-ming. Particle swarm optimization based multi-objective job shop scheduling ［J］. Journal of Shanghai Jiaotong University, 2007, 41(11): 1796-1800.

［7］ 潘全科,王文宏,朱剑英. 基于粒子群优化和模拟退火的混合调度算法［J］.中国机械工程, 2006, 17(10): 1044-1046.

PAN Quan-ke, WANG Wen-hong, ZHU Jian-ying. Effective hybrid heuristics based on particle swarm optimization and simulated annealing algorithm for job shop scheduling ［J］.China Mechanical Engineering, 2006, 17(10): 1044-1046.

［8］ XIA Wei-jun, WU Zhi-ming. A hybrid particle swarm optimization approach for the job-shop scheduling problem ［J］. International Journal of Advanced Manufacturing Technology, 2006, 29(3/4): 360-366.

［9］ JAMILI A, SHAFIA M, TAVAKKOLI M. A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem ［J］. International Journal of Advanced Manufacturing Technology, 2011, 54 (1/2/3/4): 309-322.

［10］ MOSLEHI G, MAHNAM M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search ［J］. International Journal of Production Economics, 2011,129(1): 14-22.

［11］ ZHANG Guo-hui, SHAO Xin-yu, LI Pei-gen, et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem ［J］. Computers and Industrial Engineering, 2009,56(4):1309-1318.

［12］ 宋书强,叶春明.用QPSO算法求解模糊交货期Flow-shop调度问题［J］.计算机工程与应用,2009,45(6): 246-248.

SONG Shu-qiang, YE Chun-ming. Quantum particle swarm optimization for flow-shop scheduling problem with fuzzy delivery time ［J］. Computer Engineering and Applications, 2009, 45(6): 246-248.

［13］ 虞斌能,焦斌,顾幸生.改进协同粒子群优化算法及其在Flow Shop调度中的应用［J］.华东理工大学学报: 自然科学版,2009,35(3): 468-474.

YU Bin-neng, JIAO Bin, GU Xing-sheng. An improved cooperative particle swarm optimization and its application to flow shop scheduling problem ［J］. Journal of East China University of Science and Technology: Natural Science Edition, 2009, 35(3): 468-474.

［14］ LIAN Zhi-gang, JIAO Bin, GU Xing-sheng. A similar particle swarm optimization algorithm for job shop scheduling to minimize make span ［J］. Applied Mathematics Computation, 2006, 183(2): 1008-1017.

［15］ 叶建芳,王正肖,潘晓弘.免疫粒子群优化算法在车间作业调度中的应用［J］.浙江大学学报:工学版,2008,42(5): 863-868.

YE Jian-fang, WANG Zheng-xiao, PAN Xiao-hong. Application of immune particle swarm optimization to job-shop scheduling problem ［J］. Journal of Zhejiang University: Engineering Science, 2008, 42(5): 863-868.

［16］ SHA D, HSU C Y. A hybrid particle swarm optimization for job shop scheduling problem ［J］. Computers and Industrial Engineering, 2006, 51(4): 791-808.

［17］ BEHNAMIAN J, ZANDIEH M, FATEMI G. Due windows group scheduling using an effective hybrid optimization approach ［J］. International Journal of Advanced Manufacturing Technology, 2010, 46(5/6/7/8): 721-735.

［18］ TANG Li-xin, WANG Xian-peng. An improved particle swarm optimization algorithm for the hybrid flowshop scheduling to minimize total weighted completion time in process industry ［J］. IEEE Transactions on Control Systems Technology, 2010, 18(6): 1303-1314.

［19］ TSUNG L L, SHI J H, TZONG W K, et al. An efficient job-shop scheduling algorithm based on particle swarm optimization ［J］. Expert Systems with Applications, 2010, 37(3): 2629–2636.

［20］ TRELEA I C. The particle swarm optimization algorithm: convergence analysis and parameter selection ［J］. Information Processing Letters, 2003, 85(6): 317-325.

［21］ NAKA S, GENJI T, YURA T, et al. A hybrid particle swarm optimization for distribution state estimation ［J］. IEEE Transaction on Power Systems, 2003, 18(1): 60-68.

［22］ 刘洪波,王秀坤,谭国真.粒子群优化算法的收敛性分析及其混沌改进算法［J］.控制与决策, 2006, 21(6): 636-640.

LIU Hong-bo, WANG Xiu-kun, TAN Guo-zhen. Convergence analysis of particle swarm optimization and its improved algorithm based on chaos ［J］. Control and Decision, 2006, 21(6): 636-640.

［23］ 刘志雄,梁华.粒子群算法中随机数参数的设置与实验分析［J］.控制理论与应用,2010,27(11):1489-1496.

LIU Zhi-xiong, LIANG Hua. Parameter setting and experimental analysis of the random number in particle swarm optimization algorithm ［J］. Control Theory and Applications, 2010, 27(11): 1489-1496.

［24］ 贾兆红,陈华平,孙耀晖.混合粒子群算法在柔性工作车间调度中的应用［J］.系统仿真学报,2007,19(20):4743-4747.

JIA Zhao-hong, CHEN Hua-ping, SUN Yao-hui. Hybrid particle swarm optimization for flexible job shop scheduling ［J］. Journal of System Simulation, 2007, 19(20): 4743-4747.

［25］ 戴冬雪,王祁,阮永顺,等.基于混沌思想的粒子群优化算法及其应用［J］.华中科技大学学报:自然科学版, 2005, 33(10): 53-55.

DAI Dong-xue, WANG Qi, RUAN Yong-shun, et al. Chaos-based particle swarm optimization algorithm and its application ［J］. Journal of Huazhong University of Science and Technology: Nature Science Edition, 2005, 33(10): 53-55.

［26］ 贾松卫,高岳林.融合模拟退火和混沌的混合粒子群算法［J］.计算机工程与应用, 2009, 45(7): 52--55.

JIA Song-wei, GAO Yue-lin. Hybrid particle swarm optimization algorithm merging simulated annealing and chaos ［J］. Computer Engineering and Applications, 2009, 45(7): 52-55.

［27］ 王巍,彭力.嵌入隔离小生境技术的混沌粒子群算法［J］.系统工程与电子技术, 2008, 30(6): 1152-1154.

WANG Wei, PENG Li. Chaos particle swarm optimization combined with isolation niche ［J］. Systems Engineering and Electronics, 2008, 30(6):1152-1154.

［28］ 王万良,周明,徐新黎,等.基于改进粒子群算法的离子膜车间调度问题研究［J］.控制与决策, 2010, 25(7): 1021-1025.

WANG Wan-liang, ZHOU Ming, XU Xin-li, et al. Research of ion exchange membranes shop scheduling problem based on improved PSO ［J］. Control and Decision, 2010, 25(7): 1021-1025.

［29］ OTT E, GREBOGI C, YORKE J A. Controlling chaos ［J］. Physical Review Letters, 1990, 64(11): 1196-1199.
[1] 徐姗姗, 董利达, 朱丹, 朱承丞. S4PR网的极小信标计算方法[J]. J4, 2013, 47(3): 431-441.
[2] 田景红, 潘晓弘, 王正肖. 基于频繁模式挖掘的实时供应链数据分析[J]. J4, 2009, 43(12): 2259-2263.
[3] 叶建芳, 潘晓弘, 王正肖, 等. 基于免疫离散粒子群算法的调度属性选择[J]. J4, 2009, 43(12): 2203-2207.