CaixeiroViajante

a) Estrutura do cromossomo
Para cada vértice de um circuito hamiltoniano existe um sucessor. No algoritmo genético desenvolvido, cada cromossomo ri = ( si1, si2,...,sin) representa um circuito, onde o gene s,, é o vértice sucessor do vértice x, no í-ésimo circuito. No processo de geração de uma população inicial de cromossomos aleatórios, a probabilidade de um vétice suceder outro foi adotada como sendo inversamente proporcional ao quadrado da distância entre os vértices.
b) Avaliação do fitness
O fitness de um cromossomo representa a sua capacidade de adaptação ao meio ambiente. Neste algoritmo adotou-se um fitness igual ao custo do circuito, isto é:
Ci = Fitness (ri) = somatório(w(xj,sij)de j=1 ate n onde w (xj , sij) é o custo associado ao deslocamento de xj, a sij .
Assim, na avaliação de um roteiro, (cromossomo), quanto maior o fitness calculado, menor sua capacidade de adequação e vice-versa.
c) Processo de seleção natural
Considerando a ordenação estabelecia na população, na qual C1 <= C2 <= ... <= Cn, a escolha de um cromossomo para a realização de um cruzamento é feita considerando uma distribuição de probabilidade inversamente proporcional ao índice dos cromossomos na população. Em outras palavras, quanto menor o índice do cromossomo, maior é a probabilidade de escolha. De acordo com esta distribuição, a função de seleção é a seguinte:
Select (R) ={rj E R| j=[(-1+raiz quadrada de (1+4.rnd(n^2+n))/2]} onde rnd E [0,l) é um número aleatório uniformemente distribuído, e [b] é o menor inteiro maior do que b.
d) Processo de reprodução
O cruzamento entre cromossomos é realizado pela operação de crossover. Neste procedimento, o maís próximo dos sucessores de cada vértice nos cromossomos ancestrais (gene dominante) é herdado pelo cromossomo filho. Esta operação é definida pela seguinte função: rn = Crossover (ri,rj) =snk={sik se w(xk,sik)<=w(xk,sik) {sik em caso contrario
e) Processo de mutação
Ao ser