基于聚类与引力斥力优化的选址算法

在浩繁实际场景中，诸如消防办法选址、基站结构规划以及充电桩站点摆设等，都面临着怎样利用最少的资源，实现对全部目的对象全面覆盖的困难。为有用办理这类标题，本文提出一种全新的组合算法模子 —— 基于聚类与引力斥力优化的选址算法。
算法简介

1. K - means 聚类初始化

•         目的：快速天生初始中心点，开端分别数据分布。
  
•         方法：通过 K - means 算法将二维点聚类为 k 组，每组中心作为初始候选点。联合肘部法则或外貌系数确定最优 k，并利用 K - means++ 优化初始中心选择。
  

2. 贪默算法增补覆盖

•         目的：确保全部数据点被覆盖，增补初始聚类未覆盖的地域。
  
•         方法：设置中心点覆盖半径 r，标记未被覆盖的点。每次从未覆盖点中选择能覆盖最多未覆盖点的点作为新中心点，直至全部点被覆盖。
  

3. 引力搜刮算法（GSA）优化

•         目的：动态调解中心点位置，剔除冗余点，实现最少中心点全覆盖。
  
•         方法：
  
•         引力与斥力：中心点受未覆盖点引力（向数据移动）和其他中心点斥力（克制麋集）。
  
•         协力驱动：根据引力和斥力的矢量和移动中心点，验证覆盖后更新位置。
  
•         剪枝操纵：定期实行删除冗余中心点，确保覆盖性的同时最小化中心点数目。
  

4. 组合算法上风

•         高效性：K - means 快速聚类，贪默算法快速覆盖，GSA 风雅调优。
  
•         鲁棒性：联合多少覆盖与物理开导式优化，顺应复杂分布。
  
•         可表明性：每一步逻辑清楚，便于根据场景调解参数或更换算法。
  

算法步调与公式

第一步：K - means 聚类

1. 初始聚类中心

利用算法初始化聚类中心，选择隔断已有中心最远的点作为新中心：

2. 聚类分配与中心更新

盘算每个点到中心的欧氏隔断并分配：

重新盘算中心坐标：

此中Sj是第j个聚类的数据点聚集。
第二步：贪默算法覆盖未被覆盖点

1. 覆盖条件

点x被中心cj覆盖当且仅当：

2. 选择最优新中心

每次选择覆盖最多未覆盖点的点：

此中I(·)是指示函数。
第三步：引力搜刮算法（GSA）优化中心点

1. 质量界说

中心点ci的质量mi由覆盖点数决定：

2. 引力盘算

数据点x对中心ci的引力：

此中

是时变引力常数。
3. 斥力盘算

其他中心cj对ci的斥力：

4. 协力与位置更新

总协力：

位置更新：

此中 λ是方向系数，step_size是步长。
5. 中心点剔除条件

若剔除中心ci后全部点仍被覆盖：

代码

python代码

2. import numpy as np
3. import matplotlib.pyplot as plt
4. from sklearn.cluster import KMeans
6. # 第一步：K - means 聚类
7. # 随机生成一些示例数据
8. points = np.random.rand(100, 2)
9. # 设置聚类中心数
10. k = 10
11. # 执行 K - means 聚类
12. kmeans = KMeans(n_clusters=k, random_state=42)
13. idx = kmeans.fit_predict(points)
14. centers = kmeans.cluster_centers_
16. # 第二步：贪心算法覆盖未被覆盖点
17. # 设置覆盖半径
18. r = 0.2
19. # 标记未被覆盖的点
20. covered = np.zeros(points.shape[0], dtype=bool)
21. for center in centers:
22.     distances = np.linalg.norm(points - center, axis=1)
23.     covered[distances <= r] = True
24. uncovered_points = points[~covered]
26. while len(uncovered_points) > 0:
27.     max_coverage = 0
28.     best_point = None
29.     for point in uncovered_points:
30.         distances = np.linalg.norm(points - point, axis=1)
31.         current_coverage = np.sum((distances <= r) & ~covered)
32.         if current_coverage > max_coverage:
33.             max_coverage = current_coverage
34.             best_point = point
35.     centers = np.vstack((centers, best_point))
36.     distances = np.linalg.norm(points - best_point, axis=1)
37.     covered[distances <= r] = True
38.     uncovered_points = points[~covered]
40. # 第三步：引力搜索算法（GSA）优化中心点
41. # 设置参数
42. T = 100  # 迭代次数
43. G0 = 1  # 引力常数
44. alpha = 2  # 质量衰减系数
46. # 初始化质量
47. masses = np.zeros(centers.shape[0])
48. for i in range(centers.shape[0]):
49.     distances = np.linalg.norm(points - centers[i], axis=1)
50.     masses[i] = np.sum(distances <= r)
52. for t in range(T):
53.     G = G0 * np.exp(-alpha * t / T)
54.     for i in range(centers.shape[0]):
55.         force = np.zeros(2)
56.         # 计算斥力
57.         for j in range(centers.shape[0]):
58.             if i != j:
59.                 distance = np.linalg.norm(centers[i] - centers[j])
60.                 if distance > 0:
61.                     force += G * masses[j] * (centers[i] - centers[j]) / distance
62.         # 计算引力
63.         for j in range(points.shape[0]):
64.             distance = np.linalg.norm(centers[i] - points[j])
65.             if 0 < distance <= 2 * r:
66.                 force -= G * (centers[i] - points[j]) / distance
67.         # 移动中心点（先假设移动）
68.         new_center = centers[i] + force
69.         # 检查移动后的中心点是否能覆盖所有数据点
70.         temp_centers = centers.copy()
71.         temp_centers[i] = new_center
72.         temp_covered = np.zeros(points.shape[0], dtype=bool)
73.         for center in temp_centers:
74.             distances = np.linalg.norm(points - center, axis=1)
75.             temp_covered[distances <= r] = True
76.         if np.all(temp_covered):
77.             centers[i] = new_center
78.     # 尝试剔除冗余的中心点
79.     for i in range(centers.shape[0]):
80.         temp_centers = np.delete(centers, i, axis=0)
81.         temp_covered = np.zeros(points.shape[0], dtype=bool)
82.         for center in temp_centers:
83.             distances = np.linalg.norm(points - center, axis=1)
84.             temp_covered[distances <= r] = True
85.         if np.all(temp_covered):
86.             centers = temp_centers
87.             masses = np.delete(masses, i)
88.             break
90. # 输出最终的中心点
91. print('最终的中心点坐标：')
92. print(centers)
94. # 可视化结果
95. plt.figure()
96. plt.scatter(points[:, 0], points[:, 1], s=20, c='b', marker='s', edgecolors='b')
97. plt.scatter(centers[:, 0], centers[:, 1], s=20, c='r', marker='^', edgecolors='r')
98. # 为每个中心点绘制覆盖半径的透明圆
99. theta = np.linspace(0, 2 * np.pi, 100)
100. for center in centers:
101.     x = center[0] + r * np.cos(theta)
102.     y = center[1] + r * np.sin(theta)
103.     plt.fill(x, y, 'r', alpha=0.1, edgecolor='r')
104. plt.xlabel('X')
105. plt.ylabel('Y')
106. plt.show()

复制代码

结果图

matlab代码

2. clear
3. clc
4. close all
6. % 第一步：K - means 聚类
7. % 假设我们有一组二维点数据 points
8. % 随机生成一些示例数据
9. points = rand(100, 2); 
10. % 设置聚类中心数
11. k = 10; 
12. % 执行 K - means 聚类
13. [idx, centers] = kmeans(points, k);
15. % 第二步：贪心算法覆盖未被覆盖点
16. % 设置覆盖半径
17. r = 0.2; 
18. % 标记未被覆盖的点
19. covered = false(size(points, 1), 1);
20. for i = 1:size(centers, 1)
21.     distances = sqrt(sum((points - repmat(centers(i, :), size(points, 1), 1)).^2, 2));
22.     covered(distances <= r) = true;
23. end
24. uncovered_points = points(~covered, :);
26. while ~isempty(uncovered_points)
27.     max_coverage = 0;
28.     best_point = [];
29.     for i = 1:size(uncovered_points, 1)
30.         distances = sqrt(sum((points - repmat(uncovered_points(i, :), size(points, 1), 1)).^2, 2));
31.         current_coverage = sum(distances <= r & ~covered);
32.         if current_coverage > max_coverage
33.             max_coverage = current_coverage;
34.             best_point = uncovered_points(i, :);
35.         end
36.     end
37.     centers = [centers; best_point];
38.     distances = sqrt(sum((points - repmat(best_point, size(points, 1), 1)).^2, 2));
39.     covered(distances <= r) = true;
40.     uncovered_points = points(~covered, :);
41. end
43. % 第三步：引力搜索算法（GSA）优化中心点
44. % 设置参数
45. T = 100; % 迭代次数
46. G0 = 1; % 引力常数
47. alpha = 2; % 质量衰减系数
49. % 初始化质量
50. masses = zeros(size(centers, 1), 1);
51. for i = 1:size(centers, 1)
52.     distances = sqrt(sum((points - repmat(centers(i, :), size(points, 1), 1)).^2, 2));
53.     masses(i) = sum(distances <= r);
54. end
56. for t = 1:T
57.     G = G0 * exp(-alpha * t / T);
58.     for i = 1:size(centers, 1)
59.         force = zeros(1, 2);
60.         % 计算斥力
61.         for j = 1:size(centers, 1)
62.             if i ~= j
63.                 distance = sqrt(sum((centers(i, :) - centers(j, :)).^2));
64.                 if distance > 0
65.                     force = force + G * masses(j) * (centers(i, :) - centers(j, :)) / distance;
66.                 end
67.             end
68.         end
69.         % 计算引力
70.         for j = 1:size(points, 1)
71.             distance = sqrt(sum((centers(i, :) - points(j, :)).^2));
72.             if distance <= 2*r && distance > 0
73.                 force = force - G * (centers(i, :) - points(j, :)) / distance;
74.             end
75.         end
76.         % 移动中心点（先假设移动）
77.         new_center = centers(i, :) + force;
78.         % 检查移动后的中心点是否能覆盖所有数据点
79.         temp_centers = centers;
80.         temp_centers(i, :) = new_center;
81.         temp_covered = false(size(points, 1), 1);
82.         for j = 1:size(temp_centers, 1)
83.             distances = sqrt(sum((points - repmat(temp_centers(j, :), size(points, 1), 1)).^2, 2));
84.             temp_covered(distances <= r) = true;
85.         end
86.         if all(temp_covered)
87.             centers(i, :) = new_center;
88.         end
89.     end
90.     % 尝试剔除冗余的中心点
91.     for i = 1:size(centers, 1)
92.         temp_centers = centers;
93.         temp_centers(i, :) = [];
94.         temp_covered = false(size(points, 1), 1);
95.         for j = 1:size(temp_centers, 1)
96.             distances = sqrt(sum((points - repmat(temp_centers(j, :), size(points, 1), 1)).^2, 2));
97.             temp_covered(distances <= r) = true;
98.         end
99.         if all(temp_covered)
100.             centers(i, :) = [];
101.             masses(i) = [];
102.             break;
103.         end
104.     end
105. end
107. % 输出最终的中心点
108. disp('最终的中心点坐标：');
109. disp(centers);
111. % 可视化结果
112. figure;
113. scatter(points(:, 1), points(:, 2), 20, 'bs', 'filled');
114. hold on;
115. scatter(centers(:, 1), centers(:, 2), 20,'r^', 'filled');
116. % 为每个中心点绘制覆盖半径的透明圆
117. theta = linspace(0, 2*pi, 100);
118. for i = 1:size(centers, 1)
119.     x = centers(i, 1) + r * cos(theta);
120.     y = centers(i, 2) + r * sin(theta);
121.     h = fill(x, y, 'r');
122.     set(h, 'FaceAlpha', 0.1); % 设置透明度为 0.1
123.     set(h, 'EdgeColor', 'r');
124. end
125. xlabel('X')
126. ylabel('Y')
127. title('基于聚类算法的选址结果')
128. legend('数据点', '中心点', '覆盖区域', 'Location', 'northeast')

复制代码

结果图