Otimização usando a rede Hopfield
Otimização é uma ação de tornar algo como design, situação, recurso e sistema o mais eficaz possível. Usando uma semelhança entre a função de custo e a função de energia, podemos usar neurônios altamente interconectados para resolver problemas de otimização. Esse tipo de rede neural é a rede de Hopfield, que consiste em uma única camada contendo um ou mais neurônios recorrentes totalmente conectados. Isso pode ser usado para otimização.
Pontos a serem lembrados ao usar a rede Hopfield para otimização -
A função de energia deve ser mínima da rede.
Ele encontrará uma solução satisfatória em vez de selecionar um dos padrões armazenados.
A qualidade da solução encontrada pela rede Hopfield depende significativamente do estado inicial da rede.
Problema do caixeiro viajante
Encontrar o caminho mais curto percorrido pelo vendedor é um dos problemas computacionais, que pode ser otimizado usando a rede neural de Hopfield.
Conceito Básico de TSP
O Problema do Caixeiro Viajante (TSP) é um problema clássico de otimização em que um vendedor tem que viajar ncidades, que estão conectadas entre si, mantendo o custo e a distância percorrida mínimos. Por exemplo, o vendedor tem que percorrer um conjunto de 4 cidades A, B, C, D e o objetivo é encontrar o trajeto circular mais curto, ABC-D, de forma a minimizar o custo, que inclui também o custo da viagem de a última cidade D para a primeira cidade A.
Representação de Matriz
Na verdade, cada passeio do TSP de n-cidades pode ser expresso como n × n matriz de quem ith linha descreve o ithlocalização da cidade. Esta matriz,M, para 4 cidades A, B, C, D pode ser expresso da seguinte forma -
$$ M = \ begin {bmatrix} A: & 1 & 0 & 0 & 0 \\ B: & 0 & 1 & 0 & 0 \\ C: & 0 & 0 & 1 & 0 \\ D: & 0 & 0 e 0 e 1 \ end {bmatrix} $$
Solução da Hopfield Network
Considerando a solução deste TSP pela rede Hopfield, cada nó da rede corresponde a um elemento da matriz.
Cálculo da função de energia
Para ser a solução otimizada, a função de energia deve ser mínima. Com base nas seguintes restrições, podemos calcular a função de energia da seguinte forma -
Restrição-I
A primeira restrição, com base na qual calcularemos a função de energia, é que um elemento deve ser igual a 1 em cada linha da matriz M e outros elementos em cada linha devem ser iguais a 0porque cada cidade pode ocorrer em apenas uma posição no tour do TSP. Esta restrição pode ser matematicamente escrita da seguinte forma -
$$ \ displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j} \: = \: 1 \: para \: x \: \ in \: \ lbrace1, ..., n \ rbrace $ $
Agora, a função de energia a ser minimizada, com base na restrição acima, conterá um termo proporcional a -
$$ \ displaystyle \ sum \ limits_ {x = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {j = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
Restrição-II
Como sabemos, no TSP uma cidade pode ocorrer em qualquer posição no passeio, portanto, em cada coluna da matriz M, um elemento deve ser igual a 1 e os outros elementos devem ser iguais a 0. Esta restrição pode ser matematicamente escrita da seguinte maneira -
$$ \ displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j} \: = \: 1 \: para \: j \: \ in \: \ lbrace1, ..., n \ rbrace $ $
Agora, a função de energia a ser minimizada, com base na restrição acima, conterá um termo proporcional a -
$$ \ displaystyle \ sum \ limits_ {j = 1} ^ n \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {x = 1} ^ n M_ {x, j } \ end {array} \ right) ^ 2 $$
Cálculo da Função de Custo
Vamos supor uma matriz quadrada de (n × n) denotado por C denota a matriz de custo do TSP para n cidades onde n > 0. A seguir estão alguns parâmetros ao calcular a função de custo -
Cx, y - O elemento da matriz de custo denota o custo de viajar da cidade x para y.
A adjacência dos elementos de A e B pode ser mostrada pela seguinte relação -
$$ M_ {x, i} \: = \: 1 \: \: e \: \: M_ {y, i \ pm 1} \: = \: 1 $$
Como sabemos, em Matrix, o valor de saída de cada nó pode ser 0 ou 1, portanto, para cada par de cidades A, B, podemos adicionar os seguintes termos à função de energia -
$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) $$
Com base na função de custo acima e no valor de restrição, a função de energia final E pode ser dado da seguinte forma -
$$ E \: = \: \ frac {1} {2} \ displaystyle \ sum \ limits_ {i = 1} ^ n \ displaystyle \ sum \ limits_ {x} \ displaystyle \ sum \ limits_ {y \ neq x} C_ {x, y} M_ {x, i} (M_ {y, i + 1} \: + \: M_ {y, i-1}) \: + $$
$$ \: \ begin {bmatrix} \ gamma_ {1} \ displaystyle \ sum \ limits_ {x} \ left (\ begin {array} {c} 1 \: - \: \ displaystyle \ sum \ limits_ {i} M_ {x, i} \ end {array} \ right) ^ 2 \: + \: \ gamma_ {2} \ displaystyle \ sum \ limits_ {i} \ left (\ begin {array} {c} 1 \: - \ : \ displaystyle \ sum \ limits_ {x} M_ {x, i} \ end {array} \ right) ^ 2 \ end {bmatrix} $$
Aqui, γ1 e γ2 são duas constantes de pesagem.