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