Решение задачи коммивояжера с использование нейронной сети Хопфилда

20 Сен
2011

В ходе своей работы столкнулся с необходимостью решения задачи маршрутизации в телекоммуникационной сети с использованием нейронной сети Хопфилда.
Самым главным условием была практическая реализация для проведения экспериментов и исследований.
Как всегда начал с анализа того, что уже есть в интернете.
Есть достаточно большое количество работ по этой теме. Список литературы приведен ниже.
Но практически нигде нет понятных алгоритмов их решения. Вот тогда я и начал отталкиваться от «классической» статьи «Neural» Computation of Decisions in Optimization Problems J. J. Hopfield and D. W. Tank.

Потом была попытка поискать готовые решения в сети. Оказалось что задача очень интересная и существуют множество готовых решений. Было только одно ограничение с моей стороны это использование готового кода для MATLAB.
В результате поисков нашел отличный сайт для студентов и не очень талантливых программистов (типа меня) где можно найти множество идей и их реализаций на различных языках программирования. Именно там я и нашел исходник для решения задачи коммивояжера, который реализовывал идею Хопфилда описанную в его статье и именно на MATLABе.
Задача о коммивояжере формулируется следующим образом:
Пусть имеется n городов соединенных между собой дорогами различной длины. Необходимо выйти из начального города обойти все города по одному разу и вернуться в начальный город. Путь должен быть минимальной длины.
Вроде бы все просто. И в принципе, существует много методов решения данной задачи. Однако часто эти задачи требуют большого числа вычислений которые увеличиваются с ростом количества городов. Хопфилд предложил интересный метод решения с приемлемой вычислительной сложностью и достаточной точностью вычислений.
Найденный исходник снабжен файлом-описанием на китайском. Поэтому мной было потрачено значительное количество времени на перевод описания и разбор программы. Исходный листинг приведен ниже с моими комментариями.
%function myTSP1
%задается количество вершин (городов)
N=10;
%координаты городов
cityx=[0.4,0.2439,0.1707,0.2293,0.5171,0.8732,0.6878,0.8488,0.6683,0.6195,0.9125];
cityy=[0.4439,0.1463,0.2293,0.761,0.9414,0.6536,0.5219,0.3609,0.2536,0.2634, 0.9568];
plot(cityx,cityy,’r*’);
for i=1:1:N
for j=1:1:N
d(i,j)=sqrt((cityx(i)-cityx(j))^2+(cityy(i)-cityy(j))^2);
end
end
%константы решения
%для одного в столбце
A=500;
%для одного в строке
B=500;
%для одного маршрута
C=1000;
%для минимизации цены маршрута
D=500;
%пераметр расчета функции активации (в статье мю)
u0=0.02;
tao=1;
%шаг пересчета
lamda=0.0001;
%поиск маршрутов
%получение статистики результатов
%подсчет числа циклов расчетов
total=0;
%признак конца расчета
toend=0;
time=clock;
display([‘текущее время ‘,num2str(time(1,4:6))])
while toend==0
total=total+1;
total
% V
tic
%инициализация массива функций передачи нейрона
V=rand(N,N);
%инициализация массива значений весов связей между нейронами
U=atanh(2*V-1)*u0;
%расчет сети
for renew=1:1:1000
%пересчет значений для частей функции оптимизации
for ux=1:1:N
for ui=1:1:N
m1=0;
m2=0;
m3=0;
m4=0;
%первая часть функции оптимизации (в каждой строке 1
%город)
for j=1:1:N
if j~=ui
m1=m1+V(ux,j);
end
end
m1=-A*m1;
%вторая часть функции оптимизации (в каждом столбце 1
%город)
for y=1:1:N
if y~=ux
m2=m2+V(y,ui);
end
end
m2=-B*m2;
%третья часть функции оптимизации (один маршрут)
for x=1:1:N
for j=1:1:N
m3=m3+V(x,j);
end
end
m3=-C*(m3-N);
%четвертая часть функции оптимизации (минимизация длины
%«стоимости»
%пути)
for y=1:1:N
if y~=ux
if ui==1
m4=m4+d(ux,y)*(V(y,ui+1)+V(y,N));
elseif ui==N
m4=m4+d(ux,y)*(V(y,ui-1)+V(y,1));
else
m4=m4+d(ux,y)*(V(y,ui+1)+V(y,ui-1));
end
end
end
m4=-D*m4;
Udao(ux,ui)=-U(ux,ui)+m1+m2+m3+m4;
end
end
%пересчет весов связей
U=U+lamda*Udao;
%расчет выходных значений передаточной функции нейрона
V=(1+tanh(U/u0))/2;
%пересчет еще раз выходов нейронов (повторное предъявление)
for ux=1:1:N
for ui=1:1:N
if V(ux,ui)<0.3
V(ux,ui)=0;
end
if V(ux,ui)>0.7
V(ux,ui)=1;
end
end
end
end
%вывод промежуточного результата
V
%тестирование, проверка результатов
%Подсчет общего числа едениц в матрице
test1=0;
for ux=1:1:N
for ui=1:1:N
test1=test1+V(ux,ui);
end
end
%проверка в каждой строке один город
test2=0;
for x=1:1:N
for i=1:1:N-1
for j=i+1:1:N
test2=test2+V(x,i)*V(x,j);
end
end
end
%проверка в каждом столбце один город
test3=0;
for i=1:1:N
for x=1:1:N-1
for y=x+1:1:N
test3=test3+V(x,i)*V(y,i);
end
end
end
%проверка всех условий тестирования (проверки) матрицы
if test1==N && test2==0 && test3==0
toend = 1;
else
toend=0;
end
end
toc
time=clock;
display([‘конечное время ‘,num2str(time(1,4:6))])
V
total
%пересчет координат городов в порядке их следования
for j=1:1:N
for i=1:1:N
if V(i,j)==1
cityx_final(j)=cityx(i);
cityy_final(j)=cityy(i);
end
end
end
cityx_final(N+1)=cityx_final(1);
cityy_final(N+1)=cityy_final(1);
cityx_final;
cityy_final;
%отображение городов и маршрута
td=0;
for i=1:1:N-1
td=td+sqrt((cityx_final(i)-cityx_final(i+1))^2+(cityy_final(i)-cityy_final(i+1))^2);
end
td=td+sqrt((cityx_final(N)-cityx_final(1))^2+(cityy_final(N)-cityy_final(1))^2);
td
plot(cityx_final,cityy_final,’o-‘);
Количество операций 200
ряд существующих решений 29
Количество оптимальных решений 1
Оптимальное решение (общая протяженность маршрута) 2.6907
Количество суб-оптимальных решений 1
Второе-лучшее решение (общая протяженность маршрута) 2.7693
Оптимальное решение (общая протяженность маршрута) 2.7782
Оптимальное решение (общая протяженность маршрута) 2.8352
среднее время, необходимое для поиска маршрута (s) 0.8813
Это послужило основой для разработки тестовой программы для подбора коэффициентов для оптимизационной функции из статьи Хопфилда и послужило основой для дальнейшего поиска решения задачи маршрутизации с использованием сети Хопфилда, над решением данной задачи я сейчас и тружусь. Вроде и статьи есть а решение не сходится. Буду рад любым комментариям и идеям.
Список литературы
1. Хайкин С. Нейронные сети: полный курс. Издание 2.: Пер. с англ. –М.: Издательский дом «Вильямс», 2006. – 1104 с.
2. Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities// Proceedings of National Academy of Sciences. -1982. — Vol.79, No. 8. P. 2554–2558.
3. Kojić N. S., Zajeganović-Ivančić M.B., Reljin I.S., Reljin B.D. New algorithm for packet routing in mobile ad-hoc networks //Journal of Automatic Control. – 2010. -Vol.20. — No.1. — P.9-16.
4. Schuler W.H., Bastos-Filho C.J.A., Oliveira A.L.I. A novel hybrid training method for hopfield neural networks applied to routing in communications networks //International Journal of Hybrid Intelligent Systems.- 2009. – Vol.6.- No.1. –P.27-39.
5. Терехов В. А., Ефимов Д. В., Тюкин И. Ю. Нейросетевые системы управле-ния. — 1-е. — Высшая школа, 2002. — С. 184.
По материалам Хабрахабр.



загрузка...

Комментарии:

Наверх