Optimized heuristic implementations in al multi - agent systems

Abstract

A central vision of the combinatorial optimization is to deliver a number of independent lines of operational research by implementing algorithms and hyper-graph theory on a series of random theoretical computer science problems. A main motivation is that thousands of real-life problems can be formulated as abstract combinatorial optimization problems. Albeit, multi-agent systems can also be used to solve problems that are difficult or impossible for monolithic systems to solve and methodic, functional, procedural, algorithmic and reinforcement forms of approaches are needed. Thus, in practice, extensive research and development efforts are required when applying combinatorial optimization in intelligent multi-agent systems, in order to achieve cooperation, interoperability and sustainability in heterogeneous and complex existing or future industrial, aerospace, robotic systems or/and any other cyber-physical system. Driven by the above mentioned problems, this Doctoral Dissertation presents meta-heuristic approaches in the area of AI algorithms and specifically the particle swarm and ant colony optimization to solve combinatorial optimization problems. More specifically present thesis’ applications/implementations focus on enhancing the:I.Combinational optimization of the intelligent multi-agent systems;II.Capabilities of the modern and intelligent multi-agent systems;III.Sustainability of the global cyber-physical systems.The methodological approach followed in this Dissertation for reaching the first goal may be described within the following achievements: •Reformulate the problem of dartboard game within the spectrum of metaheuristic algorithms•Use/Apply the Ant Colony System and Max-Min Ant System (MMAS) algorithm as a metaheuristic strategy that guide the search process•Reinforces local search in neighborhood of the best solution found in each iteration. In addition, heuristic is an adjective for experience-based techniques that help in problem solving, learning and discovery and heuristic methods are used to rapidly come to an 'optimal solution'. In more precise terms, heuristics stand for strategies using readily accessible information to control problem solving in many practical scenarios, slowing convergence and facilitating exploration.However, the Ant Colony Optimization technique has emerged recently as a new meta-heuristic for hard combinatorial Optimization Problems. Implementing a randomized construction heuristic extension of Ant Colony System algorithm in the Vehicle Scheduling Problem has become the second goal of this dissertation which is met by the following: •Definition the objective function for VSP •Make probabilistic decisions as a function of artificial pheromone trails •Estimate the effect of varying of levels of initial pheromone quantities on the objective function using an extension of Ant Colony System (ACS) algorithmThe final goal of this thesis is to enhance the previously referred goals/contribution regarding the sustainable development of an application paradigm. All parts included in currently presented thesis must meet the needs of the present forms of computing without compromising the ability of future generations to meet their own needs. This last objective is met at high-level by presenting the application of a ship dispatching real-life problem by: •Proposing a solution for a ship dispatching problem with the usage of Particle Swarm Optimization algorithm•Analyze the operational dimension of the problem by introducing a VPR formulation•Providing the paradigm of a set of 13 ports of the Aegean Sea (including a depot port) that was taken into considerationSummarizing the thesis outline is consisted of six (6) chapters as described below:•Chp.1: Artificial Intelligence and Agents •Chp.2: Multi-Agent Systems, Taxonomy and Architectures•Chp.3: Graph Searching Methods and Swarm Intelligence•Chp.4: PSO Algorithm Application: Solving a Ship Dispatching Problem •Chp.5: Ant Colony Optimization Application: An extension to the VSP•Chp.6: Comparison of the Meta-heuristic ACS and MMAS Algorithms: An Optimized Dartboard Design Application•Chp.7: Conclusions and Future Directions

Κεντρικός στόχος της συνδυαστικής βελτιστοποίησης είναι να παραδώσει μια σειρά από ανεξάρτητα αποτελέσματα της επιχειρησιακής έρευνας με την εφαρμογή αλγορίθμων και της θεωρίας υπερ-γράφηματων σε μια σειρά τυχαίων θεωρητικά προβλημάτων της επιστήμης των υπολογιστών. Ένα βασικό κίνητρο είναι ότι χιλιάδες προβλήματα της πραγματικής ζωής μπορεί να διατυπωθούν ως αφηρημένα προβλήματα συνδυαστικής βελτιστοποίησης. Αν και, τα συστήματα πολλαπλών πρακτόρων μπορεί επίσης να χρησιμοποιηθεί για την επίλυση προβλημάτων που είναι δύσκολο ή αδύνατο για τυπικά συστήματα. Στην πράξη εκτεταμένη έρευνα απαιτείται για την επίλυση συνδυαστικών προβλημάτων βελτιστοποίησης με τη χρήση πολυπρακτορικών συστημάτων.Η παρούσα διατριβή ασχολείται με μεθευρετικές προσεγγίσεις των αλγορίθμων τεχνητής νοημοσύνης και συγκεκριμένα και ειδικότερα του "Βελτιστοποίηση σμήνους σωματιδίων" και του "Βελτιστοποίηση αποικίας μυρμηγκιών"Συγκεκριμένα η παρούσα διατριβή εστίασε στα παρακάτω θέματα1.συνδυαστική βελτιστοποίηση των ευφυών συστημάτων πολλαπλών πρακτόρων2.Δυνατότητες των σύγχρονων ευφυών πολυπρακτορικών συστημάτων και βιωσιμότητα αυτών Στα παραπάνω πλαίσια για να ερευνήσουμε τη συμπεριφορά αυτών των αλγορίθμων ασχοληθήκαμε με την επίλυση των παρακάτω τριών προβλημάτων βελτιστοποίησεις1. Το πρόβλημα της δρομολόγησης ενός πλοίου με τη χρήση του αλγορίθμου "Βελτιστοποίηση Σμήνους Σωματιδίων"2. Στην αποτίμηση της επίδρασης του ορισμού αρχικής ποσότητας φερορμόνης στον αλγόριθμο "Βελτιστοποίηση αποικίας μυρμηγκιών" για την επίλυση προβλημάτων δρομολόγησης3. Μια συγκριτική μελέτη των μεθευρετικών αλγορίθμων για το σχεδιασμό ενός "Στόχου από Βελάκια (Dartboard)"