基于遗传禁忌混合搜索算法的设备布局研究

万方数据
第４期
竺长安等：基于遗传禁忌混合搜索算法的设备布局研究
·６３１·
复杂系统优化计算的自适应概率优化技术。它将问题的求 解表示成染色体适者生存的过程，通过染色体的复制、交叉 和变异等操作使染色体不断进化，最终收敛到最适应环境 的个体，从而求出问题的最优解或满意解幢Ｊ。
禁忌搜索最早由Ｃｌｏｖｅｒ提出的，是对局部邻域搜索的一种 扩展，通过引入—个灵活的存储结构和相应的禁忌准则来避免 迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进 而保证多样化的有效搜索以最终实现全局优化【２Ｊ。
ａｌｇｏｒｉｔｈｍ ａｌｇｏｒｉｔｈｍ ｌａｙｏｕｔ．Ｔｈｅ ｐａｐｅｒ ｃｏｍｂｉｎｅｓ ｇｅｎｅｔｉｃ
ｗｉｔｈ ｔａｂｕ ｓｅａｒｃｈ ｔｏ ｍａｋｅ ｔｈｅ ｎｅｗ
ｈａｖｅ ｔｈｅ ｔＷＯ ａｌｇｏｒｉｔｈｍｓ’ａｄ—
ａｌｇｏｒｉｔｈｍ， ｖａｎｔａｇｅｓ．Ｉｔ ｓｅａｒｃｈｅｓ ｎｅｗ ｓｏｌｕｔｉｏｎｓ ｉｎ ｔｈｅ ｍｕｌｔｉｐｌｅ ｉｎｄｉｖｉｄｕａｌｓ ｗｈｉｃｈ ｉｓ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｇｅｎｅｔｉｃ
ａｎｄ ｔａｂｕ ｓｅａｒｃｈ ｈｙｂｒｉｄ
ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ａｌｇｏｒｉｔｈｍ，ｉｔ ｉｓ ｖｅｒｙ
ｕｓｅｆｕｌ ｉｎ ｓｏｌｖｉｎｇ ｔｈｅ ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ ｓｕｃｈ ａｓ ｔｈｅ ｍａｃｈｉｎｅ ｌａｙｏｕｔ ｐｒｏｂｌｅｍ．
万方数据
·６３２·
系统工程与电子技术
第２８卷
表１零件工艺流程及数量
，／，，，一，—。：＠ｉ！…；｝！｝！＠ｉ｝！。一：ｊｉ』＠；ｉ…｝！÷！；剧！：ｊｉ｛掣｝｛；！孥
每臣霉（圈１ｆ７ ７一■…缅矿…一、ｊ（）哆嘲圈
、、｜～嚆高％者孺≯函 ｌ堡、冲匡Ｉ ｌ堡韭匡ｌ ｌ堡韭匿【匿必
图ｌ单向环型布局
在设备布局设计的第一阶段，主要考虑系统运行费用，
ｗｈｉｌｅ ｉｔ ｈａｓ ｍｅｍｏｒｙ ａｂｉｌｉｔｙ ａｎｄ ｅｆｆｉｃｉｅｎｔ ｈｉｌｌ—ｃｌｉｍｂｉｎｇ ｃａｐａｂｉｌｉｔｙ ｗｈｉｃｈ ｉｓ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔａｂｕ ｓｅａｒｃｈ．Ｔｈｒｏｕｇｈ ａｎ
ａｌｇｏｒｉｔｈｍ ａｌｇｏｒｉｔｈｍ ｅｘａｍｐｌｅ，ｗｅ ｃａｌｌ ｃｏｎｃｌｕｄｅ ｔｈａｔ ｇｅｎｅｔｉｃ
的全局搜索能力。简单遗传算法的交叉操作使得群体的染 色体具有相似性，而且对重复产生的染色体不能进行有效禁 忌，容易出现迂回搜索，这是遗传算法早熟的主要根源。为 避免早熟现象的产生，在交叉算子中引入了记忆功能，对于 每对配对个体组交叉产生的个体，通过设置禁忌表来决定其 接受还是舍弃，为了保留优良个体，在此引入藐视准则。
在制品在系统中停留时间等定量要求。这两个参数是越小
越好，它们皆与完成全部加工任务运输工具在系统中的总
行程有关，运输工具在系统中的总行程越小，系统运行费用
越低，运输工具在系统中的总行程越小，在制品在系统中的
停留时间越短，因此设备布局的目标变成了追求运输工具
ｍａｘ（ｏ，宦等））ｍ 在系统中的总行程最小，所以目标函数是
算法是一种行之有效的算法，对解决设备布局这类组合优化问题具有实用价值。
关键词：遗传算法；禁忌搜索；遗传禁忌混合搜索算法；设备布局
中图分类号：Ｎ９４
文献标识码：Ａ
Ｓｔｕｄｙ ｏｎ ｍａｃｈｉｎｅ ｌａｙｏｕｔ ｐｒｏｂｌｅｍ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ Ｔａｂｕ ｓｅａｒｃｈ ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ
ＺＨＵ Ｃｈａｎｇ－ａｎ，ＱＩ Ｊｉ—ｙａｎｇ，ＺＥＮＧ Ｙｉ
（Ｄｅｐｔ．ｏｆ Ｐｒｅｃｉｓｉｏｎ Ｍａｃｈｉｎｅｒｙ ａｎｄ Ｐｒｅｃｉｓｉｏｎ Ｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ，Ｕｎｉｖ．ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ，Ｈｅｆｅｉ ２３００２６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｔｈｅ ｍａｃｈｉｎｅ ｌａｙｏｕｔ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｐａｒｔ ｏｆ ｔｈｅ ｄｅｓｉｇｎ ｏｆ ａ ｍａｎｕｆａｃｔｕｒｉｎｇ ｓｙｓｔｅｍ．Ｉｔ ｈａｓ
某企业为完成某项工程，组建了柔性加工工段，该工段 需要加工１０种零件，根据要加工零件的工艺，采购了９台 加工设备，分别是数控车床３台，立式加工中心１台，卧式 加工中心２台，数控线切割机床１台，电火花加工机２台。 零件的工艺流程和加工数量如表１所示（为叙述方便，１０ 种零件分别用声１，声２，…，ｐｌＯ表示，９台加工设备分别用 ７７／１，埘２，…，ｍ９表示，ｍＯ表示装卸站）。考虑单向环型物 流路径具有结构简单、物流控制容易、物料处理柔性高等优 点，在本项目中，采用单向环型布局（如图１），物料运送工 具采用单向有轨小车，每种零件从装卸站进入系统，当被加 工完成后，由有轨小车将其运送到下一个工序所需的设备 的位置，若该设备处于空闲状态，则立即加工，否则存储在 缓冲区，等待空闲状态。
存，物料流动的阻碍，生产时间的延长和生产效率的降低。 因此，探讨研究制造系统的设备布局具有重要的理论意义 和应用价值。
设备布局根据物流设备的不同，可以分为线性单行布 局，线性多行布局，Ｕ型布局，环型布局【１ Ｊ。无论哪种布局形 式，确定设备的具体位置则是设备布局设计的关键所在，本 文在考虑遗传算法早熟收敛问题和禁忌搜索自适应优点的 基础上，综合运用禁忌搜索和遗传算法，提出了遗传禁忌混 合搜索的设备布局算法，通过实验证明了该算法的有效性。
１遗传禁忌混合搜索算法
遗传算法是Ｈｏｌｌａｎｄ教授于２０世纪６０年代受生物进 化论的启发而提出的一种基于生物遗传和进化机制的适合
收稿日期：２００５—０３—０２；修回日期：２００５一０８—３０。 作者简介：竺长安（１９５７～），男，教授，博士，主要研究方向为智能机器人，现代集成制造系统。Ｅ—ｍａｉｌ：ｑｉｊｙ＠ｍａｉｌ．ｕｓｔｃ．ｅｄｕ．ｃｎ
ｈｙｂｎｄ蛔‰；１Ｔ蝈ｔｃｈｉｎｅ Ｋｅｙ ｗｏｒｄｓ：ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｔａｂｕ ｓｅａｒｃｈ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔａｂｕ ｓｅａｒｃｈ
ｌａｙｏｕｔ
０引 言
设备布局的设计在国内一直是被忽视的一个领域，事 实上，设备布局设计是制造系统设计的重要组成部分，设备 布局是否合理对整个制造系统的总体功效有着非常重要的 影响。Ｔｏｍｐｋｉｎｓ和Ｗｈｉｔｅ指出因设备布局不合理所产生的 运行费用占制造系统整体运行费用的２０％～５０％，而优良 的设备布局可使这一费用减少１０％～３０％；优良的设备布 局还能加快物料处理的效率，减少在制品的停留时间，提高 企业生产率－１ｊ，使企业对市场需求做出及时地响应，增强企 业的市场竞争力；优良的设备布局可以减少工件缓冲区的 容量，缩小制造系统所占用的空间，减少制造系统建设的费 用。反之，若设备布局设计不合理，将会导致过量的中间储
步骤５判断群体是否进化到预先指定的代数，或者 达到预先指定的要求，如果达到，则停止进化；否则，转至步 骤３，继续进化。
步骤６解码。当群体进化到指定的代数时，或者满 足预先指定的要求，则对其解码，即由基因型转化为表现 型，输出最终结果。
２设备布局应用实例
制造系统布局的设计需要考虑多种因素，既包括系统 运行费用最小，在制品在系统中停留时间最短等定量要求， 又包括布局的美观性，操作的舒适性、生产的安全性等定性 要求，它是一个多目标优化问题。～般情况下分为两个阶 段，第一个阶段主要考虑定量要求，解决设备最优布局序列 问题，该阶段主要通过各种算法加以解决；第二阶段主要考 虑定性问题，虚拟现实技术能够很好地解决这一问题。 ２．１问题的描述
，：１０，ｓ
ｍｉｎｆ（ｎ）＝∑ｉ＝１１（善Ｉ 、『Ｉ
／
Ｔ
、、
’一ｚ，
一ｌ Ｌ，十ｌ，。’７
式中：Ｓｉ——零件Ｐｉ的工序数，Ｌｉ——加工零件Ｐ，的第Ｊ
道工序所用的机床的位置，Ｌｍ十１）——加工零件Ｐ，的第ｊ ＋１道工序所用的机床的位置，ｑ，——零件Ｐｉ的数量， 口——当前布局，可以用加工设备的排列表示。
遗传禁忌混合搜索算法的运算过程如下所述。 步骤１初始化。确定遗传算法的参数，如遗传代数 丁，种群数量Ｍ，交叉概率只，变异概率Ｐ卅等，随机生成初 始群体Ｐ（Ｏ）。 步骤２编码。根据不同的问题，采用不同的编码方 法，对初始群体Ｐ（Ｏ）的个体编码，即由个体的表现型转换 为基因型。 步骤３个体适应度评价。计算群体中的各个个体的 适应度，作为下一步选择算子的重要依据。 步骤４生成新一代群体。对当代群体Ｐ（ｔ）通过选择 算子、交叉算子、变异算子等算子的操作生成新一代群体 Ｐ（ｔ＋１）。 步骤４．１选择遗传算法通过选择算子来实现对群体 中的个体优胜劣汰，适应度较高的个体以较高的概率遗传 到下一代，适应度较低的个体以较低的概率遗传到下一代， 从而促使算法朝着最优解方向前进。在遗传禁忌混合搜索 算法中，采用赌盘选择方式，这与简单遗传算法没有什么区 别，在这里就不再赘述。 步骤４．２交叉将群体中Ｍ个个体以随机的方式两两 配对，组成Ｍ／２对配对个体组，每对配对个体组的个体以某 种方式交换其染色体的部分基因，从而产生两个新个体。交 叉算子是遗传算法产生新解的主要手段，它决定了遗传算法
（中国科学技术大学精密机械与精密仪器系，安徽合肥２３００２６）
摘要：针对设备布局影响制造系统的总体功效的问题，但同时遗传算法在实际应用中，出现早熟现象，爬山
能力弱，等一系列缺点提出遗传禁忌混合搜索算法，该算法将遗传算法和禁忌搜索相结合，遗传算法的交叉算子
中增加记忆功能，避免迂回搜索，以禁忌搜索作为遗传算法的变异算子。通过实例计算，证明遗传禁忌混合搜索
第２８卷第４期 ２００６年４月
文章编号：１００１—５０６Ｘ（２００６）０４—０６３０—０３
系统工程与电子技术 Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ
Ｖ０１．２８ Ｎｏ．４ Ａｐｒ．２００６