Algoritmo genético: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 26:
O '''indivíduo''' é meramente um portador do seu '''código genético'''. O código genético é uma representação do espaço de busca do problema a ser resolvido, em geral na forma de seqüências de bits. Por exemplo, para otimizações em problemas cujos valores de entrada são inteiros positivos de valor menor que 255 podemos usar 8 bits, com a representação binária normal, ou ainda uma forma de código gray. Problemas com múltiplas entradas podem combinar as entradas em uma única seqüência de bits, ou trabalhar com mais de um "cromossomo", cada um representando uma das entradas. O código genético deve ser uma representação capaz de representar todo o conjunto dos valores no espaço de busca, e precisa ter tamanho finito..<ref name="goldbergp80"> Para uma discussão sobre as formas de representação do espaço de busca, veja: {{Referência a livro|Autor=Goldberg, David E.|Título=Genetic Algorithms in Search, Optimization, and Machine Learning|Editora=Addison-Wesley|Local de publicação=EUA|Ano=1989|Id=0-201-15767-5}} página 80</ref>
A '''seleção''' também é outra parte chave do algoritmo. Em geral, usa-se o algoritmo de seleção por "roleta", onde os indivíduos são ordenados de acordo com a função-objetivo e lhes são atribuídas probabilidades decrescentes de serem escolhidos - probabilidades essas proporcionais à razão entre a adequação do indivíduo e a soma das adequações de todos os indivíduos da população. A escolha é feita então
Algoritmos Genéticos - uma importante ferramenta da inteligência computacional - 2ª Edição|Editora=Brasport|Local de publicação=BR|Ano=2008|Id=9788574523736}} Capítulo 9 - Outros métodos de seleção.</ref>
A '''reprodução''', tradicionalmente, é divididas em três etapas: [[acasalamento]], [[recombinação]] e [[mutação]]. O acasalamento é a escolha de dois indivíduos para se reproduzirem (geralmente gerando dois descendentes para manter o tamanho populacional). A recombinação, ou ''crossing-over'' é um processo que imita o processo biológico homônimo na [[reprodução|reprodução sexuada]]: os descendentes recebem em seu código genético parte do código genético do pai e parte do código da mãe. Esta recombinação garante que os melhores indivíduos sejam capazes de trocar entre si as informações que os levam a ser mais aptos a sobreviver, e assim gerar descendentes ainda mais aptos. Por último vem as mutações, que são feitas com probabilidade a mais baixa possível, e tem como objetivo permitir maior variabilidade genética na população, impedindo que a busca fique estagnada em um mínimo local..<ref name="goldbergp147"> Veja em {{Referência a livro|Autor=Goldberg, David E.|Título=Genetic Algorithms in Search, Optimization, and Machine Learning|Editora=Addison-Wesley|Local de publicação=EUA|Ano=1989|Id=0-201-15767-5}} página 147 para ver outras orperações que podem ser aplicadas nos indivíduos para a reprodução.</ref>
| |||