O método da Roleta Viciada

Como sortear aleatoriamente um número? Essa é simples. Muitas linguagens têm um método tipo Random que gera um número entre 0 e 1. Isso vai gerar um número qualquer nessa faixa, todos com a mesma probabilidade.

Mas como fazer, quando alguns números têm probabilidade diferente?

Exemplo. Vou sortear uma rifa, e o peso de cada participante é proporcional à contribuição dele.

Nesse caso, o método é chamado de “Roleta viciada”.

Primeiro, calculamos a probabilidade Acumulada da série.

A seguir, usamos o mesmo método random comum, para gerar um número entre 0 e 1. Depois, vemos em que faixa esse número sorteado está, na probabilidade acumulada.

No caso, se for de 0 a 38% é o Manoel, de 38% a 53% Pedro, e acima de 53% Larissa.

Interpretação: É como plotar a probabilidade acumulada, escolher um número aleatório no eixo Y, e verificar a ordenada correspondente no eixo X.

É o mesmo truque utilizado para gerar distribuições como Normal, Triangular, Weibull, a partir da distribuição uniforme.

Vide arquivo no link.

RoletaViciada.xlsx

Veja também:

https://ideiasesquecidas.com

Padrões em círculos

É possível criar padrões extremamente intrincados, a partir de construções simples.

No VBA, é possível desenhar um círculo com o seguinte comando.

    ActiveSheet.Shapes.AddShape(msoShapeOval, 25, 25, 15, 15)

(parâmetros: posição x e y, tamanho na direção x e tamanho na direção y)

Para trocar cores da borda, preenchimento do círculo, etc, normalmente uso o “gravar macro” e reaproveito o código.

Utilizando apenas círculos com raios pequenos, é possível criar uma malha formada de pontos.

(Versão em Excel (https://1drv.ms/x/s!Aumr1P3FaK7joCmnhqOUkgQfqrwW), e versão JS D3 em: https://asgunzi.github.io/Padr-es-em-C-rculos/PadroesCirculos.html)

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos01.png?w=1024

Se o raio de cada ponto for aumentado, e com o raio vermelho levemente maior que o azul.

Começa a ficar interessante quando os raios aumentam a ponto de se tangenciar.

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos03.png?w=1024

Aumentando mais ainda.

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos04.png?w=1024

E assim sucessivamente:

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos05.png?w=1024

Padrões diversos formados aumentando mais ainda os raios:

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos06.png?w=1024

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos07.png?w=1024

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos08.png?w=1024

São desenhos de alta complexidade, feitos a partir de um padrão simples de círculos.

https://ideiasesquecidas.files.wordpress.com/2022/05/circulos09.png?w=1024

Vide planilha, para criar estes e outros padrões.

É necessário ativar macros para funcionar.

Veja também:

https://ideiasesquecidas.com/

Como gerar um UUID no Excel?

Num banco de dados, é importante ter um registro único como chave, para evitar que dois registros conflitem.

Como eu posso fazer para ter esse identificador (ID) único para cada registro?

Uma forma é ter um controle de IDs: verificar qual o último número já gravado e gerar um novo número. Talvez sequencial, como no exemplo abaixo.

Porém, para casos onde for difícil ou custoso fazer essa verificação, ou a comunicação central online for complicada, é possível utilizar uma técnica de números aleatórios.

É aí que entra o conceito de UUID, identificador universal exclusivo. É um número de 128 bits representado por 32 dígitos hexadecimais, cada um gerado aleatoriamente.

Algo como:

c3d5d666-4050-4bad-8258-6a0c4f8eb701

Há uma série de protocolos para gerar esse número. Apesar de aleatório, é aleatório dentro desses protocolos.

O site a seguir fornece o serviço que gera um UUID, de forma gratuita.

https://www.uuidgenerator.net/

A tabela ficaria assim, para efeito de comparação:

Há chance de duplicação? Sim, há uma probabilidade maior que zero, porém muito pequena: 1 em 2,7 quintilhões. É mais fácil ganhar na mega sena duas vezes seguidas do que dar um conflito de UUIDs.

Em anexo, uma rotina em Excel – VBA que consulta o site citado acima, gera um UUID aleatório e puxa para uma célula. Foi desenvolvida pelo amigo Bruno Cambria, como um componente de um projeto que tocamos.

Um uso possível pode ser gerar N bancos separados, assíncronos, e juntar depois, com chance quase nula de duplicação. Ciência da computação pura.

Link para saber mais.

https://en.wikipedia.org/wiki/Universally_unique_identifier

Bônus: Review do livro Hacking Digital, com boas dicas e cuidados a serem tomados na transformação digital da companhia.

Acesse em https://www.linkedin.com/posts/arnaldogunzi_hacking-digital-best-practices-to-implement-activity-6924321829675241472-73gh

https://ideiasesquecidas.com/

O poder de um único neurônio

Redes neurais do mundo moderno podem utilizar centenas de milhares, milhões de neurônios artificiais. Porém, o que dá para fazer com um único neurônio? Resposta: um classificador simples. Segue um exemplo.

Este é o mesmo exercício visto anteriormente, de criar uma reta para classificar o Resultado em função da Performance e Dificuldade:

(Vide https://medium.com/ideias-anal%C3%ADticas-avan%C3%A7adas/classificador-e-svm-97b5b39c3e06)

Performance = [6.8, 7.9, 9.6, 9.6, 9.4, 7.9, 8.8, 7.9, 5.8, 7.8, 5.9, 6.7, 9.3, 7.9, 6.5, 7.8, 8.0, 6.3, 9.4, 7.4, 9.2, 9.5, 6.8, 5.5, 5.7, 6.2, 5.6, 6.6, 5.5, 5.5]

Dificuldade = [8.0, 6.5, 8.4, 5.4, 7.2, 8.5, 8.5, 9.3, 9.3, 8.3, 9.6, 9.1, 8.9, 7.0, 9.1, 8.1, 9.2, 9.1, 6.5, 9.8, 8.9, 5.4, 5.9, 5.6, 5.5, 6.6, 5.4, 7.0, 5.9, 5.4]

Resultado = [‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’]

No exercício anterior (vide aqui), o classificador era simplesmente a reta x + y = 14.

Um neurônio artificial é comumente representado da forma abaixo. É exatamente igual a um classificador. Recebe valores de entrada, multiplica por pesos e soma uma constante.

É inspirado no neurônio do cérebro humano, onde os dendômetros recebem algum sinal de outros neurônios, e o axônio dispara uma composição dos sinais de entrada para os próximos elos do sistema.

Vamos usar um único neurônio em uma única camada, para criar um classificador. Ferramenta: Keras, um pacote de AI que funciona sobre o TensorFlow, um pacote de computação eficiente do Google.

from keras.models import Sequential
from keras.layers import Dense
from tensorflow import keras
from tensorflow.keras import layers

import tensorflow

Declarando o modelo

model = keras.Sequential()

Adicionando uma camada com: um neurônio, dimensão do vetor de entrada = 2

model.add(Dense(1, input_dim=2, kernel_initializer=’uniform’, activation = ‘sigmoid’))

A seguir, criar uma função de otimização, a métrica a otimizar e manda rodar

opt = keras.optimizers.Adam(learning_rate=0.5)
model.compile(loss=’binary_crossentropy’, optimizer=opt, metrics=[‘accuracy’])
model.fit(X,y, epochs =100, batch_size = 10)

Resultado, convergiu com uma acurácia de 96,6%, é um bom modelo.

Epoch 100/100
3/3 [==============================] – 0s 3ms/step – loss: 0.1256 – accuracy: 0.9667

Via o comando “predict”, vamos predizer o resultado para combinações de entradas:
x_test = [(5,5), (3,8),(8,8), (7,5), (7,8), (6.8, 8)]

print(model.predict(x_test))

[[0.00640216]
[0.01692742]
[0.84710884]
[0.06093016]
[0.6358352 ]
[0.5808778 ]]

Nota: o forecast é uma função contínua entre 0 e 1. Para traduzir se passou ou não, vamos usar outra regra. Se o valor for maior que 0,5, podemos dizer ‘Ok’ , senão, ‘Não OK’.

Vamos dar uma olhada nos pesos do modelinho.

weights, biases = model.layers[0].get_weights()
print(weights)
[[1.1547703]
[1.0974979]]

print(biases)
[-16.306044]

Ou seja, esse modelo pega a primeira entrada, multiplica por 1.15, pega a segunda e multiplica por 1.09 e soma -16.3.

Isso dá muito próximo à reta x + y – 14 = 0, que já tínhamos encontrado.

Modelos mais complexos podem ter dezenas de camadas, centenas de neurônios por camada, função de ativação não-linear, camadas especiais (como convolução) e outros truques que possibilitam ferramentas de detecção de imagens, algoritmos de tradução e reconhecimento de padrões utilizados no mundo atual.

Exemplo: Arquitetura do Alexnet, uma das primeiras redes profundas. Cada retângulo é uma camada de neurônios.

Para quem quiser rodar, segue link do Colab:
https://colab.research.google.com/drive/1gURlAAKEWZ2rRbdTrWtnhThIE7tBDM1X?usp=sharing

Coloquei também no Github: https://github.com/asgunzi/keras-unico-neuronio

Veja também: https://medium.com/ideias-anal%C3%ADticas-avan%C3%A7adas

Classificador e SVM

Sobre o problema da reta para classificador.

Dados os pontos:

Performance =  [6.8, 7.9, 9.6, 9.6, 9.4, 7.9, 8.8, 7.9, 5.8, 7.8, 5.9, 6.7, 9.3, 7.9, 6.5, 7.8, 8.0, 6.3, 9.4, 7.4, 9.2, 9.5, 6.8, 5.5, 5.7, 6.2, 5.6, 6.6, 5.5, 5.5]

Dificuldade =  [8.0, 6.5, 8.4, 5.4, 7.2, 8.5, 8.5, 9.3, 9.3, 8.3, 9.6, 9.1, 8.9, 7.0, 9.1, 8.1, 9.2, 9.1, 6.5, 9.8, 8.9, 5.4, 5.9, 5.6, 5.5, 6.6, 5.4, 7.0, 5.9, 5.4]

Resultado =  [‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’, ‘Não Ok’]

A forma mais simples é fazer no braço. Traçar uma linha no gráfico, ver onde intercepta nos eixos, e resolver o sisteminha de equações:

9 = a*5+b

5 = a*9 +b

Isso dá a reta x + y = 14.

Há várias retas possíveis que satisfazem a separação, e todas elas estão corretas.

Porém, dentre as inúmeras retas, qual a mais robusta?

Dentre as técnica possíveis para resolver a questão, tem uma chamada SVM (Support vector machine).

Intuitivamente, esta técnica maximiza a margem entre as duas classes, sendo assim melhor das retas possíveis nesse sentido. A margem é a distância entre paralelas do separador (vide Máquina de vetores de suporte – Wikipédia, a enciclopédia livre (wikipedia.org))

No Python, o SVM já vem pronto:

from sklearn import svm

clf = svm.SVC(kernel = ‘linear’) #Classificador linear

#Faz fit entre dados e resultado

clf.fit(X, Y)

#Predizer uma combinação

print(clf.predict([[7.5, 7]])) #Resposta = 1, classificado

Vide o código deste exercício em:

https://colab.research.google.com/drive/1yZUYTwDq0o7OtN94Hwg4t3_NNi4fNaon?usp=sharing

Para classificador, é possível também usar árvores de decisão, redes neurais – fica para o próximo exercício.

Ideias Analíticas Avançadas

Um mundo mais eficaz através do Analytics

https://ideiasesquecidas.com/

O problema da mochila

  1. (Fácil)

Digamos que eu vá fazer uma viagem para a Europa. Tenho 6 itens, cada um com um peso e um valor.

Consigo carregar no máximo 60 kg na minha mochila. Quais os itens a levar, de forma a maximizar o valor na mochila, dentro da restrição?

  1. (Difícil) Agora, tenho mais de 30 itens, e consigo carregar 800 Kg. Desenvolver um algoritmo para resolver o problema (o solver do Excel é suficiente).

Solução

Este problema pode ser resolvido utilizando o solver.

Imagine uma variável de decisão binária (0 = não levo o item, 1 = levo o item).

ProblemaMochila_Solucao.xlsx

Queremos maximizar o valor a ser carregado.

A função objetivo será o somarproduto entre a variável binária e o valor de cada item.

A restrição será o somarproduto entre a variável binária e o peso de cada item, que deve ser menor ou igual ao peso máximo.

No solver, definir a função objetivo como a célula que calcula o valor transportado.

O range das variáveis de decisão deve estar em “Alterando células variáveis”.

São duas restrições.

– a variável de decisão deve ser binária

– o peso total (calculado na célula G7) deve ser menor do que a restrição de peso máximo.

O método de solução é LP Simplex, ou seja, um problema de otimização linear simples.

Se o solver não estiver habilitado, ir em Arquivos -> Opções -> Suplementos

Ir… em Suplementos do Excel, e habilitar o Solver.

O Desafio 1 é mais simples, dá para resolver no braço.

O Desafio 2 tem a mesma estrutura, e dá para resolver de forma similar. Vide arquivo ProblemaMochila_Solucao.xlsx.

Qual a aplicação deste tipo de problema no cotidiano?

Na indústria de papel e celulose, o problema do Trim deve ser resolvido todos os dias. Como eu corto o rolo jumbo de papel, nos diversos pedidos dos clientes, de forma a ter o maior aproveitamento possível do mesmo?

O problema da mochila pode ser utilizado de forma auxiliar, a gerar novos cortes, numa técnica chamada de “Geração de colunas”.

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Metaheurística com 2 variáveis

Essa versão é um pouquinho mais elaborada que a versão com uma variável (https://ferramentasexcelvba.wordpress.com/2021/03/27/exemplo-de-metaheuristica-uma-variavel/)

Serve para resolver o problema linear:

Max 10*x +5*y

Sujeito a:

2*x+4*y <= 50

1*x -6*y <= 15

É semelhante ao anterior, mas agora as variáveis são matrizes.

‘Inicializando coeficientes FO

coefFO(1) = 10

coefFO(2) = 5

‘Inicializando coeficientes Matriz

coefMatriz(1, 1) = 2

coefMatriz(1, 2) = 4

coefMatriz(2, 1) = 1

coefMatriz(2, 2) = -6

‘Inicializando rhs

RHS(1) = 50

RHS(2) = 15

Um parâmetro adicional, restringindo as variáveis a assumir valor máximo 50 e mínimo 0.

For i = 1 To nvar

    varmin(i) = 0 ‘Range Mínimo

    varmax(i) = 50 ‘Range Máximo

Next i

Em linhas gerais:

– Escolhe valores aleatórios no range das variáveis

– Pondera o valor aleatório com a melhor solução até agora

– Lambda controla o mix valor aleatório x melhor solução até agora. No início lambda é pequeno, depois vai aumentando

– Verifica se cumpre todas as restrições

 – função objetivo que avalia a solução

– salva o histórico

‘Algoritmo evolutivo

For iter = 1 To Niteracoes ‘Numero de iteracoes

    lambda = iter / Niteracoes

    ‘Sorteia um valor

    sorteia var, varmin, varmax, varbest, lambda

    ‘Verifica restricoes

    isOk = verificaRestricoes(var, coefMatriz, RHS)

    If isOk Then

        ‘Avalia a função atual

        FOatual = FO(var, coefFO)

        ‘Salva a melhor (maximizando)

        If FOatual > FOBest Then

            FOBest = FOatual

            copiaUni var, varbest

        End If

    End If

    FOhist(iter, 1) = FOBest

Next iter

Usando o solver, as variáveis ótimas são 22,5 e 1,25.


A metaheurística chega a valores próximos ao ótimo, o que mostra que funciona para uma solução suficientemente boa.

Provavelmente, com muitas variáveis e muitas restrições, vai ficar bem mais difícil convergir para uma solução boa.

Uma coisa ruim é todas as equações serem hard coded, mas quem domina código consegue fazer isso fácil.

É possível “tunar” esse algoritmo básico com pré processamento, ou algum chute guiado ao invés de ser basicamente aleatório, mas aí vai depender do problema.

Planilha para download no Github: https://github.com/asgunzi/Metaheuristica-2-var

Exemplo de metaheurística – uma variável

A ideia aqui é escrever uma série de metaheurísticas de dificuldade crescente.

Começando do caso mais simples possível. Variável unidimensional “x”.

Defino um range de valores, no caso, x entre 0 e 100.

varmin = 0 ‘Range Mínimo

varmax = 100 ‘Range Máximo

Seja a função objetivo –x^3 + 20*x^2 + 100, mostrado no gráfico abaixo.

Private Function FO(ByVal var) As Double

    ‘Implementa a função objetivo

    FO = -var ^ 3 + 20 * var ^ 2 + 100

End Function

Este algoritmo vai:

 – escolher um valor aleatório entre 0 e 100

– ponderar o valor aleatório com a melhor solução até agora

– lambda controla o mix valor aleatório x melhor solução até agora. No início lambda é pequeno, depois vai aumentando

– função objetivo que avalia a solução

– salva o histórico

Trecho do código:

For iter = 1 To Niteracoes ‘Numero de iteracoes

    lambda = iter / Niteracoes

    ‘Sorteia um valor

    sorteia var, varmin, varmax, varbest, lambda

    ‘Avalia a função atual

    FOatual = FO(var)

    ‘Salva a melhor (maximizando)

    If FOatual > FOBest Then

        FOBest = FOatual

        varbest = var

    End If

    FOhist(iter, 1) = FOBest

Next iter

Resultado. Em apenas 100 iterações, já chegou num valor excelente: x = 13,3

Você pode mudar a FO, ranges, etc.

Próximo passo é fazer um exemplo multidimensional, etc.

Planilha para download no Github: https://github.com/asgunzi/Metaheuristica-uma-variavel

O código da transposição

Dentre os métodos existentes em criptografia, há alguns bens simples (e fáceis de quebrar).

O código da transposição funciona assim.

Imagine uma mensagem a ser enviada: “Conta a lenda que dormia”.

Temos que ter um tamanho para quebrar a mensagem em pedaços menores.

Digamos que o tamanho seja 5.

Escrevemos a mensagem numa tabela, quebrando pelo tamanho dado.

Para codificar a mensagem, começamos a ler pelas colunas

A primeira coluna é codificada como “C nur”. A segunda é “oadem”.

A mensagem completa vira:

“C nuroademn a itl daaeqo”

Exercício: o que está escrito a seguir, sabendo que foi utilizado o código da transposição (com outro tamanho)?

“Tapem uule aéedena  no a npa a aãev sloq”

Exercício extra. Criar uma função que codifique e decodifique o código, com uma string e um tamanho de entrada.


Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Veja também:

Desafio: O ponto de parada ótimo

Imagine a seguinte situação. Quero alugar um apartamento num bairro muito concorrido de São Paulo. Vou visitar 20 imóveis, e assim que o fizer, ou eu faço a proposta para alugar na hora, ou decido ver o imóvel seguinte e perco o visitado para sempre (afinal, é um bairro concorrido).

O ordem de visitas é aleatória.

Qual estratégia maximiza a escolha?

É um claro tradeoff. Para conseguir informação, devo prospectar, porém, por ser uma prospecção destrutiva, vou descartar bons imóveis e acabar ficando sem opções.

Este problema é conhecido como o “Ponto de parada ótimo”, e a resposta ótima é 37%.

Primeiro, tenho que coletar informações, e a única forma de fazer é visitando os imóveis. Visito 37% dos imóveis, e avalio qual o melhor destes.

A seguir, pego o primeiro imóvel igual ou superior ao score avaliado anteriormente.

Exemplo:

Tenho uma lista de 20 imóveis, com notas aleatórias (quanto maior a nota, melhor).

37% de 20 dá 7, arredondando. Visito os 7 primeiros imóveis, sem escolher nenhum deles, mas anotando qual o melhor.

No caso, o melhor imóvel visitado teve nota 65.

A seguir, continuo fazendo as visitas até encontrar algum igual ou superior a 65. No caso, faço a proposta na hora e fico com o imóvel de nota 77.

Na lista, há dois imóveis com score maior (de 91 e 97), de forma que a estratégia citada escolheu o terceiro melhor da lista (lembrando que, no problema, não teríamos essa informação da nota sem visitar – e descartar – o imóvel)

Desafio em Excel.

Dada uma lista com números aleatórios (PontoParada.xlsx), escrever fórmulas (ou rotinas ou qualquer outro truque) para implementar o algoritmo de parada ótima descrito. Comparar com a melhor solução.

(Clicar em F9 ou mudar qualquer célula vai alterar os valores).

Favor enviar as respostas para mim em private. Na quarta-feira que vem envio a compilação das respostas.