Aplicação do Algoritmo GRASP Reativo para o Problema do Próximo Release

IntroducaoFundamentacao teorica

MetodologiaResultados

Conclusao e Trabalhos Futuros

Aplicacao do algoritmo GRASP Reativo para oProblema do Proximo Release

Gabriela Rosa Machado Linhares

Curso de Ciencia da ComputacaoUniversidade Estadual do Ceara - UECE

19 de maio de 2010

Gabi Linhares GRASP no PPR




Topicos

Introducao

Fundamentacao teorica

Metodologia

Resultados






SBSEProblema do Proximo ReleaseMotivacaoObjetivos e ContribuicoesTrabalhos Relacionados

Topicos

IntroducaoSBSEProblema do Proximo ReleaseMotivacaoObjetivos e ContribuicoesTrabalhos Relacionados


Metodologia

Resultados

Conclusao e Trabalhos FuturosGabi Linhares GRASP no PPR





SBSE

I Search-Based Software Engineering

I Inıcio da decada de 70 - primeiros artigos na area; nos ultimos10 anos teve um crescimento bastante acentuado.

I Areas:I Geracao de dados de testeI Selecao de casos de testeI Estimativa de custoI PlanejamentoI Selecao de RequisitosI ...

I Ingredientes:I Escolha da representacaoI Definicao da funcao objetivo






SBSE










SBSE










SBSE










Problema do Proximo Release

I O que e Release?I Liberacao de versao oficial de um software, para homologacao

ou producao.

I NRP:I Selecionar clientes cuja satisfacao seja 100% e a restricao de

custo seja obedecida.






Problema do Proximo Release

I O que e Release?I Liberacao de versao oficial de um software, para homologacao

ou producao.I NRP:

I Selecionar clientes cuja satisfacao seja 100% e a restricao decusto seja obedecida.






Problema do Proximo Release - Cont...

I Abordagens:I Selecao de Clientes (2001)I Selecao de Requisitos (2007)

I Por que nao otimizar com um metodo exato?I Programacao Linear mostrou-se ineficiente para instancias com

valores muito altos.






Problema do Proximo Release - Cont...

I Abordagens:I Selecao de Clientes (2001)I Selecao de Requisitos (2007)

I Por que nao otimizar com um metodo exato?I Programacao Linear mostrou-se ineficiente para instancias com

valores muito altos.






Motivacao

I Porque estudar este problema?I Satisfacao completa do cliente quanto aos requisitos de

software;I Dependendo dos tipos de NRP, pode ser NP-Completo ou

NP-Difıcil;I Algumas metaheurısticas nao foram testadas neste problema.

EX:I GRASP Reativo






Objetivos e Contribuicoes

I Utilizar GRASP Reativo no NRP

I Comparar com outras metaheurısticas

I Novo metodo para geracao de solucoes
























Trabalhos Relacionados

I The Next Release Problem - Bagnall e Smith (Informationand Software Technology - 2001);

I EasyMeta - Rafael Carmo (TCC - 2008)

I Release Planning - Felipe Colares (SBPO - 2009)

I STNSNP - Steiner Two-Node-Survivable Network Problem:em uma rede de fibras oticas - Rubino (International Journalos Logistics Systems and Management - 2010)

I Automated Test Case Prioritization with Reactive Grasp -Camila Maia (2010)

















































Modelagem do NRPAlgoritmos

Topicos

Introducao

Fundamentacao teoricaModelagem do NRPAlgoritmos

Metodologia

Resultados







Modelagem do NRP

I Matematicamente, um exemplo de configuracao do NRP:I R = {r1, r2, r3, r4, r5, r6, r7}I c1 = 10, c2 = 6, c3 = 7, c4 = 1, c5 = 4, c6 = 6, c7 = 1I R1 = {r6},R2 = {r6, r7},R3 = {r5}I E ={(1, 3), (1, 4), (1, 6), (1, 7), (2, 5), (2, 7), (3, 6), (4, 7), (5, 7)}

I R1 = {r1, r3, r6}, R2 = {r1, r3, r4, r6, r7}, R3 = {r2, r5}I w1 = 50,w2 = 60,w3 = 70






Modelagem do NRP - cont...

I Maximizar o custo total de clientes selecionados ouEvaluate, sujeito a restricoes de custo, B ≤ b, onde b ∈ {30%, 50%, 70% do custo total de requisitos existentes.}

I Considerar entre os requisitos:I Independencia (E = 0): NP-Difıcil;I Interdependencia: aplicacao de heurısticas para encontrar

solucoes de boa qualidade, em tempo habil.






Algoritmos

I Aplicados no NRP original:I Inicia com conjunto vazio de clientes satisfeitos;I Adicao de cada cliente ao conjunto, sem ultrapassar o

percentual estabelecido de custos de requisitos.I Metricas de selecao:

I Maximum Profit: cliente com maior lucro;I Minimum Cost: exigencia mınima de requisitos;I Maximum Ratio: ordena o cliente por razao entre lucros

custos.

I Melhorou os resultados em qualidade, adaptando MaximumRatio com Grasp: escolher K clientes no topo da lista decandidatos.






Tempera Simulada

I Analogia ao processo metalurgico de recozimento ouannealing ;

I Vantagem: Fuga de otimos locais, pois aumenta o universo desolucoes, testando solucoes piores que a atual.

I Metodo: Aquecimento brusco → Fusao do Metal →Resfriamento Lento → Equilıbrio.

I f (Energia) < 0: solucao atual melhor que a anterior;I f (Energia) = 0: nao houve variacao de energia;I f (Energia) > 0: solucao atual tem pior custo com a anterior.

I Fator de Boltzzman: p = e − f (Energia)T

, regula a probabilidadede solucoes com pior custo;

I Gera um numero aleatorio entre [0,1];I Se esse numero e menor ou igual a p, a solucao e aceita;I Caso contrario, solucao e rejeitada.






Algoritmo Genetico

I Classe particular de algoritmos evolutivos: hereditariedade,mutacao, selecao natural e crossing over ;

I A cada geracao, uma populacao e avaliada de forma aselecionar indivıduos adaptados a proxima geracao.

I Vantagem: Metodo flexıvel, de facil hibridizacao com outrastecnicas e baseia-se no conjunto de solucoes possıveis e naonos parametros de otimizacao;






GRASP

I Baseia-se em construcao e busca local:I RCL - Restricted Candidate List

I e ∈ RCL se c(e) ∈ [cmin, cmin + α(cmax − cmin)];I α = 0: puramente guloso;I α = 1: puramente aleatorio;






GRASP Reativo

I Especializacao de Grasp: valores de α dependem diretamentedas solucoes anteriores;

I A = {a1, a2, a3, · · · , am};I pi = 1

m , iguais para todos os candidatos;

I Reavaliacao das probabilidades: pi = qi∑mj=i qj

e qi = s∗Mi

. EX.:

I Problema de minimizacao: escolheu αj ;I Solucao encontrada: otimo local;I Mj diminui, logo pj e qj tambem diminuem;I Valor de α e diretamente proporcional a qualidade das solucoes

obtidas atraves dele.

I Vantagem: maior robustez por conta da menor dependenciade acertos na escolha de α;





Dados AleatoriosParametrizacao das metaheurısticas

Topicos

Introducao


MetodologiaDados AleatoriosParametrizacao das metaheurısticas

Resultados







Dados Aleatorios

I Tres instancias (M1, M2, M3);I M1: 10C, 20R, 30%B;I M2: 20C, 40R, 50%B;I M3: 30C, 60R, 70%B;

I Densidade de ligacoes: 0.05, 0.03 e 0.03;

R1

R12

C3

R18

C2C8

R4

R9 C1

R6

R8 R11

C5 C10

R10

R15

C7

R17

R20

R19

C9

R7 R3

C4

R14 R16

C6

R2






Parametrizacao das metaheurısticas

I Algoritmo Genetico: No de iteracoes = 35; Populacao = 20;% de Mutacao = 20%;

I Tempera Simulada: Taxa de Decrescimento da Temperatura= 0.95; Criterio de Parada = temperatura menor que 0.0005;

I Grasp: No Maximo de Iteracoes = 50; Alpha = 0.3;

I Grasp Reativo: No Maximo de Iteracoes = 60; Qtde. deAlpha = 9; Valores de Alpha = 0.1 a 0.9;





Topicos

Introducao


Metodologia

Resultados






Resultados

I Flutuacao de apenas 5% no tempo de execucao.

I Grasp Reativo mostrou-se melhor que todas as outrasmetaheurısticas, em ambiente de testes;

I Bom resultado de GReativo pode ser estendido a um cenarioreal, onde este tambem e a melhor escolha;

I Os Tipos de instancias abordadas no trabalho sao maisabrangentes do que no artigo de Bagnall, pois nao halimitacao multi-nıvel.





Resultados - Cont...

I Evaluates encontrados com custo limitado a 30%:

















Topicos

Introducao


Metodologia

Resultados







I Objetivo atingido: Grasp Reativo e uma boa estrategia desolucao para problemas de otimizacao na engenharia derequisitos;

I Trabalho futuro 1: analisar media e desvio-padrao de tempode execucao, considerando instancias mais complexas;

I Trabalho futuro 2: Aplicar outras metaherısticas: ScatterSearch, Tabu Search, VNS, BLS, ILS;

I Trabalho futuro 3: Estudar a versao mono-objetiva do NRP,aplicando outras metaheurısticas e o conceito de Frente dePareto;





FIM


Documents

Aplicação do Algoritmo GRASP Reativo para o Problema do Próximo Release