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