毕业论文移动版

1。2。1  遗传算法

   遗传算法（Genetic Algorithms）是一种源自于生物进化理论的原理而发展出来的一种应用于：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术等等的广为应用、高效的随机搜索能力和优化的方法。

根据达尔文的优胜劣汰生物进化论，遗传算法将要解决的问题仿真为一个生物种群进化的方式，通过复制、交叉、突变等一些操作繁衍后代，并逐步淘汰掉适应度值低（对环境的变化不能产生足够应激行为）的解，与此同时，保存适应度函数值高（能及时根据环境而变换自身的状态）的解。这样进化了数代后就能出现适应度值高的后代。

遗传算法有三个最基本的操作：选择，交叉，变异。

选择：选择一些染色体来产生后代。

交叉：两条染色体交换部分基因相互替换形成新的染色体，来繁殖下一代的两

      条新的染色体。

变异：在交叉过程中，下一代的两条新的染色体会有一定的几率发生错误。

   遗传算法是一类能应用于优化解决搜索寻优问题的一种通用算法，与其他智能算法相比具有以下几方面的特点：

   （1）遗传算法从优化函数解的串集之中搜索，搜索范围空间广，能有效全局则优。这是遗传算法与传统算法的最大区别。

   （2）遗传算法能够一起计算并处理群体内所有个体的数据，在对其进行评估，文献综述

   （3）通过给出的适应度函数来决定遗传算法下一步的操作，拓展了算法的应用。

（4）遗传算法采用概率的变迁规则来指导搜索方向。

（5）遗传算法通过利用在仿真过程中从空间外部所获得的信息来进行群体内部的全局搜索，选择生存强的个体得到适应环境的基因数据。

遗传算法通过计算所得后的初始解开始优化，将每一个初始解作为一个染色体，染色体之间在选择、交叉、变异等操作后不断进化保证后代比上一代更加强大，但在实际操作过程中，可能会出现后代比前代差既退化的情况发生，为避免我们把当前的基因最优的个体保留下来。在进行优化时，我们先将要优化的问题函数寻优范围转到遗传空间，即将该函数的解用染色体来表示，称其为编码，反之则称其为解码。因此优化后要对结果进行评价故其要回到函数空间进行解码。在进行遗传算法时，为模拟染色体中基因信息采用二进制编码，二进制的一串编码就代表一条染色体的基因。

1。2。2  蚁群算法

   蚁群算法（Ant Colony Optimization,ACO）,又称蚂蚁算法，是一种用来在图中寻找优化路径的几率型算法，它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于寻找食物过程中发现路径的行为。

图1-1蚁群算法原理图

     如图1-1所示在蚁群巢穴和食物之间有2条道路：巢穴-A-B-D-食物和巢穴-A-C-D-食物，其长度分别为4和6。每次单个蚂蚁只能移动一个单位长度。

   在 t=0 时刻，20 只蚂蚁从蚁巢出发移动到 A。在巢穴-A的路径上没有影响移动行为的外在因素，因此它们分别有10只蚂蚁走A-B和A-C道路。

   在 t=4 时刻，此时走巢穴-A-B-D道路的蚂蚁将会找到食物并开始返回。

   在 t=5 时刻，这两组蚂蚁会在D点相遇，此时在各自道路上的所释放的外激素一致，因此这两组蚂蚁仍然沿着来时的道路返回巢穴。

在 t=8 时刻，走巢穴-A-B-D的5 个蚂蚁已经回到巢穴，与此同时在 A-C、C-D 和 A-B 这三条道路上都有5个蚂蚁还是移动。 (责任编辑：qin)