对智能算法的优化

通用的智能算法面临诸多问题，如收敛速度慢，精度差等。为了缩短计算时间提高精度，可以从以下两大方面对智能算法进行优化：

非凸优化到凸优化

Tip

沿用实分析中好坏集的思想，在非凸集中人为构造多若干好集，缩小搜索范围，甚至人为求解。

1. 分支定界

它做的事是：

• 把原来的大可行域不断切分成很多子区域
• 在每个子区域上做一个较容易的下界估计，常常借助凸松弛
• 如果某个子区域不可能优于当前最好解，就剪掉
• 只保留有希望的区域继续细分

2. 逐次凸近似

它做的事是：

• 在当前点附近，把原来的非凸目标或非凸约束，用一个局部凸模型近似
• 解这个凸子问题
• 得到新点后，再重新凸化
• 不断迭代

这像是在说：

原问题虽然非凸，但每一步我只解一个凸问题。

只不过它不是先分区，而是 沿迭代轨迹不断局部凸化。 具体操作可以参考局部近似求解

3. 凸松弛

很多非凸问题很难直接解，于是先构造一个更容易的凸问题：

原问题：

$$\underset{x\in \Omega }{\min }f(x)$$

其中 $f$ 或 $\Omega$ 非凸。

然后构造一个凸松弛问题：

$$\underset{x\in \tilde{\Omega }}{\min }\tilde{f}(x)$$

其中：

• $\tilde{\Omega }$ 是比原可行域更大的凸集
• $\tilde{f}$ 是更容易处理的凸目标

这样做的意义通常不是直接得到精确解，而是得到：

• 一个下界或上界
• 一个高质量初值
• 一个可供剪枝的判据
• 一个近似解

比如整数规划里把

$$x\in \{0,1\}$$

放松成

$$x\in [0,1]$$

这就是最经典的凸松弛。

所以这里的思路是：
先解一个凸版本，获得结构信息，再回头处理原非凸约束。 凸化松弛

4. DC 分解

很多非凸函数可以写成

$$f(x)=g(x)-h(x)$$

其中 $g,h$ 都是凸函数。
这叫 DC（difference of convex）分解。

然后在迭代中，把 $-h(x)$ 这一部分在当前点线性化。
因为凸函数的切线是全局下界，所以这样一线性化，整个问题会变成一个凸问题。

于是每一步都在解：

• 一个由原非凸问题导出的
• 当前点附近的
• 凸子问题

这就是 CCCP / DCA 这一类方法的核心。

把非凸问题“化整为零”，变成一连串可解的凸问题。
但要注意，这里不是变成“多个彼此独立的凸问题”，而是变成“按迭代串起来的一系列凸问题”。 DC分解是一类衍生算法的基础CCCP 与 DCA

多启动局部优化

目的不是让单次算法变强，而是弥补 局部方法只会掉进一个吸引盆 的缺陷。

这是一种对智能算法的改进，以梯度下降为例：我们可以通过多步长和多初值最大可能让算法跳出局部陷阱，得到多组解。再通过对比择优出最佳数值。

对于无法算梯度的情况，启动器和精修器也可以进一步回退：

• 连续变量、维度中低、函数计算还能承受：优先考虑 DE
• 连续变量、维度不高、想法简单稳妥：可以考虑 Nelder–Mead / pattern search 做局部器，外面套多启动
• 目标函数噪声较大、不可微、黑箱：优先考虑 DE、CMA-ES、Bayesian optimization（低维昂贵问题）
• 离散/组合问题：回到 SA、GA、ACO、禁忌搜索 这一类
• 只有很弱的连续结构，但不可微且约束复杂：先用 随机采样 / Latin hypercube + 局部无导数搜索

情形 A：连续变量，不可微，但函数值能算

优先级建议：

1. DE
2. 随机采样 / LHS
3. CMA-ES（如果维度中等、连续实值）
4. PSO（也能用，但我一般更偏向 DE / CMA-ES）

然后局部器接：

• Nelder–Mead
• pattern search

情形 B：连续变量，有噪声

优先考虑：

• CMA-ES
• DE
• 更鲁棒的采样策略

因为噪声下，很多局部无导数方法会被扰乱。

情形 C：离散或组合优化

这时梯度下降本来就不该在场。
启动器可直接用：

• 模拟退火 SA
• 遗传算法 GA
• 蚁群 ACO
• 禁忌搜索 TS

这里“启动器”和“主算法”经常是同一个东西。

情形 D：混合变量（连续 + 整数）

这时通常更偏向：

• GA
• DE 的离散改造版
• SA
• 分层搜索
• 分支定界 + 启发式初值

在完成启动器的回退后可以进一步对精修器进行无导数局部优化