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

Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem

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

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.