Submitted by Rafael Santana (rafael.silvasantana@ufpe.br) on 2017-05-04T18:13:43Z
No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Teste - Péricles Miranda.pdf: 1959669 bytes, checksum: 8b0b1e3f94dd3295bce6153865564a12 (MD5) / Made available in DSpace on 2017-05-04T18:13:43Z (GMT). No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
Teste - Péricles Miranda.pdf: 1959669 bytes, checksum: 8b0b1e3f94dd3295bce6153865564a12 (MD5)
Previous issue date: 2016-08-22 / A escolha de algoritmos ou heurísticas para a resolução de um dado problema é uma tarefa
desafiadora devido à variedade de possíveis escolhas de variações/configurações de algoritmos e
a falta de auxílio em como escolhê-las ou combiná-las. Por exemplo, o desempenho de algoritmo
de otimização depende da escolha dos seus operadores de busca e do ajuste adequado de seus
hiper-parâmetros, cada um deles com muitas possibilidades de opções a serem escolhidas. Por
este motivo, existe um interesse de pesquisa crescente na automatização da otimização de
algoritmos de modo a tornar esta tarefa mais independente da interação humana. Diferentes
abordagens têm lidado com a tarefa de ajuste de algoritmos como sendo outro problema de
(meta)otimização. Estas abordagens são comumente chamadas de hiper-heurísticas, onde cada
solução do espaço de busca, neste caso, é um possível algoritmo avaliado em um dado problema.
Inicialmente, hiper-heurísticas foram aplicadas na seleção de valores de hiper-parâmetros em
um espaço de busca pré-definido e limitado. No entanto, recentemente, hiper-heurísticas têm
sido desenvolvidas para gerar algoritmos a partir de componentes e funções especificados. Hiperheurísticas
de geração são consideradas mais flexíveis que as de seleção devido à sua capacidade
de criar algoritmos novos e personalizados para um dado problema. As hiper-heurísticas têm sido
largamente utilizadas na otimização de meta-heurísticas. No entanto, o processo de busca torna-se
bastante custoso, pois a avaliação das soluções trata-se da execução do algoritmo no problema
de entrada. Neste trabalho, uma nova hiper-heurística foi desenvolvida para a otimização de
algoritmos considerando um dado problema. Esta solução visa prover algoritmos otimizados que
sejam adequados para o problema dado e reduzir o custo computacional do processo de geração
significativamente quando comparado ao de outras hiper-heurísticas. A hiper-heurística proposta
combina uma abordagem de seleção de algoritmos com uma hiper-heurística de geração. A hiperheurística
de geração é responsável por criar uma base de conhecimento, que contém algoritmos
que foram gerados para um conjunto de problemas. Uma vez que esta base de conhecimento
esteja disponível, ela é usada como fonte de algoritmos a serem recomendados pela abordagem de
seleção de algoritmos. A ideia é reusar algoritmos previamente construídos pela hiper-heurística
de geração em problemas similares. Vale salientar que a criação de hiper-heurísticas visando
reduzir o custo de geração de algoritmos sem comprometer a qualidade destes algoritmos não foi
estudada na literatura. Além disso, hiper-heurísticas híbridas que combinam de abordagens de
seleção de algoritmos e hiper-heurísticas de geração para a otimização de algoritmos, proposta
nesta tese, é novidade. Para avaliar o algoritmo proposto, foi considerada como estudo de caso
a otimização do algoritmo baseado em enxames (PSO). Nos experimentos realizados, foram
considerados 32 problemas de otimização. O algoritmo proposto foi avaliado quanto à sua
capacidade de recomendar bons algoritmos para problemas de entrada, se estes algoritmos
atingem resultados competitivos frente à literatura. Além disso, o sistema foi avaliado quanto à
sua precisão na recomendação, ou seja, se o algoritmo recomendado seria, de fato, o melhor a
ser selecionado. Os resultados mostraram que a hiper-heurística proposta é capaz de recomendar
algoritmos úteis para os problemas de entrada e de forma eficiente. Adicionalmente, os algoritmos
recomendados atingiram resultados competitivos quando comparados com algoritmos estado da
arte e a recomendação dos algoritmos atingiu um alto percentual de precisão. / Designing an algorithm or heuristic to solve a given problem is a challenging task due to the
variety of possible design choices and the lack of clear guidelines on how to choose and/or
combine them. For instance, the performance of an optimization algorithm depends on the
designofitssearchoperatorsaswellasanadequatesettingofspecifichyper-parameters,eachof
them with many possible options to choose from. Because of that, there is a growing research
interest in automating the design of algorithms by exploring mainly optimization and machine
learningapproaches,aimingtomakethealgorithmdesignprocessmoreindependentfromhuman
interaction. Different approaches have dealt with the task of optimizing algorithms as another
(meta)optimization problem. These approaches are commonly called hyper-heuristics, where
each solution of the search space is a possible algorithm. Initially, hyper-heuristics were applied
for the selection of parameters in a predefined and limited search space. Nonetheless, recently,
generation hyper-heuristics have been developed to generate algorithms from a set of specified
components and functions. Generation hyper-heuristics are considered more flexible than the
selection ones due to its capacity to create new and customized algorithms for a given problem.
Hyper-heuristics have been widely used for the optimization of meta-heuristics. However, the
search process becomes expensive because the evaluation of each solution depends on the
execution of an algorithm in a problem. In this work, a novel hyper-heuristic was developed
to optimize algorithms considering a given problem. The proposed approach aims to provide
optimizedalgorithmsfortheinputproblemandreducethecomputationalcostoftheoptimization
process significantly when compared to other hyper-heuristics. The proposed hyper-heuristics
combines an automated algorithm selection method with a generation hyper-heuristic. The
generation hyper-heuristic is responsible for the creation of the knowledge base, which contains
previously built algorithms for a set of problems. Once the knowledge base is available, it
is used as a source of algorithms to be recommended by the automated algorithm selection
method. The idea is to reuse the algorithms already built by the generation hyper-heuristic on
similar problems. It is worth mentioning that the creation of hyper-heuristics aiming to reduce
the cost of the algorithm generation without harming the quality of these algorithms were not
studied yet. Besides, hybrid hyper-heuristics which combine an algorithm selection approach
with a generation hyper-heuristic for the algorithm optimization, proposed in this thesis, are a
novelty. To evaluate the proposed algorithm, it was considered as case study the optimization
of the Particle Swarm Optimization algorithm (PSO). In our experiments, we considered 32
optimizationproblems.Theproposedsystemwasevaluatedregardingitscapacitytorecommend
adequate algorithms for an input problem, the quality of the recommended algorithms, and,
finally, regarding its accuracy to recommend algorithms. The results showed that the proposed
system recommends useful algorithms for the input problem. Besides, the algorithms achieved
competitive results when compared to state-of-the-art algorithms, and also, the system presented
a high percentage of accuracy in the recommendation.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/18703 |
| Date | 22 August 2016 |
| Creators | MIRANDA, Pericles Barbosa Cunha de |
| Contributors | http://lattes.cnpq.br/2984888073123287, PRUDÊNCIO, Ricardo Bastos Cavalcante |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.0042 seconds