求解动态背包问题的改进原对偶遗传算法

A Novel Primal-Dual Genetic Algorithm for Dynamic Knapsack Problems

动态背包问题是一类常见的工程设计问题,同时也是动态进化算法研究领域的难点之一。将贪婪近似法与双概率原对偶映射思想相结合,提出一种求解动态背包问题的改进双概率原对偶遗传算法。一方面,针对传统遗传算法求解动态问题时存在多样性缺失的缺陷,从保持等位基因多样性角度出发,引入基于基因位值的双概率对偶映射,该映射通过弱势基因位值的概念,在迭代过程中根据该数目对两个对偶概率进行适应性调整,使种群具有较理想的多样性;另一方面,通过当前环境反馈的启发式信息使种群较快地搜索到"可行优秀"区域,使得算法更快地追踪最优点的变化轨迹。仿真结果表明,采用该贪婪法后的原对偶遗传算法在动态背包问题的求解中具有较好的性能。

Dynamic knapsack problem is a familiar engineering design optimization problem,which is also a challenge in the field of investigating evolutionary algorithms for dynamic optimization problems.An improved double-probability primal-dual genetic algorithm is proposed,which integrates the greedy approximation method and double-probability primal-dualism scheme for solving dynamic knapsack problem.Firstly,for the sake of maintaining diversity of allies,the allele-based double-probability primal-dual mapping operator is introduced,which uses the notion of inferior-allele to adaptively adjust the two dual probabilities,and hence preventing diversity loss of classical genetic algorithm when dealing with dynamic optimization problems.Secondly,it is hoped that the heuristic information could enhance population searching for the'feasible and fitter'regions,and help the algorithm tracking the moving optimum as soon as possible.The recommended algorithm has been applied to the dynamic 0-1 knapsack problem with promising results and demonstrated the effectiveness of the proposed algorithm.