VII. Parâmetros de GA Crossover e Mutação Probabilidade Existem dois parâmetros básicos de probabilidade de cruzamento GA e probabilidade de mutação. A probabilidade de Crossover diz com que frequência será executado o crossover. Se não houver crossover, a prole é uma cópia exata dos pais. Se houver um crossover, a prole é feita a partir de partes do cromossomo dos pais. Se a probabilidade de crossover for 100. Então toda prole é feita por crossover. Se for 0. Toda a nova geração é feita a partir de cópias exatas de cromossomos da população antiga (mas isso não significa que a nova geração seja a mesma). O Crossover é feito com a esperança de que os novos cromossomos tenham boas partes dos cromossomos antigos e talvez os novos cromossomos sejam melhores. No entanto, é bom deixar parte da população sobreviver para a próxima geração. A probabilidade de mutação diz com que frequência as partes do cromossomo são mutadas. Se não houver mutação, a prole é levada após o cruzamento (ou cópia) sem qualquer alteração. Se a mutação for realizada, uma parte do cromossomo é alterada. Se a probabilidade de mutação for 100. O cromossomo inteiro é alterado, se for 0. Nada é alterado. A mutação é feita para evitar a queda de GA em extremos locais, mas isso não deve ocorrer com muita frequência, porque o GA, na verdade, mudará para pesquisa aleatória. Outros parâmetros Existem também alguns outros parâmetros da GA. Um parâmetro importante também é o tamanho da população. O tamanho da população diz quantos cromossomos estão em população (em uma geração). Se houver muito poucos cromossomos, a GA tem algumas possibilidades para realizar o cruzamento e apenas uma pequena parte do espaço de busca é explorada. Por outro lado, se houver muitos cromossomos, GA fica mais lento. A pesquisa mostra que, após algum limite (que depende principalmente da codificação e do problema), não é útil aumentar o tamanho da população, porque não resolve o problema mais rapidamente. Algumas recomendações para todos os parâmetros podem ser encontradas em um dos seguintes capítulos. Exemplo Aqui você pode ver um exemplo semelhante ao anterior. Mas aqui você pode tentar mudar a probabilidade de cruzamento e mutação. Você também pode controlar o elitismo. No gráfico abaixo, você pode ver o desempenho da GA. O vermelho é a melhor solução, o azul é o valor médio (aptidão física) de toda a população. Tente alterar parâmetros e veja como a GA se comporta. Aqui está o applet, mas o seu navegador não suporta Java. Se você quiser ver applets, verifique os requisitos do navegador. Pergunta: Se você tentar aumentar a probabilidade de mutação para 100, GA começará a se comportar muito estranho, quase como se a probabilidade de mutação fosse 0. Você sabe por que você pode usar uma dica e se você ainda não sabe, olhe a solução Genética Algoritmos foram inventados para imitar alguns dos processos observados na evolução natural. Muitas pessoas, incluindo os biólogos, ficam surpresas com o fato de que a vida no nível de complexidade que observamos poderia ter evoluído no tempo relativamente curto sugerido pelo registro fóssil. A idéia com GA é usar esse poder de evolução para resolver problemas de otimização. O pai do Algoritmo Genético original foi John Holland, que o inventou no início da década de 1970. O que é Algoritmos Genéticos Os Algoritmos Genéticos (GAs) são algoritmos de pesquisa heurística adaptativa baseados nas idéias evolutivas de seleção natural e genética. Como tal, eles representam uma exploração inteligente de uma pesquisa aleatória usada para resolver problemas de otimização. Embora randomizados, os GAs não são aleatórios, em vez disso, eles exploram informações históricas para direcionar a pesquisa para a região de melhor desempenho dentro do espaço de busca. As técnicas básicas dos GAs são projetadas para simular processos em sistemas naturais necessários para a evolução, especialmente aqueles que seguem os princípios estabelecidos pela Charles Darwin de sobrevivência dos mais aptos ... Uma vez que na natureza, a competição entre os indivíduos por recursos escassos resulta no mais apto Indivíduos dominando os mais fracos. Por que os algoritmos genéticos é melhor do que o AI convencional na medida em que é mais robusto. Ao contrário dos sistemas de AI mais antigos, eles não quebram facilmente mesmo que as entradas mudassem ligeiramente, ou na presença de ruído razoável. Além disso, ao pesquisar um grande espaço de estados, espaço de estado multimodal ou superfície n-dimensional, um algoritmo genético pode oferecer benefícios significativos sobre pesquisas mais típicas de técnicas de otimização. (Programação linear, heurística, profundidade-primeiro, respiração-primeiro e praxis.) Algoritmos genéticos Visão geral Os GAs simulam a sobrevivência do mais apto entre os indivíduos durante a geração consecutiva para resolver um problema. Cada geração consiste em uma população de cordas de caracteres que são análogas ao cromossomo que vemos no nosso DNA. Cada indivíduo representa um ponto em um espaço de busca e uma possível solução. Os indivíduos da população são então criados para passar por um processo de evolução. Os GAs são baseados em uma analogia com a estrutura genética e o comportamento dos cromossomos dentro de uma população de indivíduos que usam os seguintes fundamentos: indivíduos em uma população competem por recursos e companheiros. Os indivíduos mais bem sucedidos em cada competição produzirão mais descendentes do que os indivíduos que apresentam um desempenho fraco. Os genes de indivíduos bons se propagam em toda a população de modo que dois bons pais às vezes produzam descendentes que são melhores do que qualquer dos pais. Assim, cada geração sucessiva se tornará mais adequada ao seu ambiente. Espaço de busca Uma população de indivíduos é mantida dentro do espaço de busca para uma GA, cada uma representando uma possível solução para um determinado problema. Cada indivíduo é codificado como um vetor de comprimento finito de componentes, ou variáveis, em termos de algum alfabeto, geralmente o alfabeto binário. Para continuar a analogia genética, esses indivíduos são comparados aos cromossomos e as variáveis são análogas aos genes. Assim, um cromossomo (solução) é composto de vários genes (variáveis). Uma pontuação física é atribuída a cada solução que representa as habilidades de um indivíduo para competir. É procurado o indivíduo com a pontuação de aptidão ideal (ou geralmente ideal). O GA pretende usar a criação seletiva das soluções para produzir descendência melhor do que os pais, combinando informações dos cromossomos. O GA mantém uma população de n cromossomos (soluções) com valores de aptidão associados. Os pais são selecionados para se acasalar, com base em sua condição física, produzindo descendentes através de um plano reprodutivo. Consequentemente, as soluções altamente adequadas recebem mais oportunidades de reprodução, de modo que a prole herdar características de cada pai. À medida que os pais se aproximam e produzem descendentes, deve ser feita uma sala para os recém-chegados, uma vez que a população é mantida num tamanho estático. Os indivíduos da população morrem e são substituídos pelas novas soluções, eventualmente criando uma nova geração, uma vez que todas as oportunidades de acasalamento na população antiga foram esgotadas. Desta forma, espera-se que, ao longo das gerações sucessivas, as melhores soluções irão prosperar enquanto as soluções menos adequadas desaparecerem. Novas gerações de soluções são produzidas contendo, em média, genes mais bons do que uma solução típica em uma geração anterior. Cada geração sucessiva conterá mais soluções parciais boas do que as gerações anteriores. Eventualmente, uma vez que a população convergiu e não está produzindo descendentes visivelmente diferentes daquelas em gerações anteriores, o próprio algoritmo deve ter convergido para um conjunto de soluções para o problema em questão. Detalhes da implementação com base na seleção natural Depois que uma população inicial é gerada aleatoriamente, o algoritmo evolui através de três operadores: seleção que equivale à sobrevivência do cruzamento mais adequado, o que representa o aparecimento entre mutação individual que introduz modificações aleatórias. 1. Seleção Ideia da chave do operador: dar prévia a melhores indivíduos, permitindo que eles transmita seus genes para a próxima geração. A bondade de cada indivíduo depende da sua condição física. A aptidão física pode ser determinada por uma função objetiva ou por um julgamento subjetivo. 2. Crossover Operator Prime fator distinto de GA de outras técnicas de otimização Dois indivíduos são escolhidos da população usando o operador de seleção Um site de cruzamento ao longo das cadeias de bits é escolhido aleatoriamente Os valores das duas cadeias são trocados até este ponto Se S1000000 e s2111111 E o ponto de cruzamento é 2, então S1110000 e s2001111 Os dois novos descendentes criados a partir deste acoplamento são colocados na próxima geração da população Ao recombinar porções de indivíduos bons, esse processo provavelmente criará pessoas ainda melhores 3. Operador de Mutação Com algum baixo Probabilidade, uma parte dos novos indivíduos terá alguns de seus pedaços virados. O objetivo é manter a diversidade dentro da população e inibir a convergência prematura. A mutação por si só induz uma caminhada aleatória através do espaço de busca. Mutação e seleção (sem crossover) criam algoritmos paralelos, tolerantes ao ruído e escalada. Efeitos dos operadores genéticos. Usar a seleção sozinho tenderá a preencher a população com cópias do melhor indivíduo da População A utilização de operadores de seleção e crossover tenderá a fazer com que os algoritmos convergem em uma solução boa, mas subóptima. Usar a mutação sozinha induz uma caminhada aleatória através do espaço de busca. Usando a seleção e a mutação criam um algoritmo de escalada de parrallel, tolerante ao ruído, os Algoritmos inicializam aleatoriamente a população (t) determinam a aptidão da população (t) repitam pais selecionados da população (t) realizam cruzamentos nos pais criando população (t1) realizam mutação de A população (t1) determina a adequação da população (t1) até que o melhor indivíduo seja suficientemente bom. Na subseção anterior, afirmou-se que, através das operações de seleção, cruzamento e mutação, a GA convergirá em gerações sucessivas para o global (ou quase global) Optium. Por que essa operação simples deve produzir uma tecnologia rápida, útil e robusta, é em grande parte devido ao fato de que os GAs combinam direção e chance na busca de forma eficaz e eficiente. Uma vez que a população contém de forma implícita muito mais informações do que apenas as pontuações de aptidão individuais, os GAs combinam a boa informação escondida em uma solução com boa informação de outra solução para produzir novas soluções com boa indomação herdada de ambos os pais, inevitavelmente (espero) liderar a otimização dos engenhos. A capacidade do algoritmo para explorar e explorar simultaneamente, uma crescente quantidade de justificativa teórica e uma aplicação bem-sucedida em problemas do mundo real reforçam a conclusão de que as AG são uma técnica de otimização robusta e robusta. Uma introdução aos Algoritmos Genéticos. Com imprensa editada por Melanie Mitchell Algoritmos genéticos em engenharia e ciência da computação editados por G. Winter. Et al .. c1995 Fundamentos de algoritmos genéticos editados por Gregory J. E. Rawlins. C1991 Para detalhes sobre aplicações de algoritmos de genética, consulte o meu parceiro, artigo de Chun s.
No comments:
Post a Comment