[1]谭代伦,田树聪.基于布谷鸟算法求解折扣{0-1}背包问题[J].西华师范大学学报(自然科学版),2019,40(04):420-427.[doi:10.16246/j.issn.1673-5072.2019.04.016]
 TAN Dailun,TIAN Shucong.To Solve the Discount {0-1} Knapsack Problem by Cuckoo Search Algorithm[J].Journal of China West Normal University(Natural Sciences),2019,40(04):420-427.[doi:10.16246/j.issn.1673-5072.2019.04.016]
点击复制

基于布谷鸟算法求解折扣{0-1}背包问题

()
分享到:

《西华师范大学学报(自然科学版)》[ISSN:1673-5072/CN:51-1699/N]

卷:
40
期数:
2019年04期
页码:
420-427
栏目:
出版日期:
2019-12-20

文章信息/Info

Title:

To Solve the Discount {0-1} Knapsack Problem by Cuckoo Search Algorithm

作者:

谭代伦田树聪

(西华师范大学 数学与信息学院,四川 南充637009)

Author(s):

TAN DailunTIAN Shucong

(College of Mathematics and Information,China West Normal University,Nanchong Sichuan 637009,China)

关键词:

布谷鸟算法Levy飞行折扣{0-1}问题背包混合编码贪心策略

Keywords:

cuckoo search algorithmLevy flightdiscount {0-1} knapsack problemhybrid encodinggreedy strategy

分类号:
TP18
DOI:
10.16246/j.issn.1673-5072.2019.04.016
文献标志码:
A
摘要:

有N个备选集的折扣{01}背包问题(D{0-1}KP)的规模大,对智能进化算法的选用要求高,为此提出了基于Levy飞行策略的布谷鸟算法(CS)。首先,利用贪心核加速算法往背包添加部分物品,降低后续计算的复杂度;其次,利用混合编码的布谷鸟算法求解,并对结果中非正常编码进行修复;然后,利用贪心修复策略进一步完善求解结果;最后,通过实验确定CS中相关参数合理取值。通过对四类大规模的D{0-1}KP实例的求解结果表明:CS对于求解大规模D{0-1}KP有很好的计算性能。

Abstract:

Considering that the discount {0-1} knapsack problem (D {0-1} KP) with N selections of goods has a larger scale and higher requirement of intelligent evolutionary algorithm,an improved cuckoo search algorithm (CS) based on Levy flight is proposed.Firstly,the greedy nuclear acceleration algorithm is used to add some items to the backpack to reduce the complexity of subsequent calculations;secondly,the hybrid encoding cuckoo search algorithm is used to solve the problem,and the abnormal codes in the result are repaired;then,the greedy repair strategy is used to further improve the solution result;finally,the reasonable value of the relevant parameters in the CS are determined through experiments.The experimental results on four types of large-scale D {0-1} KP show that CS has good computational performance in solving largescale D {0-1} KP.

备注/Memo

备注/Memo:

收稿日期:2019-01-18
基金项目:〖HTSS〗四川省教育厅自然科学基金重点项目(15ZA0152);四川省科技计划资助(2019YFG0299);西华师范大学英才基金项目(17YC387);布谷鸟搜索算法改进实现及在物流管理中的应用(18ZA0469);南充市科技计划项目(17YFZJ0018)
作者简介:谭代伦(1971—),男,重庆铜梁人,教授,硕士生导师,主要从事优化理论与应用研究。

通信作者:谭代伦,E-mail:daulun_tan@cwnu.edu.cn

更新日期/Last Update: 2019-12-25