test.txt

另外一个中文分词程序

   TSP问题的免疫遗传算法
 开题报告
 
                 班级：计0202    姓名：皇甫大鹏
                 指导教师 ：李淑琴    
一、综述
1、研究意义   
 遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。
免疫系统可分为先天性免疫系统和适应性免疫系统。先天性免疫系统是生物在种系发育和进化过程中逐渐建立起来的一系列天然防御功能，其特点是与生俱有，能传给下一代，无特异性，对各种病原体都有一定的防御功能。适应性免疫系统则是在个体生命过程中慢慢建立起来的，当免疫系统与某种病原体产生免疫初次响应之后，能记住该病原体，当再次遇到它时，会产生免疫再次响应，迅速而有效地消除该病原体。
免疫算法作为一种新的信息处理方法，与神经网络和遗传算法相比，它的研究与应用还处在起步阶段。深入分析和研究免疫识别、学习和记忆免疫调节等机制，形成既有生物依据又有工程应用价值的免疫模型和算法，对于研究新一代计算智能及应用都是十分有意义的。
免疫算法和免疫遗传算法主要是利用免疫系统的多样性产生和维持机制，来保持群体的多样性，从而克服一般寻优过程尤其是多峰值函数中最难应付地“早熟”问题，最终求得问题的全局最优解；免疫规划除利用免疫多样特性之外，还引入了疫苗接种机制，即利用先验知识来引导寻优过程，进一步提高算法的快速性和有效性；否定选择算法是源于免疫系统的抗原识别机制而设计的针对计算机安全保护问题的一种算法，是当前解决计算机安全保护问题的一个值得推广的新思路。
2、研究现状
     免疫系统正在进行的研究已跨越了生物学和医学的疆域，引向一个新的领域----具备免疫特征和功能的人工生命系统。除了上述研究之外，基于免疫网络理论设计自治式多Agent系统、免疫型自适应系统，免疫型安全系统或抗干扰系统等研究，可望不久的将来得到实际的应用。
3、已有成果
基于人工免疫系统的函数优化问题研究、基于Multiagent独特型人工免疫网络、免疫原理在入侵检测系统中的应用研究、基于克隆选择计算的入侵检测方法研究、基于免疫克隆计算的Multi-Agent组播路由算法、基于克隆智能体自学习的入侵检测方法研究、免疫原理在网络入侵检测系统中的应用研究、人工免疫系统理论及免疫克隆优化算法研究、基于危险模式免疫算法的研究 、基于人工免疫系统的入侵检测器生成算法研究等。
二、研究内容     
1、研究方向
   TSP问题的免疫遗传算法:（这里你是在介绍TSP问题，而不是用免疫遗传算法解决TSP问题，再加上几句话，跟下面衔接上！！） 旅行商问题(Traveling Salesman Problem，TSP)是指给定n个城市和两两城市之间的距离，旅行商必须以最短路径访问所有的城市一次，且仅一次，并回到出发地。TSP问题是组合优化问题的代表，属于NP完全问题。

2、研究内容
   编码和适应度函数、交叉与变异算子、免疫算子、仿真研究。
   设有n个城市，并对n个城市编号为1，2，3，? ，n一1，n。则对n个城市的一次遍历即为按访问次序对编号进行的一次编码，定义抗体为遍历城市组成的向量，抗原定义为问题的部分解。抗体和抗体之间的亲和力定义为各组遍历城市的向量中包括的相同城市个数。抗体和抗原的亲和力定义为包含相同城市的路径长度。在特定的形态空间中，随机产生的抗体试图与抗原发生匹配，即尝试解决问题。匹配度高的抗体被认为有可能产生更好的解，被赋予更大的复制概率参与下一次匹配过程。
3、系统功能
编码和适应度函数:对于有n个城市的旅行商问题，从其中的一个城市出发．遍历其余(n-1)个城市且每个城市只去一次的路径有(n!／2n)？？？条。对这n个城市编号，其号码分别为1，2，3,? ,n，并且把商人所在城市即出发城市编为第1号．其它城市可随意编号？？。把这n个城市的编号任意排列成一个长度为 ？？的字符串都可以形成一个抗体。因此抗体空间包含n!个抗体。而解空间只包含(n!/2n)个可行解。这 n!个抗体只代表（n!/2n）个可行解。因此人工免疫算法要在抗体空间中搜索到与抗原相匹配的抗体．比在解空间中搜索到最优解更难。为了缩小抗体空间，提高搜索效率，本文提出的TSP问题抗体编码方式将每个抗体(字符串)的第一个字符固定为出发城市的编号1。这样，每个抗体只有(n-1)个字符可任意排列，抗体空间就只包含(n-1）!个抗体。
交叉与变异算子:交叉是有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而重组,变异是细胞进行复制时可能以很小的概率产生某些复制差错.
免疫算子: 免疫算子由接种疫苗和免疫选择两部分操作构成的.每次遗传操作后,随机抽取一些个体注射疫苗,然后进行免疫监测,即对接种了疫苗的个体进行检测:若适应度提高,则继续;否则,说明变异的过程出现了严重的退化现象,这时该个体将被父代中所对应的个体所取代.
仿真研究:在基本参数保持不变的前提下,对通用遗传算法和免疫算法进行比较,若群体的最佳适应度值在连续100次迭代中保持不变则认为结束搜索.
三、实现方法及预期目标
1、实施的初步方案
免疫规划流程如图所示：免疫规划算法实现的基本步骤：
（1）	随机产生初始父代种群A1。
（2）	根据先验知识抽取疫苗。
（3）	若当前种群中包含了最佳个体，则，结束算法；否则进行以下步骤。
（4）	对当前第K代父代种群A进行交叉操作，得到种群B1。
（5）	对种群B1进行变异操作，达到种群C1。
（6）	对种群C1进行接种疫苗操作，得到种群D1。
（7）	对种群D1进行疫苗选择操作，得到新一代父代种群A2，返回步骤3。

 
2、重点：免疫遗传算子
（1）接种疫苗：对于个体x，对它接种疫苗是指按照先验知识来修改其某些基因位上的基因，使所得个体以较大的概率具有更高的适应度。
     其一，若个体y的每一个基因位上的信息都是错误的，即每一位码都与最佳个体不同，则对任一个体x，x转移到y的概率为0。
     其二，若个体x的每一个基因位都是正确的，则x已是最佳个体，则x以概率为1转移为x。
（2）免疫选择：该操作分两步完成。第一步是免疫检测，即对接种了疫苗的个体进行检测，若其适应度仍不如父代，说明在交叉、变异的过程中出现了严重的退化现象。第二步是退火选择。
3、难点
     编码和仿真研究
4、环境
    VC++ 6.0

四、对进度的具体安排

进



度



安



排	周     次	内        容
	
第1、2周

第3，4周

第5，6周

第7，8周

第9、12周

第13、14周

第15、16周
	
搜集资料，消化

写开题报告 ，进行外文资料翻译

制定解决问题方案，熟悉相关的软件工具
	
完成算法设计
算法调试、实现
                      
撰写毕业论文

修改论文，准备答辩

五、参考文献
1.	王曙霞.葛东媛. 一种TSP求解的人工免疫遗传算法.湖北: 武汉大学计算机学院
2.	刘克胜.曹先彬.郑浩然.基于免疫算法的TSP问题求解.合肥:中国科学技术大学计算机系
3.	魏平.李利杰 .熊伟清.求解TSP问题的一种混合遗传算法.宁波:宁波大学科学与技术学院
4.	王凌 .智能优化算法及其应用,北京:清华大学出版社.2004
5.	王小平.曹立明.遗传算法-理论应用与软件实现.西安:西安交通大学出版社
6.	陈国良．王喷法．庄填泉等．遗传算法及其应用．北京：人民邮电出版社．1996
7.	吴敏毓．刘恭谨医学免疫学.合肥： 中国科学技术大学出版社．1995
8.	张显俊.免疫遗传算法及应用_硕士学位论文.合肥：中国科科学技术大学,1998
9.	刘克胜，曹先彬，郑浩然,等． 基于免疫算法的TSP问题求解［Ｊ］． 计算机工程，2000;26(1): 1-2,16．














指导教师：（签署意见并签字）                                年   月   日 
                                      
督导教师：（签署意见并签字）                                   年   月   日                                     

                      
领导小组审查意见：               
                                      审查人签字：         年  月   日

意见：
1．	红笔的地方时有疑问的，你再确定一下是否正确。
2．	再好好排排版。
3．	参照放假前发给你的任务书中的要求，增加些预计实现的目标内容。