蚁群算法模拟系统的设计与实现_毕业论文(编辑修改稿)

蚁群算法模拟系统的设计与实现_毕业论文(编辑修改稿)内容摘要：

.o为后缀的文件，是编译后的目标文件； .s为后缀的文件，是汇编语言源代码文件； .S为后缀的文件，是经过预编译的 汇编语言源代码文件。 执行过程 虽然我们称 Gcc 是 C 语言的编译器，但使用 gcc 由 C语言源代码文件生成可执行文件的过程不仅仅是编译的过程，而是要经历四个相互关联的步骤∶ 预处理 (也称 预编译 ， Preprocessing)、 编译 (Compilation)、 汇编 (Assembly)和 链接 (Linking)。 命令 gcc 首先调用 cpp 进行预处理，在预处理过程中，对源代码文件中的文件包含(include)、预编译语句 (如 宏 定义 define 等 )进行分析。 接着调用 cc1进行编译，这个阶段根据输入文件生成以 .o 为后缀的目标文件。 汇编过程是针对汇编语言的步骤，调用as进行工作，一般来讲， .S 为后缀的汇编语言源代码文件和汇编、 .s为后缀的汇编语言文件经过预编译和汇编之后都生成以 .o 为后缀的目标文件。 当所有的目标文件都生成之后， gcc 就调用 ld来完成最后的关键性工作，这个阶段就是连接。 在连接阶段，所有江苏大学 2020 届本科毕业论文 8 的目标文件被安排在可执行程序中的恰当的位置，同时，该程序所调用到的库函数也从各自所在的档案库中连到合适的地 方。 基本用法 在使用 Gcc 编译器的时候，我们必须给出一系列必要的调用参数和文件名称。 Gcc编译器的调用参数大约有 100多个，其中多数参数我们可能根本就用不到，这里只介绍其中最基本、最常用的参数。 Gcc 最基本的用法是∶ gcc [options] [filenames] 其中 options 就是编译器所需要的参数， filenames 给出相关的文件名称。 c，只编译，不连接成为可执行文件，编译器只是由输入的 .c 等源代码文件生成 .o为后缀的目标文件，通常用于编译不包含主程序的子程序文件。 o output_filename，确定输出文件的名称为 output_filename，同时这个名称不能和源文件同名。 如果不给出这个选项， gcc 就给出预设的可执行文件。 g，产生符号调试工具 (GNU 的 gdb)所必要的符号资讯，要想对源代码进行调试，我们就必须加入这个选项。 O，对程序进行优化编译、连接，采用这个选项，整个源代码会在编译、连接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、连接的速度就相应地要慢一些。 O2，比 O更好的优化编译、连接 ，当然整个编译、连接过程会更慢。 Idirname，将 dirname 所指出的目录加入到程序头文件目录列表中，是在预编译过程中使用的参数。 C程序中的头文件包含两种情况∶ A)include B)include “ ” 其中， A 类使用尖括号 ( )， B类使用双引号 (“ ” )。 对于 A 类，预处理程序 cpp在系统预设包含文件目录 (如 /usr/include)中搜寻相应的文件，而 B类，预处理程序在目标文件的文件夹内搜索相应文件。 江苏大学 2020 届本科毕业论文 9 . 基本蚁群算法 基本蚁群算法 蚁群优化算法是一种受自然界生物行为启发而产生“自然”算法。 产生于对蚁群行为的研究。 蚁群中的蚂蚁以“信息素” (pheromone)为媒介，间接异步的相互联系。 这是蚁群优化算法的最大特点。 蚂蚁在行动过程中 (寻找食物或寻找回巢的路径 )中，会在他们经过的地方留下一些化学物资，称之为“信息素”。 这些物资能被同一蚁群中后来的蚂蚁感受到并作为一种信号影响后者的行动。 具体表现在后到的蚂蚁选择有这些物资的路径的可能性比选择没有这些物资的路径的可能性大得多。 后到者留下的信息素会对原有的信息素进行加强，并 循环下去。 这样，经过蚂蚁越多的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间内被其他蚂蚁选中的可能性也就越大。 这个过程会一直持续到所有的蚂蚁都走最短的那一条路为止。 通过图 简单的了解蚂蚁的运动过程。 假设一个蚂蚁外出寻找食物，蚂蚁从 nest点出发，行走速度相同，食品在 food 点，蚂蚁可能行走的路线如图。 由于无法预知道路中间的情况，蚂蚁出发时会随机选择 nestBfood 或 nestCfood 中的一条。 假设初始每条路线上分别分配一只蚂蚁，每单位时间走一步。 当行走 7 个单位 时间 后，为图 中上半部分的情形，已经有一个蚂蚁到达 food 点。 当行走 14个单位时间 后，走 nestBfood 的蚂蚁己经回到 A点，而行走 nestCfood 的蚂蚁到达 food 点。 如果蚂蚁每经过一点都留下大小为 1的信息素，这时 nestBfood 路线的第一点聚集 2点，而 nestCfood 路线的第一点聚集 1点。 在行走 28个单位时间后，这两点的信息素变化分别为 4和 2，比值为 2:1， nestCfood 路线的蚂蚁返回 nest 点。 如果按比值的比例，一群决定 nestBfood 路线派两个蚂 蚁，而 nestCfood 路线上派一个蚂蚁。 在每个蚂蚁再各行走 28个单位时间后， nestBfood 和 nestCfood路线的第一个点各累计 12和 4，比值为 3:1。 如果再按比值分配蚂蚁数量，则 nestBfood路线分配三只蚂蚁，而 nestCfood 路线分配一只蚂蚁。 按原有的模式重复 28个单位时间， nestBfood 和 nestCfood 路线的第一点信息素各积累 24 和 6，比值为 4:1。 如此重复下去，可以发现 nestBfood 和 nestCfood 路线的第一点信息素的比值会越来越大， 最后的极限是所有的蚂蚁只选择 nestBfood 路线。 江苏大学 2020 届本科毕业论文 10 图 :蚂蚁寻物过程的简化图 为了更好的描述蚁群算法，下面所有的符号和算法设计以 TSP 为基础，其它应用可以据此进行改进。 令 ),( 1 inidii xxxx  为 n为搜索空间中第 i只蚂蚁的位置。 假设),( 1 sjji xxxis  表示第 i只蚂蚁可以去的所有位置的集合。 等式 ()给出了第 i只蚂蚁向第 j 个位置移动的概率函数， 并且位置 ix 与位置 jx 之间的信息素 ij 的值越大、先验值 ij 的值越大选择路径 ij 的概率越大，其中 ij 为ji xxJ1 ,这里ji xxJ1 是由位置 ix 移动到位置 jx 的耗费，通常由目标函数决定，它可以是两点间的距离或花费的费用。 等式中的α ,β是两个系数，分别为残留信息素和转移耗费的相对重要程度。  sl ililijijxx tttttPji1)]([)]([)]([)]([)( ()下一个位 置可以根据 )(tP ji xx 的最大值来选择或是用轮盘赌来随机的选择下一个位置。 江苏大学 2020 届本科毕业论文 11 当一个蚂蚁走完了所选的路径，则按式 ()更新信息素值。 在每一次循环结束后，每条路径上的信息数值都按 ()式 进行更新，其中是 g 全局信息素挥发系数 , 10  g。 10)。 ()()1()1(   ttt ijijij （ ） )()1()1( tt g   （ ） 蚁群算法基本步骤 以 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)蚂蚁数目 k← k+1。 (5)蚂蚁个体根据状态转移概率公式 (1)计算的概率选择元素 (城市 ) j 并前进， j∈{C tabuk}。 (6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素 (城市 )，并把该元素 (城市 )移动到该蚂蚁个体的禁忌表中。 (7)若集合 C 中元素 (城市 )未遍历完，即 km，则跳转到第 (4)步，否则执行第 (8)步。 (8)根据公式 ()和式 ()更新每条路径上的信息量。 (9)若满足结束条件，即如果循环次数 Nc≥ Ncmax 则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第 (2)步。 蚁群算法流程图 江苏大学 2020 届本科毕业论文 12 图 基本蚁群算法程序流程图 复杂度分析 对于 TSP，所有可行的路径共有 (n1)!/2 条，以此路径比较为基本操作，则需要(n1)!/21次基本操作才能保证得到绝对最优解。 若 1M FLOPS，当 n=10, 需要 秒 n=20, 需要 1929 年 输出程序计算结果 按式（ 2）和式（ 3）进行信息量更新 修改禁忌表 按式（ 1）选择下一元素 蚂蚁 k=1 循环次数 Nc← Nc+1 初始化 开始 结束 K≥m 满足结束条件 蚂蚁 k=k+1 N Y Y N 江苏大学 2020 届本科毕业论文 13 n=30, 需要 年 . 基本人工免疫算法 一般免疫算法的理论思想 生物免疫系统 (Biological Immune System)是一种高度并行的、分布式的自适应系统，它是脊椎动物体内能够识别和排除抗原性异物，保护机体免受损害以及维持机体内部环境稳定的极为复杂的生物学系统。 在免疫系统中，外来的细菌、病毒 (dangerous foreign bacteria， viruses， etc)等“非己’，物质称为抗原，负责识别和清除抗原的是抗体。 抗体与抗原的匹配程度用亲合力 (affinity)表示。 当亲合力超过某一闭值时，即表示抗体与抗原匹配成功，免疫应答 (immune response)过程被启动。 此时，与外来抗原匹配 的免疫细胞 (B 细胞 )被激活 (activation)并大量增生 (Proliferation)，分泌出抗体，这些抗体与抗原结合将抗原消灭。 那些能够参与免疫应答的细胞，会被记忆下来而长期保存在免疫系统中，当相同或相似的抗原再次入侵机体时 (Previously)，免疫系统会产生所谓的“二次应答”，能更快、更准确、更有效地消除抗原。 所以，生物免疫系统具有学习、记忆及联想 (associative retrieval)的功能。 从信息处理的观点看 (From an informationprocessing perspective)，免疫系统是与遗传系统、神经系统并存的人体三大信息系统之一，它具有如下的功能 :模式识别能力，并行信息处理能力，学习能力，记忆与联想能力，自适应能力，自组织自调整能力以及抗体的多样性保持能力。 正是因为免疫系统所具有的这些优良特性，引发了工程领域内众多研究人员对免疫系统极大的研究兴。