No description available.

No description available.

[pt] Muitos avanços da ciência foram obtidos a partir da observação da natureza. Milênios de seleção natural e evolução fizeram com que certos seres vivos desenvolvessem habilidades e características realmente notáveis, e que ainda hoje surpreendem pela sua complexidade e adaptabilidade. Alguns ramos da ciência fazem uso constante da observação intensiva dessas características, na tentativa de reproduzi-las em um ambiente controlado, com o objetivo de desenvolver métodos e ferramentas nelas baseados. Exemplos de métodos desenvolvidos dessa forma são os algoritmos de colônias de formigas. Sistemas de colônias de formigas (Ant Colony Systems - ACS) são modelos matemáticos baseados no comportamento de formigas quando imersas em colônias de indivíduos semelhantes. Formigas são indivíduos simples, porém capazes de interagir entre si, obtendo muitos benefícios desta prática. Estes modelos são muito úteis na resolução de grandes problemas de otimização combinatória, geralmente muito complexos para serem resolvidos por métodos exatos de otimização e representam um incipiente e importante campo de estudos da engenharia de produção. Este trabalho se propõe a descrever alguns algoritmos de colônias de formigas, utilizados em problemas de otimização combinatória/discreta. Particularmente, o foco do trabalho será na aplicação destes algoritmos no problema de roteirização de veículos com janelas de tempo. Uma forma de implementação do algoritmo no ambiente Matlab será proposta e testada em problemas padrão usados como benchmarking na literatura. / [en] Many advances in science were achieved from the observation of nature. Thousands of years of natural selection and evolution made certain living beings develop notable abilities and characteristics, that still nowadays surprise us with their complexity and adaptability. Some fields of science make constant use of intensive observation of these characteristics, in order to reproduce them in a controlled environment, with the objective of developping methods and tools based on them. Examples of methods developped this way are ant colony algorithms. Ant Colony Systems are mathematical models based on the behavior of ants when immersed in colonies of likely individuals. Ants are simple individuals, however capable of interacting with each other, obtaining benefits from this practice. These models are very useful in solving large combinatory optimization problems, usually too complex to be solved by exact optimization methods, and represent an important and incipient field of study in production engineering. This work aims to describe some ant colony algorithms, used in combinatory/discrete optimization problems. Particularly, the focus of this work will be in the application of these algorithms to the vehicle routing problem with time windows. A form of implementation of the algorithm in Matlab environment will be proposed and tested in standard problems used as benchmarking in the literature.

Στην παρούσα εργασία γίνεται μια προσπάθεια συνολικής παρουσίασης των τεχνικών χρονοπρογραμματισμού έργου ακολουθώντας την πορεία εξέλιξής τους. Στο τρίτο κεφάλαιο απαντάμε στα βασικά ερωτήματα που αφορούν το τι περιλαμβάνει η έννοια του όρου έργο και διαχείριση έργου. Είναι πολύ σημαντικό πριν να προχωρήσουμε σε τεχνικές χρονοπρογραμματισμού ενός έργου να μπορούμε να αποκωδικοποιήσουμε τις ανάγκες του αλλά και τον τρόπο δόμησής του ώστε να υπολογίσουμε σωστά τις ανάγκες και τα κόστη σε χρόνο αλλά και σε πόρους, ώστε να φθάσουμε στην επίτευξη του τελικού σκοπού μέσα στο χρονικό ορίζοντα που έχουμε θέσει και χωρίς να έχουμε αποκλίσεις από τις προϋπολογισθείσες δαπάνες πόρων. Στη συνέχεια αναλύονται οι κλασικές τεχνικές χρονοπρογραμματισμού μέσα από παραδείγματα εφαρμογών. Στο τέταρτο κεφάλαιο γίνεται μια παρουσίαση των βασικότερων μεθόδων επίλυσης προβλημάτων συνδυαστικής βελτιστοποίησης και παρουσιάζονται οι προσεγγίσεις αντιμετώπισης μέσω τριών κατηγοριών αλγορίθμων που έχουν αναπτυχθεί τα τελευταία χρόνια. Αυτοί είναι: οι ακριβείς μέθοδοι μαθηματικού προγραμματισμού, οι ευρετικοί αλγόριθμοι και οι μεταευρετικοί αλγόριθμοι. Στη συνέχεια δίνεται έμφαση στην παρουσίαση των κυριότερων εκπροσώπων των ακριβών μεθόδων. Αναλύουμε τις ευρετικές και μεταευρετικές μεθόδους όπως αυτές έχουν παρουσιαστεί τα τελευταία χρόνια από τους ερευνητές. Οι ευρετικές μέθοδοι αποτελούν τη πηγή έμπνευσης θα λέγαμε για τη δημιουργία των μεταευρετικών αλγορίθμων οι οποίοι υπόσχονται ακόμα καλύτερη αντιμετώπιση του προβλήματος καθώς δίνουν μια απάντηση σε προβλήματα που θεωρούνταν αδύνατο να λυθούν αποτελεσματικά και να επιστρέψουν βέλτιστες λύσεις με τους ευρετικούς αλγόριθμους. Στο πέμπτο κεφάλαιο αναλύεται η φιλοσοφία, η εξέλιξη και ο τρόπος λειτουργίας των αλγόριθμων του μοντέλου της κοινωνίας των μυρμηγκιών και γίνεται παρουσίαση των διάφορων εκδόσεων τους των τελευταίων 3 δεκαετιών που αυτοί έχουν κάνει αισθητή της παρουσία τους στην έρευνα. Γίνεται επίσης παρουσίαση τους σε μορφή ψευδοκώδικα και διαγραμμάτων ροής. Κύριο μέρος του κεφαλαίου λαμβάνει η αντιμετώπιση του Προβλήματος του Περιοδεύοντας Πωλητή (Traveling Salesman Problem- TSP) που είναι το κυριότερο πρόβλημα χρονοπρογραμματισμού και πάνω στο οποίο στηρίζεται η εύρεση λύσεων και σε άλλα υπολογιστικά προβλήματα όπως αυτό της δρομολόγησης οχημάτων, χρονοπρογραμματισμού παραγωγής κα. Στο έκτο κεφάλαιο γίνεται παρουσίαση του τρόπου αντιμετώπισης του προβλήματος της εύρεσης της κρίσιμης διαδρομής σε ένα έργο και παρουσιάζεται ο αλγόριθμος που ακολουθείται. Παράλληλα, παρουσιάζεται μια μελέτη συμπεριφοράς του αλγορίθμου σε μεταβολές των μεταβλητών του. Στο έβδομο κεφάλαιο βλέπουμε κάποια γενικά συμπεράσματα και μελλοντικές κατευθύνσεις ενώ στο Παράρτημα Ι γίνεται παρουσίαση της θεωρίας των γράφων για να γίνει καλύτερα κατανοητή η χρήση τους και ο σπουδαίος ρόλος τους στην ανάπτυξη των αλγορίθμων χρονοπρογραμματισμού, ενώ στο Παράρτημα ΙΙ παρουσιάζεται αναλυτικά το πρόβλημα του πλανόδιου πωλητή. / -

Cette thèse s’intéresse à une problématique ayant de nombreuses applications pratiques, à savoir la comparaison automatique d’objets et l’évaluation de la similarité. Lorsque les objets sont modélisés par des graphes, ce problème de comparaison automatique d’objets se ramène à un problème d’appariement de graphes, c’est-à-dire, chercher une mise en correspondance entre les sommets des graphes permettant de retrouver le plus grand nombre de caractéristiques communes. Différentes classes existent allant de la plus restrictive à la plus générale. Dans la plus restrictive isomorphisme de (sous-) graphes, il s’agit de chercher un appariement exact entre les sommets des graphes de manière à prouver que les deux graphes possèdent une structure identique ou que l’un d’eux est inclus dans l’autre, un sommet étant apparié avec au plus un sommet. Dans la plus générale (appariement multivoque), l’objectif n’est plus de trouver un appariement exact mais le meilleur appariement, c’est-à-dire, celui qui préserve un maximum de sommets et d’arcs, un sommet pouvant être apparié à un ensemble de sommets. Nous nous intéressons au problème de la recherche du meilleur appariement multivoque, ce problème étant plus général que les problèmes d’appariement restrictifs. Sa résolution est clairement un défi tant par la difficulté du problème que par l’importance de ses applications. Pour relever ce défi, nous proposons d’étudier les capacités de l’optimisation par colonies de fourmis (ACO). Notre étude est menée dans deux contextes : un contexte statique, où le problème est figé, et un contexte dynamique, où les graphes à comparer, les contraintes à respecter ainsi que les critères définissant la qualité des appariements changent régulièrement de sorte que la solution doit être dynamiquement adaptée. Un premier objectif, de cette thèse, est de proposer l’algorithme ACO générique pour la résolution des problèmes d’appariement de graphes. Plusieurs points clés sont étudiés dans cet algorithme, à savoir : l’influence des paramètres sur la qualité des solutions construites, l’influence de la stratégie phéromonale et du facteur heuristique, et l’hybridation avec une technique de recherche locale. Un deuxième objectif est de proposer un algorithme ACO générique pour résoudre des problèmes d’optimisation dynamiques. L’algorithme proposé est appliqué et expérimenté à quelques problèmes dynamiques, à savoir : l’appariement de graphes, le problème du sac à dos multidimensionnel, et le voyageur de commerce / The thesis addresses the problematic of comparing objects and similarity measuring. If objects are described by graphs, so that measuring objects similarity turns into determining graph similarity, i.e., matching graph vertices to identify their common features and their differences. Different classes of graph matching have been proposed going on the most restrictive ones to the most general. In restrictive graph matching (graph or sub-graph isomorphism), the objective is to show graph equivalence or inclusion, a vertex in a graph may be matched with one vertex at most on the other graph. In general graph matching (multivalent matching), the goal is not yet to find an “exact” matching (a matching which preserves all vertices and edges), but to look for a “best” matching (a matching which preserves a maximum number of vertices and edges), a vertex in one graph may be matched with a set of vertices in the other graph. In our work, we consider the problem of searching the best multivalent matching which is a NP-hard optimization problem. More precisely, we propose to investigate the ability if the ant colony optimization meta-heuristic (ACO). Two cases are considered in our study: the static case where the problem remains invariant through time and the dynamic case where graphs to compare constrained to satisfy and the criterions defining matching quality may change over the time, so that solutions must be dynamically adapted to the changes. A first goal of this thesis is to propose a generic ACO algorithm for solving graph matching problems. Different key points, like the pheromonal strategy to be used, the heuristic factor and the use of a local search procedure, are studied. A second goal of this work is to propose a generic ACO algorithm for solving dynamic optimization problems. The proposed algorithm will be applied and experimentally studied on three different dynamic problems: graph matching problem, multi-dimensional knapsack problem and the travelling salesman problem

As redes de telecomunicações são responsáveis pelo envio de informação entre pontos de origem e destino. Dentre os diversos dispositivos que participam deste processo, destaca-se o sistema de roteamento, que realiza a seleção das rotas a serem percorridas pelas mensagens ao longo da rede e sua condução ao destino desejado. O avanço das tecnologias utilizadas pelas redes de telecomunicações provocou a necessidade de novos sistemas de roteamento, que sejam capazes de lidar corretamente com as diversas situações enfrentadas atualmente. Dentro deste contexto, este projeto de pesquisa desenvolveu um algoritmo de roteamento adaptativo e distribuído, resultado da integração de três estratégias de aprendizagem e da adição de alguns mecanismos extras, com o objetivo de obter um algoritmo eficiente e robusto às diversas variações das condições de operação da rede. As abordagens utilizadas foram a aprendizagem-Q, aprendizagem por reforço dual e aprendizagem baseada no comportamento coletivo de formigas. O algoritmo desenvolvido foi aplicado a duas redes de comutação de circuitos e seu desempenho foi comparado ao de dois algoritmos baseados no comportamento coletivo de formigas, que foram aplicados com sucesso ao problema de roteamento. Os experimentos conduzidos envolveram situações reais enfrentadas pelas redes, como variações dos seus padrões de tráfego, nível de carga e topologia. Além disto, foram realizados testes envolvendo a presença de ruído nas informações utilizadas para a seleção das rotas a serem percorridas pelas chamadas. O algoritmo proposto obteve melhores resultados que os demais, apresentando maior capacidade de adaptação às diversas situações consideradas. Os experimentos demonstraram que novos mecanismos de otimização devem ser anexados ao algoritmo proposto, para melhorar seu comportamento exploratório sob variações permanentes do nível de carga da rede e presença de ruído nos dados utilizados em suas tarefas. / The telecommunications networks are responsible for transmiting information between source and destination points in a fast, secure and reliable way, providing low cost and high quality services. Among the several devices that takes place on this process, there is thre routing system, which selects the routes to be traversed by the messages through the network and their forwarding to the destination desired. The advances in tecnologies used by telecommunications networks caused the necessity of new routing systems, that can work correctly with the situations faced by current telecommunications networks. Hence, this research project developed an adaptive and distributed routing algorithm, resulting of the integration of three leaming strategies and addition of some extra mechanisms, with the goal of having a robust and adaptive algorithm to the several variations on operation network conditions. The approaches chosen were Q-learning, dual reinforcement learning and learning based on collective behavior of ants. The developed algorithm was applied to two circuit-switching telecommunications networks and its performance was compared to two algorithms based on ant colony behavior, which were used with success to solve the routing problem. The experiments run comprised real situations faced by telecommunications networks, like variations on the network traffic patterns, load level and topology. Moreover, we did some tests with the presence of noise in information used to select the routes to be traversed by calls. The algorithm proposed produced better results than the others, showing higher capacity of adaptation to the several situations considered. The experiments showed that new optimization mechanisms must be added to the routing algorithm developed, to improve its exploratory behavior under permanent variations on network load level and presence of noise in data used in its tasks.

As redes de telecomunicações são responsáveis pelo envio de informação entre pontos de origem e destino. Dentre os diversos dispositivos que participam deste processo, destaca-se o sistema de roteamento, que realiza a seleção das rotas a serem percorridas pelas mensagens ao longo da rede e sua condução ao destino desejado. O avanço das tecnologias utilizadas pelas redes de telecomunicações provocou a necessidade de novos sistemas de roteamento, que sejam capazes de lidar corretamente com as diversas situações enfrentadas atualmente. Dentro deste contexto, este projeto de pesquisa desenvolveu um algoritmo de roteamento adaptativo e distribuído, resultado da integração de três estratégias de aprendizagem e da adição de alguns mecanismos extras, com o objetivo de obter um algoritmo eficiente e robusto às diversas variações das condições de operação da rede. As abordagens utilizadas foram a aprendizagem-Q, aprendizagem por reforço dual e aprendizagem baseada no comportamento coletivo de formigas. O algoritmo desenvolvido foi aplicado a duas redes de comutação de circuitos e seu desempenho foi comparado ao de dois algoritmos baseados no comportamento coletivo de formigas, que foram aplicados com sucesso ao problema de roteamento. Os experimentos conduzidos envolveram situações reais enfrentadas pelas redes, como variações dos seus padrões de tráfego, nível de carga e topologia. Além disto, foram realizados testes envolvendo a presença de ruído nas informações utilizadas para a seleção das rotas a serem percorridas pelas chamadas. O algoritmo proposto obteve melhores resultados que os demais, apresentando maior capacidade de adaptação às diversas situações consideradas. Os experimentos demonstraram que novos mecanismos de otimização devem ser anexados ao algoritmo proposto, para melhorar seu comportamento exploratório sob variações permanentes do nível de carga da rede e presença de ruído nos dados utilizados em suas tarefas. / The telecommunications networks are responsible for transmiting information between source and destination points in a fast, secure and reliable way, providing low cost and high quality services. Among the several devices that takes place on this process, there is thre routing system, which selects the routes to be traversed by the messages through the network and their forwarding to the destination desired. The advances in tecnologies used by telecommunications networks caused the necessity of new routing systems, that can work correctly with the situations faced by current telecommunications networks. Hence, this research project developed an adaptive and distributed routing algorithm, resulting of the integration of three leaming strategies and addition of some extra mechanisms, with the goal of having a robust and adaptive algorithm to the several variations on operation network conditions. The approaches chosen were Q-learning, dual reinforcement learning and learning based on collective behavior of ants. The developed algorithm was applied to two circuit-switching telecommunications networks and its performance was compared to two algorithms based on ant colony behavior, which were used with success to solve the routing problem. The experiments run comprised real situations faced by telecommunications networks, like variations on the network traffic patterns, load level and topology. Moreover, we did some tests with the presence of noise in information used to select the routes to be traversed by calls. The algorithm proposed produced better results than the others, showing higher capacity of adaptation to the several situations considered. The experiments showed that new optimization mechanisms must be added to the routing algorithm developed, to improve its exploratory behavior under permanent variations on network load level and presence of noise in data used in its tasks.