GOES.UECE - SOES Especial Minicurso SBES 2009

Metaheurísticas Aplicadas a Problemas Complexos da Engenharia de Software

GOES.UECE - Grupo de Otimização em Engenharia de Software

Universidade Estadual do Ceará

Dr. Jerffeson Teixeira de Souza

XXIV Simpósio Brasileiro de Banco de Dados XXIII Simpósio Brasileiro de Engenharia de Software

Fortaleza, 05 a 09 de Outubro de 2009

Jerffeson Teixeira de SouzaUniversidade Estadual do Ceará Professor Adjunto

http://goes.comp.uece.br/prof.jerff@gmail.com

Prazer em conhecer,

Nosso tempo estádividido desta forma

Parte 01 Otimização em Engenharia de SoftwareParte 02 Introdução a Metaheurísticas Parte 03 Aplicação de Metaheurísticas em

Engenharia de Software Parte 04 Considerações Finais Parte 05 Discussões (se o tempo permitir)

Metaheurísticas Aplicadas a Problemas Complexos da Engenharia de SoftwarePARTE 01 – OTIMIZAÇÃO EM ENGENHARIA DE SOFTWARE

XXIV Simpósio Brasileiro de Banco de Dados XXIII Simpósio Brasileiro de Engenharia de Software

Fortaleza, 05 a 09 de Outubro de 2009

Espere um minuto.

Antes, vamos definir ...

Otimização

Engenharia de Software

Engenharia de Software

Disciplina da engenhariaque se ocupa de todos osaspectos da produção de software, desde os estágiosiniciais de especificação atéa manutenção desse

sistema.

Sommerville

“

”

Otimização

βελτιστοποίησης

Otimização “Otimização consiste em encontrar uma ou mais soluções válidas para um determinado problema que correspondem a valores extremos (ou ótimos) de uma ou mais funções que valoram tais soluções.”

Tipos de Otimização

Mono-objetiva

Uma única função a ser otimizada

Possui uma Ordenação Total

Busca uma única solução (ótima)

Multi-objetiva

Duas ou mais funções a serem otimizadas

Possui uma Ordenação Parcial

Busca um conjunto de soluções

Ordenação Parcial

f(x) f(y) ou f(x) f(y), para todo x e y

Ordenação Total

f(x) f(y), f(x) f(y) ou (f(x) f(y) e f(x) f(y)) para algum x e y

/ /

Na Otimização multi-objetiva, o conceito de Dominância substitui o conceito “melhor-pior-igual”

Dominância“Uma solução S1 domina uma solução S2 se S1 é melhor ou igual a S2 em todos os critérios, e estritamente melhor em pelo menos um deles”

EXEMPLO ILUSTRATIVO

ProblemaEscolher um voo entre São Paulo e Fortaleza, minimizando

o custo, que deve ser no máximo de R$ 800,00, e que possua o menor tempo de voo possível.

Tempo de Voo(horas)

2 1 2 3,5 4 6 7 8

Custo (R$) 300,00 700,00 900,00 650,00 400,00 100,00 300,00 600,00

Voos Disponíveis

EXEMPLO ILUSTRATIVO

ProblemaEscolher um voo entre São Paulo e Fortaleza, minimizando

o custo, que deve ser no máximo de R$ 800,00, e que possua o menor tempo de voo possível.

Tempo de Voo(horas)

2 1 2 3,5 4 6 7 8

Custo (R$) 300,00 700,00 900,00 650,00 400,00 100,00 300,00 600,00

Voos Disponíveis

EXEMPLO ILUSTRATIVO

ProblemaEscolher um voo entre São Paulo e Fortaleza, minimizando

o custo, que deve ser no máximo de R$ 800,00, e que possua o menor tempo de voo possível.

Solução Inválida

0,00

100,00

200,00

300,00

400,00

500,00

600,00

700,00

800,00

900,00

1.000,00

0 1 2 3 4 5 6 7 8 9 10

custo() (R$)

tempo_de_voo() (horas)

Objetivo: Minimizar tempo_de_voo() e custo()

S2

S1

S1 domina S2

0,00

100,00

200,00

300,00

400,00

500,00

600,00

700,00

800,00

900,00

1.000,00

0 1 2 3 4 5 6 7 8 9 10

custo() (R$)

tempo_de_voo() (horas)

Objetivo: Minimizar tempo_de_voo() e custo()

S2

S1

S1 não domina S2 eS2 não domina S1

0,00

100,00

200,00

300,00

400,00

500,00

600,00

700,00

800,00

900,00

1.000,00

0 1 2 3 4 5 6 7 8 9 10

custo() (R$)

tempo_de_voo() (horas)

Objetivo: Minimizar tempo_de_voo() e custo()

Melhor

Indiferente

Indiferente

Pior

0,00

100,00

200,00

300,00

400,00

500,00

600,00

700,00

800,00

900,00

1.000,00

0 1 2 3 4 5 6 7 8 9 10

custo() (R$)

tempo_de_voo() (horas)

Objetivo: Minimizar tempo_de_voo() e custo()

Soluções Dominadas

Soluções Não Dominadas

Frente de Pareto

Formulação de Um Problema da Otimização

minimizar (x) fm

0

0

)()( Uii

Li

k

j

xxx

(x)h

(x)g

Funções a Minimizar/Maximizar

ni

Kk

Jj

Mm

,...,1

,...,1

,...,1

,...,1

:a sujeito

Definem as Soluções Válidas

Restrições

Métodos à posterioriDecisor explicita suas preferências após o processo de busca

1 Métodos à prioriDecisor explicita suas preferências antes do processo de busca

2

Métodos InterativosDecisor explicida suas preferências durante o proceso de busca, guiando o processo iterativamente

3

Resolvendo Problemas Multi-objetivos

1 Métodos à Priori

Atribui-se um peso a cada objetivo, explicitando as preferências do decisor, assim técnicas de otimização mono-objetivo podem ser utilizadas diretamente.

n

i

i

n

i

ii wxfwxf11

1 )()(

Técnicas de Resolução: Métodos Exatos, Métodos Aproximativos, Heurísticas, Metaheurísticas Mono-objetivas.

2 Métodos à Posteriori

Selecionam um conjunto de soluções não dominadas, que deverão ser analisadas posteriormente pelo decisor.

Técnicas de Resolução: Metaheurísticas Multi-objetivas.

Otimização

Engenharia de Software

Otimização em Engenharia de Software

Por que, quando e como aplicar.

?Recapitulando...

Otimização em Engenharia de Software

Novo ramo da Engenharia de Software dedicado a resolução

automática de problemas complexos dessa área, modelados

como problemas de otimização

Otimização em Engenharia de Software

=Search-based Software

Engineering (SBSE)

óri

Otimização em Engenharia de SoftwarePor que ?

Sistemas cada vez mais complexosAbordagens automáticas se tornam cada vez mais necessárias.

EscalabilidadeSoluções convencionais sofrem com problemas de escalabilidade em grandes projetos. SBSE é escalável, dado o aumento no poder de processamento.

IndependênciaResultados são gerados a partir de análises ausentes de qualquer vício ou pré-conceitos.

Por que ?

óri

Otimização em Engenharia de SoftwareQuando ?

Problemas Complexos

1: Grande Espaço de Busca

2: Ausência de Solução Ótima Conhecida

Quando ?

óri

Otimização em Engenharia de SoftwareComo ?

Aplicando Otimização em Engenharia de Software

Escolha de uma Representação para as soluções do problema

Definição da Função(ões) de Avaliação e das Restrições do problema

Escolha e Aplicação de Algoritmos de Busca

Exemplos de Problemas Complexos em Engenharia de Software

Estimativa de Custos

Alocação de Pessoal

Planejamento de Releases

Exemplos de Problemas Complexos em Engenharia de Software

Otimização de Projeto

Otimização de Código Fonte

Geração, Seleção e Priorização de Casos de Teste

Um Pouco de

História

até 2001Diversos trabalhos esparsos, especialmenteem teste de software, tratam problemas de Engenharia de Software como problemas de busca.

2001Mark Harman e Bryan Jones introduzem o termo Search-based Software Engineering em um artigo de mesmo nome.

2008Chamada para Edição Especial do periódico IEEE Transactions on Software Engineering em Search-Based Optimization for Software Engineering.

Maio de 20091st International Symposium on Search Based Software Engineering, na cidade de Windsor, UK

2007Mark Harman publica o artigo “The Current State and Future of Search Based Software Engineering”.

Agosto de 2009Chamada para Edição Especial do periódico Software—Practiceand Experience em Practical Aspects of Search-Based Software Engineering

Metaheurísticas Aplicadas a Problemas Complexos da Engenharia de Software

PARTE 02 - INTRODUÇÃO A METAHEURÍSTICAS

XXIV Simpósio Brasileiro de Banco de Dados XXIII Simpósio Brasileiro de Engenharia de Software

Fortaleza, 05 a 09 de Outubro de 2009

MetaheurísticaCombinação de duas palavras gregas: heuriskein, quesignifica “encontrar”, e o sufixo meta significando“além, em um nível mais alto”.

Refere-se a uma estratégia inteligente de alto nível que guia um processo de busca, explorando eficientemente um espaço de soluções a procura de soluções ótimas ou sub-ótimas.

Discutiremos as seguintes Metaheurísticas

Mono-objetivas Algoritmos GenéticosTêmpera SimuladaGRASP

Multi-objetiva NSGA II

Algoritmos Genéticos

Introdução

Método de busca inspirado na Teoria da

Evolução Natural de Charles Darwin

Introduzido por John Holland (1975) e

popularizado por um dos seus alunos, David

Goldberg (1989).

Charles Darwin (1809 – 1882)

•Naturalista Britânico

•1859 – Livro “A Origem das Espécies”

•Conceitos Fundamentais

•Evolução é natural

•Seleção Natural

•Sobrevivências dos mais adaptados

•Propagação genética

•Mutação

procedimento ALGORITMO_GENÉTICO()

cria_população_inicial(P);

repita

P’ ← avaliação_da_população(P);

P’’ ← seleção_dos_pais (P);

P’ ← recombinação_dos_pais(P’’);

mutação(P’’);

P ← P’’;

enquanto condições de parada não for atingida

fim ALGORITMO_GENÉTICO

Pseudocódigo do Algoritmo

Genético

Representação Genética

Um AG processa populações de cromossomos.

Um cromossomo é uma estrutura de dados, geralmente vetor ou cadeia de bits (cadeia de bits é a estrutura mais tradicional, porém nem sempre a melhor), que representa uma possível solução do problema a ser otimizado.

O primeiro passo para resolver um problema utilizando AGs é representar uma possível solução deste problema na forma de um cromossomo.

População Inicial

Um Algoritmo Genético começa com uma população inicial de N cromossomos.

Essa população pode ser gerada de forma aleatória ou a partir de conhecimentos prévios do problema.

O tamanho da população inicial deve ser determinado de acordo com cada problema.

Seleção

Inspirado no processo de seleção natural de seres vivos.

O AG seleciona os melhores cromossomos (aqueles de alta aptidão) com maior probabilidade para gerar cromossomos filhos (que são variantes dos pais) através dos operadores de cruzamento e mutação.

Métodos de Seleção

• Seleciona um cromossomo com probabilidade proporcional a sua aptidão.

Método da Roleta

• Seleciona um cromossomo a partir de competições, normalmente envolvendo dois cromossomos.

Método de Torneio

Cruzamento (ou Crossover)

Processo de combinação de dois cromossomos para a geração de dois filhos.

Garante a propagação de material genético.

Respeita uma Taxa de Cruzamento (entre 60 e 90%) determinada a priori.

Métodos de Cruzamento

• Realiza um corte único de cada cromossomo e combina os materiais genéticos divididos.

Cruzamento de 1 ponto

• Realize dois cortes, e similarmente combina os materiais genéticos divididos.

Cruzamento de 2 pontos

Mutação

Processo de alteração genética aleatório.

Permite a adição de material genético inédito.

Respeita uma Taxa de Mutação (até 5%) determinada a priori.

Calibragem dos Parâmetros

Tamanho da População

Número de Populações

Taxa de Reprodução

Taxa de Mutação

Critério de Parada

• Número de Gerações• Qualidade da Solução • Ausência de Evolução• Tempo

Alternativas

Têmpera Simulada

Introdução

Simulação do processo de tratamento térmico

de têmpera de um sólido.

Aplicação a problemas de otimização, em que a

pesquisa pelo mínimo de uma função objetivo

corresponderá a procurar o valor mínimo de

energia na matéria solidificada após

tratamento térmico de têmpera.

Têmpera RealX

Têmpera Simulada

Soluções viáveis

Qualidade de uma solução

Transição para uma solução vizinha

Parâmetro de controle

Número de iterações

Solução ótima global

Microestados

Energia de um Microestado

Perturbação de um Microestado

Temperatura

Tempo de arrefecimento

Microestado de energia mínima

procedimento TEMPERA_SIMULADA()

s ← GerarSoluçãoInicial()

T ← T0enquanto condições de parada não for atingida faça

s’ ← EscolherRandomicamente(N(s))

se (f(s ) < f(s)) então

s ← s

senão

Aceita s’ com probabilidade e -(f(s ) - f(s))/T

fim se

Atualiza(T)

fim enquanto

fim TEMPERA_SIMULADACritério de Metrópolis

Análise do Critério de Metrópolis

e -(f(s ) - f(s))/T

Quanto maior f(s ) - f(s), menor a probabilidade de aceitação

Quanto maior T, maior a probabilidade de aceitação

Calibragem dos Parâmetros

Temperatura Inicial

Taxa de Resfriamento

Critério de Parada

• Congelamento Número de iterações sem melhora• Número de iterações (soluções visitadas)• Qualidade da Solução• Tempo

Alternativas

GRASP

Introdução

Proposto por Feo e Resende (1995)

Possui duas fases1. Construcão

Encontra uma solução viável utilizando método

semiguloso (utiliza fator aleatório)

2. Busca Local

Procura o mínimo local a partir da solução obtida

na fase Construção

procedimento GRASP()

enquanto condições de parada não for atingida faça

s ConstruirSolucaoGulosaRandomica()

BuscaLocal(s)

GuardarMelhorSolucaoEncontrada()

fim enquanto

fim GRASP

Melhor Solução

...

...

...

...

...

......

Fase de Construção

Fase de Busca Local

procedimento GRASP()

enquanto condições de parada não for atingida faça

s ConstruirSolucaoGulosaRandomica()

BuscaLocal(s)

GuardarMelhorSolucaoEncontrada()

fim enquanto

fim GRASP

Fase de Construção

Inicia com lista de candidatos válidos

Reduz essa lista para uma Lista Restrita de Candidatos (RLC)

Escolhe aleatoriamente um elemento na RLC

Como ??

procedimento ConstruirSolucaoGulosaRandomica()

Solução

Inicializar o conjunto dos candidatos C E

Avaliar os custos incrementais dos elementos candidatos

enquanto Solução não estiver completa faça

cmin min{c(e)|e C}

cmax max{c(e)|e C}

LRC {e C|c(e) cmin + (cmax – cmin)}

Selecionar um elemento s LRC randomicamente

Solução Solução {s}

Atualizar C

Reavaliar os custos incrementais dos candidatos

fim enquanto

retorne Solução

fim ConstruirSolucaoGulosaRandomica

Fase de Construção do GRASP

Análise da LRC

LRC {e C|c(e) cmin + (cmax – cmin)}

varia de 0 a 1

Quando = 1, LRC = C

Quando = 0, LRC = {e C|c(e) cmin}

Fase de Busca Local

Retorna melhor solução da vizinhança

GRASP Reativo

Ajuste dinâmico do valor de de acordo com as soluções encontradas

Conjunto de valores possíveis de

Probabilidade inicial de escolha de cada é igual a 1/ n, onde n é o número de valores possíveis de

NSGA-II

Introdução

AG multi-objetivo desenvolvido em Deb et al. (2000)

Utiliza dois algoritmos de ordenação1. Non-dominated Sorting Algorithm

Busca por soluções próximas a Frente de Pareto

2. Crowding Distance Sorting

Busca por soluções bem distribuídas no espaço

Rejeitado

Non-Dominated Sorting

Crowding Distance Sorting

pop

filhos

pop

F1F2

F3

Non-dominated Sorting

Para cada solução calcula-se quantas outras soluções a dominam e quais soluções são dominadas por ela

Faz-se um ciclo no qual a cada iteração são retiradas as soluções que não são dominadas e diminui-se o contador das soluções dominadas por estas que foramretiradas

A cada ciclo, uma nova frente é criada com as soluçõesretiradas do conjunto

Crowding Distance Sorting

Utiliza uma função de cálculo de distância entre soluções que estejam no mesmo front para garantir um melhor fitness àquelas que estejam em áreas menospovoadas no espaço de busca.

Para cada função objetivo as soluções com valoresextremos são classificadas como tendo distância infinita.

As outras soluções tem sua distância recalculada de acordo com uma fórmula normalizada que utiliza a diferença de valores para esta solução e as duas maispróximas a ela.

Metaheurísticas Aplicadas a Problemas Complexos da Engenharia de SoftwarePARTE 03 - APLICAÇÃO DE METAHEURÍSTICAS

EM ENGENHARIA DE SOFTWARE

XXIV Simpósio Brasileiro de Banco de Dados XXIII Simpósio Brasileiro de Engenharia de Software

Fortaleza, 05 a 09 de Outubro de 2009

Roteiro de Aplicações

Engenharia de Requisitos

Problema do Próximo Release (Mono-objetivo)

Problema do Próximo Release (Multi-objetivo)

Planejamento de Releases

Roteiro de Aplicações

Teste de Software

Alocação de Pessoal

Priorização de Casos de Teste

ATENÇÃO

Notações e formulação serão respeitadas integralmente

!

Problema do Próximo Releases (Mono-Objetivo)

Fonte: Bagnall, A., Rayward-Smith, V., e Whittley, I. The Next Release Problem. Information andSoftware Technology, 43:883-890(8), 2001.

Empresas desenvolvedoras de sistemascomplexos para vários clientes precisam

determinar quais requisitos serãoincluidos no próximo release.

Demanda de vários clientes por requisitosindividuais

Requisitos possuem pré-requisitos

Clientes tem importâncias diferentes

Requisitos possuem custo

Problema do Próximo Releases (Mono-Objetivo)

Problema

Selecionar um conjunto de requisitos que possam ser implementados dentro de um orçamento restrito e quesatisfaçam as demandas de clientes importantes

Formulação

Problema do Próximo Releases (Mono-Objetivo)

R é o conjunto de requisitos

Cada cliente, i, possui um conjunto de requisitos, Ri R, e um peso, wi, o qualindica a importância desse clientes para a empresa

Associado com o conjunto R está um grafo G = (R,E), direcionado e acíclico, onde

(r,r´) E sss r é um pré-requisito de r´

Se a empresa decide satisfazer os requisitos do cliente i, ela deve tambémdesenvolver não somente Ri, mas também, parents(Ri), onde

parents(Ri) = {r R | (r,r´) E , r´ Ri}

Formulação

Problema do Próximo Releases (Mono-Objetivo)

R*i = Ri parents(Ri ) contêm todos os requisitos que devem ser implementados para satisfazer o cliente i.

Cada r possui um custo associado, cost(r) Z+

Para um subconjunto de requisitos R´, temos que cost (R´) = ({cost(r)|r R´}

Assumindo que a empresa tem n clientes, a tarefa é encontrar um subconjuntode clientes, S {1,2,3,…,n}, cujo requisitos serão satisfeitos

Problema do Próximo Releases (Mono-Objetivo)

Si

iwMaximizar

BRcostSi

i * a sujeito

Maximização da Importância

Restrição de Custo

Problema do Próximo Releases (Mono-Objetivo)

Foram avaliados vários algoritmos (Método Exato, GRASP, Busca Local, Subidaem Encosta e Têmpera Simulada) sobre problemas gerados aleatoriamentecontendo entre 100 clientes e 140 tarefas e 500 clientes e 3250 tarefas.

No menor dos problemas, o Método Exato se mostrou satisfatório. Enquanto nos outros, a Têmpera Simulada encontrou as melhores soluções com baixo custo computacional, obtendo em médio resultados somente 1.5% piores que os ótimos conhecidos.

Resultados

Problema do Próximo Releases

(Multi-Objetivo)

Fonte: Zhang, Y., Harman, M., e Mansouri, S. A. The multi-objective next release problem. Anais

do IX Annual Conference on Genetic and Evolutionary Computation. 2007.

Extensão da formulação anterior

Considera o custo como objetivo, e não como restrição

Problema do Próximo Releases (Multi-Objetivo)

Problema

Selecionar um conjunto de requisitos que possammaximizar o valor total e minimizar o custo requerido.

Formulação

Problema do Próximo Releases (Multi-Objetivo)

Conjunto de clientes, C = {c1, . . .,cm} e conjunto de requisitos, R = {r1, . . .,rm} todos independentes

Cada requisito possui um certo custo, dado por Cost = {cost1, . . .,costm}

Cada cliente têm uma importância, dado por Weight = {weight1, . . .,weightm}

Cada cliente indica um valor para cada requisito, dado por value(ri,cj), ondevalue(ri,cj) > 0 se possui esse requisito, ou value(ri,cj) = 0, ao contrário.

A importância total de um requisito ri é dada por scorei= j=1m value(ri,cj)

A tarefa é encontrar um vetor de decisão x = {x1, . . .,xn} {0,1}, onde 1 indicaque o requisito foi selecionado, e 0 que não.

Problema do Próximo Releases (Multi-Objetivo)

i

n

i

i xscore1

Maximizar

i

n

i

i xcost1

-Maximizar

Maximização da Importância

Minimização do Custo

Problema do Próximo Releases (Multi-Objetivo)

Foram avaliados vários algoritmos (NSGA-II, Algoritmo Genético de Pareto (Pareto GA), Algoritmo Genético Mono-Objetivo, Busca Randômica) sobre doisproblemas de tamanhos variados.

A metaheurística NSGA-II obteve os melhores resultados em todos os casos.

Quando maior o conjunto de teste, maior foi a diferença de desempenho entre o NSGA-II e o Pareto GA, que obteve o segundo melhor resultado nos experimentos.

Resultados

Planejamento de Releases

Fonte: Colares, F., Souza, J., Carmo, R., Pádua, C. e Mateus, G. A New Approach to the Software

Release Planning. Anais do XXIII Simpósio Brasileiro de Engenharia de Software. 2009.

Extensão da formulação anterior

Trata a dependência entre requisitos e risco

Planeja todos os releases, e não somente o próximo

Aspectos Considerados

• Satisfação dos Clientes

• Priorização de Requisitos (pelo risco)

• Interdependência entre Requisitos

• Recursos Limitados

Planejamento de Releases

Problema

Distribuir um conjunto de requisitos entre diversos releases com os objetivos de aumentar a satisfação dos clientes e diminuir os riscos do projeto, respeitando a quantidade de recursos disponíveis em cada release e a interdependência entre requisitos.

Formulação

Planejamento de Releases

Conjunto de Requisitos, R = {r1, r2, ..., r|R|}

Conjunto de Clientes, S = {s1, s2,..., s|S|}

Conjunto de Releases, K = {k1, k2,..., k|K|}

Conjunto de Recursos, P = {p1, p2, ..., p|P|}

Formulação

Cada cliente possui um peso, Weight = {weight1, . . .,weight|S|}

Cada cliente tem uma prioridade para cada requisito, prioritys,r

Cada requisito tem um custo relativo a cada recurso, efforti

Planejamento de Releases

Formulação

Há um valor disponível para cada recurso em cada iteração, Available_resources = {available_resources1, . . .,available_resources iority|K|}

Cada requisito tem um risco associado, Risk = {risk1, . . .,risk|R|}

Deseja-se calcular o vetor x = {x1, ..., r|R|}, onde cada xi varia de 1 até |K|, indicando em qual release o requisito i será implementado.

Planejamento de Releases

Ss Rr

i

s

rs

s xKprioritytotal

priorityweight

_Maximizar

,

Rr

ir xriskMinimizar

Rr

ir Kiiresourcesavailableeffort 1|,_ a Sujeito

)(, jiji rrxx

Maximização da Satisfação

Minimização do Risco

Restrição de Recursos

Restrição de Precedência

Planejamento de Releases

A metaheurística NSGA-II foi avaliada sobre um problema com 19 requisitos, 5 releases, 5 clientes e 3 recursos diferentes.

A metaheurística NSGA-II obteve melhores resultado que uma busca aleatória.

Comparado com os resultados gerados por 5 profissionais, o NSGA-II os superou significantemente.

Resultados

Planejamento de Releases

Alocação de Pessoal

Fonte: Burdett, G. e Li, R. Quantitative Approach to the Formation of Workgroups. Anais do ACM

SIGCPR Conference on Supporting Teams, Groups, and Learning inside and Outside

the IS Function: Reinventing IS. 1995

Alocação de pessoas para a execução de uma determinada conjunto de

tarefas

Considera as preferências e as habilidades de cada pessoa

Alocação de Pessoal

Problema

Alocar um conjunto de pessoas a um conjunto de tarefas minimizando o custo salarial, priorizando as habilidadesde cada pessoa e respeitando suas preferências.

Alocação de Pessoal

P

p

a

N

a

app DurASal1 1

Minimizar

N

a

P

p

P

p

ppapappp

N

a

P

p

apmpa

N

a

P

p

appa

P

p

S

s

N

a

sapps

XAAP

APAP

SIAR

1 11 12

212121

1 11 1

1 1 1

Formulação

Alocação de Pessoal

Duração da Atividade a, Dura

Tempo de finalização da Atividade a, FTa

Número de instâncias da Habilidade s requeridas para a Atividade a, Isa

Peso da performance na função objetivo,

Formulação

Alocação de Pessoal

Peso das preferências na função objetiva,

Número total de Atividades, N

Número total de Pessoas, P

Preferência da gerência pela Pessoa P na Atividade a, Pma

Preferência da Pessoa p pela Atividade a, Ppa

Formulação

Alocação de Pessoal

A Pessoa 1 prefere trabalhar com a Pessoa 2, Pp1p2

Ranking da Pessoa p na Habilidade s, Rps

Custo salarial da Pessoa p por unidade de tempo, Salp

Importância da Habilidade s, SIs

Tempo de inicialização da Atividade a, STa

Onde ...

Alocação de Pessoal

Aap = 1 se a Pessoa p for alocada para a Atividade a, e 0, caso contrário

Aap1 = 1 se a Pessoa p1 for alocada para a Atividade a, e 0, caso contrário

Aap2 = 1 se a Pessoa p2 for alocada para a Atividade a, e 0, caso contrário

Onde ...

Alocação de Pessoal

Das = 1 se a Atividade a demanda a habilidade s, e 0, caso contrário

Xp1p2 = 1 se a Pessoa p1 é diferente da pessoa p2, e 0, caso contrário

Alocação de Pessoal

P

p

a

N

a

app DurASal1 1

Minimizar

N

a

P

p

P

p

ppapappp

N

a

P

p

apmpa

N

a

P

p

appa

P

p

S

s

N

a

sapps

XAAP

APAP

SIAR

1 11 12

212121

1 11 1

1 1 1

Custo Salarial

Alocação de Pessoal

P

p

a

N

a

app DurASal1 1

Minimizar

N

a

P

p

P

p

ppapappp

N

a

P

p

apmpa

N

a

P

p

appa

P

p

S

s

N

a

sapps

XAAP

APAP

SIAR

1 11 12

212121

1 11 1

1 1 1

Priorização das Habilidades

Alocação de Pessoal

P

p

a

N

a

app DurASal1 1

Minimizar

N

a

P

p

P

p

ppapappp

N

a

P

p

apmpa

N

a

P

p

appa

P

p

S

s

N

a

sapps

XAAP

APAP

SIAR

1 11 12

212121

1 11 1

1 1 1

Priorização das Preferências por

Atividades

Alocação de Pessoal

P

p

a

N

a

app DurASal1 1

Minimizar

N

a

P

p

P

p

ppapappp

N

a

P

p

apmpa

N

a

P

p

appa

P

p

S

s

N

a

sapps

XAAP

APAP

SIAR

1 11 12

212121

1 11 1

1 1 1

Priorização das Preferências por

Pessoas

Alocação de Pessoal

A metaheurística Têmpera Simulada foi avaliada sobre dados geradosaleatoriamento contendo 10, 20, 50 e 100 pessoas, onde foram selecionadasequipes de 5 ou 10 pessoas.

A solução ótima foi encontrado pela Têmpera Simulada para equipes de 5 pessoas de um total de 10, 20, 50 e 100 pessoas, com baixo custocomputacional.

Para equipes de 10 pessoas, como as soluções ótimas não eram conhecidas, os resultados obtidos pela Têmpera Simulada não puderam ser avaliados.

Resultados

Priorização de Casos de Teste

Fonte: Maia, C. , Carmo, R., Campos, G. e SOUZA, J. A Reactive GRASP Approach for Regression

Test Case Prioritization. Anais do XL Simpósio Brasileiro de Pesquisa Operacional. 2008.

Modificações em um software pode causar problemas em outras funcionalidades

Re-testar todo o software pode ser inviável

A ordenação de casos de teste permite a seleção de um subconjunto destes

Um caso de teste é avaliado pela quantidade de erros que ele encontra

Calcular esse valor é impossível sem executar o caso de teste

Métricas de cobertura (de bloco, de linhas de comando e de decisão) são utilizadas

Priorização de Casos de Teste

Problema

Ordenar os casos de teste de forma que somente um subconjunto de casos de teste possa ser executado, com somente pequena, ou nenhuma, perda de efetividade.

Formulação

Suíte de testes, T, com n casos de teste que cobre um conjunto B de mblocos de código

Seja TBi o primeiro caso de teste na ordem T´, de T, que cobre o bloco i.

A métrica APBC (Average Percentage Block Coverage) para a ordem T´ é dada por 1 – (TB1 + TB2 + ... + TBm)/nm + 1/2n

As métricas APDC (Average Percentage Decision Coverage) e APSC (Average Percentage Statement Coverage) são calculadas de forma similar

Priorização de Casos de Teste

Entendendo a Métrica APBC

Priorização de Casos de Teste

1 2 3 4 5 6 7 8 9 10

A X X

B X X X X

C X X X X X X

D X X

E X X X XCas

os

de

Test

e

Blocos

0102030405060708090

100

0,0 0,2 0,4 0,6 0,8 1,0

Per

cen

tual

de

Co

ber

tura

de

Blo

cos

Fração do Suíte de Teste

Ordenação T1: A – B – C – D – E

APBC = 46%

Entendendo a Métrica APBC

Priorização de Casos de Teste

1 2 3 4 5 6 7 8 9 10

A X X

B X X X X

C X X X X X X

D X X

E X X X XCas

os

de

Test

e

Blocos

0102030405060708090

100

0,0 0,2 0,4 0,6 0,8 1,0

Per

cen

tual

de

Co

ber

tura

de

Blo

cos

Fração do Suíte de Teste

Ordenação T1: C – E – B – A – D

APBC = 82%

Priorização de Casos de Teste

APBCMaximizar

Priorização de Casos de Teste

A metaheurística GRASP Reativo foi comparada com os métodos Guloso, GulosoAdicional e Algoritmo Genético. Foram usados 5 programas de tamanhosvariados, onde foram avaliadas as métricas APBC, APDC e APSC.

O algoritmo Guloso Adicional teve o melhor desempenho de todos, superando significantemente o método Guloso e Algoritmo Genético, que surpreendentemente obteve a pior performance de todos.

O GRASP Reactivo obteve o segundo melhor resultado, gerando resultados insignificantemente piores do que o Guloso Adicional.

Não foram encontradas diferenças de performance nas diferentes métricas.

Resultados

Metaheurísticas Aplicadas a Problemas Complexos da Engenharia de Software

PARTE 04 - CONSIDERAÇÕES FINAIS

XXIV Simpósio Brasileiro de Banco de Dados XXIII Simpósio Brasileiro de Engenharia de Software

Fortaleza, 05 a 09 de Outubro de 2009

A Otimização em Engenharia de Software (Search-based Software Engineering) se apresenta como novo ramo de pesquisa daEngenharia de Software.

Tem alcançado um crescente interesse mundial (ver slide a seguir), e gerado resultados relevantes rapidamente, especialmente porcombinar conhecimentos consolidados.

Muito ainda precisa ser feito no sentido de popularização desses resultados fora do meio acadêmico.

Considerações Finais

0

10

20

30

40

50

60

70

80

90

100

Histórico de Publicações em SBSE

FONTE: SEBASE

Pesquisa em Otimização em Engenharia de Software

Novos Problemas

Geração de novas formulações para problemas da engenharia de software. Extensão de formulações existentes . Tratamento multi-objetivo para formulações mono-objetivas.

Novas Abordagens

Aplicações de novos métodos de busca em problemas existentes. Estudos comparativos de técnicas de busca.

Competitividade Humana

Análise da competitividade dos resultados gerados automaticamente em comparação com resultados produzidos por humanos.

Pesquisa em Otimização em Engenharia de Software

Análise de Sensibilidade

Avaliação da influência de variáveis na qualidade de resultados gerados e na dificuldade de resolver certos problemas.

Otimização Interativa

Estratégias de incorporação do julgamento humano durante o processo de otimização.

Hibridização

Combinação de métodos na geração de abordagens mais eficientes.

Cooperação

O Grupo de Otimização em Engenharia de Software (GOES.UECE) está a disposição.

Divulgação/Aprendizado

2nd International Symposium on Search Based Software Engineering, em Setembro de 2010 na Cidade de Benevento, Itália

1o Workshop Brasileiro de Otimização em Engenharia de Software, em conjunto com o SBES´2010 (a confirmar)

Oportunidades

Chegamos ao fim!Obrigado pelo tempo e pela atenção.

Chegamos ao fim!Obrigado pelo tempo e pela atenção.

Universidade Estadual do Ceará

GOES.UECE - Grupo de Otimização em Engenharia de Software

http://goes.comp.uece.br/

XXIV Simpósio Brasileiro de Banco de Dados XXIII Simpósio Brasileiro de Engenharia de Software

Fortaleza, 05 a 09 de Outubro de 2009

prof.jerff@gmail.com

Metaheurísticas Aplicadas a Problemas Complexos da Engenharia de Software