第二十三章 现代优化算法.doc

第二十三章 现代优化算法 现代优化算法是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）问题等效果很好。 §1 模拟退火算法 1.1 算法简介 模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。 如果用粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了退火过程。假设材料在状态i之下的能量为E(i)，那么材料在温度T时从状态i进入状态j就遵循如下规律： （1）如果E(j)≤E(i)，接受该状态被转换。 （2）如果E(j)gt;E(i)，则状态转换以如下概率被接受： E(i)??E(j)KT e 其中K是物理学中的波尔兹曼常数，T是材料温度。 在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i的概率满足波尔兹曼分布： E(i)??KTe P(x=i)= TE(j)??KTe∑j∈S其中x表示材料当前状态的随机变量，S表示状态空间集合。 显然 E(i)??KTe1 lim= E(j)T→∞??|S|KTe∑j∈S -271- 其中|S|表示集合S中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时， E(i)??EE(i)??Eminmin????KTKTeelim=lim E(j)??EE(j)??EE(j)??EminminminT→0T→0??????KTKTKTee+e∑∑∑j∈Sj∈Sj??SminminE(i)??Emin1????KT 若i∈Se??min|S| =lim= ??minE(j)??EminT→0????KTe0 其它∑??j∈Smin其中E=minE(j)且S={i|E(i)=E}。 minminminj∈S上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。 假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。 +考虑这样一个组合优化问题：优化函数为f:x→R，其中x∈S，它表示优化+问题的一个可行解，R={y|y∈R,ygt;0}，S表示函数的定义域。N(x)??S表示x的一个邻域集合。 首先给定一个初始温度T和该优化问题的一个初始解x(0)，并由x(0)生成下一个0解x#039;∈N(x(0))，是否接受x#039;作为一个新解x(1)依赖于下面概率： ??1 若f(x#039;)lt;f(x(0))??P(x(0)→x=f(x#039;)??f(x(0))#039;) ???? T0??e其它??换句话说，如果生成的解x#039;的函数值比前一个解的函数值更小，则接受x(1)=x#039;作为f(x#039;)??f(x(0))??T0一个新解。否则以概率e接受x#039;作为一个新解。 泛泛地说，对于某一个温度T和该优化问题的一个解x(k)，可以生成x#039;。接受x#039;i作为下一个新解x(k+1)的概率为： ??1 若f(x#039;)lt;f(x(k))?? P(x(k)→x=f(x#039;)??f(x(k))#039;) （1）