《基于Stretching技术的免疫遗传算法的研究》由会员分享，可在线阅读，更多相关《基于Stretching技术的免疫遗传算法的研究（5页珍藏版）》请在金锄头文库上搜索。
1、 1 引言(Introduction) 多目标优化问题长期以来受到人们的广泛关 注，从T.C.Koopmans 第一次提出Pareto 最优解至今 已有半个多世纪，最优化问题的解决在理论和实际 上都得到了充分的发展.近年来，受生物免疫系统信 息处理机制启发而发展起来的人工免疫算法（AIA） 因其固有的多样性、自调整性、记忆和学习等功能， 已经在组合优化、机器学习、异常和故障诊断、网 络入侵检测、神经网络设计、工业生产等领域取得 了令人注目的成果。但是由于缺乏统一的算法范 式、仿生机理借鉴不够深入以及算法的收敛性和稳 定性有待进一步分析， AIA仍然存在一些问题。 特别 是当面对复杂的优化问题，
2、尤其是多峰、多极值的 多模态函数优化问题时，由于目标问题存在着众多 的局部极值，因此也会存在着早熟、收敛速度慢等 缺陷。 IEEE Catalog Number: 06EX1310 此项工作得到北京市教委重点学科共建项目资助 为了提高免疫算法对复杂多模态优化问题全局 最优解的收敛能力，本文提出一种“Stretching” 免 疫遗传算法（SIGA）。在结合免疫遗传算法的基础 上，引入一种函数“Stretching”技术，该技术能在 算法的优化过程中，不断缩小目标函数极值点的范 围,从而降低算法的搜索难度，提高算法的全局收敛 性能。文中首先阐述了函数“Stretching”技术的拉 伸机理，然后
3、给出了SIGA算法的步骤，基于Markov 链随机过程理论，证明了该算法以概率1全局收敛。 多模态函数优化的仿真结果也表明了基于该拉伸技 术的SIGA算法比不用该技术的传统IGA算法具有更 好的收敛性能。 2 函 数 “ StretchingStretching ” 技 术 (Function “Stretching” Technique) 寻求性能良好的全局优化算法并使之能可靠收 敛于问题的全局最优解，这一直是优化领域孜孜以 求的研究目标。目前已有的各种全局优化算法，如 GA、ES、EP、AIA、PSO等，尽管已被成功地应用 于各种优化问题及实际工程领域，但是当面对复杂 多模态函数优化问题时
4、，由于目标问题存在着众多Proceedings of the 25th Chinese Control Conference 7-11 August, 2006, Harbin, Heilongjiang 基于“Stretching”技术的免疫遗传算法的研究 洪 露， 穆志纯 北京科技大学信息工程学院, 北京 100083 E-mail: 摘 要: 为了提高人工免疫算法（AIA）对复杂多模态函数优化问题的全局最优解搜索能力, 本文在免疫原理和遗 传算法机制的基础上引入“Stretching”技术设计了拉伸免疫遗传算法（SIGA）, 该技术能在算法的优化过程中, 不断缩小目标函数极值点的范围,
5、降低算法的搜索难度, 从而提高了算法的全局收敛性能.利用Markov链为数学工 具, 从理论上证明了SIGA以概率1全局收敛. 实验结果表明, 基于该技术的SIGA算法比传统免疫遗传算法（IGA） 具有更好的收敛性能. 关键词: 人工免疫算法, 函数“Stretching”技术, 多模态函数优化 Study of Immune Genetic Algorithm Based on “Stretching” Technique Hong lu, Mu Zhichun School of Information Engineering, University of Science and Tech
6、nology Beijing, Beijing 100083 E-mail: Abstract: In order to enhance the global optimal search ability of AIA in solving multi-modal function optimization problem, based on mechanism of immune theory and genetic algorithm, a function “stretching” technique is introduced to obtain stretching immune
7、genetic algorithm (SIGA). The algorithm equipped with the technique can narrow the range of extreme value of the objective function, so it reduces searching difficulty and improves the global convergence performance effectively. Using mathematical methods of Markov chains theory, it is proved theore
8、tically that the SIGA is global convergent with probability 1. Simulation results indicate that the SIGA equipped with the “Stretching” technique exhibits better convergent performance compared with traditional immune genetic algorithm. Key Words: Artificial Immune Algorithm, Function “Stretching” T
9、echnique, Multi-Modal Function Optimization 1423的局部极值，因此不可避免地存在着早熟、收敛速 度慢等缺陷。基于此，Vrahatis提出了一种函数 “Stretching”技术2，用于提高全局优化算法的全 局收敛性能。 函数“Stretching”技术的实质是借助于问题的 局部极值点信息，对原始目标函数进行一种“拉伸” 变换，其目的是在全局优化算法的实施过程中，不 断缩小目标函数极值点的范围，从而降低算法的搜 索难度。通常在使用函数“Stretching”技术之前， 首先要通过优化算法按照常规的方法对其局部极值 点进行搜索，在算法探测到了一个局部极
10、值x后， 就可对目标函数( )xf进行如下“拉伸”变换 ( )( )( )( )()()1 1+=xfxfsignxxxfxG （1） ( )( )( )( )() ( )( )()()2tanh21 xGxGxfxfsignxGxH+= （2） 式中，x是目标函数( )xf的局部极值点； ,21是三个任意的正数常量；( )sign为符号函 数，即 ( ) = 010001xifxifxif xsign 符号函数( )sign也可用人工神经网络中常用的双曲 正切Sigmoid函数来近似计算，当和较大时，有 ( )( )()( )xxxsigxsigntanh1exp12tan+=（3） 在整个
11、变换过程中，根据已搜索到的局部极值 ( )xf信息，函数的解空间划分为两个区域，即区域( )( ) 1|xfxfxS=。由（1）式和（2）式可知，区域1S在整个变换过程中始终保持不变，均有( )( )( )xfxHxG=；区域2S则不同，经过（1）式后，目标函数( )xf变换为 ( )xG，即 ( )( ) 12xxxfxG+= （4） 相当于( )xf在区域2S中的每一函数值均向上进行了一次拉伸，并且点x离局部极值点x越远，其函 数值被拉伸的幅度越大，使得2S区域内目标函数的形态变得平缓，从而使得2S区域内的部分极值点转变为非极值点了，从而降低了搜索难度；2S区域中目标函数经 （2） 式进一
12、步变换后，( )xG变为( )xH， 即 ( )( )( )( )()()2 tanhxGxGxGxH+=（5） 很明显，( )xf得到了进一步的拉伸， 且距离x越 近的点其函数值被拉伸越大，因为x为局部极值 点，则其周围领域内的点具有与其相近的特性，因 此第二次拉伸是有一定意义的，可以进一步缩小后 续的搜索空间。 将此技术与全局优化算法相结合，每当优化算 法搜索到一个局部极小点，该技术就对目标函数进 行两次“拉伸”变换，将该局部极小点及劣于该局 部极小点的其它局部极小点从搜索空间剔除掉，而 优于该局部极小点的解及全局最优点却始终保持不 变。因此，函数“Stretching”技术的使用，不但没
13、 有改变搜索目标，反而降低了搜索过程的难度，提 高了优化算法的搜索效率。 3 基于函数“StretchingStretching”技术的SIGASIGA算法 (SIGA Based on Function “Stretching” Technique) 为了提高人工免疫算法求解多模态复杂函数优 化问题的效率，本文将函数“Stretching”技术引入 到人工免疫算法中，形成了一种高效的全局优化算 法 “Stretching” 免疫遗传算法 （SIGA） 。 在SIGA 算法中，把待求解的问题对应为抗原，问题的可行 候选解对应为抗体，用抗原和抗体的适应度描述可 行候选解对问题的满足程度。 主要步
14、骤如下： Step1：算法首先接收一个抗原（对应特定问 题）。 Step2：随机产生一组初始抗体种群)0(A，个体 数 为N， 抗 体 采 用 实 数 编 码 ， ,21l iiiixxxxK=表示抗体，其中l为编码长度，为待求函数的自变量个数。 Step3：计算每一个抗体和抗原的适应度。 Step4：对抗体进行两点交叉和高斯变异，如变 异后抗体适应度大于父代抗体适应度，则取代父代 抗体；如变异后抗体适应度小于或等于父代抗体适 应度，则不取代父代抗体。 Step5： 通过基于浓度的群体更新策略进行抗体的促进和抑制， 生成下一代抗体种群)(kA， 其中k表示代数。 Step6：判断新种群的大小与
15、上一代是否相同, 如不同，则随机产生新的抗体给予补充，确保抗体 种群规模大小不变。 Step7：判断算法是否满足结束条件，如不满 足，则找出该代中最优候选解，即一个局部极值解， 利用函数 “Stretching” 技术， 即根据式 （1） 和式 （2） 对目标函数进行两次拉伸变换，并转Step3，接着对 拉伸变化后的目标函数继续进行搜索优化，重复上 述操作，直到满足问题的终止条件，算法结束。 SIGA算法中主要的操作算子有： 1424（1）两点交叉法 设()11 21 11,nlxxxx=，()22 22 12,nlxxxx=是两个抗体，在第i个点和第j个点实施两点算术交叉， 产生的下一代为 ()11 11 11 1,njjilxxxxxx=+()22 1 211 2,njjilxxxxxx=+其中， kx和)( jkixk由如下线性组合产生 21)1 (kkkxxx+= 12 )1 (kkkxxx+= 1 , 0，为比例系数。 （2）高斯变异法 在高斯变异法中，抗体按照如下公式进行变异 ( )() 1 , 0(expifxxii+= （6） 式中， ix是变异后的抗体，ix是变异前的抗体， ) 1 , 0(是均值为0、方差为l的正态分布随机变量，) 1 , 1(，是个体的变异率，( )if是第i个抗体的亲和力
