Demonstração da Execução de um Algoritmo Genético

No post Introdução a Algoritmos Genéticos falei um pouco sobre os AG’s e falei sobre a estrutura básica de um AG.
Neste post irei demonstrar passo-a-passo a execução de um AG através de figuras.
Neste site tem alguns applets demonstrando a execução de um AG. Foi através deste site que consegui as imagens abaixo e pedi a autorização do dono do site para que pudesse usá-las neste post. Portanto se você deseja copiar as imagens para utilizar, certifique-se de ler os termos de uso.

Algoritmo

Um AG funciona da seguinte maneira:
1. Inicialmente é gerado uma população de indivíduos chamada de geração.
2. Todos os indivíduos de cada geração são avaliados pela função objetivo e recebem uma nota de acordo com a sua adequação ao ambiente. Quanto melhor for a adequação do indivíduo, mais chances ele tem de ser selecionado.
3. Se for encontrada uma solução, ou seja, nesta geração possui uma solução ótima, então o problema está resolvido.
4. Alguns indivíduos são selecionados, de acordo com a nota de adequação adquirida no passo 2, para fazer o cruzamento e assim gerar a próxima geração.
5. Após o cruzamento é aplicada a mutação.
6. Os passos 2 a 5 são repetidos até que a solução ótima seja encontrada.
Algumas variações podem ocorrer, mas basicamente um AG funciona desta maneira.

Demonstração

Já vimos que o entendimento de um AG é muito simples. O objetivo deste post é demonstrar, através de imagens, um passo-a-passo da execução do algoritmo.

Demonstração AG 01

Na figura acima podemos ver a população atual (present population) e a população que vai ser gerada (new population). O gráfico representa o espaço de soluções, onde as linhas verticais indicam a população atual. A linha vermelha representa a melhor solução da população atual, enquanto as linhas verdes representam as outras soluções candidatas.
Assumindo que a representação do problema foi feita em forma de vetor de valores binários, então podemos dizer que os pontos em azul e vermelho representam, respectivamente, os bits 0 e 1 (ou vice-versa) de cada posição do vetor.
Podemos perceber que já temos uma população gerada e que para todos os indivíduos desta população já foi atribuído a nota pela função de aptidão (pois já temos conhecimento da melhor solução da população atual).

Demonstração AG 02

O elitismo é demonstrado neste passo, ou seja, os melhores cromossomos (indivíduos) são simplesmentes copiados para a nova população.

Demonstração AG 03

Neste passo, 2 cromossomos são escolhidos para que seja feito o cruzamento. Lembre-se que, os melhores cromossomos tem mais chances de serem escolhidos para o cruzamento (crossover). Isto não significa que eles sempre serão escolhidos.
Note que na população atual, os dois cromossomos que foram selecionados estão marcados com um ponto preto em cima e embaixo da representação.
O “Crossover point” (ou ponto de cruzamento) é o ponto que foi escolhido para que seja feita a troca de genes entre os pais. Ou seja, um filho vai ser gerado pela combinação dos genes que estão acima do ponto de cruzamento de um genitor com os genes que estão abaixo do ponto de cruzamento do outro genitor. E a geração do outro filho segue da mesma forma mas invertendo a ordem.

Demonstração AG 04

Na figura acima temos os filhos que foram gerados e podemos ver claramente como foi realizado o cruzamento.

Demonstração AG 05

Após o cruzamento é feito a mutação de alguns genes para que ocorra a diversificação da espécie e que algumas características não sejam perdidas.
Os genes que sofreram mutação estão marcados com um ponto preto ao lado. Neste caso, apenas o primeiro filho sofreu mutação.

Demonstração AG 06

Os filhos que foram gerados são adicionados à nova população.

Demonstração AG 07

Esses passos são executados até que uma nova geração inteira seja formada.

Demonstração AG 08

A nova geração que foi criada passa a ser a população atual e o algoritmo continua sua execução até que uma solução ótima seja encontrada.

Conclusão

Como podemos ver não é complicado de entender o funcionamento de um AG. Vale relembrar que existem alguns parâmetros que podem ser configurados, por exemplo, taxa de mutação, taxa de cruzamento, dentre outros, e que esta configuração influencia muito no desempenho do algoritmo.

Recomendo vocês a testarem vocês mesmo a execução de um AG neste applet.

Introdução a Algoritmos Genéticos

Introdução

Algoritmos Genéticos (AG) é uma sub-área da Computação Evolutiva, área de pesquisa de Inteligência Artifical que trata de sistemas para a resolução de problemas que utilizam modelos computacionais baseados na teoria da evolução natural.[¹]

Foi fundamentada pelo americano John Henry Holland, que publicou o livro “Adaptation in Natural and Articial Systems”.

Definição

AGs são programas evolutivos baseados na teoria de seleção natural e na hereditariedade. Ou seja, partem do pressuposto que, em uma dada população, indivíduos com boas características genéticas têm maiores chances de sobrevivência e de produzirem indivíduos cada vez mais aptos. Como resultado, os indivíduos menos aptos tenderão a desaparecer.[¹]

Conceitos Básicos

Uma geração é uma população de indivíduos. Para cada indivíduo (solução candidata) dá-se o nome de cromossomo. O conjunto de todas as configurações que o cromossomo pode assumir forma o seu espaço de busca. Um cromossomo é formado por um conjunto de genes (blocos de DNA). O valor atribuído a cada gene é chamado de alelo. Cada gene possui uma posição e a essa posição dá-se o nome de locus. O genótipo de um cromossomo é a representação de um conjunto particular de genes, enquanto o fenótipo é a representação do genótipo no mundo real. Por exemplo, o genótipo 010010 pode representar a cor do cabelo marrom no mundo real.

A cada geração os indivíduos são avaliados quanto à sua adequação ao ambiente. Esta avaliação é feita pela função objetivo (também chamada de função de avaliação, função de custo ou função de aptidão). Os indivíduos (pais) são selecionados à partir da avaliação para que sejam realizados os cruzamentos e as mutações e assim gerar novos indivíduos (filhos). Cruzamento (crossover ou recombinação) é a recombinação de características dos pais para permitir que as próximas gerações de filhos herdem suas características. Mutação é a alteração aleatoriamente de alguns genes dos filhos, permitindo assim a introdução de novos elementos na população.

Na seleção os cromossomos mais aptos têm mais probabilidade de serem escolhidos para o cruzamento, mas isto não significa necessariamente que eles serão escolhidos. Então para que não se perca os melhores cromossomos de uma geração é utilizada uma técnica chamada de elitismo, que significa que pelo menos 1 cromossomo (o mais apto) será copiado para a nova população para que os melhores descendentes permaneçam durante por várias gerações.

Características

Os AGs diferem dos métodos tradicionais de busca e otimização, principalmente em quatro aspectos [¹]:

1. trabalham com uma  codificação do conjunto de parâmetros e não com os próprios parâmetros;
2. trabalham com uma população e não com um único ponto;
3. utilizam informações de custo ou recompensa e não derivadas ou outro conhecimento auxiliar;
4. utilizam regras de transição probabilísticas e não determinísticas.

Aplicação

Encontrar soluções ótimas em um espaço de busca com um número, possivelmente, indeterminado de soluções possíveis. [³] Um exemplo de aplicação onde pode ser utilizado um AG para realizar a busca da solução ótima é o Problema do Caixeiro Viajante, ou então, localizar o pico mais alto de uma montanha em um mapa topográfico [³].

Estrutura básica

A estrutura básica de um AG é mostrada na figura abaixo:

Estrutura Básica de um AG ²

1. Inicialmente é gerado uma população de indivíduos chamada de geração.
2. Todos os indivíduos de cada geração são avaliados pela função objetivo e recebem uma nota de acordo com a sua adequação ao ambiente. Quanto melhor for a adequação do indivíduo, mais chances ele tem de ser selecionado.
3. Se for encontrada uma solução, ou seja, nesta geração possui uma solução ótima, então o problema está resolvido.
4. Alguns indivíduos são selecionados, de acordo com a nota de adequação adquirida no passo 2, para fazer o cruzamento e assim gerar a próxima geração.
5. Após o cruzamento é aplicada a mutação.
6. Os passos 2 a 5 são repetidos até que a solução ótima seja encontrada.

Pontos Chaves

Existem alguns pontos chaves de um AG que devem ser destacados (nos próximos posts falarei sobre cada um destes pontos chaves):

Representação
Identificar qual a melhor maneira de representar o problema para que o AG possa trabalhar adequadamente sobre ele. A maneira mais utilizada (porém nem sempre a mais indicada) é em foma de vetor de valores binários, exemplo, 110010101100.

Seleção
É o processo de selecionar os indivíduos mais aptos para realizar o cruzamento e a mutação para que sejam gerados indivíduos ainda mais aptos. Exemplos de métodos de seleção são: Método da Roleta, Método do Torneio, Método da Amostragem Universal Estocástica.

Operadores
São utilizados para assegurar que a nova geração formada seja totalmente nova apesar de manter, de alguma forma, as características dos pais (cruzamento); e também para diversificar a população (mutação).
Alguns exemplos de cruzamento são: Cruzamento de um-ponto, Cruzamento Multipontos e Cruzamento Uniforme.

Parâmetros
Existem alguns parâmetros que podem ser configurados em um AG, como exemplo, tamanho da população, taxa de cruzamento, taxa de mutação, dentre outros. É importante ressaltar que o desempenho do AG é altamente influenciado pela definição dos parâmetros utilizados.

Referências Bibliográficas

[1] REZENDE, S. O., Sistemas Inteligentes – Fundamentos e Aplicações, 2005, Manole
[2] Algoritmos Genéticos: Fundamentos e Aplicações
[3] Algoritmos Genéticos – Visão Geral
[4] Introdução aos Algoritmos Genéticos
[5] Algoritmo genético

Boas Vindas

Neste blog irei falar sobre Tecnologia da Informação, especialmente sobre os meus estudos e pesquisas na área de Inteligência Artificial neste meu caminho para o Mestrado (e quem sabe um dia, Doutorado ).

Outra área que também gosto muito é a área de Finanças e pretendo escrever alguns posts sobre esse assunto. Alguns assuntos off-topic irão surgir mas eles serão devidamente adicionados à categoria de off-topic.

Este é o meu primeiro blog e não sou muito acostumado a escrever (como vocês podem perceber hehe). Mas irei melhorar a escrita com o decorrer do tempo.

É isso aí, sintam-se bem vindos e voltem sempre.