第1章优化算法基本理论

智能优化算法

第一章优化算法基本理论

第二章神经网络基本理论

第三章遗传算法基本理论

第四章蚁群算法基本理论

第五章蜂群算法基本理论

第六章粒子群算法基本理论

第七章鱼群算法基本理论

第八章其他群智能优化算法课程结构及学时安排1.1

优化的概念与方法

1.1.1优化的概念1.1.2优化的一般数学模型

1.1.3优化的分类

1.1.4优化问题的求解方法

1.1.5

常用的无约束优化方法1.2智能优化的概念及分类

1.2.1智能优化的概念1.2.2智能优化的分类1.3群体智能的概念及分类

1.3.1群体智能的概念1.3.2群体智能的分类

1.3.3群体智能的特点1.3.2群体智能算法的一般流程第1章优化算法基本理论1.1优化的概念及方法

1.1.1优化的概念优化、最优化均是一个术语，是指关于求解一个问题的“最优”解的计算科学的一个分支，也就是从各种可能方案中选取一个最好的，以达到最优目标。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。1.1优化的概念及方法

优化技术是一种以数学为基础、用于求解各种工程问题优化解的应用技术。1.1.2优化的一般数学模型

数学模型

s.t.式中，，即为n维矢量，也称为决策变量；、和均为的函数，称为目标函数，称为等式约束函数，称为不等式约束函数；s.t.为英文subjectto的缩写，表示“受限制于”。对于求目标函数极大值的问题，可以转化为求极小值。

1.1优化的概念及方法

几个定义

♣可行解：又称为可行点或容许解，是指满足约束条件的。♣可行域：又称为容许集，是指全体可行解构成的集合，即若和为连续函数，则D是闭集。♣最优解：一般分为整体最优解（总体最优解）、严格整体最优解、局部最优解、严格局部最优解。♣整体最优解：若，对于一切恒有，则称为最优问题的整体最优解。1.1优化的概念及方法1.1优化的概念及方法

♣严格整体最优解：若，对于一切和恒有，则称为最优问题的严格整体最优解。♣局部最优解：若，存在的某邻域（），使得对于一切，恒有，则称为最优问题的局部整体最优解。♣严格局部最优解：若，存在的某邻域（），使得对于一切，恒有，则称为最优问题的严格局部整体最优解。♣最优值：最优解对应的目标函数值称为最优值。

♣范数：在n维线性空间中，定义实函数，使其满足以下三个条件：

①对于任意，有，当且仅当，；

②对于任意及实数，有；

③对于任意，有。则称函数为上的向量范数。♣

p-范数：对于任意，，定义p-范数为1.1优化的概念及方法

♣∞-范数：

♣2-范数：，通常记作

整体最优解与局部最优解的关系整体最优解一定是局部最优解，而局部最优解不一定是整体最优解。1.1优化的概念及方法1.1.3优化的分类

根据约束条件分类♣无约束最优化问题：没有约束条件限制的最优化问题。♣约束最优化问题：有约束条件的最优化问题。约束最优化问题又可分为

♣等式约束最优化问题：

♣不等式约束最优化问题：♣混合约束最优化问题：既有等式约束，又有不等式约束最优化问题。即1.1优化的概念及方法1.1优化的概念及方法根据决策变量取值的状态分类♣连续最优化问题：决策变量取值是连续的优化问题。♣离散最优化问题：决策变量取值是离散的优化问题。

根据决策变量取值的性质分类♣确定性最优化问题：每个决策变量取值是确定的。♣随机性最优化问题：某些决策变量取值是不确定的，但知道决策变量取某值而服从一定的概率分布。

按照目标函数和约束函数的劳累性分类♣线性最优化问题：目标函数和所有约束条件中的函数都是决策变量的线性函数，即、和均为的线性函数。1.1优化的概念及方法

♣非线性最优化问题：目标函数或约束条件中至少有一个是决策变量的非线性函数，即、和中至少有一个是的非线性函数。

按照最优化解是否变化分类♣静态最优化问题：最优化问题的解不随时间而变。♣动态最优化问题：最优化问题的解随时间而变化。

按照目标函数的个数分类♣单目标最优化问题：最优化问题中只有一个目标函数。♣多目标最优化问题：最优化问题中含有多个目标函数。1.1.4优化问题的求解方法

一般思路

最优化问题的一般求解方法是迭代算法。首先给定一个初始可行点（即初始值），然后从此点出发，依次产生一个可行点列，记作，使得某个恰好是问题的一个最优解，或者说该点列收敛到问题的一个最优解。一般步骤包括：

①给定初始点，即令；

②确定处的下降方向，使得点沿方向移动时函数值有所下降；

③确定步长，令使得；1.1优化的概念及方法1.1优化的概念及方法④若满足某种终止准则，则停止迭代，以为近似最优解。否则令转①。

影响算法收敛的条件

♣如果某算法构造出的点列能够在有限步之内得到最优化问题的最优解，或者说点列有极限点，且其极限点就是最优解，则称算法是收敛的。算法收敛的影响因素较多，包括初始点的选取、下降方向的确定、迭代步长的选择以及目标函数自身的影响。除要求收敛外，一般还要求收敛速度要快。♣收敛：设序列，对于，存在正整数N，当时，有，则称收敛于。1.1优化的概念及方法

♣线性收敛：设序列收敛于，且若，则称序列为线性收敛，为收敛比；若，则称序列为超线性收敛；若，则称序列为次线性收敛。

♣

p阶收敛：设序列收敛于，若对于某个实数，有则称序列为p阶收敛，一般情况下，称为二阶收敛。1.1优化的概念及方法常用的终止准则

♣（，预先给定）或；♣，；♣；

♣上述三种终止准则的组合。1.1.5常用的无约束优化方法

常用的无约束最优化方法包括最速下降法和牛顿法等。

最速下降法最速下降法又称为梯度法、梯度下降法，是1847年由著名数学家Cauchy推导而出。根据泰勒公式得由此可见，当时，，符合迭代要求。1.1优化的概念及方法

由于，为和的夹角。故当时，取得极小值，下降最快。一般取，得到即负梯度方向使目标函数下降最快，称为最速下降法。

牛顿（Newton）法牛顿（Newton）法最初由艾萨克·牛顿（IsaacNewton，1643年1月4日~1727年3月31日）在《流数法》（MethodofFluxions）首次提出（1671年完成，在牛顿死后的1736年公开发表），同时约瑟夫·拉弗森（JosephRaphson，1648年~1715年）也曾于1690年在AnalysisAequationum中提出此方法。故有时称为牛顿-拉弗森法。1.1优化的概念及方法

设二阶连续可导，对在处进行泰勒展开，得设为的近似最优解，得到即得到牛顿迭代公式为1.1优化的概念及方法

最速下降法的应用以最小均方算法（简称LMS）为例。如图1-1为一横向滤波器图中，为输入矢量，为抽头系数矢量。1.1优化的概念及方法图1-1横向滤波器结构图

设为系统的期望响应信号，为滤波器实际输出相对于的误差，即按照最小均方误差准则（简称MMSE），定义滤波器的输出与期望响应之间的均方误差（简称MSE）为代价函数，即定义为滤波器输入序列的自相关矩阵，是一个L×L阶方阵；为互相关矩阵。于是，上式可表示为1.1优化的概念及方法

根据最小均方误差准则，使上式对W的梯度（即偏导）为零，即则可得到

的最佳值

应满足方程式中，称为横向滤波器的维纳解，即最佳滤波器系数矢量。由于均方误差函数（即代价函数）是滤波器系数的二次方程，故形成了一个多维的超抛物曲面，好象一个碗状曲面且只有唯一的碗底最小点，通常称为滤波器的误差性能曲面。当给定初始值时，均方误差就位于误差性能曲面上的某一点，系数的自适应调节使得均方误差超碗底的最小点方向移动，最终到达碗底的最小点，实现了最佳维纳滤波。1.1优化的概念及方法

在自适应算法中，人们提出了不少梯度估计的方法，其中最著名、应用最广的是B.Widrow提出的LMS算法。其算法的核心思想是用平方误差代替均方误差，即代价函数变为根据最陡下降法得到LMS自适应均衡算法公式为式中，为步长因子。1.1优化的概念及方法1.2智能优化的概念及方法1.2智能优化的概念及方法

1.2.1智能优化的概念人工智能（ArtificialIntelligent，简称AI）是在计算机科学、控制论、信息论、哲学、语言学等多种学科研究基础上发展起来的一门综合性交叉学科。即人工智能就是用人工的方法在机器（计算机）上实现的智能，或者说是人们使机器具有类似于人的智能。智能优化算法（intelligentoptimizationalgorithms）是以模拟物质变化过程或模拟生命体而设计的搜索方式为基础的各类算法的总称。有时也称为启发式算法（modernheuristicalgorithms）、仿生算法、演化算法或进化算法。1.2智能优化的概念及方法

智能优化算法的本质都属于随机性算法，最大优点是不需要目标函数具有可导性，甚至不需要目标函数有明确的表达形式，只要知道输入输出即可。1.2.2智能优化的分类兔子理论：为了找出地球上最高的山，一群兔子开始想办法。

兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。

兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。1.2智能优化的概念及方法兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。

兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。1.3群体智能的概念及方法1.3群体智能的概念及方法

1.3.1群体智能的概念群体智能（SI）简称群智能，指的是简单智能的个体通过合作表现出复杂智能行为的特性，也就是无智能的主体通过合作表现出智能行为的特性。其本质上是一种概率搜索，不需要问题的梯度信息。群体智能算法的基本思想是模拟自然界生物的群体行为来构造随机优化算法。将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体，将求解问题的目标函数度量成个体对环境的适应能力，将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。1.2智能优化的概念及方法

因此，形成一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。也可以说，群智能是一种自下而上的优化方法，即首先设计单个实体的感知、行为机制，然后将一个或一群实体置于环境中，让它们在与环境的交互作用中解决问题。1.3.2群体智能的分类由于群体智能是由社会性动物的自组织行为产生的，因此新算法不断涌现。根据目前的有关报道，主要有粒子群算法、蚁群算法、鱼群算法、蜂群算法、蛙跳算法、布谷鸟算法、萤火虫算法、蝙蝠算法、磷虾群算法、细菌觅食算法、烟花算法、头脑风暴算法、智能水滴算法、磁铁算法等等。1.2智能优化的概念及方法1.3