Por que indivíduos com baixa aptidão física têm chance de sobreviver até a próxima geração?

24

Atualmente, estou lendo e assistindo sobre algoritmo genético e acho muito interessante (não tive a chance de estudá-lo enquanto estava na universidade).

Entendo que as mutações se baseiam na probabilidade (a aleatoriedade é a raiz da evolução), mas não entendo por que a sobrevivência é.

Pelo que eu entendo, um indivíduo ter uma aptidão como por um outro indivíduo tendo uma aptidão temos , então tem uma probabilidade melhor do que para sobreviver para a próxima geração. $I$ $F(i)$ $J$ $F(j)$ $F(i) > F(j)$ $I$ $J$

Probabilidade implica que pode sobreviver e pode não (com "má sorte"). Eu não entendo por que isso é bom? Se teria sempre sobreviver a seleção, o que iria dar errado no algoritmo? Meu palpite é que o algoritmo seria semelhante a um algoritmo ganancioso, mas não tenho certeza. $J$ $I$ $I$

algorithms optimization genetic-algorithms Máx.
fonte

13

Ficar preso no mínimo local.

Louis

Mesmo na vida real, mutações benéficas não garantem / melhor condicionamento ambiental não garantem a sobrevivência dos indivíduos com elas, o que realmente permite a expressão de uma variedade maior de características (e pode potencialmente ser benéfica se o ambiente mudar inesperadamente, embora isso não seja tão provável para um algoritmo de otimização). ... E isso é afirmado no final da resposta de Nick, tanto faz.

21914 JAB

1

Se você mata os fracos o tempo todo, o que você tem senão um alpinista comum?

Raphael

35

A idéia principal é que, ao permitir que indivíduos abaixo do ideal sobrevivam, é possível alternar de um "pico" no cenário evolutivo para outro através de uma sequência de pequenas mutações incrementais. Por outro lado, se você apenas pode subir, é necessária uma mutação gigantesca e altamente improvável para mudar de pico.

Aqui está um diagrama mostrando a diferença:

insira a descrição da imagem aqui

Na prática, essa propriedade de globalização é o principal ponto de venda dos algoritmos evolutivos - se você deseja apenas encontrar um máximo local, existem técnicas especializadas mais eficientes. (por exemplo, L-BFGS com gradiente de diferença finita e pesquisa de linha)

No mundo real da evolução biológica, permitir que indivíduos abaixo do ideal sobrevivam cria robustez quando a paisagem evolutiva muda. Se todos estiverem concentrados em um pico, se esse pico se tornar um vale, toda a população morre (por exemplo, os dinossauros eram as espécies mais aptas até que houve um ataque de asteróide e a paisagem evolucionária mudou). Por outro lado, se houver alguma diversidade na população, quando a paisagem mudar, alguns sobreviverão.

Nick Alger
fonte

2

"No mundo real da evolução biológica, permitir que indivíduos abaixo do ideal sobrevivam cria robustez quando a paisagem evolutiva muda" - como biólogo, isso irrita. Indivíduos com baixa aptidão física não têm "permissão" de sobreviver para maximizar a aptidão, que é apenas a natureza da realidade. Organismos de baixa aptidão estão tentando sobreviver tanto quanto qualquer outra coisa.

Jack Aidley

Claro que você está certo, a natureza não decide permitir ou não qualquer coisa, apenas acontece. Por outro lado, existem muitos exemplos em que os seres humanos criaram seletivamente plantas e animais, mantendo apenas o "melhor", criando uma monocultura que não é robusta quando surge uma nova doença ou o ambiente muda.

Nick Alger

Existem outras técnicas para combater esse efeito, por exemplo, dar passos maiores e executar novamente com populações iniciais aleatórias. Além disso, na presença de recombinação cruzada, manter um genótipo mais fraco ao redor pode ser útil se um mais forte sofrer mutação e um cruzamento entre os dois for ainda mais forte.

Raphael

13

A resposta de Nick Alger é muito boa, mas vou torná-la um pouco mais matemática com um método de exemplo, o método Metropolis-Hastings.

$i$ $j$ $Q(i,j)$ $Q(i,j) = Q(j,i)$ $F(i)>0$ $i$

$i$ $j$

min (1, \frac{F (j)}{F (i)})

$\min\left(1, \frac{F(j)}{F(i)}\right)$

Em outras palavras, se é mais adequado, sempre o aceitamos, mas se é menos adequado, o aceitamos com probabilidade ; caso contrário, tentamos novamente até aceitarmos um mutação. $j$ $j$ $\frac{F(j)}{F(i)}$

Agora gostaríamos de explorar , a probabilidade real de fazer a transição de para . $P(i,j)$ $i$ $j$

Claramente é:

P (i, j) = Q (i, j) min (1, \frac{F (j)}{F (i)})

$P(i,j) = Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$

Vamos supor que . Então = 1, e assim: $F(j) \ge F(i)$ $\min\left(1, \frac{F(j)}{F(i)}\right)$

F (i) P (i, j)

$F(i) P(i,j)$

= F (i) Q (i, j) min (1, \frac{F (j)}{F (i)})

$= F(i) Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$

= F (i) Q (i, j)

$= F(i) Q(i,j)$

= Q (j, i) m i n (1, \frac{F (i)}{F (j)}) F (j)

$= Q(j,i) min\left(1, \frac{F(i)}{F(j)}\right) F(j)$

= F (j) P (j, i)

$= F(j) P(j,i)$

Executando o argumento para trás e também examinando o caso trivial em que , você pode ver isso para todos os e : $i=j$ $i$ $j$

F (i) P (i, j) = F (j) P (j, i)

$F(i) P(i,j) = F(j) P(j,i)$

Isso é notável por alguns motivos.

A probabilidade de transição é independente de . É claro que pode demorar um pouco para acabarmos com o atrator, e pode demorar um pouco para aceitar uma mutação. Uma vez que fazemos, a probabilidade de transição é totalmente dependente , e não sobre . $Q$ $F$ $Q$

Somando tudo o que dou: $i$

\sum_{i} F (i) P (i, j) = \sum_{i} F (j) P (j, i)

$\sum_i F(i) P(i,j) = \sum_i F(j) P(j,i)$

Claramente deve somar se você somar todo (ou seja, as probabilidades de transição de um estado devem somar ), para obter: $P(j,i)$ $1$ $i$ $1$

F (j) = \sum_{i} F (i) P (i, j)

$F(j) = \sum_i F(i) P(i,j)$

Ou seja, é a função de densidade de probabilidade (não normalizada) para a qual os estados o método escolhe. Você não só garante a exploração de toda a paisagem, mas também o faz na proporção de quão "adequado" é cada estado. $F$

Obviamente, este é apenas um exemplo dentre muitos; como observei abaixo, é um método muito fácil de explicar. Você normalmente usa um GA não para explorar um pdf, mas para encontrar um extremo, e pode relaxar algumas das condições nesse caso e ainda garantir eventual convergência com alta probabilidade.

Pseudônimo
fonte

Resposta maravilhosa! Eu gostaria de poder votar várias vezes. Uma pergunta: você pode motivar por que escolheríamos ? Isso foi escolhido porque todo o resto da matemática acaba produzindo um resultado muito bacana? Ou existe alguma razão externa para que essa seja uma escolha natural para ? (Eu esperaria que um valor natural para fosse um sobre o número de extremidades externas do estado , caso em que não teríamos desde que, em geral, o out-grau de e pode ser diferente).

Q (i, j) = Q (j, i)

$Q(i,j)=Q(j,i)$

Q

$Q$

Q (i, j)

$Q(i,j)$

i

$i$

Q (i, j) = Q (j, i)

$Q(i,j)=Q(j,i)$

i

$i$

j

$j$

DW

A motivação, neste caso, é a condição detalhada do equilíbrio, , que é uma condição suficiente (embora não necessária) para garantir que é o estacionário pdf. Se você deseja que seu pdf seja estacionário, ajuda o processo a ser reversível em algum sentido. Além disso, se ajudar, o algoritmo MH foi projetado para problemas contínuos (transporte de nêutrons) onde não há um número discreto de bordas externas. Claro, se você está tentando encontrar um máximo global, pesquisar o PDF inteiro nem sempre é o que você realmente deseja. Isso foi apenas para fins ilustrativos.

F (i) P (i, j) = F (j) P (j, i)

$F(i) P(i,j) = F(j) P(j,i)$

F

$F$

Pseudônimo

7

A vantagem de usar um GA é que você pode explorar espaços de pesquisa mais amplos seguindo caminhos que vêm de candidatos potencialmente piores. Deveria haver candidatos piores, a fim de explorar essas diferentes áreas da pesquisa, não muitas, mas definitivamente algumas. Se você começar a tirar o melhor de todas as vezes que remover esse aspecto de exploração do algoritmo, ele se tornará mais um alpinista. Além disso, apenas selecionar os melhores constantemente pode levar a uma convergência prematura.

lPlant
fonte

6

Na verdade, os algoritmos de seleção adotam as duas abordagens. Uma delas é o que você sugeriu e a outra é que indivíduos com maior aptidão física são selecionados e aqueles com menor condição física não são.

A abordagem escolhida para a seleção também é adaptada ao problema que você está tentando modelar. Em um experimento na escola, estávamos tentando evoluir os jogadores de cartas, fazendo-os jogar uns contra os outros (por exemplo , seleção de torneio ). Nesse cenário, poderíamos muito bem sempre favorecer sobre (do seu exemplo), porque o aspecto 'sorte' já está no próprio jogo. Mesmo que para quaisquer dois e , em qualquer rodada, puramente pela maneira como as mãos eram distribuídas e como os outros jogavam, poderia ter vencido a rodada e, portanto, poderíamos terminar com $I$ $J$ $F(i) > F(j)$ $I$ $J$ $J$ $F(j) > F(i)$ . Lembre-se de que uma população geralmente é grande o suficiente para perder pessoas boas e, no geral, isso não importa tanto.

Como as AGs são modeladas em torno da evolução do mundo real, quando as distribuições probabilísticas são usadas, elas são modeladas principalmente em torno de como as comunidades reais evoluem nas quais, às vezes, indivíduos com menor condicionamento físico podem sobreviver, enquanto indivíduos com maior condicionamento físico não conseguem (uma analogia grosseira: acidentes de carro, naturais). desastres etc. :-)).

Omer Iqbal
fonte

0

é muito simples, de um ponto de vista: às vezes as soluções "filho" de melhor condicionamento físico podem nascer de soluções "parentais" de menor condicionamento, por meio de crossover ou mutação (que na verdade é grande parte da teoria dos algoritmos genéticos). portanto, em geral, se deseja buscar / levar soluções de alta aptidão, mas muita ênfase em manter / criar apenas soluções de alta aptidão pode levar a ficar preso nos mínimos locais e não procurar a grande "paisagem evolutiva". na verdade, pode-se fazer o "ponto de corte mais adequado" para a sobrevivência, tão rigoroso ou relaxado quanto se deseja, e experimentar como isso afeta a qualidade da solução final. estratégias de corte muito rigorosas ou muito frouxas levarão a soluções finais inferiores. é claro que tudo isso tem alguma relação com a verdadeira evolução biológica. aí é mais "

vzn
fonte

Por que indivíduos com baixa aptidão física têm chance de sobreviver até a próxima geração?

Respostas: