第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
免疫遗传算法论文（对算法做了很好解释，很容易写出程序）.pdf
免疫遗传算法及其程序设计
http://www.paper.edu.cn
王登银，童新华
河海大学水利水电工程学院，江苏南京 (210098)
E-mail: wangdengy2005@sina.com
摘 要：鉴于遗传算法局部收敛性能较差等缺点，本文引进免疫记忆库和浓度控制的免疫机
制，即免疫遗传算法，从而提高了算法的收敛效率和局部收敛性能。同时，将该算法通过程
序加以实现，并用 Camel 函数验证了该算法的合理性。
关键词：免疫遗传算法；免疫记忆库；浓度控制；免疫机制
1. 引言
遗传算法是以自然选择和群体遗传理论为基础、模拟生物进化过程中适者生存规则与群
体内部染色体的信息随机交换机制的一类自适应并行概率性全局搜索算法，它主要用来处理
最优化问题和机器学习[1]。该算法是对一个被编码的参数空间进行高效搜索，具有十分顽强
的鲁棒性，可操作性和简单性；并2且只需利用目标函数的取值信息，无需梯度等高价信息，
因而适用于大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数优
化，具有很强的通用性；再者，其良好的并行性，使其具有良好的全局优化性能和稳健性。
多年来，遗传算法已经形成了一套较完善的体系，但还存在一些缺陷，遇到一些难以解
决的问题，如早熟收敛、随机漫游、控制参数的选择等，而这些问题的存在，给遗传算法的
实际应用带来极大的不便。因此，研究如何解决这些问题，提高优化效率，对于遗传算法的
实际应用十分必要。
2. 免疫遗传算法理论提要
免疫优化的常用理论[2]有双官能结构、基因重组、网络作用、混沌增殖、免疫变异、免
疫选择、免疫记忆、免疫记忆、浓度控制、小生境等。本文考虑到前面介绍的遗传算法局部
收敛性能较差的缺陷，引进免疫记忆库和浓度控制的免疫机制，免疫记忆库可以确保群体在
历代进化过程中得到的优良个体不被遗忘和破坏，从而加速算法的收敛效率和提高算法局部
收敛性能，免疫浓度机制可以让个体在一特定的生存环境中进化，预防个体同一化，防止其
过早收敛而陷入“早熟”。下面对免疫记忆库和免疫浓度机制分别予以介绍：
1) 免疫记忆库
抗体记忆机制的引入是免疫遗传算法的一个重要特点，系统能保留一定规模的求解过程
中的较优抗体，即记忆细胞库。具有高适应度的抗体写入数据库，具体操作：
a. 首次计算，初始群体 N 全部在参数限制范围内随机产生，并将群体中适应度高的
M 个个体存入记忆细胞库；
b. 非首次计算，首先对库中的记忆细胞和经算子操作产生的更新群体 N 按适应度高
低一起排序，然后选择前 N 个个体作为下一代的初始群体，并将适应度最高的 M
个个体写入记忆细胞库，完成对记忆细胞库的更新过程。
2) 免疫浓度机制
当抗体针对抗原有较高的亲和度时，该抗体就增殖，当这个抗体的增殖浓度过高时就被
抑制。这个过程能确保搜索方向的多样性以防局部极大化。
如果以抗体的相似度评价为标准，当群体中的某个抗体占据了相当规模，而又不是最优
- 1 -
http://www.paper.edu.cn
解时，就极易导致过早收敛。为此，当有些抗体的规模达到一定程度后，就要对其进行限制，
以防过早收敛。
涉及的几个名词：结合强度、亲和力、抗体浓度、浓度概率和选择概率，分别介绍如下：
a. 结合强度
一般免疫算法种计算抗体 u 和ｖ之间结合强度的数学工具有：海明空间的海明距离、
Euclidean 形态空间的 Euclidean 距离和 Manhattan 形态空间的 Manhattan 距离。本文采用
Euclidean 距离衡量抗体之间的结合强度，定义为：
H
uv
=
M
−∑
x
i
(
i
1
=
y
i
)2
(1)
式中 M 为抗体长度， ix 、 iy 分别为抗体 u 和 v 的基因。 ix 、 iy 取值：先用科学计算法
a × 表示各基因位数值，但必须保证不同抗体相同基因位数值的 b 统一，然后取其系数 a
10b
作为 ix 、 iy 计算 uvH ，按这样的方法统一数量级之后，解决了当各基因位数值数量级不同
时精度不一致的问题。
b. 亲和力
uvA 是抗体 u 和 v 之间的亲和力，定义为：
A
uv
=
1
H
uv
1
+
(2)
式中 uvH 为抗体 u 和 v 的结合强度，由(1)式算得。 uvH ＝0，ｕ和ｖ的基因完全匹配，
此时 uvA ＝1。
c. 浓度
抗体浓度是指抗体在群体中与其相似抗体所占的比重，即
iC
= 与抗体 相似度大于 的抗体数
i
λ
N
抗体总数
(3)
其中λ为亲和力常数，一般取为 0.9
d. 浓度概率
用式（3）计算抗体浓度，并找出浓度较大的个体，记为个体1，2，……，t，则定义该
1.0λ≤ ≤ ，情况特殊可以取值不在此范围内。
ｔ个个体的浓度概率为：
P
d
=
1 1
⎛
−⎜
N
⎝
t
N
⎞
⎟
⎠
其中1 t N
< < ，其它（N－ｔ）个个体的浓度概率为
2
N t
*
1 1
⎛
+⎜
N
⎝
t
−
P
d
N
=
2
(4)
(5)
⎞
⎟
⎠
e. 选择概率
个体的选择概率P由适应度概率 fP 和浓度概率 dP 两部分组成，即
(6)
式中α为亲和系数，α>0； fP ， dP <1。通过上式可以实现：个体适应度越大，则选择
概率越大；个体浓度越大，则选择概率越小，这样既可保留适应度高的个体，又能确保个体
P
α
f
P
d
P
=
(
1
+ −
)
α
- 2 -
http://www.paper.edu.cn
的多样性，以防早熟收敛。在选定亲和系数α时，如果取值大小，则降低了适应度在遗传
算法选择机制中的作用，不利于进化；反之，若取值太大，则降低了免疫遗传算法中的自我
调节能力，甚至破坏群体中个体的多样性，容易出现早熟收敛现象。
3. 免疫遗传算法程序设计
有了前面诸多分析、归纳、设计等工作的基础，下面着手进行免疫遗传算法（IG A）的
设计,考虑一个 M 维函数的优化问题
,
2
,
z
]
,
Z
))
L
Max F Z
(
(
]
[
[
a b
z z
,
,
∈
=
式中
m
m
1
[
)F Z 对应抗原，自变量
a b
z
目标函数 (
,
∈
m
m
[
]
1,2,
=
L
]
[
m
M
1,2,
= L 对应备选抗体，将自
iX i
变量编码（本文使用浮点编码方式）为遗传算法中的个体 (
1,2,
= L ，这样有
， N 表示算法设定的种群规模，于是在 IGA 意义下，上述优化问
X
X X
m
]
) 0
>
F Z
(
M
N
=
)
z
M
M
M
,
(7)
[
,
i
1
i
(8)
[
1,2,
]
L
M
]
N m
,
=
L
抗 原 识 别
初始群体产生
适应度评价及排序
基于浓度的选择
交叉、变异
群 体 更 新
终止条件
N
Y
结 束
题就转化为：
式中
i
,
L
2
Max F Z Max F X z
(
i M
[
) 0,
>
]
X
,
iN
( ( ))
=
]
a b
,
m
m
[
(
F X
(
，
i
]
) )
i
(
)
im
=
∈
记忆细胞库 M
[
z X
1,2,
M
设计 IGA 涉及的步骤（示意图如图 1）：
- 3 -
图1.免疫遗传算法流程图
Fig.1 Flow chart of immune genetic
algorithm
1) 编码方法：
采用浮点数编码方式，所谓浮点数编码方法，是指个体的每个基因值用某一范围内的一
个浮点数表示，个体的编码长度等于其决策变量的个数。因为这种编码方法使用的是决策变
量的真实值，所以也叫做真值编码方式。
http://www.paper.edu.cn
2) 初始群体：
设初始种群数目为 N，随机产生 N 个初始染色体。 (
为第 i 个染色体，
[
i b
i ba
2 , 分别为第 i 个染色体中 x 与 y 两个基因的取值范围。对于一般函数优化，
1 ,
2
1
随机产生 2 N× 个小于 1 的数 1iβ 和 2iβ ，i=1，2，3，…，N；取初始第 i 个染色体的两个基
因分别为
i x yψ
,
,[
a
]i
]i
)
x
i
y
i
=
=
β
i
1
β
2
i
+
+
b
(
i
1
b
(
2
i
a
−
i
1
a
−
)
2
i
β
×
i
1
)
β
×
i
2
⎫
⎬
⎭
(9)
重复上述过程N次，即可获得初始染色体 1ψ ， 2ψ ，…， Nψ 。
3) 适应度评价：
适应度函数是算法进化的驱动力和唯一依据。改变种群内部结构的操作都是通过适应
值来控制的，其合理性直接关系到算法的优劣。
本文建立基于排序的适应度评价函数,种群按目标值进行排序,适应度仅仅取决于个体在
种群中的序位,而不是实际的目标值。排序方法克服了比例适应度计算的尺度问题,当选择压
力(最佳个体选中的概率与平均选中概率的比值)太小的情况下,导致搜索带迅速变窄而产生
过早收敛,再生范围被局限。
排序选择方法的主要思想是：对群体中的所有个体按目标函数值大小进行升序排列，然
后基于这个排序分配各个个体被选中的概率。排序方法比比例方法表现出更好的鲁棒性，是
一种很好的选择方法。排序方法引入种群均匀尺度,提供了控制选择压力的简单有效方法。
让染色体 1ψ ， 2ψ ，…， Nψ 按个体目标函数值的大小降序排列，使得适应性强的染色体被
选择产生后代的概率更大。Michalewicz 提出了非线性排序的选择概率计算公式：
eval ψ α α −
)
i
1
(1
= × −
(
)
i
(10)
上式中 i 为个体排序序号，α为排序第一的个体的选择概率。
4) 记忆细胞库：
将个体按适应度降序排列，取前M个存于记忆细胞库，完成细胞库更新过程，免疫优
化理论提要已详述。
5) 基于浓度控制的选择算子：
对个体适应度施加免疫浓度调节，个体的选择概率P由适应度概率 fP 和浓度概率 dP 两
部分组成，适应度概率由（5）式算得，浓度概率在免疫理论提要中已详述。比例选择算子
是以各个个体所分配到的概率值作为其能够被遗传到下一代的概率，基于这些概率值用比例
选择（赌盘选择）的方法来产生下一代。该算子是一种随机采样方法,以旋转赌轮N次为基础,
每次旋转都可选择单个个体进入子代种群。
∑
P eval
i
eval
(
ψ
i
(
ψ
i
) /
=
)
N
(11)
i
1
=
比例算子的具体操作过程为：
- 4 -
http://www.paper.edu.cn
i. 计算累积概率 iPs ；
Ps
i
= ∑ ， i=1，2，……N， 0
P
i
Ps = ；
0.0
i
m
1
=
ii. 利用 FORTRAN 库函数 random()从区间(0,1)产生一个随机浮点数γ；
iii. 若γ (∈
iv. 重复(іi)～(iii),从而得到子代种群所需的 N 个染色体。
1iPs − ， iPs ],则 iψ 进入子代种群；
6) 交叉算子：
交叉运算选择算术交叉算子。算术交叉是指由两个个体的线性组合而产生两个新的个
,χ χ 进
，随机选取得两个父代向量 t
a
0.4,0.99
∈
(
)
t
b
体。例如：按杂交概率 cp ，一般建议
cp
行算术交叉，产生的两个新个体如下：
t 1
+
=
a
t 1
+
=
b
t
⎧
χ αχ
⎪
b
⎨
t
χ αχ
⎪⎩
a
(1
+ −
(1
+ −
t
αχ
a
t
αχ
b
)
)
(12)
)0,1 范围内的随机参数，它可以是一个常数，此时所进行的交叉运算称均匀算
式中，α为(
术交叉；它也可以是一个由进化代数所决定的变量，此时所进行的交叉运算称为非均匀算术
交叉。
7) 变异算子：
本文采用均匀变异算子，其操作过程是：首先，依次指定个体编码串中每个基因座为变
异点。然后，对每一个变异点以变异概率 mp 从对应基因值的取值范围内取一随机数来替代
原有基因值。一般建议
假设有一个个体为
mp
X
。
(
)
0.0001,0.1
∈
x x x
x
k
1 2 3
=
′
X
在该点对个体 X 进行均匀变异操作后，可得到一个新的个体
)
U
式中γ为[0，1]范围内符合均匀概率分布的一个随机数。
kx U
′ =
(
U
γ
max
min
min
+
−
x
l
L L ，若 kx 为变异点，其取值范围为[
x
′
k
x x x
1 2 3
=
L L 。
x
l
,U U ，
max
min
]
(13)
8) 群体更新：
将第g步得到的N个个体和第d步记忆的M个个体合并在一起，得到一个含有M+N个个体
的新种群，依据M+N个个体新的适应度对其降序排列，记忆前M个个体存入记忆库，前N个
个体作为下一代进化的初始群体。
9) 终止条件判断：
终止条件设为世代数超过预先设定的值或适应度函数低于某个值就停止跌代。若不满
足终止条件，更新进化代数计算器，t=t+1,返回到e；若满足终止条件，则输出最佳个体，进
程终止。
- 5 -
http://www.paper.edu.cn
4. 程序测试
本文用 FORTRAN 语言编制遗传算法程序，从优化一个简单函数的实例入手，分析该
程序的可行性。
样例函数 Camel 函数 (
yxf
,
)
=
x
1.24
−
2
+
⎛
⎜⎜
⎝
x
4
3
⎞
⎟⎟
⎠
2
x
+
xy
(
+−+
44
2
y
) 2
y
。
该函数的曲面图如图 2 所示。此函数有 6 个局部极小点，其中有两个（-0.0898，0.7126）
和（0.0898，-0.7126）为全局最小点，最小值为-1.031628，自变量的取值范围为-100＜x,y
＜100。
下面我们用免疫遗传算法搜索该函数的近似最小值点，并计算该点的函数值。
设定种群大小 M 为 100，交叉概率
，变异概率
0.005
9.0=cp
mp =
，亲和力常数
8.0=α
(
x y
,
ψ
，
)
=
0.9λ=
(
0.089818, -0.712690
。 当 程 序 运 行 到 11 代 时 获 得 最 佳 个 体 ：
。表 1 列出了模拟世代的种群中最佳个体演变的情况。
)
max
由表 1 可见：算法经过 11 代进化，搜索到的最佳个体是(
Fig.2 Curved face chart of Camel function
图 2 .Camel 函数的曲面图
0.089818, -0.712690 ，其
对应目标函数值等于-1.031628，这与 camel 函数全局最小值-1.031628 及其对应点（0.0898，
-0.7126）保持一致。由此得出：算法加入的记忆细胞库和浓度控制的免疫机制具有良好的
自适应性，免疫机制通过对进化历程中优秀个体的记忆遗传和对种群中相似个体的浓度抑
)
制，这样不仅有利于提高算法的搜索效率，而且可以调节个体之间的差异性，增加群体多样
度，防止超级个体的产生而导致“早熟”现象的发生。由此初步验证本文开发的免疫遗传算法
能够高效率的搜索到全局最小点，算法性能较好。
- 6 -
表 1 .免疫遗传算法模拟世代的种群中最佳个体演变情况
http://www.paper.edu.cn
,x yψ
(
)
7041.983000
0.577176
-0.460303
-1.008898
-1.028502
-1.029062
-1.031439
-1.031619
-1.031627
-1.031628
-1.031628
-1.031628
-1.031628
-1.031628
-1.031628
x
y
0.832665
-0.959936
0.133689
-0.024006
-0.072646
-0.103861
-0.091372
-0.088279
-0.089905
-0.089818
-0.089818
-0.089818
-0.089818
-0.089818
-0.089818
-6.517041
0.863979
0.891990
0.734933
0.695852
0.698522
0.717425
0.712681
0.713099
0.712690
0.712690
0.712690
0.712690
0.712690
0.712690
世代数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5. 结束语
1).本文引进记忆细胞库和浓度控制的免疫机制，克服遗传算法早熟收敛、随机漫游等
缺点，对算法进一步完善，并通过程序加以实现。
2).由于数学函数优化问题不需要专门领域的知识，且能较好地反映算法本身的实际效
能，所以以往工程实例总是从一般简单函数出发验证算法的可行性。 从 Camel 函数优化的
实例中可以看出，本文的免疫遗传算法是一种强大的随机搜索方法，其全局和局部搜索性能
较好。
参考文献
[1] 金菊良,遗传算法在水资源工程中的应用研究[D],四川大学,2000:21.
[2] 莫宏伟. 人工免疫系统原理与应用[M]. 哈尔滨:哈尔滨工业大学出版社.2002.11. No:4～6.
- 7 -
http://www.paper.edu.cn
Immune genetic algorithm and its program realization
College of water Conservancy and Hydropower Engineering, HohaiUniv, Nanjing, Jiangsu
WANG Dengyin, Tong Xinhua
(210098)
Abstract
To overcome the shortcomings of local convergence of genetic algorithm, we proposed the immune
genetic algorithm with introducing immunity mechanism of memory cell storehouse and the density
control , thus improving convergence efficiency and local convergence. Meanwhile, the program
realization for this method and its rationality has been tested by a Camel function.
Key words: immune genetic algorithm, memory cell storehouse, density control, immunity mechanism
作者简介：王登银，男，1983- ，工学硕士，主要从事土石坝等水工岩土方面的研究。
- 8 -
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
