Algoritmos Genéticos - Tópicos Avançados

Nesta seção, apresentamos alguns tópicos avançados em Algoritmos Genéticos. Um leitor que procura apenas uma introdução aos AGs pode optar por pular esta seção.

Problemas de otimização restrita

Problemas de otimização restrita são aqueles problemas de otimização em que temos que maximizar ou minimizar um determinado valor de função objetivo que está sujeito a certas restrições. Portanto, nem todos os resultados no espaço da solução são viáveis, e o espaço da solução contém regiões viáveis, conforme mostrado na imagem a seguir.

Em tal cenário, os operadores de crossover e mutação podem nos dar soluções que são inviáveis. Portanto, mecanismos adicionais devem ser empregados no AG ao lidar com problemas de otimização restritos.

Alguns dos métodos mais comuns são -

  • Usando penalty functions o que reduz a adequação de soluções inviáveis, de preferência de forma que a adequação seja reduzida na proporção do número de restrições violadas ou da distância da região viável.

  • Usando repair functions que pegam uma solução inviável e a modificam para que as restrições violadas sejam satisfeitas.

  • Not allowing infeasible solutions para entrar na população em tudo.

  • Use um special representation or decoder functions que garante a viabilidade das soluções.

Antecedentes Teóricos Básicos

Nesta seção, discutiremos sobre o esquema e o teorema da NFL, juntamente com a hipótese do bloco de construção.

Teorema do Esquema

Os pesquisadores têm tentado descobrir a matemática por trás do funcionamento dos algoritmos genéticos, e o Teorema do Esquema de Holland é um passo nessa direção. Ao longo do ano, várias melhorias e sugestões foram feitas ao Teorema do Esquema para torná-lo mais geral.

Nesta seção, não nos aprofundamos na matemática do Teorema do Esquema, em vez disso, tentamos desenvolver uma compreensão básica do que é o Teorema do Esquema. A terminologia básica a saber é a seguinte -

  • UMA Schemaé um “modelo”. Formalmente, é uma string sobre o alfabeto = {0,1, *},

    onde * é não importa e pode assumir qualquer valor.

    Portanto, * 10 * 1 pode significar 01001, 01011, 11001 ou 11011

    Geometricamente, um esquema é um hiperplano no espaço de busca de soluções.

  • Order de um esquema é o número de posições fixas especificadas em um gene.

  • Defining length é a distância entre os dois símbolos fixos mais distantes no gene.

O teorema do esquema afirma que este esquema com aptidão acima da média, comprimento de definição curto e ordem inferior tem mais probabilidade de sobreviver a crossover e mutação.

Hipótese de Bloco de Construção

Os blocos de construção são esquemas de baixa definição e ordem inferior com a adequação média fornecida acima. A hipótese do bloco de construção diz que tais blocos de construção servem como base para o sucesso e adaptação dos AGs em AGs à medida que progride, identificando e recombinando sucessivamente esses “blocos de construção”.

Teorema Sem Almoço Grátis (NFL)

Wolpert e Macready publicaram em 1997 um artigo intitulado "Nenhum Teorema do Almoço Grátis para Otimização". Essencialmente, ele afirma que, se calcularmos a média de todos os problemas possíveis, todos os algoritmos de caixa preta não revisáveis ​​exibirão o mesmo desempenho.

Isso significa que quanto mais entendemos um problema, nosso GA se torna mais específico para o problema e oferece melhor desempenho, mas compensa isso apresentando desempenho insatisfatório para outros problemas.

Aprendizado de máquina baseado em GA

Algoritmos genéticos também encontram aplicação no aprendizado de máquina. Classifier systems são uma forma de genetics-based machine learning(GBML) que são frequentemente usados ​​na área de aprendizado de máquina. Os métodos GBML são uma abordagem de nicho para o aprendizado de máquina.

Existem duas categorias de sistemas GBML -

  • The Pittsburg Approach - Nesta abordagem, um cromossomo codifica uma solução e, portanto, a aptidão é atribuída às soluções.

  • The Michigan Approach - uma solução é normalmente representada por muitos cromossomos e, portanto, a aptidão é atribuída a soluções parciais.

Deve-se ter em mente que o problema padrão como crossover, mutação, Lamarckiano ou Darwiniano, etc. também estão presentes nos sistemas GBML.