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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
import random
import numpy as np
import matplotlib.pyplot as plt
def distance(x1, x2):
"""计算两个坐标点的欧氏距离平方（无需开方以优化性能）"""
return (x1[0] - x2[0]) ** 2 + (x1[1] - x2[1]) ** 2
def total_distance(airports, cities):
"""计算所有城市到最近机场的距离总和（使用向量化计算）"""
airports_arr = np.array(airports)
cities_arr = np.array(cities)
# 计算每个城市到所有机场的平方距离
diff = cities_arr[:, None, :] - airports_arr[None, :, :]
dist_sq = np.sum(diff**2, axis=2)
# 获取每个城市到最近机场的距离
min_dists = np.min(dist_sq, axis=1)
return np.sum(min_dists)
# 城市坐标数据集
cities = [
[91, 492], [400, 327], [253, 288], [165, 299], [562, 293],
[305, 449], [375, 270], [534, 350], [473, 506], [165, 379],
[168, 339], [406, 537], [131, 571], [320, 368], [233, 410],
[207, 457], [94, 410], [456, 350], [509, 444], [108, 531]
]
# 算法参数
POP_SIZE = 50 # 种群规模
MAX_ITER = 10000 # 最大迭代次数
# 记录最佳解和迭代信息
best_global = float("inf")
best_solution = None
no_improve = 0
convergence_data = []
MAX_NO_IMPROVE = 100 # 连续无改进的最大迭代次数
# 获取城市坐标边界
x_coords = [c[0] for c in cities]
y_coords = [c[1] for c in cities]
x_min, x_max = min(x_coords), max(x_coords)
y_min, y_max = min(y_coords), max(y_coords)
# 初始化种群（每个个体包含3个机场坐标）
population = []
for _ in range(POP_SIZE):
airport1 = [
round(random.uniform(x_min, x_max), 2),
round(random.uniform(y_min, y_max), 2),
]
airport2 = [
round(random.uniform(x_min, x_max), 2),
round(random.uniform(y_min, y_max), 2),
]
airport3 = [
round(random.uniform(x_min, x_max), 2),
round(random.uniform(y_min, y_max), 2),
]
population.append([airport1, airport2, airport3])
# 差分进化主循环
for iter in range(MAX_ITER):
pop_array = np.array(population)
new_population = []
no_improve_flag = True
# 自适应差分权重（随迭代次数递减）
F = 0.9 * (1 - iter / MAX_ITER) + 0.4 * (iter / MAX_ITER)
for individual in population:
# 变异操作：生成变异向量
a, b, c = random.choices(population, k=3)
mutant = a + F * (np.array(b) - np.array(c))
mutant = mutant.tolist()
# 交叉操作：生成试验向量
trial = []
for j in range(3):
if random.random() <= 0.5 or j == random.randint(0, 2):
trial.append(mutant[j])
else:
trial.append(individual[j])
# 选择操作：保留更优解
current_fitness = total_distance(individual, cities)
trial_fitness = total_distance(trial, cities)
if trial_fitness < current_fitness:
new_population.append(trial)
# 更新全局最优解
if trial_fitness < best_global:
best_global = trial_fitness
best_solution = np.copy(trial)
no_improve = 0
no_improve_flag = False
else:
new_population.append(individual)
population = new_population
# 记录收敛数据
convergence_data.append(best_global)
if no_improve_flag:
no_improve += 1
# 检查提前终止条件
if no_improve >= MAX_NO_IMPROVE:
print(f"提前终止于第{iter}代，已连续{no_improve}代无改进")
break
# 结果提取与验证
# 记录最优个体的下标
best_idx = 0
for i in range(len(population)):
if total_distance(population[i], cities) < total_distance(
population[best_idx], cities
):
best_idx = i
# 记录次优个体的下标
second_best_idx = 0
for i in range(len(population)):
if i != best_idx and total_distance(population[i], cities) < total_distance(
population[second_best_idx], cities
):
second_best_idx = i
# 计算最优个体与次优个体的差值，以判断收敛情况
diff = total_distance(population[second_best_idx], cities) - total_distance(
population[best_idx], cities
)
print(f"最优解与次优解距离差: {diff:.2f}")
print(f"最优机场坐标: {population[best_idx]}")
print(f"最小距离和: {total_distance(population[best_idx], cities):.2f}")
|
记录生活