获取更多资讯，赶快关注上面的公众号吧！
文章目录
- 第十三章 猫群算法
- 13.1 介绍
- 13.2 搜寻模式（Seeking Mode）
- 13.3 跟踪模式（Tracing Mode）
- 13.4 猫群优化算法
- 参考文献
第十三章 猫群算法
13.1 介绍
猫群优化算法（Cat Swarm Optimization）是基于猫科动物的捕食策略提出的一种新型的群优化算法，由Shu-An Chu等人[1]在2006年首次提出。一般来说，猫大部分时间都处于休息状态，很少去搜寻和捕捉猎物。但是猫的警觉性非常高，即使在休息的时候也处于一种高度的警惕状态，时刻保持对周围环境的警戒搜寻；它们对于活动的目标具有强烈的好奇心，一旦发现目标便进行跟踪，并且能够迅速地捕获到猎物。猫群算法正是关注了猫的搜寻和跟踪两种行为。
首先，将猫随机分布在整个搜索空间中，然后将猫细分为两种模式。第一种模式称为“搜寻模式”，该模式下的猫处于休息状态，密切注视着周围的环境；第二种模式称为“追踪模式”，是猫跟踪、追逐动态猎物时的状态。通过结合这两种模式往往能实现全局优化。
猫群算法中，一部分猫执行搜寻模式，剩下的则执行跟踪模式，两种模式通过结合率MR(Mixture Ratio)进行交互，MR表示执行跟踪模式下的猫的数量在整个猫群中所占的比例，在程序中MR应为一个较小的值，因为猫只会花一小部分时间跟踪它们的食物。
13.2 搜寻模式（Seeking Mode）
搜寻模式用来模拟猫的当前状态，分别为休息、四处查看、搜寻下一个移动位置。在搜寻模式中，定义了4个基本要素：维度变化数(counts of dimension to change，CDC)、维度变化域(seeking range of selected dimension，SRD)、搜寻记忆池(seeking memory pool，SMP)和自身位置判断(self-position consideration，SPC)。CDC指用于变异的维度个数，其值是一个从0到总维数之间的随机值；SRD声明了所选维度的变化量，对于需要进行变异的维度，新旧值之间的变化不能超出范围定义，而这个范围正是由SRD定义的；SMP定义了每一只猫的搜寻记忆大小，表示猫所搜寻到的位置点，猫将根据适应度大小从记忆池中选择一个最好的位置点；SPC是一个布尔值，表示猫是否将已经过的位置作为将要移动到的候选位置之一，其值不影响SMP的取值。
搜寻模式过程如下：
-
将猫catk的当前位置复制j份，即j=SMP，如果SPC为true，令j=（SMP-1），则保留当前位置为其中的一个候选解；
-
对于每一个副本，根据CDC，随机地对当前值加上或者减去SRD%，并替换旧值；
X c n = ( 1 ± S R D × R ) × X c (1) {X_{cn}} = (1 \pm SRD \times R) \times {X_c}\tag 1 Xcn=(1±SRD×R)×Xc(1)
其中Xc为当前位置，Xcn为新的位置，R为[0,1]内的任意值。 -
计算所有候选解的适应度值（FS）；
-
如果所有的FS不全相等，则根据式（2）计算每个候选解的选择概率，否则设置每个候选解的选择概率为1；（该过程实际上进行了缩放归一化）
P i = ∣ F S i − F S b ∣ F S max − F S min , w h e r e 0 < i < j (2) {P_i} = \frac{{\left| {F{S_i} - F{S_b}} \right|}}{{F{S_{\max }} - F{S_{\min }}}},{\rm{ }}where{\rm{ }}0 < i < j\tag 2 Pi=FSmax−FSmin∣FSi−FSb∣,where0<i<j(2)
其中Pi为当前解的选择概率，FSi为猫的适应度值，FSmax和FSmin分别为适应度的最大和最小值，对于最大化问题，FSb=FSmin，而对于最小化问题，FSb=FSmax。 -
从记忆池的候选解中按照选择概率随机选择位置进行移动，并替换catk的位置。
13.3 跟踪模式（Tracing Mode）
跟踪模式对猫在跟踪目标时的情况进行建模，一旦猫进入跟踪模式，其会根据每一维上的速度进行移动。跟踪模式过程如下：
- 对每只catk，按照式（3）更新其当前迭代每一维的速度；
v k , d ( t ) = v k , d ( t − 1 ) + r 1 ⋅ c 1 ⋅ [ x b e s t , d ( t − 1 ) − x k , d ( t − 1 ) ] d = 1 , 2 , … , M (3) \begin{array}{l}{v_{k, d}(t)=v_{k, d}(t-1)+r_{1} \cdot c_{1} \cdot\left[x_{\mathrm{best}, d}(t-1)-x_{k, d}(t-1)\right]} \\ {d=1,2, \ldots, M}\end{array}\tag 3 vk,d(t)=vk,d(t−1)+r1⋅c1⋅[xbest,d(t−1)−xk,d(t−1)]d=1,2,…,M(3)
其中xbest,d(t-1)是上一次迭代具有最优适应度值的猫的位置，xk,d(t-1)是上一次迭代catk的位置。c1为常数，r1为[0,1]之间的随机数。 - 判断速度是否在最大速度范围内，如果超出了边界，则取边界值；
- 根据式（4）更新catk的位置。
x k , d ( t ) = x k , d ( t − 1 ) + v k , d ( t ) (4) {x_{k,d}}(t) = {x_{k,d}}(t - 1) + {v_{k,d}}(t)\tag 4 xk,d(t)=xk,d(t−1)+vk,d(t)(4)
13.4 猫群优化算法
猫群算法CSO的伪代码如下：
Step1：创建N只猫；
Step2：将这些猫随机散布在M维解空间中，并为每只猫选择速度值，要求这些值位于最大速度范围内，然后根据MR随意地选择一定量的猫，将它们设置为跟踪模式，其他设置为搜寻模式；
Step3：将猫的位置代入适应度函数，从而评估每只猫的适应度值，记录最优猫。注意只需要记住最优猫的位置（xbest）即可，因为其表达了当前最优解；
Step4：根据模式标志移动猫，如果catk处于搜寻模式，则进行搜寻过程，否则进行跟踪过程；
Step5：根据MR，重新选取一定数量的猫设置其为跟踪模式，剩余的猫为搜寻模式；
Step6：判断终止条件是否满足，满足则算法终止，否则重复Step3~Step5。
参考文献
- Chu, S.-C., P.-w. Tsai, and J.-S. Pan. Cat Swarm Optimization. in PRICAI 2006: Trends in Artificial Intelligence. 2006. Berlin, Heidelberg: Springer Berlin Heidelberg.
