文摘
高精度的导航和监视系统是至关重要的,以确保高效的船舶路线规划和海上安全。基于现有船舶导航和海上碰撞预防规则,避碰路径规划的一种改进方法利用微分进化算法。仿真结果表明,该算法能够显著提高优化线路过电流的方法。它有可能被用作工具来生成最优船路由的存在冲突。
1。介绍
避碰技术日益成为相关领域的海上运输,确保安全(1]。这些技术支撑三个关键组件:导航和监控技术和优化逻辑。技术,如差分全球定位系统(DGPS),自动雷达标绘援助(ARPA),自动识别系统(AIS),和电子海图显示与信息系统(航行)显著提高定位和监视性能。此外,优化和决策理论近年来迅速发展2,3),使更好的船轨迹的计算多支环境。这些包括人工智能算法如遗传算法(GA)(见[4,5]),蚁群算法(ACA)(见[6,7(见[]),模糊决策方法8- - - - - -10]),以及各种其他方法(11- - - - - -15]。Smierzchalski提出进化算法模型船的轨迹在碰撞情况下(见[16,17])。然而,计算效率较低使这种方法的实际应用问题。灵感来自于迷宫路线算法(18),提出了一种实用模型由Chang et al。19]在避碰决策问题转化为一个路线距离优化问题。Szlapczynski [20.)该模型提高了占船舶操纵特点,为COLREGS(国际海上避碰规则)和通过引入其他操作约束(例如,减速能力)。在[21- - - - - -23)的一组安全的概念(尽管通常不是最优的)轨迹,提出了基于防撞path-searches场景涉及多个船只和固定约束。这些软计算方法不仅可用于寻找最优路线从港口到港口,但也避免碰撞24,25]。
然而,解的质量和收敛时间的电流优化方法通常不能满足实际应用。此外,另一半的挑战依然存在,包括占避碰的法规,以及导航和可操作性因素。此外,计算效率和适应能力限制水域中的动态目标饱和状态需要进一步提高。为了解决这些问题,介绍了一种改进微分进化算法。
本文地址上面的一些限制通过开发一个修改社区微分进化算法(MNDE),与全球和当地社区。差分进化(DE)算法Storn首次引入的特性和价格(26),导致显著的变异与改进的性能27]。这些算法是为了解决多目标问题,约束,大规模优化问题。分析表明,他们的表现在准确性方面,健壮性和收敛时间明显优于GA, ACA和粒子群优化(PSO)算法(28,29日]。
部分2提供了一个简短的提纲的基本DE算法的家庭。部分3介绍了提出了微分进化的变异与全球和地方社区(DEGL)算法,和部分4描述开发算法的性能。该算法应用于部分5船舶避碰路径规划和结果进行了分析和讨论。
2。最先进的微分进化算法
德是一个基于造型群体行为的进化算法,它使用优化技术基于种群内个体之间的合作与竞争。德是基于一个实际的代码贪婪遗传算法。与其他进化算法一样,德是基于以下几点:从一个随机生成的初始种群,根据一定的规则的操作(如变异、交叉和选择),最好的人保留一个迭代过程后占每个个人的健身和消除了劣质个体,从而指导搜索过程在搜索最优解。
在数学上,德是一个简单的并行直接搜索法,试图找到全局最优解维实际参数空间。在这里我们表示适应度函数和定义的决策规则一个非空的有限集的搜索空间,从而导致如下优化问题: 德的目标是找到一个参数向量这样,适应度函数(目标函数)是最小化。假设每个元素的人口在德来标示,th向量的人口在这一代是表示为 在哪里是总数,最小化过程中是不变的。突变是由捐赠者向量基于两个随机选择的解决方案向量之间的区别;从这个意义上说,其突变如勘探模式搜索。德的交叉操作可以执行二项或指数的方式。德是基于全球人口的搜索策略,使用一个简单的微分变异操作和一对一的竞争生存策略。此外,DE特定记忆功能启用动态跟踪调整搜索策略搜索不需要问题的特点的详细知识。显示了较强的全局收敛能力和鲁棒性。
德的性能取决于正确的平衡全局探索和局部开发能力,显著依赖控制参数,包括人口规模、比例因子,交叉率。近年来,德的重要变量,如德家族Storn和价格(26,2710)由古典变异策略,发展。然而,提高突变策略不能完全解决DE弱点如过早收敛和局部收敛的可能性。例如,是一种最有效的突变策略提出Storn和价格: 在哪里是最好的个体向量和最好的健身(即。,lowest objective function value for a given minimization problem) in the population at generation。比例因子是一个积极的控制参数扩展向量的区别。在突变策略中,任意两个之间的区别这三个随机选择的向量扩展的因素生成相应的捐赠向量。全球最优搜索过程中是恒定的。对于每次迭代,所有的向量是接近最优的位置健身表面,导致快速收敛于最优解。然而,“发展”的能力可能会导致一些本地搜索的最优解空间,导致德失去全球搜索功能经过一系列的迭代。此外,DE算法采用“贪婪”选择规则(选择总是更好的目标向量和审判向量之间的向量),与一个固定的比例因子(通常选择的范围)。因此,如果向量产生干扰很小(单个向量相互接近时,通常人口收敛于一个小范围),单个矢量不会探索一个更好的搜索空间,,很难避免成为被困在一个次优的解决方案(30.]。为了解决这个问题,启发算法,Das et al。31日)提出了一个新颖的DE算法,DEGL(微分进化使用于社区的变异算子与全球和当地社区)。
在达斯等人的工作,一个策略类似于(3)采用设计两种类型的于社区的模型局部突变和全球突变分别使用全局最优向量在这一代给定人口成员变异。社区的概念来自于PSO算法。假设一个给定的微分进化种群与半径,一个社区(是一个非零的整数在区间内吗,在那里)被定义为每个向量。这导致一个社区人口。这里,采用环形拓扑结构,这两个相邻的社区是和。基于上述假设,Das等人给当地和全球于社区的突变模型如下。
当地的突变模型描述 在哪里代表社区人口的最优向量和。
同样,全球突变模型
最后捐赠向量DEGL结合当地和全球捐赠向量使用标量的体重:
当和,(5)将被转换为变异策略(见(3))。DEGL实际上是一个广义模型提供一个更好的平衡之间的局部和全局的策略。
3所示。一种改进的基于DEGL DE算法
DEGL模型的一个关键限制由达斯等人的全局最优搜索能力和收敛速度非常敏感这些比例因素的选择。的选择比例因子因此DEGL的性能优化的关键。如果规模因素小,干扰了人口可以忽略不计,导致算法过早收敛。因此,很难算法收敛到最小值。如果另一方面向量是接近全局最优的位置,一个较小的比例因子将有助于减少搜索时间,这大大有助于加快收敛速度。另一方面,一个大比例因子可以有利于提高个体的多样性变异的过程中;因此,过早收敛可能被避免,但收敛速度为代价的。
为了解决使用固定比例的限制因素,从而提高DEGL的性能,在本文中,我们提供了一个新变种,称为MNDE(修改于社区的变异算子DE)。介绍了两个关键的小礼品:首先,我们采用变量缩放抖动因素而不是固定比例因子来提高收敛性能;其次,全局最优个体向量是用于替换第一个项目在全球突变模型,大大加快收敛速度。
MNDE结合当地的突变模型和新的全球突变模型,重新定义全球突变模型 在这里,和变量缩放抖动因素基于固定比例因子,用于规模差别向量生成相应的捐赠向量变异策略。取代了固定比例因子变量缩放抖动因素可以有效地保持种群的多样性在全球社区模型;此外,收敛速度明显提高。更具体地说,当变量比例因子相对较大,个人倾向于样本不同区域在全球最优搜索的搜索空间,从而防止人口陷入局部最小值。同时,较小的规模因素在全球最佳的第二步搜索帮助调整运动试验解决方案的第一步,并允许更好地探索的室内空间怀疑全球最佳谎言,因此允许人口收敛到全局最优的解决方案。
比例随机抖动抖动因素在一个小社区的固定比例因子。换句话说,一个小扰动介绍修改比例因子增加人口的多样性,从而避免与先进的DEGL可能过早收敛观测。抖动因素计算 和给出了比例因子的总和和维随机矩阵,在那里和个人向量和的尺寸吗通常对应于优化问题的维数。我们引入控制参数调整比例因子的抖动范围为了维护开发和探索的性能。如前所述,如果比例因子太小,向量的区别非常小(即。,individual vectors are very close to each other, typical during population convergence to a small domain), and the individual vectors would not explore a better search space, making it difficult to avoid becoming trapped in a suboptimal solution. Under these circumstances we choose a larger产生一个更大的比例因子保持向量属于同一个社区的多样性。另一方面,如果比例系数太大,所需的迭代次数搜索全球最佳很大,延迟解收敛。我们因此减少控制参数生成一个合适的比例因子,以提高收敛性能。
第二个新奇的是,与DEGL算法,我们采用全局最优个体向量在目前这一代作为全球第一项突变模型。全球突变模型用于指导变异策略,变异种群成员,提高了收敛能力特别是在全球多峰优化。选择最好的矢量在整个人口确保新的试验向量和小健身价值可能在附近的一个小的搜索空间生成全局最优的解决方案,从而提高收敛能力。此外,如果向量越来越接近全局最优解的位置,收敛速度加快,选择全球最优个体向量而不是当前的个人目标向量。
4所示。性能测试和分析
评估MNDE算法的性能,各种模拟进行。
我们选择古典基准函数(见表81)和使用三个DE算法包括DEGL相比,(简化为DE1),(简化为德)。硬件平台采用的是ThinkPad笔记本电脑配置Core2双核CPU, 2.10 GHz, 4 GB内存和64位Windows 7操作系统;2009软件MATLAB。对于每个仿真,算法都是独立运行40倍,和最优的解决方案,最糟糕的解决方案,意思是,标准偏差,平均处理时间(s)给定收敛阈值计算。
在这些模拟中,我们选择所有德变种的人口规模,一个比例因子,交叉率。DEGL,我们设置了固定规模的因素MNDE,抖动规模因素,在那里,附近的半径,结合标量重量在(8)是用来平衡全局变异策略和局部突变策略在搜索最优解。在优化的初步阶段,小有助于提高开发能力,而一个更大的吗提高了勘探能力在以后的阶段。在本文中,一个线性增量计划改变采用以实现全局优化。在这里,所有四个选手(即算法和相同的停止标准。,同样的最大进化迭代的数量)。对于每一个测试函数,个人向量进化搜索的限制范围内,表所示1。每个向量的维数,3000次迭代进行。当矢量演化的最佳解决方案测试函数的最优值是获得。
最优解决方案,最糟糕的解决方案,均值和标准差的best-of-run值的四个选手展示在表的算法2。平均所需的迭代次数达到相同的规定阈值健身表所示3的符号“-”表示算法未能达到规定的迭代阈值在3000。表2显示了改善MNDE算法相对于其他算法的性能。可以清楚地看到,这个解决方案发现其中MNDE算法是最精确的比较算法,这是由于使用的缩放抖动因素MNDE算法。可以调整缩放抖动因素本身根据当前解决方案在变异过程中;因此人口的多样性增强,因此,个人倾向于样本不同区域搜索空间的全局最优搜索过程中,防止人口陷入局部最小值。在大多数情况下,MNDE算法也跑得快和收敛更快,如表所示3选择最好的向量的,这是因为在全球突变操作策略。采用矢量在整个人口能确保新的试验向量和次要的健身价值可能在附近的一个小的搜索空间生成全局最优的解决方案;因此,该算法可以避免盲目搜索;因此,融合能力大大提高。
进一步说明MNDE的性能,两个基准函数被用来测试和评估算法性能在困难的条件下。
在下一节中,比较MNDE和其他DE变体。
。函数是一个典型的二维测试函数与一个峰值,这有一个独特的全球最低为0(1,1),如图1。四个算法的收敛特性DE1,德,DEGL, MNDE数据所示2和3。MNDE策略展品最短的收敛时间对于一个给定的阈值健身和最少的迭代次数达到全局最小值0。当我们使用全局最优个体向量作为全球第一项突变模型(7),MNDE策略明显更好的性能比DEGL进化的收敛精度和速度。
Rastrigin函数是一个典型的multipeak测试函数用来评估一个全局优化问题:
Rastrigin函数有一个全球最佳点在0和大量的局部最小值,如图4。例如,当,,有1771561局部最小值。
图5表明MNDE有显著的优势比其他算法搜索全局最优的解决方案。测试结果,MNDE策略后的收敛于最优点相对少量的迭代(DE1和DEGL策略相比,减少了近50%)的迭代次数。德战略无法找到任何解决方案在预定义的迭代次数。应该注意的是,当我们介绍扩展抖动因素和,MNDE可以有效地保持种群的多样性在全球社区模型,提高全局搜索DEGL。
5。应用于船舶避碰路径规划
在最近的研究中,研究人员调查的方法提高避碰路径规划性能的进化算法,例如,李[18和扎曼et al。10]。我们测试的动态船舶避碰路径规划方法改进的微分进化算法在本文开发的。
在本文中,我们使用一个方法测试性能类似于在李18和扎曼et al。10]。新方法在本文中GA相比,德,MNDE,使用相同的平台评估船舶避碰的性能。所有程序运行Visual studio 2008和MATLAB R2009混合仿真环境。表4给出了详细的设置和操作不同的算法。
我们简化健身功能来减少执行时间。经济和安全是最两船避碰路径规划的重要因素。在这里,我们选择最短的距离和最小威胁作为性能指标,产生以下最小油耗适应度函数:
适应度函数是由最小的威胁
总适应度函数可以表示为 在哪里是距离的路线,是燃油消耗模型,路线距离的函数。在这里,我们假设= 1,使燃料的成本线性路径距离成正比的。与此同时,表明与路径相关的威胁。注意重量系数允许平衡成本效率和安全性能。
使用设置和操作规则表4,我们假设目标船的过程中是固定的,和自己的速度和目标船只是常数,如表所示5。实验分析小说中描述的两种典型情况下COLREGS,即正面和穿越场景。避免操作以下三个最短避碰路径分别获得GA,德,MNDE算法。
场景1。无冲突避免场景(图6)。
场景2。正面碰撞场景(图7),要求自己的船通过目标船的右边。
场景3。一个穿越场景(图8),在自己的船需要通过目标船的左侧,避免通过目标船的前面。
在数据6,7,8、黑色、黄色和红色线生成的路线MNDE,标准的德,分别和GA算法。实线显示执行路线,而虚线显示当前时间的计划路线。
图6显示的实际和计划的路线在无冲突的情况下三艘船在开放水域。MNDE算法提供最短的路线计划和执行路线。
图7显示了正面碰撞场景在开放水域。在这个场景中,MNDE和标准DE算法明显优于GA算法。MNDE和标准,本船能够恢复原来的路线没有任何明显的延迟。
图8显示了一个穿越的场景。这里,我们再次看到MNDE提供比标准DE或更好的路线。MNDE所提供的解决方案和标准也比GA所提供的更可靠。
6。结论
一种改进的微分进化算法在本文开发的。它引入了变量的概念扩展抖动因素保持群体的多样性,加快收敛速度。变量缩放抖动因素使一个更好的权衡之间的开发和探索的能力通过控制参数。采用全局最优个体向量在全球突变模型,算法的收敛能力显著增强。基准性能测试与不同的功能和应用场景进行评估验证算法的可行性和有效性在解决动态路径规划问题。三种不同的算法(DE MNDE, GA)运行搜索理想动态路由基于gis技术的系统。结果表明,MNDE算法达到明显比其他两个算法更好的性能。未来的工作将会研究更复杂的场景,包括更多的船只,不同的船舶类型和速度设置,变量的天气条件和其他操作限制,交通状况,和船载设备。这将导致一个实用的智能支持系统的发展船舶导航。
利益冲突
作者宣称没有利益冲突。他们保证他们有任何财务或科学利益冲突对于本文中所描述的研究。
确认
这项工作是支持部分由中国国家自然科学基金批准号51379049,中央大学的基础研究基金(HEUCFX41302)。