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

《遗传算法及其在油料保障路径优化中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法及其在油料保障路径优化中的应用研究刚1，张仁平2曹(1．解放军76167部队保管队，广东韶关512133;解放军后勤工程学院军事油料应用与管理工程系，重庆401311)2．【摘要】路径探索算法是古老而常新的问题。在介绍遗传算法的基础上，通过一个简单例子详细分析用遗传算法解决油料保障路径问题。最后对算法结果进行总结和分析。【关键词】油料保障;路径优化;遗传算法【文章编号】1008-8032(2012)06-0046-03【中图分类号】E919【文献标识码】A探索和优化方法，适合于解决复杂系统优化问题。遗传算法作为一种实用、有效、鲁棒性强、适应性好

2、的优化算法，近年来发展极为迅速，已在函数优化、组合优化、生产调度、自动控制、机器人学习等方面得到广泛应用［2］。下面介绍遗传算法常用的几个基本概念。1)染色体(Chromosome):染色体由基因组成的遗传信息的载体，基因是指用一位二进制代码(0或1)表示的一个遗传因子，基因的数量就是染色体的长度。使用遗传算法时，需要首先明确染色体编码规则，明确基因的长度，把问题的解变成染色体。一个染色体就代表问题的一个解。2)群体(Population):每代染色体的集合称为群体，群体中染色体的数量称为群体的大小。使用遗传算法时，根据问题设置群体的大小，一般可设置为

3、10或20。3)适应度(Fitness):各个个体对环境的适应程度叫做适应度。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数，也是问题的目标函数。0引言在部队行军、交通运输、市政规划、最优选址等诸多方面，往往会遇到网络最优化问题，即路径优化类问题，其核心是求最短路径，包括含权路(指道路质量、类别、安全等所含不同的权重系数，下同)的最短路径。油料保障路径优化与其它路径优化问题存在不同之处:一是不仅仅要找一条最短路，很多时候需要同时找出最短路或次短路，为指挥员决策作参考;二是有时不仅要知道两个定点的最短路，而且要知道

4、某个定点到其它定点的最短路径;三是路径优化中可能寻找排除某一条或几条道路(可能被炸毁、冲毁)之后的最短路，这就需要在最短路中增加一些附加条件。因此，许多路径探索的传统经典优化算法，典型的有Dijkstra算法、Bellman-Ford-Moore算法、A*(也可读作A星)算法等等［1］，对于油料保障路径优化问题则显得有些力不从心。遗传算法是解决搜索问题的一种通用算法，其共同特征是:1)首先生成一组候选解;2)依据某些适应性条件计算候选解的适应度;3)根据适应度决定保留或放弃候选解;4)对保留的候选解进行遗传操作，生成新的候选解。遗传算法上述特征以一种特

5、殊的方式组合在一起:基于染色体群的并行搜索。这就使得遗传算法区别于其他搜索算法，像油料保障路径优化类的路径探索，遗传算法就是一个很好的选择。1.2遗传算法基本原理遗传算法类似于自然进化，通过寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的染色体进行评价，使适应度高的染色体有更多繁殖机会。在遗传算法中，通过随机方式产生若干个染色体，即假设解，形成初始群体;通过适应度函数对每个个体进行评价，淘汰低适应度的个体，选择高适应度的个体进行选择、交换和突变等遗传操作，经过遗传操作后的个体集合形成下一代新的种群，

6、依次类推。11.1遗传算法的基本概念遗传算法基本概念遗传算法(GeneticAlgorithm，简称GA)是模仿达尔文生物进化论和孟德尔遗传学机理的随机全局收稿日期:2012-09-14作者简介:曹刚(1979－)，工程师，主要从事军用油料的管理及研究。47第6期曹刚等:遗传算法及其在油料保障路径优化中的应用研究心就是首先生成一组染色体(候选最优路径)，根据指挥员意图确定目标函数，计算染色体的适应度，再根据适应度决定保留或放弃染色体，并对保留的候选解进行遗传操作，生成新的候选解，依次循环，找到一个或一组最优解。为了便于算法的理解和实现，下面举个例子加以

7、说明。1.3遗传算法基本步骤最简单的遗传算法操作主要有三种:选择(se-lection)，交换(crossover)和突变(mutatiun)。1)选择操作:从群体中选择某些染色体用于繁殖后代(生成新的候选解)，染色体的适应度越高，它被选中的概率就越大。2)交换操作:随机地选定一个位置，将两个染色体在该位置上交义互换，得到两个后代。例如，两个染色体分别为100和111，随机选定的位置是第二位，进行交换的结果是110和101。3)突变操作:随机改变染色体中某一位置上的遗传因子的值。例如，二进制串011在第二位上发生突变，变成001。突变可能发生在染色体的

8、任意位置基因上。通常发生突变的概率很小。从表现型到基因型的映射称为编码。遗传算法在进行搜索之前