营口市网站建设_网站建设公司_jQuery_seo优化

【最小生成树-Matlab】（在Matlab中使用粒子群算法（PSO），帝国主义竞争算法（ICA），和萤火虫算法（FA）实现最小生成树）

最小生成树这玩意儿在算法圈子里可是个经典问题，不过用群体智能算法来搞它倒是挺有意思的。今天咱们拿Matlab当试验田，试着把粒子群、帝国主义竞争和萤火虫这三个算法都往图结构上怼一怼，看看这些花里胡哨的算法到底能不能解实际问题。

先来点准备工作，整个邻接矩阵是必须的。咱们用个随机生成的带权图试试水：

n = 10; % 节点数 adj_matrix = triu(randi([1,20],n,n),1); % 上三角矩阵 adj_matrix = adj_matrix + adj_matrix'; % 对称处理 adj_matrix(adj_matrix==0) = inf; % 对角线置无穷大

接下来要搞个计算权重的函数，这个函数会被各个算法反复调用。注意这里用到了避免环路的处理：

function total_weight = calc_weight(tree_edges, adj_matrix) visited = zeros(1,size(adj_matrix,1)); visited(tree_edges(1,1)) = 1; total_weight = 0; for i = 1:size(tree_edges,1) total_weight = total_weight + adj_matrix(tree_edges(i,1), tree_edges(i,2)); visited(tree_edges(i,2)) = 1; end if sum(visited) ~= size(adj_matrix,1) total_weight = inf; % 存在未连通节点时惩罚 end end

粒子群算法（PSO）实现：

关键是把生成树编码成粒子位置。这里用了个取巧的编码方式——记录边的选择状态：

% 参数设置 max_iter = 50; swarm_size = 30; w = 0.6; c1 = 1.4; c2 = 1.4; % 初始化粒子（随机选n-1条边） particles = cell(swarm_size,1); for i=1:swarm_size edges = randperm(n*(n-1)/2, n-1); particles{i} = struct('position',edges, 'velocity',zeros(size(edges)),... 'pbest',edges, 'pbest_weight',inf); end

速度更新部分要注意处理离散值的问题，这里用了概率映射：

% 速度更新公式（离散版） new_vel = w*particle.velocity + c1*rand*(pbest_edge - curr_pos) + c2*rand*(gbest_edge - curr_pos); prob = 1./(1+exp(-new_vel)); % sigmoid转换 particle.position = rand(size(prob)) < prob; % 二值化

帝国主义竞争算法（ICA）实战：

这个算法的帝国划分机制挺有意思，咱们把每个国家定义为一种生成树解：

% 初始化帝国 num_empires = 5; [~, sorted_idx] = sort([countries.cost]); imperialist = sorted_idx(1:num_empires); colonies = sorted_idx(num_empires+1:end); % 分配殖民地（这里用了动态比例分配） empire_strength = 1./[countries(imperialist).cost]; prob_dist = empire_strength / sum(empire_strength); colony_allocation = arrayfun(@(p) sum(rand>=cumsum([0 p])), prob_dist);

同化过程要注意保持树结构，这里用了边交换策略：

% 同化操作（交换两条边） defense_edges = imperialist_tree; attack_edges = colony_tree; common_edges = intersect(defense_edges, attack_edges, 'rows'); candidate_edges = setdiff(attack_edges, common_edges, 'rows'); if ~isempty(candidate_edges) swap_idx = randi(size(candidate_edges,1)); new_edge = candidate_edges(swap_idx,:); colony_tree = [common_edges; new_edge]; end

萤火虫算法（FA）的亮度设计：

亮度函数直接影响搜索方向，这里把权重倒数作为亮度，同时处理约束：

function brightness = compute_brightness(fireflies, adj_matrix) brightness = zeros(1,length(fireflies)); for k=1:length(fireflies) if is_connected(fireflies(k).edges) brightness(k) = 1 / sum(adj_matrix(sub2ind(size(adj_matrix),... fireflies(k).edges(:,1), fireflies(k).edges(:,2)))); else brightness(k) = 0; % 不连通直接判死刑 end end end

移动策略采用了带变异因子的边替换：

% 向更亮的萤火虫移动（概率性替换边） diff_edges = setdiff(brighter_firefly.edges, current_edges, 'rows'); if ~isempty(diff_edges) replace_num = min(2, size(diff_edges,1)); % 每次最多替换两条边 new_edges = [setdiff(current_edges, diff_edges(1:replace_num,:), 'rows'); diff_edges(1:replace_num,:)]; % 补充随机边保证数量 if size(new_edges,1) < (n-1) new_edges = [new_edges; randi([1,n], (n-1)-size(new_edges,1), 2)]; end end

折腾完这三个算法，实测发现FA在稀疏图上表现最稳，PSO收敛速度惊人但容易早熟，ICA则对参数敏感但全局搜索能力不错。不过这些启发式算法在节点超过50之后就开始吃力了，毕竟时间复杂度摆在那儿。下次或许可以试试混合策略，比如用ICA做全局搜索再用FA局部优化，说不定能突破现有局限。