第13章--启发式与元启发式算法

13启发式与元启发式算法定义一个基于直观或经验构造的算法，在可接受的花费(指计算时间、占用空问等)下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计启发式算法是一种技术，这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至大多数情况下，无法阐述所得解同最优解的近似程度元启发式算法：启发式算法的改进，随机方法与局部搜索算法相结合。启发式与元启发式算法优势(1)有些难的优化问题可能还没有找到最优算法，即使存在，由算法复杂性理论，得知它们的计算时间是无法接受或不实际的(2)一些启发式算法可用在最优算法中，如在分支定界算法中，可用启发式算法估界．(3)简单易行，比较直观；易被使用者接受，(4)速度快，在适时控制中非常重要．(5)多数情况下，程序简单，因此易于修改．启发式与元启发式算法不足(1)不能保证求得最优解．(2)表现不稳定．启发式算法在同一问题的不同实例计算中会有不同的效果．有些解很好，而有些则很差．在实际应用中，这种不稳定性造成计算结果不可信(3)算法的好坏依赖于实际问题、经验和设计者的技术．这点很难总结规律，同时使不同算法之间难以比较启发式与元启发式算法遗传算法模拟退火粒子群算法禁忌搜索神经网络13.1遗传算法•遗传算法包含以下的主要处理步骤．–首先是对优化问题的解进行编码，此处，我们称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和用于之后遗传算法中的计算．–第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定．当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰．生存下来的染色体组成种群．形成一个可以繁衍下一代的群体．–第三是染色体的结合．双亲的遗传基因结合通过编码之间的交配(crossover)达到下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解．–最后是变异．新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更历的遍历性．生物遗传概念在遗传算法中的对应关系例1用遗传算法求解的最大值x为整数．()2,031fxxx=＃解：一个简单的表示解的编码是二进制编码，由于变量的最在值是31，因此可以采用5位数的二进制码，如以上的5位字符串称为染色体．每一个分量称为基因，每个基因有两种状态0或1。模拟生物进化，首先要产生一个群体，可以随机取4个染色体组成一个群体，如x1=(00000)，x2=(1l001),x3=(Ollll)，x4=(O1OOO)．群体有4个个体．适应函数可以依据目标函数而定，如适应函数fitness(x)=f(x)=x2。于是例1定义第i个个体入选种群的概率为于是，适应函数值大的染色体个体的生存概率自然较大．若群体中选4个个体成为种群，则极有可能竞争上的是x2=(11001),x2=(11001),x3=(01111),x4=(01000)。若它们结合，采用如下的交配方式，称为简单交配即交换第二个位置以后的基因，得到y1,y2,y3和y4。若y4的第一个基因发生变异，则变成y4=(11001)简单遗传算法轮盘赌简单遗传算法例2求()2max1,0,1fxxx轾=-?犏臌由于对连续变量求解，要解决的一个问题是如何编码。假设对解的误差要求是1/16，则可以4位二进制编码，对应关系为执行一步计算，结果见下表解：简单遗传算法简单遗传算法可以理解为：求解的问题是极大目标函数的优化问题；采用0-1二进制编码；pop(t)中的染色体个数是一个常数；初始群体随机选取；适应函数数为口标函数；按轮盘赌方法选取染色体个数同pop(t)相同的种群；交配按例2的常规交配方法——一对染色体按随机位交换位后的基因；染色体中的每一个基因都以相同的概率变异关键问题(1)解的编码和解码．遗传算法的基础工作之一是解的编码，只有在编码之后才可能有其他的计算(2)初始群体的选取和计算中群体的大小．一般采用随机产生初始群体或通过其他方法先构造一个初始群．通过其他方法构造的初始群体可能会节省进化的代数，但也能过早地陷人局部最优群体中．我们称过早地陷入局部最优群中的现象为早熟(premature)现象群体中个体的个数称为群体维数．群体的维数越大其代表性越广泛，最终进化到最优解的能性越大关键问题(3)适应函数的确定．一般情况，适应函数同目标函数相关，以保证较优的解有较大的生存机会(4)三个算子。遗传算法的三个算子是：种群选取、交配和变异（突变）遗传算法的优越性(1)遗传算法适合数值求解那此带有多参数、多变量、多目标和在多区域但连通性较差的NP-hard优化问题．遗传算法是一个有普适性的方法，对目标函数的性质几乎没有要求，甚至都不一定要显式地写出目标函数。遗传算法所具有的特点是记录一个群体，它可以记录多个解而不同于局部搜索、禁忌搜索和模拟退火仅仅是一个解，这多个解的进化过程正好适合多目标优化问题的求解遗传算法的优越性(2)遗传算法在求解很多组合优化问题时．不需要有很强的技巧和对问题有非常深入的了解．(3)遗传算法同求解问题的其它启发式算法有较好的兼容性13.2