智能优化算法.doc

《智能优化算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、智能计算读书报告（二）智能优化算法姓名：XX学号：XXXX班级：XXXX联系方式：XXXXXX一、引言智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适用于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家的经验，理论上可以在一定时间内找到最优解或者近似最优解。所以，智能优化算法是一数学为基础的，用于求解各种工程问题优化解的应用科学，其应用非常广泛，在系统控制、人工智能、模式识别、生产调度、VLSI技术和计算机工程等各个方面都可以看到它的踪影。最优化的核心是模型，最优化方法也是随着模型的变化不断发展起来的，最优化问题就

2、是在约束条件的限制下，利用优化方法达到某个优化目标的最优。线性规划、非线性规划、动态规划等优化模型使最优化方法进入飞速发展的时代。20世纪80年代以来，涌现出了大量的智能优化算法，这些新颖的智能优化算法被提出来解决一系列的复杂实际应用问题。这些智能优化算法主要包括：遗传算法，粒子群优化算法，和声搜索算法，差分进化算法，人工神经网络、模拟退火算法等等。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，并且在很多领域得到了成功地应用。二、模拟退火算法（SA）1.退火和模拟退火模拟退火算法(SimulatedAnnealing，SA)

3、最早的思想是由N.Metropolis等人于1953年提出。1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机

4、器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图2.1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。图2.1模拟退火示意图若J(Y(i+1))>=J(Y(i))(即移动后得到

5、更优解)，则总是接受该移动，若J(Y(i+1))

6、不叫退火了），因此dE/kT<0，所以P(dE)的函数取值范围是(0,1)。随着温度T的降低，P(dE)会逐渐降低。将一次向较差解的移动看做一次温度跳变过程，以概率P(dE)来接受这样的移动。2.Bolzman方程同一温度下，S处在能量小的状态要比处在能量大的状态概率大，若存在E1P2(Tk)若i*表示S中最低能量的状态，是关于温度Tk单调递减的，对Pi(Tk)求对温度的导数，则当Tk→0时，所以：同理，当Tk→0时所以可以总结为能量越低越稳定。3.SA的算法步骤（1）初始化,任选初始解,i∈S,给定初始温

7、度T_0，终止温度T_f，令迭代指标k=0，T_k=T_0。（2）随机产生一个邻域解，j∈N(i)，计算目标值增量△f=f(j)-f(i)。（3）若△f＜0，令i=j，转第（4）步；否则产生这种情况下则令i=j。（4）若达到热平衡（内循环次数大于n(T_k）)，转第（5）步，否则转（2）。（5）k=k+1,则降低T_k，若T_k＜T_f，则停止，否则转第（2）步。程序流程图如下所示：图2.2SA算法程序流程图三、禁忌搜索（TS）禁忌搜索的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟

8、。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索