赵工的个人空间

遗传算法GA（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的一种计算模型，即遵循适者生存、优胜劣汰的法则搜寻最优解，也就是寻优过程中有用的保留无用的去除。这种算法最初由美国Michigan大学Holland教授首先提出，是进化算法的一种。
免疫算法基于生物免疫系统基本机制，把免疫概念引入工程领域并将其与已有的一些智能算法结合起来，以建立新的进化理论与算法来提高算法的整体性能。免疫算法通过类似生物免疫系统的机能，构造具有动态性和自适应性的信息防御体系，以此来抵制外部无用的或有害的信息侵入，从而保证接受信息的有效性。

一、遗传算法：

遗传算法的整体搜索策略和优化搜索方法在计算时不依赖梯度信息或其他辅助知识，而只需影响搜索方向的目标函数和相应的适应度函数，提供了一种求解复杂系统问题的通用框架，一般用于函数优化和组合优化等领域，也在生产调度、自动控制、机器人、图像处理、机器学习等方面获得应用。

1. 遗传算法基本原理：

遗传操作是模拟生物基因遗传的做法，在算法中通过编码组成初始群落后，遗传操作的任务就是对群体的个体按照它们对环境适应度施加一定的操作，从而实现优胜劣汰的进化过程。
遗传操作包括三个基本遗传算子，选择、交叉、变异。
1）算法运算过程：
⑴选择：
从群体中选择优胜个体、淘汰劣质个体的操作称为选择，选择算子有时也称为再生算子。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。
选择操作是建立在群体中个体的适应度评估基础上的，常用的选择算子有适应度比例方法、随机遍历抽样法、局部选择法。其中，轮盘赌选择法（roulette wheel selection）是最简单最常用的选择方法，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度fi，则i被选择的概率为：

概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例，个体适应度越大，其被选择的概率就越高。计算出群体中各个个体的选择概率数后，为了选择交配个体，需要进行多轮选择，每轮产生一个[0,1]之间的均匀随机数，将该随机数作为选择指针来确定被选个体。个体选择后，可随机组成交配对，以供后面的交叉操作。
⑵交叉：
在自然界生物进化过程中起核心作用的是遗传基因的重组，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉，是把两个父代个体的部分结构加以替换重组，而生成新个体的操作。通过交叉，遗传算法的搜索能力得以提高。
交叉算子根据交叉率将种群中的个体随机地交换某些基因，能够产生新的基因组合，期望将有益的基因组合在一起。根据编码的不同，可以有实值重组和二进制交叉两类，实值重组包括离散重组、中间重组、线性重组、扩展线性重组等，而二进制交叉有单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉等。
最常用的交叉算子是单点交叉，具体操作是，在个体串中随机设定一个交叉点实行交叉时，该点前或后的两个个体的部分结构进行交换，并生成两个新个体。
⑶变异：
变异算子是针对群体中的个体串的某些基因座上的基因值做变动，依据个体编码表示方法的不同，有实值变异和二进制变异。一般来说，变异算子操作是对群中所有个体以事先设定的变异概率判断是否进行变异，而对进行变异的个体随机选择变异位进行变异。遗传算法引入变异，使算法具有局部的随机搜索能力，也维持群体的多样性，以防止未成熟收敛现象。
遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合，是指当群体在进化中陷入搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱；所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。
基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座，并对这种基因座的基因值做变动。变异率的选取一般受种群大小、染色体长度等因素影响，通常选取很小的值，一般取0.001~0.1。
当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设代数一般设置为100~500。
2）算法编码：
遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体，这一转换操作称为编码。评估编码策略常采用三个规范：
⑴完备性：问题空间中的所有点（候选解）都能作为GA空间中点（染色体）的表现
⑵健全性：GA空间中的染色体能对应所有问题空间中的候选解
⑶非冗余性：染色体和候选解一一对应
目前几种常用的编码技术有二进制编码、浮点数编码、字符编码、变成编码等。而二进制编码是目前遗传算法中最常用的编码方法，也就是由二进制字符集{0,1}产生通常的0、1字符串来表示问题空间的候选解，这种方法简单易行，符合最小字符集编码原则，便于用模式定理进行分析。
遗传算法有四个参数需要提前设定，一般在以下范围内进行设置：
·群体大小：20~100
·遗传算法的终止进化代数：100~500
·交叉概率：0.4~0.99
·变异概率：0.0001~0.1
3）适应度和初始群体选择：
进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也称评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。
遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。
适应度函数的设计主要满足单值、连续、非负、最大化，要计算量小和通用性强。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定，该函数设计直接影响到遗传算法的性能。
遗传算法中初始群体中的个体是随机产生的。一般来说，初始群体的设定可采取如下策略：
⑴根据问题固有知识，设法把握最优解所占空间在整个空间中的分布范围，然后在此分布范围内设定初始群体。
⑵先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中，这个过程不断迭代，直到初始群体中个体数达到预先确定的规模。
4）适应度函数的调整：
在遗传算法运行的初期阶段，群体中会有少数几个个体的适应度相对于其他个体来说非常高，若按照常用的比例选择算子来确定个体的遗传数量，则这几个相对较好的个体将在下一代群体中占有很高的比例。极端情况下或当群体规模较小时，新的群体甚至完全由这样的少数几个个体所组成，这时交叉运算起不了什么作用，这样会使多样性降低，容易导致发生早熟，使遗传算法求得的解留在某一局部最优点上。因此，希望在遗传算法运行的初期，能够对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制其复制数量，以维护群体的多样性。
在遗传算法运行的后期阶段，群体中所有个体的平均适应度可能会接近于群体中最佳个体的适应度，它们之间无竞争力，都会有以相接近的概率被遗传到下一代的可能性，从而使得进化过程无竞争性可言，只是一种随机的选择过程。这将导致无法对某些重点区域进行重点搜索，从而影响遗传算法的运行效率。因此，希望在遗传算法的后期阶段，算法能够对刚体的适应度进行适当的放大，扩大最佳个体适应度与其他个体适应度的差异程度，以提高个体之间的竞争性。

2. MATLAB遗传算法工具箱：

MATLAB软件有专门的遗传算法工具箱，方便用户调用。也有第三方开发的工具箱。
1）ga函数：
[x,fval,exitflag,output,population,scores]=ga(fitnessfun,nvars,...options)
其中，fitnessfun为适应度句柄函数；nvars为目标函数自变量的个数；options为算法的属性设置，该属性是通过函数gaoptimset赋予的；x为经过遗传进化以后自变量最佳染色体返回值；fval为最佳染色体的适应度；exitflag为算法停止的原因；output为输出的算法结构；population为最终得到种群适应度的列向量；scores为最终得到的种群。
2）gaoptimset函数：
gaoptimset函数是设置遗传算法的参数和句柄函数，常用的11种属性见表：

使用格式为：options=gaoptimset('param1',value1,'param2',value2,...)
⑴前一次运行结果种群作为下一次运行的初始种群：
由于遗传算法本质上是一种启发式的随机算法，需要重复运行多次才能得到理想结果。因此，可以将前一次运行得到的最后种群作为下一次运行的初始种群，如此操作会得到更好的结果。
[x,fval,reason,output,finnal_pop]=ga(@fitnessfun,nvars)
上述代码输出变量finnal_pop，其返回的是本次运行得到的最后种群。然后再将finnal_pop作为函数ga的初始种群：
options=gaoptimset('InitialPopulation',finnal_pop);
[x,fval,reason,output,finnal_pop2]=ga(@fitnessfun,nvars,finnal_pop);
⑵直接令目标函数为适应度函数：
遗传算法和ga函数是求解目标函数的最小值，求目标函数最小值的问题可直接令目标函数为适应度函数，语法格式为：
function f=fitnessfcn(x)
f=f(x);
如果有约束条件，包括自变量的取值范围，对于求解函数的最小值问题，可以使用语法：
function f=fitnessfcn(x)
if (x<=-1)|x>3)
f=inf;
else
f=f(x);
end
如果有约束条件，包括自变量的取值范围，对于求解函数的最大值问题，可以使用语法：
function f=fitnessfcn(x)
if (x<=-1)|x>3)
f=inf;
else
f=-f(x);
end
若目标函数作为适应度函数，则最终得到的目标函数值为-fval而不是fval。
3）gaoptimget函数：
用于得到遗传算法参数结构中的参数具体值。调用格式：
val=gaoptimget(options,'name')
其中，options为结构体变量；name为需要得到的参数名称，返回值为val。

3. 使用MATLAB GUI实现遗传算法：

命令行输入gatool可以打开遗传算法工具箱GUI界面。有些版本可能不支持。

二、免疫算法：

在遗传算法的交叉和变异运算中，因为本身具有一定盲目性，如果引入免疫方法，对遗传算法全局搜索的过程进行一定强度的干扰，就可以避免很多重复无效的工作，从而提高算法效率。
免疫系统具有辨识记忆的特点，所以可以更快识别个体群体。面对求解问题时，相当于面对各种抗原，可以提前注射疫苗来抑制退化问题，从而更加保持优胜劣汰的特点，使算法一直优化下去，即达到免疫的目的。

1. 免疫算法的基本原理：

一般免疫算法可分为三种情况，模仿免疫系统抗体与抗原识别，结合抗体产生过程而抽象出来的免疫算法；基于免疫系统中的其他特殊机制抽象出的算法，如克隆选择算法；与遗传算法等其他智能算法融合产生新算法，如免疫遗传算法。合理提取疫苗是免疫算法的核心。
1）免疫算法的步骤：
⑴抗原识别：输入目标函数和各种约束条件作为免疫算法的抗原，并读取记忆库文件
⑵产生初始解：初始解的产生来源有两种，根据上一步对抗原的识别，如果记忆库中有则取记忆库，不足则随机产生；若记忆库为空，全部随机生成。
⑶适应度评价：按给定的适应度评价函数计算各自适应度
⑷记忆单元的更新：将适应度高的个体加入到记忆库，使其能够延续到后代中
⑸基于解的选择：选入适应度较高的个体，产生后代，使适应度较低的个体受到抑制
⑹产生新抗体：通过交叉、变异、逆转等算子，选入的父代将产生新一代抗体
⑺终止条件：条件满足则终止，若不满足则跳转到步骤⑶
2）亲和力计算：
免疫算法中最复杂的计算是亲和力计算，亲和力公式为：

式中，tk为抗原和抗体k的结合强度。
一般免疫算法计算结合强度tk的数学工具主要有：
⑴海明距离：

⑵Euclidean距离：

⑶Manhattan距离：

目前，一般免疫算法问题的编码方式主要有二进制编码、实数编码和字符编码三种。其中，二进制编码因简单而得到广泛应用。
3）免疫系统模型和免疫算法：
ARTIS（Artificial Immune System）是Hofmeyr提出的一种分布式人工免疫系统模型，它由一系列模拟淋巴结的节点构成，每个节点由多个检测器组成，各个节点都可以独立完成免疫功能。模型涉及的免疫机制包括识别、抗体多样性、调节、自体耐受、协同刺激等。
在ARTIS中，用固定长度的二进制串构成的有限集合U来表示蛋白质链，U可以分为两个子集，N表示非自体，S表示自体，满足：

目前常用的两种免疫算法是阴性选择算法和克隆选择算法。

2. 免疫遗传算法：

免疫遗传算法的基本思想是在传统遗传算法的基础上加入免疫算子，加入免疫算子的目的是防止种群退化，免疫算子由接种疫苗和免疫选择两个步骤组成，具有更好地保持群体多样式的能力。
免疫遗传算法和遗传算法的结构基本一致，最大的不同之处在于，在免疫遗传算法中引入了浓度调节机制。进行选择操作时，遗传算法值只利用适应度值指标对个体进行评价；免疫遗传算法的选择策略变为：适应度越高，浓度越小，个体复制的概率越大；适应度越低，浓度越高的个体，得到选择的概率就越小。
免疫遗传算法的流程为：
⑴抗原识别。将所求的目标函数及约束条件当作抗原进行识别，来判断是否曾经解决过该类问题
⑵初始抗体的产生，对应遗传算法就是解的初始值。经过对抗原的识别，如果曾解决过此类问题，则直接寻找相应的记忆细胞，从而产生初始抗体
⑶记忆单元更新。选择亲和度高的抗体进行存储记忆
⑷抗体的抑制和促进。在免疫遗传算法中，亲和力高的抗体受到促进，而亲和力低的就会受到抑制，这样很容易导致群体的进化单一，导致局部优化，因此需要在算法中插入新的策略，保持群体的多样性。
⑸遗传操作。遗传是经过交叉、变异产生下一代抗体的过程，而免疫遗传算法通过考虑抗体亲和度和群体多样性选择抗体群体，进行交叉编译从而产生新一代抗体，保证种群向适应度高的方向进化。