組合優(yōu)化問題的目標是從組合問題的可行解集中求出最優(yōu)解，組合優(yōu)化往往涉及排序，分類篩選等問題，是運籌學的一個重要分支，典型的組合優(yōu)化問題，有旅行商問題，加工調(diào)度問題，背包問題裝箱問題，圖著色問題，聚類問題等，這些問題描述非常簡單，并且有很強的工程代表性，但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法運行時需要極長的運行時間與極大的存儲空間，以致根本不可能在現(xiàn)有的計算機上實現(xiàn)，就會產(chǎn)生所謂的“組合爆炸”問題。

利用神經(jīng)網(wǎng)絡解決組合優(yōu)化問題，是神經(jīng)網(wǎng)絡應用的一個重要方面，將Hopfield網(wǎng)絡應用于求解組合優(yōu)化問題，將目標函數(shù)轉(zhuǎn)化為網(wǎng)絡的能量函數(shù)，把問題的變量對應到網(wǎng)絡的神經(jīng)元的狀態(tài)，這樣當網(wǎng)絡的能量函數(shù)收斂于極小值時，問題的最優(yōu)解也隨之求出，由于神經(jīng)網(wǎng)絡是并行計算的，其計算量不會隨著維數(shù)的增加而發(fā)生指數(shù)型“爆炸”，因而對于優(yōu)化問題的告訴就算特別有效。

%% 清空環(huán)境變量、定義全局變量

clear 

clc

global A D

%% 導入城市位置

load city_location

%% 計算相互城市間距離

distance=dist(citys,citys');

%% 初始化網(wǎng)絡

N=size(citys,1);

A=200;

D=100;

U0=0.1;

step=0.0001;

delta=2*rand(N,N)-1;

U=U0*log(N-1)+delta;

V=(1+tansig(U/U0))/2;

iter_num=10000;

E=zeros(1,iter_num);

%% 尋優(yōu)迭代

for k=1:iter_num  

    % 動態(tài)方程計算

    dU=diff_u(V,distance);

    % 輸入神經(jīng)元狀態(tài)更新

    U=U+dU*step;

    % 輸出神經(jīng)元狀態(tài)更新

    V=(1+tansig(U/U0))/2;

    % 能量函數(shù)計算

    e=energy(V,distance);

    E(k)=e;  

end

 %% 判斷路徑有效性

[rows,cols]=size(V);

V1=zeros(rows,cols);

[V_max,V_ind]=max(V);

for j=1:cols

    V1(V_ind(j),j)=1;

end

C=sum(V1,1);

R=sum(V1,2);

flag=isequal(C,ones(1,N)) & isequal(R',ones(1,N));

%% 結果顯示

if flag==1

   % 計算初始路徑長度

   sort_rand=randperm(N);

   citys_rand=citys(sort_rand,:);

   Length_init=dist(citys_rand(1,:),citys_rand(end,:)');

   for i=2:size(citys_rand,1)

       Length_init=Length_init+dist(citys_rand(i-1,:),citys_rand(i,:)');

   end

   % 繪制初始路徑

   figure(1)

   plot([citys_rand(:,1);citys_rand(1,1)],[citys_rand(:,2);citys_rand(1,2)],'o-')

   for i=1:length(citys)

       text(citys(i,1),citys(i,2),['   ' num2str(i)])

   end

   text(citys_rand(1,1),citys_rand(1,2),['       起點' ])

   text(citys_rand(end,1),citys_rand(end,2),['       終點' ])

   title(['優(yōu)化前路徑(長度：' num2str(Length_init) ')'])

   axis([0 1 0 1])

   grid on

   xlabel('城市位置橫坐標')

   ylabel('城市位置縱坐標')

   % 計算最優(yōu)路徑長度

   [V1_max,V1_ind]=max(V1);

   citys_end=citys(V1_ind,:);

   Length_end=dist(citys_end(1,:),citys_end(end,:)');

   for i=2:size(citys_end,1)

       Length_end=Length_end+dist(citys_end(i-1,:),citys_end(i,:)');

   end

   disp('最優(yōu)路徑矩陣');V1

   % 繪制最優(yōu)路徑

   figure(2)

   plot([citys_end(:,1);citys_end(1,1)],...

       [citys_end(:,2);citys_end(1,2)],'o-')

   for i=1:length(citys)

       text(citys(i,1),citys(i,2),['  ' num2str(i)])

   end

   text(citys_end(1,1),citys_end(1,2),['       起點' ])

   text(citys_end(end,1),citys_end(end,2),['       終點' ])

   title(['優(yōu)化后路徑(長度：' num2str(Length_end) ')'])

   axis([0 1 0 1])

   grid on

   xlabel('城市位置橫坐標')

   ylabel('城市位置縱坐標')

   % 繪制能量函數(shù)變化曲線

   figure(3)

   plot(1:iter_num,E);

   ylim([0 2000])

   title(['能量函數(shù)變化曲線(最優(yōu)能量：' num2str(E(end)) ')']);

   xlabel('迭代次數(shù)');

   ylabel('能量函數(shù)');

else

   disp('尋優(yōu)路徑無效');

end