当前位置：文档之家 › 免疫遗传算法的研究及其在TSP中的应用

免疫遗传算法的研究及其在TSP中的应用

  • 格式：pdf
  • 大小：368.19 KB
  • 文档页数：12

http://www.paper.edu.cn

- 1 -免疫遗传算法的研究及其在TSP中的应用

刘旭旺，齐微

辽宁工程技术大学理学院，辽宁阜新（123000）

E-mail：liuxuwang007@163.com，qiwei1119@163.com

摘 要：本文针对遗传算法（GA）在优化计算中存在的某些缺陷，并影响着一些问题求解

中的正确性和有效性的现实问题，将生物免疫算法与遗传算法相结合，提出了一种免疫遗传

算法（IGA）。这种方法在一定程度上避免了遗传算法易出现早熟、搜索效率低及不能很好

的保持个体多样性等问题。实验结果表明，免疫遗传算法可有效改善基本遗传算法未成熟收

敛、收敛速度慢等缺陷，提高了全局搜索的效率及能力，在TSP求解中取得了满意的结果。

关键词：遗传算法，免疫遗传算法，优化，TSP

1．引言

传统的遗传算法虽然自成体系且使用广泛，但是依然有许多不足，例如对于局部空间的

搜索问题不是很有效，个体的多样性减少的很快等，这些缺陷的存在限制了遗传算法的应用。

而近年来在生物学领域的研究发现免疫原理对改进和提高遗传算法的性能具有重要的启迪

作用，免疫行为可以很好的保持多样性，防止早熟收敛。但是目前对于免疫遗传算法还是不

太完善，所以研究这个课题很有意义。

2．预备知识

2.1 遗传算法

遗传算法（以及普遍意义上的进化算法）出现在20世纪60年代早期，并在计算机科学

的确定性和非确定性算法之间占据了一席之位。本质上，遗传算法具有希望的确定性，意味

着用户可以决定重复次数和结束条件。

由于遗传算法自身存在许多难以解决的问题（如早熟收敛、随机漫游、控制参数的选择

等），而这些问题的存在，给遗传算法的实际应用带来了极大的不便。因此，研究如何解决

这些问题，提高优化效率，对于遗传算法的实际应用十分必要。为此，需要从遗传算法的机

理开始研究。

利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制或者十

进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算

每一个解的目标函数值，也就是编码的适应度。接着就象自然界中一样，利用选择机制从编

码组中按某种规律挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能

够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过

程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑

选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样

通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足

为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。

2.2 遗传算法的基本操作

遗传操作包含三个基本遗传算子（genetic operator）：复制，交换，突变，这三个算子有

如下特点：

① 三个遗传算子的操作都是在随机扰动情况下进行，换句话说，遗传操作是随机操作，http://www.paper.edu.cn

- 2 -因此群体中个体向最优解迁移的规则是随机的。

② 遗传操作效果和上述三个遗传算子所取操作概率、编码方式、群体大小、初始群体

以及适应度函数设定，都有密切关系。

三个基本遗传算子的操作方法或操作策略具体求解问题不同而异，更具体的讲是与个体

的编码方式直接相关。下面对这三个遗传算子进行具体的说明[1]

。

（1）复制

复制是遗传算法的基本算子，对当前群体实施复制操作的意图是使适应度高的优良个体

尽可能地在下一代新群体中得以繁殖，体现“适者生存”的自然选择，同时还要使新一代群体

中的个体数量与原来群体相同。

但是，单纯地按照适应度大小来实行复制，虽然保存了眼下的优良个体，却不一定有利

于发现更好的个体，因为存在着这样的情况，最优解可能在某个劣解附近。丢掉了劣解却不

利于实施其他遗传操作去寻找最优解。所以，在遗传算法中，并不是简单地利用适应度的大

小来选择被复制的个体，而是采用一种随机抽样的方法来选择复制对象。为了能体现出“适

者生存”的原则，这个随机抽样应该保证适应度高的个体被抽到的机会大于适应度低的个体。

J.Holland设计了一种满足适应者生存原则的随机抽样方案，即采用一种轮盘方式来选择复

制对象，轮盘选择法就是一最常用的，同时也是最基本的重要的轮盘方式[2]

。

（2）交换

复制算子每次仅作用在一个个体上，而交换算子每次作用在从群体中随机选取的两个个

体上。通过两个个体的交换可以产生两个新的个体，称为子代。通常子代与父代不同，但却

包含着两个父代的遗传信息。

在群体中实施交换操作时要解决两个问题，一是确定有多少个体需要进行交换操作，称

群体中执行交换的个体数目与群体中个体总数之比为交换概率，记为

cP，一般取

cP为

8.0~5.0.另一个是确定字符串（个体）中交换点的位置。

设群体中个体数目总数为n，交换概率为

cP. 当确定了实行交换的个体数目

cPn⋅后，

可采用轮盘选择法，从群体中随机地选取被交换的个体实行交换操作。

交换点的选择也是随机的，交换分为单点交换、两点交换和多点交换几种方式。

①单点交换。假设个体表示的字符串长为L，x 和y为两个个体，其字符串分别表示

为

}}}{{{⎪

⎭⎪

⎬⎫

∈∈∈Ljibabbbyaaax

jiLL

,,2,1,,1,0,1,0::

2121

ΛΛΛ

（1）

首先在1到1−L的整数集上按均匀分布产生一个随机数i，然后将两个需要交换的字符串x

和y从第1+i到L段内字符相互交换，交换作用的结果是产生两个新的字符串

LiiibbbaaaxΛΛ

2121:'

++；

LiiiaaabbbyΛΛ

2121:'

++.

② 两点交换。假设需要交换的个体如式（1），首先在整数1到L中按均匀分布产生两

个整数i和j，然后对两个字符串从第i位到第j位的所有字符进行交换，结果为

LjjjiiiaaabbbaaaxΛΛΛ

211121:'

+++−； http://www.paper.edu.cn

- 3 -LjjjiiibbbaaabbbyΛΛΛ

211121:'

+++−.

不难看出，当ji=时，交换的只有一个字符。如果产生的随机整数是1和L，则两个字符

串整体互换，等于没有交换。所以这样的随机数可以认为无效，再重新产生。

通常，当字符串长度较短时，采用单点交换，字符串较长时则采用两点交换方式。如果

字符串非常长时，还可以进行多点交换，即对字符串实行多段交换。

（3）突变

突变是对个体中某一位字符进行运算，一种是补运算，即把0变为1，或把1变为0，

进而产生一个新的个体。还有一种是，当字符选定后，不论该字符原来是什么，按5.0的概

率随机产生一个0或1代替原字符。

执行突变的方式有很多种，这里介绍两种常用的方法。

① 字符决定法。在字符决定法中，执行突变的个体及位置是由字符决定的。

设群体有n个长度为L的个体，则群体字符总数为Ln⋅.首先确定一个突变概率

mP，在

遗传算法中

mP都很小，一般为01.0~001.0。然后，针对Ln⋅个字符中的每一个字符在[]

1,0

之间按均匀分布产生一个三位有效的随机数),,2,1(nLk

kΛ=α

，如果

mkP

，则对该字

符实行突变操作（当然，也就是对该字符所在的个体进行突变）。

实行突变的字符（个体及位置）确定后，实行突变有两种方式，一种是补运算，即原字

符是1则改为0，原来字符是0则改为1。另一种是将该字符按5.0概率随机产生0或1。

容易看出，对于第一种方法，突变后的新个体不同于原个体，而对于第二种方法（假设

个体字符串中仅有一个字符实行突变），新个体有50%的可能性与原个体相同，也就是说只

有50%的可能发生突变。

② 个体决定法。首先给定一个概率

mP，按此概率在群体中随机选出突变的个体。对于

每一个被选种的个体，在个体字长范围内按均匀分布随机选出突变的字符，再按照补运算或

者随机变化对该字符实施操作。

虽然在遗传算法中突变和交换都能产生新个体，但交换的作用更重要，因此交换概率

cP

远比突变概率

mP大得多。

2.3 免疫优化理论

免疫优化的理论基础主要是免疫遗传学——免疫学（Immunology）和遗传学（Genetics）

的边缘学科。免疫遗传学的研究说明了免疫物质不仅受遗传基因控制，而且由此发生的免疫

功能（免疫应答）也同样受到遗传调控。

根据相关的免疫学、生物学和遗传学等理论，免疫优化的理论要点可以归纳如下：

（1）免疫过程中基因会任意重组——这不同于SGA的交叉算子设计方法，交叉算子容

易引起父代与子代之间的相似，而重组算子则有利于增加种群中个体的多样性；

（2）免疫响应启动后，B细胞会大量生成，其变异机制也有助于增加个体的多样性；

（3）生物体的新陈代谢会排除5%激励值B细胞，代之以从骨髓中生成同样数量的新B

细胞，也有利于多样性的保持；

（4）免疫记忆有助于优良个体和信息的保持。

如上所述，我们可以看到：免疫过程中个体的多样性可以较好地得到维持，因而我们可

以考虑模拟生物体的实际免疫行为设计出一种新的优化算法——免疫遗传算法（IGA，http://www.paper.edu.cn

- 4 -Immune Genetic Algorithm）[3]

，它较SGA而言将有利于寻优。

3．基于免疫遗传算法的优化设计

3.1 免疫遗传算法及几个基本定义

为了克服遗传算法在实际工程优化计算中出现的早熟收敛问题，以提高遗传算法的全局

搜索能力，将生物免疫机制原理引入到标准遗传算法中，构造成了一种新的改进遗传算法

——免疫遗传算法（Immune Genetic Algorithm 简称为IGA）[4]

。

免疫遗传算法基于生物免疫机制提出的一种改进的遗传算法，它是模拟和反映生物机体

免疫系统的特点，并结合工程优化应用而提出的一种仿生优化算法。它将求解问题的目标函

数对应为入侵生命体的抗原，而问题的解对应为免疫系统产生的抗原，通过抗原和抗体的亲

和力描述可行解与最优解的逼近程度。生物免疫系统对抗原会自动产生相应的抗体来防御，

这一过程被称为免疫应答。在此过程中，部分抗体作为记忆细胞保存下来，当同类抗原再次

侵入时，记忆细胞被激活并产生大量抗体，使再次应答比初次应答更迅速，体现了免疫系统

的记忆功能。同时，抗体与抗体之间也相互促进和抑制，以维持抗体的多样性及免疫平衡，

这种平衡是依浓度机制完成的，即抗体的浓度越高，则越受抑制，反之亦然，体现了免疫系

统的自我调节功能。抗体的浓度计算是系统保持种群多样性的基本手段之一。

假设免疫系统由N个抗体组成（即群体规模为N），每个抗体基因长度为M，采用符号

集大小为S（对二进制编码，2=S，即采用0，1两种字符），如图1.下面介绍几个定义[5]

。

等位基因

1K

2K

iK

图1 免疫细胞等位基因的信息熵

Fig.1 Entropy of information immune body mendelian unit

1） 多样度

为了有效地保持和扩大免疫系统淋巴细胞种群进化个体的多样性，必须要度量和评价个

体之间的差异。显然，差异度量的精细程度，制约了免疫遗传算法个体多样性的水平。这里，

个体之间的差异性由Shannon的平均信息熵)(NH表述，即

∑

==M

jjNH

MNH

1)(1

)( （2）

其中)(NH

合集下载

改进遗传算法解决TSP问题

改进遗传算法解决TSP问题

改进遗传算法解决TSP问题

陈林;潘大志

【摘 要】针对基本遗传算法收敛速度慢，易早熟等问题，提出一种改进的遗传算法。新算法利用贪婪思想产生初始种群来加快寻优速度，用贪婪思想来引导交叉操作，在交叉操作之前，把当前较差的一半种群替换成随机种群，最后用改进的变异算子和进化逆转操作进行寻优，利用新的遗传算法求解基本的旅行商问题。仿真结果表明，改进的遗传算法具有全局搜索能力强、收敛速度快的特点，优化质量和寻优效率都较好。%Aiming at the problem of slow convergence and easy

premature convergence, an improved genetic algorithm is proposed. New

algorithm uses greedy idea to generate the initial population for speeding

up the searching speed and greedy idea to guide the crossover operation,

before the crossover operation, selects the random population to replace

the half of the poor population, finally with the help of the improved

mutation operator and evolutionary reversal operation to realize

optimization, constructs a new genetic algorithm for solving the traveling

salesman problem. The simulation results show that the improved genetic

遗传算法及几个例子

遗传算法及几个例子

遗传算法及几个例子

遗传算法是一种模拟自然选择和遗传机制的优化算法。它是由约翰·霍兰德（John Holland）于1975年首次提出的。遗传算法通过模拟生物的进化过程，利用适者生存的原则来问题的最优解。遗传算法的主要应用领域包括优化问题、机器学习、组合优化、图像处理等。本文将介绍遗传算法的工作原理及几个应用实例。

首先，遗传算法的工作原理是模拟自然界的进化过程。它由三个基本操作组成：选择、交叉和变异。

选择操作是指根据适应度函数选择出优秀个体，将它们作为父代参与下一代的繁衍。适应度函数是用来评估个体在问题空间中的优劣程度的函数。

交叉操作是指将两个父代个体的染色体进行交换，产生子代个体。交叉操作可以通过染色体的交叉点位置进行分类，如一点交叉、多点交叉、均匀交叉等。

变异操作是指对个体的部分基因进行突变，以增加空间的多样性。变异操作在遗传算法中起到"探索"新解的作用。

下面是几个遗传算法的应用实例：

1. 旅行商问题（Traveling Salesman Problem，TSP）

旅行商问题是指在给定的一系列城市中，找到一条路径使得旅行商遍历每个城市且每个城市仅访问一次，最终回到起点城市。遗传算法可以通过优化路径找到满足条件的最短路径。

2.集装箱装载问题 集装箱装载问题是指如何在给定的一系列货物和一些规定的集装箱中，找到一种最佳的装载方案，以使得尽可能多的货物被装载到集装箱中。遗传算法可以通过调整货物装载顺序和集装箱布局等来解决这个问题。

3.入侵检测系统

入侵检测系统（Intrusion Detection System，IDS）用于检测计算机网络中的恶意入侵行为。遗传算法可以通过学习适应网络环境的特征和规则，以准确地识别出正常和异常的网络流量。

4.机器学习中的特征选择和参数优化

在机器学习任务中，特征的选择和参数的优化对于模型性能的提升非常重要。遗传算法可以通过优化特征子集的选择和调整模型参数的取值，来提高机器学习模型的性能。

混合遗传蚁群算法的改进及在TSP问题中的应用研究

混合遗传蚁群算法的改进及在TSP问题中的应用研究

一　

康岚兰－曹文梁：　

Ｋａｎｇ　Ｌａｎｌａｎ　Ｃａｏ　Ｗｅｎｌｉａｎｇ　（１．江西理工大学应用科学学院，江西赣州３４１０００；２．东莞职业技术学院计算机工程系，广东东莞５２３８０８）　

（１．Ｆａｃｕｌｔｙ　ｏｆＡｐｐｌｉｅｄ　Ｓｃｉｅｎｃｅ，ＪｉａｎｇｘｉＵｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，ＪｉａｎｇｘｉＧａｎｚｈｏｕ　３４１０００；２．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ　

Ｅｎｇｉｎｅｅｒｉｎｇ，Ｄｏｎｇｇｕａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ，Ｇｕａｎｇｄｏｎｇ　Ｄｏｎｇｇｕａｎ　５２３８０８）　

摘要：蚁群算法（ＡＣＡ）与遗传算法（ＧＡ）都属于仿生型优化算法，是解决组合优化问题的强有力工具，并都分别成功应　

用于旅行商问题（ＴＳＰ）中。本文将两种算法进行融合，并给出了新的融合方式。实验结果表明，新的遗传蚁群混合算法有效地改　

进了算法的全局收敛性，并加快了收敛速度。　关键词：蚁群算法；遗传算法；混合算法；旅行商问题　

中图分类号：ＴＰ３０１　文献标识码：Ａ　文章编号：１６７１－４７９２．（２０１０）７．００１０—０３　

Ａｂｓｔｒａｃｔ：Ａｎｔ　Ｃｏｌｏｎｙ　Ａｌｇｏｒｉｔｈｍ（ＡＣＡ）ａｎｄ　Ｇｅｎｅｒａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ（ＧＡ）ａｒｅ　ｔｗｏ　ｂｉｏｎｉｃ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ｔｈｅｙ　ａｒｅ　ａｌｓｏ　ｔｗｏ　ｐｏｗｅｒｆｕｌ　ａｎｄ　ｅｆｆｅｃｔｉｖｅ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｔｈｅ　ｃｏｍｂｉｎａｔｉｏｎ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ，ｍｏｒｅｏｖｅｒ　ｔｈｅｙ　ａｌｌ　ｗｅｒｅ　ｓｕｃｃｅｓｓｆｕｌｌｙ　ｕｓｅｄ　ｉｎ　ｔｒａｙ－　

ｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ（ＴＳＰ）．Ｔｈｉｓ　ｐａｐｅｒ　ｓｙｎｃｒｅｔｉｚｅｓ　ｔｗｏ　ａｌｇｏｒｉｔｈｍｓ，ｍｅａｎｗｈｉｌｅ，ａ　ｎｅｗ　ｓｙｎｃｒｅｔｉｃ　ｍｅｔｈｏｄ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌ￣　

遗传算法的研究及应用

遗传算法的研究及应用

龙源期刊网

遗传算法的研究及应用

作者：彭志勇 邓世权

来源：《计算机光盘软件与应用》2013年第07期

摘要：遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式，它可以应用与生活中的很多领域。

关键词：遗传算法；函数优化；生产调度；自动控制

中图分类号：TP183文献标识码：A文章编号：1007-9599 (2013) 07-0000-02

遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式。与传统的数学模型进行比较，遗传算法有很多的不同的地方，因为它能够解决很多复杂的问题，而传统的数学模型却没办法做到。

1遗传算法的理论研究

1.1遗传算法的由来。美国密西根大学的霍兰德（Holland）将该算法应用于自然和人工系统的自适应行为的研究之中，并且在二十世纪七十年代中期，出版他的第一部著作《自然与人工系统中的适应》。随后，Holland与他的学生们将该算法进行了大力的推广，并把它应用到优化及机器学习等问题之中，而且正式定名为遗传算法。

1.2遗传算法的发展。遗传算法的兴起于20世纪70年代，而到了20世纪80年代的时候，它正好属于一个发展中的过程，到了20世纪90年代时，它已经发展到了颠疯时刻。为一种实用性较强而又很有效率的优化技术，遗传算法的发展还是非常迅速，在国内外已经造成了非常大的影响力。

1.3遗传算法的基本思想。遗传算法是从一个种群（population）开始的，而这个种群代表问题可能潜在解集的，一个种群是由经过基因（gene）编码（coding）的一定数目的个体（individual）所组成。染色体是遗传物质的主要载体，它是由多个基因的集合，其内部表现是某种基因组合决定的。自从初始种群产生以后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小来挑选（selection）个体，遗传算法是采纳了选择、交叉、变异、迁移、局域与邻域等自然进化模型，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），从而产生出代表新的解集的种群。