基于遗传的免疫算法在函数优化中的应用

摘要:通过对传统免疫算法的研究,在此算法的基础上提出了一种改进的免疫算法—基于遗传的免疫算法,该算法把遗传算法的思想引入到免疫算法中,通过把遗传算法和免疫算法的思想结合起来,既保证了抗体的多样性又保留了群体中较优抗体,避免了免疫算法搜索速度慢和遗传算法易出现未成熟收敛、限于局部最优解的缺点,得到了全局最优解。并且将提出的基于遗传的免疫算法应用到函数优化中。

关键词:免疫算法;遗传算法;函数优化

中图分类号:TP301文献标识码:A文章编号:1009-3044(2009)25-7217-02

Application of Immune Algorithm Based on Genetic in Function Optimization

ZHAO Lian-di, MA Yong-qiang

(School of Information Science and Technology, Southwest JiaoTong University, Chengdu 610031, China)

Abstract: Through the research of traditional immune algorithm, an improved effective immune genetic algorithm is proposed based on this algorithm. The algorithm put the thought of genetic algorithm into immune algorithm, by combining idea of genetic algorithm and immune algorithm, It not only ensure the diversity of the antibody but also retain the better antibodies in group, and avoid the disadvantage of immune algorithm’s slow search speed and genetic algorithm prone to premature convergence and limit to local optimal solution, finally get the global optimal solution. And the proposed immune algorithm based on genetic applied to function optimization.

Key words: immune algorithm; genetic algorithm; function optimization

免疫算法近几年来得到了迅速发展,在众多工程和科学领域中得到了广泛应用,其中在工程应用中有许多复杂的组合优化问题和函数优化问题 ,这些问题大都是非线性的,有些甚至不连续,若不对其进行简化处理,用常规的数学优化方法一般都无法进行有效求解。免疫算法[1-2]作为一种借鉴生物免疫系统独有的计算机制,模拟生物免疫系统自适应调节过程的全局优化算法,具有搜索速度相对较快,群体多样性,容易获得全局最优解等特点。由于免疫算法有着其他算法无法比拟的优点,因此,人们广泛的应用免疫算法来解决各种实际问题,然而在实际应用中还有许多问题有待进一步研究讨论。免疫算法具有搜索全局最优解的优点,但是它的搜索速度还有待于改进,我们利用遗传算法[3-4]的搜索局部最优解的优点来调节免疫算法,使它既能避免遗传算法的“早熟”现象,又能使免疫算法的寻优速度和寻优质量有所提高。因此,研究免疫优化理论以及遗传算法[5-8]设计新的有效优化算法对优化问题具有重要的意义。

1 基本免疫算法

基本免疫算法基于生物免疫系统基本机制,模仿了人体的免疫系统。基本免疫算法从体细胞理论和网络理论得到启发,实现了类似于生物免疫系统的抗原识别、细胞分化、记忆和自我调节的功能 。如果将免疫算法与求解优化问题的一般搜索方法相比较,那么抗原、抗体、抗原和抗体之间的亲和性分别对应于优化问题的目标函数、优化解、解与目标函数的匹配程度。

基本免疫算法在优化领域中的应用非常广泛,但其存在以下缺点[7]:

1)抗体评价主要靠抗体和抗原的亲和度;

2)促进高亲和度抗体和抑制低亲和度抗体往往容易导致陷入局部最优;

3)记忆库往往只在产生初始群体时被使用,在之后的过程中只是更新记忆库,未再利用它,这没起到加速收敛的效果。

2 基于遗传的免疫算法

免疫系统对于一个优化问题而言,抗原对应问题的是目标函数,而抗体对应问题的最优解[9]。由于免疫算法和遗传算法各有优缺点[1,8],所以把二者结合起来,既能避免二者的缺点,又能更好的发挥优点。

如图1所示,基于遗传的免疫算法的主要步骤包括:

1)抗原输入:输入目标函数和各种约束,作为基于遗传的免疫算法的抗原。

2)产生初始群体:对初始应答,初始抗体随机产生,面对再次应答,部分或全部由上一代的进化群体而得,其余的随机产生,这样既保留了具有较高亲和力的解,又保证了抗体的多样性,因此,可提高收敛速度和全局搜索能力。

3)计算抗体的适应度:在当前群体中计算所有抗体的适应度。抗体的适应度函数通常是采用带优化问题目标函数的某一变换。这里采用下面的公式:

D=1-abs(y"-y)

其中y为实际值,y"为用基于遗传的免疫算法求得的最大值。

4)记忆细胞的更新:将与抗原的亲和度高的抗体放到记忆细胞中。由于记忆细胞的数量有限,所以在每次更新时,用新加入的记忆细胞取代原有的记忆细胞中亲和度较低的部分。

5)抗体生成的促进和抑制:当一种抗体和抗原相遇时,如果适应度越高则越接近最优解,反之,则越远离最优解。在寻优过程中,采用在每一代记忆细胞中随机产生部分新的抗体而取代适应度较低的抗体来调节记忆细胞,以防寻优陷入局部最优解。

6)群体更新:

① 免疫群体更新:通过选择、克隆和变异操作,产生进入下一代的抗体。u为激活阀值,当适应度大于激活阀值时,就被选择进行克隆,适应度越高,被克隆的数量越多,反之,越少。克隆数目为:l=round(10×(B(m)-u)),其中round为四舍五入取整,B(m)为第m个抗体的适应度,u为激活阀值。变异是对抗体进行小幅度的扰动,在它附近搜索最优解,本文中使用b=a+(2×rand()/10-0.1000)×a,其中a为原始抗体,rand()为随机产生的0-1之间的数。

② 遗传群体的更新:在父代中随机的选择更适应的个体,产生后代以构成下一代,在一代中好的个体可能被选几次,而较差的个体可能没有机会被选到。当选出两个父代个体后,它们被重组,这里C(n)=A(s)+(2×rand()/10-0.1000) ×A(t),C(n+1)= A(t)+(2×rand()/10-0.1000) ×A(s),其中C(n)、C(n+1)为A(t)、A(s)交叉变异后的两个个体。

7)终止条件判断:若满足终止条件,输出最优解,否则,转3)。

3 基于遗传的免疫算法在函数优化中的应用

函数优化通常是极大或极小某个多变量的函数并满足一些等式或不等式的约束。函数优化分为无约束优化和约束优化两类。虽然绝大多数实际优化问题都有必须满足的约束,但是无约束优化问题的研究是约束优化问题的基础。现有的函数优化研究大都是面向单峰函数优化问题的,但在现实生活中,很多数学工程问题都是多峰函数优化问题。对这种问题,当然可以采用多次优化计算直至发现所有峰值,但这不仅浪费时间,还不能保证各次计算收敛到多个不同的峰上。免疫遗传算法以其独特的种群策略和内在的并行性成为很多学者用来求解多峰函数优化问题的最佳选择。为了验证本文所提出的免疫遗传算法在函数优化中的应用,我们采用下列函数进行优化计算,如图2:

我们采用上述免疫遗传算法进行函数优化,用于检验该算法的有效性。本文对免疫算法和免疫遗传算法各做了200次试验,免疫遗传算法寻找到最优解的平均迭代次数为31.16次,而免疫算法的平均迭代次数为34.61次,试验结果如图3所示,其中横坐标表示搜索到最优解所需要的迭代次数,纵坐标表示在200次试验中搜索到最优解的试验次数。从图3中我们可以看出,本文所提出的把免疫算法和遗传算法结合起来的方法由于对抗体一半进行免疫搜索一半进行遗传搜索,之后进行交换抗体,循环迭代,充分利用了免疫算法和遗传算法的优点,有效的避免了两者的不足,所以更容易收敛到最优解。

显然,由图4可以看出免疫遗传算法在200次试验中,迭代次数小于10的试验有52次,而免疫算法有45次;免疫遗传算法迭代次数大多数集中在50以内,在200次试验中免疫遗传算法有173次,免疫算法有155次,免疫遗传算法明显多于免疫算法;迭代次数在50次以上的试验次数明显少于免疫算法,而且迭代次数超过100次的,免疫遗传算法是6次,免疫算法是13次,明显优于免疫算法。总体而言,本文提出的免疫遗传算法在大部分情况下确实有一定的优势,可以更快的搜索到全局最优解。

4 结论

介绍了基本免疫算法及其存在的缺点,针对其存在的缺点,提出把人工免疫算法与遗传算法相结合,在每一代操作中,把抗体分为两部分,一部分使用免疫算法的思想进行操作,另一部分使用遗传算法的思想进行操作,在本代执行完后,把两部分进行交换,很好的保证了抗体的多样性和群体中的最优抗体,避免了免疫算法搜索速度慢和遗传算法易出现未成熟收敛、限于局部最优解的缺点。将所提出的算法应用到函数优化问题中,在求解过程中,我们把抗原作为对应问题的目标函数和约束条件,把抗体作为对应问题的最优解。仿真实验证明,本文所提出的算法具有较好的优化效果,有较强的脱离局部最优值的能力,能快速稳定收敛。

参考文献:

[1] 李涛.计算机免疫学[M].北京:电子工业出版社,2004:67-68.

[2] 苏彩红,朱学锋,毛宗源.一类免疫优化算法及其应用[J].西南交通大学学报,2002,37(6):677-680.

[3] 王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.

[4] 玄光男,程润伟,于歆杰,等.遗传算法与工程优化[M].北京:清华大学出版社,2004.

[5] 高岩,位耀光,付冬梅,等.免疫遗传算法的研究及其在函数优化中的应用[J].微计算机信息,2007,23(2):183-184.

[6] 位耀光,郑德玲,付冬梅.基于生物免疫系统克隆选择机理和免疫网络理论的免疫算法[J].北京科技大学学报,2005(2)245-249.

[7] 关静.免疫遗传算法在函数优化中的应用[J].软件导刊,2007(2):91-92.

[8] 张建萍,刘希玉,谭业武.改进免疫遗传算法及其应用研究[J].计算机技术与发展,2008,18(10):166-169.

[9] 桂超,汪波.基于遗传算法的最短路径路由优化算法[J].计算机信息,2005,21(12):193-195.

推荐访问:遗传 算法 免疫 函数 优化