智能优化算法：阴阳对优化算法

@[toc]
摘要：阴阳对优化(YYPO)算法是 Varun Punnathanam等人于 2016 年基于阴阳平衡原理提出的一种新型元启发式优化算法。目前已在函数、多目标优化等领域得到应用。

1.算法原理

该算法基于 2 个点集(P1 和P2)，其中 P1 设计为专注于开发变量空间，P2 设计为专注于探索变量空间，通过开发与探索 2 个矛盾行为之间的相互协调、补充达到平衡，并利用分裂、存储 2 个阶段进行迭代更新来求解最优化问题。

1.1 设置待优化

设置待优化问题维度 $D$ ，随机初始化 2 个点集 $P1 = \{P1^1,P1^2,...,P1^D\}$ 和 $P2 = \{P2^1,P2^2,...,P2^D\}$
。对点集 P1 和 P2 进行归一化处理，即 $0 ≤ (P1^j ，P2^j ) ≤1$ ，其中， $j = 1，2，3，…，D$ 。

1.2 分裂阶段

a) 单向分裂:在 YYPO 算法中，点 $P$ 的二维相同副本被存储为 $S$ ，其可以被认为是尺寸为 $2D × D$ 的矩阵。 $S$ 中每个点的一个变量用下面的公式修改:
$\begin{cases} S_j^j=S^j+r\delta \\ \quad \quad \quad \quad \quad \quad \quad j=1,2,3,...,D\\ S_{D+j}^j = S^j -r\delta \tag{1} \end{cases}$
式中下标—点号;上标—正被修改的决策变量号; $r$ —在 0 和 1 之间的随机数，对于 $S$ 中任意点的每个变量产生新的 $r$ ，共需2D ×D 个 0 和 1 之间的随机数; $\delta$ —搜索半径。

b) D 向分裂:在 YYPO 算法中，点 $P$ 的2D相同副本被存储为 $S$ ，其可以被认为是 $2D × D$ 大小的矩阵，生成包含长度为 $D$ 的二维随机二进制矩阵 $B$ ，使得每个二进制串是唯一的。随后，使用以下等式来修改任意点的每个变量:
$\begin{cases} S_k^j=S^j+r(\delta/\sqrt{2})\, if\,B_k^j=1 \\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad j=1,2,3,...,D\\ S_{k}^j = S^j -r(\delta/\sqrt{2})\, else \tag{2} \end{cases}$
式中下标—点号(或行);上标—决策变量号(或列); $r 、δ$ 意义同上;二进制矩阵 $B$ 通过随机选择 $0 ～ 2 D －1$ 之间的唯一整数并转换成长度为 $D$ 的二进制串来组成。

1.3 存储阶段

存储阶段是在满足所需数量的存储更新之后启动，且该存储阶段包含 $2 I$ 个点( $I$ 为存储阶段的更新次数大小)，对应于在分裂阶段前每个更新中添加的 2 个点 $P1 、P2$ 。若存储中的最佳点比点 $P1 、P2$ 更合适，则与点 $P1 、P2$ 交换。存储阶段因此保持精英主义并且确保算法的单调收敛(即在任何迭代中确定的最佳点不会丢失)。在存储阶段结束时，存储矩阵设置为空，并且在其指定范围 $I_{min}$ 和 $I_{max}$ ( $I_{min}$ 和 $I_{max}$ 分别为存储更新的最小数和最大数)内随机生成存储更新 $I$ 的新值。搜索半径 $δ_1$ 和 $δ_2$ 的更新公式如下:
$\begin{cases} \delta_1 = \delta_1- (\delta_1/a)\\ \delta_2 = \delta_2+ (\delta_2/a) \tag{3} \end{cases}$
式中 $δ 1、δ2$ —点集 $P1、P2$ 的搜索半径; $a$ —扩张/收缩因子。YYPO 算法的特点在于随机生成的点集数量取决于问题维度，针对高维优化问题将生成较多的点，这种自适应能力能有效解决不同维度问题并获得待优化问题的最优解。