ISSN 2317-3297
Seleção de Serviços utilizando Algoritmos Genéticos
Marcelo Silva Santos,
E-mail: [email protected]
Thiago Evangelista,
E-mail: thi [email protected]
Álvaro Coêlho
E-mail: [email protected]
UESC - Departamento de Ciências Exatas e Tecnológicas
Campus Soanes Nazaré de Andrade
45662-900, ilhéus, BA
3 de setembro de 2012
Palavras-chave: Sistemas P2P, Algoritmos Genéticos, Otimização
Resumo: Em sistemas P2P multisserviço baseados em reciprocidade os nós precisam implementar
métodos heurı́sticos para fazer a seleção dos serviços que são oferecidos, buscando com isso maximizar
seu lucro. Este trabalho apresenta e avalia um método baseado em Algoritmos Genéticos e mostra que
seu desempenho supera em 32% os melhores resultados obtidos nas mesmas condições.
1
Introdução
Com a popularização das redes de computadores, que ganham cada vez mais velocidade e recursos, as
empresas e organizações podem conseguir externamente os recursos computacionais de que necessitam.
Nesse sentido, uma alternativa é a federação em redes P2P, onde os participantes desempenham ao
mesmo tempo o papel de cliente e servidor. Neste contexto, pode-se mediar a oferta e o consumo destes
recursos através de esquemas baseados em reciprocidade[1], de forma que os nós são incentivados a doar
recursos ociosos a outros nós, com a expectativa de receber destes os recursos de que necessitará no futuro.
Considerando um ambiente em que os recursos são trocados na forma de vários tipos diferentes de serviços,
os nós buscarão maximizar seu ganho empregando estratégias que selecionem o melhor conjunto possı́vel
de serviços para oferecer. Este problema, porém, é difı́cil computacionalmente devido à complexidade
do ambiente, o que torna impraticável desenvolver um seletor ótimo de serviços para problemas reais,
impondo aos nós a necessidade de implementar heurı́sticas [5].
Neste trabalho apresentamos uma heurı́stica de seleção de serviços baseada em algoritmos genéticos [7],
e avaliamos seu desempenho utilizando um modelo computacional para um ambiente P2P com múltiplos
serviços. Mostramos que esta heurı́stica superou a que havia obtido o melhor desempenho até então,
obtendo uma lucratividade média aproximadamente 32% maior.
2
Descrição do Problema
Redes peer-to-peer (P2P) são comunidades onde os compontenes, chamados nós, compartilham múltiplos
serviços, que podem ser tomados num nı́vel elementar, como a alocação de ciclos de CPU ou de capacidade
de armazenamento, bem como num nı́vel mais sofisticado, como a execução de um software em um ambiente particularmente configurado [6]. Para que a troca destes recursos aconteça satisfatoriamente, muitas
alternativas baseadas em modelos econômicos de mercado tem sido propostas [2] mas, alternativamente,
sistemas baseados em reciprocidade vem sendo apresentados como uma alternativa para o escalonamento
destes recursos [1]. Nestes ambientes, os serviços que cada nó consegue obter dos demais é resultado da
reciprocidade por serviços doados no passado, de forma que cada nó buscará oferecer serviços que sejam
consumidos por nós recı́procos em uma parceria mutuamente lucrativa. Ocorre, porém, que os custos
associados no provimento de cada serviço são especı́ficos, variando de nó para nó, e não se espera que
nenhum nó possa oferecer todos eles devido a limitações de orçamento. Desta forma posa-se o problema
de escolher um portifólio de serviços que, ao ser ofertado, maximize a relação entre o custo para ser
oferecido e a receita resultante da reciprocidade.
255
ISSN 2317-3297
Neste ambiente, as seleções realizadas por um nó p influenciam, pela reciprocidade, o comportamento
dos demais nós e, assim, determinam um cenário especı́fico, composto pela demanda dos outros nós,
mais seus respectivos portifólios. O número de possı́veis portifólios acessı́veis a cada um dos N nós
x X
x
do sistema é dada por
, sendo x o número máximo de serviços que podem ser selecionados.
k
k=0
Assim, a combinação total de possı́veis estados após cada seleção feita por cada um dos nós é dada por
" x #N
X x
, o que torna impraticável a seleção do melhor conjunto possı́vel de serviços, legando aos nós
k
k=0
a imperativa necessidade de abrir mão da solução ótima e implementar métodos heurı́sticos de seleção de
serviços.
Apesar de ser impraticável desenvolver um algoritmo ótimo, do ponto de vista metodológico é interessante tê-lo para que se proceda à avaliação das heurı́sticas de seleção. Por este motivo usamos, neste
trabalho, um modelo do problema real baseado numa variação do problema da mochila 0/1, possibilitando a avaliação de heurı́sticas de seleção comparadas a um algoritmo ótimo [3]. A estratégia é imergir
o agente que seleciona serviços num ambiente em que, sendo (cp,s,t ) o custo total em que o nó p incorre
ao oferecer o serviço s no instante t, e sendo (λp,s,t ) a receita futura obtida pelo nó p em função da oferta
do serviço s no instante t, se define o lucro do nó p ao oferecer um serviço s no instante t (πp,s,t ) como
πp,s,t = λp,s,t − cp,s,t . Assim, para cada item i da mochila, o seu valor (vi ) é dado pelo lucro πp,i,t do
i−ésimo serviço; o seu peso (wi ) é dado pelo custo cp,i,t do i−ésimo serviço; e o valor xi , que é 1 se
o item está na mochila ou 0 caso contrário, além do orçamento do nó p (Bp ) representar a capacidade
da mochila. O problema, então, é encontrar uma seleção de itens de forma que o valor da mochila seja
maximizado, da seguinte forma:
Maximize
tf
n
X
X
πp,j,t · xtj
t=to j=1
Pn
Sujeito a j=1 wj · xtj ≤ Bp considerando xtj . ∈ {0, 1}. Assim, o problema da seleção de serviços, em
que um nó faz sucessivas seleções de serviços ao longo do tempo, pode ser visto como a resolução sucessiva
de problemas da mochila, sendo que o agente conhece a capacidade da mochila e o peso dos itens, que
correspondem ao orçamento do nó e ao custo dos serviços, mas lhe é sonegado o valor do item, já que o
lucro do serviço é desconhecido. Finalmente, para que estes múltiplos problemas da mochila reflitam as
condições em um ambiente real, é necessário se estabelecer um mecanismo que permita se parametrizar
as mochilas em função das caracterı́sticas do ambiente. Isto é feito da seguinte maneira: num universo de
n serviços, considerando que um nó consome, em média F serviços, então a probabilidade de um serviço
qualquer não ser consumido por um nó especı́fico é dada por 1− Fn ). Assim, a probabilidade de um serviço
N
Y
F
não ser consumido por nenhum nó é dada por Ω =
(1 − ). Deste modo, a receita que o serviço s
n
i=1
retorna para o nó p como resultado de p ter oferecido s no instante t, é 0 com probabilidade Ω ou igual
a X ∼ N (α, σ) com probabilidade 1 − Ω, sendo α a média e σ é o desvio padrão da receita futura. Esta
distribuição normal é justificada pelo Teorema do Limite Central, já que a receita é dada pelo somatório
de serviços doados por diferentes nós. De posse destas variáveis, supondo que cp,s seja o custo do serviço
s para o nó p, sendo cp o custo médio, para o nó p, de todos os serviços, e sendo Bt o orçamento médio
por nó disponı́vel no turno t, a quantidade média de serviços diferentes oferecidos por um nó p qualquer
Bt
é dada por ( ). Dessa forma, considerando que p esteja oferecendo serviços no turno t, a quantidade
cp
esperada de nós que estão disputando pela doação de um serviço s qualquer contando com o próprio p, é
Bt
dada por χ = (pdon · (N − 1)) · nc̄ + 1, onde pdon é a probabilidade de um nó qualquer estar doando no
mesmo instante que p. Finalmente, considerando um ambiente de competição, a receita gerada por cada
serviço precisa ser dividida entre os nós que estão disputando com p, oferecendo o mesmo serviço. Assim,
λ
o lucro médio gerado pelo serviço s ao ser oferecido pelo nó p no turno t é dado por πp,s,t = p,s,t
χ − cp,s .,
o que permite mapear efetivamente a seleção de portifólio no problema da mochila 0/1.
3
Heurı́sticas de Seleção
Em ambientes baseados em reciprocidade, é possı́vel se ordenar os serviços pela ordem de receita
esperada ao se considerar o histórico dos nós que os consumiram: os serviços que foram consumidos
256
ISSN 2317-3297
pelos nós mais recı́procos são aqueles que geram mais receita. Com isso pode-se desenvolver heurı́sticas
que utilizam uma ordem esperada de receita dos serviços, já que sua receita não pode ser determinada.
Utilizando este conceito, Coêlho e Brasileiro desenvolveram a heurı́stica Smart-Restricted [4], que seleciona
os serviços conforme a ordem de receita esperada, buscando oferecer os serviços que se espera serem
mais lucrativos. A fim de encontrar um melhor compromisso entre o custo e a receita, esta heurı́stica
implementa um método de subida de colina, de forma que, a cada intervalo de tempo (k turnos) avalia-se
δπp,s,t
a lucratividade - derivada do lucro em função do tempo ( δt
) - e uma decisão é tomada: incrementar
ou decrementar a parte do orçamento disponı́vel que é efetivamente usada. Para isso adiciona-se ou
subtrai-se um passo. Caso a lucratividade seja positiva a decisão anterior é mantida e, caso contrário,
ela é invertida. Para evitar as situações de máximos locais, esta heurı́stica também implementa uma
estratégia de reinı́cio aleatório, de forma que a cada momento de avaliação, com probabilidade , a
decisão será escolher um valor aleatório de orçamento para ser utilizado e avaliado.
3.1
Heurı́stica Genetic-Based
Algoritmos genéticos constituem uma técnica de busca e otimização inspirada no princı́pio de seleção
natural [7]. A estratégia é privilegiar indivı́duos mais aptos dando-lhes maior probabilidade de reprodução.
Nesse trabalho, desenvolvemos a heurı́stica Genetic-Based que funciona da seguinte maneira: uma população inicial é constiuida pela geração aleatória de vários portifólios diversos, cada um deles descrito pelo
vetor I = hi1 , i2 , ...in i onde is é 1 se o serviço s está selecionado, ou 0 caso contrário. Esses portifólios são
submetidos a um processo de cruzamento, onde são selecionados pares aleatórios de portifólios segundo
uma probabilidade de cruzamento. O cruzamento entre os portifólios P 1 e P 2 gera dois novos portifólios:
um pela concatenação do prefixo de P 1 (os x primeiros itens do vetor I de P 1) com o sufixo de P 2 (os
n − x últimos itens do vetor I de P 2) e o outro pela concatenação do prefixo de P 2 com o sufixo de P 1. O
valor de X é definido aleatoriamente. Após esse processo é realizada a mutação. Este processo seleciona
aleatoriamente itens do vetor I, segundo uma probabilidade de mutação, e inverte seu valor.
Tanto a operação de cruzamento quanto a operação de mutação podem gerar portifólios inválidos,
que ultrapassem a capacidade da mochila (que representa o orçamento do nó). Estes portifólios são
descartados. Finalmente é realizada a operação de seleção utilizando o elitismo, de forma que, a cada
iteração apenas as F melhores mochilas sejam mantidas no processo. Este processo é repetido até que a
condição de parada seja satisfeita.
4
Resultados
Exploramos de que forma estas heurı́sticas se comportam quando selecionam serviços sob diferentes
condições de orçamento, que podem ser mais restritivos ou mais generosos. A heurı́stica Referential,
usada como algoritmo de referência, implementa um método de programação dinâmica para encontrar
a melhor solução possı́vel. No experimento as heurı́sticas foram implementadas em cenários diversos,
com orçamentos médios que variam em 3, 4, 5, 10, 15, 20, 25, 30, 35, 40, 45 e 50. Para cada valor de
orçamento gerou-se 1000 mochilas, que foram avaliadas pelas diferentes heurı́sticas. Note que, quanto
maior o orçamento, mais serviços cada nó poderá prover, o que aumenta a concorrência entre eles, já
que a chance de nós diferentes oferecerem o mesmo serviço é mais alta. Com isso, a receita desse serviço
acabará sendo rateada entre eles. Os resultados abaixo foram obtidos com 95% de confiança e erro
máximo de 0.15%. A heurı́stica Smart-Restricted, que foi comparada à heurı́stica Genetic-Based, foi
parametrizada como alcançou seu melhor desempenho em experimentos semelhantes [5]: a probabilidade
de geração de orçamento aleatório ( = 10%), passo de mudança do orçamento utilizado (step = 5), o
tempo de execução de uma seleção para verificação de sua lucratividade (k = 10). A heurı́stica Geneticbased foi parametrizada conforme sugerido na literatura: probabilidade de cruzamento (pcrossing = 70%),
probabilidade de mutação (pmutating = 0, 1%). Além disso, definimos uma população inicial de 10
indivı́duos e um total de 10 gerações.
A Figura 1 apresenta os resultados obtidos por cada heurı́stica, comparadas à melhor solução possı́vel
(Referential ). Os resultados da heurı́stica Smart-Restricted são sempre positivos, mas consistentemente
superados pela heurı́stica Genetic-based nos cenários onde o orçamento médio é mais alto, pois a quantidade de possı́veis combinações é muito grande, permitindo que o Genetic-Based encontre mais combinações de seleções. É importante observar que a lucratividade começa a cair quando o orçamento médio
aumenta, mesmo no caso do algoritmo de referência. Isto acontece porque, quanto maior é o orçamento
médio, maior a quantidade de serviços que são oferecidos pelos nós e maior a concorrência de nós oferecendo o mesmo serviço. Este fenômeno limita a lucratividade, e é referido por Adam Smith como a “mão
257
ISSN 2317-3297
invisı́vel”. Caso o orçamento médio se torne muito alto, então não haverá distinção de desempenho entre
o algoritmo de referência e as demais heurı́sticas. No limite, para orçamentos muito grandes (−→ ∞) a
concorrência seria tal que o lucro seria sempre negativo. Note que, dada a necessidade de gerar e implementar as populações de indivı́duos de cada geração, a heurı́stica Genetic-Based não consegue resultados
relevantes no inı́cio de seu processamento. Por este motivo ela sempre é parametrizada com valores baixos
de tamanho da população e número de gerações. Como a qualidade da solução final produzida é boa, é
razoável supor que esta heurı́stica seja mais adequada para ambientes em que as mudanças sejam menos
constantes, e assim a solução permaneça válida por mais tempo para compensar o custo inicial de a obter.
Figura 1: Lucro com diferentes orçamentos
5
Conclusões
Neste trabalho mostramos e avaliamos uma heurı́stica baseada em algoritmos genéticos para seleção
de serviços em ambientes P2P através de um modelo formal que permite avaliar métodos desta natureza.
O desempenho desta heurı́stica superou em aproximadamente 32% o melhor resultado até então. Este
desempenho destacado ocorre particularmente em cenários onde o orçamento médio é mais alto, já que
esta heurı́stica não restringe sua busca pela ordem esperada dos serviços.
Pelo fato de as heurı́sticas obterem diferentes lucratividades quando se varia aspectos distintos do ambiente, em trabalhos futuros poderemos explorar outros aspectos. Além disso, por se tratar de um ambiente cooperativo, pode ser interessante estudar a implementação distribuı́da e colaborativa da heurı́stica
Genetic-based, bem como de outras técnicas de otimização combinatória como espalhamento de partı́culas,
colônia de formigas, redes neurais e sistemas imunológicos naturais.
Referências
[1] N. Andrade, F. Brasileiro, W. Cirne, and M. Mowbray, “Automatic grid assembly by promoting
collaboration in peer-to-peer grids,” J. Parallel Distrib. Comput., vol. 67, no. 8, pp. 957–966, 2007.
[2] R. Buyya and S. Vazhkudai, “Compute power market: Towards a market-oriented grid,” The First
IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGrid 2001), 2000.
[3] A. Coêlho and F. Brasileiro, “On the evaluation of services selection algorithms in multi-services p2p
grids,” in Fourth IEEE International Workshop on Business-driven IT Management (BDIM’09).
Piscataway, NJ, USA: IEEE Press, 2009, pp. 52–60.
[4] A. Coêlho and F. Brasileiro, , “Smarter heuristics for business-driven services selection in multiservices p2p grids,” in The 7th IEEE 2010 International Conference on Services Computing (SCC
2010). IEEE Press, 2010, pp. 417–424.
[5] A. Coêlho, F. Brasileiro, and P. D. Maciel, “Using heuristics to improve service portfolio selection
in p2p grids,” in IM’09: Proceedings of the 11th IFIP/IEEE international conference on Symposium
on Integrated Network Management. Piscataway, NJ, USA: IEEE Press, 2009, pp. 438–444.
[6] A. Coêlho, P. D. Maciel Jr., F. d. Figueiredo, D. Candeia, and F. Brasileiro, “On the impact of
choice in multi-service p2p grids,” in Third IEEE International Workshop on Business-driven IT
Management (BDIM’08), Salvador, Bahia, Brazil, 2008, pp. 98–101.
[7] D. Goldberg, Genetic algorithms in search, optimization, and machine learning, ser. Artificial Intelligence. Addison-Wesley Pub. Co., 1989.
258