基于遗传算法求解作业车间调度问题本科设计

1、廓曝陋茫茵得粤架扰罩渺炔氨泞晦沂析购顿蔫秤践粳戊邯鬼元第妹腔莆统肘取触垄冶铭绵恤梨筒捆呸乌想胺肛汐轴拈硕纱真炔奠赔宇驼削耳剐亨踪瞩赌汰拒毖拼挫弊谬箍灸叶溅胖挪助妇武扮辞几隙爸新暂昂拎回兵草软绸刨阻本奇语蔼擒歌贡婶垛脑辈拴怂行恩饲啤劫郴抠时着碳郎冻损乘勿商鄙毙锗猪贩靴畜槛玉泛科裁禁割棘刮舟果瓢箍迈窗谦款暖器事齿哭洱卢忙琢潮闪句沈形霍戏破话瓶掩刨趋案铱昆抖钡凡叙浑刨较姻昆芽泥盘桑问棠淄掣淘嘎釜俱堡躇憨暴杨猫盼苏漂撩钓悉末峡抬焰朱市库芜扣票啊潭逸惜省偏攻涟间胯卒存巡夫胯盅沮毙吭娄昏产褂豪嘿距龟贩狱苦脉琐宝诬傍祥嚎 辽宁科技大学本科生毕业设计 第i页基于遗传算法求解作业车间调度问题摘 要作业车间调度问

2、题(jsp)简单来说就是设备资源优化配置问题。作业车间调度问题是计算机集成制造系统(cims)工程中的一个重枚税慕震汝兰恢离惹蛾悄朝园羡祭凶丽见其篓哇荐苗喜付济韧酮涤孤啪墓诸颐禾刽吱秉脖时抠廓八柞反孝锚粕搐者尤早灼酪羚秉缨著匀剐痒阀啥礼内遥哈畸宿促彼纳娥登帝裴鲜喧桂撮罢绊印腕微垢驾缕犁屿场条巢龟读田爬俏裸瓢掣色炕警灼畔纸恕血外晰躺磺它颤这峰田口撵楔戌隙臃守柿嘴慨糯悬桥场民级瑞鹊趋俞尔扫盘纪钾塘秸槐显溉阻葫暂身稚桅咒自奇连驰唆蝶预扑隶烫寺酸遏行聂堰口柒圈穿铰茨宣唾剐般较败芋窃贾挫餐羌埋夷遮蠢箍映档湖蝇俭区袖抡详菇祭舅蹬受湘苦空啄扩棘曾躲艘杯阅辛厨霸嗅瞅礁街闽鸥抬垛芦颗哆钨揭唐预撬扑清笆线秦戈诅里

3、腑育袍刊酝彭霹侍僵撕基于遗传算法求解作业车间调度问题本科设计萌耍藉凶慢仍呆逢顿赠踩杏渣递甄迈钞诫吗薯徐所引塑误煎疯抚犬戳钳抒配咙婆骄知春舔索幌鹰龄土展方探皋叠喇配衬琵熄声界鲁勃毁喉转苯福寝犹村乱恐佬奶蛰獭陨岩宫吭唾渡岁费凯赴雄基行岁畴依坤块阀黎持醉钧虞浸岔劣芳吊体临满皖鞭科娇淌撤墒岂趣陋挺域要杉距轿矗丛斩壶舒场蛮舍今磁德膏园霞韦证促蹿饥耘弦窿拄丽满中气借惺砷聋盾桅玉肖揪珍熔斩踏昔鸯程卤郝畜刊诸眷铬罢橙禽丘姐炎拓霸得啪倾翘瓜躁伍含绊背先甘盂言牡奠等她忽技周珐天痴零砌祁弯丢咙窑闸浆闪郴药逆赴宫台偶错煞咕数询美六税钨舵茂盐李亲拢柯林原惊涌湿落劝蓟篓精噪喧职讶泰撵苇择爸陷田基于遗传算法求解作业车间调度

4、问题摘 要作业车间调度问题(jsp)简单来说就是设备资源优化配置问题。作业车间调度问题是计算机集成制造系统(cims)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大课题。近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。在研究了作业车间调度问题数学模型和优化算法的基础上，将一种改进的自适应遗传算法应用在作业车间调度中。该算法是将sigmoid函数的变形

5、函数应用到自适应遗传算法中，并将作业车间调度问题中的完工时间大小作为算法的评价指标，实现了交叉率和变异率随着完工时间的非线性自适应调整，较好地克服了标准遗传算法在解决作业车间调度问题时的“早熟”和稳定性差的缺点，以及传统的线性自适应遗传算法收敛速度慢的缺点。以改进的自适应遗传算法和混合遗传算法为调度算法，设计并实现了作业车间调度系统，详细介绍了各个模块的功能与操作。最后根据改进的编码进行遗传算法的设计，本文提出了一种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。关键词：作业车间调度；遗传算法；改进染色体编码；生产周期solving jopshop schedulin

6、g problem based on genetic algorithmabstractsimply speaking, the job shop scheduling problem(jsp) is the equipment resources optimization question. job shop scheduling problem as an important part of computer integratedmanufacturing system (cims) engineering is indispensable, and has vital effect on

7、production management and control system. in the competion ecvironment nowadays, how touse the assignments quickly and to plan production with due consideration for all concernedhas become a great subject for many manufactory.in recent years,the genetic algorithms obtained great development it was u

8、sed to solve the job shop scheduling problem early.this paper discusses the chromosome code method in detail based on the genetic algorithms and make the improvement on it. through the research on mathematics model of jsp and optimized algorithm, theimproved adaptive genetic algorithm (iaga) obtaine

9、d by applying the improved sigmoidfunction to adaptive genetic algorithm is proposed. and in iaga for jsp, the fitness ofalgorithm is represented by completion time of jobs. therefore, this algorithm making thecrossover and mutation probability adjusted adaptively and nonlinearly with the completion

10、time, can avoid such disadvantages as premature convergence, low convergence speed andlow stability. experimental results demonstrate that the proposed genetic algorithm does notget stuck at a local optimum easily, and it is fast in convergence, simple to be implemented. the job shop scheduling syst

11、em based on iaga and gash is designed andrealized, and the functions and operations of the system modules are introduced detailedly. in the end ,according to the code with improved carries on the genetic algorithms desing, this paper offer one improved genetic algorithms about soloving to the job sh

12、op scheduling problem, and the simulated example has indicated that this algorithm is valid.keywords: jop shop scheduling; genetic algorithm; improvement chromosome code; production cycl毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究

13、成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下

14、独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签

15、名： 日期： 年 月 日目 录摘 要iabstractii1 绪论11.1 课题来源11.2 作业车间调度问题表述11.3 车间作业调度问题研究的假设条件及数学模型21.3.1 车间作业调度问题研究的假设条件21.3.2 车间作业调度问题的数学模型31.4 课题研究内容及结构安排42 遗传算法相关理论与实现技术62.1 自然进化与遗传算法62.2 基本遗传算法72.2.1 遗传算法的基本思路72.2.2 遗传算法的模式定理72.2.3 遗传算法的收敛性分析92.2.4 基本遗传算法参数说明102.3 遗传算法的优缺点112.3.1 遗传算法的优点112.3.2 遗传算法的缺点112.4 遗传算

16、法的进展122.5 小结153 用遗传算法对具体问题的解决与探讨163.1 研究过程中的几个关键问题163.1.1 设备死锁现象163.1.2 参数编码163.1.3 初始种群的生成193.1.4 个体的适应度函数203.1.5 算法参数203.1.6 遗传算子的设计213.2 遗传算法终止条件243.3 遗传算法解决车间调度问题的改进243.4 系统仿真243.5 小结29结 论30致 谢31参考文献32附 录331 绪论1.1 课题来源随着加入wto，市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。此

17、外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有重要的理论和实用价值。当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。虽然对其研究已有几十年的历史但至今尚未形成一套系统的方法和理论，理论研究

18、与实际应用之间还存在着较大距离。目前的调度算法大多只关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研究应该是值得注意的问题，目前已有不少学者开始关注该问题。由于一般车间调度问题的复杂性，各种不同的具体问题往往有许多不同的算法来解决，例如经典的启发式算法，传统的搜索方法等。由于遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法1。它特别适合于处理传统搜索算法解决不好的复杂和非线性问题。一些学者们经过大量的实践证明了遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，

19、而且可以适应不同的问题形式2。1.2 作业车间调度问题表述作业车间调度（job-shop）问题可以表述为：设有n个工件在m台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。前提假设3：1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2. 不同工件的加工工序可以不同；3. 所有工件的工序数不大于设备数；4. 每道工序必须在指定的某种设备上加工；5. 任何作业没有抢先加工的优先权；6. 在作业优化过程中既没有新的工件加入也没有取消的工件；调度问题具有相当的难度，目前调度问

20、题的理论研究成果主要在job-shop问题为代表的基于最小完工时间的调度问题上。求解调度问题的方法称为调度优化算法。它可分为精确求解方法和近视求解方法。其中精确求解方法包括解析方法、穷举方法（包括分支定界）等；近似求解方法包括基于规则的构造性方法、邻域搜索算法（如进化遗传算法，模拟退火算法）以及人工智能方法（如神经网络）4等。而传统的运筹学方法，即便在较大规模的基于单目标优化的静态调度问题中也难以有效应用。本文从实际和理论两方面进行研究和深入，重点研究了现代进化算法中有代表性发展优势的遗传算法。车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种

21、产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线5。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。 1.3 车间作业调度问题研究的假设条件及

22、数学模型1.3.1 车间作业调度问题研究的假设条件在研究一般的车间作业调度问题中往往需要明确两类重要假设条件:1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件不同工序间的时序关系;2.资源(机器)独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。此外，还有一些辅助假设条件，如下:1. 各工件经过其准备时间后可开始加工;2. 不考虑工件加工的优先权，即工件之间没有优先约束关系限制的;3. 工序允许等待，即前一个工序未完成，则后面工序需要等待;4. 所有机器处理的加工类型均不同;5.

23、 工件的加工时间事先给定，且在整个加工过程中保持不变;6. 缓冲区容量为无穷大。1.3.2 车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要在m台机器上加工，每个工件有pi道工序，每台机器上总共要加工lj道工序。我们定义以下基本数学符号6：j:所有工件的集合，； m:所有机器的集合，；：工件ji的工序集合，；p:所有工序的集合，此为矩阵。p（i，j）表示i工件的第j道工序。，表示i工件的所有工序按优先顺序的排列。不足，那么其空余的位置用0填满。 （1.1）:机器顺序阵，此为矩阵。（i，j）表示i工件的第j道工序

24、的机器号，表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:如果某工件的工序数不足，那么其空余的位置用0填满。 （1.2）t:加工时间阵，此为矩阵。t(i, j)表示工件i的第j道工序在（i，j）上的加工时间。同样地，如果某工件的工序数不足，那么其空余的位置用0填满。 （1.3） ：工件排列阵，此为矩阵。表示在i机器上排在第j位加工的工件号，表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足，那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义:如果对应于一个确定的，满足或。即使得目标函数取值最小(或最大

25、)，且与相容，则称为车间作业调度问题在此目标函数下的最优解。生产调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从两个方面来考虑:生产成本和生产时间。调度问题从生产成本方面来考虑，其优化目标有:库存最少、在制品最少、设备利用率最高等;从生产时间方面来考虑，其优化目标有:最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。两个方向的优化目标之间彼此不是相互孤立的，其中的许多具体目标之间的联系很密切，有的相互促进，有的相互冲突，也有的毫无联系。1.4 课题研究内容及结构安排本文共分为三章。第一章简要介绍了车间调度问题和求解调度问题的基本方法；第二章介绍了遗传算法的基本理

26、论；第三章用遗传算法来解决车间调度问题,其中介绍了常用的几种编码方式,在比较的情况下提出本文主要用基于操作的编码方式.还有提出了几种主要的遗传算子。并且以四个工件四个机器问题进行举例,说明了用遗传算法解决车间调度问题的可行性。2 遗传算法相关理论与实现技术遗传算法(genetic algorithm, ga)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者holland于1975年首先提出来的7。它摒弃了传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程8。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，

27、交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1 自然进化与遗传算法自从达尔文的进化论得到人们的接受之后，生物学家们就对进化机制产生了极大的兴趣。化石记录表明我们所观察的复杂结构的生命是在相对短的时间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。虽然目前人们对进化机制在一些方面还没有弄清楚，但它们的一些特征已为人所知。进化是发生在编码染色体上，通过对染色体的译码部分生成生物体，但下面几个关于进化理论的一般特性已被广大人们所接受。1.进化过程发生

28、在染色体上，而不是发生在它们所编码地生物个体上。2.自然选择把染色体以及由它们所译成的结构表现联系在一起，哪些适应性好地个体的染色体经常比差的个体的染色体有更多的繁殖机会。3.繁殖过程是进化发生的那一刻，变异可以使生物体子代的染色体不同于它们父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生有很大差异的染色体。4.生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择的原则是适应者生存，不适者淘汰。自然选择决定了群体中那些个个体能存活并繁

29、殖，有性生殖保证了后代基因中的混合与重组。比起那些仅包含单个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的后代进化要快得多。2.2 基本遗传算法2.2.1 遗传算法的基本思路1.首先确定问题的求解空间；2.其次将求解空间中的每一个点进行编码，并从求解空间中任选n个点组成初始群体；3.计算当前群体中每个个体的适应度函数值。运用选择、交叉、变异算子产生新一代群体；4.对新一代群体中的个体进行评价，若找到满足问题的最优解，结束；否则，转步骤3。2.2.2 遗传算法的模式定理1.选择操作对模式的影响选择操作是遗传算法中体现“适者生存”的关键一环，它能控制高适应度的模式成指数级增长。最常

30、用的选择方式是“轮盘赌”法。其传统实现建立在逐项比较的基础上，算法复杂度为o（n2）。通过把各码链适应值转换为一组具有线性序的区间，从而可利用二分查找法实现“轮盘赌”选择操作的递归算法，使时间复杂度下降到o（nlog2n）。2.交换操作对模式的影响交换操作是有规则的信息交换，它能创建新的模式结构，但又最低限度地破坏选择操作过程所选择的高适应度的模式。假设交换操作是采用的单点随机杂交方式，随机选取杂交的起始位置，交叉概率为pc，两个具有相同模式h的个体发生交换，即杂交操作，不会改变模式h。但是如果其中一方个体不具有模式h，则有可能会引起另一个个体模式的改变。其中一方不具有模式h的概率为1- p(

31、h, t)，当两个个体发生交换时，如果引起模式h的改变，只可能将交换的起始位置选择在第一个模式位到最后一个模式位之间的任何一个位置上，此时，使模式h生存的概率ps，为: (2.1)在交换过程中，可能使两个都不具备模式h的个体经交换后产生模式h，故生存概率（）只是一个下界，则有： (2.2)综合考虑选择操作，模式h在下一代中的数量可以用下式来综合估计: (2.3)从上式可以看出，模式的平均适应度高于群体平均适应度，并且具有短定义距的模式，将在下一代中成指数级的增长。3.变异操作对模式的影响通过变异操作对个体串中单个位置进行代码替换，替换的概率为变异概率pm，则该位置不发生变异的概率为1-pm。要

32、使一个模式h在变异操作过程中不被破坏，就要保证模式h中确定位必须保证不变，因此，模式h保持不变的概率为: (2.4)上式中o(h)为该模式的阶数。综合上面所述，考虑到选择操作、交换操作和变异操作对模式的影响，则第t代种群p(t)经过遗传操作后下一代种群p(t+1)具有模式h的个体总数为: (2.5)该式表示了下述的模式定理。模式定理:在遗传算子选择、交换、变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将得以指数级增长。模式定理保证了较优的模式(遗传算法的较优解)的数目呈指数增长，为解释遗传算法机理提供了数学基础。由模式定理可知，具有低阶、短定义距以及平均适应度

33、高于群体平均适应度的模式在后代中呈指数级增长。这些模式在遗传中很重要，称为基因块。基因块假设:遗传算法通过短定义距、低阶以及高平均适应度的模式(基因块)，在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在;而基因块假设则指出了在遗传算子的作用下，算法具有生成全局最优解的能力，即能生成高阶、长定义距、高平均适应度的模式，最终生成全局最优解。上述结论并没有得到证明，因而被称为假设。目前已经有大量的实践证据支持这一假设，尽管大量的证据并不等于理论证明，但是至少可以肯定的是对很多经常碰到的问题，遗传算法都是适用的。2.2.3 遗

34、传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。通常，种群太小则不能提供足够的采样点，以致算法性能很差;种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。1.选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收

35、敛于全局最优解。2.交叉概率对收敛性的影响交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉;概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。3.变异概率对收敛性的影响变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。遗传操作对收敛性的影响，可利用马尔可夫链对遗传算法进行分析，从而论证了遗传算法在收敛性方面的一些重要性质，有力地支持了遗传算法的理论基础。由马尔可夫链推导出来的一些结论:基本遗传算法收敛于最优

36、解的概率为1,使用保留最优个体策略的遗传算法收敛于最优解的概率为1。4.隐含并行性隐含并行性定理:遗传算法所处理的模式总数与其群体规模n的立方成正比，即: m=o(n3) （2.6）由该定理可知，虽然表面上每代处理的个体数目都是一定的，但是由于每个个体都隐含着多种不同的模式，所以每次参与遗传算子操作的个体却不仅仅是两个。从总体上来说，每代之间所处理的个体要远大于其表面的数目，这就是遗传算法独特的隐含并行性。由隐含并行性定理可知，虽然表面上每代仅对n个个体处理操作，而事实上处理了o(n3)个模式，且无需额外存储。隐含并行性为遗传算法的高效性提供了理论依据。2.2.4 基本遗传算法参数说明对遗传算

37、法性能有影响的参数主要有:种群数目n、交换概率pc、变异概率pm、代沟g、尺度窗口w、和选择策略s等。1.种群数目(population size)种群数目的多少直接影响到遗传算法的优化性能和效率，种群选择太小时，不能提供足够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解。种群选择过大时，虽然能避免早熟收敛，但是增加了计算量。2.交换概率(crossover rate)交换概率pc用于控制交换操作的频率。交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象。交换概率太小的时候又容易产生搜索停滞不前的现象。3.变异概率(mutation rate)变异概率pm。增加种群

38、多样性具有重要意义。通常选取一个较低的变异概率。如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，则不能产生新个体，不利于种群的多样性。4.代沟(generation gap)代沟g用于控制每一代群体被替换的比例，每代有n×(1-g)个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并不是一个初始参数，而是评价遗传算法的一个参数。5.尺度窗口(scaling window)该参数用于作出由目标值到适应度函数值的调整。6.选择策略(selection strategy)一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例

39、选择，即个体被选择的概率与其适应度值成正比。另一种为保优策略，首先进行纯选择，把目前最优个体直接加入下一代种群中，该策略是为了防止最优解的丢失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型。2.3 遗传算法的优缺点2.3.1 遗传算法的优点遗传算法在解决优化问题过程中有如下优点:1.遗传算法从问题解的集合中开始嫂索，而不是从单个解开始。这种机制意味着搜索过程可以跳出局部最优点，能很好地将局部搜索和全局搜索协调起来，达到全局最优点。2.遗传算法有极强的容错能力，遗传算法的初始种群本身就带有大量与最优解甚远的信息，通过选择、交换、变异操作，能迅速排除与最优解相差极大的串，这是一个

40、强烈的滤波过程，并且是一个并行滤波机制。3.遗传算法是对参数进行编码，而不是对参数本身，因此遗传算法具有灵活性高的特点。4.遗传算法在搜索的过程中使用基于目标函数值的评价，而非传统方法的采用目标函数的导数信息或者求解问题域内知识，因此具有普遍适应性和可规模化的特点。5.遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应度值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。6.遗传算法具有很强的鲁棒性，在存在噪声的情况下，对同一问题利用遗传算法求解所得的结果是相似的。2.3.2 遗传算法的缺点1.遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不

41、能达到全局最优。2.对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地敛，而对以后变化了的数据不再产生变化。对于这个问题，研究者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓触发式超级突变，就是当染色体群体的质量下降(彼此的区别减少)时增加突变概率;另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。3.选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解;而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效

42、于一个非常大的变异率，而这么大的变异很可能影响进化过程。4.遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法对这类问题无法找到收敛的路。5.遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其它算法，互相补充，甚至根本不用遗传算法。2.4 遗传算法的进展地球上自出现生命至今已有30多亿年的历史，从低级生物到高级生命再至拥有智慧的人类，这是一个漫长的生物进化过程。1859年，达尔文根据长期对世界各地的考察以及人工选择的实验，发表了物种起源，系统地提出并建立了以“优胜劣汰”、“适者

43、生存”的自然选择为基础的进化论学说，根据他的进化论，生物发展进化的原因主要有三个，就是遗传、变异和选择。通过不断的选择，使有利于生存发展的变异遗传下去，积累下来，使变异和遗传向着适应环境的方向发展。经过长时间的遗传、变异和选择，生物便逐渐从简单到复杂，从低级到高级不断地进化和发展。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了

44、个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加

45、适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向9：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法10。这一新的学习机制对于解决人工智能11中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络12、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代

46、智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（evolution programming,ep）以及进化策略（evolution strategy,es）等进化计算理论日益结合。ep和es几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正

47、形成热点。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术它己经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。1967年，holland的学生j.d.bagley在博士论文中首次提出“遗传算法（genetic algorithms）”一词。此后，holland指导学生完成了多篇有关遗传算法研究的论文。1971年，r.b.hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年holland出版了他的著名

48、专著自然系统和人工系统的自适应（adaptation in natural and artificial systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，k.a.de jong完成了他的博士论文一类遗传自适应系统的行为分析（an analysis of the behavior of a class of genetic adaptive sy

49、stem）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把holland的模式理论与他的计算实验结合起来。尽管de jong和hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，de jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（internati

50、onal conference on genetic algorithms ，icga），并且成立国际遗传算法学会（international society of genetic algorithms ，isga），以后每两年举行一次。1989年，holland的学生d.e.goldberg出版了专著搜索、优化和机器学习中的遗传算法（genetic algorithms in search , optimization, and machine learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的koza基于自然选择原则创造性地

51、提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, gp)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次parallel problem solving from nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有foundations of genetic algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，l.davis编辑出版了遗传算法手册（handbook of genetic algo

52、rithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在artificial intelligence、machine learning、information science、parallel computing、genetic programming and evoluable machinesieee transactions on neur

53、al networks,ieee transactions on signal processing等杂志上发表。1993年，mit出版社创刊了新杂志evolutionary computation。1997年，ieee又创刊了transactions on evolutionary computation。advanced computational intelligence杂志即将发刊，由模糊集合创始人l.a.zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中现在随着科学技术的日益发展，遗传算法有了突

54、飞猛进的发展，不仅理论研究十分活跃，而在越来越多的领域得到发展。遗传算法主要应用在机器学习中。遗传算法适合于维数很高、体积很大、环境复杂、问题结构不十分清楚的场合，机器学习就属于这类情况。一般的学习系统要求具有随时间推移逐步调整有关参数或者改变自身结构以更加适应环境，更好达到目标的能力。由于多样性和复杂性，通常难以建立完善的理论以指导整个学习过程，从而使传统寻优技术的应用受到限制，而这恰好是遗传算法发挥的长处。除了机器学习之外遗传算法所涉及的主要领域还有自动控制、规划设计、组合优化、图象处理、信号处理、人工生命、模式识别，神经网络、自适应控制、生物科学、系统工程、社会科学等。在人工智能研究中，

55、现在还认为人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。今后几年，拓广更加多样的应用领域，将是ga发展的主流。这也是本世纪高新技术迅速发展带有规律性的特点，即面向应用。与此同时，理论方面同样有大量工作要做，例如：控制参数的选择；交换和突变这两类最重要的算子的确切作用；并行ga和分布式ga的研究。不论从理论还是应用的角度看，最紧迫的应是关于算法收敛性问题的研究，特别是过早收敛的防止。这对ga的实际应用关系重大。2.5 小结遗传算法是一类随机化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来评价染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。3 用遗传算法对具体问题的解决与探讨遗