Motforestillinger mot andre tiltak for vektreduksjon

Desde a década de 1960 tem havido um interesse crescente em imitar os seres vivos na busca pelo desenvolvimento de algoritmos poderosos para aplicação em problemas de otimização complexos, sendo que tais técnicas fazem parte do que pode ser denominado como “computação evolutiva” (GEN; CHENG, 2000). Os AGs foram propostos originalmente por John Holland (1975). Uma das vantagens de sua utilização é que, na busca pela solução de um

26

problema de otimização, eles podem encontrar o mínimo global com alta probabilidade (RAO, 2009).

A utilização de técnicas de inteligência artificial na área de controle é bastante difundida. Algoritmos genéticos (AGs) são algoritmos matemáticos inspirados nos mecanismos de evolução natural e recombinação genética (GOLDBERG, 1989). Eles fornecem um mecanismo de busca adaptativa baseada na teoria da evolução, a qual define o ciclo de reprodução, mutação e sobrevivência dos mais aptos (seleção natural).

O AG busca a solução de um problema através da submissão de uma população de indivíduos que são candidatos a soluções desse problema a um processo de evolução (seleção, reprodução e mutação) por vários ciclos (ou gerações). Esses indivíduos são representados por cromossomos, cada um associado a uma aptidão (desempenho de cada indivíduo na solução do problema), o que irá definir o mecanismo de seleção.

A sequência das operações básicas de um AG é mostrada no fluxograma da Figura 2.11.

A etapa inicial do desenvolvimento de um AG é a determinação da estrutura de cada indivíduo da população, ou seja, a estrutura das possíveis soluções. Para isso, deve-se conhecer o formato da solução do problema. As representações dos indivíduos podem ser de diversos tipos como, por exemplo, um vetor de números reais. Dessa forma, o espaço de busca do AG é o conjunto de todas as possíveis configurações desse indivíduo.

A população inicial contém as primeiras propostas de solução do problema geradas de forma aleatória, e ela pode ser gerada de três formas: determinística, aleatória ou mista (RODRIGUES, 2011).

O cálculo da aptidão dos indivíduos é realizado através de uma função de avaliação. A função de avaliação pode ser, por exemplo, uma função de máximo ou de mínimo. Assim, a aptidão está relacionada com o resultado obtido quando o indivíduo é testado nessa função. Essa função indicará o quanto cada indivíduo da população está próximo da melhor solução para o problema, sendo que esse procedimento é realizado para todos os indivíduos.

O processo de seleção consiste em selecionar um determinado número de indivíduos para a próxima geração e, posteriormente, selecionar os pares para o crossover de acordo com um método que privilegie os de melhor aptidão. Dentre os vários métodos de seleção existentes, a seguir são descritos dois:

• Truncamento: todos os indivíduos são ordenados de acordo com a aptidão, do de maior para o de menor, ou seja, o primeiro deve ser o de maior aptidão. Em seguida, selecionam-se os N primeiros indivíduos, sendo que N é o número de indivíduos que se deseja selecionar. No caso da seleção dos indivíduos para a próxima geração, esse método também pode definido como “reinserção ordenada”;

• Ranking: como no método anterior, o primeiro passo é ordenar todos os indivíduos de acordo com a aptidão. Depois disso, para cada indivíduo, são dadas “fichas” numeradas, sendo que o número de “fichas” que cada indivíduo recebe é diretamente proporcional à sua aptidão. Assim quanto maior a aptidão, maior é o número de “fichas” que o indivíduo recebe. Depois disso, são feitos N sorteios entre essas “fichas”, e os detentores das “fichas” sorteadas são selecionados. Assim, um indivíduo pode ser selecionado mais de uma vez, pois além do indivíduo poder ter mais que uma ficha, a cada sorteio a “ficha” retorna, tendo a chance de ser sorteada novamente. Dessa forma, probabilidade de um indivíduo ser sorteado depende unicamente da sua aptidão.

28

A diferença entre os métodos de seleção é o que é denominado pressão seletiva. Quanto maior a chance de os indivíduos com maior aptidão serem sorteados, maior é a pressão seletiva. Quanto maior a pressão seletiva, menor será o número de gerações necessárias para se chegar à solução, porém maior será o risco de convergência prematura, ou seja, maior é o risco de o AG convergir para um mínimo local.

Durante a seleção para o crossover, os indivíduos são agrupados em pares, sendo que na maioria dos casos, cada par de pais dá origem a um par de filhos. O crossover (recombinação) consiste na combinação dos genes dos indivíduos selecionados gerando novos indivíduos. Os métodos de crossover possibilitam a recombinação desses pais a fim de transmitir suas características para a próxima geração. O crossover depende da forma do cromossomo (indivíduo).

Para um indivíduo na forma de vetor de números reais, pode ser utilizado, por exemplo, a recombinação intermediária. A Figura 2.12 exemplifica esse tipo de crossover, onde as máscaras são vetores de números reais, indicados por α1 e α2, sorteados aleatoriamente dentro de um intervalo pré-determinado. A diversidade dos filhos é controlada pelo intervalo de sorteio dos pesos α.

Figura 2.12 – Exemplo de crossover a partir do método de recombinação intermediária

A mutação tem o objetivo de introduzir e manter a diversidade da população, alterando aleatoriamente um ou mais genes de uma parcela dos filhos gerados no crossover, e o método utilizado para realizá-la também depende do tipo de cromossomo. Para vetores reais, por exemplo, pode-se sortear uma posição desse vetor e multiplicar o valor correspondente por um número aleatório dentro de um intervalo pré-definido.

Apesar de aleatórios, AGs são mecanismos de busca direcionados, pois exploram informações históricas para encontrar novos pontos de busca onde são esperados melhores desempenhos (RODRIGUES, 2011).

As principais vantagens dos AGs são: técnica de busca global, viabiliza a otimização de problemas mal estruturados e dispensa a formulação matemática precisa do problema. Esta técnica é robusta e aplicável a uma grande diversidade de problemas e, para muitos deles, é capaz de encontrar soluções sub-ótimas, inclusive ótimas, em um tempo razoável.

Em contrapartida, as principais desvantagens do AGs são: dificuldade para achar o ótimo global exato, requerem um grande número de avaliações das funções de aptidão e suas restrições e grandes possibilidades de configurações podendo complicar a resolução.

Os parâmetros de desempenho de um AG são as variáveis que devem ser definidas para a sua construção, os quais são: tipo de cromossomo, quantidade de indivíduos da população total, quantidade de indivíduos selecionados a cada geração, métodos de seleção para próxima geração e para o crossover, tipos de crossover e de mutação, número de filhos por geração e quantidade de filhos que sofrerão mutação.

Esses parâmetros devem ser analisados através de testes de forma a encontrar a melhor configuração para o AG de acordo com o problema a ser resolvido, evitando convergência prematura, que resulta no risco de não encontrar respostas satisfatórias, ou, por outro lado, esforço computacional desnecessário. Rezende (2005) cita a influência desses parâmetros no comportamento do AG.

Maiores detalhes a respeito das possíveis estruturas para os AGs, suas aplicações, métodos de seleção, crossover e mutação e ajuste dos parâmetros de desempenho podem ser encontrados nos trabalhos de Rezende (2005), Gen e Cheng (2000), Goldberg (1989) e Rao (2009).