第二十三章现代优化算法简介汇编.doc

第二十三章 现代优化算法简介 §1 现代优化算法简介 现代优化算法是80年代初兴起的启发式算法。这些算法包括禁忌有哪些信誉好的足球投注网站（tabu search），模拟退火（simulated annealing），遗传算法（genetic algorithms），人工神经网络（neural networks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目标－求NP-hard组合优化问题的全局最优解。虽然有这些目标，但NP-hard理论限制它们只能以启发式的算法去求解实际问题。 启发式算法包含的算法很多，例如解决复杂优化问题的蚁群算法（Ant Colony Algorithms）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。 现代优化算法解决组合优化问题，如TSP（Traveling Salesman Problem）问题，QAP（Quadratic Assignment Problem）问题，JSP（Job-shop Scheduling Problem）问题等效果很好。 本章我们只介绍模拟退火算法，初步介绍一下蚁群算法，其它优化算法可以参看相关的参考资料。 §2 模拟退火算法 2.1 算法简介 模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。 如果用粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了退火过程。假设材料在状态之下的能量为，那么材料在温度时从状态进入状态就遵循如下规律： （1）如果，接受该状态被转换。 （2）如果，则状态转换以如下概率被接受： 其中是物理学中的波尔兹曼常数，是材料温度。 在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态的概率满足波尔兹曼分布： 其中表示材料当前状态的随机变量，表示状态空间集合。 显然 其中表示集合中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时， 其中且。 上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。 假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。 考虑这样一个组合优化问题：优化函数为，其中，它表示优化问题的一个可行解，，表示函数的定义域。表示的一个邻域集合。 首先给定一个初始温度和该优化问题的一个初始解，并由生成下一个解，是否接受作为一个新解依赖于下面概率： 换句话说，如果生成的解的函数值比前一个解的函数值更小，则接受作为一个新解。否则以概率接受作为一个新解。 泛泛地说，对于某一个温度和该优化问题的一个解，可以生成。接受作为下一个新解的概率为： （1） 在温度下，经过很多次的转移之后，降低温度，得到。在下重复上述过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。 我们注意到，在每个下，所得到的一个新状态完全依赖于前一个状态，可以和前面的状态无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个状态生成的概率，在中是均匀分布的，且新状态被接受的概率满足式（1），那么经过有限次的转换，在温度下的平衡态的分布由下式给出： （2） 当温度降为0时，的分布为： 并且 这说明如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率1被找到。因此可以说模拟退火算法可以找到全局最优解。 在模拟退火算法中应注意以下问题： （1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的有哪些信誉好的足球投注网站算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。 （2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续次的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个