当前位置：文档库 › 9人工鱼群算法在孔群加工路径优化中的应用研究

9人工鱼群算法在孔群加工路径优化中的应用研究

人工鱼群算法在孔群加工路径优化中的应用研究

蔡芸周立炜

(武汉科技大学机械自动化学院，湖北，武汉，430081)

摘要：将人工鱼群算法应用于孔群加工路径优化的研究，建立了以最短加工路径为目标的路径优化数学模型，阐述了算法实施的具体过程，实例计算结果表明：该方法求最优解的性能优于Hopfield算法、进化蚁群算法、人工免疫算法、改进的遗传算法，获得的最优路径可以节省71.47%的行走路程。

关键词：路径规划；孔群加工；人工鱼群算法；优化

中图分类号：TH165 文献标识码：A 文章编号：

大量孔的连续加工任务称为孔群加工，孔群加工常见于钣金加工、印刷电路板加工、机械零件加工中，合理规划孔群加工路径，缩短刀具移动路径、减少换刀次数及刀具变向次数，将有助于减少辅助加工时间，提高生产效率，节约成本。

孔群加工路径规划含有典型的旅行商问题(Travel Sale-man Problem，TSP)，其解空间存在“组合爆炸”，例如在一块已确定初始位置的工件上加工某类孔（数量为n>2），加工完毕后返回，则其可选路径为(n-1)!/2条，当n=26时，可选路径为7.76×1024条，传统的数学规划方法难以求解。目前已经有学者采用遗传算法[1]、蚁群算法[2]、人工免疫系统算法[3]、禁忌搜索算法[4]等智能计算方法求解了孔群加工路径优化的单目标或多目标问题。

人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）[5][6]是近年来提出的一种模拟鱼群行为的随机搜索方法，是群智能思想的一个具体应用。该算法通过仿真鱼的觅食、聚群、追尾行为快速获得最优解。在解决函数优化、组合优化等问题上都取得了成功。目前国内外学者还没有将人工鱼群算法应用于该问题，比较它与其他人工智能算法在此问题上的求解效果，为此本文将其应用于孔群加工路径优化问题，通过具体实例的算法实现，对比各类算法的求解效果。目的是为讲求时效的生产作业，提供更好的理论方法。

1 路径优化的数学模型

当加工多孔类零件时，需要选择合理的孔群加工序列，使总加工成本最小。总加工成本由刀具行进成本、换刀成本和刀具加工成本等组成。若在加工孔群过程中，换刀次数不多，且单位时间的刀具行进成本、换刀成本和刀具加工成本都是定值，则孔群加工的总成本可以仅考虑刀具行进成本。为了比较人工鱼群算法与其他智能算法的优化性能，本文采用了文献[1]、[3]中的最小化刀具行进成本模型，抽象为一个典型的TSP问题：

∑

≠

Y min

min

(1)

s.t.

}1,0{

∈

,i,j=1,2,..., n,

i≠(2)

∑

,2,1

(3)

∑

,2,1

(4)

}

,2,1{

2,1

≤

∑

∈

∈(5) 式(1)为目标函数，其中Y表示刀具行进路径长度，式中D ij为孔i和孔j间已知距离；式(2) 表示是否选择孔i到孔j的路径，a ij=0时，表示不选择从孔i到孔j；当a ij=1时，表示选择；式(3)和式(4)表示孔i和孔j的出入只有一次；式(5)约束的是在任何一个孔的真子集中不形成回路[7]。

2应用人工鱼群算法求解

2.1 符号定义

X：人工鱼群的状态，即被搜索到的最优解状态。X= (X1, X2,…, X n)，其中X i (i=1,..., n) 代表第i条人工鱼的状态，它是孔群加工的序列，这里采用自然数链进行孔序编码，如X i = (3 2 5 4 7 1 6 9 8)，即从孔3出发依次经过孔2-5-4-7-1-6-9-8，然后返

回孔3的一条路径。

Y i ：对应于 X i 的目标函数值，即刀具行进路径长度。它表示人工鱼当前状态的食物浓度。

D ij ：第i 条和第j 条人工鱼间的距离，它表示两条路径同序列位置的孔序编码差异数目，如 X i =(1,3,2,5,6,4)和X j =(1,3,6,2,5,4)在路径序列位置2，3，4处的孔序编码不相同，故D ij 为3。

Visual ：人工鱼的视野范围。

(,)i N X Visual ：第i 条鱼的视觉邻居集合。

{}

(,)i j ij N X Visual X D Visual =≤。

δ：表示拥挤度因子，0 < δ < 1。

FishNum ：参与寻优的人工鱼的数目。 Maxgen ：最大迭代次数。

Trynumber ：人工鱼觅食时最大的试探次数。

m i m

j j j i m X X X X X Center 11

21)(),...,,(=≠==称

为决策变量X 1 , X 2 , ?, X m 的中心。 2.2 人工鱼群算法的行为描述

人工鱼群算法模拟鱼集群游弋觅食的行为，通过鱼群之间的集体协作使群体达到目的。在AFSA 中，每个备选解被称为一条“人工鱼”，多条人工鱼共存，合作寻优(类似鱼群寻找食物)。AFSA 初始化为一群人工鱼(随机解)，通过迭代搜寻最优解，在每次迭代过程中，人工鱼通过觅食、聚群及追尾等行为来更新自己，从而实现寻优。人工鱼的行为描述如下。

(1)追尾行为：指鱼向临近的最活跃者追捉的行为。人工鱼X i 搜索其视野内的所有伙伴中函数值为最小的伙伴X min ，如果Y i > Y min ，并且X min 的邻域内伙伴的数目nf 满足nf / (,)i N X Visual <δ， (0 <δ< 1) ，表明X min 的附近有较多的食物并且不太拥挤，则向X min 的位置前进一步；否则执行觅食行为。

(2)觅食行为：指鱼向着食物多的方向游动的一种行为。人工鱼X i 在其视野范围内随机选择一个状态X j ，如果Y i > Y j ，则向状态X j 方向前进一步；否则，X i 继续在其视野内重新随机选择状态X j ，判断是否满足前进条件，反复尝试Trynumber 次后，如果仍没有找到更优的状态，则执行其他行为。 (3)聚群行为：指每条鱼在游动过程中尽量向临近伙伴的中心移动并避免过分拥挤。设人工鱼当前状态为X i ，探索其邻域的伙伴数目nf ，如果nf /

(,)i N X Visual <δ， (0 <δ< 1) ，则表明伙伴中

心有较多的食物并且不太拥挤，如果此时Y i > Y c ，则人工鱼向中心位置X c 前进一步；否则执行其他行为。

2.3 算法步骤

步骤1：设置参数 FishNum , Maxgen , Trynumber , Visual ,δ; 随机产生人工鱼群来初始化X = (X 1, X 2, …, X i ,…, X FishNum )。 m = 0，i =0。

步骤2：m =m +1；

步骤.3：i =i +1；对人工鱼X i 执行追尾行为；如发现更好的解X j ，用 X j 代替 X i 并转到步骤8；否则转到步骤4。

步骤4：圆整)/1(Maxgen

m Visual -?获得最近的整数Visual2；如果Visual2 >0, 转到步骤5 并

将 Visual2应用其中；否则转到步骤6。

步骤5：对人工鱼 X i ，执行觅食行为；如果发现一个更佳的解X j ，用 X j 代替 X i 然后转到步骤8；否则转到步骤6。

步骤6：对于人工鱼X i ，执行聚群行为；如发现一个更佳的解X j ，用 X j 代替X i 然后转到步骤 8；否则转到步骤7。

步骤7：对于人工鱼X i ，随机改变X i 的元素得到新状态X j 。如果它是一个较佳的状态，则用X j 代替 X i 并转到步骤8；否则转到步骤3，评价第i +1条人工鱼。

步骤8：更新公告板上的最优化解记录，如果i = FishNum ；则转到步骤9；否则转到步骤3，评价第i +1条人工鱼。

步骤9：如果 m = Maxgen , 输出最优解，程序结束；否则转到步骤2，计算第m +1代人工鱼群。

3 计算实验

3.1 算例的已知条件

图1 注塑模上模

Fig.1 The upper die of injection mold

为了比较人工鱼群算法与其他智能算法的优化性能，采用文献[1]、[3]中的注塑模上模具的孔群加工实例(参见图1)。已知26个孔中心的坐标邻接矩阵为：B=[50,50；50,450；690,450；690,50；100,120；100,380；640,380；640,120；30,150；30,350；710,350；710,150；160,70；580,430；160,150；160,350；580,350；580,150；230,250；300,130；440,130；510,250；440,370；300,370；250,180；490,320]

3.2 计算实验结果

当算法参数取FishNum=10，Maxgen=150，Trynumber=150，Visual=8，δ=0.8时，采用配置为Intel Core 2 Duo E6550, 2.0GB RAM的计算机, 在MatLabR2010a软件平台上实现的算法程序，需耗时 2.2286s找到最短路径：1-5-13-15-19-25-20-21-18-8-4-12-11-3-7-14-17-22-26 -23-24-16-6-2-10-9-1，最短路径长度为2696.381（参见图2）。按照传统的孔类型分批加工路径（按孔的编号顺序加工），总长度为9449.5mm[1]。通过人工鱼群算法优化，加工路径缩短为传统加工方式的28.53%。

图2 最优加工路径

Fig.2 Optimal holes machining path

表1对比了不同算法经过100次实验获得的结果（其中改进遗传算法非100次实验结果）[1][3]。可见人工鱼群算法求最优解的效果是优于其他几种算法的，获得的平均解也是较优的。

表1 计算实验结果对比表

Table 1 Results comparison of computational experiments

3.3 算法参数分析

本例使用的算法参数是一个需要优化的问题。笔者在FishNum= 10~30，Maxgen= 50~200，Trynumber = 10~200，Visual = 2~10，δ =0.2~1.0的参数范围内进行了一些实验，发现参与寻优的人工鱼的数目和觅食探测次数选较大值时，求优效果较佳但耗时，考虑计算时效的情况下，参与寻优的人工鱼的数目选择10较为合适，Trymumber在100-200之间，算法容易收敛，但是不能总是收敛到目前发现的最优值2696.381。另外，Visual值通常不能取太小，需要大于参与寻优的人工鱼的数目的一半以上，例如，FishNum为10，Visual取7-8较好。此外，拥挤度因子也不能取得过小，在0.7-0.9范围内变化，求解效果较优。

4 结论

本文建立了最小化孔群加工路径的数学优化模型，对基本人工鱼群算法进行了应用改进，对人工鱼觅食过程中的视野范围因子实行了逐代改进的方法，提高了算法的搜索时效。实例计算表明人工鱼群算法能够较好地解决此类问题，在同类算法中有较优秀的表现。由于随机算法的性能同随机初始解以及算法参数的选择关系密切，所以今后还需做大量的数值实验来获取较好的算法参数组合，便于算法的工程实际应用。

参考文献

[1] 凌玲,胡于进,王青青等. 基于改进遗传算法的孔群加工

路径优化[J].华中科技人学学报(自然科学版),2009,37(8): 88-91.

[2] Ghaiebi H., Solimanpur M.. An ant algorithm for

optimization of hole-making operations[J].Computers & Industrial Engineering, 2007,52 (2): 308–319

[3] 肖人彬,陶振武. 孔群加工路径规划问题的进化求解[J].

计算机集成制造系统,2005,11(5):682-689.

[4] Kolahan F., Liang M.. Optimization of hole-making

operations: a tabu-search approach [J]. International Journal of Machine Tools & Manufacture, 2000,40

(12) :1735–1753.

[5] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:

鱼群算法[Z].系统工程理论与实践,2002,22(11):32-38. [6] 李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应

算法最优解

/mm 平均解

/mm

平均成本节约率

Hopfield 2923.6 3313.5 64.9 进化蚁群算法2876.1 3091.3 67.3 人工免疫算法2834.7 2910.2 69.2 改进遗传算法2715.9 未知未知

用.山东大学学报(工学版),2004,64(4) :64-67.

学报(自然科学版),2008,22(2):25-30.

[7] 张振普,王大承. 群孔加工路径的优化方法[J]. 五邑大学

Holes machining path optimization using an artificial fish swarm algorithm

Cai Yun Zhou Liwei

(College of Machinery and Automation, Wuhan University of Science and Technology, Wuhan 430081, China ) Abstract：An artificial fish swarm algorithm (AFSA) was applied in the research of holes machining path optimization. A holes machining path optimization mathematic model for the minimum holes machining path was established. The basic principle and the algorithm design of the AFSA were introduced. An example shows that: the algorithm has better performance than Hopfield algorithm, evolutionary ant colony system algorithm, artificial immune algorithm and improved genetic algorithm, and the optimal solution can save 71.47% tool airtime.

Key words：Path planning; Holes machining; Artificial fish swarm algorithm; Optimization

蔡芸，武汉科技大学副教授，硕士研究生导师，1991年获大连铁道学院机械制造工艺及设备专业学士学位，2002获新疆大学机械电子工程专业工学硕士学位，2005获武汉理工大学机械设计及理论专业博士学位。主要从事物流系统规划、仿真和优化技术方面的研究，在读博士期间，作为主要人员完成交通部、上海港务局等港口物流系统仿真和优化方面的研究项目4项，主持和参与完成集装化物流系统仿真优化方法与应用研究项目各一项。现在正主持物流系统仿真优化方法研究与应用和混合流水车间调度的仿真优化方法研究共2项项目。近期发表论文10余篇，被EI收录4篇。