算法大全第23课时__现代优化算法

《算法大全第23课时__现代优化算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二十三章现代优化算法现代优化算法是80年代初兴起的启发式算法。这些算法包括禁忌搜索（tabusearch），模拟退火（simulatedannealing），遗传算法（geneticalgorithms），人工神经网络（neuralnetworks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目标－求NP-hard组合优化问题的全局最优解。虽然有这些目标，但NP-hard理论限制它们只能以启发式的算法去求解实际问题。启发式算法包含

2、的算法很多，例如解决复杂优化问题的蚁群算法（AntColonyAlgorithms）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。现代优化算法解决组合优化问题，如TSP（TravelingSalesmanProblem）问题，QAP（QuadraticAssignmentProblem）问题，JSP（Job-shopSchedulingProblem）问题等效果很好。§1模拟退火算法1.1算法简介模拟退火算法得益于材料的统计力学的研究成果。统

3、计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。如果用粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了退火过程。假设材料在状态i之下的能量为E(i)，那么材料在温度T时从状态i进入状态j就遵循如下规律：（1）如果E(j)≤E(i)，接受该状态被转换。（2）如果E(j)>

4、E(i)，则状态转换以如下概率被接受：E(i)−E(j)eKT其中K是物理学中的波尔兹曼常数，T是材料温度。在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i的概率满足波尔兹曼分布：E(i)−eKTP(x=i)=TE(j)−∑eKTj∈S其中x表示材料当前状态的随机变量，S表示状态空间集合。显然E(i)−eKT1lim=T→∞−E(j)

5、S

6、∑eKTj∈S-271-其中

7、S

8、表示集合S中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时，E(i)−EminE(i)−Emin−−

9、eKTeKTlim=limT→0−E(j)−EminT→0−E(j)−Emin−E(j)−Emin∑eKT∑eKT+∑eKTj∈Sj∈Sminj∉SminE(i)−Emin1−⎧eKT若i∈S⎪min=limE(j)−Emin=⎨

10、Smin

11、T→0−∑eKT⎪⎩0其它j∈Smin其中E=minE(j)且S={i

12、E(i)=E}。minminminj∈S上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方

13、法。+考虑这样一个组合优化问题：优化函数为f:x→R，其中x∈S，它表示优化+问题的一个可行解，R={y

14、y∈R,y>0}，S表示函数的定义域。N(x)⊆S表示x的一个邻域集合。首先给定一个初始温度T和该优化问题的一个初始解x(0)，并由x(0)生成下一个0解x'∈N(x(0))，是否接受x'作为一个新解x(1)依赖于下面概率：⎧1若f(x')

15、f(x(0))−一个新解。否则以概率eT0接受x'作为一个新解。泛泛地说，对于某一个温度T和该优化问题的一个解x(k)，可以生成x'。接受x'i作为下一个新解x(k+1)的概率为：⎧1若f(x')

16、依赖于前一个状态ix(k)，可以和前面的状态x(0),L,x(k−1)无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个状态x(k)生成x'的概率，在N(x(k))中是均匀分布的，且新状态x'被接受的概率满足式（1），那么经过有限次的转换，在温度T下的平衡态x的分布由下式给出：ii-