遗传算法及其在油料保障路径优化中的应用研究

2012-08-13张仁平

重庆电力高等专科学校学报 2012年6期

关键词：优化

曹刚，张仁平

(1.解放军76167部队保管队，广东韶关512133;2.解放军后勤工程学院军事油料应用与管理工程系，重庆401311)

0 引言

在部队行军、交通运输、市政规划、最优选址等诸多方面，往往会遇到网络最优化问题，即路径优化类问题，其核心是求最短路径，包括含权路(指道路质量、类别、安全等所含不同的权重系数，下同)的最短路径。油料保障路径优化与其它路径优化问题存在不同之处:一是不仅仅要找一条最短路，很多时候需要同时找出最短路或次短路，为指挥员决策作参考;二是有时不仅要知道两个定点的最短路，而且要知道某个定点到其它定点的最短路径;三是路径优化中可能寻找排除某一条或几条道路(可能被炸毁、冲毁)之后的最短路，这就需要在最短路中增加一些附加条件。因此，许多路径探索的传统经典优化算法，典型的有Dijkstra算法、Bellman-Ford-Moore算法、A*(也可读作 A 星)算法等等［1］，对于油料保障路径优化问题则显得有些力不从心。

遗传算法是解决搜索问题的一种通用算法，其共同特征是:1)首先生成一组候选解;2)依据某些适应性条件计算候选解的适应度;3)根据适应度决定保留或放弃候选解;4)对保留的候选解进行遗传操作，生成新的候选解。遗传算法上述特征以一种特殊的方式组合在一起:基于染色体群的并行搜索。这就使得遗传算法区别于其他搜索算法，像油料保障路径优化类的路径探索，遗传算法就是一个很好的选择。