基于免疫遗传算法的旅行商问题求解

 2022-01-17 11:01

论文总字数:52717字

目 录

1.引言 1

1.1免疫遗传算法产生的背景和研究的意义 1

1.2免疫算法的发展及其应用 2

1.3旅行商问题的介绍 2

2.免疫遗传算法概述 3

2.1免疫遗传算法的基本原理 3

2.1.1免疫遗传算法的基本描述 3

2.1.2免疫遗传算法的相关概念 3

2.2免疫遗传算法的实现步骤 5

2.3 免疫遗传算法与遗传算法的比较 6

3.利用免疫遗传算法进行函数优化 7

3. 1采用免疫遗传算法求最小值 7

3.1.1问题描述 7

3.1.2求解步骤 7

3.1.3程序运行结果及结果分析 13

3.2各参数对函数优化的影响及分析 14

3.2.1群体规模(N)对函数优化问题的影响 14

3.2.2进化代数(ga)对函数优化问题的影响 15

3.2.3抗体更新数(P)对函数优化问题的影响 16

3.3免疫遗传算法(IGA)与传统遗传算法(GA)的比较结果 17

4.基于免疫遗传算法的旅行商问题求解 17

4.1国内外研究现状 17

4.2基于免疫遗传算法的旅行商问题求解 18

4.2.1旅行商问题的数学模型 18

4.2.2具体问题描述 19

4.3旅行商问题的求解方法 19

4.3.1个体的编码方式及初始种群的生成 19

4.3.2初始参数的写入 19

4.3.3适应度函数的确定 20

4.3.4遗传算子的选择 20

4.3.5交叉算子 21

4.3.6变异算子 21

4.3.7基于免疫遗传算法的筛选 22

4.3.8结果输出 24

4.4程序运行结果 25

4.5参数分析 26

4.5.1种群规模(N)对函数的影响 26

4.5.2迭代次数(ga)对函数的影响 28

4.5.3群体抗体更新数(P)对函数的影响 29

4.6遗传算法和免疫遗传算法的结果对比 29

5.结束语 31

参考文献 32

致谢 33

附 录 34

基于免疫遗传算法的旅行商问题研究

周玉康

, China

Abstract: This paper is mainly based on the immune genetic algorithm to solve the traveling salesman problem. It gives the research background and significance of the project. The common concepts, application fields, basic principles and specific implementation steps of the immune genetic algorithm are also described. Apart from that, it summarizes some problems of traveling salesman problem exists and the research status of immune genetic algorithm in solving the traveling salesman problem. The immune genetic algorithm is applied to solve the problem of the most value of the specific function and analyzes the influence of each parameter on the performance and the results of the optimization. Then use its result to compare with the results obtained by genetic algorithm. This paper design specific steps of using immune algorithm to solve the path planning of logistics. The immune part is added to the genetic algorithm by MATLAB simulation and succeed calculating the optimal path of traveling salesman problem.

Key word: Immune genetic algorithm; Traveling salesman problem; Antibody; Antigen; Affinity

  1. 引言

1.1免疫遗传算法产生的背景和研究的意义

遗传算法(Genetic Algorithm,GA)是人们从生物系统的进化发展过程中学习并总结出的一种算法,它是以达尔文“物竞天择,适者生存”的进化论为理论基础,根据自然界生物的新陈代谢的进化过程,提出一种通过不断的进化寻找最优解的新型算法[1]。遗传算法包括以下几个特点:

  1. 遗传算法从问题的候选解群体进行查找,并非某一个解。这是遗传算法区分于传统优化算法的主要地方。通常情况下,传统的优化算法都是从某一个初始值进行迭代求最优解的,但是容易陷入局部最优解,与传统优化算法相比较之下,遗传算法从多个解即候选解集展开搜索的方式,能够有效降低陷入局部最优的几率。
  2. 遗传算法仅仅使用适应度函数来对个体进行评估,不依赖于搜索空间的其他变量,而且适应度函数的变量取值是随机的,不受连续或可微等条件的约束,因而有着更广大的应用范围。
  3. 遗传算法能够进行自我调节。在利用遗传算法计算时,群体会保留那些适应度值较高的个体,并且能够将父代个体中的优良个体保存下来,使整个群体向着良好的方向进化发展。
  4. 遗传算法具有不确定性特性,它的寻优方法采用的是概率寻优,利用概率寻优来指导搜索方向。

实际上在解决一些问题中,GA与别的优化算法基本是一样有效的;但是GA在解决那些复杂的优化问题上所具有的潜力是普通优化算法难以媲美的。遗传算法目前已经成为解决那些复杂优化问题的主要处理手段,受到了国内外的共同关注。然而就遗传算法本身还是存在着很多的缺陷。

由于遗传算法是一个概率型算法,它的交叉和变异算子都是在一定概率下产生的,随着迭代次数增加,它的随机性也就越大。因此交叉算子和变异算子经过迭代进化会不可避免的发生早熟收敛,种群的多样性也会相应的降低。免疫遗传算法正是针对传统遗传算法可能会发生的早熟收敛而提出的,通过在种群的进化过程中添加了计算抗体浓度,并根据抗体浓度对群体进行更新,从而实现对群体的多样性保持策略,可以有效的防止遗传算法中出现的早熟,从而能够筛选到更好的优化值。

免疫遗传算法是在GA的基础上增加了一个免疫部分,通过免疫部分可以有效的提升种群的多样性,有效解决了GA在求解多峰值优化问题中的早熟问题,加强了算法的全局搜索能力,对于那些搜索空间大、容易出现局部收敛问题的求取全局最优有着很大的帮助。在未来的实际应用中也有着广阔的前景。

1.2免疫算法的相关应用

免疫算法能够对那些复杂的系统优化进行求解,并且不依赖于问题的详细信息,因而被广泛应用于各种领域,其中包括非线性最优、组合优化、控制工程、机器人、故障诊断、病毒检测和图像处理等问题。

  1. 非线性最优化问题:对于那些有多个局部极值的非线性问题,一般的优化方法往往会约束在局部最优解中,对全局最优解很难求到。而基于免疫系统的优化算法则可以有效的避免过早收敛,对于解决那些有多峰值求最优的问题有着很大的帮助。
  2. 组合优化:当问题的群体规模增大时,算法的查找空间也会相应的扩大。目前,计算机经常利用枚举法对问题进行求解,但其结果远远没有免疫算法求的准确。免疫算法对于求解组合优化中的一些NP问题是相当有效的。目前,免疫算法已经在旅行商问题、生产进度安排等方面得到应用。
  3. 控制工程:免疫系统能够应用到处理汽车尾部防撞中,它可以同时处理各个传感器发送来的信号,并能够快速、准确地控制各执行器进行相应动作。除此之外,免疫算法也被运用于神经网络权值优化、动态复杂控制等方面。

1.3旅行商问题的介绍

旅行商问题的英文名为Traveling Salesman Problem,常常被人们简称成TSP。从其字面意思可以理解为一个商人的旅行问题,它描述的是一个商人要到多个城市进行商品推销,它要求商人每个城市只能去一次,并且最后回到起点位置,在这两个约束的基础上要求找出一条最佳路径使商人所走的路径最短。旅行商问题的难度会随着城市数量的增加而提高,这是因为对于n个需要遍历的城市来说,可供选择的路线有种,随着n的增大,搜索全局最佳路径的难度会加深很多。对于TSP问题来说最普遍的解法是用的枚举法,它就是通过不断的产生几组路径,在这些路径中进行搜索最优解,然后把每一代的最优解相互比较,进而挑选出全局最优解;当然如果城市数目很大的话,把所有可能解列出来是不现实的,计算机运行数据的时间过于冗长,不利于在实际中解决问题,所以一般情况下都会设定一定的终止条件,比如运行时间、运行次数等等。

本文主要是利用免疫遗传算法解决TSP的基础上对算法进行了优化。免疫遗传算法将问题的解表示成生物系统中的染色体,通过生物细胞内部的选择、交叉、变异以及基于抗体弄得的群体更新实现了种群的进化,免疫遗传算法在不断迭代过程中求出了问题的最优解,免疫遗传算法一般以迭代次数作为终止条件。除了利用免疫遗传算法解决TSP问题外,模拟退火算法、禁忌搜索算法、蚁群算法等也均被应用到TSP问题的求解中。

  1. 免疫遗传算法概述

2.1免疫遗传算法的基本原理

2.1.1免疫遗传算法的基本介绍

生物的免疫系统是生物抵抗外界有害分子入侵生物体的系统。当外界的危险抗原侵入生物时,系统的免疫细胞会主动识别外来抗原,通过自身的增殖分化来产生多个抗体细胞,从而实现对外来抗原的抑制和消除。生物免疫系统具有识别多种抗原、进行免疫记忆和自我调节的三大显著特性,而免疫遗传算法正是基于这三大特点所提出的;利用其自我调节功能可以使算法减少陷入局部收敛的可能性,大大提高了全局搜索的能力。免疫记忆则能够减少搜索时间,对全局的搜索能力得到很大的提高。而它的多样性保持功能对算法进行局部搜索的性能有着很大的改善。与传统遗传算法相比,这三个方面是免疫遗传算法的三大优势。

免疫遗传算法(Immune Genetic Algorithm,IGA)[2]就是将传统的遗传算法(Genetic Algorithm,GA)和免疫理论(Immune Algorithm,IA)相综合,利用免疫理论解决TSP问题中可能会出现的过早收敛问题。把两者的优点相结合,使免疫遗传算法既囊括了遗传算法良好的搜索性能,又包含了免疫算法的免疫机制,进而解决了TSP问题中的早熟问题,提高了算法的全局搜索能力。

剩余内容已隐藏,请支付后下载全文,论文总字数:52717字

相关图片展示:

您需要先支付 80元 才能查看全部内容!立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找;