Aprendizado de Máquinas - Algoritmos genéticos

[Música] Olá eu sou o professor José Avelino placa e nós vamos iniciar Hoje a aula número 14 de aprendizado de máquinas na aula de hoje nós vamos ver algoritmos genéticos que é uma técnica que faz parte do subconjunto dos algoritmos evolucionários e é muito utilizada para resolução principalmente de problemas de busca como nós vamos ver ao longo da aula bom nós vamos passar pelos seguintes tópicos não é uma breve introdução falar sobre os métodos de busca existentes os algoritmos evolucionários do qual algoritmo genéticos é uma subárea os passos principais um algoritmo genético é os itens

principais que a gente vai ter que atentar na construção do algoritmo seria a população inicial a função aptidão e a seleção dos Pais os métodos de geração das novas populações né através dos mecanismos de crossover cruzamento e da Mutação é os critérios e parada para o algoritmo genético vamos ver um exemplo de aplicação e fazer algumas considerações falando sobre as vantagens e aplicações dos algoritmos genéticos bom o algoritmo genético Na verdade ele foi baseado né na teoria da evolução das espécies de Charles Darwin a gente sabe que davam escreveu essa sua teoria né a partir

de observações né que ele fez na natureza né onde ele percebeu que os indivíduos mais aptos né de qualquer espécie que fosse observada né são aqueles com mais chance de produzir os seus descendentes e a seleção natural faz com que os indivíduos mais o mais condições genéticas né de sobrevivência são aqueles que é acabam né Sobrevivendo ao longo do tempo então esses conceitos é que vão ser usados na implementação de soluções utilizando os algoritmos genéticos para os problemas dos quais vamos tratá-los bom então Inicialmente vamos identificar onde que o algoritmo genético pode ser uma boa

técnica empregada né em geral se utilizam algoritmo genéticos para problemas e busca quando a gente fala de busca a gente tem basicamente três grandes linhas né de estratégias para tratar problemas e busca chamada busca cego exaustiva aonde eu vou repetindo um processo de buscar a solução o algoritmo guloso é um exemplo dessa busca o problema da busca cega é que para problemas com um espaço de possibilidades muito grande evidentemente que a performance não é das melhores a busca ourística é aquela que busca é colocar alguma informação específica do problema do qual se está tratando e

a partir daí é direciona né A minha busca em função dessa eurística o método né da distância mais culta até o próximo nó é um exemplo né de busca eurisse e finalmente os métodos de busca local é eu sempre pato do meu estado atual para o meu estado da vizinhança a partir de um critério de otimização é aí que se encontra né os algoritmos genéticos o problema que nós vamos ver é que os métodos de busca local eles podem não encontrar a solução ótima global e encontrar uma solução ótima local e isso a gente vai

ter que tratar né de acordo com cada situação bom projeto poder entender melhor os conceitos aplicados em algoritmo de genéticos Vamos Fazer Uma Breve recordação dos conceitos de biologia né quando a gente pensa né em dois indivíduos e uma espécie qualquer numa reprodução sexuada que ocorre que os gametas né do masculino e o gameta feminino né dessas espécies na reprodução eles vão se dividirem né e os filhos formados vão ter parte do gameta do pai e parte do gameta da mãe então isso vai ser esse conceito vai ser utilizado também na solução do algoritmo genéticos

e também né pela lei da evolução das espécies e daven né os indivíduos mais aptos é aqueles que tem mais chance de gerar descendentes Então nós vamos associar uma função de aptidão também chamada de fitness indivíduo que vai me indicar o quão hábito aquele indivíduo está para gerar descendentes e a maioria dos descendentes gerados vão ser proporcionais aos indivíduos então que tem essa melhor função aptidão Além disso né além dessas questões nós vamos introduzir também a questão do crossover que seria né o cruzamento onde parte do Genoma do pai pata do Genoma da mãe são

utilizados para compor o Genoma do filho e a possibilidade de haver mutações Em algumas situações que fazem com que alguns cromossomos alguns genes ficam modificados isso tudo ocorre na natureza e a gente também implementa né os algoritmos genéticos bom Como foi dito né o algoritmo genético ele é uma sub área dos algoritmos evolucionários que é congregam todas essas situações que a gente falou né de operadores de cruzamento que a gente vai chamar de crossover operador de mutação a função de aptidão que vai me dizer o quanto que o indivíduo está a mais apto né para

sobreviver para gerar descendentes né então baseados nessas nesses conceitos é que a gente vai implementar uma solução do algoritmo genético para resolver principalmente problemas de busca bom então esse é o esquema básico né do algoritmo genético nós vamos partir de uma população Inicial que normalmente ela é gerada de forma aleatória né para que a gente não não coloque nenhum viés né nessa parte inicial a partir daí eu vou estabelecer a minha função de avaliação ou Fitness ou seja vou quantificar cada indivíduo para saber o quão apto ele é de acordo com o problema que eu

quero encontrar vou fazer a seleção dos Pais de uma forma também aleatória mas proporcional aptidão de cada pai né como a gente vai ver né os pais mais aptos são aqueles que tem mais probabilidade de gerar os seus descendentes aplico as funções né de cruzamento crossover e as funções e mutação para gerar os filhos aí eu tenho uma nova população e esse processo pode se repetir por um número n de vezes né até que eu tenho uma condição de nada que seja a quantidade de populações geradas Pode ser pré-estabelecido ou então eu chega a solução

né eu verifique né que eu atingi a solução então eu tenho essa condição de parada Esse é o esquema básico de funcionamento de um algoritmo genético então os passos principais no algoritmo genético é primeiro como que eu vou codificar a minha população né Nós vamos ver cada um desses Passos né Depois como é que eu vou definir a minha função de avaliação ou de aptidão né ou Fitness né que eu vou quantificar o quão apto um dado indivíduo né da minha amostra inicial da minha população Inicial é definir né o método da seleção dos Pais

para depois aplicar os operadores né de recombinação né seria o cruzamento crossover e o de mutação bom a população Inicial né Ela é a representação das Inicial é fundamental para o sucesso do meu algoritmo genético em geral né na grande maioria das vezes se utiliza uma representação binária né então a minha população vai ser formada de bits que vai ter a representação do problema que eu tô querendo resolver né mas poderia ser outras representações poderiam ser números decimais poderiam ser listas e regras né poderia ser Strings né então qualquer outra representação que possa traduzir a

população que eu tô trabalhando né e o problema que eu quero encontrar pode ser válida né Nós vamos ver vários exemplos né nesse sentido bom depois passo para a função de avaliação a função de avaliação aptidão né é que vai quantificar o quão hábito aquele indivíduo está nós vamos ver um exemplo né mais à frente para encontrar o máximo da função f de x = x quadrado no intervalo Era 31 bom o máximo dessa função seria né o 31 ao quadrado que vai dar 961 então a função de avaliação é simplesmente pegar um indivíduo qualquer

nesse intervalo e levar ao quadrado e ver o quão próximo ele está do máximo né ou seja o quão o quão próximo aquele valor está aumentando né até o limite máximo né que é o 31 ao quadrado tá a seleção dos pais como foi dito né tem que ter também um caráter de aleatoriedade né dado uma população Quem são os pais né os pais eu vou buscar selecionado de uma forma aleatória porém né levando em consideração a proporção de indivíduos que estão mais aptos segundo a teoria da evolução das espécies que a gente viu de

Darwin né os indivíduos mais aptos são aqueles com mais probabilidade de gerar os seus descendentes bom um método bastante utilizado seria uma roleta virtual aonde cada parte dessa roleta é proporcional a quantidade de indivíduos da minha população que tem uma aptidão maior então eu vou dividir essa roleta em pedaços né e depois eu faço né uma uma escolha randômica né É desses indivíduos né claro que a parte maior da roleta tem uma probabilidade maior de ser considerada né E com isso eu consigo privilegiar os indivíduos que tem uma melhor função de aptidão melhor Fitness né

mas também vou ter os demais indivíduos também vão ter a sua participação né nessa seleção dos Pais né então uma vez feito isso né Eu já tenho os pais como é que vai ser feito né a operação de cruzamento bom se a gente pensar que cada indivíduo né Tem N Gente é a maneira mais simples é dividir ao meio né esse conjunto de n genes metade do pai e metade da mãe né Pega a primeira metade do Pai com a primeira metade da mãe e Gero né Essa combinação gera o meu primeiro descendente meu primeiro

filho pega a segunda metade do pai a segunda metade da mãe gera o meu segundo filho mas na verdade eu posso fazer esse corte no gel em qualquer posição né então se eu tenho né um cromossomo um N Gente né o n bits né eu teria ele menos um ponto de corte então a a escolha né do ponto de corte também é um Outro fator do qual né eu posso parametrizar na construção do meu algoritmo genético bom como é que a operador de crossover né o cruzamento né como a gente já falou né metade do

dos genes do filho vem do pai a outra metade vem da mãe dependendo né do ponto de corte escolhido né se for o ponto de corte né É bem ao meio né do meu cromossomo né mas de maneira que o filho sempre vai carregar uma carga genética do pai uma carga genética da mãe né como tá no exemplo aí né foi feito um ponto de corte que não é exatamente no meio né então eu peguei o zero um do pai né e a parte final né da mãe 0010 né gerei o meu primeiro filho e

peguei as outras partes né que seria o 011 do pai e um um zero da mãe para gerar né o outro filho né Então essa é a forma né de da geração né de filhos né que seriam as novas populações do meu algoritmo genético pois a gente tem o gene mutação a mutação ela corre na natureza né E quando a gente pensa em mutação né na verdade não é só uma mutação que pode acrescentar elementos negativos né ou de aptidão negativo ao indivíduo né eu posso ter mutações que possam melhorar o indivíduo né isso ocorre

na natureza né só que a taxa de mutação ela deve sempre ser levada muito baixa né em geral se usa de um a no máximo cinco por cento dos da probabilidade de se ocorrer alguma mutação em algum jegue e essa mutação implica né no caso uma representação binária né deu mudar um Beat que normalmente seria um ele passa a ser zero Bito que normalmente seria ser zero ele passa a ser um né então eu aplico essa probabilidade de mutação em cada bit do da população gerada né E aí eu vou ter em alguns casos né

é essa população modificada né em função do operador de mutação bom e a condição de parada né a condição de parada né ela pode ser estabelecida né quando eu chegar na condição na solução desejada né ou eu posso também estabelecer a partir de n gerações né a partir da população Inicial né quando eu não tenho exatamente uma uma noção Clara de qual é o a solução desejada Então se a gente voltar o nosso algoritmo né eu vou ter a nossa população Inicial aplica os operadores né de seleção para selecionar os pais com melhor aptidão depois

eu faço os operadores né de cruzamento de mutação gera os filhos né Tem uma nova população e repito e vou vendo seus satisfaço a condição né que pode ser né a solução alcançada ou chega um limite de populações Gerais Vamos ver um exemplo né que é aquele que a gente já citou né de encontrar o máximo da função f de x igual a x quadrado no intervalo de 0 a 31 o máximo evidentemente vai ser 31 ao quadrado que vai dar 961 né Então essas são as condições né o X é inteiro e eu tô

nesse intervalo de 0 até 31 tá então a representação escolhida e vai ser para cada número desse intervalo vai ser sua representação binária né ou seja o zero vai ser 0000 né o 31 vai ser representado por cinco números juntos e a função de aptidão vai ser simplesmente aplicar né f de x ao quadrado então f de três Vai dar 9 né com isso a gente escolhe aleatoriamente a nossa população Inicial Então tá ali meus quatro cromossomos iniciais correspondente ao valor numérico de 25 15 14 10 escolhido aleatoriamente aplico a função de aptidão para cada

um ou seja leva ao quadrado aí eu vou ter uma proporcionalidade desses valores em função do total né dos valores alcançados ou seja os 625 corresponde a 54,54 por 100 né da fatia correspondente e os demais eu faço a mesma coisa né então eu calculo essa proporcionalidade né de cada um desses dessas funções aptidão E com isso eu uso essa probabilidade de seleção para que para que eu use na roleta né então a minha roleta ela vai ficar né com uma parcela maior para o cromossomo A1 né uma parcela um pouco menor para o cromossomos

a dois e assim por diante faço a seleção dos Pais em função dessa proporcionalidade né E aí eu vou começar a aplicar os operadores e crossover mutação nesse caso aqui foi escolhido um ponto de cota aleatório né Eu tenho um cromossomo 5 a partir do terceiro do terceiro cromossomo com 5 bits a partir do terceiro bita eu fiz o ponto de corte aplica o crossover e gera os filhos né Então essa é a maneira que nós vamos gerar os filhos né e a mutação nós vamos usar uma taxa de em torno de 1% para mudar

algum Beat né então antes da Mutação eu podia ter um cromossomo 01101 depois da Mutação eu mudei apenas o segundo bit né de um passou para zero fiquei 00101 né bom feito isso né A minha primeira geração é a partir daqueles pais que a gente selecionou aplica o crossover Então faça o cruzamento metade do gênero do Pai com metade do gênero da mãe aplica a mutação e eu tenho os filhos gerados que seriam a minha população então a minha primeira geração é a minha primeira geração de filhos gerados aí eu aplico novamente o fitness a

função de avaliação para os filhos Note que agora os filhos que eu tenho gerados tem valores diferentes e função de avaliação dos pais deles né esses filhos gerados são 27 25 23 né e as respectivos valores do f de x igual a x ao quadrado faço a probabilidade de seleção aplica a roleta novamente vou ter assim a minha segunda geração Vocês estão vendo que os filhos vão tão eles eles vão se aproximando do meu valor máximo que é o 31 novamente aplica a probabilidade de seleção gera a terceira geração né Aqui nós vamos chegar até

a quinta geração né E vocês viram aí que na quinta geração eu já tô me aproximando da solução que é o valor de x igual a 31 e a função f de x 961 que é o ao quadrado ou seja né eu cheguei né ao ponto de máximo né onde a maioria da população me indica né esse valor né de 31 com 31 ao quadrado 961 que é o máximo desejado da função Então é assim que a gente vai aplicar algoritmos genético para resolver problemas e busca né algumas questões importantes a representação dos indivíduos evidentemente

é importante né alguns parâmetros que a gente viu né o tamanho da população a taxa de mutação né como que eu vou fazer o crossover se eu vou fazer num ponto fixo ou não né o critério de parada e a função de avaliação que nesse caso foi bem simples né mas em outros em outras situações eu posso ter que definir uma função um pouco mais complexa né a vantagem dos algoritmos genético é que a medida que eu vou gerando novas populações ele tende a melhorar a solução né E quanto mais conhecimento a gente tendo problema

também posso ajustar melhor esses parâmetros que a gente viu os algoritmos genéticos podem ser usado em vários tipos de aplicação né normalmente são problemas e busca né Mas a gente pode identificar em problemas e busca alocação de tarefas seleção de rotas né e geralmente eles são muito bons quando a solução convencional não traz um bom resultado né e o algoritro genético ele tem essa característica né de ser disparado né de uma forma paralela Ou seja eu Gero várias populações né e vou avaliando o quanto que ela tá próxima para solução do meu problema né então

chegamos ao final da aula de hoje até a próxima aula [Música] [Música]