-
第
1
页
《决策支持系统》实验报告
开课实验室：信息中心
学院
课程
名称
教师
评语
教师签名：
年
月
日
一、实验目的
1
、掌握智能程序的构造方法；
2
、掌握遗传算法的设计过程；
3
、掌握概率发生器的编写过程；
<
/p>
4
、讨论
TSP
问题中不同评价函数的使用结果。
二、实验原理
遗传算法（
genetic algorithm, GA
）是模拟生物进化的自然选择和遗传机制的一种搜索寻优
算法。它利
用适者生存的进化原则，通过演化逐步逼近问题的最优解。基本原理是通过随机方
式将问
题的每一个可能的解进行数字编码，编码后的解称作染色体（个体）
，随机选取
N
个染
色体构成初始种群，通过适应度函数给每
个个体一个数值评价，淘汰低适应度的个体，选择适
应值高的染色体进行复制，通过遗传
算子（选择、交叉、变异）
，产生一群新的适应环境的染
色体，
形成新的种群。这样一代一代不断进化，最后收敛到适应环境较好的一些个体中，求得
问
题的最优解。
遗传算法的执行过程中，每一代有许多不同的染
色体（个体）同时存在，这些染色体中哪
个保留、
哪个淘汰是根
据它们对环境的适应能力来决定的，
适应性强的有更多的机会保留下来。
适应性强弱是由适应值函数
f
(
x
)
的值来判别的。每个个体代表一条可能的路径。个体
n
的适应
值为
D<
/p>
n
Fitness
n
年级、专业、班
实验项目
名
称
姓名
成绩
决策支持系统（双语）
TSP
问题的遗传算法求解
指导教师
?
1
/
D
n
，其
中，
N
为种群数，
10
D
n
为沿个体标示的城市序列所经过的路径长度，
2
2
可通过以下公式计算出来：
D
n
?
?
i
?
1
(
x
n
i
?
x
n
i
?
1<
/p>
)
?
(
y
n
i
?
y
n
i
?
1
)
其中，
n
i
表示个体第
i
位的城市编号。
?
D
m
表示所有个体的路径长度的总和
。适应值为非负，且取值越大越好。
遗传算法中主要的遗传算子有如下几种：
（
1
）选择（
selection
）算子：
又称复制、繁殖算子。选择
是从种群中选择生命力强的染色体产生种群的过程。依据每个
染色体的适应值大小，
适应值越大，
被选中的概率就越大，
其子孙
在下一代产生的个数就越多。
本实验采用的是比率法，比率法的原理是每个染色体产生后
代的数目正比于它的适应值，并有
一个约束条件，即每一代中染色体的总数应保持不变。
（
2
）交叉
（
crossover
）算子
又称重组、配对算子。交叉采用部分匹配交叉策略，首先根据交叉概率
P
c
，随机地从新复
制的种群中选出要
交叉的两个不同个体；然后，随机地选取一个交叉段，交叉段中两个个体的
对应部分通过
匹配换位实现交叉操作。
例如，对个体
A
和
B
：
第
2
页
A=9 8 4 5 6
7 1 3 2 10
B=8 7 1
4 10 3 2 9 6
5
交叉段
交叉后得到：
A
’
=9 8 1
4 10 3 2 3 2
10
B
’
= 8 7 4
5 6 7 1 9 6
5
交叉段
（
3
）变异（
mutation
）算子<
/p>
即根据变异概率
P
e
，
随机地从种群中选出要变异的个体，
< br>随机地在该个体上选出两个变异
位置，然后将两个位置上的城市序号进行变换。选
择和交叉算子基本上完成了遗传算法地大部
分搜索功能，而变异则增加了遗传算法找到接
近最优解的能力。如：
A=9
8
4
5
6
7
1
3
2
10
下划线部分为要变异的两个位置，变异为：
A
’
=9
7
4
5
6
8
1
3
2
10
三、使用仪器、材料
计算机，
VB
系统
四、实验步骤
(1)
编写适应值函数
适应度值是根据适应度函数来计算的，如适应度函数代码如下：
Public Function calfitness(ByRef c As
Integer) As Single
Dim temp As Single
Dim i As Integer
If = 1
Then
calfitness = 1# /
lengthchro(c)
Else
temp = 0#
For i = 1 To Pool_Size
temp = temp + lengthchro(i)
Next
calfitness =
temp - lengthchro(c)
End If
End Function
(2
）编写概率发生器
即选择算子，
选择的目的是为了从当前群体中选出优良的个体，
使它们有机会
作为父代产
生后代个体，如代码：
Public Sub reproduce()
ReDim temppchropool(1 To Pool_Size, 1 To City_Num)
As Integer
ReDim temppro(0 To
Pool_Size) As Single
Dim rndnum As
Single
Dim i, j, k As Integer
temppro(0) = 0#
For i =
1 To Pool_Size
temppro(i) =
temppro(i - 1) + calprobability(i)
Next i
For i = 1 To Pool_Size
rndnum = Rnd
For j =
1 To Pool_Size
If rndnum <=
temppro(j) And rndnum > temppro(j - 1) Then
For k = 1 To City_Num
temppchropool(i, k) =
chromosome(j, k)
第
3
页
Next
Exit For
End
If
Next
Next
For k = 1 To Pool_Size
For i = 1 To City_Num
chromosome(k, i) = temppchropool(k, i)
Next
Next k
End Sub
(3
）编写交叉算子
实现过程是对选中用于繁殖下一代的个体，
随机地选择两个个体的相同位置，
按交叉概率
Pc
，在选择的位置实行交
换，目的在于产生新的基因组合。
Public Sub
crossover()
Dim chr1, chr2, cit1,
cit2, rndnum, gen_no, i, j As Integer
Dim gen_a1, gen_a2, gen_b1, gen_b2 As Integer
ReDim choiced(1 To CrossNum) As
Integer
ReDim precho(1 To
Pool_Size) As Integer
For i = 1 To
Pool_Size
precho(i) = i
Next
For i = 1 To
CrossNum
Do
chr1 = Int(Pool_Size * Rnd + 1)
Loop Until precho(chr1) > 0
choiced(i) = chr1
precho(chr1) =
0
Next
For j = 1 To
CrossNum Step 2
chr1 = choiced(j)
chr2 = choiced(j + 1)
gen_no = Int(City_Num * Rnd + 1)
gen_a2 = gen_no
gen_b1 = gen_no
cit1 = chromosome(chr1, gen_no)
cit2 = chromosome(chr2, gen_no)
For i = 1 To City_Num
If chromosome(chr1, i) = cit2 Then
gen_a1 = i
Exit For
End If
Next
For i = 1 To City_Num
If chromosome(chr2, i) = cit1 Then
gen_b2 = i
Exit For
End If
Next
chromosome(chr1, gen_a1) = cit1
chromosome(chr1, gen_a2) = cit2
chromosome(chr2, gen_b1) = cit1
第
4
页
chromosome(chr2,
gen_b2) = cit2
Next
End
Sub
(4
）编写变异算子
按一定概率随机改变某个个体的基因值，以变异概率
Pm
对某个个体的某些位执行变异，
在变异时，对执行变异的串的对应位求反，如
代码：
Public Sub mutation()
Dim chr1, cit1, cit2, i As Integer
Dim gen_a1, gen_a2 As Integer
If MutationNum > 0 Then
ReDim choiced(1 To
MutationNum) As Integer
ReDim precho(1 To Pool_Size) As Integer
For
i = 1 To Pool_Size
precho(i) = i
Next
For i = 1 To
MutationNum
Do
chr1 = Int(Pool_Size * Rnd + 1)
Loop Until precho(chr1) > 0
choiced(i) = chr1
precho(chr1) = 0
Next
For i = 1 To MutationNum
chr1 = choiced(i)
gen_a1 = Int(City_Num * Rnd + 1)
gen_a2 = Int(City_Num * Rnd + 1)
cit1 = chromosome(chr1, gen_a1)
cit2 = chromosome(chr1, gen_a2)
chromosome(chr1, gen_a1) = cit2
chromosome(chr1, gen_a2) = cit1
Next
End If
End Sub
五、
实验过程原始记录
(
数据、图表、计算等
)
实验包含参数：
城市数、种群大小、进化代数、交叉概率
、变异概率、选择算法，具体设
置如表
1
：
分组
第一组
第二组
第三组
第四组
第五组
表
1
实验参数
城市数
种群大小
进化代数
交叉概率
35
30
100
0.4
35
30
100
0.4
35
30
100
0.4
35
100
100
0.4
35
30
100
0.4
35
30
200
0.4
35
30
100
0.4
35
30
100
0.7
35
30
100
0.4
35
30
100
0.4
第
5
页
变异概率
选择算法
参照图
0.1
选择算法
1
图
1
0.1
图
2
0.1
1
图
3
0.1
1
图
4
0.1
1
图
5
0.1
1
图
6
0.1
1
图
7
0.1
1
图
8
0.1
1
图
9
0.5
1
图
10
-
-
-
-
-
-
-
-
-
上一篇：三个遗传算法matlab程序实例
下一篇：各种机械行业缩写