机械优化设计教学提纲

1、机械优化设计1. 机械优化设计基本思路1.1优化问题概述在保证基本机械性能的基础上，借助计算机，应用一些精度较高的力学/数学规划方法进行分析计算，让某项机械设计在规定的各种设计限制条件下， 优选 设计参数，使某项或几项设计指标(外观、形状、结构、重量、成本、承载能力、 动力特性等)获得最优值。机械优化设计的过程：(|)分析设计变量，提出目标函数，确定约束条件，建 立优化设计的数学模型；(2)选择适当的优化方法，编写优化程序;(3)准备必须的初 始数据并上机计算，对计算机求得的结果进行必要的分析。优化方法的选择取决于数学模型的特点，如优化设计问题规模的大小、目标 函数和约束函数的性态以及计算精度

2、等， 在选择各种可用的优化方法时，需要考 虑的问题是优化方法本身的适应性和计算机执行该程序时所花费的时间和费用。 一般认为，对于目标函数和约束函数均为显函数且设计变量个数不太多的问题， 可选用罚函数法；对于只含有线性约束的非线性规划问题，可选用梯度投影法； 对于函数易于求导的问题，可选用可行方向法；对于难以求导的问题则应选用直 接法，如复合形法。1.2传统优化算法概述根据对约束条件处理的方式不同，可将传统的约束优化方法分为直接法和间 接法两大类。直接法通常适用于只含不等式约束的优化问题，它是在可行域内直 接搜索可行的最优点的优化方法，如复合形法、随机方向法、可行方向法和广义 简约梯度法。间接法

3、是目前在机械优化设计中应用较为广泛的一种优化方法，其基本思路是将约束优化问题转化成一个或一系列无约束优化问题，再进行无约束优化计算，从而间接地搜索到原约束问题的最优解。如惩罚函数法和增广拉格朗 日乘子法。1.2.1直接法复合形法是一种求解约束优化问题的重要的直接解法，其基本思想是在n维设计空间内构造以k个可行点为顶点的超多面体，即复合形。对各个顶点所 对应的目标函数值进行比较，将目标函数值最大的顶点，即最坏点去掉，然后按 照一定的法则求出目标函数值有所下降的可行的新点，并以此点代替最坏点，构成新的复合形。如此重复，直至复合形缩小到一定的精度，即可停止迭代，获得 最优解。随机方向法是一种原理很简

4、单的直接解法，其基本思想是在可行域内任意选 一初始点，然后利用随机数的概率特性产生若干个随机方向， 并从中选出一个使 目标函数值下降最快的随机方向作为搜索方向进行搜索。约束变尺度法是一种最先进的非线性规划计算方法，它将二次规划、线性近 似、拉格朗日乘子、罚函数、变尺度以及不确定搜索这些方法有效地结合在一起， 其基本思想是首先对优化问题产生拉格朗日函数，然后利用该函数在每个迭代点构造一个带有不等式约束条件的二次规划子问题，由于该子问题不易求解析解， 所以只能借助于数值方法求解其极值，以每次迭代的二次规划子问题的极值解作 为此次迭代的搜索方向，同时采用不精确一维搜索确定搜索步长因子，产生新的迭代点

5、，经过一系列迭代后，最终逼近原问题的最优解。广义简约梯度法是一种求解一般非线性规划问题的有效方法，其基本思想是在优化问题中引进松弛变量，在起作用的约束集合中，将不等式约束转化为等式 约束，并且保留变量的上、下边界值，将原问题转化为只有等式约束和边界约束 的数学规划问题。将设计变量分为基变量和非基变量两部分，利用目标函数对非基变量的简约梯度构造该次迭代的搜索方向， 沿此方向进行一维搜索以确定步长， 从而获得新的迭代点。对于非线性约束条件，需要不断运用牛顿法向边界投影， 以确保起作用约束条件的交界处向最优点逼近。122间接法惩罚函数法(Sequential Unconstrained Minimi

6、zation Technique SUMT)， 即SUMT是一种使用广泛的、有效的间接解法，其基本思想是将约束优化问题 中的等式和不等式约束函数经过加权转化后， 和原目标函数结合形成一个新的目 标函数一惩罚函数，然后通过求解该惩罚函数的无约束极小值， 以期望得到原问 题的约束最优解。根据迭代过程是否在可行域内进行，惩罚函数又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法三种增广拉格朗日乘子法也是求解非线性优化问题的有效方法之一，其主要思想是把惩罚函数与拉格朗日乘子法相结合，即在惩罚函数中引入拉格朗日乘子或者 说是在拉格朗日函数中引入惩罚项。 当采用外点惩罚函数时，试图在惩罚因子不 超过某

7、个适当大的正数的情况下，通过调节拉格朗日乘子，逐次求解无约束优化 问题的最优解，并使之逐渐逼近原约束问题的最优解。1.3现代优化方法随着20世纪70年代初期计算机复杂性理论的形成，科学工作者发现并证 明了大量来源于实际的组合最优化问题是非常难求解的，针对大规模组合优化问题，传统优化方法已显得无能为力了。20世纪80年代初期，应运而生出现了一系列现代优化方法，如遗传算法、模拟退火算法、蚁群算法等。它们的共性是 基于客观世界中一些自然现象，通过与组合最优化求解进行类比，找出一些共性， 以此为基础建立相应的算法。这些算法的目标是希望能够求解NP完全冋题的全局最优解，具有一定的普适性，可用于解决大量实

8、际应用问题。 其基本内容介 绍如下。2. 遗传算法遗传算法(Genetic Algorithm, GA)是模拟生命进化机制搜索和优化，并将自然 遗传学和计算机科学结合的优化方法。美国 Michigan大学的JOHNHHOLLAND (1975)首先提出了 GA的概念和方法，其依据是以生物界中基因的遗传变异及达尔 文的自然选择和适者生存原理，对问题进行随机的进化操作，逐步迭代寻求问题最 优解的方法，目前应用范围几乎涉及到传统优化方法难以解决的优化问题。2.1遗传算法的基本概念一般的遗传算法由四个部分组成：编码机制、控制参数、适应度函数、遗传 算子。编码机制(encoding mechanism)

9、GA不是对研究对象直接进行讨论，而是通 过某种编码机制把对象统一赋于有特定符号按一定顺序排成的串(string)。正如研 究生物遗传，是从染色体着手,染色体则是由基因排成的串。串的集合构成群体， 个体就是串。在优化问题，一个串对应一个可能的解；在分类问题中，串可解释为一 个规则。目前有二进制编码、实数编码、结构编码等。(2) 适应度函数(fitness function)优胜劣汰是自然进化的原则。优、劣要有标准。 在GA中，用适应度函数描述每一个个体的适宜程度。引进适应度函数的目的在于可根据其适应度对个体进行评估比较，定出优劣程度。适应度函数可分为原始适 应度函数和标准适应度函数。原始适应度函

10、数是问题求解目标的直接表示，通常采用问题的目标函数作为个体的适应性度量；标准适应度函数是将原始适应度函 数作一个适当的变换以转换成标准的度量方式，即皆化为极大化情形，并且适应值 非负。(3) 遗传算子(genetic operator遗传算法有三个遗传算子：选择、交叉、变异。(a) 选择算子 也称复制(reproduction)算子,它的作用在于根据个体的优劣程度决定它在下一代是被淘汰还是被选择。一般的说，适应度高即优良个体有较大的选择机会，而适应度小即低劣的个体继续存在的机会也较小。选择策略有适应 值比例选择、排名选择、局部竞争机制选择等。(b) 交叉算子 交叉的最简单方法是从群体中随机取出

11、两个字符串 (父辈个 体)，并随机确定一个交叉点，将交叉点两个字符串的右段互相交换，从而形成两个 新串(后代)。杂交方式一般有一点交叉、两点交叉、均匀交叉、基于顺序交叉等。(c) 变异算子 它的作用是随机地改变字符串的某个位置上的字符。如在二 进制编码的字符串中，某位置字符0变为1,或1变为0。变异有均匀性变异、正态性 变异、非一致性变异、自适应性变异和多级变异。(4) 控制参数(control parameters)在GA的实际操作时，需适当确定某些参数的 值以提高选优的效果。这些参数是：(a) 字符串所含字符的个数L,即串长。(b) 每一代群体的大小N,即所包含字符串的个数，也称群体的规模

12、。(c) 交叉率(crossover rate)Pc即施行交叉算子的概率。(d) 突变率(mutation)Pm,即施行突变算子的概率。根据经验，对于算子执行重叠的算法，即遗传操作产生的新的个体替代上一代 中部分较差的个体，而生成新的种群,算法的主要控制参数取值范围一般 为:N=20100,Pc=0600 95,Pm=O0O1O 01(或取 1/L,此处L为串长);对于算子执行非重叠的算法，即用后代替换掉整个群体产生新种群，取值范围一般为:N=20100,Pc=0 50 7,Pm=0 20 4。2.2遗传算法的实现目前,遗传算法经过改进已有各种不同形式的遗传算法，一般把John Holla n

13、d 于1975年提出的遗传算法称作标准的遗传算法(Simple GA,简称GA),现就SGA应 用在机械优化设计的主要步骤简述如下。(1) 建立优化数学模型。就是把机械设计的具体问题用数学关系表达出来及 准确地描述出来。具体地讲，就是确定设计变量、目标函数以及约束函数。其数 学模型为maxF(X) X=x1,x2,xnTs t - gu(X) <0u=1,2,phv(X)=0v=p+1,p+2,p+m(2) 编码的确定。遗传算法求解问题不是直接作用在问题的解空间上，而是利用某种编码表示。GA在求解之前，首先确定合适的编码方式，如二进制编码，将问 题的所有设计变量编码成子串，再将子串连成一

14、定长度的串，即染色体，一个串对 应一个设计点，即设计空间的一个解。选择何种编码表示有时将对算法的性能、 效率等产生很大的影响。(3) 适应函数的确定。适应值是对解的质量的一种度量 ，用以反映个体对问题 环境适应能力的强弱。适应函数是个体竞争的测度 ，控制个体的生存的机会。一 般以目标函数的形式表示。(4) 选择策略的确定。选择体现了优胜劣汰的自然法则，适应值越高的个体被选择的机会就越多。一般采用适应值比例选择，具体地讲，个体的选择概率为 pi=fi/刀ni=1其，中fi为个体的适应值，刀ni=1为个体适应值的总和。实践证明，不同 的选择策略对算法的性能也有较大的影响。(5) 交叉。交叉是遗传算

15、法的重要的遗传算子，目的是产生新的基因组合，形成 新的个体。SGA采用的是一点交叉，即随机地在两个父串上选择一个交叉点，然后 交换这两个对应子串。如设两个父串为9仁(10111010), 9 2=(010110随机交叉点 是5,交换9 1,的子串(010)与(011)得到两个新串B' 1=(101110和)B '=(21011010)。 交叉体现了自然界中信息交换的思想。(6) 突变。交叉完成后即可进行突变操作，突变是按位进行的，即以概率pm改变 串上的某一位，以二进制串为例：串0101001突变0101101突变的目的在于增强GA 的搜索最优解的能力，通过突变操作，可确保群体

16、中个体的多样性，有效的防止算 法的早熟收敛。但过多的突变会使 GA退化为随机搜索。(7) 终止判据的确定。目前，确定遗传算法终止条件的主要判据有以下几个：(a) 判断GA进化是否达到了预定的最大代数；(b) GA是否找到了较优的个体，即问题的较优的解；(c) 个体的适应值是否已趋于稳定，而无改进。(8) 最优解的确定:若找到的最优解或次优解满意，则结束;否则,修改数学模型 或调整GA的各控制参数，直到求出最优解。2.3遗传算法的特点遗传算法具有十分顽强的鲁棒性，这是因为遗传算法与其它普通的优化搜索 方法相比，采用了许多独特的技术和方法，其主要特点如下：(1) GA的自组织、自适应和自学习性(智

17、能性)。应用遗传算法求解问题时，在确定编码方案、适应度函数以及遗传算子后，遗传算法将利用进化过程 中获得的信息自行组织搜索，由于基于自然系统的选择策略为 优胜劣汰”因而 适应度大的个体具有较高的生存概率。通常适应度大的个体具有更适应环境的基 因结构，再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。 遗传算法的这种自组织、自适应特性，使它同时具有能根据环境变化来自动发现 环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。 因此，利用遗传算法可以解决复杂的非线性规划问题。(2) GA的处理对

18、象不是参数本身，而是参变量编码后的染色体串。编码 操作使得遗传算法可直接对结构对象进行操作。所谓结构对象泛指集合、序列、 矩阵、树、图、链和表等各种一维或二维或三维结构形式的对象。这一特点，使 得遗传算法具有广泛的应用领域。 通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树（3）通过对任务序列的操作，遗传算法可用于规划，而通过对序列的处理， 遗传算法可自动构造顺序控制系统。（4）GA同时搜索解空间中的一群点，而非单个点。如同在解空间中撒网 一样，GA同时对空间中的不同区域采样，并构成不断进化的群体序列，或者说 GA并行地爬多个山峰。而许多传统搜索方法都是单点搜索方法，即通过一些变 动规

19、则，问题的解从搜索空间中的当前解转移到另一个解。对于多峰值分布的搜 索空间常常会陷于局部的某个单峰的优化解。而遗传算法同时处理多个解，并行 爬多个峰，从而使其具有较好的全局搜索性能，减少陷入局部解的可能。同时， 这使遗传算法本身也十分易于并行化。（5）在GA中，基本上不用搜索空间的知识或其它辅助信息，而仅用适应 度函数值对个体进行评估，并在此基础上进行遗传操作。需要着重提出的是：遗 传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对 适应度函数的唯一要求是：对于输入可计算出加以比较的正的输出， 这一特点使 得遗传算法的应用范围大大扩展。GA不是采用确定性规则，而是采用概率的

20、变 迁规则来指导搜索方向。遗传算法采用概率仅仅是作为一种工具来指导其搜索过 程朝着搜索空间的更优的解空间移动。因此遗传算法虽然看起来采用的是一种盲 目的搜索方法，但实际上具有明确的搜索方向。（6）GA对给定问题，可以产生许多潜在解，最终选择可以由使用者确定。 遗传算法对于确认可替代解集而言是特别合适的。同时，GA算法亦存在过早收敛和易陷入局部最优的问题。基于上述特点，GA算法适用于大规模、高度非线性的不连续多峰函数的优 化以及无解析表达式的目标函数的优化。2.4改进的遗传算法如何提高遗传算法跳出局部最优的能力和如何提高遗传算法的收敛速度成 为近年来遗传算法的研究热点，许多学者从不同的角度对遗传

21、算法进行了改进，使 遗传算法的寻优能力有了不同程度的提高。而对遗传算法的研究主要集中在数学 基础、各环节的实现方式以及与其他算法的结合方面 ，其中,尤以遗传算法与其他算法相结合方面的研究最为引人关注。由于遗传算法具有开放式的结构，与同题的关联性不大，很容易和其它算法进行结合，所以融合了其它的算法思想和遗传算 法思想的混合遗传算法成了目前改进遗传算法研究的一个重要方向。模拟退火遗传算法：模拟退火算法的基本思想是通过模拟高温物体退火过程 的方法，来找到优化问题的全局最优或近似全局最优解。遗传算法的局部搜索能 力较差，但把握搜索过程总体的能力较强，而模拟退火算法具有较强的局部搜索能 力，并能使搜索过

22、程避免陷入局部最优解，但它却对整个搜索空间的了解不多，不 便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不 高。但如果将遗传算法和模拟退火算法相结合，互相取长补短，则有可能开发出性 能优良的新的全局搜索算法。目前，已有许多学者将退火机制引入到遗传操作中， 使遗传操作产生优良个体的概率增加，并使遗传算法的寻优能力有了明显的提高。模糊遗传算法：模糊遗传算法，即融合模糊优化设计思想的遗传算法，它把模 糊优化和遗传算法优化结合起来，构成一种混合优化的设计方法。其目的是利用 模糊优化设计的优点，克服一般遗传算法优化设计存在的不足，从而使得系统的优 化设计更灵活、方便，取得好的设计效

23、果。模糊遗传算法运用模糊控制的思想，来 自适应改变遗传算法的种群规模、 交叉概率、变异概率、适应度函数以及控制策 略等。混沌遗传算法：混沌是自然界广泛存在的一种非线性现象，它充分体现了系统 的复杂性。混沌运动具有类似随机变量的杂乱表现 ，具有随机性。混沌运动的上 述性质作为避免陷入局部极小的优化搜索机制，恰好可以弥补遗传算法易陷入局 部最优、收敛速度慢的缺陷。可以利用混沌的遍历性产生初始种群，也可以对优良个体进行变异操作，从而增强了遗传算法的全局寻优能力。此外,遗传算法的全局搜索能力及免疫算法的局部优化相配合的免疫遗传算 法;用小生境思想来实现遗传算法的选择操作，使遗传算法的全局寻优能力得到了

24、 明显提高的小生境遗传算法；量子计算思想与遗传算法结合的产物的量子遗传算 法，可使量子遗传算法表现出比标准遗传算法更好的种群多样性、更强的全局搜 索能力和更快的收敛速度。蜜蜂进化型遗传算法中，种群的最优个体作为蜂王与 被选的每个个体（雄蜂）以概率进行交叉操作，增强了对种群最优个体所包含信息 的开采能力，结果表明,蜜蜂进化型遗传算法是一种提高遗传算法性能的有效改进算法2.5遗传算法在机械工程中的应用前景遗传算法作为一种非确定性的模拟自然演化的学习过程的求解问题方法，在很多领域具有广泛的应用价值，其在机械工程领域的应用前景主要体现在以下几 个方面：（1）与CAD技术相结合，解决总体方案设计方面的优

25、化问题；（2）利用遗传算法的组合优化特性解决机械系统中多种系列化标准件的组 合选取问题；（3）将遗传算法和计算机仿真技术相结合，对工程实际问题中难以确定的 参数进行编码，以原设计产品的性能和数学模型的仿真性能之间的差异最小为目 标函数，求解符合原设计要求的设计参数与工艺参数；（4）用遗传算法进行系统可靠度分配，从而使机械系统获得最高的可靠性；（5）以能耗降低到最小为目标，运用遗传算法进行节能设计，使设备在满 足功能要求的条件下达到最佳效果。虽然遗传算法在很多方面还有待于进一步的研究、探讨和完善，但是，随着计算机技术的进步和生物学研究的深入，遗传算法在操作技术和方法上将更加通 用、更加有效，并且

26、在机械工程领域的应用也会越来越广泛。3. 模拟退火法模拟退火算法（Simulate Anneal Arithmetic, SAA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是S.Kirkpatrick,C.D.Gelatt和M.P.Vecchi 在 1983年所发明。而 V.?ern&yacute;在 1985年也独立发明 此演算法。模拟退火算法是解决TSP问题的有效方法之一。模拟退火的原理也和 金属退火的原理近似：将热力学的理论套用到统计学上， 将搜寻空间内每一点想 像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点， 也像空气分子一样

27、带有“能量”，以表示该点对命题的合适程度。演算法先以搜 寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位 置到达“邻居”的概率。3.1模拟退火法的实现模拟退火算法可以分解为解空间、目标函数和初始解三部分。 重要理解：假设材料在状态i之下的能量为E(i),那么材料在温度T时从状态i进入状态j 就遵循如下规律：如果E(j)<= E(i),接受该状态被转移如果E(j)> E(i)，则状态转移以如下的概率被接受：expE(i)-E(j)/KT其中，K是物理学中的波尔兹曼常数，T是材料温度。算法关键参数和操作的设定：从算法的流程上看，模拟退火算法包括三函数两准则，即状态

28、产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设 计将决定模拟退火算法的优化性能。 此外，初温的选择对模拟退火算法性能也有 很大影响。状态产生函数：原则：设计状态产生函数(领域函数)的出发点应该是尽可能保证产生的候选 解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式 和候选解产生的概率分布。方法：在当前状态的领域结构内以一定概率方式 (均匀分布、正态分布、指 数分布等)产生。状态接受函数：原则：函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率 的形式不同。设计状态接受概率，应该遵循以下原则：(1) 在固定温度下，接受使目标函数

29、下降的候选解的概率要大于使目标函 数上升的候选解概率；(2) 随温度的下降，接受使目标函数上升的解的概率要逐渐减少；(3) 当温度趋于零时，只能接受目标函数下降的解。方法：状态接受函数的引入是模拟退火算法实现全局搜索的最关键的因素，初始温度：初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程。原则：通过理论分析可以得到初温的解析式， 但解决实际问题时难以得到精 确的参数；实际应用时往往要让初温充分大。实验表明：初温越大，获得高质量解的机率越大，但花费较多的计算时间。方法：（1）均匀抽样一组状态，以各状态目标值的方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标差

30、值，根据差值，利用一定的函数确定初温，譬如tO =- /InPr,其中Pr为初始接受函数；（3）利用经验公式。温度更新函数：温度更细函数，即温度的下降方式，用于在外循环中修改温 度值。内循环终止准则：常用的Metropolis 抽样准则：（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。外循环终止准则（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。模拟退火的基本思想：（1）初始化：初始温度T（充分大），初始解状态S（是算法迭代的起点），每 个T值的迭代次数L（2）对k=1,，L做第 至

31、第6步：（3）产生新解S'（4）计算增量厶t ' =C（S'）-C（S），其中C（S）为评价函数(5) 若厶t ' <0则接受S'作为新的当前解，否则以概率exp(- t ' /T)接受S' 作为新的当前解(6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。(7) T逐渐减少，且T->0，然后转第2步。模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起 点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率 I收 敛于全局最优解的全局优化

32、算法；模拟退火算法具有并行性。3.2模拟退火法参数控制问题模拟退火算法的应用很广泛，可以求解NPI全问题，但其参数难以控制，其 主要问题有以下三点：(1) 温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初 始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反 之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始 温度一般需要依据实验结果进行若干次调整。(2) 退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度 下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针 对具

33、体问题的性质和特征设置合理的退火平衡条件。(3) 温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：式中k为正的略小于1.00的常数，t为降温的次数。4. 蚁群算法蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中 寻找优化路径的机率型算法。它由 Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质针对PID控制器参数优化设计 问题，将

34、蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。4.1蚁群算法的基本概念(1) 蚁群算法中的参数：ALPHA :启发因子，信息素的重要程度，一般取值1.0oBETA :期望因子，城市间距离的重要程度，一般取值 2.00R0U :信息素挥发系数，一般取值0.5。ANT_C0UNT :蚂蚁数量，一般取值为城市数量的2/3。CITY_C0UNT :城市数量。IT_COUNT :迭代次数，就是全部蚂蚁搜索多少次，取值自己设定。Q:信息素总量，取值多少对算法没什么影响。(2) 蚂蚁类实现蚁群算法的关键是用代码实现蚂蚁的行为，我们

35、来实现一个蚂蚁类，这个蚂蚁类应该具有以下行为。1、初始化,蚂蚁从某个城市出发。2、选择下一个城市。3、移动到下一个城市。4、如果全部城市都去过了，直接返回到出发城市，到第 5步，否则再跳转 到第2步。5、计算走过的路径长度。(3) TSP类有了蚂蚁类只是实现了单个蚂蚁的行为， 蚁群算法是多个蚂蚁的行为，还有 更新环境信息素，输出最后结果等工作需要做，我们再定义一个 TSP类。这个类 完成下面工作。1、初始化环境信息素。2、管理多个蚂蚁，让多只蚂蚁按设定的搜索次数去搜索路径。3、蚂蚁完成一次搜索后，更新环境信息素，同时保存下目前的最优路径4、输出最后结果。(4) 全局变量有了上面两个类之后，还有

36、一些工作要做，环境信息素需要保存，算法参数 需要定义，城市信息的数据需要保存，这些东西都放到全局变量的定义里。4.2蚁群算法的实现Dorigo等人提出的蚂蚁群体优化的元启发式规则较好地描述了蚁群算法的 实现过程，其过程可以表示为：当没有达到结束条件时，蚂蚁在一定的限制条件 下寻找一条路径；轨迹(即信息激素)浓度的挥发；后台程序，主要是完成单个蚂 蚁无法完成的任务，比如说根据全局信息对信息激素浓度进行更新；达到条件， 结束。下面以一维搜索为例，引申到n维空间的函数优化问题中。假定优化函数为：m inZ=f(x) x a,b。设m个人工蚂蚁，刚开始时位于区间a,b的m等分处，蚂蚁从位置i转移到位置

37、j 的概率定义为pij,则：f TZURfij mfTZUJ ij j 1式中:fj蚂蚁j的领域吸引强度；Zij 目标函数的差值，定义为fi(x)-fj(x);T,U经验系数,T,U 1,5。在得到新一代的解以后，更新方程为:fj(i+ 1)=df(i)+Xdj(O, 1)。(12)式中： fj 第j只蚂蚁在本次循环中吸引强度的增加；d强度的持久性。式中 f的更新按下式进行： fj=Q/Lj式中:Q正常数,0<Q<10 000;Lj 本次循环中f(x)的增量，定义为f(x+r)-f(x)。于是函数f(x)的寻优就借助m个蚂蚁的不断移动来进行:当Zij时,蚂蚁i按概 率pij从其领域

38、i移至蚂蚁j的领域;当Zij<0时，蚂蚁i做领域搜索(搜索半径或步长为 r）,即每个蚂蚁要么转移至其它蚂蚁处，要么进行领域搜索。由此可见，当蚂蚁的数 量足够多，搜索半径足够小，这种寻优方式相当于一群蚂蚁对定义区间a,b做穷尽 的搜索，逐渐收敛到问题的全局最优解。上述函数优化过程不受优化函数是否连续、是否可导等限制，较之经典搜索 方法具有明显的优越性和稳定性。4.3蚁群算法的特点（1）蚁群算法是一种自组织的算法。在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果 系统在获

39、得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们 便 说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系 统墒增加的过程（即是系统从无序到有序的变化过程）。蚁群算法充分休现了这个 过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序 的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的 越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。（2）蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多age n係统，它在问题空间的多点同时开始进行独立的解

40、搜索， 不仅增加了算法的可靠性， 也使得算法具有较强的全局搜索能力。（3）蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短 路径，直接依赖于最短路径上信息激素的堆积，而 信息激素的堆积却是一个正反馈的过程。 对蚁群算法来说，初始时刻在环境中存 在完全相同的信息激素，给予系统 一个微小扰动，使得各个边上的轨迹浓度不 相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路 径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进 化。因此，正反馈是蚂蚁算法的重要特征

41、，它使得算法演化过程得以进行。（4）蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算 法应用到其它组合优化问题的求解。5. 粒子群算法粒子群算法，也称粒子群优化算法(Particle Swarm Optimization)，缩写为 PSO，是近年来发展起来的一种新的进化算法(Evolutionary Algorithm - EA )。PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解， 通过迭代搜寻最优值。但是它没有遗传算法

42、用的交叉(crossover以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO 的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。5.1粒子群算法的实现PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次 迭代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最 优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解， 这个极值是全局极值gBesto另外也可以不用整个种群而只是用其中一部分作为 粒子的邻居

43、，那么在所有邻居中的极值就是局部极值。(1)粒子公式在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置：v = w * v + cl * ran d() * (pbest - prese nt) + c2 * ran d() * (gbest - prese nt)prese nt = prese nt + vv是粒子的速度,w是惯性权重,prese nt是当前粒子的位置.pbest a nd gbest如前定义rand ()是介于(0， 1)之间的随机数.c1, c2是学习因子.通 常 c1 = c2 = 2.应用PSO解决优化问题的过程中有两个重要的步骤：问题解的编码和适应

44、 度函数。（2）基本粒子群算法的流程（a）依照初始化过程，对粒子群的随机位置和速度进行初始设定；（b）计算每个粒子的适应度；（c） 对于每个粒子，将其适应度与所经历的最好位置Pi的适应度值进行比 较，若较好，则将其作为当前最好位置；（d） 对于每个粒子，将其适应度与全局所经历的最好位置Pg的适应度值进 行比较，若较好，则将其作为全局最好位置；（e）根据两个迭代公式对粒子的速度和位置进行优化；（f）如未达到结束条件通常为足够好的适应度值或达到一个预设最大代数（Gmax），返回步骤（2）；否则执行步骤（h）；（h）输出 gbes。（3）编码的确定不需要像遗传算法一样是二进制编码（或者采用针对实数的

45、遗传操作例如对 于问题f（x） = x1A2 + x2A2+x3A2求解，粒子可以直接编码为 （x1, x2, x3）,而适 应度函数就是f（x）.接着我们就可以利用前面的过程去寻优.这个寻优过程是一个 叠代过程，中止条件一般为设置为达到最大循环数或者最小错误PSO中并没有许多需要调节的参数，下面列出了这些参数以及经验设置粒子数：一般取20 -40.其实对于大部分的问题10个粒子已经足够可以取 得好的结果,不过对于比较难的问题或者特定类别的问题,粒子数可以取到100 或200粒子的长度：这是由优化问题决定，就是问题解的长度粒子的范围：由优化问题决定，每一维可是设定不同的范围Vmax:最大速度，

46、决定粒子在一个循环中最大的移动距离，通常设定为粒子 的范围宽度，例如上面的例子里，粒子（x1, x2, x3） x1属于-10,10,那么Vmax 的大小就是20学习因子：c1和c2通常等于2.不过在文献中也有其他的取值.但是一般 c1等于c2并且范围在0和4之间中止条件：最大循环数以及最小错误要求.例如，在上面的神经网络训练例 子中，最小错误可以设定为1个错误分类，最大循环设定为2000,这个中止条件由具体的问题确定全局PSO和局部PSO:两种版本的粒子群优化算法：全局版和局部版.前者 速度快不过有时会陷入局部最优后者收敛速度慢一点不过很难陷入局部最优 在实际应用中,可以先用全局PSO找到大

47、致的结果，再用局部PSO进行搜索(4) 惯性权重另外的一个参数是惯性权重,Shi和Eberhar指出(A modified particle swarm optimizer,1998):当 Vmax很小时(对 schaffer的f6函数，Vmax<=2),使用接近于 1 的惯性权重；当Vmax不是很小时(对schaffer的f6函数，Vmax>=3),使用权重w=0.8 较好如果没有Vmax的信息，使用0.8作为权重也是一种很好的选择.惯性权重w很 小时偏重于发挥粒子群算法的局部搜索能力；惯性权重很大时将会偏重于发挥粒 子群算法的全局搜索能力。5.2粒子群算法的特点PSO算法属于进

48、化算法的一种，和模拟退火算法相似，它也是从随机解出 发，通过迭代寻找最优解，它也是通过适应度来评价解的品质。 这种算法以其实 现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。粒子群算法是一种并行算法。粒子还有一个重要的特点，就是有记忆。与遗传算法比较，PSO的信息共享 机制是很不同的.在遗传算法中，染色体(chromosomes)互相共享信息，所以整 个种群的移动是比较均匀的向最优区域移动.在PSO中,只有gBest (or pBest)给 出信息给其他的粒子，这是单向的信息流动.整个搜索更新过程是跟随当前最优 解的过程.与遗传算法比较，在大多数的情况下，所有的粒子可能更快的收敛于 最优解。缺点：对于离散的优化问题处理不佳；对于有多个局部极值点的函数， 容易陷入局部极值点中，得不到正确的结果。此外，由于缺乏精密搜索方法的配合， PSO方法往往不能得到精确地结果。再则，PSO方法提供了全局搜索的可能，但 不能严格证明它在全局最优点上的收敛性。因此，PSO般适用于一类高维的，存在多个局部极值点而并不需要得到很高精度的优化问题