551 |
[en] NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM / [pt] NOVAS HEURÍSTICAS E UMA ABORDAGEM POR PROGRAMAÇÃO INTEIRA PARA UM PROBLEMA DE CORRESPONDÊNCIA INEXATA DE GRAFOSALEXANDRE ROCHA DUARTE 26 March 2004 (has links)
[pt] Esta dissertação apresenta novos algoritmos aproximados e
uma abordagem exata para a resolução de um problema de
correspondência inexata de grafos. O problema considerado é
o de correspondência entre um grafo representando um modelo
genérico e outro representando dados a serem reconhecidos.
Assumi-se que o grafo dos dados possui mais vértices que o
do modelo. A motivação para o estudo desse problema vem de
problemas de reconhecimento de cenas, que consistem na
caracterização dos objetos envolvidos em uma determinada
cena, assim como das relações existentes entre eles. Uma
aplicação para este problema na área de reconhecimento de
imagens médicas é a de efetuar-se o reconhecimento de
estruturas 3D do cérebro humano, a partir de imagens
obtidas por ressonância magnética. Tais imagens são
previamente processadas por algum método de segmentação
automática e o processo de reconhecimento consiste na busca
da correspondência estrutural entre a imagem e um modelo
genérico, tipicamente definido como um atlas de imagens
médicas. Foram propostos novos algoritmos aproximados, tais
como um algoritmo construtivo guloso aleatorizado, um
procedimento de reconexão de caminhos e um GRASP que
combina estes com uma técnica de busca local. Além disso,
foi proposta uma formulação original do problema como um
problema de programação linear inteira, que permitiu a
resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and
an exact approach to the solution of an inexact graph
matching problem. The problem consists in finding the best
match between a generic model graph and a graph
representing an image, the latter with more nodes than the
former. The motivation for studying this problem comes from
a scene recognition problem, which consists in
characterizing objects involved in a given scene and the
relationships between them. An application of this problem
appears in the analysis of medical images and consists in
recognizing 3-dimensional structures in the human brain
using images obtained by magnetic resonance. Such images
must be previously processed by an automatic segmentation
method and the recognition process consists in the search
of an structural matching between the image and a generic
model, typically defined as an atlas of medical images.
New heuristics are proposed, such as a greedy randomized
construction algorithm, a path relinking procedure and a
GRASP heuristic that combines them with a local search
technique. Furthermore, an original integer formulation
of the problem based on integer multicommodity flows is
proposed, which makes possible the exact solution of medium-
sized instances.
|
552 |
Méthodes de décomposition pour la résolution des PCSP (Partial Constraint Satisfaction Problem) : application aux problèmes FAP et coloration de graphes / Decomposition methods for solving PCSP (Partial Constraint Satisfaction Problem) : application to FAP and graph coloring problemsSadeg, Lamia 30 October 2016 (has links)
Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem
|
553 |
Optimization and Scheduling on Heterogeneous CPU/FPGA Architecture with Communication Delays / Optimisation et ordonnancement sur une architecture hétérogène CPU/FPGA avec délais de communicationAbdallah, Fadel 21 December 2017 (has links)
Le domaine de l'embarqué connaît depuis quelques années un essor important avec le développement d'applications de plus en plus exigeantes en calcul auxquels les architectures traditionnelles à base de processeurs (mono/multi cœur) ne peuvent pas toujours répondre en termes de performances. Si les architectures multiprocesseurs ou multi cœurs sont aujourd'hui généralisées, il est souvent nécessaire de leur adjoindre des circuits de traitement dédiés, reposant notamment sur des circuits reconfigurables, permettant de répondre à des besoins spécifiques et à des contraintes fortes particulièrement lorsqu'un traitement temps-réel est requis. Ce travail présente l'étude des problèmes d'ordonnancement dans les architectures hétérogènes reconfigurables basées sur des processeurs généraux (CPUs) et des circuits programmables (FPGAs). L'objectif principal est d'exécuter une application présentée sous la forme d'un graphe de précédence sur une architecture hétérogène CPU/FPGA, afin de minimiser le critère de temps d'exécution total ou makespan (Cmax). Dans cette thèse, nous avons considéré deux cas d'étude : un cas d'ordonnancement qui tient compte des délais d'intercommunication entre les unités de calcul CPU et FPGA, pouvant exécuter une seule tâche à la fois, et un autre cas prenant en compte le parallélisme dans le FPGA, qui peut exécuter plusieurs tâches en parallèle tout en respectant la contrainte surfacique. Dans un premier temps, pour le premier cas d'étude, nous proposons deux nouvelles approches d'optimisation, GAA (Genetic Algorithm Approach) et MGAA (Modified Genetic Algorithm Approach), basées sur des algorithmes génétiques. Nous proposons également de tester un algorithme par séparation et évaluation (méthode Branch & Bound). Les approches GAA et MGAA proposées offrent un très bon compromis entre la qualité des solutions obtenues (critère d'optimisation de makespan) et le temps de calcul nécessaire à leur obtention pour résoudre des problèmes à grande échelle, en comparant à la méthode par séparation et évaluation (Branch & Bound) proposée et l'autre méthode exacte proposée dans la littérature. Dans un second temps, pour le second cas d'étude, nous avons proposé et implémenté une méthode basée sur les algorithmes génétiques pour résoudre le problème du partitionnement temporel dans un circuit FPGA en utilisant la reconfiguration dynamique. Cette méthode fournit de bonnes solutions avec des temps de calcul raisonnables. Nous avons ensuite amélioré notre précédente approche MGAA afin d'obtenir une nouvelle approche intitulée MGA (Multithreaded Genetic Algorithm), permettent d'apporter des solutions au problème de partitionnement. De plus, nous avons également proposé un algorithme basé sur le recuit simulé, appelé MSA (Multithreaded Simulated Annealing). Ces deux approches proposées, basées sur les méthodes métaheuristiques, permettent de fournir des solutions approchées dans un intervalle de temps très raisonnable aux problèmes d'ordonnancement et de partitionnement sur système de calcul hétérogène / The domain of the embedded systems becomes more and more attractive in recent years with the development of increasing computationally demanding applications to which the traditional processor-based architectures (either single or multi-core) cannot always respond in terms of performance. While multiprocessor or multicore architectures have now become generalized, it is often necessary to add to them dedicated processing circuits, based in particular on reconfigurable circuits, to meet specific needs and strong constraints, especially when real-time processing is required. This work presents the study of scheduling problems into the reconfigurable heterogeneous architectures based on general processors (CPUs) and programmable circuits (FPGAs). The main objective is to run an application presented in the form of a Data Flow Graph (DFG) on a heterogeneous CPU/FPGA architecture in order to minimize the total running time or makespan criterion (Cmax). In this thesis, we have considered two case studies: a scheduling case taking into account the intercommunication delays and where the FPGA device can perform a single task at a time, and another case taking into account parallelism in the FPGA, which can perform several tasks in parallel while respecting the constraint surface. First, in the first case, we propose two new optimization approaches GAA (Genetic Algorithm Approach) and MGAA (Modified Genetic Algorithm Approach) based on genetic algorithms. We also propose to compare these algorithms to a Branch & Bound method. The proposed approaches (GAA and MGAA) offer a very good compromise between the quality of the solutions obtained (optimization makespan criterion) and the computational time required to perform large-scale problems, unlike to the proposed Branch & Bound and the other exact methods found in the literature. Second, we first implemented an updated method based on genetic algorithms to solve the temporal partitioning problem in an FPGA circuit using dynamic reconfiguration. This method provides good solutions in a reasonable running time. Then, we improved our previous MGAA approach to obtain a new approach called MGA (Multithreaded Genetic Algorithm), which allows us to provide solutions to the partitioning problem. In addition, we have also proposed an algorithm based on simulated annealing, called MSA (Multithreaded Simulated Annealing). These two proposed approaches which are based on metaheuristic methods provide approximate solutions within a reasonable time period to the scheduling and partitioning problems on a heterogeneous computing system
|
554 |
[en] HEURISTICS FOR THE PROBLEM OF DNA SEQUENCING BY HYBRIDIZATION / [pt] HEURÍSTICAS PARA O PROBLEMA DE SEQÜÊNCIAMENTO DE DNA POR HIBRIDAÇÃOERALDO LUIS REZENDE FERNANDES 04 May 2005 (has links)
[pt] O seqüenciamento por hibridação é uma alternativa
interessante para a tarefa
de seqüenciamento de DNA. Este método ainda está sendo
aperfeiçoado
e pode superar as técnicas utilizadas em termos de tempo e
custo. Uma
etapa crucial do método consiste em resolver um problema
combinatório
que pode ser formulado como um caso especial do problema do
caixeiro viajante
com coleta de prêmios. Neste trabalho, propõe-se uma nova
heurística
construtiva multi-partida para resolver este problema. Uma
estratégia de
aprendizado baseada em uma memória adaptativa e um
procedimento de
construção de vocabulário são utilizados para melhorar o
desempenho da
heurística multi-partida. A memória adaptativa é utilizada
para intensificar as construções de novas soluções com os
elementos que aparecem com
uma freqüência maior nas melhores soluções encontradas
anteriormente pela
heurística multi-partida. O procedimento de construção de
vocabulário consiste
em construir novas soluções através da combinação de partes
comuns a
boas soluções. Testes computacionais mostraram que estas
duas estratégias
aumentam significativamente o desempenho da heurística
multi-partida e
são particularmente indicadas para problemas de
escalonamento nos quais
as melhores soluções são na maioria dos casos formadas por
blocos de elementos
que aparecem juntos com muita freqüência. A heurística
proposta
supera os resultados dos melhores algoritmos encontrados na
literatura,
tanto em termos da qualidade das soluções encontradas, como
do tempo
de computação. / [en] Sequencing by hybridization is an attractive alternative
for DNA sequencing.
This novel method can be less time and cost consuming than
the techniques
applied nowadays. A very important step of this method is
to solve
a combinatorial problem formulated as a special case of the
prize-collecting
traveling salesman problem. In this work, we propose a new
multistart construtive
heuristic to solve this problem. A learning strategy based
on adaptive
memory and a vocabulary building procedure are used to
improve the
performance of the multistart heuristic. The adaptive
memory is used to
intensify the construction of new solutions with the
elements that appear
frequently in the best solutions previously found by the
multistart heuristic.
The objective of the vocabulary building procedure is to
construct new
solutions combining parts of good solutions. Computational
experiments
have shown that these two methods significantly improves
the performance
of the multistart heuristic and are particularly suitable
for scheduling problems
whose best solutions are in most cases built by blocks of
elements that
appear together very often. The proposed heuristic obtains
systematically
better solutions and is less time consuming than the best
algorithms found
in the literature.
|
555 |
Solutions optimales des problèmes de recouvrement sous contraintes sur le degré des nœuds / Optimal solutions of problems of finding spanning tree with constraints on the degree of the nodesMerabet, Massinissa 05 December 2014 (has links)
Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires. / The work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs.
|
556 |
Algoritmos baseados em colônia de formigas para otimização multiobjetivo / Ant colony algorithms for multi-objective optimizationAngelo, Jaqueline da Silva 24 July 2008 (has links)
Made available in DSpace on 2015-03-04T18:51:05Z (GMT). No. of bitstreams: 1
Dissert_MSc_JaquelineAngelo.pdf: 926474 bytes, checksum: da4b07a3aac6c41fe497e0351128bde1 (MD5)
Previous issue date: 2008-07-24 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / This dissertation presents the BicriterionAnt, MACS and MONACO Ant Colony algorithms, available in literature, to solve the Multi-Objective Traveling Salesman Problem (MOTSP). The characteristics of the problem and of each
algorithm used are presented. Those algorithms were tested in six bi-objective instances of MOTSP. Changes in the original algorithms were implemented to try to produce better results than the original ones. To validate the results and to measure the quality of the solutions, metrics of performance were used which help to identify the best non-dominated solution sets. / Esta dissertação apresenta os algoritmos BicriterionAnt, MACS e MONACO,
disponíveis na literatura, baseados em colônia de formigas, para resolução do
Problema do Caixeiro Viajante Multiobjetivo (PCVMO). São apresentadas as
características do problema e de cada algoritmo utilizado. Estes algoritmos foram
testados em seis instâncias bi-objetivo do PCVMO. Foram implementadas algumas alterações na estrutura original dos algoritmos na tentativa de produzir resultados melhores do que os algoritmos originais. Para a avaliação dos resultados e medição da qualidade das soluções, foram utilizadas métricas de desempenho que auxiliam na identificação dos melhores conjuntos de soluções não-dominadas.
|
557 |
Abordagem neuro-genética para mapeamento de problemas de conexão em otimização combinatória / Neurogenetic approach for mapping connection problems in combinatorial optimizationPires, Matheus Giovanni 21 May 2009 (has links)
Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.
|
558 |
PCAISO-GT: uma metaheurística co-evolutiva paralela de otimização aplicada ao problema de alocação de berçosOliveira, Carlos Eduardo de Jesus Guimarães 24 March 2013 (has links)
Submitted by Maicon Juliano Schmidt (maicons) on 2015-03-30T11:51:21Z
No. of bitstreams: 1
Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5) / Made available in DSpace on 2015-03-30T11:51:21Z (GMT). No. of bitstreams: 1
Carlos Eduardo de Jesus Guimarães Oliveira.pdf: 1236896 bytes, checksum: ef9d04e6f25aee7908b56a622411bc74 (MD5)
Previous issue date: 2014-01-31 / Nenhuma / Este trabalho apresenta um algoritmo de otimização baseado na metaheurística dos Sistemas Imunológicos Artificiais, princípios de Teoria dos Jogos, Co-evolução e Paralelização. Busca-se a combinação adequada dos conceitos de Teoria dos Jogos, Co-evolução e Paralelização aplicados ao algoritmo AISO (Artificial Immune System Optimization) para resolução do Problema de Alocação de Berços (PAB). Dessa maneira, o algoritmo é formalizado a partir das técnicas citadas, formando o PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Inicialmente, foram realizados experimentos visando à sintonia dos parâmetros empregados nas diferentes versões da ferramenta desenvolvida. Com base nas melhores configurações identificadas, foram realizados experimentos de avaliação através da solução de um conjunto de instâncias do PAB. Os resultados obtidos permitiram a indicação da versão co-evolutiva associada à teoria dos jogos como a melhor para solução do problema em estudo. / This paper presents an optimization algorithm based on metaheuristic of Artificial Immune Systems, principles of Game Theory, Co-evolution and parallelization. The objective is find the appropriate combination of the concepts of Game Theory, Co-evolution and Parallelization applied to AISO algorithm (Artificial Immune System Optimization) for solving the Berth Allocation Problem (BAP). Thus, the algorithm is formalized from the above mentioned techniques, forming the PCAISO-GT: Parallel Coevolutionary Artificial Immune System Optimization with Game Theory. Initially, experiments aiming to tune the parameters were performed using different versions of the tool developed. Based on the identified best settings, evaluation experiments were carried out by solving a set of instances of the PAB. The results obtained allowed the appointment of co-evolutionary version associated with game theory as the best solution to the problem under study.
|
559 |
Abordagem metaheurística híbrida para otimização do planejamento de estiva de navios porta-contêineresGonçalves Júnior, Joel da Silva 07 March 2016 (has links)
Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2016-06-10T15:26:09Z
No. of bitstreams: 1
Joel da Silva Gonçalves Júnior_.pdf: 1935811 bytes, checksum: 2c6b67ad91c1de26271d67142ef7721b (MD5) / Made available in DSpace on 2016-06-10T15:26:09Z (GMT). No. of bitstreams: 1
Joel da Silva Gonçalves Júnior_.pdf: 1935811 bytes, checksum: 2c6b67ad91c1de26271d67142ef7721b (MD5)
Previous issue date: 2016-03-07 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O transporte marítimo mercante desempenha um papel fundamental para a economia de uma nação, ligando a produção ao consumo. No cenário de expansão do transporte marítimo, a utilização de contêineres para organização das cargas confere maior facilidade, segurança e rapidez ao transporte, aumentando, assim, a produtividade dos terminais e dos navios. No entanto, a operação de navios porta-contêineres possui limitações de movimentação e de estabilidade que impactam no custo operacional de um terminal portuário. Como os guindastes só podem acessar as pilhas de contêineres a partir do topo, a realização de remoções desnecessárias de contêineres bloqueantes gera um custo adicional de movimentação e de tempo nas operações de carga e descarga. Desta forma, faz-se necessária a elaboração de um plano de estiva eficiente para estas atividades, minimizando tanto os remanejamentos quanto a instabilidade da embarcação. Este estudo propõe uma abordagem híbrida, elaborada através da combinação das metaheurísticas Algoritmo Genético e Busca Tabu, utilizando a codificação da solução baseada em regras, a fim de elaborar uma ferramenta computacional que faça a gestão do número de remanejamentos e da instabilidade da embarcação, que são objetivos conflitantes. Nos experimentos, as metaheurísticas puras foram comparadas ao algoritmo híbrido e os resultados comprovaram que a aplicação hibridizada apresenta uma eficiência maior do que as metaheurísticas puras. As diferentes configurações de regras assumidas mostraram que a proposta de um número maior de regras, em complemento àquelas propostas na literatura, implica em melhores resultados. Através da aplicação da abordagem com múltiplos objetivos, foi possível observar a importância de considerar a movimentação e a estabilidade no plano de estiva. Com os resultados obtidos, demonstrou-se que o uso da abordagem proposta gera soluções melhores que as encontradas até o momento na literatura. / The merchant shipping perform a fundamental role in the economy of a nation, by linking production to consumption. In shipping expansion scenario, the use of containers for cargo organizing provides greater facility, safety and velocity, thus increasing the productivity of terminals and ships. However, the use of container ships has handling and stability limitations that affect the operating cost of a port terminal. As the cranes can only access the container stacks from the top, carrying out unnecessary removals of blocking containers generates an additional cost of handling and time in loading and unloading operations. Thus, it is necessary to elaborate an efficient stowage plan for loading and unloading operations, minimizing both the shifting and the instability of the vessel. This study proposes an hybrid approach developed by the combination of Genetic Algorithms and Tabu Search metaheuristics, using a rules-based encoding for solution representation, in order to create a computational tool that manage both the rehandling and instability, which are conflicting. In the experiments, pure metaheuristics were compared to the hybrid algorithm and the results demonstrate that the hybridization presents greater efficiency than the pure metaheuristics. The different rules configuration have proven that the proposal of a greater number of rules, in addition to those proposed in the literature, implies better results. The application of a multiple objectives approach has proven the importance of considering the handling and stability in the stowage plan. With the results, it was showed that the use of the proposed approach produces better solutions than those found in the literature.
|
560 |
Scalable cost-efficient placement and chaining of virtual network functions / Posicionamento e encadeamento escalável e baixo custo de funções virtualizados de redeLuizelli, Marcelo Caggiani January 2017 (has links)
A Virtualização de Funções de Rede (NFV – Network Function Virtualization) é um novo conceito arquitetural que está remodelando a operação de funções de rede (e.g., firewall, gateways e proxies). O conceito principal de NFV consiste em desacoplar a lógica de funções de rede dos dispositivos de hardware especializados e, desta forma, permite a execução de imagens de software sobre hardware de prateleira (COTS – Commercial Off-The-Shelf). NFV tem o potencial para tornar a operação das funções de rede mais flexíveis e econômicas, primordiais em ambientes onde o número de funções implantadas pode chegar facilmente à ordem de centenas. Apesar da intensa atividade de pesquisa na área, o problema de posicionar e encadear funções de rede virtuais (VNF – Virtual Network Functions) de maneira escalável e com baixo custo ainda apresenta uma série de limitações. Mais especificamente, as estratégias existentes na literatura negligenciam o aspecto de encadeamento de VNFs (i.e., objetivam sobretudo o posicionamento), não escalam para o tamanho das infraestruturas NFV (i.e., milhares de nós com capacidade de computação) e, por último, baseiam a qualidade das soluções obtidas em custos operacionais não representativos. Nesta tese, aborda-se o posicionamento e o encadeamento de funções de rede virtualizadas (VNFPC – Virtual Network Function Placement and Chaining) como um problema de otimização no contexto intra- e inter-datacenter. Primeiro, formaliza-se o problema VNFPC e propõe-se um modelo de Programação Linear Inteira (ILP) para resolvêlo. O objetivo consiste em minimizar a alocação de recursos, ao mesmo tempo que atende aos requisitos e restrições de fluxo de rede. Segundo, aborda-se a escalabilidade do problema VNFPC para resolver grandes instâncias do problema (i.e., milhares de nós NFV). Propõe-se um um algoritmo heurístico baseado em fix-and-optimize que incorpora a meta-heurística Variable Neighborhood Search (VNS) para explorar eficientemente o espaço de solução do problema VNFPC. Terceiro, avalia-se as limitações de desempenho e os custos operacionais de estratégias típicas de aprovisionamento ambientes reais de NFV. Com base nos resultados empíricos coletados, propõe-se um modelo analítico que estima com alta precisão os custos operacionais para requisitos de VNFs arbitrários. Quarto, desenvolve-se um mecanismo para a implantação de encadeamentos de VNFs no contexto intra-datacenter. O algoritmo proposto (OCM – Operational Cost Minimization) baseia-se em uma extensão da redução bem conhecida do problema de emparelhamento ponderado (i.e., weighted perfect matching problem) para o problema de fluxo de custo mínimo (i.e., min-cost flow problem) e considera o desempenho das VNFs (e.g., requisitos de CPU), bem como os custos operacionais estimados. Os resultados alcaçados mostram que o modelo ILP proposto para o problema VNFPC reduz em até 25% nos atrasos fim-a-fim (em comparação com os encadeamentos observados nas infra-estruturas tradicionais) com um excesso de provisionamento de recursos aceitável – limitado a 4%. Além disso, os resultados evidenciam que a heurística proposta (baseada em fix-and-optimize) é capaz de encontrar soluções factíveis de alta qualidade de forma eficiente, mesmo em cenários com milhares de VNFs. Além disso, provê-se um melhor entendimento sobre as métricas de desempenho de rede (e.g., vazão, consumo de CPU e capacidade de processamento de pacotes) para as estratégias típicas de implantação de VNFs adotadas infraestruturas NFV. Por último, o algoritmo proposto no contexto intra-datacenter (i.e. OCM) reduz significativamente os custos operacionais quando comparado aos mecanismos de posicionamento típicos uti / Network Function Virtualization (NFV) is a novel concept that is reshaping the middlebox arena, shifting network functions (e.g. firewall, gateways, proxies) from specialized hardware appliances to software images running on commodity hardware. This concept has potential to make network function provision and operation more flexible and cost-effective, paramount in a world where deployed middleboxes may easily reach the order of hundreds. Despite recent research activity in the field, little has been done towards scalable and cost-efficient placement & chaining of virtual network functions (VNFs) – a key feature for the effective success of NFV. More specifically, existing strategies have neglected the chaining aspect of NFV (focusing on efficient placement only), failed to scale to hundreds of network functions and relied on unrealistic operational costs. In this thesis, we approach VNF placement and chaining as an optimization problem in the context of Inter- and Intra-datacenter. First, we formalize the Virtual Network Function Placement and Chaining (VNFPC) problem and propose an Integer Linear Programming (ILP) model to solve it. The goal is to minimize required resource allocation, while meeting network flow requirements and constraints. Then, we address scalability of VNFPC problem to solve large instances (i.e., thousands of NFV nodes) by proposing a fixand- optimize-based heuristic algorithm for tackling it. Our algorithm incorporates a Variable Neighborhood Search (VNS) meta-heuristic, for efficiently exploring the placement and chaining solution space. Further, we assess the performance limitations of typical NFV-based deployments and the incurred operational costs of commodity servers and propose an analytical model that accurately predict the operational costs for arbitrary service chain requirements. Then, we develop a general service chain intra-datacenter deployment mechanism (named OCM – Operational Cost Minimization) that considers both the actual performance of the service chains (e.g., CPU requirements) as well as the operational incurred cost. Our novel algorithm is based on an extension of the well-known reduction from weighted matching to min-cost flow problem. Finally, we tackle the problem of monitoring service chains in NFV-based environments. For that, we introduce the DNM (Distributed Network Monitoring) problem and propose an optimization model to solve it. DNM allows service chain segments to be independently monitored, which allows specialized network monitoring requirements to be met in a efficient and coordinated way. Results show that the proposed ILP model for the VNFPC problem leads to a reduction of up to 25% in end-to-end delays (in comparison to chainings observed in traditional infrastructures) and an acceptable resource over-provisioning limited to 4%. Also, we provide strong evidences that our fix-and-optimize based heuristic is able to find feasible, high-quality solutions efficiently, even in scenarios scaling to thousands of VNFs. Further, we provide indepth insights on network performance metrics (such as throughput, CPU utilization and packet processing) and its current limitations while considering typical deployment strategies. Our OCM algorithm reduces significantly operational costs when compared to the de-facto standard placement mechanisms used in Cloud systems. Last, our DNM model allows finer grained network monitoring with limited overheads. By coordinating the placement of monitoring sinks and the forwarding of network monitoring traffic, DNM can reduce the number of monitoring sinks and the network resource consumption (54% lower than a traditional method).
|
Page generated in 0.0347 seconds