现代智能优化算法

发布时间：2024-04-22 13:58浏览次数：来源于：网络

现代智能优化算法本质上是一类算法，是为了解决NP-hard问题而诞生的启发式算法，常见的启发式算法主要包括模拟退火、遗传算法等。

在这之前，必须了解一个概念，叫做多项式时间：在计算复杂度理论中，指的是一个问题的计算时间不大于问题大小的多项式倍数。通俗来说就是一定规模的问题，总有一个时间范围内可以将它解决，这个范围就是多项式时间。
所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。也就是说，我们可以很容易验证答案是否可行，但是无法快速求解，因为NP-hard问题所包含的解集实在是太多，常见的NP-hard问题有TSP旅行商问题。
如：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

根据目前常用的情况，本文将选择模拟退火和遗传算法进行讲解。为了更方便入门，本文选用实例十分简单。

模拟退火的基本思想来自于材料统计学，里面涉及到一些物理量，但我们并不需要理解其中物理量的含义。只需要知道如何求解即可。
在高温条件下,粒子的能量较高,可以自由运动和重新排列。在低温条件下,粒子能量较低。如果从高温开始,非常缓慢地降温(这个过程被称为退火),粒子就可以在每个温度下达到热平衡。当系统完全被冷却时,最终形成处于低能状态的晶体。

首先，我们求解一个函数最大值时，有什么手段？
1.求导
2.取间隔为0.01，使用蒙特卡洛模拟1遍历区间
3.启发式算法
这里我们举例如下：
求解函数z = sin((x²+y²)^0.5)在x、y在区间[-5,5]的最小值。这个函数的最大值很容易用肉眼看出来大概范围，这里我们主要是作为示例说明。
绘图有：

具体实现代码如下：

运行结果如下：
已经迭代温度890次，此时最佳值为-0.9999983220396803
已经迭代温度900次，此时最佳值为-0.9999839439032638
已经迭代温度910次，此时最佳值为-0.9999999909611703
总共迭代了917次,最佳值为-0.9999999999928478,对应的自变量x为3.280114346731557,y为3.383414757360287

核心实现在于初始化温度为100，在不断迭代中使得温度变为0，在这之间不断迭代最优解。
代码步骤：
1.首先利用随机值生成初始解，大小为n自由设置
2.当当前温度大于要求温度0时，循环遍历每个解（x，y）
3.对于每个解，先计算得分（一般为每个解打分，这个打分是自己设置的，如旅游商问题所花总费用，我们这里即为函数值）
4.随后将每个解生成新的解

生成条件为当前温度*随机值+原来值，确保在可行域下。这里可以明确，当温度越来越低后，新的值和原来的值的差距会逐渐缩小，这也是启发式算法通用的核心思想：在初期广度搜索，后期在找到可能的最优值后再最优值左右微微的波动。
5.随后再次计算新的得分（此题为函数值），并利用函数判断是否保留新的值，如果保留则将原来值替换，代码如下：

这里的核心思想在于，得分越高的值，保留下来的几率比原来大，这和遗传算法中的遗传实现也很类似，核心在于将更高的值更好的可能下继承下来。
6.在将解集（n大小）的所有值都更新完毕后，开始温度的更新，这里温度的更新格式为self.t=self.t*self.alpha#温度按照一定比率下降，即按照一定比例下降，alpha为自由设定值。

7.反复迭代1-6步，一直到温度最终低于阈值。

可见，整个遗传算法的思路并不难，但是这个问题很简单，当遇到一个复杂问题的时候，我们在构建产生新的可行解时会更加困难，可能需要考虑各种各样的限制。同时，得分也会更加难以确定。但但我们理解到算法思想后，便能够更加只有的去设计具体细节，以便更好的收敛。
旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。对于旅行商问题，我们应该怎么改进我们的算法来求解？
这里我提一下思路，由于篇幅限制暂且不进行求解。
在生成解集时，利用随机数生成满足题意的多条路线，可以使用深度优先+随机生成。在更新解集时，随机更改一条路线下的的某段城市点，但是确保修改后的路线是可行的。在衡量得分的时候，旅行商问题即为直接求和取负即可。

遗传算法是用于解决最优化问题的一种搜索算法。从名字来看，遗传算法借用了生物学里达尔文的进化理论：”适者生存，不适者淘汰“，将该理论以算法的形式表现出来就是遗传算法的过程。
遗传算法的整体算法思想和模拟退火类似，但是他采用了一个更奇妙的表现方式表达了整个迭代更新。

求函数y = x + 16 * sin(5x) + 10 * cos(4x)的最大值，设置x区间范围为：[-10,10]。
具体实现代码如下：

运行结果如下：

已经迭代进化220次，此时种群平均值为32.05702212366586，最佳值为33.31557993182841
已经迭代进化240次，此时种群平均值为31.837646996627015，最佳值为33.27762194440547
已经迭代进化260次，此时种群平均值为31.45958626656901，最佳值为33.19787983857166
已经迭代进化280次，此时种群平均值为32.23062520430858，最佳值为33.19787983857166
已经迭代进化300次，此时种群平均值为32.087583602871064，最佳值为33.11304968140086

和模拟退火算法一样，本质思想就是随机生成后产生新的解，并使得更好的解更多的留下来，最终迭代多次后求得最优解。
在遗传算法中我们可以将整个流程分为如下的
1.首先生成初始可行解，也就是初始种群（n个），比如在此题中即为区间内生成随机数，在旅行商问题中即为生成初始可行路径。
2.接下来将初始可行解进行编码，将其变为基因格式，常见的基因格式有二进制编码，onehot编码等等。
3.接下来的进行自然选择过程

具体来说，就是对种群（n个）进行解码并获取到种群得分，将得分对应权重的转为概率矩阵，pro = scores[i]/sum_score，也就是得分越高的越容易被选择。
4.接下来就是交配过程，我们可以假设每次交配产生两个孩子，保持种群总数不变，因此需要进行种群大小/2次交配，每次交配2只，每次配对的交配概率自由设置，可设置为逐渐减少的，也可以设置为固定概率的。随后依照得分概率在种群中随机选取两个个体，并将编码基因基因进行随机组合（也就是生物学上的基因的交叉结合），常用的手段有简单拼接等（即直接将父母之间的基因进行交叉组合，如0b11011和0b10121，直接将两者之间进行随机选取中间段拼接），还可以采用其他的如固定拼接，段落交叉等等，交叉的方式将决定算法的收敛情况。
5.得到新的孩子的基因后，依然需要判断，是否可行以及是否能够是否优于原来，并按照自己设置的方式选择是否保留，常用的手段有择优选取、有偏差的择优选取（在容忍程度下，尽管后代更差了，依然保留，因为可能距离最优解更近）。
6.在做完自然选择后，需要依照概率进行基因图片

也就是说，基因中的编码，有概率随机变化，如0突变为1，点（x，y）变为（x+1,y+1）等，其中的概率自由设置。
7.随后计算出整个种群的得分，保证种群稳步前进。并保存下最优的种群，并不断重复2-6过程，最终迭代获取最优解。

相对模拟退火来说，遗传算法更加复杂一些，整体算法趣味也更大，其中有很多是我们可以自由设置的，如交叉结合方式，编码方式，突变概率和突变方式。
两个算法的思想非常类似，如果说非要做一点区分，那就是模拟退火更在意个人的优秀，而遗传算法则是站在整个种群的角度下，不断迭代使得整个种群向前发展。

启发式算法本质上思想都很类似，但是实现思想不太一致。
模拟退火的思想是，在不断搜索最优解的过程中不断降低波动范围（辐射范围），最终收敛于最优解附近。
遗传算法的思想在于不断搜索的过程中保证更高质量个体之间更有可能产生后代，最终整个种群将会趋于同质化，并且收敛于最优解。
而粒子群算法的思想在于，种群中的精英作为目标，整个种群朝着精英前进，最终精英之间交互产生，相互追逐，最终整个种群将会收敛于最优值附近。

1.什么是NP-Hard
2.Python三维绘图–Matplotlib

下一篇：华为户用光伏产品
上一篇：Seo优化是什么（seo整站优化怎么做）