Fiskeforsøk

Um levantamento exaustivo e pormenorizado do trabalho desenvolvido nesta área pode ser obtido em [Fonseca, Fleming 1995] e [Coello 1999]. Nos trabalhos referidos, os seguintes factores são considerados determinantes para o pioneirismo dos GA como meta- heurística multiobjectivo:

1. o facto de se trabalhar, em cada momento, com uma população de soluções, o que permite procurar o conjunto de soluções eficientes numa única execução do algoritmo, em vez de se realizar um conjunto de execuções separadas, como é o caso das abordagens de programação matemática tradicionais;

2. a menor susceptibilidade à forma ou continuidade da fronteira de Pareto, que constituem preocupações fundamentais nas técnicas de programação matemática. Com base nas referências citadas, apresenta-se de seguida uma descrição necessariamente sucinta de algumas das abordagens mais relevantes nesta área, estruturadas em três grandes grupos:

1. baseadas em funções de agregação;

2. outras, não baseadas na noção de óptimo de Pareto; 3. baseadas na noção de óptimo de Pareto.

Abordagens de GA baseadas em funções de agregação

As abordagens baseadas em funções de agregação surgem naturalmente ligadas ao facto de os GA utilizarem informação de aptidão ("fitness") escalar, inspirando-se nos diversos métodos clássicos que empregam funções de agregação (e mantendo as suas vantagens e inconvenientes):

§ Equivalente Paramétrico [Syswerda, Palmucci 1991], § "Goal Programming" [Wienke et al. 1992],

§ "Goal Attainment" [Wilson, MacLeod 1993] e

Um exemplo particular de utilização de funções de agregação, neste caso aditivas, e com grande interesse na área das meta-heurísticas, é a incorporação de restrições na função objectivo, considerando penalizações pela sua violação.

Outras abordagens de GA, não baseadas na noção de óptimo de Pareto

Deve, antes do mais, referir-se que uma preocupação comum a diversas abordagens aqui enquadradas consiste em procurar evitar a convergência para uma única região da fronteira de Pareto. Para tal, o mecanismo utilizado mais frequentemente é o "fitness sharing" [Goldberg, Richardson 1987], um mecanismo de criação de "nichos" ("niches"), que permite manter soluções ao longo de toda a fronteira de Pareto. Este mecanismo realiza ajustes ao valor das aptidões das soluções, penalizando as que se encontram em áreas de grande "densidade" de soluções. Em torno de cada solução a avaliar é definido um "nicho" de determinada dimensão, sendo a "densidade" aferida não só pelo número de soluções aí encontradas, mas também pela sua proximidade à solução a avaliar.

O conjunto de outras abordagens não baseadas na noção de óptimo de Pareto, a que se refere esta secção, fundamenta-se em dois princípios: o tratamento separado dos objectivos e a consideração de objectivos alternativos. Apresentam-se de seguida algumas destas abordagens.

1. Tratamento separado dos objectivos

§ Em [Schaffer 1985] foi introduzido o VEGA (Vector Evaluated Genetic Algorithm), algoritmo em que se realizam diversas selecções de soluções, segundo cada um dos objectivos, dando origem a diversas sub-populações que são posteriormente fundidas numa única população.

§ O Método Lexicográfico encontrou aplicação na selecção de soluções realizada por comparação de pares, de acordo com as prioridades atribuídas aos objectivos pelo agente de decisão [Fourman 1985]. Uma implementação alternativa recorre à selecção aleatória, em cada iteração, do objectivo a utilizar para comparação [Kursawe 1991].

§ Em [Périaux et al. 1997] é apresentada uma abordagem baseada em Teoria dos

Jogos, aplicada a um problema biobjectivo. Duas sub-populações independentes

são vistas como jogadores não-cooperativos que, em cada geração, tentam optimizar um dos objectivos, sem degradar o outro, sendo a melhor solução de cada uma das sub-populações enviada para a outra.

§ Diversas abordagens têm utilizado o conceito de "géneros", identificados com objectivos. No caso mais geral [Lis, Eiben 1996], a recombinação envolve várias soluções geradoras, uma de cada género. O género da solução gerada é idêntico ao da solução geradora mais determinante para as suas características. Para cada género há diferentes funções de aptidão e o operador de mutação é concebido de forma a não alterar o género das soluções.

Nos casos referidos, com excepção da abordagem baseada em Teoria dos Jogos, na qual se gera apenas uma solução não-dominada, procede-se, durante a execução do algoritmo, à identificação de soluções não-dominadas. Esta informação não é, no entanto, utilizada pelos algoritmos.

2. Utilização de objectivos alternativos

§ Em [Hajela, Lin 1992] as soluções são avaliadas por comparação com o ponto ideal, determinado pela resolução separada dos problemas de optimização para cada critério. Nessa avaliação, é utilizada uma abordagem min-max, sendo considerada como solução desejável aquela que apresentar os menores incrementos relativos, face aos extremos de cada função objectivo. Na referência citada são utilizadas diversas combinações de pesos dentro da população. Noutras referências, diversas variações têm sido propostas, como a utilização de pesos aleatórios, a evolução paralela de várias populações com conjuntos de pesos distintos, ou a aplicação da abordagem min-max na selecção por comparação de pares.

§ Uma abordagem baseada na determinação de distâncias relativas ao conjunto de Pareto é apresentada em [Osyczka, Kundu 1995]. As soluções não dominadas têm uma avaliação unitária, enquanto a solução mais distante de todas as soluções

não-dominadas, de acordo com uma métrica euclidiana (L2), tem uma avaliação

nula. Para as restantes soluções, as avaliações são atribuídas por interpolação linear entre zero e um, com base na respectiva distância euclidiana à solução não- dominada mais próxima.

§ Em [Valenzuela-Rendón, Uresti-Charre 1997] o problema original é transformado num problema com dois objectivos: minimizar um indicador de dominância, constituído pela média ponderada do número de soluções que dominaram o indivíduo até ao momento; minimizar um contador de "nicho", dado pela média ponderada do número de indivíduos considerados próximos segundo uma certa função de "sharing". Este problema é transformado num problema de um só objectivo por combinação linear dos dois objectivos.

Abordagens de GA baseadas na noção de óptimo de Pareto

Em [Goldberg 1989] foi proposta a utilização de uma função de aptidão baseada na optimalidade de Pareto. Esta abordagem opera com base no operador de selecção e numa

classificação de não-dominância: determinam-se as soluções não-dominadas, que recebem a

classificação mais elevada e são removidas da população; a operação repete-se até toda a população estar classificada. Para impedir a convergência para uma única solução ("genetic

drift"), recorre-se, conforme já referido, a um mecanismo de criação de "nichos".

Uma das maiores dificuldades com que se depara este tipo de abordagem é a inexistência de algoritmos eficientes para verificar a não-dominância num conjunto de soluções admissíveis. A determinação de uma dimensão de nicho adequada apresenta também algumas dificuldades.

Neste conjunto de abordagens é ainda possível destacar:

§ "Multiple Objective Genetic Algorithm" [Fonseca, Fleming 1993]. A classificação de uma solução corresponde, neste caso, ao número de soluções pelos quais a solução é dominada. As soluções são ordenadas de acordo com a sua classificação, sendo-lhes atribuída uma aptidão, através de interpolação, linear ou não, da melhor à pior classificação. Para todas as soluções com a mesma classificação é calculada uma aptidão média, de forma a que possam ser objecto de amostragem com a mesma probabilidade.

Para evitar a convergência prematura, recorre-se a métodos de formação de nichos, através de "fitness sharing" no espaço dos objectivos. Este facto impede a existência na população de duas soluções diferentes com vectores de critérios idênticos.

§ "Non-dominated Sorting Genetic Algorithm" [Srinivas, Deb 1993]. Este algoritmo procede de forma semelhante ao anterior, mas recorrendo à classificação proposta em [Goldberg 1989].

§ "Niched Pareto Genetic Algorithm" [Horn, Nafpliotis 1993]. A selecção é, neste caso, baseada na comparação de pares de soluções, mas tomando em consideração um conjunto de outras soluções. Se ambas as soluções forem dominadas ou não- dominadas, o resultado decide-se por "fitness sharing".