Made available in DSpace on 2015-03-03T15:47:46Z (GMT). No. of bitstreams: 1
LeonardoCTB_DISSERT.pdf: 2119704 bytes, checksum: 5bdd21de8bfa668bba821593cdd5289f (MD5)
Previous issue date: 2011-02-07 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Multi-objective combinatorial optimization problems have peculiar characteristics that
require optimization methods to adapt for this context. Since many of these problems are
NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many
different approaches using Ant Colony Optimization (ACO) have been proposed. In this
work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared
to two other optimizers found in the literature. A set of 18 instances from two
distinct types of graphs are used, as well as a specific multiobjective performance assessment
methodology. Initial experiments showed that the proposed algorithm is able
to generate better approximation sets than the other optimizers for all instances. In the
second part of this work, an experimental analysis is conducted, using several different
multiobjective ACO proposals recently published and the same instances used in the first
part. Results show each type of instance benefits a particular type of instance benefits a
particular algorithmic approach. A new metaphor for the development of multiobjective
ACOs is, then, proposed. Usually, ants share the same characteristics and only few works
address multi-species approaches. This works proposes an approach where multi-species
ants compete for food resources. Each specie has its own search strategy and different
species do not access pheromone information of each other. As in nature, the successful
ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced
here shows to be able to inherit the behavior of strategies that are successful
for different types of problems. Results of computational experiments are reported and
show that the proposed approach is able to produce significantly better approximation
sets than other methods / Problemas de otimiza??o combinat?ria multiobjetivo apresentam caracter?sticas peculiares
que exigem que t?cnicas de otimiza??o se adaptem a esse contexto. Como muitos
desses problemas s?o NP-?rduos, o uso de metaheur?sticas tem crescido nos ?ltimos anos.
Particularmente, muitas abordagens que utilizam a Otimiza??o por Col?nias de Formigas
t?m sido propostas. Neste trabalho, prop?e-se um algoritmo baseado em col?nias de formigas
para o Problema do Caminho mais Curto Multiobjetivo, e compara-se o algoritmo
proposto com dois otimizadores encontrados na literatura. Um conjunto de 18 inst?ncias
oriundas de dois tipos de grafos ? utilizado, al?m de uma metodologia espec?fica para a
avalia??o de otimizadores multiobjetivo. Os experimentos iniciais mostram que o algoritmo
proposto consegue gerar conjuntos de aproxima??o melhores que os demais otimizadores
para todas as inst?ncias. Na segunda parte do trabalho, uma an?lise experimental de diferentes
abordagens publicadas para col?nias de formigas multiobjetivo ? realizada, usando
as mesmas inst?ncias. Os experimentos mostram que cada tipo de inst?ncia privilegia uma
abordagem algor?tmica diferente. Uma nova met?fora para o desenvolvimento deste tipo
de metaheur?stica ? ent?o proposta. Geralmente, formigas possuem caracter?sticas comuns
e poucos artigos abordam o uso de m?ltiplas esp?cies. Neste trabalho, uma abordagem
com m?ltiplas esp?cies competindo por fontes de comida ? proposta. Cada esp?cie possui
sua pr?pria estrat?gia de busca e diferentes esp?cies n?o tem acesso ? informa??o dada
pelo ferom?nio das outras. Como na natureza, as popula??es de formigas bem sucedidas
tem a chance de crescer, enquanto as demais se reduzem. A abordagem apresentada aqui
mostra-se capaz de herdar o comportamento de estrat?gias bem-sucedidas em diferentes
tipos de inst?ncias. Resultados de experimentos computacionais s?o relatados e mostram
que a abordagem proposta produz conjuntos de aproxima??o significativamente melhores
que os outros m?todos
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/18682 |
| Date | 07 February 2011 |
| Creators | Bezerra, Leonardo Cesar Teon?cio |
| Contributors | CPF:81652011749, http://lattes.cnpq.br/2888641121265608, Goldbarg, Marco C?sar, CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Canuto, Anne Magaly de Paula, CPF:66487099449, http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4790093J8, Buriol, Luciana Salete, Gouv?a, Elizabeth Ferreira |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0027 seconds