Critérios de parada baseados em probabilidade bayesiana aplicados a heurísticas GRASP : um estudo experimental

Neves, Layni Andrade

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

dc.contributor.advisor	Alvim, Adriana Cesário de Faria
dc.contributor.author	Neves, Layni Andrade
dc.date.accessioned	2019-06-04T22:39:40Z
dc.date.available	2019-06-04T22:39:40Z
dc.date.issued	2009-05-13
dc.identifier.citation	NEVES, Layni Andrade. Critérios de parada baseados em probabilidade Bayesiana aplicados a heurísticas Grasp : um estudo experimental. 2009, 83.f. Dissertação ( Mestrado em Informática ) - Universidade Federal do Estado do Rio de Janeiro, Rio de Janeiro, 2009.	pt_BR
dc.identifier.uri	http://hdl.handle.net/unirio/12807
dc.description	Dissertação também disponível em formato impresso, com o número de chamada MI 2009/08.	pt_BR
dc.description.sponsorship	n/a	pt_BR
dc.language.iso	Portuguese	pt_BR
dc.rights	openAccess	pt_BR
dc.title	Critérios de parada baseados em probabilidade bayesiana aplicados a heurísticas GRASP : um estudo experimental	pt_BR
dc.title.alternative	Stopping criteria based on the Baeysian applied GRASP Heuristics - An Experimental Study	pt_BR
dc.type	masterThesis	pt_BR
dc.contributor.advisor-co	Resende, Mauricio Guilherme de Carvalho
dc.contributor.referee	Alvim, Adriana Cesário de Faria
dc.contributor.referee	Resende, Mauricio Guilherme de Carvalho
dc.contributor.referee	Andreatta, Alexandre Albino
dc.contributor.referee	Souza, Reinaldo Castro
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	Grasp	pt_BR
dc.subject.en	Bayesian Statistic	pt_BR
dc.subject.en	Heuristic	pt_BR
dc.subject.en	Combinatorial Optimization	pt_BR
dc.subject.en	Stopping Rule	pt_BR
dc.description.abstracten	The use of algorithms based on the GRASP metaheuristic is relevant for the solution of many combinatorial optimization problems. These algorithms find a feasible solution of good quality when is difficult to find an exact solution because of the problem’s computational complexity. One of the key issues in designing heuristics is the balance between processing time and solution quality. This thesis presents the implementation and testing of Bayesian stopping rules in GRASP heuristics. The objective is to choose a stopping rule that results in a short running time of the heuristic while at the same time achieving good solution quality. In the computational experiment, we compared, on five previously published GRASP heuristics, the original version using a stopping rule based on a fixed number of iterations with versions that use Bayesian stopping rules.	pt_BR
dc.degree.country	Brasil	pt_BR
dc.description.sponsordocumentnumber	n/a	pt_BR
dc.description.abstractpt	O uso de algoritmos baseados em metaheurísticas é de relevante importância para a resolução de diversos problemas de otimização combinatória. Estes algoritmos procuram uma solução viável de boa qualidade quando é difícil encontrar a solução exata devido a complexidade computacional do problema. Uma das questões fundamentais em heurísticas baseadas em metaheurísticas e equilibrar tempo de processamento e qualidade da solução. Este trabalho apresenta a implementação e teste de critérios de parada baseados em estatística bayesiana em heurísticas baseadas na metaheurística GRASP. O objetivo e escolher um critério de parada que resulte em um tempo de processamento curto ´ da heur´ıstica, e que, ao mesmo tempo, alcance uma soluc¸ao de boa qualidade. No experimento computacional foram comparadas cinco implementações de heurísticas GRASP previamente publicadas que utilizam como critério de parada um número fixo de iteracoes, com novas versões que utilizam o critério de parada bayesiano.	pt_BR
dc.subject.pt	Grasp	pt_BR
dc.subject.pt	Estatística Bayesiana	pt_BR
dc.subject.pt	Heurística	pt_BR
dc.subject.pt	Otimização combinatória	pt_BR
dc.subject.pt	Critério de parada	pt_BR