基于prim算法求出网络最小生成树实现网络社团划分和规划
1.程序功能描述
路线制定
1,将算法得到的各社团的需充电节点数量排序,将其视为节点权值
2,利用prim算法求出最小生成树,即完成了整个网络规划。
2.测试软件版本以及运行结果展示
MATLAB2022a版本运行
3.核心程序
%将算法三得到的各社团的需充电节点数量排序,将其视为节点权值
%节点权值
W = [];
Xz = [];
Yz = [];
Ridx= 0;
for j=1:length(Cpn)
if Cpn(j) == 0%N型社团
Ridx = Ridx + 1;
tmp = C{j,1};
E = Eres(tmp);
%找到能量最小的三个
[VV,II] = sort(E);
%求出其质心作为停留点
indx = tmp(II(1:min(3,length(tmp))));
Xz = [Xz,mean(Xo(indx))];
Yz = [Yz,mean(Yo(indx))];
%分析无需充电节点
Nindx1 = find(E>=0.9*Ec);
%分析需充电节点
Nindx2 = find(E< 0.9*Ec);
%权值
W = [W,length(Nindx2)];
end
end
%权值
W
%利用prim算法求出最小生成树,即完成了整个网络规划
figure;
for j = 1:length(Cj)
tmp = Cj{j,1};
X0 = Xo(tmp);
Y0 = Yo(tmp);
plot(X0,Y0,colors{j});
hold on
Xc(j)= mean(X0);
Yc(j)= mean(Y0);
for i = 1:length(tmp)
dist(i) = sqrt((Xc(j)-X0(i))^2 + (Yc(j)-Y0(i))^2);
end
if Cpn(j) == 1
plot3(Xc(j),Yc(j),max(dist));
else
plot4(Xc(j),Yc(j),max(dist));
end
hold on
end
plot(Xc,Yc,'rs','LineWidth',2,'MarkerEdgeColor','b','MarkerFaceColor','y','MarkerSize',10)
title('社团划分结果(Red:P;Black:N),Yellow:P&N中心点');
hold on
[All_Lens,T,xx,yy]=func_prim([Xc;Yc]);
grid on;
%按先序遍历顺序访问
for i=1:length(T)-1
Xc(i) = xx(T(1,i));
Yc(i) = yy(T(1,i));
end
%统计首次通过的
Xc1 = unique(Xc);
Yc1 = unique(Yc);
%路由表,保存点坐标
[Xc1',Yc1']
12_035m
4.本算法原理
旅行商问题(Traveling Salesman Problem, TSP)是组合优化领域的一个经典NP难问题,旨在寻找访问一系列城市并返回起点的最短路径。TSP问题可以描述为:给定一个城市集合和每对城市之间的距离,要求找出访问每个城市一次并返回起点的最短路径。
4.1 遗传算法(Genetic Algorithm, GA)在TSP中的应用
遗传算法是一种模拟自然选择和遗传学机制的优化算法,适用于求解组合优化问题。在TSP问题中,GA通过编码生成初始路径种群,然后通过选择、交叉和变异等操作不断迭代优化,最终找到近似最优解。
编码方式:采用自然数编码,每个城市的编号代表一个基因,一条路径则由一串基因组成。
初始种群生成:随机生成一定数量的初始路径,构成初始种群。
适应度函数:以适应度函数来衡量每个个体的优劣。在TSP问题中,适应度函数通常取为路径长度的倒数。
选择操作:采用轮盘赌选择法,即根据每个个体的适应度值在总体适应度值中的比例来选择个体。
交叉操作:采用部分映射交叉(PMX)或顺序交叉(OX)等方法,生成新的个体。
变异操作:通过随机交换路径中两个城市的位置来实现变异。
4.2 粒子群优化算法在TSP中的应用
粒子群优化算法是一种模拟鸟群觅食行为的优化算法,适用于连续和离散优化问题。在TSP问题中,PSO将每个解看作一个粒子,通过不断更新粒子的速度和位置来寻找最优解。
粒子表示:每个粒子表示一个可能的解,即一条路径。粒子的位置由路径中城市的排列顺序决定。
速度更新公式:根据每个粒子的历史最优位置和群体最优位置来更新粒子的速度。速度更新公式为:(v_{id} = w * v_{id} + c1 * rand() * (pbest_{id} - x_{id}) + c2 * rand() * (gbest_d - x_{id})),其中 (v_{id}) 表示第i个粒子在第d维上的速度,(x_{id}) 表示第i个粒子在第d维上的位置,(pbest_{id}) 表示第i个粒子在第d维上的历史最优位置,(gbest_d) 表示群体在第d维上的最优位置,w为惯性权重,c1和c2为学习因子,rand()为随机数生成函数。
位置更新公式:根据更新后的速度来更新粒子的位置。位置更新公式为:(x_{id} = x_{id} + v_{id})。
需要注意的是,在更新位置时要保证新生成的路径满足TSP问题的约束条件。
- 点赞
- 收藏
- 关注作者
评论(0)