基于prim算法求出网络最小生成树实现网络社团划分和规划

举报
软件算法开发 发表于 2024/10/15 20:20:59 2024/10/15
【摘要】 1.程序功能描述路线制定1,将算法得到的各社团的需充电节点数量排序,将其视为节点权值2,利用prim算法求出最小生成树,即完成了整个网络规划。2.测试软件版本以及运行结果展示MATLAB2022a版本运行3.核心程序%将算法三得到的各社团的需充电节点数量排序,将其视为节点权值%节点权值W = [];Xz = [];Yz = [];Ridx= 0;for j=1:length(Cpn)...

1.程序功能描述
路线制定

1,将算法得到的各社团的需充电节点数量排序,将其视为节点权值

2,利用prim算法求出最小生成树,即完成了整个网络规划。

2.测试软件版本以及运行结果展示
MATLAB2022a版本运行


1.jpeg

2.jpeg

3.jpeg

4.jpeg

5.jpeg


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问题的约束条件。

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。