Implementation in computer code
4.3 Testing the numerical precision
(NSGA-II)
Dentre os diversos métodos utilizados para solucionar problemas de otimização multiobjetivo destacam-se os algoritmos evolucionários. Estes métodos permitem que um conjunto de so- luções aproximadas da fronteira Pareto sejam encontradas mesmo para problemas discretos e não-convexos.
O primeiro algoritmo genético multiobjetivo, conhecido como VEGA (Vector Evaluated Genetic Algorithm), foi proposto por Schaffer [1984]. O algoritmo é constituído dos conceitos básicos do algoritmo genético simples e de otimização multiobjetivo. Neste algoritmo não há elitismo e mecanismo para melhorar a diversidade das soluções na fronteira. Além disso, outra característica do método é que a população é dividida em subconjuntos e os indivíduos de cada subconjunto são avaliados de acordo com um dos objetivos do problema.
Posteriormente, Goldberg [1989] apresentou um procedimento de ordenação das soluções por fronteiras não-dominadas e, a partir de então, diversos outros algoritmos genéticos multi-
Figura 2.4: Busca Local Iterativa Multiobjetivo (MOILS) [Geiger, 2009]
objetivo foram propostos na literatura, como: MOGA (Multiobjective Genetic Algorithm) [Fonseca e Fleming, 1993], NPGA (Niched Pareto Genetic Algorithm) [Horn et al., 1994], NSGA (Non-Dominated Sorting Genetic Algorithm) [Srinivas e Deb, 1994], NSGA-II (Fast Non-Dominated Sorting Genetic Algorithm) [Deb et al., 2002], SPEA (Strength Pareto Evo- lutionary Algorithm) [Zitzler, 1999], SPEA-2 [Zitzler et al., 2002], PESA [Corne et al., 2000], PESA-II [Corne et al., 2001], dentre outros.
O que difere a maioria destes algoritmos é a forma como é feita a avaliação dos indivíduos, como é aplicado o elitismo ou, ainda, o método utilizado para garantir a diversidade das soluções na fronteira Pareto aproximada.
O NSGA-II, proposto por Deb et al. [2002], é um dos algoritmos mais utilizados para solucionar problemas de otimização com mais de um objetivo. A vantagem do NSGA-II se deve a sua baixa complexidade computacional, O(MN2), sendo M o número de objetivos e N o tamanho da população. Além disso, o método é capaz de gerar soluções de boa qualidade para a maioria dos problemas no qual é aplicado, sendo estas soluções bem distribuídas na fronteira de soluções não-dominadas.
O NSGA-II possui um módulo para classificação da população baseado no ordenamento de soluções proposto por Goldberg [1989], chamado de fast-non-dominated-sort. Este proce- dimento consiste em classificar os indivíduos de maneira elitista utilizando a dominância de Pareto como referência. A classificação é feita de acordo com a relação de dominância das soluções, no qual a população é dividida em subgrupos ou fronteiras de acordo com o seu grau de dominância. Em um mesmo subgrupo, nenhuma solução deve dominar outra solução.
A primeira fronteira contém os melhores indivíduos de toda a população, sendo eles so- luções não dominadas por nenhuma outra solução. Seguindo esta ideia, a última fronteira contém os piores indivíduos da população. A figura 2.5 apresenta uma ilustração de um problema de minimização com duas funções objetivo e três fronteiras.
Figura 2.5: Ordenação por dominância
Para garantir a diversidade das soluções ao longo da fronteira Pareto, o NSGA-II utiliza um operador denominado distância de multidão (Crowding Distance) [Deb et al., 2002]. Este operador melhora a distribuição das fronteiras, evitando que as soluções fiquem próximas umas das outras e represente de forma adequada a fronteira Pareto.
Dado os subgrupos formados na ordenação por dominância, para avaliar soluções em um mesmo grupo e garantir maior diversidade, o operador distância de multidão indica o valor do perímetro do cubóide criado a partir de uma solução, sendo os vértices desse cubóide as soluções vizinhas a solução no subgrupo ou fronteira a qual pertencem. Os indivíduos contidos nas extremidades da fronteira recebem um valor arbitrariamente grande a fim de serem priorizados durante a seleção elitista. Os demais indivíduos i da fronteira recebem um valor correspondente à distância entre i e seus vizinhos mais próximos. Assim sendo, uma solução com a melhor classificação em uma fronteira é aquela que apresenta um maior valor da distância de multidão. A figura 2.6 ilustra o cálculo da distância de multidão. Na figura, a distância de multidão da solução i é dada pelo perímetro do retângulo formado pelos seus vizinhos mais próximos i − 1 e i + 1.
Dados os dois procedimentos básicos do NSGA-II, o algoritmo aplica o método de seleção por torneio da seguinte forma: uma solução i, pertencente a fronteira F ronteirai após a ordenação de dominância, é considerada melhor que a solução j, pertencente a fronteira F ronteiraj, se:
Figura 2.6: Distância de Multidão
2. F ronteirai = F ronteiraj e a distância de multidão de i é maior que distância de multidão de j.
O algoritmo 2.2 mostra todo o procedimento do NSGA-II. O algoritmo inicia com a geração aleatória de uma população inicial P de tamanho N (linhas 2 e 3). Uma nova população Q de tamanho N é gerada através de mecanismos de seleção, cruzamento e mutação aplicados a população inicial. As populações Q e P são então agrupadas em uma população R, de tamanho 2N, que passará pela ordenação por não-dominância (linhas 5 e 6). A partir de então (linhas 9-11), N soluções de R serão copiadas para a população P da seguinte forma: enquanto não extrapolar o limite máximo de N soluções da população P , as soluções da primeira fronteira de R são inseridas em P . Em seguida, se o limite N ainda não foi alcançado, as soluções da segunda fronteira serão copiadas e assim sucessivamente. Este procedimento se repete até que não seja mais possível inserir inteiramente uma fronteira da população P . Neste instante, alguns indivíduos da fronteira serão selecionados de acordo com o operador distância de multidão, até completar os N indivíduos da população P (linhas 13-19). A figura 2.7 ilustra o procedimento de inserção das soluções da população R na população P .
Em seguida, aplica-se os operadores de seleção por torneio, conforme mencionado anteri- ormente, cruzamento e mutação, formando uma nova população Q. O procedimento então se repete até que um determinado critério de parada seja satisfeito. Ao final, o método retorna as soluções não dominadas contidas nas populações P e Q.
2.4 Métodos de Avaliação de Solução
A análise da qualidade dos resultados obtidos para problemas que envolvem múltiplos ob- jetivos é mais complexa que para problemas com um único objetivo. Isto ocorre devido
Algoritmo 2.2 Pseudocódigo do NSGA-II
1: n ← 0; {contador de gerações}
2: Pn← Gerar População Inicial(); {População Pai}
3: Qn ← Aplicar operadores de Seleção, Cruzamento e Mutação(Pn); {População
Filha}
4: repita
5: Rn ← Pn∪ Qn;
6: F [ ] ← Ordenação por dominância(Rn); 7: Pn+1 ← ∅; 8: i ← 1 9: enquanto|Pn+1+ Fi| ≤ N faça 10: Pn+1← Pn+1∪ Fi; 11: i ← i + 1; 12: fim enquanto
13: para todosj ∈ Fi faça
14: dj ← Distância de Multidão(sj); 15: fim para
16: s ← Ordenar as soluções s ∈ Fi crescentemente de acordo com o valor de dj; 17: para j = 1 até j = N − |Pn+1| faça
18: Pn+1← sj; 19: fim para
20: Qn+1← Aplicar operadores de Seleção, Cruzamento e Mutação(Pn+1); 21: n ← n + 1;
22: até Critério de Parada
23: Rn← Pn∪ Qn;
24: F ronteira ← Obter soluções não-dominadas(Rn); 25: retornar F ronteira;
Pn
Qn
F1
F2
F3
F4
F5
Rn
F3
Pn+1
Rejeitadas Rejeitadas O rd e n a ç ã o p o r n ã o -d o m in â n c ia D is tâ n c ia d e m u lti d ã oFigura 2.7: Procedimento do NSGA-II
à otimização multiobjetivo, em grande parte, envolver objetivos conflitantes, levando a um conjunto de soluções não dominadas.
As principais características avaliadas em soluções de problemas multiobjetivo são: (i) a proximidade à fronteira Pareto ótima; (ii) a cardinalidade, que é o número de soluções obtidas; (iii) a distribuição, isto é, se as soluções estão distribuídas de maneira uniforme ao longo da fronteira; e (iv) a extensão, que é o intervalo de valores coberto pela fronteira para cada objetivo.
Existem diversas métricas para avaliar uma solução para o problema de otimização com múltiplos objetivos, cada qual avalia uma determinada característica desejável a esta solução. As métricas aplicadas neste trabalho são: hipervolume (S) e Cobertura (C).