锐客网

  1. 首页 > 睿知 > >

最优化理论的三大经典算法 优化算法有哪些

生活知识睿知

该账号为华为云开发者社区官方运营账号，提供全面深入的云计算前景分析、丰富的技术干货和程序样本，分享华为云前沿信息动态 。
本文分享自华为云社区《智能优化算法(一)——遗传算法》，原作者:我是大西瓜 。
智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强、适合并行处理的算法 。一般来说，这种算法有严格的理论基础，而不是单纯依靠专家经验，理论上可以在一定时间内找到最优解或接近最优解 。常用的智能优化算法包括遗传算法、模拟退火算法、禁忌搜索算法、粒子群优化算法和蚁群算法 。
本文主要给大家带来遗传算法和蚁群算法的详细解读 。
1.遗传算法遗传算法(Genetic algorithm，GA)，是一种模拟生物在自然环境中的遗传和进化(遗传参数的自适应调整)(随机变异不断搜索全局最优解)的自适应全局优化算法，是应用最广泛、最有效的以“适者生存”为基本思想的智能优化算法 。
1.1编码方法该算法对个体(解)采用二进制编码(01编码)、自然数编码、实数编码和树编码 。在计算个体的适应度时，需要解码来实现问题的解空与算法搜索空之间的相互转换 。
1.2健身功能每个人都有一个适应度函数，它定量地评估这个人的优点和缺点 。适应度函数是“优胜劣汰，适者生存”算法的基础 。需要根据目标函数设置适应度函数 。设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选择操作选择是从当前种群中选择适应度函数值大的个体 。这些优秀的个体可能会被用作父母来培育下一代 。个体适应度函数越大，被选为父母的概率越大(可能！)
选择算法有很多，其中最基本的是轮盘赌算法:
p _ I =\frac{f_i}{\sum_{i=1}^{n}f_i}pi =∑I = 1n fi fi
其中，P_iPi表示个体被选择的概率；F_iFi代表个体的适应度函数值；NN代表人口规模 。
根据选择概率P_iPi，将圆盘形赌轮分为NN个部分，第二个扇形的中心角为2\pi P_i2πPi 。随机生成一个0-1之间均匀分布的数rr，在第二个扇区的累计下降概率为Q _ I = \ sum _ {j = 1} I P _ Jqi = ∑ j = 1ipj，然后选择个体ii，重复NN次选择NN个个体 。
1.4交叉操作两个个体通过交叉和交换染色体部分基因重组产生新的个体，即产生新的解 。穿越前需要随机配对 。
一般来说，二进制编码的个体采用点交叉法，即从两个成对的字符串中随机选择一个或多个交叉点，交换一些子字符串生成新的字符串 。
两个个体是否进行交叉操作取决于交叉概率 。较大的交叉概率可以使遗传算法产生更多的新解，保持种群的多样性，防止算法过早成熟 。但是如果交叉概率太大，算法搜索不必要的解区域会太多，会消耗太多的计算时间 。一般来说，该值约为0.9 。
1.5突变操作在生物学的进化过程中，一些染色体可能会发生基因突变，从而产生新的染色体，这是产生新解决方案的另一个重要途径 。交叉操作相当于全局探索，变异操作相当于局部开发，这是智能优化算法必备的两种搜索能力 。
一个个体能否变异，取决于变异的概率 。如果太低，一些有用的基因就无法进入染色体，解决方案的质量也无法提高 。过多会使后代失去父母的优秀基因，从而导致算法失去从过去的搜索经验中学习的能力 。一般突变概率在0.005左右 。
值得注意的是，鲁道夫通过马尔可夫链理论证明了只有选择、交叉和变异三种操作的遗传算法不能收敛到全局最优解，而具有精英保留策略的遗传算法是全局收敛的 。
算法的整体流程如下图所示:
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蚁群优化算法蚁群优化算法是一种起源于自然界和生物学的模拟算法，其思想吸收了蚁群在觅食过程中的行为特征 。蚁群算法在通信网络中的TSP问题、二次分配问题、图着色问题、车辆调度问题和负载均衡问题中表现出良好的优化性能 。
自然界的蚂蚁没有视觉，依靠环境中分布的同类信息素来决定去哪里 。孤立的蚂蚁沿着同伴的信息素轨迹移动，同时释放自己的信息素，从而增加了这条路线上信息素的数量 。随着越来越多的蚂蚁经过这条路线，形成了一条更好的路线(这条路线不一定最短，但对于NP难问题来说已经足够了) 。
2.1.1算法模型以旅行商问题为例，它在图论中被称为最小哈密尔顿问题 。
G = (V，E)G=(V，E)是一个加权图，V=(1，2，3，...，N)V=(1，2，3，...，N)是顶点集，EE是边集，顶点之间的距离d_{ij}dij已知(

    推荐阅读


    上一篇：吹空调开点窗的好处

    下一篇：认知能力测试 能力分为一般能力和认知能力