一种求解绿色模块划分的蚁群算法研究

0 引言

模块化设计是实现大规模批量生产的关键技术，这种技术通过将大量的零件按照对应的属性进行模块组合，可以组合成不同功能和特性的产品，在一定程度上能满足客户特有的要求，同时为大批量的生产奠定基础，提高企业的效率。绿色设计是基于传统设计的层面上，面向产品整个生命周期内，考虑产品环保属性，比如通用性、升级性、回收性、维护性、处理性、污染性、耗能性，并将其以上作为设计目标，同时考虑产品功能结构特性，使得产品的环境友好性在最佳状态。

国内外不泛这方面的研究，文献[5]在确定产品整个生命周期的基础上，采用模拟退火算法进行模块化划分；文献[6]在考虑产品装配/拆卸性能方面，利用遗传算法实现了模块化划分；文献[7]引入聚类和模块密度等概念来进行模块划分。但是基于蚁群算法的求解，几乎是空白，由于蚁群算法有其收敛速度快的优势，能很好的解决大批量零件的模块化组合NP_Hard问题；基于此作者提出了一种绿色模块划分的蚁群优化方法，很好的解决了实际问题。

1 问题描述

一个双梁桥式起重机桥梁作为实例，°共有11 个基本单元:1.主梁、2.轨道、3.端梁、4.端梁栏杆、5.走台、6.走台栏杆、7.直梯、8.斜梯、9.司机室平台、10.司机室、11.检验平台；分别用T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11表示。将进行模块划分，划分成模块内聚合度最高，模块之间耦合度最低，同时绿色度最大。

2 相关知识和数据

2.1 数据表示说明

功能相关性便于将实现同一功能的基本单元聚合成模块，以提高模块的功能独立性。结构相关性便于实现每种功能所对应的模块在结构上的完整性。它们的相关程度是根据人的经验和知识进行数值来描述。假设功能相关性有属性很强强较强一般无，分别用10.0,8.0,5.0,2.0,0.0。结构相关性表示类似。零件的绿色性属性大部分用很好、好、较好、一般,差和无6个语言标度度量，分别用10.0,8.0,6.0,4.0,2.0,0.0ธ表示。

2.2 零件属性和相关性数据

假设基本零件单元有七个绿色属性，其中五个绿色属性：通用性、回收性、升级性、维护性和处理性是属性值越大绿色性越好；而后面两个属性：污染性、耗能性是属性值越小绿色性越好。

3 多个目标模型建立

3.1 模块耦合度和内聚度模型

设产品有N个基本单元，则两两模块的总关联度为 ，F 和S 为功能相关准则的权重系数和结构相关准则的权重系数，fij为功能相关值，sij为结构相关值。

4 问题求解

规划模型为式、式、式三个目标函数，分别是maxC1，minC2，maxG~ ；在此采用加权系数法把多目标转化为单目标求解求最大值，这是个NP组合问题，适合用提出的蚁群优化算法求解。

4.1 基本蚁群算法

蚁群算法的初衷是用于求解TSP问题，然后又有着色问题，作业问题等等组合问题。TSP问♪题非常类似于蚁群的觅食过程；基于TSP问题的基本蚁群算法步骤如下：

步骤1：初始化各个参数，设置最大迭代次数N，各个路径信息素ij，启发式参数值,等；

步骤2：循环迭代开始；

步骤3：将m只蚂蚁随机的放在n个城市上面；

步骤4：设置好禁忌表控制下一个访问城市，保存好访问的城市；

步骤5：根据状态概率公式来计算蚂蚁选择下一个城市j的概率，j是非禁忌表中的城市；

步骤6：选择具有最大状态转移概率的城市，并把该城市标记进禁忌表中，存好城市访问次序；

步骤7：若m只蚂蚁还没有访问完所有的城市，就转步骤5继续执行；否则转步骤8；

步骤8：采用蚁周模型，对路径上的信息素按式~式进行更新；

步骤9：若m只蚂蚁均迭代最大迭代次数则输出结束，否则☁清空禁忌表，城市访问次序表以及初始化相关值转步骤3。

4.2 提出一种求解蚁群算法

本文提出一种蚁群算法对绿色模块划分优化

进行求解，求解步骤如下：

步骤1：初始化各个参数以及矩阵值，蚂蚁数，迭代次数，初始化信息素；存储好功能相关性值、结构相关性值以及绿色性值；准备好禁忌表和访问表以及模块划分递增表。

步骤2：循环迭代开始。

步骤3：把蚂蚁随机存放在各个顶点上，在这里各个顶点是指各个可供选择的各个零件，同时记录好禁忌表和访问表以及模块划分递增表。

步骤4：按照式，选择转移概率最大的那个作为下一个选择，如果所得的转移概率大于随机数rand，则归为上一个顶点所在的模块，否则作为另外一个模块。

步骤5：如果每只蚂蚁所有顶点还没有访问完，则继续步骤3；否则步骤6。

步骤6：更新信息素，根据模块划分递增表所走过的路径，按照式~式对称添加信息素，同时考虑挥发因素；比如1112234456则相同的两个顶点之间添加信息素，跳变而不相同的相邻两顶点不添加信息素。

步骤7：迭代次数未完则转步骤2，否则结束输出最优解。

通过十次实验均获得收敛，该蚁群算法所均在一秒钟内完成算法的计算，同时获得收敛，收敛速度极快；最优适应值为26.000;最佳模块划分数值为1,1,1,1,5,5,4,4,4,3,2和5,5,5,5,1,1,4,4,4,3,2；最优模块划分为{主梁、轨道、端梁、端梁栏杆}为同一模块，{走台、走台栏杆}为同一模块，{直梯、斜梯、司机室平台}为同一模块，{司机室}为一单独模块，{检验平台}为一独立模块；这也符合文献[8]的结论和实际要求。

在十次实验中，无论改变蚁群算法的相应参数，该算法均表示很大的稳定性，不同于以往的基本蚁群算法的情况有两点：1）参数的设置随意性较大，信息素启发因子，功能相关性和结构相关性启发因子，绿色性启发因子，挥发系数，蚂蚁数目М均可以较大的随意性，不会影响收敛结果和最优结果；2）收敛速度极快。但是也发现一些需要进一步研究的问题：当蚂蚁M数目比较小时候，发现蚂蚁走的路径几乎每一次迭代遍历路径中，蚂蚁都是走的最优路径，最优值都是26.000；但是当蚂蚁数目M设置比较大的时候，任何一次迭代的路径遍历中，每只蚂蚁只有部分会走最优路径，这跟生活当中蚂蚁觅食过程中，最后所有蚂蚁趋向最优路径有点不同。

5 结束语

本文提出了一种蚁群算法来求解同时考虑模块功能相关性和结构相关性以及零件绿色性的绿色模块划分最优组合问题；结果符合实际要求，实验方法具有可行性和应用性。当可供选择的零件急剧增大的时候，往往这些问题都是NP问题，大数据获取信息需要的是速度和方法结果的正确性，把此方法移植到制造业信息化当中，能够给企业带来节省财力人力的利益，带来企业竞争力。通过大量的实验作者，发现蚁群算法继续发挥它自身的特点，收敛速度极快，作者提出的蚁群算法能极大效率的解决绿色模块划分问题，在实验中发现蚂蚁不尽是走向同一条最优路径，可能跟作者在算法中的进行模块划分时提出的随机数大小比较有▼关；作者将继续改进算法，下一步的研究将是基于PARETO求解的多目标离散蚁群算法获取解集的多样性，还会引入带约束条件的目标随机模型等，解决更多的生产实际问题。