摘要
【目的】针对组合优化中的经典背包问题,提出了一种用于求解0-1背包问题的改进正弦余弦算法.【方法】按幂递减函数自适应调整参数r1,较好地平衡算法的全局探索与局部开发能力;利用采蜜蜂算子和贪婪选择策略,加快算法的收敛速度,提高算法优化精度;通过侦察蜂算子,增加种群多样性,防止算法陷入局部最优;采用贪心变换算法和修正连续解算法对求解过程中的不可行解进行修复.【结果】求解10个经典0-1背包问题的仿真实验表明,改进算法在收敛速度、求解精度和成功率等方面明显优于基本正弦余弦算法,并与其它改进智能算法的优化结果相当.【结论】改进算法具有较高的优化性能,能较好地求解0-1背包问题.
【Objective】Aiming at the classical knapsack problem in combinatorial optimization,an improved sine cosine algorithm for solving 0-1 knapsack problem was proposed.【Method】At first,the parameters r1 was adjusted by power decreasing function adaptively,which better balanced global exploration and local development capability of the algorithm.Then,the operator of employed bees and greedy selection strategy were utilized,which accelerated the convergence speed of the algorithm.Besides,the operator of reconnaissance bees was introduced,which increased diversity of the population and protected the algorithm from falling into local optimum.At last,the greedy transform algorithm and the revising continuous solution algorithm were used to repair the infeasible solution.【Result】The simulation results for solving ten classic 0-1 knapsack problems illustrated that the improved algorithm is better than the basic sine cosine algorithm in terms of convergence speed,solving accuracy and success rate,and the optimization results are similar to those of other improved intelligent algorithms.【Conclusion】The improved algorithm has higher optimization performance and can solve the 0-1 knapsack problem well.
作者
刘小娟
封成智
王联国
LIU Xiaojuan;FENG Chengzhi;WANG Lianguo(College of Information Science & Technology,Gansu Agricultural University,Lanzhou 730070,China)
出处
《甘肃农业大学学报》
CAS
CSCD
2021年第4期185-194,共10页
Journal of Gansu Agricultural University
基金
甘肃农业大学科技创新基金项目(GAU-XKJS-2018-251)
甘肃省教育信息化建设专项任务项目(2011-02)
国家自然基金项目(61751313).
关键词
智能优化算法
正弦余弦算法
人工蜂群算法
贪心变换算法
贪婪选择
0-1背包问题
intelligent optimization algorithm
sine cosine algorithm
artificial bee colony algorithm
greedy transform algorithm
greedy selection
0-1 knapsack problem
