智能优化算法.docx
23页
智能计算读书报告（二）智能优化算法姓名：XX学号：XXXX班级：XXXX联系方式：XXXXXX一、引言智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且合用于并行解决的算法这种算法一般具有严密的理论根据，而不是单纯凭借专家的经验，理论上可以在一定期间内找到最优解或者近似最优解因此，智能优化算法是一数学为基本的，用于求解多种工程问题优化解的应用科学，其应用非常广泛，在系统控制、人工智能、模式辨认、生产调度、VLSI技术和计算机工程等各个方面都可以看到它的踪影最优化的核心是模型，最优化措施也是随着模型的变化不断发展起来的，最优化问题就是在约束条件的限制下，运用优化措施达到某个优化目的的最优线性规划、非线性规划、动态规划等优化模型使最优化措施进入飞速发展的时代20世纪80年代以来，涌现出了大量的智能优化算法，这些新颖的智能优化算法被提出来解决一系列的复杂实际应用问题这些智能优化算法重要涉及：遗传算法，粒子群优化算法，和声搜索算法，差分进化算法，人工神经网络、模拟退火算法等等这些算法独特的长处和机制，引起了国内外学者的广泛注重并掀起了该领域的研究热潮，并且在诸多领域得到了成功地应用。
二、模拟退火算法（SA）1. 退火和模拟退火模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域它是基于Monte-Carlo迭代求解方略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性模拟退火算法从某一较高初温出发，随着温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目的函数的全局最优解，即在局部最优解能概率性地跳出并最后趋于全局最优模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号解决等领域模拟退火算法是通过赋予搜索过程一种时变且最后趋于零的概率突跳性，从而可有效避免陷入局部极小并最后趋于全局最优的串行构造的优化算法模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素模拟退火算法以一定的概率来接受一种比目前解要差的解，因此有也许会跳出这个局部的最优解，达到全局的最优解以图2.1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。
也许通过几次这样的不是局部最优的移动后会达到D点，于是就跳出了局部最大值A图2.1 模拟退火示意图若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动，若J( Y(i+1) )< J( Y(i) ) (即移动后的解比目前解要差)，则以一定的概率接受移动，并且这个概率随着时间推移逐渐减少（逐渐减少才干趋向稳定）这里的“一定的概率”的计算参照了金属冶炼的退火过程，这也是模拟退火算法名称的由来 根据热力学的原理，在温度为T时，浮现能量差为dE的降温的概率为P(dE)，表达为：P(dE) = exp( dE/(kT) )其中k是一种常数，exp表达自然指数，且dE<0这条公式说白了就是：温度越高，浮现一次能量差为dE的降温的概率就越大；温度越低，则浮现降温的概率就越小又由于dE总是不不小于0（否则就不叫退火了），因此dE/kT < 0 ，因此P(dE)的函数取值范畴是(0,1) 随着温度T的减少，P(dE)会逐渐减少将一次向较差解的移动看做一次温度跳变过程，以概率P(dE)来接受这样的移动2. Bolzman方程同一温度下，S 处在能量小的状态要比处在能量大的状态概率大，若存在E 1
3. SA的算法环节（1）初始化,任选初始解, i∈S,给定初始温度T_0，终结温度T_f，令迭代指标k=0，T_k=T_02）随机产生一种邻域解，j∈N(i)，计算目的值增量△f=f(j)-f(i)3）若△f＜0，令i=j，转第（4）步；否则产生这种状况下则令i=j4）若达到热平衡（内循环次数不小于n(T_k）)，转第（5）步，否则转（2）5）k=k+1,则减少T_k，若T_k＜T_f，则停止，否则转第（2）步程序流程图如下所示：图2.2 SA算法程序流程图三、禁忌搜索（TS）禁忌搜索的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐渐寻优算法，是对人类智力过程的一种模 拟TS算法通过引入一种灵活的存储构造和相应的禁忌准则来避免迂回搜索，并通过鄙视准则来赦免某些被禁忌的优良状态，进而保证多样化的有效摸索以最后实 现全局优化相对于模拟退火和遗传算法，TS是又一种搜索特点不同的 meta-heuristic算法迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域获得了很大的成功，近年来又在函数全局 优化方面得到较多的研究，并大有发展的趋势。
禁忌搜索算法是组合优化算法的一种，是局部搜索算法的扩展禁忌搜索算法是人工智能在组合优化算法中的一种成功应用禁忌搜索算法的特点是采用了禁忌技术所谓禁忌就是严禁反复前面的工作禁忌搜索算法用一种禁忌表记录下已经达到过的局部最长处，在下一次搜索中，运用禁忌表中的信息不再或有选择地搜索这些点禁忌搜索算法实现的技术问题是算法的核心禁忌搜索算法波及侯选集合、禁忌对象、评价函数、特赦规则、记忆频率信息等概念TS算法环节：（1） 选一种初始点x∈X,令x*=x，T=∅，渴望水平A(s,x)=C(x*)，迭代指标k=0；（2） 若S(x)-T=∅停止，否则领k=k+1；若k＞NG（其中NG为最大迭代次数）停止；（3）若C(sl(x))-Opt{C(s(x)),s(x)∈S(x)},若C(sl(x))＜A(s,x)，令x=sl(x),转（5）；（4）若C(sk(x))=Opt{C(s(x)),s(x)∈S(x)-T},令x=sk(x)；（5）若C(x)＜C(x*),令x*=x, C(x*)= C(x)，A(s,x)= C(x*)；（6）更新T表，转步（2）组合优化是TS算法应用最多的领域置换问题，如TSP、调度问题等，是一大批组合优化问题的典型代表，在此用它来解释简朴的禁忌搜索算法的思想和操作。
对于 n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数字，而禁忌搜索则但愿仅通过摸索少数解来得到满意的优化解一方面，我们对置换问题定义一种邻域搜索构造，如互换操作（SWAP），即随机互换两个点的位置，则每个状态的邻域解有Cn2=n（n一1）/2个称从一种状态转移到其邻域中的另一种状态为一次移动（move），显然每次移动将导致适配值（反比于目的函数值）的变化另一方面，我们采用一种存储构造来辨别移动的属性，即与否为禁忌“对象”在如下示例中：考虑7元素的置换问题，并用每一状态的相应21个邻域解中最优的5次移动（相应最佳的5个适配值）作为候选解；为一定限度上避免迂回搜索，每个被采纳的移动在禁忌表中将滞留3步（即禁忌长度），即将移动在如下持续3步搜索中将被视为禁忌对象；需要指出的是，由于目前的禁忌对象相应状态的适配值也许较好，因此在算法中设立判断，若禁忌对象相应的适配值优于“ best so far”状态，则忽视其禁忌属性而仍采纳其为目前选择，也就是一般所说的鄙视准则（或称特赦准则）可见，简朴的禁忌搜索是在领域搜索的基本上，通过设立禁忌表来禁忌某些已经历的操作，并运用鄙视准则来奖励某些优良状态，其中领域构造、候选解、禁忌长度、禁忌对象、鄙视准则、终结准则等是影响禁忌搜索算法性能的核心。
需要指出的是：（1） 一方面，由于TS是局部领域搜索的一种扩大，因此领域构造的设计很核心，它决定了目前解的领域解的产生形式和数目，以及各个解之间的关系2） 另一方面，出于改善算法的优化时间性能的考虑，若领域构造决定了大量的领域解（特别对大规模问题，如TSP的SWAP操作将产生Cn2个领域解），则可以仅尝试部分互换的成果，而候选解也仅取其中的少量最佳状态3） 禁忌长度是一种很重要的核心参数，它决定禁忌对象的任期，其大小直接进而影响整个算法的搜索进程和行为同步，以上示例中，禁忌表中禁忌对象的替代是采用FIFO方式（不考虑鄙视准则的作用），固然也可以采用其她方式，甚至是动态自适应的方式4） 鄙视准则的设立是算法避免遗失优良状态，鼓励对优良状态的局部搜索，进而实现全局优化的核心环节5） 对于非禁忌候选状态，算法忽视它与目前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种拟定性方略）6） 为了使算法具有优良的优化性能或时间性能，必须设立一种合理的终结准则来结束整个搜索过程此外，在许多场合禁忌对象的被禁次数（frequency）也被用于指引搜索，以获得更大的搜索空间。
禁忌次数越高，一般可觉得浮现循环搜索的概率越大四、遗传算法遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的措施遗传算法是从代表问题也许潜在的解集的一种种群（population）开始的，而一种种群则由通过基因（gene）编码的一定数目的个体(individual)构成每个个体事实上是染色体(chromosome)带有特性的实体染色体作为遗传物质的重要载体，即多种基因的集合，其内部体现（即基因型）是某种基因组合，它决定了个体的形状的外部体现，如黑头发的特性是由染色体中控制这一特性的某种基因组合决定的因此，在一开始需要实现从体现型到基因型的映射即编码工作由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
这个过程将导致种群像自然进化同样的后生代种群比前代更加适应于环境，末代种群中的最优个体通过解码（decoding），可以作为问题近似最优解1. 基本思路图4.1 遗传算法基本思路遗传算法的基本运算过程如下：(1) 初始化：设立进化代数计数器t=0，设立最大进化代数T，随机生成M个个体作为初始群体P(0)2) 个体评价：计算群体P(t)中各个个体的适应度3) 选择运算:将选择算子作用于群体选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代选择操作是建立在群体中个体的适应度评估基本上的4) 交叉运算：将交叉算子作用于群体遗传算法中起核心作用的就是交叉算子5) 变异运算：将变异算子作用于群体即是对群体中的个体串的某些基因座上的基因值作变动群体P(t)通过选择、交叉、变异运算之后得到下一代群体P(t+1)6) 终结条件判断:若t=T,则以进化过程。
