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

提出本文主要用基于操作的编码方式 .还有提出了几种主要的遗传算子。 并且以四个工件四个机器问题进行举例 ,说明了用遗传算法解决车间调度问题的可行性。 辽宁科技大学本科生毕业设计 第 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。 增加种群多样性具有重要意义。 通常选取一个较低的变异概率。 如果变异概率太大的时,遗传算法易变成随机搜索,如果变异概率太小,则不能产生新个体,不利于种群的 多样性。 (generation gap) 代沟 G 用于控制每一代群体被替换的比例,每代有 N (1G)个父代个体选中进入下一代种群中,该参数和交换、变异概率以及选择策略有很大关系,它并不是一个初始参数,而是评价遗传算法的一个参数。 (scaling window) 该参数用于作出由目标值到适应度函数值的调整。 (selection strategy) 一般来说有两种选择策略,一种为纯选择,种群中每个个体根据其适应度值进行比例选择,即个体被选择的概率与其适应度值成正比。 另一种为 保优策略,首先进行纯选择,把目前最优个体直接加入下一代种群中,该策略是为了防止最优解的丢失, 但在实际应用中往往采取这两种选择策略结合的方法,并做适当的变型。 辽宁科技大学本科生毕业设计 第 11 页 遗传算法的优缺点 遗传算法的优点 遗传算法在解决优化问题过程中有如下优点 : ,而不是从单个解开始。 这种机制意味着搜索过程可以跳出局部最优点,能很好地将局部搜索和全局搜索协调起来,达到全局最优点。 ,遗传算法的初始种群本身就带有大量与最优解甚远的信息,通过选择、交换、 变异操作,能迅速排除与最优解相差极大的串,这是一个强烈的滤波过程,并且是一个并行滤波机制。 ,而不是对参数本身,因此遗传算法具有灵活性高的特点。 ,而非传统方法的采用目标函数的导数信息或者求解问题域内知识,因此具有普遍适应性和可规模化的特点。 ,容易形成通用算法程序。 由于遗传算法使用适应度值这一信息进行搜索,并不需要问题导数等与问题直接相关的信息。 ,在存在噪声的 情况下,对同一问题利用遗传算法求解所得的结果是相似的。 遗传算法的缺点 ,而不能达到全局最优。 ,用遗传算法求最优解比较困难,因为染色体种群很可能过 早地 敛,而对以后变化了的数据不再产生变化。 对于这个问题,研究者提出了一些方法增加基因的多样性,从而防止过早的收敛。 其中一种是所谓触发式超级突变,就是当染色体群体的质量下降 (彼此的区别减少 )时增加突变概率。 另一种叫随机外来染色体,是偶尔加入一些全新的随机生成的染色体个体,从而 增加染色体多样性。 ,但交叉和变异的重要性存在争议。 一种观点认为交叉比变异更重要,因为变异仅仅是保证不丢失某些可能的解。 而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新,对于初期的种群来说,交叉几乎等效于。
阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体),仅供学习参考。 用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权,请联系我们反馈本站将在三个工作日内改正。