基于遗传算法的资源优化选择.pdfVIP

基于遗传算法的资源优化选择 基于遗传算法的资源优化选择 李言肖继明郑建明王平洪伟 (西安理工大学) ■翼本丈针对生产实际中经常遇到的资源选择问题，提出了一种基于遗传算法(G^)的优化方法， 来解决生产实际中的多机床选择问题．设计了相应的编码规则以及遗传操作符．给出了完整的算法并用C 语言实现．优化结果表明，所设计的算法思想正确，是盘好的优化算法，可以满足集成化生产的需求． 美■调遗传算法{G^)资源选择 优化 1．引言 在实际生产中资源选择、匹配与优化一直受到研究者的重视。生产调度就是这样问题的 一个重要应用，特别是在集成制造环境下，考虑各选工艺提供多台资源可供选择，问题就变 得更加复杂，如何对这些众多的资源进行选择和分配，以解决生产调度过程的瓶颈，提高调 度系统柔性，使生产过程达到最优就成为矛盾的焦点。任务分配模型为解决这一问题提供了 决调度中的多机床选择问题，取得了很好的效果。 2．任务描述 设有n个工序，耍安排到车间的n台机床上去，每台机均可加工这些工序(不能完全加 工的情况在后边讨论，而每台机床加工范围和精度等级不同，加工的费用和时间也会不同。 问题是如何选择会使方案最优。设第j台机床加工第i个工件的时间用e。表示，则构成效益 矩阵(P。】…。引入分配(或叫解)矩阵【‘]…。 其中 Z，=I表示第i个工序在第j台机床上加工 0表示第i个工序不在第j台机床上加工 则极小化问题的数学模型，可用下列形式表示： 三上 minZ=∑∑e口·矗 (1) ∑％ (2) {‘ ∑％ (3) 户I 约束条件2表示每一工件一次只能安排到一台机床上，约束条件3表明，每台机床在同 一时刻只能加工一个工件。如果不满足这两个条件，将产生非法解。 3．遗传算法研究 GA作为一种很好的优化有哪些信誉好的足球投注网站方法已在许多工程问题中得到应用。1。在讨论适合解决上述 RP技术与快速模具制造 问题的遗传算法之前，先对一些符号定义如下： Ⅳ： 染色体长度： Z： 群体大小； P。，n，P。：分别表示交叉率，到位率和变异率： C。(，)： 第，代群体中的低足个染色体串： 以(，)： 第r代群体中染色体串C。(f)的适度函数值； 只，只： 随机选择的两个染色体作为亲本； 0l，n：由只和只经遗传操作产生的后代： 被安排在机床；上加：亡。 3．1问题的染色体编码 本文设计了一种称之为机床——工件联系参数编码法。编码原理是染色体的每一位和确 定的机床代号相对应，如第一位表示1号机床，第二位表示2号机床，依次类推。而各位上 的值表示工件编号。因此染色体串的长度和机床数目相同。其含义是箢，基因位上的基因值i 表示用，号机床加工第i号工件。则可用关系Ac。(，)=f将工件安排到相应的机床上去。例 到3号机床上。这就预示蓿南，=1，x。，=1，等等，这样的编码方法直观，容易使人理解。 3．2遗传操作符设计 根据本文的研究对象，设计了混合交换、倒位和互联变异三种操作符。 (1)混合交换：设有N位长度的两个串作为亲本只和昱，随机选取r。其中1≤r≤N，交换 后的后代为0。和q，则有如下关系： fr Aoj(f)=Apl(i)t 。4p2(f)，f≥， A02(i)=AP2(i)，i≥r Ap2(f)，ir (4) 对于资源分配和机床选择问题，这样的简单交换往往产生非法解，例如只=(5，3，2，1， 上加工的条