基于蚁群算法的工艺路线生成及优化

第１６卷第７期２０１０年７月计算机集成制造系统ＣｏｍｐｕｔｅｒＩｎｔｅｇｒａｔｅｄＭａｎｕｆａｃｔｕｒｉｎｇＳｙｓｔｅｍｓＶ０１．１６Ｎｏ．７Ｊｕｌｙ２０１０

文章编号：１００６—５９１１（２０１０）０７—１３７８—０５

基于蚁群算法的工艺路线生成及优化刘伟，王太勇，周明，饶俊（天津大学天津市先进制造技术与装备重点实验窀，天津３０００７２）

摘要：针对计算机辅助工艺规划中的工艺路线的决策问题，提出了一种基于蚁群算法的工艺路线生成及优化算法。该算法将被加＿［零件划分为若干特征元，并由各个特征元的加工链得到该零件的加工元；根据加工元的属性，用加权海明距离表示加丁元之间的相似度；根据加工元之间的约束条件，确定其优先加工关系并得到各自的前趋加工元；对基本蚁群算法进行改进，在禁忌准则和约束条件的限制下对解空间进行搜索，从『ｆＩｉ得到优化的零件加工工艺路线。通过实例验证了该算法的可行性和有效性。关键词：计算机辅助工艺规划；特征元；加工元；工艺路线；优化；蚁群算法中图分类号：ＴＰｌ６２文献标志码：Ａ

Ｇｅｎｅｒａｔｉｏｎａｎｄｏｐｔｉｍｉｚａｔｉｏｎｏｆｐｒｏｃｅｓｓｒｏｕｔｉｎｇｂａｓｅｄｏｎａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ

ＬｊＵＷｅｉ，ＷＡＮＧＴａｉ—ｙｏｎｇ，ＺＨＯＵＭｉｎｇ，ＲＡＯ，“”

（ＴｉａｎｊｉｎＫｅｙＬａｂｏｒａｔｏｒｙｏｆＡｄｖａｎｃｅｄＭａｎｕｆａｃｔｕｒｉｎｇＴｅｃｈｎｏｌｏｇｉｅｓ＆Ｅｑｕｉｐｍｅｎｔｓ．ＴｉａｎｉｉｎＵｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ３０００７２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｂａｓｅｄｏｎｔｈｅａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ａｎａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄｆｏｒｔｈｅｐｒｏｃｅｓｓｒｏｕｔｅｏｐｔｉｍｉｚａｔｉｏｎｔｏｓｏｌｖｅｔｈｅｄｅｃｉｓｉｏｎ－ｍａｋｉｎｇｐｒｏｂｌｅｍｓｏｆｔｈｅｐｒｏｃｅｓｓｒｏｕｔｅｉｎａＣｏｍｐｕｔｅｒＡｉｄｅｄＰｒｏｃｅｓｓＰｌａｎｎｉｎｇ（ＣＡＰＰ）ｓｙｓｔｅｍ．Ｅａｃｈ

ｐａｒｔｗａｓｄｉｖｉｄｅｄｉｎｔｏｓｏｍｅｆｅａｔｕｒｅｃｅｌｌｓ，ａｎｄｔｈｅｏｐｅｒａｔｉｏｎｃｅｌｌｓｗｅｒｅｇｅｎｅｒａｔｅｄｂｙｍａｃｈｉｎｉｎｇｃｈａｉｎｓｏｆｆｅａｔｕｒｅｃｅｌｌｓ．ＴｈｅｓｉｍｉｌａｒｉｔｙｏｆｅｖｅｒｙｔｗｏｏｐｅｒａｔｉｏｎｃｅｌｌｓｗａｓｒｅｐｒｅｓｅｎｔｅｄｂｙｔｈｅｗｅｉｇｈｔｅｄＨａｍｍｉｎｇｄｉｓｔａｎｃｅｏｎｔｈｅｂａｓｉｓｏｆｔｈｅｉｒ

ｐｒｏｐｅｒｔｉｅｓ．Ａｃｃｏｒｄｉｎｇｔｏｔｈｅｃｏｎｓｔｒａｉｎｔｓｏｆｔｈｅｏｐｅｒａｔｉｏｎｃｅｌｌｓ，ｔｈｅｐｒｅｆｅｒｅｎｃｅｓｅｑｕｅｎｃｅｓｏｆｔｈｅｏｐｅｒａｔｉｏｎｃｅｌｌｓｗｅｒｅｄｅｔｅｒｍｉｎｅｄ，ａｎｄｔｈｅｆｏｒｅｃｅｌｌｓｏｆｅａｃｈｏｐｅｒａｔｉｏｎｃｅｌｌｗｅｒｅｏｂｔａｉｎｅｄ．Ａｐｒｏｃｅｓｓｒｏｕｔｅｗａｓｇｅｎｅｒａｔｅｄａｎｄｏｐｔｉｍｉｚｅｄｂｙ

ｕｓｉｎｇｔｈｅｍｏｄｉｆｉｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｕｎｄｅｒｔｈｅｔａｂｏｏｃｒｉｔｅｒｉｏｎａｎｄｃｏｎｓｔｒａｉｎｔｓ．Ｅｘｐｅｒｉｍｅｎｔｓｒｅｓｕｌｔｓｒｅｖｅａｌｅｄｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｗａｓｆｅａｓｉｂｌｅａｎｄｅｆｆｅｃｔｉｖｅ．

Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｕｔｅｒａｉｄｅｄｐｒｏｃｅｓｓｐｌａｎｎｉｎｇ；ｆｅａｔｕｒｅｃｅｌｌ；ｏｐｅｒａｔｉｏｎｃｅｌｌ；ｐｒｏｃｅｓｓｒｏｕｔｅ；ｏｐｔｉｍｉｚａｔｉｏｎ；ａｎｔｃｏｌｏｎｙａｌ—ｇｏｒｉｔｈｍ

０引言

计算机辅助工艺规划（ＣｏｍｐｕｔｅｒＡｉｄｅｄＰｒｏｃｅｓｓＰｌａｎｎｉｎｇ，ＣＡＰＰ）是联系设计和制造的纽带，目的是提高工艺设计的效率和质量，使工艺人员从烦琐重复的事务性工作中解脱出来。随着现代集成制造技术的迅猛发展，以及多品种、小批量的生产越来越占主导地位，ＣＡＰＰ系统的研究与开发显得尤为重要。工艺路线的决策是ＣＡＰＰ的关键问题之一，它不仅受机床、夹具和刀具等因素的影响，而且受工艺约束的制约。因此，它实际上是一个带约束的非线性规划问题。但是，工艺路线的优化目标和约束条件都难以用明确的解析式表达，并且传统的优化算法（如单纯型法、最速下降法、牛顿法等）都比较复杂、低效，且容易陷入局部最优解ｎ］，因此采取传统的优化算法来解决该问题遇到了很大的困难。

收稿日期：２００９—０８—０５；修订日期：２００９—１２－０６。Ｒｅｃｅｉｖｅｄ０５Ａｕｇ．２００９Ｉａｃｃｅｐｔｅｄ０６Ｄｅｃ．２００９．

基金项目：国家８６３计划资助项目（２００７ＡＡ０４２００５）；国家自然科学基金资助项日（５０９７５１９３）；高等学校博士学科点专项科研基金资助项目（２００６００５６０１６）。Ｆｏｕｎｄａｔｉｏｎｉｔｅｍｓ：ＰｒｏｊｅｃｔｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＨｉｇｈ—Ｔｅｃｈ．Ｒ＆ＤＰｒｏｇｒａｍ，Ｃｈｉｎａ（Ｎｏ．２００７ＡＡ０４２００５），ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎ．Ｃｈｉｎａ（Ｎｏ．５０９７５１９３），ａｎｄｔｈｅＳｐｅｃｉａｌｉｚｅｄＲｅｓｅａｒｃｈＦｕｎｄｆｏｒｔｈｅＤｏｃｔｏｒａｌＰｒｏｇｒａｍｏｆＨｉｇｈｅｒＥｄｕｃａｔｉｏｎ。Ｃｈｉｎａ（Ｎｏ．２００６００５６０１６）．

万方数据第７期刘伟等：基于蚁群算法的工艺路线牛成及优化

１３７９

近年来，一些智能优化算法，如遗传算法［１≈］、蚁群算法［３ｑ］及模拟退火算法口３等，逐渐被用于工艺路线规划问题的研究并取得了一些成果。其中，蚁群算法是由Ｄｏｒｉｇｏ等人受自然界中蚁群寻找食物过程中发现路径行为的启发而首先提出来的［６。］。蚁群算法具有全局寻优、信息正反馈、启发式搜索和分布式计算等特征，在求解旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，ＴＳＰ）Ｉｓ］、Ｊｏｂ—Ｓｈｏｐ调度一３和资源二次分配［１们等组合优化问题时，表现出了良好的性能。针对面向多品种、小批量生产的ＣＡＰＰ系统中的工艺路线决策问题，本文在对被加工零件的特征进行知识表示和对基本蚁群算法进行改进的基础上，提出一种生成并优化零件加工工艺路线的算法。１零件特征的知识表示在ＣＡＰＰ系统中，关于零件特征的知识是对零件加工工艺路线进行规划和决策的基础，而知识表示应与知识本身相分离，这样，当知识更新时，相应的决策方法就不需要改变。１．１特征元如文献［１１］所述，将零件上具有加工意义的最基本的加工特征称为特征元。它是零件的基本信息单元，其属性可表示为一个四维的特征向量＾＝（ＩＤ，Ｆ，Ａ，Ｍａ，ｏｆ）。其中：，，表示零件的第ｉ个特征元；ＩＤ表示特征元编号；Ｅ表示特征类型；Ａ表示精度；Ｍａ表示零件所用材料；Ｏｉ表示加工序列。１．２加工元对于每个特征元＾，根据零件的材料、特征元的结构形状和加工要求，采用反向设计法，可以得到该特征元的加工链，表示为０；一｛ｏｉｌ，０，２，…，ｏｉ，…，ｏ。｝。其中０ｉ称为特征元，，的一个加工元。零件的加工工艺路线，是将各个特征元的所有加工元按一定顺序排列而成。为方便讨论，将所有加工元统一编号，表示成为一个集合。一｛Ｄ１，Ｄｚ，…，ｏ∥”，ｏＮ｝，Ｎ表示加工元的总数。对于加工元，有以下约定：（１）一个加工元属于且仅属于一个特征元，可以是一道工序，也可以是一个工步。（２）一个加工元属于且仅属于一个安装。（３）一个加工元使用且仅使用一把刀具。（４）一个加工元属于且仅属于一个加工阶段。因此，类似于文献［１１］对工序的描述，加工元也可以被表示成为一个六维的特征向量仉＝（Ｆ。Ｓ，Ｃ，ＦＳ，Ｆｔ，Ｍ）。其中：Ｆ表示特征元即加工表面；Ｓ表示加工阶段；Ｃ表示所用刀具；ＦＳ表示装夹表面，是零件上的另一个特征元；Ｆｔ表示所用夹具；Ｍ表示所用机床。

２工艺路线生成和优化的算法２．１优化目的。一｛ｏ，，ｏ：，…，ｏｌ’．”，ｏＮ）表示加工元集合。令Ｌ一｛Ｄｉ，Ｄ，∈０）表示。中元素两两连接的集合，则Ｇ一（ｏ，Ｌ）就表示一个图。因此，类似于ＴＳＰ，工艺路线的优化目的也是从Ｇ中找出长度最短的Ｈａｍｉｌ－ｔｏｎｉａｎ圈。２．２加工元距离加工元之间的距离指它们的相似程度，用加权海明距离ｄ。（ｉ，Ｊ）表示，ｄ。（ｉ，歹）：叫ｐ（ｏｉ．Ｆ，ｏｉ．Ｆ）＋训ｓ艿（ｏ，．Ｓ，Ｄ，．Ｓ）＋硼ｐ（Ｄ。．Ｃ，Ｄ，．Ｃ）＋（训舟＋ＷＲ）・ｍａｘ［３（ｏｉ．ＦＳ，０ｉ．ＦＳ），３（０，．Ｆｔ，ｏ，．Ｆｔ）］＋ｗＭ３（Ｄｉ．Ｍ，Ｖ卜Ｍ）。（１）其中：以．Ｆ，ｏｉ．Ｓ，ｏｉ．Ｃ，ｏｉ．ＦＳ，ｏ，．Ｆ。，Ｄ，．Ｍ分别表示加工元ｏ。所加工的表面、加工阶段及其所用的刀具、装夹表面、夹具和机床；叫Ｆ，硼ｓ，硼ｃ，ＷＦＳ，叫Ｒ，叫Ｍ分别表示上述各项在零件加工中所占的权重；ｍａｘ［￥（ｏ：．ＦＳ，Ｄ卜ＦＳ），３（ｏ，．Ｆｔ，，．Ｆｔ）］是求ｄ（ｏ。．ＦＳ，Ｄ，．ＦＳ）和３（ｏｉ．Ｆｔ，Ｄｉ．Ｆｔ）的最大值，这表示只要装夹表面和夹具中的一个发生改变，就意味着要重新装夹；艿（ｚ，ｙ）是一个判断函数，ｆ１．ｚ≠ｖ２３（ｘ，ｖ）一｛’。一

（２）

１０，ｚ—Ｙ。

由式（１）可知，加工元之间的距离越大，它们之间的相似程度越小。２．３禁忌准则和约束条件的处理蚂蚁必须走合法的路线，在同一次迭代中，每个加工元只允许访问一次。设ｔａｂｕ。为蚂蚁ｋ的禁忌表，蚂蚁ｋ每经过一个加工元，都将其存放在自己的禁忌表ｔａｂｕｔ中，并且不允许再次访问。当所有Ｎ个加工元都被加入到ｔａｂｕ。中时，蚂蚁ｋ就完成了一次迭代。加工元的组合不是任意的，必须满足一定的约束条件。常见的约束条件有：先粗后精、先面后孔、先主后次和基准先行，也可以由用户自定义其他约

万方数据