（应用数学专业论文）供应计划问题的遗传算法求解.pdf

摘要 供旋计划目遐是生产和销售中十势霪鬻的闷题如何在资源有限秘米来需求不确定 麓1 l 蓍鬟下，实际努配嚣韩产品魏供应鼙，班健慧弱澜最夫，辊会按失避夺，蔗鞠定袋 应计划的主要目的t e z u k am a s a r u 和h i mm a s a h i r o ( 2 0 0 3 ) 给出了一种不确定、独 立需求摄下的供应计划问题的遗传算法求解该方法已经通过数据检测，计算结果比较 接近实际 健在实嚣生产孛，袈种产品嚣嚣戡是稿关鼹，大多满足一定静耀笑关系。困扰， 本文在t e z u k am a s a r u 和h i j im a s a h i r o 所提出方法的基础上，将冀改进为适用子 产品需求满足一定相关关系的情况，并对遗传算法的操作以及各个算子进行进一步的 研究，蔓新算法在利用蒙特卡洛方法模拟估计供成计划所获得的总利润和风险的过 程中，本文假设除了每静产晶自身艨扶一定鲍概率势蠢之舞，产品之瓣还存在一定浆 相关关系，并提出了种产生穗关随辘数静算法；本文黻芷态分布为硼，产生出了满 足一定相关关系并且服从正态分布的随机数，最后把斌个随机数作为对将来需求的预 测；本文还通过抽样的符法对产生隧帆数的方法进行了统计分析，并得到很好的结果 在产生韧始种群的过程巾，本文； 入7m i c h a l e w i c z 边嚣娃理技术并作修改来处理约束 条俘，嶷毙较蘸争令体之霹鳇霞娄孵，零文擐据龚应诗翔弱援往诧懿蠢糖，提凄了一种 向盏适应值的比较策睹并且提出对早熟机理的预防墩后通过数值实验来验证改进的 算法，寓验表明通过这种方法模拟所得划的结果更具有广泛性，更接近实际 关键调：供应诗翔；道传算法；蒙祷卡潺模掇：摇关赣辊数 a b s t r a c t s u p p l yp l a n n i n go p t i m i z a t i o ni so n eo ft h em o s ti m p o r t a n ti s s u e sf o rm a n u f a c t u r e s a n dd i s t r i b u t o r s s u p p l yi sp l a n n e dt om e e tt h ef u t u r ed e m a n d u n d e rt h eu n c e r t a i n t yi n - v o l v e di nd e m a n df o r e c a s t i n g p r o f i ti sm a x i m i z e da n dr i s ki sm i n i m i z e d t e z u k am a s a r u a n dh i j im a s a h i r og a v ea i lg e n e t i ca l g o r i t h mt os o l v et h es u p p l y p l a n n i n gp r o b l e m su n d e r t h eu n c e r t a i n t y , i n d e p e n d e n c ei n v o l v e di nd e m a n df o r e c a s t i n g h o w e v e r ，t h ed e m a n do fp r o d u c t si sc o r r e l a t e di nf a c t s oi nt h i sp a p e rt h ea u t h o r r e p a i r e di ti no r d e rt os a r i s f yt h ec o r r e l a t i o ns i t u a t i o n w h e nu s m gm o n t ec a r l os i m u l a - t i o nt oe v a l u a t et h ep r o f i ta n dr i s k ，t h ea u t h o ra s s u m e de v e r yp r o d u c tf o l l o w i n gn o r m a l d i s t r i b u t i o n ，a n dt h e r ew e r ec o r r e l a t i o nr a n d o mn u m b e rb e t w e e nt h e mw h i c hf o l l o w i n g n o r m a ld i s t r i b u t i o n f i n a l l yt h er a n d o mn u m b e rw e r eu s e da st h ef u t u r ed e m a n d t h i s p a p e ra l s od i dt h es t a t i s t i c a la n a l y s i sf o rt h ea l g o r i t h mb ys a m p l i n g ，a n do b t a i nag o o d r e s u l t i nt h ep r o c e s so fg e n e r a t i n gi n i t i a lp o p u l a t i o n ，t h ea u t h o ri n t r o d u c e dm i c h a l e w i e z b o u n d a r yh a n d l i n gt e c h n i q u e ，a n dr e p a i r e di ti no r d e rt or e s o l v et h ec o n s t r a i n tc o n d i - t i o no fs u p p l yp l a n n i n gp r o b l e m w h e nc o m p a r i n gt w oi n d i v i d u a l s ，t h ea u t h o rp r o p o s e d ap o l i c yw h i c hc o m p a r e dv e c t o rf i t n e s s a n dt h i sp a p e rp r o p o s e dh o wt op r e v e n te a r l y - m a t u r i n g m e c h a n i s m t h e a p p r o a c h w a s t e s t e do i l t h e s u p p l y p l a n n i n g d a t a o f a ne l e c t r i c a p p l i a n c e sm a n u f a c t u r e r ，a n dh a sa c h i e v e dar e m a r k a b l er e s u l t k e yw o r d s ：s u p p l yp l a n n i n g ；g e n e t i ca l g o r i t h m ；m o n t ec a r l os i m u l a t i o n ； c o r r e l a t i o nr a n d o mn u m b e r 1 引言 供应计划问题的遗传算法求解 供应计划问题一直是最受生产商和销售商重视的问题对于生产多种产品而言，生 产商需要制定生产计划，决定每一种产品的生产数量而这一决定的做出依赖于对未来 需求的预测预测的需求量具有不确定性，如果需求量大于生产量，机会损失就会发 生；如果需求量小于生产量容易导致产品积压，库存成本增多，总利润降低并且对 于产品的生产而言，诸如生产资料、生产设备、运输工具等资源是有限的所以在资源 有限和需求不确定的前提下，如何实际分配各种产品的供应量，以使总利润最大，并 且机会损失最小，是制定供应计划的主要目的 1 1 供应计划问题的传统解决方法 传统上，供应计划是通过库存管理f 1 】的方法制定的用这种方法制定的计划可以使 库存成本最小，通过库存成本的极小化达到总利润的极大化然而这种方法忽略了需求 量大于生产量时机会损失就会发生，没有考虑到利润和风险之间的关系比如，在资源 约束下，如果某种产品的利润很高，我们可以通过减少机会损失来获得尽可能多的利 润；相反，利润很低的产品，即使机会损失很小，也不能期望很多的利润但是，利润 很高的产品的需求是很不确定的也就是说存在根大的风险；而利润低的产品的需求 大多是有规律的，也就是风险是低的因此，为得到一个风险较低的并且总量较大的利 润，高风险产品和低风险产品之间的最好结合是很重要的 显然这是一个多目标规划问题，虽然我们希望同时实现利润最大和风险最小的双 重目的，但是利润最大和风险最小是交替出现的，因此供应计划问题在高风险高利润 到低风险低利润间会产生很多的p a r e t o 解这些解对决策者的决策是十分有用的：通 过得到不同经济状况下的生产预案，根据自己的实际情况来选择相应的预案如公司的 当前经济状况好，会选择高风险高收入的预案；若公司的当前经济状况不好，会选择 低风险低利润的预案，然而传统的方法大多只能产生一个解，很多决策者都不喜欢这种 只产生一个解的黑盒子系统 1 2 基于遗传算法的解决方法 供应计划问题在许多情况下建立起来的数学模型难以精确求解，即使经过一些简 化之后可以进行求解，也会因为简化太多而使得求解结果与实际相差太远因此，目前 在现实生产中也主要根据一些经验进行调度遗传算法已成为解决复杂调度问题的有效 - 具，在单件生产车间调度，流水线生产车问调度、生产规划、任务分配等方面遗传 算法都得到了有效的应用 供应计划问题的遗传算法求解 与传统方法不同，遗传算法有不受搜索空间限制的约束不必要求诸如连续性、 单峰性等假设，以及其固有的并行性的特点对于特定的问题，它能一次产生许多潜在 解，这将更有利于决策者做出选择另外，供应计划问题是多目标的，它优化的目标是 利润最大化同时风险最小化；而遗传算法是解决多目标问题非常有效的方法，只要将 多个优化目标同时引入到遗传算法的选择策略中，经过若干代的进化后即可达到优化 的目的 t e z u k am a s a r u 和h i j im a s a h i r o ( 2 0 0 3 ) 给出了一种求解不确定需求量下的供 应计划问题的遗传算法【2 1 其计算流程如下： l n i t p o p u l a t i o n 厂e ”l u t i o n - - m o n t ec a r l os i m “耐 0 n l e j 6 d m ( c r o s s o v e r , m u t a t i o n ) e k 其中蒙特卡洛法( 1 v i o n t ec a r l o ) 模拟( m c s ) 是根据历史需求在各种产品需求相 互独立的情况下对不确定需求的随机模拟，计算利润和损失的概率分布；其目的是 用m c s 作为遗传算法( g a ) 的适应值函数故求解供应计划问题的方法分为以下步 骤： g a ：通过随机的边界初始种群优化多目标函数，使得利润极大，风险极小 m c s ：通过对不确定需求的模拟，计算利润和损失的概率及统计参数，为g a 提 供适应值函数 最终为决策者提供p a r e t o 解 该方法已经通过数据检测，计算结果比较接近实际 但在实际生产中，各种产品的需求是相关的，大多满足一定的相关关系因此。本 文在t e z u k am a s a r u 和h i j im a s a h i r o 所提出方法的基础上，给出一种产品需求满 足一定相关关系的遗传算法，并对遗传算法的操作以及各个算子进行进一步的研究， 更新算法本文用蒙特卡洛方法模拟了满足给定相关系数且满足正态分布的不确定需 求，通过这种方法模拟所得到的结果更具有广泛性，更接近实际 1 3 论文的结构与研究的内容 本文在第二部分对遗传算法作简要介绍。其中包括遗传算法的基本概念、摹本 流程、基本机理；第三部分，介绍了t e z u k am a s a r u 和h i j im a s a h i r o 提出的供应 计划问题，并由此得出数学模型，给出用相关随机数预测将来需求的方法；在第四 部分中我们给出了该方法的具体实现算法，并对此算法进行了抽样检验：第五部分 我们详细介绍了用遗传算法解决供应计划问题的实现过程，在这一部分我们引入了 m i c h a l e w i c z 边界处理技术并作修改来处理约束条件，并给出早熟机理的预防方浊：我 们在第六部分做了三个数值实验来验证我们的算法：在第七部分做了总结 2 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a1 由美国科学家j o h n h o l l a n d 提出，它足一种 概率搜索算法利用某种编码技术作用于称之为染色体的二进制串，其基本思想是模拟 由这些串组成的群体的进化过程遗传算法通过有组织的，然而是随机的信息交换来重 新组合那些适应值好的串来生成一个新的串的群体；偶尔也要在串结构中尝试用新的 位段来替代原来的部分( 类似于自然界的变异) 遗传算法对所求解问题的本身一无所 知，它需要的仅是对算法产生的每个染色体进行评价，并基于适应值来选择染色体， 使适应值好的染色体比适应值差的染色体有更多的繁殖机会通过个体的不断进化逐 步接近最优解。从而达到优化的目的 2 1 遗传算法的基本概念 由于遗传算法是由自然遗传学抽象而来的新的计算方法，所以遗传算法中常要用 到自然进化中的一些术语为了能更好地描述遗传算法在供应计划问题中的应用，现对 遗传算法中的基本概念及在供应计划问题中的具体意义简要介绍如下1 3 】： 染色体( c h r o m o s o m e ) ：生物细胞中含有的一种微小的丝状化合物，它是遗传物 质的主要载体，由多个遗传因子一基因组成在供应计划问题中，染色体对应于各个产 品在各个阶段的供应量， 个体( i n d i v i d u a l ) ：指染色体带有特征的实体供应计划中，个体对应于各个阶段 的供应量的集台。即具体的一个供应计划方案 种群( p o p u l a t i o n ) ：染色体带有特征的个体的集合称为种群，该集合内个体数称 为种群的大小种群对应于供应计划的集合，每个种群中都包含一定数量的供应计划方 案 适应值( f i t n e s s ) ：在研究自然界中生物的遗传和进化现象时生物学家使用适应 度这个术语来度量某个物种对生存环境的适应程度对生存环境适应程度高的物种获得 更多的繁殖机会，而对生存环境适应程度低的物种，其繁殖机会就相对较小，甚至逐 渐灭绝供应计划中适应值即是用蒙特卡洛模拟方法估计出来的利润值和风险值所组成 的向量供应计划问题就是要使得所制定的供应计划能达到利润最大化同时风险最小 化 选择( s e l e c t i o n ) ：指决定以一定的概率从种群中选择若干个个体的操作一般而 言，选择的过程是一种基于适应度的优胜劣汰过程，选择的过程也是淘汰的过程，每 一次选择都把利润相对较高同时风险相对较小的供应计划保留下来，这样经过若干次 选择后，高利润低风险的个体即被保留下来，而高风险低利润的个体被淘汰，这正是 遗传算法得以实现优化的关键所在 交叉( c r o s s o v e r ) ：有性生殖生物在繁殖下一代时两个同源染色体之间通过交义而 重组，即在两个染色体的菜一相同位置切断，且前扁两串分别交叉组合形成两个新的 个体，既保留了双亲的部分基因，又引入了新的辇酬，这样有助下种群中保持个体的 多样性交义操作是按照定的概率来进行的 3 供应计划问题的遗传算法拳解 变异fm u t a t i o n ) ：在缀熬进行复裁拜章爵辘班缀书韵概率产生某些复靠l 麓糖，蔽蔼 使得染色体敏嫩某些变异，产生新的染色体，这些新的染色体表现出新的性状变异操 作也是按照一定的概率进行的虽然变异的概率非常小，但这种变异在优化过程中是非 常有意义的，它可以防止求解过程中过早收敛产生局部最优解丽菲全局最优解+ 2 2 遗传算法的操作流程 遗传算i 虫猩整个进化过程中的遗传操作魁随机的，但它所璺现的特性并不是完全 疆辊搜索，它缝有效的利用掰史信息来推测下一代期望性能有所提高的寻优点集，其基 本操作流程翔下| 4 l ： 1 初始种群的生成( i n i t i a l i z a t i o n ) 随机产擞一个初始种群，种群中n 个染戗体都满足约束条件，设世代为t 一0 n 为秘群的太小( p o p s i z e ) 。 2 译稳( e v a l u a t i o n ) 根据各个个体的遗传基阌，依照预先确定的方法对各个个体鼍( i = 1 ，2 ，n ) 进 行评估，并且求出各自的适艨度，( 五) ，检焱是否满足终止条件如满足终也条件则结 束，如果不满足终止条件则依照下列步骤进行 3 。选择fs e l e c t i o n ) 扶当代t 的n 个个体最，岛中选择下一代t + 1 的n 个个俸，选簿盼允许重 复 4 遗传操作的应用fc r o s s o v e ra n dm u t a t i o n ) 设t o ，对于新的一代，瘟用遗抟操作，g p 进行交叉和变髯 头主壶移骠2 舞步骤4 耪成逮传算法豹一个周期，称之麓一找g e n e r a t i o n ) ，透过 反复世代交替，在种群内的个体中，适应度高的新的个体就会缓慢的增加起米 2 。3 遗传算法的基本枫理 h o l l a n d 提出的模式定壤f s l ，蘑数学方法辩遗传算法的王律原理进行了分桥，照琵 揭示了许多背景材料下面对遗传算法的这一越本定理模式定理作一个简要的介绍 首先引入“模式”( s c h e m a ) 这一概念我们将种群中的个体即基因串中的相似样 援称为“模斌”，模式表示嫠因串中某些特征稠阍麴结构，鞭此模式也可以锵释为相 蘑豹 毒形。窀瓣述瓣是一令事豹子集，在二避潮编玛静辜孛，模式是基予三个字符集( 0 ，1 ，+ ) 的字符串，符号+ 代袭任意字符，即。或1 例如模式t 1 ，描述了卟四个 元素的子集f010 ，011 ，110 ，111 ) 所有的模式并不是以同等机会产生的肖螳模式比其他模式更确定，如与模式0 4 $ ；4 ；胡毙，模式01l 。+ l 在赣钕寿蠹巍更孵璃的表示毒些模式瓣跨瘴装魄其它 的长，如与模式isl + * 4 栩比，1 + $ + l 要跨越整个宰长更大盼部分为了定量的 描述模式，我们介耋_ r 模式中包宙的两个重鬻的参数：模式阶( s c h c m ao r d c r ) 和定义距( d c f i n i t i n gl e n g t h ) 供应计划问题的遗传算法求解 定义1 模式h 中确定位置的个数称为模式h 的模式阶，记作o ( h ) 例如，0 ( 0 11 + 1 + 1 = 4 模式阶用来反映不同模式确定。的差异模式阶数越高，摸式确定性就越高，所匹 配的样本个数就越少 定义2 模式h 中第一个确定位置和最后一个确定位置之间的距离称为模式的定义 距，记作叫h ) 例如，酬0 1 1 + 1 十+ ) = 4 在遗传算法操作中，即使阶数相同的模式，也会有不同的性质，模式的定义距反 映了这种性质的差异 有了以上的定义即可给出如下的模式定理： 模式定理( s c h e m at h e o r e m ) 在遗传算子选择、交叉、变异的作用下，具有低 阶、短定义距以及平均适应值高于种群平均适应值的模式在子代中成指数增长 模式定理是遗传算法的基本理论，保证了较优的模式( 遗传算法的较优解) 的数 目成指数增长，为解释遗传算法的机理提供了一种数学工具 供应计划螭题的遗传算法求辫 3 供应计划掰题 3 1供应计划问蹶的基本描述 壤设家工厂生产l 季争产最，欲潮定一个壹霉令跨段缀或豹莺定期阕的袋应嚣翔 文i ，鲰，啦分剐表涿产品l 在第 个酚段的需求蠹、供应量和库存爨，则产品i 在第 t 个阶段的销售量s 机会损失量f “，在第t + 1 个阶段的库存量q ( ) ，由下列等 式获樽； 张一m i n ( d ，绺缬i ) k = 也t 一3 “ 埘件l k = m + 吼一0 “ 若产品i 在第t 个阶段的单位销售价格为地 ，单位嫩产价格为饥，单位库存价格为 蚴，那么工厂的总利润计算如下： 机会损失可以表水为 g = s “啦一p “v t l 一鼽毗。) = 1f = 1 墙是随机变量，而生产量a 。是敬策变量既然札是随机的，那么与之相关的总 利润g 和机会损失l 自然也是随机的，g 、l 的分布依靠于决策变量执i 因此，生产 计划惩鞋魏解捷蘸在予鲡鹰确定生产璧捷褥g 、l 分配最往 然褥工厂的生产资源是有限静蒋工厂有j 种资灏，n ，表示生产单位产品i 消耗 资源j 的数量，啦，表示在第t 个阶段资源j 的可利用赣，各种产品消耗资源的总和不 能超过资源的可利用豢此外，产量是非负的因此，生产计划问题的约束条件如下表 示： 勺期a t 孙o ( = 1 ，五，。z 一1 ，2 ，- ，砖 巍然约束条髓w 行集是凸擒。 6 妊 ；， | | 供应计划问题的遗传算法求解 3 2 供应计划问题的数学模型 由上可知，供应计划问题的数学模型为 s t m a x g = ( u f - m v t 。一毗。) i = l m i n l = f 池 利润最大 风险( 机会损失) 最小 ：1r j p t i “t = 1 ，2 ，t , j = 1 ，2 ，j 资源约束 8 “= m i n ( d ，p * i + 吼i ) t = 1 ，2 ，一，t ，i = 1 ，2 ，i l “= d “一8 “t = 1 ，2 ，l l = 1 ，2 ， q ( t + 1 ) i = 鼽t + g “一s “= 1 ，2 ， lp f 。0t = l ，2 ，l i = 1 ，2 ， 其中数学符号的意义如下： 正i = 1 ，2 ， ，非负约束 总利润 机会损失( 风险) 第t 种产品在第t 个阶段的需求量，是不定的 第i 种产品在第t 个阶段的供应量。是不定的 第i 种产品在第t 个阶段开始时的存储量 第i 种产品在第t 个阶段的销售量 第i 种产品在第t 个阶段的机会损失量 第i 种产品在第t 个阶段的销售单位价格 第i 种产品在第t 个阶段的供应单位价格 第i 种产品在第t 个阶段的存储单位价格 第j 种资源在第t 个阶段的可利用量 第i 种单位产品所消耗的第j 种资源量 3 3 用相关随机数预涌将来需求 随机需求预测是供应计划问题中的一个重点和难点在t e z u k am a s a r u 和h i m m a s a h i r o 的方法中，预测将来的需求是通过一个商业软件来实现的这个软件能够分 析历史的需求数据并能自动生成符合历史数据的预测信息，包括将来的需求及其期望 和方差这种预测方法是在假设各产品的将来需求是相互独立的情况下进行的但在 实际上，在更多的情况下产品的需求量之间是存在一定的相关关系的，因此本文在 t e z u k am a s a r u 和h i j im a s a h i r o 提出方法的基础上，给出了一种假设各产品的需求 量之问存在给定相关关系的预测方法 我们假设各产品历史需求量的期望和方差，需求量的相关系数均可由历史数据确 定在这个前提f ，我们的算法产生出了满足这蜱期望和方斧且相瓦之问还符台这些相 关系数的随机数，然后把这些随机数作为相应产品的将来需求量本文以正态分布为例 7 g l 1芋陬k毗叼 供应计划问题的遗传算法求解 进行预测，也就是说各产品的需求量服从正态分布并且各产品的需求量之间还满足给 定的相关系数运用了相关随机数预测方法的供应计划优化方法将具有更大的灵活性 供应计划问题的遗传算法求解 4生成正态分布相关随机数的计算方法 4 1 理论依据 ，( 钆钝，z 。) = ( 2 ”) ；i m 一“p 一；( z 一司7 m _ 1 ( f 一司) 肚a l l a 1 2 - - - a l n a 隹a n00 铲愁i - 00ii 上矗( y ) ，e 2 ( x ) 日l ( y ) 十e 2 ( y ) 时，个体x 优于个体y ，否则劐s t e p 3 ， s t e p 3 麓枫选出一个侉兔袋谯， 利用上述魄较方法，在逸择的过程中我们可鞋选出青剥予达劐供应诗划翻满最大 风险最小目标的个体 根据上磷的比较原则，我们采用锦标赛选择【，q 的方法在锦标褰选择中，随机地 扶静群中挑选定数强ft o u r ) 的个体，然惹将选择残来鲍个体中最好的个体选作父代 采产生下+ 代这中过程重复避行静可完成个馋的选择 锦标赛选择方法的参数t o u r 称为竞赛规模。竞赛规模的大小直接决定嚣选择雕力 的大小选择腻山指的是选姆机制给适应值较小的个体造成的“生存雕力”胝力过大 会小容易搜索劁令局最优解，腻力过小则算法收敛速度太慑 1 9 供应计划问题的遗传算法求解 使用这种选择操作仍隐含着个问题，即在进化过程中，可能某一代的最优解被 交叉和变异破坏，从而可能导致退化，所以产生了最佳个体保存方法但是容易导致 收敛于局部晟优解，为了避免这种情况发生，我们采用排挤式的最佳个体保存方法： 设时刻t ( 第t 代) 时，群体矿( t ) 为最佳个体，又设a ( t + 1 ) 为经过选择、交叉、 变异等操作后产生的新一代( 下一代) 群体若a ( t + 1 ) 代中最劣个体劣于a ( t ) 代中 最佳个体t l * ( t ) ，则a + ( t ) 排挤出a ( t + 1 ) 代中最劣个体，成为a ( t + 1 ) 代中第n 个个体 ( 其中n 为种群的大小) 这种选择操作避免了某一代的最优解被破坏而造成的退化 5 4 2交叉操作 算术交叉算术交叉是两个个体的线性组台假设父代为x = ( 。l ，。”一，z ，) ，y = ( 1 ，啦，蚰) 交叉方法为 x y ， ：= 。a 。x 一+ 。，( x 1 - + a 。) y y 其中n 【0 ，1 】是一个均匀随机数，由于约束条件的可行集是凸的，显然算术交叉 对于约束条件的可行集是封闭的 5 4 3 变异操作 均匀变异设父代x = ( 。1 ，z 2 ，z ，z 小选择分量。女，u k 】 1 七兰 f ，执行变异后所得予代为x = 如，x , 2 ，z ：，z f ) ，其中 ，f 。+ ( t ，一z k ) 。= 1 善。一( ，。一。) 若z t 警 若z 女 专且 t 为当前演化代，( t ，可) = 剪【l r ( x - 孛) 一】，( ，掣) 【o ，训，其中r ( o ，1 ) 是一个随机 数，a 【2 ，5 ，u k ，k 为边界初始化时所得的值域限制的上下限此方法把变异算子与 演化代数联系起来，在演化初期变异范围相对大，到后期变异范围越来越小 边界变异边界变异与均匀变异相似只是将z ：取成k 或，并且取如和u 的概 率相等 5 5 早熟收敛的产生和克服 早熟现象是指遗传算法在进化操作过程中，由于遗传操作的随机性而引起的群体 内个体多样性的降低，使得遗传算法的解停留在某局部最优点上，无法达到全局最 优解早熟收敛是遗传算法的个严重问题，在算法的每个环节都可能导入产生早熟 收敛的因素，其本质是无法保证种群个体的多样性如在本文中已经提到的初始种群的 选取，以及排挤选择方法，都是为了克服早熟现象 此外，克服早熟现象，我们采取了摧1 ：控制参数旧白适应调整策略【l l j ： 供应计划问题的遗传算法求解 交叉操作是遗传算法产生新个体的主要方法，p c 一般选取较大值，但若取值过 大，易于破坏群体中的优良模式：若取值过小，产生新个体的速度又太慢变异操作是 遗传算法产生新个体必不可少的辅助方法，若p 。取值较大，有可能破坏掉很多较好的 模式，使得算法的性能近似于随机搜索：若p 。取值太小，则变异操作产生新个体的能 力和抑制早熟的能力较差由上可知，p c 与p 。越大，算法产生新个体的能力越强，个 体之间的适应度波动就越大，产生新的超平面的能力越强；p c 与p 。越小，算法使个 体趋于收敛的能力越强，个体的平均适应度比较平稳，有可能产生早熟的现象采用自 适应度的思想，在算法的运行中对p c 与p 。进行调整。让它们随着个体适应值的增加 而变小，随着个体适应值的减小而增加其计算公式如下 交叉率： ： 凰i f - # f ，苎f ：e w i恐 ， 若f f 口。9 变异率： ： k 3 。l 老i ，若腔如， i凰 ，若f b 。g 其中。为当前群体中适应度的最大值 r 。为当前群体中适应度的平均值， ，为参与交叉操作的两个个体中适应度较大的一个，f 为参与变异的个体的适应 度， l 舞：i 表示f m f 一- r f 。 。模的大小，且k l = 0 9 ，k 2 = 0 9 5 ，k 3 = i ；4 = 0 0 1 上式表明： ( 1 ) = i f m 。一r 。，i 越小，种群达到局部最优的可能性越大，早熟的可能性也越 大，让p c 和严相应变大，以增加种群产生新个体的能力；相反，越太