Что не так с моим решением Hopfield Neural Network для задачи коммивояжера? - PullRequest
Новая
       371

Что не так с моим решением Hopfield Neural Network для задачи коммивояжера?

12 голосов
/ 01 декабря 2010

Во-первых, это домашнее задание. Я думаю, ясно, что я сделал усилие, и я ищу подсказки, а не код.

Проблема заключается в следующем. Уравнение действия имеет четыре компонента для изменения данного нейрона.

  • А) Одна часть, гарантирующая посещение каждого города не более одного раза.
  • B) Один, чтобы каждая позиция (первая, вторая, третья и т. Д.) Имела не более одного города.
  • C) Одна часть, чтобы гарантировать, что общее количество активных нейронов равно количеству городов.
  • D) Одна часть, чтобы минимизировать расстояние.

Если я достаточно сильно нагружу D, чтобы это оказало какое-либо влияние, сеть рассчитывает на недопустимый обход (например, посещение A, D, никуда, E, C). Я могу, однако, уменьшить вес D, и код найдет решения, но не те, которые имеют минимальное расстояние.

Буду чрезвычайно признателен за любой совет, некоторое время я бился головой о клавиатуру. Код должен быть понятен любому, кто знаком с решением TSP с сетью Хопфилда.

Код Das: 

%parameters
n=5;
theta = .5;
u0 = 0.02;
h = .1;
limit = 2000;

%init u
u=zeros(n,n);
uinit = -u0/2*log(n-1); %p94 uINIT = - u0/2 * ln(n-1) 
for i=1:n
    for j=1:n
        u(i,j) = uinit * (1+rand()*0.2-0.1); %add noise [-0.1*uInit 0.1*uINIT]
    end
end 

%loop
for index=1:limit
    i = ceil(rand()*n);
    k = ceil(rand()*n);

    %runge kutta
    k1 = h*du(u,i,k,0);
    k2 = h*du(u,i,k, k1/2);
    k3 = h*du(u,i,k, k2/2);
    k4 = h*du(u,i,k, k3);
    u(i,k) = u(i,k) + (k1 + 2*k2 + 2*k3 + k4)/6;
end

Vfinal = hardlim(V(u)-theta)

ди () 

function  out=du(u,X,i,c)

dist = [0, 41, 45, 32, 32;
        41, 0, 36, 64, 54;
        45, 36, 0, 76, 32;
        32, 64, 76, 0, 60;
        32, 54, 32, 60, 0];

t = 1;
n = 5;
A = 10;
B = 10;
C = 10;
D = .0001;


AComp = A*sum(V(u(X,:))) - A*V(u(X,i));
BComp = B*sum(V(u(:,i))) - B*V(u(X,i));
CComp = C*(sum(sum(V(u)))-n);

DComp = 0;
before = i-1;
after = i+1;
if before == 0
    before = 5;
end
if after == 6
    after = 1;
end
for Y=1:5
    DComp = DComp + dist(X,Y) * (V(u(Y,after)) + V(u(Y,before)));
end
DComp = DComp * D;

out = -1*(u(X,i)+c)/t - AComp - BComp - CComp - DComp;

В () * +1031 * 

function  out=V(u)
u0 = 0.02;
out = (1 + tanh(u/u0))/2;

1 Ответ

4 голосов
/ 30 января 2011

Я никогда не пытался решить TSP с помощью нейронной сети, но я обнаружил, что он решает очень хорошо и очень быстро, используя генетический подход.

Я сделал много проектов нейронных сетей, и я бы предположил, что, поскольку TSP, как правило, может иметь много решений в одной сети (городов), нейронную сеть можно перетаскивать между решениями никогда по-настоящему успешно не сходится ни на одном.

Джон Р. Донер

...