Criar algoritmo genético em Java para Iniciantes – Parte 1

Criar algoritmo genético em Java para IniciantesUm algoritmo genético é uma técnica de pesquisa que permite encontrar soluções aproximadas para problemas de optimização cuja melhor solução é impossível de encontrar em tempo útil. Os algoritmos genéticos utilizam técnicas inspiradas na biologia evolutiva tais como a selecção natural, crossing over, mutações, etc…

Para mostrar todo o processo de criação e aplicação de um algoritmo genético, vamos resolver um problema de matemática conhecido como o Problema do Caixeiro-Viajante.

Se estás interessado neste assunto e queres aprender a criar um algoritmo genético como mostro no gif abaixo, acompanha-me nesta jornada!

Algoritmo Genético - Preview

Entender o problema do caixeiro-viajante

Imagina que és um vendedor e foi-te dado um mapa como o que está representado abaixo.

Algoritmo genetico cidades

O mapa é composto por 25 cidades portuguesas e é te dito que o teu trabalho é visitar cada uma das cidades para vender alguma coisa (consideramos que o vendedor começa numa cidade arbitrária, passa por cada uma das cidades do mapa uma vez e volta à cidade inicial). Provavelmente antes de iniciar a jornada de vendas íamos mentalmente planear um percurso a percorrer que minimizasse o tempo de viagem. Contudo com tantas cidades é difícil de decidir qual o menor percurso a percorrer e mesmo que encontrássemos um bom percurso como iríamos testar se ele era o melhor percurso?

A resposta a esta pergunta é que não podemos, pelo menos de forma prática e em tempo útil. A razão disto é que no mapa acima existem 25! (25 factorial) caminhos possíveis, ou seja, 15.511.210.043.330.985.984.000.000 caminhos, isto para apenas 25 cidades.

Então, para encontrar o melhor caminho na rota teríamos de testar 15.511.210.043.330.985.984.000.000 caminhos diferentes. Isto é impossível de concretizar em tempo útil mesmo para os computadores actuais.

Uma vez que não é prático encontrar a melhor solução para o problema, teremos que encontrar uma solução quase tão boa quanto a melhor solução. Com um algoritmo genético somos capazes de encontrar uma dessas soluções em tempo útil.

Funcionamento do algoritmo genético

Como sabemos, o algoritmo genético é baseado no processo de selecção natural ou seja, num algoritmo genético tentamos pegar nas propriedades fundamentais da selecção natural e aplicá-las ao problema em causa.

O algoritmo genético funciona da seguinte forma:

Inicialização: Criação de uma população inicial, normalmente aleatória com o tamanho desejado.

Evolução: Os membros da população são evoluídos e calculamos o “fitness” para cada membro. O “fitness” é calculado através de uma função que avalia o quão bom um membro é perante os nossos requisitos. No nosso problema os percursos com um menor comprimento terão um menor fitness uma vez que pretendemos o menor percurso.

Selecção: O nosso objectivo é melhorar o “fitness” nas nossas populações. A selecção ajuda-nos a concretizar isto eliminando os membros da população com um “fitness” mais baixo (ou seja, os percursos com um comprimento maior).

Crossover: Durante o crossover são criados novos indivíduos combinando aspectos diferentes dos indivíduos mais evoluídos dentro das nossas populações. Com o crossover esperamos que sejam criados novos indivíduos ainda mais evoluídos do que os existentes.

Mutação: Com as mutações conseguimos criar alguma imprevisibilidade e aleatoriedade nas nossas populações. Se não houvessem mutações todas as soluções que poderíamos encontrar seriam baseadas na nossa população inicial o que não seria muito bom.

Repetição: O último passo é repetir todos os passos acima durante um número finito de vezes, concretizando assim várias gerações. Quanto maior for o número de repetições do algoritmo, melhor será a solução encontrada. Um algoritmo genético pode ser repetido durante um número definido de vezes, por exemplo 200 vezes ou até a solução encontrada ser melhor que a solução mínima exigida (por exemplo, correr o algoritmo até o caminho encontrado ter menos de 1000km).

Encontrar a solução

Encontrar uma solução para o problema do caixeiro viajante implica criar um algoritmo genético de uma forma muito especifica. Uma solução válida para o problema necessitaria de representar uma rota onde cada cidade é incluída pelo menos uma vez e só uma vez. Se um percurso inclui uma cidade mais do que uma vez ou não inclui todas as cidades do mapa acima então esse percurso não seria válido. Nós queremos garantir que iremos gastar tempo de computação a calcular apenas percursos válidos. Para garantir que o algoritmo genético satisfaz estes requisitos, iremos precisar de criar métodos de mutação e de crossover especiais.

Em primeiro lugar o método de mutação deve apenas ser capaz de baralhar o percurso. Ele não deve ser capaz de adicionar ou remover uma cidade do percurso, de outra forma estaríamos a arriscar criar um percurso inválido. Portanto iremos utilizar um tipo de mutação chamado mutação de troca.

Com a mutação de troca, duas localizações num percurso são seleccionadas de forma aleatória e depois as suas posições são trocadas. For exemplo, se aplicarmos uma mutação de troca à lista seguinte:

a, b, c, d, e

Poderíamos obter vários resultados tais como:

a,c,b,d,e

e,b,c,d,a

Entre muitos outros. A lista é sempre a mesma, só muda a sua ordem, nunca serão adicionados ou removidos elementos à lista.

Um método de crossover que seria capaz de produzir um percurso válido é o crossover ordenado. Neste método de crossover seleccionamos um subconjunto de cidades do primeiro pai, copiamos esse subconjunto para o percurso filho. As cidades em falta são adicionadas ao percurso filho através do segundo pai na ordem em que são encontrados. O exemplo abaixo deve tornar esta ideia mais clara (para simplificação, consideramos cada letra uma cidade e consideramos apenas 7 cidades).

Criar algoritmo genético em Java - crossover

Utilizando o método de crossover acima o percurso filho resultante será sempre um percurso válido.

Gostou do artigo? Tem dúvidas ou sugestões? Então deixe um comentário abaixo!

Este post faz parte de uma série de três tutoriais, não perca as outras partes:

 

 

Deixar uma resposta