乐趣区

关于算法:详解智能优化算法遗传算法和蚁群算法

jiezi

摘要：智能优化算法又称古代启发式算法，是一种具备全局优化性能、通用性强且适宜于并行处理的算法。本文次要为大家带来遗传算法和蚁群算法的具体解读。

本文分享自华为云社区《智能优化算法（1）——遗传算法》，原文作者：我是一颗大西瓜。

智能优化算法又称古代启发式算法，是一种具备全局优化性能、通用性强且适宜于并行处理的算法。这种算法个别具备紧密的理论依据，而不是单纯凭借专家教训，实践上能够在肯定的工夫内找到最优解或近似最优解。罕用的智能优化算法有：遗传算法、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。

本文次要为大家带来遗传算法和蚁群算法的具体解读。

1. 遗传算法

遗传算法（Genetic algorithm, GA），模仿生物在自然环境中遗传和进化的 自适应 （对遗传参数的自适应调整） 全局优化（随机变异一直寻找全局最优解）算法，根本思维是“优胜劣汰”，是利用最宽泛和成果最显著的智能优化算法。

1.1 编码方法

算法模型通过对个体（individual，也即 solution）进行二进制编码（01 编码）、自然数编码、实数编码和树型编码。在对个体进行适应度计算时须要进行解码，实现问题的解空间与算法搜寻空间的互相转换。

1.2 适应度函数

每个个体都有一个适应度函数（Fitness），对这个个体的优劣进行定量评估，适应度函数是算法执行“适者生存、优胜劣汰”的根据。适应度函数须要依据指标函数进行设置，令 g(x)g(x)示意指标函数，令 G(x)G(x)示意适应度函数，从指标函数 g(x)g(x)映射到适应度函数 G(x)G(x)的过程称为标定。

对于最大值优化问题，可间接将 g(x)g(x)设定为适应度函数 G(x)G(x)，即 G(x)=g(x)G(x)=g(x)；对于最小值优化问题，G(x)=-\min g(x)G(x)=−ming(x)；在遗传算法规定中，适应度函数为正值，但上述二式无奈保障，因而须要加上最小值或者最大值以及分段函数。

1.3 抉择操作

抉择（Selection）是从以后群体中抉择适应度函数值大的个体，这些低劣个体有可能作为父代滋生下一代，个体适应度函数越大，被抉择作为父代的概率越大（有可能！）

抉择算法有很多，最根本的是轮盘赌算法：

​​其中，P_iPi​示意个体被抉择的概率；F_iFi​示意个体的适应度函数值；NN 示意种群规模。

依据抉择概率 P_iPi​将圆盘形赌轮分为 NN 份，第 ii 个扇形的中心角为 2\pi P_i2πPi​。随机产生 0 到 1 之间遵从均匀分布的数 rr，落在第 ii 个扇形的累计概率为 Q_i = \sum_{j=1}^i P_jQi​=∑j=1i​Pj​，则抉择个体 ii，反复 NN 次，就能够抉择 NN 个个体。

1.4 穿插操作

两个个体通过穿插（Crossover）调换染色体局部基因而重组产生新的个体，也就是产生新解。穿插前须要进行随机配对。

个别状况下，对二进制编码的个体采纳点穿插的办法，也就是在两个配对字符串随机抉择一个或者多个交叉点，调换局部子串从而产生新的字符串

两个个体是否进行穿插操作由穿插概率决定，较大的穿插概率能够使遗传算法产生更多新解，放弃群体多样性，并能避免算法过早成熟，然而穿插概率过大会使算法过多搜寻不必要的解区域，耗费过多的计算工夫，个别取值在 0.9 左右。

1.5 变异操作

生物进化中，某些染色体可能会产生基因突变（Mutation），从而产生新的染色体，这也是产生新解的另外一种重要形式。穿插操作相当于进行全局摸索，变异操作相当于进行部分开发，这也是智能优化算法必备的两种搜寻能力。

个体是否变异取决于变异概率，过低会使得局部有用基因无奈进入染色体，不能进步解的品质；过大会使子代丢失父代低劣基因，导致算法失去从过来搜寻教训的学习能力，个别状况下，变异概率取值为 0.005 左右。

值得注意的是，Rudolph 通过马尔科夫链相干实践证实仅采纳抉择、穿插和变异三个操作的遗传算法不能收敛到全局最优解，而采纳精英保留策略的遗传算法是全局收敛的。

算法的整体流程如下图所示：

1.6 算法剖析

一个好的智能算法，关键在于全局摸索和部分开发能力的均衡。全局摸索的目标是对解空间进行更全面的摸索，部分开发次要目标是对已知区域进行更精密的搜寻，心愿取得品质更好的新解。

遗传算法能够通过设置抉择压力实现全局摸索和部分开发的均衡。在算法运行初始阶段，设置较小的抉择压力能够使算法具备较好的全局摸索能力，进行广域搜寻；算法运行前期，设置较大的抉择压力能够使算法进行比拟精密的部分搜寻。

抉择压力的设置能够从适应度函数标定和抉择策略。

适应度函数标定，在算法晚期，该当放大个体适应度差距，缩小淘汰率；算法运行最初阶段，扩充个体适应度差距，保障算法能在高适应度个体对应解区域进行集中搜寻，放慢算法收敛速度。罕用办法有：

抉择策略，低抉择压力可抉择多种类型的个体，增强对未知解区域的搜寻，防止算法陷入部分极值，但算法优化速度会变得迟缓；高抉择压力可抉择低劣个体，放慢优化速度但群体多样性会降落，缩小搜寻到全局最优值的概率。除了轮盘赌算法外，抉择策略还有：

  • 分级抉择法
  • 锦标赛抉择法
  • Boltzmann 抉择法

2. 蚁群算法

2.1 蚁群优化算法

蚁群优化（Ant Colony Optimization, ACO）算法是源自大自然生物界的仿真类算法，其思维排汇了蚁群觅食过程中的行为个性。蚁群算法在 TSP 问题、二次调配问题、图着色问题、车辆调度问题、通信网络中的负载平衡问题等体现出良好的优化性能。

大自然中的蚂蚁没有视觉，依赖于同类散发在环境中的信息素决定本人何去何从，孤立的蚂蚁沿着伙伴的信息素轨迹挪动，同时开释本人的信息素，从而加强了该路线上的信息素数量，随着越来越多的蚂蚁通过该路线，一条较佳的路线就造成了（这条门路不肯定最短，但对于 NP-hard 问题而言足够了）。

2.2. 算法模型

以旅行商问题（Traveling Salesman Problem, TSP）为例，在图论中称为最小 Hamilton 问题。

蚁群优化算法根本模型：

  1. 蚂蚁群体总是寻找最小费用可行解
  2. 蚂蚁具备记忆性，存储以后门路的信息，结构可行解、评估解的品质、门路反向追踪
  3. 以后状态的蚂蚁能够挪动到可行畛域任意一点
  4. 每个蚂蚁赋予一个初始状态和若干个终止条件
  5. 蚂蚁从初始状态到可行畛域状态，以递推形式结构解，当有一个蚂蚁满足至多一个终止条件时结构过程完结
  6. 蚂蚁按某种概率决策规定挪动至畛域结点
  7. 挪动后信息素轨迹被更新，过程称为“单步在线信息素更新”
  8. 一旦结构出一个解，蚂蚁沿原路方向追踪，更新信息素轨迹，称为“在线提早信息素更新”

2.3 算法剖析

算法复杂度是 O(nc\cdot n^2\cdot m)O(nc⋅n2⋅m)，m 为蚂蚁个数，nc 为迭代次数或者搜寻次数，n 为顶点数。算法运行成果受到 \alpha, \betaα,β 等参数影响，其中 \betaβ 的影响在于体现信息素轨迹的持久性，数值过小意味着信息隐没过快；数值过大容易落入部分最长处，因而其数值通常取 0.7 左右。

在根本的蚁群优化算法上，能够与其余启发式算法相结合，最典型的就是嵌入部分搜索算法，在各个蚂蚁造成本人的路线后，用部分调整办法（2-opt, 3-opt）加以改进，此外，与遗传算法、模拟退火和禁忌搜寻等联合也有肯定的功效。

混合蚁群优化算法次要步骤：

  1. Begin
  2. 蚂蚁初始化；
  3. LOOP：
  4. \quad 蚂蚁门路结构；
  5. \quad 对某个蚂蚁施行部分搜索算法
  6. \quad 蚂蚁轨迹更新
  7. \quad 若迭代次数未到，转 LOOP；
  8. 输入以后最好解
  9. End

点击关注，第一工夫理解华为云陈腐技术~

退出移动版