计算机技术与发展2020，Vol.30Issue(7) ：71-75.

混合人工化学反应优化算法求解0-1背包问题

Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem

王建辉 郑光勇 徐雨明
计算机技术与发展2020，Vol.30Issue(7) ：71-75.
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据

混合人工化学反应优化算法求解0-1背包问题

Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem

王建辉 1郑光勇 2徐雨明3
扫码查看

作者信息

  • 1. 长沙南方职业学院 民航学院,湖南 长沙 410208;湖南大学 信息科学与工程学院,湖南 长沙 410208
  • 2. 衡阳师范学院 计算机科学与技术学院,湖南 衡阳 421002
  • 3. 长沙师范学院 信息科学与工程学院,湖南 长沙 410001
  • 折叠

摘要

人工化学反应优化算法(ACROA)是一种模拟化学反应过程的元启发式算法,它把化学反应中的对象、状态、过程和事件设计成一种计算方法;把反应中焓和熵的能量变化设计成目标函数,通过求目标函数的最优组合来实现问题的求解.在现实生活中有许多问题都是求最优组合问题,它的求解可以采用人工化学反应优化算法来实现,但求解这些问题就是求解0-1背包问题,也是计算机领域的NP难问题,所以提出一种混合人工化学反应优化算法求解0-1背包问题.该方法首先把化学反应分成单分子和双分子两种反应类型,并对这两种类型中的不同化学反应进行二进制编码;其次,为了获得问题的最优解,引入一个贪婪策略的修正算子来修正反应过程的随机选择所产生的非可行解,并通过局部和全局搜索来获得问题的最优求解.实验结果证明ACROA算法的性能明显优于GA算法和QEA算法,该算法在解决背包问题等有很大的优势.

关键词

人工化学反应优化/0-1背包问题/组合优化/贪婪/化学反应

引用本文复制引用

基金项目

湖南省教改项目(ZJGB2019230)

湖南省教育科学研究项目(18C1824)

出版年

2020
计算机技术与发展
陕西省计算机学会

计算机技术与发展

CSTPCD
影响因子：0.621
ISSN：1673-629X
被引量2
参考文献量6
段落导航相关论文