Orientador: Prof. Dr. Gustavo Sousa Pavani / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. / Algoritmos baseados em Otimização por Colonia de Formigas (Ant Colony Optimization { ACO) vem sendo usados com bastante sucesso no metaescalonamento distribuído e integrado dos recursos de computação e de comunicação em ambientes de grade computacional baseadas em redes opticas (lambda grid ). Nesse ambiente sao utilizados infraestruturas de comunicações compostas por enlaces de fibras opticas e nós opticos, que são elementos sujeitos aos mais variados tipos de falhas. Com efeito, problemas decorrentes dos equipamentos ou meios de transmissão podem interromper o trafego de informações e, consequentemente, causam a indisponibilidade de recursos na grade. A arquitetura proposta em [1] é capaz de gerenciar dinamicamente e de forma conjunta os recursos de rede e processamento no ambiente de lambda grid, além de prover agendamento e reserva futura desses recursos. Neste trabalho, considerar-se-à tambem a capacidade de sobrevivencia da grade sob condições adversas de falhas. Para tanto, a grade computacional deve prover mecanismos de restauração de forma a se recuperar em caso de falhas de enlace ou nó. Simulações foram realizadas com os diversos algoritmos de metaescalonamento propostos originalmente em [1], demonstrando o respectivo desempenho em termos de capacidade de restauração e de atraso de execução das tarefas restauradas. / Algorithms based on Ant Colony Optimization (ACO) have been successfully used in distributed and integrated meta-scheduling of computing and networking resources in lambda grids. The lambda grid environment is composed by optical fiber links and optical nodes, which are susceptible to diferent types of failure. In eect, problems due to equipment or transmission outages may interrupt the information trac and, consequently, cause unavailability of grid resources. The architecture proposed in [1] is capable of the dynamic, joint management of networking and processing resources at the lambda grid. It can also provide scheduling and advance reservation of those resources. In this work, we also consider the survivability capacity of the lambda grid when a failure occurs. Therefore, the lambda grid has to provide a restoration mechanism in order to recover from link and node failures. Simulations carried with the meta-scheduling algorithms originally proposed in [1] demonstrate their performance in terms of restorability and delay in scheduling the restored tasks.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-12-21T10:50:23Z No. of bitstreams: 1 flaviarodriguesdonascimento.pdf: 1211614 bytes, checksum: ab9ba99ac0572dc9242451b399b808c5 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-12-22T12:00:31Z (GMT) No. of bitstreams: 1 flaviarodriguesdonascimento.pdf: 1211614 bytes, checksum: ab9ba99ac0572dc9242451b399b808c5 (MD5) / Made available in DSpace on 2016-12-22T12:00:31Z (GMT). No. of bitstreams: 1 flaviarodriguesdonascimento.pdf: 1211614 bytes, checksum: ab9ba99ac0572dc9242451b399b808c5 (MD5) Previous issue date: 2011-09-15 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A programação diária da operação de sistemas termoelétricos de geração consiste em determinar uma estratégia de despacho das unidades geradoras para atender a demanda de energia, satisfazendo as restrições operacionais e funcionais do sistema elétrico de potência. O problema pode ser dividido em dois subproblemas: (i) referente à determinação das unidades que devem estar em operação mediante a demanda solicitada, “Thermal Unit Commitment” e (ii) referente à determinação da potência gerada por cada uma das unidades colocadas em serviço, “Despacho Econômico”. Devido à variação de carga ao longo do tempo, a programação da operação envolve decisões do sistema de geração a cada hora, dentro do horizonte de um dia a duas semanas. Os estudos relacionados às técnicas de otimização bio-inspiradas, utilizadas na resolução da programação diária da operação de sistemas termoelétricos de geração, apontam que a combinação entre os métodos computacionais biologicamente inspirados com outras técnicas de otimização tem papel importante na obtenção de melhores soluções em um menor tempo de processamento. Seguindo esta linha de pesquisa, o presente trabalho faz uso de uma metodologia baseada na otimização por colônia de formiga para a minimização do custo da programação diária de operação de unidades termoelétricas. O modelo proposto utiliza uma Matriz de Sensibilidade (MS) baseada nas informações fornecidas pelos multiplicadores de Lagrange a fim de melhorar o processo de busca bio-inspirado. Desta forma, um percentual dos indivíduos da colônia faz uso destas informações no processo evolutivo da colônia. Os resultados alcançados através das simulações indicam que a utilização da MS resulta em soluções de qualidade com um número reduzido de indivíduos. / The daily schedule of thermoelectric systems consists of determining the strategy to set the generation units to be put in operation to meet the load, meeting also the operational and functional constraints of the respective power system. This problem can be split into two subproblems: (i) schedule of units that must operate in accordance with a given load, or Thermal Unit Commitment and (ii) set the power generation for each committed unit, or Economical Schedule. Due to load variations the schedule involves hourly generation decisions, in a horizon that varies from one day to two weeks. Researches related to bio-inspired optimization strategies applied to the daily thermal system operation show that the combination between bio-inspired computing techniques and other optimization methods has an important role in order to obtain better solutions in a shorter computing time. Following this, the present work makes use of a methodology based on Ant Colony Optimization to minimize the costs of the thermal system daily scheduling. This proposed method uses a Sensitivity Matrix (SM) based on information from Lagrange Multipliers related to the problem in order to improve the bio-inspired process. In this way, a percentage of the individuals make use of the provided information in the colony evolution process. The results obtained through those simulations indicate that the use of the SM presents better quality solutions with a reduced number of individuals.

In this study, three different algorithms are implemented to solve thecapacitated vehicle routing problem with and without time windows:ant colony optimization, a genetic algorithm and a genetic algorithmwith self-organizing map. For the capacitated vehicle routing problemthe Augerat et al’s benchmark problems were used and for the capaci-tated vehicle routing problem with time windows the Solomon’sbenchmark problems. All three algorithms were tuned over thirtyinstances per problem with the tuners SPOT and ParamILS. The tuningresults from all instances were combined to the final parameter valuesand tested on a larger set of instances. The test results were used tocompare the algorithms and tuners against each other. The ant colonyoptimization algorithm outperformed the other algorithms on bothproblems when considering all instances. The genetic algorithm withself-organizing map found more best known solutions than any otheralgorithm when using parameters, on the capacitated vehicle routingproblem. The algorithms performed well and several new best knownresults were discovered for the capacitated vehicle routing problem andnew best solutions found by heuristics were discovered for the 100customer Solomon problems. When comparing the tuners they bothworked well and no clear winner emerged.

Particulièrement lors de collaborations dans le cadre de chaînes logistiques ou d'entreprises virtuelles, établir les workflows collaboratifs est une étape laborieuse car souvent réalisée soit de façon humaine, soit avec des méthodes manquant de flexibilité. Sur la base d'un réseau social d'entreprises, cette thèse vise à faciliter cette étape en proposant un service de déduction de processus collaboratifs inter-organisationnels. Cela soulève trois problèmes: (i) trouver les activités qui doivent être exécutées pour remplir les objectifs de la collaboration (Quoi?), (ii) sélectionner les partenaires pouvant réaliser ces activités (Qui?) et (iii) ordonner ces activités en un processus métier collaboratif (Quand?). Dans le cadre d'un réseau social, il est attendu que plusieurs organisations soient capables de fournir les mêmes activités. Dans un tel contexte de concurrence entre les organisations, une optimisation globale permet de trouver un processus final quasi-optimal, en prenant en compte ces trois questions de manière simultanée : trouver l'ensemble des "meilleurs" partenaires et leurs activités dans un contexte de collaboration spécifique. A cette fin, des ontologies de collaboration ont été développées et permettent de représenter et collecter des connaissances sur les collaborations. Ainsi, quand les utilisateurs remplissent leurs profils sur le réseau social, le système peut comprendre (i) les attentes des utilisateurs lorsqu'ils fournissent leurs objectifs de collaboration et (ii) les capacités qu'ils peuvent fournir. Un outil d'aide à la décision, basé sur un algorithme d'optimisation par colonies de fourmis permet ensuite d'exploiter les ontologies de collaboration afin de trouver un processus quasi-optimal répondant aux attentes et objectifs de la collaboration. Les résultats de cette thèse s'inscrivent au sein du projet FUI OpenPaaS dont le but est d'établir un nouveau réseau social d'entreprises visant à faciliter leurs collaborations intra et inter-organisationnelles. / Especially in the context of collaborative supply chains and virtual enterprises, the step of designing the collaborative workflows remains laborious because either it is still carried out humanly or the methods lack of flexibility. Based on an enterprise social network, this thesis aims at facilitating this step by proposing a service for the deduction of collaborative processes. It raises three main issues: (i) finding the activities to execute that answer the objectives of the collaboration (What?), (ii) selecting the corresponding partners (Who?) and (iii) ordering the activities into a collaborative business process (When?). Moreover, it is expected that many companies could be able to provide the same activities, on the enterprise social network. In this competitive context, a global optimization should be set up in order to find the quasi-optimal collaborative process that answer these three questions simultaneously. A three-dimensional solution is proposed here. First, a non-functional framework has been set up in order to determine the criteria that make a « good » partner in a specific collaborative context. Then, collaborative ontologies have been implemented and enable the representation and the acquisition of collaborative knowledge, so that the IT system can understand (a) the user's needs when they model their objectives of collaboration and (b) the user's capabilities when they model their profiles on the enterprise social network. And finally, a tool for decision support has been implemented thanks to an ant colony optimization algorithm that exploits the collaborative ontologies in order to provide a quasi-optimal process that fits the context of the collaboration and answers its objective. The results are in line with the FUI French project OpenPaaS which aims at offering an enterprise social network to facilitate their collaborations.

Topology design of distributed local area networks (DLANs) can be classified as an NP-hard problem. Intelligent algorithms, such as evolutionary and swarm intelligence techniques, are candidate approaches to address this problem and to produce desirable solutions. DLAN topology design consists of several conflicting objectives such as minimization of cost, minimization of network delay, minimization of the number of hops between two nodes, and maximization of reliability. It is possible to combine these objectives in a single-objective function, provided that the trade-offs among these objectives are adhered to. This thesis proposes a strategy and a new aggregation operator based on fuzzy logic to combine the four objectives in a single-objective function. The thesis also investigates the use of a number of evolutionary algorithms such as stochastic evolution, simulated evolution, and simulated annealing. A number of hybrid variants of the above algorithms are also proposed. Furthermore, the applicability of swarm intelligence techniques such as ant colony optimization and particle swarm optimization to topology design has been investigated. All proposed techniques have been evaluated empirically with respect to their algorithm parameters. Results suggest that simulated annealing produced the best results among all proposed algorithms. In addition, the hybrid variants of simulated annealing, simulated evolution, and stochastic evolution generated better results than their respective basic algorithms. Moreover, a comparison of ant colony optimization and particle swarm optimization shows that the latter generated better results than the former. / Thesis (PhD)--University of Pretoria, 2009. / Computer Science / unrestricted

Philosophiae Doctor - PhD / Wireless sensor networks (WSNs) have become a popular research area that is widely gaining the attraction from both the research and the practitioner communities due to their wide area of applications. These applications include real-time sensing for audio delivery, imaging, video streaming, and remote monitoring with positive impact in many fields such as precision agriculture, ubiquitous healthcare, environment protection, smart cities and many other fields. While WSNs are aimed to constantly handle more intricate functions such as intelligent computation, automatic transmissions, and in-network processing, such capabilities are constrained by their limited processing capability and memory footprint as well as the need for the sensor batteries to be cautiously consumed in order to extend their lifetime. This thesis revisits the issue of the energy efficiency in sensor networks by proposing a novel clustering approach for routing the sensor readings in wireless sensor networks. The main contribution of this dissertation is to 1) propose corrective measures to the traditional energy model adopted in current sensor networks simulations that erroneously discount both the role played by each node, the sensor node capability and fabric and 2) apply these measures to a novel hierarchical routing architecture aiming at maximizing sensor networks lifetime. We propose three energy models for sensor network: a) a service-aware model that account for the specific role played by each node in a sensor network b) a sensor-aware model and c) load-balancing energy model that accounts for the sensor node fabric and its energy footprint. These three models are complemented by a load-balancing model structured to balance energy consumption on the network of cluster heads that forms the backbone for any cluster-based hierarchical sensor network. We present two novel approaches for clustering the nodes of a hierarchical sensor network: a) a distance-aware clustering where nodes are clustered based on their distance and the residual energy and b) a service-aware clustering where the nodes of a sensor network are clustered according to their service offered to the network and their residual energy. These approaches are implemented into a family of routing protocols referred to as EOCIT (Energy Optimization using Clustering Techniques) which combines sensor node energy location and service awareness to achieve good network performance. Finally, building upon the Ant Colony Optimization System (ACS), Multipath Routing protocol based on Ant Colony Optimization approach for Wireless Sensor Networks (MRACO) is proposed as a novel multipath routing protocol that finds energy efficient routing paths for sensor readings dissemination from the cluster heads to the sink/base station of a hierarchical sensor network. Our simulation results reveal the relative efficiency of the newly proposed approaches compared to selected related routing protocols in terms of sensor network lifetime maximization.

In einer von Vernetzung und Globalisierung geprägten Umwelt wächst der Wettbewerbsdruck auf die Unternehmen am Markt stetig. Die effektive Nutzung der Ressourcen einerseits und die enge Zusammenarbeit mit Lieferanten und Kunden andererseits führen für nicht wenige Unternehmen des industriellen Sektors zu entscheidenden Wettbewerbsvorteilen, die das Fortbestehen jener Unternehmen am Markt sichern. Viele Unternehmen verstehen sich aus diesem Grund als Bestandteil so genannter Supply Chains. Die unternehmensübergreifende Steuerung und Optimierung des Wertschöpfungsprozesses stellt ein charakteristisches Problem des Supply Chain Managements dar und besitzt zur Erzielung von Wettbewerbsvorteilen hohes Potential. Produktionsnetzwerke sind ein wesentlicher Forschungsschwerpunkt der Professur für Produktionswirtschaft und Industriebetriebslehre an der TU Chemnitz. Das Extended Value Chain Management (EVCM) stellt ein kompetenzorientiertes Konzept für die Bildung und zum Betrieb hierarchieloser temporärer regionaler Produktionsnetzwerke im Sinne virtueller Unternehmen dar. Gegenstand dieser Arbeit ist ein diskretes Optimierungsproblem, dass einen mehrstufigen Entscheidungsprozesses unter Berücksichtigung mehrerer Ziele abbildet, der sich bei der Auswahl möglicher Partner in einem Produktionsnetzwerk nach dem Betreiberkonzept des EVCM ergibt. Da mehrere Zielstellungen bestehen, werden grundlegende Methoden der mehrkriteriellen Optimierung und Entscheidung erörtert. Neben der Vorstellung des Problems sollen mehrzielorientierte Ansätze im Sinne einer Pareto-Optimierung auf Basis des Dynamic Programmings als Verfahren zur Bestimmung von Optimallösungen sowie Ant Colony Optimization zur näherungsweisen Lösung vorgestellt werden. Darauf aufbauend werden verschiedene Möglichkeiten der Hybridisierung beider Methoden diskutiert. Die entwickelten Ansätze werden auf ihre Eignung im Rahmen der informationstechnischen Umsetzung des EVCM-Konzepts untersucht und einer Evaluierung unterzogen. Hierzu werden verschiedene Kennzahlen zur Beurteilung der Verfahren entwickelt. Die modellierten Algorithmen und entwickelten Konzepte beschränken sich nicht ausschließlich auf das betrachtete Problem, sondern können leicht auf Probleme mit ähnlichen Eigenschaften übertragen werden. Insbesondere das NP-vollständige mehrkriterielle Kürzeste-Wege-Problem stellt einen Spezialfall des behandelten Optimierungsproblems dar.

No description available.

This thesis focuses on applying one of the rapidly growing non-deterministic optimization algorithms, the ant colony algorithm, for simulating automatic hose/pipe routing with several conflicting objectives. Within the thesis, methods have been developed and applied to single objective hose routing, multi-objective hose routing and multi-hose routing. The use of simulation and optimization in engineering design has been widely applied in all fields of engineering as the computational capabilities of computers has increased and improved. As a result of this, the application of non-deterministic optimization techniques such as genetic algorithms, simulated annealing algorithms, ant colony algorithms, etc. has increased dramatically resulting in vast improvements in the design process. Initially, two versions of ant colony algorithms have been developed based on, respectively, a random network and a grid network for a single objective (minimizing the length of the hoses) and avoiding obstacles in the CAD model. While applying ant colony algorithms for the simulation of hose routing, two modifications have been proposed for reducing the size of the search space and avoiding the stagnation problem. Hose routing problems often consist of several conflicting or trade-off objectives. In classical approaches, in many cases, multiple objectives are aggregated into one single objective function and optimization is then treated as a single-objective optimization problem. In this thesis two versions of ant colony algorithms are presented for multihose routing with two conflicting objectives: minimizing the total length of the hoses and maximizing the total shared length (bundle length). In this case the two objectives are aggregated into a single objective. The current state-of-the-art approach for handling multi-objective design problems is to employ the concept of Pareto optimality. Within this thesis a new Pareto-based general purpose ant colony algorithm (PSACO) is proposed and applied to a multi-objective hose routing problem that consists of the following objectives: total length of the hoses between the start and the end locations, number of bends, and angles of bends. The proposed method is capable of handling any number of objectives and uses a single pheromone matrix for all the objectives. The domination concept is used for updating the pheromone matrix. Among the currently available multi-objective ant colony optimization (MOACO) algorithms, P-ACO generates very good solutions in the central part of the Pareto front and hence the proposed algorithm is compared with P-ACO. A new term is added to the random proportional rule of both of the algorithms (PSACO and P-ACO) to attract ants towards edges that make angles close to the pre-specified angles of bends. A refinement algorithm is also suggested for searching an acceptable solution after the completion of searching the entire search space. For all of the simulations, the STL format (tessellated format) for the obstacles is used in the algorithm instead of the original shapes of the obstacles. This STL format is passed to the C++ library RAPID for collision detection. As a result of using this format, the algorithms can handle freeform obstacles and the algorithms are not restricted to a particular software package.

No description available.