史伟民,方 俊,杨亮亮

(浙江理工大学机械与自动控制学院,杭州 310018)

基于模拟退火蚁群混合算法的裁床样片切割路径优化

史伟民,方 俊,杨亮亮

(浙江理工大学机械与自动控制学院,杭州 310018)

样片切割是影响数控皮革裁床皮革加工效率的重要因素,为了提高加工效率,应优化切割路径。样片切割路径受到样片遍历顺序和刀具加工起始位置的影响。将样片切割路径优化归结为广义旅行商问题,用贪婪算法确定刀具加工起始位置,结合模拟退火和蚁群算法对皮革裁床样片切割路径进行优化。仿真实验验证了算法的有效性。

样片切割; 路径优化; 贪婪算法; 模拟退火算法; 蚁群算法; 数控裁床

0 引 言

在数控皮革裁床的样片轮廓数控加工中,一张皮革需要切割成几十个或上百个样片。样片切割路径主要由各样片的加工有效行程和样片间的辅助快速进给空行程构成[1]。各样片切割总的有效切割行程是一定的,而走刀空行程主要由遍历样片轮廓的顺序和样片上轮廓加工的起点位置决定。当加工的样片数量较大时,走刀空行程将成为影响加工效率的重要因素。因此,需要对走刀空行程进行优化。

走刀空行程优化问题可以归结为广义旅行商问题。目前,该优化问题普遍的解决方法是将广义旅行商问题转化为标准旅行商问题,然后用求解标准旅行商问题的算法,得到走刀空行程的优化结果。季国顺等[2]提出结合蚁群算法和最邻近算法对数控多轮廓加工走刀空行程路径进行优化。张伟等[3]引入蚁群算法优化矩形件切割路径。这些方法在一定程度上减少了样片加工时间,提高了加工效率,对路径进行优化时都采用了基本蚁群算法。然而,基本蚁群算法存在着初始信息素匮乏,计算时间较长等局限性,因此,本文用贪婪算法计算出样片上轮廓加工的起点位置,并将模拟退火算法和基于精英蚂蚁系统的改进蚁群算法相结合,对样片轮廓加工顺序进行优化。通过在数控皮革裁床样片切割路径优化软件对算法进行验证。

1 样片切割的数学模型

用数控裁床切割样片时,对于要切割的样片,从下刀点开始,沿着刀具总的空行程最短的轨迹,从一个样片移动到另一个样片,且不重复,直到所有样片被加工完毕。对样片切割路径的优化建立数学模型如下:

a) 变量设计。设有n个待切割样片,V={v1,v2,…,vn}为样片中心点的集合,d(vi,vj)为样片i、j中心点vi、vj之间的距离。

c) 约束条件。从待切割样片中随机选择一个样片开始切割,遍历每一个样片,且不重复。

d) 优化算法。模拟退火算法结合改进蚁群算法。

2 路径优化算法

针对数控皮革裁床样片切割,本文采用贪婪算法确定刀具加工起点位置,采用模拟退火算法与改进蚁群算法相结合的方法用以优化样片切割路径。

用贪婪算法构建出一条以距离刀具位置最近的样片为第一个节点的样片加工序列,用模拟退火算法和蚁群算法对样片切割路径进行优化时,不改变样片库中第一个样片在样片库中的序列,就能保证刀具加工的起点位置离待加工样片最近。

蚁群算法初始信息素匮乏。对于基本蚁群算法,信息素初始化时为各条路径上分配一定量的信息素Q。Q值太小,路径上信息素积累会很慢,算法搜索时间较长;Q值太大,算法会快速收敛,不利于搜索到全局最优解。模拟退火算法具有快速全局搜索能力,但对系统反馈信息利用率较低[4],求精确解效率较低。因此本文采用模拟退火算法和蚁群算法的并行实现来克服这一局限性。先用模拟退火算法生成一条较优路径,在这一路径上生成初始信息素分布,然后利用蚁群算法求精确解。

2.1 贪婪算法

贪婪算法在求解问题时,总是作出当前最好选择,因此算法求解效率较高[5]。采用贪婪算法确定刀具开始加工样片轮廓的起始位置,可以简单有效地优化走刀路径。

假设P={p1,p2,…,pn}为待加工样片序列,刀具的位置p0,用贪婪算法求出刀具加工样片起始节点的步骤如下:

a) 计算刀具的位置p0与待加工样片序列中第一个样片p1的距离d(p1,p0);

b) 对于k=2,…,n,计算样片pk与刀具位置p0的距离d(pk,p0),如果d(pk,p0)小于d(p1,p0),则交换pk和p1在样片序列P中的位置,构成当前以距离刀具位置最近的样片为起始节点的新序列P;

c) 最后可以得到一个以所有样片中距离刀具位置最近的样片为起始节点的样片序列P。

2.2 模拟退火算法

模拟退火(simulated annealing,SA)算法是一种启发式的随机搜索算法,是对局部搜索算法的一种扩展[6]。但SA以一定概率选择邻域中目标值较小的状态,是一种理论上的全局最优算法。模拟退火算法模拟了物理退火过程,首先给定一个初温,然后利用Metropolis策略在解空间中进行随机搜索,伴随着温度的下降,结合概率突跳特性寻找到问题的全局最优解[7]。

SA算法简单,运行效率高,易于与其他算法相结合,且对初始条件的依赖性不高,因此本文将它与蚁群算法结合,生成初始化信息素分布,提高算法的搜索效率。

2.3 蚁群算法

蚁群优化算法(ant colony optimization,ACO)是由意大利学者Dorigo等人于1991年提出的一种模仿蚂蚁群体行为的智能算法[8]。该算法具有良好的鲁棒性,并且引入正反馈并行机制和分布式计算机制。目前已被广泛应用于解决组合优化问题。

蚂蚁在觅食过程中会分泌信息素,觅食路径越短,则信息素浓度越高。后继的蚂蚁在选择觅食路径的时候,会参考路径上的信息素浓度,路径被选择的概率与信息素浓度成正比。蚂蚁在选择的路径上分泌信息素,引导后来的蚂蚁,形成正反馈机制。在信息素正反馈机制的影响下,最终蚁群会聚集到最短路径上。蚁群算法的核心机制有状态转移规则和信息素更新规则。

a) 状态转移规则

蚂蚁k在t时刻由元素i转移到元素j的概率:

(1)

其中:U为蚂蚁k下一步允许的选择;α为信息启发式因子;β为期望启发因子;τil为残留信息量;φil为启发函数。

b) 信息素更新规则

在每一只蚂蚁访问完所有n个节点后,削弱旧的信息,将最新的蚂蚁访问路径的信息加入τij。更新规则可用下式表示。

(2)

(3)

2.4 精英蚂蚁系统

精英蚂蚁系统(elitist ant system,EAS)在基本蚁群算法的基础上对信息素更新规则作了改进,增加了一个对当前最优路径的强化手段[9]。在一次迭代搜索完成更新信息素的时候,为最优路径增加额外的信息素。改进的信息素更新公式如式(4)所示。

(4)

(5)

式(4)中e为权值(一般设置e值为城市的规模n),Lb为最优路径,由式(4)可见,EAS在每轮迭代中为最优路径增加了额外的信息素量。

引入这种额外信息素强化手段,可以更好引导蚂蚁的搜索偏向,提高算法搜索效率。

2.5 改进蚁群算法

蚁群算法在搜索过程中,蚂蚁在经过的路径上释放信息素为一个常量Q,因此次优路径上的信息量可能会偏大,算法容易陷入局部最优,限制算法的全局性。所以蚂蚁在释放信息素时应随着算法搜索状态的变化而作相应的调整。调整规则如下:当某条路径上的信息素浓度越高,经过该路径的蚂蚁分泌的信息素越少。设Q(t)为释放信息素量,则

(6)

其中:r为经过路径(i,j)的蚂蚁数量,R为经过节点i的蚂蚁数量。

基于精英蚂蚁系统,改进蚁群算法信息素更新规则为,当所有蚂蚁完成一轮搜索后,信息素更新如下:

(7)

(8)

3 算法实现

将改进的蚁群算法应用到皮革裁床样片切割路径优化,程序流程图见图1。算法实现步骤如下:

a) 参数初始化;

b) 运用贪婪算法构建出一条以距离刀具位置最近的样片为初始节点的样片加工序列;

c) 运用模拟退火算法生成一条初始节点不变的较优路径,并在这条路径上分布信息素作为初始的信息素;

d) 循环次数Nc=Nc+1;

e) 蚂蚁数k=k+1;

f) 蚂蚁k从样片序列第一个节点(相当于蚁巢)出发,将初始节点加入禁忌表;

g) 对第k只蚂蚁根据状态转移概率公式(1)计算的概率选择下一个样片j,且j为不包含在禁忌表中的样片;

h) 修改禁忌表,蚂蚁移动到新选择的样片,并把刚访问的样片移动禁忌表中;

i) 若样片未遍历完,则跳转到第e步,否则执行第h步;

j)若不是所有蚂蚁都构建完路径,则跳转到第d步,否则执行第i步;

k) 根据信息素更新公式(6)、(7)、(8)更新信息素;

l)若循环次数Nc≥Ncmax,则蚁群算法结束并保存最优结果,否则清空禁忌表并跳转到第c步。

图1 改进蚁群算法流程

4 仿真实验

在windows 7环境下的PC机上,在用Visual C++6.0编写的皮革裁床上位机控制软件中实现以上改进蚁群算法。

蚁群算法参数已由研究人员、学者通过大量实验给出,参考文献[5]给出的经验值,本文对蚁群算法和模拟退火算法参数的设置如表1所示。

表1 算法参数设置

在数控皮革裁床上位机控制软件界面上放置88个待切割样片,如图2所示,带有向箭头的直线即为样片切割路径。初始路径根据样片放置的先后顺序规划的。样片上的数字即为为样片库中样片排放序列。初始路径总长度为10 268 mm。

数控皮革裁床上位机控制软件界面中,横向为x轴,方向向右,纵向为y轴,方向向下。界面样片排版区域左上角为坐标原点。假设刀具位于坐标原点,则距离刀具位置最近的样片即为排版区域左上角第一个样片。交换该样片与样片库中第一个样片的位置,得到新的样片序列后,在用模拟退火和蚁群算法对样片序列进行优化时,不改变样片库中第一个样片的序列,就能保证刀具加工的位置最近。如图2所示,离刀具位置最近的样片在样片库中的序列为2,交换样片库中的序列为1、2的样片位置,得到新的样片序列如图3所示。

图4为模拟退火算法计算出来的路径,在该路径上分布信息素。

图5为基本蚁群算法优化后所得到的路径,路径总长度为7 066 mm,优化过程花费时间为97 309 ms。图6为改进蚁群算法优化结果。最优路径长度为6 864 mm,优化过程花费时间为72 856 ms。分析实验结果数据可以得出,改进蚁群算法优化过程所花费时间为基本蚁群算法的74.87%,由此可见,改进蚁群算法的效率得到较大的提高。改进蚁群算法的最优路径长度比基本蚁群算法优化后路径长度减少202 mm,由此可见,改进蚁群算法的全局优化性能较基本蚁群算法得到了提高。

表2列出了不同数量样片,基本蚁群算法和改进蚁群算法的优化结果及优化时间。当样片数为16时,两个算法优化后路径长度一样,改进蚁群算法优化时间为基本蚁群算法的99.5%;当样片数为32时,改进蚁群算法优化后路径长度不变,优化时间为基本蚁群算法的96.9%;当样片数为48时,改进蚁群算法优化路径长度减少79 mm,优化时间为基本蚁群算法的94.5%;当样片数为64时,改进蚁群算法优化路径长度减少209 mm,优化时间为基本蚁群算法的84.6%。由以上数据可以看出,随着样片数目的增多,改进蚁群算法的全局优化能力和计算效率更加突出。

实验结果表明改进的蚁群算法比基本蚁群算法具有更强的全局搜索能力,效率也明显高于基本蚁群算法。

图2 样片切割初始路径

图3 贪婪算法计算结果

图4 模拟退火算法计算结果

图5 基本蚁群算法优化路径

图6 改进蚁群算法优化路径

表2 不同样片数量基本蚁群算法和改进蚁群算法优化结果

5 结 论

针对基本蚁群算法在优化路径时初始信息素匮乏而影响全局搜索性能以及计算时间较长的局限性,本文提出了基于模拟退火算法和改进蚁群算法的混合算法对空行程走刀路径进行优化。用贪婪算法确定刀具加工的起始位置,结合模拟退火算法和蚁群算法对样片轮廓加工路径进行优化。仿真实验结果表明,改进算法的计算效率和全局优化性能都得到了提高,证明了算法的有效性,节省了皮革加工时间,提高了加工效率。

[1] 王 凌.智能优化算法及其应用[M].北京: 清华大学出版社,2001: 22-30.

[2] 季国顺,王 文,陈子辰.数控多轮廓加工走刀空行程路径优化[J].农业机械学报,2008,39(7): 154-158.

[3] 张 伟,安鲁陵,张 臣,等.基于蚁群算法的矩形件切割路径优化[J].机械科学与技术,2011,30(3): 391-393.

[4] Park M H,Kim K S.Chattering reduction in the position control of induction motor using sliding mode[J].IEEE Trans Power Electronics,2011,6(3): 317-325.

[5] Andries P E.Computational intelligence: an introduction[M].2nd.John Wiley & Sons,2007: 273-313.

[6] 李会玲,汪振华,王基维.基于模拟退火的遗传算法在TSP中的应用[J].热处理技术与装备,2007,12(25): 51-55.

[7] 王忠英,白艳萍,岳利霞.经过改进的求解TSP问题的蚁群算法[J].数学的实践与认识,2012,42(4): 174-181.

[8] 刘晓东,冒勇军.蚁群算法在WSN路由协议中的应用[J].计算机工程,2009,16(2): 243-244,247.

[9] 段海滨,张祥银,徐春芳.仿生智能计算[M].北京: 科学出版社.2011: 33-64.

(责任编辑：康 锋)

Sample Cutting Path Optimization Based on Simulated Annealing and Ant-Colony Algorithm

SHIWei-min,FANGJun,YANGLiang-liang

(School of Mechanical Engineering & Automation,Zhejiang Sci-Tech University,Hangzhou 310018,China)

The sample cutting is the key factor influencing leather working efficiency of CNC cutting bed.To boost processing efficiency and optimize the cutting path,sample cutting path is influenced by sample traversal order and the initial position of cutter.Sample cutting path optimization is boiled down to generalized travelling salesman problem.Greedy algorithm is used to confirm the initial position of cutter.Sample cutting path is optimized in combination of simulated annealing and ant-colony algorithm.The simulation experiment verifies the effectiveness of the algorithm.

sample cutting; path optimization; greedy algorithm; simulated annealing algorithm; ant-colony algorithm; CNC cutting bed

1673-3851 (2015) 02-0214-05

2014-06-18

国家科技支撑计划项目(2013BAF05B01);国家自然科学基金项目(51305404);浙江理工大学重点实验室优秀青年人才培养基金(ZSTUMD2012B004)

方 俊(1989-),男,浙江安吉人,硕士研究生,主要从事智能算法方面的研究。

杨亮亮,E-mail:yangliangliang@zstu.edu.cn

TP249

A