AVALIAÇÃO E INTERPRETAÇÃO DO OPERADOR mAG NO ALGORITMO GENÉTICO REAL-POLARIZADO

Ricardo H. C. Takahashi Departamento de Matemática

Universidade Federal de Minas Gerais Av. Antônio Carlos 6627 – Campus da Pampulha

30123-970 - Belo Horizonte – MG e-mail: taka@mat.ufmg.br

Flávio V. C. Martins

Departamento de Matemática Universidade Federal de Minas Gerais

Av. Antônio Carlos 6627 – Campus da Pampulha 30123-970 - Belo Horizonte – MG

Resumo Este trabalho aborda o estudo do operador mAG (Micro Algoritmo Genético), que foi recentemente proposto na literatura como operador de “busca local” na otimização via Algoritmos Genéticos. É proposta aqui uma nova interpretação do funcionamento desse operador, mostrando o papel que este pode exercer em uma “busca global”. Tal interpretação permite o estabelecimento de diretrizes para a sintonia dos parâmetros desse operador, de forma a constituir algoritmos genéticos mais eficientes, que atingem os pontos de ótimo com maior probabilidade e com menor número de avaliações da função objetivo. Palavras-Chave: Algoritmos genéticos, otimização não-linear.

Abstract This work studies the mGA operator (Micro Genetic Algorithm), that has been recently proposed in literature as a “local search” operator for optimization with Genetic Algorithm. A new interpretation for this operator behavior is proposed here, showing the role that this operator can have in a “global search”. Such interpretation allows the definition of some directives for this operator parameter tuning, leading to more efficient genetic algorithms that reach the optima with greater probability, spending less objective function evaluations. Keywords: Genetic algorithms, non-linear optimization. Área: PM – Programação Matemática

Introdução

Os Algoritmos Genéticos (AG) têm adquirido crescente importância enquanto mecanismo de otimização nos últimos anos, em virtude de serem uma ferramenta genérica de otimização que busca com razoável eficiência os mínimos globais de funções multimodais, exigindo ainda, em grande parte dos problemas em que se aplica, um esforço muito pequeno de adaptação do algoritmo ao problema (Man et al, 1996; Johnson & Ramat-Semii, 1997). De fato, mesmo em problemas para os quais haveria algoritmos até mais eficientes, muitas vezes se adota um AG como mecanismo de otimização, devido à reduzida necessidade de agregação de conhecimento adicional (não é necessário, por exemplo, o

1437

conhecimento prévio de soluções iniciais, ou de regiões de confiança, ou o cálculo de gradientes ou subgradientes, etc) para a formulação do problema.

Algoritmos Genéticos trabalham com um conjunto de soluções-candidatas que são consideradas simultaneamente; tal conjunto é denominado população, sendo cada solução-candidata denominada indivíduo. Um AG se define como um algoritmo que emprega alguma versão de três operações básicas (os operadores genéticos básicos), defindas por: - Cruzamento: operação que combina a informação de dois indivíduos, gerando novos indivíduos; - Mutação: operação que “perturba” um indivíduo, gerando um novo indivíduo com alguma

semelhança com o indivíduo que o originou; - Seleção: operação que gera uma nova população a partir da população corrente, permitindo a

transmissão à nova população dos indivíduos da população atual, com maior probabilidade para os indivíduos com melhor função-objetivo, e com menor probabilidade para os indivíduos com pior função-objetivo.

Esses operadores são aplicados sequencialmente, repetindo-se a seqüência a cada iteração, até a convergência para um ponto considerado ótimo segundo algum critério de parada. Algoritmos constituídos segundo esse esquema são genericamente denominados Algoritmos Genéticos. Algumas referências que abordam o estudo desses operadores são (Belmont-Moreno, 2001; Choi & Oh, 2000; Hasancebi & Erbatur, 2000; Takahashi et al, 2003; Vasconcelos et al, 2001). A maioria dos AG’s atualmente utilizados emprega, além desses operadores básicos, também outros operadores genéticos adicionais, que aumentam a eficiência do algoritmo. Alguns desses operadores possuem aplicabilidade genérica, mantendo o grau de generalidade do AG básico, tais como: - Elitismo: causa a seleção determinística de parte da população corrente, usualmente os melhores

indivíduos, para integrarem a nova população; - Nicho: evita a concentração excessiva de indivíduos explorando a mesma região de um espaço de

busca. Esses operadores tendem a ser incorporados à maioria dos AG’s, uma vez que não restringem a aplicabilidade destes, ao mesmo tempo em que a experiência de seu uso ao longo dos anos vem mostrando que eles tendem a melhorar as propriedades de convergência do algoritmo. O estudo de operadores não-básicos é apresentado em diversas referências, por exemplo (Fan et al, 2000; Potts et al, 1994; Sareni & Krahenbuhl, 1998; Vasconcelos et al, 2001) Deve-se fazer menção, nesse contexto, ao operador de cruzamento real-polarizado, proposto na referência (Takahashi et al, 2003), que se encontra ainda pouco disseminado, mas que parece pertencer a essa classe de operadores de natureza genérica que consistentemente melhoram as propriedades dos AG’s: esse operador de cruzamento produz indivíduos-filhos a partir de indivíduos-pais de maneira a levar em consideração a diferença existente entre os valores da função objetivo dos pais. Os indivíduos-filhos tendem a estar mais próximos do indivíduo-pai com melhor valor de função objetivo. Outros operadores, com algum grau de particularização de sua aplicabilidade, também têm sido propostos. Nessa categoria podem ser citados operadores desenvolvidos especialmente para problemas de otimização de alocação de tarefas em sistemas de produção (Pongchareen et al, 2001), ou a sistemas de otimização inteira mista (Lin et al, 2001), por exemplo. Os algoritmos genéticos usualmente apresentam um desempenho pobre, em comparação com outros métodos de otimização, quando o processo de otimização se encontra no estágio em que já se possuem boas aproximações do ponto de ótimo que está sendo procurado, sendo necessário o refinamento dessas aproximações, até a determinação de uma solução com erro suficientemente pequeno. Esse fato vem motivando nos últimos anos o estudo de uma classe de operadores genéticos: os operadores de busca local, que fazem uma busca nas proximidades do melhor ponto corrente, utilizando estratégias que aumentam a eficiência dessa busca em comparação com o uso dos operadores genéticos básicos. Têm surgido na literatura diversas alternativas para a implementação desses operadores, desde aquelas mais rudimentares, que implementam buscas unidimensionais baseadas em gradiente (e que, portanto, possuem a desvantagem de requererem cálculos de gradiente), até alternativas que executam essa função de maneiras mais sutis. Dentre essas últimas, deve-se citar o operador micro-genético (mAG), que é o objeto de estudo no presente trabalho. Esse operador foi proposto na referência (Kazarlis et al, 2001) com o objetivo de implementar a função de busca local, funcionando da seguinte forma:

1438

- O melhor ponto da população corrente é determinado ao final de uma iteração do AG; - Um pequeno conjunto de pontos é gerado nas proximidades desse melhor ponto, tomando este

como “centro” do conjunto; - Esse conjunto de pontos é utilizado como “população inicial” para a execução de uma versão

reduzida do mesmo algoritmo genético (que é o mesmo algoritmo, executado com essa população menor). Esse algoritmo “reduzido” converge muito mais rapidamente para o ponto de ótimo local próximo do melhor ponto corrente do que convergiria o algoritmo genético com toda a população corrente.

Na referência em que o operador mAG foi proposto, é apresentado um estudo detalhado de suas propriedades enquanto operador de busca local, que dão suporte à conclusão de que seu uso é vantajoso. O presente trabalho estuda o operador mAG segundo outra ótica, não apontada no estudo que o propôs. Os dados aqui apresentados sugerem que o mAG executa também a operação aqui denominada busca de tendência global. Tal operação é aqui definida como:

Busca de Tendência Global Consiste na utilização das amostras da função objetivo na busca de regularidades de comportamento observáveis não-localmente, capazes de fornecer indícios a respeito da localização do ponto de ótimo.

O operador mAG aqui estudado é executado sobre o algoritmo genético real-polarizado (AGRP), apresentado na referência (Takahashi et al, 2003), que adota o operador de cruzamento real-polarizado, o qual, por si só, já executa a função de busca de tendência global. Dessa forma, a estrutura específica do operador mAG assim obtida é aqui denominada mAGRP. Os estudos aqui relatados dão suporte à conclusão de que o mAGRP é capaz de realizar buscas de tendência global sob certas circunstâncias. Uma interpretação geométrica para esse fato é proposta. A partir dessa interpretação, é proposto um procedimento de ajuste dos parâmetros do mAGRP que torna provável a execução de buscas de tendência global. Os dados obtidos sugerem que é significativo o ganho de desempenho com a inclusão do mAGRP ajustado dessa forma.

Algoritmo Genético Real-Polarizado

O algoritmo genético a ser empregado como base para o teste do operador mAG é o chamado algoritmo genético real-polarizado (AGRP), apresentado na referência (Takahashi et al, 2003). Esse algoritmo, embora tenha sido publicado apenas recentemente, foi concebido há alguns anos (em 1998), já tendo sido amplamente testado em problemas diversos (Takahashi et al, 2002; Ramos et al, 2003; Scorretti et al, 2004). Trata-se de um algoritmo que domina praticamente todos aqueles com os quais foi comparado, quando observado simultaneamente sob os critérios de (i) mínimo número de avaliações da função objetivo, em média, para determinação do ótimo; e (ii) mínimo percentual de insucessos na determinação do ótimo. A referência (Takahashi et al, 2003) apresenta os dados da comparação do AGRP com alguns milhares de versões de outros algoritmos genéticos, que dão suporte à sua caracterização como um dos melhores AG’s disponíveis.

A versão do AGRP aqui utilizada é a seguir descrita: - Os indivíduos são representados como vetores num espaço Rn. - A população inicial é gerada segundo uma distribuição gaussiana com média igual a um ponto do

espaço definido pelo usuário, e variância definida pelo usuário (possivelmente diferente para cada coordenada).

- O operador de mutação corresponde à soma de uma perturbação gaussiana a um indivíduo, com média zero e variância igual ao mínimo valor, entre: dez por cento da variância da população original (para cada coordenada) e o tamanho da população corrente. A cada iteração, esse operador é aplicado com probabilidade três por cento;

- O operador de cruzamento real-polarizado toma dois indivíduos, pareados ao acaso, e gera dois novos indivíduos. Considerando o segmento de reta que une esses indivíduos, estende-se esse

1439

segmento dos dois lados, de forma a aumentar seu comprimento em 20%. Os dois indivíduos-filhos são pontos sorteados sobre esse segmento estendido. Um deles é obtido com probabilidade uniforme sobre esse segmento. O outro é obtido segundo uma distribuição de probabilidades quadrática, que aumenta a probabilidade da extração do novo indivíduo nas proximidades do indivíduo-pai de melhor função-objetivo.

- O operador de seleção se baseia na tradicional roleta, com “fitness function” igual à proposta por Goldberg (1989).

- Aplica-se o elitismo básico, com a escolha determinística apenas do melhor indivíduo de cada geração.

- O critério de parada utilizado nos testes aqui descritos é o da proximidade em relação ao ótimo previamente conhecido da função de teste.

Operador microgenético real-polarizado

O operador mAG aqui empregado é basicamente o próprio algoritmo genético real-polarizado (sendo por isso denominado mAGRP), com as seguintes modificações: - A população do mAGRP corresponde a uma fração da população do AGRP. Um dos fatores

estudados aqui é o efeito do tamanho dessa população. - O centro do mAGRP é o melhor indivíduo da população corrente. - A população do mAGRP é gerada segundo uma distribuição uniforme (e não mais gaussiana,

como era feito no AGRP), com raio igual a uma fração do raio do AGRP. O efeito do tamanho desse raio é também investigado neste trabalho.

- O operador mAGRP é acionado a cada iteração, sendo que se sua execução resulta na obtenção de um ponto melhor que o melhor ponto corrente, este é substituído pelo novo ponto obtido.

Todas as demais características do AGRP são mantidas no operador mAGRP.

Resultados

Todos os testes relatados nesta seção foram realizados com uma população de 200 indivíduos para o AGRP e um raio de dispersão de tamanho 10. O critério de convergência adotado foi de distância menor que 10-3 em relação ao ponto de ótimo conhecido da função de teste. A população teve como centro para sua geração um ponto sorteado aleatoriamente dentro de uma caixa de aresta com tamanho de 40. Todos os testes se referem às médias obtidas em 100 execuções de cada versão do algoritmo testado.

Primeiramente serão apresentados resultados executados com a função Rastrigin em 2 e em 4 variáveis, e a seguir com uma função contendo nove bacias de atração ordenadas segundo certo padrão. Função Rastrigin

f(x) = ∑ x(i)2 – 10 cos(2π x(i))

Os testes em 4 variáveis fazendo n = 4 na equação 1 (função Rastrigin), foram executados com o tamanho da população do mAGRP igual a dez por cento do tamanho da população do AGRP, sendo obtidos os seguintes resultados: - Executando somente o AGRP sem o operador mAGRP, nenhuma solução convergiu em 100

iterações. - Executando o AGRP com o operador mAGRP e variando raio de dispersão da população do

mAGRP foram obtidos os dados representados na tabela abaixo:

i = 1

n (1)

1440

R mAG 2 4 6 8 10 12

% Conv 14 10 6 7 16 12

Nº Aval 16000 12560 13300 13829 17400 13717

Os testes em 2 variáveis fazendo n = 2 na equação 1, foram executados também com a população do mAGRP sendo dez por cento da população do AGRP, sendo obtidos os resultados: - Executando somente o AG:

AGRP

% Conv 45

Nº Aval 11196

- Executando o AGRP com o operador mAGRP (este com diversos raios diferentes sendo testados), são obtidos os seguintes gráficos juntamente com suas tabelas de dados:

0 5 10 15 20 25 301500

2000

2500

3000

3500

4000

4500

5000

5500

6000

6500

Tamanho do Raio usado no mAG

Núm

ero

de A

valia

ções

Figura 1: Número de avaliações necessário, em média, para convergência do AGRP com operador mAGRP, em função do raio adotado no mAGRP.

1441

Executando o AG com Pop 200 e R 10 e Após o mAG com Pop 0.1 R mAG 0.01 0.51 0.61 0.71 0.81 0.91 1.01 1.51 2 % Conv 77 75 81 96 100 100 100 100 100 Nº Aval 4431 4472 11196 5390 6489 4802 2332 2052 1914

Executando o AG com Pop 200 e R 10 e Após o mAG com Pop 0.1 R mAG 4 6 8 10 15 18 21 24 30 % Conv 100 100 100 100 100 100 100 100 100 Nº Aval 1910 2040 2054 2346 2364 2436 2262 2406 2234

Nota-se, de maneira imediata, nos gráficos e tabelas anteriores, o expressivo ganho tanto no que se refere ao número médio de avaliações necessário para se atingir o ótimo quanto no que diz respeito ao percentual de execuções do algoritmo com sucesso na determinação do ótimo.

Uma observação mais atenta ainda revela um dado interessante: Para raios muito pequenos, o efeito do operador mAGRP sobre a convergência não é muito importante (embora seja positivo). A partir do raio 0,81, entretanto, o operador mAGRP passa a causar a convergência do AGRP para o ponto de ótimo em 100% das execuções. Esse efeito sobre a convergência permanece mesmo para raios “grandes”, de tamanho semelhante ao tamanho da própria população inicial. Dessa forma, pode-se concluir que o operador mAGRP não possui apenas um papel enquanto operador de “busca local”; pelo contrário, seu efeito mais importante sobre o comportamento geral do algoritmo genético parece ocorrer precisamente quando ele é ajustado para executar buscas de “longa distância”.

Observando agora o comportamento do número de avaliações em função do raio, nota-se que o número de avaliações atinge valores expressivamente melhores no mAGRP, quando comparado ao

0 5 10 15 20 25 3070

75

80

85

90

95

100

Tamanho do Raio usado no mAG

% d

e C

onve

rgên

cia

Figura 2: Percentual de execuções em que ocorre convergência doAGRP com operador mAGRP, em função do raio adotado nomAGRP

1442

AGRP puro, para raios muito pequenos. Isso se deve, aparentemente, ao efeito de “busca local”, para o qual o mAG foi originalmente projetado: uma vez nas proximidades do ponto de ótimo, este operador acelera efetivamente a determinação do ponto de mínimo. Crescendo o raio, esse efeito de melhoria no número de avaliações necessário para determinação do ótimo praticamente se anula: para o raio 0,61, o número de avaliações necessário para a convergência se torna praticamente igual ao do AGRP puro. Para esse raio, o efeito da “busca local” já não mais ocorre. À medida em que se aumenta mais o raio, entretanto, o número de avaliações para determinação do ótimo volta a cair, sendo que um valor de menos da metade do número que era necessário para o raio de 0,01 é obtido para raios entre 1,51 e 8,0. Para esses raios, observe-se, a convergência para o ótimo ocorre em 100% dos casos. Para raios ainda maiores, o número de avaliações necessário volta a crescer levemente, ficando sempre abaixo que aquele que era necessário no caso do raio muito pequeno.

Tal comportamento deve ser interpretado da seguinte maneira: para otimizar a função que está sendo utilizada para teste, o AG necessita realizar duas operações em sequência:

(i) A determinação da “bacia de atração” na qual se localiza o ponto de mínimo da função; e (ii) A determinação do “ponto de mínimo” localizado nessa bacia.

Como a função possui um grande número de mínimos locais na região de teste (da ordem de 1600 mínimos), uma grande parcela do esforço computacional é gasta na etapa (i). O esforço realizado na etapa (ii) certamente é diminuído quando se emprega o mAGRP para o propósito de fazer uma busca local, com um pequeno raio. Esse ganho é o observado para os raios até 0,5, que correspondem exatamente ao raio da bacia de atração. Tal ganho se perde para raios um pouco maiores. No entanto, para raios ainda maiores, acima de 1,0, outro efeito parece se manifestar, causando nova diminuição no número de avaliações necessário para convergência. Essa outra diminuição, agora, é muito mais pronunciada que no caso anterior. Essa diminuição, certamente, não pode ser explicada por um mecanismo de “busca local”, pois tal explicação não seria compatível com aumento verificado do número de avaliações, para raios entre 0,6 e 0,9. A explicação que parece compatível com essas observações é a de que o efeito que passa a se manifestar, para raios maiores ou iguais a 1,0, é o de uma “busca de tendência global”, que causa a diminuição do número de avaliações necessário na etapa (i), e não mais na etapa (ii). Como a maior parte do esforço computacional neste problema estava associado precisamente à etapa (i), a perda do efeito de “busca local”, que melhoraria a eficiência da etapa (ii) é mais que compensada, permitindo a melhoria global do funcionamento do algoritmo. Essa explicação também é compatível com o fenômeno da melhoria do percentual de sucesso do algoritmo com o mAGRP: a não convergência ocorre, na maior parte das vezes, quando a etapa (i) não é bem sucedida. Assim, é de se esperar que uma intervenção no algoritmo que melhore a etapa (i) tenha efeito sobre o percentual de sucesso muito maior que o efeito de uma melhoria na etapa (ii). Um indício a respeito do preciso mecanismo envolvido nessa “busca de tendência global”, que causa a melhoria do desempenho do AG na etapa (i), pode ser obtido da observação de que os diversos “mínimos locais” da função objetivo encontram-se distanciados precisamente de 1,0. Ou seja, esse tipo de busca começa a se manifestar exatamente quando torna-se possível, com o mAGRP, saltar de um ponto “localmente próximo de um mínimo” situado em uma bacia de atração para um ponto “localmente próximo de um mínimo” na bacia de atração vizinha. É razoável esperar que o melhor ponto corrente, ao redor do qual será lançado o mAGRP, esteja próximo de um mínimo local. Para ser possível “melhorar” esse ponto, é preciso não apenas saltar para uma bacia de atração anexa que possua mínimo melhor: é também necessário que o novo ponto esteja suficientemente próximo desse mínimo, de forma a ser melhor que o ponto corrente. A distância a ser vencida, portanto, é da ordem de 1,0, para a função objetivo sob consideração. Evidentemente, com raio um pouco maior que esse “mínimo necessário”, é maior a probabilidade do mAGRP proporcionar saltos em direção às bacias de atração anexas que contêm pontos melhores que o ponto corrente. Isso explica a redução que continua a ocorrer no número médio de avaliações necessário para convergência, para raios maiores que 1,0, até 2,0. É de se esperar também que, se o raio aumentar muito mais, a especificidade do mAGRP para gerar saltos para bacias anexas deva diminuir. Isso se verifica, sendo observado um aumento do número médio de avaliações necessário para a convergência, para raios maiores que 2,0. No entanto, uma propriedade interessante observada é que o mAGRP parece pouco sensível a esse parâmetro, quando o raio cresce além daquele

1443

valor “ótimo”: mesmo perdendo a especificidade, o mAGRP permanece cumprindo o papel de executar uma a busca de tendência global. Mantendo agora o raio do mAGRP no valor ótimo de 2,0, é feito o teste da variação do número de indivíduos na população do mAGRP. Os resultados são mostrados na figura 3.

A figura 3 mostra que um número muito pequeno de indivíduos no operador mAGRP faz com que esse operador seja “irrelevante”. Um número entre 10% e 20% da população do AGRP, por outro lado, é suficiente para colocar em ação o efeito de busca de tendência global do operador. Populações maiores, entretanto, fazem com que o ganho no número de avaliações comece a diminuir, pois o próprio operador começa a despender um grande número de avaliações para sua própria execução. Os dados referentes à figura 3 são mostrados nas tabelas abaixo:

AG com Pop 200 e R 10 e Após o mAG com o R 2

% Pop 0.01 0.04 0.07 0.1 0.15 0.2 % Conv 58 100 100 100 100 100 Nº Aval 12995 6438 3878 2253 2119 2222

AG com Pop 200 e R 10 e Após o mAG com o R 2

% Pop 0.4 0.6 0.8 1 1.2 % Conv 100 100 100 100 100 Nº Aval 4098 5685 8053 9736 11338

Função com nove bacias de atração Essa função foi montada com nove bacias de atração tendo seus mínimos afastados de uma distância de cinco. O objetivo dessa função é testar a conjectura, levantada na discussão anterior, de que a característica de busca de tendência global exibida pelo operador mAGRP esteja associada com o deslocamento consecutivo do melhor ponto corrente, de uma bacia de atração para outra bacia anexa. A “tendência global” captada pelo operador mAGRP seria então caracterizada pela contiguidade de

Figura 3: Número de avaliações necessário para convergência, emfunção do tamanho da população do mAGRP.

1444

bacias sucessivamente melhores. A função utilizada para teste é formada de nove termos com a seguinte estrutura:

f(x) = - (Cn*exp(-(x-xn)'*Q*(x-xn))

sendo os valores de Cn e Xn para 0 ≤ n ≤ 8 mostrados nas tabelas a seguir:

n Cn Xn

0 1 [-6 20]'

1 4 [-2 17]'

2 6 [2 14]'

3 9 [7 14]'

4 11 [11 11]'

n Cn Xn

5 13 [11 6]'

6 16 [8 2]'

7 17 [5 6]'

8 19 [1 3]'

As curvas de nível da função assim construída são mostradas na figura 5. Nota-se que a função é caracterizada pela presença de bacias de atração isoladas, circundadas por “platôs” nos quais a função fica praticamente constante. Trata-se, portanto, de um problema cuja otimização é difícil para grande parte dos algoritmos existentes.

A tabela a seguir mostra o comportamento do AGRP sem mAG:

(2)

Figura 5: Gráfico de curvas de nível da função da eq. 2, mostrando o caminho percorrido pelo melhor ponto corrente da população quando se aplica o operador mAGRP.

1445

AG Puro R AG 10 100

% Conv 50 70

Nº Aval 1022 20746

Os testes novamente foram executados com população de 200 e raio de dispersão de 10 para o AGRP, sendo a população do mAG fixada em 10% da população do AG. O comportamento do AGRP, agora com operador mAGRP, é mostrado na tabela a seguir, para diferentes raios no mAGRP:

Executando o AG juntamente com o mAG

R mAG 1 2,5 5,06 7,6 11,4 17,1 25,6 30000

% Conv 71 74 100 100 100 100 100 78

Nº Aval 2347 2621 2439 2637 2704 3244 3123 11548

Deve-se notar, na tabela acima, que o algoritmo AGRP com operador mAGRP passou a convergir em 100% das execuções a partir de um raio utilizado de 5,0, igual à distância entre os mínimos consecutivos, conforme havia sido conjecturado. Desta feita, é interessante notar que o AGRP puro converge em apenas 50% dos casos (para o mesmo raio 10), mas com número médio de avaliações muito menor que o melhor valor obtido pelo AGRP com mAGRP. Isso possivelmente ocorre porque o problema é de baixa complexidade (poucos mínimos): quando o algoritmo converge, essa convergência é rápida. Quando não converge rapidamente, no entanto, o padrão de informação existente no problema é desfavorável para permitir uma ulterior convergência, mesmo à custa de muitas avaliações de função. O operador mAGRP, nesse caso, permite fazer algum processamento do padrão de informação do problema, e consegue obter convergência mesmo nos casos mais desfavoráveis. O padrão de evolução do algoritmo com operador mAGRP, num caso bastante desfavorável, é representado pelas setas na figura 5. Esse processamento, entretanto, necessariamente representa algum custo computacional, de forma que a média do número de avaliações que são necessárias para a convergência fica elevada. Em outras palavras: o mAGRP transforma problemas para os quais não haveria qualquer possibilidade de convergência em problemas nos quais o algoritmo converge, à custa de esforço computacional. Nos problemas em que haveria convergência de qualquer forma, possivelmente o operador mAGRP não está causando qualquer efeito, nem de melhoria, nem de degradação do desempenho.

Conclusões

O operador mAGRP mostrou indícios de que pode servir para executar a função de “busca de tendência global” em funções multimodais, sendo tal busca executada pela visita consecutiva a mínimos de bacias de atração adjacentes. Tal comportamento parece ocorrer quando o raio utilizado no operador mAGRP é pelo menos igual à distância entre mínimos adjacentes. Esse comportamento, entretanto, fica melhor para raios um pouco maiores que essa distância, e não se deteriora significativamente para raios até mesmo muito maiores que tal distância. Parece portanto possível recomendar, na ausência de informação mais detalhada a respeito da geometria da função objetivo, a utilização de raios da mesma ordem de grandeza que o raio empregado no próprio algoritmo genético. Evidentemente, no caso de se dispor de tal informação detalhada, parece recomendável estabelecer o raio do mAGRP em um valor próximo da distância esperada entre os mínimos locais.

A conclusão mais curiosa do presente estudo é, talvez, a observação de que o operador microgenético, pelo menos na versão que foi aqui estudada, não parece ser a melhor alternativa para

1446

executar a função para a qual foi proposto, a de busca local. O operador de “cruzamento real polarizado” parece executar tal função com maior eficácia. No entanto, o operador mAGRP parece ser, potencialmente, importante elemento constitutivo de algoritmos genéticos genéricos, para executar a função de explorar o tipo de informação global relacionada com a contiguidade de bacias de atração contendo mínimos sucessivamente melhores. Tal informação, dependendo da geometria do problema, pode ser dificilmente captável através de outros mecanismos.

Bibliografia Belmont-Moreno., E. (2001). The role of mutation and population size in genetic algorithms applied

to physics problems. International Journal of Modern Physics C, 12(9):1345-1355.

Choi, D. H. ; Oh, S. Y. (2000). A new mutation rule for evolutionary programming motivated from backpropagation learning. IEEE Transactions on Evolutionary Computation, 4(2):188-190.

Fan, H. Y.; Lu, J. W. Z.; Xu., Z. B. (2000). An empirical comparison of three novel genetic algorithms. Engineering Computations, 17(8):981-1001.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.

Hasancebi, O.; Erbatur, F. (2000). Evaluation of crossover techniques in genetic algorithm based optimum structural design. Computers & Structures, 78(1-3):435-448.

Johnson, J. M.; Ramat-Semii, Y. (1997). Genetic algorithms in engineering electromagnetics. IEEE Antennas and Propagation Magazine, 39(4):7-25.

Kazarlis, S. A.; Papadakis, S. E.; Theocharis J. B.; Petridis, V. (2001). Microgenetic algorithms as generalized hill-climbing operators for GA optimization. IEEE Transactions on Evolutionary Computation, 5(3):204--217.

Lin, Y. C.; Hwang, K. S.; Wang F. S. (2001). Co-evolutionary hybrid differential evolution for mixed-integer optimization problems. Engineering Optimization, 33(6):663-682.

Man, K. F.; Tang, K. S.; Kwong, S. (1996). Genetic algorithms: concepts and applications. IEEE Transactions on Industrial Electronics, 43(5):519—534.

Pongchareen, P.; Stewardson, D. J.; Hicks, C.; Braiden, P. M. (2001). Applying designed experiments to optimize the performance of genetic algorithms used for scheduling complex products in the capital goods industry. Journal of Applied Statistics, 28(3-4):441-455.

Potts, J. C.; Giddens, T. D.; Yadav, S. B. (1994) The development and evaluation of an improved genetic algorithm based on migration and artificial selection. IEEE Transactions on Systems, Man and Cybernetics, 24(1):73-86.

Ramos, R. M.; Saldanha, R. R.; Takahashi, R. H. C.; Moreira, F. J. S. (2003). The real-biased multiobjective genetic algorithm and its application to the design of wire antennas. IEEE Transactions on Magnetics, 39(3):1329--1332.

Sareni, B.; Krahenbuhl, L. (1998). Fitness sharing and niching methods revisited. IEEE Transactions on Evolutionary Computation, 2(3):97-106.

Scorretti, R.; Takahashi, R. H. C.; Nicolas, L.; Burais, N. (2004). Optimal characterization of LF magnetic field using multipoles. International Journal of Computation and Mathematics in Electrical and Electronic Engineering (to appear).

Takahashi, R. H. C.; Ramos, D. C. W.; Peres, P. L. D. (2002). Robust control synthesis via a genetic algorithm and LMIs. in Proceedings of the IFAC World Congress. IFAC. Barcelona - Spain.

1447

Takahashi, R. H. C.; Vasconcelos, J. A.; Ramirez, J. A.; Krahenbuhl, L. (2003). A multiobjective methodology for evaluating genetic operators. IEEE Transactions on Magnetics, 39(3):1321--1324.

Vasconcelos, J. A.; Ramirez, J. A.; Takahashi, R. H. C.; Saldanha, R. R. (2001). Improvements in Genetic Algorithms. IEEE Transactions on Magnetics. 37(5):3414-3417.