Esquema (algoritmos genéticos) - Schema (genetic algorithms)

Parte de uma série no
Algoritmo evolucionário
Desenvolvimento artificial Algoritmo evolutivo celular Algoritmo cultural Evolução diferencial Aptidão eficaz Estratégia de evolução Adaptação gaussiana Otimização multimodal evolutiva Evolução gramatical Otimização de enxame de particulas Algoritmo memético Estratégia de evolução natural Algoritmo genético baseado no promotor Algoritmo de otimização espiral
Algoritmo genético
Cromossoma Algoritmo de seleção clonal Crossover Mutação Memória genética Sistemas genéticos fuzzy Seleção Algoritmo de voo
Programação genética
Programação genética cartesiana Programação genética linear Programação de múltiplas expressões Esquema Eurisko Paridade benchmark
v t e

Um esquema é um modelo em ciência da computação usado no campo de algoritmos genéticos que identifica um subconjunto de strings com semelhanças em certas posições de string. Os esquemas são um caso especial de conjuntos de cilindros ; e assim formar um espaço topológico .

Descrição

Por exemplo, considere cadeias binárias de comprimento 6. O esquema 1 ** 0 * 1 descreve o conjunto de todas as palavras de comprimento 6 com 1's na primeira e sexta posições e um 0 na quarta posição. O * é um símbolo curinga , o que significa que as posições 2, 3 e 5 podem ter um valor de 1 ou 0. A ordem de um esquema é definida como o número de posições fixas no modelo, enquanto o comprimento de definição é a distância entre a primeira e a última posição específica. A ordem de 1 ** 0 * 1 é 3 e seu comprimento de definição é 5. A adequação de um esquema é a adequação média de todas as strings que correspondem ao esquema. A adequação de uma string é uma medida do valor da solução codificada do problema, conforme calculado por uma função de avaliação específica do problema. ${\ displaystyle \ delta (H)}$

comprimento

O comprimento de um esquema , chamado , é definido como o número total de nós no esquema. também é igual ao número de nós nos programas correspondentes . ${\ displaystyle H}$${\ displaystyle N (H)}$${\ displaystyle N (H)}$${\ displaystyle H}$

Ruptura

Se a criança de um indivíduo que partidas de esquema H não em si corresponder H, o esquema é dito ter sido interrompido .

Propagação de esquema

Na computação evolutiva , como algoritmos genéticos e programação genética , a propagação se refere à herança de características de uma geração para a próxima. Por exemplo, um esquema é propagado se os indivíduos da geração atual corresponderem a ele e também os da próxima geração. Os da próxima geração podem ser (mas não precisam ser) filhos de pais que combinam com ela.

Os operadores de expansão e compressão

Recentemente, o esquema foi estudado usando a teoria da ordem .

Dois operadores básicos são definidos para o esquema: expansão e compactação. A expansão mapeia um esquema em um conjunto de palavras que ele representa, enquanto a compressão mapeia um conjunto de palavras em um esquema.

Nas seguintes definições denota um alfabeto, denota todas as palavras de comprimento sobre o alfabeto , denota o alfabeto com o símbolo extra . denota todo o esquema de comprimento sobre o alfabeto , bem como o esquema vazio . ${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^ {l}}$${\ displaystyle l}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma _ {*}}$${\ displaystyle \ Sigma}$${\ displaystyle *}$${\ displaystyle \ Sigma _ {*} ^ {l}}$${\ displaystyle l}$${\ displaystyle \ Sigma _ {*}}$${\ displaystyle \ epsilon _ {*}}$

Para qualquer esquema, o seguinte operador , chamado de , é mapeado para um subconjunto de palavras em : ${\ displaystyle s \ in \ Sigma _ {*} ^ {l}}$${\ displaystyle {\ uparrow} s}$${\ expansão displaystyle}$${\ displaystyle s}$${\ displaystyle s}$${\ displaystyle \ Sigma ^ {l}}$

Onde subscrito denota o caractere na posição em uma palavra ou esquema. Quando então . Simplificando, é o conjunto de todas as palavras em que pode ser feito trocando os símbolos de com os símbolos de . Por exemplo, se , e então . ${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle s = \ epsilon _ {*}}$${\ displaystyle {\ uparrow} s = \ emptyset}$${\ displaystyle {\ uparrow} s}$${\ displaystyle \ Sigma ^ {l}}$${\ displaystyle *}$${\ displaystyle s}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma = \ {0,1 \}}$${\ displaystyle l = 3}$${\ displaystyle s = 10 *}$${\ displaystyle {\ uparrow} s = \ {100,101 \}}$

Por outro lado, para qualquer um que definimos , chamado de , que mapeia para um esquema : ${\ displaystyle A \ subseteq \ Sigma ^ {l}}$${\ displaystyle {\ downarrow} {A}}$${\ compressão displaystyle}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle s \ in \ Sigma _ {*} ^ {l}}$

onde é um esquema de comprimento tal que o símbolo na posição em é determinado da seguinte maneira: se para todos então caso contrário . Se então . Pode-se pensar nesse operador como empilhando todos os itens em e, se todos os elementos em uma coluna forem equivalentes, o símbolo nessa posição assume esse valor, caso contrário, haverá um símbolo curinga. Por exemplo, deixe então . ${\ displaystyle s}$${\ displaystyle l}$${\ displaystyle i}$${\ displaystyle s}$${\ displaystyle x_ {i} = y_ {i}}$${\ displaystyle x, y \ in A}$${\ displaystyle s_ {i} = x_ {i}}$${\ displaystyle s_ {i} = *}$${\ displaystyle A = \ emptyset}$${\ displaystyle {\ downarrow} A = \ epsilon _ {*}}$${\ displaystyle A}$${\ displaystyle s}$${\ displaystyle A = \ {100.000.010 \}}$${\ displaystyle {\ downarrow} A = ** 0}$

Os esquemas podem ser parcialmente ordenados . Para qualquer um , dizemos se e somente se . Segue-se que é uma ordenação parcial em um conjunto de esquemas da reflexividade , antissimetria e transitividade da relação de subconjunto . Por exemplo ,. Isso é porque . ${\ displaystyle a, b \ in \ Sigma _ {*} ^ {l}}$${\ displaystyle a \ leq b}$${\ displaystyle {\ uparrow} a \ subseteq {\ uparrow} b}$${\ displaystyle \ leq}$${\ displaystyle \ epsilon _ {*} \ leq 11 \ leq 1 * \ leq **}$${\ displaystyle {\ uparrow} \ epsilon _ {*} \ subseteq {\ uparrow} 11 \ subseteq {\ uparrow} 1 * \ subseteq {\ uparrow} ** = \ emptyset \ subseteq \ {11 \} \ subseteq \ { 11,10 \} \ subseteq \ {11,10,01,00 \}}$

Os operadores de compressão e expansão formam uma conexão de Galois , onde é o adjunto inferior e o adjunto superior. ${\ displaystyle \ downarrow}$${\ displaystyle \ uparrow}$

A conclusão esquemática e a estrutura esquemática

Para um conjunto , chamamos o processo de cálculo da compressão em cada subconjunto de A, ou seja , a conclusão esquemática de , denotado . ${\ displaystyle A \ subseteq \ Sigma ^ {l}}$${\ displaystyle \ {{\ downarrow} X | X \ subseteq A \}}$${\ displaystyle A}$${\ displaystyle {\ mathcal {S}} (A)}$

Por exemplo, deixe . A conclusão esquemática de resulta no seguinte conjunto: ${\ displaystyle A = \ {110.100.001.000 \}}$${\ displaystyle A}$

O poset sempre forma uma rede completa chamada rede esquemática. ${\ displaystyle ({\ mathcal {S}} (A), \ leq)}$

A estrutura esquemática é semelhante à estrutura conceitual encontrada na análise de conceito formal .

Veja também

• Teorema do esquema de Holland
• Análise formal de conceito

Referências