下载文档原格式
1 遗传算法1.1 遗传算法的定义遗传算法(GeneticAlgorithm，GA)是近多年来发展起来的一种全新的全局优化算法，它是基于了生物遗传学的观点，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
它通过自然选择、遗传、复制、变异等作用机制，实现各个个体的适应性的提高，从而达到全局优化。
遗传算法151解决一个实际问题通常都是从一个种群开始，而这个种群通常都是含有问题的一个集合。
这个种群是由一定数目的个体所构成的，利用生物遗传的知识我们可以知道这些个体正好组成了我们知道的染色体，也就是说染色体是由一个个有特征的个体组成的。
另外我们还知道，遗传算法是由染色体组成，而染色体是由基因组成，可以这么说，基因就决定了个体的特性，所以对于遗传算法的最开始的工作就需要进行编码工作。
然后形成初始的种群，最后进行选择、交叉和变异的操作。
1.2遗传算法的重要应用在现实应用中，遗传算法在很多领域得到很好的应用，特别是在解决多维并且相当困难的优化问题中时表现出了很大的优势。
在遗传算法的优化问题的应用中，其中最为经典的应用就是我们所熟悉的函数优化问题，它也是对遗传算法的性能进行评价的最普遍的一种算法;另外的一个最重要的应用，也就是我们本文所研究的应用—组合优化问题，一般的算法很难解决组合优化问题的搜索空间不断扩大的局面，而组合优化问题正好是解决这种问题的最有效的方法之一，在本文的研究中，比如求解TSP问题、VRP问题等方面都得到了很好的应用;另外遗传算法在航空控制系统中的应用、在图像处理和模式识别的应用、在生产调度方面的应用以及在工人智能、人工生命和机器学习方面都得到了很好的应用。
其实在当今的社会中，有关于优化方面的问题应用于各行各业中，因此有关于优化问题已经变得非常重要，它对于整个社会的发展来说都是一个不可改变的发展方向，也是社会发展的一个非常重要的需要。
1.3 遗传算法的特点遗传算法不同于传统的搜索与优化方法，它是随着问题种类的不同以及问题规模的扩大，能以有限的代价来很好的解决搜索和优化的方法。
什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。
举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。
同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。
遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。
现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术之一。
1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。
这种学说认为，生物要生存下去，就必须进行生存斗争。
生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。
在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。
遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。
选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。
选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。
遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。
即是对群体中的个体串的某些基因座上的基因值作变动。
群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。
每个个体实际上是染色体(chromosome)带有特征的实体。
染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。
因此，在一开始需要实现从表现型到基因型的映射即编码工作。
由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
遗传算法（GeneticAlgorithms）遗传算法前引：1、TSP问题1.1 TSP问题定义旅⾏商问题（Traveling Salesman Problem，TSP）称之为货担郎问题，TSP问题是⼀个经典组合优化的NP完全问题，组合优化问题是对存在组合排序或者搭配优化问题的⼀个概括，也是现实诸多领域相似问题的简化形式。
1.2 TSP问题解法传统精确算法：穷举法，动态规划近似处理算法：贪⼼算法，改良圈算法，双⽣成树算法智能算法：模拟退⽕，粒⼦群算法，蚁群算法，遗传算法等遗传算法：性质：全局优化的⾃适应概率算法2.1 遗传算法简介遗传算法的实质是通过群体搜索技术，根据适者⽣存的原则逐代进化，最终得到最优解或准最优解。
它必须做以下操作：初始群体的产⽣、求每⼀个体的适应度、根据适者⽣存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染⾊体的基因并随机变异某些染⾊体的基因⽣成下⼀代群体，按此⽅法使群体逐代进化，直到满⾜进化终⽌条件。
2.2 实现⽅法根据具体问题确定可⾏解域，确定⼀种编码⽅法，能⽤数值串或字符串表⽰可⾏解域的每⼀解。
对每⼀解应有⼀个度量好坏的依据，它⽤⼀函数表⽰，叫做适应度函数，⼀般由⽬标函数构成。
确定进化参数群体规模、交叉概率、变异概率、进化终⽌条件。
案例实操我⽅有⼀个基地，经度和纬度为（70，40）。
假设我⽅飞机的速度为1000km/h。
我⽅派⼀架飞机从基地出发，侦察完所有⽬标，再返回原来的基地。
在每⼀⽬标点的侦察时间不计，求该架飞机所花费的时间（假设我⽅飞机巡航时间可以充分长）。
已知100个⽬标的经度、纬度如下表所列:3.2 模型及算法求解的遗传算法的参数设定如下：种群⼤⼩M=50；最⼤代数G=100;交叉率pc=1，交叉概率为1能保证种群的充分进化；变异概率pm=0.1，⼀般⽽⾔，变异发⽣的可能性较⼩。
编码策略:初始种群：⽬标函数：交叉操作：变异操作：选择：算法图：代码实现：clc,clear, close allsj0=load('data12_1.txt');x=sj0(:,1:2:8); x=x(:);y=sj0(:,2:2:8); y=y(:);sj=[x y]; d1=[70,40];xy=[d1;sj;d1]; sj=xy*pi/180; %单位化成弧度d=zeros(102); %距离矩阵d的初始值for i=1:101for j=i+1:102d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*...cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));endendd=d+d'; w=50; g=100; %w为种群的个数，g为进化的代数for k=1:w %通过改良圈算法选取初始种群c=randperm(100); %产⽣1，...，100的⼀个全排列c1=[1,c+1,102]; %⽣成初始解for t=1:102 %该层循环是修改圈flag=0; %修改圈退出标志for m=1:100for n=m+2:101if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<...d(c1(m),c1(m+1))+d(c1(n),c1(n+1))c1(m+1:n)=c1(n:-1:m+1); flag=1; %修改圈endendendif flag==0J(k,c1)=1:102; break %记录下较好的解并退出当前层循环endendendJ(:,1)=0; J=J/102; %把整数序列转换成[0,1]区间上实数即染⾊体编码for k=1:g %该层循环进⾏遗传算法的操作for k=1:g %该层循环进⾏遗传算法的操作A=J; %交配产⽣⼦代A的初始染⾊体c=randperm(w); %产⽣下⾯交叉操作的染⾊体对for i=1:2:wF=2+floor(100*rand(1)); %产⽣交叉操作的地址temp=A(c(i),[F:102]); %中间变量的保存值A(c(i),[F:102])=A(c(i+1),[F:102]); %交叉操作A(c(i+1),F:102)=temp;endby=[]; %为了防⽌下⾯产⽣空地址，这⾥先初始化while ~length(by)by=find(rand(1,w)<0.1); %产⽣变异操作的地址endB=A(by,:); %产⽣变异操作的初始染⾊体for j=1:length(by)bw=sort(2+floor(100*rand(1,3))); %产⽣变异操作的3个地址%交换位置B(j,:)=B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);endG=[J;A;B]; %⽗代和⼦代种群合在⼀起[SG,ind1]=sort(G,2); %把染⾊体翻译成1，...,102的序列ind1num=size(G,1); long=zeros(1,num); %路径长度的初始值for j=1:numfor i=1:101long(j)=long(j)+d(ind1(j,i),ind1(j,i+1)); %计算每条路径长度endend[slong,ind2]=sort(long); %对路径长度按照从⼩到⼤排序J=G(ind2(1:w),:); %精选前w个较短的路径对应的染⾊体endpath=ind1(ind2(1),:), flong=slong(1) %解的路径及路径长度xx=xy(path,1);yy=xy(path,2);plot(xx,yy,'-o') %画出路径以上整个代码中没有调⽤GA⼯具箱。
遗传算法一、遗传算法的简介及来源1、遗传算法简介遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《自然系统和人工系统的自适应》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。
遗传算法模仿了生物的遗传、进化原理, 并引用了随机统计理论。
在求解过程中, 遗传算法从一个初始变量群体开始, 一代一代地寻找问题的最优解, 直至满足收敛判据或预先设定的迭代次数为止。
它是一种迭代式算法。
2、遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机理的搜索算法, 它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。
在利用遗传算法求解问题时, 问题的每个可能的解都被编码成一个“染色体”,即个体, 若干个个体构成了群体( 所有可能解) 。
在遗传算法开始时, 总是随机地产生一些个体( 即初始解) , 根据预定的目标函数对每个个体进行评价, 给出了一个适应度值。
基于此适应度值, 选择个体用来繁殖下一代。
选择操作体现了“适者生存”原理, “好”的个体被选择用来繁殖, 而“坏”的个体则被淘汰。
然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。
这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代, 这样逐步朝着更优解的方向进化。
因此, 遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。
3、遗传算法的一般算法（1）创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。
（2）评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。
什么是遗传算法遗传算法的基本意思就是说象人的遗传一样，有一批种子程序，它们通过运算得到一些结果，有好有坏，把好的一批取出来，做为下一轮计算的初值进行运算，反复如此，最终得到满意的结果。
举个例子，假如有一个动物群体，如果你能让他们当中越强壮的越能优先交配和产籽，那么千万年后，这个动物群体肯定会变得更加强壮，这是很容易理解的。
同样，对于许多算法问题，特别是NP问题，比如说最短路径，如果有400个城市，让你找出最短的旅游路线，采用穷举比较，复杂度为O（n！），这时，你可以先随机产生100种路径，然后让他们之中路程越短的那些越能优先互相交换信息(比如每条里面随机取出10个位置互相交换一下),那么循环几千次后，算出来的路径就跟最短路径非常接近了（即求出一个近似最优解）。
遗传算法的应用还有很多，基本思想都一样，但实现上可能差别非常大。
现在有许多搞算法的人不喜欢遗传算法，因为，它只给出了一种“有用”的方法，却不能保证有用的程度，与此相反，能保证接近最优程度的概率算法更受青睐。
遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。
它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
它是现代有关智能计算中的关键技术之一。
1.遗传算法与自然选择 达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。
这种学说认为，生物要生存下去，就必须进行生存斗争。
生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。
在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。
遗传算法总结简介遗传算法（Genetic Algorithm，简称GA）是一种基于生物进化过程中的遗传机制和自然选择原理的优化方法。
它模拟了自然界的进化过程，通过对问题空间中的个体进行选择、交叉和变异等操作，逐步搜索并优化解的过程。
遗传算法被广泛应用于解决各种优化、搜索和机器学习问题。
基本原理遗传算法的基本原理是通过模拟自然选择和遗传机制，寻找问题空间中的最优解。
其主要步骤包括初始化种群、选择操作、交叉操作、变异操作和确定终止条件等。
1.初始化种群：遗传算法的第一步是生成一个初始种群，其中每个个体代表一个可能的解。
个体的编码可以使用二进制、整数或实数等形式，具体根据问题的特点而定。
2.选择操作：选择操作通过根据适应度函数对种群中的个体进行评估和排序，选择较优的个体作为下一代种群的父代。
通常采用轮盘赌选择、竞争选择等方法来进行选择。
3.交叉操作：交叉操作模拟了生物遗传中的交配过程。
从父代个体中选择一对个体，通过交叉染色体的某个位置，生成下一代个体。
交叉操作可以通过单点交叉、多点交叉或均匀交叉等方式进行。
4.变异操作：变异操作引入了种群中的一定程度的随机性，通过改变个体的染色体或基因，以增加种群的多样性。
变异操作可以是位变异、部分反转、插入删除等方式进行。
5.确定终止条件：遗传算法会循环执行选择、交叉和变异操作，直到满足一定的终止条件。
常见的终止条件有达到最大迭代次数、找到最优解或达到计算时间限制等。
优点和局限性优点•遗传算法可以在大规模问题空间中进行全局搜索，不受问题的线性性和连续性限制。
它适用于解决多目标和多约束问题。
•遗传算法具有自适应性和学习能力，通过不断的进化和优胜劣汰过程，可以逐步收敛到最优解。
•遗传算法易于实现和理解，可以直观地表示问题和解决方案。
局限性•遗传算法需要选择合适的编码方式和适应度函数，以及调整交叉和变异的概率等参数。
这些参数的选择对算法的性能和结果有较大影响，需要经验和调整。
基于新的混合遗传算法的订单生产工序顺序相关的流水车间调度问题研究A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problemMohammad Mirabi •S. M. T. Fatemi Ghomi •F. Jolai2013年5月29号收到该文献,2014年3月18号录取,2014年4月9日出版.作者（2014）.这篇文章在开放存取的 网站发表摘要流水车间调度问题（FSP）用于处理m台机器n个工序的流水作业。
尽管FSP是典型的NP-hard问题，依然没有有效的算法以找到这个问题的最优解。
为了减少库存，延迟和安装成本,在工作时间一定,序列相关的每台机器上解决流水车间调度排序问题，在这提出了一种有三个遗传算子的新型混合遗传算法（HGA）。
该算法应用一种改进的方法来生成初始种群，并使用一种应用迭代交换过程改进初始解的改进启发式算法。
我们认为订单式生产方式，工序间隔时间是基于最大安装成本的禁忌搜索算法的解。
此外，与最近开发的启发式算法通过计算实验结果比较表明，该算法在解\的精度和效率方面表现出非常强的竞争力。
关键词:混合遗传算法流水作业调度序列相关引言流车间调度问题（FSP）作为在制造业研究的主要问题已经近七十年。
在一个有M台机器的流水作业车间中有m个工位,每个工序又有一台或几台机器。
此外，有n个工件在m个工位上依次加工。
在经典的流水作业问题里，每个工位都有一台机器，这一领域的研究吸引了最多的人次。
FSP的两个主要子问题是序列独立时间设置（SIST）和顺序相关时间设置（SDST）。
SDST流水作业问题更具有现实意义，但是吸引的注意力却少得多，特别是2000年以前（Allahverdi等，2008）在流水车间调度问题的目标是找到一个序列的机器加工的作业，以便一个给定的标准进行了优化。
这里有n个工件在每台机器上操作的可能的顺序，以及（N！）*M个的可能处理顺序。
流水作业调度的研究通常只参加置换序列，其中操作的处理顺序是所有机器。
在这里，我们也采用这种限制。
最小化所有最大完工时间作业（成为完工期并通过的Cmax表示）是公知的，也是在文献M. Mirabi (&)Group of Industrial Engineering, Ayatollah Haeri Universityof Meybod, P.O. Box 89619-55133, Meybod, Irane-mail: M.Mirabi@S. M. T. Fatemi GhomiDepartment of Industrial Engineering, Amirkabir University ofTechnology, P.O. Box 15916-34311, Tehran, Irane-mail: Fatemi@aut.ac.irF. JolaiDepartment of Industrial Engineering, College of Engineering,University of Tehran, P.O. Box 14395-515, Tehran, Iran中的适用标准。
考虑到计算的复杂性，SDST流水作业用的Cmax目标已被Gupta和Darrow （1986）证明是NP-hard问题，即使当m= 1，和m= 2，安装只能在第一台或第二台机器之间。
因此，由精确算法解决该问题是耗时和难于计算验证的。
开拓性的工作归功于约翰逊（1954）提出的一个简单的规则用于与流水作业问题（PFSP）两台机器的最佳序列。
这项工作是解决PFSP有两个以上的机器多次尝试的起点。
鉴于PFSP 问题的NP完整性（Garey等人1976年;坎贝尔等人1970年），研究人员已经主要推动启发式和元启发式的发展。
一些在本领域最早的启发式方法是纳瓦兹（1983）的NEH启发式和里夫斯的遗传算法（1995年）。
2000年以后，启发式算法有了更宽的研究范围，元启发式演算法和混合元启发式算法用于研究人员流水作业和置换流水作业。
Ruiz等在2005年对于同样的问题提出了两个启发式算法，结果显示他们的启发式超越以往。
Ruiz和Stutzle（2008）提出两个简单的以本地搜索基础的迭代贪婪算法，并表明，他们的算法执行比Ruiz等的更好。
Tseng等（2005年）开发了一个基于罚启发式算法解决同样的问题，比较了它们的启发式算法与现有的索引启发式算法。
在所有方法中，到现在为止解决PFSP问题最成功的元启发式之一是遗传算法。
Sun and Hwang (2001)发表了F2/STsd/Cmax的相关问题，其中设置时间只存在于第二机器和作业的设置时间取决于K表（1）紧接的工作。
他们对于这个问题提出了一个动态规划的制定和遗传算法。
Chaari等（2011年）研究了调度在不确定条件下的问题。
他们开发了一个遗传算法来解决混合流水车间调度问题中每个工件在每个机器的处理时间不确定的问题。
他们定义一个强大的双目标评价函数来获得健壮，有效的解决方案，而且对数据的不确定性非常敏感。
Tseng and Lin 在2010年提出了一个混合动力遗传算法来解决流水车间无等待调度完工期最优化问题。
该算法杂交了遗传算法和新奇的局部搜索算法。
这个本地搜索算法结合了两种局部搜索方法：插入搜索和一个新的具备剪切和修复能力的本地搜索方法。
Jarboui等在2011年提出了一个混合动力遗传算法来解决最小化完工时间和总流动时间的无等待流水作业调度问题。
在他们的研究中，基因的最后一步的改进过程采用可变邻域搜索。
Huang 在2010年研究了流水作业调度问题中材料同步的由一个自动化机器中心移动装载/卸载（L/ U），m台加工机器和一个转盘。
此外，其他有用和强大方法来解决PFSP问题。
Li等人在2004年提出部分枚举法（PEM）用来最小化大流量车间调度的完工期。
该PEM运行在短的时间内，很容易与其他算法或规则相结合，提高性能。
在他们的研究中，两个优先规则，方差方法和方差均值方法被开发。
Laha和Chakraborty在2007年开发出一种高效的随机混合启发式（H3）为流水作业调度问题，并表明他们相比其他研究者的优越性Noori-Darvish和Tavakkoli-Moghaddam在2012年提出了一种新的双目标数学规划解决开放式车间调度问题，其中处理时间不仅取决于机器，而且取决于应处理的作业顺序。
他们最小的迟到和完工时间。
Maleki-Darounkolaei等在2012年研究了三个阶段的组装流水作业调度问题在第一阶段顺序相关设置的时间和每个阶段阻断时间使得加权平均完成时间和完工时间最小化。
最后，Sheibani在2010年提出了PH算法解决置换流水车间调度完工时间标准化。
他的方法分为两个阶段：在排列优先顺序的作业然后构造一个序列。
他采用了一个模糊贪婪的评价函数应用到启发式的结构式中。
GA在解决NP-hard问题的成功应用，如FSP.刺激了我们研究混合遗传（HGA），以有效精确地处理这个问题。
正如之前在经典的流水作业问题所提到的，完工时间最小化原则一直吸引研究人员的关注。
通过在真实世界情况下的观察，我们可以看到，完工日期和安装成本是生产计划的最重要的原则，特别是在按订单生产的情况下。
各类客户提供他们的订单（工种），每个订单都有其自己的完工日期，持有成本和延误成本，而只是专注在完工时间是不科学的。
几乎全部现实世界的问题是多标准，并只考虑一个标准和实际情况相差太远。
Allahverdi等在2008年指出没有考虑多标准的研究根据实际情况是不可用的。
他还对到期日的相关标准提出了建议。
如前所述，SDST是与实际更加适应的情况。
此外，在复杂的情况下，有一些根据设置成本不可行序列（禁忌序列）。
例如，在各种纤维的染色工艺，每筐湿纤维（作业）必须通过几个染色机（工位）。
将染成鲜艳颜色的作业（奶油色，白色）在完全染成深色后（黑色，蓝色和红色）引起的高安装成本（染深颜色后，每台机器必须仔细清洗几乎2天，也至少有一个批次的颜色鲜艳浪费原因是深色染料的残留），所以他们是是不可行的序列。
这些在电缆行业用于生产彩电线的情况相同。
在这项研究中，我们考虑到置换流水车间必须处理n个工件，每一个都是从顾客准确的接收。
每个工件都有确定的截止日期和延误成本。
设置时间和设置成本是序列相关的，目标函数由三个标准构建:延迟，持有和安装成本。
此外，某些序列基于设置成本成为禁忌搜索的内容。
这种情况是兼容与现实世界的大部分问题，却没有文献记载。
我们就制订了HGA 去解决这个问题。
本文结构如下：第二节讨论用于解决PFSP算法的原理。
第三节比较集中算法的性能。
第四节总结全文。
混合遗传算法在这项研究中，遗传算法（GA）被应用于解决置换流水车间调度问题。
John Holland 在上世纪60年代的第一次提出GA。
GA作为进化算法（EA）的一种，它受到自然进化的启发，如突变，选择和交叉，找到优化问题和启发式问题的最优解。
GA的主要概念是产生方案解的一个初始群体（称为个人，生物，或表型）并且朝更准确的方向优化。
如今，GA具有宽广和成功的应用在解决复杂函数优化问题方面。
它的成功主要是由于其简单易操作和极大的灵活性。
这些原因刺激我们使用这种强大的方法来解决所出现的问题。
最初，许多个性化解决方案（称为染色体）通常随机产生，以产生一个初始群体。
种群大小取决于问题的性质，但一般包含几个数百或数千的可能的解决方案。
染色体通过连续迭代，被称为子代。
在每一代中，染色体通过基于适应度方法进化，其中更合适的解决方案（由适应度函数测量）通常是更容易被选择，下一个步骤是从这些解决方案中通过遗传操作：选择，交叉和突变生成一个第二代种群。
从产生的每一个新的解决方案中，从之前的可行解中选择一对'父代'用来繁殖，通过使用上述交叉和变异的方法产生一个“子代”解，一个新的解通常具备“父代”共同的优点。
从新的“子代”中选择“父代”，重复上述过程，直到产生一个大小合适的种群。
经过固定数目的迭代，算法收敛到最佳染色体，这可能是问题的最优解或近似最优解。
流水作业调度问题可以看作是一个难优化问题，杂交一些其他方法以丰富在本文提到的GA。
本文提到的遗传算法杂交了几个启发式算法使得到的解更准确。
图1示出HGA解决FSP的流程图,HGA杂交一种叫做迭代交换过程（ISP）的启发式算法。
除了ISP，它还采用启发式方法构建初始解池。
此外，使用三个遗传算子繁殖出更好的后代。
HGA的过程描述如下：GA参数的确定，如迭代次数，则种群大小(P size)，交叉速率，和突变率，生成这个问题初始种群。
