钣金件数控激光切割割嘴路径的优化
第 16卷 第 5期
2004年 5月
计 算 机 辅 助 设 计 与 图 形 学 学 报
J0URNAL 0F COMPUTER—AIDED DESIGN & COMPUTER GRAPHICS
V01．16．No．5
M ay．2004
钣 金 件 数 控 激 光 切 割 割 嘴 路径 的优 化
刘会霞 王 霄 蔡 兰
(江 苏大学 机械 工程 学 院 镇江 212013)
摘 要 提 出 了分 级规 划 的三 步算 法来 解决 优 化 问题．首先用 改 进 的最 近邻算 法 选 择 打孔 点 ；然后 用 智 能仿 生 算 法
— — 蚁 群算 法来 求 解最 佳割 嘴路 径 ；最 后根 据 z轴 随 动功 能约 束情 况 ，用 路径 调 整算 法来 调 整前 两 步 算法 确 定 的 最
佳路 径 ，并 获得 最终 割 嘴最 佳 路径 ．给 出 了运行 实例 并指 出进一 步 的研究 工 作．
关 键词 钣 金件 ；数控 激光 切 割 ；割 嘴路 径优 化 ；打孔点 ；蚁群 算法
中图法 分类 号 TP391；TH16
Torch Path Optim ization for NC Laser Cutting of Sheet M etal Part
Liu H uixia W ang Xiao Cai Lan
(School of Mechanical Engineering，Jiangsu University，Zhe卅iang 212013)
Abstract An hierarchical three—step approach is presented to solve the optim ization problem ．First，
an im proved nearest neighbor algorithm is applied to select pierce points．Then ant system algorithm is
used to solve the optimal cutting path．At last，the former path is adj usted to avoid the torch falling
dow n into the finished cut cavity during its vacancy course． Exam ple and the further research are
discussed．
Key words sheet metal part； NC lase r cutting； torch path optim ization； pierce point； ant colony
algorithm
1 问题 的 提 出
CNC数控激 光切 割机 床(Laser Cutting Machine，
LCM)是典型 的机 、光 、电为一 体 的技术密 集型 高科
技设 备．在工 业 发 达 国家 ，LCM 已被 看 作 为 “敏捷
制造 ”模式 下 的一 种 快速 响应 生 产 的制 造 设备 ．近
年来 ，LCM 正 在 被 越 来 越 多 的 国 内 企 业 所 采 用 ，并
在经 济发达地 区 ，如 深圳 、上海 、江 南 一带发 展 十分
迅 猛 ．在 数 控 激 光 切 割 技 术 日趋 成 熟 的 情 况 下 ，与
之配套 的专用 CAD／CAM 一 体 化 自动 编 程 系统 的
性 能 越 来 越 引 起 用 户 的 关 注 ，因 为 这 种 应 用 软 件 的
性 能 严 重 制 约 了这 些 先 进 数 控 激 光 加 工设 备 的 加 工
效 率 与 质 量 ．通 过 我 校 2．5KW (COz)激 光 切 割 机 床
生产实践发现 ，在这些性 能要 求中 ，激光 切割打孔点
位置 的合理选取 与割 嘴路径 的有效 规划 ，对 激光 切
割这样一个高投入 、高消耗 、更高产 出的高新 设备而
言 ，即使单件 节省较少 的时 间 ，其效益也是 十分可观
的．然而从我们接 触 的国 内外 几个 商品化 激光 切割
自动编程系统 中发现 ，它 们在 打孔 点位 置 的合 理选
取 及割嘴路径 的确定 方面 尚存在如 下问题 ：(1)要求
人工 交互 设置切割 路 径或 在 图形 中补加 有关 信息 ；
(2)对割嘴 随动功 能给切 割路 径带 来 的不 良影 响处
理不 当 或 没 有 考 虑 ，导 致 非 切 割 时 间 增 长 或 易 产 生
切割故障 ；(3)缺 乏 较好 的割 嘴路 径 优 化 策 略 与算
法 ．国外 学者 已对此 作 过一 些 研 究 ：Manber等?1解
原稿 收到 日期 ：2003—04—10；修 改稿 收到 日期 ：2002—08—04．刘 会霞 ，女 ，1964年生 ，博 士 研 究 生 ，副教 授 ，主 要 研 究方 向 为 CAD／CAM 、网 络
化制 造 、激 光加 工技 术等 ．王 霄 ，男 ，1964年生 ，博 士研 究 生 ，副 教授 ，主要研 究 方 向为 CAD／CAE／CAM 、虚拟 制造 、网络 化 制造 等 ．墓 兰 ，
女 ，1939年生 ，教授 ，博 士生导 师 ，主 要研 究方 向为 CAD／CAM 、虚 拟制 造 、激 光加 工与检 测等 ．
维普资讯 http://www.cqvip.com
5期 刘 会 霞等 ：钣 金 件数 控激 光 切割 割嘴 路径 的优 化 661
决 了 一块 板 上 排 样 多 个 零 件 在 火 焰 切 割 机 切 割 时 打
孔点 的选取 与切割 顺序 的优 化 (与激 光切 割类 似 )，
但 没 有 考 虑 被 排 样 的每 个 零 件 的 内部 又 包 含 多 个 要
加工 的内部轮廓 的情 况 ；Jackson等 J考虑 了内部轮
廓 情 况且 能 从 已 有 的 CAD 系 统 中 自动 地 确 定 切 割
的路 径 ，但 需 用 户 在 图形 上补 加 引 入 I出 线 等 信 息
确 定 打孔 点 ，并 且 切 割 路 径 也 并 未 优 化 ；Han等 J考
虑 了排 样 零 件 在 激 光 切 割 过 程 中切 割 温 度 对 切 割 质
量 的 影 响 ，并 纳 入 了 切 割 路 径 优 化 的 数 学 模 型 中 ．
文献 [1—3]皆未 涉 及 割嘴 随 动功 能对 切 割路 径 的影
响 ．国 内 关 于 激 光 切 割 的 自动 编 程 系 统 的 论 文 很 少
有 系统 地 研 究 路 径 优 化 或 随 动 功 能 对 切 割 路 径 的
影 响 ．
在 单 件 小 批 量 生 产 中 ，尺 寸 较 大 且 内 部 包 含 多
个 内轮廓 特征 的这类零 件 在实 际 生产 中十 分常 见 ，
而这 类零 件只能 单件 加工 (如纺织机械设备 、收获机
械 设 备 上 的 钣 金 零 件 )．因此 ，开 展 这 类 零 件 打 孔 点
的选取及割 嘴路径 的优 化 的研 究 ，并将 其补 加 到 自
动 编 程 系 统 中是 十分 必 要 的．
2 割 嘴切 割路 径 问题 的定 义
2．1 钣 金 零 件 的 几 何 表 达 及 定 义
本文 研 究 包含 多 个 内轮 廓 特 征 的单 个钣 金 零
件 ，这 类 零 件 主要 由 首 尾 连 接 的 直 线 、圆 弧 、圆 等 图
元 构 成 的多 个 封 闭 轮 廓 图形 组 成 ．我 们 定 义 有 向 有
序 边 首 尾 相 连 组 成 的 封 闭 轮 廓 为 环 (Loop)，组 成 环
的基本元 素称为边 (E)，边 的端点 称为顶 点 (V)，环
又分 为 内环 与 外 环 ．显 然 ，对 单 件 钣 金 零 件 有 且 只
有 一 个 外 环 ，内环 可 以有 多 个 ；边 可 以是 直 线 、圆 弧 、
圆等 ，定 义 直 线 的 顶 点 是 直 线 的 首 尾 两 端 点 ，圆 弧 的
顶 点 是 圆弧 的起 点 与 终 点 ．对 圆 而 言 ，定 义 一 个 顶
点 ，这 个 顶 点 是 圆 上 的 某 一 点 ，这 点 对 切 割 过 程 而 言
图 1 钣金 零 件 轮廓 的定 义
既是 切 割 的 起 点 又 是 切 割 的 终 点 ．本 文 规 定 ：外 环
记为 Oloop，外 环 顶 点 总 数记 为 叫，任 一 顶 点记 为
OV ( 1，2，?， )；任一 内环记为 loop ，其对应 的
顶点 总数记为 V( )，第 k个 内环 loop 对应 的第
个 顶 点 记 为 ，(k=1，2，? ，m ； =1，2，V(k))，所
有 内外 环 皆按 整 体 逆 时针 方 向从 某 一 顶 点 开 始 排 列
构 成 ，如 图 1所 示 ．在 图 1中 ，环 集 loop= {Oloop，
loop 。‘loop }；顶 点 集 V = {Vl， 2，? ， ，Vll，
l2，? ，V1 v(1)，? ，V 一， v( }．
2．2 割 嘴路 径 问 题 数 学 模 型 的建 立
激 光 切 割 最 终 的 目的是 要 切 割 出 所 有 的 内环 与
外 环 而 形 成 工 件 ，切 割 内 环 或 外 环 时 ，首 先 以 一 个 环
上 的某一顶 点 为打 孔 点 ，打 穿再 切 割完 该 环 ．按 实
际切 割工艺 ，切 割顺序应遵循先 内环后外 环的原则 ，
其 整个 切 割 过 程 是 割 嘴 从 编 程 零 点 (即 对 刀 点 )出
发 ，快 速 行 进 到 某 一 内 环 上 的 打 孔 点 ，并 开 光 打 孔 ；
再 以该 打孔点所在 的顶点 为起点切 割完该有向有序
的封 闭环 ，即回到开始打孔 点 ；然后关 光快速行进到
下一个 内环上的打孔 点 上 ，重复 前 面类似过 程 直到
切 割 完 所 有 内环 ；再 关 光快 速 行 进 到 外 环 打 孔 点 ，开
光打孑L并切 割外环 ；最后 从 外环 打孔 点关光 快 速返
回程 序 零 点 ．在 图 1中假 定 程 序 零 点 为 P ，内环
loop1打孔点 为 ? loop2打孔 点 为 V21，loop3打
孑L点 为 V3l，loop4打 孔 点 为 V41，Oloop 打 孔 点 为
OV ，则一个完整的切割路径可表示为 Pn 翌
扣
11(开 光 打 孔 ) Vl2一 V13一 V14一 V15一 V16一
7一 v。8一 v1。(关 光) 皇 V
21 (开 光 打 孔 )
翌V22一 v23一 V24一 v25一 v21(关光) 兰 一 一 V23一 一 V25一 V21(关光)_二二==二二+
七丌割
31(开 光 打 孔 ) V32一 V33一 34一 V35一 V31
(关光) 塑 V4。(开光打孔)型 V42一 V43一
v 一 V 。(关 光 ) 兰 OV (开 光打 孔)里
0 2一 oV3一 oV4一 OV5一 OV6一 OV7一 OV1(关
光) 兰 P
． 由于 封 闭 的 内外 环 必 须 切 割 ，因 此
无论从何点 开始切 割 ，内外环 的长度 不变 ，即不存 在
路 径 优 化 问题 ．这 样 ，割 嘴 路 径 规 划 就 是 指 如 何 安
排切割顺序 ，使激光 切割 过程 中快 速空 移 的行程 的
时间最 短．对 图 1而言 ，就 是从 P 出发 ，如何 选 择
? V2l，V3l，V4l，OVl及其 加工顺 序所 构成 的 回
路路 径 最 短 ．很 显 然 ，当 打 孔 点 一 定 时 ，路 径 优 化 的
问题 就 是 最 著 名 的 旅 行 售 货 员 问 题 (Traveling
维普资讯 http://www.cqvip.com
662 计 算 机辅 助 设计 与 图形学 学报 2004钲
Salesman Problem，TSP)．然 而 ，内外 环 上 的 打 孑L点
从切割工艺 上讲并不惟一 ，可 以是 环上的任一顶点 ，
打孔点在切 割路径的优化算法 中应被考虑 的总顶点
数 为 外 环 总 顶 点 数 ∞ 加 上 所 有 内 环 总 顶 点 数
M
：V(k)个．为了给出切割路径的数学表达式 ，本
k= I
文 中把按某种方 法确 定 的内环 loop，上 的打孔 点记
为 P ，Oloop上 的打 孔点 记为 PE．显 然 ，P ∈ {
、／r 2，? ， y( )}；PE= ∈ {OV1，OV2，? ，0 }，并
设对所有打孔 点 P：{P0，P1，P2，? ，PM，PE}的一
个访问顺序为 T={Po，t1，t 2，tM，PE，Po}，其 中 t
∈{P0，Pl，P2，? ，PM，PE}，则 切割 路 径 的数 学 模
型 为
M — l
min L：{a(p0，tt)+∑ (t ，ti+1)+
i= I
d( M，户E)+ d(PE，Po)}．
在实际切 割过程 中，切 割路 径 的优化 还受 到 z
轴 随 动 功 能 的制 约 ．Z 轴 随 动 功 能 实 质 上 是 一 种 激
光焦点 自动跟踪 功能 ，它能保 证 在切 割过 程 中使激
光切割焦点始终保 持 在工 件表 面 内 ，且与工 件表 面
的距离恒定 ，从而避 免了因工件变形 、表面粘附物等
因素影响引起焦 点位 置变化 ．z轴 随动 功能会 引起
下列问题 ：当一个环切 割完后 ，割 嘴快速空移到下一
个 环 打 孔 点 的过 程 中 ，随 动 功 能 有 可 能 导 致 割 嘴 掉
人 已切割 的板材 空洞 中而 造 成割 嘴损坏 ，使机 床无
法正常切 割．如 图 2所 示 ，当打孔 点为 t 一1，t ，t +1
时 ，切 割 完 loop 后 ，loop，区 域 内 钢 板 会 因 重 力 下
落 ，则割嘴 由 t 快速 空移 到 t +】，会 掉人 loop，形成
的空洞 中．而 当打孔点 t 改为 t 时 ，将不 存在 此 问
题．因为加 工完 loop 后 ，割嘴 由 t 一】快 速空移 到 t
点 ，此 时 loop；还 未 加 工 ．
图 2 割嘴 掉人 切割 区 域示 意 图
3 打 孔 点 的 选择 及 路 径 优化
当打孔 点 确 定 后 ，路 径 优 化 问 题 相 当 于 一 个
TSP问题 ，此时切割路径共 有 M !条 ，如考虑 到打孔
M
点的可变化性 ，切割路径将为 M !X∞X lI V(k)
i= l
条．其数 目是 十分 巨大 的 ，即使 对 于如 图 1所 示 这
样简单的零件 ，切割路 径 也 有 4 1 X 7 X 8 X 5×4 X 5
=134 400条．从形式 上看 ，打孔 点选择 及 路径 优化
可被看 作一个具 有约 束 的离散 变量 的优 化 问题 ，然
而解决这一 问题 十分 复杂．由于 TSP问题本 身就属
于著名的 NP问题 ，因此 若再 同时考 虑 打孔 点 变化
及 z轴 随动功能 的影 响 ，将使 这一 问题变 得更 加复
杂 ．早 期 人 们 为 了 简 化 这 一 难 题 ，采 用 固 定 打 孔 点
且不考 虑 z轴 随 动功 能 的影 响 ，这显 然 很 不合 理 ．
本 文 针 对 这 一 问题 ，提 出 了分 级 规 划 的 三 步 方 法 ：先
按 改进最近邻算法合理 选择 打孔点 ；再按 TSP问题
进行路径优化 ；最后再判定 空移时是否掉入 空洞 中 ，
并按一 定算法调整 路径 使 之避 开空 洞 ，有效 地解 决
了这 一 难 题 ．
3．1 打孔 点 的 确 定
打孑L点确定 的原则是 一个 内环或外环 仅有一个
打孑L点 ，本文按 切割工 艺采 用最 近邻算 法 的一个 改
进 算法确定打孔点．该算 法充 分考虑 了打 孔点对 割
嘴路 径 优 化 的影 响．
算 法 1．打 孑L点 的确 定
Step1．从 编程零 点 Po出发 ，令 Pk=Po，P={Po1．
Step2．遍历 所 有 待 加 工 内 环 loop= {loopl，loop2，? ，
loopM}对 应 的顶点 集 V={V11，V12，? ，V1vt1)，? ， ，? ，
VMv(女)}．找 到 距 最 近 的 顶 点 Pi= VO(对 应 内 环 为
loop。)，并 将 P。加入 到 打 孔 点 集 Q 中 ，Q = P+ {P，}；令
= P ，然 后 在 loop集 中 删 除 loopi及 looPl对 应 的顶 点 { l，
V，!，? ，V y(。)}．
Step3．依 次遍 历所 有 的未 访 问的 内轮 廓 ／oop对 应 的 顶
点集 ，找 到 打孔 点 ，并 加入 打孔 点集 Q 中 ，令 P=Q．
Step4．从 出发 ，再 遍 历 外 环 上 的 所有 顶 点 集 {OVl，
OV!，? ，0v山}，找 到 距 离 最 近 的 一个 顶 点 即 打 孔 点 PE，则
所有 打孑L点 P={Po，Pl，P2，? ，PM，PE}．
注意 ：当环是 圆时 ，按最 近邻算 法 ，前一 个 切割
起 点 与 圆 上 最 近 点 即 切 割 起 点 ，它 是 前 一 个 切 割 起
点与该圆圆 心连 线 与 圆 的交 点 ．本 文 为求 解 方便 ，
把圆心定义为虚顶 点 ，以便 标 识及 方便 求解 圆上 的
切 割 起 点 ．
3．2 基 于 打 孔 点 的路 径 优 化
对 所 有 已知 的 打 孔 点 P= {Po，Pl，P2，? ，PM，
P }，由第 2．2节 可知路 径 优化 问题 等 同于 著 名 的
TSP问题 ．TSP问 题 是一 个典 型 的 、易 于描 述 却难
以处理的 NP完 全问题．人 们针对 TSP问题提 出了
维普资讯 http://www.cqvip.com
5期 刘会 霞 等 ：钣金 件数 控 激光 切 割割 嘴路径 的优化 663
多 种解 决 办 法 ，典 型 的 优 化 算 法 有 局 部 优 化 、遗 传 算
法 、模 拟退火法 、禁忌 搜索 、人工 神经 网络算法 和 蚁
群 系 统 等 启 发 式 搜 索 算 法 ．
20世纪 90年代 初 ，意大 利学 者 Dorigo等 从生
物进 化 的 机 理 中 受 到 启 发 ，通 过 模 拟 自然 界 蚂 蚁 寻
径 的行 为 ，提 出一种 全新 的智能仿 生 算法——蚁 群
算法 ¨J．蚁群 算法 不仅 能够智 能搜 索 、全局 优化 ，而
且具 有稳健性 (鲁棒 性 )、正 反馈 、分布式 计算 、易 于
与其他算法 结合 等特点 ，在一 系列 复杂 困难 的系统
优化 问题求解 中取 得 了成效 ，显示 出该算 法在求 解
复 杂 优 化 问 题 ，特 别 是 离 散 优 化 问 题 方 面 的 一 些 优
越性 ，如蚁群算法 求解 TSP明显优 于其他算 法[5-8~．
本文 采用 蚁群算法 求解激 光切割 中的 TSP问题 ．
3．2．1 蚁 群 算 法 原 理
蚁 群 算 法 是 对 自然 界 蚂 蚁 的寻 径 方 式 进 行模 拟
而得 出的一种 仿生算法 ．虽然单 个蚂 蚁 的行为极 其
简单 ，但 它们所组 成 的蚁群 群体 却 表现 出极 其复 杂
的行 为．它们 在 找到 食 物 时 ，总 有 能力 找 到一 条 从
食物源到寓巢之 间的最 优路 径 ，并 能 随环境 的变 化
而变化 ，适应地搜 索新 的路径 ，产生 新的选 择 ，这 是
因 为 蚂 蚁 在 寻 找 路 径 时 会 在 路 径 上 释 放 一 种 特殊 的
信息素．当他们 遇 到 一个 还 没 有 走过 的路 口时 ，就
随 机 地 挑 选 一 条 路 径 前 行 ，同 时 释 放 与 路 径 长 度 有
关的信息素．路径 越长 ，释放 的信息素 浓度越 低．当
后 来 的蚂蚁再 次遇到这个路 口时选择 信息素浓度较
高的路径概率就 会 相对较 大 ，这 样大 量蚂 蚁组 成 的
蚁群 集体行 为便形成 了一 种信 息正 反馈 现象 ．最优
路径 上的激素浓 度越 来越 大 ，而 其他 路径 上 的信息
素浓 度却会 随时 间 的流逝 而 消减 ，最 终整 个蚁 群会
找 到 最 优 路 径 ．不 仅 如 此 ，蚂 蚁 还 能 够 适 应 环 境 变
化 ，当蚁群 运动路线上 突然出现障碍物 时 ，蚂蚁能够
很 快 地 重 新 找 到 最优 路 径 ．
3．2．2 蚁群算法 模型及算法 实现
定 义．切 割 中打 孔 点 即 TSP 问题 中 的 城 市 ；d ，
表示两个 打孔 点之间 的欧 氏距 离 ，即 TSP问题 中两
个 城 市 间 的 花 费 ；bm )表 示 t时 刻 位 于 城 市 的 蚂
蚁的个数，m= ∑ bi( )；r 表示t时刻边( ， )上
l= 1
的信息激素 浓 度 ，且设 r (0)=C(C 为 常数 )， ，
=0，1，? ， 一1； =1／ 表 示 t时 间 边 弧 ( ，J)的
能见度 ，反映 由城市 i转 移到城市 的期望 程度．
由蚁 群 算 法 原理 可 知 ，蚂 蚁 k(k= 1，2，? ，m )
在运动过 程 中根 据各 条 路 径上 的信 息 决 定转 移 方
向 ，随着 时间的推 移 ，从前 留下 的信息 逐渐 消逝 ；经
过 个 时 刻 ，蚂 蚁 完 成 一 次 循 环 ，各 路 径 上 的 信 息
量 要 作 调 整 ．人 工 蚁 群 系 统 模 型 [ 。]如 下 ：
(1)设蚁 群在并行 搜索 TSP的解 ．通过 一种 信
息激素作媒体相互 通信 ，在每个 结 点上且 和该 结点
相连的边的长度上 ，以信息 激 素量 作为 搜索 下一结
点的试探依据 ，直到找到一个 TSP可行解．
(2)根据 路径 上 的激素 浓 度 ，以相 应 的转移 概
率来选取下一 步路径 ．在 t时刻蚂 蚁 k由一个 结点
位置 i转移至下一个位置 的转 移概率为
： 翥 s ㈩ ：{ ￡)旌(￡) 一 (1)
各 s
其 中，参数 a表示 信 息 的相对 重 要 性 (a≥ 0)； 表
示能 见度 的相 对 重要 性 ( ≥ 0)；S表 示 可 行 结 点
集 ，即蚂 蚁 k下 一 步 允 许 选 择 的城 市 ．a， 分 别 反
映了蚂蚁 在运动过程 中所积集 的信息 以及启 发式 因
子在蚂蚁 选择路径 中所起 的不 同作用 ．
(3)不 再选 取 上 次 循 环 已经 走 过 的 路 径 为 下一
步路径 ，而 由禁忌表控制．
(4)当 m 个蚂蚁按式 (1)找 到可行解后 ，则修改
各边 的信息量 ，即调整信息激素强度的更新方程为
(t+ ，2)= P× (t)+ Ar巧，P∈ (0，1) (2)
其 中 Ar =
。
△￡ ，△《表示第k只蚂蚁在本次循环
中留在路径 ( ， )上 的信息激素量 ．
本文采用能 反 映整体 信息 的 Ant．Cycle System
模 型 ，故
J ，如果在时刻 t和t十 之间
～ 一 1 第 k只蚂蚁使用边e(￡， )
l0，其 他
其 中 ，Q 是一个 常数 ，L 是 第 k只蚂蚁 周游 的路 程
长度 ；At 表示本次循环 中路径 (i， )上 的信息激 素
量的增量 ；参数 P表示信 息 的特征性 ；1．JD表 示信 息
衰减度 ，即信息 消逝 程度 ．
对 上述系 统模 型 ，其求解 算法 步骤可 归结 为算
法 2．
算 法 2．TSP模型求解
Step1．初 始 化．
Nc一 0(NC为 迭代 步 数 或 搜 索 次数 )； (t)=C ；Ar
=0，将 m 只蚂蚁 置 于 个顶 点上 ．
Step2．把 k个蚂 蚁 的初 始城 市号 放 置到 tabul(s)中 ．
Step3．根 据式 (1)概 率来 选 择 下 一 步 应该 到达 的城 市 ，
维普资讯 http://www.cqvip.com
计 算机 辅 助设 计 与 图形 学 学报 2004正
将第 k个蚂蚁 移 到城 市 ，并将 插入 到 tabu女(s)中．
Step4．计 算第 k个 蚂 蚁 的 总 路 径 长 度 L ，更 新 找 到 的
最短 路 径．
Step5．按 更新 方 程 (2)更 新边 上 的信 息激 素浓 度 ．
Step6．对 各边 弧 (i，J)，置 △r。一 0；NC— NC+1．
Step7．若 NC< 预 定 的迭 代 次 数 且 无 退 化 行 为 ，则 转
Step2；否则 ，输 出 当前 最 好解 ，终止 程序 ．
蚁群算法 的核 心有三条 ：(1)选择 机制 ．信 息激
素越多 ，被选 中的概率越大 ；(2)信息激素 更新机 制．
路 径 越 短 ，信 息 激 素 增 加 越 快 ；(3)协 作 机 制 个 体 之
间 通 过 信 息 激 素进 行 信 息 交 流 ．
3．3 割 嘴 切 割 路 径 的调 整 算 法
过去 ，人们 为避 免 割嘴掉 入 已切割 区域形 成 的
空洞问题 ，一 般通过 小 功率试 切 割 的办法或 通过 自
动编 程 中 的 加 工 模 拟 来 检 查 这 一 情 况 ，然 后 人 工 干
预来调 整打孔点位 置 或直 接修 改生 成 的数控 指令 ，
即存在 问题 的快 速空 移 空行 程 指 令 前 补 加取 消 z
轴随动指令 ，让 z轴 抬起 某 一高度 ，再 快 速空 移 到
下一 打孔点 ，并 补加 启动 随动 指令 使 割嘴下 落 打孔
并 切 割 ．但 由于 Z 轴 随 动 每 次 取 消 与 启 动 系 统 响 应
速度 较 慢 ，严 重 影 响 切 割 效 率 ，因此 应 尽 可 能 调 整 打
孔点 ，仅 当无 法通 过 打孔 点 调整 时 ，才 用 z轴 随 动
功能 ．
由于 人 工 干 涉 严 重 影 响 了数 控 编 程 效 率 ，并 易
引起差错 ，因此本 文研 究 了一个 有 效地解 决 这一 问
题 的算 法．假 设经 过 3．1、3．2算 法优化后 的打孔 点
顺序 (即切割顺序 )为 {P0，tl，t 2，? ，tM，PE，P0}，显
然切 割 路 径 调 整 是 通 过 调 整 环 上 打 孔 点 的位 置 实 现
的 ．如 图 2所 示 ．
算 法 3．割 嘴 路 径 调 整 算 法
Step1．根据 打孔 点顺 序 建立 待 切 割 环 集 WP 及 切割 环
集 PP，每切 割 完一 个环 ，则从 待 切割 环集 WP 中转入 已切 割
环 集 PP 中．
Step2．判 定 打孔 点 t 到 t + 快 速 空 行 程构 成 的直 线 是
否 与 已切割 环集 PP 的 某 一 边 有 交 点 (除 t 外 )(如 图 2所
示 )，完 成所 有 路径判 定 后则 程 序停 止．
a．若 无交 点 ，不 需调 整 ．
b．若有 交点 ，则将 打 孔 点 t 调 整 为该 交 点 所 在 环 上 的
边 的最 近端点 t ，再 返 回 Step2重 新 判 定 ；若 无 交 点 则 调 整
成功 ．
c ． 若还 有交 点 ，则 依 次选 环上 各边 端 点继 续 按 Step2判
定 ；若 环上 所有 边 选完 后都 存 在交 点 ，则 转 Step3．
Step3．标识 t ，t +1点 ，以 便 在 数 控 指 令 生 成 时在 t 到
t + 快速 移动 指令 前 补加 取 消 Z轴 随 动 指令 ，在 t 到 t + 快
速移 动 指令后 补 加启 动 Z轴 随动 指令 ．转 Step2．
3．4 实 例
本 文 算 法 用 Visual C++ 6．0编 写 ，在 P IV
1．7GHz高档微 机 上调 试 并通 过 运 行 ．人 工蚁 群 算
法中 a，p， ，』D， 等 参数 对算 法性 能有 较 大影 响 ：
a 值 的 大 小 表 明 留在 每 个 结 点 上 的 信 息 量 受 重 视 的
程度 ，a值越大 ，蚂蚁选择 以前选 过的点 的可能性 越
大 ，但过 大会 使搜索过早满足 于局部最 小点 ；口的大
小表 明启发式信 息受 重视 的程 度 ； 值 会影 响算 法
的收敛速度 ， 过 大会 使算法收敛 于局部 最小值 ，过
小 又会 影 响 算 法 的 收敛 速度 ，随着 问 题 规 模 的增 大 ，
值 也 需 随 之 变 化 ；p表 示 信 息 的持 久 性 ，减 少 P虽
可以提 高算法的全 局搜 索 能力 ，但 又会 使算 法 的收
敛速度 降低 ．蚂蚁 数 目越多 ，算 法 的全 局搜 索 能 力
越强 ，但 算 法 的 收敛 速 度减 慢 ．蚁 群 算 法 中 ，a， ，
， ID等参数 的设 定 目前 尚无理论 上的依据 ，只有经
a算法 1，2求 得的 初始切 害I路 径
b算法 3求得 的最 终切 害I路径
图 3 打 孔点 及 最佳 割嘴 路径
维普资讯 http://www.cqvip.com
5期 刘会 霞 等 ：钣金 件数 控 激光 切 割割 嘴路 径 的优化 665
验 结 果 7_：(1)COS口≤ 5；(2)1≤ p≤ 5；(3)0．1≤ l0≤
0．99，一 般 p取 0．7左 右 ；(4)1≤ ≤ 10000．图 3
所 示为一个实例运 行结果 ．在 图 3 a中 ，由算 法 1确
定 的打孔点 为 P0，1，2，3，??24，PE，由算 法 2求
得 的 最 佳 割 嘴 路 径 为 图 中 各 打 孔 点 的 连 线 ；图 3 b
所 示为 由算法 3所获得 的最终 割嘴最佳路径 ．
4 结 束 语
本 文 对 钣 金 件 切 割 中割 嘴路 径 优 化 问题 进 行 了
数 学建模 ，这是一个极 其复杂的 、具有约束 的离散变
量 的优 化 难 题 ．文 中提 出 了 分 级 规 划 的 三 步 方 法 并
给出 了三个 实现 算 法 ，有 效 地解 决 了这一 难 题 ．其
算法实现程序 已被加入我校 自行开发 的激光切割 自
动 编 程 系 统 中 ，并 取 得 了 较 好 的 应 用 效 果 ．然 而 在
实际应用 中，我们 又发 现本 文算 法对 薄板 切 割还不
能 令 人 满 意 ．薄板 切 割 中 热 影 响将 严 重 影 响 切 割 质
量 ，而 切 割 路 径 不 同 引 起 的 热 影 响 也 不 同 ．因此 ，当
切割参数 优化完 成后 ，还 必 须在 切割 路径 优化 中进
一 步 考 虑 热 影 响 约束 。这 正是 我 们 今 后 要 做 的 工 作 ．
参 考 文 献
[1] Manber Udi， Israni Sharat． Pierce point minimization and
optimal torch path determination in flame cutting[J]．Journal of
Manufacturing Systems，1984，3(1)I：81～88
[2] Jackson Steven D，Mittal Ravi O．Automatic generation of 2一
axis laser—cutter NC machine-program and path planning from
CAD[J]．Computer in Industry 1993，21(2)：223--231
[3] Han GUK—CHAN， Na SUCK—Joo ． A study on torch path
planning in laser cutting processes part2： Cutting pa th
optimization using simulated annealing [J]． Journal of
Manufacturing Process，1999，1(1)：62～70
l4j Dorigo M ，Maniezzo V ，Colorni A．The an t system optimization
by a colony of cooperating agents[J]．IEEE Transactions on
Systems，Man，and CyberneticsPartB，1996，26(1)：1～13
[5] Gambardella L M， Dorigo M． Solving symmetric and
asymmetric TSPS by ant colonies[A]．In：Proceedings of the
IEEE Intern ational Conference on Evolutionary Co m putation
(ICEC’96)[C]．Nagoya：IEEE Press，1996．622--627
[6] Dorigo M，GambardellaLM．Ant colony system：A cooperative
learning approach to the traveling salesman problem [J]．IEEE
Transactions on Evolutionary Computation，1997，1(1)：53～
66
[7] Ma Liang ．An t colony optimization for bottleneck TSP [J]．
Co mputer Engineering，2001，27(9)：24--25(in Chine~)
(马 良．瓶 颈 TsP的蚂 蚁系统 优化 [J]．计算 机工 程 ，2001，
27(9)：24～25)
l8j Li Suoping， Zhang Xiuyuan 。 et a1．Theory on artificial an t
algorithm and its application in TSP．Problem [J]．Journal of
Tran spo rtation Systems Eng ineering an d Information
Technology，2002，2(1)：54～57(in Chinese)
(黎锁平 ，张 秀嫒 ，等 ．人 工 蚁 群 算 法 理 论 及 其 在经 典 TSP
问题 中的实 现 [J]．交通 运输 系 统 工程 与 信息 ，2002，2(1)：
54～57)
维普资讯 http://www.cqvip.com
钣金件数控激光切割割嘴路径的优化.pdf
