蚁群算法模拟系统设计与实现

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 月江苏大学 2010 届毕业设计（论文）I蚁群算法模拟系统的设计与实现专业班级：J 计算机 0601 学生姓名：汤琪 指导教师：蔡涛 职称：副教授摘要： 人工免疫算法具有快速随机的全局搜索能力，但对于系统中的反馈信息利用不足，往往做大量无为的冗余迭代，求解效率低。蚁群算法具有分布式并行全局搜索能力，但初始解随机，易早熟且求解速度慢。本文提出免疫算法和蚁群算法的混合算法免疫蚁群算法，通过信息素更新获得全局最佳解。通过匹配检测仿真实验，结果证明该算法是计算精度较好的一种算法。本设计是在 Linux 环境下，用 C 语言编写的。Linux 是一类 Unix 计算机操作系统的统称。Linux 操作系统的内核的名字也是“ Linux”。Linux 操作系统也是自由软件和开放源代码发展中最著名的例子。严格来讲，Linux 这个词本身只表示 Linux 内核，但在实际上人们已经习惯了用 Linux来形容整个基于 Linux 内核，并且使用 GNU 工程各种工具和数据库的操作系统。Linux 得名于计算机业余爱好者 Linus Torvalds。 关键词：人工免疫算法 蚁群算法 匹配检测 Linux英文摘要IIAnt Colony Simulation System Design and ImplementationAbstract Artificial 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 kernels 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 Words Artificial immune algorithm ant colony algorithm matching test Linux英文摘要1目 录中文摘要 .IABSTRACT.II目 录 .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英文摘要2第四章 运行 .234.1 各运行命令 .234.2 检测器的添加 .244.3 整体检测 .244.4 随机选取检测器检测 .244.5 蚁群算法选取检测器检测 .25第五章 总结 .27致 谢 .28参考文献 .29英文摘要3第一章 引言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)是模仿生物免疫系统的免疫应答、免疫调节等机理，构造出的一类高性能、自组织、鲁棒性好的人工智能系统。目英文摘要4前，人工免疫系统的研究己经受到学者们越来越广泛的关注，人工免疫算法也在实际工程应用中得到了推广。人工免疫成为继神经网络、模糊逻辑和进化计算后人工智能领域又一研究热点。免疫系统是一种复杂的分布式信息处理学习系统，这种系统具有免疫防护、免疫耐受、免疫记忆、免疫监视功能，这些功能和特点给予研究人员较多的灵感，促成许多学者建立了基于免疫机理的智能方法，解决大量的非线性科学问题。本文将人工免疫算法与蚁群算法混合产生新的算法免疫蚁群算法(Artificial Immune Ant Colony Algorithm，简称 AIACA)，并将该算法应用于匹配检测，计算机仿真结果证明该算法是计算精度都较好的一种算法。1.2. 本课题的开发意义本课题通过蚁群优化算法改进人工免疫算法，主要改进人工免疫算法中通过抗体与抗原之间的亲和力以及抗体与抗体之间的排斥力来选择抗体的方法。采用人工免疫算法生成信息素分布，利用蚁群算法求优化解，优势互补，在收敛速度和寻优能力两方面较原有算法都有明显改善。英文摘要5第二章 关键技术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 得以迅速普及。英文摘要62.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 表示建立目