算法打包
已经把算法打包了，scikit-opt
def demo_func(x):
x1, x2, x3 = x
return x1 ** 2 + (x2 - 0.05) ** 2 + x3 ** 2
from sko.SA import SA
sa = SA(func=demo_func, x0=[1, 1, 1])
x_star, y_star = sa.fit()
print(x_star, y_star)
算法介绍
蚁群算法（Ant Colony Algorithm, ACA）由Marco Dorigo于1992年在他的博士论文中首次提出，该算法模拟了自然界中蚂蚁的觅食行为。
自然界中蚂蚁的觅食行为有以下特点：
- 蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。
- 通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样，会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短。
- 路径上的信息素浓度会随着时间的推进而逐渐衰减。
- 将蚁群算法应用于解决优化问题，其基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对 应的便是待优化问题的最优解。
蚁群算法的特点：
- 正反馈机制，最后会收敛
- 每个个体释放信息素，并且感知信息素，间接进行通讯
- 分布式计算，可以使得多个个体同时并行计算
- 启发式概率搜索，不容易陷入局部最优
转移概率
在每个节点上，每个蚂蚁按照一定的概率随机转移到下一个节点
\(P^k_{ij}(t)=\left \{ \begin{array}{ccc}
\dfrac{[\tau_{ij}(t)]^\alpha \times [\eta_{ij}(t)]^\beta}{\sum\limits_{s\in allow_k} [\tau_{ij}(t)]^\alpha \times [\eta_{ij}(t)]^\beta}&s\in allow_k\\
0&s\not\in allow_k
\end{array}\right.\)
$P^k_{ij}(t)$是一个概率，表示的是蚂蚁k，在第t时间，从第i个节点向第j个节点移动的概率，
下面对变量进行解释，
m:蚂蚁数量
n：城市总数量
$d_{ij}(i,j=1,2,…n)$:距离。指的是城市i到城市j的距离
$\tau_{ij}(t)$:信息素浓度，t时刻,城市i到城市j的路径上的信息浓度
$\eta_{ij}(t)=1/d_{ij}$:启发函数，这个值用来控制蚂蚁从城市i到城市j的期望程度
$allow_k$:一个集合,用来存放蚂蚁k还没访问到的城市编号，这个集合随着时间t的增加而减少，最后是空值
$\alpha,\beta$：重要程度。分别表示信息素浓度，启发函数的重要程度
信息素
信息素是蚁群算法的关键，蚁群算法每次迭代的目的是对信息素进行操作，算法结束后，留下一条信息素最大的路径，这个路径就是最优解
$\tau_{ij}(t+1)=(1-\rho)\tau_{ij}(t)+\Delta \tau_{ij}$
也就是说，下一时刻的信息素，等于这一时刻的未挥发的信息素，加上这一时刻所有蚂蚁抹上去的信息素
$\rho \in (0,1)$是信息素的挥发程度。
其中，
$\Delta \tau_{ij}=\sum\limits_{k=1}^n \Delta \tau_{ij}^k$
(意思是所有m个蚂蚁在ij路径上释放的信息素的总和)
单个蚂蚁产生的信息素
单个蚂蚁产生的信息素，有几个不同模型
1. ant cycle system
\(\Delta \tau_{ij}^k=\left \{ \begin{array}{ccc} Q/L_k&if&ij&visited\\ 0 &if¬ \end{array}\right.\)
Q是预先设定的常数，表示蚂蚁走完整个闭环所释放的信息素
$L_k$是第k个蚂蚁总路径的长度
注：这个式子可以这么推导：第k个蚂蚁在固定的时间内，走完整个路径后返回再走，直到时间用尽
2. ant quantity system
\(\Delta \tau_{ij}^k=\left \{ \begin{array}{ccc}
Q/d_{ij}&if&ij&visited\\
0 &if¬
\end{array}\right.\)
注：这个式子可以这么推导：第k个蚂蚁并不走完全程，而是在固定时间内，在ij之间来来回回
3. ant density system
\[\Delta \tau_{ij}^k=\left \{ \begin{array}{ccc} Q&if&ij&visited\\ 0 &if¬ \end{array}\right.\]算法步骤
- 初始化参数：蚂蚁数量m，信息素重要程度$\alpha$,启发函数重要程度$\beta$,信息素挥发速度$\rho$,信息素总量$Q$,最大迭代次数$max_iter$
- 构建解空间：各个蚂蚁随机放到不同的位置，按照转移概率进行移动，直到访问完毕所有城市
- 更新信息素：按照信息素迭代规则更新信息素
- 判断是否终止，如果不终止则转到2
