智能优化算法---遗传算法(GA)
说明
基础内容源自 智能优化算法及其MATLAB实例(第二版)源程序
源程序为 matlab 代码,笔者在此基础上将 matlab 代码转化为 python 代码实现
一、标准遗传算法求函数极值
GA21.m
1 |
|
func1.m
1 |
|
GA21.py
1 |
|
1 |
|

二、实值遗传算法求函数极值
GA22.m
1 |
|
GA22.py
1 |
|
三、遗传算法解决TSP问题
GA23.m
1 |
|
GA23.py
对应的python脚本如下: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100import numpy as np
import matplotlib.pyplot as plt
# 数据初始化
C = np.array([
[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535],
[3326, 1556], [3238, 1229], [4196, 1044], [4312, 790], [4386, 570],
[3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695],
[3715, 1678], [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578],
[4029, 2838], [4263, 2931], [3429, 1908], [3507, 2376], [3394, 2643],
[3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826],
[2370, 2975]
]) # 31个省会城市坐标
N = C.shape[0] # 城市数目
D = np.zeros((N, N)) # 距离矩阵
# 计算距离矩阵
for i in range(N):
for j in range(N):
D[i, j] = np.sqrt((C[i, 0] - C[j, 0])**2 + (C[i, 1] - C[j, 1])**2)
NP = 200 # 种群规模
G = 1000 # 最大遗传代数
# 初始化种群
f = np.array([np.random.permutation(N) for _ in range(NP)])
R = f[0] # 存储最优种群
len_paths = np.zeros(NP) # 路径长度
fitness = np.zeros(NP) # 适应值
gen = 0
# 遗传算法主循环
Rlength = []
while gen < G:
# 计算路径长度
for i in range(NP):
path = f[i]
len_paths[i] = D[path[-1], path[0]]
for j in range(N - 1):
len_paths[i] += D[path[j], path[j + 1]]
maxlen = np.max(len_paths) # 最长路径
minlen = np.min(len_paths) # 最短路径
# 更新最短路径
best_index = np.argmin(len_paths)
R = f[best_index]
# 计算归一化适应值
fitness = 1 - ((len_paths - minlen) / (maxlen - minlen + 0.001))
# 选择操作
F = f[fitness >= np.random.rand(NP)]
while len(F) < NP:
nnper = np.random.permutation(len(F))
A = F[nnper[0]]
B = F[nnper[1]]
# 交叉操作
W = np.ceil(N / 10).astype(int) # 交叉点个数
p = np.random.randint(0, N - W + 1) # 选择交叉点
for i in range(W):
x = np.where(A == B[p + i])[0][0]
y = np.where(B == A[p + i])[0][0]
A[p + i], B[p + i] = B[p + i], A[p + i]
A[x], B[y] = B[y], A[x]
# 变异操作
p1, p2 = np.random.choice(N, 2, replace=False)
A[p1], A[p2] = A[p2], A[p1]
B[p1], B[p2] = B[p2], B[p1]
F = np.vstack([F, A, B])
if len(F) > NP:
F = F[:NP] # 保持种群规模
f = F # 更新种群
f[0] = R # 保留每代最优个体
gen += 1
Rlength.append(minlen)
# 绘图
plt.figure()
for i in range(N - 1):
plt.plot([C[R[i], 0], C[R[i + 1], 0]], [C[R[i], 1], C[R[i + 1], 1]], 'bo-')
plt.plot([C[R[-1], 0], C[R[0], 0]], [C[R[-1], 1], C[R[0], 1]], 'ro-')
plt.title(f'优化最短距离: {minlen:.2f}')
plt.show()
plt.figure()
plt.plot(Rlength)
plt.xlabel('迭代次数')
plt.ylabel('目标函数值')
plt.title('适应度进化曲线')
plt.show()

发现写的 python 脚本运行效果不好,不如 matlab 脚本
从网上找了一段python代码来比较下:
1 |
|

这个明显效果好一些
对于上述tsp问题,还可以使用蚁群算法解决,参考: http://t.csdnimg.cn/C5NqG