Monte Carlo na Prática: Encontrando o valor de iterações ideal

Um dos maiores motivos pelo qual qualquer metodologia de gerenciamento de projetos existe, é trazer redução de custos.

O atraso de uma semana em um projeto, gera dois custos diferentes:

  • O primeiro custo é o custo das pessoas presentes no time do projeto, por terem que trabalhar por mais uma semana.
  • Já o segundo, trata-se do custo de atraso (normalmente chamado de cost of delay) que por sua vez é a receita que deixa-se de receber pelo atraso, por exemplo: supondo que um novo produto tenha uma receita diária de 100 reais, o custo de atraso seria de 700 reais (100 reais x 7 dias), aqui no blog temos um post muito interessante sobre o assunto.

Como esses custos podem ser altos, é preciso utilizar ferramentas que possam dar visibilidade para as datas de entrega. Uma das formas encontradas para dar visibilidade a estes potenciais problemas, foi através da adoção do Diagrama de Gantt, para gerenciamento de projetos, nele é possível identificar os pontos mais delicados do projeto (os caminhos críticos) em que deve-se dar maior esforço para que não atrasem, visto que ao atrasar nesses pontos o projeto inteiro também irá atrasar.

Embora essa ferramenta seja ótima para alguns tipos de projetos (normalmente onde existe um grau de incerteza baixo), ela não é a ideal para projetos com previsibilidade baixa devido a variância de entregas, como ocorre em projetos que lidam com o campo do conhecimento (redigir um livro ou desenvolver software, como exemplos).

Aqui na Plataformatec temos sempre feito o máximo para que todas as nossas previsões de entregas sejam embasadas em dados e sigam métodos científicos comprovados. Os dois métodos que mais utilizamos são:

  • Progressão linear
  • Simulação de Monte Carlo

PROGRESSÃO LINEAR

Na progressão linear, fazemos uma análise dos dados de itens de trabalho entregues durante algum período (normalmente trabalhamos com periodicidade semanal) e através de uma análise destes valores elegemos quais são os melhores valores a serem alocados na progressão. Por exemplo: supondo que tenhamos os valores de histórico de itens de trabalho entregues por semana (throughput), conforme o gráfico abaixo:

Um valor que faz sentido para a progressão pessimista será de que a cada semana iremos entregar 1 item de trabalho por semana, visto que tivemos 5 casos em que a entrega foi de 1 ou 0, para a estimativa otimista podemos utilizar o valor 3 ou 4 ou até mesmo 3,5 visto que tivemos 4 casos em que o valor foi 3 ou mais, por fim para a progressão provável o melhor valor seria o de 2 visto que é o valor da mediana do dataset e é o valor que mais aparece (a moda).

O maior problema da progressão linear é de que estamos informando os valores a serem utilizados para cada cenário, algo que pode ser perigoso caso a pessoa que está fazendo a progressão não tenha um bom domínio de análise de dados. Além disso, a progressão linear também ignora a variância. Desta forma, em sistemas com uma variância de entrega muito elevada, a progressão linear pode não fazer tanto sentido.

MONTE CARLO

Outra técnica que utilizamos chama-se Monte Carlo, para entender melhor como o método funciona, bem como ter uma inferência do que ele faz, recomendo esse blogpost que é bem completo.

Tenho utilizado o método desde que entrei na Plataformatec com grande sucesso, porém uma coisa sempre ficava na minha mente era: “Quantas iterações são necessárias para que eu possa ter um bom grau de confiabilidade no método?”. Para responder essa pergunta eu fiz muitas pesquisas em livros estatísticos e pela internet e não consegui encontrar nenhum tipo de informação que me auxiliasse.

Dessa forma resolvi fazer um estudo desse assunto. O objetivo do Monte Carlo é de inferir a probabilidade de algum evento, “forçando” que o evento ocorra tantas vezes que o resultado me dê a probabilidade da ocorrência do evento. Por exemplo, ao lançar uma moeda mil vezes se eu contar quantas vezes a moeda cai em “cara” e dividir esse valor pelas mil vezes que a moeda foi lançada, obterei uma inferência da probabilidade da moeda cair em “cara”.

Para conseguir saber a qualidade do método eu realizei testes nos quais eu já sabia o resultado esperado, e fui fazendo com que o problema fosse cada vez mais complexo, de forma a ver se existe alguma relação entre a dificuldade do problema e a quantidade de iterações necessárias para que o valor inferido pelo método seja o mais próximo possível do valor calculado.

O objetivo é verificar quantas iterações são necessárias para que o erro entre o valor inferido pelo método e o valor calculado seja mínimo (para previsões de probabilidade de entrega um erro a partir da segunda ou terceira casa decimal é bem aceitável). Gostaria de ressaltar que esse blogpost não é um estudo científico acerca do assunto, e seu objetivo é entender através de inferência qual é um valor de iterações bom para ser utilizado em predições para projetos.

OS TESTES

Os testes foram todos realizado utilizando a linguagem de programação R, que pode ser baixado neste link. Caso prefira utilizar um IDE, recomendo o RStudio.

Em todos os testes eu rodei o sistema por 100 vezes utilizando as seguintes quantidades de iterações: 100 (cem), 1000 (mil), 10000 (dez mil), 100000 (cem mil), 1000000 (um milhão), 10000000 (dez milhões), 100000000 (cem milhões) e 200000000 (duzentos milhões). Os resultados são os consolidados dessas 100 “rodadas”, em cada iteração.

A MOEDA

O primeiro teste que fiz foi em cima de um lançamento de moeda. Uma moeda tem 50% de chance de cair em qualquer um de seus lados e este é o valor que queremos que seja inferido pelo Monte Carlo. Para isso utilizei o seguinte código em R:

LancaMoeda <- function(iteracoes)
{
# Cria o vetor com os valores possíveis para a moeda 1 = Cara e 0 = Coroa
moeda = c(0,1)
resultado = 0

# Soma todos os resultados em que a moeda foi "Cara"
resultado = sum(sample(moeda, iteracoes, replace=T))

# Divide o valor pela quantidade de iterações e transforma em percentual
resultado = (resultado/iteracoes) * 100

return(resultado)
}

# Inicializa variáveis
vetor_resultado = 0
vetor_tempo = 0
controle = 0

# Informa a quantidade de iterações a serão executadas
rodadas = 100

# Aloca os resultados percentuais em um vetor de 100 itens e aloca os tempos de execução em outro
while (controle != 100)
{
tempo_inicial = Sys.time()
vetor_resultado = append(vetor_resultado, LancaMoeda(rodadas))
tempo_final = Sys.time()

tempo = tempo_final - tempo_inicial
vetor_tempo = append(vetor_tempo, tempo)

controle = controle + 1
}

# Mostra os percentuais
vetor_resultado

# Mostra os tempos de execução
vetor_tempo

Alterando os valores da variável iterações e compilando os resultados obtive a seguinte tabela:

IteraçõesResultado MinResultado MaxResultado EsperadoResultado MédioResultado Médio - Resultado Esperado Mediana do Resultado Mediana Resultado - Resultado EsperadoDesvio-Padrão do Resultado
10033.0000067.0000050.00000 50.02000 0.02000 50.00000 0.00000 5.09368
100043.6000056.20000 50.00000 49.99440 0.00560 50.00000 0.00000 1.59105
1000048.3500051.78000 50.00000 50.01263 0.01263 50.02000 0.02000 0.51001
10000049.5800051.78000 50.00000 49.99110 0.00890 49.99350 0.00650 0.15805
1000000 49.8517050.15090 50.00000 49.99883 0.00117 49.99785 0.00215 0.04811
1000000049.95433 50.05807 50.00000 50.00013 0.00013 50.00010 0.00010 0.01564
10000000049.98435 50.01637 50.00000 50.00004 0.00004 49.99989 0.00011 0.00516
20000000049.9889050.01195 50.00000 49.99981 0.00019 49.99987 0.00013 0.00345

No caso de um problema simples, como o lançamento de uma moeda, podemos ver que a quantidade ideal de iterações seria algo entre 10 e 100 milhões de vezes. Visto que é nessa faixa em que o desvio padrão dos resultados começa a ser na ordem da terceira casa decimal, outro ponto interessante é que se você deseja mostrar apenas a primeira casa decimal um valor de 1 milhão de iterações já atenderia.

O DADO

Com o teste da moeda podemos ter uma idéia de quantas iterações são necessárias, para cada grau de confiabilidade desejado. Porém uma pergunta que fica é se esse comportamento é o mesmo para sistemas mais complexos. Por este motivo fiz um teste parecido, porém agora rodando um dado de 6 lados, que tem 16,67% de chances de cair em qualquer face.

RolaDado <- function(iteracoes)
{
# Cria o vetor com os valores possíveis para o dado
dado = 1:6
resultado = 0

# Aloca os resultados das rolagens do dado
resultado = sample(dado,iteracoes,replace=T)

# Soma todos os valores que tiverem sigo iguais a 6
resultado = sum(resultado == 6)

# Divide o valor pela quantidade de iterações e transforma em percentual
resultado = (resultado/iteracoes) * 100

return(resultado)
}

# Inicializa variáveis
vetor_resultado = 0
vetor_tempo = 0
controle = 0

# Informa a quantidade de iterações a serão executadas
rodadas = 100

# Aloca os resultados percentuais em um vetor de 100 itens e aloca os tempos de execução em outro
while(controle != 100)
{
tempo_inicial = Sys.time()
vetor_resultado = append(vetor_resultado, RolaDado(rodadas))
tempo_final = Sys.time()

tempo = tempo_final - tempo_inicial
vetor_tempo = append(vetor_tempo, tempo)

controle = controle + 1
}

# Mostra os percentuais
vetor_resultado

# Mostra os tempos de execução
vetor_tempo

Alterando os valores da variável iterações e compilando os resultados obtive a seguinte tabela:

IteraçõesResultado MinResultado MaxResultado EsperadoResultado MédioResultado Médio - Resultado Esperado Mediana do Resultado Mediana Resultado - Resultado EsperadoDesvio-Padrão do Resultado
1006.0000028.0000016.6666716.58100-0.0856716.00000-0.666673.64372
100013.2000020.4000016.6666716.685000.0183316.60000-0.066671.16949
1000015.6000017.9400016.6666716.65962-0.0070516.670000.003330.38072
10000016.2220017.0620016.6666716.66109-0.0055716.66500-0.001670.11356
1000000 16.5496016.5496016.6666716.66616-0.0005016.667900.001230.03650
1000000016.6329416.7026616.6666716.66607-0.0006016.66577-0.000900.01220
10000000016.6559216.6794816.6666716.666700.0000416.666790.000120.00372
20000000016.6578716.6747616.6666716.666710.0000416.666710.000040.00267

Podemos ver que neste caso também temos que a quantidade ideal de iterações seria algo entre 10 e 100 milhões de vezes, para termos um erro a partir da segunda ou terceira casa decimal. Esse resultado mostra que, ou a complexidade do problema não tem influência na quantidade de iterações ou de que o problema da moeda e do dado têm complexidades parecidas. Analisando os tempos de execuções da moeda e do dado verifica-se que eles demoram tempos parecidos de execução, o que corrobora a hipótese de que os problemas tem complexidades próximas.

DOIS DADOS

Para saber se a complexidade era muito próxima e por isso que os valores de iterações ideais ficaram iguais, decidi dobrar a complexidade do problema ao rodar dois dados em vez de um (entendo que nem sempre ao dobrar a quantidade de funções teremos mais complexidade por conta da ordem de complexidade ou Big-O Notation, porém fiz o teste para ter certeza se isso se aplicava). A maior probabilidade de resultado encontrada ao rolar dois dados é o valor 7, tendo 16,67% de chances de ocorrer.

RolaDoisDados <- function(iteracoes)
{
# Cria o vetor com os valores possíveis para o dado
dado = 1:6
resultado = 0

# Aloca os resultados das rolagens dos dados
primeira_rolagem = sample(dado,iteracoes,replace=T)
segunda_rolagem = sample(dado,iteracoes,replace=T)

# Soma os vetores, item a item
resultado = primeira_rolagem + segunda_rolagem

# Soma todos os valores que tiverem sigo iguais a 7
resultado = sum(resultado == 7)

# Divide o valor pela quantidade de iterações e transforma em percentual
resultado = (resultado/iteracoes) * 100

return(resultado)
}

# Inicializa variáveis
vetor_resultado = 0
vetor_tempo = 0
controle = 0

# Informa a quantidade de iterações a serão executadas
rodadas = 100

# Aloca os resultados percentuais em um vetor de 100 itens e aloca os tempos de execução em outro
while(controle != 100)
{
tempo_inicial = Sys.time()
vetor_resultado = append(vetor_resultado, RolaDoisDados(rodadas))
tempo_final = Sys.time()

tempo = tempo_final - tempo_inicial
vetor_tempo = append(vetor_tempo, tempo)

controle = controle + 1
}

# Mostra os percentuais
vetor_resultado

# Mostra os tempos de execução
vetor_tempo

Novamente alterando os valores da variável iterações e compilando os resultados:

IteraçõesResultado MinResultado MaxResultado EsperadoResultado MédioResultado Médio - Resultado Esperado Mediana do Resultado Mediana Resultado - Resultado EsperadoDesvio-Padrão do Resultado
1005.0000031.0000016.6666716.37100-0.2956716.00000-0.666673.77487
100013.4000021.8000016.6666716.64710-0.0195716.60000-0.066671.18550
1000015.3300017.7700016.6666716.683070.0164016.685000.018330.38059
10000016.2310017.0660016.6666716.66546-0.0012016.668000.001330.11597
1000000 16.5445016.8117016.6666716.66657-0.0001016.668600.001930.03798
1000000016.6288816.7028216.6666716.66683 0.0001616.667050.000380.01155
10000000016.6540816.6789916.6666716.666690.0000216.666730.000070.00382
20000000016.6588116.6745516.6666716.666750.0000916.666820.000150.00258

Novamente verificamos que uma quantidade de iterações entre 10 e 100 milhões traz uma variação baixa o suficiente para ser confiável. E nesse caso pude identificar que o problema era sim mais complexo, visto que o tempo de execução para 200 milhões de vezes levou em média 7,47 segundos a mais que o problema de um único dado.

CINCO DADOS

A inferência que tive até este momento é de que a complexidade do problema influi muito pouco na quantidade de iterações a serem realizadas, mas para ter certeza eu fiz o teste com 5 dados. A maior probabilidade de resultado encontrada ao rolar cinco dados são os valores 17 e 18, tendo 10,03% de chances de ocorrer.

RolaCincoDados <- function(iteracoes)
{
# Cria o vetor com os valores possíveis para o dado
dado = 1:6
resultado = 0

# Aloca os resultados das rolagens dos dados
primeira_rolagem = sample(dado,iteracoes,replace=T)
segunda_rolagem = sample(dado,iteracoes,replace=T)
terceira_rolagem = sample(dado,iteracoes,replace=T)
quarta_rolagem = sample(dado,iteracoes,replace=T)
quinta_rolagem = sample(dado,iteracoes,replace=T)

# Soma os vetores, item a item
resultado = primeira_rolagem + segunda_rolagem + terceira_rolagem + quarta_rolagem + quinta_rolagem

# Soma todos os valores que tiverem sigo iguais a 18
resultado = sum(resultado == 18)

# Divide o valor pela quantidade de iterações e transforma em percentual
resultado = (resultado/iteracoes) * 100

return(resultado)
}

# Inicializa variáveis
vetor_resultado = 0
vetor_tempo = 0
controle = 0

# Informa a quantidade de iterações a serão executadas
rodadas = 10

# Aloca os resultados percentuais em um vetor de 100 itens e aloca os tempos de execução em outro
while(controle != 100)
{
tempo_inicial = Sys.time()
vetor_resultado = append(vetor_resultado, RolaCincoDados(rodadas))
tempo_final = Sys.time()

tempo = tempo_final - tempo_inicial
vetor_tempo = append(vetor_tempo, tempo)

controle = controle + 1
}

# Mostra os percentuais
vetor_resultado

# Mostra os tempos de execução
vetor_tempo

Compilando os resultados:

IteraçõesResultado MinResultado MaxResultado EsperadoResultado MédioResultado Médio - Resultado Esperado Mediana do Resultado Mediana Resultado - Resultado EsperadoDesvio-Padrão do Resultado
1002.0000020.0000010.0308610.043000.0121410.00000-0.03086 3.01268
10006.8000013.4000010.0308610.041600.0107410.00000-0.03086 0.96373
100009.0700011.0300010.0308610.046000.01514 10.045000.014140.30501
1000009.7470010.3150010.0308610.02726-0.00360 10.031000.000140.09366
1000000 9.9503010.1124010.0308610.02994-0.00092 10.03045-0.00041 0.02945
1000000010.0006010.0676810.0308610.03072-0.00014 10.03065 -0.00022 0.00956
10000000010.0215110.0411610.0308610.030910.0000410.031020.000160.00310

E mais uma vez podemos ver que entre 10 e 100 milhões é valor ideal. Interessante notar que esse caso realmente foi mais complexo, levando 35 segundos a mais em média quando comparada com a rolagem de um único dado.

Conclusão

Depois de realizar todos esses testes, é possível concluir que, para a utilização em gerenciamento de projetos, uma quantidade de iterações entre 10 e 100 milhões atenderia adequadamente a necessidade de prever alguma data de entrega.

O valor que tenho utilizado é de 10 milhões, quando vou passar os dados para algum stakeholder. Porém como o processo fica demorado (em média de 30 minutos para rodar com 10 milhões), quando eu preciso verificar os dados no dia-a-dia utilizo algum valor menor (algo entre 100 mil a 1 milhão).

E você? Tem utilizado o método? Se sim, quais valores de iterações têm usado para a análise? Os resultados obtidos tem tido valor para os stakeholders de seus projetos? Caso queira trocar experiências, podemos iniciar um bate-papo por e-mail, através do endereço gabriel.lopes@plataformatec.com.br

Comments are closed.