Otimização local vs. global

O caminho mais rápido é sempre o melhor? Este artigo pode oferecer-lhe uma perspetiva diferente se a sua resposta é sim.

Normalmente existem múltiplas formas de resolver um determinado problema ou tarefa. No campo da otimização, não é diferente, pois dispomos de várias abordagens para encontrar uma solução ótima. A escolha do melhor caminho pode depender das variáveis que consideramos, dos dados disponíveis, da complexidade do sistema, do tempo necessário para atingir a melhor solução, etc.

Neste artigo, exploramos duas abordagens bem conhecidas em otimização: Otimização Local e Otimização Global.

Para além de discutirmos as diferenças em termos de ideologia, vantagens e desvantagens, analisamos a sua aplicação num cenário de caso de uso real: alocação de agentes imobiliários a apartamentos para venda.

Otimização local vs. otimização global

As técnicas de otimização local e global procuram encontrar a melhor solução possível utilizando caminhos diferentes.

As técnicas de otimização local são normalmente mais "gulosas", pois preferem seguir o caminho mais promissor conhecido até ao momento, em vez de explorar outros espaços de busca. Este tipo de otimização é mais adequado para sistemas simples onde o número de variáveis a otimizar é reduzido e claramente identificado. Além disso, pode ser utilizado quando pretendemos obter uma solução aceitável o mais rapidamente possível.

A otimização global, por outro lado, concentra-se em encontrar o caminho para a melhor solução possível em todo o espaço de busca, ainda que possa levar mais tempo. Isto permite criar soluções mais fiáveis, embora possa demorar mais tempo a obtê-las. Esta pode ser uma boa abordagem se existirem relações desconhecidas entre as diferentes variáveis do sistema ou se temos um sistema mais complexo ou de caixa negra.

Ao treinar um modelo de machine learning em IA, normalmente procuramos evitar atingir um ótimo local (que pode ser uma boa solução, mas não a melhor) enquanto esperamos atingir o ótimo global, o que se traduz num modelo mais robusto e generalizável. Embora, em alguns casos em que o tempo é um fator importante, uma abordagem gulosa pode ser suficiente.

A seguir, aplicamos ambas as abordagens a um caso de uso específico: alocação de agentes imobiliários a apartamentos para venda.

Caso de uso

Suponha que é uma empresa imobiliária. Como poderia otimizar a alocação de apartamentos aos agentes imobiliários disponíveis?

O primeiro aspeto importante a considerar é a(s) variável(is) que pretendemos otimizar. É o tempo? O lucro? O número de visitas necessárias? A diversidade nas vendas? Uma boa suposição é considerar que pretendemos gerar o lucro máximo no menor tempo possível. Assim, uma boa métrica a otimizar poderá ser o preço por dia (rácio entre o lucro e os dias necessários para venda).

Dados

Em termos de dados disponíveis, supomos que temos as seguintes informações:

• Apartamento:

  • Número de quartos
  • Área (M2)
  • …
  • Preço de compra
  • Localização
  • Características sobre infraestruturas na área envolvente

• Agente Imobiliário:

  • Inventário:
    • Número total de apartamentos a vender, baseado em localização, faixa de preço, tipologia, área, etc
  • Vendas históricas:
    • Vendas realizadas no passado (para uma janela de tempo específica) baseadas em localização, faixa de preço, tipologia, área, etc

• Apartamento vs. Agente:

  • Dias previstos no mercado para um determinado par (apartamento, agente). Ou seja, em quantos dias um determinado agente consegue vender um determinado apartamento.
    Como esta é uma informação mais difícil de obter, uma alternativa é treinar um algoritmo de machine learning (baseado nos dados restantes) que possa prever os dias no mercado para um par específico (apartamento, agente)

• Mercado:

  • Número de apartamentos vendidos no passado (últimos x dias)
  • Apartamentos atualmente disponíveis para venda

Aplicação de otimização local

Seguindo a ideologia de otimização local, uma abordagem provável seria começar com as melhores correspondências entre agente imobiliário e apartamento, ou seja, começar por alocar os agentes mais adequados aos apartamentos respetivos primeiro.

Como vimos anteriormente, euros/dia é uma boa métrica a considerar nas alocações, portanto o passo 1 é calcular o euros por dia para cada par <Agente, Apartamento>. De seguida, como esta é uma abordagem gulosa, classificamos as alocações (em ordem descendente) pelo valor de euros_por_dia e começamos a alocar os agentes aos apartamentos com métrica euros_por_dia mais elevada.

Assim, a abordagem pode ser definida da seguinte forma:

1. Calcular euros por dia:
   1. Margem = avaliação do agente para um apartamento específico – preço de compra
   2. euros por dia = margem / previsão de dias no mercado para (apartamento, agente)
2. Processo de alocação: classificação de euros por dia (em ordem descendente)

Aplicação de otimização global

Utilizando uma abordagem de otimização global, para além de euros por dia, podemos considerar outras métricas que podem ser relevantes ao medir o quão adequada é a alocação de um determinado apartamento a um agente.

1. Velocidade_de_venda: se um determinado agente é bom a vender um tipo específico de apartamento, devemos atribuir-lhe mais apartamentos desse tipo
2. Inventário: se um determinado agente já tem apartamentos similares a vender, provavelmente não devemos alocar mais apartamentos com essas características a ele. Uma alternativa é definir um número máximo de apartamentos atribuídos a um único agente.

(Neste contexto, supomos que apartamentos similares têm a mesma faixa de preço, faixa de área e a mesma tipologia.)

Assim, existem 3 aspetos a considerar no modelo de alocação:

• [maximizar] euros por dia: lucro/dias, igual à abordagem de otimização local

• [maximizar] Velocidade de venda: percentagem de apartamentos similares vendidos nos últimos X dias

• [minimizar] Inventário: percentagem de apartamentos similares em inventário

Utilizando esta informação, podemos definir uma função objetivo que o nosso modelo de alocação tentará maximizar, assumindo que queremos alocar n apartamentos a agentes imobiliários.

![ $$\frac{\sum_{}^{allocations} (\alpha * euros\_por\_dia + \beta * velocidade\_venda + \gamma * inventario)}{n}$$ ](/wp-content/ql-cache/quicklatex.com-ad7b1d74935a86f0ec51f6713cfa5552_l3.png)

Esta função corresponde essencialmente a uma média ponderada, em que o nosso modelo de alocação aprenderá os melhores parâmetros para maximizar a função objetivo.

Curso

Metaheuristics: Theory and Applications

Conheça este curso para saber mais sobre abordagens de otimização!

Saber Mais

Comparação entre soluções

Considerando este caso de uso específico, usando uma abordagem de otimização local, estaríamos a fazer as alocações sequencialmente (alocação a alocação), começando pelas melhores alocações, sem considerar o impacto de cada alocação no conjunto total de alocações. Portanto, não podemos garantir que, no final, atingiremos a melhor solução, embora possamos obter uma solução aceitável em menos tempo. Se aplicarmos uma técnica de otimização global, globalmente, as alocações deverão ser mais precisas, pois estamos a considerar o conjunto total de alocações e não alocação a alocação. Isto significa que o desempenho deverá ser melhor, embora o tempo para obter a solução possa ser mais longo.

O facto de podermos ter múltiplas variáveis a otimizar, dependendo da forma como pretendemos "medir" o quão boa é uma determinada alocação, é outro fator que beneficia a abordagem global em vez da abordagem local neste caso de uso específico.

A quantidade de dados disponíveis também pode ser um fator decisivo importante na escolha da melhor abordagem. Normalmente, as abordagens de otimização global requerem mais dados do que as abordagens de otimização local.

Finalmente, o tipo de processamento de dados também é importante. Se as alocações forem realizadas em lotes, então uma abordagem global determinaria as melhores alocações considerando todo o sistema (conjunto de todas as alocações). Por outro lado, se as alocações são suposto serem entregues de forma contínua, uma abordagem gulosa seria útil, pois não precisa considerar alocações de múltiplos apartamentos.

Quer aprofundar este tema?

Marque uma reunião com Kelwin Fernandes

Conheça Kelwin Saber Mais

Conclusão

Voltando à primeira questão, no campo da otimização, o caminho mais rápido e mais promissor pode não ser o melhor a seguir, especialmente se envolver tomar várias decisões ao longo do processo.

Uma abordagem de otimização local pode ser mais gulosa na forma como encontra a melhor solução, o que se traduz numa boa solução, mas não a melhor. Utilizando uma abordagem mais de otimização global, pode levar mais tempo, e a solução obtida deverá ser mais confiável.

Utilizou recentemente alguma destas abordagens? Qual considera mais apropriada para utilizar? Não hesite em contactar-nos, ficaríamos felizes em conhecer a sua opinião sobre este tema!