Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético

Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inheren...

ver descrição completa

Na minha lista:
Detalhes bibliográficos
Autor principal: Lima Júnior, Francisco Chagas de
Outros Autores: Melo, Jorge Dantas de
Formato: doctoralThesis
Idioma:por
Publicado em: Universidade Federal do Rio Grande do Norte
Assuntos:
MetaheurísticaGRASP
Algoritmos genéticos
AlgoritmoQ-learning
Problema do caixeiro viajante
GRASP metaheuristic
Genetic algorithm
Q-learning algorithm
Travelling salesman problem
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Endereço do item:https://repositorio.ufrn.br/jspui/handle/123456789/15129
Tags: Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
id ri-123456789-15129
record_format dspace
institution Repositório Institucional
collection RI - UFRN
language por
topic MetaheurísticaGRASP
Algoritmos genéticos
AlgoritmoQ-learning
Problema do caixeiro viajante
GRASP metaheuristic
Genetic algorithm
Q-learning algorithm
Travelling salesman problem
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
spellingShingle MetaheurísticaGRASP
Algoritmos genéticos
AlgoritmoQ-learning
Problema do caixeiro viajante
GRASP metaheuristic
Genetic algorithm
Q-learning algorithm
Travelling salesman problem
CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Lima Júnior, Francisco Chagas de
Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
description Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process
author2 Melo, Jorge Dantas de
author_facet Melo, Jorge Dantas de
Lima Júnior, Francisco Chagas de
format doctoralThesis
author Lima Júnior, Francisco Chagas de
author_sort Lima Júnior, Francisco Chagas de
title Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
title_short Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
title_full Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
title_fullStr Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
title_full_unstemmed Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
title_sort algoritmo q-learning como estratégia de exploração e/ou explotação para metaheurísticas grasp e algoritmo genético
publisher Universidade Federal do Rio Grande do Norte
publishDate 2014
url https://repositorio.ufrn.br/jspui/handle/123456789/15129
work_keys_str_mv AT limajuniorfranciscochagasde algoritmoqlearningcomoestrategiadeexploracaoeouexplotacaoparametaheuristicasgraspealgoritmogenetico
_version_ 1773959563781865472
spelling ri-123456789-151292017-11-02T08:15:40Z Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético Lima Júnior, Francisco Chagas de Melo, Jorge Dantas de http://lattes.cnpq.br/7325007451912598 Dória Neto, Adrião Duarte http://lattes.cnpq.br/1987295209521433 Aloise, Dario José http://lattes.cnpq.br/7266011798625538 Viana, Gerardo Valdisio Rodrigues http://lattes.cnpq.br/6262051397848744 MetaheurísticaGRASP Algoritmos genéticos AlgoritmoQ-learning Problema do caixeiro viajante GRASP metaheuristic Genetic algorithm Q-learning algorithm Travelling salesman problem CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process Técnicas de otimização conhecidas como metaheurísticas têm obtido sucesso na resolução de problemas classificados como NP - Árduos. Estes métodos utilizam abordagens não determinísticas que geram soluções próximas do ótimo sem, no entanto, garantir a determinação do ótimo global. Além das dificuldades inerentes à complexidade que caracteriza os problemas NP-Árduos, as metaheurísticas enfrentam ainda o dilema de exploração/explotação, que consiste em escolher entre intensificação da busca em uma região específica e a exploração mais ampla do espaço de soluções. Uma forma de orientar tais algoritmos em busca de melhores soluções é supri-los de maior conhecimento do problema através da utilização de um agente inteligente, capaz de reconhecer regiões promissoras e/ou identificar em que momento deverá diversificar a direção de busca, isto pode ser feito através da aplicação de Aprendizagem por Reforço. Neste contexto, este trabalho propõe o uso de uma técnica de Aprendizagem por Reforço - especificamente o Algoritmo Q-learning - como uma estratégia de exploração/explotação para as metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure) e Algoritmo Genético. Na implementação da metaheurística GRASP proposta, utilizou-se o Q-learning em substituição ao algoritmo guloso-aleatório tradicionalmente usado na fase de construção. Tal substituição teve como objetivo melhorar a qualidade das soluções iniciais que serão utilizadas na fase de busca local do GRASP, e, ao mesmo tempo, suprir esta metaheurísticas de um mecanismo de memória adaptativa que permita a reutilização de boas decisões tomadas em iterações passadas e que evite a repetição de decisões não promissoras. No Algoritmo Genético, o algoritmo Q-learning foi utilizado para gerar uma população inicial de alta aptidão, e após um determinado número de gerações, caso a taxa de diversidade da população seja menor do que um determinado limite L, ele é também utilizado em uma forma alternativa de operador de cruzamento. Outra modificação importante no algoritmo genético híbrido é a proposta de um processo de interação mutuamente cooperativa entre o os operadores genéticos e o Algoritmo Q-learning. Neste processo interativo/cooperativo o algoritmo Q-learning recebe uma atualização adicional na matriz dos Q-valores com base na solução elite da população corrente. Os experimentos computacionais apresentados neste trabalho consistem em comparar os resultados obtidos com a implementação de versões tradicionais das metaheurísticas citadas, com aqueles obtidos utilizando os métodos híbridos propostos. Ambos os algoritmos foram aplicados com sucesso ao problema do caixeiro viajante simétrico, que por sua vez, foi modelado como um processo de decisão de Markov 2014-12-17T14:54:52Z 2009-06-09 2014-12-17T14:54:52Z 2009-03-20 doctoralThesis LIMA JÚNIOR, Francisco Chagas de. Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético. 2009. 140 f. Tese (Doutorado em Automação e Sistemas; Engenharia de Computação; Telecomunicações) - Universidade Federal do Rio Grande do Norte, Natal, 2009. https://repositorio.ufrn.br/jspui/handle/123456789/15129 por Acesso Aberto application/pdf application/pdf Universidade Federal do Rio Grande do Norte BR UFRN Programa de Pós-Graduação em Engenharia Elétrica Automação e Sistemas; Engenharia de Computação; Telecomunicações

Registros relacionados