Melhorando heurísticas para o NRP através da visualização do espaço de busca

Fuchshuber, Richard

DSpace Home
→
Centro de Ciências Exatas e Tecnologia (CCET)
→
Informática Aplicada
→
INAP - Dissertações de Mestrado
→
View Item

dc.contributor.advisor	Barros, Márcio de Oliveira
dc.contributor.author	Fuchshuber, Richard
dc.date.accessioned	2018-06-26T22:27:51Z
dc.date.available	2018-06-26T22:27:51Z
dc.date.issued	2015-09-18
dc.identifier.citation	FUCHSHUBER, Richard. Melhorando heurísticas para o NRP através da visualização do espaço de busca. 2015. 64 f. Dissertação (Mestrado em Informática) - Universidade Federal do Estado do Rio de Janeiro, Rio de janeiro, 2015.	pt_BR
dc.identifier.uri	http://hdl.handle.net/unirio/11810
dc.description	Dissertação também disponível em formato impresso, com o número de chamada CCET MI 2015/20.	pt_BR
dc.description.sponsorship	n/a	pt_BR
dc.language.iso	Portuguese	pt_BR
dc.rights	openAccess	pt_BR
dc.title	Melhorando heurísticas para o NRP através da visualização do espaço de busca	pt_BR
dc.type	masterThesis	pt_BR
dc.contributor.referee	Barros, Márcio de Oliveira
dc.contributor.referee	Alvim, Adriana Cesário de Faria
dc.contributor.referee	Murta, Leonardo Gresta Paulino
dc.degree.department	CCET	pt_BR
dc.degree.grantor	Universidade Federal do Estado do Rio de Janeiro - UNIRIO	pt_BR
dc.degree.level	Mestrado Acadêmico	pt_BR
dc.degree.local	Rio de Janeiro, RJ.	pt_BR
dc.degree.program	Programa de Pós-Graduação em Informática	pt_BR
dc.subject.cnpq	CIÊNCIAS EXATAS E DA TERRA	pt_BR
dc.subject.cnpq	CIÊNCIA DA COMPUTAÇÃO	pt_BR
dc.subject.en	Heuristics	pt_BR
dc.subject.en	Next Release Problem	pt_BR
dc.subject.en	Fitness Landscape Visualization	pt_BR
dc.description.abstracten	The selection of requirements to be included in the next release of a software requires balancing customers needs and budget constraints. The Next Release Problem (NRP) aims to select a subset of the requirements to be implemented in the next release that maximizes customer’s benefits while the development budget is satisfied. Given a large set of requirements or clients, an exhaustive search that examines all subsets cannot be performed in feasible time. Thus, heuristic algorithms are employed to find solutions for the NRP. Visualizing the fitness landscape from a customer concentration perspective, we observed a recurring pattern in several instances of the NRP. This work presents these findings and describes an Iterated Local Search (ILS) algorithm modified to take advantage of this pattern. The proposed algorithm is much simpler than the current state-of-art heuristic approach for the NRP, known as BMA (Backbone- Based Multilevel Algorithm). When executed against two commonly used large scale instance sets, BMA generated solutions that are, on average, 4.1% worse than the optimal solution for each instance. The algorithm proposed in this work reduced the distance from the optimal solutions to 1.3%, an 68% improvement when compared with BMA.	pt_BR
dc.degree.country	Brasil	pt_BR
dc.description.sponsordocumentnumber	n/a	pt_BR
dc.description.abstractpt	A seleção de quais requisitos incluir na próxima versãoo de um software requer o equilíbrio entre as necessidades dos clientes e as restrições orçamentárias. O Problema da Próxima Versão do Software (Next Release Problem - NRP) consiste em selecionar um subconjunto dos requisitos para serem implementados na próxima vers˜ao do software, de modo a maximizar o benef´ıcio gerado aos clientes sem exceder o or¸camento dispon´ıvel. Dado um grande conjunto de requisitos e clientes, uma busca exaustiva que examina todos os subconjuntos n˜ao pode ser executada em um tempo computacional aceitável. Por isso, algoritmos heurísticos são empregados para obter soluções para o NRP. Através da visualização do espaço de busca de uma perspectiva da concentração de clientes, foi identificado um padrão gráfico que foi observado em diversas instâncias do NRP. Este trabalho apresenta estes resultados e descreve uma Busca Local Iterada (Iterated Local Search - ILS) que foi adaptada para utilizar este padrão no processo de busca. O algoritmo proposto é muito mais simples que a atual heur´ıstica estado-da-arte para o NRP, conhecida como BMA (Backbone-Based Multilevel Algorithm). Ao ser executado em dois conjuntos de instâncias amplamente utilizadas pela literatura, o BMA gerou soluções, em média, 4,1% piores que as soluções ótimas destas instâncias. O algoritmo proposto neste trabalho foi capaz de reduzir o afastamento médio em relação aos valores ótimos para 1,3%, uma melhoria de 68% em relação ao BMA.	pt_BR
dc.subject.pt	Heurísticas	pt_BR
dc.subject.pt	Next Release Problem	pt_BR
dc.subject.pt	Visualização do espaço de busca	pt_BR