2.4 M ALAWI
2.4.3 Hib and Hep B in Malawi
Dada a definição da função objetivo do algoritmo, nesta subseção é descrito o seu funcionamento geral, segundo o fluxograma apresentado pela Figura 8.
Primeiramente, no passo inicializar, o algoritmo atribui cada componente a um módulo. Com esta configuração, o valor inicial da função é calculado, sendo o maior valor possível, já que nessa situação todas as dependências entre os componentes caracterizam dependências externas aos módulos.
Em seguida, o algoritmo seleciona um componente no passo escolher componente randomicamente e segue para o passo mover componente randomicamente, onde escolhe um módulo randomicamente e move o componente escolhido para ele, gerando uma nova solução de agrupamento. Então, no passo calcular CTC, o algoritmo calcula o valor da função para essa nova solução e verifica se esse valor foi reduzido em relação à solução anterior no passo o valor de CTC foi reduzido.
CAPÍTULO 5 – ABORDAGEM PARA RECOMENDAÇÃO DE MÓDULOS PARA PROJETOS DISTRIBUÍDOS DE LPS 59 início Fim Inicializar Escolher componente randomicamente Mover componente randomicamente Calcular CTC O valor de CTC foi reduzido? Aceitar solução Aceitar solução? O limite de estabilidade foi atingido?
Retornar melhor solução
SIM SIM NÃO NÃO NÃO SIM Atualizar solução de reinício
A solução atual é a melhor solução?
SIM NÃO Aceitar solução de reinício Atualizar melhor solução O limite de recomeços foi atingido? NÃO SIM O limite de iterações foi atingido? SIM Atualizar temperatura NÃO
Figura 8. Fluxograma do algoritmo baseado em SA.
Em geral, o deslocamento do componente para o módulo se torna permanente quando promove a redução do valor de . Quando isso acontece, o algoritmo salva a melhor solução encontrada até o momento, que é a solução corrente, no passo atualizar melhor solução e efetiva o deslocamento no passo aceitar solução. Contudo, para prevenir que o algoritmo fique preso a um ótimo local, é empregada a metaheurística Simulated Annealing, que faz o algoritmo explorar novas áreas no espaço de busca ao permitir que este aceite, com certa probabilidade, o deslocamento de um componente apesar de não ocorrer redução do valor de . A decisão de aceitar uma solução de custo superior é tomada no passo aceitar
CAPÍTULO 5 – ABORDAGEM PARA RECOMENDAÇÃO DE MÓDULOS PARA PROJETOS DISTRIBUÍDOS DE
LPS 60
solução e depende do cálculo da probabilidade de aceitação de uma solução de custo superior.
A probabilidade de aceitação de uma solução de custo superior é expressa pela equação de Metropolis, em analogia ao processo da termodinâmica no qual SA está baseado. Essa equação foi introduzida em [Metropolis et al. 1953] e simula a possibilidade da movimentação de átomos que apresentam ganho de energia ser realizada numa determinada temperatura, conforme descrito a seguir pela Equação (19). Nessa equação, é a probabilidade de movimentação do átomo, é a variação de energia causada por esta movimentação, é a constante de Boltzman (dependente do material) e é a temperatura do sistema.
(19)
A metaheurística SA para problemas de otimização foi introduzida por [Kirkpatrick et al. 1983] utilizando a equação de Metropolis com , resultando na Equação (20), e desde então vem sendo utilizada dessa forma com excelentes resultados. Na Equação (20), é um parâmetro de controle denominado temperatura e Δ consiste na diferença entre o custo total de comunicação da nova solução e da solução corrente, conforme especificado pela Equação (21).
(20)
(21)
O algoritmo gera um valor randômico no intervalo fechado . Se ,
a solução que não promove a redução do custo total de comunicação é aceita. Dessa forma, o algoritmo segue para o passo atualizar solução de reinício, no qual a solução atual, a última solução aceita antes da nova solução, é memorizada, e em seguida, o algoritmo prossegue para o passo aceitar solução, a partir do qual a nova solução passa a ser a solução atual, significando que novas soluções serão geradas a partir dela.
Ao longo da busca, a temperatura é resfriada de acordo com a Equação (22), que foi proposta por [Zolfaghari et al. 2002] e visa proporcionar um resfriamento mais rápido nas primeiras iterações e um resfriamento mais lento à medida que o número de iterações aumenta, minimizando buscas desnecessárias em temperaturas elevadas, quando a probabilidade de aceitação de uma solução de custo superior é elevada. Nessa equação, é a
CAPÍTULO 5 – ABORDAGEM PARA RECOMENDAÇÃO DE MÓDULOS PARA PROJETOS DISTRIBUÍDOS DE
LPS 61
iteração corrente, é a temperatura na iteração , - é a temperatura na iteração anterior e
é a temperatura inicial. O valor de é o valor inicial da função .
(22) Usando a mesma temperatura, o algoritmo repete o processo de gerar uma nova solução e decidir se esta deve ser aceita durante um número pré-definido de tentativas, especificado no parâmetro limite de iterações e avaliado no passo o limite de estabilidade foi atingido. A idéia de gerar várias soluções admitindo uma mesma temperatura é tentar alcançar a estabilidade da busca para a temperatura em questão. Dessa forma, esse valor deve ser elevado.
Após realizar todas as tentativas a uma mesma temperatura, no passo o limite de estabilidade foi atingido, o algoritmo checa se a busca atingiu a condição de estabilidade, especificada no parâmetro limite de estabilidade, que simplesmente é o número de vezes que a temperatura pode ser reduzida. Se o limite de estabilidade ainda não foi alcançado, o algoritmo atualiza a temperatura no passo atualizar temperatura, e procede para outro bloco de limite de iterações tentativas, como descrito anteriormente. Caso contrário, se o limite de estabilidade tiver sido alcançado, o algoritmo supõe que encontrou uma solução de agrupamento, e então, verifica se a solução atual é a melhor solução conhecida até o momento, tal como demonstrado pelo passo a solução atual é a melhor solução.
Se a solução atual é a melhor solução conhecida até o momento, a busca é finalizada e tal solução é retornada como indicado pelo passo retornar melhor solução. Caso contrário, a busca é reiniciada tomando como ponto de partida a solução de reinício, como indicado pelo passo aceitar solução de reinício. Observe que a solução de reinício é a solução anterior à última solução de custo superior que foi aceita pelo mecanismo de SA, e que foi previamente armazenada no passo atualizar solução de reinício, fazendo o algoritmo retroceder algumas soluções no espaço de busca e assim ter a chance de melhor explorá-lo.
Após recuperar a solução de reinício, no passo o limite de recomeços foi atingido, o algoritmo verifica se o número de reinícios foi alcançado, como denotado pelo parâmetro limite de recomeços. Se tal limite ainda não tiver sido alcançado, o algoritmo atualiza a temperatura no passo atualizar temperatura, e procede para outro bloco de limite de iterações tentativas, como já foi explicado. Caso contrário, a busca é finalizada e a melhor solução
CAPÍTULO 5 – ABORDAGEM PARA RECOMENDAÇÃO DE MÓDULOS PARA PROJETOS DISTRIBUÍDOS DE
LPS 62
encontrada é retornada. Os valores iniciais de limite de iterações, limite de estabilidade e limite de recomeços são definidos como parâmetros de entrada.
No caso de existir módulos previamente definidos, situação que ocorre quando um projeto é desenvolvido em múltiplas iterações, após a primeira iteração deve ser aplicada uma variação do algoritmo descrito, que recebe como entrada a DSM que contém todos os componentes, incluindo os que já foram agrupados em módulos, e a CMM que especifica tais módulos. A versão alternativa do algoritmo não permite que componentes previamente agrupados sejam movidos para outros módulos, embora permita que sejam introduzidos novos componentes em tais módulos. Nesse sentido, no passo escolher componente randomicamente, somente componentes que não foram previamente agrupados se tornam aptos para serem escolhidos.
Componentes em módulos previamente definidos já foram implementados. Dessa forma, movê-los para outro módulo causa a perda de informação sobre a equipe que os desenvolveram, informação esta que pode ser útil para fins de alocação. Quando novos componentes são introduzidos em módulos previamente definidos, a dependência deles com os componentes no módulo denota que a equipe que desenvolveu o módulo está apta para implementar esses novos componentes. E caso essa mesma equipe não esteja mais disponível e seja alocada uma nova equipe para o módulo reconfigurado, ao menos é possível prever a necessidade de comunicação que (provavelmente) existirá entre a equipe anterior e a nova equipe, o que irá influenciar na escolha da nova equipe.