智能计算读书报告（二）智能计算读书报告（二）智能优化算法智能优化算法姓名：姓名：XX学号：学号：XXXX班级：班级：XXXX联系方式：联系方式：XXXXXX一、引言一、引言智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适用于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家的经验，理论上可以在一定时间内找到最优解或者近似最优解。所以，智能优化算法是一数学为基础的，用于求解各种工程问题优化解的应用科学，其应用非常广泛，在系统控制、人工智能、模式识别、生产调度、VLSI 技术和计算机工程等各个方面都可以看到它的踪影。最优化的核心是模型，最优化方法也是随着模型的变化不断发展起来的，最优化问题就是在约束条件的限制下，利用优化方法达到某个优化目标的最优。线性规划、非线性规划、动态规划等优化模型使最优化方法进入飞速发展的时代。20 世纪 80 年代以来，涌现出了大量的智能优化算法，这些新颖的智能优化算法被提出来解决一系列的复杂实际应用问题。这些智能优化算法主要包括：遗传算法，粒子群优化算法，和声搜索算法，差分进化算法，人工神经网络、模拟退火算法等等。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，并且在很多领域得到了成功地应用。二、模拟退火算法（二、模拟退火算法（SASA）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) )P 2 (T k )若 i * 表示 S 中最低能量的状态， 是关于温度 T k 单调递减的，对 P i (T k ) 求对温度的导数，则当 T k 0 时，所以：同理，当 T k 0 时所以可以总结为能量越低越稳定。3. SA 的算法步骤的算法步骤（1）初始化,任选初始解, iS,给定初始温度 T_0，终止温度 T_f，令迭代指标 k=0，T_k=T_0。（2）随机产生一个邻域解，jN(i)，计算目标值增量f=f(j)-f(i)。（3）若f0，令 i=j，转第（4）步；否则产生这种情况下则令 i=j。（4）若达到热平衡（内循环次数大于 n(T_k）)，转第（5）步，否则转（2）。（5）k=k+1,则降低 T_k，若 T_kT_f，则停止，否则转第（2）步。程序流程图如下所示：图 2.2 SA 算法程序流程图三、禁忌搜索（三、禁忌搜索（TSTS）禁忌搜索的思想最早由 Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模 拟。TS 算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实 现全局优化。相对于模拟退火和遗传算法，TS 是又一种搜索特点不同的 meta-heuristic算法。迄今为止，TS 算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局 优化方面得到较多的研究，并大有发展的趋势。禁忌搜索算法是组合优化算法的一种，是局部搜索算法的扩展。禁忌搜索算法是人工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌对象、评价函数、特赦规则、记忆频率信息等概念。TS 算法步骤：（1） 选一个初始点 xX,令 x*=x，T=，渴望水平 A(s,x)=C(x*)，迭代指标 k=0；（2） 若 S(x)-T=停止，否则领 k=k+1；若 kNG（其中 NG 为最大迭代次数）停止；（3）若 C(sl(x)-OptC(s(x),s(x)S(x),若 C(sl(x)A(s,x)，令 x=sl(x),转（5）；（4）若 C(sk(x)=OptC(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,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。算法程序流程图如下所示：图 4.2 遗传算法程序流程图2. 遗传算法的优势和特点遗传算法的优势和特点(1) 自组织、自适应和自学习性在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。(2) 本质并行性 (3) 不需求导只需目标函数和适宜度函数(4) 概率转换规则强调概率转换规则，而不是确定的转换规则五、五、遗传算法遗传算法工程技术与科学研究中的最优化求解问题十分普遍，在求解过程中，人们创造与发现了许多优秀实用的算法。群智能算法是一种新兴的演化计算技术，已成为越来越多研究者的关注焦点，智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化是智能优化的一个重要分支，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为，利用群体中个体之间的信息交互和合作实现寻优。1. 粒子群算法粒子群算法粒子群优化算法（PSO）是一种进化计算技术（e