TEMA 1 Algoritmos Genéticos Aula 3

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

71

TEMA1Aula3

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Oqueé?•  mecanismodebuscanumespaçodesoluções

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

•  Quemestáporpertonãocostumasertãodiferente

75

AlgoritmosEvolucionárioseGenéticosfundamentos

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

76

AlgoritmosEvolucionárioseGenéticosfundamentos

ÓtimaBoaNeutraRuimAmostras

AGéumprocedimentoparaescolhersucessivasamostrascomaexpectativadechegarcadavezmaispróximodamelhorsituação

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosEvolucionárioseGenéticosfundamentos

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosEvolucionárioseGenéticosfundamentos

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

eprocessos•  Podemapresentarprincípiosassociadosà

– Criatividade– Emergência(surgiralgonovo)

79

AlgoritmosEvolucionárioseGenéticosfundamentos

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Algoritmosgenéticos•  Buscaporcaminhosparaumdestino

–  Identificarumaboaseqüênciadeetapasparaatingiroobjetivo

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

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

81

AlgoritmosGenéticosprincípios

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosGenéticosprincípios

82

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

•  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

AlgoritmosGenéticosprincípios

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

85

AlgoritmosGenéticosconceito

Desempenho

Gerações

Ideal

Real

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

86

AlgoritmosGenéticosmodelo

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosGenéticosmodelo

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Ex:individuoéumanimal(consistênciaestrutural)

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

•  Oquenãopodeaconteceréporexemplosurgiralgocomospésnacabeça!

88

AlgoritmosGenéticosmodelo

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Emboraoexemploanteriorpareçaobvio,nemsempreéfácildesegarantirtalconsistência

•  Ex:individuocorrespondeaumconjuntoderotasdeônibus

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

trivial.Ex,ofilhopodeherdardoisconjuntosderotasdeumaregiãodacidadedeixandooutraregiãodescoberta

89

AlgoritmosGenéticosmodelo

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

90

AlgoritmosGenéticosmodelo

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Operadoresagemsobreogenótipocomefeitosobreofenótipo

Altera-seocódigoecomissotransforma-seoindividuo

91

AlgoritmosGenéticosoperadores

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Representação/CodificaçãoEx:AutomatoCrossOver2paisgerando2filhosCompostosapartirdepartedecadaumdospais

94

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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)

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

96

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

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

97

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

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

99

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

100

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

101

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

agregandomutaçãochancedemutaçãoepontodemudança

102

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

103

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

104

AlgoritmosGenéticosexemplo/procedimento

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

Próximaaula

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

maiseficiente)

105

AlgoritmosGenéticosconclusão

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

107

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

108

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

109

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

110

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

TEMA1AlgoritmosGenéticosAula4

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

111

TEMA1Aula3

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

WOXBOTumrobôcontroladoporautômatoqueevolui

GENPOLISplanosemafóricoqueevolui

112

AlgoritmosGenéticosexemplos

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

113

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Robôvivenumaarena(ambiente)

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

consomeenergiadeformacontinua,precisandoportantoencontrarfontesondepossaserecarregar

114

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

RobôDotadodesensorvisual(câmeracomredesneurais)

•  câmeracapturaimagensdopontodevistadorobô•  RNApreviamentetreinadareconheceobjetosnacena

•  identificandocubosepirâmides•  reportandosualocalizaçãorelativa

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

115

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

RobôControladoporumautômatoevolutivo(decisor)

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

evitaroutros

116

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

RobôControladoporumautômatoevolutivo(decisor)

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

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

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

117

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Robômelhoradaptadoéaqueledemaisrapidamentetomardecisõescorretasapartirdosobjetosidentificados,demodoairaoencontrodaspirâmidesenquantoevitaoscubos

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

Oboméquepodemserencontradasdeformaautônomausandoconceitosadaptativos/evolutivos

118

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

119

AlgoritmosGenéticosWOXBOT

Parado

Giraaesquerda

Giraadireita

Segueem

frente

ObjEsq

ObjFrente

ObjDir

Vira

SemObj

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

120

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

RepresentaçãocomvistasaCodificação

121

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

122

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

124

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

125

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

Resumindo,aintervençãodeumprojetistaaindasefaznecessária

Nemtudoécriadoouemergeapartirdonadadeformaautônoma

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

126

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

127

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

128

AlgoritmosGenéticosWOXBOT

Poucastransições

Muitastransições

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

129

AlgoritmosGenéticosWOXBOT

Universodeestadospossíveis(8)

MEF1:comalgunsestados(4)

MEF2:comoutrosestados(4)

MEFn:comoutrosestados(6)

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

130

AlgoritmosGenéticosWOXBOT

RedepequenaPoucosestadosTotalmenteconectada

RedepequenaPoucosestadosParcialmenteconectada

RedepequenaPoucosestadosParcialmenteconectada

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

131

AlgoritmosGenéticosWOXBOT

RedepequenaPoucosestadosTotalmenteconectada

RedegrandeMuitosestadosParcialmenteconectada

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

134

AlgoritmosGenéticosWOXBOT

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

Representaçãodasrotas

135

AlgoritmosGenéticoTráfego/MobilidadeUrbana

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

137

AlgoritmosGenéticosGENPOLIS

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

138

AlgoritmosGenéticosGENPOLIS

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

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

nestasjanelastemporaisquesejamantidocompoucadispersão

139

AlgoritmosGenéticosGENPOLIS

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

AnáliseEspaçoTemporal

140

AlgoritmosGenéticosGENPOLIS–situaçãooriginal

DiaFaixaHoráriaTrechoVia

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

141

AlgoritmosGenéticosGENPOLIS–situaçãomelhorada

DiaFaixaHoráriaTrechoVia

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

CartaSemafórica

142

AlgoritmosGenéticosGENPOLIS

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

MapaGenético

143

AlgoritmosGenéticosGENPOLIS

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

MapaGenético

144

AlgoritmosGenéticosGENPOLIS

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

145

AlgoritmosGenéticosGENPOLIS

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

146

AlgoritmosGenéticosGENPOLIS

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

147

AlgoritmosGenéticosGENPOLIS

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

148

AlgoritmosGenéticosGENPOLIS

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

graus de saturação

defasagens defasagens

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

0 0 0 0 1 0 0 1

graus de saturação

defasagens

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

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

149

AlgoritmosGenéticosGENPOLIS

GERAÇÃO 1

412

1886 1534

800

750

1203

930

1343

450

650

785

1212

1004 850

910

650 500

763

560

701

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

150

AlgoritmosGenéticosGENPOLIS

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%

EPUSP-PSIEletrônicaeSistemasSistemasInteligentesIIConcepçãoeImplantaçãodeSistemasInteligentes

2019Prof.Dr.MarcioLoboNetto

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

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

151

AlgoritmosGenéticosWOXBOT