基于模式记忆的免疫遗传算法

第２２卷第８期计算机仿真２００５年８月文章编号：１００６—９３４８（２００５）０８—００９８—０３

基于模式记忆的免疫遗传算法

武晓今，朱仲英

（上海交通大学电子信息与电气工程学院自动化系，上海２０００３０）

摘要：免疫遗传算法在传统遗传算法的全局随机搜索的基础上，借鉴生物免疫机制中的抗体的多样性，能有效提高群体的多样性，同时其具有记忆功能能够有效地提高搜索效率。但是在函数优化问题的解决上，免疫记忆功能一直没有能很好的实现。该文提出在免疫遗传算法中引入模式控制的方法来解决复杂函数优化的问题。基于免疫遗传机翻，利用免疫记忆库记忆优秀免疫遗传模式，它能有效地加速优化过程，并且克服通常函数优化无缺乏记忆的功能。通过一个复杂函数的仿真实例证明了该方法的有效性。

关键词：免疫；模式控制；函数优化

中图分类号：ＴＰ２０２＋．７文献标识码：Ａ

ＳｃｈｅｍａＣｏｎｔｒｏｌｆｏｒＩｍｍｕｎｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

ＷＵＸｉａｏ—ｊｉｎ，ＺＨＵＺｈｏｎｇ—ｙｉｎ

（ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｏｎｉｃＩｎｆｏｒｍａｔｉｏｎ＆ＥｌｅｃｔｒｉｃｉｔｙＥｎｇｉｎｅｅｒｉｎｇ，ＳｈａｎｇｈａｉＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ，２０００３０，Ｃｈｉｎａ）ＡＢＳＴＲＡＣＴ：ＩｍｍｕｎｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ｂａｓｅｄｏｎｇｅｎｅｒａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｈａｓｔｈｅｐｅｒｐｅｔｕｉｔｙｏｆｇｌｏｂａｌｓｅａｒｃｈｉｎｇａｎｄｄｉｖｅｒｓｉｔｙｏｆｔｈｅｂｉｏｌｏｇｉｃａｌｉｍｍｕｎｅｍｅｃｈａｎｉｓｍ，ｃａｎａｄｖａｎｃｅｔｈｅｄｉｖｅｒｓｉｔｙｏｆｅｖｏｌｕｔｉｏｎｇｒｏｕｐｅｆｆｅｃｔｉｖｅｌｙ，ａｎｄｉｔｓｍｅｍｏｒｙｆｕｎｃｔｉｏｎｃａｎｉｍｐｒｏｖｅｔｈｅｓｅａｒｃｈｉｎｇｅｆｆｉｃｉｅｎｃｙ．Ｈｏｗｅｖｅｒ，ｉｍｍｕｎｅｍｅｍｏｒｙｆｕｎｃｔｉｏｎ

ｆｏｒｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｈａｓｎｏｔｂｅｅｎｒｅａｌｉｚｅｄｖａｌｉｄｌｙｙｅｔ．Ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓａｓｃｈｅｍａｃｏｎｔｒｏｌｍｅｔｈｏｄｆｏｒｉｍｍｕｎｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅｃｏｍｐｌｅｘｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ．Ｂａｓｅｄｏｎｉｍｍｕｎｅｇｅｎｅｔｉｃｍｅｃｈａｎｉｓｍ，ｉｔｕｓｅｓｖａｃｃｉｎｅｓｂａｎｋｔｏｍｅｍｏｒｉｚｅｅｘｃｅｌｌｅｎｔＩＧＡｓｃｈｅｍａｉｎｏｒｄｅｒｔｏｖａｌｉｄｌｙａｃｃｅｌｅｒａｔｅｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｃｅｓｓ，ａｎｄｍａｋｅｇｅｎｅｒａｌｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎｈａｖｅｔｈｅｍｅｍｏｒｙｆｕｎｃｔｉｏｎ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｐｒｏｖｅｔｈａｔｔｈｉｓａｌｇｏｒｉｔｈｍｈａｓｇｏｏｄｐｅｒｆｏｒｍａｎｃｅ．

ＫＥＹＷＯＲＤＳ：Ｉｍｍｕｎｅ；Ｓｃｈｅｍａｃｏｎｔｒｏｌ；Ｆｕｎｃｔｉｏｎｏｐｔｉｍｉｚａｔｉｏｎ

ｌ引言

免疫的遗传算法是基于生命科学中免疫原理与传统遗传算法的结合。免疫系统是高度进化的生物系统，它的功能是针对外来抗原的输入产生识别并消灭抗原的抗体。脊椎动物体内存在不同类别的抗体对外来抗原有不同的敏感程度，受到抗原刺激后产生的结果也不同。同时对某种抗原，抗体还存在一定的记忆功能，并可以随生物体的繁衍而带入下一代。

近年来，对免疫与遗传算法的研究一般侧重于两个方面：一是侧重于把遗传操作转向免疫操作…旧１，他们利用亲和度函数和浓度函数来进行免疫操作，能够比较好地消除致死遗传子，但是对于利用先验的经验知识即免疫记忆比较

收稿日期：２００４—０５～１２

—９８一少；另一个是注重免疫记忆旧１，它使用公式：免疫算法＝遗传算法＋记忆细胞＋抑止细胞来构成算法。这类研究侧重于组合优化特别是ＴＳＰ等ＮＰ完全问题，但是对函数优化方面研究较少，主要原因是许多现存的组合优化问题都可以比较容易构建固定的优化模式（如利用先验知识或者经验来形成一些固定的优化路径），利用记忆这些优化模式来加速进化计算过程；然而在函数优化问题中，这类模式很难找到，总体搜索是随机的。为此，本文提出利用模式记忆功能的免疫遗传算法，把免疫记忆功能引入函数优化问题的解决中，从而扩大免疫遗传算法的应用范围。

２具有模式记忆的免疫遗传算法构造

２．１免疫遗传算法

免疫遗传算法把问题的目标函数和制约条件作为抗原，通过计算抗体与抗原的亲和度探索最优解。为防止近亲繁殖又设定了抗体与抗体间的相似度的计算，有效地控制了优秀

　万方数据万方数据