- Generated by
1.9.8
|
TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
|
| TesteTVector | Aspirador 1 | Aspirador 2 | Puzzle 8 | 8 Damas | Partição | 8 Damas CI | 8 Damas CP | Partição CB |
Execução de exemplo com base no problema das 8 damas, com a codificação inteira. Pode acompanhar o teste executando as ações localmente.
No Visual Studio, selecione o projeto TProcuraMelhorativa, e execute-o. No Linux na pasta .../TProcura/Melhorativa/Teste execute make seguido de ./bin/Release/TProcuraMelhorativa
┌─ Teste TProcuraMelhorativa ──┐
│ 1 - 8 Damas (Inteira) │
│ 2 - 8 Damas (Permutacao) │
│ 3 - Partição (Binária) │
└──────────────────────────────┘
Opção: 1
Vamos entrar no problema 8 Damas Inteira, insira: 1.
8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): NADA | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 50 | P9(SELECAO): Roleta | P10(PRESSAO): 150 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 1 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): 1-ponto | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── :: :: :: ♛ ::♛ :: :: :: :: :: :: ::♛ ♛ :: :: :: :: :: :: ♛ :: :: :: ::♛ :: :: :: ♛ :: :: :: :: ♛ ┌─ ☰ Menu ─────────┬────────────────┬─────────────────────┬──────────────┐ │ 1 📄 Instância │ 2 🔍 Explorar │ 3 ⚙ Parâmetros │ 4 ✔ Solução │ │ 5 ⚖ Indicadores │ 6 ► Executar │ 7 🛠️ Configurações │ 8 🧪 Teste │ └───────────────────┴────────────────┴─────────────────────┴──────────────┘ Opção:
Temos uma instância das 8 Damas como no exemplo da TProcuraConstrutiva. Em vez de um tabuleiro vazio, em que iamos construindo a solução adicionando damas, existem damas já colocadas mas algumas atacam-se mutuamente. Esta é uma solução completa aleatória, que pretendemos melhorar. Tem ainda violações, que são damas a atacarem-se, que neste contexto convertem-se em custos, que pretendemos remover. Uma solução de custo 0 é prortanto uma solução válida.
Temos um número de parâmetros mais extenso, embora os 5 primeiros parâmetros sejam os mesmos que no exemplo do teste TVector. O último parâmetro é o P24, muito embora não estejam 24 parâmetros. O P11 por exemplo não é mostrado. Alguns parâmetros só são ativos devido a valores de outros parâmetros. Como temos o P1(ALGORITMO) em Algoritmos Evolutivos, este algoritmo tem muitos parâmetros, e por esse motivo são mostrados bastantes. Iremos abordar cada um no momento próprio.
Vamos trocar para uma instância menor antes de avançarmos, para simplificar a nossa exploração.
Insira: 1; 4.
Opção: 1 ┌─ 📄 Instância ─────────────────────────────────────────────────────── │ ID atual: 8 Intervalo: [4–40] │ Prefixo atual: 'instancia_' └────────────────────────────────────────────────────────────────────── Novo ID (ENTER mantém) ou novo prefixo (texto): 4 8 Damas (Inteira) ... :: ♛ ::♛ :: :: ::♛ ♛ :: :: ... Opção:
Estavamos na instância 8 e agora estamos na instância 4. Temos um tabuleiro de 4x4 para colocar 4 damas. Podiamos ter escolhido até tabuleiros de 40x40.
Vamos primeiro procurar resolver a instância manualmente, e ver a codificação inteira utilizada. Insira: 2.
Opção: 2 │ 🏆 ⏱ 💰 g:2 ─┴─────────────────── ♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── ├─┬─ 📆 0 ⏱ ──── 💰 g2-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 2 0 3 💰 g:2 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 3 3 1 0 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 1 2 3 4 │ │ ────┼────┼────┼────┼────┼ │ │ 1 │ │ 4│ 4│ 4│ │ │ 2 │ 4│ │ 3│ 1│ │ │ 3 │ 4│ 3│ │ 3│ │ │ 4 │ 4│ 1│ 3│ │ │ │ ────┴────┴────┴────┴────┴ │ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos):
Entramos num modo de expoloração manual com as operações dos algoritmos melhorativos. No entanto a população foi fixada em 4, para melhor gerir a exploração manual. Durante a geração da população dos 4 elementos foi encontrada uma solução de custo 2, que foi mostrada de imediato. Arranca a época 0 (linha: " ├─┬─ 📆 0 ⏱ ──── 💰 g2-4"), tal como os algoritmos evolutivos, mas neste caso cada época é o resultado de aplicar um operador.
Podemos ver a população de 4 elementos com custos de 2 a 4. É mostrado a codificação inteira e não as soluções a que correspondem. Assim pretendemos focar no que os algoritmos vêm, e não nas soluções.
A descodificação, ou seja, a conversão da codificação para uma solução, é neste caso simples: cada número na posição K corresponde à coluna em que a dama da linha K deve estar. A descodificação é normalmente necessária para avaliar o custo de uma solução, neste caso o número de pares de damas a atacarem-se mutuamente.
A codificação de uma solução é também imediata. No entanto em problemas complexos estas duas operações, codificar/descodificar uma solução, podem ter custos computacionais consideráveis.
Como temos 4 damas temos 4 números de 0 a 3.
Podemos utilizar outra codificação, desde que exista forma de codificar todas as soluções de interesse, ou seja, de uma solução converter na codificação única, e descodificar, de uma codificação reconstruir a solução a que corresponde.
Há outras possibilidades de codificar o problema das 8 damas, estando implementado a codificação com base na permutação, no próximo exemplo.
Na população os 4 elementos têm cor de fundo para auxiliar a identificação, e os custos têm cor da letra para sinalizar os melhores elementos de forma visual.
Temos um mapa de distâncias entre os 4 elementos para dar uma ideia da diversidade da população. A medida de distancia por omissão é Hamming, significando que conta simplesmente os valores distintos. Podemos alterar através do parâmetro P24(TIPO_DISTANCIA):. Há vários tipos de distâncias disponíveis dependendo da codificação. Há dois elementos à distância de 1 unidade, o 2 e 4. De facto, estes diferem apenas no valor do segundo inteiro.
Temos 3 operações para testar, a mutação, cruzamento e vizinhança. Vamos começar pela mutação, e mutar o indivíduo 4. Insira: 1; 4.
│ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos): 1 │ ┌───── 🦠 ───── │ │ 🧍 [1-4]: 4 │ │ 🧍 3 3 1 0 mutar vizinho incDecValor (3,1) │ │ 🦠 3 3 1 1 │ │ :: ::♛ │ │ :: ♛ │ │ ::♛ :: │ │ ♛ :: │ └────────────── ├─┬─ 📆 1 ⏱ ──── 💰 g2-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 2 0 3 💰 g:2 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 3 3 1 1 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 1 2 3 4 │ │ ────┼────┼────┼────┼────┼ │ │ 1 │ │ 4│ 4│ 4│ │ │ 2 │ 4│ │ 3│ 2│ │ │ 3 │ 4│ 3│ │ 4│ │ │ 4 │ 4│ 2│ 4│ │ │ │ ────┴────┴────┴────┴────┴ │ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos):
A mutação acabou por trocar apenas um valor, o que se pode confirmar nas linhas 🧍(atual) e 🦠 (mutado), com as codificaçõe seguidas e alinhadas. Ficou uma solução igualmente má de custo 4. Podemos alterar a mutação no parâmetro P21(TIPO_MUTAR). Existem também vários operadores de mutação disponíveis dependente do tipo de codificação.
Vamos agora passar para o cruzamento, e cruzar o individuo 1 com o 3, os dois melhores na população, e substituir o individuo 4. Insira: 2; 1; 3; 4.
│ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos): 2 │ ┌───── 🧬 ───── │ │ 🧍 Pai [1-4]: 1 │ │ 🧍 Mãe [1-4]: 3 │ │ 🧍 Filho [1-4]: 4 │ │ │ │ 🧍 Pai 0 2 0 3 │ │ 🧍 Mãe 1 0 3 0 cruzamento 1-ponto(s): 3 │ │ 🧬 Filho 0 2 0 0 │ │ ♛ :: │ │ ::♛ :: │ │ ♛ :: │ │ ♛ :: :: │ └────────────── ├─┬─ 📆 2 ⏱ ──── 💰 g2-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 2 0 3 💰 g:2 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 0 2 0 0 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 1 2 3 4 │ │ ────┼────┼────┼────┼────┼ │ │ 1 │ │ 4│ 4│ 1│ │ │ 2 │ 4│ │ 3│ 3│ │ │ 3 │ 4│ 3│ │ 3│ │ │ 4 │ 1│ 3│ 3│ │ │ │ ────┴────┴────┴────┴────┴ │ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos):
O filho ficou quase igual ao pai, com os três primeiros elementos do pai, e o último da mãe. Existem vários tipos de operadores de cruzamento, controlados pelo parâmetro P20(TIPO_CRUZAR). Diferentes operadores estão disponíveis em diferentes codificações, podendo cada operador ter também parâmetros próprios.
Falta-nos explorar o operador de vizinhança, pelo que vamos aplicar ao melhor individuo 1, e escolher o melhor vizinho. Insira: 3; 1; 1.
│ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos): 3 │ ┌───── 🧍🧍 ───── │ │ 🧍 [1-4]: 1 │ │ 🧍 0 2 0 3 vizinhança incDecValor (limite 0) │ ├───── Vizinhos ───── │ │ 🧍 1 1 2 0 3 💰 g:1 │ │ 🧍 2 0 3 0 3 💰 g:3 │ │ 🧍 3 0 1 0 3 💰 g:5 │ │ 🧍 4 0 2 1 3 💰 g:2 │ │ 🧍 5 0 2 0 2 💰 g:2 │ │ 🧍 [1-5]: 1 │ │ │ 🏆 ⏱ 💰 g:1 ─┴─────────────────── │ │ ::♛ :: │ │ ::♛ :: │ │ ♛ :: │ │ :: ♛ ─┬─────────────────── │ └────────────── ├─┬─ 📆 3 ⏱ ──── 💰 g1-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 1 2 0 3 💰 g:1 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 0 2 0 0 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 1 2 3 4 │ │ ────┼────┼────┼────┼────┼ │ │ 1 │ │ 4│ 3│ 2│ │ │ 2 │ 4│ │ 3│ 3│ │ │ 3 │ 3│ 3│ │ 3│ │ │ 4 │ 2│ 3│ 3│ │ │ │ ────┴────┴────┴────┴────┴ │ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos):
O melhor vizinho gerado tem custo 1, pelo que estamos mais perto. Foi feita a substituição da melhor solução. Notar que o tipo de vizinhança é descrito, neste caso apenas incrementamos ou decrementamos cada valor em uma unidade. Devido a esta opção, a vizinhança tem um número baixo de indivíduos.
Vamos insistir e ver os vizinhos deste novo elemento, e novamente escolher o melhor destes. Insira: 3; 1; 3.
│ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos): 3 │ ┌───── 🧍🧍 ───── │ │ 🧍 [1-4]: 1 │ │ 🧍 1 2 0 3 vizinhança incDecValor (limite 0) │ ├───── Vizinhos ───── │ │ 🧍 1 2 2 0 3 💰 g:2 │ │ 🧍 2 0 2 0 3 💰 g:2 │ │ 🧍 3 1 3 0 3 💰 g:1 │ │ 🧍 4 1 1 0 3 💰 g:3 │ │ 🧍 5 1 2 1 3 💰 g:3 │ │ 🧍 6 1 2 0 2 💰 g:2 │ │ 🧍 [1-6]: 3 │ │ │ │ ::♛ :: │ │ :: ♛ │ │ ♛ :: │ │ :: ♛ │ └────────────── ├─┬─ 📆 4 ⏱ ──── 💰 g1-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 1 3 0 3 💰 g:1 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 0 2 0 0 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 1 2 3 4 │ │ ────┼────┼────┼────┼────┼ │ │ 1 │ │ 4│ 3│ 3│ │ │ 2 │ 4│ │ 3│ 3│ │ │ 3 │ 3│ 3│ │ 3│ │ │ 4 │ 3│ 3│ 3│ │ │ │ ────┴────┴────┴────┴────┴ │ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos):
Neste caso o vizinho tem o mesmo custo, mas é outro vizinho, pelo que vale a pena ainda uma última vez, ver quais os seus vizinhos. Insira: 3; 1; 5.
│ └─■ ⚡ Operação (1 🦠 Mutar, 2 🧬 Cruzar, 3 🧍🧍Vizinhos): 3 │ ┌───── 🧍🧍 ───── │ │ 🧍 [1-4]: 1 │ │ 🧍 1 3 0 3 vizinhança incDecValor (limite 0) │ ├───── Vizinhos ───── │ │ 🧍 1 2 3 0 3 💰 g:3 │ │ 🧍 2 0 3 0 3 💰 g:3 │ │ 🧍 3 1 2 0 3 💰 g:1 │ │ 🧍 4 1 3 1 3 💰 g:2 │ │ 🧍 5 1 3 0 2 💰 g:0 │ │ 🧍 [1-5]: 5 │ │ │ 🏆 ⏱ 💰 g:0 ─┴─────────────────── │ │ ::♛ :: │ │ :: ♛ │ │ ♛ :: │ │ ::♛ :: ─┬─────────────────── │ └────────────── └──────────────── 8 Damas (Inteira) ... ::♛ :: :: ♛ ♛ :: ::♛ :: ... Opção:
Temos finalmente a solução de custo 0, o que pretendiamos. Uma solução com as 4 damas, sem se atacarem. Ao selecionar o vizinho com a solução ótima, a exploração é interrompida, tal como qualquer algoritmo, sendo a solução obtida retornada.
Vamos agora ver como o algoritmo evolutivo poderia obter esta solução de forma automática, com a parametrização por omissão. Insira: 1; 4; 6.
Opção: 6 ═╤═ ► Execução iniciada ═══ ├─ Parâmetros ─ P1=1 P2=0 P3=1 P4=10 P5=1000000 P6=20 P7=100 P8=50 P9=1 P10=150 P13=1 ├─ ⚙ ─ P14=100 P16=1 P17=1 P18=3 P19=0 P20=1 P21=0 P22=1 P23=0 P24=1 ═╧═ 🏁 Execução terminada ⏱ ═══ 8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): NADA | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 50 | P9(SELECAO): Roleta | P10(PRESSAO): 150 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 1 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): 1-ponto | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ┌─ ⚖ Indicadores ───────────────────────────────────────────────────── │ I1(Resultado): 0 | I2(Tempo(ms)): 0 | I3(Iterações): 241 | I4(Épocas): 10 | │ I5(Gerações): 249 └────────────────────────────────────────────────────────────────────── ... Opção:
Podemos ver que o primeiro indicador, I1(Resultado) é igual a 0. Este é o custo da solução. Podemos observar a solução e ver que as damas não se atacam, aliás, é exatamente a mesma solução obtida manualmente.
O segundo indicador I2(Tempo(ms)) é 0, o que significa que foi consumido menos de 1 milissegundo.
Temos o número de iterações a 241, que corresponde às avaliações efetuadas, e 10 épocas, o que corresponde ao número de ciclos do algoritmo evolutivo. Finalmente, temos o número de estados gerados a 249.
Há informação visível nos indicadores, mas não vemos nada em termos de funcionamento do algoritmo. O que aconteceu nestas 10 épocas? Vendo a parametrização podemos ver que há população de 20, e toda a informação de operadores e opções. Podemos obter na literatura qual a melhor parametrização para um dado problema ou tipo de problemas, e utilizar como parametrização base. Mas estaremos satisfeitos com esta informação? Não! Precisamos de ver o que se passou em concreto, para saber o que correu bem e menos bem, sem dependências de terceiros. Queremos até mais tarde confirmar que a configuração base é a melhor parametrização possível, ou identificar qual é a mais adequada, pela via experimental.
Como podemos repetir todas as execuções, podemos ver a mesma execução com diferentes níveis de detalhe. Vamos aproveitar esta execução que tem tamanho reduzido, para ir subindo o nível de debug. Insira: 1; 4; 3; 2; 1; ENTER; 6.
Opção: 6 ═╤═ ► Execução iniciada ═══. │ 🏆 ⏱ 💰 g:2 ─┴─────────────────── ♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── │ 🏆 ⏱ 💰 g:1 ─┴─────────────────── ♛ :: ::♛ :: :: ::♛ ♛ :: ─┬─────────────────── │ 🏆 ⏱ 💰 g:0 ─┴─────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ─┬─────────────────── ├─ Parâmetros ─ P1=1 P2=1 P3=1 P4=10 P5=1000000 P6=20 P7=100 P8=50 P9=1 P10=150 P13=1 ├─ ⚙ ─ P14=100 P16=1 P17=1 P18=3 P19=0 P20=1 P21=0 P22=1 P23=0 P24=1 ═╧═ 🏁 Execução terminada ⏱ ═══ 8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): ATIVIDADE | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 50 | P9(SELECAO): Roleta | P10(PRESSAO): 150 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 1 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): 1-ponto | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ┌─ ⚖ Indicadores ───────────────────────────────────────────────────── │ I1(Resultado): 0 | I2(Tempo(ms)): 0 | I3(Iterações): 241 | I4(Épocas): 10 | │ I5(Gerações): 249 └────────────────────────────────────────────────────────────────────── ... Opção:
Nesta repetição vemos um ponto de quando em quando, para saber que há atividade. No final são introduzidos 128 pontos, se o número de iterações for atingido. Como gastamos muito poucas iterações e o limite é muito alto, estes pontos nem chegam a ser impressos.
Mas vemos algo importante. Sempre que se encontra uma melhor solução global, é registado o tempo e a solução é mostrada ao utilizador. Podemos ver que primeiro foi encontrada uma solução de custo 2, de seguida outra de custo 1 e finalmente a de custo 0.
Sabemos mais alguma coisa do que se passou, mas não muito. Numa execução longa podemos ver quando as diferentes soluções são encontradas, e se são encontradas soluções de custos incrementais, ou diretamente a solução de custo 0.
Vamos ver agora o nível de debug PASSOS. Insira: 1; 4; 3; 2; 2; ENTER; 6.
Opção: 6 ═╤═ ► Execução iniciada ═══ │ 🏆 ⏱ 💰 g:2 ─┴─────────────────── ♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── ├─── 📆 0 ⏱ ──── 💰 g2-5 │ 🏆 ⏱ 💰 g:1 ─┴─────────────────── ♛ :: ::♛ :: :: ::♛ ♛ :: ─┬─────────────────── ├─── 📆 1 ⏱ ──── 💰 g1-5 ├─── 📆 2 ⏱ ──── 💰 g1-5 ├─── 📆 3 ⏱ ──── 💰 g1-5 ├─── 📆 4 ⏱ ──── 💰 g1-5 ├─── 📆 5 ⏱ ──── 💰 g1-5 ├─── 📆 6 ⏱ ──── 💰 g1-4 ├─── 📆 7 ⏱ ──── 💰 g1-5 ├─── 📆 8 ⏱ ──── 💰 g1-5 ├─── 📆 9 ⏱ ──── 💰 g1-4 │ 🏆 ⏱ 💰 g:0 ─┴─────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ─┬─────────────────── ├─ Parâmetros ─ P1=1 P2=2 P3=1 P4=10 P5=1000000 P6=20 P7=100 P8=50 P9=1 P10=150 P13=1 ├─ ⚙ ─ P14=100 P16=1 P17=1 P18=3 P19=0 P20=1 P21=0 P22=1 P23=0 P24=1 ═╧═ 🏁 Execução terminada ⏱ ═══ 8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): PASSOS | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 50 | P9(SELECAO): Roleta | P10(PRESSAO): 150 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 1 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): 1-ponto | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ┌─ ⚖ Indicadores ───────────────────────────────────────────────────── │ I1(Resultado): 0 | I2(Tempo(ms)): 0 | I3(Iterações): 241 | I4(Épocas): 10 | │ I5(Gerações): 249 └────────────────────────────────────────────────────────────────────── ... Opção:
Temos agora a informação das diferentes épocas. Em cada época é registado o instante em que esta ocorre, neste caso apenas alguns milissegundos, o número da época, e o menor e maior custo na população.
Aqui é possível observar que nesta procura, a melhor solução na população nunca piorou de uma época para a outra. Dependente da parametrização, nem sempre esta situação é garantida. A utilização de P16(ELITISMO)=1 garante que pelo menos um elemento da população antiga, irá manter-se caso na nova população não exista nenhum elemento com valor melhor ou igual.
Aumentamos o conhecimento, mas ainda estamos um pouco às escuras. Sabemos em que as duas soluções intermédias foram encontradas logo ao gerar a população inicial, e na primeira geração. Fora o parâmetro do elitismo, nada mais pode ser observado ou verificada a sua utilidade.
É tempo para aumentar o nível de debug para DETALHE. Insira: 1; 4; 3; 2; 3; ENTER; 6.
Opção: 6 ═╤═ ► Execução iniciada ═══ │ 🏆 ⏱ 💰 g:2 ─┴─────────────────── ♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── ├─┬─ 📆 0 ⏱ ──── 💰 g2-5 [📏 1-4 (μ=2, melhor/pior 3)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 2│ 4│ 3│ 4│ 4│ 2│ 3│ 2│ 4│ 2│ │ │ 10│ 2│ 4│ 2│ 5│ 3│ 2│ 5│ 3│ 5│ 4│ │ └──────────────────────────────────── │ 🏆 ⏱ 💰 g:1 ─┴─────────────────── ♛ :: ::♛ :: :: ::♛ ♛ :: ─┬─────────────────── ├─┬─ 📆 1 ⏱ ──── 💰 g1-5 [📏 1-4 (μ=2, melhor/pior 4)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 1│ 4│ 4│ 4│ 3│ 2│ 5│ 4│ 3│ 2│ │ │ 10│ 4│ 4│ 2│ 3│ 2│ 2│ 3│ 4│ 4│ 3│ │ └──────────────────────────────────── ├─┬─ 📆 2 ⏱ ──── 💰 g1-5 [📏 1-4 (μ=3, melhor/pior 3)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 2│ 4│ 3│ 5│ 2│ 3│ 4│ 3│ 3│ 4│ │ │ 10│ 4│ 3│ 2│ 2│ 4│ 1│ 3│ 2│ 4│ 2│ │ └──────────────────────────────────── ├─┬─ 📆 3 ⏱ ──── 💰 g1-5 [📏 1-4 (μ=2, melhor/pior 3)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 4│ 3│ 5│ 3│ 4│ 2│ 1│ 4│ 4│ 3│ │ │ 10│ 3│ 1│ 3│ 3│ 3│ 3│ 2│ 4│ 2│ 4│ │ └──────────────────────────────────── ├─┬─ 📆 4 ⏱ ──── 💰 g1-5 [📏 0-4 (μ=2, melhor/pior 2)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 4│ 2│ 1│ 2│ 3│ 1│ 4│ 4│ 3│ 3│ │ │ 10│ 4│ 3│ 3│ 3│ 1│ 5│ 3│ 3│ 2│ 4│ │ └──────────────────────────────────── ├─┬─ 📆 5 ⏱ ──── 💰 g1-5 [📏 1-4 (μ=2, melhor/pior 3)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 1│ 4│ 1│ 3│ 3│ 4│ 2│ 4│ 4│ 1│ │ │ 10│ 4│ 2│ 4│ 3│ 3│ 3│ 5│ 2│ 3│ 4│ │ └──────────────────────────────────── ├─┬─ 📆 6 ⏱ ──── 💰 g1-4 [📏 1-4 (μ=2, melhor/pior 4)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 3│ 4│ 3│ 2│ 4│ 2│ 1│ 4│ 1│ 2│ │ │ 10│ 4│ 3│ 1│ 3│ 4│ 3│ 2│ 3│ 1│ 3│ │ └──────────────────────────────────── ├─┬─ 📆 7 ⏱ ──── 💰 g1-5 [📏 0-4 (μ=2, melhor/pior 4)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 3│ 3│ 4│ 4│ 2│ 3│ 3│ 2│ 1│ 5│ │ │ 10│ 4│ 3│ 4│ 1│ 2│ 1│ 1│ 3│ 5│ 4│ │ └──────────────────────────────────── ├─┬─ 📆 8 ⏱ ──── 💰 g1-5 [📏 1-4 (μ=2, melhor/pior 4)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 5│ 2│ 4│ 4│ 4│ 3│ 4│ 1│ 5│ 1│ │ │ 10│ 1│ 4│ 3│ 3│ 3│ 1│ 3│ 4│ 3│ 4│ │ └──────────────────────────────────── ├─┬─ 📆 9 ⏱ ──── 💰 g1-4 [📏 0-4 (μ=2, melhor/pior 2)] │ │🧍 1 2 3 4 5 6 7 8 9 10 │ │────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ 0│ 2│ 3│ 2│ 3│ 2│ 2│ 1│ 1│ 2│ 2│ │ │ 10│ 4│ 3│ 2│ 3│ 4│ 2│ 2│ 3│ 2│ 3│ │ └──────────────────────────────────── │ 🏆 ⏱ 💰 g:0 ─┴─────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ─┬─────────────────── ├─ Parâmetros ─ P1=1 P2=3 P3=1 P4=10 P5=1000000 P6=20 P7=100 P8=50 P9=1 P10=150 P13=1 ├─ ⚙ ─ P14=100 P16=1 P17=1 P18=3 P19=0 P20=1 P21=0 P22=1 P23=0 P24=1 ═╧═ 🏁 Execução terminada ⏱ ═══ 8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): DETALHE | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 50 | P9(SELECAO): Roleta | P10(PRESSAO): 150 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 1 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): 1-ponto | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ┌─ ⚖ Indicadores ───────────────────────────────────────────────────── │ I1(Resultado): 0 | I2(Tempo(ms)): 0 | I3(Iterações): 241 | I4(Épocas): 10 | │ I5(Gerações): 249 └────────────────────────────────────────────────────────────────────── ... Opção:
Temos agora uma tabela para cada época e informação sobre as distâncias. Na época 0, devido à linha [📏 1-4 (μ=2, melhor/pior 3)] sabemos que as distâncias entre indivíduos vão de 1 a 4, a média das distâncias é 2, e a distância entre o melhor e o pior indivíduo é 3.
A cada linha da época segue-se agora uma tabela 🧍. Esta tabela tem para cada um dos 20 indivíduos na população o seu custo. Tem 10 colunas e tantas linhas quantas necessárias, uma por cada dezena de indivíduos. O indivíduo 14 está na linha com índice 10 e coluna com índice 4, que na época 0 tinha custo 5.
Assim, podemos ter uma ideia mais detalhada dos custos dos indivíduos, e uma ideia da diversidade. Se a diversidade da população for muito baixa, podemos observar a média de distâncias com valor baixo. Se apenas alguns elementos tiverem um bom valor, e a maior parte tiver um valor mau, podemos também observar.
Idealmente pretendemos uma diversidade alta e alto valor nos indivíduos, portanto baixo custo. Por vezes o que ocorre num problema mal afinado, é que todas as soluções ficam com o mesmo valor, e a diversidade é muito baixa. Nesse caso o algoritmo fica estagnado, sendo essa a situação mais crítica a evitar.
Embora possamos observar a situação mais indesejável que pode ocorrer num algoritmo evolutivo, a estagnação, nada sabemos sobre os indivíduos concretos, e o que se passa de uma população para a outra.
Há várias fases para passar de uma época para a outra, e muitos operadores são aplicados. Mas isso é interno aos algoritmos evolutivos, nada é visível neste nível de debug.
É portanto tempo para passarmos para o último nível de debug, COMPLETO. Insira: 1; 4; 3; 2; 4; ENTER; 6.
Opção: 6 ═╤═ ► Execução iniciada ═══ │ 🏆 ⏱ 💰 g:2 ─┴─────────────────── ♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── ├─┬─ 📆 0 ⏱ ──── 💰 g2-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 2 0 3 💰 g:2 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 3 3 1 0 💰 g:4 │ │ 🧍 5 3 1 2 3 💰 g:4 │ │ 🧍 6 3 0 2 3 💰 g:2 │ │ 🧍 7 3 0 3 0 💰 g:3 │ │ 🧍 8 2 0 2 3 💰 g:2 │ │ 🧍 9 0 0 0 3 💰 g:4 │ │ 🧍 10 3 0 0 2 💰 g:2 │ │ 🧍 11 0 3 1 1 💰 g:2 │ │ 🧍 12 1 2 3 0 💰 g:4 │ │ 🧍 13 2 3 3 0 💰 g:2 │ │ 🧍 14 0 0 1 0 💰 g:5 │ │ 🧍 15 0 3 0 0 💰 g:3 │ │ 🧍 16 3 0 0 3 💰 g:2 │ │ 🧍 17 1 2 1 2 💰 g:5 │ │ 🧍 18 3 0 1 1 💰 g:3 │ │ 🧍 19 1 2 1 0 💰 g:5 │ │ 🧍 20 0 0 2 2 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 4│ │ │ 3 │4 │ 3│ │ │ 5 │6 │ 1│ │ │ 7 │8 │ 3│ │ │ 9 │10 │ 2│ │ │ 11 │12 │ 4│ │ │ 13 │14 │ 3│ │ │ 15 │16 │ 3│ │ │ 17 │18 │ 3│ │ │ 19 │20 │ 4│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 150 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 75│ 38│ 49│ 41│ 43│ 59│ 51│ 64│ 33│ 62│ │ │ │ 10│ 72│ 46│ 70│ 25│ 54│ 67│ 28│ 57│ 30│ 36│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2│ 1│ 1│ 0│ 1│ 1│ 1│ 2│ 0│ 2│ │ │ │ 10│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 0│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 10⇄ 14│ 6⇄ 8│ 16⇄ 8│ 5⇄ 1│ 15⇄ 13│ │ │ │ 10│ 11⇄ 17│ 10⇄ 19│ 18⇄ 3│ 2⇄ 7│ 12⇄ 1│ │ 🏆 ⏱ 💰 g:1 ─┴─────────────────── ♛ :: ::♛ :: :: ::♛ ♛ :: ─┬─────────────────── │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 5│ 2⇄ 2│ 2⇄ 2│ 4⇄ 2│ 3⇄ 2│ │ │ │ 10│ 2⇄ 5│ 2⇄ 5│ 3⇄ 3│ 4⇄ 3│ 4⇄ 2│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 14 ───── 📈 1 🟰 17 📉 2 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 4⇄ 3│ 2⇄ 2│ 3⇄ 2│ 4⇄ 4│ 2⇄ 3│ │ │ │ 10│ 4⇄ 2│ 5⇄ 2│ 3⇄ 4│ 4⇄ 4│ 4⇄ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ ├───── 🚶🌍 Imigrantes 9✖ →🆕 ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── 🧹 4 ├─┬─ 📆 1 ⏱ ──── 💰 g1-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 2 3 1 💰 g:1 │ │ 🧍 2 1 2 3 3 💰 g:4 │ │ 🧍 3 3 1 1 1 💰 g:4 │ │ 🧍 4 1 0 3 2 💰 g:4 │ │ 🧍 5 0 0 3 0 💰 g:3 │ │ 🧍 6 1 2 0 2 💰 g:2 │ │ 🧍 7 3 0 1 0 💰 g:5 │ │ 🧍 8 0 0 1 2 💰 g:4 │ │ 🧍 9 0 3 0 0 💰 g:3 │ │ 🧍 10 1 3 3 0 💰 g:2 │ │ 🧍 11 0 2 0 0 💰 g:4 │ │ 🧍 12 3 1 3 3 💰 g:4 │ │ 🧍 13 3 0 0 3 💰 g:2 │ │ 🧍 14 3 0 1 3 💰 g:3 │ │ 🧍 15 1 0 2 3 💰 g:2 │ │ 🧍 16 3 0 2 3 💰 g:2 │ │ 🧍 17 0 1 0 2 💰 g:3 │ │ 🧍 18 3 1 1 0 💰 g:4 │ │ 🧍 19 3 2 2 3 💰 g:4 │ │ 🧍 20 3 3 0 0 💰 g:3 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 2│ │ │ 3 │4 │ 4│ │ │ 5 │6 │ 4│ │ │ 7 │8 │ 2│ │ │ 9 │10 │ 2│ │ │ 11 │12 │ 4│ │ │ 13 │14 │ 1│ │ │ 15 │16 │ 1│ │ │ 17 │18 │ 3│ │ │ 19 │20 │ 3│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 150 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 75│ 43│ 46│ 38│ 57│ 64│ 25│ 30│ 49│ 62│ │ │ │ 10│ 36│ 33│ 72│ 51│ 70│ 67│ 54│ 41│ 28│ 59│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 0│ 1│ 2│ │ │ │ 10│ 0│ 1│ 1│ 1│ 2│ 1│ 1│ 1│ 1│ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 13⇄ 6│ 10⇄ 5│ 17⇄ 14│ 9⇄ 20│ 1⇄ 2│ │ │ │ 10│ 18⇄ 15│ 19⇄ 16│ 7⇄ 4│ 3⇄ 15│ 10⇄ 12│ │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 2│ 2⇄ 3│ 3⇄ 3│ 3⇄ 3│ 1⇄ 4│ │ │ │ 10│ 4⇄ 2│ 4⇄ 2│ 5⇄ 4│ 4⇄ 2│ 2⇄ 4│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 10 ───── 📈 5 🟰 12 📉 3 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 4⇄ 2│ 3⇄ 1│ 4⇄ 2│ 2⇄ 3│ 4⇄ 4│ │ │ │ 10│ 3⇄ 3│ 4⇄ 2│ 3⇄ 2│ 5⇄ 3│ 4⇄ 2│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ ├───── 🚶🌍 Imigrantes 7✖ →🆕 ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── ├─┬─ 📆 2 ⏱ ──── 💰 g1-5 ├─┬─ 📆 3 ⏱ ──── 💰 g1-5 ├─┬─ 📆 4 ⏱ ──── 💰 g1-5 ├─┬─ 📆 5 ⏱ 1ms ──── 💰 g1-5 ├─┬─ 📆 6 ⏱ 1ms ──── 💰 g1-4 ├─┬─ 📆 7 ⏱ 1ms ──── 💰 g1-5 ├─┬─ 📆 8 ⏱ 1ms ──── 💰 g1-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 2 3 2 3 💰 g:5 │ │ 🧍 2 0 1 3 1 💰 g:2 │ │ 🧍 3 1 1 3 3 💰 g:4 │ │ 🧍 4 2 2 2 1 💰 g:4 │ │ 🧍 5 2 2 2 0 💰 g:4 │ │ 🧍 6 1 3 0 1 💰 g:3 │ │ 🧍 7 3 0 0 0 💰 g:4 │ │ 🧍 8 0 2 3 1 💰 g:1 │ │ 🧍 9 0 1 0 1 💰 g:5 │ │ 🧍 10 1 2 0 3 💰 g:1 │ │ 🧍 11 1 3 0 3 💰 g:1 │ │ 🧍 12 1 0 0 1 💰 g:4 │ │ 🧍 13 1 0 3 1 💰 g:3 │ │ 🧍 14 0 2 3 3 💰 g:3 │ │ 🧍 15 1 3 3 2 💰 g:3 │ │ 🧍 16 3 0 3 1 💰 g:1 │ │ 🧍 17 3 3 0 3 💰 g:3 │ │ 🧍 18 2 1 0 0 💰 g:4 │ │ 🧍 19 2 3 0 3 💰 g:3 │ │ 🧍 20 2 2 0 0 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 4│ │ │ 3 │4 │ 4│ │ │ 5 │6 │ 4│ │ │ 7 │8 │ 4│ │ │ 9 │10 │ 3│ │ │ 11 │12 │ 2│ │ │ 13 │14 │ 3│ │ │ 15 │16 │ 3│ │ │ 17 │18 │ 3│ │ │ 19 │20 │ 2│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 150 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 25│ 64│ 30│ 41│ 36│ 57│ 33│ 67│ 28│ 75│ │ │ │ 10│ 70│ 38│ 51│ 59│ 49│ 72│ 54│ 46│ 62│ 43│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 0│ 2│ 0│ 1│ 1│ 1│ 0│ 2│ 0│ 2│ │ │ │ 10│ 1│ 1│ 1│ 1│ 1│ 2│ 1│ 1│ 1│ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 19│ 5⇄ 20│ 13⇄ 12│ 16⇄ 10│ 4⇄ 6│ │ │ │ 10│ 17⇄ 15│ 10⇄ 8│ 11⇄ 2│ 16⇄ 18│ 8⇄ 14│ │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 3│ 4⇄ 4│ 3⇄ 4│ 1⇄ 1│ 4⇄ 3│ │ │ │ 10│ 3⇄ 3│ 1⇄ 1│ 1⇄ 2│ 1⇄ 4│ 1⇄ 3│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 12 ───── 📈 3 🟰 14 📉 3 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 2│ 4⇄ 4│ 3⇄ 3│ 2⇄ 3│ 4⇄ 2│ │ │ │ 10│ 2⇄ 1│ 1⇄ 2│ 2⇄ 2│ 3⇄ 2│ 3⇄ 2│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ ├───── 🚶🌍 Imigrantes 6✖ →🆕 ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── 🧹 15 🧹 17 ├─┬─ 📆 9 ⏱ 1ms ──── 💰 g1-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 3 3 1 💰 g:2 │ │ 🧍 2 0 2 3 0 💰 g:3 │ │ 🧍 3 2 0 2 1 💰 g:2 │ │ 🧍 4 3 1 0 3 💰 g:3 │ │ 🧍 5 0 3 1 3 💰 g:2 │ │ 🧍 6 0 2 0 3 💰 g:2 │ │ 🧍 7 0 2 3 1 💰 g:1 │ │ 🧍 8 1 3 0 3 💰 g:1 │ │ 🧍 9 0 3 3 2 💰 g:2 │ │ 🧍 10 2 2 3 1 💰 g:2 │ │ 🧍 11 1 3 3 1 💰 g:4 │ │ 🧍 12 1 2 0 1 💰 g:3 │ │ 🧍 13 3 0 0 3 💰 g:2 │ │ 🧍 14 1 0 3 1 💰 g:3 │ │ 🧍 15 2 2 2 0 💰 g:4 │ │ 🧍 16 0 1 3 1 💰 g:2 │ │ 🧍 17 2 2 0 3 💰 g:2 │ │ 🧍 18 0 3 2 2 💰 g:3 │ │ 🧍 19 3 2 0 3 💰 g:2 │ │ 🧍 20 1 2 0 1 💰 g:3 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 2│ │ │ 3 │4 │ 4│ │ │ 5 │6 │ 2│ │ │ 7 │8 │ 4│ │ │ 9 │10 │ 3│ │ │ 11 │12 │ 2│ │ │ 13 │14 │ 3│ │ │ 15 │16 │ 4│ │ │ 17 │18 │ 4│ │ │ 19 │20 │ 2│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 150 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 57│ 41│ 49│ 36│ 51│ 46│ 72│ 75│ 67│ 54│ │ │ │ 10│ 28│ 33│ 64│ 30│ 25│ 59│ 62│ 43│ 70│ 38│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 1│ 1│ 1│ 0│ 1│ 1│ 2│ 1│ 2│ 1│ │ │ │ 10│ 0│ 1│ 1│ 1│ 0│ 1│ 2│ 0│ 2│ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 10⇄ 1│ 19⇄ 3│ 8⇄ 17│ 14⇄ 12│ 7⇄ 16│ │ │ │ 10│ 17⇄ 7│ 9⇄ 9│ 20⇄ 6│ 5⇄ 2│ 19⇄ 13│ │ 🏆 ⏱ 1ms 💰 g:0 ─┴─────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ─┬─────────────────── │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 2│ 2⇄ 2│ 1⇄ 2│ 3⇄ 3│ 1⇄ 2│ │ │ │ 10│ 2⇄ 1│ 2⇄ 2│ 3⇄ 2│ 2⇄ 3│ 2⇄ 2│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 12 ───── 📈 3 🟰 11 📉 6 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 3⇄ 1│ 1⇄ 5│ 1⇄ 4│ 4⇄ 0│ 4⇄ 2│ │ │ │ 10│ 2⇄ 1│ 2⇄ 3│ 2⇄ 2│ 3⇄ 2│ 2⇄ 2│ │ │ └──────────────────────────────────── ├─ Parâmetros ─ P1=1 P2=4 P3=1 P4=10 P5=1000000 P6=20 P7=100 P8=50 P9=1 P10=150 P13=1 ├─ ⚙ ─ P14=100 P16=1 P17=1 P18=3 P19=0 P20=1 P21=0 P22=1 P23=0 P24=1 ═╧═ 🏁 Execução terminada ⏱ 1ms ═══ 8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): COMPLETO | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 50 | P9(SELECAO): Roleta | P10(PRESSAO): 150 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 1 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): 1-ponto | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── :: ♛ ♛ :: :: :: ::♛ ♛ :: ┌─ ⚖ Indicadores ───────────────────────────────────────────────────── │ I1(Resultado): 0 | I2(Tempo(ms)): 1 | I3(Iterações): 241 | I4(Épocas): 10 | │ I5(Gerações): 249 └────────────────────────────────────────────────────────────────────── ... Opção:
A informação é agora bastante extensa, mas cortamos a informação de debug desde a época 2 ├─┬─ 📆 2 ⏱ ──── 💰 g1-5 até à época 7 ├─┬─ 📆 7 ⏱ 1ms ──── 💰 g1-5. Mostramos apenas as primeiras e últimas épocas.
Em cada época (vamos ver a época 0) temos agora toda a população (├───── 🧍🧑🤝🧑🚶 ─────), mostrando a codificação de cada elemento e o seu custo (🧍 1 0 2 0 3 💰 g:2). Temos após a população um mapa de distâncias entre indivíduos (├───── 📏 ─────), caso a população seja 10 ou menor, ou pares de distâncias entre elementos consecutivos. Assim ficamos com uma ideia mais completa da diversidade da população.
Mostramos informação de todas as fases. A primeira fase é a seleção dos pais (├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ─────).
Há informação na época 0 de que irão ser selecionados 20 pais pelo método Roleta, com pressão 150 (├───── Roleta, pressão 150 ─────). Este valor corresponde a 1,5, sendo que o valor 1 todos os membros têm a mesma probabilidade, e com 2 os melhores têm muito mais possibildiades de ser escolhidos. A permilagem de cada indivíduo é colocada na tabela 100%.
Podemos ver a diferença entre o 1 e o 2, tendo o indivíduo 1 custo 2 e o indivíduo 2 custo 4. A probabilidade de ser selecionado o indivíduo 1 é de 7,5% enquanto que o indivíduo 2 tem probabilidade de 3,8%.
Como resultado destas probabilidades, a tabela seguinte, #Pai, tem o número de vezes que cada indivíduo foi escolhido para pai. O primeiro indivíduo foi escolhido 2 vezes. Podemos ver alguns indivíduos que nem foram escolhidos, como o 4.
Terminada a fase de seleção dos pais, arranca a fase de reprodução (├─┬─── FASE 🧬 Reproduzir 20 pais ─────). Nesta fase temos os pais emparelhados (├───── Pais (🧑🤝🧑 ) ─────). Na tabela IDs podemos ver os indivíduos da população original por uma ordem de reprodução. Podemos confirmar que o indivíduo 1 está duas vezes, na posição 8 e 20. Irá reproduzir com o indivíduo 5 e 12.
Os filhos são gerados com base nestes pares, o primeiro com o segundo, o terceiro com o quarto e assim sucessivamente. Há sempre dois filhos por cada casal de pais. Durante a geração dos filhos, foi encontrado uma solução melhor que o registo global.
As duas tabelas seguintes têm os custos dos pais (├───── Pais (💰 ) ─────) e dos filhos (├───── Filhos (💰 ) 🧬 10 🦠 14 ───── 📈 1 🟰 17 📉 2), onde se pode ver o GAP geracional. Podemos ver por exemplo, o casal 11 e 12, tinham custo 2 e 5 e os seus filhos ficaram com custos 4 e 2. Neste caso um ficou entre os valores dos pais, o outro ficou com o melhor valor dos pais.
Na geração houve 1 melhoramento, 2 que pioraram o valor de ambos os pais, e 17 que ficaram entre o valor dos pais. Esta informação está na linha dos filhos: 📈 1 🟰 17 📉 2.
A fase de sobrevivência (├─┬─── FASE ⚔️ Sobrevivência ─────), atendendo a que o método é a idade, não há muito a mostrar, dado que a geração nova substitui a geração antiga. Há no entanto indicação sobre elite e imigrantes. Neste caso a Elite não foi necessária, já que o melhor elemento da nova geração até é melhor que o melhor da geração anterior. Nos imigrantes entrou 1, saindo o elemento 9: ├───── 🚶🌍 Imigrantes 9✖ →🆕 ─────.
Ocorreu nesta época a fase de limpeza, tendo sido eliminado um elemento que estava duplicado, atendendo às configurações por omissão: └───── FASE 🌈 Diversidade - limpeza ───── 🧹 4
Esta análise permite ver a origem do elemento que tem a solução ótima. Focando agora na época 9, vemos que o filho com custo 0 é o 8. Esse elemento tem como irmão uma solução de custo 4, e ambos os pais têm custo 3. Os pais sãos os elementos 12 e 14, vamos ver a sua codificação:
🧍 12 1 2 0 1 💰 g:3🧍 14 1 0 3 1 💰 g:3O estado de custo 0 é codificado com 2 0 3 1. Parte da codificação está nos pais, mas o primeiro número não está, o que significa que a mutação trocou esse valor. Vemos aqui um exemplo que a mutação ajudou, mas neste caso mesmo que o elemento 14 estivesse sozinho, após mutar incrementando o primeiro número, passa de uma solução de custo 3 para uma solução de custo 0.
Esta é uma análise bastante completa tendo muita informação. Pode ser utilizada em instâncias pequenas para compreender os algoritmos e diferentes opções, e também para um dado problema procurar entender porque algumas parametrizações resultam melhor que outras. Aumentando o entendimento no problema é possível que apareçam oportunidades de melhoria que se possam explorar.
Para identificar as melhores parametrizações, temos de ter testes empíricos, tal como nos restantes exemplos, e esse é o tema da próxima secção.
O modo interativo é importante para compreender e aprender, mas para se poder tirar conclusões temos de ter um número considerável de execuções.
Atendendo ao volume de parâmetros nos algoritmos evolutivos, estes testes vão utilizar desde logo um cluster (Deucalion).
Neste estudo foi identificada a melhor parametrização para este problema e codificação: P6=20 P7=100 P8=0 P9=1 P10=175 P13=1 P14=100 P16=1 P17=0 P18=3 P19=0 P24=1 P20=0.
Podemos ver como a alteração da parametrização afeta este exemplo:
Opção: 6 ═╤═ ► Execução iniciada ═══ │ 🏆 ⏱ 💰 g:2 ─┴─────────────────── ♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── ├─┬─ 📆 0 ⏱ ──── 💰 g2-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 2 0 3 💰 g:2 │ │ 🧍 2 3 1 1 0 💰 g:4 │ │ 🧍 3 1 0 3 0 💰 g:3 │ │ 🧍 4 3 3 1 0 💰 g:4 │ │ 🧍 5 3 1 2 3 💰 g:4 │ │ 🧍 6 3 0 2 3 💰 g:2 │ │ 🧍 7 3 0 3 0 💰 g:3 │ │ 🧍 8 2 0 2 3 💰 g:2 │ │ 🧍 9 0 0 0 3 💰 g:4 │ │ 🧍 10 3 0 0 2 💰 g:2 │ │ 🧍 11 0 3 1 1 💰 g:2 │ │ 🧍 12 1 2 3 0 💰 g:4 │ │ 🧍 13 2 3 3 0 💰 g:2 │ │ 🧍 14 0 0 1 0 💰 g:5 │ │ 🧍 15 0 3 0 0 💰 g:3 │ │ 🧍 16 3 0 0 3 💰 g:2 │ │ 🧍 17 1 2 1 2 💰 g:5 │ │ 🧍 18 3 0 1 1 💰 g:3 │ │ 🧍 19 1 2 1 0 💰 g:5 │ │ 🧍 20 0 0 2 2 💰 g:4 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 4│ │ │ 3 │4 │ 3│ │ │ 5 │6 │ 1│ │ │ 7 │8 │ 3│ │ │ 9 │10 │ 2│ │ │ 11 │12 │ 4│ │ │ 13 │14 │ 3│ │ │ 15 │16 │ 3│ │ │ 17 │18 │ 3│ │ │ 19 │20 │ 4│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 175 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 88│ 32│ 48│ 36│ 40│ 64│ 52│ 72│ 24│ 68│ │ │ │ 10│ 84│ 44│ 80│ 12│ 56│ 76│ 16│ 60│ 20│ 28│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2│ 1│ 1│ 0│ 1│ 1│ 2│ 1│ 0│ 2│ │ │ │ 10│ 1│ 1│ 2│ 0│ 1│ 2│ 0│ 1│ 1│ 0│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 10⇄ 13│ 6⇄ 8│ 16⇄ 7│ 5⇄ 1│ 15⇄ 13│ │ │ │ 10│ 11⇄ 16│ 10⇄ 19│ 18⇄ 3│ 2⇄ 7│ 12⇄ 1│ │ 🏆 ⏱ 💰 g:1 ─┴─────────────────── ::♛ :: ::♛ :: ♛ :: :: ♛ ─┬─────────────────── │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 2│ 2⇄ 2│ 2⇄ 3│ 4⇄ 2│ 3⇄ 2│ │ │ │ 10│ 2⇄ 2│ 2⇄ 5│ 3⇄ 3│ 4⇄ 3│ 4⇄ 2│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 0 ───── 📈 2 🟰 14 📉 4 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 3⇄ 1│ 2⇄ 2│ 2⇄ 2│ 3⇄ 4│ 3⇄ 2│ │ │ │ 10│ 3⇄ 3│ 4⇄ 4│ 5⇄ 3│ 4⇄ 3│ 4⇄ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── 🧹 5 🧹 20 🧹 16 🧹 18 ├─┬─ 📆 1 ⏱ ──── 💰 g1-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 1 2 0 3 💰 g:1 │ │ 🧍 2 0 2 0 0 💰 g:4 │ │ 🧍 3 3 0 3 0 💰 g:3 │ │ 🧍 4 3 1 1 0 💰 g:4 │ │ 🧍 5 1 0 1 1 💰 g:5 │ │ 🧍 6 3 0 1 2 💰 g:4 │ │ 🧍 7 3 0 0 0 💰 g:4 │ │ 🧍 8 0 0 1 1 💰 g:3 │ │ 🧍 9 3 3 0 3 💰 g:3 │ │ 🧍 10 2 3 3 0 💰 g:2 │ │ 🧍 11 0 3 0 0 💰 g:3 │ │ 🧍 12 3 1 2 3 💰 g:4 │ │ 🧍 13 3 1 0 3 💰 g:3 │ │ 🧍 14 3 0 0 3 💰 g:2 │ │ 🧍 15 3 0 2 3 💰 g:2 │ │ 🧍 16 3 3 0 2 💰 g:1 │ │ 🧍 17 2 1 1 0 💰 g:3 │ │ 🧍 18 3 2 0 3 💰 g:2 │ │ 🧍 19 2 3 0 3 💰 g:3 │ │ 🧍 20 0 1 0 3 💰 g:5 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 2│ │ │ 3 │4 │ 2│ │ │ 5 │6 │ 2│ │ │ 7 │8 │ 3│ │ │ 9 │10 │ 3│ │ │ 11 │12 │ 4│ │ │ 13 │14 │ 1│ │ │ 15 │16 │ 3│ │ │ 17 │18 │ 4│ │ │ 19 │20 │ 2│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 175 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 88│ 36│ 44│ 20│ 16│ 24│ 32│ 48│ 40│ 68│ │ │ │ 10│ 60│ 28│ 64│ 72│ 80│ 84│ 56│ 76│ 52│ 12│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2│ 0│ 1│ 1│ 0│ 0│ 1│ 1│ 1│ 1│ │ │ │ 10│ 1│ 1│ 1│ 2│ 1│ 2│ 1│ 2│ 1│ 0│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 1⇄ 11│ 17⇄ 3│ 13⇄ 4│ 8⇄ 1│ 12⇄ 15│ │ │ │ 10│ 10⇄ 16│ 18⇄ 9│ 16⇄ 14│ 7⇄ 19│ 18⇄ 14│ │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 1⇄ 3│ 3⇄ 3│ 3⇄ 4│ 3⇄ 1│ 4⇄ 2│ │ │ │ 10│ 2⇄ 1│ 2⇄ 3│ 1⇄ 2│ 4⇄ 3│ 2⇄ 2│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 0 ───── 📈 2 🟰 14 📉 4 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 4⇄ 1│ 3⇄ 4│ 4⇄ 4│ 2⇄ 1│ 4⇄ 4│ │ │ │ 10│ 1⇄ 4│ 3⇄ 2│ 3⇄ 2│ 2⇄ 2│ 2⇄ 2│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── 🧹 2 🧹 7 🧹 8 🧹 12 🧹 17 ├─┬─ 📆 2 ⏱ ──── 💰 g1-4 ├─┬─ 📆 3 ⏱ ──── 💰 g1-4 ├─┬─ 📆 4 ⏱ ──── 💰 g1-4 ├─┬─ 📆 5 ⏱ 1ms ──── 💰 g1-4 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 0 2 2 💰 g:4 │ │ 🧍 2 1 3 1 2 💰 g:2 │ │ 🧍 3 0 3 2 1 💰 g:4 │ │ 🧍 4 0 2 2 0 💰 g:4 │ │ 🧍 5 3 0 1 3 💰 g:3 │ │ 🧍 6 0 3 3 3 💰 g:4 │ │ 🧍 7 3 3 3 2 💰 g:4 │ │ 🧍 8 3 3 0 2 💰 g:1 │ │ 🧍 9 2 0 3 3 💰 g:1 │ │ 🧍 10 0 3 0 3 💰 g:3 │ │ 🧍 11 0 0 0 3 💰 g:4 │ │ 🧍 12 2 3 0 3 💰 g:3 │ │ 🧍 13 0 3 0 2 💰 g:1 │ │ 🧍 14 1 3 1 3 💰 g:2 │ │ 🧍 15 3 0 0 0 💰 g:4 │ │ 🧍 16 0 1 1 3 💰 g:4 │ │ 🧍 17 0 0 1 3 💰 g:3 │ │ 🧍 18 1 2 1 3 💰 g:3 │ │ 🧍 19 0 0 1 1 💰 g:3 │ │ 🧍 20 2 2 3 3 💰 g:3 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 3│ │ │ 3 │4 │ 2│ │ │ 5 │6 │ 3│ │ │ 7 │8 │ 1│ │ │ 9 │10 │ 3│ │ │ 11 │12 │ 2│ │ │ 13 │14 │ 3│ │ │ 15 │16 │ 4│ │ │ 17 │18 │ 2│ │ │ 19 │20 │ 4│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 175 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 13│ 72│ 36│ 40│ 44│ 24│ 20│ 80│ 88│ 56│ │ │ │ 10│ 32│ 64│ 84│ 76│ 28│ 16│ 60│ 68│ 48│ 52│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 0│ 1│ 1│ 1│ 1│ 0│ 1│ 1│ 2│ 1│ │ │ │ 10│ 1│ 1│ 2│ 1│ 1│ 0│ 1│ 2│ 1│ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 5⇄ 12│ 3⇄ 20│ 10⇄ 2│ 19⇄ 13│ 9⇄ 7│ │ │ │ 10│ 8⇄ 18│ 11⇄ 14│ 9⇄ 4│ 18⇄ 15│ 17⇄ 13│ │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 3⇄ 3│ 4⇄ 3│ 3⇄ 2│ 3⇄ 1│ 1⇄ 4│ │ │ │ 10│ 1⇄ 3│ 4⇄ 2│ 1⇄ 4│ 3⇄ 4│ 3⇄ 1│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 0 ───── 📈 5 🟰 12 📉 3 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 3⇄ 3│ 2⇄ 2│ 2⇄ 1│ 4⇄ 4│ 3⇄ 4│ │ │ │ 10│ 2⇄ 1│ 2⇄ 2│ 4⇄ 3│ 2⇄ 2│ 4⇄ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── 🧹 16 🧹 15 🧹 14 ├─┬─ 📆 6 ⏱ 1ms ──── 💰 g1-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 0 3 1 2 💰 g:1 │ │ 🧍 2 0 0 0 2 💰 g:4 │ │ 🧍 3 3 2 0 3 💰 g:2 │ │ 🧍 4 3 0 0 3 💰 g:2 │ │ 🧍 5 0 0 3 3 💰 g:3 │ │ 🧍 6 2 2 2 0 💰 g:4 │ │ 🧍 7 1 0 0 3 💰 g:2 │ │ 🧍 8 0 3 1 3 💰 g:2 │ │ 🧍 9 1 3 0 3 💰 g:1 │ │ 🧍 10 1 3 1 3 💰 g:2 │ │ 🧍 11 2 3 3 2 💰 g:4 │ │ 🧍 12 2 0 3 2 💰 g:3 │ │ 🧍 13 0 0 1 2 💰 g:4 │ │ 🧍 14 0 3 3 1 💰 g:2 │ │ 🧍 15 2 2 3 1 💰 g:2 │ │ 🧍 16 2 3 0 3 💰 g:3 │ │ 🧍 17 3 0 1 3 💰 g:3 │ │ 🧍 18 1 2 3 3 💰 g:4 │ │ 🧍 19 0 3 3 1 💰 g:2 │ │ 🧍 20 1 2 1 2 💰 g:5 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 2│ │ │ 3 │4 │ 1│ │ │ 5 │6 │ 4│ │ │ 7 │8 │ 3│ │ │ 9 │10 │ 1│ │ │ 11 │12 │ 1│ │ │ 13 │14 │ 3│ │ │ 15 │16 │ 3│ │ │ 17 │18 │ 3│ │ │ 19 │20 │ 4│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 175 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 88│ 16│ 60│ 52│ 40│ 28│ 56│ 68│ 84│ 64│ │ │ │ 10│ 20│ 36│ 24│ 76│ 72│ 44│ 48│ 32│ 80│ 12│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 1│ 1│ 1│ 1│ 1│ 0│ 1│ 2│ 1│ 2│ │ │ │ 10│ 0│ 1│ 0│ 2│ 1│ 1│ 1│ 1│ 1│ 1│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 20⇄ 7│ 17⇄ 10│ 2⇄ 19│ 15⇄ 18│ 10⇄ 8│ │ │ │ 10│ 16⇄ 3│ 9⇄ 12│ 8⇄ 14│ 5⇄ 14│ 1⇄ 4│ │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 5⇄ 2│ 3⇄ 2│ 4⇄ 2│ 2⇄ 4│ 2⇄ 2│ │ │ │ 10│ 3⇄ 2│ 1⇄ 3│ 2⇄ 2│ 3⇄ 2│ 1⇄ 2│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 0 ───── 📈 0 🟰 15 📉 5 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 5⇄ 3│ 3⇄ 4│ 4⇄ 3│ 4⇄ 4│ 2⇄ 2│ │ │ │ 10│ 2⇄ 2│ 3⇄ 4│ 4⇄ 2│ 3⇄ 2│ 4⇄ 3│ │ │ └──────────────────────────────────── │ ├─┬─── FASE ⚔️ Sobrevivência ───── │ │ ├───── ⏳ Idade ───── │ │ ├───── 👑 Elite 1→13 ───── │ │ └──────────────────────────────────── │ └───── FASE 🌈 Diversidade - limpeza ───── 🧹 5 🧹 10 🧹 12 ├─┬─ 📆 7 ⏱ 1ms ──── 💰 g1-5 │ ├───── 🧍🧑🤝🧑🚶 ───── │ │ 🧍 1 3 3 1 2 💰 g:3 │ │ 🧍 2 0 0 0 2 💰 g:4 │ │ 🧍 3 0 3 3 1 💰 g:2 │ │ 🧍 4 0 0 3 3 💰 g:3 │ │ 🧍 5 0 3 3 3 💰 g:4 │ │ 🧍 6 2 3 3 3 💰 g:4 │ │ 🧍 7 1 0 0 2 💰 g:3 │ │ 🧍 8 2 2 0 3 💰 g:2 │ │ 🧍 9 1 3 1 3 💰 g:2 │ │ 🧍 10 0 3 1 2 💰 g:1 │ │ 🧍 11 1 2 3 1 💰 g:4 │ │ 🧍 12 0 0 3 2 💰 g:3 │ │ 🧍 13 0 0 0 1 💰 g:4 │ │ 🧍 14 3 3 1 3 💰 g:4 │ │ 🧍 15 1 0 1 3 💰 g:3 │ │ 🧍 16 1 2 1 3 💰 g:3 │ │ 🧍 17 1 2 1 2 💰 g:5 │ │ 🧍 18 2 2 2 3 💰 g:4 │ │ 🧍 19 0 1 2 0 💰 g:4 │ │ 🧍 20 1 2 1 3 💰 g:3 │ ├───── 📏 ───── │ │ 🧍 🧍 📏 │ │ ────┼────┼────┼ │ │ 1 │2 │ 3│ │ │ 3 │4 │ 2│ │ │ 5 │6 │ 1│ │ │ 7 │8 │ 3│ │ │ 9 │10 │ 2│ │ │ 11 │12 │ 3│ │ │ 13 │14 │ 4│ │ │ 15 │16 │ 1│ │ │ 17 │18 │ 3│ │ │ 19 │20 │ 4│ │ │ ────┴────┴────┴ │ ├─┬─── FASE 🧩 Selecionar 20 🧑🤝🧑 pais ───── │ │ ├───── Roleta, pressão 175 ───── │ │ │ 100% 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 60│ 40│ 76│ 52│ 32│ 24│ 48│ 80│ 84│ 88│ │ │ │ 10│ 20│ 68│ 16│ 36│ 64│ 72│ 12│ 44│ 28│ 56│ │ │ ├───── Número de seleções ───── │ │ │ #Pai 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 1│ 1│ 1│ 1│ 1│ 0│ 1│ 2│ 1│ 2│ │ │ │ 10│ 1│ 1│ 0│ 1│ 1│ 2│ 0│ 1│ 0│ 2│ │ │ └──────────────────────────────────── │ ├─┬─── FASE 🧬 Reproduzir 20 pais ───── │ │ ├───── Pais (🧑🤝🧑 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 8⇄ 2│ 4⇄ 5│ 10⇄ 15│ 20⇄ 16│ 18⇄ 12│ │ │ │ 10│ 8⇄ 11│ 9⇄ 3│ 10⇄ 1│ 20⇄ 16│ 7⇄ 14│ │ 🏆 ⏱ 1ms 💰 g:0 ─┴─────────────────── ::♛ :: :: ♛ ♛ :: ::♛ :: ─┬─────────────────── │ │ ├───── Pais (💰 ) ───── │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 2⇄ 4│ 3⇄ 4│ 1⇄ 3│ 3⇄ 3│ 4⇄ 3│ │ │ │ 10│ 2⇄ 4│ 2⇄ 2│ 1⇄ 3│ 3⇄ 3│ 3⇄ 4│ │ │ ├───── Filhos (💰 ) 🧬 10 🦠 0 ───── 📈 1 🟰 18 📉 1 │ │ │ 🧍 1 2 3 4 5 6 7 8 9 10 │ │ │ ────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼ │ │ │ 0│ 4⇄ 2│ 3⇄ 3│ 3⇄ 3│ 3⇄ 3│ 3⇄ 3│ │ │ │ 10│ 2⇄ 3│ 2⇄ 4│ 3⇄ 3│ 3⇄ 3│ 3⇄ 0│ │ │ └──────────────────────────────────── ├─ Parâmetros ─ P1=1 P2=4 P3=1 P4=10 P5=1000000 P6=20 P7=100 P8=0 P9=1 P10=175 P13=1 ├─ ⚙ ─ P14=100 P16=1 P17=0 P18=3 P19=0 P20=0 P21=0 P22=1 P23=0 P24=1 ═╧═ 🏁 Execução terminada ⏱ 1ms ═══ 8 Damas (Inteira) ┌─ ⚙ Parâmetros ────────────────────────────────────────────────────── │ P1(ALGORITMO): Algoritmo Evolutivo | P2(NIVEL_DEBUG): COMPLETO | P3(SEMENTE): 1 │ P4(LIMITE_TEMPO): 10 | P5(LIMITE_ITERACOES): 1000000 | P6(POPULACAO): 20 │ P7(PROB_CRUZAR): 100 | P8(PROB_MUTAR): 0 | P9(SELECAO): Roleta | P10(PRESSAO): 175 │ P13(SOBREVIVENCIA): Idade | P14(PERC_DESCENDENTES): 100 | P16(ELITISMO): 1 │ P17(IMIGRANTES): 0 | P18(DIVERSIDADE): Limpeza | P19(DIST_MINIMA): 0 │ P20(TIPO_CRUZAR): uniforme | P21(TIPO_MUTAR): 0 | P22(TIPO_VIZINHO): incDecValor │ P23(LIMITE_VIZINHOS): 0 | P24(TIPO_DISTANCIA): Hamming └────────────────────────────────────────────────────────────────────── ::♛ :: :: ♛ ♛ :: ::♛ :: ┌─ ⚖ Indicadores ───────────────────────────────────────────────────── │ I1(Resultado): 0 | I2(Tempo(ms)): 1 | I3(Iterações): 209 | I4(Épocas): 8 | │ I5(Gerações): 215 └────────────────────────────────────────────────────────────────────── ... Opção:
Podemos ver que foram utilizadas apenas 8 épocas. Neste caso a solução foi gerada de pais com custo 3 e 4, tendo um irmão com custo 3. Esses pais foram os estados 7 e 14:
🧍 7 1 0 0 2 💰 g:3🧍 14 3 3 1 3 💰 g:4A solução gerada resulta na codificação 1 3 0 2, tendo sido utilizado o operador de cruzamento uniforme, e pela informação não houve mutações. Assim este filho resultou em cada posição de um valor do pai ou da mãe. O operador de cruzamento inicial de 1 ponto, não poderia gerar este filho destes dois pais, atendendo a que o primeiro e último número pertence ao elemento 7, mas o segundo número pertence ao elemento 14. O operador uniforme pode perfeitamente gerar este filho.
| TesteTVector | Aspirador 1 | Aspirador 2 | Puzzle 8 | 8 Damas | Partição | 8 Damas CI | 8 Damas CP | Partição CB |
1.9.8