Explicação Básica Sobre Algoritmos Genéticos com Exemplo Prático

o olá meu nome é renée e este é um trabalho sobre algoritmos genéticos para cadeira de inteligência artificial no curso de ciência da computação da ufrn o algoritmo genético é uma técnica de busca muito utilizada para achar soluções aproximadas em problemas de otimização e buscar tal conceito foi fundamentado principalmente pelo cientista e professor americano johnny harry holland autor de muitas obras sobre sistemas adaptativos complexos entre elas adaptation in natural and artificial systems and order ou adaptation beauty complex it e emergência from various water os algoritmos genéticos são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas pela biologia evolutiva como hereditariedade mutação e seleção natural e cruzamento segundo a teoria evolucionária de charles darwin os seres vivos sofrem mutações e os mais aptos sobreviverão então investigar como ocorre tal seleção natural efetuar uma simulação dela permite gerar dados com as características por nós desejadas de vida é assim inspiração muitos termos utilizados nos algoritmos genéticos vem da própria biologia primeiro que veremos será o conceito de o som que nada mais é do que a representação de um conjunto de indivíduos indivíduos que por sua vez serão representados por cromossomos cada cromossomo é formado por um array que contém todas as suas características características essas representadas por genes a cada número dentro do rei é um gene que traz uma informação sobre aquela característica do indivíduo os genes podem ser representados diversas formas como por exemplo decimal binário inteiro muitas outras nesse caso que está aparecendo na tela ele está na forma binária é uma das aplicações mais conhecidas para algoritmos genéticos é o problema do caixeiro-viajante ele pode ser resolvido com força bruta porém tal solução tem crescimento fatorial ou seja 4 fatorial para quatro cidades por exemplo sendo assim ele escalaria muito rápido um algoritmo genético nós podemos reduzir o seu tempo de execução e aqui nós temos as principais características de um algoritmo genético os algoritmos genéticos baseavam-se em uma codifi cação do conjunto das soluções possíveis e não nos parâmetros da utilização esse e os resultados são apresentados com uma população de soluções e não como uma solução única no caso a população final eles não necessitam de nenhum conhecimento derivado do problema apenas de uma forma de avaliação do resultado e usam transações probabilísticas e não regras de tênis agora que nós já vimos um pouco da história dos algoritmos genéticos suas características termos de aplicações vamos ao passo a passo de como eles funcionam primeiro passo é o algoritmo genético é gerada a sua população inicial ela pode ser gerada tanto de forma randômica quanto de forma holística e na inicialização randômica são atribuídos valores aleatórios a cada gene dos cromossomos já na inicialização heurísticas são atribuídos valores que julgamos estar mais próximos da solução uma forma de dar uma certa ajuda algoritmo no início caso já temos alguma ideia de qual é a solução após gerado a população vamos para etapa de avaliação da população avaliação da população vai depender do objetivo que queremos atingir o algoritmo avaliação é feita medindo com próximo cada cromossoma chegou de um resultado considerado óptico baseado nisso atribuímos a ele o valor chamado fitness os cromossomos com melhor fitness serão considerados os mais aptos a sobreviver e continuar no algoritmo e aqui podemos ver um exemplo de um modelo básico de avaliação onde fitness é diferença do resultado gerado pelo cromossoma com o modelo ao nesse caso quanto melhores referências melhor logo quanto menor o fitness melhor feita avaliação precisamos saber se a solução foi encontrada e existem várias maneiras de sabemos a resposta para essa pergunta dentre elas podemos estabelecer um número fixo de gerações que serão produzidos pelo crítico nós podemos também estabelecer um valor mínimo a ser atingido pelo fitness por último podemos comparar a população atual com a anterior e parar caso a diferença entre elas começam a ser em cima significa que o algoritmo chegou a um estado de estagnação não dessa forma conseguiremos saber se a solução foi encontrada e se a resposta for sim significa que podemos parar a execução do algoritmo porém se a resposta for não devemos continuar para o próximo passo o qual chamamos de seleção onde selecionamos os pais da próxima população a seleção pode ser feita de diversas formas essas não são as únicas que existem mas eu vou citar apenas essas três primeira delas é a seleção aleatória onde você simplesmente seleciona indivíduos de forma randômica depende muito do que você quer fazer com seu organismo mas geralmente se usa algum parâmetro para selecionar os pais como na seleção por torneio nesse jeito selecionamos um número n de indivíduos da população aleatoriamente para formar uma subpopulação temporária deste grupo ou indivíduo dependerá de uma probabilidade de cá definida previamente e esse é um exemplo básico de implementação deixar o egito onde dois indivíduos são colocados para batalhar melhor indivíduo nesse caso tem setenta e cinco porcento de chance de vitória esse é o método mais utilizado pois oferece a vantagem de não exigir que a comparação seja feita entre todos os indivíduos da população por último temos um método da roleta e nele cada indivíduo da população representada na roleta proporcionalmente ao seu instinto e aptidão assim para indivíduos com alta aptidão é dado uma porção maior da roleta enquanto as indivíduos de aptidão mais baixa é dado uma porção relativamente menor essa forma quem tem melhor fitness tem mais chance de ganhar quando a roleta rodada e aqui temos um exemplo básico de algoritmo de seleção de roleta o valor aleatório entre 0 e somatório de todos os fitness é sorteado então os indivíduos da população são percorridos sequencialmente acumulando em écio fitness de cada indivíduo percorrido momento que o valor de s passagem dr indivíduo atual é selecionada simulando assim uma roleta e após selecionados os pais vamos para etapa de cruzamento é através do cruzamento são criados novos indivíduos misturando características de dois indivíduos paz essa mistura é feita a tentando imitar com altos níveis de abstração a reprodução de genes em células trechos das características de um indivíduo são trocados pelo trecho equivalente do outro resultado dessa operação é um indivíduo que tem a possibilidade de ter combinado as melhores características dos indivíduos paz dois tipos de cruzamento muito utilizados são o cruzamento em um ponto e um dois pontos cruzamento em um ponto seleciona-se aleatoriamente um ponto de corte el-rei as informações genéticas dos cromossomos a partir desse ponto são trocadas gerando dois descendentes diferentes e e com dois pontos de cruzamento um dos descendentes fica com a parte central de um dos países e as partes extremas do outra e vice-versa é e após o cruzamento vamos para o processo de mutação como de costume existem várias formas de mutação também mas a mais utilizada é mutação uniforme nela fazemos uma pequena modificação aleatória em alguma característica do cromossomo mas não queremos fazer mutações muito grandes para não nos afastarmos sem querer da resposta e geralmente após a fase de mutação repetimos novamente todo o processo até encontrarmos a solução e agora vamos ao nosso estudo de caso onde temos o seguinte problema dada a seguinte equação de primeiro grau com os x eo y fornecido pelo usuário quais valores os pesos precisam assumir para que a equação seja verdadeira para resolver esse problema iremos utilizar os seguintes operadores a inicialização aleatória o fitness ser a diferença absoluta entre o cromossomo e o modelo a seleção será feita considerando apenas o melhor fitness cruzamento em um ponto e mutação uniforme com probabilidade de um por cento e agora as referências e de onde esses dados foram retirados e vamos para a parte da implementação e aí é bom aqui temos o algoritmo que vai resolver o problema em questão e no início tem uma tem instruções rápidas de como executar o algoritmo para quem quiser executar ele e aqui nós temos o valor de y e aqui nós temos o valor do x a seguir é declarado o arlei onde serão colocados os pesos oi e o número de cromossomos por população então a primeira população e iniciada iniciado um array vazio e então ele é preenchido com números aleatórios de -4 até 4 e aqui nós temos a precisão a precisão vai ser o nosso a nossa condição de parada é o número mínimo que nós queremos que o fitness atinja e o número máximo de gerações que é caso a caso a nossa precisão seja muito seja muito alta pode acontecer da gente conseguir das gerações ficarem sendo geradas por muito tempo e não conseguirem atingir o fitness apropriada então nós vamos colocar um limite de 1000 para essas gerações e aqui o número de pais que serão combinados para gerarem descendentes e nós iniciamos calculando a aptidão da população atual com a função top fitness e essa função é está aqui no modo lugar oi e ela basicamente calcula essa equação aqui com base nos pesos do cromossomo atual o e calcula a diferença do y geraldo pelo cromossoma e com o y que queremos atingir bom então essa diferença absoluta porque não importa se é uma diferença para cima ou para baixo vai ser o fitness atribuída a olá seguindo olá seguindo da avaliação nós temos aqui a nossa condição de parada então aqui nós chegamos se o melhor fitness da da população é menor do que a precisão se for ele vai interromper o loop nós temos a nossa resposta e continuando aqui nós temos a seleção dos dos cromossomos mais rápidos para gerarem seus descendentes na função selleck matchpool eu acho são ser leque meio tempo irá selecionar os cromossomos que tem o melhor fitness no caso o menor fixas já é passado um loop no caso o número de paz é quatro e ele vai pegar os quatro que tem o menor e vai retornar esses pais tô passando da etapa de seleção vamos para etapa de crossover a netapp de crossover nós vamos primeiro selecionar o ponto onde os cromossomos serão divididos nesse caso o ponto será sempre no meio interessam e serão divididos em partes iguais mas lembrem-se que esse ponto pode ser escolhido randomicamente e vamos cruzar os pais de forma circular então o pai zero vai cruzar com um ou um vai cruzar com o 2 o 2 com 3 ou três com 0 até que seja gerado o número de descendentes desejados e aqui nós pegamos a primeira metade do primeiro pai segunda metade a primeira mensagem do primeiro pai a segunda metade do segundo pai e retornamos um descendente e após o cruzamento dos pais nós vamos realizar a mutação a anotação consiste em gerar um número aleatório de menos um e somar esse número ao quarto gene de cada cromossomo e também esse o gene que é alterado pode ser qualquer um pode ser um gene randômico também esse caso nós estamos utilizando quatro e após isso nós vamos criar a nova população como a os descendentes correm o risco de não serem melhores que os pais nós vamos manter os quatro os quatro melhores cromossomos da população anterior e adicionar os quatro descendentes gerados nesse nessa nesse look e vamos voltar desde o início e isso vai ser executado de novo e de novo então até que a solução seja encontrada quando a solução encontrada aqui ele encontra o aquele faz o fitness da última geração aquele encontra o melhor fitness da última geração e printa tudo aquele ele mostra qual é o y gerado afinal que vai ser um y perto de 600 né com no mínimo no no máximo 0,1 de diferença 600 e vamos vamos ver agora como é a execução e aí e aí nós podemos ver que com a precisão de 0. 1 foram geradas 145 gerações o melhor fitness dos cromossomos foi 0. 0.

6 0. 06 e o valor final gerado do y foi 599.