VII. Parâmetros de GA Crossover e Probabilidade de Mutação Existem dois parâmetros básicos de GA - crossover probabilidade e probabilidade de mutação. Crossover probabilidade diz quantas vezes será crossover realizada. Se não houver crossover, descendência é 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 a 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 é a mesma). Crossover é feito na esperança de que novos cromossomos terão boas partes de cromossomos antigos e talvez os novos cromossomos será melhor. No entanto, é bom deixar alguma parte da população sobreviver à próxima geração. Probabilidade de mutação diz quantas vezes serão partes do cromossomo mutado. Se não houver mutação, a descendência é tomada após cruzamento (ou cópia) sem qualquer alteração. Se a mutação é realizada, parte do cromossomo é alterado. Se a probabilidade de mutação for 100. Todo o cromossomo é alterado, se for 0. Nada é mudado. A mutação é feita para evitar a queda de GA em extremos locais, mas isso não deve ocorrer com muita freqüência, porque então a GA mudará na busca aleatória. Outros Parâmetros Existem também alguns outros parâmetros de GA. Um parâmetro importante também é o tamanho da população. O tamanho da população diz quantos cromossomos estão na população (em uma geração). Se houver muito poucos cromossomos, GA tem algumas possibilidades para realizar crossover e apenas uma pequena parte do espaço de pesquisa é explorada. Por outro lado, se houver demasiados cromossomos, GA desacelera. Pesquisas mostram 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 torna a solução do problema mais rápida. Algumas recomendações para todos os parâmetros podem ser encontradas em um dos capítulos a seguir. Exemplo Aqui você pode ver um exemplo semelhante ao anterior. Mas aqui você pode tentar mudar crossover e probabilidade de mutação. Você também pode controlar o elitismo. No gráfico abaixo você pode ver o desempenho do GA. O vermelho é a melhor solução, o azul é o valor médio (aptidão) de toda a população. Tente alterar os parâmetros e veja como o GA se comporta. Aqui está o applet, mas o seu navegador não suporta Java. Se você quiser ver os 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 é 0. Você sabe por que Você pode usar uma dica e se você ainda não sabe, olhe para a solução Genética Os algoritmos foram inventados para imitar alguns dos processos observados na evolução natural. Muitas pessoas, incluindo os biólogos, ficam surpresos 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 dos anos 70. O que é Algoritmos Genéticos Os Algoritmos Genéticos (GAs) são algoritmos adaptativos de busca heurística baseados nas idéias evolutivas de seleção natural e genética. Como tal, 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 de forma alguma aleatórios, em vez disso, exploram informações históricas para direcionar a pesquisa para a região de melhor desempenho dentro do espaço de pesquisa. 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 primeira vez por Charles Darwin de sobrevivência do mais apto. Como na natureza, a competição entre indivíduos por recursos escassos resulta no mais apto Indivíduos dominando sobre os mais fracos. Por que Algoritmos Genéticos É melhor do que o AI convencional em que é mais robusto. Ao contrário dos sistemas mais antigos de IA, eles não se quebram facilmente mesmo se os inputs mudaram ligeiramente, ou na presença de ruído razoável. Além disso, ao pesquisar um grande estado-espaço, espaço de estados multi-modal, ou superfície n-dimensional, um algoritmo genético pode oferecer benefícios significativos sobre a busca mais típica de técnicas de otimização. (Programação linear, heurística, profundidade-primeiro, respiração-primeiramente, e praxis.) Algoritmos genéticos Vista geral GAs simular a sobrevivência do mais apto entre indivíduos durante a geração consecutiva para resolver um problema. Cada geração é constituída por uma população de cordas de caracteres que são análogas ao cromossomo que vemos em 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 levados a passar por um processo de evolução. As AGs baseiam-se numa analogia com a estrutura genética eo comportamento dos cromossomas dentro de uma população de indivíduos usando as seguintes fundações: Indivíduos em uma população competem por recursos e companheiros. Aqueles indivíduos mais bem sucedidos em cada competição produzirá mais prole do que aqueles indivíduos que executam mal. Genes de bons indivíduos se propagam por toda a população de modo que dois bons pais às vezes produzem filhos que são melhores do que qualquer dos pais. Assim, cada geração sucessiva se tornará mais adequada ao seu ambiente. Espaço de Pesquisa Uma população de indivíduos é mantida dentro do espaço de busca para um GA, cada um 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 a cromossomos e as variáveis são análogas aos genes. Assim, um cromossoma (solução) é composto por vários genes (variáveis). Uma pontuação de fitness é atribuída a cada solução que representa as habilidades de um indivíduo para competir. O indivíduo com a pontuação ótima (ou geralmente ótima) de fitness é procurada. A GA tem como objetivo usar a criação seletiva das soluções para produzir prole 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 acasalar, com base em sua aptidão, produzindo prole através de um plano reprodutivo. Consequentemente, as soluções altamente aptas têm mais oportunidades de reproduzir, de modo que a prole herda características de cada pai. À medida que os pais se acasalam e produzem descendência, deve haver espaço para os recém-chegados, uma vez que a população é mantida num tamanho estático. Os indivíduos na população morrem e são substituídos pelas novas soluções, acabando por criar uma nova geração, uma vez que todas as oportunidades de acasalamento na população idosa foram esgotadas. Desta forma, espera-se que, ao longo das sucessivas gerações, melhores soluções prosperem enquanto as soluções menos adequadas desaparecem. Novas gerações de soluções são produzidas contendo, em média, mais bons genes do que uma solução típica em uma geração anterior. Cada geração sucessiva conterá mais boas soluções parciais do que as gerações anteriores. Eventualmente, uma vez que a população tem convergido e não está produzindo descendência visivelmente diferente daqueles em gerações anteriores, o algoritmo em si é dito ter convergido para um conjunto de soluções para o problema em questão. Detalhes de Implementação Baseados na Seleção Natural Após uma população inicial ser gerada aleatoriamente, o algoritmo evolui através de três operadores: seleção que equivale à sobrevivência do crossover mais apto que representa o acoplamento entre mutações individuais que introduz modificações aleatórias. 1. Seleção Operador idéia-chave: dar prefrence a melhores indivíduos, permitindo-lhes passar os seus genes para a próxima geração. A bondade de cada indivíduo depende da sua aptidão. A aptidão pode ser determinada por uma função objetiva ou por um julgamento subjetivo. 2. Operador de Crossover Primeiro fator diferenciado 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 local de cruzamento ao longo das seqüências de bits é escolhido aleatoriamente Os valores das duas cordas 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 acasalamento são colocados na próxima geração da população Por recombinar porções de indivíduos bons, este processo é susceptível de criar indivíduos ainda melhores 3. Operador de Mutação Com algumas baixas Uma parte dos novos indivíduos terão alguns de seus bits invertidos. Sua finalidade é manter a diversidade dentro da população e inibir a convergência prematura. Mutação por si só induz uma caminhada aleatória através do espaço de busca Mutação e seleção (sem crossover) criar um paralelo, tolerante ao ruído, hill-climbing algoritmos Efeitos de operadores genéticos Usando a seleção por si só tenderá a preencher a população com cópias do melhor indivíduo do 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-ótima. Usando a mutação por si só induz uma caminhada aleatória através do espaço de pesquisa. Os algoritmos inicializam aleatoriamente a população (t) determinam a aptidão da população (t) repetem os pais selecionados da população (t) realizam o crossover nos pais que criam a população (t1) executam a mutação de (T1) determinar a aptidão da população (t1) até que o melhor indivíduo seja bom o suficiente Na subseção anterior foi alegado que através das operações de seleção, cruzamento e mutação o GA irá convergir ao longo das gerações sucessivas para o global (ou próximo global) Opio. Por que estas simples operação deve produzir um rápido, útil e robusto técnicas é em grande parte devido ao fato de que GAs combinar direção e oportunidade na busca de forma eficaz e eficiente. Uma vez que a população contém implicitamente mais informação do que simplesmente as pontuações de aptidão individual, as AGs 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 indormação herdada de ambos os pais, inevitavelmente. A capacidade do algoritmo para explorar e explorar simultaneamente, uma quantidade crescente de justificação teórica e aplicação bem-sucedida a problemas do mundo real reforça a conclusão de que GAs são uma técnica de otimização poderosa e robusta. Uma introdução aos Algoritmos Genéticos. Mit press editado por Melanie Mitchell Algoritmos genéticos em engenharia e informática editado por G. Winter. Et al .. c1995 Fundamentos de algoritmos genéticos editados por Gregory J. E. Rawlins. C1991 Para detalhes de aplicações de algoritmos genéticos, por favor consulte meu parceiro, artigo Chun s. Algoritmos genéticos em Inglês simples O objetivo deste tutorial é explicar algoritmos genéticos o suficiente para que você possa usá-los em seus próprios projetos. Este é um tipo de tutorial simplificado para o básico. Eu não vou entrar em uma grande dose de profundidade e eu não vou assustar aqueles de vocês com ansiedade matemática, jogando equações mal em você cada poucas frases. Na verdade, eu não vou jogar qualquer equação desagradável em você em tudo Não neste tutorial particular de qualquer maneira. Ltsmilegt Este tutorial foi projetado para ser lido duas vezes. Então não se preocupe se pouco faz sentido a primeira vez que você estudá-lo. (Um leitor, Daniel, traduziu gentilmente este tutorial para o alemão.) (Outro leitor, David Lewin, traduziu o tutorial em francês. Você pode encontrá-lo aqui.) Primeiro, uma lição de Biologia Cada organismo tem Um conjunto de regras, um plano, por assim dizer, descrevendo como esse organismo é construído a partir dos pequenos blocos de construção da vida. Essas regras são codificadas nos genes de um organismo, que por sua vez são conectados em longas cadeias chamadas cromossomos. Cada gene representa um traço específico do organismo, como a cor do olho ou cor do cabelo, e tem várias configurações diferentes. Por exemplo, as configurações para um gene de cor de cabelo podem ser loiras, pretas ou castanhas. Estes genes e as suas configurações são geralmente referidos como um genótipo de organismos. A expressão física do genótipo - o próprio organismo - é chamada fenótipo. Quando dois organismos se acasalam compartilham seus genes. A prole resultante pode acabar tendo metade dos genes de um dos pais e metade do outro. Esse processo é chamado de recombinação. Muito ocasionalmente um gene pode ser mutado. Normalmente, este gene mutado não afectará o desenvolvimento do fenótipo, mas muito ocasionalmente será expresso no organismo como uma característica completamente nova. A vida na Terra evoluiu para ser como é através dos processos de seleção natural, recombinação e mutação. Para ilustrar como esses processos trabalham juntos para produzir a diversidade de flora e fauna que compartilhamos nosso planeta com deixe-me contar uma pequena história. Era uma vez uma espécie de criaturas chamadas Hooters. Hooters tinha evoluído inteiramente dentro dos limites escurecidos de um vasto sistema de cavernas escondido nas entranhas de uma cordilheira. Eles tinham uma vida fácil, sentindo e cheirando as paredes úmidas das cavernas pelas algas que tanto gostavam de comer, escorrendo entre rochas e, no momento do acasalamento, ouvindo atentamente os buzinas de outros Hooters. Não havia predadores nas cavernas, eram apenas os Hooters, as algas e as bolas amigáveis ocasionais, então os Hooters nunca tinham nada a temer (exceto talvez o Hooter ocasionalmente mal-humorado). Um rio subterrâneo fluiu através do sistema de cavernas e água continuamente pingaram para baixo através da mesa de água trazendo com ele os nutrientes frescos as algas prosperaram em assim que havia sempre abundância para comer e beber. No entanto, embora Hooters podia sentir e ouvir bem nunca tiveram qualquer necessidade de olhos na escuridão de campo das cavernas e como resultado foram totalmente cegos. Isso nunca pareceu preocupação de qualquer Hooters embora e todos eles tinham uma baleia de um tempo mastigando afastado e hooting na escuridão. Então, um dia, um terremoto fez com que parte do sistema de cavernas desmoronasse e, pela primeira vez em muitos milênios, os Hooters sentiram o calor da luz do sol sobre sua pele e a macia e macia do musgo sob seus pés. Alguns ousados Hooters provaram o musgo e descobriram que era ainda melhor comer do que as algas da caverna. - Oooooooooohquot eles hooted entre bocados de musgo e prontamente foi devorado pelas águias marauding que tinha voado dentro para ver o que toda a agitação era sobre. Por algum tempo, parecia que os Hooters podiam ser caçados à extinção, pois embora gostassem de comer o musgo eles nunca poderiam dizer se uma águia voava acima. Não só isso, eles não poderiam nem dizer se eles estavam escondidos sob uma rocha ou não, a menos que fosse baixo o suficiente para alcançar com seus sensores. Todos os dias muitos Hooters tropeçavam para fora das cavernas com o doce cheiro de musgo em suas narinas, apenas para serem rapidamente levados e comidos por uma águia. A situação deles parecia realmente sombria. Felizmente, ao longo dos anos, a população de Hooters tinha crescido a ser enorme na segurança das cavernas e bastante deles estavam sobrevivendo para mate - afinal, uma águia só pode comer tanto. Um dia, uma raça de Hooters nasceu que compartilhou um gene de célula de pele mutada. Este gene particular era responsável para o desenvolvimento das pilhas da pele em suas testas. Durante o desenvolvimento do bebê Hooters, quando suas células da pele cresceu a partir das instruções do gene mutado eles eram ligeiramente sensíveis à luz. Cada novo bebê Hooter poderia sentir se algo estava bloqueando a luz para a testa ou não. Quando estes pequenos Hooters cresceram em Hooters maiores e se aventuraram na luz para comer o musgo eles poderiam dizer se algo estava swooping sobrecarga ou não. Então, esses Hooters cresceram para ter uma chance um pouco melhor de sobrevivência do que seus primos totalmente cegos. E porque eles tinham uma melhor chance de sobrevivência, eles se reproduziam muito mais, portanto, passando o novo gene de célula de pele sensível à luz para a sua prole. Depois de muito pouco tempo a população tornou-se dominada pelos Hooters com esta ligeira vantagem. Agora, vamos criar alguns milhares de gerações no futuro. Se você extrapolar esse processo ao longo de muitos anos e envolvendo lotes de pequenas mutações que ocorrem nos genes da célula da pele é fácil imaginar um processo onde uma célula sensível à luz pode se tornar um aglomerado de células sensíveis à luz e, em seguida, como as células do interior do clump Pode mutar para endurecer em uma pequena lente em forma de área, o que ajudaria a reunir a luz e focalizá-lo em um só lugar. Não é muito difícil imaginar uma mutação que dá origem a duas dessas áreas de coleta de luz conferindo assim visão binocular sobre os Hooters. Isso seria uma enorme vantagem sobre seus primos Cicopsianos, já que os Hooters agora seriam capazes de avaliar as distâncias com precisão e ter um campo de visão maior. Como você pode ver os processos de seleção natural - sobrevivência do mais apto - e mutação genética têm papéis muito poderosos para desempenhar na evolução de um organismo. Mas como a recombinação se encaixa no esquema das coisas Bem para mostrar que eu preciso contar sobre alguns outros Hooters. Por volta da mesma época, os Hooters com as células sensíveis à luz estavam brincando no musgo e provocando as águias, outra raça de Hooters havia nascido, que compartilhava um gene mutado que afetou seu hooter. Esta mutação deu origem a um hooter ligeiramente maior do que os seus primos, e porque era maior que poderia agora hoot sobre distâncias mais longas. Isso acabou por ser útil na população em rápida diminuição, porque os Hooters com os hooters maiores poderiam chamar os companheiros potenciais situados longe. Não só isso, mas a fêmea Hooters começou a mostrar uma ligeira preferência para os homens com hooters maiores. O resultado disso, é claro, era que os Hooters mais bem dotados tinham uma chance muito melhor de acasalamento do que qualquer Hooters não tão bem. Durante um período de tempo, hooters grandes tornou-se predominante na população. Então, um bom dia, um Hooter feminino com o gene para células sensíveis à luz da pele encontrou um Hooter masculino com o gene para produzir hooters enormes. Eles se apaixonaram, e logo depois produziu uma raça de adoráveis Hooters. Agora, porque os bebês cromossomos foram uma recombinação de ambos os pais cromossomos, alguns dos bebês compartilhada tanto os genes especiais e cresceu não só para ter luz células sensíveis da pele, mas enormes hooters também Estes novos filhos foram extremamente bons em evitar as águias e Reproduzindo assim o processo de evolução começou a favorecer-los e mais uma vez este tipo melhorado novo de Hooter tornou-se dominante na população. E assim por diante. E assim por diante. Os Algoritmos Genéticos são uma forma de resolver problemas imitando os mesmos processos que a mãe natureza usa. Eles usam a mesma combinação de seleção, recombinação e mutação para evoluir uma solução para um problema. Neat huh Vire a página para descobrir exatamente como é feito.
No comments:
Post a Comment