智能优化算法_4

下标从1开始！！

• ：相当于不等于!=

• eps表示的是一个数可以分辨的最小精度，返回1.0和下一个精度最高的双精度浮点数的差值， 即2^(-52)。

• Inf和-Inf分别代表正无穷和负无穷

• y= 函数计算指定向量或矩阵的长度y。如果参数变量x是向量，则返回其长度；如果参数变量是非空矩阵，则length(x)与max(size(x))等价

矩阵取值

• v(m , : )：取第m行
• v( : ，m)：取第m列
• v(x,y)：取第x行第y列

矩阵计算

• [SortFit1,Index]=：对Fit进行排序，排序结果放入SortFit1矩阵，结果每位上的元素在原来列上的序号放入Index矩阵
• [aa,bb]=：aa=行数，bb=列数
• ：对矩阵x进行逐列累加，例：[a,b,c,d]=>[a,a+b,a+b+c,a+b+c+d]
• ：对矩阵x进行逐列求和，即每列之和

取整函数

• fix朝零方向取整，如fix(-1.3)=-1; fix(1.3)=1;
• ，顾名思义，就是地板，所以是取比它小的整数，即朝下取整，如floor(-1.3)=-2; floor(1.3)=1;floor(-1.8)=-2，floor(1.8)=1
• ，与floor相反，它的意思是天花板，也就是取比它大的最小整数，即朝上取整，如ceil(-1.3)=-1; ceil(1.3)=2;ceil(-1.8)=-1，ceil(1.8)=2
• 四舍五入到最近的整数，如round(-1.3)=-1;round(-1.52)=-2;round(1.3)=1;round(1.52)=2

生成随机数函数

• rand 生成均匀分布的伪随机数。分布在（0~1）之间
  • rand(m,n)生成m行n列的均匀分布的伪随机数
• randn 生成标准正态分布的伪随机数（均值为0，方差为1）
• randi 生成均匀分布的伪随机整数
  • randi(iMax)在闭区间[1，iMax]生成均匀分布的伪随机整数
  • randi(iMax，m，n)在开区间[1，iMax]生成mXn型随机矩阵
  • r=randi([iMin,iMax],m,n)在开区间[iMin，iMax]生成m*n型随机矩阵
• randperm 生成整数的随机排列

排序函数

按升序对 的元素进行排序。

• 如果 是向量，则 对向量元素进行排序。
• 如果 是矩阵，则 会将 的列视为向量并对每列进行排序，从上到下，从小到大
• 如果 是多维数组，则 会沿大小不等于 1 的第一个数组维度计算，并将这些元素视为向量

复制函数

生成重复数矩阵

• 若A是一个数，则生成x*y的矩阵，全是A
• 若A是一个矩阵，将矩阵A复制2行3列

代表人物汇总

算法名	英文名	代表人物
遗传算法GA	Genetic Algorithm	J.H.Holand
差分进化算法DE	Differential evolution	Storn
免疫算法IA	Immune algorithm	Burnet
蚁群算法ACO	Ant Colony optimization	M.Dorigo，V.Maniezzo，A.Colorni
粒子群算法PSO	Particle swarm optimization	James Kennedy，Rusell Eberhart
模拟退火算法SA	Simulated annealing	Metropolis
禁忌搜索算法TS	Tabu Search	Glover
神经网络算法NN	Neural Newwork	McCulloch，Pitts，J.J.Hopfield

算法特点汇总

算法名字	特点	优缺点
遗传算法	群体搜索策略和简单的遗传算子	全局搜索能力强，局部搜索能力较弱，早熟，算法收敛性无法保证
差分进化算法
免疫算法
蚁群算法
粒子群算法		收敛速度快但容易陷入局部最优解
模拟退火算法
禁忌搜索算法
神经网络算法

? 遗传算法模拟生物在自然环境中的遗传和进化的过程，从而形成自适应全局优化搜索算法，它借用了生物遗传学的观点，通过自然选择，遗传，变异等机制，实现各个个体适应性的提高

名词解释

遗传学术语	遗传算法术语
群体	可行解集
个体	可行解
染色体	可行解的编码
基因	可行解编码的分量
基因形式	遗传编码
适应度	评价函数值
选择	选择操作
交叉	交叉操作
变异	变异操作

• 群体规模Np：群体规模将影响遗传优化的最终结果以及遗传算法的执行效率。一般取10~200。
• 交叉概率Pc：交叉概率控制着交叉操作被使用的频度。一般取0.25~1.00。
• 变异概率Pm：变异的主要目的是保持群体的多样性，一般地频度的变异可防止群体中重要基因的丢失。一般取0.001~0.1。
• 遗传运算的终止进化代数G：终止遗传代数表示遗传算法运行到指定的进化代数之后就停止运行。一般取100~1000。

轮盘赌选择（Roulette Wheel Selection）

一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例

轮盘赌选择法是最简单也是最常用的选择方法，在该方法中，各个个体的选择概率和其适应度值成比例，适应度越大，选中概率也越大。但实际在进行轮盘赌选择时个体的选择往往不是依据个体的选择概率，而是根据“累积概率”来进行选择。

例子：

1. 假设群体 A：a, b, c, d, e
2. 适应度 F1：0.45, 0.1, 0.1, 0.15, 0.2
3. 对F1进行累加操作得到F2（累积概率）：0.45, 0.55, 0.65, 0.8, 1.0
4. 生成排序随机队列MS：0.2, 0.3, 0.4 , 0.7 ,0.8 ,0.9
5. 选择完成群体 B：a, a, a, d, e, e

合并新旧种群取最优

该选择策略，是在交配产生的新子代和父代中，通过合并子代和父代，并且按照个体的适应度进行排序，选择适应度最佳的前 NP 个个体作为新的种群，达到更好的收敛的效果。

例子：

1. 父代个体parent : a,b,c
2. 父代适应度parent_obj : 1 , 5 , 3
3. 子代个体son : d , e , f
4. 子代适应度son_obj : 2 6 4
5. 合并个体total=a,b,c,d,e,f
6. 合并适应度total_obj : 1,5,3,2,6,4
7. 适应度排序order : e,b,f,c,d,a
8. 前 NP=3个作为下一代：save=e,b,f

单点交叉

单点交叉通过选取两条染色体，在随机选择的位置点上进行分割并交换右侧的部分，从而得到两个不同的子染色体。

例子：

（空格处代表该处为随机生成的交叉点，往后的基因需要进行交换操作）

待交叉染色体： 11111 22222

? 33333 44444

交换后染色体： 11111 44444

? 33333 22222

君主交叉

君主交叉就是在种群内选择出最优个体，用最优个体作为君主染色体，并随机生成交叉位点，然后将君主染色体的特定位点上的基因遗传给子代染色体。

例子：

（中间空格分隔的基因代表随机生成的交叉位点，该位点上的基因需要遗传给子代染色体）

待交叉染色体： 101000 1 101

? 011001 0 011

交换后染色体： 101000 1 101

? 011001 1 011

多点奇偶交叉

• 先规定一个交叉率，然后循环奇数位
• 每次生成一个随机数，判断是否小于交叉率
  • 如果是，则进行交叉
    • 对二进制位上每一位取随机数，如果等于1，则与偶数位同位置的数进行交换
  • 如果不是，则跳过交叉

通过变异率计算第i个个体的j个基因二进制位上会发生变异，即取反

域内随机值

描述：

对新种群内的所有染色体每个基因进行变异操作，先通过随机值和变异率去判断该基因是否会发生变异，再通过随机值在基因的取值范围内进行改变。

例子：

1. 在所有染色体中随机挑选 NP * Pm 个染色体进行变异
2. 假设挑选出染色体h1：11000011
3. 随机挑选 L（染色体长度，基因个数） * Pm 个基因进行变异
4. 挑选下标：1,2,4
5. h2：00101011（下标1,2,4处基因取反）

奇偶交叉GA1

君主交叉GA2

GA算法求解旅行商问题

差分演化算法是一种基于群体差异的启发式随机搜索算法，将问题的求解表示成"染色体"的适者生存过程，通过"染色体"群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到"最适应环境"的个体，从而求得问题的最优解或满意解。

? 种群数量Np：一般来说，种群数量越大，种群的多样性也就越大，寻优能力也就越强，但也会增加计算的难度。为了算法具有足够的不同的变异向量，Np >=4。一般取5D~10D。（D为变量维数）

? 变异算子F：变异算子 F∈[0, 2] 决定偏差向量的缩放比例。F过小，可能造成算法“早熟”，容易陷入局部最优；F过大，算法很难快速收敛到最优值。F=0.5通常是一个较好的初始选择。如果种群过早收敛，那么 F 或 Np 应该增大。

? 交叉算子CR：交叉算子 CR∈[0, 1]控制着一个试验向量参数来自随机选择的变异向量而不是原来的向量的概率。CR越大，发生交叉的概率越大。CR的一个较好选择是 0.1，但较大的 CR通常会加速收敛。为了尝试获得一个快速解，可以先尝试 CR=0.9 或 CR=0.1。

DE/rand/1/bin

描述：

1. 对需要变异的染色体 m，通过随机值选择 3 条互不相同且与染色体 m 也不相同的其他染色体 r1, r2, r3
2. 利用变异算子对 r2, r3 的差异进行缩小，
3. r2, r3与 r1 进行合并后替换到原染色体 m 上，完成变异过程。

DE/rand/1/bin + 自适应变异

描述：

在 DE/rand/1/bin 的基础上，针对变异算子进行自适应计算。此自适应计算的方法可以基于变异代数，对于变异代数越高的变异操作，可以考虑减小变异算子，从而做到更好的收敛效果。

自适应算子计算

将变异算子中随机选择的三个个体Xb,Xm,Xw进行计算得变异种群数组

DE 交叉

描述：

同时采用随机选择和概率遗传两种方法，随机选择通过随机选择一位基因进行变异替换，概率遗传通过概率值决定是否采用变异后的基因进行交叉。这样可以确保子代至少有一个基因来自变异。

二项式交叉

贪婪准则：对原种群和变异后种群每个个体一对一进行判断，取适应度更高的作为下一代种群

DE/rand/1/bin + 自适应变异

免疫算法是模仿生物免疫机制，结合基因的进化机理，人工构造出的一种新型智能优化算法。采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解。相比于其他算法，免疫算法利用自身产生多样性和维持机制的特点，保证了群体多样性，克服了‘早熟’问题，可以得到全局最优解。具有自适应性，随机性并行性，全局收敛性，种群多样性等特点。

生物免疫系统	免疫算法
抗原	优化问题
抗体（B细胞）	优化问题的可行解
亲和度	可行解的质量
细胞活化	免疫选择
细胞分化	个体克隆
亲和度成熟	变异
克隆抑制	克隆抑制
动态维持平衡	种群刷新

• 抗体种群大小Np：保留了免疫细胞的多样性，种群越大，算法全局搜索能力越好，但算法每代的计算量也就相应增大。一般取10~100，且200以内。

• 免疫选择比例：免疫选择的抗体数量越多，产生抗体越多，搜索能力越强，但增加每代计算量。一般取0.1Np

  0.5Np

• 抗体克隆扩增的倍数：决定了克隆扩增的细胞的数量，从而决定算法的搜索能力。数值越大，局部搜索能力越强，全局搜索能力也有一定提高，但是计算量增大。一般取5~10。
• 种群刷新比例：细胞的淘汰和更新是产生抗体多样性的重要机制，从而对免疫算法的全局搜索能力产生重要影响。一般不超过0.5Np。
• 算子
  • 亲和度评价算子：相当于遗传算法中的适应度，与具体问题相关
  • 抗体浓度评价算子：表征抗体种群的多样性好坏，浓度过高意味非常类似个体大量存在；不利于全局优化
  • 激励度算子：对抗体质量的最终评价结果，通常亲和度大，浓度低的抗体会得到较大激励度
  • 克隆抑制算子：用于对经过变异后的克隆体进行再选择，抑制亲和度低的抗体(重新生成随机新生种群-种群刷新)，保留亲和度高的抗体作为免疫种群，最后免疫种群与新生种群进行进行合并

前 NP / 2 个激励度高的个体指针对 NP/2 个激励度高的个体进行交叉和变异，目的是试图产生激励度更高的个体。随机生成指针对另一半的个体产生采用随机生成的方式，保证了种群中不断有新个体的加入。

抗体间亲和度计算

对于实数编码，亲和度通常可以使用抗体向量间的欧氏距离来计算

抗体浓度计算

抗体浓度公式

其中N为种群规模，S(abi, abj)表示抗体间的相似度，具体表示如下

相似度检查

若小于相似度阈值，则设为1

激励度计算

激励度算子就是抗体的综合评价，计算方式如下，二者取其一，其本质目的是为了共同考虑亲和度和浓度，从而筛选下一代的抗体

变异操作

变异源邻域

描述：

在需要变异的个体染色体中，通过添加一个扰动，从而使其偏离原来的位置落入原个体相邻的另外一个位置中，从而实现变异源领域的搜索。

实数编码算法变异计算

交叉操作

克隆抑制

描述：

对于克隆产生的所有个体进行亲和度的计算，然后保留亲和度最高的个体，从而实现交叉操作。

例子：

1. 原个体亲和度为 10
2. 克隆后新个体亲和度分别为 [12，6，34，43，2，15，3，8，19，22]
3. 将10个新个体和原个体合并后取亲和度最高的个体，即亲和度为 43 的个体

蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。

在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度， 并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。

由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并 倾向于选择一条较短的路径前行。

这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的 最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。

• 构建解
  • 状态转移概率
    • 启发式信息
      • 启发因子：城市间距离的倒数
    • 信息素
• 信息素
  • 蒸发
  • 增量
    • 最优解
    • 走过部分解

• 信息素启发式因子α：代表信息量对是否选择当前路径的影响程度，反应蚂蚁在运动过程中所积累的信息素在知道蚁群搜索中的相对重要程度。一般取α ∈[1, 4]。
• 期望启发因子β：表示在搜索时路径上的信息素在指导蚂蚁选择路径时的向导性，反映蚁群在搜索最优路径的过程中的先验性和确定性因素的作用强度。一般取β ∈[3, 5]。β越大，蚂蚁在某个局部点上选择局部最短路径可能性越大，算法收敛速度越快，但随机性越弱，容易陷入局部最优解
• 信息蒸发系数p：p ∈[0,1]，表示信息素的蒸发程度，反映了蚂蚁群体中个体之间相互影响的强弱。p过小时，影响算法的随机性能和全局搜索能力；p过大是，降低算法的收敛速度。
• 信息素强度Q：代表计算信息素增量的一个取值
• 蚂蚁数目m：蚂蚁数量增多，提高算法的全局搜索能力和稳定性，但正反馈作用不明显，收敛速度减慢；蚂蚁数量减少，收敛速度加快，但算法全局性能降低，稳定性差，容易出现过早停滞现象。一般取10~50。

选择

采用的是轮盘赌的方式，其概率的计算是基于信息素和距离权重的，公式如下（ 为信息素， 为距离权重）

信息素更新

信息素增量计算公式，其中 Q 信息素强度系数， 为第 k 只蚂蚁在本轮周游中所走过的路径的长度

信息素蒸发量计算公式，其中  表示路径上信息素的蒸发系数，表示信息素的持久性系数

蚁群算法解决旅行商问题

粒子群算法模拟鸟群的捕食行为，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

• 粒子种群规模N：粒子数目越大，算法搜索的空间范围就越大，也就更容易发现全局最优解，但算法运行时间也就越长。一般10个粒子已经可以取得比较好的结构。对于比较难的问题或特定的问题，粒子的数量可以取到100或200。
• 惯性权重w：代表对粒子当前速度继承的多少，用来控制算法的开发和探索能力。权重较大时，全局寻优能力较强，局部寻优能力较弱；权重较小时，全局寻优能力较弱，局部寻优能力较强。一般取0.8~1.2。
• 加速常数c1和c2：分别调节向 pbest 和 gbest方向飞行的最大步长，他们分别决定粒子个体经验和群体经验对粒子运行轨迹的影响。通常可以取c1=c2=1.5。

PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解，在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。

第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，

另一个极值是整个种群找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。

• 粒子的速度及位置更新的方式如下：

1. 其中
2. 粒子的速度更新公式由三部分组成：粒子先前速度+个体最优+全局最优
3. 是一个非负数，称为惯性因子，对算法的收敛起到很大的作用，其值越大，粒子飞跃的范围就越广，更容易找到全局最优，但是也会错失局部搜寻的能力。
4. 分别为局部和全局最优位置。
5. 加速常数 也是非负常数，是调整局部最优值和全局最优值权重的参数，如果前者为0说明搜寻过程中没有自身经验只有社会经验，容易陷入局部最优解；若后者为0，即只有社会经验，没有自身经验，常常会陷入局部最优解中，不能飞越该局部最优区域。
6. 是[0,1]范围之内的随机数， 是约束因子，目的是控制速度的权重。

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小，即所求值

能量即目标函数，能量最低态即最优解，

温度是Metropolis算法的一个重要控制参数，开始时T大，可以接受较差恶化解；随着T减小，只能接受较好的恶化解了

根据Metropolis准则，粒子在温度T时趋于平衡的概率为 ，其中 为温度 时的内能，ΔE为其改变数, 为 常数。 准则常表示为

1. 系统从一个能量状态变化到另一个能量状态时(根据当前温度产生新解：邻域随机选取+边界处理)，相应的能量从Eold变化到Enew
2. 若新状态是全局最优，则更新全局最优解，保留上一个最优解
3. Metropolis过程
   1. 若状态向下(局部最优)，则接受新解
   2. 若状态向上(全局搜索)，则以一定概率接受()
4. 在系统每次变化时，T也在冷却，。当T趋向于0(设置一个小值，如0.001)时，求得问题整体最优解

基本思想：

采用邻域选优的搜索方法，为了逃离局部最优解，算法必须能够接受劣解，也就是每一次得到的解不一定优于原来的解。

但是，一旦接受了劣解，算法迭代即可能陷入循环。为了避免循环，算法将最近接受的一些移动放在禁忌表中，在以后的迭代中加以禁止。即只有不再禁忌表中的较好解（可能比当前解差）才能接受作为下一代迭代的初始解。

随着迭代的进行，禁忌表不断更新，经过一定的迭代次数后，最早进入禁忌表的移动就从禁忌表中解禁退出。

• 遗传算法
  • 最早是由美国的 John Holland于20世纪70年代提出
  • 能有效求解NP问题(所有的非确定性多项式时间可解的判定问题构成NP类问题)，以及非线性，多峰函数优化和多目标优化问题
• 差分进化算法
  • 由Storn和Price于1995年首次提出
• 免疫算法
  • 1958年澳大利亚学者Burnet率先提出克隆选择原理
  • 1973年Jerne提出免疫系统的数学框架
• 蚁群算法
  • 由Marco Dorigo于1992年在他的博士论文中提出
  • 蚁群算法是一种用来寻找优化路径的概率型算法，灵感来源于蚂蚁在寻找食物过程中发现路径的行为
• 粒子群算法
  • 由Eberhart博士和kennedy博士发明
• 模拟退火算法
  • 最早的思想是由Metropolis等人于1953年提出。1983 年,Kirkpatrick 等成功地将退火思想引入到组合优化领域。
  • 模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数目标函数)的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。
• 禁忌搜索算法
  • 由Glover教授于1986年在一篇论文中首次提出
  • 从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。
• 神经网络算法
  • 最早由McCulloch与Pitts提出形式神经元数学模型
  • 由Hopfield提出具有联想记忆功能的Hopfield神经网络，标志神经网络取得重大进展
  • 用大量的简单计算单元（神经元）构成非线性系统，在一定程度上模拟了大脑的信息处理、存储和检索等功能。
  • 常见网络结构
    • 前馈神经网络
    • 反馈神经网络
      • BP网络的误差反向后传学习算法，是最常用的神经网络算法。它利用输出后的误差来估计输出层的直接前导层误差，再利用这个误差更新前一层的误差，如此反传下去获得所有其他各层的误差估计。
    • 自组织网络

• tall：运行计时

• mean：平均

• gen：代数

• fes：函数评价次数

• trace：最优值

注意输出信息最终应该包括：

• 测试的函数名Fname算法参数取值，如D, Pc, Pm, NP,MAXG, MAXRUN等

• 表3最优函数值bestfun, 最差函数值worstfun，平均值meanfun,标准差stdfun，算法总体平均用时meantotaltimes(s)

• 表4首次获得至今最优解值对应的平均代数meanbestGen，对应的函数评价次数meanbestFEs，对应的用时meanbesttime(s)，统计得到的成功次数success%