基于改进蚁群算法的邮船舱室模块移运路径规划.pdf
《基于改进蚁群算法的邮船舱室模块移运路径规划.pdf》由会员分享,可在线阅读,更多相关《基于改进蚁群算法的邮船舱室模块移运路径规划.pdf(8页珍藏版)》请在咨信网上搜索。
1、第52 卷第1期2024年2 月文章编号:10 0 0-38 7 8(2 0 2 4)0 1-0 0 0 1-0 7基于改进蚁群算法的邮船舱室模块移运路径规划造船技术Zaochuan JishuDOI:10.12225/j.issn.1000-3878.2024.01.20240101Vol.52 No.1Feb.,2024王炬成,赵学涛(江苏科技大学船舶与海洋工程学院,江苏镇江2 12 10 0)摘要:针对大型邮船舱室模块运输过程中存在的移运路线长、路线混乱、舱室模块易与障碍物发生碰撞等问题,提出应用加入动态搜索模型的蚁群算法对邮船舱室模块进行路线规划,为运输舱室模块提供清晰、便捷的移运路线
2、。对主竖区的障碍物进行分析,建立模拟实际工况的栅格地图,采用改进蚁群算法寻找移运路径。对不同位置所经过的栅格地图和蚁群数量进行动态调整。采用模拟退火算法寻找蚁群算法的参数。采用离散点分析确定移运路径的主、支通道。仿真试验结果表明,应用改进蚁群算法建立主、支通道进行舱室模块移运可有效提高舱室模块的运输效率。关键词:邮船;舱室模块;移运路径规划;改进蚁群算法;动态搜索模型;障碍物优化;模拟退火算法中图分类号:U671.4文献标志码:ATransport Path Planning of Cruise Ship Cabin ModuleBased on Improved Ant Colony Alg
3、orithmWANG Jucheng,ZHAO Xuetao(School of Naval Architecture&.Ocean Engineering,Jiangsu University of Science and Technology,Zhenjiang 212100,Jiangsu,China)Abstract:In view of the problems such as long transport path,chaotic path,and easy collision withobstacles during the transport of large cruise s
4、hip cabin modules,an ant colony algorithm with dynamic searchmodel is proposed for the path planning of cruise ship cabin modules,so as to provide the clear and convenienttransport path for the transport of cabin modules.The obstacles in the main vertical zone are analyzed,the gridmap simulating the
5、 actual working conditions is established,and the transport path is sought with the improvedant colony algorithm.The grid map of different locations and the number of ant colonies are dynamicallyadjusted.The parameters of the ant colony algorithm are sought with the simulated annealing algorithm.The
6、main and branch channels of transport path are determined with the discrete point analysis.The simulationresults show that establishing the main and branch channels for the transport of cabin modules with the improvedant colony algorithm can effectively improve the transport efficiency of cabin modu
7、les.Key words:cruise ship;cabin module;transport path planning;improved ant colony algorithm;dynamicsearch model;obstacle optimization;simulated annealing algorithm有重要的意义。传统的路径规划算法为遗传算0 引言法、人工势场法等 2-3,当前比较主流的算法为研究邮船舱室模块从航侧开孔进人至主竖区指A*算法、蚁群算法、神经网络算法等 4-6 ,其中,定安装位置的路径规划问题,对于减少邮船舱室模蚁群算法具有稳健性佳、全局搜索能力强、环境
8、约块运输所需时间、提高邮船舱室模块的安装效率具束表达简便等优势。基金项目:工业和信息化部高技术船舶项目(编号:MC-201917-C09)作者简介:王炬成(19 7 8 一),男,副教授,研究方向为船舶先进制造技术2学者们将蚁群算法用于各领域中。孙功武等 门提出一种新的启发式函数,用于水面无人舰艇的路径规划。濮明月等 8 提出结合遗传算法的蚁群算法,用于物流配送车辆的路径规划。游晓明等 9 提出一种动态搜索策略,用于机器人路径规划。吴雨婷等 10 1将蚁群算法用于安徽某公司的速冻蔬菜配送,并在实际应用中取得较好的效果。针对在大型邮船舱室模块运输过程中的移运路线长、路线混乱、舱室模块易与障碍物发
9、生碰撞等问题,通过应用加人动态搜索模型的蚁群算法、模拟退火算法对邮船舱室模块的移运路线进行规划加以解决,并根据实际情况进行进一步改进。对同一主竖区的舱室模块同时进行路径规划,分析区域内的障碍物,限制蚁群的搜索方向;对每个舱室模块所要行走的栅格地图进行动态调整;对主竖区内不能通过的区域进行优化;在确定每个舱室模块较优路径后,通过离散数据分析,确定主通道与各舱室模块行走的支路。蚁群算法参数 11是影响蚁群算法性能的重要因素,可采用模拟退火算法 12-13 获得。通过试验仿真,对改进蚁群算法在舱室模块移运过程中缩短舱室模块运输路线、移运路线清晰化、避免舱室模块与障碍物碰撞等方面进行验证。1算法研究1
10、.1加入动态搜索模型的蚁群算法蚁群算法是一种模拟蚂蚁觅食行为的模拟优化算法 5。蚁群算法主要步骤如下:步骤1:初始化。对蚁群算法所需的各项参数(信息素启发式因子、期望启发因子、信息素蒸发系数、信息素强度、初始信息素质量分数、蚁群数量和迭代次数等)进行初始化。步骤2:进行路径更新、禁忌表更新。(1)根据蚁群算法概率公式 6 采用“轮盘赌”的方式选择下一个行走城市(栅格)。概率公式(城市i至城市i的概率)为P式中:t为城市i至城市j的信息素强度;为城市i与城市i之间距离的倒数;、分别为信息素启发式因子和期望启发因子,均为常数。(2)更新禁忌表。将走过的城市进行记录、删除,保证接下来的路径不会再次选
11、择该城市。(3)记录路径。包括到达终点和未到达终点的造船技术第52 卷第1期行走路径,完成一次路径游历。(4)信息素增强。每只蚂蚁在行走路径到达终点时会在该路径上的城市残留信息素,对路径上的城市起到信息素增强的作用,未到达终点的路径不进行信息素增强。信息素增强公式为t i;=Q/L式中:ti为城市i至城市i的信息素增强;Q为信息素强度,为常数;L为需进行信息素增强路径的总长度。步骤3:更新信息素。在所有蚂蚁均完成一次路径更新后进行全局信息素更新,包括信息素挥发与信息素增强。信息素更新公式为Tau=(l-p)Tau+t式中:Tau为全局信息素质量分数,用于指导下一代蚁群路径的选择;为信息素蒸发系
12、数,为常数;t为某一代中所有到达终点的路径的信息素质量分数增强之和。步骤4:重复上述3步,完成迭代,输出最优路径。通过加人动态搜索模型对蚁群算法收敛速度慢、易陷入局部最优等问题进行改进。(1)根据初始位置与终止位置的相对位置,对蚁群的斜格移动进行限制。(2)信息素质量分数更新过程设置惩罚系数,通过动态搜索模型控制信息素质量分数的更新。动态搜索模型为Q-L+1)LL(Lm+1)T h=(Q/Lkr,式中:t为到达终点的第k代、第r只蚂蚁在完成一次路径游历后在路径上的残留信息素;L为第k代、第r只蚂蚁在完成一次路径游历后的路径长度;Lmin为迭代至某一代前所有代中的最小值。(3)由于算法本身的特点
13、,在迭代至2 0 次以后会出现相对较优路径所在栅格的信息素质量分数(1)远大于其他栅格,使蚁群算法丧失活跃性,向局部最优进行迭代,因此设置最低质量分数下限,使算法不仅可依照信息素质量分数差寻优,而且可保留一定的活跃性,增强算法的纠错能力。设置全局信息素质量分数下限为10-3。1.2模拟退火算法模拟退火算法以统计物理为基础。算法的核心(2)(3)Lkr(Lmin+1)(4)王炬成,等:基于改进蚁群算法的邮船舱室模块移运路径规划3是以一定的概率拒绝局部极小值问题解,从而跳出局部极值点继续开采状态空间的其他状态解,进而得到全局最优解 1-13模拟退火算法主要步骤如下:(1)初始化参数。将初始温度、温
14、度下降速率、温度下限、解空间(迭代次数)进行初始化。(2)产生一组初始解。获得一组参数,输人改进蚁群算法获得一组最短距离,作为初始解Ibest,用于后续与新解进行对比。(3)产生一组新解。获得一组新的参数,获得一组新解Ibes,将新解与初始解进行对比。(4)初始解与新解进行对比。若新解比初始解更优秀,即I0,则记录该组新解并将其更新为初始解,为后续与新的新解进行对比。若新解不如初始解优秀,即I0,则按照模拟退火概率公式进行概率跳跃,选择是否更新初始解。一开始温度很高,选择更新初始解的概率就会很高,算法在解空间中活跃地寻找优势解;随着温度降低,选择更新初始解的概率降低,算法的活跃程度下降,趋于稳
15、定。模拟退火概率更新公式 13 为P=eI=I b e s t -Ib e s t 1式中:I为新解与初始解之差;T为当前温度。(5)更新温度。重复步骤(3)和(4),直至达到迭代次数,随即更新温度。(6)重复步骤(3)步骤(5),直至达到最低温度,输出符合条件的参数组合。2舱室模块移运路径优化舱室模块移运是舱室模块完成吊装与舱室模块安装的中间操作。重点解决舱室模块在移运过程中遇到的问题,并使用算法进行移运路径规划。改进蚁群算法虽在处理复杂环境下的路径寻优与旅行商问题(Traveling Salesman Problem,TSP)同样表现不错,但其并未将舱室模块大小、主竖区面积、障碍物的相对位
16、置等因素考虑进去,因此需在该算法基础上对栅格地图、蚁群移动规则、障碍之间相对距离和不同舱室位置行走的栅格地图进行优化。2.1建立栅格地图以某一中型邮船的主竖区为例,分析其中障碍物,包括不可移动的立柱、安装舱室模块的三角区和一些角钢等。布局主要为有楼梯间和无楼梯间。大型邮船的主竖区中间可供游客行走、游玩的区域更大,因此在两种船舱布局的基础上进一步扩展使其适用于更多的邮船舱室模块运输。根据两种布局主竖区类型分别对其进行栅格地图建模,尺寸分别为15mX30m与 2 1 mX30 m。在15 mX30m的主竖区,可搭载10 个舱室,每个号位代表舱室模块6 mX3m的安装区域和安装顺序,每一小格表示主竖
17、区内0.5m0.5m的方形区域,用于计算移运路径和表示障碍物区域,人口位置一般位于10 号位与14号位处。主竖区布局与栅格地图如图1所示,其中,栅格地图的横、纵坐标表示栅格的数量。(a)布局1比例尺:10:13010号位9号位(5)8号位(6)107号位06号位0102030405060栅格数/个(c)主竖区地图I图1主竖区布局与栅格地图建模2.2蚁群的移动规则由于一层甲板的主竖区内并不会有太多障碍物,因此可对蚁群的前进方向进一步限制。舱室的入口与安装位置的相对位置一般包括正右方、正下方和右下方等3种。在舱室位置处于前两种情况时,蚁群只进行上、下和右的转移,即在较为空旷的地图上,舱室模块只能前
18、进不能后退。在舱室位置位于安装位置右下方时,可进行斜格移动,通常分为4种情况,如图2 所示,其余情况不发生斜格移动。图2 舱室位置位于右下方蚁群的移动规则(b)布局2比例尺:10:15号位404号位3号位4号位2号位3号位201号位2号位10号位109号位1号位08号位0102030405060栅格数/个(d)主竖区地图II7号位6号位5号位4号位3号位2号位1号位4在前进路上遇到障碍物,为避免刮擦、碰撞等情况发生,无法采取斜向移动方式(见图3中的)通过,可采取绕行方式躲开障碍物(见图3中的。图3前进方向遇到障碍物示例2.3障碍物优化在两个障碍物的间距不足以通过舱室模块时,需对栅格地图进行优化
19、。根据舱室模块体积,在两个障碍物的行间距 6 行且列间距6 列时,将栅格地图上两个障碍物所围成的矩形内的栅格均设为障碍物。例如:在行间距为2、列间距为5计算栅格间距时,将3行6 列范围内的栅格全部设为障碍物,即舱室模块不会通过该区域,如图4所示。0100000070111111000000000011111000000010101111110图4障碍物优化规则2.4栅格地图和蚁群数量动态调整在同一主竖区,不同的舱室模块所处的位置不同,按照安装顺序,在寻得上一个舱室模块的最短路线后,表示该位置已安装舱室模块,然而蚁群算法在计算栅格间距时依然会包含该位置,因此该位置需进行优化。根据主竖区的栅格地图
20、,在寻得下方的舱室模块最优路径后,会影响上方舱室模块的最优路径寻找。由于上一个舱室模块所在行对应的栅格对于其上方的舱室模块寻优是一个较大干扰,因此对这一部分需进行优化。栅格地图的动态调整主要分为两个方面:(1)在寻得一个舱室模块的最优路径后将该位置栅格全部变为障碍物(将该部分的0 变为1),保证后续最优路径不会通过该位置,该变化只用于后续其他舱室模块路径规划的计算,并不会显示在最终的栅格地图上。以一个3行6 列的舱室模块为例,在该模块寻得最优路径后将其设置为障碍物,如图 5 所示。(2)根据需进行路径规划的舱室模块的终点位置,对栅格地图可行走区域进行限制。栅格地图动态调整如图6 所示。造船技术
21、第52 卷第1期100000000000000000图5某舱室模块寻得最优路径后的地图优化18126102030405060栅格数/个(a)目标舱室位置图6 栅格地图动态调整示例随栅格地图变化的还有蚁群数量,对于一个主竖区的两列舱室模块采用不同的蚁群数量计算公式。在地图调整后,靠近舫侧开孔的舱室模块由于栅格数量远小于远离开孔处的舱室模块,因此蚁群数量为其舱室模块中心位置所在行的10 倍;而远离侧开孔的舱室模块,蚁群数量为其舱室模块中心位置所在行的2 0 倍,同时设置下限为30 0。舱室模块蚁群数量更新公式为rd=10E,E;300,E,6d=300,d300式中:d为蚁群数量;E;、E,分别为
22、舱室模块中心位置栅格所在的行和列。2.5蚁群算法的初始参数每个主竖区在寻找不同舱室模块的最优路径时,栅格地图会动态变化,每个舱室模块所需的参数会不同,且后期舱室模块数量较多,单个舱室模块寻找参数不仅困难而且消耗时间。为方便计算,采用模拟退火算法寻找一组相对通用的参数组合。参数组合计算过程:参照以往文献给出的蚁群算法,参数范围适当扩大,作为模拟退火算法的参数范围;模拟退火算法在给出的范围中随机生成参数组合并输入舱室模块移运算法,该参数组将用于所有舱室模块的路径寻优;记录所有生成路径和作为模拟退火算法的解,待退火完成,生成较为稳定、通用、适用于多舱室模块路径规划的蚁群算法参数组合。2.6改进蚁群算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 算法 邮船 舱室 模块 路径 规划
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。