蚁群算法模拟系统设计及实现.doc

J I A N G S U U N I V E R S I T Y本 科 毕 业 论 文蚁群算法模拟系统的设计与实现Ant Colony Simulation System Design and Implementation学院名称： 专业班级： 学生姓名： XXXXX 指导教师姓名： XXXXX 指导教师职称： 2010年 6 月蚁群算法模拟系统的设计与实现专业班级：J计算机0601 学生姓名：汤琪 指导教师：蔡涛 职称：副教授摘要： 人工免疫算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用不足，往往做大量无为的冗余迭代，求解效率低。蚁群算法具有分布式并行全局搜索能力，但初始解随机，易早熟且求解速度慢。本文提出免疫算法和蚁群算法的混合算法免疫蚁群算法，通过信息素更新获得全局最佳解。通过匹配检测仿真实验，结果证明该算法是计算精度较好的一种算法。本设计是在Linux环境下，用C语言编写的。Linux是一类Unix计算机操作系统的统称。Linux操作系统的内核的名字也是“Linux”。Linux操作系统也是自由软件和开放源代码发展中最著名的例子。严格来讲，Linux这个词本身只表示Linux内核，但在实际上人们已经习惯了用Linux来形容整个基于Linux内核，并且使用GNU 工程各种工具和数据库的操作系统。Linux得名于计算机业余爱好者Linus Torvalds。 关键词：人工免疫算法 蚁群算法 匹配检测 LinuxAnt Colony Simulation System Design and ImplementationAbstractArtificial immune algorithm is fast random global search capability, but the feedback system is underutilized, often do a lot of inactive redundant iteration, solve the low efficiency.Ant colony algorithm has the distributed parallel global search capability, but the initial solution randomly, prematurity and slow to solve.In this paper, the immune algorithm and ant colony hybrid immune algorithm ant colony algorithm, pheromone update access to the global optimal solution.Detected by matching simulation results show that the algorithm is an algorithm for better accuracy.The design is in the Linux environment, using C language. Linux is a Unix-computer operating system collectively. Linux operating system kernel's name is "Linux". Linux operating system is free software and open source development in the most famous example. Strictly speaking, Linux is only the word that Linux kernel itself, but in fact people have used to describe the use of Linux based on Linux kernel and GNU project using various tools and database operating systems. Linux is named after the computer amateur Linus Torvalds. Key WordsArtificial immune algorithm ant colony algorithm matching test Linux目 录中文摘要IABSTRACTII目 录1第一章 引言31.1. 研究背景31.2. 本课题的开发意义4第二章 关键技术52.1. Linux 基本知识52.1.1 Linux的发展历史52.1.2 Linux的常用命令62.1.3 GCC基础知识要点72.2. 基本蚁群算法92.2.1 基本蚁群算法92.2.2 蚁群算法基本步骤112.2.3蚁群算法流程图112.2.4复杂度分析122.3. 基本人工免疫算法132.3.1 一般免疫算法的理论思想132.3.2 人工免疫算法15第三章 系统的设计与实现173.1 人工免疫算法设计173.1.1 人工免疫算法基本步骤173.1.2 人工免疫算法流程图173.1.3人工免疫的相关设计183.2蚁群算法设计203.2.1 蚁群算法实现步骤203.2.2 蚁群算法流程图213.3随机检测设计21第四章 运行234.1各运行命令234.2检测器的添加244.3整体检测244.4随机选取检测器检测244.5蚁群算法选取检测器检测25第五章 总结27致 谢28参考文献29第一章 引言1.1. 研究背景人工智能经历了20世纪80年代整整10年的繁荣后，由于方法论上始终没有突破经典计算思想的樊篱，再次面临着寒冬季节的考验。在这种背景下，社会性动物(如蚁群、蜂群、鸟群等)的自组织(Self-organization)行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用于计算机对其进行仿真，这就产生了所谓的“群体智能” (Swarm Intelligence，简称SI)。社会性动物的妙处在于:个体的行为都很简单，但当他们一起协同工作时，却能够“突现”出非常复杂(智能)的行为特征。例如，单只蚂蚁的能力极其有限，但当这些简单的蚂蚁组成蚁群时，却能完成像筑巢、觅食、迁徙、清扫蚁巢等复杂行为;一群行为显得盲目的蜂群能造出精美的蜂窝;鸟群在没有集中控制的情况下能够同步飞行等。这些自组织行为中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注目。受其启发，意大利学者M.Dorigo，V.Maniezzo and A.colorni于20世纪90年代初提出的一种新型的智能优化算法蚁群优化 (Ant Colony Optimization，简称ACO)。它通过信息素的积累和更新来寻求最优解，主要特点是模拟自然界中蚂蚁的群体行为。目前国内外研究者用蚁群算法研究了旅行商问题，指派问题，调度问题等，取得了一系列较好的实验结果。蚁群算法具有分布式并行搜索能力，较强的鲁棒性和易于与其他算法结合等优点，但同时也存在着一些不足之处:(1)与其他算法相比该算法需要较长的搜索时间;(2)该算法容易早熟，即搜索进行一定程度后，所有个体所发现的解完全一致，不能对解空间进行进一步搜索;(3)初始解和初始信息素随机。 近几年，人们提出了多种方法来解决蚁群算法的这三个缺点，其中蚁群算法与其他算法混合产生新的混合算法是一个研究方向，例如禁忌算法与蚁群算法混合，遗传算法与蚁群算法混合，粒子群算法与蚁群算法混合等。这些算法应用于TSP问题或函数优化问题的求解取得了较好效果。 人工免疫系统 (Artificial Immune System，简称AIS)是模仿生物免疫系统的免疫应答、免疫调节等机理，构造出的一类高性能、自组织、鲁棒性好的人工智能系统。目前，人工免疫系统的研究己经受到学者们越来越广泛的关注，人工免疫算法也在实际工程应用中得到了推广。人工免疫成为继神经网络、模糊逻辑和进化计算后人工智能领域又一研究热点。免疫系统是一种复杂的分布式信息处理学习系统，这种系统具有免疫防护、免疫耐受、免疫记忆、免疫监视功能，这些功能和特点给予研究人员较多的灵感，促成许多学者建立了基于免疫机理的智能方法，解决大量的非线性科学问题。本文将人工免疫算法与蚁群算法混合产生新的算法免疫蚁群算法(Artificial Immune Ant Colony Algorithm，简称AIACA)，并将该算法应用于匹配检测，计算机仿真结果证明该算法是计算精度都较好的一种算法。1.2. 本课题的开发意义 本课题通过蚁群优化算法改进人工免疫算法，主要改进人工免疫算法中通过抗体与抗原之间的亲和力以及抗体与抗体之间的排斥力来选择抗体的方法。采用人工免疫算法生成信息素分布，利用蚁群算法求优化解，优势互补，在收敛速度和寻优能力两方面较原有算法都有明显改善。第二章 关键技术2.1. Linux 基本知识2.1.1 Linux的发展历史 Linux的历史可以追溯到1990年，Linus Torvalds还是芬兰赫尔辛基大学的一名学生，最初用汇编语言写了一个在80386保护模式下处理多任务切换的程序，后来从Linux(用于操作系统教学、很小的Unix)中得到灵感，发誓要写一个比Linux更好的Linux，于是开始写了一些硬件的设备驱动程序、一个小的文件系统.，这样0.0.1版本的Linux就出来了，但是它必须在有Linux的机器上编译以后才能玩，这时候的Linus已经完全“走火入魔”了，决定踢开Linux “闹革命”，于是在1991年10月5号发布了Linux 0.0.2版本，这个版本已经可以运行bash(一种用户与操作系统内核通讯的软件)和gcc(GNU C编译器)了。 Linux从一开始，就决定自由扩散Linux、包括源代码，他把源代码发布在网上，随即就引起爱好者的注意，他们通过互连网也加入了Linux的内核开发工作，一大批高水平程序员的加入，使得Linux达到迅猛发展，到1993年底，Linux 1.0终于诞生。Linux 1.0已经是一个功能完备的操作系统了，其内核写得紧凑高效，可以充分发挥硬件的性能，在4M内存的80386机器上也表现得非常好 很多人对Linux的认识有个误区，即总把Linux与低档硬件平台联系到一起，其实从2.1.xx系列内核开始，Linux就开始走高端的路子了，大约在1.3版本之后，开始向其他硬件平台上移植，包括号称最快的CPU-Digital Alpha(目前主频是最高的)，目前Linux能将硬件的性能充分发挥出来，可以囊括低端到高端的所有应用。 Linux加入GNU并遵循公共版权许可证(GPL)，由于不排斥商家对自由软件进一步开发，不排斥在Linux上开发商业软件，故而使Linux又开始了一次飞跃，出现了很多的Linux发行版，如Slackware、Redhat、Suse、Turbo Linux、Open Linux等十多种，而且还在增加，还有一些公司在Linux上开发商业软件或把其他Unix平台的软件移植到Linux上来，如今很多IT界的大腕如IBM、Intel、Oracle、Infomix、Sysbase、Corel、Netscape、CA、Novell等都宣布支持Linux! 商家的加盟弥补了纯自由软件的不足和发展障碍，Linux得以迅速普及。2.1.2 Linux的常用命令 如果在Linux命令行模式下遇到不会用的命令，你可以打"man command"得到该命令的帮助，如果想知道一个命令有哪些参数，可以打command -help来得到。 注意：Linux中的参数输入形式和dos不一样，在命令后面应该打一个空格，然后打"-"，最后再跟一个或多个参数；另外Linux下大小写是有区别的！ 下面介绍几个Linux下最常用的命令，每个命令都与对应的dos命令作比较，并列出一些常用的参数。 命令参数 意 义 Ls -a列出系统中的隐含文件，linux下的隐含文件是靠文件名的格式来表示的，不同于dos是靠文件属性来表示，即只要该文件以“.”开头，那么它就是隐含文件。 -l以长式列出。就是把该文件或目录的所有信息都列出来，一个文件占一行 相当于dos下的dir命令，是列文件列表的命令。 cd 和dos下的cd一样，转换目录的命令。 注意：linux下转到上级目录要打"cd ."而不是dos下的"cd."，即"cd"后面要有个空格 pwd 列出当前目录命令，相当于dos下没有参数的cd命令。例如： rootttqq bin# pwd /usr/bin rootttqq bin# 这表示目前在"/usr/bin"目录下。 Mkdir -m mode表示建立目录时默认的目录模式。这个是dos和Windows所没有的功能，主要是关于权限的问题。 建立新目录，相当于dos的md命令。一般就用 mkdir dirname rmdir 删除目录，相当于dos的rd命令。 用法：rmdir dirname cat 在文件后面追加文件，或在屏幕上打印文件内容，追加功能相当于dos的copy file1+file2，而在屏幕上打印文件内容可以和dos的typeml来类比。如果文件太大，在一屏上无法完全显示，则可用more命令 more 分屏显示文件内容，和dos下的more命令大致相同，但它可以和别的命令搭配使用。如：cat /home/eec/myfile | more。 cp -r相当于dos的xcopy/s。用于拷贝一个目录下的所有子目录和文件 拷贝文件，相当于dos下的copy，使用方法与dos下的copy一样。2.1.3 GCC基础知识要点 基本规则gcc所遵循的部分约定规则： .c为后缀的文件，C语言源代码文件；.a为后缀的文件，是由目标文件构成的档案库文件；.C，.cc或.cxx 为后缀的文件，是C+源代码文件；.h为后缀的文件，是程序所包含的头文件；.i 为后缀的文件，是已经预处理过的C源代码文件；.ii为后缀的文件，是已经预处理过的C+源代码文件；.m为后缀的文件，是Objective-C源代码文件；.o为后缀的文件，是编译后的目标文件；.s为后缀的文件，是汇编语言源代码文件；.S为后缀的文件，是经过预编译的汇编语言源代码文件。 执行过程 虽然我们称Gcc是C语言的编译器，但使用gcc由C语言源代码文件生成可执行文件的过程不仅仅是编译的过程，而是要经历四个相互关联的步骤预处理(也称预编译，Preprocessing)、编译(Compilation)、汇编(Assembly)和链接(Linking)。命令gcc首先调用cpp进行预处理，在预处理过程中，对源代码文件中的文件包含(include)、预编译语句(如宏定义define等)进行分析。接着调用cc1进行编译，这个阶段根据输入文件生成以.o为后缀的目标文件。汇编过程是针对汇编语言的步骤，调用as进行工作，一般来讲，.S为后缀的汇编语言源代码文件和汇编、.s为后缀的汇编语言文件经过预编译和汇编之后都生成以.o为后缀的目标文件。当所有的目标文件都生成之后，gcc就调用ld来完成最后的关键性工作，这个阶段就是连接。在连接阶段，所有的目标文件被安排在可执行程序中的恰当的位置，同时，该程序所调用到的库函数也从各自所在的档案库中连到合适的地方。 基本用法在使用Gcc编译器的时候，我们必须给出一系列必要的调用参数和文件名称。Gcc编译器的调用参数大约有100多个，其中多数参数我们可能根本就用不到，这里只介绍其中最基本、最常用的参数。Gcc最基本的用法是gcc options filenames其中options就是编译器所需要的参数，filenames给出相关的文件名称。-c，只编译，不连接成为可执行文件，编译器只是由输入的.c等源代码文件生成.o为后缀的目标文件，通常用于编译不包含主程序的子程序文件。-o output_filename，确定输出文件的名称为output_filename，同时这个名称不能和源文件同名。如果不给出这个选项，gcc就给出预设的可执行文件a.out。-g，产生符号调试工具(GNU的gdb)所必要的符号资讯，要想对源代码进行调试，我们就必须加入这个选项。-O，对程序进行优化编译、连接，采用这个选项，整个源代码会在编译、连接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、连接的速度就相应地要慢一些。-O2，比-O更好的优化编译、连接，当然整个编译、连接过程会更慢。-Idirname，将dirname所指出的目录加入到程序头文件目录列表中，是在预编译过程中使用的参数。C程序中的头文件包含两种情况A)#include <myinc.h>B)#include “myinc.h”其中，A类使用尖括号(< >)，B类使用双引号(“ ”)。对于A类，预处理程序cpp在系统预设包含文件目录(如/usr/include)中搜寻相应的文件，而B类，预处理程序在目标文件的文件夹内搜索相应文件。2.2. 基本蚁群算法2.2.1 基本蚁群算法 蚁群优化算法是一种受自然界生物行为启发而产生“自然”算法。产生于对蚁群行为的研究。蚁群中的蚂蚁以“信息素”(pheromone)为媒介，间接异步的相互联系。这是蚁群优化算法的最大特点。蚂蚁在行动过程中(寻找食物或寻找回巢的路径)中，会在他们经过的地方留下一些化学物资，称之为“信息素”。这些物资能被同一蚁群中后来的蚂蚁感受到并作为一种信号影响后者的行动。具体表现在后到的蚂蚁选择有这些物资的路径的可能性比选择没有这些物资的路径的可能性大得多。后到者留下的信息素会对原有的信息素进行加强，并循环下去。这样，经过蚂蚁越多的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其他蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路为止。 通过图2.1简单的了解蚂蚁的运动过程。假设一个蚂蚁外出寻找食物，蚂蚁从nest点出发，行走速度相同，食品在food点，蚂蚁可能行走的路线如图2.1。由于无法预知道路中间的情况，蚂蚁出发时会随机选择nest-B-food或nest-C-food中的一条。假设初始每条路线上分别分配一只蚂蚁，每单位时间走一步。当行走7个单位时间后，为图2.1中上半部分的情形，已经有一个蚂蚁到达food点。当行走14个单位时间后，走nest-B-food的蚂蚁己经回到A点，而行走nest-C-food的蚂蚁到达food点。如果蚂蚁每经过一点都留下大小为1的信息素，这时nest-B-food路线的第一点聚集2点，而nest-C-food路线的第一点聚集1点。在行走28个单位时间后，这两点的信息素变化分别为4和2，比值为2:1，nest-C-food路线的蚂蚁返回nest点。 如果按比值的比例，一群决定nest-B-food路线派两个蚂蚁，而nest-C-food路线上派一个蚂蚁。在每个蚂蚁再各行走28个单位时间后，nest-B-food和nest-C-food路线的第一个点各累计12和4，比值为3:1。如果再按比值分配蚂蚁数量，则nest-B-food路线分配三只蚂蚁，而nest-C-food路线分配一只蚂蚁。按原有的模式重复28个单位时间，nest-B-food和nest-C-food路线的第一点信息素各积累24和6，比值为4:1。如此重复下去，可以发现nest-B-food和nest-C-food路线的第一点信息素的比值会越来越大，最后的极限是所有的蚂蚁只选择nest-B-food路线。 图2.1:蚂蚁寻物过程的简化图为了更好的描述蚁群算法，下面所有的符号和算法设计以TSP为基础，其它应用可以据此进行改进。令为n为搜索空间中第i只蚂蚁的位置。假设表示第i只蚂蚁可以去的所有位置的集合。等式(2.1)给出了第i只蚂蚁向第j个位置移动的概率函数，并且位置与位置之间的信息素的值越大、先验值的值越大选择路径i-j的概率越大，其中为,这里是由位置移动到位置的耗费，通常由目标函数决定，它可以是两点间的距离或花费的费用。等式中的,是两个系数，分别为残留信息素和转移耗费的相对重要程度。 (2.1)下一个位置可以根据的最大值来选择或是用轮盘赌来随机的选择下一个位置。当一个蚂蚁走完了所选的路径，则按式(2.2)更新信息素值。在每一次循环结束后，每条路径上的信息数值都按(2.3)式进行更新，其中是全局信息素挥发系数,。 （2.2） （2.3）2.2.2 蚁群算法基本步骤以TSP为例，基本蚁群算法的具体实现步骤如下：(1)参数初始化。令时间t=0和循环次数Nc=0，设置最大循环次数Ncmax, 将m个蚂蚁置于n个元素(城市)上，令有向图上每条边(i, j)的初始化信息量ij(t)=const, 其中const表示常数，且初始时刻ij(0)=0 (2)循环次数Nc Nc+1。 (3)蚂蚁的禁忌表索引号k=1。 (4)蚂蚁数目 kk+1 。 (5)蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市) j 并前进，jC - tabuk。 (6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。 (7)若集合C中元素(城市)未遍历完，即k<m，则跳转到第(4)步，否则执行第(8)步。 (8)根据公式(2.2)和式(2.3)更新每条路径上的信息量。 (9)若满足结束条件，即如果循环次数Nc Ncmax 则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。2.2.3蚁群算法流程图输出程序计算结果按式（2）和式（3）进行信息量更新修改禁忌表按式（1）选择下一元素蚂蚁k=1循环次数Nc Nc+1初始化开始结束Km满足结束条件蚂蚁k=k+1NYYN 图2.2 基本蚁群算法程序流程图2.2.4复杂度分析对于TSP，所有可行的路径共有(n-1)!/2条，以此路径比较为基本操作，则需要(n-1)!/2-1次基本操作才能保证得到绝对最优解。若1M FLOPS，当n=10, 需要0.19秒n=20, 需要1929年n=30, 需要1.4X10e17年2.3. 基本人工免疫算法2.3.1 一般免疫算法的理论思想 生物免疫系统(Biological Immune System)是一种高度并行的、分布式的自适应系统，它是脊椎动物体内能够识别和排除抗原性异物，保护机体免受损害以及维持机体内部环境稳定的极为复杂的生物学系统。在免疫系统中，外来的细菌、病毒(dangerous foreign bacteria，viruses，etc)等“非己，物质称为抗原，负责识别和清除抗原的是抗体。抗体与抗原的匹配程度用亲合力(affinity)表示。当亲合力超过某一闭值时，即表示抗体与抗原匹配成功，免疫应答(immune response)过程被启动。此时，与外来抗原匹配的免疫细胞(B细胞)被激活(activation)并大量增生(Proliferation)，分泌出抗体，这些抗体与抗原结合将抗原消灭。那些能够参与免疫应答的细胞，会被记忆下来而长期保存在免疫系统中，当相同或相似的抗原再次入侵机体时(Previously)，免疫系统会产生所谓的“二次应答”，能更快、更准确、更有效地消除抗原。所以，生物免疫系统具有学习、记忆及联想(associative retrieval)的功能。从信息处理的观点看(From an information-processing perspective)，免疫系统是与遗传系统、神经系统并存的人体三大信息系统之一，它具有如下的功能:模式识别能力，并行信息处理能力，学习能力，记忆与联想能力，自适应能力，自组织自调整能力以及抗体的多样性保持能力。正是因为免疫系统所具有的这些优良特性，引发了工程领域内众多研究人员对免疫系统极大的研究兴趣。研究者们根据问题的需要，从生物免疫系统中抽取若干个特性，建立了很多人工免疫系统(Artificial Immune System-AIS)和人工免疫算法(Artificial Immune Algorithm-AIA)，以解决复杂的工程实际问题。目前，在AIS和AIA中，主要采用了三种生物学免疫原理，即:免疫网络理论，反向选择机制以及克隆选择原理。免疫系统是高等脊椎动物体内能够识别和排除抗原性异物，保护机体免受损害及维持内环境稳定的极为复杂的生物学系统。抗原性异物即是所谓“非己”物质，称为抗原，不管是曾经遇到过的“非己”物质，还是未曾遇到过的“非己”物质，免疫系统均能识别并将其清除，很少错把“非己”当作“自己”，或把“自己”当作“非己”。在免疫系统中，负责识别和清除抗原的是抗体，免疫系统的强大的识别能力，即来源于抗体的多样性。阐明免疫系统抗体多样性产生机理的，是奥地利免疫学家伯内特(N.K.Burnet)于1957年提出的细胞克隆选择学说。这个学说认为免疫系统在胚胎期由于遗传和免疫细胞在增殖中发生基因突变，形成了免疫细胞的多样性。这些细胞不断增殖形成无性繁殖系。细胞的无性繁殖系称作克隆。有机体内免疫细胞的多样性能达到这种程度，以至于当每一种抗原侵入机体都能在机体内选择出能识别和消灭相应抗原的免疫细胞，使之激活、分化和增殖，进行免疫应答以最终清除抗原。当病原体被清除后，免疫系统中就只存在抗体而不存在抗原了，或者抗原存在但浓度很低，这种(或多种)与病原体匹配并参与清除抗原的抗体在免疫系统中大量存在，浓度较高，免疫系统这时处于一种失衡状态，它如何回复到平衡状态呢?N.K.Jerne等人提出的独特型(idiotypic)网络学说回答了这个问题。这个学说主要基于这样的概念，即淋巴细胞并不是彼此孤立的，相反，不同种类的淋巴细胞间通过抗体的相互作用而交换信息并相互作用，共同完成免疫系统的功能。这一免疫网络学说认为，抗体不但具有与抗原的抗原决定基(epitope)相结合的抗体结合部位(paratope)，而且具有自己的特定的抗原决定基(idiotope)。具有这种特定的抗原决定基的抗体作为一种特殊的抗原与别的抗体相结合，亦即被抗原激励的抗体反过来可以激励别的抗体。当某种抗体的浓度达到一个给定闭值时，它就起到了某种抗原的作用而对别的能与之相匹配的抗体产生激励作用，同时，它也被别的抗体抑制，从而导致其浓度的下降，直到免疫系统回复到平衡状态。这就产生了所谓的免疫网络。免疫识别是免疫系统的主要功能，识别的本质是区分“自我”和“非我”。免疫识别具有两个层次上的涵义。一层涵义的识别是对入侵抗原的识别，主要是通过淋巴细胞上的抗原识别受体与抗原的结合来实现的，二者结合的强度称为亲合度。另一层涵义的识别发生在胸腺中T细胞成熟的过程，是生物免疫系统免疫耐受行为的根源所在。免疫系统对外界入侵抗原的识别依靠T细胞表面的受体进行检测，而在T细胞的产生过程中，受体通过伪随机基因重组过程来形成。基因重组形成的未成熟T细胞在胸腺中首先要经历一个审查环节，只有那些不能与生物体自身蛋白细胞组织(自我)发生免疫应答的T细胞才可以离开胸腺，执行免疫应答的任务;而那些对自身蛋白产生免疫应答的未成熟T细胞则被就地破坏掉，从而防止对生物体自身造成错误攻击。也就是说，经历阴性选择后的存留下来的成熟T细胞都对抗原具有亲和力，可形成免疫识别;而对自体蛋白质不具备亲和力，可形成免疫耐受。T细胞成熟过程中经历的选择过程称为阴性选择(Negative Selection)，亦称反向选择，基于阴性选择的个体识别方法称为免疫系统的自我-非自我识别原理，它也是免疫识别的一种主要方式。2.3.2 人工免疫算法 近年来，国内外己提出并发展了一些免疫算法，不同免疫算法的分析和比较主要从以下两方面进行研究:1)自然免疫系统的免疫学理论和方法;2)计算机算法的分析量度。主要免疫学说有反向选择原理、进化学说、克隆选择理论、疫苗学说和免疫网络理论等。根据这些不同的免疫学说提出以下5种不同的免疫算法: 1、反向选择算法 免疫系统中的T细胞在胸腺中发育，与自身蛋白质发生反应的未成熟T细胞被破坏掉，所以成熟的T细胞具有忍耐自身的性质，不对自身蛋白质发生反应，只对外来蛋白质产生反应，以此来识别自己与非己，这就是所谓的反向选择原理。 Forrest基于反向选择原理提出了反向选择算法用来异常检测，算法主要包括两个步骤:首先，产生一个检测器集合，其中每一个检测器与被保护的数据不匹配;其次，不断地将集合中的每一个检测器与被保护数据相比较，如果检测器与被保护数据相匹配，则判定数据发生了变化。Forrest用概率分析的方法估计了算法的可靠性与检测集合大小的关系。该算法的显著特点是异常检测时不需要先验知识，具有很强的鲁棒性，其缺点为当被保护的数据变长时，集合中检测器的数量按指数率增加，产生检测器的代价过大。针对这一缺点，Helman提出一种更有效的检测器产生算法，使得集合中检测器的数量随着数据的长度按线性增长。Patrik对反向选择算法进行了理论分析。 2、免疫遗传算法 Chun等提出了一种免疫算法，实质上是改进的遗传算法。根据体细胞和免疫网络理论改进了遗传算法的选择操作，从而保持了群体的多样性，提高算法的全局寻优性能。通过在算法中加入免疫记忆功能，提高了算法的收敛速度。算法中把抗原看作目标函数，抗体看作问题的可行解，抗体与抗原的亲和力看作可行解的适应度。算法中引入了抗体浓度的概念，并用信息嫡来描述，表示群体中相似可行解的多少。算法根据抗体与抗原的亲和力和抗体的浓度进行选择操作，亲和力高且浓度小的抗体选择概率大，这样就抑制了群体中浓度高的抗体，保持了群体的多样性。Chun将免疫算法与进化策略、遗传算法相比较，指出免疫算法的特点与优点。 3、克隆选择算法 Castro提出基于免疫系统的克隆选择理论提出克隆选择算法，该算法是模拟免疫系统学习过程的进化算法。 免疫应答产生抗体是免疫系统的学习过程，抗原被一些与之匹配的B细胞识别，这些B细胞分裂，产生的子B细胞在母细胞的基础上发生变化。以寻求与抗原匹配更好的B细胞。与抗原匹配更好的子B细胞再分裂。如此循环往复，最终找到与抗原完全匹配的B细胞，B细胞变成浆细胞产生抗体，这一过程就是克隆选择过程。克隆选择算法模拟这一过程进行优化。 Castro进一步将免疫网络理论和克隆选择算法相结合，提出了人工免疫网络学习算法用于知识发现，冗余数据挖掘，自动分类，并对算法的参数灵敏度特性进行了分析。 4、基于疫苗的免疫算法 焦李成等提出基于免疫系统的理论提出基于疫苗的免疫算法。该算法中加入免疫算子，以提高算法的收敛速度和防止群体退化。免疫算子包括苗和免疫选择两个部分，前者为了提高适应度，后者为了防止种群退化。理论明这种免疫算法是收敛的，对75城市TSP问题的仿真验证了该算法的有效性。 5、基于免疫网络的免疫算法 Naruaki提出基于主要组织相溶性复合体(MHC)和免疫网络理论自适应优化的免疫算法，用于解决多艾真体中每个艾真体的工作域分配问题要分两步:(1)MHC区别自己和非己，消除智能体中的竞争状态;(2)用免疫网络产生智能体的自适应行为。N-TSP问题的仿真表明，该算法具有自适应能力遗传算法具有更高的搜索效率。 除了以上主要免疫学习算法外，Hunt提出了一种包括骨髓、B细胞网和抗体的免疫学习算法;Ishida提出了基于智能体结构的免疫算法。第三章 系统的设计与实现3.1 人工免疫算法设计3.1.1 人工免疫算法基本步骤（1）问题识别。根据给定的目标函数和约束条件作为算法的抗原。（2）产生抗体群。初始抗体群通常是在解空间用随机的方法产生的，抗体群采用二进制编码来表示。（3）计算抗体适应值。即计算抗原和抗体的亲和度。（4）生成免疫记忆细胞。将适应值较大的抗体作为记忆细胞加以保留。（5）抗体的选择(促进和抑制)。计算当前抗体群中适应值相近的抗体浓度， 浓度高的则减小该个体的选择概率抑制;反之，则增加该个体的选择概率促进，以此保持群体中个体的多样性。（6）抗体的演变。进行交叉和变异操作，产生新抗体群。（7）抗体群更新。用记忆细胞中适应值高的个体代替抗体群中适应值低的个体，形成下一代抗体群。（8）终止。一旦算法满足终止条件则结束算法。否则转到（3）重复执行。3.1.2 人工免疫算法流程图 图3.1人工免疫算法基本流程 图3.2 否定选择算法流程图3.1.3人工免疫的相关设计int r=6;/*最长有效位长度*/int flag_r=0;/*用于关闭自适应r值*/int antinum=2048;/*抗体最大个数*/int antitotal=0;/*抗体是否足够*/int antileng=48;/*每次检查的抗体长度*/开始通过递归算法生成检测器：调用函数selectiona_rcb(char *anti,int n,float rone)antitotal=antinum Y Nn>=antileng Y