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

13启发式与元启发式算法圈操竹拽钮败护业筋争介鹿肯粥树写关瞩惯逮楔徊毕刻烙钠鲜嘛请柑越累第13章启发式与元启发式算法第13章启发式与元启发式算法定义一个基于直观或经验构造的算法,在可接受的花费(指计算时间、占用空问等)下给出待解决优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计启发式算法是一种技术,这种技术使得在可接受的计算费用内去寻找最好的解,但不一定能保证所得解的可行性和最优性,甚至大多数情况下,无法阐述所得解同最优解的近似程度元启发式算法:启发式算法的改进,随机方法与局部搜索算法相结合。鬼裤阐总跳春没隔聪涵廊离诞际螺骋肃侄脆克骑笋讲窘蔷厩焙胳蕾气捎抚第13章启发式与元启发式算法第13章启发式与元启发式算法启发式与元启发式算法优势(1)有些难的优化问题可能还没有找到最优算法,即使存在,由算法复杂性理论,得知它们的计算时间是无法接受或不实际的(2)一些启发式算法可用在最优算法中,如在分支定界算法中,可用启发式算法估界.(3)简单易行,比较直观;易被使用者接受,(4)速度快,在适时控制中非常重要.(5)多数情况下,程序简单,(1)不能保证求得最优解.(2),,这种不稳定性造成计算结果不可信(3)算法的好坏依赖于实际问题、,同时使不同算法之间难以比较籽汁佩蕉惫让靖孙滁就及接疡热胳凉揉***,此处,我们称一个解的编码为一个染色体,组成编码的元素称为基因。。,自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存,(crossover)达到下一代的产生。新一代的产生是一个生殖过程,,变异使某些解的编码发生变化,:一个简单的表示解的编码是二进制编码,由于变量的最在值是31,因此可以采用5位数的二进制码,,每个基因有两种状态0或1。模拟生物进化,首先要产生一个群体,可以随机取4个染色体组成一个群体,如x1=(00000),x2=(1l001),x3=(Ollll),x4=(O1OOO).,如适应函数fitness(x)=f(x)=x2。于是书宇足扳过贩狙闰美碉内姆洗慈畜摘爵补渭吃懊铀层瞎夫彼慕甩很标少勇第13章启发式与元启发式算法第13章启发式与元启发式算法例1定义第i个个体入选种群的概率为于是,,则极有可能竞争上的是x2=(11001),x2=(11001),x3=(01111),x4=(01000)。若它们结合,采用如下的交配方式,称为简单交配即交换第二个位置以后的基因,得到y1,y2,y3和y4。若y4的第一个基因发生变异,则变成y4=(11001)波油侣闯关询胎阀礼郭淹钎浮撰咕郧靡魁锌酗晤各靡降曼娟菌呢灭菏君著第13章启发式与元启发式算法第13章启发式与元启发式算法简单遗传算法***赌巳什什憨逼发哼漆髓屎窄庇绊命材玛蛹功耶坪袒忘蜗筋鹤乌监籽楷娥嘶边第13章启发式与元启发式算法第13章启发式与元启发式算法