Kapittel 3. Metodisk tilnærming
3.1 Fra spørsmål til svar
Apesar de decorridos mais de 40 anos desde que foi concebida, a aplicabilidade dos AGs a problemas práticos se confirmou apenas em meados da década de 1980. Isso ocorreu em virtude, principalmente, do aumento da capacidade de processamento dos computadores, além do desenvolvimento de rotinas mais eficientes. Comparativamente com os métodos tradicionais empregados em otimização, Soares (2003) enumera as principais vantagens dos AGs como sendo:
• execução da busca a partir de um conjunto de pontos, e não apenas de um, sendo capazes de trabalhar bem em problemas com funções objetivo complexas;
• usam apenas os valores das funções objetivo e não requerem diferenciação e continuidade das mesmas;
• são facilmente adaptáveis a qualquer problema de otimização;
• podem trabalhar com um grande número de variáveis, varrendo o espaço dos objetivos de forma eficaz;
• apresentam possibilidade de se trabalhar com computação paralela; • adaptam-se bem a problemas contínuos e discretos.
A principal desvantagem relatada diz respeito ao tempo de processamento computacional, já que os mesmos, por trabalharem com um conjunto muito grande de pontos, exigem um tempo de processamento relativamente maior.
Os AGs são compostos basicamente por dois processos (VENDHUIZEN, 1999):
2. seleção dos candidatos mais aptos;
3. aprimoramento das soluções, geralmente via recombinações e mutações. Esses procedimentos são regidos de um modo geral pelo Algoritmo 3.1. Este pode ser descrito da seguinte forma.
A idéia básica dos AGS é a escolha da melhor solução em detrimento da “pior”. Fazendo analogia com os processo de seleção natural, as soluções candidatas são chamadas de indivíduos, sendo o conjunto dessas seleções chamado de
população. Primeiramente, uma população inicial é gerada a partir de um processo
aleatório. Essa população é o ponto inicial do processo evolutivo. A seguir procede-se um processo repetitivo que consiste em avaliar, selecionar, recombinar e “mutar” os indivíduos (solução), gerando novas populações de soluções. Dá-se o nome de geração a cada iteração desse processo. O número máximo de gerações é usualmente adotado como o critério de parada. Porém, existem outras condições como critério de parada tais como, estagnação da população e existência de um indivíduo com qualidades suficientemente satisfatórias, entre outros. O melhor indivíduo é aquele que tem a maior aptidão, seja da população final, ou de uma população dentro do processo iterativo, sendo este a solução que se procura.
Algoritmo 3.1 Algoritmo Genético
1. Geração de uma população inicial; 2. Avaliação dos indivíduos da população;
3. Seleção dos indivíduos que irão participar do processo de reprodução; 4. Recombinação dos indivíduos selecionados;
5. Mutação;
6. Repetem-se as etapas de 2 a 5 até satisfazer um critério de parada
Cada um dos processos dos AGs será detalhado a seguir.
3.2.3.1.1
Representação das Soluções
Os AGs trabalham com uma codificação específica para as variáveis de decisão, em que são aplicados os operadores de seleção, cruzamento e mutação. Dessa forma, cada variável do conjunto x1, x2, ..., xP tem que ser representada de
acordo com a codificação escolhida. Escolher a representação adequada é um passo importante para que a aplicação dos AGs a um determinado problema seja bem sucedida (GEN E CHENG, 1997).
Segundo Ticona (2003), as sistemáticas de codificação mais usadas são: a binária e a real. No entanto, representações mais complexas como árvores e matrizes também são utilizadas. As variáveis codificadas são agrupadas formando uma cadeia (string) que representa a solução, ou indivíduo.
Representação Binária
A representação pioneira e que mais tem sido empregada nos AGs é a binária, principalmente quando se trabalha com variáveis discretas. No caso de um problema com variáveis contínuas, os códigos binários também podem ser empregados, porém, é necessário um processo de decodificação. Além disso, quando a precisão requerida é alta, a cadeia binária tende a ficar muito grande o que desfavorece fortemente o seu uso (SOARES, 2003).
Na codificação binária, um conjunto ou intervalo de variáveis é convertido para um número binário. Por exemplo, o intervalo de 0 a 10 pode ser representado, com uma discretização de 1 da seguinte forma:
0000 = 0 0001 = 1 0010 = 2 0011 = 3 1001 = 9 1010 = 10 Representação Real
A representação real tem sido muito utilizada nos últimos anos, principalmente pela possibilidade de redução do tamanho da cadeia. Esse tipo de codificação proporciona também a introdução de novos operadores.
Na codificação real a variável pode assumir o seu próprio valor, não sendo necessário nenhum processo de conversão. Para problemas discretos, pode-se também empregar uma forma inteira que é semelhante à real.
3.2.3.1.2
Seleção
No processo de seleção, que pode ser estocástico ou determinístico, os indivíduos de menor adaptabilidade tendem a ser removidos enquanto que os indivíduos mais aptos — as soluções com melhores valores da função objetivo num problema de otimização simples — se reproduzem passando os valores do seu código, ou variáveis de decisão, para as iterações, ou gerações, posteriores. A qualidade do indivíduo, geralmente representada por um escalar, é denominada de aptidão. O conceito da seleção é muito amplo e permite que diversos esquemas possam ser empregados. As principais classificações dos processos de seleção são apresentadas a seguir (BRINCKLE, 1996):
• quanto ao tamanho da população que será substituída:
Geracional e Permanente (Steady-State): no primeiro tipo o processo de
seleção incide sobre toda a população, enquanto que no segundo, apenas um pequeno número de indivíduos são substituídos, através da seleção-recombinação.
• quanto à permanência de indivíduos:
Elitista e Não Elitista: em um processo geracional comum, não existe
garantias de que os indivíduos “mais aptos” irão permanecer na população da geração seguinte, isto implica na possibilidade de perda de bons “espécimes”. Este tipo de abordagem é denominado não-elitista. Quando se cria um mecanismo que assegure a permanência das melhores soluções na iteração seguinte, diz-se que o processo é
elitista. Esta classificação é aplicada apenas aos métodos geracionais e foi proposto
originalmente por De Jong (1975) (LACERDA E CARVALHO, 1999).
Existem dois métodos principais empregados para se fazer seleção de um indivíduo, a saber: seleção proporcional ou roda de roleta (roullette) e torneio.
Nos métodos de seleção proporcional propostos por Holland (1975) a probabilidade de um indivíduo ser escolhido será função da sua aptidão, descrita pela seguinte expressão:
∑
= = P k k i i p 1 χ χ (3.5)em que pi é a probabilidade de uma solução ser escolhida, χi é o valor da função de aptidão e P é o tamanho da população.
Na seleção por torneio (tournament), um grupo de t indivíduos é escolhido aleatoriamente a partir da população com ou sem reposição. As soluções escolhidas irão participar de um "torneio", em que o "vencedor" é determinado a partir do valor de sua aptidão. A "solução vencedora" é inserida na próxima população e o processo é repetido P vezes até que uma nova população seja formada. Os torneios são realizados frequentemente entre dois indivíduos (t=2), porém torneios com mais soluções podem ocorrer. Recomenda-se, entretanto, que o tamanho do grupo que participa dos torneios não seja grande (t<5) de modo a evitar a perda de diversidade da população (BRINCKLE, 1996).
3.2.3.1.3
Aprimoramento das soluções
A variação das soluções é introduzida a cada geração através da
recombinação e mutação. Tais operadores criam novas populações, ditas filhas, que
contêm indivíduos que ocupam diferentes posições no espaço de busca. Por esse motivo, tais procedimentos são denominados de exploratórios. Esses processos ajudam a gerar novas soluções a partir de variações das soluções existentes. Na maioria dos métodos, o operador de cruzamento cria um ou dois novos indivíduos (filhos) a partir de um par de soluções (pais) já existente. Para simular a natureza estocástica da evolução, uma probabilidade de cruzamento é associada a esse operador.
O operador de mutação é responsável por modificar o indivíduo através de pequenas variações no seu código genético de acordo com uma taxa de mutação. Detalhes de alguns tipos de operadores de mutação e de recombinação são apresentados no item 4.3.2 do próximo capítulo.