人工免疫思维进化算法的设计.doc

人工免疫思维进化算法的设计
摘要：文中提出一种人工免疫思维进化算法，此算法在免疫系统优化机理的基础上吸取了思维进化算法中的优点，提出了趋同半径和异化半径的概念，实现了免疫算法中抗体的局部和全局寻优，并且给出了一种基于矢量距的概率选择方法。同时，本文描述了算法的具体实现步骤，证明了算法的收敛性，给出了仿真实验。实验结果表明，新算法有机地结合了人工免疫算法和思维进化算法的优点，具有不易陷入局部极值，解的精度高，收敛速度快等特性。
关键词：人工免疫算法 思维进化算法 趋同 异化 矢量距
中图分类号：tp18 文献标识码：a 文章编号：1007-9416(2012)02-0127-03
the design of artificial immune mind evolution algorithm
li xiao-min
(engineering school of shanxi datong university, datong 037003, shanxi province)
abstract:a kind of artificial immune mind evolution algorithm is proposed in this paper, which combines the advantage of mind evolution algorithm with the optimization mechanism of immune system; the concept of similartaxis radius and dissimilation radius is defined; to realize the local optimization and global optimization of antibody, and probability choice based on vector distance was given. meanwhile, algorithm description was given in detail in this paper; the convergence of algorithm was proved, and simulation experiment was carried out. the experiment result has shown that the new algorithm has good performance with the merit of artificial immune algorithm and mind evolution algorithm, such as avoiding local optima, high precision solution, and quick convergence.
key words:artificial immune algorithm mind evolution algorithm similartaxis; dissimilation；vector distance
1、引言
生命现象和生物的智能行为一直为人工智能研究者所关注。而自然免疫系统正是人工智能方法灵感的重要源泉之一。免疫系统在显示学习、适应性、记忆机制等应用于不同计算任务的方法方面可以给人们提供丰富的灵感和启示。从人体免疫系统发展出的计算方法已经引起许多不同领域广泛的研究兴趣。受人类自然免疫系统的启发，现在已经提出了各种人工免疫算法。人工免疫算法是模拟自然免疫系统功能的一种智能方法，它实现一种受生物免疫系统启发，通过学习外界物质的自然防御机理的学习技术，提供噪声忍耐、无师学习、自组织、记忆等进化学习机理，结合了分类器、神经网络和机器推理等系统的一些优点，因此具有提供新颖的解决问题的方法的潜力[1]。它已经成为继神经网络、模糊逻辑推理和进化计算后人工智能的又一研究热点[2]。
思维进化算法[3,4]是模拟人类思维进化过程的一种新型进化算法，其中的趋同与异化的概念对于目前正在大量广泛研究的人工免疫算法有着重要的启示。
根据人工免疫和思维进化的特点，本文提出了人工免疫思维进化算法。该算法借鉴了思维进化中的上述特点，引入了趋同半径和异化半径的概念，这样抗体根据克隆扩增和受体编辑的原理分别进行局部竞争和全局竞争，实现了两层搜索机制。另外，算法中强调了免疫记忆的优良抗体保持作用。
2、人工免疫思维进化算法的生物学机理[5,6,7]
与达尔文生物进化原理相似，生物免疫系统中也存在着进化现象。当抗原侵入肌体时，b细胞群体通过如下进化过程产生抗体以消灭抗原：
(1)与抗原亲合力高的b细胞被选出。(2)在辅助t细胞的作用下，该b细胞分裂增生，产生大量b细胞，称为克隆扩增（clonal expansion）。b细胞通过克隆扩增在形状空间中的小范围内产生大量子b细胞以在局部范围内搜索亲合性更高的b细胞。(3)一些亲合力低的子b细胞删除其受体并生成新受体，即受体编辑（receptor editing）。受体编辑使得子b细胞在形状空间中可能突变为离其较远的点，以在全局范围内搜索亲合性更高的b细胞。另一些亲合力低的子b细胞死亡，同时骨髓产生一部分新b细胞以增加群体的多样性。(4)经过若干世代的选择、克隆扩增、受体编辑、骨髓产生新b细胞过程，最终产生了亲合力很高的b细胞以消灭抗原。
3、算法中的几个概念
3.1 趋同半径与异化半径
趋同和异化[3,4]是思维进化算法中的两个重要概念，将趋同与异化的思想分别与克隆扩增和受体编辑相对应。为此分别定义趋同半径和异化半径：
群体中的任一抗体的局部范围构造为：
其中为欧几里德范数，为解空间，是由与的欧氏距离不大于常数的所有可行解构成，解空间是以为中心，为半径的局部球形区域，定义为趋同半径。
群体中的任一抗体的全局范围构造为：
其中是以为中心，为半径的全局球形区域，定义为异化半径。
3.2 基于矢量距的选择方法[8]
在常见的算法中，通常选取与种群中个体适应度成正比的方法作为选择概率，这样很容易使种群中相似适应度的个体迅速增加，使算法未成熟收敛。为此，提出基于矢量距的选择方法。
将抗原、b细胞和抗体分别对应于优化问题的目标函数、优化解，解的适应度函数，n个抗体构成了一个非空免疫系统集合x。规定抗体在集合x上的距离为：
这就是抗体矢量距的定义式。于是抗体的浓度可由如下公式表示：
由此可推导出基于抗体浓度的概率选择公式：
由此可知，集合x中与抗体i基因相似的抗体越多，抗体i被选中的概率越小。反之亦然。这使得亲合力低的抗体也能得到繁殖机会，增加了抗体的多样性。
4、人工免疫思维进化算法的步骤
算法的操作步骤如下：
4.1 抗原识别
输入目标函数和各种约束条件作为免疫算法的抗原。
4.2 产生初始抗体群
产生n个实数编码的抗体作为初始群体a，在第一次迭代时，抗体通常在解空间中用随机的方法产生。
4.3 抗体选择操作
计算群体a中每个抗体的亲合力值，并且计算抗体的浓度，基于抗体浓度的概率公式选择其中m个抗体组成群体b（其中m半径全局范围内进行突变操作，保持群c的规模不变并组成群体d。突变操作是对每个抗体，按一定概率pm进行变异操作。这相当于在解空间的全局范围内进行大范围搜索。
4.6 抗体更新
群体d中亲合力最低的m1个抗体替换成步骤3中的免疫记忆抗体，组成新一代群体a。
4.7 终止条件
如果新一代群体a中有满足要求的抗体，则输出最优抗体，算法结束；否则转到第3步重复执行。
算法的流程图如图1所示。
5、算法的收敛性分析
定义1设是时刻k时群体中的最优抗体，是待求问题的抗原，当且仅当成立，称人工免疫思维进化算法是全局收敛的。
定义2[9] a是一个的方阵。
(1)若对所有的i，j，，记为，称a为非负的（nonnegative）；
(2)若a是非负的，且对所有的i，，则a是随机的（stochastic）；
(3)若a是非负的，且对a中的行和列经过置换能得到形式（c，t是方阵），则a是可约的（reducible）。
定理1[10] 设p是一个可约随机矩阵，，其中c是正的m阶随机矩阵，，，则。
定理2 人工免疫思维进化算法是依概率1收敛的。
证明：算法中的交叉操作是以概率pc对选择的一对抗体上的两个基因位进行交叉。变异操作是对抗体的每个基因位以概率pm相互独立的进行变异。则算法步骤（1～5）的n步状态转移可用状态转移阵表示，且，。根据定义1和2，状态转移矩阵p是随机的。
通过置换将转移矩阵p的各状态排列如下：第一个状态为全局最优解；第二个状态为全局次优解；依此类推，第n个状态为全局最差解。则算法步骤（6）中的更新操作可视为：对任意状态i，依 和，对转移矩阵更新，生成新的转移阵。。这里，， ，r，，是一阶正的随机矩阵，根据定义，状态转移阵p是可约的。
根据定理1，。的第一状态的极限概率为1，即，由定义1可知人工免疫思维进化算法是全局收敛的。
6、仿真实验与结论
以求极小值为例，选取以下4个函数作为测试函数：
以上函数的最优值分别为：－25、0.397887、0、－4.687，其中函数有3个极小值点。
设置人工免疫思维进化算法中的参数n=20，m=10，m15，并且使算法循环迭代100次，于是将该算法与基本思维进化算法进行函数优化比较，优化结果如表1所示。为了表示方便，以aimea代表人工免疫思维进化算法，以mea代表思维进化算法。
从上面的实验中我们可以看到，在此类阶梯函数的优化中，aimea在100代的时候已经能够找到最优解－25，但是mea却只能得到－20。由此可知，aimea在多变量求解方面较mea要好，而且其优化结果与收敛速度，都优于mea。
在和此类多峰函数的优化中，虽然函数有许多局部极小值，但是aimea仍能较快地找出全局最优解，可见其有效地避免了“早熟”现象，不容易陷入局部极值，其收敛速度也要优于mea。
而在此类函数的优化中，虽然两种算法都是有效的，都能够找到最优解。但是从收敛速度来看，aimea明显比mea快。而且其寻优结果也要比mea精确。
8、结语
综上所述，算法能在群体中优秀抗体的局部范围和全局范围内同时搜索亲合力更高的抗体。突变操作在异化半径内进行大范围搜索，以在全局搜索亲合力高的区域，是粗搜索，当粗搜索找到亲合力较高的区域后，扩增操作通过趋同半径进行局部细搜索以寻求高精度的解。算法通过粗和细的两层搜索，以保证其全局寻优和局部求精度的性能。
由此可见，人工免疫思维进化算法不易陷入局部极值，并且在收敛速度与精确性等方面还是有一定的优势的。
参考文献
[1]丁永生,任立红.人工免疫系统：理论与应用[j].模式识别与人工智能,2000,13(1):52－59.
[2]jon timmis,mark neal,john hunt.an artificial immune system for data analysis[j].biosystem,2000(55):143-150.
[3]keming xie, changhua mou, gang xie. the multi-parameter combination mind-evolutionary-based machine learning and its application[a]. 2000 ieee international conference on system, man, and cybernetics(smc2000). music city sheraton, nashville, tennessee, usa, 2000. 183—187.
[4]keming xie, changhua mou, gang xie. a new mebml-based algorithm for adjusting parameters on-line[a]. 2000 5th international conference on signal processing proceedings(icsp2000, wcc2000). beijing, china, 2000.1714—1717.
[5]左兴权,李士勇,黄金杰.一种新的免疫进化算法及其性能分析[j].系统仿真学报,2003,15(11):1607－1609.
[6]de castro l n,von zuben f j.learning and optimization using the clonal selection principle[j].ieee transactions on evolutionary computation,2000,6(3):239-251.
[7]ada g l,nossal g.the clonal selection theory[j].scientific american,1987,257(2):50-57.
[8]吕岗,陈小平,谭得健.免疫算法抗体浓度调节定义的改进[j].数据采集与处理,2003,18(1):44－48.
[9]rudolph g.convergence properties of canonical genetic algorithms[j].ieee trans on nerual networks,1994,5(1):96-101.
[10]iosifescu m.finite markov processes and their applications [m].chichester,wiley,1980.