智能优化算法-遗传算法

智能优化算法--遗传算法

什么是智能优化算法？

智能优化算法是一种启发式优化算法，通过程序来模拟自然界已知的进化方法来进行优化的方法，比如模拟生物进化的遗传算法，模拟自然选择进行筛选，逐步归向最大值，包括遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法、粒子群算法等。·智能优化算法一般是针对具体问题设计相关的算法，理论要求弱，技术性强。一般，我们会把智能算法与最优化算法进行比较，相比之下，智能算法速度快，应用性强。遗传算法（GA）

遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的操作算法(1)复制或选择算子：将父代的个体原封不动地传递到子代,在复制过程中,每个个体是按照适应度值的大小决定其能否被复制到下一代的概率,复制算子可使群体中的优秀个体数目逐渐增加,使进化过程向更优解的方向发展,反映了自然界中优胜劣汰的法则.:（3）变异算子：复制和交叉算子只能在现有基因型的排列组合内寻找最优，而不能产生新的基因型，变异算子可使基因型发生变化，从而扩大寻优范围。(2)交叉算子：上面的复制算子只能在现有群体中寻找最优，而不能产生与父代不同的个体，交叉算子可使同一代的某对个体间，按一定的概率交换其中的部分基因，从而产生新的基因组合，可望获得比父代更好的个体。遗传算法优化

遗传算法具有很强的鲁棒性，而且所需的领域知识少，应用范围广泛，但它具有一个根本的缺点——过早收敛。由于遗传算法中选择及交叉等算子的作用，使得一些优秀的基因片段过早丢失，从而限制搜索范围，使得搜索只能在局部内找到最优值，而不能得到满意的全局最优值。优化方向：1）对选择，交叉和变异算子的改进2）改进控制参数；种群规模，交叉概率Pc，变异概率Pm1自适应参数调整令fmax代表某一代种群中最优个体的拟合度，令F代表此代种群平均的拟合度，则Δ=fmax-F，诺Δ越小，表示种群个体拟合度差别较小，达到局部最优和过早收敛可能性越大；反之，Δ越大，个体特性分散，拟合度差别较大。Pc和Pm参数由Δ决定，且

pc=k1/(fmax-F)(1)

pm=k2/(fmax-F)(2)在调整过程中，当种群趋于收敛时，提高Pc和Pm，破坏当前的稳定性，克服过早收敛；当种群个体发散时，降低Pc和Pm，增加开发能力，使个体趋于收敛。但，当已收敛到全局最优时，此时误判别函数，从而使得Pc和Pm增大，最优个体遭到破坏的概率也增大，使得GA性能下降。

在克服过早收敛和避免优秀个体被破坏之间选择折衷方案：

pc=k1(fmax-f′)/(fmax-F),f′≥

F

(3)

pc=k3,f′<F

(4)

pm=k2(fmax-f)/(fmax-F),f≥F

(5)

pm=k4,f<F

(6)f为变异个体的拟合度，f′为两个交叉个体中拟合度大的k1，k2，k3，k4≤1.0，并为常数

对于k3，k4由于此时f′<F或f<F，即个体拟合度小于平均拟合度，说明个体特性差，因此增大Pc和Pm，易使差的个体破坏的可能性增大，因此，k3,k4的值应大一些，而k1,k2可依据实际情况而定2

多种群进化

将原种群按特性划分为几个子种群，每个子种群有各自的特点具有不同的Pc和Pm，不同的种群规模，具有不同的进化策略和算子，个体的特性分布也不同。这样通过不同子种群之间的进化，可以选取和保留每个种群的优秀个体，避免单种群进化产生的过早收敛现象，同时又可以保持优秀个体的进化稳定性。另外为了使每个种群进化的灵活性，在Pc和Pm的设置时，不再像以前那样将它们设为常值，而是根据种属的实际情况，使其自动调整参数值。遗传算法的应用基于遗传算法的移动机器人动态避障路径规划方法动态路径的规划要求：路径在路边之内、能动态避障和路径最短(1)路径在路边之内路边约束限制了解空间的范围,即各个y;值只能在路边约束范围内取值,各个点的y值取值范围的确定方法如下:在图2中,首先计算出各个x;位置与x轴垂直的各直线与路两边折线相交的两个y坐标值,然后再分别向路中心收缩一定量,收缩量的确定是按照机器人中心必须远离路边的安全距离确定的,显然安全距离应大于移动机器人的最大半径,设确定的yi的取值范围是(y,l,y2)因此路边约束的适应度函数flt1可表达为式中i为路径上的所有点上式表明只要各个路径点在离路边的安全距离之内,则适应度为1,否则为0,这样确定是比较符合实际情况的.(2)能动态避障

动态避障是比较关键的一个约束条件,假设障碍物的个数、障碍物的位置和速度信息可由机器视觉和激光雷达确定;在局部动态路径的规划过程中,假设移动机器人以当前的速度行走,各障碍物也以当前测定的速度做匀速直线运动,因为控制周期一般小于500m、,此外,路径跟踪控制算法会自动控制机器人行走速度的变化,因此在路径规划过程中,可以不考虑机器人和障碍物行走速度的变化.动态避障的基本条件是,对于某一路径,组成路径的各点与各障碍物之间的最小距离必须大于机器人与障碍物的半径之和.可得动态避障的适度函数fit2为Dmin为于任意一条路径,路径上与障碍物的最短距离（3）路径最短路径最短的适应度函数确定如下：最后综合得到遗传算法的综合适应度函数为最后综合得到遗传算法的综合适应度函数为该综合适应度函数把三个约束条件有机融合在一起,计算简单,且能避免三项加权求和引起的优化不稳定问题复制算子:同传统复制算子一样,即采用与适应度成比例的概率来选择个体.为了保证最优个体在进化过程中不被破坏,新一代群体中适应度最小的个体可以直接用上一代的适应度最大的个体取代交叉算子:与传统的交叉算子类似,交换的位置和交换的点数是随机确定的.变异算子:其作用是在个体结构一定的前提下,加人随机扰动,以寻找最优解,本文采取加人零均值高斯白噪声的方法.

此外,为提高初始种群的优良性能,在随机产生初始种群的过程中,加人初选评估程序,即对随机产生的初始种群考察其路边约束和动态避障的适应度值,由此保证初始种群中满足路边约束和动态避障条件的个体数目大于一定的数量,这样可保证遗传算法快速、稳定地找到全局最优解.参考文献1《基于克服过早收敛的自适应并行遗传算法》——周远晖,陆玉昌,石纯一2《基于遗传算法的移动机器人动态避障路径规划方法》——李庆中顾伟康叶秀清PPT模板下载：/moban/行业PPT模板：/hangye/节日PPT模板：/jieri/PPT素材下载：/sucai/PPT背景图片：/beijing/PPT图表下载：/tubiao/优秀PPT下载：/xiazai/PPT教