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 GAs pode optar por pular esta seção.

Problemas de otimização restrita

Problemas de otimização restrita são aqueles problemas de otimização nos quais temos que maximizar ou minimizar um determinado valor objetivo da função 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.

Otimização restrita

Nesse cenário, os operadores de crossover e mutação podem nos fornecer soluções inviáveis. Portanto, mecanismos adicionais devem ser empregados no GA ao lidar com problemas de otimização restritos.

Alguns dos métodos mais comuns são -

  • Utilizar funções de penalidade que reduzam a adequação de soluções inviáveis, de preferência para que a adequação seja reduzida proporcionalmente ao número de restrições violadas ou à distância da região viável.

  • Usando funções de reparo que tomam uma solução inviável e modificam-na para que as restrições violadas sejam satisfeitas.

  • Não permitindo que soluções inviáveis entrem na população.

  • Use uma representação especial ou funções de decodificador que garantam a viabilidade das soluções.

Fundamentos Teóricos Básicos

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

Teorema do Esquema

Os pesquisadores tentam 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, mas tentamos desenvolver um entendimento básico do que é o Teorema do Esquema. A terminologia básica a saber é a seguinte -

  • Um esquema é um "modelo". Formalmente, é uma string sobre o alfabeto = {0,1, *},

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

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

    Geometricamente, um esquema é um hiperplano no espaço de pesquisa da solução.

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

Ordem do esquema
  • Definir comprimento é a distância entre os dois símbolos fixos mais distantes no gene.

Esquema Definindo o comprimento

O teorema do esquema afirma que este esquema com aptidão acima da média, comprimento de definição curto e ordem inferior é mais provável que sobreviva ao cruzamento e mutação.

Hipótese do bloco de construção

Os Blocos de Construção são esquemas de ordem baixa e comprimento baixo que definem a aptidão média fornecida acima. A hipótese do bloco de construção diz que esses blocos de construção servem como base para o sucesso e a adaptação das AGs nas AGs à medida que progridem, identificando e recombinando sucessivamente esses "blocos de construção".

Teorema Sem Almoço Gratuito (NFL)

Wolpert e Macready, em 1997, publicaram um artigo intitulado "Nenhum Teorema de Almoço Gratuito para Otimização". Afirma essencialmente que, se calcularmos a média no espaço de todos os problemas possíveis, todos os algoritmos de caixa preta que não revisitam exibirão o mesmo desempenho.

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

Aprendizado de máquina baseado no GA

Algoritmos genéticos também encontram aplicação no Machine Learning. Os sistemas classificadores são uma forma de sistema de aprendizado de máquina baseado em genética (GBML) que é frequentemente usado no campo 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 -

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

  • A abordagem de Michigan - 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 a questão padrão como crossover, mutação, lamarckiana ou darwiniana etc. também está presente nos sistemas GBML.