第13章 启发式与元启发式算法_图文.ppt

13 启发式与元启发式算法定义一个基于直观或经验构造的算法,在可接受的花费(指计算时间、占用空问等)下给出待解决优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计启发式算法是一种技术,这种技术使得在可接受的计算费用内去寻找最好的解,但不一定能保证所得解的可行性和最优性,甚至大多数情况下,无法阐述所得解同最优解的近似程度元启发式算法:启发式算法的改进,随机方法与局部搜索算法相结合。启发式与元启发式算法优势(1)有些难的优化问题可能还没有找到最优算法,即使存在,由算法复杂性理论,得知它们的计算时间是无法接受或不实际的(2)一些启发式算法可用在最优算法中,如在分支定界算法中,可用启发式算法估界.(3)简单易行,比较直观;易被使用者接受,(4)速度快,在适时控制中非常重要.(5)多数情况下,程序简单,(1)不能保证求得最优解.(2),,这种不稳定性造成计算结果不可信(3)算法的好坏依赖于实际问题、,同时使不同算法之间难以比较启发式与元启发式算法?遗传算法?模拟退火?粒子群算法?禁忌搜索? 遗传算法?遗传算法包含以下的主要处理步骤.–首先是对优化问题的解进行编码,此处,我们称一个解的编码为一个染色体,组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和用于之后遗传算法中的计算.–第二是适应函数的构造和应用。,自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存,.–(crossover)达到下一代的产生。新一代的产生是一个生殖过程,它产生了一个新解.–,变异使某些解的编码发生变化,.()2,0 31f x x x= #解:一个简单的表示解的编码是二进制编码,由于变量的最在值是31,因此可以采用5位数的二进制码,,每个基因有两种状态0或1。模拟生物进化,首先要产生一个群体,可以随机取4个染色体组成一个群体,如x1=(00000),x2=(1l001), x3=(Ollll),x4=(O1OOO).,如适应函数fitness(x)=f(x)=x2。于是例1定义第i个个体入选种群的概率为于是,,则极有可能竞争上的是x2=(11001), x2=(11001), x3=(01111), x4=(01000)。若它们结合,采用如下的交配方式,称为简单交配即交换第二个位置以后的基因,得到y1, y2, y3和y4。若y4的第一个基因发生变异,则变成y4=(11001)简单遗传算法轮盘赌