TEMA 1 Algoritmos Genéticos Aula 3

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

TEMA1AlgoritmosGenéticosAula321out-  fundamentos:conceito/modelo/operadores/algoritmo

71

TEMA1Aula3



KarlSims–EvolvingCreatures(1994)https://www.youtube.com/watch?v=JBgG_VSP7f8Morfologia•  corpo:membros/articulações•  controle:propósito/movimentos&ações•  evoluçãogenética

72

ArtificialLife



Caixeiroviajante(travelingsalesman)https://www.youtube.com/watch?v=KdrfFFWwWiUhttps://www.youtube.com/watch?v=Lw-91UORjx4https://www.youtube.com/watch?v=q6fPk0--eHYAdaptaçãogenéticaderedesneuraishttps://www.youtube.com/watch?v=8V2sX9BhAW8 73

AlgoritmoGenético



Algoritmosevolucionários•  Algoritmos(estratégias)evolucionários

–  (Rechenberg,1965)–  Métodosparaevoluçãodesoluçõesdeproblemas

•  Programaçãoevolucionária–  (Fogel,1966)–  Quandoaplicadosparaodesenvolvimentodeprogramas

•  Algoritmosgenéticos–  (Holland,1975)–  Métodosevolutivosbaseadosnousodecodificaçãogenética

•  Programaçãogenética–  (Koza,1992)–  Quandoaplicadosparaodesenvolvimentodeprogramas

74

AlgoritmosEvolucionárioseGenéticoscategorias/propostas



Oqueé?•  mecanismodebuscanumespaçodesoluções

•  Buscamosumasolução(individuo)numespaçodesoluções–  Umbomindividuo–  Esperandopoderencontra-losemprecisartestartodos!!!–  Combaseemalgumacoerênciaentrevizinhos

•  Quemestáporpertonãocostumasertãodiferente

75

AlgoritmosEvolucionárioseGenéticosfundamentos



76


ÓtimaBoaNeutraRuimAmostras

AGéumprocedimentoparaescolhersucessivasamostrascomaexpectativadechegarcadavezmaispróximodamelhorsituação



Quandoéinteressante?•  Quandoadimensãodesteespaçoéintratável

–  Ousejaquandonãosepodetestarcadasoluçãopelofatodequetalaçãoexcedeemmuitoacapacidade(tempo)disponível

•  Exdimensõesintratáveis:–  ~1080 númeroátomosuniverso–  ~10120númerodepossíveisestadosnoxadrez–  106000 6.000semáforosemSP;10estados/semáforo

77




Aexploraçãodediferentesindivíduospermitevasculharoenormeespaçodesoluções•  entendendo-secadaindividuocomoumaparticular

soluçãodoproblema,eoespaçodesoluçõescomoaquelequecontemplaatodasaspossíveissoluções

Particularmenteindicadoemcasosemqueoespaçoémuitogrande(ex:1030)•  situaçõesemqueexplorartodasassoluçõesnabuscada

melhoréalgointratável,eemquenãoháconhecimentodafunçãoquequalificacadasolução(sehouvereforconhecidapode-seterumasoluçãoanalíticasimples–exfunçãolinear,ouderivável,bastaveroseumáximo!)

78




Computaçãoevolucionária•  Métodosbottom-upparadesenvolvimentodesistemas

eprocessos•  Podemapresentarprincípiosassociadosà

– Criatividade– Emergência(surgiralgonovo)

79




Algoritmosgenéticos•  Princípio

– Métododeembasamentoestatístico–  Sucessivaalteraçãodeindivíduosnumapopulaçãosegundoumcritérionorteadordoprocesso

•  Mecanismodeavaliaçãodaqualidadedosindivíduos(fitness)–  Codificaçãogenéticadosindivíduos,sobreaqualoperamosprocedimentosdereproduçãoemutação

•  Permitemmanterboas(melhores)característicasdosindivíduosdapopulaçãoenquantoexploramtambémoutrasnovas

–  Início:sistemaexploratório–favorecenovascaracterísticas– Fim:sistemaconservativo–favoreceamanutençãodasmelhorescaracterísticasobtidas

80

AlgoritmosGenéticosprincípios



Algoritmosgenéticos•  Buscaporcaminhosparaumdestino

–  Identificarumaboaseqüênciadeetapasparaatingiroobjetivo

•  Buscaporsoluções– Procurarporumaboasoluçãodoproblema(ouótima)

•  Quandooespaçodepossíveissoluçõesédealtíssimadimensão

81




Algoritmosgenéticos•  Exemplo

– Evoluçãodemáquinadeestadosquedefineocomportamentodeumrobôvirtual(WoxBot)

•  Máquina(estadosetransições)codificadageneticamente•  Métricadeavaliaçãodedesempenho:osucessodorobôemprocurarpirâmidesevitandocubos

•  Procedimentosdereproduçãogenética:– cruzamento– mutação


82



•  Identificaçãodoindividuo(aquiloquesequermelhorar)

•  Codificaçãogenéticadoindivíduo(parapermitirousodeoperadoresgenéticos)

•  Criaçãodesucessivasgeraçõesdapopulação(diversosindivíduoscomalgumasdiferençasentresi,representadasnasdiferentescodificaçõesgenéticas)

•  Avaliaçãoerankingdetodososindivíduos

•  Criaçãodenovosindivíduos(novageração)apartirdosatuaisporreprodução(combinaçãoentrepais)emutação(pequenasalteraçõesaleatórias)

83




Individuo•  Cadasoluçãoérepresentadaporumindivíduo

População•  Conjuntoparcialdesoluçõesérepresentadoporuma

população

Gerações•  Aolongodediversasgeraçõesseobservaumamudança

noperfildosindivíduosdapopulaçãoquevãoseespecializando(chegandomaispróximosdamelhor)

84

AlgoritmosGenéticosconceito



85

AlgoritmosGenéticosconceito

Desempenho

Gerações

Ideal

Real



Fenótipo•  Oindividuoemsi•  RepresentaumapossívelsoluçãodoproblematratadoGenótipo•  Umacodificação(binária)doindivíduo

86

AlgoritmosGenéticosmodelo



Amaiordificuldadeestaemgarantiraconsistênciadofenótipocombasenogenótipo

•  CorrespondênciabiunívocaCadanovogenótipotemquepodercorresponderaumfenótipo

(individuoousolução)possível(consistente)•  Modeloshomogêneos

–  Fácil•  Modelosheterogêneos

–  Podeserdifícil–  Eventualmentenecessitedevalidadoresdoprocesso

construtivo

87




Ex:individuoéumanimal(consistênciaestrutural)

•  Ocruzamento(reprodução)deveproduzirumnovoindividuoquemantenhaasmesmascaracterísticasdosseuspais,combinando-as–  Pernasmaislongas(pai)ebraçosmaiscurtos(mãe)

•  Oquenãopodeaconteceréporexemplosurgiralgocomospésnacabeça!

88




Emboraoexemploanteriorpareçaobvio,nemsempreéfácildesegarantirtalconsistência

•  Ex:individuocorrespondeaumconjuntoderotasdeônibus

•  Umnovoindividuodevecorresponderaumnovoconjuntoderotas,masdeve-segarantirporexemploqueacoberturadasmesmassejacompleta(todaacidade)•  Eaosemisturardoisconjuntosderotasissopodenãoser

trivial.Ex,ofilhopodeherdardoisconjuntosderotasdeumaregiãodacidadedeixandooutraregiãodescoberta

89




Oprimeiroetalvezmaisimportantepontoasertrabalhadoquandosetrabalhacomalgoritmosgenéticoséodaespecificaçãodomodelodoindividuo(fenótipo)edeumcorrespondentecódigo(genótipo)queorepresente

Nãoparecehaverumaregraparaisso.Cadaprojetodevesertratadoindependentemente,analisandosuascaracterísticaseprocurandoumarepresentaçãoquepermitaumamanipulaçãoconsistente

90




Operadoresagemsobreogenótipocomefeitosobreofenótipo

Altera-seocódigoecomissotransforma-seoindividuo

91

AlgoritmosGenéticosoperadores



Reprodução•  novoindividuocompostoapartirdacomposição(partes)de

seuspais–  Paisescolhidosconsiderandoprobabilisticamenteseus

desempenhos•  melhoreslevamvantagem,maspioresnãosãoexcluídos!

Mutação•  novoindividuotransformadoaleatoriamente

–  mutaçõestembaixaocorrência(3%a10%)–  dentreasocorrênciasaspequenasalteraçõessãomais

frequentes(leidaspotenciasinversas–terremotos!)

92

AlgoritmosGenéticosoperadores



Representação/CodificaçãoEx:Automatoestadosetransiçõesnúmerodeestados(vamosconsidera-lofixo)númerodetransições(entremínimoemáximo)código:cadatransição implícito(posiçãonocódigo):Ei/C explícito(valor):Ef

6estados/de0a3transiçõesporestado

93

AlgoritmosGenéticosexemplo/procedimento



Representação/CodificaçãoEx:AutomatoCrossOver2paisgerando2filhosCompostosapartirdepartedecadaumdospais

94




95

AlgoritmosGenéticosexemplo/procedimento1 2 3

54 6

Ef:(EiC)

a b c

1 4 2 5

2 3 6

3 4

4 5

5 6

6

Ef:(EiC)

a b c

1 4 2

2 3 4 5

3 6

4 5

5 3 6

6

1 2 3

54 6

Ef:(EiC)

a b c

1 4 2

2 3 4 5

3 6

4 5

5 6

6

Ef:(EiC)

a b c

1 4 2 5

2 3 6

3 4

4 5

5 3 6

6

1 2 3

54 6

1 2 3

54 6

Reprodução1(1-3/4-6)



96


54 6

Ef:(EiC)

a b c

1 4 2 5

2 3 6

3 4

4 5

5 6

6

Ef:(EiC)

a b c

1 4 2

2 3 4 5

3 6

4 5

5 3 6

6

Ef:(EiC)

a b c

1 4 2

2 3 4 5

3 4

4 5

5 6

6

1 2 3

54 6

Ef:(EiC)

a b c

1 4 2 5

2 3 6

3 6

4 5

5 3 6

6

1 2 3

54 6

1 2 3

54 6

Reprodução2(1-2/3-6)

4 2 5 3 2 6 3 3 4 4 5 4 5 5 6 6 6 6

4 2 1 3 4 5 3 3 6 4 5 4 3 5 6 6 6 6



97


54 6

Ef:(EiC)

a b c

1 4 2 5

2 3 6

3 4

4 5

5 6

6

Ef:(EiC)

a b c

1 4 2

2 3 4 5

3 6

4 5

5 3 6

6

Ef:(EiC)

a b c

1 4 2

2 3 4 5

3 5

4 5

5 6

6

1 2 3

54 6

Ef:(EiC)

a b c

1 4 2 5

2 3 6

3 6

4 5

5 3 6

6

1 2 3

54 6

1 2 3

54 6

Reprodução2(1-2/3-6)comMutação(3/4)

4 2 5 3 2 6 3 3 4 4 5 4 5 5 6 6 6 6

4 2 1 3 4 5 3 3 6 4 5 4 3 5 6 6 6 6



PseudocódigoCriaçãodapopulaçãoinicial(nindivíduos)Avaliaçãodecadaindividuoeordenação(ranking)Criaçãodanovapopulaçãoseleçãodeparesparareprodução(quem)seleçãodocritériodereprodução(como)reavaliação(novosindivíduos)escolhadosindivíduosdanovapopulação

98




PseudocódigoCriaçãodapopulaçãoinicial(nindivíduos)aleatória(normalmenteamelhorforma–generalidade)ousegundoalgumcritério ex:homogeamentedistribuídosnoespaçodesoluções

99




PseudocódigoAvaliaçãodecadaindividuo....avaliaçãoindividual(desempenhonatural)ouavaliaçãoporcompetição(torneios:umcontraooutro(s))

...eordenação(ranking)mantendoosmelhoresoufavorecendoosmelhores(maioreschances)

100




PseudocódigoCriaçãodanovapopulaçãoseleçãodeparesparareprodução(quem)aleatóriaoufavorecendoosmelhores proporcionalmenteaodesempenhodecadaum

101




PseudocódigoCriaçãodanovapopulaçãoseleçãodecritériosparareprodução(como)definiçãodopontodequebradocódigofixaoualeatória

agregandomutaçãochancedemutaçãoepontodemudança

102




PseudocódigoCriaçãodanovapopulaçãoreavaliação

103




PseudocódigoCriaçãodanovapopulaçãoescolhadosindivíduosdanovapopulaçãomantendoosmelhores(elitismo)oufavorecendoosmelhoresoualeatóriaoualgumacombinaçãodasanteriores

104




Métodogenérico•  paraprocuradesoluções•  paraevoluir(melhorar)soluções

Próximaaula

•  estudodealgunscasos•  Woxbot(robôqueevoluiparasobreviverpormaistempo)•  Genpolis(sistemadeprocuraporumacartasemafórica

maiseficiente)

105

AlgoritmosGenéticosconclusão



Caixeiroviajante(travelingsalesman)https://www.youtube.com/watch?v=KdrfFFWwWiUhttps://www.youtube.com/watch?v=Lw-91UORjx4https://www.youtube.com/watch?v=q6fPk0--eHYAdaptaçãogenéticaderedesneuraishttps://www.youtube.com/watch?v=8V2sX9BhAW8 106

AlgoritmoGenético



107



108



109



110



TEMA1AlgoritmosGenéticosAula4

21out-  aplicações:exemplos/simulações/vídeos-  (modelagemdoindividuo)-  exemplos:woxbot/genpolis- 

111

TEMA1Aula3



WOXBOTumrobôcontroladoporautômatoqueevolui

GENPOLISplanosemafóricoqueevolui

112

AlgoritmosGenéticosexemplos



113

AlgoritmosGenéticosWOXBOT



Robôvivenumaarena(ambiente)

•  ondeseencontramcubos(roubamenergia)•  epirâmides(fornecemenergia)•  ondesemovimentalivremente

consomeenergiadeformacontinua,precisandoportantoencontrarfontesondepossaserecarregar

114




RobôDotadodesensorvisual(câmeracomredesneurais)

•  câmeracapturaimagensdopontodevistadorobô•  RNApreviamentetreinadareconheceobjetosnacena

•  identificandocubosepirâmides•  reportandosualocalizaçãorelativa

–  frente,direita,esquerda/perto,longe•  Informaçãorepassadaparaocentrodedecisões(MEF)

115




RobôControladoporumautômatoevolutivo(decisor)

•  estadoscorrespondemaações•  Seguiremfrente,viraradireitaouesquerda•  Emconsequênciadoquesemovimentanacena•  Podendoentão(MEFadequada)perseguiralgunsobjetose

evitaroutros

116




RobôControladoporumautômatoevolutivo(decisor)

•  evoluiaolongodegeraçõesdemodoaconduziraumrobômaisadaptadoaoambiente•  vidaprosperaelonga(DrSpock,StarTrek)

•  semquehajainterferênciadocriadordorobô•  adaptaçãoéautônoma!

•  Favorecerobôsqueprocurampirâmidesenquantoevitamcubos(acumulammaisenergia,tendoentãovidamaislonga)

117




Robômelhoradaptadoéaqueledemaisrapidamentetomardecisõescorretasapartirdosobjetosidentificados,demodoairaoencontrodaspirâmidesenquantoevitaoscubos

EncontraraFSMidealnãoétarefatrivial.Existemdiversasopções(estratégiaspararegerocomportamento)

Oboméquepodemserencontradasdeformaautônomausandoconceitosadaptativos/evolutivos

118




119


Parado

Giraaesquerda

Giraadireita

Segueem

frente

ObjEsq

ObjFrente

ObjDir

Vira

SemObj



120




RecolhimentodosexercíciosfeitosemcasaDiscussãodaspropostas–semelhançasediferençasAnalisedoprocessomentalhumanoquelevouaoresultadonestecasonósfizemostudo

Comparaçãocomométodocomputacionalevolutivonestecasonósparticipamos,definindocritériosecondiçõesdecontorno

RepresentaçãocomvistasaCodificação

121




Pararesolverumproblemaéfundamentaldefini-lobemEentãocompreenderquaisestratégiasparecemmaisadequadas(númerodeestados,grausdepercepção,oquepareceseramelhoraçãoemcadasituação)

Mesmoqueasoluçãovenhaaserencontradacomputacionalmente(deformaautônomapormétodosevolutivos)elasóacontecedepoisquetiveremsidodefinidasascondiçõesdecontornodoproblema

122




Nestecasocompõeacondiçãodecontornonúmerodeestadosadequado nemtãopoucoquenãoconsigalidarcomoproblema nemtantoquetorneseutratamentodifícil

Temosquedefinirosestados?émaisfácildefinirosignificadodecadaestadoapriorimaspodeserdeixadoparaquesejadefinidopeloAG,sóquenestecasosecriaumproblemaamais(comoautomatizaradefinição/significadodecadaestado)

Temosquedefinirastransições?não,nestecasocabeaoprocessoevolutivofaze-lomastemosquedefiniroconjuntodecondiçõesaseravaliado

123




Nestecasocompõeacondiçãodecontornograusdepercepção(condiçõesdetransição) nenhum,umoumaisobjetosnocampovisual melhordecisãoemcadacaso

124




Separtirmosdeestadospré-definidos,deixaremosparaaevoluçãoabuscaótimadastransições émaissimples,mastambémmaisrestritivo

Sedeixarmostudolivre,podemosimaginarquesejapossívelencontrarummodelomaisrobusto,mascujocusto(tempocomputacional)sejamaior(proibitivo?)

125




Resumindo,aintervençãodeumprojetistaaindasefaznecessária

Nemtudoécriadoouemergeapartirdonadadeformaautônoma

Apenasdamoscondiçõesparaquemecanismosautomáticos(pornósconcebidos/programados)possamintervireentãocriarautonomamenteoqueesperamosdeles(nesteexemploaMEF)

126




DequalquerformaaideiaéqueoAGsejacapazdefazerboasescolhas,oquepressupõequeoelencodeitensaescolhersejadefinidoapriori porexemplotodososestadospossíveis,dosquaisoAGescolheriaalguns(ouusariatodos)

127




128


Poucastransições

Muitastransições



129


Universodeestadospossíveis(8)

MEF1:comalgunsestados(4)

MEF2:comoutrosestados(4)

MEFn:comoutrosestados(6)



130


RedepequenaPoucosestadosTotalmenteconectada

RedepequenaPoucosestadosParcialmenteconectada

RedepequenaPoucosestadosParcialmenteconectada



131


RedepequenaPoucosestadosTotalmenteconectada

RedegrandeMuitosestadosParcialmenteconectada



Construçãodasredesconexãocompletaouparcialhomogêneaounão(algumahierarquia)

Oquequerqueseja,oconceitodeveserescolhidoparapoderserdefinido

entreoscritériosqueserãousadospeloAGnabuscapornovasconfigurações

Amenosdaconfiguraçãocompletaehomogênea,asdemaiscorremorisco

delevararedesdesconexasnoprocessodereprodução Nestecasopode-seprocedercomasaveriguaçõesdeconsistênciaousimplesmentedeixarissoemaberto(estasredestemmenoreschancesdeseremboaseserãoprovavelmentedescartadas)

132




Omesmovaleparaastransições,enestecasoseresumeadefiniroconjuntodetodasassituaçõesquepodemservislumbradas nestecasoérazoávelsuporquetenhamosquecriar

classes umobjeto,doisobjetos,váriosobjetos localização:segmentada direita,direita-centro,centro,... próximo,intermediário,longe

133




DISCUSSÃOCONSTRUÇÃOCONJUNTADEUMAREDE(FSM)escolhadecritériosproposiçãodeumaarquitetura(FSM)identificaçãodedúvidas,problemas,...

134




Rotasdeônibus(campusdaUSP)Descriçãodoproblemamatrizorigemdestinoescolhadospontos(aglomeração)

Representaçãodasrotas

135

AlgoritmosGenéticoTráfego/MobilidadeUrbana



PlanoSemafóricoqualacartadetemposquepropiciaomelhorescoamentodotráfegonumadeterminadacondição?porcondiçãoentende-seasituaçãodotransito(densidadedeveículosnamalha)considerandopadrões(mediashistóricas)porfaixahoraria

aumentarotempodeverdeparafavorecerofluxonumcruzamento(paraumadasvias)temefeitonoscruzamentosseguintesdarede,damesmaformaqueéafetadaporcruzamentosanterioresTrata-seportantodeumproblemadeotimizaçãodecaráterglobal(distribuído)

136

AlgoritmosGenéticosGENPOLIS



137




138




AG–propõesucessivassoluções,combinandosoluçõesanteriores

SIMULADOR–avaliaoimpactodecadanovasolução(cartasemafórica)noescoamentodotrafego

DADOSINICIAIS–obtidosapartirdemedidas/observaçõesdarealidade,discriminadoporfaixashorarias(intervalosdeduashoras) assumindoqueexistaumpadrãomédiodetrafego

nestasjanelastemporaisquesejamantidocompoucadispersão

139




AnáliseEspaçoTemporal

140

AlgoritmosGenéticosGENPOLIS–situaçãooriginal

DiaFaixaHoráriaTrechoVia



141

AlgoritmosGenéticosGENPOLIS–situaçãomelhorada

DiaFaixaHoráriaTrechoVia



CartaSemafórica

142


gerações

G1 G2 G3 G4 GF

cruzam

entos

C1 30/30 35/25 40/20 50/10 45/15 40/20 35/25

C2 20/40 20/40 25/35 35/25 30/30 25/35 30/30

C3 10/50 20/40 40/20 35/25 30/30 25/35 25/35

Cn 10/50 20/40 40/20 35/25 40/20 45/15 40/20Km(total)congestionamento

108 98 102 96 92 93 91



MapaGenético

143


gene C1 C2 C3 C4 C40

G1 1 5 3 4 3G2 3 3 3 1 4

Gn 2 4 2 3 5

5estadosporsemáforo40semáforosnaredeconsiderada540possíveiscombinações

tempos plano

10/50 1

20/40 2

30/30 3

40/20 4

50/10 5



MapaGenético

144


gene C1 C2 C3 C4 C40

G1 1 8 3 8 5G2 3 6 3 9 7

Gn 4 7 2 7 9

tempos plano

05/55 1

10/50 2

15/45 3

20/40 4

25/35 5

30/30 6

35/25 7

40/20 8

45/15 9

50/10 10

55/05 11

11estadosporsemáforo40semáforosnaredeconsiderada1140possíveiscombinações



Modelagem(definiçãodogene)émuitosimplesBoasimulação(avaliaçãodecadacandidato)équemconsome

muitotempodeprocessamentoExplosãocombinatóriaTestartodasaspossibilidadeséimpraticávelTemportantoqueexplorarcoerênciaentresoluçõessedefatoexistir,entãocomumnumerodetestessensivelmentemenorqueototalépossívelsechegaraboassoluções

145




FIGURASCenário/rededeviasmetropolitanaCartasemafóricaMedidasestatísticas(históricasporfaixahoraria)Combinaçãoideal

146




147


30921378

1108

3194

30923194

11081378 1378

1378 1378

1378

2886

2886

2886

3194

3194

13781378

28492849

2849

2849

169613781378 1378

137813781378

1696

1696 2992

2217

2217

22173134

4701

2997

2217

2997

2997

1108

14431108

2997

2997

3092



148


0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1

0 0 1 0 0 1 0 00 0 0 0 1 0 0 1

graus de saturação


defasagens defasagens

Tempo de ciclo, tempos de verde, defasagens à Atrasos + 20*nParadas

0 0 0 0 1 0 0 1


defasagens

0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1



149


GERAÇÃO 1

412

1886 1534

800

750

1203

930

1343

450

650

785

1212

1004 850

910

650 500

763

560

701



150


520540560580600620640660680

0 50 100 150 200

120%

780820860900940980

10201060110011401180

0 50 100 150 200

130%

350

370

390

410

0 50 100 150 200

100%

420

440

460

480

500

0 50 100 150 200

110%



Exercícioparapróximaaula!ComopoderiaseraMEFquepersigapirâmidesevitandocubos?Considerenomáximoousode8estados.

Definacadaestadopropostoeascondiçõesdetransição(dentrecategoriasresultantesdoclassificaçãovisual)

151


Documents

TEMA 1 Algoritmos Genéticos Aula 3