基于遗传算法的综合布线路径布局研究

时间：2024-12-22

陈超,陈振中

(1.江苏卓易信息科技股份有限公司,江苏宜兴 214200) (2.东华大学机械工程学院,上海 201620)

在5G技术和“互联网+”的新兴浪潮下,高速通讯网络已成为现代化生活和办公必不可少的内容. 作为通讯网络的载体,综合布线系统是当下智能化建筑内部通讯的中枢部分,综合布线的稳定和合理化运行是建筑智能化的重中之重,也是其他系统智能化的前提条件[1-2]. 随着数据网络的飞速发展,网络对布线的要求越来越高,而线缆的合理路径规划是保证智能化建筑整体性能和信号传输可靠性的重要前提.

相比于人工布线技术,智能优化布线技术具有较高的性价比. 由于实际中的布线施工需要考虑工期、质量、成本、安全等诸多因素[3-4],当前自动布线技术的优化算法尚不成熟,不能解决实际的需求. 计算机仿真技术的不断发展,为解决传统线缆布局质量不达标、布局效率低下、过于依赖设计人员的经验等问题提供了新的途径,其中线缆的布线设计在经历了计算机辅助人机交互阶段后,正在向自动化布局发展[5-6]. 近年来,国内外诸多学者开始将智能优化技术应用于综合布线的决策中. Wang等[7]使用蚁群算法对影响综合布线的指标约束进行了演化,对平面上的布线路径优化进行了研究,一定程度上优化了整体布线的设计,有效地降低了成本. 杜海遥[8]研究了机电产品中基于斯坦纳树和粒子群算法的布线优化方法,对斯坦纳树模型进行了创新,将布线路径问题转变为斯坦纳树的问题进行求解并提出了符合实际布线的最小生成树算法. 王树玉[9]以DNA遗传算法为基础开发了综合布线的辅助系统,针对顶点着色和最大独立集等高端需求进行了研究,不仅能够结合实际情况进行布线的统筹规划,还得到多种解决方案. 国外对于遗传算法的研究起步较早. 早在上个世纪,Srinivas[10]在研究多目标问题时,就首次提出了用遗传算法解决多目标问题. 近来,Sabyasachi等[11]利用遗传算法进行最优网络拓扑的研究,建立稳定的网络代理,进一步促进了智能优化算法的发展.

本文基于遗传算法对综合布线路径的优化设计提出新的解决方法,并将其应用于某新建医院智能化项目,以验证其实际效果. 该方法可根据工期和成本的需求调节相应的权重,并结合仿真系统自动生成所需的合理布线路径图,实现了综合布线的自动化设计.

1 综合布线路径规划分析及优化模型的建立

本文根据实际工程需求,进行综合布线的布局规划. 在某施工平面图中以X轴和Y轴进行点位的定位,模拟的路径也是沿着X轴与Y轴衍生出来的网格进行布置,网格设定为正方形,所以无需考虑远近端问题. 为方便后文中数学模型的定义,文中将X轴定义为i轴,Y轴定义为j轴. 如图1所示,先将某个施工平面图网格化,为便于观察,降低了网格的密度,在实际操作中网格密度可根据需要进行调节.

由图1可知,本文的优化路径设计是根据图中由英文和数字标识出的网格进行布置. 首先确定起始点,即弱电间的位置,为了便于观察和理解,起始点将被固定在图纸的中央底部位置,其余的终端点位将随机生成,然后在约束条件下进行布线路径的生成. 终端点位包含网络点、监控点、音响点3种不同类型. 同时,为了符合实际,还将随机生成障碍点,以模拟实际工程中不可穿越的立柱等障碍物.

本文的数学模型与一般的旅行商问题不同,本系统不是寻找一条经过所有点且每个点只被访问一次的路径问题,由于综合布线的每一条线路都是独立的,所以要分别考虑每一条线路的路径,还要根据不同需求确定其权重. 为便于设计及区别点位名称,将横轴设定为i轴,竖轴设定为j轴,这样即可准确地定位每一个点位在图纸上的位置,i和j取值范围分别为(0,I)和(0,J),以此保证模型的合理性. 其决策变量如下:

(1)

(2)

(3)

由于弱电间是固定位置,所以将起始点的数学模型设定在j轴最底端,即j=0,而i轴上的定位则根据网格的数量设置定位在中央,则:

xi0=yi0=zi0=1.

(4)

此外,还需设定其拥有相同的公共路径,即至少两个点位可同时使用的路径,则:

(5)

(6)

(7)

则整个综合布线路径优化问题的数学模型即为:

最短路径:

(8)

最大公共路径:

(9)

为方便函数的建立,应将最大公共路径由max问题改为min问题,也即公式前缀“max”改为“-min”,这样就可合并两个路径的数学模型. 在两种路径方式前加入权重ω,且两边权重相加为1,则目标函数即为:

(10)

对上述函数还应加入约束条件,以保证路径的生成能在正常范围内,路径优化系统能正常运作. 约束条件如下:

(1)路径约束:

(11)

式中,公共路径为两种及以上的线缆都会通过的共同路径,因此α、β、γ为独立点位路径的乘积.

(2)点位约束:

(1-xij)=(1-xi-1,j)(1-xi+1,j)(1-xi,j-1)(1-xi,j+1),

(12)

式中,具体点位的确定还应根据十字定位来约束,即该点位的位置应与网格图中上下左右4个点位的乘积相一致.

由上文公式所得数学模型是非线性的,根据“0”和“1”的决策变量也明确了此问题为非线性整数规划问题,这类问题通常是NP-HARD问题,目前并无有效的算法,所以仿真生成的布线路径与理论上的最优路径可能会有部分偏差. 这类问题的大型实例难以求解,只能寻求有效的启发式算法.

2 模型的多目标遗传算法优化设计

本文利用遗传算法进行优化设计. 遗传算法一般是基于目标函数的适应度值,由这个目标函数开始运算,并不需要其他类别的函数值信息,例如梯度等信息,因此面向大规模的、不连续的、高度非线性的多模态函数的优化,以及解决无解析表达式的目标函数等问题时通用性较强. 本文使用二进制编码方式,选择轮盘赌法进行遗传算法的设计. 首先对染色体进行编码,在实际操作中一条遗传染色体可以代表一组可行解,在满足题目约束的前提下,可初始化随机产生N组可行解以作为初始种群,初始种群经交叉变异等过程逐渐产生最优解[12-13]. 算法的执行过程如图2所示.

在定义基础算法后,可确定遗传算法的设计思路如下:

由于上述的数学模型为非线性函数,在设计优化模型程序时进行双目标规划,一个目标是求最大公共路径,另一个目标是求全程路径最小,在上文公式中统一为min开头,即可使两个目标的单调性一致. 由于该模型是双目标规划,处理双目标问题时利用权重法使两者统一,在优化模型程序中fitness计算即是根据上述函数进行的[14]. 具体步骤如下:

Step1初始化资源点集合F,其包含3类资源点,同时初始化地图G,随机生成起始点,定义算法的基本参数;

Step2建立初始种群,重复产生N=100个个体,选取其中适应度最好的个体加入种群,并按该方式建立个体个数为500的初始种群X;

Step3记录当前资源点染色体中的数据,并依据欧式距离计算出该方案所占用的几何距离,根据实际要求调整权重weight,转变成适应度函数所需的变量;

Step4按照已确定的交叉参数Pe,在当前种群集合中随机选取待交叉的个体集合Xe,随机生成位置l,并进行染色体交叉操作,按照已确定的变异参数Pm,在当前种群集合中随机选择待变异的个体集合Xm;

Step5采用确定性的选择策略,选取目标函数值最大的一部分个体进化到下一代,按照已确定的选择概率Ps,在当前已有种群中选取适应度最低的一部分个体,并将其淘汰;

Step6经上述过程,种群已进化成新的一代,在达到最大进化代数之后,即可选择出最优解,即适应度最高的个体,将其作为本模型的Pareto解.

3 工程仿真试验

本系统的优化理念是以建筑的施工平面图为基础进行布线设计. 为进一步了解基于遗传算法的工期费用综合优化模型的求解过程,并验证其有效性和可行性,本文以宜兴某医院智能化项目的工作层作为模型系统测试的对象. 该医院工程的主体为钢筋混凝土框架结构,总建筑面积约7.5万m2,主楼除一楼大厅外,皆为相同建筑构造且形状方正,因此可利用本系统进行布线路径试验.

根据上文的阐述,首先将施工平面图网格化,为方便观察、利于计算,将网格线按照16×16的样式进行布置,如需改变精度,可以变更网格线的密度. 楼层结构中的立柱位置是已知的,但由于医院结构的复杂性,许多障碍物如通风管道、设备支架等都是不可预估的,因此在测试时将障碍物设定为随机定位,增加优化难度的同时,也更符合实际的情况. 首先定位起始点,弱电间位置一般在设计阶段就已确定. 再明确各类终端的需求,这类终端可能是网络语音点,也可能是监控点或广播点,在此基础上规划出一条既能节省材料又能节省工期的最佳路线. 同时,也应考虑建筑物内无法穿越的障碍物,在实际的工程中这是不可避免的,因此综合布线的路径优化需能动态调整,才能满足实际施工需要. 根据前文所述内容设计出来的所有主程序思路与具体步骤,在程序运行后会自动生成一个网格状的坐标图,并自动生成出发点和终点及障碍点等,如图3所示.

在数学模型完善以及系统架构成型的基础上按设计要求分配目标1和目标2的权重,进行系统测试,以此验证最终效果. 分别修改权重参数为0.01、0.3、0.5、0.7、0.99,得出如图4～图8所示的路径图进行对比分析,并生成如图9所示的Pareto图.

从上述的仿真路径图可以看出,该路径优化系统能达到预定的要求,根据工期和成本的权重分配可生成直观有效的路径布局图,而Pareto图也证明了其实际效果能满足实际工程的需求.