遗传算法GeneticAlgorithmVIP免费

24/10/24遗传算法遗传算法(GeneticAlgorithm)(GeneticAlgorithm)进化算法(EvolutionaryAlgorithm)24/10/24遗传算法遗传算法(GA)(GA)Darwin(1859):“物竟天择，适者生存”JohnHolland(universityofMichigan,1975)《AdaptationinNaturalandArtificialSystem》遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。24/10/24遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制遗传算法的搜索机制24/10/24局部局部全局全局遗传算法遗传算法(GA)(GA)24/10/24Wehaveadream!!Wehaveadream!!IamatthetopIamatthetopHeightis...Heightis...Iamnotatthetop.Iamnotatthetop.Myhighisbetter!Myhighisbetter!IwillcontinueIwillcontinue遗传算法遗传算法(GA)(GA)GA-----第0代24/10/24DeadoneDeadoneNewoneNewone遗传算法遗传算法(GA)(GA)GA----第1代24/10/24Notatthetop,Notatthetop,ComeUp!!!ComeUp!!!遗传算法遗传算法(GA)(GA)GA----第?代24/10/24IamtheIamtheBESTBEST!!!!!!遗传算法遗传算法(GA)(GA)GA----第N代24/10/24适者生存(SurvivaloftheFittest)GA主要采用的进化规则是“适者生存”较好的解保留，较差的解淘汰遗传算法遗传算法(GA)(GA)24/10/24生物进化与遗传算法对应关系生物进化与遗传算法对应关系生物进化遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应函数24/10/24遗传算法的基本操作遗传算法的基本操作选择(selection):根据各个个体的适应值，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。交叉(crossover):将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc(称为交叉概率，crossvoerrate)交换它们之间的部分染色体。变异(mutation):对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutationrate)改变某一个或一些基因座上基因值为其它的等位基因。24/10/24如何设计遗传算法如何设计遗传算法如何进行编码？如何产生初始种群？如何定义适应函数？如何进行遗传操作(复制、交叉、变异)？如何产生下一代种群？如何定义停止准则？24/10/24编码编码(Coding)(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间={0,1}L011101001010001001100100101001000124/10/24选择选择(Selection)(Selection)选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中主要思想:适应值较高的染色体体有较大的选择(复制)机会实现1：”轮盘赌”选择(Roulettewheelselection)将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率Ps产生一个在0与总和之间的的随机数m从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于m24/10/24选择选择(Selection)(Selection)设种群的规模为Nxi是i为种群中第i个染色体AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=21()()()isiNjjFxpxFx染色体xi被选概率24/10/24选择选择(Selection)(Selection)染色体的适应值和所占的比例轮盘赌选择24/10/24选择选择(Selection)(Selection)随机数23491338627所选号码262514所选染色体110000001111000011000111010010染色体编号123456染色体011101100000100100100110000011适应度81525128被选概率0.160.30.040.10.240.16适应度累计82325304250染色体被选的概率被选的染色体24/10/24选择选择(Selection)(Selection)轮...