[1]王建辉,郑光勇,徐雨明.混合人工化学反应优化算法求解 0-1 背包问题[J].计算机技术与发展,2020,30(07):71-75.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
　WANG Jian-hui,ZHENG Guang-yong,XU Yu-ming.Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem[J].,2020,30(07):71-75.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
点击复制

混合人工化学反应优化算法求解 0-1 背包问题()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
30
期数:
2020年07期
页码:
71-75
栏目:
智能、算法、系统工程
出版日期:
2020-07-10

文章信息/Info

Title:
Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem
文章编号:
1673-629X(2020)07-0071-05
作者:
王建辉1; 2 ; 郑光勇3 ; 徐雨明4
1. 长沙南方职业学院 民航学院,湖南 长沙 410208; 2. 湖南大学 信息科学与工程学院,湖南 长沙 410208; 3. 衡阳师范学院 计算机科学与技术学院,湖南 衡阳 421002; 4. 长沙师范学院 信息科学与工程学院,湖南 长沙 410001
Author(s):
WANG Jian-hui1; 2 ; ZHENG Guang-yong3 ; XU Yu-ming4
1. School of Civil Aviation,Changsha Nanfang Professional College,Changsha 410208,China; 2. School of Information Science and Engineering,Hunan University,Changsha 410208,China; 3. School of Computer Science and Technology,Hengyang Normal University,Hengyang 421002,China; 4. School of Information Science and Engineering,Changsha Normal University,Changsha 410001,China
关键词:
人工化学反应优化; 0-1 背包问题; 组合优化; 贪婪; 化学反应
Keywords:
artificial chemical reaction optimization; 0-1 knapsack problem; combinatorial optimization; greedy; chemical reaction
分类号:
TP309
DOI:
10. 3969 / j. issn. 1673-629X. 2020. 07. 016
摘要:
人工化学反应优化算法(ACROA) 是一种模拟化学反应过程的元启发式算法,它把化学反应中的对象、状态、过程和事件设计成一种计算方法;把反应中焓和熵的能量变化设计成目标函数,通过求目标函数的最优组合来实现问题的求解。 在现实生活中有许多问题都是求最优组合问题,它的求解可以采用人工化学反应优化算法来实现,但求解这些问题就是求解 0-1 背包问题,也是计算机领域的 NP 难问题,所以提出一种混合人工化学反应优化算法求解 0-1 背包问题。 该方法首先把化学反应分成单分子和双分子两种反应类型,并对这两种类型中的不同化学反应进行二进制编码; 其次,为了获得问题的最优解,引入一个贪婪策略的修正算子来修正反应过程的随机选择所产生的非可行解,并通过局部和全局搜索来获得问题的最优求解。 实验结果证明 ACROA 算法的性能明显优于 GA 算法和 QEA 算法,该算法在解决背包问题等有很大的优势。
Abstract:
Artificial chemical reaction optimization algorithm (ACROA) is a kind of heuristic algorithm that simulates chemical reactions by designing objects,states,processes and events in chemical reactions as a computational method. Enthalpy and entropy energy changes can be utilized as objective functions to solve the problem by their optimal combination. It is a well-known combinatorial optimization problem in many real life applications,which can be solved by the artificial chemical reaction optimization algorithm,but to solve these problems is to solve the 0-1 knapsack problems,and it is also a NP hard problem in the computer field. The hybrid artificial chemical reaction optimization algorithms for solving 0-1 knapsack problems have been proposed in the literature. Firstly,the chemical reactions are divided into monomolecular and bimolecular reaction types,and binary encoding is used for different chemical reactions in the two types. Secondly,in order to obtain the optimal solution of the problem, a greedy strategy correction operator is introduced to correct the unfeasible solution generated by the random selection of the reaction process,and the local and global search is used to obtain the optimal solution of the problem. The experiment proves that ACROA is superior to the GA and QEA in performance,which has great advantages in solving knapsack problem.

相似文献/References:

[1]聂 鑫,殷若兰,刘海峰.软硬件协同的遗传算法设计[J].计算机技术与发展,2021,31(11):114.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 019]
　NIE Xin,YIN Ruo-lan,LIU Hai-feng.Design of Genetic Algorithm Based on Software and Hardware Cooperation[J].,2021,31(07):114.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 019]
[2]孙佳宁,马海龙,张立臣,等.求解 0-1 背包问题的融合贪心策略的回溯算法[J].计算机技术与发展,2022,32(02):190.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 031]
　SUN Jia-ning,MA Hai-long,ZHANG Li-chen,et al.Backtracking Algorithm of Fusion Greedy Strategy for Solving 0-1 Knapsack Problem[J].,2022,32(07):190.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 031]
[3]陈建荣.求解 0-1 背包问题的改进二进制捕鱼算法[J].计算机技术与发展,2023,33(05):187.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 028]
　CHEN Jian-rong.An Improved Binary Fishing Algorithm for 0-1 Knapsack Problem[J].,2023,33(07):187.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 028]

更新日期/Last Update: 2020-07-10