路径规划的智能算法主要有遗传算法、模拟退火算法、蚁群算法等。 1.遗传算法遗传算法( Genetic Algorithm,GA)是目前自主车辆路径规划中常用的一种算法。它是利用达尔文的生物自然遗传选择和生物自然淘汰的进化来实现的数学模型。遗传算法源于自然进化规律和遗传基因学,并且拥有“生成”与“检测”这种迭加顺序的査询算法。遗传算法把整个蚁群当中每个成员作为研究对象,而且通过随机化方法去控制当前被编码的参数空间进行查询。遗传算法的主要流程是选择、交叉、变异。遗传算法可以直接对蚁群对象操作,没有必要考虑函数导数与连续性的限制。遗传算法内部存在良好并行处理能力和优秀的全局查询特色。 遗传算法通过概率化的方法,能自动获得查询空间,自动地改变查询方向,不需要有明确的规定。遗传算法目前已成为较新颖的查询方法,它的计算方法不复杂,高效、实用,而且有较好的鲁棒性,适用于并行处理领域。 遗传算法步骤如下。 (1)初始化 设定起始群体P(0),生成N个个体,设定进化代数变量t=0,设定T最大进化代数。 (2)个体评价 获得群体P(t)中每个样本的适应度(3)选择计算 选择是为了把优秀的个体或通过交配产生新的个体传到下代。 (4)交叉计算 将最核心的交叉算子作用于群体。 (5)变异计算 把总群中的每个个体的一些基因座上的基因值改动。种群P(t1)是种群P(t)历经选择、交叉、变异产生的。 (6)结束判断 当t=T时,停止计算,输出具有最大适应度的个体。 2.模拟退火算法
模拟退火( Simulated Annealing,SA)算法是求解规划问题中的最优值,方法是利用热力学中经典粒子系统的降温过程。当孤立的粒子系统的温度缓慢降低时,粒子系统会保持在热力学平衡稳定的状态,最终体系将处于能量最低的情况简称基态。基态是能量函数的最小点。模拟退火算法能够有效地解决复杂的系统优化问题,并且限制性约束较小。
模拟退火算法步骤如下。
3.蚁群算法蚁群算法( Ant Colony Algorithm,ACA)寻找最优解是效仿了真实蚂蚁的寻径行为,利用蚂蚁之间的相互通信与相互合作。蚁群算法与其他进化算法的相似之处:首先都是一种随机查找算法;其次,都是利用候选解群体的进化来寻找最优解,具有完善的全局优化能力,不依赖于特定的数学问题。
通过蚁群算法求解某些比较复杂的优化问题时,则将体现出该算法的优越性,同时蚁群算法自身也具有不少缺陷。蚁群算法具有以下优点。
①蚁群算法在优化问题领域具有很强的搜索较优解的能力,因为它能够把一些常用的分布式计算、贪婪式搜索等特点综合起来,并且是一种正反馈机制的算法。想要快速地发现较优解,可利用正反馈机制得到;而过早收敛现象可由分布式计算来排除;这样在査找过程的前期,就会找到可实施的方法,同样,若要减少查找过程消耗的时间,可通过贪婪式搜索来实现。
②蚁群算法具有很强的并行性。
③蚁群中蚂蚁之间通过信息素展开协同合作,则系统会有比较好的可扩展性。
蚁群算法也具有以下缺陷。
①蚁群算法需要消耗比较多的时间来査找。尤其是在群体规模较大时,由于蚁群中的蚂蚁活动是任意的,即使利用信息交换都可以找到最优路径,但在不是很长的时间里,很难发现一条比较好的线路。由于在刚开始寻找路径时,各线路上的信息浓度大小几乎是相同的,这样就存在一定困难。虽然利用正反馈方法反馈信息,能够让好线路上的信息量越来越多,但是需要消耗很长的时间间隔,才能使较多的信息量出现在较好的路径上,伴随正反馈的不断进行,会产生明显的差别,从而得到最好的路径。这一过程需要较长时间。
②当査找过程进行到一定阶段时,蚁群中蚂蚁查找到的解相同,很难能够再深层次去査找得到更好的解,使算法岀现停滞现象。
除了上述算法之外,还有其他很多算法,如基于广度优先搜索、深度优先搜索、最小生成树、神经网络、层次空间推理等。
