非线性方程组的数值解法及最优化方法.ppt

若对任意 都有一个实数 与之对应，且满足：（1）非负性：当 时，；当 时，；（2）齐次性：对任何，；（3）三角不等式：对任意，都有（4）相容性：对任意，都有，则称 为 上矩阵 的范数，简称矩阵范数。,非线性方程组的数值解法,非线性方程组的数值解法,考虑如下方程组式中 均为 的多元函数，向量形式为其中,非线性方程组的数值解法,当，并且 中至少有一个是自变量 的非线性实函数时，称方程组 为非线性方程组。其求根问题就是确定方程组在指定范围内的一组解，可以通过对单个非线性方程求根问题的直接推广得到非线性方程组的求解算法。,非线性方程组的数值解法,常用解法分为两类：一类是线性化方法，将非线性方程组用一个线性方程组来近似，由此构造一种迭代公式，逐次逼近所求的解；另一类是属于求函数极小值的方法，即由非线性函数 构造一个模函数，例如构造函数然后通过各种下降法或优化算法求出模函数的极小值点，此极小值点即为非线性方程组的一组解。,非线性方程组的数值解法,不动点迭代法：根据非线性方程求根的迭代法，将方程组改写为如下等价方程组构造迭代公式选取初始向量则由迭代公式可以得到一个向量序列。如果方程组有唯一解向量，并且，则 可作为逐次逼近 的近似解。,非线性方程组的数值解法,如果把迭代公式写为向量形式并记矩阵 为则可以证明当 时，迭代公式是收敛的。,非线性方程组的数值解法,例题1：用迭代法解如下非线性方程组取初值。解：构造迭代公式,非线性方程组的数值解法,式中所以有取初值，在 附近，所以迭代公式收敛。,非线性方程组的数值解法,x10=0;x20=0;k=0;while 1 k=k+1;x1k=(1+x20-0.1*exp(x10)/4;x2k=(x10-x102/8)/4;%雅克比迭代法%x2k=(x1k-x1k2/8)/4;%高斯-赛德尔迭代法 err1=abs(x1k-x10);err2=abs(x2k-x20);err=max(err1,err2);if err=0.00000000005 break;end x10=x1k;x20=x2k;end,非线性方程组的数值解法,非线性方程组的数值解法,上述迭代公式与求解线性方程组的雅克比迭代公式形式相同，可以对其进行改进，构造求解非线性方程组的高斯-赛德尔迭代公式，即对上例采用高斯-赛德尔迭代公式计算迭代计算过程如下表所示,非线性方程组的数值解法,非线性方程组的数值解法,牛顿迭代法：根据求解非线性方程的牛顿迭代法，如果已经给出方程组 的一个近似根，则可把函数 的分量 在 处按多元函数泰勒公式展开，取其线性部分做近似，得则得到线性方程组,非线性方程组的数值解法,方程组的解为上式即为求解非线性方程组的牛顿迭代公式。式中称为 的雅克比矩阵。,非线性方程组的数值解法,例题2：用牛顿迭代法求解下面非线性方程组计算时取初始值。解：先求雅克比矩阵,非线性方程组的数值解法,由牛顿迭代公式得到迭代计算过程如下表所示。,非线性方程组的数值解法,X0=1.5;1;k=0;while 1 k=k+1;F=X0(1,1)+2*X0(2,1)-3;2*X0(1,1)2+X0(2,1)2-5;Fd=1 2;4*X0(1,1)2*X0(2,1);Xk=X0-inv(Fd)*F;err=max(abs(Xk-X0);if err=0.00005 break;end X0=Xk;end,非线性方程组的数值解法,练习题：用牛顿迭代法求解方程组取结果：,非线性方程组的数值解法,非线性方程组的数值解法,应用经过海底一次反射到达水听器阵的特征声线传播时间，来反演海底参数。假设水中和沉积层声速都是恒定的，海底沉积层上界面水平，下界面倾斜。特征声线由水中声源出发折射进入沉积层，经过沉积层的下界面反射后，再折射进入水中，由水中水听器阵接收。特征声线的传播时间为声线在水中和沉积层中的传播时间之和。三维坐标关系如图所示：,非线性方程组的数值解法,非线性方程组的数值解法,由声线传播的几何关系和折射定律，一个接收点可以导出如下6个方程：,非线性方程组的数值解法,方程中 为声线的位置参数，为海底倾角 为声源到沉积层的距离，为声源处的沉积层厚度，为声线水平偏转角，为声源和水听器的水平距离，为水听器到沉积层的距离。假设声线位置参数未知，其它参数都是已知的，根据方程求解参数。,智能计算及其在数值计算中的应用,匹配场处理（MFP：Matched Field Processing）：利用海洋环境参数和声传播信道特性，通过水下声场模型计算得到接收基阵的声场幅度和相位，形成拷贝场向量，并与基阵接收数据进行“匹配”，从而实现水下目标的被动定位和海洋环境参数的精确估计。声源、海洋信道和水听器阵是三个基本要素，三者构成不可分割的统一整体，已知其中两者，就可以推断第三者。已知水听器阵接收信号和海洋信道信息，待求解的是包括声源位置在内的声源信息，就是匹配场被动定位；如果已知水听器阵接收信号和声源信息，待求解的是海洋信道信息，就是匹配场反演（MFI：Matched Field Inversion）。,智能计算及其在数值计算中的应用,匹配场反演包括4个重要环节：反演目标函数、声场传播模型、全局优化算法和反演结果的不确定性分析。目标函数是反映拷贝物理量与观测物理量之间匹配关系的函数。目标函数的确定包括：匹配物理量的选取及目标函数的建立，海洋环境参数模型的建立，反演参数的先验信息及上下界，反演参数的敏感性分析等。目标函数中拷贝物理量的计算通过前向声场模型来完成，声传播模型：简正波模型、声线模型、抛物模型、谱积分模型等。由于反演的复杂性，全局寻优算法的高效率是关系到反演结果可靠性的重要因素，遗传算法、模拟退火算法都得到了很好的应用。,智能计算及其在数值计算中的应用,Bartlett处理器在匹配场参数估计中应用最广泛。估计的参数 是使得以下目标函数取得最大值时的变量 式中，是水听器阵接收信号，是拷贝场信号。拷贝场向量的估计由下式决定,智能计算及其在数值计算中的应用,最优化问题：在满足一定的约束条件下，寻找一组参数值，使某些最优性度量得到满足，使系统的某些性能指标达到最大或最小。最优化问题的应用涉及工业技术、社会、经济、管理等各个领域，具有重要意义。最优化问题的一般形式为：式中，称为目标函数，称为约束函数。极大极小形式的转换：,数学规划：在一些等式或不等式约束条件下，求一个目标函数的极大（或极小）的优化模型称为数学规划。根据有、无约束条件可以分为约束数学规划和无约束数学规划；根据目标函数 和约束函数 是否为线性函数，分为线性规划和非线性规划；根据问题中是否只有一个目标函数，分为单目标规划和多目标规划。很多非常重要的问题是线性的（或者用线性函数能够很好地近似表示），因此线性规划的研究具有重要意义。与非线性规划相比，线性规划的研究更加成熟。非线性规划问题相当复杂，求解方法多种多样，目前为止仍没有一种有效的适合所有问题的方法。,智能计算及其在数值计算中的应用,在数学规划中，把满足所有约束条件的点 称为可行点（或可行解），所有可行点组成的点集称为可行域，记为 于是数学规划即为求，并且使得 在 上达到最大（或最小），把 称为最优点（最优解），称为最优值。,智能计算及其在数值计算中的应用,对于很多实际问题进行数学建模后，都可以抽象为一个数值函数的优化问题。由于问题的种类繁多，影响因素复杂，数学函数呈现出不同的数学特征（连续、离散，凸函数、非凸函数，单峰值、多峰值，多种不同数学特征的组合）。除了在函数是连续、可导、低阶的简单情况下可通过解析方法求出最优解外，大部分情况下需要通过数值计算的方法来进行近似优化计算。至今没有一种既能处理各种不同的复杂函数，又具有良好求解结果的数值计算方法。,智能计算及其在数值计算中的应用,总的来说，求最优解或近似最优解的方法主要有三类：枚举法、启发式算法和搜索算法。（1）枚举法：枚举出可行解集合内的所有可行解，以求出精确最优解。但是对于连续函数，需要先进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法效率低下，甚至在目前最先进的计算工具上都无法求解。（2）启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。虽然效率较高，但是对于每一个需要求解的问题都必须找出其特有的启发式规则，因此无通用性，不适合于其他的问题求解。,智能计算及其在数值计算中的应用,（3）搜索算法：寻求一种搜索算法，在可行解集合的子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但如果适当地利用一些启发知识，就可在近似解的质量和求解效率上达到一种较好的平衡。当问题的规模比较大，优化计算的搜索空间急剧扩大，要严格地求出其最优解是不可能的，所以需要研究出一种能够在可接受的时间和精度范围内求出数值函数近似最优解的方法或通用算法。,智能计算及其在数值计算中的应用,智能计算及其在数值计算中的应用,智能计算 智能计算基于“从大自然中获取智慧”的理念，通过对自然界独特规律的认知，借用自然界、生物界规律的启迪，根据其原理模仿设计求解问题的算法，最终发展出适合获取知识的一套计算工具。包括：（1）进化算法：遗传算法、模拟退火算法、进化策略、进化规划等；（2）群体智能算法：粒子群算法、蚁群算法、人工鱼群算法等；（3）免疫算法、量子计算等。共同要素：自适应的结构，随机产生的或指定的初始状态，适应度的评测函数，修改结构的操作，系统状态的存储，终止计算的条件，指示结果的方法，控制过程的参数。总的来说，通过自适应学习的特性，这些算法达到了全局优化的目的。,遗传算法等进化算法提供了一种求解这种优化问题的通用框架。遗传算法通过对群体所施加的迭代进化过程，不断地将当前群体中具有较高适应度的个体遗传到下一代群体中，并且不断地淘汰掉适应度较低的个体，从而最终得到适应度最大的个体。这个适应度最大的个体经过解码处理后对应的个体表现型就是这个实际应用问题的最优解或近似最优解。自然界中的生物对其生存环境具有优良的自适应性，各种物种在一种竞争的环境中生存，优胜劣汰，使得物种不断改进。几十年来，人们从不同的角度出发对生物系统及其行为特征进行了模拟，产生了一些对现代科技发展有重大影响的新兴学科。,智能计算及其在数值计算中的应用,基于对生物进化机制的模仿，发展了三种典型的优化计算模型，分别是遗传算法（Genetic Alogrithms，GA）、进化策略（Evolution Strategy，ES）和进化规划（Evolutionary Programming，EP）。这些方法各自有不同的侧重点，各自有不同的生物进化背景，各自强调了生物进化过程中的不同特性，但是都是一种稳定性较好的计算机算法，适用范围广。近年来这几种方法相互借鉴和交流，使得区别逐渐缩小，统称为进化计算（Evolutionary Computation，EC）或进化算法（Evolutionary Alogrithms，EA）。,智能计算及其在数值计算中的应用,进化计算（Evolutionary Computation，EC）受生物进化论和遗传学等理论的启发，是一类模拟生物进化过程与机制，自组织、自适应的对问题进行求解的人工智能技术。进化计算的具体实现方法与形式称为进化算法（Evolutionary Algorithm，EA）。进化算法是一种具有“生成+检测”（generate-and-test）迭代过程的搜索算法，算法体现群体搜索和群体中个体之间信息交换两大策略，为每个个体提供了优化的机会，使得整个群体在优胜劣汰（survival of the fittest）的选择机制下保证进化的趋势。,智能计算及其在数值计算中的应用,进化算法采用编码的形式来表示复杂结构，并将每个编码称为一个个体（individual），算法维持一定数目的编码集合，称为种群或群体（population）。通过对群体中个体进行相应的操作，最终获得一些具有较高性能指标的个体。进化算法的研究始于20世纪60年代，Holland针对机器学习问题发展了遗传算法（Genetic Algorithm，GA），Fogel对于优化模型系统提出了进化规划（Evolutionary Programming，EP），Rechenberg和Schwefel对于数值优化问题提出了进化策略（Evolutionary Strategy，ES）。,智能计算及其在数值计算中的应用,进化计算的基本框架 进化计算提供了一种求解复杂系统优化问题的通用框架，性能比较稳定，下面给出进化计算的统一算法描述。算法Evolutionary Algorithms（1）进化代数计数器初始化：；（2）随机产生初始群体；（3）评价群体 的适应度；（4）个体重组操作：；（5）个体变异操作：；,智能计算及其在数值计算中的应用,（6）评价群体 的适应度；（7）个体选择、复制操作：（8）终止条件判断：如果不满足终止条件，则，转到（4）继续进行进化操作过程；如果满足终止条件，则输出当前最优个体，算法结束。进化计算的三个主要分支虽然基于自然界中生物进化的不同背景，但是具有很多相似之处，可以统一于上面的基本框架之内。,智能计算及其在数值计算中的应用,三种进化计算方法具有如下基本特点：（1）算法的操作对象都是有多个个体组成的一个集合，即群体；（2）每个个体都有一个对系统环境的适应度，这个适应度是算法对每个个体优劣程度的一种度量；（3）算法都要进行选择或复制操作，以便能够将当前群体中具有较高适应度的个体更多地保留到下一代群体中；（4）算法都通过个体重组、变异等进化操作，以及对个体所加入的一些微小变动，来增加群体的多样性；,智能计算及其在数值计算中的应用,（5）算法所模拟的生物进化过程都是一个反复迭代的过程。在群体的迭代进化过程中，个体的适应度和群体中所有个体的平均适应度都不断地得到改进，最终可得到一个或几个具有较高适应度的个体，它们就对应于问题的最优解或近似最优解；（6）算法所模拟的进化过程均受随机因素的影响，所以不易陷入局部最优点，并都能以较大的概率找到全局最优点；（7）算法具有一种天然的并行结构，均适合于在并行机或局域网环境中进行大规模复杂问题的的求解。,智能计算及其在数值计算中的应用,由于进化算法具备上述特点，使得它能够用于解决复杂系统的优化问题，特别是能够解决一些利用其他方法难以解决或根本无法解决的问题。并且说明了进化算法是一类全局优化自适应概率搜索技术，不依赖于具体问题的种类，具有广泛的应用价值。,智能计算及其在数值计算中的应用,遗传算法是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程。遗传算法通过模拟达尔文“优胜劣汰、适者生存”的原理，激励好的结构；通过模拟孟德尔遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构。适应度：遗传算法中使用适应度这个概念来度量群体中的每个个体在优化计算中可能达到或接近最优解的程度。适应度较高的个体遗传到下一代的概率较大，而适应度较低的个体遗传到下一代的概率相对较小。度量个体适应度的函数称为适应度函数（Fitness Function）。,智能计算及其在数值计算中的应用,编码：在遗传算法的运行过程中，它不对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码施加遗传运算，通过遗传操作来达到优化的目的。在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。编码是应用遗传算法时首先要解决的问题，也是设计遗传算法的一个关键步骤。编码方法在很大程度上决定了如何进行群体的遗传进化运算，以及遗传进化运算的效率。目前的编码方法可以分为三大类：二进制编码、浮点数编码和符号编码。,智能计算及其在数值计算中的应用,遗传操作是遗传算法的核心，它直接影响和决定遗传算法的优化能力，是生物进化机理在遗传算法中的最主要体现，遗传算法的遗传操作包括选择、交叉和变异。选择（selection）：选择操作与生物的自然选择机制相类似，体现了“适者生存，优胜劣汰”的生物进化机理。根据适应度的大小来判断个体的优良，性状优良的个体有更大的机会被选择，产生后代。比例选择：个体被选中的概率与其适应度大小成正比。假设群体规模为M，个体i的适应度为，则个体i被选中的概率为,智能计算及其在数值计算中的应用,交叉（crossover）：交叉操作是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其它进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法，决定了遗传算法的全局搜索能力。,智能计算及其在数值计算中的应用,单点交叉：,算术交叉：,变异（mutation）：变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换从而形成一个新的个体。变异运算只是产生新个体的辅助方法，但也是一个必不可少的运算步骤，它决定了遗传算法的局部搜索能力。通过变异操作可以维持群体多样性，防止出现早熟现象，改善遗传算法的局部搜索能力。基本位变异：对个体编码串中以变异概率随机指定的某一位或某几位基因座上的基因值做变异运算。二进制中，把基因值取反，即0变1，1变0。浮点数编码中对选定的第i个个体进行逆转操作，如果浮点数变化范围是，则,智能计算及其在数值计算中的应用,遗传算法是一个迭代过程，它模拟生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的最优解或近似最优解。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对于一个需要进行优化计算的实际应用问题，可按下述步骤构造求解该问题的遗传算法:第一步：确定决策变量及其各种约束条件，即确定出个体的表现型和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型（求解目标函数的最大值还是最小值）及其数学描述形式或量化方法,智能计算及其在数值计算中的应用,第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型及遗传算法的搜索空间；第四步：确定解码方法，即确定出由个体基因型到个体表现型的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定出由目标函数值 到个体适应度值 的转换规则；第六步：设计遗传算法，即确定出选择、交叉、变异等遗传算子的具体操作方法；第七步：确定遗传算法的有关运行参数，包括个体数、进化代数、变异概率、交叉概率等。,智能计算及其在数值计算中的应用,智能计算及其在数值计算中的应用,具体的运算步骤：第一步：初始化，设置进化代数记数器，设置最大进化代数T，随机生成M个个体作为初始群体；第二步：个体评价，计算群体 中每个个体的适应度第三步：选择运算；第四步：交叉运算；第五步：变异运算，群体 经过选择、交叉、变异运算得到下一代群体；第六步：终止条件判断，若，则，转到第二步；若，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。,智能计算及其在数值计算中的应用,智能计算及其在数值计算中的应用,群体智能算法（Swarm Intelligence Algorithm）的研究开始于20世纪90年代，其基本思想是模拟自然界生物的群体行为来构造随机优化算法。典型的有蚁群算法、粒子群算法、人工鱼群算法等。粒子群优化（Particle Swarm Optimization，PSO）算法由美国社会心理学家James Kennedy和电气工程师Eberhart共同提出。基本思想是受到鸟群和鱼群群体觅食行为研究结果的启发，与基于达尔文“适者生存，优胜劣汰”进化思想不同，粒子群优化算法是通过个体间的协作来寻找最优解的。作为一种新的并行优化进化算法，粒子群优化算法具有很强的通用性，可用于解决大量非线性、不可微和多峰值的复杂问题优化，并已广泛应用于科学和工程领域。,智能计算及其在数值计算中的应用,自然界中各种生物体均具有一定的群体行为，人工生命的主要研究领域之一就是探索自然界生物的群体行为，从而在计算机上构建其群体模型。通常，群体行为可以由几条简单的规则进行建模，但群体表现出的行为却非常复杂。在对鸟群行为进行仿真时，可以采用下面三条简单规则：（1）飞离最近的个体，避免碰撞；（2）飞向目标；（3）飞向群体的中心。群体内的每一个体的行为可采用上述规则描述，这是粒子群算法的基本概念之一。,智能计算及其在数值计算中的应用,在研究人类的决策过程中，人们提出了个体学习和文化传递的概念。一个人在决策过程中，会使用两类重要的信息：一是自身的经验，二是其他人的经验。也就是说，人们根据自身的经验和他人的经验进行自己的决策。这是粒子群算法的另一基本概念。粒子群（PSO）算法与其它进化类算法相类似，也采用“群体”与“进化”的概念，同样也是依据个体（粒子）的适应度大小进行操作。粒子群算法将每个个体看作是在N维搜索空间中的一个没有重量和体积的粒子，并在搜索空间中以一定的速度飞行。飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。,智能计算及其在数值计算中的应用,假设 为粒子 的当前位置，为粒子 的当前飞行速度，为粒子 所飞过的最好位置，也就是粒子 所经历过的具有最好适应度的位置，称为个体最好位置。对于最小化问题，目标函数值越小，对应的适应度越好。为了讨论方便，设 为最小化的目标函数，则粒子 的当前最好位置由下式确定：,智能计算及其在数值计算中的应用,假设群体中的粒子数为，群体中所有的粒子所飞过的最好位置为，称为全局最好位置，则：有了上面的定义，基本粒子群算法的进化方程可描述为：式中，下标 表示粒子的第 维，即第 个决策变量；表示第 个粒子；表示代数；表示加速常数，通常在02之间取值；为两个相互独立均匀分布的随机函数。,智能计算及其在数值计算中的应用,从上述粒子进化方程可以看出，调节粒子飞向自身最好位置方向的步长，调节粒子向全局最好位置飞行的步长。为了减少在进化过程中，粒子离开搜索空间的可能性，通常限定于一定范围内，即。微粒的最大速度取决于当前位置与最好位置间区域的分辨率。若 太高，则微粒可能会飞过最好解；若 太小，则又将导致微粒移动速度过慢而影响搜索效率；而且当微粒聚集到某个较好解附近时，由于 过小而不利于微粒跳出局部最优解。通常设定为每个决策变量变化范围的10%20%，即如果问题的搜索空间限定在内，则可设定,智能计算及其在数值计算中的应用,基本粒子群算法的初始化过程为：（1）设定群体规模M，即个体的数量；（2）对任意i、j，在 内服从均匀分布产生；（3）对任意i、j，在 内服从均匀分布产生；（4）对任意i，设定。算法的运算过程：（1）依照上述初始化过程，对粒子群的随机位置和速度进行初始设定；（2）计算每个粒子的适应度；（3）对于每个粒子，将其适应度与所飞过的最好位置 的适应度进行比较，若较好，则将其作为当前的最好位置；,智能计算及其在数值计算中的应用,（4）对于每个粒子，将其适应度与全局所经历的最好位置的适应度进行比较，若较好，则将其作为当前的全局最好位置（5）根据公式对粒子的速度和位置进行进化计算；（6）如果没有达到结束条件，即适应度不够好或没有达到预先设定的最大进化代数，则返回步骤（2）。,智能计算及其在数值计算中的应用,基本粒子群算法的社会行为分析：速度进化方程分为三部分，第一部分为粒子原速度；第二部分为认知部分，仅考虑了粒子自身的经验，表示的是粒子自身的思考。如果速度进化方程只包含认知部分，即则算法性能变差。因为不同粒子之间缺乏信息交流，粒子间没有交互和社会信息共享，使得规模为N的群体等价于运行了N个单个粒子，得到最优解的概率非常小。,智能计算及其在数值计算中的应用,速度进化方程中第三部分为社会部分，表示粒子间的社会信息共享。如果方程只包含社会部分，则粒子没有认知能力，这样粒子在相互作用下，有能力达到新的搜索空间，虽然收敛速度比基本粒子群算法更快，但对于复杂问题，容易陷入局部最优点。,智能计算及其在数值计算中的应用,量子粒子群优化（Quantum-behaved Particle Swarm Optimization，QPSO）算法：从量子力学的角度，通过对粒子收敛行为的研究，基于粒子群优化算法提出的一种新的算法模型。在QPSO中，由于粒子满足聚集态的性质完全不同，使粒子在整个可行解空间中进行搜索寻求最优解，因而QPSO在搜索能力上远远优于所有已开发的PSO，通过理论分析证明QPSO是一个全局收敛算法。同时，QPSO具有参数少、易于编码实现等特点。,智能计算及其在数值计算中的应用,QPSO中粒子的位置更新方程为：式中t是算法的当前迭代次数，D为粒子的维数，N为粒子个数，是均匀分布在（0,1）上的随机数，当时，上式 前面取负号，否则取正号。由下式确定：式中 为在（0,1）上均匀分布的随机数，为第i个粒子的当前最优位置，为当前群体的全局最优位置。,智能计算及其在数值计算中的应用,称为压缩-扩张因子，是QPSO中的唯一参数，调节其值能控制算法的收敛速度，一般采用线性减小的取值策略，即 的值随迭代次数的增加而线性减小，方程如下：式中 分别是迭代初始值和终止值，一般取值为或 效果较好。称为平均最优位置，是所有粒子自身最优位置的中心点，由下式计算得到：,智能计算及其在数值计算中的应用,智能计算及其在数值计算中的应用,pNum=1000;%粒子数pDim=4;%粒子维数gen=300;%迭代次数X1min=-100;X2min=-100;X3min=-100;X4min=-100;X1max=100;X2max=100;X3max=100;X4max=100;%变量范围%粒子初始化am=rand(pNum,pDim);%随机数辅助变量Pc(:,1)=X1min+(X1max-X1min)*am(:,1);Pc(:,2)=X2min+(X2max-X2min)*am(:,2);Pc(:,3)=X3min+(X3max-X3min)*am(:,3);Pc(:,4)=X4min+(X4max-X4min)*am(:,4);,56页例题1(线性方程组),智能计算及其在数值计算中的应用,%计算适应度fitness=zeros(pNum,1);for kk=1:pNum a1=abs(5*Pc(kk,1)+Pc(kk,2)-Pc(kk,3)-2*Pc(kk,4)+2);a2=abs(2*Pc(kk,1)+8*Pc(kk,2)+Pc(kk,3)+3*Pc(kk,4)+6);a3=abs(Pc(kk,1)-2*Pc(kk,2)-4*Pc(kk,3)-Pc(kk,4)-6);a4=abs(-Pc(kk,1)+3*Pc(kk,2)+2*Pc(kk,3)+7*Pc(kk,4)-12);fitness(kk,1)=(a1+a2+a3+a4);endpBestp=Pc;%粒子局部最优pBestf=fitness;gBestf index=max(fitness);%全局最优值(适应度)gBestp=Pc(index,:);%全局最优值(个体)Best=zeros(gen+1,pDim+1);%记录最优值变化Best(1,1)=gBestf;Best(1,2:pDim+1)=gBestp;,智能计算及其在数值计算中的应用,for gm=1:gen gm mbest=mean(pBestp);%中值最优位置 c=rand(pNum,1);pp=c c c c.*pBestp+(1-c)*gBestp;u=rand;beita=1.2-0.8*gm/gen;if u0.5 Pc=pp-beita*abs(ones(pNum,1)*mbest-Pc)*log(1/u);else Pc=pp+beita*abs(ones(pNum,1)*mbest-Pc)*log(1/u);end%适应度 for kk=1:pNum a1=abs(5*Pc(kk,1)+Pc(kk,2)-Pc(kk,3)-2*Pc(kk,4)+2);a2=abs(2*Pc(kk,1)+8*Pc(kk,2)+Pc(kk,3)+3*Pc(kk,4)+6);a3=abs(Pc(kk,1)-2*Pc(kk,2)-4*Pc(kk,3)-Pc(kk,4)-6);a4=abs(-Pc(kk,1)+3*Pc(kk,2)+2*Pc(kk,3)+7*Pc(kk,4)-12);fitness(kk,1)=(a1+a2+a3+a4);end,智能计算及其在数值计算中的应用,for gn=1:pNum%限定范围 if Pc(gn,1)X1max Pc(gn,1)=2*X1max-Pc(gn,1);end,%选择个体局部最优和全局最优 if fitness(gn,1)pBestf(gn,1)pBestp(gn,:)=Pc(gn,:);pBestf(gn,1)=fitness(gn,1);end if fitness(gn,1)gBestf gBestf=fitness(gn,1);gBestp=Pc(gn,:);end end Best(gm+1,1)=gBestf;Best(gm+1,2:pDim+1)=gBestp;end,智能计算及其在数值计算中的应用,计算结果(1.0000,-2.0000,-1.0000,3.0000)91页例题3(非线性方程)：fitness(kk,1)=abs(Pc(kk,1)3-Pc(kk,1)2-1);计算结果:1.4656,非线性方程组：精确解为（4,3,1）,智能计算及其在数值计算中的应用,智能计算及其在数值计算中的应用,for kk=1:pNum a1=abs(Pc(kk,1)Pc(kk,2)+Pc(kk,2)Pc(kk,1)-5*Pc(kk,1)*Pc(kk,2)*Pc(kk,3)-85);a2=abs(Pc(kk,1)Pc(kk,3)-Pc(kk,2)Pc(kk,3)-Pc(kk,3)Pc(kk,2);a3=abs(Pc(kk,1)Pc(kk,3)+Pc(kk,3)Pc(kk,1)-Pc(kk,2)-2);fitness(kk,1)=(a1+a2+a3);end,计算结果(4.0000,3.0000,1.0000),智能计算及其在数值计算中的应用,声线参数反演算例计算结果：,最优适应度值对应的,参考文献：1 曾建潮，介婧，崔志华。微粒群算法。科学出版社，20042 施光燕，董加礼。最优化方法。高等教育出版社，19993 周明，孙树栋。遗传算法原理及应用。国防工业出版社，19994 张文修，梁怡。遗传算法的数学基础。西安交通大学出版社，20005 李守巨，刘迎曦，孙伟。智能计算与参数反演。科学出版社，20086 焦李成，杜海峰，刘芳，公茂果。免疫优化计算、学习与识别。科学出版社，20077 Sun J,Feng B,Xu WB.Particle swarm optimization with particles having quantum behavior.IEEE Con.Evolutionary Computation.2004:325-331P8 方伟，孙俊，谢振平 等.量子粒子群优化算法的收敛性分析及控制参数研究.物理学报，2010,59(6):3687-3694页9 杨坤德。水声阵列信号的匹配场处理。西北工业大学出版社，2008,智能计算及其在数值计算中的应用,