摘要
物流配送车辆路径问题(VRP)是一类典型的NP问题。在基本遗传算法的基础上,根据生物的免疫系统原理,提出一种改进的算法——免疫遗传算法。在算法中构造一种基于抗体浓度的群体多样性保持策略,引入免疫算子和免疫记忆库。将该算法应用于求解VRP问题,实验结果表明算法可以实现解的多样性,避免出现早熟收敛,可以有效防止进化过程中最优解退化的可能,是求解车辆路径问题的一种有效的算法。
The vehicle routing problem is a kind of NP problem. To solve this problem a new modified genetic algo- rithm-immune genetic algorithm based on the immune principle is presented. A kind of group diversity maintaining strategy based on the density of individual is constructed. A immune operator and a immune memory library are applied to the algorithm. The experimental results of a VRP instance show that the algorithm is a preferable scheme for the VRP which can implement diversity of solutions, avoid the problem of ＂premature convergence＂ and prevent the possibility of the degradation of the optimal solution effectively.
出处
《成都信息工程学院学报》
2008年第6期637-641,共5页
Journal of Chengdu University of Information Technology
关键词
车辆路径问题
免疫遗传算法
浓度
免疫算子
vehicle routing problem
immune genetic algorithm
density
immune operator
