基于相似性遗传算法及其在JSP中的应用

维普资讯

第２３卷，第２期　２００６年４月　深圳大学学报理工版　ＪＯＵＲＮＡＬ　ＯＦ　ＳＨＥＮＺＨＥＮ　ＮＩＶＥＲＳＩＴＹ　ＳＣＩＥＮＣＥ　ＡＮＤ　ＥＮＧＩＮＥＥＲＩＮＧ　、’ｏ１．２３．Ｎｏ．２　Ａｐｒ．２００６　文章编号：１０００—２６１８（２００６）０２—０１０７—０５　基于相似性遗传算法及其在ＪＳＰ中的应用　蔡良伟，胡世曦　（深圳大学信息＿［程学院，深圳５１８０６０）　摘　要：提出一种基于个体相似性的改进算法，当种群的多样性较好时，采用标准的交叉策略；当种　群的多样性较差时，根据个体的相似性选择个体配对，避免相同的个体配对交叉，减少高度相似个体进行　配对交叉的概率，从而提高交叉操作的效率、用该改进算法对基准作业车间调度问题（ＪＳＰ）进行计算，仿　真结果表明：该算法优于标准遗传算法，　关键词：遗传算法；多样性；相似性；作业车间调度　中图分类号：ＴＰ　３０１．６　文献标识码：Ａ　弓ｊ　言　遗传算法（ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ＧＡ）　１　２是模拟自　然界生物进化机理的一种随机搜索并行优化算法，　在复杂函数优化、生产调度、图像识别、机器学习　等众多领域都获得了成功的应用　，实践表明，标　１　标准遗传算法　标准遗传算法从一组随机产生的个体开始，反　复经过选择、交叉和变异３种遗传操作，不断进　化．选择操作根据个体的适应度来确定个体的生　存，体现“优胜劣汰，适者生存”的自然规律，适　准遗传算法常常由于近亲繁殖，容易出现个体早熟　现象，使算法不能跳出局部极值而收敛到全局最　优，这是标准遗传算法的最大不足．出现这一现象　的根本原因是，种群经过一定代数的进化后，由于　优胜劣汰，只有少数的优良个体生存下来，这些个　应度高的个体具有较高的生存慨率，相反，适应度　低的个体则不断遭到淘汰，选择操作使种群的平均　适应度不断提高，但它不会产生出新的个体；交叉　操作是对父代个体配对进行基因交换重组，产生出　大量新的个体，从而使更优个体的出现成为可能；　体往往具有相同或高度近似的基因，很难产生出新　的优良个体．为克服标准遗传算法的这一不足，改　变异操作通过改变个体内部基因，保持种群中个体　的多样性．　善算法的收敛性能，许多学者做了大量的研究和探　索，提出了许多改进措施　～．　本文分析标准遗传算法中交叉操作容易产生无　效操作及效率低下的原因，提出一种基于种群多样　性和个体相似性的改进遗传算法，当种群的多样性　较好时，采用标准的交叉策略；当种群的多样性较　标准遗传算法结构如下：　①初始化：确定个体种群大小，产生初始种　群，选定交叉概率和变异概率；　②计算个体适应度，根据适应度用轮转盘法　选择父代个体种群；　③根据交叉概率Ｐ，选择个体，配对进行交叉　操作；　差时，根据个体的相似性选择个体配对，避免相同　的个体配对交叉，减少高度相似个体进行配对交叉　的慨率，从而提高交叉操作的效率，对基准作业车　④根据变异概率Ｐ　选择个体基因，进行变异　操作；　间调度问题进行了仿真计算，结果表明了该方法的　性能优于标准遗传算法．　⑤重复②～④，直至满足收敛条件．　交叉操作是遗传算法中最重要的操作，是决定　收稿日期：２００５—１２—２３；修回日期：２００６—０１—１５　作者简介：蔡良伟（１９６４．），男（汉族）．广东省阳江市人，深圳大学副教授．Ｅ－ｍａｉｌ：ｃａｉｌｗ＠ＳＺｔ１．ｅｄｕ．Ｃｆｌ　

维普资讯

１Ｏ８　深圳大学学报理工版　第２３卷　算法收敛性能的关键．在标准遗传算法中，进行交　叉操作时，首先按照预先设定的交叉概率选出要进　到不同的交叉结果．可以肯定的是，进行单点交叉　操作时，如果一对父代个体完全相同或仅有一个基　因不同，无论交叉点选在何处，交叉结果都相同，　行交叉的个体，形成交叉配对池，然后对配对池中　的个体进行完全随机的等概率一一配对，最后对每　一不可能生成新的个体；而当一对父代个体完全不相　同（即每一个基因位都不同）时，不管交叉点选在　对父代个体随机确定交叉点，交换基因片段，生　成出新的子代个体．标准交叉操作具体描述如下：　ｆ０ｒ（种群中的每个个体）　对个体产生一个随机数；　ｉｆ（随机数小于交叉概率）　该个体进入交叉配对池；　（　ｆ０ｒ（配对池中的每个个体）　｛　随机配对；　随机选择交叉点；　交换基因片段；　｝　交叉操作有单点交叉和两点交叉等多种形式，　在标准遗传算法中，采用的交叉策略是单点交叉，　如图１．由图可见，两个父代个体有两个基因位不　同，分别是第４位和第７位，当交叉点选取如图１　（ａ）时，产生的两个后代个体与两个父代个体相　同，故本次操作是一次无效的交叉操作；当交叉点　选取如图１（ｂ）时，产生出两个与父代个体不同　的后代个体，因而本次交叉操作有效．由此可见，　同样一对父代个体，由于交叉点的选取不同，会得　Ⅱ工　ⅢⅡ工ⅡⅢ　交叉点—　后代个体　口ＩＩ—Ｉ　Ｉ—Ｉ—ｌ　ｌ　ｌ　ｌ口］　工　ｆａ）无效交叉操作　口］］　二］＝　口］］　二］＝皿　▲　交叉点—　后代个体　口］二］［工土］［＝口口］二］［工工　ｆｈ１有效交叉操作　图１交点交叉操作　Ｆｉｇ．１　Ｏｎｅ　ｐｏｉｎｔ　ｃｒｏｓｓｏｖｅｒ　何处，交叉操作肯定能产生出新的个体；对其他情　况，交叉操作能否有效则与交叉点的选择有关．一　般而言，两个父代个体中相同的基因位愈多，交叉　操作产生出新个体的概率就愈小，操作无效的概率　就愈大．当种群进化到一定阶段时，种群中会出现　相当多相同或高度相近的个体，导致很多交叉操作　无效，大大影响算法的收敛速度，甚至不能收敛到　全局最优解．　２　基于个体相似性的改进遗传算法　２．１种群多样性　种群的多样性是衡量遗传算法进化状态的重要　标志，当算法寻找到一个存在极值的区域时（不管　是局部的还是全局的），种群中的个体会不断向该　区域集中，出现很多相同或相似的个体，使种群的　多样性变差，从而影响算法遗传操作的效率和探索　其他极值区域的能力．目前，普遍的做法是用种群　的最大适应度厂…、平均适应度　和最小适应度厂　…来衡量种群的多样性，但实际上，只用这３个参　数有时并不能反映出种群多样性的真实情况．例　如，两个种群中个体的适应度分别为｛０，１，２，３，　４，５，６，７，８，９，１０｝和｛０，０，０，０，０，５，ｌ０，　ｌ０，ｌ０，ｌ０，１０｝，这两个种群的　、厂　和厂　ｉ　分　别相同，但显然两个种群具有非常不同的多样性，　前者的多样性比后者的多样性要强得多．本算法定　义种群多样性如下：　ｄ＝∑ｇ　其中，　为每个个体的基因数目；ｑ　为种群中所有个　体第位最多相同基因数目与个体数目的比率．ｄ愈　小，表示种群的多样性愈好．　２．２个体相似性　个体的相似性反映两个个体之间的近似程度，　设两个个体　，和　分别为　

维普资讯

第２期　蔡良伟，等：基于相似性的遗传算法及其在ＪＳｐ问题中的应用　１　ｇ，ｌ，ｇｉ２，…，ｇ　ｌ，　，　ｘｉ　多样性，在进化的初始阶段，由于种群的多样性较　ｇ　，ｇ　，…，ｇｉＭ　・　好，因此可以不进行变异操作，这样可以减少算法　的计算量；在进化的后期阶段，种群的多样性较　定义个体　和个体　的相似性如下：　ｌ，　差，需要进行变异操作，同时采用基于个体相似性　ｓ（　，　）＝∑ｇ　ｏ　＝】　，”　－／　的交叉操作，提高交叉操作的效率。改进算法的结　构如下：　其中，　。　：｛　ｎ　；　（３）　①初始化．确定个体种群大小，产生初始种　Ｌ０，ｉｆ　ｇｉｋ≠ｇ　．　实际上，ｓ（　，　，）表示　和　，之间相同基因的数目，　ｓ（　，　，）愈小，表明　和ｘｊ的相似性愈小；反之，　ｓ（　，ｘ）愈大；则表明　和　，的相似性愈大，当　，　和　，完全相同时，ｓ（　，　，）等于　．　２．３基于个体相似性的交叉配对　设个体　的交叉配对池为　，　，…，　｝，要在　其中选出一个个体和　进行交叉操作．在标准遗传　算法中，配对池中的所有个体具有相同的被选概　率，均为１／Ｌ．当种群的多样性较小，个体和其配　对池中其他个体的总体差异不很明显时，交叉操作　的效率会受到很大的影响．本算法采取非等概率配　对策略，给配对池中和　相似性小的个体赋予较大　的被选概率，可有效提高交叉操作的效率．配对池　中个体　被选择与个体　进行配对交叉的概率定义　如下：　ｐ（　Ｉ　）：　（４）　［　—ｓ（　，　）］　其中，ｉ＝ｌ，２，…，￡由式（４）可知，当交叉配对池　，　，…，　｝中某个体和　完全相同时，其被选概　率为零，从而排除了一对相同的个体进行交叉操　作，避免无效的交叉操作．　在交叉配对池　，Ｙ　，…，Ｙ　｝中给个体　寻找　配对个体进行交叉操作的算法如下：　①计算Ｓ（　，　），ｉ＝ｌ，２，…，　；　②计算Ｐ（Ｙ，Ｊ　），ｉ＝ｌ，２，…，　；　③计算７ｒ＝∑ｐ（　），ｉ＝ｌ，２，…，　；　④产生一个在［０，１］内均匀分布的随机数Ｐ，　令．　＝ｒａｉｎ｛ｉ　Ｉ　７ｒ　＞Ｐ，ｉ＝ｌ，２，…，￡　；　个体　和个体）　，配对，交换基因片段．　２．４改进算法的结构　在遗传算法中，变异操作的作用是增加种群的　群，选定交叉概率和变异概率，设定多样性阈值；　②计算个体适应度．根据适应度用轮转盘法　选择父代个体种群；　③根据交叉概率Ｐ，选择交叉个体，形成交叉　配对池；　④计算种群的多样性；　⑤当种群的多样性大于设定阈值时，进行标　准交叉操作，返回②；否则进入⑥；　⑥计算个体的相似性，进行基于个体相似性　的交叉操作；　⑦根据变异概率Ｐ　选择个体基因，进行变异　操作；　⑧判断是否满足收敛条件，若满足则停止计　算；否则返回②．　３　改进算法在作业车间调度问题中　的应用　在最小化完工时问的作业车问调度问题（ｊｏｂ　ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ，ＪＳＰ）　中，给定一组工件　和一组机器，在任一时刻每台机器最多可加工一个　工件，每个工件都包含一系列的操作，这些操作必　须按照规定的顺序进行，每个操作需要在一台指定　的机器上不间断地加工一预先给定的时间，目标是　要找出一个加工调度方案，使完成所有工件加工所　需时问最少．　设．，是所有工件的集合，Ｍ是所有机器的集　合，Ｄ是所有操作的集合，　＜　＜…＜　表示　工件　的加工顺序约束，ｍ是集合Ｍ中元素的个数，　＜　＋　表示操作　＋　只能在操作　完成后才能　开始，　（（ｒ｛）表示操作　所用的机器，Ｐ（　）表示　操作　所需的时间，ｔ（（ｒ｛）表示操作　的起始时　间，最小化完工时间的ＪＳＰ问题可描述如下：　ｍｉｎ　Ｃ　＝ｒａｉｎ｛ｍａｘ［ｔ（　）＋Ｐ（　）］　ｔＥ０　

维普资讯

１１０　深圳大学学报理工版　第２３卷　ｓｕｂｊｅｃｔ　ｔｏ：　ｔ（　）≥ｔ（（ｒ｛）＋Ｐ（（ｒ｛），Ｖ（ｒ｛＜　，Ｊ∈Ｊ　ｔ（　）≥ｔ（（ｒ｛）＋Ｐ（（ｒ｛）Ｖ　ｔ（（ｒＩ）≥ｔ（　）＋　Ｐ（　），Ｖ　Ｍ（　）＝Ｍ（　）　ｔ（　）≥０，Ｖ　∈０　应用本文提出的改进算法（ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌ・　ｇｏｒｉｔｈｍ，ＩＧＡ）和标准遗传算法（ｓｔａｎｄａｒｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ＳＧＡ）对基准ＪＳＰ　ＭＹ６×６　进行求解，　两算法选择相同的参数：种群规模为３０，交叉概率　Ｐ　为０．８５，变异概率Ｐ　为０．０１，遗传进化终止代　数为３００，两算法各自随机运行２０次．图２为一最　优方案的甘特图，仿真统计结果如表１所示．　口臣口固田　［二臣［田［Ⅱ　臣Ⅱ［三二］［口９　田　匝臣曰］［　［二Ⅱ］　田　田目　田田口田　图２最优方案的甘特图　Ｆｉｇ．２　Ｇａｎｔｔ　ｄｉａｇｒａｍ　ｏｆ　ｏｎｅ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　表Ｉ　ＭＴ６×６仿真结果　Ｔａｂｌｅ　１　Ｓｉｅｒｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｏｆ　ＭＴ６　ｘ６　由表１可见，改进算法和标准遗传算法都能求　出问题的最优解，但改进算法在最小收敛代数、平　均收敛代数和收敛概率等方面均优于标准遗传算　法．　结　语　遗传算法能否收敛到全局最优以及收敛速度的　快慢在很大程度上取决于遗传操作的有效性，本文　提出一个基于个体相似性的改进遗传算法，有效提　高遗传操作效率，改善算法性能．求解ＪＳＰ的仿真　结果表明，该算法优于标准遗传算法．　参考文献：　［１］Ｇｏｌｄｂｅｒｇ　Ｄ　Ｅ．搜索，优化和机器学习中的遗传算法　［Ｍ］．美国：Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ出版公司，１９８９（英文　版）．　［２］Ｚｂｉｇｎｉｅｗ　Ｍｉｃｈａｌｅｗｉｃｚ．遗传算法＋数据结构＝进化程序　［Ｍ］．柏林：Ｓｐｒｉｎｇｅｒ，１９９６（英文版）．　［３］尹文君，刘民，吴澄．带工艺约束并行机调度问题　的一种新的遗传算法［Ｊ］．电子学报，２００１，２９（１１）：　１４８２—１４８５．　［４］Ｓｒｉｎｉｖａｓ　Ｍ，Ｐａｔｎａｉｋ　Ｌ　Ｍ．遗传算法中的自适应交叉和变　异概率［Ｊ］．ＩＥＥＥ系统、人和控制论学报，１９９４，２４　（４）：６５６—６６７（英文版）．　［５］江瑞，罗予频，胡东成，等．一种基于多Ａｇｅｎｔ协同　的准并行遗传算法［Ｊ］．电子学报，２００２，３０（１０）：　１４９０．１４９５．　［６］曾宏坤，沈德耀．基于多智能体的新型遗传算法及其在　复杂系统中的应用研究［Ｊ］．信息与控制，２００３，３２　（３）：２７７－２８０．　［７］郑金华，叶正华，蒙祖强，等．基于空间交配的遗传算　法［Ｊ］．模式识别与人工智能，２００３，１６（４）：４８２—４８５．　『８］Ｍｕｔｈ　Ｊ　Ｆ，Ｔｈｏｍｐｓｏｎ　Ｇ　Ｌ．工业调度［Ｍ］．新泽西：　Ｐｒｅｎｔｉｃｅ．Ｈａｌ１．１９６３（英文版）．　

维普资讯

第２期　蔡良伟，等：基于相似性的遗传算法及其在ＪＳＰ问题中的应用　Ａｂｓｔｒａｃｔ：１０００・２６１８（２００６）０２．０１１１－ＥＡ　Ａ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｓｉｍｉｌａｒｉｔｙ　ａｎｄ　ｉｄ　ｉｔ　ｐｐｌｉｃａｔｉｔｓ　ａｏｏＲｃａｔｉ￣ｏｎ　ｏｎ　Ｊ—ＳＰ—　ＣＡＩ　Ｌｉａｎｇ－ｗｅｉ　ａｎｄ　ＨＵ　Ｓｈｉ・ｘｉ　Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｈｅｎｚｈｅｎ　Ｕｎｉｖｅｒｓｉｔｙ　Ｓｈｅｎｚｈｅｎ　５　ｌ　８０６０　Ｐ．Ｒ．Ｃｈｉｎａ　Ａｂｓｔｒａｃｔ：Ｓｔａｎｄａｒｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｏｆｔｅｎ　ｌｏｓｔ　ｉｎ　ｌｏｃａｌ　ｏｐｔｉｍｕｍ　ｂｅｃａｕｓｅ　ｇｅｎｅｔｉｃ　ｏｐｅｒａｔｉｏｎ　ｉｓ　ｏｆ　ｌｏｗ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｕｎａｂｌｅ　ｔｏ　ｍａｋｅ　ｏｕｔ　ｎｅｗ　ｃｈｒｏｍｏｓｏｍｅｓ　ｗｈｅｎ　ｔｈｅ　ｄｉｖｅｒｓｉｔｙ　ｏｆ　ｐｏｐｕｌａｔｉｏｎ　ｉｓ　ｐｏｏｒ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａｎ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｓｉｍｉｌａｒｉｔｙ　ｏｆ　ｃｈｒｏｍｏｓｏｍｅｓ．Ｓｔａｎｄａｒｄ　ｃｒｏｓｓｏｖｅｒ　ｏｐｅｒａｔｉｏｎ　ｉｓ　ｕｓｅｄ　ｗｈｅｎ　ｔｈｅ　ｄｉｖｅｒｓｉｔｙ　ｏｆ　ｐｏｐｕｌａｔｉｏｎ　ｉｓ　ｇｏｏｄ；ｏｔｈｅｒｗｉｓｅ，ｃｈｒｏｍｏｓｏｍｅｓ　ａｒｅ　ｍａｔｃｈｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅｉｒ　ｓｉｍｉｌａｒｉｔｙ，ｃｒｏｓｓｏｖｅｒ　ｂｅｔｗｅｅｎ　ｔｗｏ　ｖｅｒｙ　ｓｉｍｉ—　ｌａｒ　ｃｈｒｏｍｏｓｏｍｅｓ　ａｒｅ　ａｖｏｉｄｅｄ，ａｎｄ　ｔｈｅ　ｐｒｏｂａｂｉｌｉｔｙ　ｏｆ　ｃｒｏｓｓｏｖｅｒ　ｂｅｔｗｅｅｎ　ｔｗｏ　ｖｅｒｙ　ｓｉｍｉｌａｒ　ｃｈｒｏｍｏｓｏｍｅｓ　ｉｓ　ｄｅｃｒｅａｓｅｄ．　Ｔｈｕｓ，ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｃｒｏｓｓｏｖｅｒ　ｏｐｅｒａｔｉｏｎ　ｉｓ　ｉｍｐｒｏｖｅｄ．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｕｓｅｄ　ｔｏ　ｓｏｌｖｅ　ａ　ｂｅｎｃｈｍａｒｋ　ｏｆ　ｊｏｂ　ｓｈｏｐ　ｓｃｈｅｄ—　ｕｌｉｎｇ　ｐｒｏｂｌｅｍｓ，ｔｈｅ　ｓｉｍｕｌａｔｉｏｎａｌ　ｒｅｓｕｌｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｉｓ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅｆｆｅｃｔｉｖｅ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｄｉｖｅｒｓｉｔｙ；ｓｉｍｉｌａｒｉｔｙ；ｊｏｂ　ｓｈｏｐ　ｓｃｈｅｄｕｌｉｎｇ　Ｒｅｆｅｒｅｎｃｅｓ：　［１　Ｇｏｌｄｂｅｒｇ　Ｄ　Ｅ．Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ　ｉｎ　Ｓｅａｒｃｈ，Ｏｐｔｉｍｉｚａｔｉｏｎ，　ａｎｄ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ［Ｍ］．ＵＳＡ：Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ　Ｐｕｂ—　ｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙ，１　９８９．　ｒｉｔｈｍｓ『Ｊ　１．Ａｃｔａ　Ｅｌｅｃｔｒｏｎｉｃａ　Ｓｉｎｉｃａ，２００２，３０（１０）：　１４９０—１４９５（ｉｎ　Ｃｈｉｎｅｓｅ）．　［６］ＺＥＮＧ　Ｈｏｎｇ—ｋｕｎ，ＳＨＥＮ　Ｄｅ—ｙａｏ．Ｓｔｕｄｙ　ｏｆ　ａ　ｎｅｗ　ｍｕｌｔｉａｇｅｎｔ—　ｂａｓｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｉｎ　ｃｏｍｐｌｅｘ　ｓｙｓ—　［２：Ｚｂｉｇｎｉｅｗ　Ｍｉｃｈａｌｅｗｉｃｚ．Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ＋Ｄａｔａ　Ｓｔｍｃ—　ｔｕｒｅｓ＝Ｅｖｏｌｕｔｉｏｎ　Ｐｒｏｇｒａｍｓ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，１９９６．　ｔｅｎ『Ｊ］．Ｉｒｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｃｏｎｔｒｏｌ，２００３，３２（３）：２７７—２８０　（ｉｎ　Ｃｈｉｎｅｓｅ）．　［３　ｊ　ＹＩＮ　Ｗｅｎ—ｊｕｎ，ＬＩＵ　Ｍｉｎ，ｗｕ　Ｃｈｅｎｇ．Ａ　ｎｅｗ　ｇｅｎｅｔｉｃ　ａｌｇｏ—　ｒｉｔｈｍ　ｆｏｒ　ｐａｒａｌｌｅｌ　ｍａｃｈｉｎｅ　ｓｃｈｅｄｕｌｉｎｇ　ｗｉｔｈ　ｐｒｏｃｅｓｓ　ｃｏｎｓｔｒａｉｎｔ　［７］ＺＨＥＮＧ　Ｊｉｎ—ｈｕａ，ＹＥ　Ｚｈｅｎｇ—ｈｕａ，ＭＥＮＧ　Ｚｕ—ｑｉａｎｇ，ｅｔ　ａ１．　Ｔｈｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｓｐｅｃｉａｌ　ｃｒｏｓｓｏｖｅｒ［Ｊ］．Ｐａｔ—　ｔｅｍ　Ｒｅｃｏｇｎｉｔｉｏｎ　ａｎｄ　Ａｒｔｉｉｆｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００３，１　６（４）：　４８２—４８５（ｉｎ　Ｃｈｉｎｅｓｅ）．　『Ｊ’．Ａｃｔａ　Ｅｌｅｃｔｒｏｎｉｃａ　Ｓｉｎｉｃａ，２００１，２９（１１）：１４８２—１４８５　（ｉｎ　Ｃｈｉｎｅｓｅ）．　［４］Ｓｒｉｎｉｖａｓ　Ｍ，Ｐａｔｎａｉｋ　Ｌ　Ｍ．Ａｄａｐｔｉｖｅ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｏｆ　ｃｒｏｓｓｏｖｅｒ　ａｎｄ　ｍｕｔａｔｉｏｎ　ｉｎ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｓｙｓ—　ｔｅｍｓ．Ｍａｎ　ａｎｄ　Ｃｙｂｅｒｎｅｔｉｃｓ．１９９４，２４（４）：６５６—６６７．　［８］Ｍｕｔｈ　Ｊ　Ｆ，Ｔｈｏｍｐｓｏｎ　Ｇ　Ｌ．Ｉｎｄｕｓｔｉｒａｌ　ｓｃｈｅｄｕｌｉｎｇ［Ｍ］．Ｎｅｗ　Ｊｅｒｓｅｙ：Ｐｒｅｎｔｉｃｅ—Ｈａｌｌ，１　９６３．　［５］ＪＩＡＮＧ　Ｒｕｉ，ＬＵＯ　Ｙｕ—ｐｉｎ，ＨＵ　Ｄｏｎｇ—ｃｈｅｎｇ，ｅｔ　ａ１．Ａ　Ｍｕｌｔｉ—　ａｇｅｎｔ　ｃｏｏｐｅｒａｔｉｎｇ　ａｐｐｒｏａｃｈ　ｔｏ　ｑｕａｓｉ・－ｐａｒａｌｌｅｌ　ｇｅｎｅｔｉｃ　ａｌｇｏ‘‘　【中文责编：英子；英文责编：雨辰】