此账号为华为云开发者社区官方运营账号，提供全面深入的云计算前景分析、丰富的技术干货、程序样例，分享华为云前沿资讯动态
本文分享自华为云社区《智能优化算法（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_i =\frac{F_i}{\sum_{i=1}^{N}F_i}Pi=∑i=1NFiFi
其中，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=1iPj，则选择个体ii，重复NN次，就可以选择NN个个体。
1.4 交叉*作两个个体通过交叉（Crossover）互换染色体部分基因而重组产生新的个体，也就是产生新解。交叉前需要进行随机配对。
一般情况下，对二进制编码的个体采用点交叉的方法，也就是在两个配对字符串随机选择一个或者多个交叉点，互换部分子串从而产生新的字符串
两个个体是否进行交叉*作由交叉概率决定，较大的交叉概率可以使遗传算法产生更多新解，保持群体多样 ，并能防止算法过早成熟，但是交叉概率过大会使算法过多搜索不必要的解区域，消耗过多的计算时间，一般取值在0.9左右。
1.5 变异*作生物进化中，某些染色体可能会发生基因突变（Mutation），从而产生新的染色体，这也是产生新解的另外一种重要方式。交叉*作相当于进行全局探索，变异*作相当于进行局部开发，这也是智能优化算法必备的两种搜索能力。
个体能否变异取决于变异概率，过低会使得部分有用基因无法进入染色体，不能提高解的质量；过大会使子代丧失父代优良基因，导致算法失去从过去搜索经验的学习能力，一般情况下，变异概率取值为0.005左右。
值得注意的是，Rudolph通过马尔科夫链相关理论证明仅采用选择、交叉和变异三个*作的遗传算法不能收敛到全局优解，而采用精英保留策略的遗传算法是全局收敛的。
算法的整体流程如下图所示：
1.6 算法分析一个好的智能算法，关键在于全局探索和局部开发能力的平衡。全局探索的目的是对解空间进行更全面的探索，局部开发主要目的是对已知区域进行更精细的搜索，希望获得质量更好的新解。
遗传算法可以通过设置选择压力实现全局探索和局部开发的平衡。在算法运行初始阶段，设置较小的选择压力可以使算法具有较好的全局探索能力，进行广域搜索；算法运行后期，设置较大的选择压力可以使算法进行比较精细的局部搜索。
选择压力的设置可以从适应度函数标定和选择策略。
适应度函数标定，在算法早期，应当缩小个体适应度差距，减少淘汰率；算法运行后阶段，扩大个体适应度差距，保证算法能在高适应度个体对应解区域进行集中搜索，加快算法收敛速度。常用方法有：
线 尺度变换 H= aF+bH=aF+b\sigmaσ截断法 H= F+(\hat F - c\sigma)H=F+(F^−cσ)幂律尺度变换 H= F^\alphaH=Fα选择策略，低选择压力可选择多种类型的个体，加强对未知解区域的搜索，避免算法陷入局部极值，但算法优化速度会变得缓慢；高选择压力可选择优良个体，加快优化速度但群体多样 会下降，减少搜索到全局优值的概率。除了轮盘赌算法外，选择策略还有：
分级选择法锦标赛选择法Boltzmann选择法2. 蚁群算法2.1 蚁群优化算法蚁群优化（Ant ColonyOptimization, ACO）算法是源自大自然生物界的仿真类算法，其思想吸收了蚁群觅食过程中的行为特 。蚁群算法在TSP问题、二次分配问题、图着色问题、车辆调度问题、通信网络中的负载均衡问题等表现出良好的优化 能。
大自然中的蚂蚁没有视觉，依赖于同类散发在环境中的信息素决定自己何去何从，孤立的蚂蚁沿着同伴的信息素轨迹移动，同时释放自己的信息素，从而增强了该路线上的信息素数量，随着越来越多的蚂蚁通过该路线，一条较佳的路线就形成了（这条路径不一定短，但对于NP-hard问题而言足够了）。
2.1.1算法模型以旅行商问题（TravelingSale**an Problem, TSP）为例，在图论中称为小Hamilton问题。
记G = (V,E)G=(V,E)为赋权图，V=(1,2,3,...,N)V=(1,2,3,...,N)为顶点集，EE为边集，各顶点间的距离d_{ij}dij已知(d_{ij}0,d_{ii}=\infty,i,j\in V)(dij0,dii=∞,i,j∈V)，设x_{ij} = 1, 若(i,j)在优回路上；否则为0xij=1,若(i,j)在优回路上；否则为0
则经典的TSP问题可以表示如下：
\min Z =\sum_{i=1}^{n}\sum_{j=1}^{n}d_{ij}x_{ij}minZ=i=1∑nj=1∑ndijxij
服从如下几个约束：
约束1：\sum_{j=1}^{n}x_{ij}=1, i\in V∑j=1nxij=1,i∈V约束2：\sum_{i=1}^{n}x_{ij}=1, j\in V∑i=1nxij=1,j∈V约束3：\sum_{i\in S}\sum_{j\inS}x_{ij} \le |S|-1, \forall S \subset V∑i∈S∑j∈Sxij≤∣S∣−1,∀S⊂V约束4：x_{ij}\in \{0, 1\}xij∈{0,1}其中|S|∣S∣为**中所含图的顶点数；约束1和2对于每个点来说只有一条边进一条边出，也就是任意两个点间只有一条优路线；约束3保证了没有任何子回路的产生。
当d_{ij} = d_{ji}dij=dji时，问题被称为对称型TSP；当对于所有1\le i, j,k \le n1≤i,j,k≤n时，有不等式d_{ij}+d_{jk}\ge d_{ik}dij+djk≥dik成立，问题被称为是满足三角形不等式的，记为\DeltaΔTSP。三角形不等式在很多情况下是满足的，即使不满足也可以转换为闭包形式求等价TSP优解。
蚁群优化算法基本模型：
1. 蚂蚁群体总是寻找小费用可行解
2. 蚂蚁具有记忆 ，存储当前路径的信息，构造可行解、评价解的质量、路径反向追踪
3. 当前状态的蚂蚁可以移动到可行领域任意一点
4. 每个蚂蚁赋予一个初始状态和若干个终止条件
5. 蚂蚁从初始状态到可行领域状态，以递推方式构造解，当有一个蚂蚁满足至少一个终止条件时构造过程结束
6. 蚂蚁按某种概率决策规则移动至领域结点
7. 移动后信息素轨迹被更新，过程称为“单步**信息素更新”
8. 一旦构造出一个解，蚂蚁沿原路方向追踪，更新信息素轨迹，称为“**延迟信息素更新”
2.1.2算法分析算法复杂度是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
点击关注，第一时间了解华为云新鲜技术~
