? ? ? ? 大家好，我是帶我去滑雪！

? ? ? ? 利用神經(jīng)網(wǎng)絡(luò)解決組合優(yōu)化問(wèn)題是神經(jīng)網(wǎng)絡(luò)應(yīng)用的一個(gè)重要方面。所謂組合優(yōu)化問(wèn)題，就是在給定約束條件下，使目標(biāo)函數(shù)極小（或極大）的變量組合問(wèn)題。將Hopfield網(wǎng)絡(luò)應(yīng)用于求解組合優(yōu)化問(wèn)題，把目標(biāo)函數(shù)轉(zhuǎn)化為網(wǎng)絡(luò)的能量函數(shù)，把問(wèn)題的變量對(duì)應(yīng)到網(wǎng)絡(luò)的狀態(tài)，這樣，當(dāng)網(wǎng)絡(luò)的能量函數(shù)收斂于極小值時(shí)，問(wèn)題的最優(yōu)解也隨之求出。由于神經(jīng)網(wǎng)絡(luò)是并行計(jì)算的，其計(jì)算量不隨維數(shù)的增加而發(fā)生指數(shù)性“爆炸”，因而對(duì)于組合優(yōu)化問(wèn)題的高速計(jì)算特別有效。典型的組合優(yōu)化問(wèn)題有旅行商問(wèn)題、0-1背包問(wèn)題、裝箱問(wèn)題、圖著色問(wèn)題、聚類問(wèn)題等問(wèn)題。這些問(wèn)題的描述都非常簡(jiǎn)單，但優(yōu)化求解很困難，其主要原因是求解這些問(wèn)題的算法運(yùn)行時(shí)，需要極長(zhǎng)的運(yùn)行時(shí)間和極大的存儲(chǔ)空間。

? ? ? ? 本期使用連續(xù)Hopfield神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)旅行商問(wèn)題優(yōu)化計(jì)算。

一、問(wèn)題與模型設(shè)計(jì)?

（1）問(wèn)題描述

? ? ? ?旅行商問(wèn)題，（Traveling Saleman Problem，TSP）是VRP的特例，由于Gaery[1]已證明TSP問(wèn)題是NP難題，因此，VRP也屬于NP難題。旅行商問(wèn)題（TSP）又譯為旅行推銷(xiāo)員問(wèn)題、貨郎擔(dān)問(wèn)題，簡(jiǎn)稱為T(mén)SP問(wèn)題，是最基本的路線問(wèn)題，該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過(guò)所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。

? ? ? ? 現(xiàn)對(duì)于一個(gè)城市數(shù)量為10的TSP問(wèn)題，要求設(shè)計(jì)一個(gè)可以對(duì)其組合優(yōu)化的連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)模型，利用改模型可以快速地找到最優(yōu)（或者近似最優(yōu)）的一條路線。

（2）模型建立思路

? ? ? ? 由于連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)具有優(yōu)化計(jì)算的特性，因此將TSP問(wèn)題的目標(biāo)函數(shù)（即最短路徑）與網(wǎng)絡(luò)的能量函數(shù)相對(duì)應(yīng)，將經(jīng)過(guò)的城市順序與網(wǎng)絡(luò)的神經(jīng)元狀態(tài)相對(duì)應(yīng)。這樣，由連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性定理知，當(dāng)網(wǎng)絡(luò)的能量函數(shù)趨于最小值時(shí)，網(wǎng)絡(luò)的神經(jīng)元狀態(tài)也趨于平衡點(diǎn)，此時(shí)對(duì)應(yīng)的城市順序即為最佳的路線。

（3）設(shè)計(jì)步驟

? ? ? ?模型映射：為了將TSP問(wèn)題映射為一個(gè)神經(jīng)網(wǎng)絡(luò)的動(dòng)態(tài)過(guò)程，Hopfield神經(jīng)網(wǎng)絡(luò)采取換位矩陣的表示方式，用NxN的矩陣表示商人訪問(wèn)N個(gè)城市。對(duì)于N個(gè)城市TSP問(wèn)題，使用NxN個(gè)神經(jīng)元來(lái)實(shí)現(xiàn)，而每行每列只能有一個(gè)1，其余都是0，矩陣中1的和為N，該矩陣成為換位矩陣。

? ? ? ??構(gòu)造網(wǎng)絡(luò)能量函數(shù)和動(dòng)態(tài)方程：設(shè)計(jì)的Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)與目標(biāo)函數(shù)（即最短路徑）相對(duì)應(yīng)的。同時(shí)，考慮到有效解的實(shí)際意義，即換位矩陣的每行每列都只能有一個(gè)1。因此，網(wǎng)絡(luò)的能量函數(shù)包含目標(biāo)項(xiàng)和約束項(xiàng)兩部分。

? ? ? ??初始化網(wǎng)絡(luò)：Hopfield神經(jīng)網(wǎng)絡(luò)迭代過(guò)程對(duì)網(wǎng)絡(luò)的能量函數(shù)及動(dòng)態(tài)方程的系數(shù)十分敏感，在總結(jié)前人經(jīng)驗(yàn)及多次實(shí)驗(yàn)的基礎(chǔ)上，網(wǎng)絡(luò)輸入初始化選取如下：A=200，D=100，采樣時(shí)間設(shè)置為0.0001，迭代次數(shù)為10000。

? ? ? ?優(yōu)化計(jì)算：當(dāng)網(wǎng)絡(luò)的結(jié)果及參數(shù)設(shè)計(jì)完成后，迭代優(yōu)化計(jì)算的過(guò)程就變得非常簡(jiǎn)單，具體步驟：

步驟1：導(dǎo)入N個(gè)城市的位置坐標(biāo)并計(jì)算城市之間的距離；

步驟2：網(wǎng)絡(luò)初始化；

步驟3：計(jì)算能量函數(shù)；

步驟4：判斷迭代次數(shù)是否結(jié)束，若迭代次數(shù)大于10000，則終止。

二、代碼實(shí)現(xiàn)

（1）清空環(huán)境變量、聲明全局變量

clear all
clc
global A D

（2）城市位置導(dǎo)入并計(jì)算城市間距離

load city_location
distance = dist(citys,citys');

（3）初始化網(wǎng)絡(luò)

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);

?（4）尋優(yōu)迭代

? ? ? ? 尋優(yōu)迭代過(guò)程包括動(dòng)態(tài)方程計(jì)算、輸入神經(jīng)元狀態(tài)更新、輸出神經(jīng)元狀態(tài)更新、能量函數(shù)計(jì)算四個(gè)步驟。?

for k = 1:iter_num  dU = diff_u(V,distance);U = U + dU*step;V = (1 + tansig(U/U0))/2;e = energy(V,distance);E(k) = e;  
end

（5）動(dòng)態(tài)方程計(jì)算

function du=diff_u(V,d)
global A D
n=size(V,1);
sum_x=repmat(sum(V,2)-1,1,n);
sum_i=repmat(sum(V,1)-1,n,1);
V_temp=V(:,2:n);
V_temp=[V_temp V(:,1)];
sum_d=d*V_temp;
du=-A*sum_x-A*sum_i-D*sum_d;

（6）能量函數(shù)計(jì)算

function E=energy(V,d)
global A D
n=size(V,1);
sum_x=sumsqr(sum(V,2)-1);
sum_i=sumsqr(sum(V,1)-1);
V_temp=V(:,2:n);
V_temp=[V_temp V(:,1)];
sum_d=d*V_temp;
sum_d=sum(sum(V.*sum_d));
E=0.5*(A*sum_x+A*sum_i+D*sum_d);

（7）主函數(shù)

[rows,cols] = size(V);
V1 = zeros(rows,cols);
[V_max,V_ind] = max(V);
for j = 1:colsV1(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));%% 結(jié)果顯示
if flag == 1% 計(jì)算初始路徑長(zhǎng)度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)])endtext(citys_rand(1,1),citys_rand(1,2),['       起點(diǎn)' ])text(citys_rand(end,1),citys_rand(end,2),['       終點(diǎn)' ])title(['優(yōu)化前路徑(長(zhǎng)度：' num2str(Length_init) ')'])axis([0 1 0 1])grid onxlabel('城市位置橫坐標(biāo)')ylabel('城市位置縱坐標(biāo)')% 計(jì)算最優(yōu)路徑長(zhǎng)度[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,:)');enddisp('最優(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)])endtext(citys_end(1,1),citys_end(1,2),['       起點(diǎn)' ])text(citys_end(end,1),citys_end(end,2),['       終點(diǎn)' ])title(['優(yōu)化后路徑(長(zhǎng)度：' num2str(Length_end) ')'])axis([0 1 0 1])grid onxlabel('城市位置橫坐標(biāo)')ylabel('城市位置縱坐標(biāo)')% 繪制能量函數(shù)變化曲線figure(3)plot(1:iter_num,E);ylim([0 2000])title(['能量函數(shù)變化曲線(最優(yōu)能量：' num2str(E(end)) ')']);xlabel('迭代次數(shù)');ylabel('能量函數(shù)');
elsedisp('尋優(yōu)路徑無(wú)效');
end

（8）結(jié)果輸出

? ? ? ?優(yōu)化前的路徑：

? ? ? 優(yōu)化后的路徑圖：

? ? ? 優(yōu)化后的路徑距離相比于沒(méi)有優(yōu)化的路徑距離更短。

? ? ? 能量函數(shù)變化曲線：

? ? ? ?結(jié)果表明：利用Hopfield神經(jīng)網(wǎng)絡(luò)?，可以快速準(zhǔn)確地解決TSP問(wèn)題。同理，對(duì)于其他利用枚舉法會(huì)產(chǎn)生“組合爆炸”的組合優(yōu)化問(wèn)題，利用連續(xù)型Hopfield神經(jīng)網(wǎng)絡(luò)也可以進(jìn)行優(yōu)化計(jì)算。

需要數(shù)據(jù)集的家人們可以去百度網(wǎng)盤(pán)（永久有效）獲取：

鏈接：
提取碼：2138?

---

更多優(yōu)質(zhì)內(nèi)容持續(xù)發(fā)布中，請(qǐng)移步主頁(yè)查看。

? ?點(diǎn)贊+關(guān)注,下次不迷路！