|
* usam transições probabilísticas e não regras determinísticas.<ref name="goldberg">{{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}}</ref>
SNPSM
== Algoritmo ==
Os Algoritmos genéticos são em geral algoritmos simples e fáceis de serem implementados. Segue abaixo um trecho de ''pseudo-código'' descrevendo um algoritmo genético:
'''função''' ''AlgoritmoGenético''(''população'', ''função-objetivo'') saídas: ''indivíduo''
'''entradas''': ''população→ uma lista de indivíduos
''função-objetivo''→ uma função que recebe um indivíduo e retorna um número real.
;repetir
''lista de pais'' := ''seleção''(''população'', ''função-objetivo'')
''população'' := reprodução(lista de pais)
'''enquanto''' nenhuma condiçao de parada for atingida
'''retorna''' o melhor indivíduo da população de acordo com a ''função-objetivo
A '''função-objetivo''' é o objeto de nossa otimização. Pode ser um problema de otimização, um conjunto de teste para identificar os indivíduos mais aptos, ou mesmo uma "caixa preta" onde sabemos apenas o formato das entradas e nos retorna um valor que queremos otimizar. A grande vantagem dos algoritmos genéticos esta no fato de não precisarmos saber como funciona esta função objetivo, apenas tê-la disponível para ser aplicada aos indivíduos e comparar os resultados.
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. A escolha é feita então aleatóriamente de acordo com essas probabilidades. Dessa forma conseguimos escolher como pais os mais bem adaptados, sem deixar de lado a diversidade dos menos adaptados. Outras formas de seleção podem ser aplicadas dependendo do problema a ser tratado.<ref name="goldbergp121"> 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 121 uma comparação sobre diversas formas 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>
== Programação Genética ==
| 