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

AUTOR(ES)
DATA DE PUBLICAÇÃO

2009

RESUMO

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

ASSUNTO(S)

q-learning algorithm metaheurísticagrasp problema do caixeiro viajante algoritmoq-learning algoritmos genéticos grasp metaheuristic genetic algorithm engenharia eletrica travelling salesman problem

ACESSO AO ARTIGO

Documentos Relacionados