Como executar algoritmos evolucion rios Otimiza o Natural ...gabriel/cpe723/Aula6_Rafael_WorkingWithGAs.pdf · Tipos de problemas: Projeto, Repetitivos, Controle on-line; Exemplo

Introducao Medidas de desempenho Problemas de teste para comparacoes experimentais Aplicacoes-exemplo

Como executar algoritmos evolucionarios OtimizacaoNatural - Algoritmos Geneticos

Rafael Lima de Carvalho

2 de maio de 2012

1 / 52

Como executar algoritmos evolucionarios Otimizacao Natural - Algoritmos Geneticos


Agenda

1 Introducao

2 Medidas de desempenho

3 Problemas de teste para comparacoes experimentais

4 Aplicacoes-exemplo

2 / 52



Objetivo desta aula

Objetivo

Discutir tipos de problemas para resolucao atraves de AEs eapresentar meios de avaliar a qualidade das solucoes alcancadascom AEs.

3 / 52



Revisao - Problemas de otimizacao

3-SAT

Data um expressao booleana na forma conjuntiva normal C usandoo conjunto U de variaveis, o problema consiste em determinar umacombinacao de valores para U que torne C verdadeira. Se existirao menos uma combinacao, significa que o problema esatisfatıvel. O 3-SAT e um subconjunto onde cada clausula ecomposta por exatamente tres elementos de U.

Ex.: U = {A,B ,C ,D}, C = (A ∨ B ∨ C ) ∧ (A ∨ B ∨ ¬D)

4 / 52



Revisao - Problemas de otimizacao

Timetabling

O problema de agendamento consiste em encontrar a melhorcombinacao professor/sala/horario segundo um conjunto decriterios (restricoes de dia para professores, disponibilidade desalas, minimizacao de janelas vagas, etc);

5 / 52



O que se deseja que um AE faca?

Resposta

Que resolva meuproblema!

6 / 52




Tipos de problemas: Projeto, Repetitivos, Controle on-line;

Exemplo - Projeto de antenas

Qualidade da solucao mais importanteque o desempenho do algoritmo;

Geralmente nao generalizado: tornando oAE quase unico para o projeto.

7 / 52





Exemplo - Empresa de logıstica

Problema:

Varios destinos, motoristas, caminhoes...Cada motorista + caminhao: uma instanciado TSPa;+ restricoes de toda empresa + criterios deotimizacao → problema complexo.

Requisitos do EA:

Boas solucoes rapidamente;Tratar diferentes instancias do problema;Minimizar a variancia das solucoes;

aTraveling Salesman Problem

8 / 52





Vistos como um umcaso especial deproblemas repetitivos;

Restricoes rigorosasem relacao ao tempo!

Exemplo: controle desemaforos!

Semaforo

Problema:

Calcular o numero de aberturas dossemaforos de maneira a maximizar avazao de veıculos;

Projeto AE:

Usando simulacoes: otimizar o projetodo controlador;Colocar o AE no proprio controlador!

9 / 52



Contexto da pesquisa academica

As consideracoes anteriores aplicam-se a problemas orientados aaplicacao;

A academia tem sua propria dinamica;

Estudo dos comportamentos complexos que sao interessantes por si;

Teorias podem produzir ideias sobre evolucao biologica “real”;

Objetivo da pesquisa: encontrar melhores AEs;

10 / 52



Contexto da pesquisa academica

Alguns objetivos para experimentacao na academia:

Obter uma boa solucao para um problema complexo de otimizacao;Mostrar que AG e aplicavel em algum domıno (novo);Mostrar que alguma caracterıstica nova e melhor que algumbenchmark de EA;Mostrar como um AG se comporta conforme aumenta acomplexidade do problema;...

11 / 52



Medidas de desempenho - introducao

Avaliacao de qualidade: comparacoes experimentais entre EAs ×EA, ou EA × Algoritmo comum;

Tunning de parametros: trabalho experimental comparando-sediferentes variantes do algoritmo;

Medidas comuns para avaliacao de algoritmos:

Numero de linhas de codigo;Legibilidade;

Contexto de EAs:

Medidas de desempenho: estatısticas por natureza;Necessita de experimentos → dados experimentais;

12 / 52



Medidas de desempenho

Discussao das medidas estabelecidas:

Taxa de Sucesso;

Efetividade (qualidade da solucao);

Eficiencia (velocidade);

Medidas:

Success Rate (SR);

Mean Best Fitness (MBF);

Average Number of Evaluations to a Solution (AES);

13 / 52



Success Rate

Cenario:

Problemas onde a solucao otima pode ser reconhecida;

Ou ∃ criterio definido para a qualidade da solucao;

Criterio de sucesso: encontrar uma solucao com a qualidade exigida;

Success Rate: porcentagem de execucoes que terminaram emsucesso.

14 / 52



Success Rate - Discussao

Pergunta

Em problemas onde as solucoes otimas nao sao conhecidas, epossivel usar SR?

15 / 52



Success Rate - Discussao

Pergunta

Em problemas onde as solucoes otimas nao sao conhecidas, epossivel usar SR?

Exemplo:

University Timetabling Problem;

Benchmark: o do ultimo ano ou algum feito a mao;

Objetivo: timetable beating the benchmark by 10%;

Criterio de sucesso pratico:

O otimo teorico e conhecido mas o usuario nao requer este otimo;Solucao e boa se possui um erro menor que ǫ > 0;

15 / 52



Mean Best Fitness - MBF

EA usando uma medida de fitness explıcita (excluindo aplicacoes daarte evolucionaria);

Best Fitness → fitness do melhor indivıduo da terminacao;

MBF e a media desses valores de best fitness sobre todas asexecucoes;

Algumas aplicacoes: e interessante guardar o melhor e pior,calculado sobre um numero de execucoes;

16 / 52



Medidas SR e MBF - Discussao

NOTA: SR pode nao serdefinido para algumasaplicacoes;

MBF e sempre uma medidavalida;

Cenarios:

↑MBF e ↓SR;↓MBF e ↑SR;

17 / 52






Cenarios:


↑MBF e ↓SR

Bom aproximador

Indicadores: aumentar onumero de execucoes;

Ex. ambiente desejavel:timetabling problem.

17 / 52






Cenarios:


↓MBF e ↑SR

Algoritmo Murphy: se daerrado, da muito errado!

Indicadores: aquelas poucasexecucoes que terminamsem um otimo, terminamem um disastre!

Ex. ambiente desejavel:3-SAT problem.

Fitness measure: numerode clausulas insatisfeitas;

17 / 52




Best-ever fitness

Problemas de projeto: omelhor de todos e umamedida mais adequada doque o MBF;

Requerimento: uma melhorsolucao;

Worst-ever fitness

Problemas repetitivos;

O pior de todos pode serestudado como cenario epode ajudar a estabelecergarantias estatisticas sobre aqualidade da solucao;

18 / 52



Medidas de Desempenho

Ambas SR e MBF assumemum limite de esforcocomputacional (conhecido a

priori);

Refletem a execucao dentrode uma quantidade fixa decomputacao;

Maximo muda → o rankingdos algoritmos muda;

Best fitn

ess fun

ction

na p

opu

lação

Time T1 T2

19 / 52



Medidas de Desempenho

Ambas SR e MBF assumemum limite de esforcocomputacional (conhecido a

priori);

Refletem a execucao dentrode uma quantidade fixa decomputacao;

Maximo muda → o rankingdos algoritmos muda;

Best fitn

ess fun

ction

na p

opu

lação

Time T1 T2

Resumo

Em resumo: SR e MBF sao medidas de desempenho para aefetividade de um algoritmo, indicando quao longe ele vai dentrode um limite computacional.

19 / 52



Average number of evaluations to a solution -AES

Abordagem complementar:

Identificar solucao candidata satisfatoria;Calcular a quantidade de computacao necessaria para alcanca-la;

Velocidade: qtde gasta de tempo de computacao ou tempo de CPU;

Problemas: dependente de hardware, SO, compilador, rede;

20 / 52




Contar o numero de pontos visitados no espaco de busca;

Mesmo que contar a quantidade de vezes que a funcao de fitness foiexecutada;

Este numero e contato para um numero de execucoes independentes(com sucesso): a media deste numero e o AES;

Numero medio de avaliacoes para terminacao;

Desvantagem: execucoes sem solucoes → param no maximo quepodem ir;Uma mistura de SR e AES → resultados sao difıceis de interpretar;

21 / 52




Combinando: porcentagem de sucesso e extensao da execucao →expressao da quantidade de processamento necessario para resolverum problema com uma dada probabilidade;

Parametros ajustaveis: tamanho da populacao (µ) e o numero degeracoes (i);

Y (µ, i) → Probabilidade que uma data execucao encontre umasolucao pela primeira vez na geracao i ;

P(µ, i) → probabilidade que uma dada geracao i ira conter umasolucao (encontrada em uma geracao j ≤ i);

1− (1− P(µ, i))R Probabilidade que a geracao i encontre umasolucao pelo menos uma vez em R execucoes;

22 / 52




O numero de execucoes independentes necessarias para encontraruma solucao pela geracao i com probabilidade z :

R(µ, i , z) = ⌈log(1 − z)

log(1 − P(µ, i))⌉

O numero de fitness evaluations I (µ, i , z) = µ.i .R(µ, i , z)

23 / 52




O uso de AES geralmente oferece uma comparacao justa em relacaoa velocidade do algoritmo;

Em alguns casos, seu uso pode levar a erros:

1 Trabalho oculto: operador de mutacao pode incorporar heurısticascujo custo fica invisıvel ao AES;

2 Avaliacoes: individuos que precisam de reparo → lentidao naavaliacao;

3 Quick Fitness1 avaliacoes mais rapidas que os demais passos doalgoritmo; AES nao refletira a velocidade do algoritmo;

1Usualmente 70-90% do tempo e gasto na avaliacao.

24 / 52




Outro problema: diferentesespacos de busca;

Passos de busca:

AE : cria e testa umanova solucao candidata;Constructive searchalgorithm: extende asolucao corrente;

Estudar a proporcionalidadede crescimento;

Avera

ge

num

ber

of S

tep

s for

a s

olu

tio

n

Problem size

25 / 52



Peak Versus Average Performance

No contexto de EA, A e melhor que B, se seu desempenho medio emelhor;

Aplicacoes interessadas na melhor solucao encontrada:

apos x execucoes;dentro de y horas/dias/semanas;

Tıpico em problemas de projeto;

Peak performance mais importante;

26 / 52




Cenario diferente para aplicacoes que permitem apenas umaexecucao e devem entrar a solucao;

Problemas de controle on-line;

Propriedades de um bom algoritmo:

Alto desempenho medio;Pequeno desvio padrao;Pequeno risco de perder a unica chance que temos;

Curiosidade: trabalhos experimentais de EC na academiageralmente comparam usando o desempenho medio dosalgoritmos. Mesmo tendo tempo para executar varias vezes.

27 / 52




A interpretacao das figuras usando as medias das medidas edependente dos objetivos da aplicacao;

Em EC e comum optar por algoritmos com alto MBF, ou baixo AES;

Esta ecolha deve ser dependente do tipo de problema;

Exemplo:

Considere o timetabling;Dois algoritmos sendo comparados sobre 50 execucoesindependentes;Medida usada: MBF;

28 / 52




Qual dos dois algoritmos e omelhor?

Nú

me

ro d

e e

xe

cu

çõ

es f

ina

liza

da

s

co

m e

ste

fitn

ess

Melhor fitness na terminação

0 - 50 51 - 60 61 - 70 71 - 80 81 - 90 91 - 100

Algoritmo A

Algoritmo B

5

10

15

20

25

29 / 52




Qual dos dois algoritmos e omelhor?

Apesar dos indicativos paraA, apos 7 execucoes Bchegou em uma solucao queA nem chegou perto.

O objetivo do problema eimportante na decisao dequal algoritmo usar,observando as metricas.

Nú

me

ro d

e e

xe

cu

çõ

es f

ina

liza

da

s

co

m e

ste

fitn

ess

Melhor fitness na terminação

0 - 50 51 - 60 61 - 70 71 - 80 81 - 90 91 - 100

Algoritmo A

Algoritmo B

5

10

15

20

25

29 / 52



Peak Versus Average Performance -Estatısticas

Outros testes estatısticos podem ser conduzidos para saber maisdetalhes sobre os valores;

Two-tailed T-test;

Indica se os valores foram gerados a partir de uma mesmadistribuicao;Requer que os resultados sejam uniformemente distribuıdos;

Na pratica: continua robusto mesmo sem este requisito;

Analise da variancia (ANOVA);

Quando se deseja comparar mais de 2 algoritmos;Calc. probabilidade que qualisquer diferencas tenham sido geradasdevido a efeitos aleatorios;

Two-way ANOVA;

Investigar os efeitos de dois parametros;

Ex.: tamanho da populacao e taxa de mutacao;

30 / 52



Peak Versus Average Performance -Estatısticas

Principais problemas

Se poucos dados e resultados nao-uniformes → T-test e ANOVAnao sao apropriados;

Comparando MBF, se SR < 1 para alguns → prob. alta dos dadosnao estarem distribuıdos uniformemente;Existe um limite superior fixo para o valor de MBF (otimo doproblema);

Testes nao-parametricos;

Poucas suposicoes sobre a natureza dos dados → menos provavel denotar diferencas...

31 / 52



Problemas de teste para comparacoesexperimentais

Abordagens:

Instancias de um repositorio academico;

Instancias criadas por um gerador de instancias;

Instancias de problemas reais;

32 / 52



Usando instancias de problemas predefinidos

Suite de testes de Jong;

Poder computacional maior desde 1970;

Novas funcoes;

Ackley;Griewank;Tastringin;

Mesma suite de testes → melhores AEs para tais funcoes!

Site interessante com problemas:http://tracer.lcc.uma.es/problems/

33 / 52


http://tracer.lcc.uma.es/problems/


Usando instancias de problemas predefinidos -Funcao de Ackley

The Ackley Problem [1] is a minimizationproblem. Originaly this problem was defined fortwo dimensions, but the problem has beengeneralized to N dimensions [3].

Formally, this problem can be described as

finding an string ~x = {x1, x2, . . . , xN}, withxi ∈ (−32.768, 32.768), that minimizes the

following equation:

F (~x) = −20·exp(−0.2

√

√

√

√

1

n·

n∑

i=1

x2i )−exp(1

n·

n∑

i=1

cos(2πxi ))+20+exp(1)

(1)

34 / 52



Usando instancias de problemas predefinidos -Funcao de Griewangk

The Griewangk Problem [7] is a minimizationproblem.Formally, this problem can be described asfinding an string ~x = {x1, x2, . . . , xN}, withxi ∈ (−600, 600), that minimizes the followingequation:

F (~x) = 1 +n∑

i=1

x2i

4000−

n∏

i=1

cos(xi√i) (2)

Instances and best known solutions for those instances:

In order to define an instance of this function we need to providethe dimension of the problem (N). The optimum solution of theproblem is the vector v = (0, ..., 0) with F (v) = 0.

35 / 52



Usando instancias de problemas predefinidos -Funcao de Rastrigin

The Generalized Rastrigin Function Thisfunction was first proposed by Rastrigin as a2-dimensional function [8] and has beengeneralized by Muhlenbein et al in [6]. Thisfunction is a fairly difficult problem due to itslarge search space and its large number of localminima.

F (~x) = A · n +n∑

i=1

x2i − A · cos(ω · xi ) (3)

A = 10 ; ω = 2 · π ; xi ∈ [−5.12, 5.12] Instances and best known solutions forthose instances:

In order to define an instance of thisfunction we need to provide the dimensionof the problem (n). The optimum solutionof the problem is the vector v = (0,...,0)with F(v) = 0.

36 / 52




Outro problema com as suites de teste:

Estas funcoes nao formam uma colecao sistematica de pontos parabusca;

Como dividir estas funcoes em categorias significantes?

Esforcos nesta direcao feitos por: Eiben e Back [5];Apresentou comportamentos:

diferentes em funcoes de uma mesma categoria;similares em funcoes de outras categorias;

37 / 52




Recomendacoes de Back e Michalewicz [4] apud [2] para comporsuites de teste para EC:

1 Incluir poucas funcoes unimodais para comparacoes de velocidade deconvergencia;

2 Incluir muitas funcoes multimodais com um numero elevado de otimos locais;

3 Uma funcao teste com valores da funcao objetivo com algum tipo de ruıdo;

4 Problemas com restricoes;

5 Funcoes-objetivo multimensionais (numero alto de dimensoes);

38 / 52



Geradores de instancias

Comunidades de pesquisa desenvolveram instancias de problemas deuma certa classe;

Fonte de problemas de pesquisa operacional: J.E. Beasley:http://people.brunel.ac.uk/~mastjjb/jeb/info.html

Restricoes http://4c.ucc.ie/web/archive/bench.jspMachine Learning http://archive.ics.uci.edu/ml/

“Interessante:” apresenta resultados (inclusive de outras tecnicas);

39 / 52


http://people.brunel.ac.uk/~mastjjb/jeb/info.html

http://4c.ucc.ie/web/archive/bench.jsp

http://archive.ics.uci.edu/ml/



Instancias criadas on-the-spot;

Possibilidade de ajuste dos parametros do gerador de instancias;

Ex.: Numero de sentencas e variaveis no problema 3-SAT;

Permite ajustar a geracao em areas crıticas;

Permite a investigacao sistematica da instancia em relacao aosparametros;

40 / 52




Instancias criadas on-the-spot;

Possibilidade de ajuste dos parametros do gerador de instancias;

Ex.: Numero de sentencas e variaveis no problema 3-SAT;

Permite ajustar a geracao em areas crıticas;

Permite a investigacao sistematica da instancia em relacao aosparametros;

40 / 52




A pergunta: qual dos doisalgoritmos e o melhor?

Passa a ser: qual dos doisalgoritmos e melhor emquais instancias.

De

sem

pen

ho

do A

lgori

tmo

Parâmetro do problema

41 / 52




Repositorio para pesquisadores de EC:

http://www.cs.uwyo.edu/~wspears/generators.html

1 Bit-string Multimodality Generator (W. Spears)2 Continuous-valued Multimodality Generator (J. Kennedy)3 Random L-SAT Epistasis Generator (W. Spears)4 Matrix Epistasis Generator (J. Paredis)5 Graph Generators (P. Ross) (J. Culberson)6 Dynamic Fitness Landscape Test Function Generator - DF1 (R.

Morrison)7 Max-Set of Gaussians Landscape Generator (M. Gallagher)8 NK-Landscape Generator (M. Potter)9 Polynomial Generator (T. English)10 Constraint Satisfaction Problem Generator (New URL from J. van

Hemert)

42 / 52


http://www.cs.uwyo.edu/~wspears/generators.html


Usando problemas do mundo real

Resultados relevantes para a aplicacao;

Muito complicados;

Dispoe de poucos dados disponıveis;

Algumas vezes restritos (impedem a publicacao);

Podem ter tanta especificidade que os resultados ficam difıcies degeneralizar;

Sao como a prova do pudim!

43 / 52



Mas praticas

Cenario

O aluno inventou uma nova mutacao:tabajara mutation;

Testou o AG padrao e o novotabajara-AG 20 vezes independentementeusando 10 funcoes objetivo da literatura;

Resultado: tabajara-AG ganhou 7,empatou 1 e perdeu 2 em termos de SR;

Logo conclui: o tabajara-AG e, de fato,valioso!

44 / 52



Mas praticas

Pergunta: O que nos, a comunidade de EC, aprendemos destaexperiencia?

45 / 52



Mas praticas


Que aluno e bicho errado! (oops... prox slide)

45 / 52



Mas praticas


Que existe uma nova caracteristica que pode ser uma ideiapromissora.

45 / 52



Mas praticas

Questoes que permanecem:Quao relevantes sao estes resultados, quao tıpicas sao as funcoes de testepara problemas do mundo real, ou quao importantes sao elas sob aperspectiva academica?O que acontece se uma metrica diferente for usada, ou se as execucoesterminarem antecipadamente, ou posteriormente?Qual e o escopo que afirma sobre a superioridade do tabajara-AG?Existe uma propriedade distinguindo as 7 melhores das 2 piores funcoes?Quao sensıvel sao estes resultados a mudancas nos parametros doalgoritmo?Os diferentes desempenhos conforme medidos no exemplo saoestatisticamente significantes? Ou podem ser apenas artefatos causadospor efeitos aleatorios?

45 / 52



Uma pratica mais adequada

Como avaliar o comportamento de umnovo algoritmo

Qual tipo de problema eu estou tentandoresolver?

Qual propriedade seria desejavel de umalgoritmo para este tipo de problema:

Ex.: velocidade em encontrar boassolucoes, confiabilidade em localizarboas solucoes, occasional brilliance?

Quais metodos existem atualmente paraeste problema, e por que eu estoutentando fazer um novo, ou seja, quandoeles nao executam bem?

46 / 52




Processo

Iventar um novo EA (xEA) para resolver oproblema X;

Identificar tres outros EAs e umatradicional heuristica de benchmark para oproblema X na literatura;

Identificar quando e por que xEA foimelhor que os outros metodos;

Obter um gerador de instancias para oproblema X com dois parametros: n(tamanho do problema) e k algumindicador especifico ao problema.

47 / 52




Processo (cont)

Selecionar 5 valores para k e 5 valores para n;

Gerar 100 instancias diferentes para todas as 25combinacoes;

Executar todos os algoritmos em cada instancia100 vezes (benchmark heurıstico tambem eestocastico);

Gravar os valores de AES, SR, MBF com osdesvios padrao (exceto para SR);

Avaliar a significancia estatistica dos resultados(apos identificar os testes apropriados baseadosnos dados);

Colocar o codigo e as instancias em um website;

48 / 52



Uma pratica mais adequada - Vantagens destemodelo

Processo (cont)

Os resultados podem ser arranjados em 3D: que e, assimcomo a performance landsacep sobre o plano (n,k) comatencao especial ao efeito de n;

O nicho para xEA pode ser identificado, pex, fraco comrespeito a outros aglrotimos para (n,k) combinacoes dotipo 1, forte para (n,k) combinacoes do tipo 2,comparavel caso contrario. Assim a questao quando,pode ser respondida.

Analisando as caracteristicas especificas e os nichos decada algoritmo pode elucidar a questao do poq que.

Muito conhecimento pode ser coltado sobre o problema Xe seus resolvedores;

Resultados generalizados sao alcancados, ou pelo menosindicadores com escopo bem identificado baseado emdados solidos;

Reproducao dos resultados em qualquer outro lugar, eassim o avanco da pesquisa e facilitado. 49 / 52



Sugestoes/Duvidas

Favor colocar as sugestoes na caixa:

50 / 52



References I

D. H. Ackley.A connectionist machine for genetic hillclimbing.Kluwer, Boston, 1987.

Eiben A.E and Smith J.E.Introduction to Evolutionary Computing.Springer, 2007.

T. Back.Evolutionary algorithms in theory and practice.Oxford University Press, 1996.

T. Back, D.B. Fogel, and Z. Michalewicz.Handbook of Evolutionary Computation.Institute of Physics Publishing, Bristol and Oxford University Press,1997.

51 / 52



References II

Back Eiben, A.E.An empirical investigation of multi-parent recombination operatorsin evolution strategies.Evolutionary Computing, 1997.

H. Muhlenbein, D. Schomisch, and J. Born.The Parallel Genetic Algorithm as Function Optimizer.Parallel Computing, 17(6-7):619–632, 1991.

A. Torn and A. Pilinskas.Global optimization.In Lecture Notes in Computer Science 350. Springer-Verlag, 1989.Berlin Heidelberg.

A. Torn and A. Zilinskas.Global Optimization.Lecture Notes in Computer Science, 350, 1989.

52 / 52


Documents

Como executar algoritmos evolucion rios Otimiza o Natural ...gabriel/cpe723/Aula6_Rafael_WorkingWithGAs.pdf · Tipos de problemas: Projeto, Repetitivos, Controle on-line; Exemplo