遗传算法-report

2目录基本思想算法流程图GA的特点适用于解决的问题不足之处（自身的局限性）改进的遗传算法3智能优化算法•智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。4智能优化算法的特点•它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。5基本思想生物学角度：优胜劣汰数学角度：优（优解遗传）劣（劣解灭亡），全局搜索最优解61.个体与种群●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。●种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。基本概念72.●适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。●适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。基本概念83.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体9----1001（2，5，6）----010101110基本概念9概述对于一个最优化问题，一定数量的候选解（个体）的染色体的种群向更好的解进化。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群基于适应度随机地选择多个个体，通过自然选择（交叉、变异）产生新的种群，该种群在算法的下一次迭代中成为当前种群。10概述一个典型的GA要求：一个基因（gene）表示的求解域；一个适应度函数（fitnessfunction）来评价解决方案。遗传算法区别于其他优化算法的根本所在：交叉算子11进化模式示意图12进化流程图13算法流程图genmain10.m14具体阐述1.编码的选择：二进制编码二进制编码，不适用于多维、高精度连续函数的优化问题。根据研究问题的不同，选择合适的编码方案。15具体阐述2.适应度函数（FitnessFunction）GA在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群每个个体的适应度来进行搜索。GA评价一个解的好坏不是取决于它的解的结构，而是取决于该解的适应度值，体现了GA的优胜劣汰。16选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。NjjiixfxfxP1)()()(这里的选择概率P(xi)的计算公式为遗传算子1——选择复制（selection，reproduction）17遗传算子1——选择复制（selection，reproduction）遗传操作中，如果单纯的以适应度高低作为导向，容易导致算法快速收敛到局部最优解，而非全局最优解。（早熟现象）18轮盘赌选择示意图s40.31s20.49s10.14s30.06●轮盘赌选择法19在算法中轮盘赌法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为：ijjixPq1)(20遗传算子2——交叉/基因重组（crossover，recombination）单点交叉示意图21遗传算子3当交叉操作产生的后代个体适应值不再比他们的前辈更好，但又未达到全局最优解时，就会发生早熟收敛（prematureconvergence）。引入变异算子，保持个体多样性，还有在交叉操作的基础上，引入适度的变异，也能够提高GA的局部搜索效率。——变异（mutation）（二级）22循环终止条件（1）进化次数限制（2）计算耗费的资源限制（例如计算时间、计算占用的内存等）（3）一个个体已满足最优值的条件，即最优值已经找到（4）适应度已经达到饱和，继续进化不会产生适应度更好的个体（5）人为干预23欺骗问题在GA初期，通常会产生一些超常个体，按照比例选择法，这些超常个体会因竞争力突出，而控制选择过程，影响到算法的全局优化性能。在GA后期，当算法趋于收敛时，由于种群中个体适应度差异较小，继续优化的潜能降低，可能获得某个局部最优解。24遗传算法（GA）的特点1、GA很快就能找到良好的解，即使是在很复杂的解空间中。2、GA并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用GA的同时，也可以尝试其他算法，互相补充，甚至根本不用GA。25遗传算法（GA）的特点3、GA不能解决那些“大海捞针”的问题，（没有一个确切的适应度函数表征个体好坏的问题，使得算法的进化失去导向。）4、对于任何一个具体的优化问题，调节GA的参数（个体数目、交叉率和变异率）可能会有利于更好的更快的收敛。例如太大的变异率会导致丢失最优解，而过小的变异率会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。26适用于解决的问题GA擅长解决的问题是全局最优化问题。不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。特长：解决时间表安排问题27不足之处（自身的局限性）1.编码存在表示的不准确性2.遗传算法通常的效率比其他传统的优化方法低3.遗传算法容易出现过早收敛4.遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。28模式（schema）模式将种群中的个体即基因串中的相似样板称为模式。在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号*代表任意字符，即0或1。如模式*1*描述了一个四个元的子集{010，011，110，111}。29模式阶和定义距模式H中确定位置的个数称为模式H的模式阶，记作O(H)，如O(011*1*)=4。模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确定性就越高，所匹配的样本个数就越少。30模式阶和定义距模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作δ(H)，如δ(011*1**)=4。阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异。31模式定理（schematheorem）模式定理：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。具有低阶、短定义距以及平均适应度高于种群平均适应度的模式被定义为积木块。32积木块假设（buildingblockhypothesis）遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），产生适应度更高的个体，从而找到更优的可行解。33改进的遗传算法(1)分层遗传算法(HierarchicGeneticAlgorithm);(2)CHC算法;(3)Messy遗传算法;(4)自适应遗传算法(AdaptiveGeneticAlgorithm);(5)基于小生境技术的遗传算法(NichedGeneticAlgorithm);(6)并行遗传算法(ParallelGeneticAlgorithm);(7)混合遗传算法:①遗传算法与最速下降法相结合的混合遗传算法；②遗传算法与模拟退火法相结合的混合遗传算法。34◆遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。遗传算法的应用35