指派问题的启发式算法研究

中国矿业大学2012届本科生毕业设计（论文）中国矿业大学本科生毕业设计姓名学号学院计算机科学与技术学院专业设计题目指派问题的启发式算法研究指导教师职称2012年6月中国矿业大学2012届本科生毕业设计（论文）中文摘要本文对指派问题设计了一个新的混合单亲遗传算法。首先，设计了一个新的编码方法,并且对这种编码方法，给出了简便的解码方法。其次，设计了一种新的、有效的基因换位算子。同时，为提高该算子的搜索能力，结合一个局部搜索技术来改进该算子。再次，在此基础上，提出了解指派问题的一个新的混合单亲遗传算法。最后进行了计算机仿真，结果表明算法是有效的。关键词遗传算法指派问题组合优化局部搜索ABSTRACTANOVELHYBRIDPARTHENOGENETICAPPROACHFORASSIGNMENTPROBLEMSAPFORSHORTISPROPOSEDINTHISPAPERFIRST,ANEWENCODINGSCHEMEANDANEWDECODINGSCHEMEAREDESIGNEDSECOND,ANEFFICIENTGENEEXCHANGEOPERATORISGIVENINORDERTOENHANCEITSABILITYOFEXPLORATION,ALOCALSEARCHSCHEMEISINTEGRATEDINTOTHEOPERATORBASEDONTHESE,ANOVELANDEFFECTIVEPARTHENOGENETICALGORITHMFORAPISPRESENTEDFINALLY,THESIMULATIONISMADEANDTHERESULTSSHOWTHEEFFECTIVENESSOFTHEPROPOSEDALGORITHMKEYWORDSGENETICALGORITHM；ASSIGNMENTPROBLEMS；COMBINATORIALOPTIMIZATION；LOCALSEARCH中国矿业大学2012届本科生毕业设计（论文）目录一、引言111、指派问题、启发式算法112、遗传算法2122、单亲遗传算法的特点13123、单亲遗传算法理论研究现状14124、单亲遗传算法的应用研究现状16125、单亲遗传算法的展望17二、混合单亲遗传算法1721、算法模型简介1722、新的遗传算法18221、新的编码方法18222、基因换位算子、局部搜索19223、新的遗传算法2123、计算机仿真2224、结束语22主要参考文献24外文论文25中文译文34致谢43中国矿业大学2012届本科生毕业设计（论文）第1页一、引言11、指派问题、启发式算法在日常生活中经常会遇到这样的问题某单位需要完成N项任务，恰好M个人可以承担这些任务。由于每个人的专长不同，各人完成不同任务的效率也就不同，于是产生了应该指派哪个人去完成哪项任务，能够使得完成N项任务的总收益最大（或者总费用最小）的问题。这类问题成为指派问题或者分配问题。指派问题（ASSIGNMENTPROBLEMS,简记为AP）是十分重要的组合优化问题，在经济管理、计算机科学、运筹学及工程等领域都有着广泛的应用。由于AP是NP困难的，因此从理论的角度看，是不可能设计出理想的（多项式时间的）能求出精确最优解的算法。求解AP精确解的方法，如分枝切割法（BRANCHANDCUTMETHOD，），其计算量十分巨大，对较大规模的问题难以应用。目前，启发式算法已被证明是一类用较少计算量可求出较好质量近似解的一类有效方法。为了提高启发式方法的效率，许多研究者将局部优化方法结合进这些方法中，如1混合进化算法，从而大大地提高了进化算法的搜索能力，有助于更快找到全局最优解，是一类很有潜力的算法。本文提出了用混合单亲遗传算法求解AP的一种新算法，设计了链式的基因换位算子，将LK算法推广应用到AP。数值实验表明了该算法的有效性。比较常用的求解指派问题的算法有匈牙利算法、拍卖算法、MUNKRE算法、次序搜索算法、MBEST算法等，但上述算法在不同程度上存在某些不足。如以次序搜索算法、MBEST算法为代表的启发式算法存在着难以求得精确解的问题；以匈牙利算法、拍卖算法、MUNKRE算法为代表的最优算法虽然可以求得精确的全局最优解，但是存在着实现难、处理速度慢等不足，难以满足工程实时应用的需要。因此实际生活中，需要一种既有较高求解精度、又能满足一定效率要求有效求解算法。经典算法包括线性规划和非线性规划的传统算法、动态规划的传统算法、整数规划的传统算法和分枝定界等算法。它们或者对目标函数的解析性质要求较高，或者计算复杂性很大，只适应于求解小规模的简单问题，很难适用于工程中出现的大规模问题。启发式算法随着20世纪80年代初禁忌算法，模拟退火法SIMULATEDANNEALING、遗传算法和人工神经网络等算法的兴起，非线性规划问题又增添了一些新的解决方案。这些算法涉及生物进化、人工智能、数学和物理学、神经系统和统计力学等概念，都是以一定的直观基础而构造的算法，我们称之为启发式算法HEURISTICALGORITHM。启发式算法是相对于最优算法提出的，一个问题的最优算法求得该问题每个中国矿业大学2012届本科生毕业设计（论文）第2页实例的最优解，而启发式算法则可以认为是一种基于直观或经验构造的算法，在可以接受的花费指计算时间、占用空间等下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏移程度不一定事先可以预计。在大部分的图着色问题中，最优化算法的计算时间是无法忍受的，而且要想保证一定能找到最优解，我们很有可能要用启发式算法。启发式算法可以在我们能接受的花费下找到一个近似解。从工程实际的角度来看，在一定误差范围内的近似解都是可以接受的。而且由于数学模型本身就是实际问题的简化，或多或少地会忽略一些因素，再加上数据采集的不准确性，参数估计的不准确性可能使最优算法所得的解比启发式算法产生的解产生更大的误差。由于启发式算法速度快，直观简单易行等特点，得到了很快的发展。但是他也有自己的缺点首先，启发式算法不能保证得到最优解；其次，算法表现不稳定，对于同一问题每次得到的结果可能不相同，在实际运用中就造成计算结果不可靠。再就是启发式算法的好坏依赖于实际问题和设计者的经验，这使得不同算法之间难以比较。尽管存在这些问题，启发式算法还是取得了很大的进展。12、遗传算法生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。遗传算法的概念最早是由BAGLEYJD在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由MICHIGAN大学的JHHOLLAND所实行。当时，其主要目的是说明自然和人工系统的自适应过程。遗传算法简称GAGENETICALGORITHM，在本质上是一种不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。GA的起源及发展1950年，图灵提出可以通过模拟进化和自然选择过程自动生成智能程序。19601970，基于进化和自然选择思想的各种算法的提出和应用。1975年，HOLLAND发表ADAPTATIONINNATUREANDARTIFICIALSYSTEMS（自然界和人工系统的适应性），完整描述了GA的原理及实现步骤。1975年，DEJONG提出了5个评价GA效率的测试函数。1987年，GOLDBERG发表GENETICALGORITHMSINSEARCH，OPTIMIZATIONANDMACHINELEARNING,详细介绍了GA在工程上的应用。自从美国MICHIGAN大学HOLLAND教授等人于20世纪70年代提出遗传算法（GA）以来，即受到了广大研究工作者的关注。GOLDBERG等人对遗传算法的发中国矿业大学2012届本科生毕业设计（论文）第3页展作出了重要的贡献。进入20世纪90年代，国内外学者对遗传算法的理论和应用研究作了大量的工作，取得了辉煌的成就。HOLLAND教授提出的遗传算法后来被人们称为简单遗传算法或标准遗传算法（SIMPLEGENETICALGORITHMS，简称SGA）。简单遗传算法计算效率不高，且不是全局收敛的。为了提高遗传算法的计算效率，人们提出了各种各样的改进遗传算法。单亲遗传算法（PGA）就是近年来发展起来的一种改进遗传算法。遗传算法介绍一、遗传算法的基本概念遗传算法的基本思想是基于DARWIN进化论和MENDEL的遗传学说的。DARWIN进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。MENDEL遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下1、串STRING它是个体INDIVIDUAL的形式，在算法中为二进制串，并且对应于遗传学中的染色体CHROMOSOME。2、群体POPULATION个体的集合称为群体，串是群体的元素3、群体大小POPULATIONSIZE在群体中个体的数量称为群体的大小。4、基因GENE基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因ALLETES。5、基因位置GENEPOSITION一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点LOCUS。6、基因特征值GENEFEATURE在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。7、串结构空间SS中国矿业大学2012届本科生毕业设计（论文）第4页在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型GENOTYPE的集合。8、参数空间SP这是串空间在物理系统中的映射，它对应于遗传学中的表现型PHENOTYPE的集合。9、非线性它对应遗传学中的异位显性EPISTASIS10、适应度FITNESS表示某一个体对于环境的适应程度。遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。二、遗传算法的目的典型的遗传算法CGACANONICALGENETICALGORITHM通常用于解决下面这一类的静态最优化问题考虑对于一群长度为L的二进制编码BI，I1，2，N；有BI0,1L384给定目标函数F，有FBI，并且同时FBIFBI1求满足下式MAXFBI|BI0,1L的BI。很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串BI处，即求出最优解。三、遗传算法的基本原理长度为L的N个二进制串BII1，2，N组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种1选择SELECTION这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生REPRODUCTION。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生DIFFERENTIALREPRODUCTION。常用的选择算子（1）、轮盘赌选择（ROULETTEWHEELSELECTION）是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。（2）、随机竞争选择（STOCHASTICTOURNAMENT）每次按轮盘赌选择一对个中国矿业大学2012届本科生毕业设计（论文）第5页体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。（3）、最佳保留选择首先按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。（4）、无回放随机选择（也叫期望值选择EXCEPTEDVALUESELECTION）根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下A、计算群体中每个个体在下一代群体中的生存期望数目N。B、若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去05，若某一个体未被选中参与交叉运算，则它在下一代中的生存期望数目减去10。C、随着选择过程的进行，若某一个体的生存期望数目小于0时，则该个体就不再有机会被选中。（5）、确定式选择按照一种确定的方式来进行选择操作。具体操作过程如下A、计算群体中各个个体在下一代群体中的期望生存数目N。B、用N的整数部分确定各个对应个体在下一代群体中的生存数目。C、用N的小数部分对个体进行降序排列，顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中个个体。（6）、无回放余数随机选择可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，因而选择误差比较小。（7）、均匀排序对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。（8）、最佳保存策略当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。（9）、随机联赛选择每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。（10）、排挤选择新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。2交叉CROSSOVER这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。适用于二进制编码个体或浮点数编码个体的交叉算子（1）、单点交叉（ONEPOINTCROSSOVER）指在个体编码串中只随机设置一个交叉点，然后再该点相互交换两个配对个体的部分染色体。（2）、两点交叉与多点交叉A、两点交叉（TWOPOINTCROSSOVER）在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。B、多点交叉（MULTIPOINTCROSSOVER）中国矿业大学2012届本科生毕业设计（论文）第6页（3）、均匀交叉（也称一致交叉，UNIFORMCROSSOVER）两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。4、算术交叉（ARITHMETICCROSSOVER）由两个个体的线性组合而产生出两个新的个体。该操作对象一般是由浮点数编码表示的个体。3变异MUTATION这是在选中的个体中，对个体中的某些基因执行异向转化。在串BI中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。遗传算法的原理可以简要给出如下CHOOSEANINTIALPOPULATIONDETERMINETHEFITNESSOFEACHINDIVIDUALPERFORMSELECTIONREPEATPERFORMCROSSOVERPERFORMMUTATIONDETERMINETHEFITNESSOFEACHINDIVIDUALPERFORMSELECTIONUNTILSOMESTOPPINGCRITERIONAPPLIES这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零。以下变异算子适用于二进制编码和浮点数编码的个体（1）、基本位变异（SIMPLEMUTATION）对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。（2）、均匀变异（UNIFORMMUTATION）分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）（3）、边界变异（BOUNDARYMUTATION）随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。（4）、非均匀变异对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。（5）、高斯近似变异进行变异操作时用符号均值为的平均值，方差为的正态分布的一个随机数来替换原有的基因值。四、遗传算法的步骤和意义1初始化选择一个群体，即选择一个串或个体的集合BI，I1，2，N。这个初始的群体也就是问题假设解的集合。一般取N30160。通常以随机方法产生串或个体的集合BI,I1，2，N。问题的最优解将中国矿业大学2012届本科生毕业设计（论文）第7页通过这些初始假设解进化而求出。2选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数F，则FBI称为个体BI的适应度。以为选中BI为下一代个体的次数。显然从式386可知1适应度较高的个体，繁殖下一代的数目较多。2适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。3交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体S1100101S2010111选择它们的左边3位进行交叉操作，则有S1010101S2100111一般而言，交婊显譖。取值为025075。4变异根据生物遗传中基因变异的原理，以变异概率PM对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率PM与生物变异极小的情况一致，所以，PM的取值较小，一般取00102。例如有个体S101011。对其的第1，4位置的基因进行变异，则有S001111单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。5全局最优收敛CONVERGENCETOTHEGLOBALOPTIMUM当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。下图中表示了遗传算法的执行过程。中国矿业大学2012届本科生毕业设计（论文）第8页6、适应度函数适应度函数也称评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准。适应度函数总是非负的，而目标函数可能有正有负，故需要在目标函数与适应度函数之间进行变换。评价个体适应度的一般过程为（1）、对个体编码串进行解码处理后，可得到个体的表现型。（2）、由个体的表现型可计算出对应个体的目标函数值。（3）、根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。适应度函数的设计主要应满足以下要求（1）、单值、连续、非负、最大化。2、合理、一致性。较难。3、计算量小。4、通用性强。由目标函数F（X）到适应度函数FIT（F（X）的转换方法有以下三种1、直接以待解的目标函数F（X）转换为适应度函数。FIT（F（X）F（X）目标函数为最大化问题FIT（F（X）F（X）目标函数为最小化问题问题可能不满足常用的轮盘赌选择中概率非负的要求；某携带求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能。2、做转换。3、同（2），转换公式不同。适应度尺度变换（FITNESSSCALINGTRANSFORM）在遗传算法的不同阶段，对中国矿业大学2012届本科生毕业设计（论文）第9页个体的适应度进行适当的扩大或缩小。常用的尺度变换方法如下A线性尺度变换FAFBB乘幂尺度变换FFC、指数尺度变换FEP（BEITAF）7、约束条件处理（1）、搜索空间限定法对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中的表示一个可行解的点有一一对应关系。（2）、可行解变换法在由个体基因型向个体表现型的变换中，增加使其满足约束条件的处理过程，即寻找个体基因型与个体表现型的多对一变换关系，扩大了搜索空间，使进化过程中所产生的个体总能通过这个变换而转化成杰空间中满足约束条件的一个可行解。（3）、罚函数法对在解空间中无对应可行解的个体计算其适应度时，处以一个惩罚函数，从而降低该个体的适应度，使该个体被遗传到下一代群体中的概率减小。五、遗传算法的特点1遗传算法从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。2遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。3遗传算法有极强的容错能力遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。4遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。5遗传算法具有隐含的并行性遗传算法的基础理论是图式定理。它的有关内容如下1图式SCHEMA概念一个基因串用符号集0，1，表示，则称为一个因式；其中可以是0或1。例如H1XX0XX是一个图式。2图式的阶和长度图式中0和1的个数称为图式的阶，并用0H表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用H表示。对于图式H1XX0XX，中国矿业大学2012届本科生毕业设计（论文）第10页有0H2，H4。3HOLLAND图式定理低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为N时，每代处理的图式数目为0N3。遗传算法这种处理能力称为隐含并行性IMPLICITPARALLELISM。它说明遗传算法其内在具有并行处理的特质。六、遗传算法的应用关键遗传算法在应用中最关键的问题有如下3个1串的编码方式这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。2适应函数的确定适应函数FITNESSFUNCTION也称对象函数OBJECTFUNCTION，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。3遗传算法自身参数设定遗传算法自身参数有3个，即群体大小N、交叉概率PC和变异概率PM。群体大小N太小时难以求出最优解，太大则增长收敛时间。一般N30160。交叉概率PC太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取PC025075。变异概率PM太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取PM00102。七、遗传算法在神经网络中的应用遗传算法在神经网络中的应用主要反映在3个方面网络的学习，网络的结构设计，网络的分析。1遗传算法在网络学习中的应用在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用1学习规则的优化用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。2网络权系数的优化用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。2遗传算法在网络设计中的应用用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种1直接编码法这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。2参数化编码法中国矿业大学2012届本科生毕业设计（论文）第11页参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。3繁衍生长法这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。3遗传算法在网络分析中的应用遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。遗传算法是从代表问题可能潜在解集的一个种群POPULATION开始的，该种群由一些经过基因GENE编码CODING的一定数目的个体INDIVIDUAL组成。根据问题的特点，制订适当的适应度函数FITNESSFUNCTION，对每一代种群，根据问题域中个体的适应度FITNESS大小挑选SELECTION个体，利用遗传算子GENETICOPERATOR进行杂交（或称交叉）CROSSOVER和变异MUTATION，从而产生出代表新的解集的下一代种群。这样一代一代的不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法所涉及的六大要素参数编码、初始群体的产生、适应度函数的设计、遗传操作的设计、控制参数的设定以及算法终止条件。九、遗传算法基本流程图中国矿业大学2012届本科生毕业设计（论文）第12页传统遗传算法（TGA）模拟自然界生物的双亲繁殖方式，主要利用交叉算子繁殖后代。传统遗传算法在采用非序号编码（包括二进制编码、实数编码等）且所求解问题属无约束优化问题时是有效的。对于组合优化问题，如巡回旅行商（TSP）问题，使用序号编码比非序号编码更简单、更直接，但序号编码的染色体不能使用常规交叉算子，必须使用部分匹配交差PMX、顺序交叉OX和循环交叉CX等特殊的交叉算子，而这些特殊的交叉算子遗传操作复杂，计算效率不高，且缺乏理论基础，这在很大程度上限制了序号编码遗传算法的推广应用。针对于传统遗传算法在求解组合优化问题时的上述不足，提出了一种单亲遗传算法。单亲遗传算法主要采用序号编码，不使用传统遗传算法的交叉算子，而代之以仅在一条染色体上操作的基因重组等遗传算子，即单亲遗传算法只通过单个个体繁殖后代。单亲遗传算法也因此而得名。后来，在用遗传算法求解火电厂机组优化组合问题时，发现尽管这一问题可采取非序号编码，但由于其约束条件很多，传统遗传算法的交叉算子的作用效率大为下降。因为当交叉算子作用于代表可行解的两个个体时，产生的两个新个体很可能不再代表可行解。因此，针对火电厂机组优化组合问题提出了一种使用实中国矿业大学2012届本科生毕业设计（论文）第13页数编码的单亲遗传算法，取得了比传统遗传算法更好的效果。122、单亲遗传算法的特点与传统遗传算法一样，单亲遗传算法群体规模N的选择对计算效率有着很大的影响。如果N太小,每遗传迭代一次处理的图式数量太少,容易导致算法收敛于局部最优解；反之，如果N太大，每遗传迭代一次的适应度计算时间大幅度增加,计算效率低下。本文通过分析单单亲遗传算法在每一次遗传操作时处理的有效图式的数量，对单亲遗传算法的最优群体规模进行研究单亲遗传算法取消了传统遗传算法的交叉算子,采取单亲繁殖方式。跟传统遗传算法相比，单亲遗传算法遗传操作简单，容易在遗传操作过程中处理约束条件，不要求初始群体具有多样性，不存在“早熟”收敛问题，计算效率高，全局收敛性好。单亲遗传算法的研究对完善遗传算法的理论基础，有效地解决组合优化问题和有约束优化问题具有重要意义。单亲遗传算法与传统遗传算法的区别主要在产生新个体的方法上，传统遗传算法模拟自然界绝大多数生物的双亲繁殖方式，遗传操作主要在两个个体上进行；而单亲遗传算法模拟自然界少数生物的单亲繁殖方式，遗传操作只在一个个体上进行。众所周知，传统遗传算法的交叉算子在群体中的个体都相同时是无效的，这就要求初始群体中的个体具有广泛的多样性，并且这种多样性必须维持到遗传迭代的完成。如果在进化过程中群体中的个体失去多样性，则交叉算子不能产生新的个体，会发生所谓“早熟收敛”现象。单亲遗传算法的全部遗传操作都在一个个体上进行，遗传迭代的进行与群体的多样性无关，不要求初始群体中的个体具有的多样性，也不会发生“早熟收敛”现象。导致早熟的原因可以有以下几种类型A、群体规模当群体规模太小时，造成有效等位基因先天缺失，不能保证有效模式的正确传播，使得群体进化不能按模式定理产生所预测的期望数量。B、群体初始化初始群体分布在编码空间的局部区域，模式采样误差较大，导致遗传算法的搜索范围受到限制。C、选择压力选择压力（最佳个体与最差个体被选择的概率之比）太大，将会导致当前种群中的最优个体具有较高的复制数目，较差个体消亡速度过快，导致群体多样性迅速降低。D、变异概率当变异概率较小时，群体多样性下降速度较快，容易导致有效基因的迅速丢失且难以恢复；当变异概率较大时，虽然群体多样性可保持在较高水平，但高阶模式被破坏的概率随之增大。E、适应函数自身的性质当适应函数高度非线性，染色体基因位之间高度相关时，有效模式被破坏的可能性加大。针对上述原因，防止早熟一般有以下方法A、选择合适的群体规模在计算量允许的情况下，尽量选择较大的群体规中国矿业大学2012届本科生毕业设计（论文）第14页模，以保证群体的多样性。B、保持合适的选择压力当变异概率较小时，可采用中等压力的选择参数；当变异概率较大时，可采用较大压力的选择参数。C、适应度定标法为使遗传算法有效地工作，必须保持种群内染色体的多样性和位串之间的竞争机制。在算法进行的早期，个体差别很大，为了防止超级个体的出现，保持种群的多样性，此时必须降低个体之间适应度的差异，可对适应度采取收缩的操作；而到了后期，此时经过进化，种群中的个体在适应度上都已经很接近，从而导致了算法在后期搜索效率低下，就必须放大个体间适应度上的差异，可对个体适应度采取拉伸的操作，使得种群朝着良好的方向进化。D、参数适应性遗传算法的性能由在搜索空间进行的深度搜索和广度搜索的平衡决定。这种平衡受遗传算法中的参数（包括种群规模、遗传代数、交叉概率和变异概率等）的影响。自适应是针对遗传算法中参数配置能力不足提出来的。SRINIVASZAI提出了对交叉概率和变异概率进行算法动态自适应的思想，通过交叉概率和变异概率动态自适应，能够协调种群的多样性和算法的收敛性之间的矛盾，从而达到一个很良好的算法求解效果。WHILEY则考虑针对个体之间的海明距离HAMMINGDISTANCE来配置变异概率。E、多种群进化单纯多群体单纯多群体遗传算法的基本思想是多群体同时进化，其中多群体之间不存在染色体位串的迁移和基因的交换，这一点与并行遗传算法不同。它要求每个子群体的进化独立进行，群体之间互不干扰。协同多群体实际优化问题中的多峰搜索或多模态函数优化问题，不仅要求在可行区域内寻找全局最优解，而且需要找到多个全局最优解和局部最优解，这类问题一般用协同多群体遗传算法求解较好。它要求多个群体相互协调，同时进化。如GOLDBERG和RICHARDSON于1987年提出的基于适应度值共享机制的小生境技术NICHINGTECHNOLOGY。123、单亲遗传算法理论研究现状早期的单亲遗传算法一般都采取序号编码方式，通过多机多阶段FLOWSHOP问题两种不同编码方式的比较，说明编码方式的选择对单亲遗传算法的计算效率影响是很大的。对于同序基因数GC1的组合优化问题，应该尽量找到一种能使GC1的编码方式，以降低串空间的维数，提高搜索效率。实数编码单亲遗传算法的研究工作起步较晚，针对火电厂机组优化组合问题提出了一种实数编码方式，每条染色体中的每个基因代表一台机组某一个时段内的出力，使染色体串长大大缩短，提高了搜索效率。单亲遗传算法遗传算子的构造与编码方式有关。序号编码单亲遗传算法常用的遗传算子可分为两大类基因重组算子和基因突变算子。基因重组算子包括基因换位、基因移位、基因倒位等调整序号基因在染色体中相对位置的遗传算子。基因重组算子和基因突变算子分别搜索E和M子空间，它们的遗传操作功中国矿业大学2012届本科生毕业设计（论文）第15页能明显不同。如果单亲遗传算法采取GC1的编码方式，则不存在基因突变算子。序号编码单亲遗传算法的每一种遗传算子都可分为单点算子和多点算子。相应地有单点基因换位和多点基因换位、单点基因移位和多点基因移位、单点基因倒位和多点基因倒位、单点基因突变和多点基因突变等。多点遗传算子对图式的破坏作用太大，搜索效率不高，使用不多。但在遗传迭代的后期，使用多点遗传算子对防止算法收敛于局部最优解是有好处的。实数编码单亲遗传算法主要用于有约束的复杂工程优化问题。因为需要在遗传操作过程中处理约束条件，遗传算子的构造比较困难。针对火电厂机组优化组合问题构造了几种实数编码遗传算子，这些遗传算子对其它问题不具有通用性。有的论文给出了单亲遗传算法的几种常用选择方式，并指出单亲遗传算法的全局收敛性和收敛速度与选择方式有关。锦标赛选择方式和父子竞争选择方式不能保证算法的全局收敛性，但有较快的收敛速度；按适应度比例选择方式在引入了最优保持操作后能保证算法的全局收敛性，但收敛速度较慢。图式定理是遗传算法的重要理论基础之一。对单亲遗传算法的图式定理进行了分析研究，单亲遗传算法的遗传算子处理图式的能力与传统遗传算法的基本相当，单亲遗传算法具有与传统遗传算法类似的隐含并行性。单亲遗传算法的运行过程可以与传统遗传算法的完全相同，但先繁殖后选择的运行方式，比先选择后繁殖的运行的方式更适合于单亲遗传算法。有的论文在假定上一代群体中的所有个体被选择到下一代的概率都大于0时，对单亲遗传算法的全局收敛性进行了分析研究，指出单亲遗传算法的基因换位算子、基因移位算子、基因倒位算子和基因突变算子对串空间的搜索都具有遍历性，单亲遗传算法在引入了最优保持操作后是全局收敛的。因此单亲遗传算法是否全局收敛主要取决于选择方式。有的论文分别基于图式定理和MARKOV链对单亲遗传算法的计算效率进行了定性分析，从提高计算效率的角度，对单亲遗传算法遗传算子的作用概率等遗传控制参数的选取进行了研究。单亲遗传算法计算效率的定量分析有待进一步研究。有的论文提出了一种多模态单亲遗传算法，对其收敛性进行了分析，并通过两个典型函数优化问题验证了这种算法的有效性。有的论文提出了一种基于单亲遗传算法和模糊C均值算法的混合聚类算法。这种算法克服了模糊C均值算法的局部最优问题以及采用普通遗传算法聚类时搜索速度和聚类精度的矛盾。针对旅行商问题，对单亲遗传算法作了进一步改进。通过改进个体编码方式，压缩了个体空间；通过对初始群体进行预处理，提高了初始群体中个体的平均适应度；通过改进个体适应度函数的计算方法，减少了个体适应度的计算时间；通过对群体中个体的相似性检查而淘汰部分相同的个体，能保持群体中个体的多样性。这些改进措施对提高算法的收敛速度和算法的全局搜索能力具中国矿业大学2012届本科生毕业设计（论文）第16页有重要意义。有的论文分别就单亲遗传算法和传统遗传算法的编码方式、遗传算子、运行过程、适值计算等方面进行了比较研究，指出除了遗传操作不同外，单亲遗传算法在编码方式、运行过程、适值计算等方面都非常类似于传统遗传算法。单亲遗传算法的遗传操作虽然全部在一个个体上进行，但单亲遗传算法的基因重组算子隐含了传统序号编码遗传算法的交叉算子的功能，单亲遗传算法的子代个体也保留了父代个体的大部分遗传特征，即单亲遗传算法具有与传统遗传算法类似的进化机制。124、单亲遗传算法的应用研究现状讨论了单亲遗传算法在列车占线问题中的应用，给出了仿真实验结果，并将实验结果与传统遗传算法的进行了比较。仿真结果显示单亲遗传算法具有明显的优越性。研究了单亲遗传算法在模式聚类问题中的应用，用单亲遗传算法求解模式聚类问题可以使聚类结果完全不依赖于初始聚类中心。研究了单亲遗传算法在FLOWSHOP问题中的应用，给出了仿真实验结果，从仿真结果可以看出单亲遗传算法能够适应于较大规模的生产调度问题的优化。肖鹏等将单亲遗传算法应用于物流配送和车辆路径问题中，也取得了良好的效果。将单亲遗传算法应用于火电厂机组优化组合问题，并使用实数编码，给出了一个10台机组的仿真实例。仿真结果显示了算法的有效性。研究求解复杂工程优化问题的实数编码单亲遗传算法对降低工业生产和管理成本，提高社会经济效益具有重要的意义。针对电力系统机组优化组合问题，提出了一种基于单亲遗传算法基本思想的基因协同变异遗传算法。这种算法能同时解决机组的启、停状态组合和经济负荷分配问题。与常规遗传算法比较，实数编码单亲遗传算法通过采用一个基因对应一个参数的实数编码方式，压缩了染色体串长，且无需解码；通过采用单亲繁殖方式，提高了遗传算子的搜索效率，并能较方便地在遗传操作过程中处理约束条件；通过在遗传操作过程中实现基因协同变异，进一步提高了遗传算子的搜索效率。配电网络规划属于非线性混合整数规划问题，应用传统数学优化算法往往难以直接求解。针对目前应用广泛的常规遗传算法在求解该问题时存在的难以保证方案连通性和辐射性的缺陷，提出了基于单亲遗传算法的配电网络优化规划算法。基于整数编码策略，给出了配电网络规划中变量编码的具体方法和迭代求解程序。该算法具有进化操作成功率高，求解配电网络优化规划问题的效率高等优点，同时可将简化网架结构和选取导线截面结合在一起，既可确保解的最优性，又可减少工作量。仿真算例验证了该方法的快速性和有效性。该算法还适用于辐射型配电网络的扩展规划。针对油藏地质中复杂地层岩性划分存在的模糊性和多解性，提出了一种基于中国矿业大学2012届本科生毕业设计（论文）第17页单亲遗传算法的模式聚类划分复杂地层岩性的方法。该方法通过隐含传统遗传算法交叉算子功能的基因换位等遗传算子来实现进化操作，简化了遗传操作过程，同时避免了“早熟收敛”问题。采用该方法对大庆油田108个地层样本进行处理，总符合率达880，表明该方法可提高复杂岩性识别的精度。125、单亲遗传算法的展望单亲遗传算法自诞生以来，其理论研究和应用研究取得了一定的进展。基本上形成单亲遗传算法的理论基础，应用研究也取得了很好的成绩。但单亲遗传算法的理论体系尚不是很完善，在工程实际中的应用也有待进一步推广。单亲遗传算法的进一步研究工作可以在以下几个方面进行1、单亲遗传算法新的遗传算子的构造及新遗传算子遍历性的研究。2、单亲遗传算法选择方式的研究及选择方式对算法全局收敛性和收敛速度的影响。3、单亲遗传算法全局收敛性和收敛速度的深入研究，特别是收敛速度的定量分析。4、单亲遗传算法运行机理的进一步研究。5、单亲遗传算法在复杂工程优化中的应用研究。6、单亲遗传算法与其它优化方法的综合二、混合单亲遗传算法21、算法模型简介指派问题的标准形式（以人和事为例）有N个人和N件事，已知第I个人做第J件事的费用为CIJI,J1,2N，要确定人和事之间一一对应的指派方案，使完成这N件事的总费用最少。其数学模型为41,1,031,121,11MIN1111NJIXNIXNJXTSXCIJNJIJNIIJNJNIIJIJ指派问题的标准形式是01整数线性规划问题，其中CIJ表示第I个人作第中国矿业大学2012届本科生毕业设计（论文）第18页J件事的费用I,J1N，式（1）表示该指派方案消耗的总费用，式（2）表示每件事必有且只有一个人去做，式（3）表示每个人必做且只做一件事。因而指派问题有N个可行解。22、新的遗传算法221、新的编码方法现在设计一种新的编码方法。这种编码方法用121AAANN来表示一个指派方案，其中IA为满足IAI0的整数。定理1设,0为整数，且IIAIA11NI，则集合IINNAIAAAAS,0|121为整数，11NI中元素的个数为N个。证明因1A可取两个值0和1，2A可取3个值0,1,2，一般地，IA可取1I个值,1,0I121,AAANN而的取值相互独立，故121AAANN可能取值的个数为432NN。定理2设IAI0，且IA为整数，,11NI则在集合IAAAASINN0121，IA为整数，11NI与N,2,1的所有排列集合间存在着一一对应的关系。证明设SAAANN121与N,2,1这样的一个排列11PPPNN对应，其中IA可看作是排列11PPPNN中数1I所在位置左边比1I小的数的个数。于是，若SAAANN121给定，则可唯一地确定一个排列11PPPNN；反之，给定N,2,1的一个排列11PPPNN，也可唯一地确定一向量SAAANN121。故这种对应是一一对应。例1排列3512412345PPPPP与1,0,3,11234AAAA一一对应。上述定理2