本人还在学习，边学边完善

1. 退火算法

• 优点是 局部搜索能力强,运行时间较短；
• 缺点 是全局搜索能力差,容易受参数的影响.

2. 遗传算法

遗传算法基本原理和方法
选择算子的c语言实现
遗传算法-课本

2.1 本质

• 是适应算法，应用最多的是系统最优化的研究。
• 用途：解决优化类问题

2.2 算法思想

• 按照适者生存的原理，逐代演化产生越来越好的近似解。使用遗传算法三个步骤：编码与解码、计算个体适应度、遗传操作（选择、交叉、变异）借助于自然遗传学 的遗传算子进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。末代种群中的最优个体经过解码，可以作为问题近似最优解。
  

第一步

1.随机产生初始种群，个体数目一定，个体表示为染色体的基因编码

2.二进制编码缺点+浮点数编码特点

• 优点是编码简单、解码操作简单、交叉、变异等遗传操作便于实现
• 缺点是存在连续函数离散化的映射误差、当个体编码串较短，可能达不到精度要求。当个体编码较长，虽然能够提高精度，但是会使得算法的搜索空间急剧扩大。

第二步

计算个体的适应度（把自变量带入适应度函数计算），判断是否符合优化准则，若符合 ，输出最优解，结束计算，否则进入第三步

适应度函数的尺度变换

适应度函数的选取直接影响了遗传算法的收敛速度以及能否找到最优解。因为遗传算法在进化搜索众基本不利用外部信息，仅以适应度函数为依据，利用种群每个个体的适应度来进行搜索。

1.几种常见的适应度函数

• 第一种：直接以待求解的目标函数转化为适应度函数
  • 最大化问题： Fit(f(x)) = f(x)
  • 最小化问题： Fit(f(x)) = -f(x)

• 第二种：
  
• 第三种：
  

2.适应度函数设计原则

• 单值、连续、非负、最大化
• 合理、一致性
• 计算两小
• 通用性强

3.适应度函数的尺度变换

• 线性变换
• 线性拉伸变换
• 动态线性变换
• 幂函数变换
• 指数变换

第三步

** 依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰 **

1. 选择之前进行适应度的计算：

• 按比例的适应度（proportional fitness assignment）
• 基于排序的适应度计算（rank-based fitness assignment）

2.按照适应度进行父代个体的选择算子

• 轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。
• 排序选择（Stochastic Tournament）
  
• 最优保留选择：首先按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。
  

第四步

• 按照一定的交叉概率和交叉方法，生成新的个体
  

1. 二进制交叉

• 单点交叉
• 两点交叉与多点交叉
• 均匀交叉
• 算术交叉
• 洗牌交叉
• 缩小代理交叉

第五步

• 按照一定的变异概率和变异方法生成新的个体。
  

变异的方式

• 基本位变异
• 均匀变异
• 边界变异
• 非均匀变异
• 高斯近似变异

第六步

• 由交叉和变异产生新一代的种群，返回第二步。

2.3 优化准则（选其一）

• 种群中个体的最大适应度超过预订设定值
• 种群中个体的平均适应度超过预定设定值
• 世代数超过预定设定值

2.4 优缺点

• **优点是 ** 能很好的处理约束,能很好的跳出局部最优,最终得到全局最优解,全局搜索能力强；
• GA算法作为现代最优化的手段，实践证明，它应用于大规模、多峰多态函数、、含离散变量等情况下的全局优化问题是合适的，在求解速度和质量上远超过常规方法，因而是一高速近似算法。
• 对于组合最优化问题，与常规方法比较，可以认为遗传算法处于随机方法与启发式方法之间，它在引入随机搜索的同时，在解的构成法和演算过程中考虑了问题的原有构造。
• 缺点是 收敛较慢,局部搜索能力较弱,运行时间长,且容易受参数的影响.

2.5 处理遗传算法的约束问题:

• 显性约束
  一是把带约束的变成自由的：当约束是等式时，利用代换；约束是不等式，利用三角、指数函数化作等式；二是遗传出子代时，利用约束条件进行先天淘汰。第一个方法把运算量放在子代产生之前，第二个方法把运算量放在产生子代后。
• 隐形约束
  选择符合条件的染色体进行交叉；淘汰不符合条件的变异子代；

2.6 约束条件处理

• 搜索空间限定法：对遗传算法的搜索空间的大小加以限制，使得搜索空间中表示一个个体的点与解空间中的表示一个可行解的点有一一对应关系。
• 可行解变换法：在由个体基因型向个体表现型的变换中，增加使其满足约束条件的处理过程，即寻找个体基因型与个体表现型的多对一变换关系，扩大了搜索空间，使进化过程中所产生的个体总能通过这个变换而转化成杰空间中满足约束条件的一个可行解。
• 函数法：对在解空间中无对应可行解的个体计算其适应度时，处以一个惩罚函数，从而降低该个体的适应度，使该个体被遗传到下一代群体中的概率减小

2.7 遗传算法的应用

• 函数优化
• 组合优化
  • 研究的对象可以看作是在有限集合上定义的函数在各种条件下的极值问题。
  • 根据计算复杂性的理论，一个好的算法，其计算时间作为输入数据量的函数应该有一个多项式作为上界，这样的算法被称为多项式时间算法，简称有效算法。在组合优化中，至今还没有似乎也不可能发现普遍使适用的多项式时间算法。一个多项式时间算法问题被称为多项式时间可解问题（P问题）。组合优化中多数问题属于一类不知道是否为P问题的问题，其中包括所谓的NP（Nondeterminitic Polynomial Completeness）问题。在这类问题中，只要有一个被证明是P问题，，那么它们全部是P问题。
  • 对NP问题，既然没有准确的多项式时间算法，比较现实的妥协方法是采用多项式时间近似算法。
• 生产调度问题
• 自动控制
• 机器人智能控制
• 图像处理和模式识别
• 人工生命
• 遗传程序设计
• 机器学习

2.7 遗传算法应用于机器学习

与最优化问题的应用不同，最优化问题强调搜索收敛到一个近似最优解，而GBML（Genetic-based machine learning）不仅要获得一条规则的好的个体，而且更加强调最佳协调的规则组合。一般而言，GBML应具备以下机能

• 新规则生成，遵循优胜劣汰的规则
• 学习过程中不破坏已获得的优良规则
• 规则数目不预先给定
• 相似的或者相互包含的规则，进行适当的取舍，规则集合不过分冗余

2.8 matlab中GA工具箱的使用

matlab中GA工具箱的配置方法

2.9遗传算法的改进

2.9.1算法改进的途径

• 改变遗传算法的组成成分和使用技术，如选用优化控制参数、适合问题特性的编码技术
• 采用混合遗传算法
• 采用动态自适应技术，在进化过程中调整算法控制参数和编码粒度
• 采用非标准的遗传操作算子
• 采用并行遗传算法

2.9.2改进的算法

• 分层的遗传算法
  对于一个问题，随机生成N×n个样本，然后将它们分成N个子种群，每个子种群包含n个样本，对每个子种群独立地运行各自的遗传算法。这N个遗传算法最好在设置特性上有较大的差异，这样可以为将来的高层遗传算法产生更多种类的优良模式。
  
• 与梯度法结合的混合遗传算法
  梯度下降算子主要进行的是传统最速下降法中的线性搜索运算。
  混合算法众的遗传算子包括交叉算子、变异算子和选择算子的作用是宏观搜索，处理的是大范围的搜索问题，而最速下降算子的线性搜索过程的作用是极值局部搜索，微观搜索，处理的是小范围搜索和搜索加速问题。
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0kE39x0T-1593505723264)(/home/mgege007/Study/GA/Img/混合遗传算法.png)]
  

2.10 遗传算法资料

• 遗传算法-函数优化案例完整代码（Matlab）：
  链接: https://pan.baidu.com/s/1pyvdvu3oBBDKMf99axMlCg 密码: jrac

3.布谷鸟算法

• 优点是 全局寻优能力强，参数少且易于实现，易与其他算法相结合等综合优势，
• 缺点是 存在收敛速度慢、进化后期种群多样性差等不足。）CS算法收敛速度偏慢、求解精度较低：CS算法通过莱维飞行机制寻找鸟巢，莱维飞行是一种由小步长的短距离飞行和偶尔大步长的长距离飞行组成的随机游走过程，因此布谷鸟的寻窝路径容易在不同的搜索区域间跳跃，导致布谷鸟算法的局部精细搜索能力较差，在算法迭代后期容易在全局最优解附近的区域出现震荡现象，造成算法效率偏低群多样性差等不足
• CS算法介绍

4.蜂群算法