《基于遗传算法求解作业车间调度问题本科生毕业设计.doc》由会员分享，可在线阅读，更多相关《基于遗传算法求解作业车间调度问题本科生毕业设计.doc（40页珍藏版）》请在三一办公上搜索。
1、基于遗传算法求解作业车间调度问题摘 要作业车间调度问题(JSP)简单来说就是设备资源优化配置问题。作业车间调度问题是计算机集成制造系统(CIMS)工程中的一个重要组成部分，它对企业的生产管理和控制系统有着重要的影响。在当今的竞争环境下，如何利用计算机技术实现生产调度计划优化，快速调整资源配置，统筹安排生产进度，提高设备利用率已成为许多加工企业面临的重大课题。近年来遗传算法得到了很大的发展，应用遗传算法来解决车间调度问题早有研究。本文在已有算法基础上详细讨论了染色体编码方法并对其进行了改进。在研究了作业车间调度问题数学模型和优化算法的基础上，将一种改进的自适应遗传算法应用在作业车间调度中。该算法
2、是将sigmoid函数的变形函数应用到自适应遗传算法中，并将作业车间调度问题中的完工时间大小作为算法的评价指标，实现了交叉率和变异率随着完工时间的非线性自适应调整，较好地克服了标准遗传算法在解决作业车间调度问题时的“早熟”和稳定性差的缺点，以及传统的线性自适应遗传算法收敛速度慢的缺点。以改进的自适应遗传算法和混合遗传算法为调度算法，设计并实现了作业车间调度系统，详细介绍了各个模块的功能与操作。最后根据改进的编码进行遗传算法的设计，本文提出了一种求解车间作业调度问题的改进的遗传算法，并给出仿真算例表明了该算法的有效性。关键词：作业车间调度；遗传算法；改进染色体编码；生产周期Solving jop
3、shop scheduling 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 v
4、ital effect onproduction 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 develo
5、pment it was used 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
6、(IAGA) obtained 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
7、the completiontime, 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 s
8、cheduling system 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
9、 to the job shop scheduling problem, and the simulated example has indicated that this algorithm is valid.Keywords: jop shop scheduling; genetic algorithm; improvement chromosome code; production cycl目 录摘 要IAbstractII1 绪论11.1 课题来源11.2 作业车间调度问题表述11.3 车间作业调度问题研究的假设条件及数学模型21.3.1 车间作业调度问题研究的假设条件21.3.2 车
10、间作业调度问题的数学模型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 遗传算法的进展122.5 小结153 用遗传算法对具体问题的解决与探讨163.1 研究过程中的几个关键问题163.1.1 设备死锁现象163.1.2 参数编码163.1.3 初始种群的生成193.1.4 个体的适应度函数203.1
11、.5 算法参数203.1.6 遗传算子的设计213.2 遗传算法终止条件243.3 遗传算法解决车间调度问题的改进243.4 系统仿真243.5 小结29结 论30致 谢31参考文献32附 录331 绪论1.1 课题来源随着加入WTO，市场竞争越来越激烈，对制造企业来说，为了能够在竞争中立于不败，降低成本是不得不面临的问题，而确保生产车间较高的生产能力和效率，是当务之急。此外，有效的调度方法已经成为先进制造技术实践的基础和关键，所以对它的研究具有重要的理论和实用价值。当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代
12、科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。虽然对其研究已有几十年的历史但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着较大距离。目前的调度算法大多只关心工件的调度问题，而对其它资源分配问题则研究相对不多，将二者结合起来研究应该是值得注意的问题，目前已有不少学者开始关注该问题。由于一般车间调度问题的复杂性，各种不同的具体
13、问题往往有许多不同的算法来解决，例如经典的启发式算法，传统的搜索方法等。由于遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法1。它特别适合于处理传统搜索算法解决不好的复杂和非线性问题。一些学者们经过大量的实践证明了遗传算法在解决作业车间调度问题上比经典的启发式算法好，同时遗传算法比传统的搜索技术有更强的优越性，因为它不仅能解决某一特定问题，而且可以适应不同的问题形式2。1.2 作业车间调度问题表述作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标
14、就是如何选择加工顺序使得总的加工时间最短最优。前提假设3：1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。2. 不同工件的加工工序可以不同；3. 所有工件的工序数不大于设备数；4. 每道工序必须在指定的某种设备上加工；5. 任何作业没有抢先加工的优先权；6. 在作业优化过程中既没有新的工件加入也没有取消的工件；调度问题具有相当的难度，目前调度问题的理论研究成果主要在job-shop问题为代表的基于最小完工时间的调度问题上。求解调度问题的方法称为调度优化算法。它可分为精确求解方法和近视求解方法。其中精确求解方法包括解析方法、穷举方法（包括分支定界）等；近似求解方法包
15、括基于规则的构造性方法、邻域搜索算法（如进化遗传算法，模拟退火算法）以及人工智能方法（如神经网络）4等。而传统的运筹学方法，即便在较大规模的基于单目标优化的静态调度问题中也难以有效应用。本文从实际和理论两方面进行研究和深入，重点研究了现代进化算法中有代表性发展优势的遗传算法。车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序
16、”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线5。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。 1.3 车间作业调度问题研究的假设条件及数学模型1.3.1 车间作业调度问题研究的假设条件在研究一般的车间作业调度问题中往往需要明确两类重要假设条件:1.工艺路径约束:工件的任一工序必须在其前道工序完成后才能开始，并保证同一工件不会同时在两台机器上加工，反映了工件
17、不同工序间的时序关系;2.资源(机器)独占性约束:任一台机器每次只能加工一个工件，且一旦开工就不能中断，反映了加工队列中工件间的时序关系。此外，还有一些辅助假设条件，如下:1. 各工件经过其准备时间后可开始加工;2. 不考虑工件加工的优先权，即工件之间没有优先约束关系限制的;3. 工序允许等待，即前一个工序未完成，则后面工序需要等待;4. 所有机器处理的加工类型均不同;5. 工件的加工时间事先给定，且在整个加工过程中保持不变;6. 缓冲区容量为无穷大。1.3.2 车间作业调度问题的数学模型建立车间作业调度问题的数学模型，是我们研究该问题的出发点，同时也为其后的研究奠定了基础。假设有n个工件，要
18、在m台机器上加工，每个工件有Pi道工序，每台机器上总共要加工Lj道工序。我们定义以下基本数学符号6：J:所有工件的集合，； M:所有机器的集合，；：工件Ji的工序集合，；P:所有工序的集合，此为矩阵。P（i，j）表示i工件的第j道工序。，表示i工件的所有工序按优先顺序的排列。不足，那么其空余的位置用0填满。 （1.1）:机器顺序阵，此为矩阵。（i，j）表示i工件的第j道工序的机器号，表示i工件的所有工序按优先顺序加工的各机器号的排列。注意:如果某工件的工序数不足，那么其空余的位置用0填满。 （1.2）T:加工时间阵，此为矩阵。T(i, j)表示工件i的第j道工序在（i，j）上的加工时间。同样地
19、，如果某工件的工序数不足，那么其空余的位置用0填满。 （1.3） ：工件排列阵，此为矩阵。表示在i机器上排在第j位加工的工件号，表示i机器上依次加工的各工件的排列。同上，如果某工件的工序数不足，那么其空余的位置用0填满。事实上，工件排列阵就是调度的一种表示形式。由此，我们可以给出一般性的车间作业调度数学模型的定义:如果对应于一个确定的，满足或。即使得目标函数取值最小(或最大)，且与相容，则称为车间作业调度问题在此目标函数下的最优解。生产调度问题存在多种优化目标或者综合优化目标，调度问题的优化目标通常从两个方面来考虑:生产成本和生产时间。调度问题从生产成本方面来考虑，其优化目标有:库存最少、在制
20、品最少、设备利用率最高等;从生产时间方面来考虑，其优化目标有:最大程度满足交货期、最小完成时间、最小流动时间和最小等待时间等。两个方向的优化目标之间彼此不是相互孤立的，其中的许多具体目标之间的联系很密切，有的相互促进，有的相互冲突，也有的毫无联系。1.4 课题研究内容及结构安排本文共分为三章。第一章简要介绍了车间调度问题和求解调度问题的基本方法；第二章介绍了遗传算法的基本理论；第三章用遗传算法来解决车间调度问题,其中介绍了常用的几种编码方式,在比较的情况下提出本文主要用基于操作的编码方式.还有提出了几种主要的遗传算子。并且以四个工件四个机器问题进行举例,说明了用遗传算法解决车间调度问题的可行性
21、。2 遗传算法相关理论与实现技术遗传算法(Genetic Algorithm, GA)是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的7。它摒弃了传统的搜索方式，模拟达尔文的遗传选择和自然淘汰的生物进化过程8。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。2.1 自然进化与遗传算法自从达尔文的进
22、化论得到人们的接受之后，生物学家们就对进化机制产生了极大的兴趣。化石记录表明我们所观察的复杂结构的生命是在相对短的时间进化而来的，对这一点包括生物学家在内的许多人都感到惊奇。虽然目前人们对进化机制在一些方面还没有弄清楚，但它们的一些特征已为人所知。进化是发生在编码染色体上，通过对染色体的译码部分生成生物体，但下面几个关于进化理论的一般特性已被广大人们所接受。1.进化过程发生在染色体上，而不是发生在它们所编码地生物个体上。2.自然选择把染色体以及由它们所译成的结构表现联系在一起，哪些适应性好地个体的染色体经常比差的个体的染色体有更多的繁殖机会。3.繁殖过程是进化发生的那一刻，变异可以使生物体子代
23、的染色体不同于它们父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生有很大差异的染色体。4.生物进化没有记忆。有关产生个体的信息包含在个体所携带的染色体的集合以及染色体编码的结构之中，这些个体会很好的适应它们的环境。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择的原则是适应者生存，不适者淘汰。自然选择决定了群体中那些个个体能存活并繁殖，有性生殖保证了后代基因中的混合与重组。比起那些仅包含单个亲本的基因拷贝和依靠偶然变异来改进的后代，这种由基因重组产生的后代进化要快得多。2.2 基本遗传算法2.2.1 遗传算法的基本思路1.首先确定问题的求解空间；2.其
24、次将求解空间中的每一个点进行编码，并从求解空间中任选N个点组成初始群体；3.计算当前群体中每个个体的适应度函数值。运用选择、交叉、变异算子产生新一代群体；4.对新一代群体中的个体进行评价，若找到满足问题的最优解，结束；否则，转步骤3。2.2.2 遗传算法的模式定理1.选择操作对模式的影响选择操作是遗传算法中体现“适者生存”的关键一环，它能控制高适应度的模式成指数级增长。最常用的选择方式是“轮盘赌”法。其传统实现建立在逐项比较的基础上，算法复杂度为O（n2）。通过把各码链适应值转换为一组具有线性序的区间，从而可利用二分查找法实现“轮盘赌”选择操作的递归算法，使时间复杂度下降到O（nlog2n）。
25、2.交换操作对模式的影响交换操作是有规则的信息交换，它能创建新的模式结构，但又最低限度地破坏选择操作过程所选择的高适应度的模式。假设交换操作是采用的单点随机杂交方式，随机选取杂交的起始位置，交叉概率为Pc，两个具有相同模式H的个体发生交换，即杂交操作，不会改变模式H。但是如果其中一方个体不具有模式H，则有可能会引起另一个个体模式的改变。其中一方不具有模式H的概率为1- p(H, t)，当两个个体发生交换时，如果引起模式H的改变，只可能将交换的起始位置选择在第一个模式位到最后一个模式位之间的任何一个位置上，此时，使模式H生存的概率Ps，为: (2.1)在交换过程中，可能使两个都不具备模式H的个体
26、经交换后产生模式H，故生存概率（）只是一个下界，则有： (2.2)综合考虑选择操作，模式H在下一代中的数量可以用下式来综合估计: (2.3)从上式可以看出，模式的平均适应度高于群体平均适应度，并且具有短定义距的模式，将在下一代中成指数级的增长。3.变异操作对模式的影响通过变异操作对个体串中单个位置进行代码替换，替换的概率为变异概率Pm，则该位置不发生变异的概率为1-Pm。要使一个模式H在变异操作过程中不被破坏，就要保证模式H中确定位必须保证不变，因此，模式H保持不变的概率为: (2.4)上式中O(H)为该模式的阶数。综合上面所述，考虑到选择操作、交换操作和变异操作对模式的影响，则第t代种群P(
27、t)经过遗传操作后下一代种群P(t+1)具有模式H的个体总数为: (2.5)该式表示了下述的模式定理。模式定理:在遗传算子选择、交换、变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将得以指数级增长。模式定理保证了较优的模式(遗传算法的较优解)的数目呈指数增长，为解释遗传算法机理提供了数学基础。由模式定理可知，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在后代中呈指数级增长。这些模式在遗传中很重要，称为基因块。基因块假设:遗传算法通过短定义距、低阶以及高平均适应度的模式(基因块)，在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本
28、数呈指数增长，从而使遗传算法找到全局最优解的可能性存在;而基因块假设则指出了在遗传算子的作用下，算法具有生成全局最优解的能力，即能生成高阶、长定义距、高平均适应度的模式，最终生成全局最优解。上述结论并没有得到证明，因而被称为假设。目前已经有大量的实践证据支持这一假设，尽管大量的证据并不等于理论证明，但是至少可以肯定的是对很多经常碰到的问题，遗传算法都是适用的。2.2.3 遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。通常，种群太小则不能提
29、供足够的采样点，以致算法性能很差;种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。1.选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。2.交叉概率对收敛性的影响交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉;概率太小时，交叉操作很少进行，从而会使搜索停
30、滞不前，造成算法的不收敛。3.变异概率对收敛性的影响变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。遗传操作对收敛性的影响，可利用马尔可夫链对遗传算法进行分析，从而论证了遗传算法在收敛性方面的一些重要性质，有力地支持了遗传算法的理论基础。由马尔可夫链推导出来的一些结论:基本遗传算法收敛于最优解的概率为1,使用保留最优个体策略的遗传算法收敛于最优解的概率为1。4.隐含并行性隐含并行性定理:遗传算法所处理的模式总数与其群体规模N的立方成正比，即: m=O(N3) （2.6）由该定理可知，虽然表面上每代处理的个体数目
31、都是一定的，但是由于每个个体都隐含着多种不同的模式，所以每次参与遗传算子操作的个体却不仅仅是两个。从总体上来说，每代之间所处理的个体要远大于其表面的数目，这就是遗传算法独特的隐含并行性。由隐含并行性定理可知，虽然表面上每代仅对N个个体处理操作，而事实上处理了O(N3)个模式，且无需额外存储。隐含并行性为遗传算法的高效性提供了理论依据。2.2.4 基本遗传算法参数说明对遗传算法性能有影响的参数主要有:种群数目N、交换概率Pc、变异概率Pm、代沟G、尺度窗口W、和选择策略S等。1.种群数目(population size)种群数目的多少直接影响到遗传算法的优化性能和效率，种群选择太小时，不能提供足
32、够多的个体，致使算法性能较差，易产生早熟收敛，甚至不能得到可行解。种群选择过大时，虽然能避免早熟收敛，但是增加了计算量。2.交换概率(crossover rate)交换概率Pc用于控制交换操作的频率。交换概率太大的时，易产生更新过快，从而破坏掉高适应度个体的现象。交换概率太小的时候又容易产生搜索停滞不前的现象。3.变异概率(mutation rate)变异概率Pm。增加种群多样性具有重要意义。通常选取一个较低的变异概率。如果变异概率太大的时，遗传算法易变成随机搜索，如果变异概率太小，则不能产生新个体，不利于种群的多样性。4.代沟(generation gap)代沟G用于控制每一代群体被替换的比
33、例，每代有N(1-G)个父代个体选中进入下一代种群中，该参数和交换、变异概率以及选择策略有很大关系，它并不是一个初始参数，而是评价遗传算法的一个参数。5.尺度窗口(scaling window)该参数用于作出由目标值到适应度函数值的调整。6.选择策略(selection strategy)一般来说有两种选择策略，一种为纯选择，种群中每个个体根据其适应度值进行比例选择，即个体被选择的概率与其适应度值成正比。另一种为保优策略，首先进行纯选择，把目前最优个体直接加入下一代种群中，该策略是为了防止最优解的丢失，但在实际应用中往往采取这两种选择策略结合的方法，并做适当的变型。2.3 遗传算法的优缺点2.
34、3.1 遗传算法的优点遗传算法在解决优化问题过程中有如下优点:1.遗传算法从问题解的集合中开始嫂索，而不是从单个解开始。这种机制意味着搜索过程可以跳出局部最优点，能很好地将局部搜索和全局搜索协调起来，达到全局最优点。2.遗传算法有极强的容错能力，遗传算法的初始种群本身就带有大量与最优解甚远的信息，通过选择、交换、变异操作，能迅速排除与最优解相差极大的串，这是一个强烈的滤波过程，并且是一个并行滤波机制。3.遗传算法是对参数进行编码，而不是对参数本身，因此遗传算法具有灵活性高的特点。4.遗传算法在搜索的过程中使用基于目标函数值的评价，而非传统方法的采用目标函数的导数信息或者求解问题域内知识，因此具
35、有普遍适应性和可规模化的特点。5.遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应度值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。6.遗传算法具有很强的鲁棒性，在存在噪声的情况下，对同一问题利用遗传算法求解所得的结果是相似的。2.3.2 遗传算法的缺点1.遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。2.对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地敛，而对以后变化了的数据不再产生变化。对于这个问题，研究者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓触发式超级突变，就是当染
36、色体群体的质量下降(彼此的区别减少)时增加突变概率;另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。3.选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解;而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。4.遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法对这类问题无法找到收敛的路。5.遗传算法并不一定总是最好的优
37、化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其它算法，互相补充，甚至根本不用遗传算法。2.4 遗传算法的进展地球上自出现生命至今已有30多亿年的历史，从低级生物到高级生命再至拥有智慧的人类，这是一个漫长的生物进化过程。1859年，达尔文根据长期对世界各地的考察以及人工选择的实验，发表了物种起源，系统地提出并建立了以“优胜劣汰”、“适者生存”的自然选择为基础的进化论学说，根据他的进化论，生物发展进化的原因主要有三个，就是遗传、变异和选择。通过不断的选择，使有利于生存发展的变异遗传下去，积累下来，使变异和遗传向着适应环境的方向发展。经过长时间的遗传、变异和选择，生物便逐
38、渐从简单到复杂，从低级到高级不断地进化和发展。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜
39、劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向9：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算
40、法扩展到具有独特的规则生成功能的崭新的机器学习算法10。这一新的学习机制对于解决人工智能11中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络12、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发
41、挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术它己经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者
42、们的兴趣。1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著自然系统和人工系统的自适应（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗
43、传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文一类遗传自适应系统的行为分析（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作
44、进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次
45、。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Na
46、ture 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，L.Davis编辑出版了遗传算法手册（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在Artificial Intelligence、Machine Learning、Information science、Parallel Computing、Genetic Programming and Evoluable MachinesIEEE Transactions on Neural Networks,IEEE Transactio
