CEN/TS 12390-9 (Boråsmetoden)

EA parecem ser particularmente apropriados para a tarefa de encontrar soluções óti- mas de Pareto pois processam um conjunto de soluções em paralelo. Fonseca e Fle- ming [107] bem como Valenzuela-Rendón [226] sugerem que a otimização e pesquisa mul- tiobjetivo podem ser áreas onde EA seja capaz de produzir melhores resultados quando comparado a outros métodos computacionais.

Desde 1896, quando o conceito de ótimo de Pareto foi introduzido, diversas técnicas para resolução de MOP, tradicionais (Programação Matemática) ou alternativas (Algo- ritmos Genéticos, Algoritmos Evolutivos, Sistemas Imunológicos Artificiais, Enxame de Partículas), têm sido desenvolvidas. O objetivo é que os métodos apresentem soluções não-dominadas bem distribuidas pela frente de Pareto (global), facilitando o conhecimento do problema e a escolha da(s) solução(ões) mais adequada(s) pelo decisor.

Considerando que a solução de um MOP é constituída por um conjunto de pontos, a utilização de uma heurística baseada em populações (o que inclui EA, mas também AIS), permite encontrar vários pontos do conjunto ótimo de Pareto em uma única execução do algoritmo [231]. Outro grande potencial destes algoritmos é a integração da ampla exploração do espaço de busca com um processo de busca mais localizado resultando em um alto grau de robustez, que permite sua aplicação a diversos problemas práticos, junto aos quais outras estratégias de solução se mostram inócuas [14].

Além disso, os problemas reais tornaram-se cada vez mais complexos, sem funções definidas, na maioria das vezes descontínuas e com domínios não-convexos, dificultando a utilização de métodos exatos na resolução. Some-se a isto, o fato de heurísticas baseadas em populações serem menos suscetíveis à forma ou à continuidade da frente de Pareto [47]. As técnicas tradicionais exigem um conhecimento prévio do problema, uma especifica- ção detalhada ou uma indicação de preferências, o que quase sempre não é possível. Mas os EA (e de fato Algoritmos Bioinspirados, de uma maneira geral) requerem apenas a descrição aproximada das características que representam o comportamento global, como uma função (ou medida) de afinidade, adaptabilidade ou desempenho [48, 231].

Estas são algumas das razões que têm impulsionado cada vez mais a utilização dos métodos bioinspirados em aplicações, além de sua flexibilidade, generalidade e robustez.

Os EA têm demonstrado bom desempenho na resolução de MOPs e, nos últimos anos, diversas abordagens e algoritmos foram apresentados dentre os quais se destacam: Vector Evaluated Genetic Algorithm (VEGA) [204], Multi-Objective Genetic Algorithm

(MOGA) [106], Niched Pareto Genetic Algorithm (NPGA) [122], Pareto Archived Evo- lution Strategy (PAES) [143], Nondominated Sorting Genetic Algorithm (NSGA) [220] e NSGA-II [89], Streght Pareto Evolutionary Algorithm (SPEA) [248] e SPEA2 [245], entre outros.

O primeiro Algoritmo Evolutivo Multiobjetivo (MOEA) foi proposto por Schaffer em 1985 [204] e denominado Vector Evaluated Genetic Algorithm (VEGA). É um MOEA no qual a população é dividida em um número de subpopulações igual à quantidade de objetivos que se deseja otimizar. A idéia é fazer com que cada subpopulação seja avaliada com base em um único objetivo, e, posteriormente, mesclar as subpopulações em uma única à qual se aplicam operadores genéticos convencionais (crossover e mutação). Este é um algoritmo simples, e não garante a geração de soluções não-dominadas. Como foi observado posteriormente, unir todos os indivíduos das subpopulação a fim de obter uma nova população equivale a combinar linearmente os componentes do fitness para obter uma única função de fitness, ou seja, equivale a uma solução monobjetivo onde os coeficientes de peso dependem da população atual. Isto significa que, no caso geral, dois indivíduos não-dominados não só serão amostrados com taxas diferentes, como no caso de uma superfície côncava, a população pode se dividir em diferentes espécies, cada qual particularmente forte em um dos objetivos. Schaffer havia antecipado esta propriedade de VEGA e chamou-a de especiação. A especiação é indesejada, na medida em que se opõe ao objetivo de encontrar soluções não-dominadas que satisfaçam da melhor maneira possível todos os objetivos ao mesmo tempo [106].

No Multi-Objective Genetic Algorithm (MOGA), proposto por Fonseca e Fleming [106], a aptidão de um indivíduo está relacionada à quantidade de indivíduos que o dominam, de maneira que os indivíduos não-dominados têm a mesma aptidão, que é a maior da população.

Nondominated Sorting Genetic Algorithm (NSGA) foi proposto por Srinivas e Deb [220]. Neste algoritmo os indivíduos não-dominados globais (ou seja, não-dominados com relação a toda a população) são os primeiros a serem classificados, sendo-lhes atribuído um valor falso. Estes indivíduos são removidos da população para que o processo de classificação dos indivíduos restantes tenha continuidade. NSGA-II [89] é uma versão mais eficiente do algoritmo, na qual foram incorporados um operador de crowding e um mecanismo elitista (para preservar as melhores soluções encontradas).

Niched Pareto Genetic Algorithm (NPGA), proposto por Horn et al. [122], usa uma versão modificada de seleção por roleta associada à dominância de Pareto que funciona da seguinte maneira: são selecionados dois pais possíveis e eles são comparados com um subconjunto da população (selecionado de maneira aleatória), aquele pai que seja não- dominado com relação ao subconjunto será o ganhador. Se há um empate (ambos são

dominados, ou não-dominados), o torneio é decidido com base em um critério de crow- ding, o indivíduo com menos vizinhos ganha. Uma versão melhorada, chamada NPGA2, utiliza ordenamento aplicado ao conceito de ótimo de Pareto enquanto a seleção conti- nua sendo feita por meio de sorteio (utilizando um esquema diferente de comparação de aptidão) [101].

Strength Pareto Evolutionary Algorithm (SPEA), proposto por Zitzler e Thiele [244], usa um arquivo externo para armazenar todas as soluções não-dominadas encontradas previamente. Cada indivíduo tem a sua força (strength) calculada de maneira semelhante à feita por MOGA, uma vez que depende da quantidade de indivíduos que os dominam. A aptidão de um indivíduo da geração atual é calculada segundo a força das soluções con- tidas no arquivo externo que o domimam. Para obter uma boa distribuição das soluções dominadas, SPEA usa um método de ligação média (average linkage method). A versão melhorada deste algoritmo, SPEA2 [245], possui três principais diferenças com relação à versão original: 1) na atribuição da aptidão são considerados aspectos relacionados não só à quantidade de indivíduos que dominam o indivíduo sendo avaliado, como quantos ele domina; 2) é utilizada uma estimativa de densidade populacional com relação aos vizinhos a fim de deixar a busca mais eficiente; e, 3) é utilizado um método de quebra do arquivo externo, com o objetivo de assegurar que as soluções pertencentes aos extremos da frente de Pareto não se percam.

Pareto Archived Evolution Strategy (PAES), proposto por Knowles e Corne [142, 143] é uma estratégia evolutiva (1+1), ou seja, tem-se uma população de um indivíduo pai que gera apenas um filho por mutação. Usa um arquivo externo para manter as soluções não-dominadas obtidas ao longo do processo evolutivo e, para manter a diversidade, usa um mecanismo de crowding baseado em uma divisão recursiva do espaço das funções objetivo, de maneira que os indivíduos são “alocados” em uma rede que facilita determinar e controlar a distribuição das soluções obtidas.