基于遗传算法-多智能体的FMS刀具在线调度

本资料包含pdf文件1个，下载需要1积分

柔性制造系统flexible manufacturing system，FMS与-般生产系统的显著区别之-在于 FMS加工设备的柔性，表现在加工设备能够加载多种刀具从而完成不同的工艺过程。因此，FMS系统- 般都具有-个中央刀具库和若干机床刀具库，系统运行时，加工设备会根据实际需要更换刀具，这可能造成多台设备争用资源有限的刀具。基此刀具的调度是 FMS的-个重要内容↑年来，国内外对 FMS刀具的调度研究逐渐增多，文献1结合刀具需求和主生产计划，给出粗糙层次上的数学模型；文献2提出了基于排队论的刀具需求模型；文献3-4把遗传算法及扩展算法引入刀具需求预测与调度，以提高刀具调度效率；文献5综合考虑工件流和刀具流，提出了双重遗传算法的调度方法，减少 FMS的完工时间；文献6提出了基于合同网协议多智能体刀具调度系统，收稿 日期：2013-07-25基金项目：辅省自然科学基金项目2009J01309；辅侍育厅 A类基金项目JA11192；辅工程学院科研发展基金项目GY-211057作者简介：黄恩洲1979-，男汉，辅仙游人，讲师，硕士，研究方向：系统建模、仿真、优化.

370 辅工程学院学报 第 11卷以提高调度的效率。这些研究主要集中于两个方面，其-建立刀具的静态调度模型，但是静态调度模型须按照工件调度进行，若有突发情况，则静态调度无能为力，如文献1-5；其二建立刀具的动态调度模型，能够对突发情况及时处理，但是动态调度方案往往无法达到较优水平，如文献6。

本文提出-种基于黑板协议的多智能体刀具调度管理模型，并使用遗传算法对刀具进行调度，以弥补静态调度和合同网协议多智能体调度系统的不足。

1 基于多智能体的 FMS刀具调度管理模型智能体是某个环境中的计算机系统，智能体在该环境中自主行动以实现其设计目标。多智能体系统是通过某种协议而松散联系的智能体形成的网络，各智能体之间竞争与合作，共享知识和信息，解决单个智能体不能处理的问题。

本文把 FMS刀具调度管理系统建模成智能体社会，社会成员分为 3类：管理智能体、刀具智能体和运输智能体，如图1所示。

图1 刀具调度管理的多智能体体系结构Fi昏 1 M ulti·agent intelligent system structure fortools scheduling management刀具调度管理分为两个过程，第-个过程为刀具出库分配，第二个过程为刀具用毕入库。

1.1 刀具出库过程1管理智能体接收到外部需求信息，并将所需刀具的信息包括需求方、所需刀具编号、刀具几何参数、加工精度等内容公布于黑板上；2刀具智能体从黑板上读取到需求信息后，立即在刀具数据库中寻找合适的刀具，形成刀具信息报表，将满足要求的刀具信息写入黑板；3管理智能体的黑板监控器检测到此信息后，触发决策拈，按-定的刀具调度策略将刀具分配到各个机床上，并生成刀具运输任务公布于黑板上；4运输智能体读取到刀具运输任务后，形成运输设备信息报表，写入黑板；5管理智能体根据黑板上的信息规划刀具调度路线，通知运输智能体进行运输，并通知刀具智能体及时更新刀具数据库；6运输智能体根据任务情况更新运输设备状态数据库。

1.2 刀具用毕入库过程1管理智能体接收到生产任务结束信息后，制订刀具回收清单生成刀具回收运输任务，发布于黑板上；2运输智能体读取信息后形成运输设备信息报表写入黑板；3管理智能体根据此信息形成刀具回收运输路线，通知运输智能体，由刀具运输设备将刀具收回，经入库前处理后重新进入刀具库；4管理智能体通知刀具智能体及时更新刀具数据库。

2 刀具动态调度数学模型合同网协议的多智能体调度系统考虑各智能体自身利益，通过市场法则达到智能体与智能体之间的利益平衡点 J，该法极易陷入局部最优。

本文采用黑板协议的多智能体系统，由管理智能体统筹全局利益，也就是有-个全局的目标函数，理论上可以达到全局最优。

设 表示机床序号， 表示零件序号，k表示工序序号，t表示刀具序号，另设r1，零件 工序 k需要刀具 f 0。否则1，机床i中分配刀具t” L0，否则fl，机床 加工零件 工序kijk 0，否则假定全局目标为刀具交换次数最少，则调度模型如公式1所示：外部信息第4期 黄恩洲：基于遗传算法 -多智能体的FMS刀具在线调度 371min z∑∑∑∑ 1- ·Yi k t∑Y 1∑ ≤Ci由于在染色体编码时，每台机床的编码位数刚好为该机床刀具库容量，因此染色体交叉后产生的新个体满足公式1的约束条件，即仍然为1 可行解。

3.5 算法及结果比较， Y 0或 1 定义了以上的基本方法后，就可以编制算法其中c表示机床刀具库容量。显然，该模型为0-1整数规划问题。若用-般的整数规划算法求解，随着问题规模的增大，求解的时间呈指数增长，影响在线调度。为了减小调度时间，使其满足在线调度对于时间的要求，本文采用遗传算法。

3 基于遗传算法的模型优化3.1 染色体编码设种群大小为PopSize，机床数量为 ，机床刀具库容量为c，则第 个染色体为： l，l， 1.2，， lc， 2，l， 2，2，，2c，，XM， 肥，， 使用二进制编码， 取0或 1。

3.2 适值函数适值函数是区分群体中个体好坏的标准，是进行自然选择的唯-依据，由于公式1目标函数为最携，且最大值最坏情况容易估算出，目标函数映射为适值函数：F 进行刀具调度，算法的基本步骤为：1随机产生大小为 PopSize的初始种群，按公式2计算每个染色体的适值；2按公式3法则选择个体，以概率P 进行交叉，概率 P 对随机位进行变异，更新种群；3计算新种群每个个体的适值，保存最优计算结果；4判断是否达到最大遗传代数NG，是的话，最优结果集中的最大值即为最优值，否则转到步骤 2。

假设种群大小为PopSize50，最大遗传代数为NG100，交叉概率P 0.9，变异率P 0.05，机床数量 lO，工件数量为 20，刀具数量为100，每台机床的刀具库容量为25，经过迭代运算，最优值为35次，迭代时间为10 050毫秒。与隐枚举法和其它启发式算法相比结果如表 1所示。

表 1 各种算法计算结果比较2 m ·- m aX该适值函数对目标函数进行尺度变换，能够较好反应染色体的相对优劣。

3.3 选择策略选择是从当前种群中按照-定概率选出优良的个体，这里采用轮盘赌Roulete Whee1选择策略，对于个体 ，适值为F ，被选择的概率为P ： 3∑F 3.4 交叉运算交叉运算能够使父代的特征遗传给子代，这里采用二点交叉，即随机产生2个相异断点，然后将两个个体断点之间的串互换成两个新个体，如下所示tX1A1 1 C1 X1 A1 1 2 C1 A2 召2 C2 A2 1 。l C2Comparison ofthe results among different algo-rithms从表 l可以看出，3种算法中隐枚举法得到的结果最好，但是耗时最长，适合静态调度而不适合动态调度；启发式算法耗时最短，但结果不佳；而遗传算法耗时比启发式算法仅多 1%，结果却更接近最优解，相 比之下遗传算法在性价 比上最好。

4 结语本文提出的 FMS刀具调度多智能体模型比传统刀具调度管理更灵活，且极具智能化，只要向系统输入需求信息，就可以完成从刀具分配到回收的整个过程而无需人工的参与。另外，本文提372 辅工程学院学报 第 11卷出的遗传算法能够为刀具进行在线优化，大大提高 FMS刀具调度系统的性能。然而，也应该看到，本文只是单纯从 FMS刀具角度探讨问题，如若结合 FMS工件调度，构建 FMS工件流和刀具流的统-调度系统，将会使 FMS的性能发挥得淋漓尽致，而这也是本文下-步研究的方向。