第二章_遗传算法

第二章遗传算法目录1什么是遗传算法（内容、历史、特点）2遗传算法的主要概念3遗传算法的运算过程4遗传算法的实例5遗传算法的学术信息1什么是遗传算法遗传算法（GeneticAlgorithm，GA）。1975年Holland提出，开创了遗传算法这一领域。包括3个研究方向：基本遗传算法的研究；遗传算法用于优化的研究；带有分类系统的机器学习。2种运算（遗传运算-交叉和变异进化计算-选择）遗传算法是一种并行搜索寻优技术，它具有很多优点，除了搜索范围广，易实现全局最优外。它对于待优化的问题没有太多的数学要求，无论线性与否、连续或是离散、甚至混合的搜索空间都能够适应。2遗传算法的主要概念生物进化过程种群个体染色体交叉变异下一代（种群）适应能力遗传算法种群个体染色体交叉变异下一代（种群）适应度函数三个随机量：交叉率变异率选择概率3遗传算法的运算过程按着以下步骤完成寻优计算：1、初始化：k=1，随机产生160个样本，组成了第1代种群；2、求适应度函数：由（18）式求出种群中每个个体的适应度函数eval，并根据（17）式对每个样本分配交叉概率及概率分布范围；3、交叉：随机选出30个样本，根据公式（15）两两进行交叉，产生了30个新的样本；4、变异：随机产生100个样本,根据公式(16)进行变异,产生若干新样本；5、循环：第3、4步的运算产生了新一带的种群，因此k=k+1，并判断如果k150000，则跳到第2步；否则到底6步。6、结束：选出mV、150000中最好的样本作为最优值。4遗传算法例题例1求解22xy的最小值。例2基于遗传算法的打浆过程对于优化的问题，传统的优化方法常常是微分法。但这类方法有其局限性。首先，这类算法所寻求的极点往往是当前范围内的局部最优解。其次，微分法要求优化对象的梯度存在[5]。在打浆优化这一课题的优化目标函数中。存在湿重),,,(0gICFgg这样一个用BP神经网络训练出来的关系式和),,,,(IgSRCFP这样的构造函数。其对应关系复杂，优化对象的梯度很难求出。采用微分法（最速下降法或梯度法）实现对打浆过程的优化十分困难。因此，我们考虑采用遗传算法来完成优化。遗传算法是一种并行搜索寻优技术，它具有很多优点，除了搜索范围广，易实现全局最优解[2]外。对于本优化课题来说，由于遗传算法只用编码及适应度表示问题，并不要求明确的数学方程及导数方程。因此，遗传算法可应用于离散问题及函数关系不明确的复杂问题[3]。遗传算法虽然有诸多优点，但依然存在不完备处，例如，遗传算法的迭代停止条件尚无定论[4]。常用的一种方法是当适应度函数的最大值已知或次优解适应度下限可以确定时，一般以发现最大值或次优解作为遗传算法迭代停止条件。但是，本优化问题中适应度最大值并不知道，次优解下限也很难确定。对于这种情况一种解决办法是规定种群的代数，到达规定的代数就停止，并以最后一代中最好的个体作为优化结果。由于遗传算法是一种渐近式优化。多数情况下，新一代的结果优越于旧一代。因此由这种方法得到的最优解在一定概率下是可信的。考虑到最优解在最后一代之前已出现且最后一代的解非最优解的情况有可能发生，笔者在遗传算法中添加一个记录器，记录到目前为止最优个体，这个记录器中的个体并不参与优化计算，因此对寻优过程没有影响，其工作方法见图4.3寻优过程。首先确定种群的大小，优化代数，变异率，交叉率。种群大小30n个。第N代种群)30,,3,2,1,(kvVkNN，最大代数为1000maxN。当1000代后取出最好的个体与记忆器中的最好的个体比较，取优者作为优化结果。取变异率mP=0.09，交叉率35.0cP。我们采用如下的遗传算法来实现寻优。实数编码]..[XXXXXXXXXIFC算术交叉：211)1(vvv(11)122)1(vvv这里取7.0。非均匀变异),(kkkkXXtXX(12)brNtyyt)1(),((13)取2b，kX根据不同定义取500kI，50.3kC，15kF，1000N用线性排序法为新一代种群中第k个个体分配一个选择概率kP：rkqPk)1((14)0qqr(15)这里取08.0q，022.00q，002.0r，令mkkmPS1（其中00S）(16)使用mS为当代种群的每一个个体在1,0分配一个数段，其中第k个个体对应nknkSSSS,1(17)我们选择优化目标函数为适应值函数:),,,()),,,(()100(0gSRCFPggCFIggEEevalmmm(18)遗传算法控制参数的初始化、N=0随机产生90个量，组成30个个体求个体的适应值（目标函数）按适应值排序，选取前30个个体组成新的一代种群N=N+1选本代中最好的2个个体与记录器中（10个）个体比较取代最坏的2个以公式(5-8)对个体分配概率并按概率分配被选择数段(1-30)随机产生30个(0,1)的随机数，随机数乘30后的数落入哪个数段就选择哪个个体，选中30个个体产生30个随机数，小于0.35者所对应的个体被选中参加交叉产生90个随机数(0,1),小于0.03者所对应的基因被选中按公式(5-9)进行变异选择第1000代中的个体和记录器个体中最好的个体作为优化结果优化结果否1000NNY11图4程序流程图按图4程序流程的顺序执行直到1000代种群得到最优的个体，以这个个体含有的3个基因I、F和C为优化结果。428mI（安）、8.12mF（分米2/秒）、%9.2mC，将mI分为mI33.0、mI33.0和mI34.0三个数。5遗传算法的学术信息①著作出版时间作者书名1975HollandAdaptationinNaturalandArtificialSystem1987DavidGeneticAlgorithmsandSimulatedAnnealing1995SchwefelEvolutionandOptimumSeeking1996BäckEvolutionaryAlgorithmsinTheoryandPractice遗传算法的巨大进步出现在20世纪90年代。②学术会议自1985年，关于遗传算法的国际会议和研讨会开始出现，以下是主要讨论会：缩写会议名称ICGAInternationalConferenceonGeneticAlgoritithmsPPSNInternationalConferenceonParallelProblemSolvingfromNatureICECIEEEInternationalConferenceonEvolutionComputationANN&GAInternationalConferenceonArtificialNeuralNets&GeneticAlgoritithmsEPAnnualConferenceonEvolutionaryProgrammingFOGAWorkshoponFoundationofGeneticAlgoritithmsCOGANNInternationalWorkshoponCombinationsofGeneticAlgoritithmsandNeuralNetwork③杂志EvolutionaryComputation(1993年开始发行，MITPress出版④网络