Introdução ao Algoritmo Genético - Parte 1

ferraz que eu faço engenharia da computação da puc rio e hoje vou falar um pouquinho sobre o algoritmo genético mas então o que é um ganho de otimização baseado em evolução natural como funciona o processo de seleção natural de se basear para construir um algoritmo que vai encontrar soluções ótimas por várias gerações assim como acontece na natureza tipo de problema esse algoritmo é capaz de resolver a gente tem que fazer uma viagem do rio até o pará passando por são paulo bahia e depois voltando até o rio tudo isso no mínimo possível esse problema chama-se

é capaz de resolver forma eficiente todos os dias pode realmente tirar muita aplicação dos algoritmos mas então como é que a gente vai implementar essa seleção natural nosso algoritmo bom começar assim penso que existem duas espécies de besouro brancos eles vivem em uma floresta escuras como o preto tem uma cor mais parecido com o do ambiente ele foi melhor e assim têm mais chance de sobreviver e se reproduzir do que os brancos assim define um conjunto de indivíduos sobrevivem sempre os melhores adaptados até aí ok mas então como é que surge novos envios com características

diferentes dos originais isso se deve aos processos de crossover e mutação crossover é responsável por misturar o gênio dos pais de maneira aleatória gerando novos indivíduos com características que são a mistura das características dos pais já a alimentação é responsável por alterar um pouco os valores de alguns gente desse indivíduo de forma a adicionar variedade dentro da população poderão inclusive criar novas características que fazem o indivíduo se tornar melhor adaptado do que se ele não tivesse sofrido a amputação é esse ponto você deve estar se perguntando mas o que tem a ver com programação e

como é que vai ajudar a resolver um problema na verdade tem tudo a ver cada fator que eu comentei anteriormente a fazer parte do nosso algoritmo genético mas primeiro então precisamos mantê-la como vai ser o nosso problema no caso do besouro podemos modelar um besouro como sendo um conjunto de três variáveis cujos valores variam de 0 a 200 e 55 cada variável representando um valor r gb do besouro essa representação é válida porque a única informação que é relevante para o nosso algoritmo é se o tesouro tem cor mais claro mais escura assim representando a

cor do besouro a gente já tem toda a informação que a gente precisa para dizer se ele vai ter uma boa adaptabilidade ou não repare também que aqui a gente poderia modelar esse tesouro tendo três cores porque se você olhar o desenho tem três tons de cinza diferente mas por simplicidade vamos apresentar como se só tivesse uma cor talvez aquele cinzas do corpo num contexto algoritmo genético existem nome para cada um dos fatores que estou comentando o besouro ele vai ser um indivíduo e o conjunto de vários tesouros vai formar uma população neste indivíduo a

gente tinha aquelas três variáveis que vão descrever o indivíduo né nosso caso o valor de r gb esse conjunto de variáveis vai ser chamado o genoma do enredo que aquilo que descreve cada variável vai ter o nome de gênio ou cromossomo e o valor que essa variável assumir vai se chamar a lela preocupar muito com esse nome então agora começamos um algoritmo primeiro temos uma população não um conjunto de indivíduos convênios aleatório ou seja no nosso caso valores de rgb aleatório em seguida a gente deve submeter-se cedidos a uma avaliação para ver o quão bem

adaptados eles estão dentro desse contexto essa avaliação deve ser feita para uma função matemática chamada fitness funk é desenvolvida pelo programador do algoritmo a fitness function tem que ser modelar de uma maneira que faça sentido é compensando os indivíduos que têm maior adaptabilidade e punindo aqueles que não se adaptam bem no nosso caso a gente tem que recompensar os indivíduos com cor mais escura ou seja a receber mais baixo e punir aqueles que têm cor mais clara ou seja corrigido mais alto agora que temos nossa fitness function podemos avaliar todo sempre da população e então

selecionar aqueles que têm melhor adaptabilidade ou seja valores de fitas funks mais altos os vídeos selecionados vão seus pais e um novo indivíduo que pode ser criado por meio do crossover do gênio destes dois uma vez que temos um crossover podemos então realizar mutação nesse vida adicional no maior variedade dentro da população fazemos esse processo de gerar novos indivíduos até que tenhamos uma quantidade suficiente para gerar uma nova geração essa nova geração vai estar melhor adaptado do que a geração anterior a gente pode então repetir processo criando novas gerações até o momento em que a

gente tiver satisfeito com os indivíduos que a gente chegou isso que acabamos de ver esta cultura básica de todo o algoritmo genético ainda assim a performance desse algoritmo ea capacidade de chegar a soluções ótimas depende e como fazemos cada uma das etapas dentro desse processo no próximo vídeo então eu vou comentar cada uma dessas etapas detalhadamente para conseguirmos implementar o algoritmo