锐客网

  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算法分析好的智能算法的关键在于全局探索和局部开发能力之间的平衡 。全球探索的目的是更全面地探索解决方案空，而局部开发的主要目的是更精细地搜索已知区域，希望获得质量更好的新解决方案 。
遗传算法可以通过设置选择压力来平衡全局探索和局部发展 。在算法运行初期，设置较小的选择压力可以使算法具有更好的全局探索能力 ， 进行广域搜索 。在算法运行的后期 ， 设置较大的选择压力可以使算法执行更细致的局部搜索 。

推荐阅读


上一篇：产妇吃什么可以补气血 吃什么可以给产妇补气血

下一篇：八十天环游地球的经典语录 环游地球八十天名句