李金屏 济南大学信息科学与工程学院 模式识别与智能系统研究所 (1st version in )

Presentation on theme: "李金屏 济南大学信息科学与工程学院 模式识别与智能系统研究所 (1st version in )"— Presentation transcript:

1 李金屏 济南大学信息科学与工程学院 模式识别与智能系统研究所 (1st version in 2002.9) 2006.9
现代优化算法 李金屏 济南大学信息科学与工程学院 模式识别与智能系统研究所 (1st version in )

2 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法&进化计算 现代优化算法再述 课题组的工作
其它问题： 计算复杂性； 邻域概念； NP, NP-C 和NP-hard； Markov过程； 人工生命，蚂蚁算法，免疫算法，混沌优化算法，memetic算法等。 其它问题。 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法&进化计算 现代优化算法再述 课题组的工作 39

3 优化算法简介——概念、基本形式 什么是优化？就是从各种方案中选取一个最好的。从数学角度看，优化理论就是研究如何在状态空间中寻找到全局最优点。
比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他掺杂物比例。学校课程表排课问题、售票员上岗问题、公司内部人员安排出效益等。降低成本、提高效益是问题的关键。 一般的优化具有下面形式： minf (x1, x2, …, xn) s.t. g(x)  0，xD 其中x1, x2, …, xnΩ（即问题的可行域，代表问题参数的选择范围），即minf (X)，其中XΩ（矢量形式）。f(x)是决策问题的数学模型，也是决策问题的目标函数，g(x) 0是决策问题的约束条件，D是决策问题的定义域（可行域）。问题归结为求极值。极值点非常多，需要找到全局最小点。 注：求问题的最大和最小是同一个问题，算法完全一样。 39

4 优化算法简介——优化算法分类 如果决策问题是一个凸问题，可以利用线性规划、非线性规划等求解。然而大量的实际问题是非凸问题，需要在大量的局部极优解中寻找全局最优解。此时，决策变量x是否连续，数学模型f(x)是否具有解析表达式，对于求解难度会有不同的影响。 这是一个全局寻优问题。很多方法讨论的是如何在一个极值点附近搜索极值点。一般情况下，利用穷举的方法是不可能的。 习惯上，将优化算法分为两类：局部优化算法和全局性优化算法。前者可以称为经典优化算法，已经得到了人们广泛深入的研究。目前，运筹学（确定论方法）主要包括这些方面的内容，线性规划、整数规划、0–1规划、非线性规划、排队论、决策论。后者习惯上称为现代优化算法，是20世纪80年代兴起的新型全局性优化算法，主要包括禁忌搜索、模拟退火、遗传算法等，其主要应用对象是优化问题中的难解问题，即NP–hard问题 39

5 优化算法简介——局部优化、全局优化 有文献将神经网络也列入现代优化算法的范畴，从全局优化的角度看，这并不适宜，因为神经网络的优化算法本质上是局部优化算法和全局优化算法的综合应用。 局部优化算法主要用于解决凸问题或单峰问题，通常使用确定性搜索策略，比如单纯形法、梯度下降法、爬山法、贪心法等，其基本思想是在状态转移过程中，只接受更好的状态，拒绝恶化的状态。 全局性优化算法主要用于求解非凸问题或多峰问题，通常使用概率性搜索策略，即状态转移规则，这是由于实际的全局性优化问题通常没有解析表达式或者解析表达式非常复杂难以进行理论分析。其基本思想是在可行域中从给定的一个或多个随机初始点出发进行搜索，利用适当的状态转移规则和合理的概率性状态接收规则搜索新的更优点，在确定的时间或搜索次数之内停止算法。 39

6 优化算法简介——二者需要结合 局部优化算法由于易于陷入局部极优解而无法用于解决多峰问题；同时，全局性优化算法采用适当的状态转移规则和概率性状态接受规则，能够避免过早地陷入局部极优解从而搜索到全局性最优解。 通常，局部优化算法能够快速地收敛到局部极优解，而全局性优化算法通过概率搜索可以获得在概率意义上尽可能好的全局性最优解区域，但是其局部极优点搜索能力较低。这是全局搜索算法和局部搜索算法之间的固有矛盾。对此人们进行了多种研究。基本解决方法在于二者的结合，即利用全局性优化算法在整个可行域中搜索最优区域，利用局部搜索算法搜索最优区域中的最优解。 Memetic算法就是全局性搜索和局部性搜索相结合的算法的总称。又可以称为杂和优化算法 (Hybrid Optimization Algorithm)。 39

7 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作 39

8 正交试验法 在工农业生产及科学实验中，为了试制新产品，改革工艺，寻找优良的生产条件，需要安排一系列的实验。全面实验成本很高，而且往往做不到。因此，需要进行部分试验。正交试验法就是一种实际中广泛使用的部分试验法，又叫正交设计法或正交优化法，即通过少数次试验找到最好的或者较好的实验条件。其中的决策变量和取值分别叫做因素和水平。寻优时，先确定影响决策目标的因素和水平，再选择适当的正交表，即可按正交表安排试验，最后分析试验的结果和发现最佳的水平。 39

9 正交试验法 正交表的形式为Ln(t1t2…tm)，简记为Ln(tm)，其中n为试验数，m为因素数，ti为水平数。正交设计法能够确保决策变量具有最佳的散布性和代表性，因此获得的最佳水平应该具有相当高的满意度。 实际上，正交试验法获得的最佳结果优于总体试验结果的n/(n+1)，劣于总体试验结果的1/(n+1)，具有良好的全局最优性。该算法的另外一个最大优势在于简单易学，一般文化水平的人（比如初中以上）经过几天时间就可以掌握，因此该算法具有极其广泛的使用范围。其难点在于特定正交表的构造，人们正深入研究各种特殊正交表的构造方法。 39

10 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作 39

11 TABU禁忌搜索算法 禁忌搜索算法（tabu search） 是局部邻域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用。Glover在1986年首次提出这一概念，进而形成一套完整算法。 禁忌，就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足，采用一个禁忌表记录已经达到过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或者有选择地搜索这些点，以此来跳出局部最优点。 Tabu算法由几个基本要素的组合：邻域，Tabu表及评价函数。邻域与一般优化技术中的定义一致；Tabu表是一个或数个数据序列，是对先前的数步搜索所作的记录，记录的方式有很多，记录的长度也是可变的，选取的好坏直接影响算法的效率；评价函数通常就是问题的目标函数或它的某种变换形式，用于对一个移动作出评价。由Tabu表和评价函数可以构造一种Tabu条件，若新点满足Tabu条件则接受，否则拒绝，直至迭代终止。 39

12 TABU禁忌搜索算法 Tabu算法被认为是人工智能在组合优化中的成功应用，但是仍有很多技术的细节问题有待讨论。如参数的选择问题，该问题包括禁忌对象及其长度、候选集合的确定等。另外还涉及到评价函数、特赫规则、终止规则等的合理确定。 在提高搜索效率方面，文献[*]针对调度问题提出一种变邻域结构的禁忌搜索算法，使邻域结构随算法的进程改变，邻域规模小，并且保持了可达性；在算法的结合方面，有将禁忌搜索和遗传算法相结合，构造禁忌遗传算法，主要是利用禁忌搜索的以下特点来改善遗传算法：即Tabu搜索能有效利用全局信息、搜索过程中的获得信息和能够跳出局部最优点。 [*]孙元凯，刘民，吴澄。变邻域结构Tabu搜索算法及其在Job Shop调度问题上的应用。电子学报，2001,29(5), 。 39

13 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作 39

14 模拟退火算法 模拟退火算法（simulated annealing algorithm, SAA）是一种重要的全局性启发式概率搜索算法，其物理背景是固体的退火过程。 历史上，两个人物对于SAA的发展起了关键性的作用，他们分别是N. Metropolis和S. Kirkpatrick。 在利用Monte Carlo方法模拟恒定温度下固体达到热平衡态过程的研究中，1953年Metropolis提出了重要性采样准则，即对于处在微观状态 i 的固体系统施加一个随机扰动，使其状态变为j。 设与状态i、j对应的固体系统能量分别为Ei、Ej。则固体系统能否由状态 i 迁移到新的状态j取决于Ei、Ej之间的关系：当Ej≤Ei时，系统迁移到新的状态；当Ej>Ei时，系统将以如下概率迁移到新的状态 39

15 模拟退火算法 1 Ej ≤ Ei. 即 else 在大量迁移之后，系统趋于能量较低的平衡态，其微观状态的概率密度分布趋于Gibbs正则分布。
1982年，Kirkpatrick将退火思想首先引入求解组合优化问题，提出了SAA。引入一个温度参数T。开始时，取T为一个较大的数值，此时状态转移比较自由。随着温度降低，状态转移逐渐困难，最后原则上应该收敛到全局最优点。 目前，模拟退火算法已经广泛地用于求解TSP、VLSI电路设计等NP–完全问题。 39

16 模拟退火算法 我国第一部系统讨论模拟退火算法的中文专著《非数值并行算算法——模拟退火算法》比较详细地讨论了模拟退火算法的数学和物理背景、理论基础以及实现形式，介绍了1994年以前国内外一些学者在理论和应用上的研究成果。 这些成果主要是针对模拟退火算法性能的提高，如怎样控制冷却进度表（cooling schedule）参数（即初始温度、降温策略、温度终值准则、Markov链长），怎样实现模拟退火算法的并行运算，怎样进一步改进模拟退火算法等。 这些改进主要包括：选取合适的初始温度、最优保留策略、与局部搜索相结合、回火退火法等。需要说明，文献中的局部搜索法实质上仍然是随机搜索，只是仅接受优化解，不接受恶化解。 近些年来，不少学者对于模拟退火算法进行了深入的研究和改进。 包括：讨论模拟退火与传统局部优化算法如单纯形法、Powell方法等的结合[7]，研究邻域结构与选取状态转移随机步长方法以及相应的降温方案，如何采取合适的退火终止条件等。 39

17 模拟退火算法 Metropolis规则 Markov链长 计算 冷却进度表 基本算法（PASCAL伪码）：
Procedure SIMULATED ANNEALING; begin INITIALIZE (i0, T0, L0); k:=0; i:=i0; repeat for l:=1 to Lk do GENERATE (j from Si) if f(j) ≤ f(i) then i:=j else if exp[(f(i)—f(j))/Tk] >random[0,1] then i:=j end; k:=k+1; CALCULATE-LENGTH(Lk); CALCULATE-CONTROL(Tk); until stopcriterion 模拟退火算法 Metropolis规则 Markov链长 计算 冷却进度表 39

18 模拟退火算法 最初路径 算法结果 目前最好结果 39

19 模拟退火算法 一些文献： 1、康立山，谢云，尤矢勇等。非数值并行算法——模拟退火算法。北京：科学出版社，1998年。
2、王卓鹏，高国成，杨为平。一种改进的快速模拟退火组合优化法。系统工程理论与实践，1999，(2): 73–76。 3、赵玉清，余志军。加速全局优化–鲍威尔法和模拟退火法的组合。电子学报，1998，26(9): 75–77。 4、杨若黎，顾基发。一种高效的模拟退火全局优化算法。系统工程理论与实践，1997，(5): 29–35。 39

20 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作 39

21 遗传算法 Darwin 的物种进化的主要思想是自然选择(Natural selection)。生物通过竞争来进化，以适应环境。生物通过遗传(Heredity)、变异(Mutation)等过程实现进化。遗传和变异的物质基础是染色体(Chromosome)。染色体又是由DNA 和蛋白质组成的。基因中保留着遗传物质。通过基因的复制(production)、交叉(crossover)和变异(mutation)实现生物的性状的变异和遗传。 标准遗传算法的基本框架是由Holland于20世纪60年代提出的，它使用二进制编码，采用赌轮选择和随机配对，关键是编码。这是一类模拟生物进化过程的全局性优化算法，其搜索效率取决于搜索策略或状态转移策略、编码策略、运行参数的合理配置等方面。对于具有下面数学结构的研究对象 min（或max）f (x)，s.t. g(x)  0，xD 遗传算法可以具有较好的搜索效果。 39

22 遗传算法 基本思路： 第一步：建立研究对象的数学结构模型，确定目标函数类型（即求目标函数的最大值还是最小值?）。
第二步：确定表示可行解的染色体编码方法，即确定个体基因型X及遗传算法的搜索空间。 第三步：确定解码方法，即确定由个体基因型X到相应表现型的对应关系或转换关系。 39

23 遗传算法 基本思路： 第四步：设计遗传算子，包括选择算子、交叉算子、变异算子等的具体操作方法。
第五步：确定个体适应度的量化评价方法，即制定由目标函数 f(x) 到个体适应度的转换规则。 第六步：确定遗传算法的有关运行参数。包括编码串长度l（对于二进制编码）、交叉概率Pc、变异概率Pm、种群规模M、终止代数T等运行参数的设置。 第七步：设计遗传算法程序，其中使用了最优保留策略。 39

24 遗传算法 为了提高其搜索效率，可以在三个方面提出改进措施：
1) 采用更好的搜索策略。主要包括：精英策略（elitist strategy）；构造与模拟退火算法、局部搜索算法如最速下降法等相结合的混和遗传算法（hybrid genetic algorithm）；通过改造模式定理和引入半序关系将所有模式构成一个半序格，从而将人工智能理论中的状态空间搜索算法如A算法与遗传算法相结合而提出的统计遗传算法（statistical genetic algorithm）；基于家族优生学原理构成两两结合的家族竞争机制，通过引入正交设计法构造出“正交交配”算子，从而在每个家庭内部形成局部竞争环境的进化算法；利用小生境技术、聚类分析或狭义遗传算法而提出的分区域搜索遗传算法等。 39

25 遗传算法 2) 采用更加合理的编码策略。如采用十进制编码，多维实数编码，或根据模式定理将二进制编码的低阶、高平均适应度的长定义距模式转换为短定义距模式等。 3)合理配置运行参数。遗传算法的求解效率在很大程度上取决于编码串长度l（对于二进制编码）、种群规模M、交叉概率Pc、变异概率Pm、终止代数T、适应度函数f (M)等运行参数的设置，当然与具体的选择算子也有很大关系，这在搜索策略中已经有一定体现。 除了种群规模和终止代数之外，人们对于染色体编码、交叉和变异概率、适应度函数等进行了深入广泛的讨论。 39

26 遗传算法 编码串长度l直接决定问题的求解精度。选择策略、交叉算子和变异算子对于种群早熟、收敛等有重大影响，不少工作对此进行了有益的探讨。适应度函数f (M)是遗传算法的一个瓶颈，人们针对不同问题提出了许多不同的适应度函数定义。 最近有文献研究了遗传算法的一些统计性质，提出进化截止代数和平均截止代数的概念，指出进化截止代数分布呈现典型的Г分布，还研究了遗传算法的优化效率。 这种研究对于深刻理解遗传算法非常有益。 事实上，进化截止代数分布之中蕴含着许多丰富的知识，比如，平均进化截止代数、成功率等主要依赖于哪些因素？种群规模M、研究对象数学结构的极值个数、极值大小分布和极值区域半径分布、染色体串长l等在进化截止代数分布中主要起到什么作用？ 39

27 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作 39

28 现代优化算法——一般性描述 ——全局性优化理论的一般性描述
首先，需要确定的是状态的表示，即决策变量x的编码问题。通常x是以数值方式编码比如浮点数，也有二进制方式，还有符号编码如字母等。实际上编码方式不应该影响搜索的结果，只要x与其编码具有一一对应的关系，如浮点数编码与二进制编码之间就存在明确的一一对应的关系。原码编码采用决策变量本身作为状态参量，也是一种编码方式，只不过我们已经习以为常了。选择不同的编码方式对于优化效率具有不同的影响。我们采用C(x)表示的x编码，称为个体。 39

29 现代优化算法——一般性描述 ——全局性优化理论的一般性描述 两种搜索方式：单点法和多点法。
单点法是一种串行方式，即从一个初始状态（单个个体）出发，按照某种方式转移状态进行全局优化，这种方式通常要消耗较多机时； 多点法是一种并行方式，即从可行域的多个初始状态（多个个体）同时进行搜索寻找全局最优解，但是空间开销大。 根据各态历经假设，理论上二者可以具有相同的搜索效果。事实上，单CPU情况下的单点法和多点法并没有本质性的区别。 39

30 现代优化算法——一般性描述 ——全局性优化理论的一般性描述 两种搜索策略：确定性和概率性。
由于许多实际问题的决策变量不连续，或者没有解析表达式或者解析表达式比较复杂致使无法进行理论分析，而且大多数问题的极值数目未知，无法提供全局性搜索的确定性信息，因此通常采用概率性搜索策略，包括：1. 状态转移规则，2. 状态接受规则。 状态转移规则研究从当前状态C(x)如何转移到下一状态C(x’)，即C(x)+C  C(x’)，C表示状态转移量，需要根据决策问题的数学结构来确定。这是因为C反映f(x)的邻域结构，合理的C应该保证概率性搜索的状态具有最大代表性。这就要求C符合最佳概率分布。 39

31 现代优化算法——一般性描述 ——全局性优化理论的一般性描述
状态接受规则研究如何接受按照状态转移规则获得的新状态，即确定性接受还是概率性接受。确定性方式仍然是只接受更好的结果，拒绝恶化的结果。通常使用概率性方式，也有两种做法：一种是更好结果肯定接受，恶化结果按照一定概率接受；另一种是无论好恶均以一定概率接受，只是结果越好接受概率越高。不同方式对于最终结果会有不同影响。由于状态接受规则体现优胜劣汰的思想，全局优化也会陷入局部极优解，因此必须考虑多样性问题。单点法 39

32 现代优化算法——一些特例 在可行域中进行纯随机性概率搜索，将获得Monte Carlo方法，此时的状态转移完全是随机的，没有利用任何启发信息。 随机地从多个初始状态出发进行局部搜索，实际上是一种最原始的全局性和局部性优化算法的结合，即多点随机试探局部搜索法，此时的启发信息完全体现于局部搜索部分，全局性优化部分仍然是随机的和盲目的。 利用禁忌表记录曾经或已经到达过的局部极优解，下次搜索时利用该表信息不再或有选择地搜索这些点，以此跳出局部极优解，增加搜索的区域，是禁忌搜索的基本思想。显然这种搜索的效率是比较高的，但参数设置是一个需要认真研究的问题，涉及到禁忌对象、禁忌长度、候选集合、评价函数、特赦规则、终止规则等的合理确定。这里的全局性启发信息体现在禁忌表。 39

33 现代优化算法——一些特例 从可行域的某个初始状态出发，按照符合一定概率分布的状态转移规则搜索最优解，利用概率的方法接受新状态，即更好结果肯定接受，恶化结果按照一定概率接受，而且随着搜索的进行接受恶化解的概率逐渐变小，这是模拟退火的基本思想。这种搜索没有结合局部优化算法，但具有隐含的局部优化能力。需要考虑的参数包括初始温度选取、Markov链长度（平衡态判据）、温度控制策略、终止条件等。这里的启发信息体现在状态转移规则和状态接受规则，分别指导全局性优化和局部性优化。 39

34 现代优化算法——一些特例 从可行域中的多个初始状态（个体）出发进行并行搜索，在搜索过程中个体之间不断交流信息，采用概率方式接受新个体，比如赌盘形式。这是遗传算法的基本思想，采用一种群体搜索策略。这种方法具有很强的全局搜索能力和较强的局部搜索能力，自动嵌入有增加多样性的算子（交叉和变异运算），主要缺陷是容易出现“早熟”。需要考虑的因素有个体编码方式、种群规模、选择算子、交叉算子、变异算子、终止代数、适应度函数等。其启发信息在于选择方式（直接影响以后搜索的区域）、个体信息交流（模式的优化组合）等。 结论：在全局性优化算法的一般性描述下各种优化算法之间存在着密切的内在联系，是不同情况下的特殊算法。其中禁忌搜索、模拟退火属于单点法，遗传算法属于多点法，Monte Carlo方法和多点随机试探局部搜索法既可以以单点法方式进行，也可以以多点法方式进行。 39

35 内容概要 优化算法简介——运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作 39

36 课题组的工作——已经完成的工作 局部优化算法的改进：梯度下降法——自适应调整其学习率（步长调整）
——《模式识别与人工智能》、《系统工程与电子技术》 遗传算法的参数确定：遗传算法平均截止代数和成功率与种群规模之间的关系。 ——《系统仿真学报》（增刊） 遗传算法改进：与正交试验法相结合——正交遗传算法。 ——《电子学报》 遗传算法改进：与梯度下降法的结合——混合遗传算法。 ——《现代信息技术理论与应用——CIE-YC'2002》 遗传算法改进：与小生境进化算法、聚类分析相结合。 ——《小型微型计算机系统》 39

37 课题组的工作——Publications
BP小波神经网络快速学习算法研究。李金屏，王风涛，杨波。 《系统工程与电子技术》，Vol.23,No.8,2001,72-75. 遗传算法平均截止代数和成功率与种群规模之间的关系。李金屏，何苗，杨波。《系统仿真学报》(增刊),2001, Vol.13, 提高BP小波神经网络收敛速度的研究。李金屏，何苗，刘明军，杨波。《模式识别与人工智能》, 2002, 15(1):28-35。 正交遗传算法。史奎凡，董吉文，李金屏，曲守宁，杨波。《电子学报》 ，2002，Vol.30，No.10. 利用混合遗传算法提高小波神经网络收敛速度的研究。李金屏，牛业亭，卢刚。《现代信息技术理论与应用：CIE-YC‘2002》， ，合肥：中国科学技术大学出版社，2002.8。 基于小生境算法和聚类分析的快速收敛遗传算法。李金屏，李素芳，杨波。《小型微型计算机系统》，2004，Vol.25，No.6。 混沌优化算法性能分析。李金屏，韩延彬，孙志胜。《小型微型计算机系统》，2005，Vol.26。（accepted） 39

38 课题组的工作——未来的工作 现代全局性优化算法研究——一个综合性的研究、理论性研究
浮点数编码时遗传算法和梯度下降法相结合中若干问题的讨论：局部邻域结构的讨论 模拟退火算法的综合改进 全局优化算法的最新研究进展综合调研——蚁群算法、人工生命、免疫算法、粒子群算法等。 其它 39

39 谢谢大家！ ——于济南大学