基于新的混合遗传算法的订单生产工序顺序相关的流水车
间调度问题研究
A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem
Mohammad Mirabi ?S. M. T. Fatemi Ghomi ?F. Jolai
2013年5月29号收到该文献,2014年3月18号录取,2014年4月9日出版.作者（2014）.这篇文章在开放存取的https://www.doczj.com/doc/1f5897691.html, 网站发表
摘要流水车间调度问题（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 University
of Meybod, P.O. Box 89619-55133, Meybod, Iran
e-mail: M.Mirabi@https://www.doczj.com/doc/1f5897691.html,
S. M. T. Fatemi Ghomi
Department of Industrial Engineering, Amirkabir University of
Technology, P.O. Box 15916-34311, Tehran, Iran
e-mail: Fatemi@aut.ac.ir
F. Jolai
Department 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)，交叉速率，和突变率，生成这个问题初始种群。初始种群产生预定数量子代以后，ISP用来改善所有染色体。然后每个染色体通过评价函数测量。采用轮盘赌选择操作选择一些染色体用于遗传操
作，包括顺序交叉，启发式突变，以及反转突变。新的子代染色体产生后，他们的关联经过ISP操作后得到提高。后代的适应值经过评估可能成为加入到种群中，如果它拥有一个相对良好的质量。这些步骤是迭代进行的，然后轮盘赌选择再次进行开始下一次迭代。该HGA 将不停止直到达到迭代的预定数量。
初始化
HGA的初始解是由高性能的构造启发式算法。在初始化阶段，我们需要的初始解区域,基于我们的经验，结构式启发比随机的方法更好。之前，我们构建禁忌序列的清单基于对安装成本获得的信息序列。之后，我们在划分四个等级基于所有订单（工件）的重要性.
图1
图2
每个作业的重要性的确定于其客户的重要性和排名（根据ISO标准清单），工作延误成本，工作持有成本和其他基于管理角度的因素。等级名称分为低，中，高和非常高。工件处于高等级有非常高的重要性在低等级则只有很低的重要性。
每个工件都有自己的到期日并且在到期日前后交付，每个周期的单位延迟成本和持有成本必须分别支付.例如，假设交付编号为1的工作的时间周期4，并且处理时间为两个周期。还假设每个周期持有成本和延误成本为4和8，和规划时间有10个周期。对于作业1，我们可以构建序列图2。
这意味着在时期产生工件1成本为8。对于n个工件，我们有N个字符串是这样的。使用下面的算法进行初始化：
1）输入T（时间周期）×n（工件数）和Psize（种群大小）
2）定义工件1到n和时间周期1至T
3）t=1到T
4）t= 1
5）选择成本最低的工件t ，并把它尽快安排进在序列。如果两个作业具有相同的成本选择具有更重要的工作与或者相同的条件中随机选择一个。
6）消除所选作业的字符串相关性
7）如果在t 到4期内有多余的容量
8）如果没有t 不等于t+11
9）结束了
10）提取最终序列（初始解1）
11）为K = 1顶大小
12）交汇处相同的两个作业的位置水平（随机）
13）如果没有禁忌序列，最后确定的结果作为
一个初始解决方案
14）结束了
15）提取所有Psize 初始解
当然在初始化阶段中，我们不考虑安装成本，只关心禁忌序列。
2-opt 邻域搜索启发式通常用于改善的难优化问题得解。然而，它因为两个互换进行检查增加了计算时间，如果新的解决方案是比原来的，或父代更好的。从质量的角度衡量，它将取代之前父代种群成为新的父代种群。所有的互换子代都要进行检验，直到没有进一步改善。为了提高效率，（Ho 和Ji 2003 ，2004）如图3所示，ISP 用来提高每个初始解的相关性，后代算子由三个遗传操作生成。ISP 除了两种互换要进行检查外，其原理与2-opt 邻域搜索类似。ISP 的操作程序如下：
图3
步骤1：从父代随机选择两个基因。
步骤2：交换这两个基因的位置并后代。
步骤3：删除劣质基因产生优质后代。
第4步：将基因填充紧空第三步缺位置形成新的序列产生子代。如图4
步骤5：通过交换父代产生后代并重复第一步到第四步.
启发式变异
如前面提到的，适应度函数最小化迟到成本，持有成本，和安装成本（Mirabi 2010年）。例如，可行解区域的一个解决方案（定义为 H ）。这个选择的解决方案的适应度函数正是：
Z(h)=∑∑SC ij (∑X jit n j=0)n i=1n j=0+ ∑∑(∑X jit n j=0 (T ?DD i )?
n t=DDI+1n i=1DC I )+ ∑∑(∑X jit n j=1)?( DD i ?t)?HC i )n t=min *RTi,DD i +n j=1
其中，指数i 和j= 1，...，N 代表所有的工件，
t= 1，...，T 代表周期时间的设定。所有时间长度都假定是相等的;参数PTI 是工件i 的处理时间， DDI 是工件的交货日期，ST0i 是工件I 的初始设置时间（工件I 第一个被处理），STji 是工件j 处理之后要处理工件I 的安装时间，SC0i 是工件I 的初始设置作业成本（工件I 第一个被处理），SCji 是工件j 处理后处理工件I 的安装成本，HCI 是时间周期的持有成本，DCI 是时间周期内的延误成本，RTI 是工件I 的释放时间;变量：Xjit ，如果序列JI （作业i 在作业j 之后）出现在周期t ，否则，X0i1。如果工件I 是第一个在序列中处理的（显然它产生在第1期），否则0。
适应度函数的第一步是计算在每个JI （IJ ）序列中所有的生产设置成本总和。第二步，如果每个工件I 是在完工日期后生产的，对每个延迟期间，罚金DCI 应被支付;最后，最后一步对未按期交付支付延误成本。
在这项研究中，我们只是对适应度函数进行了研究，但这个问题也有一些制约因素。建议读者参考Mirabi （2010年）。
选择
常用的遗传操作符是轮盘赌选择操作，（Goldberg 1989），它是以适应度函数为基础按比例从交配区域选择繁殖。因此，在群体中的第I 个串按概率被选择。在染色体中适应度越高被选择的概率越大。尽管具有最高适应度染色体不能保证它一定被选择。由于在一个简单的GA 中种群大小通常保持固定，所以每个的概率的总和被选中的交配池字符串必须是。假设种群规模大小为P size ，那么选择程序如下：
第1步：计算种群总的适应度
F=∑Z(?)P size ?=1
步骤2：计算每个染色体的X h 被选择的概率P h ：
P ?=F?Z(?)
F?(P size ?1) h=1.2…. P size
步骤3：计算每个染色体的Xh 的累积概率QH ：
Q ?=∑P
j ?j=1 h=1.2…. P size 步骤4：在（0，1]范围内生成随机数r
第5步：如果Q ??1 遗传操作 图4 图5 遗传搜索进度是由两个基本遗传操作执行，包括开发和探索。一般情况下，交叉算子得到更好的解决方案,而变异算探讨更广泛的搜索空间。在用于流水车间作业问题的遗传算法是一体的交叉和两个突变，分别被称为启发式突变以及反转突变。 顺序交叉 在HGA采用的交叉算子是经典的顺序交叉（Gen and Cheng 1997）,每次产生两个子代. 顺序交叉的操作是： 第1步：随机从一个父代选择一个字符串。 第2步：通过复制字符串到父代相应位置而产生原型子代 第3步：将第二个福袋中所有字符串中已有的符号全部去掉,余下的顺序包含了原型子代需要的符号。 步骤4：将基因从左到右植入子代根的空缺职位得到步骤3中的基因序列，以产生后代，示于图4。 第5步：重复步骤1-4交换两个父代的角色产生另一个后代。 启发式突变 启发式突变是（Gen and Cheng 1997）采用邻域搜索技术来产生更好的后代。给定染色体的邻域可以考虑为从给定的一个染色体通过交换随机选择不重复基因产生的染色体集合。只有在附近最好的染色体才会作为由突变产生的后代。然而，其目的是提高种群的多样性。因此，有必要改变原来对于FPS的启发式变异，该修改是所有生成的邻域解都用作后代。该过程的启发式变异操作，示于图5，操作如下： 第1步：随意从父代选择三个基因。 第2步：评价所有的邻域调度选择最好的淋浴染色体作为子代 图6 反转基因突变 反转算子(Gen and Cheng 1997)选择来自父代子串并将其反转以形成后代，如图6，但是，反转操作者只有一条染色体，它是类似于启发式变异因而缺乏染色体之间交换的特点。因此，反转算子是突变操作，这是用于提高种群的多样性，而不是提高种群的质量。 结果分析 在本节中，我们通过计算比较HGA和其他三种启发式算法的结果。分别是Li等2004年的PEM，Laha and Chakraborty在2007年提出的H3和Sheibani在2010年提出的PH。四种方法比较了不同的问题大小（N = 10，20，30，40，50，100且m = 5，10，15，20）。对于每个类的问题都定义（N，M），随机产生10个实例。因此，我们得到总共280问题的实例。处理时间和设置时间是从给定均匀随机U（1，99）和U（1,9）离散分布分别获得，计算结果为十个实例的平均值。 HGA的问题参数是种群大小为20，交叉率0.5，变异率0.2。 因此五双染色体被选择执行顺序交叉操作，而四个染色体执行启发式变异操作和反转突变操作。每次迭代产生子代的总数的将是34（顺序操作10个，启发式变异操作20个和反转突变操作4个）。该该实验的平台是一台个人计算机，采用了奔腾III1.2赫兹的CPU和512 MB 的RAM。这些方案用MATLAB软件编码，为了确保四种方法之间运行条件的相同所有算法都运行相同的迭代次数。为了评估不同的算法，我们使用了每类问题性能指标（PM）来表示，如 PM i=SOLUTION i?BEST i BEST i Solutioni是从算法I得到的适应度值，Bestsol是所有算法最佳适应度值。所有算法的PM平均值，最小值和最大值表示在表1中。最小值列显示，有解的实例数量和所有算法的最佳适应值相等。在平均数列，我们发现两个子序列包含了10个PM值的平均数。并且十个解的平均数是这十个解的倍数。对所获得的解决方案，表1演示了该算法的排序。第一是HGA ，第二是pH，第三是H3和第四是PEM。 表.1 表.2 现在，为了得到跟详细的比较信息，两个算法HGA 和PH 被再次进行比较。在此步骤中，期望在相同的CPU 时间同时停止算法。这个CPU 时间采取表1中两个算法之间最小CPU 时间。例如，第一类的问题（N = 10，M = 5）的共同CPU 时间为是（1.05，1.83）的最小值1.05。 作者进行了假设检验，种群差异性平均值为零;具体地，进行原假设检验和备择假设检验。假定完工时间的偏差是正常的变量，显着性水平为a = 0.05. 如果假设是正确的，则随机 偏差为服从T=(X 1????X 2???)√S 1 1? S 2 2??分布，自由度是V=(S 12 1? S 22 2?)2( n ? n ?1 n ? n ?1?) (Mirabi 2010) ，临界值c 例如在表一中N1=N2=10，U0 = 0,.HGA 和H3的平均值分别为759.38和766.46，平均方差则分别为2.88和2.55。由于t=1.73﹤T=5.81我们可以断定他们之间纯在显著性差异。通过表2可以发现HGA 在一类问题上比H3表现的要好。 结论 在本文中，我们研究了在序列依赖性条件下的置换流水作业调度问题，挑战显示世界中按订单生产的完工时间策略。FSP是一个难优化问题，我们制订一个基于遗传算法的元启发式的方法称为HGA来解决这个问题。具有改进启发式杂交的遗传算法称为迭代交换过程（ISP）。除ISP之外，它杂交了启发式方法来构建初始解区域。此外，我们用三个遗传算子作来产生优良后代。计算结果表明，与最近开发的强大算法相比。值得注意的是，我们发现HGA和这些方法之间存在α= 0.05的显著性水平。 开放存取 本文是根据创造性的共用许可证来分配：，允许任何用途，分配，在任何介质中的复制。提供了原始作者和来源。。 参考 Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187:985–1032 Campbell HG, Dudek RA, Smith ML (1970) A heuristic algorithm for the n job, m machine sequencing problem. Manage Sci 16:B630– B637 Chaari T, Chaabane S, Loukil T, Loukil D (2011) A genetic algorithm for robust hybrid flow shop scheduling. Int J Comput Integr Manuf 24:821–833 Garey MR, Johnson DS, Sethi R (1976) The complexity of flow-shop and job-shop scheduling. Math Oper Res 1:117–129 Gen M, Cheng R (1997) Genetic algorithms and engineering design. Wiley, New York Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, New York Gupta JND, Darrow WP (1986) The two-machine sequence dependent flow-shop scheduling problem. Eur J Oper Res 24:439–446 Ho W, Ji P (2003) Component scheduling for chip shooter machines: a hybrid genetic algorithm approach. Comput Oper Res 30:2175–2189 Ho W, Ji P (2004) A hybrid genetic algorithm for component sequencing and feeder arrangement. J Intell Manuf 15:307–315 Huang K (2010) Hybrid genetic algorithms for flow-shop scheduling with synchronous material movement. Computer and industrial engineering (CIE), 40th international conference, pp 1–6 Jarboui B, Edadly M, Siarry P (2011) A hybrid genetic algorithm for solving no-wait flow-shop scheduling problems. Int J Adv Manuf Technol 54:1129–1143 Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Log Q 1:61–68 Laha D, Chakraborty UK (2007) An efficient stochastic hybrid heuristic for flow-shop scheduling. Eng Appl Artif Intell 20:851–856 Li X, Wang Y, Wu C (2004) Heuristic algorithms for large flow-shop scheduling problems. Intell Control Autom 4:2999–3003 Maleki-Darounkolaei A, Modiri M, Tavakkoli-Moghaddam R, Seyyedi I (2012) A three-stage assembly flow shop scheduling problem with blocking and sequence dependent set up times. J Ind Eng Int 8:26. https://www.doczj.com/doc/1f5897691.html,/content/8/1/26 Mirabi M (2010) A hybrid simulated annealing for the single machine capacitated lot-sizing and scheduling problem with sequencedependent setup times and costs and dynamic release of jobs. Int J Adv Manuf Technol. doi:10.1007/s00170-010-2988-5 Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the mmachine, n-job flow-shop sequencing problem. OMEGA Int J Manage Sci 11:91–95 Noori-Darvish S, Tavakkoli-Moghaddam R (2012) Minimizing the total tardiness and make span in an open shop scheduling problem with sequence-dependent setup times. J Ind Eng Int 8:25. https://www.doczj.com/doc/1f5897691.html,/content/8/1/25 Reeves CR (1995) A genetic algorithm for flow-shop sequencing. Comput Oper Res 22:5–13 Ruiz R, Stutzle T (2008) An iterated greedy heuristic for the sequence dependent setup times flow-shop with make-span and weighted tardiness objectives. Eur J Oper Res 87:1143–1159 Ruiz R, Maroto C, Alcaraz J (2005) Solving the flow-shop scheduling problem with sequence dependent setup times using advanced meta-heuristics. Eur J Oper Res 165:34–54 Sheibani K (2010) A fuzzy greedy heuristic for permutation flowshop scheduling. J Oper Res Soc 61:813–818 Sun JU, Hwang H (2001) Scheduling problem in a two machine flow line with the N-step prior-job-dependent set-up times. Int J Syst Sci 32:375–385 Tseng L, Lin Y (2010) A hybrid genetic algorithm for no-wait flowshop scheduling problem. Int J Prod Econ 128:144–152 Tseng FT, Gupta JND, Stafford EF (2005) A penalty-based heuristic algorithm for the permutation flow-shop scheduling problem with sequence-dependent set-up times. J Oper Res Soc 57:541–551 J Ind Eng Int (2014) 10:57 Page 9 of 9 57 123 第四章遗传算法与函数优化 4.1 研究函数优化的必要性： 首先，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于问题种类的繁多，影响因素的复杂，这些数学函数会呈现出不同的数学特征。除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况下需要通过数值计算的方法来进行近似优化计算。 其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为现实问题种类繁多，影响因素复杂，若对各种情况都加以考虑进行试算，其计算工作量势必太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识，它们便于不同应用领域中的研究人员能够进行相互理解和相互交流，并且能够较好地反映算法本身所具有的本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数，通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。 4.2 评价遗传算法性能的常用测试函数 在设计用于评价遗传算法性能的测试函数时，必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性，以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括： ●连续函数或离散函数； ●凹函数或凸函数； ●二次函数或非二次函数； ●低维函数或高维函数； ●确定性函数或随机性函数； ●单峰值函数或多峰值函数，等等。 下面是一些在评价遗传算法性能时经常用到的测试函数： (1)De Jong函数F1： 这是一个简单的平方和函数，只有一个极小点f1(0, 0, 0)＝0。 (2)De Jong 函数F2： 这是一个二维函数，它具有一个全局极小点f 2(1，1) = 0。该函数虽然是单峰值的函数，但它却是病态的，难以进行全局极小化。 (3)De Jong 函数F3： 这是一个不连续函数，对于]0.5,12.5[--∈i x 区域内的每一个点，它都取全局极小值 30),,,,(543213-=x x x x x f 。 遗传算法属于进化算法( Evolutionary Algorithms) 的一种, 它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子: 选择、交叉和变异. 。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现"死循环"现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。 生物在漫长的进化过程中，从低等生物一直发展到高等生物，可以说是一个绝妙的优化过程。这是自然环境选择的结果。人们研究生物进化现象，总结出进化过程包括复制、杂交、变异、竞争和选择。一些学者从生物遗传、进化的过程得到启发，提出了遗传算法( GA)。算法中称遗传的生物体为个体( individual )，个体对环境的适应程度用适应值( fitness )表示。适应值取决于个体的染色体(chromosome),在算法中染色体常用一串数字表示，数字串中的一位对应一个基因 (gene)。一定数量的个体组成一个群体(population )。对所有个体进 行选择、交叉和变异等操作,生成新的群体,称为新一代( new generation )。遗传算法计算程序的流程可以表示如下［3］：第一步准备工作 (i)选择合适的编码方案，将变量(特征)转换为染色体(数字串，串长为m。通常用二 进制编码。 (2 )选择合适的参数，包括群体大小(个体数M)、交叉概率PC和变异概率Pm (3、确定适应值函数f (x、。f (x、应为正值。 第二步形成一个初始群体(含M个个体)。在边坡滑裂面搜索问题中，取已分析的可能滑裂 面组作为初始群体。 第三步对每一染色体(串)计算其适应值fi ,同时计算群体的总适应值。 第四步选择 计算每一串的选择概率Pi=fi/F 及累计概率。选择一般通过模拟旋转滚花轮 ( roulette ,其上按Pi大小分成大小不等的扇形区、的算法进行。旋转M次即可选出M个串来。在计算机 上实现的步骤是：产生［0,1］间随机数r，若r 第三章 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland 的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。 3.1 模式定理 不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。 定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。 以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。 引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n 个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容 定义3.2 模式H 中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。 显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 定义3.3 模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H δ。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。 模式的阶数和定义距描述了模式的基本性质。 下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令)(t A 表示第t 代中串的群体，以),,2,1)((n j t A j =表示第t 代中第j 个个体串。 1．选择算子 在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下： 设在第t 代种群)(t A 中模式所能匹配的样本数为m ，记为),(t H m 。在选择中，一个位串 j A 以概率/j j i P f f =∑被选中并进行复制，其中j f 是个体)(t A j 的适应度。假设一代中群体 大小为n ，且个体两两互不相同，则模式H 在第1+t 代中的样本数为： GATBX遗传算法工具箱函数及实例讲解 基本原理： 遗传算法是一种典型的启发式算法，属于非数值算法范畴。它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它是采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串（称为染色体、个体），即种群，每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应度函数的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化进行不断演化，直到满足期望的终止条件。 运算流程： Step 1：对遗传算法的运行参数进行赋值。参数包括种群规模、变量个数、交叉概率、变异概 率以及遗传运算的终止进化代数。 Step 2：建立区域描述器。根据轨道交通与常规公交运营协调模型的求解变量的约束条件，设置变量的取值范围。 Step 3：在Step 2的变量取值范围内，随机产生初始群体，代入适应度函数计算其适应度值。 Step 4：执行比例选择算子进行选择操作。 Step 5：按交叉概率对交叉算子执行交叉操作。 Step 6：按变异概率执行离散变异操作。 Step 7：计算Step 6得到局部最优解中每个个体的适应值，并执行最优个体保存策略。 Step 8：判断是否满足遗传运算的终止进化代数，不满足则返回Step 4，满足则输出运算结果。 运用遗传算法工具箱: 运用基于Matlab的遗传算法工具箱非常方便，遗传算法工具箱里包括了我们需要的各种函数库。目前，基于Matlab的遗传算法工具箱也很多，比较流行的有英国设菲尔德大学开发的遗传算法工具箱GATBX、GAOT以及Math Works公司推出的GADS。实际上，GADS就是大家所看到的Matlab中自带的工具箱。我在网上看到有问为什么遗传算法函数不能调用的问题，其实，主要就是因为用的工具箱不同。因为，有些人用的是GATBX带有的函数，但MATLAB自带的遗传算法工具箱是GADS，GADS当然没有GATBX里的函数，因此运行程序时会报错，当你用MATLAB来编写遗传算法代码时，要根据你所安装的工具箱来编写代码。 以GATBX为例，运用GATBX时，要将GATBX解压到Matlab下的toolbox文件夹里，同时，set path将GATBX文件夹加入到路径当中。 这块内容主要包括两方面工作：1、将模型用程序写出来（.M文件），即目标函数，若目标函数非负，即可直接将目标函数作为适应度函数。2、设置遗传算法的运行参数。包括：种群规模、变量个数、区域描述器、交叉概率、变异概率以及遗传运算的终止进化代数等等。 基于新的混合遗传算法的订单生产工序顺序相关的流水车 间调度问题研究 A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem Mohammad Mirabi ?S. M. T. Fatemi Ghomi ?F. Jolai 2013年5月29号收到该文献,2014年3月18号录取,2014年4月9日出版.作者（2014）.这篇文章在开放存取的https://www.doczj.com/doc/1f5897691.html, 网站发表 摘要流水车间调度问题（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 University of Meybod, P.O. Box 89619-55133, Meybod, Iran e-mail: M.Mirabi@https://www.doczj.com/doc/1f5897691.html, S. M. T. Fatemi Ghomi Department of Industrial Engineering, Amirkabir University of Technology, P.O. Box 15916-34311, Tehran, Iran e-mail: Fatemi@aut.ac.ir F. Jolai Department of Industrial Engineering, College of Engineering, University of Tehran, P.O. Box 14395-515, Tehran, Iran 第32卷 第12期2009年12月 计 算 机 学 报 CH INESE JOURNA L OF COMPU TERS Vol.32No.12 Dec.2009 收稿日期:2008210219;最终修改稿收到日期:2009209227.本课题得到国家自然科学基金(60774084)资助.岳 嵚,男,1977年生,博士研究生,主要研究方向为进化算法.E 2mail:yueqqin@si https://www.doczj.com/doc/1f5897691.html,.冯 珊,女,1933年生,教授,博士生导师,主要研究领域为智能决策支持系统. 遗传算法的计算性能的统计分析 岳 嵚 冯 珊 (华中科技大学控制科学与工程系 武汉 430074) 摘 要 通过对多维解析函数的多次重复计算并对计算结果进行统计分析来讨论遗传算法的可靠性和可信度,结果表明:遗传算法的计算结果具有一定的稳定性,可以通过采用多次重复计算的方法提高计算结果的可信度,并用以评价算法及其改进的实际效果.关键词 遗传算法;计算可靠性;置信区间 中图法分类号TP 18 DOI 号:10.3724/SP.J.1016.2009.02389 The Statistical Analyses for Computational Performance of the Genetic Algorithms YU E Qin FENG Shan (Dep artment of Contr ol Science and Eng ineering ,H uazhong University of Science and T ech nology ,W u han 430074) Abstr act In this paper,the author s discuss the reliability of the GAs by reiteratively computing the multi 2dimensional analytic functions and statistical analysis of the results.The analysis re 2sults show that the GAs have certain stability;it could improve the reliability by reiteratively computation and estimates the effects of improvements. Keywor ds genetic algorithms;computational stability;confidence interval 1 遗传算法的随机性 遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物,是一种随机性的全局优化算法[1].遗传算法作为一种启发式搜索算法,其计算结果具有不稳定性和不可重现性;遗传算法的进化过程具有有向随机性,整体上使种群的平均适应度不断提高.现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚,遗传算法的许多性能特点无法在数学上严格证明.遗传算法的计算过程会受到各种随机因素的影响,如随机产生的初始种群和随机进行的变异操作等,尤其初始种群对计算结果影响较大.但另一方面,大量的实算结果表明,遗传算法的计算结果具有一定的规律性,在统计意义上具有一定的可靠性,这样就可以对待求解问题 进行多次重复计算后取平均值的方法,提高遗传算 法在实际计算中的准确性和可信度. 包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题,这些问题一般难以使用传统的优化算法解决.遗传算法对这类问题的计算结果也难达到精确的最优解.这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难,在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣. 为了分析遗传算法的计算性能,本文采用的计算对象是一个复杂的多维解析函数.使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解,这样便于评价遗传算法及其改进型的计算效果.本文从统计学角度对多次重复计算的结果进行分析,试图得到遗传算法的稳定性和可信度方面的相关结论,通过分析遗传算法及其改进 遗传算法遗传算法的计算性能的统计分析 岳嵚冯珊 （华中科技大学控制科学与工程系） 摘要：本文通过对多维解析函数的多次重复计算并对计算结果的进行统计分析来讨论遗传算法的可靠性和可信度，结果表明：遗传算法的计算结果具有一定的稳定性，可以通过采用多次重复计算的方法提高计算结果的可信度，并用以评价算法及其改进的实际效果。 关键词：遗传算法；计算可靠性；置信区间 分类号：TP18 1遗传算法的随机性 遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物，是一种随机性的全局优化算法[1]。遗传算法作为一种启发式搜索算法，其计算结果具有不稳定性和不可重现性；遗传算法的进化过程具有有向随机性，整体上使种群的平均适应度不断提高。现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚，遗传算法的许多性能特点无法在数学上严格证明。遗传算法的计算过程会受到各种随机因素的影响，如随机产生的初始种群和随机进行的变异操作等，尤其初是始种群对计算结果影响较大。但另一方面，大量的实算结果表明，遗传算法的计算结果具有一定的规律性，在统计意义上具有一定的可靠性，这样就可以对待求解问题进行多次重复计算后取平均值的方法，提高遗传算法在实际计算中的准确性和可信度。 包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题，这些问题一般难以使用传统的优化算法解决。遗传算法对这类问题的计算结果也难达到精确的最优解。这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难，在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣。 为了分析遗传算法的计算性能，本文采用的计算对象是一个复杂的多维解析函数。使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解，这样便于评价遗传算法及其改进型的计算效果。本文从统计学角度对多次重复计算的结果进行分析，试图得到遗传算法的稳定性和可信度方面的相关结论，通过分析遗传算法及其改进型求解解析问题的计算效果，再把所得到的相关结论推广应用到复杂的工程实际问题中去。 遗传算法在实际使用中有多种形式的变型，经典遗传算法是遗传算法的最简单的形式，但是经典遗传算法并不理想。本文使用的是粗粒度并行遗传算法。粗粒度并行遗传算法是遗传算法的一个重要改进型。它具有比经典遗传算法更好的计算性能。 2算例、实验方法和实验结果 2.1算例 本文所使用的算例是Deb 函数： ]10,10[,)]4cos(10[10)(12?∈??+=∑=i n i i i Deb x n x x x f i π（1） Deb 函数是一个高维的非凸函数，该函数在点（9.7624，9.7624，…，9.7624）上取得最大 目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19) 遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的 30维线性方程求解 摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。 关键词：非线性方程组；混合遗传算法；优化 1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是 随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。 2. 遗传算法解非线性方程组为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象问题描述：非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组 中含有非线性方程。其求解是指在其定义域内找出一组数能满足方程组中的每 个方程。这里，我们将方程组转化为一个函数则求解方程组就转化为求一组值使得成立。即求使函数取得最小值0 的一组数，于是方程组求解问题就转变为函数优化问题 3. 遗传算子 遗传算子设计包括交叉算子、变异算子和选择算子的设计。 摘要：基本遗传算法的操作是以个体为对象，只使用选择、交叉和变异遗传算子，遗传进化操作过程的简单框架。模式定理和积木块假设是解释遗传算法有效性的理论基础，理论分析与实际应用都表明基本的遗传算法不能处处收敛于全局最优解，因此基本遗传算法有待进一步改进。 关键词：遗传算法；遗传算法的改进 1.标准遗传算法 基本遗传算法包括选择、交叉和变异这些基本遗传算子。其数学模型可表示为： sag=（c，e，p0，n，φ，г，ψ，t） 其中c为个体的编码方法；e为个体适应度评价函数；p0为初始种群；n为种群大小；φ为选择算子；г为交叉算子；ψ为变异算子；t为遗传运算终止条件； 2 遗传算法基本方法及其改进 2.1编码方式 编码方式决定了个体的染色体排列形式，其好坏直接影响遗传算法中的选择算子、交叉算子和变异算子的运算，也决定了解码方式。 二进制编码 二进制编码使用的字符号{0，1}作为编码符号，即用一个{0，1}所组成的二进制符号串构成的个体基因型。二进制编码方法应用于遗传算法中有如下优点： 1）遗传算法中的遗传操作如交叉、变异很容易实现，且容易用生物遗传理论来解释； 2）算法可处理的模式多，增强了全局搜索能力； 3）便于编码、解码操作； 4）符合最小字符集编码原则； 5）并行处理能力较强。 二进制编码在存着连续函数离散化的映射误差，不能直接反应出所求问题的本身结构特征，不便于开发专门针对某类问题的遗传运算算子。 2.2初始种群的设定 基本遗传算法是按随机方法在可能解空间内产生一个一定规模的初始群体，然后从这个初始群体开始遗传操作，搜索最优解。初始种群的设定一般服从下列准则：1）根据优化问题，把握最优解所占空间在整个问题空间的分布范围，然后，在此分布范围内设定合适的初始群体。 2）先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。该过程不断迭代，直到初始群体中个体数目达到了预先确定的种群大小。 2.3选择算子的分析 选择算子的作用是选择优良基因参与遗传运算，目的是防止有用的遗传信息丢失，从而提高全局收敛效率。常用的遗传算子： （1）轮盘赌选择机制 轮盘赌选择也称适应度比例选择，是遗传算法中最基本的选择机制，每个个体被选择进入下一代的概率为这个个体的适应度值占全部个体适应度值之和的比例。但是轮盘赌选择机制选择误差较大，不是所有高适应度值的个体都能被选中，适应度值较低但具有优良基因模式的个体被选择的概率也很低，这样就会导致早熟现象的产生。 （2）最优保存选择机制 最优保存选择机制的基本思想是直接把群体中适应度最高的个体复制到下一代，而不进行配对交叉等遗传操作。具体步骤如下： 1）找出当前群体中适应度值最高和最低的个体的集合； 第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。 7.1 简单一元函数优化实例 利用遗传算法计算下面函数的最大值： ()sin(10) 2.0[1,2]f x x x x π=?+∈-， 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。 下面为一元函数优化问题的MA TLAB 代码。 figure(1); fplot ('variable.*sin(10*pi*variable)+2.0',[-1,2]); %画出函数曲线 % 定义遗传算法参数 NIND= 40; % 个体数目(Number of individuals) MAXGEN = 25; % 最大遗传代数(Maximum number of generations) PRECI = 20; % 变量的二进制位数(Precision of variables) GGAP = 0.9; % 代沟(Generation gap) trace=zeros (2, MAXGEN); % 寻优结果的初始值 FieldD = [20;-1;2;1;0;1;1]; % 区域描述器(Build field descriptor) Chrom = crtbp(NIND, PRECI); % 初始种群 gen = 0; % 代计数器 variable=bs2rv(Chrom,FieldD); % 计算初始种群的十进制转换 ObjV = variable.*sin (10*pi*variable)+2.0; % 计算目标函数值 while gen < MAXGEN, FitnV = ranking (-ObjV); % 分配适应度值(Assign fitness values) SelCh = select ('sus', Chrom, FitnV , GGAP); % 选择 SelCh = recombin ('xovsp',SelCh,0.7); % 重组 SelCh = mut(SelCh); % 变异 variable=bs2rv(SelCh,FieldD); % 子代个体的十进制转换 ObjVSel =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值 [Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加 % 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号 [Y,I]=max(ObjV),hold on; plot (variable (I),Y , 'bo'); trace (1,gen)=max (ObjV); %遗传算法性能跟踪 遗传算法入门到掌握 读完这个讲义，你将基本掌握遗传算法，要有耐心看完。 想了很久，应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢？遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（这是一个国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心。），TSP问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。这一章将告诉读者，我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： 图2-1 现在要求在既定的区间内找出函数的最大值。函数图像如图2-1所示。 极大值、最大值、局部最优解、全局最优解 在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图2.1里面的表现就是一个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。） 2. 模拟退火： 这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变 基于数据挖掘的遗传算法 xxx 摘要:本文定义了遗传算法概念和理论的来源，介绍遗传算法的研究方向和应用领域，解释了遗传算法的相关概念、编码规则、三个主要算子和适应度函数，描述遗传算法计算过程和参数的选择的准则，并且在给出的遗传算法的基础上结合实际应用加以说明。 关键词：数据挖掘遗传算法 Genetic Algorithm Based on Data Mining xxx Abstract：This paper defines the concepts and theories of genetic algorithm source, Introducing genetic algorithm research directions and application areas, explaining the concepts of genetic algorithms, coding rules, the three main operator and fitness function，describing genetic algorithm parameter selection process and criteria，in addition in the given combination of genetic algorithm based on the practical application. Key words: Data Mining genetic algorithm 前言 遗传算法(genetic algorithm，GAs)试图计算模仿自然选择的过程，并将它们运用于解决商业和研究问题。遗传算法于20世界六七十年代由John Holland[1]发展而成。它提供了一个用于研究一些生物因素相互作用的框架，如配偶的选择、繁殖、物种突变和遗传信息的交叉。在自然界中，特定环境限制和压力迫使不同物种竞争以产生最适应于生存的后代。在遗传算法的世界里，会比较各种候选解的适合度，最适合的解被进一步改进以产生更加优化的解。 遗传算法借助了大量的基因术语。遗传算法的基本思想基于达尔文的进化论和孟德尔的遗传学说，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。生物在自然界的生存繁殖，显示对其自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机制研究和行为模拟。通过仿效生物的进化与遗传，根据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉、变异等操作，使所要解决的问题从随机初始解一步步逼近最优解。现在已经广泛的应用于计算机科学、人工智能、信息技术及工程实践。[2]在工业、经济管理、交通运输、工业设计等不同领域，成功解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法作为一类自组织于自适应的人工智能技术，尤其适用于处理传统搜索方法难以解决的复杂的和非线性的问题。 1.遗传算法的应用领域和研 究方向 1.1遗传算法的特点 遗传算法作为一种新型、模拟生物进化过程的随机化搜索方法，在各类结 构对象的优化过程中显示出比传统优 化方法更为独特的优势和良好的性能。 它利用其生物进化和遗传的思想，所以 它有许多传统算法不具有的特点[3]： ※搜索过程不直接作用在变量上，而是 作用于由参数集进行了编码的个体 上。此编码操作使遗传算法可以直接 对结构对象进行操作。 ※搜索过程是从一组解迭代到另一组 解，采用同时处理群体中多个个体的 方法，降低了陷入局部最优解的可能 性，易于并行化。 模拟退火算法与遗传算法性能比较 摘要：模拟退火算法与遗传算法是两种非常重要的多目标优化算法。其原理简单，对优化目标函数解析性没有要求，因此在工程问题中被广泛应用。本文介绍了这两种优化算法的原理，并分析了两种算法的性能并讨论了应用过程中的关键问题，对两种算法的合理选取及改进具有参考价值。 关键字：模拟退火，遗传算法，优化 1.前言 对于多目标优化问题，传统的做法是全局搜索，即“穷举法”。这种通过搜索整个解空间的方法虽然能获得全局最优解，但运算量非常大，当优化空间的维度非常高时，该方法在计算上不可行。通过利用目标函数的解析性质以及借助实际问题的约束条件能部分降低搜索空间，但任不能解决高维问题优化。面对复杂问题，求得最优解是很困难的，在有限时间内求得满意解是可能的。获取高维优化问题满意解的常用方法是迭代运算，但通常迭代运算容易陷入局部最优陷阱，造成“死循环”。模拟退火算法及遗传算法是两种原理简单的启发式智能搜索算法，均具有逃离局部陷阱的能力，是工程应用中快速获取满意解的常用算法，对其性能比较对于正确使用这两种智能优化算法具有重要意义。 2.算法介绍 2.1.模拟退火算法 模拟退火算法是一种随机搜索算法，Kirkpatrick[1]于1983年首次将该算法应用于多目标优化。该算法模拟冶金上的退火过程而得名，其基本思想是：对当前合理解增加扰动产生新解，评价新解对目标函数的改进情况，若小于零，则接受新解为新的当前解，否则以概率接受新解为新的当前解。新的当前解将将继续优化，直到没有显著改进为止。 模拟退火算法使用过程中以下细节影响其全局搜索性能。初始温度T选择越高，则搜索到全局最优解的可能性也越大，但计算复杂度也显著增大。反之，能节省时间，但易于陷入局部最优。依据解的质量变化概率选择温度下降策略能增强算法性能。每次温度降低迭代次数及算法的终止可由给定迭代次数内获得更优解的概率而确定。 2.1.遗传算法 遗传算法最早由Holland等[2]提出，该算法模拟遗传变异与自然选择机制，是一种通过交换机制，重组基因串的概率搜索算法，其基本思想是：分析解空间大小及精度要求，确定合理解唯一编码形式。合理解转化成的编码即为染色体，随机选取的多个初始染色体构成初始种群。会依据评价函数计算种群中每个个体 遗传算法及其应用 摘要：遗传算法是一种基于生物自然选择和遗传机理的随机搜索与优化方法。近年来,由于遗传算法在求解复杂问题中的巨大潜力及其在工业工程领域的成功应用,受到了国内外学者的广泛关注。本文详细介绍了遗传算法的基本原理、主要特征以及主要应用。 关键词：遗传算法；选择算子；交叉算子；变异算子 Genetic Algorithm and Its Application Abstract: Genetic algorithm is a random search and optimization method based on biological natural selection and genetic mechanism. In recent years,genetic algorithm has attracted many domestic and overseas scholars' attention for its potential in solving many complex problems and its successful application in the field of industrial engineering, This paper introduces the basic principle ,the main characteristics and applications of genetic algorithm in detail. Key words: genetic algorithm, selection operator, crossover operator, mutation operator 1.遗传算法发展历史 1967年，Holland的学生Bagley在其博士论文中首次提出“遗传算法”[1]。1970年，Cavicchio把遗传算法应用于模式识别[2]。Hollstien最早把遗传算法应用于函数优化[3]。20世纪70年代，Holland教授提出了遗传算法的基本定理—模式定理[4]，从而奠定了遗传算法的理论基础。1975年，Holland教授出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and Artificial Systems》。同年，K.A.De Song在博士论文《遗传自适应系统的行为分析》结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，为遗传算法及其应用打下了坚实的基础，他所得出的许多结论迄今仍具有普遍的指导意义。 2.遗传算法理论 2.1遗传算法的基本思想 遗传算法借鉴Darwin 的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理。与传统搜索算法不同，遗传算法从一组随机产生的初始解（称为群体）开始。群体中的每个个体是问题的一个解，称为“染色体”，这些染色体在后代迭代过程中不断进化。遗传算法主要通过选择、交叉和变异来实现,其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。 遗传算法是一个迭代的过程，在每次迭代过程中都保留一组候选解，按解的好坏进行排序，按照约束条件从中选取一组解，利用遗传算法中的三个算子对其进行计算，产生新一代的候选解，重复此过程直到满足某种收敛条件为止。 2.2遗传算法的数学基础 定义1：模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集（0,1，*）的字符串，符号*代表（0,1）中的任意字符。例如：10**1 定义2：模式H中确定位置的个数称为模式H的阶，记O(H)。例如O(10**1)=3。 定义3：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作δ(H)。例如δ(10**1)=4。 模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的4遗传算法与函数优化
遗传算法的优缺点
第三章-遗传算法的理论基础
遗 传 算 法 详 解 ( 含 M A T L A B 代 码 )
遗传算法
遗传算法的计算性能的统计分析
遗传算法的计算性能的统计分析
遗传算法基本理论实例
人工智能之遗传算法论文含源代码
遗传算法基本理论与方法
第七章遗传算法应用举例
遗传算法——耐心看完,你就掌握了遗传算法
基于数据挖掘的遗传算法
模拟退火算法与遗传算法性能比较
GA遗传算法概述
相关主题
文本预览