Algoritmos de Seleção: Método da Roleta

Falar um pouco sobre métodos de seleção. Basicamente método de seleção é um método utilizado para selecionar ou "sorteiar" alguma coisa e são bastante usados nos algoritmos genéticos, na parte de selecionar os melhores soluções.

Quanto aos algoritmos genéticos, falo outro dia, mas os métodos de seleção pode ser útil em outras áreas, principalmente em jogos. Por exemplo, imagine um jogo de quiz para um jogo educacional. Você quer focar as perguntas em uma só pergunta, mas sempre colocando perguntas algumas perguntas de assuntos passados, para fins de estar sempre relembrando. Ou seja, é um quiz que sorteará as perguntas, mas algumas perguntas tem que ter uma chance maior de aparecer do que as outras. É nesse caso que uso o método da roleta.



Vamos ver como funciona o método da roleta. Cada pergunta vai ter um peso de probabilidade. Geralmente eu coloco como valores inteiros. Então vamos supor que tenhamos 10 perguntas com os seguintes pesos no vetor {1,1,1,1,2,3,4,5,5,5}. Como podemos ver, os pesos maiores estão no final, ou seja, as últimas perguntas é que vão ter maiores chances de ocorrer. Basta ver a tabela abaixo as probabilidades de cada um ocorrer:

Posicao  Peso   Probablidade
   0       1         3,57%
   1       1         3,57%
   2       1         3,57%
   3       1         3,57%
   4       2         7,14%
   5       3        10,72%
   6       4        14,28%
   7       5        17,86%
   8       5        17,86%
   9       5        17,86%
----------------------------
Total:    28       100,00%

A grande vantagem da roleta é que dependo da situação, eu posso adaptar os pesos de forma que seja mais interessante para mim. Por exemplo, nesse quiz, se a pessoa errar a pergunta, quero que aumente a probabilidade dessa pergunta seja feita novamente a fim de verificar se a pessoa aprendeu. Para isso, basta eu adicionar mais peso na pergunta. Por exemplo, a pessoa errou a pergunta da posição 2, então adiciono mais 3 unidades (esse é um valor arbitrário) para essa pergunta, ficando com a seguinte situação:

Posicao  Peso   Probablidade
   0       1         3,23%
   1       1         3,23%
   2       4        12,90%
   3       1         3,23%
   4       2         6,45%
   5       3         9,67%
   6       4        12,90%
   7       5        16,13%
   8       5        16,13%
   9       5        16,13%
----------------------------
Total:    31       100,00%


Como pode ver, a probabidade da pergunta 2 aumentou de 3,57% para 12,90%, obviamente, as probabilidade das outras diminuiram, mas ainda mantendo a proporção. Se quero diminuir a probablilidade, diminuo o peso e assim por diante.

O algoritmo basicamente faz com que cada posição tenha uma posição numa espécie de régua, e o peso é como se indicassemos o quanto dessa régua, a tal pergunta ocupa, como ilustra a imagem para o vetor original:



Então, sorteamos uma posição dessa régua e vemos qual é o selecionado. Por exemplo, se o valor que sorteamos resultou 14, podemos ver na régua que o número 14 é terreno do elemento 7.

Vamos ver a implementação lógica: primeira coisa que vamos precisar saber são os pesos. Vamos utilizar os mesmos pesos do exemplo acima: {1,1,1,1,2,3,4,5,5,5}, mas esses valores são todos definidos pelo programador:

01. var pesos[10]:int = {1,1,1,1,2,3,4,5,5,5};

Em seguida, precisamos saber a somatório dos pesos:

01. var pesos[10]:int = {1,1,1,1,2,3,4,5,5,5};
02  var somaPeso:int = 0;
03. PARA var i=0 ATE 9 FAÇA
04.   somaPeso+=pesos[i];
05. FIMPARA

Então, sorteamos um número entre 0 até o somatório do peso:

01. var pesos[10]:int = {1,1,1,1,2,3,4,5,5,5};
02  var somaPeso:int = 0;
03. PARA var i=0 ATE 9 FAÇA
04.   somaPeso+=pesos[i];
05. FIMPARA
06. var sorteio:INT = ALEATORIO(0,somaPeso);

Aqui nós já sorteamos o número que queremos, mas precisamos mapear qual é a posição que queremos, para isso podemos fazer o método da decomposição dos números:

01. var pesos[10]:int = {1,1,1,1,2,3,4,5,5,5};
02  var somaPeso:int = 0;
03. PARA var i=0 ATE 9 FAÇA
04.   somaPeso+=pesos[i];
05. FIMPARA
06. var sorteio:INT = ALEATORIO(0,somaPeso);
07. var posicaoEscolhida = -1;
08. FAÇA:
09.    posicaoEscolhida++;
10.    somaPeso -= pesos[posicaoEscolhida];
11. ENQUANTO(somaPeso>0);

E aqui mapeamos a posição escolhida, vamos decrescendo do somaPeso os pesos de cada posição. No momento em que o somaPeso for zerado ou for negativo, significa que encontramos a nossa posição que queremos.

Então pessoal, por hoje é só.