Embed Size (px)
Citation preview
Derick Eduardo Dias Rosa
Orientador: Claudomiro Sales
Universidade Federal do Pará - UFPA
Laboratório de Eletromagnetismo Aplicado - LEA
Programa de Iniciação Científica
Introdução
Conceitos básicos
Soluções Pareto-Ótimas e Metas em Otimização Multiobjetivo
Técnicas Tradicionais para MOOP
Algoritmos Evolutivos para Otimização Multiobjetivo
Algoritmos Genéticos
Métricas de Desempenho de MOEAs
Conclusões
Muitos problemas do mundo real possuem múltiplos
objetivos a serem atingidos.
Esse objetivos são, na maioria das vezes, conflitantes entre si.
Problema de Otimização Multiobjetivo (MOOP, do inglês
Multi-Objective Optimization Problem)
Exemplos:
Uma empresa tem que:
– minimizar taxa de acidentes;
– minimizar os custos.
Outra empresa tem que:
– maximizar o lucro;
– minimizar a taxa de poluição.
MOOP
– Procurar um vetor de variáveis de decisão que satisfaz certas
restrições e otimiza um vetor cujos elementos são funções objetivos.
– Espaço de buscar maior.
– Noção de solução ótima ampliada para vários objetivos
Maximizar/Minimizar: 𝑓1 𝑥 , 𝑓2 𝑥 , . . . , 𝑓𝑛(𝑥)
Descrição matemática de
critérios de performance
Formalmente:
Funções Objetivo
Restrições
Mapeamento x -> f(x)
Para cada solução x no
espaço de decisão,
existe um f(x) no espaço
de objetivos.
Exemplo que ilustra o preço e o desempenho de várias opções (1–5) de compra de computadores.
Existe então um “compromisso” entre os
objetivos. Quanto maior a performance, maior o
preço do computador e vice-versa.
Em um MOOP há dois possíveis tipos de soluções:
1. Soluções que, quando comparadas às demais, apresentam pior desempenho sob todos os objetivos simultaneamente considerados.
2. Soluções que, quando comparadas às demais, são melhores em um ou mais objetivos.
• Não é reflexiva.
• Não é simétrica.
• É transitiva.
Dominância
Dadas duas soluções x e y, diz-se que x domina y se as seguintes condições
são satisfeitas: A solução x é pelo menos igual a y em todas funções;
A solução x é superior a y em pelo menos uma função objetivo.
Todas as soluções não dominadas do espaço de busca S formam o conjunto Pareto-ótimo.
Um conjunto de soluções para um MOOP, pode ser dividido em conjunto de soluções dominadas e não-dominadas empregando o operador de dominância.
Dado um conjunto Pareto-ótimo P, a fronteira de Pareto é definida como:
Dois conjuntos Pareto-ótimos que são não-dominados localmente, mostrando a sua vizinhança no seu espaço de objetivos e no espaço de variáveis (à direita):
Da mesma forma que o conjunto Pareto ótimo, podem existir fronteiras de Pareto locais.
Preservar as soluções não dominadas
encontradas ao longo da busca;
Progredir continuamente em direção à
Fronteira de Pareto;
Manter a diversidadede de soluções tanto
no espaço de objetivos (fronteira de
Pareto) quanto no espaço de variáveis;
Realizar as metas anteriores com a maior
eficiência computacional possível.
Otimização com simples objetivo.
– Uma única solução.
– Trabalham unicamente no espaço de variáveis
Otimização com múltiplos objetivos.
– Múltiplas soluções.
– Trabalha com dois espaços (das variáveis e dos
objetivos)
– Preservar a diversidade na fronteira de Pareto
– Nenhuma delas é melhor do que as demais com
respeito a todos os objetivos.
Somatório de Pesos (Weighted Sum)
– Soma ponderada das funções objetivos
– Pode-se mostrar que a solução do problema na Equação pertence ao conjunto
Pareto-ótimo se os pesos são positivos para todos os objetivos. – Se um MOOP é convexo, qualquer solução Pareto-ótima pode ser encontrada
usando o método de somatório dos pesos
Somatório de Pesos (Weighted Sum)
– Dado que F é uma combinação linear dos
objetivos, obtém-se uma linha reta.
– Encontrar o mínimo valor da equação é
equivalente a achar uma linha de
contorno com um valor mínimo para F.
Somatório de Pesos (Weighted Sum)
Desvantagens:
– Dificuldade de encontrar pesos adequados.
– Não podem encontrar múltiplas soluções em uma
única rodada.
– A aplicação de vetores de pesos uniformemente distribuídos não garante um conjunto de soluções uniformemente distribuídas.
– No caso de um MOOP não convexo, este método não é capaz de determinar todas as soluções.
Método de restrições (Constraint)
– Considera-se qualquer objetivo, mantendo-se restritos os demais objetivos com valores definidos pelo usuário.
– Onde cada ‘Ԑm’ definida pelo usuário representa um limite máximo para o valor de fm.
Método de restrições
(Constraint)
– Escolhe-se f2 para ser
minimizado e mantém-se f1 (f1
≤ ε1).
– O mínimo para f2 depende da
escolha do Ԑ.
– O vetor Ԑ deve estar em uma região factível para cada objetivo.
Método de restrições (Constraint)
Desvantagens
– Resolve o problema do método do Somatório dos Pesos para
MOOP não convexos.
– Necessita que a escolha do vetor ε esteja em uma região factível
para cada objetivo.
– O uso de uma distribuição uniforme de ε não garante um conjunto
de soluções com a mesma distribuição.
– Várias iterações para determinar a fronteira de Pareto.
Programação de Metas (Goal Programming)
– Para cada objetivo é escolhido pelo usuário um valor meta z. Então, o
problema é formulado para encontrar uma solução cujo valor em f seja igual a
z:
– Cada meta é convertida em uma restrição de igualdade.
– Minimizar todos os desvios em relação as metas.
Programação de metas com pesos
– Formula-se uma função somando os desvios para cada um dos Nobj objetivos.
– αm e βm são os pesos dos desvios positivo e negativo para o j-ésimo objetivo
– zm é a meta para a função fm e Sfact é o espaço de decisão factível.
Programação de metas com pesos
– As soluções obtidas por este método dependem consideravelmente da escolha dos valores para αm e βm.
– Possui dificuldades similares ao método do somatório dos pesos
Programação de metas lexicográficas
– Metas são organizadas em vários níveis de prioridade.
– Resolvem-se sequencialmente vários problemas de programação de metas.
Espaço de objetivos para as funções f1 e f2.
Programação de Metas Min-Max
– Minimiza-se o máximo desvio em relação às metas.
– Onde δ é o desvio máximo para qualquer meta.
– φm e ηm são os desvios positivos e negativos para cada objetivo.
– αm e βm representam os pesos para cada desvio.
– Requer também a escolha dos pesos αm e βm .
Vantagens
– Provas de convergências que garantem encontrar soluções Pareto-ótimas.
– Possuem aplicações nos mais diferentes campos de engenharia e de outras
ciências.
Desvantagens
– A escolha dos parâmetros adicionais introduzidos por cada técnica afeta
diretamente os resultados obtidos.
– Para encontrar N soluções Pareto-ótimas, tem- se que solucionar no mínimo N
problemas de objetivos simples .
– Alguns métodos não garantem achar soluções ao longo de toda a Fronteira de
Pareto.
Características Básicas
– São flexíveis, de fácil implementação e têm a capacidade de encontrar
soluções de boa qualidade em problemas complexos.
– Trabalha com várias soluções simultaneamente usando o conceito de
dominância de Pareto.
– Não introduzem informações adicionais no problema.
– Possibilita escapar de ótimos locais.
– Um conjunto diversificado de soluções pode ser encontrado apenas em
uma execução do MOEA.
Os modelos de MOEA são comumente classificados em dois tipos:
– Não elitistas:
• Não utilizam alguma forma de elitismo nas suas iterações;
– Elitista:
• Alguns modelos usam uma população externa na qual são mantidas as
soluções não dominadas encontradas até aquele momento de sua execução;
• Outros métodos como NSGA-II (Non-Dominated Sorting Genetic Algorithm-II )
combinam a população atual com a população posterior para preservar ambas
as soluções.
– O elitismo melhora as soluções encontradas por um modelo MOEA.
“Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será sua chance
de sobreviver e gerar descendentes.”
(DARWIN, 1859)
Introdução
– Mecanismos de busca baseados nos processos de seleção natural da luta
pela vida e da genética de populações.
– Dada uma população inicial de soluções, esta evolui até convergir para
uma solução, por meio da aplicação de operadores genéticos de seleção,
cruzamento e mutação.
– Permitem ainda que estes sejam acoplados a qualquer outro método
matemático que auxilie no processo de busca.
Ideia básica
– Começar com um conjunto de soluções (representado por cromossomos)
chamado população
– Soluções de uma população são escolhidas e usadas para formar uma
nova população (reprodução)
– Espera-se que a nova população seja “melhor” que a anterior.
– Soluções que são escolhidas para formar novas soluções (descendentes)
são escolhidas de acordo com uma função de adaptação (função objetiva
– custo)
– O processo é repetido até que uma condição seja satisfeita
Indivíduo (simples membro da população).
Cromossomo e Genoma:
Coleção de genes
Estrutura de dados que codifica a solução de uma problema.
Genótipo
Na biologia, representa a composição genética do organismo. Nos AGs, representa a informação contida no cromossomo.
Fenótipo:
Objeto ou estrutura construída a partir das informações do genótipo.
É o cromossomo decodificado.
Exemplo: se o cromossomo codifica as dimensões de um edifício, então o fenótipo é o edifício construído.
Gene:
Codifica um simples parâmetro do problema
Alelos:
Valores que o gene pode assumir.
Ex.: um gene representando a cor de um objeto pode ter alelos como azul, preto, verde etc...
O critério de parada é alcançado
quando:
Um número de gerações
previamente definido é alcançado;
Quando uma solução
suficientemente boa é encontrada
ou;
Quando o sistema não consegue
mais evoluir.
Algoritmos Genéticos - Capítulo 10 35
Representação cromossomial é fundamental para um algoritmo genético;
– É a maneira básica de traduzir a informação do nosso problema em uma maneira viável de tratamento pelo computador ;
– É completamente arbitrária;
– Maioria dos pesquisadores usa representação binária pois ela é a mais simples e tem sido a mais freqüentemente usada
Algoritmos Genéticos - Capítulo 10 36
Representação cromossomial
Representação Binária
– Tem-se indivíduos (genótipos) de uma população. Estes indivíduos
também são chamados de cromossomos.
– A mais simples e comumente utilizada é a representação binária
Algoritmos Genéticos - Capítulo 10 38
Representação binária
– Simples de criar e manipular
– Produz bons resultados
– Facilita aplicações de operadores
– Fácil decodificação numérica ( inteiro,real )
– Facilita a demonstração de teoremas
– Porém, nem sempre é adequada
Algoritmos Genéticos - Capítulo 10 39
Representação binária tem dificuldades com múltiplas dimensões de
variáveis contínuas, especialmente quando uma grande precisão é requerida.
– Grande número de bits será necessário para atingir tal precisão;
– Cromossomos se tornarão extremamente grandes, dificultando a operação do GA;
– Há uma discretização inerente nos valores reais quando cromossomos binários são usados;
• Podemos ignorá-la quando usamos bits suficientes;
• Esta quantidade pode fazer com que nossos cromossomos se tornem grandes demais;
Representação Contínua
Para otimização de parâmetros contínuos a representação binária não é adequada – Muitos bits para obter boa precisão numérica
Parâmetros numéricos podem ser codificados diretamente nos cromossomos – Ex.: S1 = 0,637197
Deve-se implementar operadores genéticos de cruzamento e mutação adequados à essa representação.
0,2
0,4
0,6
0,8
1,0
0,0
-100 -75 -50 -25 0 25 50 10075
f x yx y
x y( , ) ,
sen ,
, ,
0 5
0 5
10 0 001
2 22
2 22
FUNÇÃO OBJETIVO :
Exemplo extraído de Davis (1991)
Cromossomo Binário:
Cromossomo Real: (-17,85; 11,04)
Representação do ponto x = -17,85 e y = 11,04
01101001001001101000001000111000100001110010
0110100100100110100000 1000111000100001110010
1722784 2328690
-17,85 11,04
x y
As vantagens da codificação real em relação à codificação binária:
– A possibilidade de trabalhar com grandes domínios para as variáveis;
– A capacidade de explorar a “gradualidade” da funções com variáveis
contínuas.;
– A capacidade de ajuste local das soluções;
– A representação das soluções é muito próxima da formulação natural de
muitos problemas, ou seja, não há diferença entre o genótipo
(codificação) e o fenótipo ( espaço de busca) ; e
– Os processos de codificação/decodificação, necessários nos alfabetos
binários, são evitados, aumentando a velocidade dos AG ’s.
Parâmetros Genéticos
– Tamanho da população • Número de cromossomos da população.
– Taxa de cruzamento • Rapidez com que novas estruturas são introduzidas na
população.
– Taxa de mutação • Determinar a probabilidade de ocorrer mutação.
– Intervalo de geração • Percentagem da população a ser substituída na geração
seguinte.
Função de Avaliação – Também chamada de função de custo
– Calcula um valor numérico que reflete quão bons os parâmetros representados no cromossomo resolvem o problema.
– Usa todos os valores armazenados no cromossomo (os parâmetros) e retorna um valor numérico, cujo significado é uma métrica da qualidade da solução obtida usando-se aqueles parâmetros.
– A função de avaliação deve ser tal que se o cromossomo c1 representa uma solução melhor do que o cromossomo c2, então a avaliação de c1 deve ser maior do que a avaliação de c2.
Operadores genéticos
– Seleção Natural
– Manipulação Genética por Mutação
– Manipulação Genética por Reprodução
Operadores genéticos (a) (b)
Pai 1
Pai 2
Selecionamos um
ponto de corte
Pai 1
Pai 2
Depois do
operador de
crossover
Filho 1
Filho 2
Depois do
operador de mutação
Filho 1
Filho 2 Gen alterado
pela mutação
(c) (d)
Seleção
– O método de seleção de pais deve simular o mecanismo de seleção natural:
• Pais mais capazes geram mais filhos;
• Pais menos aptos também podem gerar descendentes.
– Temos que privilegiar os indivíduos com função de avaliação alta, sem desprezar completamente aqueles indivíduos com função de avaliação extremamente baixa;
– Até indivíduos com péssima avaliação podem ter características genéticas que sejam favoráveis à criação de um indivíduo ótimo;
– Estas características podem não estar presentes em nenhum outro cromossomo.
Seleção por Torneio – Utiliza sucessivas disputas para realizar a seleção.
– Para selecionar k indivíduos, realiza k disputas, cada disputa envolvendo n indivíduos escolhidos ao acaso.
– O indivíduo de maior aptidão na disputa é selecionado.
– Não é proporcional a aptidão.
Os indivíduos são selecionados para os torneios com igual probabilidade.
O torneio é vencido pelo indivíduo com maior aptidão
• Aumentando o tamanho k do torneio acarreta: • Aumento da pressão de seleção.
• Risco de convergência prematura.
• Por isso, o torneio binário é o mais utilizado.
Seleção por torneio com probabilidades
(Reduz ainda mais a pressão de seleção)
O melhor indivíduo do torneio é selecionado com probabilidade p >
0,5
O segundo melhor é selecionado com probabilidade p(1-p)
O terceiro é selecionado com probabilidade p(1-p)2
e assim por diante...
Operadores Genéticos
– A etapa de seleção, gera uma população intermediária de potenciais cromossomos pais.
– Na nova geração, escolhe-se aleatoriamente dois pais para aplicação de operadores genéticos (crossover e mutação).
– Produção de filhos é feita até completar o tamanho da população desejada.
Cruzamento – Também chamado de reprodução ou crossover
– Combina as informações genéticas de dois indivíduos (pais) para gerar novos indivíduos (filhos)
– Versões mais comuns criam sempre dois filhos para cada operação
Crossover´s convencionais
n-Pontos, uniforme
Não criam novas informações (i.e. novos números reais).
Crossover´s aritméticos
Operadores que realizam operações aritméticas entre os parâmetros.
Baseados da direção (usam derivadas)
Cruzamento – Consiste em gerar dois cromossomos filhos (c1 e c2) a partir de dois
cromossomos pais (p1 e p2), usando a expressão: • Pais: ⟨x1,…,xn ⟩ e ⟨y1,…,yn⟩
• Filho1 é:
– O inverso para o outro filho com α = 0.5
0 1 1 0 0 0 1
0 1 0 0 0 0 1
Operador de Mutação – Operador randômico de manipulação
– Introduz e mantém a variedade genética da população
– Garante a possibilidade de se alcançar qualquer ponto do espaço de busca
– Contorna mínimos locais
Substitui o gene por um número aleatório de uma distribuição gaussiana.
onde N(pi,) é uma distribuição normal com média pi e desvio padrão .
Pode-se diminuir o valor de , à medida que aumenta a número de gerações (imitando a redução de temperatura no Recozimento Simulado).
contrário caso
se ),,(
i
i
ip
jipNc
Espaço de busca
* - Representação de um indivíduo
Elitismo:
– Mantém as melhores soluções encontradas previamente
nas gerações seguintes.
– A melhor solução não se deteriora nas gerações seguintes.
• Copiar diretamente as n% das soluções da população atual à
população seguinte.
• Criar a população seguinte a partir da população atual usando os
operadores genéticos usuais, e escolher as melhores N soluções de
ambas populações.
Niching:
– Métodos de nichos (niching) estendem os algoritmos evolutivos para
domínios nos quais é requerida a identificação e manutenção de
múltiplas soluções.
– Os métodos de niching podem ser divididos em dois grandes grupos:
• O método sharing funciona através da redução do fitness de cada
indivíduo da população por uma quantidade proporcional a quantidade
de indivíduos similares.
• O método de crowding insere novos indivíduos na população
substituindo indivíduos similares.
Passos para Implementar um Algoritmo Genético:
1. Definir uma representação a ser utilizada para indivíduo de maneira
que uma solução completa possa ser representada por ele;
2. Definir as estratégias de substituição, seleção, cruzamento e
mutação;
3. Definir a função de aptidão;
4. Ajustar os seguintes parâmetros: tamanho da população,
probabilidade de cruzamento,
5. Probabilidade da mutação e número de gerações.
Diferenças entre os Algoritmos Genéticos e os Métodos de Otimização Tradicionais :
– Os AGs trabalham com uma população de soluções em cada iteração
ao invés de uma única solução.
– Os AG s não precisam de informação adicional a não ser o valor de aptidão
das soluções.
– Os AGs empregam regras probabilísticas para guiar a sua busca.
Modelos de MOEAs
– 1° implementação de um MOEA foi proposta por Schaffer em 1985.
– Schaffer modificou os AGs para avaliar cada objetivo separadamente,
foi denominado VEGA (Vector Evaluated Genetic Algorithm).
– Goldberg [Goldberg, 1989] criou um procedimento para ordenação de
soluções baseado no conceito de dominância e um método de
compartilhamento .
– Com base nas ideias inicias propostas por Goldberg foram propostas
vários modelos de MOEAs.
Diferentes Modelos MOEAs
– O algoritmo MOGA [Fonseca e
Fleming, 1993] foi o prime iro a dar
ênfase ao conceito de dominância e
à diversidade das soluções.
– A cada solução é associado um valor
de ranking que é igual ao número de
soluções ni que a dominam mais um.
MOGA (Multi-Objective Genetic Algorithm)
– Distribuir as soluções sob diferentes
regiões ou nichos no espaço de busca.
– Para cada solução i é calculado um valor
de contador de nicho nci.
– Soluções que residem em um nicho
menos ocupado terão melhor aptidão de
compartilhamento.
Compartilhamento de Aptidão no MOGA
Compartilhamento de Aptidão no MOGA
MOGA: Vantagens e Desvantagens
MOGA: Vantagens e Desvantagens
– Simplicidade no cálculo do valor de aptidão.
– Tem desempenho melhor quando comparados com outros algoritmos não elitistas e é fácil de implementar.
– O valor ‘ri’ não fornece os mesmos valores para soluções que se
encontram na mesma frente, exceto a primeira.
– Sensível à forma da Fronteira de Pareto e à densidade das soluções no
espaço de busca [Deb, 2001].
– O cálculo do compartilhamento não garante que as soluções com valor
‘ri’ alto terão uma pior aptidão que soluções com ‘ri’ baixo.
NPGA (Niched Pareto Genetic Algorithm)
– Proposto por Horn e colaboradores [Horn e t al., 1994], é um algoritmo genético
geracional com sobreposição.
– Utiliza um método de seleção por torneio denominado de Torneio de Pareto, baseado
no conceito de dominância.
– Duas soluções i e j são escolhidas aleatoriamente da população P. Estas soluções são comparadas com um subconjunto T de P de tamanho tdom < |P|.
1. Se a solução i domina o subconjunto T e a solução j é dominada por algum elemento de T, a solução i é a vencedora.
2. Caso contrário, se acontecer de ambas soluções dominarem T, ou que ao menos uma solução em T domine i e j, calcula-se o contador de nicho para escolher a solução vencedora.
NPGA (Niched Pareto Genetic Algorithm)
NPGA: Vantagens e Desvantagens
– Não precisa de um método para calcular o valor de aptidão das soluções.
– Uso do operador de seleção por torneio torna o algoritmo computacionalmente eficiente.
– O NPGA usa dois parâmetros adicionais share e tdom. – Quando o parâmetro tdom é muito pequeno, as comparações de
dominância podem levar ao não destacamento das soluções não dominadas.
– Porém, quando tdom é muito grande, aumenta-se a complexidade
computacional do algoritmo NPGA.
Non-Dominated Sorting Genetic Algorithm (NSGA)
– Ideia • Utiliza um esquema de seleção baseada em ordenamento para privilegiar
soluções não-dominadas.
• Método voltado para a criação de nichos para manter a diversidade.
– Procedimento • Determinação de fronteiras não dominadas.
• Para manter a diversidade na população as soluções não-dominadas compartilham os seus valores de aptidão segundo suas distâncias Euclidianas.
• Divide-se o valor da aptidão de cada indivíduo pelo contador de nichos que é proporcional ao número de vizinhos ao seu redor.
NSGA: Vantagens e Desvantagens
– Alta complexidade computacional do processo de ordenamento por não dominância;
– Ausência de elitismo que prejudicava o funcionamento do método;
– Necessidade de especificar o parâmetro de compartilhamento;
– Praticamente qualquer número de objetivos pode ser usado para os dois tipos de problemas: maximização ou minimização.
Non-Dominated Sorting Genetic Algorithm – II (NSGA-II)
– Usa um mecanismo de elitismo para preservar e usar
previamente as melhores soluções encontradas em gerações
subsequentes;
– Usa o conceito de ordenamento por não dominância em AGs;
– Usa o operador de seleção por torneio de multidão para
preservar a diversidade entre as soluções não dominadas nos
estágios de execução posteriores.
Ordenação por dominância
– A fronteira F1 contêm as soluções não-
dominadas de todo o conjunto M .
– A fronteira F2 possui as soluções não-
dominadas de M −F1;
– F3 contêm as soluções de M −(F1 ∪F2)
e assim sucessivamente.
Para cada solução i contida em P são calculados dois
valores: 1. ndi , o número de soluções que dominam a
solução i ;
2. Ui, o conjunto de soluções que são dominadas
pela solução i.
Percorre o conjunto de soluções dominadas Ui para cada
solução i de F1. O contador ndj de cada solução j em Ui é
diminuído em 1. Se ndj = 0, então a solução j pertence a
próxima fronteira, neste caso, F2.
Esquema do modelo NSGA-II
Operador de comparação de multidão
Um a solução i é considerada ganhadora em um torneio
contra uma solução j, se:
– A solução i possui um melhor nível de não dominância;
– Se ambas soluções estão no mesmo nível, mas i tem uma
distância de multidão maior ,
NSGA: Vantagens e Desvantagens
– O cálculo da distância de multidão não requer do parâmetro σshare , como no MOGA.
– Se o conjunto F1 tem um tamanho maior que N, o processo de escolher apenas N soluções usando a distância de multidão faz que sejam perdidas soluções.
– Dado um conjunto de soluções de uma fronteira Fi , depois de aplicar o algoritmo de corte para NSGA-II, elimina-se uma solução Pareto- ótima e se mantém a solução não dominada (mas não Pareto-ótima).
Está é uma situação onde o algoritmo de corte para o NSGA-II erra!
Strength Pareto Evolutionary Algorithm (SPEA2)
– Utiliza elitismo através de população externa E onde são guardadas as
soluções não dominadas.
– A população E tem tamanho fixo de N fornecido como parâmetro.
– Cria uma população aleatória P0 e uma população externa E
inicialmente vazia.
– Calcula-se os valores de aptidão para as soluções em R = P ∪ E.
Esquema para o cálculo de aptidão no algoritmo SPEA2
Soluções não dominadas terão Fi < 1, e as demais soluções Fi ≥ 1.
Pode falhar quando existem muitas soluções não dominadas.
SPEA2 usa uma informação de densidade, baseada no método de k-vizinhos.
Algoritmo de Corte em SPEA2
– Depois disto, existe m 3 possíveis situações: 1. |En+1| = N, e não se fazem modificações sobre |Et+1|.
2. |En+1| < N, então ordena-se R por Fi e copia- se as primeiras N−|En+1| soluções i de Q tal que Fi ≥ 1.
3. |En+1| > N, neste caso se utiliza um algoritmo de corte sobre |En+1|.
– Finalmente, se realiza o processo de seleção por torneio, cruzamento e mutação sobre En+1 para gerar a nova população Pn+1.
Algoritmo de Corte em SPEA2
– Em cada iteração escolhe-se uma
solução tal que a sua distância para o
seu vizinho mais próximo seja a
menor possível.
– No caso de empate, se calcula a
segunda menor distância, e assim
por diante.
– Formalmente, em cada iteração uma
solução i é eliminada tal que i ≤d j
para todas as j ∈ En+1 .
SPEA2: Vantagens e Desvantagens
– Introduz um método baseado na dominância de Pareto que não requer
uma ordenação por não dominância, como no NSGA-II.
– O uso de uma população externa garante que as soluções Pareto-ótimas
sejam conservadas para a geração seguinte.
– Apresenta casos onde uma solução não Pareto-ótima, mas não dominada
até o momento, seja preferida a uma solução Pareto-ótima após a
aplicação do algoritmos de corte;
– SPEA2 introduz um parâmetro adicional, o tamanho da população externa
E.
Comparar experimentalmente
diferentes métodos de
otimização envolve a noção
de performance.
Metas de convergência e
diversidade podem ser
conflitantes uma com a outra.
Neste caso, um algoritmo não é superior ao outro com
relação aos critérios de convergência e diversidade.
A comparação dos algoritmos
dependerá fortemente da métrica
empregada.
Métricas de desempenho
classificadas em dois grupos:
– Métricas para medir a convergência;
– Métricas de diversidade.
Métricas de Convergência
– Comparam o soluções P encontradas ao conjunto soluções Pareto-ótimas do problema, denotado por P′:
• Taxa de Erro;
• Distância Geracional;
• Métrica de Cobertura.
Taxa de Erro
– Calcula o número de soluções em P que não estão em P’
– Assim, quanto menor for o valor de ER, melhor será a convergência.
– Se ER = 0, significa que P ⊆ P′.
Distância Geracional
– Representa a distância Euclidiana média (no espaço de objetivos) entre as soluções de P e P’: GD (do inglês Generational Distance).
– Quanto mais próximo de zero for o valor GD, melhor será a convergência de P.
Métrica de Cobertura
– Dados dois conjuntos de soluções P e Q, esta métrica calcula a proporção de soluções de Q que são fracamente dominadas pelas soluções de P.
– Quando SC(P,Q) = 1 todas as soluções de Q são dominadas por soluções de P.
– Se SC(P,Q) = 0, então nenhuma solução de Q é fracamente dominada pelas soluções em P.
Métricas de Diversidade
– Calculam a distribuição das soluções de um conjunto P:
• Espaçamento;
• Número de nichos;
• Espalhamento.
Espaçamento
– Calcula o desvio padrão entre as distâncias de soluções consecutivas (no espaço de objetivos) do conjunto P (Deb, 2001);
– neardisti representa a distância (no espaço de objetivos) entre a solução i e a solução mais próxima dela no conjunto P;
– Quanto menor for o valor da métrica SP , melhor distribuídas estarão as soluções do conjunto P.
Número de nichos
– Calcula o número de nichos dentro de um conjunto de soluções P.
– onde distij a distância entre as soluções i e j do conjunto P;
– pode ser calculada no espaço de variáveis ou de objetivos;
– NC = número de soluções cuja distância entre elas é maior que o parâmetro σ;
– Quanto maior a quantidade de nichos formados em P, melhor distribuídas estão as soluções em tal conjunto.
Métrica de Cobertura
– A métrica de espalhamento avalia: • A dispersão das soluções no conjunto P ao longo da fronteira de Pareto PF;
• A distribuição entre soluções contíguas (no espaço de objetivos) de P.
– O valor desta métrica, denotada como SPREAD é dado:
– onde extdistm representa a distância Euclidiana entre as soluções extremas na m-ésima função objetivo dos conjuntos P e P′.
Conclusão
– Foram apresentados os conceitos principais sobre Algoritmos
Genéticos (AGs) como técnica de otimização;
– As características dos AGs permitem seu emprego em problemas de
otimização Multi-Objetivo;
– Foram detalhados os principais modelos de AGs para estes problemas;
– Finalmente, algumas métricas para avaliar o desempenho dos AGs
foram mostradas.
