在很久之前，看过粒子群算法等相关的以概率收敛的优化算法。当时那个破教程写的又臭又长，丝毫没看懂。今日考试重温了一下，原来是这么简单。八点半考完的，闲的没事于是手动实现了粒子群算法。之后考虑在本文中添加遗传算法、模拟退火这两个主流的碰运气的优化算法。

这类算法被优化课程的老师嘲讽了一番，缺乏严格的推导证明和参数的解释，大多是以科学的方法去碰运气，在解空间内进行搜索。

粒子群算法

对于一个目标函数，随机生成几个解视为粒子。将这几个粒子（数学意义为决策变量的取值）代入目标函数中，根据公式不断的迭代粒子的位置和速度参数，模仿鸟类觅食的行为来求出目标函数的最优解。

效果

模型

假设此时要优化的目标为：

\begin{cases}
\min \Bigl( (x - 2)^2 - 6x + \frac{12\sin x}{x} - 9x \cos x \Bigr) \\
\text{s.t.} -4 \leq x \leq 4
\end{cases}

粒子的更新只有以下两个公式：

\begin{cases}
x_i(t+1)=x_i(t)+v_i(t+1) \\
v_i(t+1)=wv_i(t)+c_1r_{1t}\bigl(\text{pbest}-x_i(t)\bigl)+c_2r_{2t}\bigl(\text{gbest}-x_i(t)\bigl)
\end{cases}

$x_i(t)$，表示$t$时刻第$i$个粒子的位置，$0$时刻随机初始化即可；
$v_i(t)$，表示$t$时刻第$i$个粒子的移动速度，$0$时刻随机初始化即可；
$w$，权重。取值大时，速度也大，具有较强的搜索能力；反之搜索能力较差；
$c_1,c_2$，常数，表示例子向局部最优和全局最优移动的能力；
$r_{1t}, r_{2t}$，是一个在$[0,1]$区间的常数，每次迭代都要重新生成；
$\text{pbest}$，$t$时刻的局部最优解，含义为某一点决策变量的取值，非目标函数值，该决策变量对应的目标函数值局部最小；
$\text{gbest}$，从开始迭代至今得到的全局最优解，含义为某一点决策变量的取值，非目标函数值，该决策变量对应的目标函数值全局最优；

其中，$\text{pbest},\text{gbest}$带进目标函数求解即可获得。编程实现可以考虑向量形式，容易实现。

程序

核心程序如下所示，全部程序请点击这里。注意：代码目前仅限于单决策变量，暂时没时间适配到多决策变量。

# 迭代次数
for i in range(self._iter_num):
    # 计算每个点的 fitness
    self._fitness = op_func(self._x)
    # 当前最优
    self._pbest = self._x[np.argmin(self._fitness)]
    # 全局最优
    if i == 0:
        self._gbest = self._pbest
    elif op_func(self._pbest) < op_func(self._gbest):
        self._gbest = self._pbest
    # 速度更新
    r1, r2 = np.random.rand(), np.random.rand()
    self._v = self._w * self._v + \
        r1 * self._c1 * (self._pbest - self._x) + \
        r2 * self._c2 * (self._gbest - self._x) 
    # 位置更新
    self._x += self._v
    # 越界后强制到边界点
    self._x = np.clip(self._x, self._left, self._right)