基于蚁群算法的复杂空间电缆排布优化方法

初元红

摘要：在水下航行体或航空器的闭合空间内安装较多的电子元件、电路板部件和其他机械组件时，各个电子部件归总起来的多芯电缆排布问题比较烦琐复杂，合理的布线路径不仅可以使布线更加科学，最重要的是在该产品有苛刻的重量要求时，最短的布线优化可以最大程度的减轻系统的总体重量。通过选定狭小空间内的典型工作区域，并对该区域进行栅格化处理，应用蚁群智能算法，对该特定空间范围内的电线、电缆排布进行优化设计，可以使系统设计更加科学合理。

关键词：电缆排布；蚁群算法；栅格化；优化设计

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2018）28-0179-03

目前，在狭小复杂空间中的电路导线排布（如水下航行体内部）基本是按照技术人员的经验进行的。无论是细小电线的排布或者是组合电缆的排布，均未进行在长度方面的详细技术参数分析，仅具备基本的合理性，距离达到全面的科学性还有很大差距。如果要求技术人员对每根导线都进行对比分析，工作量将非常巨大，且效果不一定好。因此，需要一种能够合理优化布线设计的技术和理论来作为技术设计人员的辅助设计手段，使之能够在最大程度上缩短线缆长度，减轻系统重量，使设计更加合理科学。

仿生优化算法是人工智能研究领域中的一个重要分支，其中包括模拟生物界中自然选择和遗传机制的遗传算法，模拟蚂蚁群体觅食行为的蚁群算法以及模拟鸟类群体捕食行为的微粒群算法等[1]。各种群体智能算法目前在各个工业、军工和民用领域得到了广泛的应用。人工蚁群算法是一种新型的模拟自然界真实蚁群的觅食行为而形成的模拟进化算法，该算法是由意大利学者M.Dorigo等人首先提出，被应用于求解分配问题，作业调度问题等，取得了较好的成果。受其影响，蚁群系统模型逐渐引起了其他研究者的注意，近来也被引入到人工智能的路径规划之中[2]。

1 蚁群算法优化原理

在蚂蚁寻找食物的过程中，总能找到一条从蚁穴到距离很远的食物之间的最短路径。每个蚂蚁事先并不知道食物在什么位置，只是在本身能够看得见的局部范围内搜索，在搜索过程中将以一定的概率向其他蚂蚁留下的信息素浓度高的方向移动，同时自己也释放信息素，信息素的浓度与经过的路径长度成反比，同时所有蚂蚁的信息素将会以一定的速率挥发，经过一段时间的搜索，最短路径上的信息素将会越来越浓，按照最短路径移动的蚂蚁将会越来越多，进而形成一个正反馈，使得它们可以找到最短路径[3]。

路径规划是蚁群算法最常见的任务之一。根据对环境信息掌握的程度的不同，路径的规划基本上可分为两种类型：一个是基于环境完全信息的全局路径规划，另一个是基于传感信息的局部路径规划。其中局部路径规划按工作空间模型表达方法的不同存在三种比较典型的环境建模方法：构型空间法、自由空间法和栅格法。

栅格法是平面运动路径规划的一个抽象模型，是目前研究最广泛的路径规划方法之一。栅格法是由M.B.Metea首先提出的[4]，用于解决分等级地形的自动化路径规划问题。它将工作环境分解成一系列具有二值信息的网格单元，工作空间中障碍物的位置和大小一致，并且在运动过程中，该物的位置和大小不发生变化。用尺寸相同的栅格对机器人的二维工作空间进行划分。栅格的大小以任务目标自身的尺寸为参照，自由空间和障礙物均可表示为栅格块的集成。问题可以进一步具体化为：初始时，任务目标未知栅格图的格子信息，但是，任务目标具有感知能力与记忆能力，对于所处位置的邻接栅格信息可以感知，对于感知到的栅格信息可以记录。模型首先是要任务目标从给定栅格图的起点，绕过障碍，找出通往终点的路线，要求极小化该路线所经过的栅格数。

1.1 工作空间

在某个水下航行体需要布线的局部区域，选择比较典型的空间作为本方案的分析目标。图1是一个小工作区的模拟图，图中包括了电路板、电源、机械构件和其他组件等，分别布置在同一个平面内。

1.2 栅格化工作空间

为进行蚁群算法需要对图1所示工作空间进行栅格化，将图中各个元件和空余位置收纳到栅格内。将该区域有元器件或组件的位置设定为障碍物，根据尺寸对比，合理设计栅格。栅格化得到图2的25×25栅格地形图结果。

在软件中建立25×25地形图矩阵，1表示障碍物，0表示可布线空间。矩阵化后如矩阵G表示。

在栅格地图中，每一个栅格相当于一个节点；而在一条路径中，各个栅格是相邻的。对于有障碍的地图，障碍栅格和任何栅格都不相邻。

利用矩阵表示的栅格如下：

观察图3中矩阵G，可以看出矩阵元素为1时，即为障碍物所在位置，矩阵元素为0时，对应空白区域。

1.3 蚁群算法

蚂蚁系统是经典的蚁群算法。其搜索过程如下：

在初始时刻，[m]只蚂蚁随机放置于首发栅格中，各条路径上的信息素初始值相等，设为：[τij（0）=τ0]为信息素初始值，可设[τ0=mLm]，[Lm]是由最近邻启发式方法构造的路径长度。其次，蚂蚁[k（k=1，2，…m）]，按照随机比例规则选择下一步要转移的栅格，其选择概率为：

[pkij（t）=[τij（t）]α[ηij（t）]βs∈allowedk[τis（t）]α[ηis（t）]β，j∈allowedk0，否则] （1）

其中，[τij]为边[（i，j）]上的信息素，[ηij=1dij]为从栅格[i]转移到栅格[j]的启发式因子，[allowedk]为蚂蚁[k]下一步被允许访问的栅格集合[5]。

为了不让蚂蚁选择已经访问过的栅格，采用禁忌表[tabuk]来记录蚂蚁[k]当前所走过的栅格。经过[t]时刻，所有蚂蚁都完成一次周游，计算每只蚂蚁所走过的路径长度，并保存最短的路径长度，同时，更新各边上的信息素。首先是信息素挥发，其次是蚂蚁在它们所经过的边上释放信息素，其公式如下：

[τij=（1-ρ）τij] ，其中[ρ]为信息素挥发系数，且[0<ρ≤1]。

[τij=τij+k=1mΔτkij]，其中[Δτkij]是第[k]只蚂蚁向它经过的边释放的信息素，定义为：[Δτkij=1dij，如果边（i，j）在路径Tk上0，否则] （2）

根据式（2）可知，蚂蚁构建的路径长度[dij]越小，则路径上各条边就会获得更多的信息素，则在以后的迭代中就更有可能被其他的蚂蚁选择。

蚂蚁完成一次循环后，清空禁忌表，重新回到初始栅格，准备下一次搜索。

在蚁群算法的实现过程中，关键的步骤有三个：1）蚂蚁的移动操作，2）释放自身的信息素，3）信息素的更新操作。程序算法流程图见图4。

在栅格化工作空间和构造启发式信息矩阵后，蚁群算法按下述步骤进行：

第1步：状态初始化；

第2步：节点选取，下一步可以前往的节点；

第3步：转轮赌法选择下一步走法；

第4步：状态更新和记录；

第5步：记下每一代、每一只蚂蚁的觅食路线和路线长度；

第6步：更新信息素，判断循环或结束；

第7步：绘图输出。

2 优化结果

在图5中，选定布线起始点和终止点。以图3中栅格矩阵G为蓝图，运行预先编制好的Matlab程序，程序输出界面上将自动绘制最优路径线条。在G矩阵中第1行第1列对应栅格图的坐标（1，25）格，第25行第25列对应的栅格图位置坐标在（25，1）。在选择起始点为20（20，25），终止点为607（7，1）时，运行结果见图5。

图5为布线位置的优化计算结果。根据图中所示路径布线将实现最优布线路径。

3 结论

在水下航行体或空中航行体设计过程中，通常对整体重量有比较苛刻的要求，在狭小闭合的空间内安装较多的电路板部件和其他机械组件时，各个电子部件归总起来的多芯电缆排布问题比较复杂，人工布线难以达到科学合理。在满足功能要求的同时，布线两端路径最短的要求显得非常重要。经工作空间选择、空间栅格化、蚁群算法优化等步骤设计后，不仅可以使布线合理，最重要的是最短的布线优化可以最大程度的减轻系统的总体重量。至于设计时还要考虑到线缆直径、连接方式、电磁干扰等因素暂不涉及。

参考文献：

[1] 段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005：1.

[2] 张美玉，黄翰，郝志峰，杨晓伟.基于蚁群算法的机器人路径规划[J].计算机工程与应用，2005（25）：34-37.

[3] 杜利峰，牛永洁.蚁群算法在 MATLAB 中的实现[J].信息技术，2011（6）：115-118.

[4] M.B.Metea.Route，planning for intelligent autonomous land vehiclesusing hierarchical terrain representation[C].In：Prnc of IEEE Int Confon R obotics and Automation，1987：1947-1952.

[5] 史峰，王辉，郁磊，胡斐.智能算法30个案例分析[M].北京：北京航空航天大学出版社，2011：205-228.

[6] 春花，特日格勒，任哲明.關于蚁群算法的参数设置研究[J].内蒙古民族大学学报，2011（7）：402-404.

[7] 朱庆宝，张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人，2005（3）：132-135.

【通联编辑：张薇】