基于遗传算法求解作业车间调度问题本科毕业设计论文(编辑修改稿)

基于遗传算法求解作业车间调度问题本科毕业设计论文(编辑修改稿)内容摘要：

MJ（ i， j） 上的加工时间。 同样地，如果某工件的工序数不足 12max{ , , }nP P P，那么其空余的位置用 0 填满。 1 11 2 1 1111 2 1 ( 1 )1 1100 000ijPjjjpj j n j Pn n n iiiP PPP P PP P P PPPPT T TTT T T T （ ） jM ：工件排列阵，此为 12m ax{ , , }nP P P n矩阵。 (, )jMi j 表示在 i机器上排在第 j位 加工的工件号， (, )jMi 表示 i机器上依次加工的各工件的排列。 同上，如果某工件的工序数不足 12max{ , , }nP P P，那么其空余的位置用 0 填满。 事实上，工件排列阵就是调度的一种表示形式。 由此，我们可以给出一般性的车间作业调度数学模型的 定义 : 如 果 对 应 于 一 个确 定 的 jM ，满足 * 1 2( ) m i n { ( ) , ( ) , ( ) }nj j j jf M f M f M f M 或* 1 2( ) m a x { ( ) , ( ) , ( ) }nj j j jf M f M f M f M。 即 jM 使得目标函数 ()jfM 取值最小 (或最大 )，且与 MJ 相容，则称 jM 为车间作业调度问题在此目标函数下的最优解。 生产 调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从两个方面来考虑 :生产成本和生产时间。 调度问题从生产成本方面来考虑，其优化目标有 :库存最少、在制品最少、设备利用率最高等。 从生产时间方面来考虑，其优化目标有 :最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。 两个方向的优化目标之间彼此不是相互孤立的，其中的许多具体目标之间的联系很密切，有的相互促进，有的相互冲突，也有的毫无联系。 课题研究内容及结构安排 本文共分为三 章。 第一章简要介绍了车间调度问题和求解调度问题的基本方法 ；第 辽宁科技大学本科生毕业设计 第 5 页 二章介绍了遗传算法的基本理论；第三章用遗传算法来解决车间调度问题 ,其中介绍了常用的几种编码方式 ,在比较的情况下提出本文主要用基于操作的编码方式 .还有提出了几种主要的遗传算子。 并且以四个工件四个机器问题进行举例 ,说明了用遗传算法解决车间调度问题的可行性。 辽宁科技大学本科生毕业设计 第 6 页 2 遗传算法相关理论与实现技术 遗传算法 (Geic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者 Holland 于 1975 年首先提出来的 ［ 7］。 它摒弃了 传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程 ［ 8］。 它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。 自然进化与遗传算法 自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制产生了极大的兴趣。 化石记录表明我们所观察的复杂结构 的生命是在相对短的时间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。 虽然目前人们对进化机制在一些方面还没有弄清楚，但它们的一些特征已为人所知。 进化是发生在编码染色体上，通过对染色体的译码部分生成生物体，但下面几个关于进化理论的一般特性已被广大人们所接受。 ，而不是发生在它们所编码地生物个体上。 ，哪些适应性好地个体的染色体经常比差的个体的染色体有更多的繁殖机会。 ，变异可以使生物体子代 的染色体不同于它们父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生有很大差异的染色体。 有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。 大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。 自然选择的原则是适应者生存，不适者淘汰。 自然选择决定了群体中那些个个体能存活并繁殖，有性生殖保证了后代基因中的混合与重组。 比起那些仅包 含 单个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的后代进化要 快得多。 辽宁科技大学本科生毕业设计 第 7 页 基本 遗传算法 遗传算法的基本思路 ； 将求解空间中的每一个点进行编码，并从求解空间中任选 N个点组成初始群体；。 运用选择、交叉、变异算子产生新一代群体； ，若找到满足问题的最优解，结束；否则，转步骤 3。 遗传算法的 模式定理 选择操作是遗传算法中体现“适者生存”的关键一环，它能控制高适应度的模式成指数级增长。 最常用的选择方式是“轮盘 赌”法。 其传统实现建立在逐项比较的基础上，算法复杂度为 O（ n＾ 2）。 通过把各码链适应值转换为一组具有线性序的区间，从而可利用二分查找法实现“轮盘赌”选择操作的递归算法，使时间复杂度下降到 O（ nlog2n）。 交换操作是有规则的信息交换，它能创建新的模式结构，但又最低限度地破坏选择操作过程所选择的高适应度的模式。 假设交换操作是采用的单点随机杂交方式，随机选取杂交的起始位置，交叉概率为 Pc，两个具有相同模式 H 的个体发生交换，即杂交操作，不会改变模式 H。 但是如果其中一方个体不具有模式 H， 则有可能会引起另一个个体模式的改变。 其中一方不具有模式 H 的概率为 1 p(H, t)，当两个个体发生交换时，如果引起模式 H 的改变，只可能将交换的起始位置选择在第一个模式位到最后一个模式位之间的任何一个位置上，此时，使模式 H 生存的概率 Ps，为 : ()1 1scHPPl  () 在交换过程中，可能使两个都不具备模式 H 的个体经交换后产生模式 H，故生存概率（ ()1 1c HP l ）只是一个下界，则有： 辽宁科技大学本科生毕业设计 第 8 页 ()11scHPPl  () 综合考虑选择操作，模式 H 在下一代中的数量可以用下式来综合估计 : _( ) ( )( , 1 ) ( , ) ( 1 )1cf H Hm H t m H t p lf     () 从上式可以看出，模式的平均适应度高于群体平均适应度，并且具有短 定义距的模式，将在下一代中成指数级的增长。 通过变异操作对个体串中单个位置进行代码替换，替换的概率为变异概率 Pm，则该位置不发生变异的概率为 1Pm。 要使一个模式 H 在变异操作过程中不被破坏，就要保证模式 H 中确定位必须保证不变，因此，模式 H 保持不变的概率为 : ()(1 ) 1 ( )OHs m mp p P o H     () 上式中 O(H)为该模式的阶数。 综合上面所述，考虑到选择操作、交换操作和 变异操作对模式的影响，则第 t 代种群 P(t)经过遗传操作后下一代种群 P(t+1)具有模式 H 的个体总数为 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf    () 该式表示了下述的模式定理。 模式定理 :在遗传算子选择、交换、变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将得以指数级增长。 模式定理保证了较优的模式 (遗传算法的较优解 )的数目呈指数增长，为解释遗传算法机理提供了数学基础。 由模式定理可知，具有低阶、短定 义距以及平均适应度高于群体平均适应度的模式在后代中呈指数级增长。 这些模式在遗传中很重要，称为基因块。 基因块假设 :遗传算法通过短定义距、低阶以及高平均适应度的模式 (基因块 )，在遗传操作下相互结合，最终接近全局最优解。 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在。 而基因块假设则指出了在遗传算子的作用下，算法具有生成全局最优解的能力，即能生成高阶、长定义距、高平均适应度的模式，最终生成全局最优解。 辽宁科技大学本科生毕业设计 第 9 页 上述结论并没有得到证明，因而被称为假设。 目前已经有大量的实践证据支持这一假 设，尽管大量的证据并不等于理论证明，但是至少可以肯定的是对很多经常碰到的问题，遗传算法都是适用的。 遗传算法的收敛性分析 遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。 与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。 通常，种群太小则不能提供足够的采样点，以致算法性能很差。 种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。 影响 选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。 如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率 1 收敛于全局最优解。 交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。 交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉。 概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。 变异操作是对种群 模式的扰动，有利于增加种群的多样性。 但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。 遗传操作对收敛性的影响，可利用马尔可夫链对遗传算法进行分析，从而论证了遗传算法在收敛性方面的一些重要性质，有力地支持了遗传算法的理论基础。 由马尔可夫链推导出来的一些结论 :基本遗传算法收敛于最优解的概率为 1,使用保留最优个体策略的遗传算法收敛于最优解的概率为 1。 隐含并行性定理 :遗传算法所处理的模式总数与其群体规模 N 的立方成正比，即 : m=O(N3) （ ） 由该定理可知，虽然表面上每代处理的个体数目都是一定的，但是由于每个个体都 辽宁科技大学本科生毕业设计 第 10 页 隐含着多种不同的模式，所以每次参与遗传算子操作的个体却不仅仅是两个。 从总体上来说，每代之间所处理的个体要远大于其表面的数目，这就是遗传算法独特的隐含并行性。 由隐含并行性定理可知，虽然表面上每代仅对 N 个个体处理操作，而事实上处理了O(N3)个模式，且无需额外存储。 隐含并行性为遗传算法的高效性提供了理论依据。 基本遗传 算法参数说明 对遗传算法性能有影响的参数主要有 :种群数目 N、交换概率 Pc、变异概率 Pm、代沟 G、尺度窗口 W、和选择策略 S 等。 (population size) 种群数目的多少直接影响到遗传算法的优化性能和效率，种群选择太小时，不能提供足够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解。 种群选择过大时，虽然能避免早熟收敛，但是增加了计算量。 (crossover rate) 交换概率 Pc 用于控制交换操作的频率。 交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的 现象。 交换概率太小的时候又容易产生搜索停滞不前的现象。 (mutation rate) 变异概率 Pm。 增加种群多样性具有重要意义。 通常选取一个较低的变异概率。 如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，则不能产生新个体，不利于种群的多样性。 (。