-
一种新的改进遗传算法及其性能分析外文翻
译
@
中英文翻译
@
外文文献翻译
摘要：
虽然遗传算法以其全局搜索、
并行计算、
更好的健壮性以及在进化过程中不需要
求导而著称，但是它仍然有一
定的缺陷，
比如收敛速度慢。本文根据几个基本定理，提出了
一
种使用变异染色体长度和交叉变异概率的改进遗传算法，
它的主要思想是：
在进化的开始
阶段，
我们使用短一些的变异染色体长
度和高一些的交叉变异概率来解决，
在全局最优解附
近，
使用长一些的变异染色体长度和低一些的交叉变异概率。
最后，
一些关键功能的测试表
明，
我们的解决方案可
以显著提高遗传算法的收敛速度，
其综合性能优于只保留最佳个体的
遗传算法。
关键字：
编译染色体长度；变异概率；遗传算法；在线离线性能
遗传算
法是一种以自然界进化中的选择和繁殖机制为基础的自适应的搜索技术，
它是由
Holland 1975
年首先提出的。它以其全局搜索、并行计算、
更好的健壮性以及在进化过程
中不需要求导而著称。
然而它也有
一些缺点，
如本地搜索不佳，
过早收敛，
以及收敛速度慢。
近些年，这个问题被广泛地进行了研究。
本文提出了一种使用变异染色体长度和交叉变异概率的改进遗传算法。
< br>一些关键功能的
测试表明，
我们的解决方案可以显著提高
遗传算法的收敛速度，
其综合性能优于只保留最佳
个体的遗传算
法。
在第一部分，提出了我们的新算法。
第二部分，通过几个优化例子，将该算法和只保留
最佳个体的遗传算法进行了效率的
比较。
第三部分，就是所得出的结论。最后，相关定理的
证明过
程可见附录。
1.
算法的描述
1.1
一些定理
< br>在提出我们的算法之前，先给出一个一般性的定理（见附件），如下：我们假设有一
个变量（多变量可以拆分成多个部分，每一部分是一个变量）
x
∈
[ a, b ] , x
∈
R
，二进
制的染色体编码是
1.
定理
1
染色体的最小分辨率是
s =
定理
2
染
色体的第
i
位的权重值是
w
i
=
(
i =
1,2,
…
l
)
定理
3
单点交叉的染色体搜索步骤的数学期望
E
c
(x)
是
E
c
(x) =
P
c
其中<
/p>
P
c
是交叉概率
定理
4
位变
异的染色体搜索步骤的数学期望
E
m
(
x)
是
E
m
( x ) = ( b- a)
P
m
其中
P
m
是变异概率
1.2
算法机制
在进化过程中，我们假设变
量的值域是固定的，交叉的概率是一个常数，所以从定理
1
和
定理
3
我们知道，
较长的染色体长度有
着较少的染色体搜索步骤和较高的分辨率；
反之亦
然。同时，交
叉概率与搜索步骤成正比。由定理
4
，改变染色体的长度不影响
变异的搜索步
骤，而变异概率与搜索步骤也是成正比的。
进化的开始阶段，较短染色体（可以是过短，
否则它不利于种群多样
性）和较高的交叉
和变异概率会增加搜索步骤，
这样可进行更大
的域名搜索，
避免陷入局部最优。
而全局最优
< br>的附近，
较长染色体和较低的交叉和变异概率会减少搜索的步骤，
较长的染色体也提高了变
异分辨率，避免在全局最优解附近徘徊，提高了算法收
敛速度。
最后，
应当指出，染色体长
度的改变不会使个体适应性改变，
因此它不影响选择（轮盘
赌选
择）。
1.3
算法描述
由于基本遗传算法没有在全
局优化时收敛，
而遗传算法保留了当前一代的最佳个体，
我
们的方法采用这项策略。
在进化过程中，
我们跟踪到当代个体平均适应度的累计值。
它被写
成：
X(t) =
(t)
其中
G
是当前进化的一代，
f
avg
是个体的平均适应度。
当累计平均适用性增加到最初个体平均适应度的
k
( k> 1, k
∈
R)
倍，我们将染色体
长度变为其自身的
m
(m
是一个正整数
)
倍，然后减小
交叉和变异的概率，可以提高个体分
辨率、减少搜索步骤以及提高算法收敛速度。算法的
执行步骤如下：
第一步：
初始化群体
，
并计算个体平均适应度
f
avg
0
，
然后设置改变参数的标志
flag
。
flag
设为<
/p>
1.
第二步：在所保留的当代的最佳个体，进行选择、再生、交
叉和变异，并计算当代个体
的累积平均适应度
f
avg
第三步：如果
且
flag = 1
，把染色体的长度增加至自身的
m
倍，减少交
叉和变异概率，并设置
flag
等于
0;
否则继续进化。
第四步：如果满足结束条件，停止；否则转自第二步。
2.
测试和分析
我们采用以下两种方法来
测试我们的方法，和只保留最佳个体的遗传算法进行比
较：
2.1
收敛的分析
在功能测试中，我们进行
了以下政策：轮盘赌选择，单点交叉，位变异。种群的规
模是
60
。
L
是染
色体长度，
P
c
和
P
m
分别是交叉概率和变异概率。
我们随机选择
4
个遗传算法
所保留的最
佳个体来与我们的方法进行比较，
它们具有不同的固定染色体长度和交叉和变异
的概率。表
1
给出了在
100
次测试的平均收敛代。
在我们的方法中，我们采取的初始参数是
l
0
=
10
，
P
c0
=
0.3
，
P
m0
= 0.1
和
k = 1.2
，当满
足改变参数的条件时，我们调整参数
l
= 30
，
P
c
=
0.1
，
P
m
= 0.01
。
从表
1
中得知，我们的方法显著提高了遗传算法的收敛速度，正符合上述分析。
表
1
功能测试结果
方法
f1
f2
我们的算法
257
198
l=10
P
c=0.1,
P
m=0.1
15236
26973
l=10
P
c=0.1,
P
m=0.1
35791
42374
l=30
P
c=0.1,
P
m=0.1
1626
450
l=30
P
c=0.1,
P
m=0.1
4363
5433
2.2
在线和离线性能的分析
Dejong
提出了遗传算法
的定量评价方法，包括在线和离线性能评价。前者测试动态性
能，
而后者评估收敛性能。
为了更好地分析测试功能的在线和离线性能，
< br>我们把个体的适应
性乘以
10
，
并
f1
和
f2
分别给出了
4 000
和
1
000
代的曲线：
(a)
在线
(b)
离线
图
1
f1
的在线与离线性能
(a)
在线
(b)
离线
图
2
f2
的在线与离线性能
从图
1
和图
2
可以看出，我们方法的在线性能只比第四种情况差一点
点，但比第二种、
第三种、第五种好很多，
这几种情况下的在线
性能几乎完全相同。
同时，我们方法的离线性
能也比其他四种好
很多。
3.
结论
本文提出了一种使用变异染色体
长度和交叉变异概率的改进遗传算法。
一些关键功能的
测试表明
，
我们的解决方案可以显著提高遗传算法的收敛速度，
其综合性
能优于只保留最佳
个体的遗传算法。
附件
有了第一部分中假定的条件，定
理
1
和定理
2
的验证是显而易见的。下面给出定理
3
和定理
< br>4
的证明过程：
定理
3
单点交叉的染色体搜索步骤的
数学期望
E
c
(x)
< br>是
E
c
(x) =
P
c
其中<
/p>
P
c
是交叉概率
证明：
如图
A1
所示，
我们假设交叉发生在第
k<
/p>
个基因位点，
从
k
到
l
的父基因位点没有变化，
基因位
点
1
到
k
上的
基因改变了。
在交叉过程中，
1
到
k
基因位点上的基因改变的概率为
0.5(
“
1
”
变化
”
0
”
或者
”
0
”
变为
”
1
”
)
，
因此，
交叉之后，基
因位点上的染色体搜索步骤从
1
到
k<
/p>
的数学期望是
此外，每个位点的染色体发生交叉的概率是相等的，即
P
c
。交叉后，染色体搜索步骤
的数学期望是
把
Eq. (
A1)
替换为
Eq. (
A2)
，我们得到
其中
l
是非常大的，
，
所以
图
1
单点交叉
定理
4
位变异的染色体搜索步骤的数学期望是
其中
P
m<
/p>
是变异概率。
证明：
每个基因位点上的基因的变异
概率是相等的，比如
P
m
，因此变异搜
索步骤的数学期望
是：
参考
[1]
Li Haimin,
Wu Chengke
.
自适应变异概率的遗传算法以及其性能分析
. [J].
Acta
Electronia Sinica ,1999, 27( 5) :
89
---
92.
[2]
Nara
Koichi.
基于大规模的分布式系统损失最小化的改进遗传算法
.
[A].
进化计算
< br>IEEE
会议
[ C] .
1995: 120
---
125.
[3]
Lei Yin, Wei
Hong.
一种改进的遗传算法以及它在
E
计划波导过滤器设计重点额应用
[ J ] . Acta Electronia Sinica,
2000,
28( 6) :
121
---
124.
[4]
Enrique Alba, Jose M T roya.
迁移策略在结构化的随机交配群体中的并行分布遗传算
法的影响
. [ J ]
.
应用智能
, 2000, 12: 163
---
181.
[5]
Rudolph
R.
经典遗传算法的收敛分析
. [
J ] .
基于神经网络的
IEEE
转录
, 1994, 5( 1) :
96
---
101.
-
-
-
-
-
-
-
-
-
上一篇：吧台用英语
下一篇：大学用英语怎么说 大学英文怎么说word版