caixeiro_viajante

Prévia do material em texto

INSTITUTO FEDERAL CATARINENSE 
Curso de Graduação em Engenharia de Controle e Automação 
 
 
 
 
 
 
 
 
 
 
Relatório do Projeto Final de Tópicos em Inteligência Artificial 
ALGORITMOS GENÉTICOS APLICADOS AO PROBLEMA DO CAIXEIRO 
VIAJANTE 
 
 
 
 
 
 
 
 
 
Autoras: XX 
Professor: XX 
Luzerna, 04 de junho de 2018 
 
 
 
SUMÁRIO 
 
1. INTRODUÇÃO....................................................................................................... 4 
2. OBJETIVOS .......................................................................................................... 7 
3. METODOLOGIA .................................................................................................... 8 
4. RESULTADOS E DISCUSSÕES ....................................................................... 101 
5. CONCLUSÃO .................................................................................................... 198 
6. REFERÊNCIAS BIBLIOGRÁFICAS ................................................................... 209 
 
 
 
 
RESUMO 
 
O presente trabalho trata da atividade avaliativa final da disciplina de Tópicos em 
Inteligência Artificial. Neste projeto final foi escolhido abordar sobre o problema do 
caixeiro viajante, aplicando os conceitos referentes à Algoritmos Genéticos. Neste 
relatório será enunciado o que são Algoritmos Genéticos e seus princípios e qual o 
problema escolhido para ser solucionado através desta técnica, além de ser exposta a 
metodologia utilizada para a solução do exercício, bem como os resultados obtidos na 
elaboração do mesmo. 
 
Palavras-chave: Algoritmos Genéticos, Caixeiro Viajante, Inteligência Artificial. 
 
4 
 
1. INTRODUÇÃO 
 
A Teoria da Evolução das Espécies descreve o desenvolvimento das espécies 
que habitavam ou habitam o planeta Terra. Desse modo, as espécies atuais descendem 
de outras espécies, as quais passaram por modificações ao longo do tempo e 
transmitiram novas características aos seus descendentes. Nessa teoria, baseiam-se 
os algoritmos genéticos, que são uma técnica de otimização ou uma tática de busca, 
estruturada e paralela, porém aleatória, que é direcionada à busca pelos pontos de 
maior aptidão, ou melhor, pontos onde a função a ser minimizada ou maximizada tem 
valores altos ou baixos. 
A busca aleatória para os algoritmos genéticos é direcionada, já que utilizam 
informações históricas afim de obter novos pontos de busca, nos quais são aguardados 
melhores desempenhos. Para realizar tal fato, são necessários efetuar iterações, onde 
cada iteração é denominada geração. Ao longo de cada processo iterativo, as noções 
de seleção e reprodução são empregues a uma população de candidatos capaz de 
variar, de acordo com a complexidade do problema e do processamento computacional. 
A partir da seleção é possível precisar quais indivíduos estarão aptos a se reproduzir, 
com uma probabilidade caracterizada pelo seu índice de aptidão. Assim, segue-se a 
reprodução, de forma que a população se mantenha evoluindo, até que se possa atingir 
um critério de parada. 
Os algoritmos genéticos possuem determinados conceitos, como a população, 
caracterizada por ser um subconjunto de todas as possibilidades de solução para certo 
problema, onde a diversidade necessita ser mantida, pois caso não ocorra, poderá 
ocasionar uma convergência prematura. Além disso, é fatídico que o tamanho ideal de 
uma população precisa ser definido por tentativa e erro. Uma população pode ser 
inicializada de forma aleatória ou de forma heurística, utilizando uma investigação 
conhecida para o problema. A população pode possuir o estado estacionário, onde se 
gera uma ou duas proles em cada iteração as quais substituem um ou dois indivíduos 
da população, ou geracional, em que toda a população é substituída pela nova ao fim 
da iteração. 
Outra propriedade dos algoritmos genéticos são os cromossomos. Cada 
cromossomo é uma das possíveis soluções para o problema. Já os genes, são uma 
posição ou elemento de um cromossomo, e o valor que um gene leva para um 
cromossomo em particular é denominado alelo. 
Quando há uma população no espaço computacional, afirma-se que há um 
genótipo. Já quando a população está contida no espaço real da solução, afirma-se que 
5 
 
existem um fenótipo. Quando ocorre uma transformação do fenótipo para o espaço de 
genótipos ocorre uma codificação. 
A Função Objetivo ou Fitness é uma função que a partir de entradas que recebe, 
replique a aptidão para certo indivíduo. Em outras palavras essa função toma uma 
solução possível como entrada e produz como saída um valor que retrata se a solução 
é boa ou não em relação ao problema apresentado. 
Os operadores genéticos, por sua vez, são operações capazes de modificar a 
composição genética da prole. 
O crossover ou cruzamento, por sua vez, é um operador de funcionamento 
semelhando ao da reprodução e ao crossover biológico que ocorre na natureza, 
aproveitando o material genético dos progenitores para a composição da prole. O 
resultado desta operação é um indivíduo que potencialmente possua as melhores 
características dos pais. Os dois principais tipos de operadores de crossover são o 
crossover de um ponto e o de múltiplos pontos. No crossover de um ponto, seleciona-
se aleatoriamente um ponto de corte do cromossomo. Já no caso do crossover de 
múltiplos pontos, são realizados mais de um ponto de corte do cromossomo. 
 Quando ocorrem pequenos ajustes aleatórios no cromossomo com a finalidade 
de obter uma nova solução, afirma-se que ocorreu uma mutação, a qual é 
demasiadamente utilizada afim de manter e introduzir diversidade na população, e 
normalmente é aplicada com baixa probabilidade. A mutação no algoritmo genético está 
intimamente ligada à verificação do espaço de busca, e é necessária para que ocorra a 
convergência no algoritmo genético. 
 Outra propriedade dos algoritmos genéticos é a seleção de sobreviventes, que 
determina quais indivíduos devem ser eliminados e quais devem ser mantidos para uma 
nova geração, o que é de extrema importância pois garante que os “melhores” 
indivíduos não sejam expulsos da população. Para isso, o elitismo pode ser utilizado, 
de maneira que o indivíduo mais apto da população sempre seja prolongado para uma 
população futura, então o mesmo não deve ser substituído. Essa seleção pode ocorrer 
baseada na idade ou na função de fitness dos sobreviventes. 
 O critério de parada de um algoritmo genético é de fiel importância, já que define 
quando a execução do mesmo terminará, definindo o ponto final da implementação. 
 A utilização de algoritmos genéticos possui várias vantagens, como o fato de não 
requerer nenhuma informação derivativa, ser mais rápido e eficiente em comparação 
com os métodos tradicionais, ter bons recursos para paralelização e fornecer uma lista 
de boas soluções invés de não apenas uma solução. Porém, os algoritmos genéticos 
também possuem certas limitações, já que não são adequados para todos os problemas 
e é estocástico, não havendo garantias sobre a otimização ou qualidade da solução. 
6 
 
 A profissão de caixeiro viajante é antiga e se trata de uma pessoa que vende 
produtos fora de onde os mesmos são produzidos. Antigamente, quando não havia 
facilidade do transporte entre cidades, os caixeiros viajantes eram a única forma de 
transportar produtos entre diferentes regiões fora das grandes cidades. 
 Porém, essa profissão possuía um dilema, que era determinar a menor rota 
possível para percorrer uma série de cidades, visitando uma única vez cada uma delas, 
retornando à cidade de origem. Esse é um complexo problema deotimização inspirado 
na necessidade dos vendedores em realizar entregas em várias cidades, percorrendo o 
menor caminho possível, de forma a reduzir o tempo necessário para a viagem e os 
possíveis custos com transporte e combustível. 
 
 
7 
 
2. OBJETIVOS 
 
Este trabalho tem por objetivo solucionar um problema que consiste em resolver 
o problema do caixeiro viajante, ou seja, determinar a menor distância possível para 
percorrer uma série de cidades, visitando apenas uma vez cada uma delas, retornando 
à cidade de origem. 
 
8 
 
3. METODOLOGIA 
 
O problema apresentado é baseado em combinar as 15 cidades de maneira a 
minimizar a distância total percorrida, de forma a solucionar o problema do caixeiro 
viajante. Para a resolução do mesmo, criamos uma população inicial, onde cada 
indivíduo que também pode ser interpretado como um caminho, recebia aleatoriamente 
uma ordem de números de cidades, sempre verificando se não haviam cidades 
repetidas num mesmo caminho. A única especificação é que não hajam cidades 
repetidas, pois passar pela mesma cidade duas vezes seria um problema, já que 
estamos procurando um caminho menor possível. Cada indivíduo ou caminho então, 
nada mais é que uma linha e quinze colunas de uma matriz que varia de 0 a 14 e não 
tem números repetidos dentro. 
As distâncias de uma cidade à outra podem ser observadas na matriz abaixo, o 
elemento [2]x[5] dessa matriz é a distância da cidade 2 até a cidade 5. Com esses dados 
é possível calcular a distância total percorrida por aquele caminho. É por isso que a 
coluna diagonal principal desta matriz é 0, já que a distância de uma determinada cidade 
por ela mesma é zero. 
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
int dist[15][15]={{ 0, 29, 82, 46, 68, 52, 72, 42, 51, 55, 29, 74, 23, 72, 46},// 0 
 {29, 0, 55, 46, 42, 43, 43, 23, 23, 31, 41, 51, 11, 52, 21}, // 1 
 {82, 55, 0, 68, 46, 55, 23, 43, 41, 29, 79, 21, 64, 31, 51}, // 2 
 {46, 46, 68, 0, 82, 15, 72, 31, 62, 42, 21, 51, 51, 43, 64}, // 3 
 {68, 42, 46, 82, 0, 74, 23, 52, 21, 46, 82, 58, 46, 65, 23}, // 4 
 {52, 43, 55, 15, 74, 0, 61, 23, 55, 31, 33, 37, 51, 29, 59}, // 5 
 {72, 43, 23, 72, 23, 61, 0, 42, 23, 31, 77, 37, 51, 46, 33}, // 6 
 {42, 23, 43, 31, 52, 23, 42, 0, 33, 15, 37, 33, 33, 31, 37}, // 7 
 {51, 23, 41, 62, 21, 55, 23, 33, 0, 29, 62, 46, 29, 51, 11}, // 8 
 {55, 31, 29, 42, 46, 31, 31, 15, 29, 0, 51, 21, 41, 23, 37}, // 9 
 {29, 41, 79, 21, 82, 33, 77, 37, 62, 51, 0, 65, 42, 59, 61}, // 10 
 {74, 51, 21, 51, 58, 37, 37, 33, 46, 21, 65, 0, 61, 11, 55}, // 11 
 {23, 11, 64, 51, 46, 51, 51, 33, 29, 41, 42, 61, 0, 62, 23}, // 12 
 {72, 52, 31, 43, 65, 29, 46, 31, 51, 23, 59, 11, 62, 0, 59}, // 13 
 {46, 21, 51, 64, 23, 59, 33, 37, 11, 37, 61, 55, 23, 59, 0}};//14 
 
Foi criada uma função especialmente para o cálculo do fitness de cada caminho, 
o melhor fitness é aquele que tem o menor valor, pois quanto menos forem as distâncias 
entre as cidades, mais curto será o caminho total. 
A reprodução foi feita utilizando o operador ORDER CROSSOVER, na qual os 
dados do pai sofrem cortes aleatórios e o filho herda os dados integralmente do pai ou 
da mãe, cada um dos pais gera um dos filhos apenas com cortes e inversões em seus 
cromossomos de posição das cidades. 
9 
 
Após a criação de novos indivíduos, sempre que acontece o cálculo do fitness é 
feito a comparação e é guardado aquele que possui a menor distância entre as cidades, 
para posteriormente ser utilizado na função do elitismo, ou seja o melhor indivíduo da 
geração dos pais é passado para geração dos filhos, sendo que um dos filhos é morto 
para que isso aconteça. 
A taxa de mutação utilizada neste código foi de 10%, uma boa taxa, garantindo 
que todos os indivíduos não sejam iguais quando a população tender para o melhor. 
A menor distância possível entre as cidades é de 291 km, no código 
implementado obteve-se uma distância mínima de 306 km, ou seja, um resultado muito 
próximo do melhor resultado possível, mesmo se observarmos que foi utilizado um 
método diferente de crossover. 
 
 
10 
 
4. RESULTADOS E DISCUSSÕES 
 
Para encontrar uma boa solução do problema do caixeiro viajante, foi utilizado 
software Codeblocks e onde foi desenvolvido o código de programação com a 
implementação de algoritmos genéticos onde se buscam indivíduos bons dentro de 
repetidas populações. 
Foram incluídas no código as bibliotecas utilizadas e definida a matriz da 
distância entre as cidades, e as demais matrizes e vetores utilizados em todo o código 
também foram definidas com seus respectivos valores fixos ou iniciais conforme parte 
do código: 
 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
 
#define num_ind 1000 
#define taxa_mutacao 10 
int dist[15][15]={ 
 { 0, 29, 82, 46, 68, 52, 72, 42, 51, 55, 29, 74, 23, 72, 46}, 
 {29, 0, 55, 46, 42, 43, 43, 23, 23, 31, 41, 51, 11, 52, 21}, 
 {82, 55, 0, 68, 46, 55, 23, 43, 41, 29, 79, 21, 64, 31, 51}, 
 {46, 46, 68, 0, 82, 15, 72, 31, 62, 42, 21, 51, 51, 43, 64}, 
 {68, 42, 46, 82, 0, 74, 23, 52, 21, 46, 82, 58, 46, 65, 23}, 
 {52, 43, 55, 15, 74, 0, 61, 23, 55, 31, 33, 37, 51, 29, 59}, 
 {72, 43, 23, 72, 23, 61, 0, 42, 23, 31, 77, 37, 51, 46, 33}, 
 {42, 23, 43, 31, 52, 23, 42, 0, 33, 15, 37, 33, 33, 31, 37}, 
 {51, 23, 41, 62, 21, 55, 23, 33, 0, 29, 62, 46, 29, 51, 11}, 
 {55, 31, 29, 42, 46, 31, 31, 15, 29, 0, 51, 21, 41, 23, 37}, 
 {29, 41, 79, 21, 82, 33, 77, 37, 62, 51, 0, 65, 42, 59, 61}, 
 {74, 51, 21, 51, 58, 37, 37, 33, 46, 21, 65, 0, 61, 11, 55}, 
 {23, 11, 64, 51, 46, 51, 51, 33, 29, 41, 42, 61, 0, 62, 23}, 
 {72, 52, 31, 43, 65, 29, 46, 31, 51, 23, 59, 11, 62, 0, 59}, 
 {46, 21, 51, 64, 23, 59, 33, 37, 11, 37, 61, 55, 23, 59, 0} 
 }; 
int pop[num_ind][15]; 
int novaPopulacao[num_ind][15]; 
int fitness[num_ind]; 
int fitnessTotal; 
int melhor[15]; 
int menor = 999999; 
int indmenor; 
 
A função calculaFitness foi declarada com suas variáveis internas. Esta função, 
além de calcular o fitness armazena também o melhor indivíduo que para melhor 
entendimento é o melhor caminho que neste caso é o que possui o menor fitness. Dentro 
de uma população de x indivíduos este código percorre cada um somando as distancias 
e armazenando sempre que encontra um indivíduo com um menor fitness, além do seu 
valor de fitness (indmenor), um vetor de 15 posições (melhor[15]) recebe a ordem das 
cidades que possui aquele fitness: 
11 
 
 
int calculaFitness() 
{ 
 int cont=0; 
 int n=0; 
 int f=0; 
 int a,b; 
 
 for(cont=0;cont<num_ind;cont++) 
 { 
 fitness[cont]=0; 
 for(n=0;n<15;n++) 
 { 
 a = pop[cont][n]; 
 b = pop[cont][n+1]; 
 f = dist[a][b]; 
 fitness[cont] = f + fitness[cont]; 
 } 
 if (fitness[cont]<menor) 
 { 
 menor = fitness[cont]; 
 indmenor = cont; 
 melhor[0]=pop[cont][0]; 
 melhor[1]=pop[cont][1]; 
 melhor[2]=pop[cont][2]; 
 melhor[3]=pop[cont][3]; 
 melhor[4]=pop[cont][4]; 
 melhor[5]=pop[cont][5]; 
 melhor[6]=pop[cont][6]; 
 melhor[7]=pop[cont][7]; 
 melhor[8]=pop[cont][8]; 
 melhor[9]=pop[cont][9]; 
 melhor[10]=pop[cont][10]; 
 melhor[11]=pop[cont][11];melhor[12]=pop[cont][12]; 
 melhor[13]=pop[cont][13]; 
 melhor[14]=pop[cont][14]; 
 } 
 } 
} 
 
A função inteiroAleatorio foi declarada para posterior utilização delimitando um 
valor máximo e gerando números inteiros e aleatórios. Esta função é utilizada para gerar 
uma população inicial e também para criação do pai e da mãe na reprodução: 
 
int inteiroAleatorio(int maximo) 
{ 
 return(rand() % (maximo+1)); 
 } 
 
 
A função geraIndiv é a função que dá início a uma população do número de 
indivíduos declarado como num_ind anteriormente. Ela cria uma matriz onde o número 
de indivíduos é o número de linhas e quinze é o número de colunas e dentro destas 
colunas, são preenchidos aleatoriamente os valores das cidades de 0 a 14. Portanto 
12 
 
cada uma das linhas desta matriz corresponde a uma possibilidade de caminho. Esta 
função garante que os valores preenchidos aleatoriamente não se repitam dentro de 
uma mesma linha, e, portanto, não existam indivíduos deficientes: 
 
int geraIndiv() 
 { 
 int ind,coluna,aleat, col_1,a; 
 for(ind=0;ind<num_ind;ind++) 
 { 
 for(coluna=0;coluna<15;coluna++) 
 { 
 col_1 = coluna-1; 
 aleat = inteiroAleatorio(14); 
 while(col_1>=0) 
 { 
 a = pop[ind][col_1]; 
 if(aleat == a) 
 { 
 aleat = inteiroAleatorio(14); 
 col_1 = (coluna - 1); 
 } 
 else 
 { 
 col_1--; 
 } 
 } 
 pop[ind][coluna] = aleat; 
 } 
 } 
 } 
 
Para a reprodução dos indivíduos, foi declarada a função reproducao que 
consiste em sortear através da função inteiroAleatorio dois indivíduos chamados pai e 
mãe, dentro da população já criada para gerar dois filhos da nova população. Estes 
filhos recebem as características do pai ou da mãe com uma ordenação diferente de 
genes. Para variação desta ordenação de genes, também aleatoriamente, pode utilizar 
um ou outro arranjo dos genes dos pais. No termino desta reprodução de novos filhos, 
os valores são sobrepostos a população e é chamada a função calculaFitness para obter 
os fitness desta nova população e verificar se existe um indivíduo melhor, ou seja, que 
possui um menor fitness que o armazenado: 
 
void reproducao() 
 { 
 int xp, xm, yp, ym, colp, colm, c; 
 int pai[15]; 
 int mae[15]; 
 int conta=0; 
 int conta2=0; 
 
 while(conta<num_ind) 
 { 
13 
 
 xp = inteiroAleatorio(num_ind-1); 
 for(colp=0;colp<15;colp++) 
 { 
 yp = pop[xp][colp]; 
 pai[colp] = yp; 
 } 
 xm = inteiroAleatorio(num_ind-1); 
 for(colm=0;colm<15;colm++) 
 { 
 ym = pop[xm][colm]; 
 mae[colm] = ym; 
 } 
 c = inteiroAleatorio(10); 
 if(c<5) 
 { 
 //Filho 1 
 novaPopulacao[conta][0]=pai[4]; 
 novaPopulacao[conta][1]=pai[5]; // filho 1 gene 1 
 novaPopulacao[conta][2]=pai[6]; // filho 1 gene 2 
 novaPopulacao[conta][3]=pai[7]; // filho 1 gene 3 
 novaPopulacao[conta][4]=pai[8]; // filho 1 gene 4 
 novaPopulacao[conta][5]=pai[0]; // filho 1 gene 5 
 novaPopulacao[conta][6]=pai[1]; 
 novaPopulacao[conta][7]=pai[2]; // filho 1 gene 1 
 novaPopulacao[conta][8]=pai[3]; // filho 1 gene 2 
 novaPopulacao[conta][9]=pai[9]; // filho 1 gene 3 
 novaPopulacao[conta][10]=pai[10]; // filho 1 gene 4 
 novaPopulacao[conta][11]=pai[11]; // filho 1 gene 5 
 novaPopulacao[conta][12]=pai[12]; // filho 1 gene 3 
 novaPopulacao[conta][13]=pai[13]; // filho 1 gene 4 
 novaPopulacao[conta][14]=pai[14]; // filho 1 gene 5 
 //Filho 2 
 novaPopulacao[conta+1][0]=mae[6]; 
 novaPopulacao[conta+1][1]=mae[7]; // filho 1 gene 1 
 novaPopulacao[conta+1][2]=mae[8]; // filho 1 gene 2 
 novaPopulacao[conta+1][3]=mae[9]; // filho 1 gene 3 
 novaPopulacao[conta+1][4]=mae[0]; // filho 1 gene 4 
 novaPopulacao[conta+1][5]=mae[1]; // filho 1 gene 5 
 novaPopulacao[conta+1][6]=mae[2]; 
 novaPopulacao[conta+1][7]=mae[3]; // filho 1 gene 1 
 novaPopulacao[conta+1][8]=mae[4]; // filho 1 gene 2 
 novaPopulacao[conta+1][9]=mae[5]; // filho 1 gene 3 
 novaPopulacao[conta+1][10]=mae[10]; // filho 1 gene 4 
 novaPopulacao[conta+1][11]=mae[11]; // filho 1 gene 5 
 novaPopulacao[conta+1][12]=mae[12]; // filho 1 gene 3 
 novaPopulacao[conta+1][13]=mae[13]; // filho 1 gene 4 
 novaPopulacao[conta+1][14]=mae[14]; // filho 1 gene 5 
 
 conta= conta+2; 
 } 
 else 
 { 
 //Filho 1 
 novaPopulacao[conta][0]=pai[1]; 
 novaPopulacao[conta][1]=pai[2]; // filho 1 gene 1 
 novaPopulacao[conta][2]=pai[3]; // filho 1 gene 2 
 novaPopulacao[conta][3]=pai[4]; // filho 1 gene 3 
 novaPopulacao[conta][4]=pai[5]; // filho 1 gene 4 
 novaPopulacao[conta][5]=pai[9]; // filho 1 gene 5 
 novaPopulacao[conta][6]=pai[10]; 
14 
 
 novaPopulacao[conta][7]=pai[11]; // filho 1 gene 1 
 novaPopulacao[conta][8]=pai[12]; // filho 1 gene 2 
 novaPopulacao[conta][9]=pai[13]; // filho 1 gene 3 
 novaPopulacao[conta][10]=pai[14]; // filho 1 gene 4 
 novaPopulacao[conta][11]=pai[6]; // filho 1 gene 5 
 novaPopulacao[conta][12]=pai[7]; // filho 1 gene 3 
 novaPopulacao[conta][13]=pai[8]; // filho 1 gene 4 
 novaPopulacao[conta][14]=pai[0]; // filho 1 gene 5 
 //Filho 2 
 novaPopulacao[conta+1][0]=mae[0]; 
 novaPopulacao[conta+1][1]=mae[1]; // filho 1 gene 1 
 novaPopulacao[conta+1][2]=mae[2]; // filho 1 gene 2 
 novaPopulacao[conta+1][3]=mae[3]; // filho 1 gene 3 
 novaPopulacao[conta+1][4]=mae[11]; // filho 1 gene 4 
 novaPopulacao[conta+1][5]=mae[12]; // filho 1 gene 5 
 novaPopulacao[conta+1][6]=mae[13]; 
 novaPopulacao[conta+1][7]=mae[14]; // filho 1 gene 1 
 novaPopulacao[conta+1][8]=mae[4]; // filho 1 gene 2 
 novaPopulacao[conta+1][9]=mae[5]; // filho 1 gene 3 
 novaPopulacao[conta+1][10]=mae[6]; // filho 1 gene 4 
 novaPopulacao[conta+1][11]=mae[7]; // filho 1 gene 5 
 novaPopulacao[conta+1][12]=mae[8]; // filho 1 gene 3 
 novaPopulacao[conta+1][13]=mae[9]; // filho 1 gene 4 
 novaPopulacao[conta+1][14]=mae[10]; // filho 1 gene 5 
 conta = conta+2; 
 } 
 } 
 for(conta=0; conta <num_ind ;conta++){ 
 pop[conta][0]=novaPopulacao[conta][0]; 
 pop[conta][1]=novaPopulacao[conta][1]; 
 pop[conta][2]=novaPopulacao[conta][2]; 
 pop[conta][3]=novaPopulacao[conta][3]; 
 pop[conta][4]=novaPopulacao[conta][4]; 
 pop[conta][5]=novaPopulacao[conta][5]; 
 pop[conta][6]=novaPopulacao[conta][6]; 
 pop[conta][7]=novaPopulacao[conta][7]; 
 pop[conta][8]=novaPopulacao[conta][8]; 
 pop[conta][9]=novaPopulacao[conta][9]; 
 pop[conta][10]=novaPopulacao[conta][10]; 
 pop[conta][11]=novaPopulacao[conta][11]; 
 pop[conta][12]=novaPopulacao[conta][12]; 
 pop[conta][13]=novaPopulacao[conta][13]; 
 pop[conta][14]=novaPopulacao[conta][14]; 
 } 
 calculaFitness(); 
 } 
 
 
A função de mutacao por sua vez, consiste em alterar os genes de um indivíduo 
escolhido aleatoriamente. No caso das cidades, como não se pode repetir cidades, foi 
adotado o método de trocar o conteúdo de dois genes de posição entre si, o gene fixo 
escolhido para trocar com algum gene aleatório é o de posição 5. Da mesma forma que 
as demais funções, é feito de maneira aleatória tanto a mutação em si como o gene a 
sofrer a mutação. Assim é sobrescrito alguns indivíduos da população e a função 
calculaFitness novamente é chamada com o objetivo de verificar se há um indivíduo 
15 
 
com menor fitness que o melhor obtido até o momento, ou seja, se através da mutação 
de alguns indivíduos, se obteve um indivíduo melhor. 
 
void mutacao() 
{ 
int cont=0; 
int temp=0; 
int individuoMutante[15]; 
 for(cont=0;cont<num_ind;cont++) 
 { 
 if((inteiroAleatorio(100))<taxa_mutacao) 
 { 
 // faz uma cópia do individuo a sofrer mutação 
 individuoMutante[0]=pop[cont][0]; 
 individuoMutante[1]=pop[cont][1]; 
 individuoMutante[2]=pop[cont][2]; 
 individuoMutante[3]=pop[cont][3]; 
 individuoMutante[4]=pop[cont][4]; 
 individuoMutante[5]=pop[cont][5]; 
 individuoMutante[6]=pop[cont][6]; 
 individuoMutante[7]=pop[cont][7]; 
 individuoMutante[8]=pop[cont][8]; 
 individuoMutante[9]=pop[cont][9]; 
 individuoMutante[10]=pop[cont][10]; 
 individuoMutante[11]=pop[cont][11]; 
 individuoMutante[12]=pop[cont][12]; 
 individuoMutante[13]=pop[cont][13]; 
 individuoMutante[14]=pop[cont][14]; 
 // verifica qual o gene a sofrer mutação 
 temp=inteiroAleatorio(14); // 0 a 14 pois são 15 cidades 
 // encontra um novo valor para o gene 
 if(temp==0) 
 { 
 individuoMutante[0]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][0]; 
 } 
 if(temp==1) 
 { 
 individuoMutante[1]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][1]; 
 } 
 if(temp==2) 
 { 
 individuoMutante[2]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][2]; 
 } 
 if(temp==3) 
 { 
 individuoMutante[3]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][3]; 
 } 
 if(temp==4) 
 { 
 individuoMutante[4]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][4]; 
 } 
 if(temp==5) 
 { 
16 
 
 individuoMutante[5]=pop[cont][0]; 
 individuoMutante[0]=pop[cont][5]; 
 } 
 if(temp==6) 
 { 
 individuoMutante[6]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][6]; 
 } 
 if(temp==7) 
 { 
 individuoMutante[7]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][7]; 
 } 
 if(temp==8) 
 { 
 individuoMutante[8]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][8]; 
 } 
 if(temp==9) 
 { 
 individuoMutante[9]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][9]; 
 } 
 if(temp==10) 
 { 
 individuoMutante[10]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][10]; 
 } 
 if(temp==11) 
 { 
 individuoMutante[11]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][11]; 
 } 
 if(temp==12) 
 { 
 individuoMutante[12]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][12]; 
 } 
 if(temp==13) 
 { 
 individuoMutante[13]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][13]; 
 } 
 if(temp==14) 
 { 
 individuoMutante[14]=pop[cont][5]; 
 individuoMutante[5]=pop[cont][14]; 
 } 
 // se for válido grava o indivíduo mutante na população 
 pop[cont][0]=individuoMutante[0]; 
 pop[cont][1]=individuoMutante[1]; 
 pop[cont][2]=individuoMutante[2]; 
 pop[cont][3]=individuoMutante[3]; 
 pop[cont][4]=individuoMutante[4]; 
 pop[cont][5]=individuoMutante[5]; 
 pop[cont][6]=individuoMutante[6]; 
 pop[cont][7]=individuoMutante[7]; 
 pop[cont][8]=individuoMutante[8]; 
 pop[cont][9]=individuoMutante[9]; 
 pop[cont][10]=individuoMutante[10]; 
17 
 
 pop[cont][11]=individuoMutante[11]; 
 pop[cont][12]=individuoMutante[12]; 
 pop[cont][13]=individuoMutante[13]; 
 pop[cont][14]=individuoMutante[14]; 
 } 
 } 
 calculaFitness(); 
} 
 
A função de elitismo garante que o melhor indivíduo encontrado na população 
atual faça parte da nova população. Desta forma o melhor individuo sempre permanece 
com o passar das gerações de indivíduos: 
void elitismo() 
{ 
 int elemento; 
 elemento=inteiroAleatorio(num_ind-1); 
 pop[elemento][0]=melhor[0]; 
 pop[elemento][1]=melhor[1]; 
 pop[elemento][2]=melhor[2]; 
 pop[elemento][3]=melhor[3]; 
 pop[elemento][4]=melhor[4]; 
 pop[elemento][5]=melhor[5]; 
 pop[elemento][6]=melhor[6]; 
 pop[elemento][7]=melhor[7]; 
 pop[elemento][8]=melhor[8]; 
 pop[elemento][9]=melhor[9]; 
 pop[elemento][10]=melhor[10]; 
 pop[elemento][11]=melhor[11]; 
 pop[elemento][12]=melhor[12]; 
 pop[elemento][13]=melhor[13]; 
 pop[elemento][14]=melhor[14]; 
 } 
 
Finamente a função principal inicia uma população de maneira aleatória através 
da função geraIndiv e calcula o fitness e encontra o melhor através da função 
calculaFitness. Depois gera uma nova população através da reprodução, altera alguns 
de seus indivíduos através da mutação e passa o melhor para a próxima geração. E 
assim refeito para 10000 gerações. 
 
void main() 
{ 
 int contGeracao=0; 
 geraIndiv(); 
 calculaFitness(); 
 
 while(contGeracao<10000) 
 {contGeracao++; 
 reproducao(); 
 mutacao(); 
 elitismo(); 
 } 
 
} 
18 
 
O melhor valor obtido para população com 1000 indivíduos, taxa de mutação de 
10% e 10000 gerações foi de 306. 
 
 
19 
 
5. CONCLUSÃO 
 
Os Algoritmos Genéticos, conforme afirmado neste trabalho, se tratam de uma 
técnica de busca demasiadamente utilizada na área da ciência da computação, com a 
finalidade de encontrar soluções aproximadas em problemas de otimização e busca, ou 
seja concentram uma tática de busca estruturada e paralela, porém aleatória, a qual é 
direcionada à busca dos pontos de maior aptidão, onde a função a ser maximizada ou 
minimizada – fitness, possui valores altos ou baixos. 
Tal técnica de otimização, oriunda dos princípios da Teoria da Evolução das 
Espécies, possui uma busca aleatória direcionada, já que são utilizadas informações 
históricas para se obter novos pontos de busca, onde são aguardados melhores 
desempenhos. Para que isso seja possível, se faz necessário o uso de iterações, onde 
as noções de seleção e reprodução são empregues a uma população de candidatos, a 
qual é capaz de variar, de acordo com a complexidade do problema e do processamento 
computacional. 
A partir da seleção é possível precisar quais indivíduos estarão aptos a se 
reproduzir, com uma probabilidade caracterizada pelo seu índice de aptidão. Desse 
modo, segue-se a reprodução, de forma que a população se mantenha evoluindo, até 
que se possa atingir um critério de parada. 
A partir dos conceitos e propriedades referentes aos Algoritmos Genéticos, foi 
possível solucionar um exercício, acima explícito, o qual consistia em solucionar o 
problema do caixeiro viajante, uma antiga profissão que se trata de uma pessoa que 
A profissão de caixeiro viajante é antiga e se trata de uma pessoa que vende produtos 
fora de onde os mesmos são produzidos. Antigamente, quando não havia facilidade do 
transporte entre cidades, os caixeiros viajantes eram a única forma de transportar 
produtos entre diferentes regiões fora das grandes cidades. 
 Porém, essa profissão possuía um dilema, que era determinar a menor rota 
possível para percorrer uma série de cidades, visitando uma única vez cada uma delas, 
retornando à cidade de origem. Esse é um complexo problema de otimização inspirado 
na necessidade dos vendedores em realizar entregas em várias cidades, percorrendo o 
menor caminho possível, de forma a reduzir o tempo necessário para a viagem e os 
possíveis custos com transporte e combustível. Ao findar este trabalho é importante 
ressaltar que o desenvolvimento do mesmo proporcionou um melhor entendimento do 
conteúdo abordado na disciplina de Tópicos em Inteligência Artificial, concretizando os 
objetivos da realização do mesmo. 
 
20 
 
6. REFERÊNCIAS BIBLIOGRÁFICAS 
 
[1] SILVA, Marco Aurélio. Inteligência Artificial. Disponível em: < 
https://brasilescola.uol.com.br/informatica/inteligencia-artificial.htm>. Acesso em: 14 de 
março de 2018. 
[2] POZO, Aurora; CAVALHEIRO, Andrea de Fátima; ISHIDA, Celso; SPINOSA, 
Eduardo; RODRIGUES, Ernesto Malta. João Roberto; OLIVEIRA, André Schneider. 
Computação Evolutiva. Disponível em: 
<http://www.inf.ufpr.br/aurora/tutoriais/Ceapostila.pdf>. Acesso em: 05 de abril de 2018. 
 [3] MAGALHÃES, Lana. Teoria da Evolução. Disponível em: 
<https://www.todamateria.com.br/teoria-da-evolucao/>. Acesso em: 05 de abril de 2018. 
[4] Conteúdo ICMC USP. Algoritmos Genéticos. Disponível 
em:<http://conteudo.icmc.usp.br/pessoas/andre/research/genetic/>. Acesso em: 05 de 
abril de 2018. 
[5] KERSCHBAUMER, Ricardo. Algoritmos Genéticos. Disponível 
em:<http://professor.luzerna.ifc.edu.br/ricardo-kerschbaumer/wp-
content/uploads/sites/43/2018/03/5-Algoritmos-Gen%C3%A9ticos.pdf>. Acesso em: 05 
de abril de 2018. 
[5] KERSCHBAUMER, Ricardo. Exemplo de Algoritmos Genéticos. Disponível 
em:<http://professor.luzerna.ifc.edu.br/ricardo-kerschbaumer/wp 
content/uploads/sites/43/2018/03/Exemplo-de-Algoritmo-Gen%C3%A9tico-1.pdf>. 
Acesso em: 05 de abril de 2018. 
[6] KERSCHBAUMER, Ricardo. Exercício Algoritmos Genéticos. Disponível 
em:<http://professor.luzerna.ifc.edu.br/ricardo-kerschbaumer/wp-
content/uploads/sites/43/2018/04/Exerc%C3%ADcio-de-algoritmos-
gen%C3%A9ticos.pdf>. Acesso em: 05 de abril de 2018. 
[7] AUTOR DESCONHECIDO. Caixeiro Viajante. Disponível em: < 
https://pt.wikipedia.org/wiki/Caixeiro-viajante>. Acesso em: 20 de junho de 2018. 
[8] AUTOR DESCONHECIDO. Problema do Caixeiro Viajante. Disponível em: < 
https://pt.wikipedia.org/wiki/Problema_do_caixeiro-viajante>. Acesso em: 20 de junho 
de 2018. 
[9] SARAIVA, Filipe de Oliveira; OLIVEIRA, Antonio Costa. Uma Comparação Empírica 
de Operadores de Crossover para o Problema de Job Shop com Datas de 
Entregas. Disponível em: 
<http://www.abepro.org.br/biblioteca/enegep2010_TN_STO_118_772_15277.pdf>. 
Acesso em: 20 de junho de 2018.