Estratégias de Predição de Preços com base no Feedback do
Ambiente em Cadeias de Suprimento Dinâmicas
Gilzamir F. Gomes1 , Gustavo Augusto Lima de Campos2 , Enyo José Tavares Gonçalves3
1
Departamento de Computação – Universidade Estadual Vale do Acaraú (UEVA)
Sobral – CE – Brazil
2
Departamento de Computação – Universidade Estadual do Ceará (UECE)
Fortaleza – CE – Brazil
3
Departamento de Computação
Universidade Federal do Ceará (UFC) – Quixadá, CE – Brazil
[email protected], [email protected], [email protected]
Abstract. Dynamic pricing strategies in dynamic and highly competitive markets is a key feature of an agent in modern electronic trading environments.
Agents for these markets can explore the environment feedback and information
from the past to perform predictions. This work strategies were explored using
environment feedback in Trading Agent Competition for Supply Chain Management - TACSCM. It was shown that the use of heuristics that make use of information Recent on the environment or the use of machine learning techniques
can improve the performance of an agent which starts with a simple heuristic.
In controlled experiments, it was found that the use of neural networks based on
a strategy of retraining and logs of past games only supplanted the use of neural
networks trained using only logs of past games, even when little data are used.
Resumo. Estratégias dinâmicas de precificação em mercados dinâmicos e altamente competitivos é uma característica fundamental de um agente nos modernos ambientes de negociação eletrônica. Agentes para estes mercados podem explorar o feedback do ambiente e informações do passado recente e remoto para realizarem previsões. Neste trabalho, foram exploradas estratégias
que utilizam o feedback do ambiente no Trading Agent Competition for Supply
Chain Management - TAC SCM. Mostrou-se que o uso de heurísticas que fazem
uso de informações recentes sobre o ambiente ou o uso técnicas de aprendizado
de máquina pode melhorar o desempenho de um agente que inicia com uma
heurística simples. Em experimentos controlados, verificou-se que o uso de redes neurais baseada em uma estratégia de retraining e logs de jogos passados
suplantou o uso de apenas redes neurais treinada com o uso somente de logs
de jogos passados (dados do passado remoto), mesmo quando poucos dados do
passado recente são utilizados.
1. Introdução
Gerenciamento da cadeia de suprimentos é um ambiente dinâmico, não determinístico,
estocástico e multi-agente. O Trading Agent Competition for Supply Management (TAC
SCM) captura parte dessa complexidade em um jogo com seis participantes competindo
em um mercado de venda de computadores pessoais (doravante simplesmente computadores). Fundamentalmente, todos os agentes devem realizar três atividades interdependentes:
1. venda de computadores;
2. compra de componentes para a montagem de computadores; e
3. gerenciamento de uma linha de montagem de computadores.
Neste artigo, é apresentada uma investigação sobre o uso de feedbacks do ambiente para
o ajuste de preços de oferta em competições do TAC SCM. O objetivo dessa investigação
é a obtenção de um modelo eficiente para predição de preços de oferta no TAC SCM,
seja por meio de técnicas de aprendizado de máquina ou de heurística obtidas a partir da
análise do ambiente. Vale ressaltar que este é um dos principais problemas abordados
para o desenvolvimento de agentes de negociação. E uma observação importante é que a
melhor estratégia de precificação não é necessariamente aquela que propicia a venda da
maior quantidade de produtos, mas sim aquela que garante um maior lucro.
Para uma melhor apresentação das estratégias desenvolvidas e dos resultados obtidos neste trabalho, o texto foi organizado da seguinte forma: na Seção 2, o TAC SCM
é apresentado; na Seção 3, trabalhos relacionados ao trabalho atual são apresentados; na
Seção 4, as estratégias desenvolvidas para uso do feedback do ambiente são apresentadas;
na Seção 5, os experimentos realizados são descritos e os resultados obtidos são apresentados; na Seção 6, as conclusões e os trabalhos futuros são apresentados.
2. A Competição de Agentes Negociadores para Gerenciamento da Cadeia
de Suprimentos
Trading Agent Competition (TAC) ou Competição de Agentes de Negociação é um fórum
internacional projetado para investigação de estratégias de negociação autônomas em diferentes cenários de negociação. Um destes cenários é a competição de agentes em um
mercado de venda de computadores pessoais, denominado de TAC SCM (Trading Agent
Competition for Supply Chain Management).
TAC SCM é um cenário de montagem de computadores pessoais (PC - Personal
Computer) baseado na aquisição de componentes e na venda de computadores montados
para clientes. Neste cenário, seis agentes competem por pedidos de clientes e pela aquisição de vários tipos de componentes. Portanto, o TAC-SCM é um cenário que simula
a problemática do gerenciamento de cadeias de suprimento e provê um ambiente de simulação onde diferentes soluções para a problemática de negociação em uma cadeia de
suprimentos podem ser analisadas.
Collins et al. (Collins et al. 2006) realizam uma descrição detalhada da competição TAC-SCM. Essa competição ocorre ao longo de 220 dias simulados, cada dia simulado corresponde a 15 segundos. Ao longo dos 220 dias simulados, seis fábricas de
computadores pessoais (PCs) competem pela venda de PCs para clientes e pela obtenção
de componentes para a montagem de PCs. Ou seja, PCs são montados a partir de componentes como placa-mãe, memória principal, processador e disco rígido. Estes componentes são disponibilizados em diferentes versões (por exemplo, diferentes CPUs, diferentes
placas-mãe, etc.) por vários fornecedores. As montadoras contam com uma fábrica com
uma linha de montagem para PCs e um armazém para estocagem de componentes e PCs
finalizados. A capacidade da fábrica é expressa em ciclos de produção. O problema
das montadoras pode ser dividido nos seguintes subproblemas: venda de computadores
montados para clientes, obtenção de componentes, gerenciamento da produção e gerenciamento da entrega de produtos finalizados. Neste trabalho, o interesse é no problema
de venda de computadores montados para clientes, mais especificamente, na predição do
melhor preço de oferta em resposta à pedidos de orçamento feitos por clientes.
A demanda de clientes vem na forma de pedidos de orçamento Request for Quotes
– RFQs enviadas diariamente requisitando diferentes tipos de PCs, cada tipo sendo composto por uma combinação diferente de componentes. O jogo TAC-SCM começa quando
um ou mais agentes se conectam a um servidor de jogo. O servidor simula os fornecedores, clientes, um banco para serviços bancários e serviços de produção e de estocagem
para cada agente. Uma competição ocorre ao longo de um número pré-definido de dias
e, quando termina, o agente com maior saldo em conta bancária é declarado vencedor. O
jogo representa uma ampla variedade de situações de cadeias de suprimento. É um desafio
que requer múltiplos agentes competirem de forma concorrente em múltiplos mercados
(mercados para diferentes componentes no lado dos fornecedores e mercado para diferentes produtos no lado dos clientes) com interdependência e informações incompletas.
Isso permite diferentes estratégias de agentes (por exemplo, especializar-se em um determinado tipo de produto, armazenar componentes que estão em baixa no mercado). Os
agentes devem demonstrar suas habilidades ao reagir a variações na demanda de clientes
e disponibilidade de fornecedores, assim como se adaptarem às estratégias adotadas por
outros competidores.
Do ponto de vista da venda de computadores, os agentes são limitados pela capacidade de suas linhas de montagem e pelos componentes que conseguem comprar de
um total de oito fornecedores. Com estes recursos (capacidade de produção e inventário
de componentes, um agente deve competir pela venda de PCs. Em um determinado dia
d, clientes lançam pedidos de orçamento (Request For Quotes – RFQs) aos agentes. Os
agentes respondem aos pedidos de orçamento com ofertas que especificam o preço de
oferta e o prazo de entrega para cada RFQ. No dia d + 1, os clientes selecionam ofertas enviadas pelos agentes de acordo com o prazo de entrega prometido e com o preço
da oferta. A Figura 1 ilustra claramente os eventos diários que podem ocorrer em uma
competição do TAC SCM.
Na próxima seção, algumas das mais bem sucedidas estratégias para TAC SCM
serão apresentadas.
3. Trabalhos Relacionados
Stan et al. (Stan et al. 2006) utilizaram heurísticas para a definição de preços de oferta.
As heurísticas foram implementadas no agente Phant, considerado um forte competidor
do TAC SCM. A estratégia de precificação desse agente é baseada em um relatório diário
de preços. Assim, um relatório recebido em dia um simulado d contém duas informações:
o menor e o maior peço que clientes pagaram por tipo de computador no dia d − 1, para
d > 0. O maior preço é utilizado para definição do preço de oferta na estratégia do agente
Phant, pois os autores partem do pressuposto que o maior preço pago por um produto
no dia anterior foi o melhor preço de oferta realizado. Contudo, o maior preço pago é
ajustado de acordo com o nível de utilização da linha de montagem. Parte do trabalho
Figura 1. Ilustração dos eventos diários ocorridos durante alguns dias no TACSCM (Collins et al. 2006).
descrito neste artigo também se baseia nesse relatório de preços.
Chatzidimitriou et al. (Chatzidimitriou et al. 2008) utilizou técnicas de aprendizagem de máquina no módulo de ofertas do agente Mertacor. Para geração do modelo de
previsão do preço de oferta ótimo, foi utilizado aprendizagem supervisionada. Os dados
de treinamento foram obtidos de logs de jogos passados que incluíam os agentes com os
quais o agente Mertacor possivelmente iria competir.
Pardoe e Stone (Pardoe and Stone 2009) desenvolveram um dos agentes mais bem
sucedidos no TAC SCM, o TacTex06. A estratégia desse agente consiste em fazer predições sobre o futuro da economia, como preços que serão cobrados por fornecedores de
componentes e o nível da demanda dos consumidores. Com base nessas informações, o
agente TacTex-06 planeja suas ações futuras com a finalidade de maximizar seu lucro. O
componente fundamental desse agente é sua habilidade para adaptar estas predições baseado no comportamento observado de outros agentes. O TacTex-06 é baseado na ideia de
que uma abordagem eficaz de agente requer o desenvolvimento de módulos fortemente
acoplados para interação com fornecedores, consumidores e a fábrica.
He et al. (He et al. 2006) desenvolveram um agente competitivo que utiliza lógica
fuzzy para selecionar preços de oferta lucrativos. O agente recebe RFQs de clientes especificando algumas preferências: quantidade de um tipo particular de PC para ser entregue
em um dia especificado e um preço de reserva (preço máximo que o cliente está disposto a
pagar pelo produto). Quando seleciona para quais RFQs responder com ofertas, o agente
ordena estas ofertas de acordo o potencial lucro que elas podem trazer e de acordo com
inventário mantido pelo agente. O preço a ser ofertado é definido por um conjunto regras
fuzzy.
Fasli e Kovalchuk (Fasli and Kovalchuk 2011) mostraram que preços vencedores
no leilão de vendas de computadores pode ser predito por meio da modelagem do comportamento dos competidores. O trabalho deles mostrou que a estratégia de modelagem e
predição dos oponentes é uma técnica adequada para o ambiente que tem um formato de
jogo (isto é, vários participantes competindo uns contra os outros com objetivo de obterem a maior pontuação). Essa estratégia pode ajudar na tomada decisões mais precisas em
ambientes dinâmicos e competitivos. Os pesquisadores utilizaram redes neurais artificiais
e programação genética para a predição do comportamento dos oponentes.
4. Uso de feedback do ambiente para determinação do melhor preço de
oferta
Os agentes podem obter o feedback do ambiente para avaliarem suas ações e, possivelmente, melhorarem suas ações futuras. Estratégias de agentes do TAC SCM geralmente
utilizam o feedback do ambiente. Neste trabalho, o uso do feedback foi estudado e sistematizado com base em duas fontes de informações:
1. o relatório de preços do TAC SCM, que provê informações recentes sobre os preços de venda de computadores durante uma rodada; e
2. a resposta dos clientes à ofertas de computadores.
Ambas as fontes proveem informações recentes sobre o jogo. Por exemplo, o relatório
de preços do dia d contém os maiores e os menores preços pagos por tipo de computador
negociados no dia d − 1. Se um agente A enviou n ofertas no dia d − 1 e recebeu m
pedidos no dia d, pode-se calcular a taxa de sucesso bruta do agente A como: m/n,
n > 0, m ≥ 0, d > 0. Alguns agentes monitoram essa taxa de sucesso e ajustam o preço
de oferta de acordo com ela.
Para explorar o feedback do ambiente, este trabalho foi sistematizado com base
em três suposições:
1. dado um tipo de produto i, o maior e o menor preço pago por produtos deste tipo
no dia d, preços estes representados respectivamente por hi,d e li,d , podem ser
inferidos com base nos relatórios de preços dos dias que antecedem d, para d > 0;
2. os valores pagos no dia d por produtos do tipo i estão distribuídos entre hi,d e li,d
com base em uma distribuição que pode ser inferida por meio da análise de logs
de jogos passados e de dados obtidos durante um jogo. Os dados de logs de jogos
passados, denominou-se dados offline e aos dados obtidos durante um jogo em
andamento, denominou-se dados online.
3. o sucesso do agente na venda de computadores dependente da acurácia das estimativas de hi,d , li,d e da distribuição de preços.
Neste trabalho, mostra-se que essas três suposições são plausíveis e com potencial para o
desenvolvimento de agentes de sucesso.
A primeira abordagem utilizada para definição do preço de oferta é trivial e consiste em duas suposições:
1. hi,d = hi,d−1 e li,d = li,d−1 ; e
2. Os preços no dia d para um produto do tipo i estão uniformemente distribuídos no
intervalo [li,d , hi,d ].
Com base nessas duas suposições, uma primeira abordagem, denominada de heurística
simples e descrita na Seção 4.1, foi elaborada. Na verdade, a heurística simples mostrada
na Figura 2 é outro elemento sobre qual a sistematização do uso do feedback provido
pelo ambiente foi explorada neste trabalho. A estrutura geral dessa heurística permanece
ao longo de vários experimentos, alterando-se apenas os componentes de previsão do
algoritmo.
4.1. Heurística Simples
O relatório de preços do dia d contém o menor e o maior preços pago por tipo de computador no dia d − 1, para d > 0. Esse relatório provê uma importante informação sobre
Figura 2. Heurística simples para precificação.
o preço de oferta, dado que se trata de informações recentes sobre o preço de oferta de
todos os agentes no jogo. É uma forma de se saber os limites de oferta nos quais os agentes estão atuando. Dado um tipo de produto i, o maior preço pago por produto deste tipo
no dia d é denotado por hi,d e o menor preço é denotado por li,d . O TAC SCM contém
informações parciais, isso significa que não está disponível, por exemplo, a distribuição
de preços de ofertas no dia d no intervalo Ii,d = [li,d , hi,d ] para um produto do tipo i. Há
pelo menos duas formas de se obter uma distribuição aproximada: (1) por meio de logs de
jogos passados envolvendo os agentes com os quais se deseja competir ou (2) supor uma
distribuição dos preços no intervalo dado. Para a primeira forma, pode-se utilizar técnicas
estatística e de aprendizagem de máquina. A segunda forma, contudo, é mais simples pois
parte-se de uma suposição prévia ou de um “chute”. Pode-se supor, por exemplo, que no
dia atual os preços estão distribuídos uniformemente no intervalo Ii,d . Neste trabalho,
partiu-se dessa suposição para a concepção da heurística simples. Por exemplo, se no dia
d o intervalo de preços para o produto do tipo i (1 ≤ i ≤ 16), foi Ii,d = [li,d , hi,d ], a
suposição é de que no dia d, todos os preços de oferta vencedores para o produto do tipo i
estarão uniformemente distribuídos no intervalo Ii,d dado. Além disso, como o agente não
conhece intervalo Ii,d , apenas o intervalo Ii,d−1 , estimasse que Ii,d ≈ Ii,d−1 . Com base
nessas suposições, uma primeira versão da heurística simples foi gerada, como mostrado
na Figura 2.
O algoritmo da Figura 2 é baseado em (Pardoe and Stone 2005) e consiste na
escolha de um preço de referência e na seleção de uma fração desse preço de referência como preço de oferta. Cada fração do preço de referência é selecionado com uma
probabilidade igual à probabilidade estimada desse preço ser aceito pelo cliente. Neste
trabalho, para uma oferta realizada no dia d, escolheu-se o preço base de mercado como
preço de referência. O preço base de mercado para cada tipo de produto é definido no
início de um jogo e não muda durante todo o jogo. O intervalo de frações do preço de
referência, neste trabalho, foi determinado empiricamente, com base no fato de que o valores menores do que 80% do peço de referência não darem lucro e no fato de que valores
maiores do que 125% do preço de referência dificilmente serem selecionados. No caso da
heurística simples, valores maiores ou iguais a 100% do preço de referência são ignorados. Em um primeiro momento, a heurística parece plausível, pois captura os dados mais
recentes sobre os preços que outros agentes praticaram no jogo.
Percebe-se que dois componentes são fundamentais na heurística simples: (1) a
estimativa do maior e o menor preço pago por tipo de produto no dia d e (2) a distribuição
estimada de preços para determinado tipo de produto no intervalo definido pelos supostos
menor e maior preços pagos por tipo de produto no dia d. Analisamos estratégias baseadas
em heurísticas e redes neurais artificiais com aprendizado supervisionado para diferentes
estratégias de otimização destes dois componentes.
O agente dotado da heurística simples foi denominado de USA (UeceUva Simple
Agent).
4.2. Inferindo a distribuição de preços
Neste trabalho, foi desenvolvida uma heurística relativamente eficiente para inferir a distribuição de preços entre o menor e o maior preço pago por tipo de produto em um determinado dia simulado.
Heurística para cálculo da distribuição de preços
Na heurística simples, é suposto que os preços ofertados em um determinado dia para um
produto de determinado tipo estão uniformemente distribuídos entre o menor e o maior
preços pagos por produto do tipo determinado. Essa suposição pareceu razoável inicialmente. Uma hipótese alternativa, contudo, é que o preço de oferta da concorrência vai girar em torno do preço de reserva definido pelos clientes. Portanto, elaboramos um método
para “deformar” a distribuição uniforme de modo que os preços inicialmente distribuídos
uniformemente passem a se concentrar em torno do preço de reserva. A distribuição de
e
preços foi simulada gerando-se uniformemente valores no intervalo li,d
e hei,d para um proe
e
duto do tipo i no dia d. Os valores li,d e hi,d são as estimativas de hi,d e li,d . Inicialmente,
e
a estimativa foi que li,d
= li,d−1 e hei,d = li,d−1 . Para um pedido de orçamento com preço
e
de reserva Ri para produtos do tipo i, calculou-se o valor δ = max(Ri , hei,d ) − li,d
. Para
simular a distribuição uniforme, uma sequência de valores distribuídos uniformemente no
e
intervalo [li,d
, hei,d ] foi gerada. Depois disso, os valores dessa sequência inicial foram deslocados na direção de Ri de acordo com a Equação 1, gerando-se a distribuição resultante.
E Equação 1 é descrita como:
k
pt+1
= ptj + α · e(1− δ ) · k
j
(1)
onde, k = (Ri − ptj ), ptj representa o j − ésimo valor da distribuição uniforme
e
e
representada pela sequência (li,d
, li,d
+ 1, ..., hei,d ) e pt+1
representa o j-ésimo termo da
j
distribuição original após a simulação. O fator α determina a intensidade do deslocamento da distribuição em direção do preço de reserva (ou seja, o deslocamento que
cada preço da distribuição original sofrerá proporcionalmente à distância de cada valor
ao preço de reserva). Neste trabalho, α foi definido inicialmente e empiricamente como
random(0, 0.6) + 0.01. O intuito dessa equação é deslocar ptj em direção a Ri , contudo,
sem garantir que o valor resultante da transformação de ptj resulte em Ri . O efeito práe
, hei,d ] para
tico é alterar a distribuição de preços originalmente uniforme no intervalo [li,d
uma distribuição tal que grande parte dos valores se concentrem em torno de Ri . Dize-se,
assim, que Ri deforma a distribuição original de preços.
A Equação 1 pode ser vista como um caso especial da equação mais geral pt+1
=
j
t+1
t
pj + βk, onde β ∈ [0, 1] é definido como a intensidade do deslocamento de pj rumo ao
valor ptj + k. Para tornar intensidade do deslocamento inversamente proporcional ao valor
k
de k, β foi definido como β = α · e1− δ , que foi ajustado empiricamente e mostrou bons
resultados.
Por exemplo, suponha o intervalo de preços definido por [1500, 1600] para um produto do tipo 1. Além disso, suponha que recebeu-se um pedido de orçamento com preço
de reserva igual a 1590. A simulação gera 101 preços uniformemente distribuídos no intervalo dado, gerando-se a série 1500, 1501, ..., 1600. Suponha que random(0, 0.6)+0.01
tenha gerado o valor 0.15 para o preço 1550, que é o j − ésimo termo da distribuição original. Para o cálculo do valor do j − ésimo termo, Primeiro, calcula-se
δ = max(1590, 1550) − 1500 = 90. Em seguida, substitui-se os valores na Equação
1, obtendo-se:
pt+1
= 1550 + 0.15 · e(1−40/90) · 40 = 1560.46
j
e
, hei,d ] forem deslocados para próDepois que todos os valores no intervalo [li,d
ximo do preço de reserva, dado um preço de oferta Po , o calculo da probabilidade de Po
ser aceito é feito contando-se, na distribuição resultante, a quantidade de valores maiores
do que Po e dividindo-se o resultado pela quantidade total de valores na distribuição resultante. É interessante notar que o cálculo da probabilidade de Po é, de alguma forma,
equivalente ao cálculo da função de densidade de probabilidade, já que estamos calculando a probabilidade dos preços de oferta da concorrência serem maiores do que Po .
O agente dotado da heurística simples modificado com o cálculo da probabilidade de um preço de oferta ser aceito de acordo com a heurística descrita nessa seção,
denominou-se UAV2 (UeceUva Agent Version 2). Doravante, a heurística resultante descrita nesta seção será denominada de Heurística de Distribuição em torno do Preço de
Reserva (DPR). Foi surpreendente perceber que o agente UAV2 apresentou um comportamento superior ao agente USA. Isso mostra que a heurística DPR é promissora.
4.3. Inferindo os valores no relatório de preços
Em um ambiente altamente competitivo, o maior e o menor preço pago por um determinado tipo de produto em uma determinado dia estão muito próximos. Portanto, gerar
uma oferta com um valor entre estes preços é uma estratégia plausível. Presumivelmente,
quanto melhor a estimativa destes valores, mais eficiente será a estratégia de oferta baseada nesses preços. Portanto, a próxima tentativa de melhoramento da heurística simples
consistiu no uso de redes neurais artificiais, baseadas no algoritmo backpropagation, para
predição dos menores e maiores preços pagos por tipo de produto em um determinado
dia. Uma segunda abordagem consistiu no uso de uma arquitetura de agente com redes
neurais baseada em retraining (Dempsey et al. 2002).
Atributo(xi,d )
x1
x2
x3
x4
x5
x6
Descrição
Maior preço de reserva no dia d para produtos do tipo i
Menor preço e reserva no dia d para produtos do tipo i
Menor preço pago no dia d − 1 para produtos do tipo i
Maior preço pago no dia d − 1 para produtos do tipo i
Demanda do dia para o segmento de mercado do produto
do tipo i
Demanda total de produtos no dia d
Tabela 1. Variáveis do ambiente utilizadas para treinamento das redes neurais
que preveem o menor e maior preço pago por tipo de produto em um determinado dia.
Modelos de Aprendizagem
Duas estratégias de predição dos menores e maiores preços pagos por tipo de produto
foram avaliadas: ambas utilizando redes neurais de múltiplas camadas com o algoritmo
backpropagation. A primeira estratégia, denominada de estratégia estática, consiste no
uso de duas redes neurais treinadas com dados offline para cada tipo de produto: uma
para a previsão do menor preço de oferta pago por tipo de produto e outra para o maior
preço de oferta pago por tipo de produto. A segunda estratégia, consiste também no
uso de duas redes neurais para previsão do menor e do maior preço pago por tipo de
produto, mas inclui uma estratégia de retraining a partir de dados coletados durante o
jogo em andamento (dados recentes). A segunda estratégia foi denominada de estratégia
dinâmica.
Em ambas as estratégias, cada conjunto de exemplos foi definido como Et,i =
(xi,d , yi,d ), para t ∈ {low, hight}, i ∈ {1, 2, 3, ..., 16} e 0 ≤ d ≤ 219, onde xi,d é um
vetor de atributos associado a um tipo de produto i cujos valores consistem em variáveis
do ambiente coletadas no dia d e yi,d é um escalar que representa o preço a ser previsto do
produto do tipo i no dia d. Os termos low e rigth estão relacionados ao preço mais baixo
e ao preço mais alto, respectivamente, pago por produto do tipo i em um determinado dia.
Os atributos de entrada são resumidos na Tabela 1.
Os exemplos de treinamento foram extraídos de um total de seis logs de jogos
passados. Cinco logs incluem os agentes Mertacor, DeepMaize, MinneTac e Dummies
e um log inclui os agentes Mertacor e Dummy. De cada log foram extraídos exemplos
que vão do dia 20 ao dia 200. Os primeiros e os últimos vinte dias de cada jogo foram
removidos do conjunto de exemplos gerados, pois nestes dias os agentes geralmente adotam estratégias diferenciadas. Nos primeiros vinte dias, geralmente preços mais altos são
ofertados, dado que geralmente o jogo inicia com baixa competitividade. Nos últimos
20 dias, geralmente preços mais baixos são ofertados de modo que produtos em estoque
sejam vendidos antes do final do jogo. Em ambas as estratégias com redes neurais, a
seguinte configuração mostrou ser eficiente:
• Rede Neural com uma camada escondida
• Total de 100 neurônios na camada escondia
• Os dados de entrada foram normalizados de acordo com a equação (normalização
0
i
, onde xi é o valor original do atributo i, avgi é a média
estatística): xi = xi −avg
dpi
0
do atributo i em todos os exemplos, dpi é o desvio padrão do atributo i e xi é o
valor normalizado do atributo i.
• Os dados da saída foram normalizados de acordo com a equação (normalização
max-min equalizado) y 0 = y − ymin/(ymax − ymin), onde ymin é o menor
valor do atributo de saída no conjunto de exemplos, ymax é o valor máximo do
atributo de saída no conjunto de exemplos e y 0 é o valor normalizado da saída em
um exemplo do conjunto.
Foi notado que a normalização estatística para as saídas das redes neurais fizeram com
que as redes neurais não convergissem. Contudo, as redes convergiram com utilização de
normalização max-min equalizada nas saídas. O inverso ocorreu com a normalização das
entradas: as redes neurais não convergiram com normalização max-min equalizada das
entradas, mas convergiram com normalização estatística das entradas.
No treinamento com dados offline, o conjunto de exemplos foi dividido em dois
conjuntos: conjunto de treinamento e conjunto de teste. Cinco logs foram selecionados
para treinamento das redes neurais (um log com os agentes Mertacor e Dummy e três logs
com os agentes Mertacor, DeepMaize, MinneTac e Dummy). O log restante, representando um jogo com os agentes Mertacor, DeepMaize MinneTac e Dummy, foi utilizado
para geração do conjunto de teste.
e
e
Na estratégia estática, o agente UAV2 foi alterado de modo que os valores li,d
e
hi,d fossem calculados pela rede neural. O agente resultante foi denominado de UAV3. A
configuração geral deste agente é ilustrada na Figura 3.
Estratégia Dinâmica para Predição de Preços.
Na estratégia dinâmica, as redes neurais foram treinadas como na estratégia estática.
Além disso, as redes neurais foram retreinadas à medida que dados foram coletados do
ambiente, do jogo em andamento. Algumas questões precisaram ser respondidas para se
chegar a uma estratégia de retraining funcional:
1. Como decidir qual o momento de realizar o retraining?
2. Como verificar se a rede neural retreinada é melhor do que rede neural anterior?
3. Como selecionar os exemplos a serem utilizados no retraining?
Para se decidir o momento de realização do retraining, optou-se por uma estratégia
estática. As redes neurais foram divididas em quatro grupos de seis redes neurais e um
grupo de oito redes neurais. De dois em dois dias, um grupo diferente é treinado. Optouse por esta estratégia por uma questão de desempenho computacional, dado que treinar
todas as redes neurais de uma única vez acarretaria um atraso na resposta do agente, que
tem apenas quinze segundos para responder aos pedidos de orçamento dos clientes.
Durante o retraining uma nova rede neural é criada para cada rede existente. A
nova rede neural é semelhante à rede neural treinada com dados estáticos (rede atual)
exceto pelos pesos da conexão entre os neurônios, que são gerados aleatoriamente. A nova
rede neural para uma rede existente é treinada com um conjunto de dados correspondente
aos últimos vinte dias simulados. O erro quadrático médio da rede neural recentemente
treinada é comparado com o erro quadrático médio da rede neural atual. Se o erro da nova
rede neural foi menor do que o erro da rede neural atual, a nova rede neural ocupa o lugar
da rede neural atual.
Figura 3. Configuração de agente com redes neurais para previsão do maior e
do menor preço de venda por tipo de produto. O agente conta com 32 redes neurais. Para cada tipo de produto i, há duas redes neurais: uma para previsão do
próximo maior preço de venda de produtos do tipo i (denominada de RN A(i, 0))
e outra para previsão do próximo menor preço de venda de produtos do tipo i
(denominada de RN A(i, 1)).
Os exemplos utilizados durante o retraining são os vinte exemplos mais recentes coletados do ambiente. Uma quantidade maior de exemplos, impacta no desempenho
computacional do agente, que tem apenas quinze segundos para tomar às decisões referentes a um dia simulado, como já foi enfatizado neste texto.
O agente com retraining é uma extensão do agente UAV3 e foi denominado de
UAV4 (UECEUVA Agent Version 4).
4.4. Feedback Positivo e Feedback Negativo
Seja n a quantidade ofertas enviadas pelo agente A no dia d e m a quantidade de pedidos
de clientes em respostas às ofertas do agente A no dia d. A taxa de sucesso do agente A
no dia d pode ser calculada como
sa,d = m/n
(2)
Também foi definido a média da taxa de sucesso entre os dias que vão de d − ∆
a d como s∆ . Assim, o valor α da Equação 1 foi definido como α = s∆ , resultando na
equação
k
(3)
pt+1
= ptj + s∆ · e(1− δ ) · k
j
Observe que se s∆ varia no intervalo [0, 1] e quanto mais próximo de um for o
valor da média da taxa de sucesso, maior será a deformação da distribuição uniforme
em direção ao preço de reserva (o que leva a preços de oferta mais altos); caso s∆ esteja
próximo de zero, mais parecido com a distribuição uniforme será a distribuição final (o
que leva a preços de oferta mais baixos).
O agente que utiliza feedbacks positivos e negativos é uma extensão do agente
UAV2 foi denominado de UAV5 (UECEUVA Agent Version 5).
5. Experimentos e Resultados
Para se mensurar o desempenho dos agentes, foi utilizado o servidor modificado de acordo
com (Sodomka et al. 2007) e a quantidade de simulações foi ajustada de acordo com
Agente/Componentes
USA
UAV2
UAV3
UAV4
UAV5
Heurística Simples
Distribuição de Preços
alterada conforme
Equação 1
Redes Neurais
Retraining
Feedback
Positivo/Negativo
X
X
X
X
X
X
X
X
X
X
X
X
X
Tabela 2. Agentes e suas configurações.
(a)
(b)
Figura 4. Competições envolvendo o agente USA. (a) Desempenho médio dos
agentes ao longo de oito jogos. (d) Desvio padrão do desempenho dos agentes
ao longo de oito jogos.
a recomendação em (Sodomka et al. 2007). Para comparar diferentes configurações do
agente UECEUVA, realizou-se 8 simulações de competições contras os agentes Mertacor
e Dummy. A Tabela 2 resume as versões do agente UECEUVA testadas. Todos as simulações ocorreram em um computador Intel (R) Core (TM) i5-2410M com CPU 2.30GHz
e 4GB de memória RAM.
As Figuras 4, 5, 6, 7 e 8 mostram o desempenho médio e o desvio padrão do
desempenho das diferentes versões do agente que incorporou as estratégias desenvolvidas
neste trabalho. O agente em geral é chamado de UECEUVA, mas cada versão do agente
recebe um nome que a identifica. Os resultados mostrados foram coletados de um total
de oito simulações para avaliar cada versão, de um total de cinco versões. No total, foram
realizadas quarenta simulações para se avaliar todas as versões do agente UECEUVA.
De acordo com o gráficos mostrado na Figura 4 (a), A versão do agente UECEUVA denominada USA obteve um resultado promissor, contudo, ainda muito abaixo
do resultado obtido pelo agente Mertacor, mas foi bem acima do resultado obtido pelos
outros agentes. Deve-se levar em conta que estes outros agentes são versões de demonstração disponíveis no servidor do TAC SCM e executam uma estratégia geral build to
order, ou seja, computadores são montados e entregues conforme pedidos de clientes.
De acordo com o gráfico mostrado na Figura 5 (a), o agente UAV2 obteve um
desempenho bem próximo do agente Mertacor. Não se pode concluir, com a quantidade
de simulações realizadas, que um agente supera o outro. Mas o resultado do agente UAV2
é superior ao resultado obtido pelo agente USA em condições de simulação semelhantes.
(a)
(b)
Figura 5. Competições envolvendo o agente UAV2. (a) Desempenho médio dos
agentes ao longo de oito jogos. (d) Desvio padrão do desempenho dos agentes
ao longo de oito jogos.
(a)
(b)
Figura 6. Competições envolvendo o agente UAV3. (a) Desempenho médio dos
agentes ao longo de oito jogos. (b) Desvio padrão do desempenho dos agentes
ao longo de oito jogos.
(a)
(b)
Figura 7. Competições envolvendo o agente UAV4. (a) Desempenho médio dos
agentes ao longo de oito jogos. (b) Desvio padrão do desempenho dos agentes
ao longo de oito jogos.
(a)
(b)
Figura 8. Competições envolvendo o agente UAV5. (a) Desempenho médio dos
agentes ao longo de oito jogos. (b) Desvio padrão do desempenho dos agentes
ao longo de oito jogos.
O gráfico da Figura 6 (a) mostra que o agente UAV3 obteve um desempenho
abaixo do agente Mertacor. Comparando-se o resultado de UAV3 contra o resultado
obtido pelos agente UAV2 e USA, pode-se perceber que o uso de redes neurais treinadas com dados de jogos passados foi pior do que a estimativa simples obtida pelo agente
UAV3 e não se pode confirmar que superou o resultado obtido pelo agente simples USA.
Os resultados apresentados na Figura 7 (a) mostram que as técnicas de redes neurais e retraining utilizadas pelo agente UAV4 são tão eficientes quanto à estratégia utilizada pelo agente UAV2.
Os resultados apresentados na Figura 8 (a) mostram que o desempenho do agente
UAV5 é aproximadamente igual ao desempenho dos agentes UAV2 e UAV4. Deve-se observar que todos os agentes que obtiveram resultado superior, utilizam em seus respectivos
modelos dados de jogo em andamento. Isso acontece essencialmente porque os modelos
gerados com dados do passado ou com base em suposições gerais ocasionalmente irão
falhar quando não forem compatíveis com um jogo em andamento. A Figura 9 captura
alguns momentos em que a predição feita pelo modelo de redes neurais falha durante uma
competição.
6. Conclusões
Este artigo investigou o uso de feedback do ambiente para a predição de preços no domínio do TAC SCM. Em particular, da perspectiva do vendedor, foi investigada a predição
Figura 9. Momentos em que a baixa venda de computadores faz com que a
fábrica trabalhe abaixo da capacidade máxima.
de lances vencedores em leilões reversos fechados de primeiro preço. Redes neurais artificiais e heurísticas elaboradas a partir da análise do problema foram aplicadas para
realização da predição. Algumas configurações para o uso de redes neurais e heurísticas foram tentadas com o objetivo de melhorar o desempenho de um agente que utilizou
inicialmente uma versão simples da estratégia de predição. Foram utilizadas oito simulações para se avaliar o desempenho das diferentes configurações. Os experimentos no
ambiente do TAC SCM mostraram que a heurística DPR é muito eficiente quando utilizada com a heurística simples ou com a rede neural e retraining. O uso de DPR com
rede neural e sem retraining mostrou aproximadamente o mesmo desempenho do agente
apenas com heurística simples. Um resultado interessante é que o retraining, mesmo que
utilizando poucos dados recentes de uma competição em andamento, é mais eficiente que
o uso apenas de redes neurais com dados de jogos passados (sem retraining). Isso mostra que modelos com dados recentes são muito mais eficientes do que modelos treinados
com dados de jogos passados, mesmo que haja muitos dados para treinamento em logs
de jogos passados e poucos dados recentes. Ainda de acordo com as simulações, o uso
de heurísticas a partir da observação do problema se mostrou tão eficiente quanto o uso
de rede neurais com retraining, pelos menos com a estratégia de retraining testada neste
trabalho.
O problema de prevê de forma acurada o preço de oferta de competidores no TAC
SM tem sido realizado por outros trabalhos. A principal contribuição deste trabalho é a
elaboração de uma heurística computacionalmente eficiente (DPR) e a investigação do
uso de retraining no domínio do TAC SCM. Mas especificamente, a descoberta de que
poucos dados de um jogo em andamento podem ser mais eficientes do que o uso de logs
de jogos passados para a elaboração de modelos de definição do preço de oferta. Também
foi mostrado como algumas informações disponíveis no ambiente podem ser utilizadas
para a predição de preços de oferta vencedores no dominio do TAC SCM, especialmente,
a partir de uma estratégia sistemática que resultou na elaboração da heurística DPR.
Uma questão que ainda fica em aberto é se há alguma estratégia de retraining mais
eficiente para o domínio em estudo. Portanto, é natural que o trabalho prossiga na investigação de estratégias de retraining mais eficientes e na instalação destas estratégias, que
sejam encontradas. É importante frisar que a melhor configuração do agente UECEUVA
obteve um desempenho bem próximo do agente Mertacor, mesmo não tendo incorporado estratégias que fazem uso do feedback do ambiente para no mercado de oferta de
componentes para montagem de computadores. Portanto, há também uma necessidade
do trabalho continuar explorando o uso de previsões no mercado de oferta (compra de
componentes de fornecedores) para tornar o agente UECEUVA mais eficiente.
Referências
[Chatzidimitriou et al. 2008] Chatzidimitriou, K. C., Symeonidis, A. L., Kontogounis, I.,
and Mitkas, P. A. (2008). Agent mertacor: A robust design for dealing with uncertainty
and variation in scm environments. Expert Systems with Applications, 35(3):591 – 603.
[Collins et al. 2006] Collins, J., Raghu Arunachalan, N. S., Eriksson, J., Finne, N., and
Janson, S. (2006). The supply chain management game for the 2007 trading agent competition. Technical report, School of Computer Science – Carnegie Mellon University,
Pittsburgh, PA.
[Dempsey et al. 2002] Dempsey, D. M., Butchart, K., and Hobson, P. W. (2002). Retraining trainable data classifiers.
[Fasli and Kovalchuk 2011] Fasli, M. and Kovalchuk, Y. (2011). Learning approaches
for developing successful seller strategies in dynamic supply chain management. Information Sciences.
[He et al. 2006] He, M., Rogers, A., Luo, X., and Jennings, N. R. (2006). Designing a
successful trading agent for supply chain management. In AAMAS ’06: Proceedings of
the fifth international joint conference on Autonomous agents and multiagent systems,
pages 1159–1166, New York, NY, USA. ACM.
[Pardoe and Stone 2005] Pardoe, D. and Stone, P. (2005). Bidding for customer orders in
TAC SCM. In Faratin, P. and Rodriguez-Aguilar, J., editors, Agent Mediated Electronic
Commerce VI: Theories for and Engineering of Distributed Mechanisms and Systems
(AMEC 2004), volume 3435 of Lecture Notes in Artificial Intelligence, pages 143–157.
Springer Verlag, Berlin.
[Pardoe and Stone 2009] Pardoe, D. and Stone, P. (2009). An autonomous agent for supply chain management. In Adomavicius, G. and Gupta, A., editors, Handbooks in
Information Systems Series: Business Computing, volume 3, pages 141–72. Emerald
Group.
[Sodomka et al. 2007] Sodomka, E., Collins, J., and Gini, M. (2007). Efficient statistical
methods for evaluating trading agent performance. In AAAI’07: Proceedings of the
22nd national conference on Artificial intelligence, pages 770–775. AAAI Press.
[Stan et al. 2006] Stan, M., Stan, B., and Florea, A. M. (2006). A dynamic strategy
agent for supply chain management. Symbolic and Numeric Algorithms for Scientific
Computing, International Symposium on, 0:227–232.