下载文档原格式
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 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)，交叉速率，和突变率，生成这个问题初始种群。
