求解非满载车辆调度问题的免疫遗传算法

Solving vehicle scheduling problem with non-full load by means of immune genetic algorithm

非满载车辆调度问题是车辆调度问题中的一个基本问题,由于它是一个典型的NP难题,传统方法的求解结果往往不能令人满意.曾有研究将传统的遗传算法用于求解非满载车辆调度问题,但是由于遗传算法在遗传后期的波动现象,导致了迭代次数过大和准确率不高.该实验根据生物免疫系统的机理提出的免疫遗传算法,结合了遗传算法的进化操作和生物免疫中的浓度机制,通过抗体的期望繁殖率实现对抗体的促进和抑制,改善未成熟收敛.该算法是在传统遗传算法全局随机搜索的基础上,借鉴生物免疫机制中抗体的多样性保持策略,改善了传统遗传算法的群体多样性,通过与遗传算法的比较,结果表明,该算法不仅收敛,而且具有更好的全局和局部搜索能力和收敛速度.

Vehicle scheduling problem with non-full load is a fundamental problem of vehicle scheduling problem. Because it is a typical NP-hard problem, traditional algorithms usually are not satisfactory. Previous research has used classic genetic algorithm to solve this problem, but with the limitation of the algorithm, this result is also not very satisfactory. In this paper, immune genetic algorithm is presented based on the natural immune system mechanism. The algorithm combines the evolution function of traditional genetic algorithms and the density mechanism in creatures, immune procedure. The adtibldies is realized by theespected breed rate to improve the premature convergence. Based on the globalsearching method of classic genetic algorithm （GA） , and using the diversity preservation strategy of antibodies in biology immunity mechanism , the method greatly improves the colony diversity of GA and compared to genetic algorithm. The results show that the immune algorithm performs better in aspect of global and local search ability and search speed.