Algoritmos Genéticos - Fundamentos

Esta seção apresenta a terminologia básica necessária para entender os AGs. Além disso, uma estrutura genérica de GAs é apresentada em ambospseudo-code and graphical forms. O leitor é aconselhado a compreender adequadamente todos os conceitos apresentados nesta seção e mantê-los em mente ao ler outras seções deste tutorial.

Terminologia Básica

Antes de iniciar uma discussão sobre Algoritmos Genéticos, é essencial estar familiarizado com alguma terminologia básica que será usada ao longo deste tutorial.

Population- É um subconjunto de todas as soluções possíveis (codificadas) para o problema fornecido. A população de um AG é análoga à população de seres humanos, exceto que, em vez de seres humanos, temos Soluções Candidatas que representam seres humanos.
Chromosomes - Um cromossomo é uma dessas soluções para o problema em questão.
Gene - Um gene é a posição de um elemento de um cromossomo.
Allele - É o valor que um gene assume para um determinado cromossomo.

Genotype- Genótipo é a população no espaço de computação. No espaço de computação, as soluções são representadas de uma forma que podem ser facilmente compreendidas e manipuladas por meio de um sistema de computação.
Phenotype - Fenótipo é a população no espaço de solução do mundo real real em que as soluções são representadas de uma forma que são representadas em situações do mundo real.
Decoding and Encoding - Para problemas simples, o phenotype and genotypeos espaços são iguais. No entanto, na maioria dos casos, os espaços de fenótipo e genótipo são diferentes. A decodificação é um processo de transformação de uma solução do genótipo para o espaço do fenótipo, enquanto a codificação é um processo de transformação do fenótipo para o espaço do genótipo. A decodificação deve ser rápida, pois é realizada repetidamente em um GA durante o cálculo do valor de aptidão.

Por exemplo, considere o problema da mochila 0/1. O espaço Fenótipo consiste em soluções que contêm apenas os números dos itens a serem retirados.

No entanto, no espaço do genótipo, ele pode ser representado como uma string binária de comprimento n (onde n é o número de itens). UMA0 at position x representa isso x^tho item é escolhido enquanto 1 representa o reverso. Este é um caso em que os espaços de genótipo e fenótipo são diferentes.

Fitness Function- Uma função de aptidão definida de forma simples é uma função que toma a solução como entrada e produz a adequação da solução como saída. Em alguns casos, a função de aptidão e a função objetivo podem ser as mesmas, enquanto em outros podem ser diferentes com base no problema.
Genetic Operators- Alteram a composição genética da prole. Isso inclui crossover, mutação, seleção, etc.

Estrutura básica

A estrutura básica de um GA é a seguinte -

Começamos com uma população inicial (que pode ser gerada aleatoriamente ou semeada por outras heurísticas), selecionamos os pais desta população para o acasalamento. Aplique operadores de crossover e mutação nos pais para gerar novos descendentes. E finalmente esses descendentes substituem os indivíduos existentes na população e o processo se repete. Desta forma, os algoritmos genéticos realmente tentam imitar a evolução humana até certo ponto.

Cada uma das etapas a seguir são abordadas como um capítulo separado posteriormente neste tutorial.

Um pseudo-código generalizado para um GA é explicado no programa a seguir -

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best