Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis
The hybridization of metaheuristics is a topic that several researchers have studied due to its potential to produce more efficient heuristics than those based on a single technique. However, hybridization is not easy, as there are several ways to operationalize it. The task becomes even more cha...
Na minha lista:
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | doctoralThesis |
| Idioma: | pt_BR |
| Publicado em: |
Universidade Federal do Rio Grande do Norte
|
| Assuntos: | |
| Endereço do item: | https://repositorio.ufrn.br/handle/123456789/55323 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| id |
ri-123456789-55323 |
|---|---|
| record_format |
dspace |
| institution |
Repositório Institucional |
| collection |
RI - UFRN |
| language |
pt_BR |
| topic |
Computação Hibridização de meta-heurística Matheurística Aprendizado por oposição Aprendizado ortogonal Problema do caixeiro viajante alugador com passageiros Cabeamento de usinas eólicas CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
| spellingShingle |
Computação Hibridização de meta-heurística Matheurística Aprendizado por oposição Aprendizado ortogonal Problema do caixeiro viajante alugador com passageiros Cabeamento de usinas eólicas CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO Machado, Murilo Oliveira Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| description |
The hybridization of metaheuristics is a topic that several researchers have studied due to
its potential to produce more efficient heuristics than those based on a single technique.
However, hybridization is not easy, as there are several ways to operationalize it. The
task becomes even more challenging when three or more metaheuristic methods need
to hybridize or when someone wants to add Mathematical Programming methods, thus
creating “matheuristics.” Various methods have been proposed to hybridize metaheuristics,
including some techniques that automate hybridization, such as multi-agent architectures.
A few of these architectures use learning techniques, and an even smaller number deal
with matheuristics. This work extends the capabilities of the Multi-agent Architecture
for Metaheuristic Hybridization by including learning techniques and Mathematical Programming. The application of learning techniques is innovative, considering the agents’
choice of heuristics to apply at different search stages. This work proposes a new form of
hierarchical hybridization for Combinatorial Optimization problems with multiple decision
levels. The algorithmic proposals are tested on the Traveling Car Renter with Passengers
and the Cable Routing Problem in Wind Farms. These problems belong to the NP-hard
class and require decision-making at multiple levels. In the case of the Traveling Car
Renter with Passengers, there are three decision levels: route, car types, and customers’
transport demand. Cable routing in wind farms requires decisions concerning the cable
locations and the cable type used in each section. The experiments for the Traveling Car
Renter with Passengers were conducted on three classes of instances, totaling ninety-nine
test cases ranging from four to eighty cities, two to five vehicles, and ten to a hundred
forty people requiring transportation. Experiments for The Cable Routing Problem in
Wind Farms involved a set of two hundred instances. These instances are simulations of
real situations developed in collaboration with domain experts. The approaches proposed
in this work are compared to state-of-the-art algorithms for both problems. |
| author2 |
Goldbarg, Elizabeth Ferreira Gouvea |
| author_facet |
Goldbarg, Elizabeth Ferreira Gouvea Machado, Murilo Oliveira |
| format |
doctoralThesis |
| author |
Machado, Murilo Oliveira |
| author_sort |
Machado, Murilo Oliveira |
| title |
Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| title_short |
Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| title_full |
Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| title_fullStr |
Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| title_full_unstemmed |
Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| title_sort |
investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis |
| publisher |
Universidade Federal do Rio Grande do Norte |
| publishDate |
2023 |
| url |
https://repositorio.ufrn.br/handle/123456789/55323 |
| work_keys_str_mv |
AT machadomurilooliveira investigacaodaadicaodemetodosdeaprendizadoeprogramacaomatematicaemumaarquiteturadehibridizacaodemetaheuristicasparaproblemasdeotimizacaocomdecisoesemmultiplosniveis AT machadomurilooliveira investigatingtheinclusionoflearningmethodsandmathematicalprogramminginanarchitectureformetaheuristichybridizationformultileveldecisionsonoptimizationproblems |
| _version_ |
1784351479739449344 |
| spelling |
ri-123456789-553232023-11-13T23:30:04Z Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis Investigating the inclusion of learning methods and mathematical programming in an architecture for metaheuristic Hybridization for multi-level decisions on optimization problems Machado, Murilo Oliveira Goldbarg, Elizabeth Ferreira Gouvea http://lattes.cnpq.br/2888641121265608 Almeida, Carolina de Paula Sabry, Gustavo de Araújo Fernandes, Islame Felipe da Costa Menezes, Matheus da Silva Maia, Silvia Maria Diniz Monteiro http://lattes.cnpq.br/1498104590221901 Computação Hibridização de meta-heurística Matheurística Aprendizado por oposição Aprendizado ortogonal Problema do caixeiro viajante alugador com passageiros Cabeamento de usinas eólicas CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO The hybridization of metaheuristics is a topic that several researchers have studied due to its potential to produce more efficient heuristics than those based on a single technique. However, hybridization is not easy, as there are several ways to operationalize it. The task becomes even more challenging when three or more metaheuristic methods need to hybridize or when someone wants to add Mathematical Programming methods, thus creating “matheuristics.” Various methods have been proposed to hybridize metaheuristics, including some techniques that automate hybridization, such as multi-agent architectures. A few of these architectures use learning techniques, and an even smaller number deal with matheuristics. This work extends the capabilities of the Multi-agent Architecture for Metaheuristic Hybridization by including learning techniques and Mathematical Programming. The application of learning techniques is innovative, considering the agents’ choice of heuristics to apply at different search stages. This work proposes a new form of hierarchical hybridization for Combinatorial Optimization problems with multiple decision levels. The algorithmic proposals are tested on the Traveling Car Renter with Passengers and the Cable Routing Problem in Wind Farms. These problems belong to the NP-hard class and require decision-making at multiple levels. In the case of the Traveling Car Renter with Passengers, there are three decision levels: route, car types, and customers’ transport demand. Cable routing in wind farms requires decisions concerning the cable locations and the cable type used in each section. The experiments for the Traveling Car Renter with Passengers were conducted on three classes of instances, totaling ninety-nine test cases ranging from four to eighty cities, two to five vehicles, and ten to a hundred forty people requiring transportation. Experiments for The Cable Routing Problem in Wind Farms involved a set of two hundred instances. These instances are simulations of real situations developed in collaboration with domain experts. The approaches proposed in this work are compared to state-of-the-art algorithms for both problems. A hibridização de meta-heurísticas é um tópico que vem sendo estudado por diversos pesquisadores dado ao seu potencial de produzir heurísticas mais eficientes do que aquelas baseadas em uma única técnica. Tal hibridização, entretanto, não é uma tarefa fácil, uma vez que existem diversas maneiras de operacionalizá-la. A tarefa se torna ainda mais difícil quando existem três ou mais métodos meta-heurísticos a serem hibridizados ou quando se deseja adicionar métodos de Programação Matemática, construindo, assim, matheurísticas. Diversos métodos foram propostos para hibridizar meta-heurísticas, incluindo algumas técnicas que automatizam a hibridização, como é o caso de arquiteturas multi-agentes. Um pequeno número dessas arquiteturas se utiliza de técnicas de aprendizado e um número ainda mais restrito lida com matheurísticas. Este trabalho estende os recursos da Arquitetura Multiagentes para Hibridização de Meta-heurísticas incluindo técnicas de aprendizado e de Programação Matemática. A forma da aplicação das técnicas de aprendizado é inovadora contemplando a escolha feita pelos agentes de heurísticas a serem aplicadas em diferentes momentos da busca. Este trabalho propõe uma nova forma de hibridização hierárquica para problemas de Otimização Combinatória que possuem múltiplos níveis de decisão. As propostas algorítmicas são testadas no Caixeiro Viajante Alugador com Passageiros e no Problema de Cabeamento em Usinas Eólicas. Esses problemas pertencem à classe NP-difícil e exigem a tomada de decisão em mais de um nível. No caso do Caixeiro Viajante Alugador com Passageiros a tomada de decisão se dá em três níveis: rota, tipos de carros utilizados e atendimento de demanda por caronas. No caso do cabeamento em usinas eólicas são exigidas decisões do local de cabeamento e tipo de cabo a ser empregado em cada trecho. Os experimentos para o Caixeiro Viajante Alugador com Passageiros foram feitos para três classes de instâncias, em um total de noventa e nove casos de teste com tamanho variando de 4 a 80 cidades, 2 a 5 veículos e 10 a 240 pessoas demandando transporte. O Problema de Cabeamento em Usinas Eólicas foi alvo de experimentos que envolveram um conjunto de 200 instâncias. Essas instâncias são simulações de situações reais desenvolvidas em colaboração com especialistas da área. As abordagens propostas neste trabalho são comparadas a algoritmos do estado-da-arte para ambos os problemas. 2023-11-13T23:29:14Z 2023-11-13T23:29:14Z 2023-08-02 doctoralThesis MACHADO, Murilo Oliveira. Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis. Orientadora: Dra. Elizabeth Ferreira Gouvêa Goldbarg. 2023. 208f. Tese (Doutorado em Ciência da Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2023. https://repositorio.ufrn.br/handle/123456789/55323 pt_BR Acesso Aberto application/pdf Universidade Federal do Rio Grande do Norte Brasil UFRN PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO |