模糊遗传算法在机器调动问题运用

0I:10.13374/j.issn1001-053x.2002.01.054 第24卷第1期 北京科技大学学报 Vol.24 No.1 2002年2月 Journal of University of Science and Technology Beijing Fcb.2002 模糊遗传算法在机器调动问题运用 郑大伟玄光男 日本足利工业大学经营工学科智能系统工学研究室 摘要单机器调度问题是研究工件在多道工序进行加工的加工活动排序的组合最优化问 题.由于调度问题中绝大多数属于NP一难类问题，不存在有效的最优求解算法，针对用智能优 化算法一遗传算法求解单机器调度问题中交叉率和变异率难以确定的问题，设计了一种模糊 算法以便自动确定交叉率和变异率，通过数值实验，嵌入模糊规则的遗传算法比简单的遗传算 法要好，说明在实际生产中，此算法具有强大的发展前途 关键词机器调度问题；遗传算法：模糊逻辑 分类号TP2734TP206.1 单机器调度问题是研究工件在多道工序进 罚.根据Rinnooy Kan的定义)，本问题被定义为 行加工排序的组合最优化问题.本文把各个工 /I/IET,或被简称为ET.用TIMETABLER方法 作的提前和滞后惩罚的总和作为目标.该问题 来对染色体进行编码以便减少全惩罚. 是NP-难类问题，不存在有效的最优求解算法. 遗传算法(GAs)是一种具有“鲁棒性”(Robust-- 2子代和父代之间的相关性 ness)的方法，它可以适应不同的问题环境，在大 对于有20个单机调度的问题，随机生成200 多数情况下都能得到比较有效的满意解四.很 个调度方案，然后进行染色体交叉操作.一点顺 多研究者都在这方面作了工作.本文提出了一 序法如图1所示.交叉实施后，子代和父代的相 种改进的遗传算法来求解调度问题.设计了一 任选一个位置 按染色体2的顺序重新排工件 种模糊算法用以自动确定交叉率和变异率从而 可以省略用以确定交叉率和遗传率初始计算. 53741826 53741826 1 机器调度问题 图1一点顺序法 单机器调度问题中有个工件，每个工作的 Fig.1 One-point order method 就绪时间为0，即在开始加工时，所有工件都具 关系数如图2所示.横轴表示父代的平均目标 备加工条件.每个工件都具有下面的属性：() 值，纵轴表示子代的平均目标值.用同样的方 为加工时间：d()为完工时间：()为提前完工时 法，计算变异操作的相关性.变异方法如图3所 的单位惩罚；()为滞后完工时的单位惩罚. 示.变异实施后，子代和父代的相关系数如图4 假设n个工件分别以其自然数编号1,2，n 所示.横轴表示父代的平均目标值，纵轴表示子 标识，则工件标识的任意一个排列可以表示一 代的平均目标值.由图2和图4父代和子代之 个调度方案s=S2,小，S是第i个工件.目标 间具有正相关性，因此优良的父代能够产生优 是求解全惩罚，目标函数如下定义： 良的子代 minZ(s)=E[e(s)max(d(s)-c(s),0;+ 为确定交叉率，定义规则：(1)为了防止遗 (s)max(c(s)-d(s,),0)] (1) 传搜索停留在局部最优解，当各个染色体的目 式中，c(s)是工件的完成时刻.等式右边第1项 标值之间的差很小时应该加大交叉率.(2)如果 是提前完成的惩罚，第2项是滞后完工时的惩 任选的染色体的目标值和当前世代中的最大目 标值相差很小时应该减小交叉率，可以省略逻 收稿日期2001-02-12 郑大伟男，32岁，博士

DOI: 10. 13374 /j . issn1001 -053x. 2002. 01. 054

·86 北京科技大学学报 2002年第1期 相关系数y=0.80358 G也是小的那么P也是小的；3)如果F是大的并 :OIx/ 且F也是大的那么P也是大的；4)如果F是小的 或者F是小的那么P也是小的.参数V,G,F和 F界于[0,1]之间.图5定义了每个参数的隶属 函数.图6为交叉率的隶属函数，其中p:mm和pm 被分别定义为0.1和0.9 例如，运用模糊规则2如果V的值等于0.6， 0 1 2 3 G的值等于0.4.从图5，可以得到μr等于0.4，c 父代22x10 等于0.6.按照Mamdani方法，可以得出μ=0.4. 图2交叉方法，P,0为目标值 可以计算出交叉率p.=0.58.用方程 Fig.2 Crossover operation n.=4i=1,23,4 (2) 随机选择两个位置 可以得到基于四条模糊规则的交叉率 12348675 为突然变异操作定义几条规则用来确定变 交换相应的工件 异率：为了防止遗传搜索停留在局部最优解，当 12648375 各个染色体的目标值之间的差很小时应该加大 图3变异方法 变异率.当各个染色体的目标值之间相差很大 Fig.3 Reciprocal Method 时应减小变异率；运用和交叉操作同样的参数V 4相关系数y=0.80732 和G,转化成模糊规则：1)如果/是小的并且G是 大的那么Pm也是大的；2)如果V是小的并且G也 是小的那么P也是小的.用方程(3)，可以得到变 到c 异率. B.=凸 j=1,2,3 (2) 山 式中，4是规则j的函数值，P是第j个变异率 0 0 3 父代要x10 图4突变方法 Fig.4 Mutation operation 辑个数P,以及与之相对应的目标值F.把目标 值变为最大化问题，用几个参数来确定交叉率 (1)最优目标值与平均目标值间的距离： V=(F-F)/(F-Fin), 其中：Fr=max{Fx)}, Fmin=min,(F(x)),i=1,2,,pop size. 图5各参数隶属度函数的定义 (2)最优目标值和染色体x的目标值间的距 Fig.5 Definition of membership degree for input variables 离： G=(Fa-Fx)》/Fn-Fn), 其中：染色体x是染色体x与x中目标值较大的 那个染色体 大 (3)最优目标值和任意染色体的目标值间的 =0.4 距离：F,(Fmx-Fx)/(Fna-Fna)和 0 F=(F-Fx)/Fa-Fm)） 0P.mm-01p.=0.58 Pe.m=0.9 同时，把交叉规则转化成模糊规则：1)如果 图6交叉率的隶属度函数 G是大的那么P.也是大的；2)如果V是小的并且 Fig.6 Membership degree of p

Vol.24 No.1 郑大伟等：模糊遗传算法在机器调动问题运用 87 3 数值实验 看，带有模糊逻辑的遗传算法所得到的结果接 近用最优组合参数所得到的结果，这说明运用 用10个单机调度问题来进行数值实验，每 模糊规则，我们可以省略在遗传算法计算前确 个单机调度问题中工件数是20.为了对遗传算 定遗传参数（交叉率和变异率）的步骤 法和模糊遗传算法进行比较，对交叉率和变异 4结论 率的100种组合所得到的结果进行了比较.通 过比较，发现当p.=0.8和pm=0.4时遗传算法可 应用模糊遗传算法来求解单机调度问题， 得到较好的结果 首先确认了遗传算子的可控制性，然后设计了 p.=0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0, 模糊遗传算法.最后，通过模拟数值实验，我们 pm=0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.80.9,1.0. 验证了模糊遗传算法的有效性， 遗传算法的参数：种群规模为100，最大世 参考文献 代数为500. 1 Michalewicz Z.Genetic Algorithms Add Data Structures 表1是10个问题的计算结果.从结果上来 Evolution Programs.NY:Springer-Verlag,1994 表12种算法标准偏楚和平均目标值的比较 2 Gen M,Cheng R.Genetic Algorithms and Engineering Table 1 Standard deviation and average with GA Design.John Wiley Sons.1997 遗传算法 模糊遗传算法 3 Rinnooy Kan,A H G.Machine Scheduling Problems: No. 标准偏差平均甘标值标准偏差平均目标值 Classification,Complexity,and Computations.Martinus 1 5693.0 71688.9 8353.9 7380.9 Nijhoff,The Hague,1976 4 Davis J S,Kanet JJ.Single-Machine Scheduling with Ear- 2 4832.6 87592.2 4681.2 90126.2 ly and Tardy Completion Costs.Naval Research Logis- 3 8352.0 79698.4 11448.8 87403.6 tics,1993,40:85 4 15148.0 126440.3 17634.0 127841.1 5 Kruse R,Gebhardt J,Klawonn F.Foundations of Fuzzy 7207.8 44510.6 3879.6 45717.4 Systems.John Wiley Sons,1994 6 8811.8 77756.5 5401.5 81944.9 6 Baker K,Scudder G.Sequencing with Earliness and Tar- 7 8920.6 148355.814711.9 145585.9 diness Penalties Review.Operations Research,1990,38: 8 3787.9 91652.7 11259.7 93402.0 22 9 3799.1 35908.3 5642.3 35227.8 7 Zeng X,Besoa Rabenasolo.A Fuzzy Logic Based Design 10 13420.4 155073.026022.3 139218.3 for Adaptive Genetic Algorithms.[In:]Proceedings of EU- 平均8718.8 91867.710903.5 92014.8 F1T.1997.660 注：p.=0.8,P。=04每个问题计算10次. 8 Ronald Y,Lotfi Z.An Introduction to Fuzzy Logic Applic- ations in Intelligent Systems.Kluwer Academic Publish- ers,1992 Hybrid Genetic Algorithms with Fuzzy Logic Controller ZHENG Dawei,GEN Mitsuo Department of Industrial and Systems EngineeringAshikaga Institute of Technology,Ashikaga,326 Japan ABSTRACT New implementation of genetic algorithms(GAs)is developed for machine scheduling prob- lem.Machine scheduling problem is abundant among modern manufacturing system.The performance mea- sure of early and tardy completion of jobs is very natural as one's aim,which is usually to minimize simu- Itaneously both earliness and tardiness of all jobs.As the problem is NP-hard and no effective algorithms exist, we proposed a hybrid genetic algorithms approach is deal with in order to adjust the crossover probability and mutation probability by fuzzy logic controller whereas the hybrid genetic algorithm does not require prelimi- nary experiments to determine probabilities for genetic operators.The experimental results show the effecti- veness of the proposed GAs method. KEY WORDS machine scheduling problem;hybrid Genetic algorithms;fuzzy logic

叭, . . 2 4 N o . l 郑大伟等 : 模糊 遗传算 法在机 器调动 问题运 川 . 8 , . 3 数值实验 用 10 个单机调度 问题 来进行数值实验 , 每 个单机调 度 问题 中工件 数是 20 . 为 了对遗传算 法 和模糊遗传算 法进行 比较 , 对交叉率和 变 异 率 的 10 种组合所得 到的结 果进 行了 比较 . 通 过 比较 , 发现 当p 。 二 0 . 8 和 p 。 二 0 .4 时遗传算法可 得 到较好 的结果 . P 。 = 0 . 1 , 0 . 2 , 0 . 3 , 0 . 4 , 0 . 5 , 0 . 6 , 0 . 7 , 0 . 8 , 0 . 9 , 1 . 0 , P m = 0 . 1 , 0 . 2 , 0 . 3 , 0 . 4 , 0 . 5 , 0 . 6 , 0 . 7 , 0 . 8 , 0 . 9 , 1 . 0 . 遗传算法 的参数 : 种群规模为 10 , 最大世 代数 为 5 0 . 表 l 是 10 个问题 的计算结果 . 从结果上 来 农 1 2 种葬法标准偏 理和 平均 目标 值的 比较 aT b l e 1 5妞 . d a r d d e v i a t i o n a n d a v e , 昨 w l t七 G A 遗传算法 模糊遗传算法 平均目标值 标准偏差 平均 目标值 l 0 平均 标准偏差 5 6 9 3 . 0 4 8 3 2 . 6 8 3 5 2 . 0 1 5 14 8 . 0 7 20 7 . 8 8 8 1 1 . 8 8 9 2 0 . 6 3 78 7 . 9 3 7 9 9 . 1 1 3 4 20 . 4 8 7 1 8 . 8 7 1 6 8 8 . 9 8 7 5 9 2 . 2 7 9 6 9 8 . 4 1 26 4 4 0 . 3 4 4 5 1 0 . 6 7 7 7 5 6 . 5 1 4 8 3 5 5 . 8 9 1 6 5 2 . 7 3 5 9 0 8 . 3 1 5 5 0 7 3 . 0 9 1 8 6 7 . 7 8 3 5 3 . 9 4 6 8 1 . 2 1 1 4 4 8 . 8 17 6 3 4 . 0 3 8 7 9 . 6 5 4 0 1 . 5 14 7 1 1 . 9 ! 1 2 59 . 7 5 6 4 2 . 3 2 6 0 2 2 . 3 10 9 0 3 . 5 7 3 8 0 . 9 9 0 1 26 . 2 8 7 4 0 3 . 6 12 7 8 4 1 . 1 4 5 7 17 . 4 8 1 9 4 4 . 9 14 5 5 8 5 . 9 9 3 4 02 . 0 35 2 2 7 . 8 1 3 9 2 1 8 . 3 9 2 0 14 . 8 看 , 带有模糊逻辑 的遗传算法所得 到的结果接 近用最优 组合 参数所得到的结果 , 这说 明运 用 模糊规则 , 我们 可 以 省略在遗传算法计算前确 定 遗传参数 (交叉 率 和变 异 率 )的 步骤 . 4 结论 应用模 糊遗传 算法来 求解单 机调 度 问题 , 首先确认 了遗传算子 的可控制性 , 然后设计 了 模糊遗传算法 . 最后 , 通过模 拟数 值实验 , 我们 验证 了模糊遗传算法 的有效性 . 参 考 文 献 1 M i e h a l e w i e z Z . G e n e t i e A lg o r i thm s A dd D咖 S trU e ut r e s : Ev o lut ion Por gr am s . N 丫 S irP n 罗r 一 Ve r lag , 19 9 4 2 G e n M , C h e n g R . G e n e ti c A lg o ir t h n 1 s an d E n g i n e e r i n g D e s ign . J o hn 铂l e y & S o n s , 19 9 7 3 Ri n o y K a n , A H G . M a e hi n e s e h e d u li n g Por bl e m s : C las s i ifc iat o n , C o m P l e x i ty , a n d C o m P u t a ti o n s . M art inu s N ij h o f, hT e H a s u e , 19 7 6 4 D a v i s J S , K an e t J J . s i n g l e 一 M ac h i n e s c h e d u li n g w i th Ear - ly a n d 下ar dy C o m P l e t i o n C o s t s . N a v a l Re s e ar e h L o g i s - t i c s , 19 9 3 . 4 0 : 8 5 5 K ur s e 民 G e bh adr t J , K l a w o n E F o u n dat i o n s o f F u Z y S y s t e m s . J o hn 铂l e y & S o n s , 1 9 9 4 6 B欧e r K , s c u d d e r G · S e q u e n e i n g w i th Ear li n e s s an d 衍 - d i n e s s P e n a l t i e s R e v i e .w O P e r a t i o n s R e s e acr h , 1 9 9 0 , 3 8 : 22 7 Z e n g X , B e s o a Ra b e n as o l o . A F u Z y L o g i e B as e d D e s ig n fo r A d a Pt i v e G e n e ti e A lgo r iht m s . 【I n :』P r o e e e di n g s o f E U - F I.T 19 9 7 . 6 6 0 8 OR n a ld Y, L o tif Z . An I n tr o d u e ti o n t o F u Z y L o g i c A P Pli e - a ti o n s i n Int e lli g e n t S y s t e m s . K l u w e r A e a d e m i e Pu b li s h · .NO 21J 3467958 注 : 几 二 .0 8 ,几 = .0 4 ; 每个 问题计 算 10 次 . e r s , 1 9 9 2 H y b r id G e n e t i e A lg o r i ht m s w i ht F uz yZ L o g i c C o n tr o ll e r Z HE N G D a w e i, GE N 九五st u o D e P a rt l n e n t o f I n d u s tr i a l an d S y s t。 盯 5 En g ien e ir n gA s h议昭 a I n s titU ct o f几 e hn o l o gy , A s h ik吧 a , 3 2 6 J a p an A B S T R A C T N e w im P l e m e n ta i o n o f g e n e t i e a l g o r it hln s (G A s ) 1 5 d e v e l o P e d fo r m a e h i n e s e h e d u li n g P r o b - l e m . M a e h in e s c h e d u lin g P r o b l e m 1 5 ab un d a ll t am o n g m o d e m m an u fa c 加irL n g s y st e m . hT e P e r fo rm an c e m e a - s ur e o f e ar ly an d it 汀d y c o m Pl e t i o n o f j o b s 1 5 v e ry n a t ur a l as on e , 5 a im , w h i e h 1 5 u s u a ll y t o m i n im iez s im u - l ant e o u s l y b o ht e ar li n e s s an d atr d i n e s s o f a ll j o b s . A s t h e Pr o b l e m i s N P 一 h ar d a n d n o e fe e t i v e a lg o r it h n 1 s e x i s t , w e Pr o Po s e d a hy b ir d g e n e t i e a lgo ir ht m s 叩P r o ac h 1 5 d e a l w iht in o 川e r ot a dj u s t ht e c or s s o v e r Pr o b a b iliyt an d m u at i o n P r ob ab iliyt b y fu z Z y l o g i e e o n tr o ll e r w h e r e a s ht e h y b r id g e n e t i e a l g o r it hm d o e s n o t er q u i r e Pr e lim i - n a yr e x Pe r im e nst t o d e te mr i n e Pr o b ab ilit i e s fo r g e n e t i e o Pe r a t o r s . hT e e x Pe r im e ant l r e s u lt s s h o w ht e e fe e t i - v e n e s s o f ht e Pr o Po s e d G A s m e th o d . K E Y WO R D S m a e h i n e s e h e d u lign P r o b l e m : hy b r id G e n e t i e a lg ior t加nr s : 加石卿 l o g i e