计算机问题求解—论题4.10 启发式算法的概念 陶先平 2017年6月5日

问题1：在一个优化问题中，什么是问题空间？什么是解空间？ 问题2：启发式算法本质上来讲，是一种解空间搜索算法。你如何理解这个说法？ 洛斯阿拉莫斯国家实验室 退化 Mutation：变异

问题3：定义一个可行解的”邻居”是什么用意？ 何谓邻居？自由定义，因人因事而不同 用邻居来指导我们的搜索 提示：定义的第三点，寓意深刻

可行解的邻居图 理论上：1，邻居图连通； 2，最优解必定在图中； 3，遍历解空间的难度，决定了问题难度

局部最优解 注意：a只是在a的邻居中最好。 退而求其次，也是一个很好的策略

LSS算法 LSS算法一定能找到局部最优！但上述两个Find对结果的优劣和算法的效率是有影响的 can essentially influence the quality of the result：arbitrary poor local optima LSS算法 LSS算法一定能找到局部最优！但上述两个Find对结果的优劣和算法的效率是有影响的 first improvement, best improvement may lead to very different results for the same initial feasible solution.

必须解决局部搜索方法中的“poor local optima”问题

物理学中的“退火”是什么？

Metropolis算法：对退火过程的模拟 模拟退火算法对LSS算法的最大改进

两个方法的直观比对 Metropolis方法 LSS方法

模拟退火算法 有了“逃离”局部最优陷阱的可能

要说明的一点： 模拟退火算法只是一个算法框架 初始可行解的选择、计算需要确定 “逃离”局部最优陷阱的方法可以自由定义 邻居算法，需要自己确定 算法终止策略

何谓“遗传”？ 它给我们的启发是什么？我们的目标是“搜索”最优解 一个初始种群population 种群中的个体，有强有弱 按照某种“强弱”概率，进行配对，“产生” 下一代 优胜劣汰 为保持种群基因的不断优化而选择和“外族”通婚，以产生基因 突变 突变后的“好”基因将被遗传，“坏”基因将被淘汰 由多个可行解，进行演化，“得到”、“产生”出最优解。 它给我们的启发是什么？我们的目标是“搜索”最优解

遗传算法示例 求解以下二元函数的最大值 F(x,y)=x2+y2 x:{1,2,3,4,5,6,7} y:{1,2,3,4,5,6,7} 个体编号 初始种群(x,y) 个体强弱 1 3,5 34 2 5,3 3 3,4 25 4 7,1 50 初始种群（若干个可行解） {(3,5),(5,3),(3,4),(7,1)} 种群规 模自由定义 评估个体强弱（决定参与遗 传的“个体”） 直接用目标函数进行计算：

选择个体，参与“遗传” 适应率:个体强弱评估结果和种群强弱总和之比例 “轮盘赌”法，选择4个个体 可行解3,4被淘汰，意味着什么？ 个体编号 初始种群(x,y) 个体强弱 1 3,5 34 2 5,3 3 3,4 25 4 7,1 50 总和 143 适应率 0.24 0.17 0.35 选中次数 1 2 可行解3,4被淘汰，意味着什么？

如何进行遗传？ 基因编码：可行解的编码表达 个体编号 初始种群(x,y) 1 3,5 2 5,3 3 3,4 4 7,1 总和 基因编码 011101 101011 011100 111001 个体强弱 34 25 50 143 适应率 0.24 0.17 0.35 1 选中次数 1 2 选择结果 011101 101011 111001 你能想到111001这个个体和011101这个个体如何进行“配对”遗传吗？

交叉配对，产生后代 这里的后代，是什么？ 以某一概率相互交换某两个个体之间的部分染色体 个体编号 选择结果(x,y) 1 3,5 2 5,3 7,1 4 总和 遗传基因 011101 101011 111001 配对情况 1,3 2,4 交叉点位置 13:2 24:4 交叉结果 011001 101001 111101 111011 交叉结果适应度 10 26 74 58 这个后代明显很强

基因变异 对种群中所有个体的基因进行较小概率的改变，产生新个体 继续进行下一轮“遗传”，直到满足结束条件

遗传算法中，solution representation非常关键！

初始种群选择 计算适应度 按概率配对 交叉运算 变异运算 确定下一代

自由参数的考察

自由参数的考察 种群规模： 大/小种群的优劣 30左右？ 初始种群 预计算和随机选择的并举 适应度计算 相对和绝对

自由参数的考察 可行解的表达 变异操作的概率 The choice of a representation of individuals is of the same importance for genetic algorithms as the choice of a neighborhood for local search. 可行解的表达必须支持“交叉”算子的良定义 TSP如果用节点序来表达可行解，必须“去重” 变异操作的概率 The role of mutation in genetic algorithms is similar to the role of randomized deteriorations in simulated annealing. 和基因数量和种群大小相关，较小 遭遇并跳出陷阱的概率

自由参数的考察 子代个体的选择 直接取代 整体取优 终止条件设定 时间（迭代次数） 种群个体的表现 差距不再发生大的变化 种群趋向平稳

总结 解空间的搜索是优化问题的核心价值 模拟退火算法和遗传算法均是局部搜索的优化算法 启发式算法还有n多，你自己都可以设计 自然规律在计算机世界的体现 启发式算法还有n多，你自己都可以设计 规律（自然规律）+规律（算法框架）