吐槽：其实我特别反感老师自己不上课，让学生挨个领任务的这种行为，虽然好（jiu）像（shi）越来越多的老师喜（bian）欢（de）上（yue）这（lai）一（yue）点（lan）了。课下已经是百分之百靠自学，课上想听一下你的观点这么难？好吧，这个题目，其实是我领的任务……本身我也不想准备这个东西，但是恰逢考试周，老刷那些数学题也没啥意思，就花点时间做了个PPT当放松了。
下面进入正题。
克隆选择算法（Clonal Selection Algorithm，CSA）是依据克隆选择原理提出的一种进化算法。由于借鉴了生物体免疫系统的免疫过程，算法的很多定义和过程都和生物学中的免疫系统类似，比如抗原，抗体，浆细胞之间的关系和作用等等。从免疫过程中我们知道，只有被抗原刺激的抗体才会增殖（克隆）和分化，形成记忆细胞，从而在下次抗原到来时，加速免疫反应。也就是说，和抗原亲和度高的抗原会以更高的概率保留下来，并增殖分化，这就是CSA的核心思想。
应用到具体的问题中，CSA算法中，可以将抗原视为我们要解决的问题，抗体表示问题的解，而抗原和抗体之间的亲和度可以用解的优良程度来表示。后来的生物学家还研究到，抗体会有一种称之为超突变的机制来增强抗体的免疫性，产生所熟知的交叉免疫现象，即增强的抗体的泛化能力，使得其不仅能够免疫之前刺激的抗原，而且可以免疫和其相类似的抗原。
因此，结合亲和性选择和超突变，CSA算法的一般流程如下：
- 生成候选抗体（解）
- 根据亲和度，选择优秀的抗体克隆
- 克隆的结果进行超突变
- 重新选择突变个体，替换亲和度低的个体成为候选抗体
在多目标优化（MO）中，算法没有牵扯到抗原这个概念，因为优化函数唯一且确定，因此可以直接定义亲和性函数$\mathcal{F}$，它的输入为抗体编码，输出为亲和度，用$\mathbf{Ab}$表示抗体，这个过程表示如下：
算法框架中，抗体$\mathbf{Ab}$需要以编码的形式进行迭代，令抗体个数为$N$，编码长度为$L$，那么$\mathbf{Ab} \in S^{N \times L}$。
根据亲和度选择好克隆对象之后，就要进行克隆和超突变操作，一般是选择最好的若干个抗原（称之为$\mathbf{Ab}_{\{n\}}$）参与克隆和超突变，这个过程可以表示如下：
$\mathbf{C}，\mathbf{C^*}$表示克隆后和超突变之后的抗体集合。关于克隆的个数$N_c$，一般的，我们希望亲和度越高的个体克隆的越多，在MO问题中，我没有区分对待每一个待克隆抗体，即对$\mathbf{Ab}_{\{n\}}$的个体取相同的克隆个数，令克隆系数为$\beta$，则
之后对超突变的个体进行重新选择生成下一次迭代的候选解形成Loop就是完整的CSA过程了，有的时候考虑到解的鲁棒性，允许随机产生一些抗原进入下一次迭代的候选解中。以上CAS的MO优化过程可以用下面的流程图表示：
下面介绍两个实现的重点：
浮点编码
之前也提到了，抗原需要根据问题的定义进行编码之后才能参与CSA过程，以便进行突变操作。多目标优化问题中，$\mathbf{x}$表示最优点的位置坐标，因此，需要对浮点数进行编码。对于$L$位编码长度的序列$(b_0, b_1, \cdots, b_{L - 1})，b_i \in \{0, 1\}$，通过如下方式编码成浮点数$z，z \in [0, 1]$：
之后配合缩放因子$\xi$，生成编码结果$d$：
用MATLAB实现如下：
1
2
3
4
5
6
7
8
9function x = decode(v, L)
% N x L
s = size(v);
% 1 x L
b = 0: 1: L - 1;
% N x L
bs = repmat(2 .^ b, s(1), 1);
x = -1 + sum(v .* bs, 2) .* (2 / (2 ^ L - 1));
end因此，计算亲和度的时候，将编码序列解码成浮点值，进行克隆和超突变的时候，在原编码序列上进行。
超突变
由于浮点值被编码成二进制序列，因此，突变即在某些位上的值进行翻转，这一操作可以用异或表示，和1取异或会将原值翻转，比如：
只要控制生成的mask中1的概率即可，这个概率称为超突变概率$P_{\text{mu}} $。
关于CSA的介绍，demo实现，实验配置和结果，以及我参阅的参考文献请戳CSA-WJ-Presentation，代码比较简单我就不贴了。
PPT模板从阿里带回来的…>_<…