Metaheurísticas e Aplicações

Algoritmos, exemplos e aplicações

Esta página contém os algoritmos e exemplos das técnicas mostradas na disciplina Metaheurísticas e Aplicações. Além disso, são mostradas as aplicações destas técnicas em várias áreas da Pesquisa Operacional.

A apostila está disponível no link: apostila de Metaheurísticas

Redes Neurais Artificiais

1. Perceptron

Material das páginas 1 até 16.

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede Neural Perceptron:

0. Inicializar os pesos, o bias e a taxa de aprendizado: w = 0, θ = 0, α = 1 
    1. Enquanto o critério de parada não for satisfeito, execute os passos 2-6:
        2. Para cada par de dados de treinamento (x,d), execute os passos 3-5:
        3. Calcule y* = θ + ∑_ix_iw_i 
        4. Se y* > δ, então y = 1 
            Se -δ ≤ y* ≤ δ, então y = 0
            Se y* < -δ, então y = -1 
        5. Atualize os pesos e a tendência:
            Se y ≠ d, faça
               w_i^atual = w_i^anterior + αdx_i e θ^atual = θ^anterior + αd 
            Caso contrário
               w_i^atual = w_i^anterior e θ^atual = θ^anterior
6. Teste a condição de parada.

voltar ao topo

📃 Resolução

Vamos acompanhar os resultados e as interpretações geométricas deste exercício da Rede Neural Perceptron. Vamos usar entradas e saídas bipolares.

O primeiro padrão (1, 1) é apresentado à rede. Como y ≠ d, então os pesos são atualizados.
Usando os coeficientes de w₁, w₂ e θ que definem as equações das retas usadas para a classificação, temos apenas 1 padrão classificado corretamente.
O segundo padrão (1, -1) é apresentado à rede. Como y ≠ d, então os pesos são atualizados.
Usando os coeficientes de w₁, w₂ e θ que definem as equações das retas usadas para a classificação, temos 2 padrões classificados corretamente.
O terceiro padrão (-1, 1) é apresentado à rede. Como y ≠ d, então os pesos são atualizados. Na apresentação do último padrão, temos que y = d e os valores dos pesos são mantidos.
Usamos a combinação de pesos (w₁ = 1, w₂ = 1, θ = -1) da última apresentação de padrões para calcular o erro. Todos os padrões estão classificados corretamente. Logo, podemos finalizar o processo de aprendizagem desta Rede Neural.

📑 Atividade 1.1

voltar ao topo

📑 Atividade 1.2

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede Neural Perceptron com bolso:

0. Inicializar os pesos, o bias e a taxa de aprendizado: w = 0, w^bolso = 0, θ = 0, α = 1 
    1. Enquanto o critério de parada não for satisfeito, execute os passos 2-7:
        2. Para cada par de dados de treinamento (x,d), execute os passos 3-5:
        3. Calcule y* = θ + ∑_ix_iw_i
        4. Se y* > δ, então y = 1
           Se -δ ≤ y* ≤ δ, então y = 0
           Se y* < -δ, então y = -1 
        5. Atualize os pesos e a tendência:
           Se y ≠ d, faça
             w_i^atual = w_i^anterior + αdx_i e θ^atual = θ^anterior + αd 
           Caso contrário
             w_i^atual = w_i^anterior e θ^atual = θ^anterior
        6. Se w classifica corretamente mais exemplos do que w^bolso:  
             w^bolso = w; grave o número de exemplos corretos 
7. Teste a condição de parada.

Para separar os dados em mais classes, podemos inserir mais neurônios na Rede Neural

voltar ao topo

2. Adaline e Multi Layer Perceptron (MLP)

Material das páginas 16 até 28.

Vamos utilizar a Regra Delta para deduzir as formas de atualizações dos pesos em algumas Redes Neurais. O princípio é sempre de buscar a minimização do erro de classificação de cada Rede Neural Artificial.

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede Neural Adaline:

0. Inicializar os pesos (w = rnd), a tendência (θ = 0)
e a taxa de aprendizagem 0 < α < 1 (convergência fica muito lenta quando a taxa é muito 
próxima de zero; e a convergência não é garantida para valores muito próximos de 1).
    1. Enquanto o critério de parada não for satisfeito, execute os passos 2-5:
        2. Para cada par de dados para treinamento (x,d), execute os passos 3-4:
            3. Faça y* = θ + ∑_ix_iw_i 
            4. Atualize os pesos e a tendência:
                w_i^atual = w_i^anterior + α(d – y*)x_i  
                θ^atual = θ^anterior + α(d – y*)
                se y* ≥ 0, y = 1; caso contrário, y = 0 (ou y = -1 para bipolar)
        5. Teste a condição de parada. 
    6. Se a maior alteração de pesos não ultrapassa um limite mínimo de tolerância, pare; 
	caso contrário, continue.

📃 Resolução

Vamos acompanhar os resultados e as interpretações geométricas deste exercício de classificação de padrões usando a Rede Neural Adaline. Vamos usar entradas e saídas bipolares.

A arquitetura da Rede Neural Adaline fica análoga à arquitetura que usamos no caso do Perceptron. O resumo dos cálculos está mostrado nesta imagem. Vamos iniciar com os pesos indicados de w e θ e a taxa de aprendizagem α.
O primeiro padrão (1, 1) é apresentado à rede, com a atualização automática dos pesos. Note que o termo Δθ é comum na atualização dos pesos w₁ e w₂; logo, podemos aplicar uma simplificação para estes cálculos.
O padrão (1, -1) é apresentado à rede, com a atualização automática dos pesos. Note que a simplificação na atualização dos pesos foi aplicada neste passo para w₁ e w₂.
O padrão (-1, 1) é apresentado à rede, com a atualização automática dos pesos.
O padrão (-1, -1) é apresentado à rede, com a atualização automática dos pesos. Note que a reta com os coeficientes dos pesos classifica todos os padrões corretamente.
Usando a função do cálculo do erro, similar à usada para deduzir a Regra Delta, temos que: E = ∑_k((d_k - y)²)/2 = ((1 - 1)² + (1 - 1)² + (1 - 1)² + (-1 - (-1))²)/2 = 0. O erro quantitativo também fica nulo, logo, podemos finalizar a aprendizagem desta Rede Neural.

voltar ao topo

📑 Atividade 2.1

voltar ao topo

📃 Resolução

Neste caso, o parâmetro β da função sigmoidal é igual a 1.
A derivada da função y_k = tanh(y_k*) com parâmetro β = 1 é y'_k = (1 - y_k²).
Logo, a atualização de pesos w será Δw_jk = α(1 - y_k²)(d_k - y_k)z_j.

voltar ao topo

📃 Resolução

As derivadas das funções y_k = tanh(y_k*) e z_j = tanh(z_j*) com parâmetro β = 1 são:
y'_k = (1 - y_k²) e z'_j = (1 - z_j²).
Logo, a atualização de pesos v será Δv_ij = α∑_k[(d_k - y_k)(1 - y_k²)w_jk](1 - z_j²)x_i.

voltar ao topo

📃 Algoritmo comentado

Algoritmo 1 de Rede Neural MLP: 1 camada escondida, funções de ativação sigmoidais, m saídas

0. Inicialize os pesos das conexões e do bias com valores aleatórios; 
inicialize a taxa de aprendizagem α. Para cada padrão de entrada, execute os passos de 1 a 3:
    1. Calcule as entradas na camada escondida, e a saída da rede:
       z_j* = ∑_iv_ijx_i + θa_j  ⇒  z_j = 1/(1 + e^-z_j*), onde j = 1, ..., p, i = 1, ..., n
       y_k* = ∑_jw_jkz_j + θb_k  ⇒  y_k = 1/(1 + e^-y_k*), onde k = 1, 2, ..., m 
    2. Calcule as correções das conexões da camada de saída:
       △w_jk = αy_k(1 – y_k)(d_k – y_k)z_j  ⇒  w_jk = w_jk + △w_jk 
       △θb_k = αy_k(1 – y_k)(d_k – y_k)  ⇒  θb_k = θb_k + △θb_k 
    3. Calcule as correções das conexões da camada escondida:
       △v_ij = α∑_k[(d_k – y_k)y_k(1 – y_k)w_jk]z_j(1 - z_j)x_i  ⇒  v_ij = v_ij + △v_ij 
       △θa_j = α∑_k[(d_k – y_k)y_k(1 – y_k)w_jk]z_j(1 - z_j)  ⇒  θa_j = θa_j + △θa_j 
    4. Atualize a taxa de aprendizagem, verifique os erros para todos os padrões de entrada, 
    e teste o critério de parada.

📃 Algoritmo comentado

Algoritmo 2 de Rede Neural MLP: 1 camada escondida, funções de ativação sigmoidais, 1 saída

0. Inicialize os pesos das conexões e do bias com valores aleatórios; 
inicialize a taxa de aprendizagem α. Para cada padrão de entrada, execute os passos de 1 a 3:
    1. Calcule as entradas na camada escondida, e a saída da rede:
       z_j* = ∑_iv_ijx_i + θa_j  ⇒  z_j = 1/(1 + e^-z_j*), onde j = 1, ..., p, i = 1, ..., n
       y* = ∑_jw_jz_j + θb  ⇒  y = 1/(1 + e^-y*), onde k = 1, 2, ..., m 
    2. Calcule as correções das conexões da camada de saída:
       △w_j = αy(1 – y)(d – y)z_j  ⇒  w_j = w_j + △w_j 
       △θb = αy(1 – y)(d – y)  ⇒  θb = θb + △θb 
    3. Calcule as correções das conexões da camada escondida:
       △v_ij = α(d – y)y(1 – y)w_jz_j(1 - z_j)x_i  ⇒  v_ij = v_ij + △v_ij 
       △θa_j = α(d – y)y(1 – y)w_jz_j(1 - z_j)  ⇒  θa_j = θa_j + △θa_j 
    4. Atualize a taxa de aprendizagem, verifique os erros para todos os padrões de entrada, 
    e teste o critério de parada.

voltar ao topo

📃 Algoritmo comentado

Algoritmo 1 de Rede Neural MLP: 1 camada escondida, funções de ativação tanh, m saídas

0. Inicialize os pesos das conexões e do bias com valores aleatórios; 
inicialize a taxa de aprendizagem α. Para cada padrão de entrada, execute os passos de 1 a 3:
    1. Calcule as entradas na camada escondida, e a saída da rede:
       z_j* = ∑_iv_ijx_i + θa_j  ⇒  z_j = tanh(z_j*), onde j = 1, ..., p, i = 1, ..., n
       y_k* = ∑_jw_jkz_j + θb_k  ⇒  y_k = tanh(y_k*), onde k = 1, 2, ..., m 
    2. Calcule as correções das conexões da camada de saída:
       △w_jk = α(1 – y_k²)(d_k – y_k)z_j  ⇒  w_jk = w_jk + △w_jk 
       △θb_k = α(1 – y_k²)(d_k – y_k)  ⇒  θb_k = θb_k + △θb_k 
    3. Calcule as correções das conexões da camada escondida:
       △v_ij = α∑_k[(d_k – y_k)(1 – y_k²)w_jk](1 - z_j²)x_i  ⇒  v_ij = v_ij + △v_ij 
       △θa_j = α∑_k[(d_k – y_k)(1 – y_k²)w_jk](1 - z_j²)  ⇒  θa_j = θa_j + △θa_j 
    4. Atualize a taxa de aprendizagem, verifique os erros para todos os padrões de entrada, 
    e teste o critério de parada.

voltar ao topo

📑 Atividade 2.2

voltar ao topo

3. Multi Layer Perceptron (MLP) e aplicações

Material das páginas 29 até 40.

voltar ao topo

📑 Atividade 3.1

voltar ao topo

📑 Atividade 3.2

voltar ao topo

4. Support Vector Machines e Redes de Bases Radiais

Material das páginas 40 até 49.

voltar ao topo

📃 Resolução

Vamos acompanhar os resultados e as interpretações geométricas deste exercício da Rede Support Vector Machine (SVM) para classificação de padrões. A rede deve separar os dados de entrada em duas classes.

Utilizando a função de núcleo (1 + x^Tx), temos o problema de Programação Quadrática apresentado. Os valores de α_i diferentes de zero nos mostram quais serão os vetores suporte: 2, 4 e 6.
Substituindo os valores de x na função de decisão, encontramos a função de 2º grau. A parábola faz a separação dos dados nas classes 1 e 2.

voltar ao topo

📃 Resolução

Vamos acompanhar os resultados e as interpretações geométricas deste exercício de classificação usando a Rede Support Vector Machine (SVM). Os dados devem ser separados em duas classes.

Utilizando a função de núcleo (1 + x^Tx), precisamos desenvolvê-la para inserir os dados de entrada das variáveis x₁ e x₂.
Substituindo os valores de x₁ e x₂ na função de decisão, encontramos os vetores de decisão.
Resolvendo o problema de programação quadrática, todas as variáveis de decisão ficam com os respectivos valores $\mathsf{\alpha_i = {1 \over 8}}$, ou seja, todas as variáveis representam vetores suportes. Substituindo estes valores, temos o vetor w.
A função decisão fica representada por f(x) = −x₁x₂. Todos os dados de entrada ficam classificados corretamente com a SVM apresentada.

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede Neural de bases radiais (RBF):

0. Considere uma base de dados (x_i, d_i), i = 1, 2,..., p, onde x_i é um exemplo da base de dados 
   e d é o vetor de saídas desejadas correspondentes.
1. Defina o número q de neurônios ocultos (bases radiais), em geral escolhe-se q ≤ n. 
   Selecione aleatoriamente q exemplos do conjunto de dados, e faça a seguinte atribuição:
   u_j = x_j, j = 1, 2,..., q.
2. Especifique o(s) valor(es) do(s) raio(s) da função de base radial, σ_j. 
   Cada neurônio pode ter um raio diferente, para termos maior diversificação da RBF.
3. Para cada exemplo da base de dados x_i, onde i = 1, 2, ..., p, execute os passos 4 e 5:
    4. Calcule a ativação de cada neurônio j da camada escondida:
       ϕ_j = e^{-1/(2σ²)‖x_i−u_j‖²} 
    5. Atribua os valores das ativações dos neurônios na matriz G:
       G_i,j = ϕ_j, e G_i,q+1 = θ
6. Após a apresentação de todos os exemplos, calcule os pesos da saída:
   w = (G^TG)^-1G^Td
Temos essa expressão de w, pois:
   Gw = d  ⇒  G^TGw = G^Td  ⇒  (G^TG)^-1(G^TG)w = (G^TG)^-1G^Td  ⇒  w = (G^TG)^-1G^Td.
7. Calcule a saída de cada exemplo: y_k = ∑_j=1^q+1w_jkϕ_j. Calcule o erro de classificação.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de classificação de padrões com a rede neural Radial Basis Function (RBF). A rede deve separar os dados de entrada em duas classes usando 2 centros.

Vamos começar com a apresentação do padrão de entrada (x₁, x₂) = (0, 2), com σ = $\mathsf{\sqrt {0,5}}$. O resultado da ativação de cada neurônio da camada escondida será guardado na primeira linha da matriz G: g₁.
Agora temos as apresentações dos padrões de entrada (1, 2) e (1, 3). O resultado da ativação de cada neurônio da camada escondida será guardado nas linhas da matriz G: g₂ e g₃.
Agora temos as apresentações dos padrões de entrada (1, 0) e (2, 1). O resultado da ativação de cada neurônio da camada escondida será guardado nas linhas da matriz G: g₄ e g₅.
Agora podemos calcular o vetor de pesos usando a matriz G. Note que a terceira coluna desta matriz tem valores iguais a 1, pois são as ativações de θ. Temos o vetor de pesos calculado da seguinte maneira: w = (G^TG)^-1G^Td.
Podemos calcular as saídas e os erros quadráticos desta rede para os dois primeiros padrões de entrada: y = w₁φ₁ + w₂φ₂ + θ e E_k = (d_k − y)²)/2.
Seguem os cálculos das saídas e os erros quadráticos desta rede para mais dois padrões de entrada.
Para finalizar, são mostrados os cálculos da saída e do erro quadrático da rede para o último padrão de entrada. O erro quadrático total desta RBF ficou em E = 0,219.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de classificação de padrões com a rede neural Radial Basis Function (RBF). A rede deve separar os dados de entrada em duas classes com 3 centros.

Vamos começar com a apresentação do padrão de entrada (x₁, x₂) = (0, 2), com σ = $\mathsf{\sqrt {0,5}}$. O resultado da ativação de cada neurônio da camada escondida será guardado na primeira linha da matriz G: g₁.
Agora temos as apresentações dos padrões de entrada (1, 2) e (1, 3). O resultado da ativação de cada neurônio da camada escondida será guardado nas linhas da matriz G: g₂ e g₃.
Agora temos as apresentações dos padrões de entrada (1, 0) e (2, 1). O resultado da ativação de cada neurônio da camada escondida será guardado nas linhas da matriz G: g₄ e g₅.
Agora podemos calcular o vetor de pesos usando a matriz G. Note que a quarta coluna desta matriz tem valores iguais a 1, pois são as ativações de θ. Temos o vetor de pesos calculado da seguinte maneira: w = (G^TG)^-1G^Td.
Podemos calcular as saídas e os erros quadráticos desta rede para os dois primeiros padrões de entrada: y = w₁φ₁ + w₂φ₂ + w₃φ₃ + θ e E_k = (d_k − y)²)/2.
Seguem os cálculos das saídas e os erros quadráticos desta rede para mais dois padrões de entrada.
Para finalizar, são mostrados os cálculos da saída e do erro quadrático da rede para o último padrão de entrada. O erro quadrático total desta RBF ficou em E = 0,0057.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de classificação de padrões da função "OU EXCLUSIVO" com a rede neural Radial Basis Function (RBF). Vamos utilizar 2 centros.

Vamos começar com a apresentação dos padrões de entrada (x₁, x₂) = (1, 1) e (-1, 1), com σ = $\mathsf{\sqrt {0,5}}$. O resultado da ativação de cada neurônio da camada escondida será guardado nas duas primeiras linha da matriz G: g₁ e g₂.
Agora temos as apresentações dos padrões de entrada (-1, -1) e (1, -1). O resultado da ativação de cada neurônio da camada escondida será guardado nas linhas da matriz G: g₃ e g₄.
Agora podemos calcular o vetor de pesos usando a matriz G. Note que a terceira coluna desta matriz tem valores iguais a 1, pois são as ativações de θ. Temos o vetor de pesos calculado da seguinte maneira: w = (G^TG)^-1G^Td.
Podemos calcular as saídas e os erros quadráticos desta rede para os dois primeiros padrões de entrada: y = w₁φ₁ + w₂φ₂ + θ e E_k = (d_k − y)²)/2.
Temos que o erro é igual a ZERO para este problema de classificação usando a RBF de 2 centros.

📑 Atividade 4.1

voltar ao topo

📑 Atividade 4.2

voltar ao topo

5. Redes de Hebb e Mapas auto-organizáveis

Material das páginas 49 até 59.

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede Neural de Hebb:

0. Inicialize os pesos w_i = 0, onde i = 1, 2, ..., n
    1. Para cada par de treinamento (x,d), faça:
    2. w_i^atual = w_i^anterior + αx_id_i 
       θ_i^atual = θ_i^anterior + αd_i 
    3. Faça y* = w_ix_i + θ, onde i = 1, 2, ..., n
4. Teste a convergência. Se necessário, repita os passos 1-3.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de classificação de padrões da função "OU" utilizando a rede neural de Hebb, com α = 1.

Vamos começar com a apresentação dos padrões de entrada (x₁, x₂) = (1, 1) e (1, -1) para a rede. As atualizações dos pesos são automáticas e produzem o vetor (w₁, w₂, θ) = (2, 0, 2).
Continuando a apresentação dos padrões de entrada: (-1, 1) e (-1, -1). As atualizações dos pesos produzem o vetor (w₁, w₂, θ) = (2, 2, 2).
Ao final da 1ª iteração, temos todos os padrões classificados corretamente. Logo, o treinamento pode ser finalizado.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de classificação de padrões com a rede neural de Hebb, com α = 1. Precisamos deixar os padrões de entrada no intervalo [-1, 1] para que a rede de Hebb funcione corretamente.

Vamos começar com a apresentação dos padrões de entrada (x₁, x₂) = (-1, 0.33) e (-0.33, 0.33) para a rede. As atualizações dos pesos são automáticas e produzem o vetor (w₁, w₂, θ) = (-1.33, 0.66, 2).
Continuando a apresentação dos padrões de entrada: (-0.33, 1) e (-0.33, -1). As atualizações dos pesos produzem o vetor (w₁, w₂, θ) = (-1.33, 2.66, 2).
Ao final da 1ª iteração, o vetor de pesos (w₁, w₂, θ) = (-1.66, 2.99, 1). Todos os padrões são classificados corretamente, e o treinamento da rede pode ser finalizado.

voltar ao topo

📑 Atividade 5.1

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede Heteroassociativa:

0. Inicialize os pesos w_ij = 0, onde i = 1, 2, ..., n, j = 1, 2, ..., m.
    1. Para cada par de treinamento (x,d), faça os passos 2-4:
    2. y_j* = ∑_ix_iw_ij
    3. Se y_j* > 0, y_j = 1
       Se y_j* = 0, y_j = 0
       Se y_j* < 0, y_j = -1
    4. w_ij^atual = w_ij^anterior + αx_id_i 
5. Reduza α e teste a convergência. Se necessário, repita os passos de 1-4.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de classificação de padrões com a rede neural Heteroassociativa, com α = 1.

Vamos começar com a apresentação dos padrões de entrada (x₁, x₂, x₃, x₄) = (1, 0, 0, 0) e (1, 1, 0, 0) para a rede. As atualizações dos pesos são automáticas e produzem a matriz de pesos indicada w_ij, com i = 1, 2, 3, 4 e j = 1, 2.
Continuando a apresentação dos padrões de entrada: (0, 0, 0 ,1) e (0, 0, 1, 1). As atualizações dos pesos produzem a matriz de pesos indicada w_ij, com i = 1, 2, 3, 4 e j = 1, 2.
Multiplicando-se a matriz de pesos W pelos vetores dos dados de entrada, temos o reconhecimento destes padrões. O processo de treinamento desta rede pode ser finalizado.

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Rede de Kohonen:

0. Iniciar os pesos dos n neurônios da rede com valores aleatórios baixos: w_ij
1. Apresentar cada entrada x para a rede, e executar os passos 2 e 3:
   2. Determinar o neurônio i que possui a menor distância (euclidiana) do peso w com o vetor x.
      d_i = ∑_j=1ⁿ(x_j − w_ij)²
      Este neurônio é denominado “vencedor”.
   3. Ajustar os pesos do neurônio vencedor e de todos os neurônios que pertencem a uma vizinhança 
      centrada nele, V_i.
      w_ij^atual = w_ij^anterior + α[x_j − w_ij^anterior]
      onde i ∈ V_i.
5. Ajustar a taxa de aprendizado α e o raio de vizinhança. 
   Se não existirem mais mudanças substanciais no mapa, pare; caso contrário, volte ao passo 1.

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício de treinamento de uma rede de Kohonen, com α = 0,5. Temos um mapa com 4 neurônios em formato quadrado, e os dados com valores no intervalo [-1, 1], o que garante a convergência mais rápida da rede.

Vamos começar com a apresentação do padrão de entrada A(-0,15; 0,25). Calculamos as distâncias d_i entre as coordenadas deste padrão e as coordenadas w_ij dos pesos dos neurônios. O vencedor é o neurônio 2.
Neste exemplo, vamos usar o treinamento "hard", que só atualiza o neurônio vencedor.
Na apresentação do padrão de entrada B(-0,2; -0,2), calculamos as distâncias d_i entre as coordenadas deste padrão e as coordenadas w_ij dos pesos dos neurônios. O vencedor é o neurônio 3, que é atualizado.
Quando apresentamos o padrão de entrada C(0,2; 0,2), temos que o neurônio vencedor é o 4, que tem seus pesos atualizados.
Quando apresentamos o padrão de entrada D(0,15; 0,25), temos que o neurônio vencedor é o 4, que tem seus pesos atualizados.
Quando apresentamos o padrão de entrada E(-0,2; 0,3), temos que o neurônio vencedor é o 2, que tem seus pesos atualizados.
Quando apresentamos o padrão de entrada F(-0,25; 0,3), temos que o neurônio vencedor é o 2, que tem seus pesos atualizados.
Quando apresentamos o padrão de entrada G(-0,3; -0,2), temos que o neurônio vencedor é o 3, que tem seus pesos atualizados. Finalizamos a primeira iteração.
Na segunda iteração, reduzimos a taxa de aprendizagem α e apresentamos novamente os padrões de entrada para a rede. O critério de parada é a "convergência" da rede, ou seja, quando os pesos sofrem poucas modificações de uma iteração para outra.

📑 Atividade 5.2

voltar ao topo

6. Mapas auto-organizáveis e PCV

Material das páginas 59 até 66.

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício de treinamento de uma rede de Kohonen para resolver o Problema do Caixeiro Viajante, com α = 0,5. Temos um mapa com 6 neurônios em formato retangular 2 x 3, e os dados com valores no intervalo [-1, 1], o que garante a convergência mais rápida da rede. O comprimento da rota inicial é igual a 4.

Neste caso, vamos usar a vizinhança Gaussiana com a função Λ_ii* com as distâncias topológicas d_ii* entre os neurônios: por exemplo, o neurônio 1 tem distância topológica d₁₂ = 1 ao neurônio 2; já a distância até o neurônio 3 será d₁₃ = 2.
Apresentamos a cidade A(0,1; 0,1) para a rede, e o neurônio vencedor é o 4. Com a vizinhança Gaussiana, usamos a quarta linha e a quarta coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 3,7867. Apresentamos a cidade D(0,8; 0) para a rede, e o neurônio vencedor é o 6. Usamos a sexta linha e a sexta coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 3,5641. Apresentamos a cidade F(0,4; 0,9) para a rede, e o neurônio vencedor é o 2. Usamos a segunda linha e a segunda coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 3,4724. Apresentamos a cidade B(0,2; 0,8) para a rede, e o neurônio vencedor é o 3. Usamos a terceira linha e a terceira coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 3,2547. Apresentamos a cidade C(0,7; 0,7) para a rede, e o neurônio vencedor é o 1. Usamos a primeira linha e a primeira coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 2,9549. Apresentamos a cidade E(0,9; 0,8) para a rede, e o neurônio vencedor é o 1. Usamos a primeira linha e a primeira coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 2,8946. Apresentamos a cidade D(0,8; 0) para a rede, e o neurônio vencedor é o 6. Usamos a sexta linha e a sexta coluna da matriz de distâncias Λ_ii* para atualizar todos os pesos da rede.
O valor da rota com a atualização é de 2,8585. O processo continua até que os pesos sofram poucas alterações. Note que o neurônio 5 não está sendo utilizado adequadamente, e as cidade C e E estão competindo pelo neurônio 1. Sugestão: colocar mais neurônios do que o número de cidades.

📑 Atividade 6.1

Usando o mesmo raciocínio do Exercício 1, resolva o problema ulysses16 do TSPLIB com o mapa auto-organizável SOM. Utilize mais do que 16 neurônios nesta rede neural. As coordenadas das cidades estão na tabela a seguir:

cidade	x	y
1	38.24	20.42
2	39.57	26.15
3	40.56	25.32
4	36.26	23.12
5	33.48	10.54
6	37.56	12.19
7	38.42	13.11
8	37.52	20.44
9	41.23	9.10
10	41.17	13.05
11	36.08	-5.21
12	38.47	15.13
13	38.15	15.35
14	37.51	15.17
15	35.49	14.32
16	39.36	19.56

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício de treinamento de classificação de padrões usando uma Rede LVQ, com α = 0,1. Temos 3 neurônios que representam 2 classes.

Apresentamos o padrão x₁ = (0, 0, 1, 1) para a rede, e o neurônio vencedor é o 2, que representa a classe 1. Como o padrão x₁ pertence à classe 2, a atualização é feita como Δw_2j = − α(x_j − w_2j).
Apresentamos o padrão x₂ = (1, 0, 0, 0) para a rede, e o neurônio vencedor é o 1, que representa a classe 1. Como o padrão x₂ pertence à classe 1, a atualização é feita como Δw_1j = + α(x_j − w_1j).
Apresentamos o padrão x₃ = (0, 1, 1, 0) para a rede, e o neurônio vencedor é o 3, que representa a classe 2. Como o padrão x₃ pertence à classe 2, a atualização é feita como Δw_3j = + α(x_j − w_3j).
Apresentamos o padrão x₄ = (1, 1, 1, 0) para a rede, e o neurônio vencedor é o 1, que representa a classe 1. Como o padrão x₄ pertence à classe 1, a atualização é feita como Δw_1j = + α(x_j − w_1j).
No fim da 1ª iteração, temos a matriz de pesos apresentada. Reduzimos o valor de α e continuamos os cálculos até que a rede tenha uma convergência: poucas alterações de pesos de uma iteração para a outra.
Apresentando os padrões para a rede, temos os pesos reforçados de cada neurônio.
No fim da 2ª iteração, temos a matriz de pesos apresentada. Reduzimos o valor de α e continuamos os cálculos até que a rede tenha uma convergência: poucas alterações de pesos de uma iteração para a outra.

📑 Atividade 6.2

voltar ao topo

7. Redes Neurais Temporais

Material das páginas 66 até 75.

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício de treinamento de uma rede temporal RBF, com 2 centros: (1, 0.9) e (0.55, 0.6).

Vamos utilizar os padrões de entrada x para prever 2 passos à frente: (1, 0.9) para prever (0.75, 0.6); (0.75, 0.6) para prever (0.6, 0.55); e assim sucessivamente. Apresentamos o primeiro padrão de entrada para a rede: (1, 0.9).
Apresentamos os padrões de entrada (0.9, 0.75) e (0.75, 0.6) para a rede.
Apresentamos os padrões de entrada (0.6, 0.55) e (0.55, 0.6) para a rede.
Utilizando as 6 linhas da matriz G, calculamos os pesos para a Rede RBF.
Apresentamos os padrões de entrada (1, 0.9) e (0.9, 0.75) para a rede.
Apresentamos os padrões de entrada (0.75, 0.6) e (0.6, 0.55) para a rede.
Apresentamos o padrão de entrada (0.55, 0.6) para a rede, finalizando o conjunto de treinamento.
Apresentamos os padrões do conjunto de testes: (0.6, 0.5) e (0.5, 0.4).
A rede RBF fica com um erro quadrático E = 0,2205.

📃 Resolução

Vamos acompanhar os cálculos deste exercício de treinamento de uma rede temporal RBF, com 2 centros: (0.1, 0.2) e (0.4, 0.5).

Vamos utilizar os padrões de entrada t para prever 2 passos à frente: (0.1, 0.2) para prever (0.75, 0.6); (0.2, 0.3) para prever (0.6, 0.55); e assim sucessivamente. Apresentamos o primeiro padrão de entrada para a rede: (0.1, 0.2).
Apresentamos os padrões de entrada (0.2, 0.3) e (0.3, 0.4) para a rede.
Apresentamos os padrões de entrada (0.4, 0.5) e (0.5, 0.6) para a rede.
Utilizando as 6 linhas da matriz G, calculamos os pesos para a Rede RBF.
Apresentamos os padrões de entrada (0.1, 0.2) e (0.2, 0.3) para a rede.
Apresentamos os padrões de entrada (0.3, 0.4) e (0.4, 0.5) para a rede.
Apresentamos o padrão de entrada (0.5, 0.6) para a rede, finalizando o conjunto de treinamento.
Apresentamos os padrões do conjunto de testes: (0.6, 0.7) e (0.7, 0.8).
A rede RBF fica com um erro quadrático E = 0,2271.

voltar ao topo

8. Redes Neurais Recorrentes

Material das páginas 75 até 80.

voltar ao topo

📑 Atividade 8.1

voltar ao topo

📑 Atividade 8.2

Resolva o problema de classificação do Exercício 1 da página 27 usando uma rede de Elman ou de Jordan.

voltar ao topo

Outras Metaheurísticas

9. Busca Tabu

Material das páginas 82 até 84.

voltar ao topo

📃 Algoritmo comentado

Algoritmo da Busca Tabu:

Faça i = 1 e crie aleatoriamente uma solução S_i. 
    Enquanto iteração_atual ≤ max_iterações, faça:
        iteração_atual = iteração_atual + 1.
        Crie uma lista de movimentos M = {m₁, m₂, ..., m_k}.
        Calcule a função objetivo do problema S_i considerando a aplicação de cada movimento m_j ∈ M.
        Verifique se o critério de aspiração será usado (solução na lista tabu pode ser aceita?).
        Escolha m_j ∈ M que produz a melhor solução S_i+1, tal que tabu(m_j) = 0.
        Se f(S_i+1) ≤ f(S_i), então 
           S_i = S_i+1
           tabu(m_j) = 3
           i = i + 1
        Fim
        Atualize a lista tabu: tabu(m_q) = tabu(m_q) – 1, onde tabu(m_q) > 0.
    Fim
Fim

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação da Busca Tabu para encontrar uma rota para o problema do Caixeiro Viajante. Vamos utilizar k = 3, ou seja, 3 movimentos para cada iteração.

Com a solução aleatória S₁, aplicamos 3 movimentos da lista M: o melhor movimento é m₃, que será colocado na lista tabu por 3 iterações.
Com a solução modificada S₂, aplicamos 3 movimentos da nova lista M: o melhor movimento é m₂, que será colocado na lista tabu por 3 iterações. O movimento m₁ está na lista tabu, e não foi considerado nesta iteração.
Com a solução modificada S₃, aplicamos 3 movimentos da nova lista M: nenhum dos movimentos melhora a solução. O movimento m₃ está na lista tabu, e não foi considerado nesta iteração.
Com a solução S₃, aplicamos 3 movimentos da nova lista M: nenhum dos movimentos melhora a solução. O movimento m₂ está na lista tabu, e não foi considerado nesta iteração. Continuamos os cálculos até alcançar o número máximo de iterações.

voltar ao topo

📑 Atividade 9.1

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação da Busca Tabu para encontrar uma solução do problema da Mochila. Vamos utilizar k = 3, ou seja, 3 movimentos para cada iteração.

Com a solução aleatória S₁, aplicamos 3 movimentos da lista M: o melhor movimento é m₃, que será colocado na lista tabu por 3 iterações.
Com a solução modificada S₂, aplicamos 3 movimentos da nova lista M: o melhor movimento é m₃, que será colocado na lista tabu por 3 iterações. O movimento m₂ está na lista tabu, e não foi considerado nesta iteração.
Com a solução modificada S₃, aplicamos 3 movimentos da nova lista M: o melhor movimento é m₁, que será colocado na lista tabu por 3 iterações. O movimento m₂ está na lista tabu, e não foi considerado nesta iteração.
Com a solução S₄, aplicamos 3 movimentos da nova lista M: nenhum dos movimentos melhora a solução. O movimento m₂ está na lista tabu, e não foi considerado nesta iteração. Continuamos os cálculos até alcançar o número máximo de iterações.

📑 Atividade 9.2

voltar ao topo

10. Nuvem de Partículas

Material das páginas 85 até 93.

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação da Nuvem de Partículas para encontrar o valor mínimo da função f(x). Vamos utilizar 3 partículas que representam soluções do problema.

Com os parâmetros indicados, temos as 2 primeiras iterações da técnica. A melhor partícula é p₂ nestas iterações, com f(x) = 21,4. As melhores posições de cada partícula pbest_i são suas novas posições.
Nas 4 iterações seguintes, temos que a melhor partícula continua sendo p₂, com f(x) = 21,4.
Na 7ª iteração, a melhor partícula é p₃, com f(x) = 21,3. Porém, com as atualizações de velocidades, a partícula p₂, volta a ser a melhor com f(x) = 15,6 na 8ª iteração.
Na 11ª iteração, a melhor partícula é p₃, com f(x) = 15,4. Porém, com as atualizações de velocidades, a partícula p₂, volta a ser a melhor com f(x) = 14,6 na 14ª iteração.
Nas 4 iterações seguintes, temos que a melhor partícula é p₂, com f(x) = 14,5.
Com as partículas agrupadas, temos uma solução ótima local f(x) = 14,5. Espalhando-se as partículas e mantendo-se a melhor delas (p₂), podemos explorar o espaço de busca da técnica. O critério de parada mais usado em PSO é o número máximo de iterações alcançado.

📑 Atividade 10.1

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação da Nuvem de Partículas para encontrar rotas do Problema do Caixeiro Viajante. Vamos utilizar 3 partículas que representam soluções do problema.

As velocidades são aplicadas com as trocas de posições dos vértices, tentando "imitar" as rotas pbest_i e gbest.
Para fazermos as trocas do PCV com a técnica PSO, podemos utilizar índices para gbest - x_i. Na partícula 1, a cidade F está na posição 6; porém, na partícula gbest a cidade F está na posição 1. Logo, a posição 1 de gbest - x₁ tem índice 6.
A cidade B está na posição 2 da partícula 1; porém, na partícula gbest a cidade B está na posição 5. Logo, a posição 5 de gbest - x₁ tem índice 2. Quando a partícula é a gbest, temos que os índices de gbest - x_i estão na ordem 1, 2, 3, 4, 5, 6.
Com os parâmetros indicados, temos a 1ª iteração da técnica. A melhor partícula é p₂, com solução 39,89. Calculamos as velocidades por meio de trocas de posições dos vértices, deixando as rotas parecidas com a gbest.
Na 2ª iteração, a melhor partícula é p₃, com solução 36,05. Calculamos as velocidades por meio de trocas de posições dos vértices, deixando as rotas parecidas com a gbest.
Na 3ª iteração, a melhor partícula é p₃, com solução 36,05. Calculamos as velocidades por meio de trocas de posições dos vértices, deixando as rotas parecidas com a gbest.
A técnica prossegue até que as rotas fiquem todas iguais à gbest. Neste momento, podemos criar 2 novas partículas, mantendo-se a partícula gbest para não perdermos boas soluções. Esta técnica de "espalhar" as partículas pode ser feita algumas vezes, até alcançarmos um número máximo de iterações.

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação da Nuvem de Partículas para encontrar uma solução para o problema da Mochila. Vamos utilizar 3 partículas que representam soluções do problema.

Começamos calculando os valores da função objetivo de cada partícula. As velocidades são aplicadas com as trocas de valores dos objetos (0 ou 1), tentando "imitar" as soluções pbest_i e gbest.
Com os parâmetros indicados, temos a 1ª iteração da técnica. A melhor partícula é p₃, com solução 9. Calculamos as velocidades por meio de trocas de valores dos objetos, deixando as soluções parecidas com a gbest.
Escolhemos 1 troca de gbest - x₁: na posição 3, que a partícula gbest tem valor 1. Escolhemos 1 troca de gbest - x₂: na posição 2, que a partícula gbest tem valor 0.
Na 2ª iteração, a melhor partícula é p₁, com solução 9. Calculamos as velocidades por meio de trocas de valores dos objetos, deixando as soluções parecidas com pbest e gbest.
Escolhemos 1 troca de gbest - x₂: na posição 4, que a partícula gbest tem valor 1. Escolhemos 1 troca de gbest - x₃: na posição 5, que a partícula gbest tem valor 0.
Na 3ª iteração, a melhor partícula é p₁, com solução 9. Calculamos as velocidades por meio de trocas de valores dos objetos, deixando as soluções parecidas com pbest e gbest.
Escolhemos 1 troca de gbest - x₂: na posição 5, que a partícula gbest tem valor 0. Escolhemos 1 troca de gbest - x₃: na posição 4, que a partícula gbest tem valor 1.
A técnica prossegue até que as soluções fiquem todas iguais à gbest. Depois disso, podemos criar 2 novas partículas, mantendo-se a partícula gbest para não perdermos boas soluções. Esta técnica de "espalhar" as partículas pode ser feita algumas vezes, até alcançarmos um número máximo de iterações.

📑 Atividade 10.2

voltar ao topo

11. Simulated Annealing, ILS e GRASP

Material das páginas 93 até 99.

voltar ao topo

📃 Algoritmo comentado

Algoritmo de Simulated Annealing:

Inicialização: S₀ (solução inicial), M (máximo de iterações), V (máximo de vizinhos), 
L (máximo de sucessos), S = S₀, T = T₀, iteração = 1 
Repita
    i = 1 (número de soluções vizinhas encontradas), nsucess = 0
    Repita
        Crie uma solução S_i+1, vizinha de S_i
        Calcule a função objetivo para S_i+1
        Calcule a probabilidade P de aceitação de nova solução: P = e^-ΔE/T
        Se ΔE = f(S_i+1) - f(S_i) ≤ 0 ou P > rnd, então
            S = S_i+1 (melhor solução)
            nsucess = nsucess + 1
        fim
        i = i + 1 (tentativas)
    Até nsucess ≥ L ou i > V
    T = αT 
    iteração = iteração + 1
Até nsucess = 0 ou iteração ≥ M

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação do Simulated Annealing para encontrar rotas para o problema do Caixeiro Viajante. Vamos utilizar a solução inicial S₀ indicada.

Na 1ª iteração, encontramos a solução vizinha S₁ com uma troca de arcos de S₀. Como f(S₁) ≤ f(S₀), então a solução é aceita e podemos atualizar a temperatura para a próxima iteração.
Na 2ª iteração, encontramos a solução vizinha S₂ com uma troca de arcos de S₁. Como f(S₂) > f(S₁), então utilizamos a probabilidade P para verificar a aceitação desta solução.
Como P < rnd, a solução não é aceita e podemos encontrar mais uma vizinha de S₁ (o máximo é V = 2). Como f(S₂) ≤ f(S₁), então aceitamos a solução e podemos atualizar a temperatura para a próxima iteração.
Na 3ª iteração, encontramos a solução vizinha S₃ com uma troca de arcos de S₂. Como f(S₃) > f(S₂), então utilizamos a probabilidade P para verificar a aceitação desta solução.
Como P > rnd, a solução é aceita e podemos podemos atualizar a temperatura para a próxima iteração. O processo continua até atingir um número máximo de iterações.

voltar ao topo

📑 Atividade 11.1

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação do Simulated Annealing para encontrar soluções para o problema da Mochila. Vamos utilizar a solução inicial S₀ indicada.

Na 1ª iteração, encontramos a solução vizinha S₁ com uma troca de objetos em S₀. Como f(S₁) ≥ f(S₀), então a solução é aceita e podemos atualizar a temperatura para a próxima iteração.
Na 2ª iteração, encontramos a solução vizinha S₂ com uma troca de objetos em S₁. Como f(S₂) < f(S₁), então utilizamos a probabilidade P para verificar a aceitação desta solução.
Como P < rnd, a solução não é aceita e podemos encontrar mais uma vizinha de S₁ (o máximo é V = 2). Como f(S₂) ≥ f(S₁), então aceitamos a solução e podemos atualizar a temperatura para a próxima iteração.
Na 3ª iteração, encontramos a solução vizinha S₃ com uma troca de objetos em S₂. Como f(S₃) < f(S₂), então utilizamos a probabilidade P para verificar a aceitação desta solução.
Como P > rnd, a solução é aceita e podemos podemos atualizar a temperatura para a próxima iteração. O processo continua até atingir um número máximo de iterações.

📑 Atividade 11.2

voltar ao topo

📃 Algoritmo comentado

Algoritmo de ILS - Iterated Local Search:

x₀ = Solução_Inicial
x = busca_local(x₀) aplica uma melhoria na solução inicial
Repita
    x' = perturbação(x, histórico) encontra uma nova solução, guiada por um histórico de trocas
    x'' = busca_local(x') aplica uma melhoria na solução x'
    Se f(x'') < f(x), então 
        x = x'' (aceita a melhor solução)
    Caso contrário, se f(x') < f(x), então
        x = x' (aceita a melhor solução)
    Fim
Enquanto o critério de parada não for satisfeito

voltar ao topo

📃 Algoritmo comentado

Algoritmo de GRASP - Greedy Randomized Adaptative Search: Procedure:

Melhor_solução = M, função de avaliação: f.
Repita
    X = solução_grasp (criar uma solução aleatória por inserção gulosa de elementos)
    X = busca_local(X) (aplicar uma busca de vizinhança para melhorar a solução X: trocas de arcos)
        Se f(X) < Melhor_solução, então 
            Melhor_solução = X (aceita a melhor solução)
        Fim
Enquanto o critério de parada não for satisfeito

voltar ao topo

12. Colônia de Formigas e VNS

Material da página 99 até a página 106.

voltar ao topo

📃 Algoritmo comentado

Algoritmo de Colônia de Formigas:

Coloque cada formiga em uma cidade aleatória
    Para t = 1 até o número máximo de iterações
        Para k = 1 até m (nº de formigas)
            Enquanto a formiga k não construir a viagem S_k
                Selecione a próxima cidade pela regra da probabilidade:
                p_ij^k = τ_ij^αη_ij^β / ∑_{l∈N_j^k} τ_il^αη_jl^β, quando j ∈ N_j^k. 
            Fim
            Calcule a distância L_k da viagem S_k
            Se L_k < L* então
                S* = S_k, L* = L_k
            Fim
        Fim
        Atualize os feromônios: τ_ij = (1-ρ)τ_ij + ∑_k=1^mΔτ_ij^k, onde:
        Δτ_ij^k = Q / L_k quando a aresta (i, j) pertence S_k, onde Q é uma constante.
        Δτ_ij^k = 0 em caso contrário. 
    Fim
O resultado é a rota S*.

voltar ao topo

📑 Atividade 12.1

voltar ao topo

📃 Algoritmo comentado

Algoritmo de VNS - Variable Neighborhood Search:

x₀ = Solução_Inicial.
x = busca_local(x₀) aplica uma melhoria na solução inicial
Repita
    x' = vizinho(x) encontra uma nova solução, vizinha de x através de 1 troca de arcos
    x'' = busca_local(x') aplica uma melhoria na solução x'
    Se f(x'') < f(x), então 
        x = x'' (aceita a melhor solução)
    Caso contrário, se f(x') < f(x), então
        x = x' (aceita a melhor solução)
    Fim
Enquanto o critério de parada não for satisfeito

voltar ao topo

13. Algoritmos Genéticos

Material da página 106 até a página 116.

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação de Algoritmos Genéticos para encontrar o valor máximo da função f(x), com uma população de 4 indivíduos. Utilizaremos 1 ponto de cruzamento e mutação apenas se um número aleatório for maior do que 0,5.

Em problemas de maximização, usamos o valor da função objetivo como fitness, pois soluções com maiores valores nos fornecem maiores probabilidades p_j. Como os indivíduos serão usados em formato binário, encontramos os respectivos valores decimais e calculamos o valor da função f para cada indivíduo.
Utilizando o método da roleta, encontramos 4 números aleatórios que definem quais serão os indivíduos que participam dos cruzamentos: para o primeiro par de indivíduos (i₁ e i₃), encontramos um número aleatório entre 0 e 5 (2,51), que indica o ponto de cruzamento está entre o terceiro e o quarto bit.
Trocamos os materiais genéticos entre o ponto de cruzamento e o final de cada indivíduo, gerando os novos filhos i₁ e i₂. Para o segundo par de indivíduos (i₂ e i₁), encontramos um número aleatório entre 0 e 5 (1,23), que indica o ponto de cruzamento está entre o segundo e o terceiro bit.
Trocamos os materiais genéticos entre o ponto de cruzamento e o final de cada indivíduo, gerando os novos filhos i₃ e i₄. Agora vamos fazer as mutações nestes novos indivíduos.
Podemos sortear um número n₁ que define quando será feita a mutação. No caso do indivíduo i₃, temos n₁ > 0,5, e n₂ = 2,66 nos fornece o ponto de mutação no terceiro bit do indivíduo. Logo, a terceira posição de i₃ torna-se 1.
No caso do indivíduo i₄, temos n₁ > 0,5, e n₂ = 0,71 nos fornece o ponto de mutação no primeiro bit do indivíduo. Logo, a primeira posição de i₄ torna-se 0. Os outros indivíduos não sofrem mutações pois n₁ < 0,5. Substituindo a população, temos uma nova iteração.
Encontramos os valores dos fitness dos novos indivíduos e as respectivas probabilidades de escolhas para usarmos na roleta: p_j.
Selecionamos os indivíduos por meio de 4 números aleatórios, e criamos os pontos de cruzamentos. Trocamos os materiais genéticos dos indivíduos escolhidos e podemos avançar para a fase de mutações.
Usando o mesmo critério da primeira iteração, temos as mutações nos indivíduos i₁, i₂ e i₄. Desta forma, criamos a nova população e podemos concluir a iteração. O processo continua até que um critério de parada seja satisfeito (solução máxima encontrada ou número máximo de iterações).

📑 Atividade 13.1

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação de Algoritmos Genéticos para encontrar soluções para o problema da Mochila, com uma população de 4 indivíduos. Utilizaremos 2 pontos de cruzamento e mutação apenas se um número aleatório for maior do que 0,5.

Utilizamos o valor da função objetivo como fitness de cada indivíduo, pois soluções com maiores valores nos fornecem maiores probabilidades p_j.
Utilizando o método da roleta, encontramos 4 números aleatórios que definem quais serão os indivíduos que participam dos cruzamentos: para o primeiro par de indivíduos (i₄ e i₃), encontramos dois números aleatórios entre 0 e 6 (1,88 e 4,3), que indicam os pontos de cruzamento entre o segundo e o terceiro bit (1,88) e entre o quinto e o sexto bit (4,3).
Trocamos os materiais genéticos entre os pontos de cruzamento, gerando os novos filhos i₁ e i₂. Para o segundo par de indivíduos (i₂ e i₃), encontramos dois números aleatórios entre 0 e 6 (0,65 e 3,15), que indicam os pontos de cruzamento entre o primeiro e o segundo bit (0,65) e entre o quarto e o quinto bit (3,15).
Trocamos os materiais genéticos entre os pontos de cruzamento, gerando os novos filhos i₃ e i₄. Agora vamos fazer as mutações nestes novos indivíduos.
Podemos sortear um número n₁ que define quando será feita a mutação. No caso do indivíduo i₁, temos n₁ > 0,5, e n₂ = 3,77 nos fornece o ponto de mutação no quarto bit do indivíduo. Logo, a quarta posição de i₁ torna-se 0.
No caso do indivíduo i₄, temos n₁ > 0,5, e n₂ = 2,8 nos fornece o ponto de mutação no terceiro bit do indivíduo. Logo, a terceira posição de i₄ torna-se 1. Os outros indivíduos não sofrem mutações pois n₁ < 0,5. Substituindo a população, temos uma nova iteração.
Encontramos os valores dos fitness dos novos indivíduos e as respectivas probabilidades de escolhas para usarmos na roleta: p_j.
Selecionamos os indivíduos por meio de 4 números aleatórios, e criamos os pontos de cruzamentos. Trocamos os materiais genéticos dos indivíduos escolhidos e podemos avançar para a fase de mutações.
Usando o mesmo critério da primeira iteração, temos as mutações nos indivíduos i₁ e i₂. Desta forma, criamos a nova população e podemos concluir a iteração. O processo continua até que um critério de parada seja satisfeito (solução máxima encontrada ou número máximo de iterações).

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação de Algoritmos Genéticos para encontrar soluções para o problema do Caixeiro Viajante, com uma população de 4 indivíduos. Utilizaremos 2 pontos de cruzamento e mutação apenas se um número aleatório for maior do que 0,5.

Como o problema é de minimização, vamos usar como fitness f_j = (max{rota_k} + 1) - rota_j. Desta forma, soluções com menores valores nos fornecem maiores probabilidades p_j.
Utilizando o método da roleta, encontramos 4 números aleatórios que definem quais serão os indivíduos que participam dos cruzamentos: para o primeiro par de indivíduos (i₁ e i₃), encontramos dois números aleatórios entre 0 e 6 (2,13 e 4,81), que indicam os pontos de cruzamento entre o terceiro e o quarto bit (2,13) e entre o quinto e o sexto bit (4,81).
Trocamos os materiais genéticos entre os pontos de cruzamento, gerando os novos filhos i₁ e i₂. Para evitar soluções infactíveis, devemos trocar as cidades repetidas que entraram nas novas rotas: na terceira posição de i₁, trocamos a cidade 3 pela cidade 5, e na segunda posição de i₂, trocamos a cidade 5 pela cidade 3.
Para o segundo par de indivíduos (i₂ e i₁), encontramos dois números aleatórios entre 0 e 6 (3,87 e 1,55), que indicam os pontos de cruzamento entre o segundo e o terceiro bit (1,55) e entre o quarto e o quinto bit (3,87).
Trocamos os materiais genéticos entre os pontos de cruzamento, gerando os novos filhos i₃ e i₄. Para evitar soluções infactíveis, devemos trocar as cidades repetidas que entraram nas novas rotas: na segunda posição de i₃, trocamos a cidade 4 pela cidade 1 e na quinta posição trocamos a cidade 3 pela cidade 6; na primeira posição de i₄, trocamos a cidade 1 pela cidade 4 e na sexta posição trocamos a cidade 6 pela cidade 3.
Podemos sortear um número n₁ que define quando será feita a mutação. No caso do indivíduo i₄, temos n₁ > 0,5, n₂ = 3,2 (quarta posição) e n₃ = 0,71 (primeira posição). Logo, podemos trocar as cidades da primeira com a quarta posição do indivíduo. Substituímos a população e podemos começar a 2ª iteração.
Encontramos os valores dos fitness dos novos indivíduos e as respectivas probabilidades de escolhas para usarmos na roleta: p_j.
Selecionamos os indivíduos por meio de 4 números aleatórios, e criamos os pontos de cruzamentos. Trocamos os materiais genéticos dos indivíduos escolhidos, fazendo as trocas de cidades repetidas, e podemos avançar para a fase de mutações.
Usando o mesmo critério da primeira iteração, temos as mutações nos indivíduos i₁ e i₂. Desta forma, criamos a nova população e podemos concluir a iteração. O processo continua até que um critério de parada seja satisfeito (solução máxima encontrada ou número máximo de iterações).

voltar ao topo

📑 Atividade 13.2

voltar ao topo

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação de Algoritmos Genéticos para encontrar soluções para o problema das p-medianas, com uma população de 5 indivíduos. Utilizaremos 1 ponto de cruzamento e mutação apenas se um número aleatório for maior do que 0,5.

Como o problema é de minimização, vamos usar como fitness f_j = (max{custo_k} + 1) - custo_j. Desta forma, soluções com menores valores nos fornecem maiores probabilidades p_j.
Utilizando o método da roleta, encontramos 4 números aleatórios que definem quais serão os indivíduos que participam dos cruzamentos. O primeiro par de indivíduos (r₁ e r₅) tem as medianas 2 e 4 pertencentes apenas à solução r₅, e as medianas 1 e 5 pertencentes apenas à solução r₁.
Podemos gerar um número aleatório entre 0 e 2 que define quais serão as medianas que devem ser trocadas: 0,54 indica que trocaremos as medianas 2 e 1 entre os indivíduos r₁ e r₅, gerando os filhos r₂ e r₃.
O segundo par de indivíduos (r₄ e r₃) tem as medianas 2 e 3 pertencentes apenas à solução r₄, e as medianas 1 e 4 pertencentes apenas à solução r₃.
Podemos gerar um número aleatório entre 0 e 2 que define quais serão as medianas que devem ser trocadas: 1,3 indica que trocaremos as medianas 3 e 4 entre os indivíduos r₄ e r₃, gerando os filhos r₄ e r₅.
Podemos sortear um número n₁ que define quando será feita a mutação. No caso do indivíduo r₂, temos n₁ > 0,5, n₂ = 0,21 (primeira posição) e n₃ = 3,2 (mediana 4). Logo, o indivíduo r₂ tem a primeira mediana trocada por 4.
No caso do indivíduo r₃, temos n₁ > 0,5, n₂ = 1,3 (segunda posição) e n₃ = 1,61 (mediana 2). Logo, o indivíduo r₃ tem a segunda mediana trocada por 2. Podemos manter o melhor indivíduo e substituir os outros 4 da população para começar a próxima iteração.
Encontramos os valores dos fitness dos novos indivíduos e as respectivas probabilidades de escolhas para usarmos na roleta: p_j.
Selecionamos os indivíduos por meio de 4 números aleatórios, e criamos os pontos de cruzamentos. Trocamos os materiais genéticos dos indivíduos escolhidos, fazendo as trocas de medianas e depois as mutações nos novos indivíduos. O processo continua até que um critério de parada seja satisfeito (solução máxima encontrada ou número máximo de iterações).

voltar ao topo

14. Evolução Diferencial e Busca Local

Material da página 117 até a página 127.

voltar ao topo

📃 Algoritmo comentado

Evolução Diferencial:

Crie uma população inicial com n soluções. Defina a função fitness f. 
Faça iteração = 0, defina os valores de P_CR e F.
Repita
   Para cada indivíduo i da população, faça:
      Defina os números inteiros aleatórios r₁, r₂, r₃ ∈ [1, n], onde r₁ ≠ r₂ ≠ r₃ ≠ i.
      Para cada j ∈ [1, m], faça:
         u_i,j = x_r1,j + F*(x_r2,j - x_r3,j) (vetor teste)
         Defina o número aleatório s_j ∈ [0, 1].
         Se s_j ≤ P_CR, então 
            x'_i,j = u_i,j
         Caso contrário
            x'_i,j = x_i,j
         Fim
      Fim
      Se f(x'_i,j) < f(x_i,j), então 
         x_i,j = x'_i,j
      Fim
   Fim
   iteração = iteração + 1  
Enquanto o critério de parada não for satisfeito
Retorne o melhor vetor da população

voltar ao topo

📃 Algoritmo comentado

Evolução Diferencial:

Crie uma população inicial com n soluções. Defina a função fitness f. 
Faça iteração = 0, defina os valores de P_CR e F.
Repita
   Para cada indivíduo i da população, faça:
      Defina os números inteiros aleatórios r₁, r₂ ∈ [1, n], onde r₁ ≠ r₂ ≠ i.
      Selecione o índice k do melhor indivíduo da população atual (xbest = k).
      Para cada j ∈ [1, m], faça:
         u_i,j = x_k,j + F*(x_r1,j - x_r2,j) (vetor teste)
         Defina o número aleatório s_j ∈ [0, 1].
         Se s_j ≤ P_CR, então 
            x'_i,j = u_i,j
         Caso contrário
            x'_i,j = x_i,j
         Fim 
      Fim
      Se f(x'_i,j) < f(x_i,j), então 
        x_i,j = x'_i,j
      Fim
   Fim
   iteração = iteração + 1  
Enquanto o critério de parada não for satisfeito
Retorne o melhor vetor da população

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação de Evolução Diferencial para encontrar o valor mínimo da função f(x,y) com uma população de 6 indivíduos. Utilizaremos vetor alvo aleatório, fator de escala F = 0,5 e taxa de crossover P_CR = 0,7.

Para o indivíduo 1, definimos os índices r₁ = 2, r₂ = 3 e r₃ = 6 para o cálculo do vetor teste u da mutação.
No crossover, os números aleatórios s₁ e s₂ definem as coordenadas do novo indivíduo x'₁, com a primeira coordenada do vetor x₁ e a segunda coordenada do vetor teste u. Como o novo indivíduo é melhor do que x₁, substituímos x₁ por x'₁.
Para o indivíduo 2, definimos os índices r₁, r₂ e r₃ e fazemos a mutação e o crossover da mesma maneira usada para o indivíduo 1. O novo indivíduo sobrevive e substitui o indivíduo 2 na população.
Para os indivíduos 3 e 4, definimos os índices r₁, r₂ e r₃ e fazemos as mutações e os crossovers da mesma maneira usada para os indivíduos anteriores. Os novos indivíduos sobrevivem e substituem os indivíduos 3 e 4 na população.
Para os indivíduos 5 e 6, definimos os índices r₁, r₂ e r₃ e fazemos as mutações e os crossovers da mesma maneira usada para os indivíduos anteriores. Os novos indivíduos sobrevivem e substituem os indivíduos 5 e 6 na população.
No final da 1ª iteração, temos a nova população criada, que será usada para começarmos a próxima iteração. A melhor solução encontrada nesta iteração é do vetor x₁ com fitness f(x,y) = 1,94.
Na 2ª iteração, seguimos os mesmos passos do algoritmo para a mutação e o crossover de cada indivíduo. Note que os novos indivíduos criados a partir dos indivíduos 1 e 3 têm fitness piores do que os indivíduos originais.
Os novos indivíduos criados a partir dos indivíduos 4 e 6 substituem os indivíduos originais.
No final da 2ª iteração, temos a nova população criada, que será usada para começarmos a próxima iteração. A melhor solução encontrada nesta iteração é do vetor x₄ com fitness f(x,y) = 1,79. As próximas iterações seguem o mesmo raciocínio mostrado nestas 2 primeiras iterações.

📃 Resolução

Vamos acompanhar os cálculos deste exercício da aplicação de Evolução Diferencial para encontrar o valor mínimo da função f(x,y) com uma população de 6 indivíduos. Utilizaremos o melhor vetor alvo da população xbest, o fator de escala F = 0,5 e a taxa de crossover P_CR = 0,7.

Para o indivíduo 1, definimos os índices r₁ = 3 e r₂ = 6 para o cálculo do vetor teste u da mutação. O vetor alvo é xbest = 4.
No crossover, os números aleatórios s₁ e s₂ definem as coordenadas do novo indivíduo x'₁, com a primeira coordenada do vetor x₁ e a segunda coordenada do vetor teste u. Como o novo indivíduo é melhor do que x₁, substituímos x₁ por x'₁.
Para o indivíduo 2, definimos os índices r₁ e r₂ e fazemos a mutação e o crossover da mesma maneira usada para o indivíduo 1. O novo indivíduo sobrevive e substitui o indivíduo 2 na população.
Para os indivíduos 3 e 4, definimos os índices r₁ e r₂ e fazemos as mutações e os crossovers da mesma maneira usada para os indivíduos anteriores. Os novos indivíduos sobrevivem e substituem os indivíduos 3 e 4 na população.
Para os indivíduos 5 e 6, definimos os índices r₁ e r₂ e fazemos as mutações e os crossovers da mesma maneira usada para os indivíduos anteriores. Os novos indivíduos sobrevivem e substituem os indivíduos 5 e 6 na população. Note que o melhor indivíduo da população agora é o 5.
No final da 1ª iteração, temos a nova população criada, que será usada para começarmos a próxima iteração. A melhor solução encontrada nesta iteração é do vetor x₅ com fitness f(x,y) = 2,25.
Na 2ª iteração, seguimos os mesmos passos do algoritmo para a mutação e o crossover de cada indivíduo. Note que os novos indivíduos criados a partir dos indivíduos 1 e 3 têm fitness piores do que os indivíduos originais.
Os novos indivíduos criados a partir dos indivíduos 4 e 6 substituem os indivíduos originais. O melhor indivíduo da população é o 4.
No final da 2ª iteração, temos a nova população criada, que será usada para começarmos a próxima iteração. A melhor solução encontrada nesta iteração é do vetor x₄ com fitness f(x,y) = 1,02. As próximas iterações seguem o mesmo raciocínio mostrado nestas 2 primeiras iterações.

📑 Atividade 14.1

📑 Atividade 14.2

voltar ao topo

📃 Algoritmo comentado

Problema da Designação:

Defina os parâmetros da Rede Neural Recorrente de Wang, o número máximo de soluções
r_max, r = 0 e v(i) = 0 (i = 1, 2, ..., n). 
Repita
   Repita
      Encontre uma solução x para o problema da Designação usando a Rede de Wang
   Enquanto Wx(t) − θ > Φ
   Faça x’ = x e m = 1.
   Repita
      Escolha uma linha k da matriz x’ tal que v(k) = 0.
      Encontre l tal que x’_k,l = max_k,i{x’_k,i}, i = 1, 2, ..., n.
      x’_k,l = x’_k,l + ½(∑_i=1ⁿ x_i,l + ∑_j=1ⁿ x_k,j).
      x’_k,j = 0, para j = 1, 2, ... n, j ≠ l.
      x’_i,l = 0, para i = 1, 2, ... n, i ≠ k.
      Faça v(k) = 1 e m = m + 1.
   Enquanto m ≤ n
   Faça r = r + 1.
   Determine o custo C da solução. 
   Se C < C_min, então
      C_min = C e x_min = x’.
   Fim
Enquanto r < r_max
Retorne o melhor vetor solução x_min.

voltar ao topo

📃 Algoritmo comentado

Problema do Caixeiro Viajante:

Defina os parâmetros da Rede Neural Recorrente de Wang, o número máximo de soluções
r_max, r = 0 e x''(i) = 0 (i = 1, 2, ..., n + 1). 
Repita
   Repita
      Encontre uma solução x para o problema da Designação usando a Rede de Wang
   Enquanto Wx(t) − θ > Φ
   Faça x’ = x e m = 1.
   Escolha uma linha k da matriz x’, faça x''(1) = k e p = k.
   Repita
      Encontre l tal que x’_k,l = max_k,i{x’_k,i}, i = 1, 2, ..., n.
      x’_k,l = x’_k,l + ½(∑_i=1ⁿ x_i,l + ∑_j=1ⁿ x_k,j).
      x’_k,j = 0, para j = 1, 2, ... n, j ≠ l.
      x’_i,l = 0, para i = 1, 2, ... n, i ≠ k.
      Faça x''(m + 1) = l, m = m + 1 e k = l (para prosseguir a rota).
   Enquanto m < n
   x’_k,p = x’_k,p + ½(∑_i=1ⁿ x_i,p + ∑_j=1ⁿ x_k,j).
   Faça x''(n + 1) = p (fechamento da rota).
   Faça r = r + 1.
   Determine o custo C da solução. 
   Se C < C_min, então
      C_min = C e x_min = x’.
   Fim
Enquanto r < r_max
Retorne o melhor vetor solução x_min.

voltar ao topo

página desenvolvida por:

Paulo Henrique Siqueira

contato: paulohscwb@gmail.com

O desenvolvimento deste material faz parte do Grupo de Estudos em Expressão Gráfica (GEEGRAF) da Universidade Federal do Paraná (UFPR)

Metaheurísticas e Aplicações de Paulo Henrique Siqueira está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-SemDerivações 4.0 Internacional.

Como citar este trabalho:

Siqueira, P.H., "Metaheurísticas e Aplicações". Disponível em: <https://paulohscwb.github.io/metaheuristicas/>, Janeiro de 2021.

Referências:

FAUSETT, L. Fundamentals of Neural Networks. Prentice Hall, 1994.
HAYKIN, S. Neural Networks – A Compreensive Foundation. Macmillan College Publishing, 1994.
KOHONEN, T. Self-Organizing Maps. Springer, 1995.
SILVA, I.N.; SPATTI, D.H.; FLAUZINO, R.A. Redes Neurais Artificiais para engenharia e ciências aplicadas. Artliber, 2010.
TAFNER, M.A.; XEREZ, M.; RODRÍGUEZ FILHO, I.W. Redes Neurais Artificiais: introdução e princípios da neurocomputação. FURB, 1996.
BOÇOIS, A., OLIVEIRA, A. A., SIQUEIRA, P. H., TELLES, F. Q. Diagnóstico de Doenças Dermatológicas usando a Rede Neural de Kohonen. In: IX Encontro Nacional de Inteligência Artificial (ENIA 2012), 2012, Curitiba. Proceedings Brazilian Conference on Intelligent Systems, v. 1. p. 1-8, 2012.
SIQUEIRA, P. H., SCHEER, S., STEINER, M. T. A. Application of the Winner Takes All Principle in Wang’s Recurrent Neural Network for the Assignment problem. Lecture Notes in Computer Science, Berlin, v. 3496, n. 1, p. 731-738, 2005.
SIQUEIRA, P. H., SCHEER, S., STEINER, M. T. A. A new approach to solve the Traveling Salesman Problem. Neurocomputing (Amsterdam), v. 70, p. 1013-1021, 2007.
SIQUEIRA, P. H., STEINER, M. T. A., SCHEER, S. Recurrent Neural Network with Soft 'Winner Takes All' principle for the TSP. In: ICNC 2010 - International Conference on Neural Computation, 2010, Valencia. Proceedings of the International Conference on Fuzzy Computation and International Conference on Neural Computation, v. 1. p. 265-270, 2010.
ROSA, C. R. M. ; STEINER, M. T. A. ; STEINER NETO, P. J. Técnicas de Mineração de Dados aplicadas a um Problema de Diagnóstico Médico. Espacios (Caracas), v. 37, p. 1, 2016.
TEIXEIRA, L. L., TEIXEIRA JUNIOR, L. A., SIQUEIRA, P. H. Previsões de vazões mensais via combinação híbrida ARIMA_NEURAL com encolhimento e decomposição Wavelet. REVISTA DE ENGENHARIA E TECNOLOGIA, v. 7, p. 144-161, 2015.
DEMUTH, H., BEALE, M. Neural Network Toolbox User's Guide (For Use with MATLAB), The MathWorks, Inc., MA, USA, 1994.
SOUTO, M. Multi-layer Perceptrons e Backpropagation. DIMAp/UFRN, 2020. Disponível em: <https://slideplayer.com.br/slide/3258057/>
BENEDIKTSSON, J. A., SWAIN, P. H., ERSOY, O. K. Neural network approaches versus statistical methods in classification of multisource remote sensing data. In: 12th Canadian Symposium on Remote Sensing Geoscience and Remote Sensing Symposium, IEEE, 1989. p. 489-492.
HEPNER, G., LOGAN, T., RITTER, N., BRYANT, N. Artificial neural network classification using a minimal training set- Comparison to conventional supervised classification. Photogrammetric Engineering and Remote Sensing, v. 56, n. 4, p. 469-473, 1990.
GORNI, A. A. Redes neurais artificiais - uma abordagem revolucionária em inteligência artificial. São Paulo, Micro Sistemas, 1993.
KRÖSE, B., KRÖSE, B., SMAGT, P. An introduction to neural networks, 1993.
BOSER, B. E., GUYON, I. M., VAPNIK, V. N. A training algorithm for optimal margin classifiers. In: Proceedings of the fifth annual workshop on Computational learning theory, p. 144-152, 1992.
GAHEGAN, M., WEST, G. The classification of complex geographic datasets: An operational comparison of artificial neural network and decision tree classifiers. In: Third International Conference on GeoComputation, p. 17-19, 1998.
CORTES, C., VAPNIK, V. Support-vector networks. Machine learning, v. 20, n.3, p. 273-297, 1995.
POWELL, M. J. D. Radial basis functions for multivariate interpolation: a review. In: J.C. Mason, M.G. Cox (Eds.), Algorithms for Approximation, Clarendon Press, Oxford, 1987
VIEIRA, F. C., DÓRIA NETO, A. D., COSTA, J. A. F. An Efficient Approach to the Travelling Salesman Problem Using Self-Organizing Maps. International Journal of Neural Systems, London, UK, v. 13, n.2, p. 59-66, 2003
Le COADOU, BENABDESLEM, K. Optimizing local modeling for times series prediction. International Journal of Computational Intelligence Research, v. 2, n. 1, p. 81-85, 2006.
DORIGO, M.; GARAMBARDELLA, L.M., Ant Colonies for the Traveling Salesman Problem. Biosystems, v. 43, n. 2, p. 73-81, 1997.
ENGELBRECHT, A. P., Computational Intelligence, John Wiley & Sons, 2007.
EBERHART, R. C., SHI, Y., Comparison between genetic algorithms and particle swarm optimization, Evolutionary Programming VII: Lecture Notes in Computer Science, vol 1447, p. 611-616, 1998
LIN, S., KERNIGHAN, B. W. An effective heuristic algorithm for the traveling-salesman problem, Operations research, v. 21, n. 2, p. 498-516, 1973.
HU, X. PSO Tutorial. Disponível em: http://www.swarmintelligence.org/tutorials.php
GLOVER, F. Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem. Graduate School of Business, University of Colorado, 1991.
LOPES, H. S. Algoritmos genéticos em projetos de engenharia: aplicações e perspectivas futuras. Anais do IV Simpósio Brasileiro de Automação Inteligente, p. 64-74, 1999.
MICHALEWICZ, Z., SCHOENAUER, M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary computation, v. 4, n. 1, p. 1-32, 1999.
VAN LAARHOVEN, P. J., AARTS, E. H. Simulated annealing. In Simulated annealing: Theory and applications p. 7-15. Springer, Dordrecht, 1987.
MITRA, D., ROMEO, F., SANGIOVANNI-VINCENTELLI, A. Convergence and finite-time behavior of simulated annealing. Advances in applied probability, v. 18, n. 3, p. 747-771, 1986.
KIRKPATRICK, S., GELATT, C. D., VECCHI, M. P. Optimization by simulated annealing. science, v. 220, n. 4598, p. 671-680, 1983.
ARAGON, C. R., JOHNSON, D. S., McGEOCH, L. A., SCHEVON, C. Optimization by simulated annealing: an experimental evaluation. In: Workshop on Statistical Physics in Engineering and Biology. Yorktown Heights, 1984.
BOZORG-HADDAD, O., SOLGI, M., LOÁICIGA, H. A. Meta-heuristic and evolutionary algorithms for engineering optimization. Hoboken, John Wiley & Sons, 2017.
STORN, R., PRICE, K. Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, v. 11, p. 341–359, 1997.
TALBI, E. G. Metaheuristics: from design to implementation (Vol. 74). John Wiley & Sons, 2009.
WANG, J. Analog Neural Network for Solving the Assignment Problem. Electronic Letters, v. 28, n. 11, p. 1047-1050, 1992.