9/29/2009

1

Tópicos Avançados em Computação Evolucionária

Computação Natural

Gisele L. Pappa

Tópicos

• Algoritmos Multiobjetivo

• Algoritmos Paralelos

Otimização Multi-objetiva

• Grande parte dos problemas requer a otimização de dois ou mais objetivos

– Ex: minimizar o custo de um produto e ao mesmo tempo maximizar a qualidade do produto

• Abordagem convencional para tratar desse problema:

– Combinar os objetivos em uma fórmula, atribuindo pesos a diferentes objetivos

• Fitness = 2/3 Objective_1 + 1/3 Objective_2

(assumindo que os objetivos estão normalizados para retornar valores dentro do mesmo intervalo, como 0..1)

Otimização Multi-objetiva

• Desvantagens da abordagem convencional

– Objetivos diferentes são normalmente não-comensuráveis, isto é, eles medem aspectos diferentes da qualidade de uma solução, que não deveriam ser adicionados ou subtraídos em uma mesma fórmula

– Ela retorna uma solução, enquanto em problemas MO pode ser conveniente retornar um conjunto de soluções, representando diferentes configurações (trade-offs) entre os objetivos

• Solução:Algoritmos Evolucionários Multi-Objetivos

– Baseados no conceito de dominância de Pareto

– Retornam um conjunto de soluções não-dominadas

Otimização Multi-objetiva

• Exemplo de dominância de Pareto

– Minimizar o custo de produção e o número de bugs encontrados em um programa

Soluções A, B, C são não-dominadas

Solução X é ruim, pois é dominada por A

Solução Y é ruim, pois é dominada por B

A

B

C

X

Y

Custo de Produção

Nú

mer

o d

e b

ugs

Otimização Multi-objetiva• Definição de dominância de Pareto:

– Um solução S1 domina uma solução S2 se e apenas se:• S1 não é pior que S2 em nenhum objetivo

• S1 é obrigatoriamente melhor que S2 com respeito a pelo menos um objetivo

• O conjunto de soluções não-dominadas é chamado fronte de Pareto

• A cada geração, o conjunto de indivíduos não-dominados é utilizado como uma estimativa do verdadeiro (e desconhecido) fronte de Pareto

• O Alg. Evolucionário deve retornar ao usuário o melhor fronte de Pareto estimado, isto é, um conjunto de soluções não-dominadas

9/29/2009

2

Otimização Multi-objetiva

Fórmula combinando MO baseada em Paretoobjetivos

Usuário escolhe pesos para cada objetivo

Algoritmo busca por uma única solução ótima

Busca por um conjuntode soluções não-dominadas

Retorna uma únicasolução ao usuário

Retorna soluções não-dominadasao usuário

Usuário escolhe a soluçãode seu interesse

Algoritmos Evolucionários Multiobjetivos

• Deb e Coello

– NSGA

– SPEA

• Diversos desafio de pesquisa da área

– Tomada de decisão

– Retorna um conjunto de soluções, qual delas eu devo usar?

SPEA (Strength Pareto Evolutionary Algorithm)

• Além de uma população, trabalha com um conjunto externo de indivíduos

• Salva todos os indivíduos não-dominados únicos no conjunto externo

• O conjunto externo tem um tamanho máximo• Se o número de indivíduos não dominados é

maior que o tamanho máximo do arquivo, uma técnica de clusterização é utilizada para preservar as características

• Calcula a fitness para elementos da população e do conjunto externo

SPEA

• Cada indivíduo i no conjunto externo recebe um valor de força S(i) no intervalo de [0;1), que também representa o valor da fitness.

• S(i) é o número de indivíduos da população j que são dominados por ou iguais a i em relação aos objetivos, divididos pelo número de indivíduos da população +1.

• A fitness de um indivíduo j da população é calculado através da soma dos valores S(i) de todos os membros i do conjunto externo que dominam ou são iguais a j mais um

SPEA

• Fase de seleção (torneio de tamanho 2)– Selecionados da união da população e do

conjunto externo

• O objetivo aqui é minimizar a fitness

• Indivíduos no conjunto externos tem maior chance de ser selecionados do que membros da população

• Cruzamento e mutação criam uma nova população

SPEA

• Problemas

– Fitness – se existe apenas um indivíduo na população externa, todos os indivíduos da população tem o mesmo valor de fitness

– Tamanho máximo da população externa

• Apesar de um método de clusterização preservar indivíduos diferentes, pode perder indivíduos significativos

9/29/2009

3

SPEA-2

• Muda a maneira como a fitness é calculada para que essa utilize não apenas os indivíduos dominados, mas também os indivíduos que

• Cada indivíduo i na população e no conjunto externo recebe um valor S(i), que representao número de indivíduos dominados por i tantona população quanto no conjunto externo de dados.

SPEA-2

• “Raw” Fitness

• Distância entre indivíduos (informação sobre densidade)

• Fitness

SPEA vs SPEA-2

Fig: Valores de fitness do SPEA (esquerda) versus SPEA-2 (direita) em um problema de maximização de dois objetivos f1 e f2

Algoritmos Paralelos

• 3 abordagens principais

– Paralelização global

– Paralelização em alto nível de abstração

• Modelo da ilha (island model)

– Paralelização em baixo nível de abstração

Paralelização Global

• O algoritmo genético é executado em uma máquina e a fitness distribuída em diversas máquinas.

• Eficiente apenas quando o custo maior do algoritmo está no cálculo da fitness.

Paralelização em Alto Nível

• Mais utilizada

• População é dividida em múltiplas sub-populações

• Evolução ocorre de maneira isolada, com algumas fases de migração

• Qualidade da performance é influenciada pelo número e tamanho de demes (sub-populações) disponíveis, além do material genético trocado durante as fases de migração

9/29/2009

4

Paralelização em Baixo Nível

• Utiliza muitas sub-populações com poucos elementos

• Apropriada para estruturas de supercomputadores

• Área de pesquisa sendo explorada é a de criação de modelos híbridos

– Combinam paralelização em alto e baixo níveis

Migração

• Um dos fatores determinantes no sucesso de algoritmos evolucionários paralelos

• 3 problemas– Quando migrar– Quem migrar– Quantos migrar

• Migração normalmente ocorre em intervalos fixos de tempo

• Maioria dos artigos usa uma taxa de migração de 5% a 20% da população– Depende do problema

Outros detalhes

• Inicialização com heurísticas

• Crossover e Mutação são mutuamente exclusivos?– Não, algoritmos genéticos clássicos aplicavam

crossover seguidos de mutação (de acordo com as probabilidade definidas pelo usuário)

• Computação evolucionária interativa– Artigo para leitura

• A broad and narrow approach to interactive Evolutionary design—An aircraft design example, Oliver Bandte , Applied Soft Computing, 2009, 9, 448-455

Leitura Recomendada

• SPEA2: Improving the Strength Pareto Evolutionary

Algorithm For Multiobjective Optimization, E. Zitzlerand K. Giannakoglou and D. Tsahalis and J. Periauxand K. Papailiou and T. Fogarty , 2002.