Sobre DNA, AlphaFold e um pequeno exercício

Se um computador tem a codificação em zeros e uns, um ser humano é codificado com 4 moléculas: Adenina, Guanina, Citosina e Timina. É o livro de códigos conhecido como DNA.

Assim como um código de computador, tem instruções específicas para começar, parar e identificar o que deve ser feito.

Esse código DNA vira uma proteína no final das contas, que vira algo útil para o ser humano, como um anticorpo.

Hoje em dia, sequenciar DNA é um problema fácil. Porém, prever a estrutura final da proteína é um problema muito difícil — é uma estrutura em 3D, onde cada moleculazinha interfere em todas as outras.

Por ser um problema muito difícil e importante, é um prato cheio para as empresas de IA mais avançadas do mundo.

A empresa DeepMind, da Google, desenvolveu um algoritmo chamado AlphaFold, que prevê o dobramento da proteína a partir do sequenciamento. A DeepMind desenvolve o que há de mais avançado em IA no mundo. Só para ter uma ideia, para treinar um algoritmo desses é na ordem de alguns milhões de dólares.

Agora o DeepMind anunciou que vai tornar todo esse conhecimento público.

DeepMind vai liberar estruturas de todas as proteínas conhecidasEm dezembro de 2020, a DeepMind, braço de inteligência artificial do Google, pegou o mundo da biologia de surpresa ao…www.tecmundo.com.br

“Até agora, o banco de dados consiste em 350.000 novas estruturas de proteínas. A DeepMind diz que vai prever e liberar as estruturas de mais de 100 milhões delas nos próximos meses — mais ou menos todas as proteínas conhecidas pela ciência.” — Trecho da matéria.

Aplicações potenciais: desenvolver novos remédios, conhecer melhor moléculas do corpo humano, etc.

Exercício simples com o genoma da COVID

O genoma da COVID pode ser baixado no site a seguir.
https://www.ncbi.nlm.nih.gov/sars-cov-2/

Esse compartilhamento de informações é o que possibilitou o desenvolvimento de vacinas num tempo tão curto.

São informações como a seguinte. Peguei um pequeno trecho, a base toda tem centenas de megabytes de tamanho.

Exercício: dada uma sequência genética como a seguinte,

MEQDRDIYFMQLAIEEAKKAEEMQEVPIGAVIVLDGEVISVAHNLRETEQRSIAHAELLAIDEACKKLGTWRLEDATLYVTLEPCPMCAGGIVLSRVKRVVYGASDPKGGCAGTLMNLLTDERFNHQCEVVTGVLEEECGTLLTNFFRELRKKRKAIKKLEKSNEN

Encontre o trecho a seguir. Está em qual posição?

LEDATL

Dica: No Excel, é só usar a função “Localizar”.

Agora, para pensar. Digamos que haja uma pequena mutação em uma das posições.

LADATL

O match perfeito agora não vai dar certo. Como encontrar o match mais similar possível?

Só para saber, o match similar é um problema bem mais difícil e há vários algoritmos propostos para tal.

Ideias analíticas avançadas:

https://medium.com/ideias-anal%C3%ADticas-avan%C3%A7adas

Ideias Analíticas Avançadas

Estou lançando uma publicação na plataforma Medium: a Ideias Analíticas Avançadas (https://medium.com/ideias-anal%C3%ADticas-avan%C3%A7adas).

Os objetivos são:

  • Escrever sobre Analytics Hard: Otimização, Matemática, Python, Computação Quântica, com código e tudo
  • Convidar outros autores a publicar sobre o tema.

Fica já o convite, quem quiser escrever sobre alguns dos temas e divulgar ali.

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

Metaheurística para o Caixeiro-Viajante

Implementação em VBA de metaheurística para resolução do problema do caixeiro-viajante.

A metaheurística não vai dar o valor ótimo, porém na prática, pode entregar um valor bom o suficiente.

Algumas vantagens: é mais flexível em termos de modelar restrições, é grátis (um solver tem licença que pode custar algumas dezenas de milhares de dólares, no mínimo).

Algumas desvantagens: ter alguém que manje muito de otimização combinatória para adaptar o código corretamente, não garantir a solução ótima.

De qualquer forma, é uma alternativa viável, competitiva e possível de ser utilizada, para problemas de otimização combinatória.

Segue para download no Github.

https://github.com/asgunzi/travelingSalesmanVBA

Ideias técnicas com uma pitada de filosofia
https://ideiasesquecidas.com/

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 a estratégia que 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, 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 como o do anexo, 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).

Segue a minha versão da solução, disponível para download no OneDrive.

PontoParada.xlsx

A ideia é sempre a mesma. Pegar o maior valor dos 37% primeiros, e depois o primeiro maior valor encontrado.

Da literatura, este problema tem vários nomes (como o problema da escolha da secretária).

Em geral, experimentos práticos x teoria mostram que tendemos a ser impacientes, e fechar um negócio mais cedo, sem explorar tanto – e optar por uma solução menos ótima do que poderia ser.

Fica a dica: explorar um pouco mais o mercado, antes de fechar algum negócio.

Recomendação de livro: Algoritmos para viver (https://amzn.to/2NxjGh4)

A little integer problem

A little problem to be solved using integer variables (in excel or aimms);

Suppose we have 5 forest stands, with the volumes given as below:

i Vol
1 13.576,00
2 11.635,00
3 12.514,00
4 17.755,00
5 19.947,00

The distances to our basis in A or B are given below (these are random numbers).

j
i A B
1 64 73
2 100 79
3 85 81
4 66 99
5 98 81

A and B both need at least 30.000 tons.

30000 30000

Suppose also when you harvest a stand, it’s completely to one of the destinies, A or B – it can’t be fractioned.

I want to minimize distances, subject to the constraints.

What’s the solution of this case?

The data is given below:

The decision variable is reserved in columns K and L.

The sumproduct per destiny must be greater than 30.000.

The distance is calculated multiplying vol*distance*decision variable

The objective function is the sum of distance*decision variable.

In solver, we include the constraints. And we want to minimize distances.

Because this test is very basic, there’s not much possibilities. In general, integer programming is difficult.

Other little detail: if we need necessary to harvest the plantation, the sum of the decision variable must be one. If not, it can be less or equal 1.

This is a simple example of integer optimization using solver.


Ideias técnicas com uma pitada de filosofia: https://ideiasesquecidas.com

Ferramentas Excel-VBA: https://ferramentasexcelvba.wordpress.com/

Otimizar Match

Sobre o puzzle de match de um site de relacionamento descrito abaixo, vamos fazer a formulação e resolver no excel – solver.

Fonte: PuzzleOR (http://puzzlor.com/)

A primeira coisa a fazer é transcrever os dados da tabela acima para o Excel.


Via fórmulas, nas colunas de K a Q, contamos o número de coincidências.

Esta fórmula verifica se o conteúdo das células é igual. Deve-se fazer fórmula semelhante para cada critério, e somar o número de pontos de cada match possível.

=SE(DESLOC($C$3;$K4;0) = DESLOC($C$3;$L4;0);1;0)

Transcrevo a tabela de pontos na aba “Formulação”, copiando e colando.

Agora, a formulação para resolver com o solver do Excel.

De C18 a L28, o espaço é reservado às variáveis de decisão.
Na célula C1, a função objetivo, um somarproduto da variável de decisão com os pontos.
=SOMARPRODUTO(C5:L14;C19:L28)

Quero maximizar tal função objetivo.

Quem não tiver o solver instalado, ir em Arquivo – Opções – suplementos do excel – suplementos

Acionar o solver (só é necessário fazer a primeira vez).

Em dados – solver, especificar:

  • A função objetivo como a célula C1
  • Células variáveis

Restrições:

  • variáveis binárias (ou é zero ou 1)
  • soma das linhas deve ser <= 1 (só posso fazer o match de uma mulher com um homem)
  • soma das colunas deve ser <= 1 (só posso fazer o match de um homem com uma mulher)

O método deve ser LP Simplex (ou seja, é um Linear program que utiliza o método Simplex), e resolver.

A função objetivo vai assumir o valor 33, e os matches serão os valores 1 na tabela.

Com, isso, esperamos casar as pessoas com o maior número de características possíveis.


Ideias técnicas com uma pitada de filosofia: https://ideiasesquecidas.com

Ferramentas Excel-VBA: https://ferramentasexcelvba.wordpress.com/

Quantas bobinas cabem num contêiner?


No comércio exterior, o termo “estufar” o contêiner significa colocar a carga dentro do contêiner.

Bobinas de pé, num contêiner, podem ser modeladas puramente por geometria.

O algoritmo (download aqui) pede as dimensões do contêiner, as características das bobinas, e sugere o arranjo ideal, restrito ao espaço disponível e à carga máxima permitida.

Outro exemplo:

Há softwares comerciais que fazem isto (ex. Max Load), fazendo também a composição de diferentes tipos de bobinas, e também é possível colocar bobinas deitadas, etc. Entretanto, são softwares bem mais complicados para usar. Para a aplicação simples como o caso acima, o algoritmo do anexo funciona.

Cuidado: só vale para bobinas em pé.


Ideias técnicas com uma pitada de filosofia: https://ideiasesquecidas.com

Ferramentas Excel-VBA: https://ferramentasexcelvba.wordpress.com/

Ferramentas Excel-VBA: https://ferramentasexcelvba.wordpress.com/