Skip to content
/ AI-and-ML Public
forked from mct96/AI-and-ML

Implementação de alguns algoritmos.

0 stars 1 fork Branches Tags Activity
Star
Notifications You must be signed in to change notification settings

jjpdr/AI-and-ML

BranchesTags
 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
C++/GeneticAlgorithm
C++/GeneticAlgorithm
 
 
resources
resources
 
 
GeneticAlgoritm.py
GeneticAlgoritm.py
 
 
readme.md
readme.md
 
 

Repository files navigation

Algoritmo Genético

Implementação do algoritmo genético para a solução do problema do caxeiro viajante. A implementação desse algoritmo possui algumas variações em relação a forma canônica.

Heurística Implementada

Diferente de muitas implementações que utiliza os cromossomos no intervalo [0, 1], está implementação utiliza o nome da cidade como cromossomo. Nos teste realizados há 15 cidades, ou seja, 15 possibilidades para cada cromossomo. Para otimizar o processo (acelerar a convergência) a escolha de qual cidade substituir no caso de mutação é feita por meio de um heurística. Essa heuristica seleciona a cidade que reduz o custo da função de fitness.

Parâmetros

Esta implementação possui diversos parâmetros para ajuste. Entre eles:

  • Tamanho da população
  • Tamanho do genes
  • Função de fitness
  • Número máximo de gerações
  • Probabilidade de mutação.

Algumas considerações

  • A convergência não é garantida, porém não estou certo se isso se deve a implementação ou a natureza do problema de teste.
  • A escolha dos indivíduos selecionados para o crossover é feita iterativamente formando pares baseado no valor de fitness associado a cada indivíduo. Ex: Ind_1 com Ind_2, Ind_3 com Ind_4, e assim por diante.
  • Seleção da porção para o crossover é feito através da escolha de uma porção qualquer do genes, em vez de usar a porção inicial.

Demonstrações

Amostra 1 Amostra 2 Amostra 3

Exemplo de execução:

Legenda

Simbolo Significado
[...] Geração
hg Maior valor da geração
av Valor médio da geração
prob Probabilidade de haver mutação 
[0    ] hg: -35100.00, av: -16746.00, prob: 0.30
[500  ] hg: -1200.00, av: -6040.00, prob: 0.30
[510  ] hg: -1200.00, av: -6002.00, prob: 0.30
[520  ] hg: -1200.00, av: -5400.00, prob: 0.30
[530  ] hg: -1200.00, av: -5682.00, prob: 0.30
[540  ] hg: -1200.00, av: -6268.00, prob: 0.30
[550  ] hg: -1200.00, av: -5912.00, prob: 0.30
[560  ] hg: -1000.00, av: -5788.00, prob: 0.30
[570  ] hg: -1000.00, av: -4708.00, prob: 0.30
[580  ] hg: -1000.00, av: -5814.00, prob: 0.30
[590  ] hg: -1000.00, av: -5742.00, prob: 0.30
[600  ] hg: -1000.00, av: -5812.00, prob: 0.30
[610  ] hg: -1000.00, av: -5810.00, prob: 0.30
[620  ] hg: -1000.00, av: -5006.00, prob: 0.30
[630  ] hg: -1000.00, av: -5436.00, prob: 0.30
[640  ] hg: -1000.00, av: -5358.00, prob: 0.30
[650  ] hg: -1000.00, av: -5742.00, prob: 0.30
[660  ] hg: -800.00, av: -6214.00, prob: 0.30
[670  ] hg: -800.00, av: -6048.00, prob: 0.30
[680  ] hg: -800.00, av: -5410.00, prob: 0.30
[690  ] hg: -800.00, av: -4846.00, prob: 0.30
[700  ] hg: -800.00, av: -5454.00, prob: 0.30
[710  ] hg: -800.00, av: -5354.00, prob: 0.30
[720  ] hg: -800.00, av: -4824.00, prob: 0.30
[730  ] hg: -800.00, av: -5382.00, prob: 0.30
[740  ] hg: -800.00, av: -5632.00, prob: 0.30
[750  ] hg: -800.00, av: -5616.00, prob: 0.30
[760  ] hg: -800.00, av: -5782.00, prob: 0.30
[770  ] hg: -800.00, av: -5458.00, prob: 0.30
[780  ] hg: -800.00, av: -5448.00, prob: 0.30
[790  ] hg: -800.00, av: -5504.00, prob: 0.30
[800  ] hg: -800.00, av: -5454.00, prob: 0.30
[810  ] hg: -800.00, av: -5508.00, prob: 0.30
[820  ] hg: -600.00, av: -5510.00, prob: 0.30
[830  ] hg: -600.00, av: -5408.00, prob: 0.30
[840  ] hg: -600.00, av: -5192.00, prob: 0.30
[850  ] hg: -600.00, av: -4990.00, prob: 0.30
[860  ] hg: -600.00, av: -5006.00, prob: 0.30
[870  ] hg: -600.00, av: -5196.00, prob: 0.30
[880  ] hg: -600.00, av: -4456.00, prob: 0.30
[890  ] hg: -600.00, av: -5132.00, prob: 0.30
[900  ] hg: -600.00, av: -4872.00, prob: 0.30
[910  ] hg: -600.00, av: -4796.00, prob: 0.30
[920  ] hg: -600.00, av: -5786.00, prob: 0.30
[930  ] hg: -600.00, av: -5380.00, prob: 0.30
[940  ] hg: -600.00, av: -4700.00, prob: 0.30
[950  ] hg: -600.00, av: -4458.00, prob: 0.30
[960  ] hg: -600.00, av: -5264.00, prob: 0.30
[970  ] hg: -400.00, av: -5292.00, prob: 0.30
[980  ] hg: -400.00, av: -4486.00, prob: 0.30
[990  ] hg: -400.00, av: -5110.00, prob: 0.30
[1000 ] hg: -400.00, av: -4856.00, prob: 0.30
[1010 ] hg: -400.00, av: -4890.00, prob: 0.30
[1020 ] hg: -400.00, av: -5620.00, prob: 0.30
[1030 ] hg: -400.00, av: -4506.00, prob: 0.30
[1040 ] hg: -400.00, av: -4930.00, prob: 0.30
[1050 ] hg: -400.00, av: -4954.00, prob: 0.30
[1060 ] hg: -400.00, av: -5750.00, prob: 0.30
[1070 ] hg: -400.00, av: -4844.00, prob: 0.30
[1080 ] hg: -200.00, av: -4650.00, prob: 0.30
[1090 ] hg: -200.00, av: -4894.00, prob: 0.30
[1100 ] hg: -200.00, av: -4700.00, prob: 0.30
[1110 ] hg: -200.00, av: -4708.00, prob: 0.30
[1120 ] hg: -200.00, av: -4010.00, prob: 0.30
[1130 ] hg: -200.00, av: -4954.00, prob: 0.30
[1140 ] hg: -200.00, av: -4350.00, prob: 0.30
[1150 ] hg: -200.00, av: -3626.00, prob: 0.30
Highest value reached.
['B', 'N', 'M', 'F', 'K', 'O', 'I', 'G', 'G', 'E', 'L', 'D', 'C', 'J', 'A'] -> f: -15700.000000 d:7100.000000
['O', 'F', 'N', 'D', 'K', 'J', 'I', 'H', 'H', 'E', 'L', 'M', 'B', 'C', 'A'] -> f: -14800.000000 d:6200.000000
['F', 'N', 'M', 'L', 'B', 'H', 'H', 'O', 'G', 'E', 'I', 'D', 'C', 'K', 'J'] -> f: -14800.000000 d:6200.000000
['N', 'D', 'C', 'L', 'O', 'L', 'I', 'B', 'F', 'H', 'E', 'K', 'J', 'G', 'A'] -> f: -14700.000000 d:6100.000000
['O', 'M', 'K', 'L', 'D', 'J', 'H', 'H', 'G', 'E', 'A', 'N', 'C', 'B', 'I'] -> f: -14600.000000 d:6000.000000
['O', 'L', 'N', 'K', 'K', 'M', 'I', 'F', 'G', 'E', 'B', 'J', 'C', 'H', 'A'] -> f: -13600.000000 d:5000.000000
['O', 'A', 'D', 'L', 'K', 'J', 'I', 'M', 'G', 'E', 'F', 'H', 'C', 'C', 'B'] -> f: -13500.000000 d:4900.000000
['I', 'N', 'L', 'M', 'K', 'J', 'O', 'D', 'G', 'E', 'F', 'C', 'C', 'H', 'A'] -> f: -13400.000000 d:4800.000000
['O', 'N', 'H', 'L', 'K', 'J', 'I', 'G', 'G', 'E', 'F', 'D', 'C', 'M', 'A'] -> f: -13000.000000 d:4400.000000
['O', 'N', 'M', 'E', 'J', 'K', 'I', 'H', 'G', 'D', 'F', 'C', 'C', 'B', 'A'] -> f: -11600.000000 d:3000.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'B', 'F', 'D', 'C', 'C', 'A'] -> f: -10800.000000 d:2200.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'G', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -10200.000000 d:1600.000000
['N', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -10100.000000 d:1500.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'E', 'D', 'C', 'B', 'A'] -> f: -10000.000000 d:1400.000000
['O', 'M', 'L', 'J', 'K', 'C', 'I', 'F', 'G', 'E', 'H', 'D', 'A', 'B', 'N'] -> f: -3500.000000 d:4900.000000
['O', 'N', 'M', 'L', 'I', 'J', 'D', 'H', 'G', 'C', 'F', 'B', 'E', 'K', 'A'] -> f: -3400.000000 d:4800.000000
['O', 'N', 'M', 'L', 'K', 'J', 'E', 'H', 'D', 'G', 'F', 'I', 'C', 'B', 'A'] -> f: -1800.000000 d:3200.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'E', 'F', 'D', 'C', 'B', 'A'] -> f: -200.000000 d:1600.000000
['O', 'N', 'M', 'L', 'K', 'J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A'] -> f: 0.000000 d:1400.000000

About

Implementação de alguns algoritmos.

Resources

Readme
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages

  • C++ 39.5%
  • Makefile 30.2%
  • Python 15.4%
  • CMake 14.9%