O Algoritmo Genético Multiobjetivo

1. Algoritmo Genético Multiobjetivo

A consideração de mais de uma função objetivo em um problema de otimização induz à necessidade de uma análise de custo-benefício das soluções obtidas. A depender do grau de importância de cada objetivo para o tomador de decisão, algumas soluções podem ser mais preferíveis a outras. As informações de custo-benefício, ou simplesmente de tradeoff, versam sobre como a melhoria em relação a um objetivo pode afetar negativamente os demais objetivos. Nesse sentido, a otimização multicritério é de fundamental importância, em especial se o problema necessitar a consideração de dois ou mais critérios conflitantes entre si.

A principal diferença entre o Algoritmo Genético (AG) para um objetivo único e o AG multiobjetivo é a fase de avaliação e seleção dos indivíduos. O conceito de dominância e de otimalidade de Pareto é comumente utilizado para a análise das soluções obtidas em problemas multiobjetivo, dada a impossibilidade de encontrar uma única solução que otimize todas as funções objetivo simultaneamente. Dessa forma, o AG multiobjetivo busca a fronteira de Pareto, um conjunto de soluções não dominadas, ao invés de uma solução única, e, a menos que um algoritmo adicional de preferência de solução seja implementado, um AG multiobjetivo fornece, como solução, um conjunto de indivíduos não dominados pertencentes à fronteira de Pareto.

Uma vez que o AG pertence à classe das heurísticas populacionais probabilísticas, e não exaustiva, seu processo de busca de solução consiste em amostrar uma fronteira de Pareto que convirja para a real fronteira de Pareto e mantenha, a cada passo, uma distribuição tão uniforme quanto possível das soluções não dominadas, objetivos essenciais quando não é possível avaliar exaustivamente uma fronteira de Pareto. Diversos trabalhos mostram a eficiência dos AG’s multiobjetivo quando da aproximação da real fronteira de Pareto.

1.1. Dominância em problemas Multiobjetivo e a Fronteira de Pareto

Seja M o número de funções objetivo do problema, M > 1, uma solução x1 é dita dominada por uma solução x2 se ambas as condições a seguir forem satisfeitas, considerando objetivos de maximização:

1 - A solução x1 não é melhor do que a solução x2 em nenhum dos objetivos, ou seja, fi(x1) ≤ fi(x2) para todo i = 1, ..., n, onde fi(x) é o valor da i-ésima função objetivo para uma solução x;

2 - A solução x1 é estritamente pior do que a solução x2 em pelo menos um dos objetivos, ou seja, fi(x1) < fi(x2) para algum i∈{1,…,M}.

Se a condição 2 for válida para todos os objetivos do problema, ou seja, se fi(x1) < fi(x2) ∀ i∈{1,…,M}, tem-se uma dominância forte de Pareto (x1 ≺ x2). A satisfação das condições 1 e 2 de forma que exista algum i, tal que fi(x1) = fi(x2), constitui-se uma dominância fraca de Pareto (x1 =≺ x2).

Se uma solução viável não é dominada por nenhuma outra solução viável ela é uma Solução Pareto-Ótima. Ou seja, X* ∈ U é uma solução Pareto-Ótima, ou solução não dominada, se ∄ X ∈ U | X* =≺ X, onde U ⊆ Rm = {u ∈ Rm : G(X*) ≥ 0 e H(X*) = 0}, com G(.) e H(.) sendo, respectivamente o vetor das funções de restrições de desigualdade e de igualdade.