使用Hopfield神经网络解决旅行商问题-智慧文博士

使用Hopfield神经网络解决旅行商问题(TSP)。这是一种经典的神经网络优化方法。

Hopfield神经网络基础

Hopfield网络是一种递归神经网络，具有能量函数，能够收敛到局部最小值。

classdef HopfieldNetwork<handle properties num_neurons% 神经元数量weights% 连接权重矩阵biases% 偏置向量state% 神经元状态endmethodsfunctionobj=HopfieldNetwork(num_neurons)obj.num_neurons=num_neurons;obj.weights=zeros(num_neurons,num_neurons);obj.biases=zeros(num_neurons,1);obj.state=zeros(num_neurons,1);endfunctionenergy=compute_energy(obj)% 计算Hopfield网络的能量函数energy=-0.5*obj.state'*obj.weights*obj.state-obj.biases'*obj.state;endfunctionupdate_neuron(obj,neuron_idx)% 更新单个神经元的状态input=obj.weights(neuron_idx,:)*obj.state+obj.biases(neuron_idx);obj.state(neuron_idx)=1/(1+exp(-input));% Sigmoid激活函数endfunctionupdate_network(obj,num_iterations)% 更新整个网络foriter=1:num_iterationsfori=1:obj.num_neurons obj.update_neuron(i);end% 可选：每100次迭代显示能量ifmod(iter,100)==0energy=obj.compute_energy();fprintf('迭代 %d, 能量: %.4f\n',iter,energy);endendendendend

TSP问题建模与Hopfield网络映射

TSP的Hopfield网络表示

classdef TSPHopfieldSolver<handle properties num_cities% 城市数量city_positions% 城市坐标 [N x 2]distance_matrix% 距离矩阵 [N x N]% Hopfield网络参数N% 神经元数量 = num_cities × num_citieshopfield_net% Hopfield网络实例% 能量函数权重系数A% 行约束权重B% 列约束权重C% 路径长度权重D% 全局约束权重endmethodsfunctionobj=TSPHopfieldSolver(city_positions,A,B,C,D)% 构造函数obj.city_positions=city_positions;obj.num_cities=size(city_positions,1);obj.N=obj.num_cities^2;% 设置能量函数权重obj.A=A;obj.B=B;obj.C=C;obj.D=D;% 计算距离矩阵obj.distance_matrix=obj.compute_distance_matrix();% 创建Hopfield网络obj.hopfield_net=HopfieldNetwork(obj.N);% 构建权重矩阵obj.build_weight_matrix();endfunctiondistances=compute_distance_matrix(obj)% 计算城市间的距离矩阵distances=zeros(obj.num_cities,obj.num_cities);fori=1:obj.num_citiesforj=1:obj.num_citiesifi~=jdist=norm(obj.city_positions(i,:)-obj.city_positions(j,:));distances(i,j)=dist;endendendendfunctionbuild_weight_matrix(obj)% 构建TSP的Hopfield网络权重矩阵obj.hopfield_net.weights=zeros(obj.N,obj.N);obj.hopfield_net.biases=zeros(obj.N,1);% 四个约束项的权重计算fori=1:obj.num_citiesforj=1:obj.num_cities neuron_ij=(i-1)*obj.num_cities+j;fork=1:obj.num_citiesforl=1:obj.num_cities neuron_kl=(k-1)*obj.num_cities+l;ifneuron_ij==neuron_klcontinue;% 跳过自连接end% 约束1: 每个城市只能访问一次 (行约束)ifi==k&&j~=l obj.hopfield_net.weights(neuron_ij,neuron_kl)=...obj.hopfield_net.weights(neuron_ij,neuron_kl)-obj.A;end% 约束2: 每个位置只能有一个城市 (列约束)ifj==l&&i~=k obj.hopfield_net.weights(neuron_ij,neuron_kl)=...obj.hopfield_net.weights(neuron_ij,neuron_kl)-obj.B;end% 约束3: 总路径长度最小化ifj==l-1||(j==obj.num_cities&&l==1)ifi~=k dist_ik=obj.distance_matrix(i,k);obj.hopfield_net.weights(neuron_ij,neuron_kl)=...obj.hopfield_net.weights(neuron_ij,neuron_kl)-obj.C*dist_ik;endend% 约束4: 全局激活约束 (确保恰好有N个城市被访问)obj.hopfield_net.weights(neuron_ij,neuron_kl)=...obj.hopfield_net.weights(neuron_ij,neuron_kl)-obj.D;endend% 偏置项 (全局约束)obj.hopfield_net.biases(neuron_ij)=obj.D*obj.num_cities;endend% 确保权重矩阵对称obj.hopfield_net.weights=(obj.hopfield_net.weights+obj.hopfield_net.weights')/2;endfunctioninitialize_network(obj,noise_level)% 初始化网络状态ifnargin<2noise_level=0.1;end% 随机初始化，加入小扰动避免对称性base_state=0.5*ones(obj.N,1);noise=noise_level*(rand(obj.N,1)-0.5);obj.hopfield_net.state=base_state+noise;% 确保状态在[0,1]范围内obj.hopfield_net.state=max(0,min(1,obj.hopfield_net.state));endendend

网络求解与结果解码

function[best_tour,best_distance,convergence_info]=solve_tsp_hopfield(solver,max_iterations,annealing_schedule)% 使用Hopfield网络求解TSP% 输入:% solver: TSPHopfieldSolver实例% max_iterations: 最大迭代次数% annealing_schedule: 模拟退火计划 (可选)% 输出:% best_tour: 最优路径% best_distance: 最优路径长度% convergence_info: 收敛信息ifnargin<3annealing_schedule=@(iter)1.0;% 默认无退火end% 初始化网络solver.initialize_network();% 记录收敛信息convergence_info.energy=zeros(max_iterations,1);convergence_info.validity=zeros(max_iterations,1);best_energy=inf;best_state=solver.hopfield_net.state;foriter=1:max_iterations% 应用模拟退火 (如果提供)current_temp=annealing_schedule(iter);% 更新网络old_state=solver.hopfield_net.state;fori=1:solver.N% 计算输入input=solver.hopfield_net.weights(i,:)*solver.hopfield_net.state+...solver.hopfield_net.biases(i);% 带温度的sigmoid函数solver.hopfield_net.state(i)=1/(1+exp(-input/current_temp));end% 记录能量energy=solver.hopfield_net.compute_energy();convergence_info.energy(iter)=energy;% 检查解的有效性[is_valid,tour_length]=check_solution_validity(solver);convergence_info.validity(iter)=is_valid;% 更新最优解ifenergy<best_energy&&is_valid best_energy=energy;best_state=solver.hopfield_net.state;end% 显示进度ifmod(iter,100)==0fprintf('迭代 %d/%d, 能量: %.4f, 有效解: %d, 路径长度: %.2f\n',...iter,max_iterations,energy,is_valid,tour_length);end% 检查收敛ifiter>50&&check_convergence(convergence_info.energy,iter)fprintf('在迭代 %d 收敛\n',iter);break;endend% 恢复最优状态并解码solver.hopfield_net.state=best_state;[best_tour,best_distance]=decode_solution(solver);convergence_info.energy=convergence_info.energy(1:iter);convergence_info.validity=convergence_info.validity(1:iter);endfunction[is_valid,tour_length]=check_solution_validity(solver)% 检查当前网络状态是否表示有效的TSP解% 有效解条件: 每行恰好一个1，每列恰好一个1% 将网络状态重塑为城市×位置的矩阵state_matrix=reshape(solver.hopfield_net.state,...solver.num_cities,solver.num_cities);% 二值化处理binary_matrix=state_matrix>0.5;% 检查行约束 (每个城市只访问一次)row_sums=sum(binary_matrix,2);row_valid=all(row_sums==1);% 检查列约束 (每个位置只有一个城市)col_sums=sum(binary_matrix,1);col_valid=all(col_sums==1);is_valid=row_valid&&col_valid;% 如果有效，计算路径长度ifis_valid tour=decode_tour_from_matrix(binary_matrix);tour_length=compute_tour_length(tour,solver.distance_matrix);elsetour_length=inf;endendfunction[tour,distance]=decode_solution(solver)% 从网络状态解码TSP路径state_matrix=reshape(solver.hopfield_net.state,...solver.num_cities,solver.num_cities);% 方法1: 直接取最大值[~,tour]=max(state_matrix,[],2);% 验证tour是否包含所有城市iflength(unique(tour))~=solver.num_cities% 方法2: 使用匈牙利算法处理有冲突的情况tour=resolve_conflicts(state_matrix);enddistance=compute_tour_length(tour,solver.distance_matrix);endfunctiontour=resolve_conflicts(state_matrix)% 使用类似匈牙利算法的方法解决冲突[num_cities,~]=size(state_matrix);% 复制状态矩阵assignment_matrix=state_matrix;tour=zeros(num_cities,1);forstep=1:num_cities% 找到最大值[max_val,max_idx]=max(assignment_matrix(:));ifmax_val<=0break;end[city,position]=ind2sub(size(assignment_matrix),max_idx);% 分配tour(city)=position;% 清除该行和该列assignment_matrix(city,:)=0;assignment_matrix(:,position)=0;end% 处理未分配的城市unassigned=find(tour==0);available_positions=setdiff(1:num_cities,tour(tour>0));fori=1:length(unassigned)ifi<=length(available_positions)tour(unassigned(i))=available_positions(i);else% 随机分配剩余位置tour(unassigned(i))=randi(num_cities);endendendfunctiontour_length=compute_tour_length(tour,distance_matrix)% 计算路径长度num_cities=length(tour);tour_length=0;fori=1:num_cities from_city=tour(i);to_city=tour(mod(i,num_cities)+1);tour_length=tour_length+distance_matrix(from_city,to_city);endendfunctionconverged=check_convergence(energy_history,current_iter)% 检查能量是否收敛ifcurrent_iter<20converged=false;return;endwindow_size=min(10,current_iter);recent_energies=energy_history(current_iter-window_size+1:current_iter);energy_std=std(recent_energies);converged=energy_std<1e-6;end

完整的TSP求解示例

% 主程序：使用Hopfield网络解决TSP问题clear;clc;%% 生成测试数据rng(42);% 设置随机种子% 生成随机城市坐标num_cities=10;city_positions=100*rand(num_cities,2);fprintf('生成 %d 个城市的TSP问题\n',num_cities);%% 设置Hopfield网络参数% 能量函数权重系数（需要仔细调整）A=500;% 行约束权重B=500;% 列约束权重C=200;% 路径长度权重D=200;% 全局约束权重% 创建TSP求解器tsp_solver=TSPHopfieldSolver(city_positions,A,B,C,D);%% 设置模拟退火计划% 温度衰减函数cooling_schedule=@(iter)max(0.01,1.0*exp(-iter/500));%% 求解TSP问题max_iterations=2000;fprintf('开始Hopfield网络优化...\n');[best_tour,best_distance,convergence_info]=solve_tsp_hopfield(...tsp_solver,max_iterations,cooling_schedule);fprintf('优化完成！\n');fprintf('最优路径长度: %.2f\n',best_distance);%% 可视化结果figure('Position',[100,100,1200,400]);% 子图1: 城市分布和最优路径subplot(1,3,1);plot(city_positions(:,1),city_positions(:,2),'o','MarkerSize',8,...'MarkerFaceColor','red','MarkerEdgeColor','black');hold on;% 绘制路径tour_positions=city_positions(best_tour,:);tour_positions=[tour_positions;tour_positions(1,:)];% 回到起点plot(tour_positions(:,1),tour_positions(:,2),'b-','LineWidth',2);% 标注城市编号fori=1:num_citiestext(city_positions(i,1)+2,city_positions(i,2)+2,...sprintf('%d',i),'FontSize',10,'FontWeight','bold');endtitle(sprintf('TSP最优路径 (长度: %.2f)',best_distance));xlabel('X坐标');ylabel('Y坐标');grid on;axis equal;% 子图2: 能量函数收敛过程subplot(1,3,2);plot(convergence_info.energy,'LineWidth',2);xlabel('迭代次数');ylabel('能量函数值');title('Hopfield网络能量收敛');grid on;% 子图3: 解的有效性subplot(1,3,3);plot(convergence_info.validity,'LineWidth',2);xlabel('迭代次数');ylabel('解的有效性 (1=有效)');title('解的有效性演化');ylim([-0.1,1.1]);grid on;%% 参数敏感性分析fprintf('\n=== 参数敏感性分析 ===\n');% 测试不同的权重组合weight_combinations=[500,500,200,200;% 基准800,800,100,100;% 强约束，弱路径200,200,500,500;% 弱约束，强路径600,600,300,300% 平衡];results=cell(size(weight_combinations,1),1);fori=1:size(weight_combinations,1)weights=weight_combinations(i,:);fprintf('测试权重组合 %d: A=%.0f, B=%.0f, C=%.0f, D=%.0f\n',...i,weights(1),weights(2),weights(3),weights(4));test_solver=TSPHopfieldSolver(city_positions,...weights(1),weights(2),weights(3),weights(4));[test_tour,test_distance,~]=solve_tsp_hopfield(...test_solver,1000,cooling_schedule);results{i}=struct(...'weights',weights,...'tour',test_tour,...'distance',test_distance);fprintf(' 路径长度: %.2f\n',test_distance);end%% 与传统算法比较fprintf('\n=== 与最近邻算法比较 ===\n');% 最近邻算法nn_tour=nearest_neighbor_tsp(city_positions,tsp_solver.distance_matrix);nn_distance=compute_tour_length(nn_tour,tsp_solver.distance_matrix);fprintf('最近邻算法路径长度: %.2f\n',nn_distance);fprintf('Hopfield网络改进: %.2f%%\n',...(nn_distance-best_distance)/nn_distance*100);functiontour=nearest_neighbor_tsp(city_positions,distance_matrix)% 最近邻算法求解TSPnum_cities=size(city_positions,1);unvisited=true(num_cities,1);tour=zeros(num_cities,1);% 从随机城市开始current_city=randi(num_cities);tour(1)=current_city;unvisited(current_city)=false;fori=2:num_cities% 找到最近的未访问城市distances=distance_matrix(current_city,:);distances(~unvisited)=inf;[~,nearest_city]=min(distances);tour(i)=nearest_city;unvisited(nearest_city)=false;current_city=nearest_city;endend

高级改进技术

1. 自适应参数调整

functionadaptive_weights=adaptive_weight_adjustment(solver,validity_history)% 根据解的有效性自适应调整权重recent_validity=validity_history(end-min(10,length(validity_history))+1:end);validity_rate=mean(recent_validity);ifvalidity_rate<0.3% 提高约束权重adaptive_weights.A=solver.A*1.2;adaptive_weights.B=solver.B*1.2;adaptive_weights.C=solver.C*0.9;elseifvalidity_rate>0.8% 提高路径优化权重adaptive_weights.A=solver.A*0.9;adaptive_weights.B=solver.B*0.9;adaptive_weights.C=solver.C*1.2;elseadaptive_weights.A=solver.A;adaptive_weights.B=solver.B;adaptive_weights.C=solver.C;endadaptive_weights.D=solver.D;end

2. 多起点优化

function[global_best_tour,global_best_distance]=multi_start_hopfield_tsp(city_positions,num_starts)% 多起点Hopfield网络优化global_best_distance=inf;global_best_tour=[];forstart=1:num_startsfprintf('多起点优化: %d/%d\n',start,num_starts);% 每次使用不同的随机初始化solver=TSPHopfieldSolver(city_positions,500,500,200,200);solver.initialize_network(0.2*start);% 不同的噪声水平[tour,distance,~]=solve_tsp_hopfield(solver,1000);ifdistance<global_best_distance global_best_distance=distance;global_best_tour=tour;fprintf('发现更好解: %.2f\n',distance);endendend