元胞分布估计算法求解高维0/1背包问题

Cellular Estimation of Distribution Algorithms for Solving High-dimensional 0/1 Knapsack Problem

基于元胞自动机的原理和分布估计算法,提出一种求解高维0/1背包问题的元胞分布估计算法.该算法将元胞及其邻居引入到框架中来增强其局部搜索能力,提高算法的收敛精度;同时,设计了一种采样机制,结合概率模型和当代最优个体来产生新个体以提高算法的收敛速度;另外,根据背包问题的特点设计了一种贪心修复机制,有效改善了种群中解的质量.在实验阶段,选取三种已有的智能算法,通过对不同约束条件下的高维0/1背包问题进行仿真比较,实验结果表明该算法能够避免早熟收敛,较其他算法具有更快的收敛速度和更高的稳定性.

This paper proposed a cellular estimation of distribution algorithms to solve high-dimensional 0/1 knapsack problem, which was based on the principles of cellular automata and estimation of distribution algorithms. It used cellular and its neighbors to enhance the local search ability to improve the accuracy of convergence. And it designed a sampling mechanism which was combined with the probabilistic model and the best individual to generate new individuals, which advanced the convergence speed. According to the char- acteristics of the knapsack problem it designed a greedy repair mechanism to increase the quality of the solution effectively. Simulation experiments on the high-dimensional 0/1 knapsack problem with different constraintsand comparison with three existing intelligent al- gorithms demonstrate that, the proposed algorithm can avoid premature convergence, and also show the predominant convergence speed and stability.