算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第13章）

《算法设计 郑宇军 石海鹤 陈胜勇 算法设计（第13章）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第13章现代优化算法禁忌搜索模拟退火遗传算法蚁群算法粒子群算法差分进化算法现代优化算法启发式算法：依据人的直观经验、或是模拟自然界的某些规则而设计出的算法不一定保证得到最优解不一定保证解的近似程度13.1禁忌搜索找到问题的一个初始可行解x0，令当前解x=x0，禁忌表T为空。如果终止条件满足，那么返回当前已找到的最优解，算法结束。否则，在x的邻域N(x)中选取一个未被禁忌且评价最好的解x′，将从x到x′的搜索步(x,x′)更新到禁忌表T中，令当前解x=x′并转第2步13.1禁忌搜索终止条件时间迭代次数目标函数值水平13.1禁忌搜索终止条件解的评价：目标函数值或其它的评价函

2、数禁忌长度：太短可能会导致循环，太长则可能丢掉最优解完全禁忌的处理：结束算法，跳出当前解特赦法则：如某个邻域解x′比较不错，那么即使x′被禁忌表禁忌，仍可以选取它作为新的当前解13.1禁忌搜索抽象算法框架AlgorithmTabuSearch(d:D;ten,kmax:int;f:Zreal;Init:DZ;N:ZSet(Z))beginletx=Init(d);//找到一个初始可行解letT=newQueue(),k=0,xbest=x;while(k

3、x,x’)Tf(x)f(xbest))thencontinue;//跳过被禁忌且不被特赦的邻域解if(f(x’)

4、T

5、>ten)thenT.Dequeue();if(f(x’)

6、3.2模拟退火找出问题的一个初始解x0，令x=x0，t=tmax（初始最高温度）。如果终止条件满足，那么返回当前已找到的最优解，算法结束。从当前解x的邻域N(x)中随机选取一个解x′，计算能量差Δf=f(x)−f(x′)，若Δf为负或是一个很小的正数，则令x=x′。如果当前温度下的迭代次数超过上限则转第5步，否则转第3步。令t=d(t)，其中d为温度变化函数，而后转第3步13.2模拟退火初始温度:统计推断法或简单试验温度下降时间等差下降迭代次数等比下降更为复杂的下降函数13.2模拟退火抽象算法框架AlgorithmAnnealing(d:D;tmax,tmin

7、,a:real;kmax:int;f:Zreal;Init:DZ;N:ZSet(Z))beginletx=Init(d),t=tmax,xbest=x;while(t>tmin)doletk=0;while(k

8、N(x)

9、=0)thenbreak;letr=Random(0,

10、N(x)

11、),x’=N(x)[r],delta=f(x)−f(x’);if(delta<0)(exp(-delat/t)

12、rnxbest;end13.3遗传算法遗传进化:遗传性质以基因的形式包含在染色体中，基因中各个不同的位置控制着不同的特殊性质，基因杂交和基因突变能够产生对环境适应性更强的后代。通过优胜劣汰的自然选择，适应性更强的基因结构会被保留下来。遗传算法:将问题的解编码为“染色体”，组成编码的元素称为“基因”。在算法迭代过程中，按照“适者生存”的规律，选取适应度高的染色体进行复制，并对它们进行杂交和变异，产生新一代更适应环境的染色体群。13.3遗传算法生成问题的一组初始解，将其作为初始群体。如果终止条件满足，那么返回当前已找到的最优解，算法结束。计算群体中每个个体的适应度，选取其中

13、适应度较高的一些个体作为种群。在种群个体之间进行杂交操作，得到新一代群体。在新群体中选取少量个体进行变异操作，而后转第2步13.3遗传算法选择操作:适应度越高的个体被选中的概率越大轮盘赌13.3遗传算法选择操作:适应度越高的个体被选中的概率越大轮盘赌按概率排序锦标赛——个体之间两两相互竞争13.3遗传算法杂交操作0110101100111100011011000011011113.3遗传算法抽象算法框架AlgorithmGenetic(d:D;N,len,gmax,rmax:int;f:Vectorreal;Init:Din