Algoritmos de genética Pergunta teórica

Question

Atualmente, estou lendo "Inteligência artificial: uma abordagem moderna" (Russell+Norvig) e "Machine Learning" (Mitchell) - e tentando aprender o básico de Ainn.

Para entender poucas coisas básicas, tenho duas perguntas de 'Greenhorn':

Q1: Em um algoritmo genético, dados os dois pais A e B com os cromossomos 001110 e 101101, respectivamente, qual dos seguintes descendentes poderia ter resultado de um cruzamento de um ponto?

A: 001101

B: 001110

P2: Qual dos filhos acima poderia ter resultado de um crossover de dois pontos? e porque?

Por favor informar.

Answer 1

Não é possível encontrar pais se você não conhece a função inversa-cruzadora (para que axb => (a, b) e (qualquer a) => (a, b)).

Geralmente a função de cruzamento de 1 ponto é:

a = A1 + B2
b = B1 + A2

Mesmo se você souber uma e b vocês não pode resolver o sistema (sistema de 2 equações com 4 variáveis).

Se você conhece 2 partes de qualquer A ou/B, então pode ser resolvido (Sistema de 2 equações com 2 variáveis). É o caso da sua pergunta, pois você fornece A e B.

Geralmente a função crossover não tem função inversa e você só precisa encontrar a solução logicamente ou, Se você conhece os pais, faça o crossover e compare.

Então, para fazer uma fórmula genérica para você, devemos saber duas coisas:

1. Função crossover.
2. Função inversa-cruzada.

O segundo geralmente não é usado no gás, pois não é necessário.

---

Agora, vou apenas responder às suas perguntas.

Q1: Em um algoritmo genético, dados os dois pais A e B com os cromossomos 001110 e 101101, respectivamente, qual dos seguintes descendentes poderia ter resultado de um cruzamento de um ponto?

Olhando para o uma e b Eu posso ver que o ponto de cruzamento está aqui:

    1    2
A: 00 | 1110
B: 10 | 1101

Geralmente o crossover é feito usando esta fórmula:

a = A1 + B2
b = B1 + A2

para que as crianças possíveis sejam:

a: 00 | 1101
b: 10 | 1110

que exclui a opção B da pergunta.
Portanto, a resposta para o primeiro trimestre é o resultado da criança é a: 001101 assumindo função crossover

P2: Qual dos filhos acima poderia ter resultado de um crossover de dois pontos? e porque?

Olhando para os A e B, posso ver os pontos de cruzamento podem estar aqui:

    1   2    3
A: 00 | 11 | 10
B: 10 | 11 | 01

Usual Fórmula para o crossover de 2 pontos é:

a = A1 + B2 + A3
b = B1 + A2 + B3

Então as crianças seriam:

a = 00 | 11 | 10
b = 10 | 11 | 01

Comparando -os com as opções que você perguntou (pequeno uma e b) Podemos dizer a resposta:

Q2. UMA: Nem de uma ou b pode ser resultado de crossover de 2 pontos com AXB De acordo com a função crossover dada.

---

Novamente é não é possivel Para responder suas perguntas sem saber o função crossover.

As funções que forneci são comuns no GA, mas você pode inventar muitos deles para que eles possam responder à pergunta (veja o comentário abaixo):

Answer 2

O crossover de um ponto é quando você faz um se juntar a cada pai, o crossover de dois pontos é quando você faz duas junções. ou seja, dois de um dos pais e um dos outros.

Ver crossover (Wikipedia) para mais informações.

Answer 3

Em relação ao primeiro trimestre, (a) poderia ter sido produzido por um crossover de um ponto, pegando bits 0-4 do pai A e Bit 5 do pai B. (b) não podia a não ser que Seu algoritmo de crossover permite contribuições nulas, ou seja, contribuições dos pais do peso nulo. Nesse caso, os pais A podem contribuir com seu cromossomo completo (bits 0-5) e o pai B contribuiria com a NIL, produzindo (b).

Em relação ao Q2, são possíveis ambos (a) e (b). Existem algumas combinações para testar; Tedioso demais para escrever, mas você pode fazer o trabalho com caneta e papel. :-)