Εξελικτικοί αλγόριθμοι: Ο αλγόριθμος της Διαφορικής Εξέλιξης:
Creators: name: Γκουντή, Ανθούλα Αντωνίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Αλγόριθμος Διαφορικής Εξέλιξης
Εξελικτικοί Αλγόριθμοι
Πρόβλημα Πλανόδιου Πωλητή
Differential Evolution Algorithm
Evolutionary Algorithms
Travelling Salesman Problem

description: Η βελτιστοποίηση είναι μια έννοια, μια διαδικασία, μια μέθοδος την οποία όλοι οι άνθρωποι χρησιμοποιούν, ακόμη και μηχανικά, πάρα πολύ συχνά στην καθημερινή τους ζωή. Από την επιλογή της συντομότερης διαδρομής για τη μετάβαση στον προορισμό μας, τον τρόπο διαχείρισης και διανομής υλικών που έχουμε στην διάθεσή μας, μέχρι την επίλυση πολύπλοκων προβλημάτων σε διάφορους επιστημονικούς τομείς. Η πηγή έμπνευσης πάρα πολλών μεθόδων βελτιστοποίησης για πολλούς επιστήμονες υπήρξε η ίδια η φύση καθώς και οι μηχανισμοί που υπάρχουν σε αυτήν. Αντικείμενο της παρούσας διπλωματικής εργασίας αποτελεί η μελέτη και η έρευνα των Εξελικτικών Αλγορίθμων(ΕΑ) που βοηθούν στην αντιμετώπιση υπολογιστικά δύσκολων προβλημάτων βελτιστοποίησης, και συγκεκριμένα του αλγόριθμου της Διαφορικής Εξέλιξης. Aρχικά, γίνεται μια εισαγωγή γενικά περί της βελτιστοποίησης και δίνονται κάποιες βασικές αρχές των κλασσικών αλγορίθμων αναζήτησης. Στη συνέχεια, δίνεται μια συνοπτική περιγραφή των ευρετικών και μεθευρετικών μεθόδων, καθώς επίσης και μια κατηγοριοποίηση των τελευταίων. Ακολουθεί ο ορισμός των ΕΑ, η περιγραφή της δομής τους, του βασικού τους κύκλου και της οικογένειας αυτών. Ακόμη, γίνεται μια εκτενέστερη περιγραφή στις Εξελικτικές Στρατηγικές, καθώς ο αλγόριθμος που αναπτύχθηκε ως μέρος της διπλωματικής εργασίας ανήκει σε αυτήν την κατηγορία. Η διπλωματική εργασία επικεντρώνεται στον αλγόριθμο της Διαφορικής Εξέλιξης(ΔΕ). Η πρώτη έκδοση αυτού του αλγόριθμου προτάθηκε από τους R.Storn και K.V.Price το 1995[88]. Αναπτύσσονται τα βασικά χαρακτηριστικά του αλγορίθμου και παρουσιάζονται μέσω σχημάτων και μαθηματικών σχέσεων η δομή, η λειτουργία του και ο κύκλος του. Στη συνέχεια, γίνεται αναφορά σε κάποιες παραλλαγές του αλγόριθμου που εμφανίστηκαν πρόσφατα και στόχος τους είναι η σταδιακή αυτό-ρύθμιση των στρατηγικών δημιουργίας δοκιμαστικών διανυσμάτων και των αντίστοιχων παραμέτρων ελέγχου χωρίς την παρέμβαση του χρήστη. Επιπλέον, διερευνάται το Πρόβλημα του Πλανόδιου Πωλητή και παρουσιάζεται μία βιβλιογραφική ανασκόπηση της εφαρμογής του αλγορίθμου της ΔΕ σε αυτό με διάφορες προσεγγίσεις. Τέλος, γίνεται μια σύντομη αναφορά στον κώδικα DeWin, ο οποίος είναι γραμμένος στην γλώσσα C.
description: Optimization is a sense, a process, a method which everybody uses even automatically very often in everyday life. From choosing the shortest route in order to get to our destination, the way of managing and distributing material in our disposition, the qualitative or quantitative cost assessment in relation to the value of a product or a service, to the solution of complex problems in various scientific domains. The inspiration source of many optimization methods for scientists has been nature itself, as well as the mechanisms in it. The objective of this thesis is the study and the research of Evolutionary Algorithms(EAs) for addressing computationally hard optimization problems, and specifically of the Differential Evolution algorithm(DE). For this reason, in the introduction optimization is generally presented and the main principles of traditional search algorithms are given. Secondly, there is a short description of heuristics and metaheuristics, as well as a classification of the latter. Thirdly, there is the definition of EAs, the description of their structure, their basic cycle and their family. A more detailed description of Evolution Strategies(ES) is also given, since the algorithm presented as part of this thesis belongs to this group. The thesis focuses on the Differential Evolution algorithm(DE). The first version of this algorithm was proposed as a technical report by R. Storn and K.V. Price in 1995[88]. The basic scheme of the DE is developed and then its structure, procedure and basic cycle are presented through figures and mathematical forms. Also, there is a reference to some versions of DE, which appeared recently and whose goal is the self-adaption of both trial vector generation strategies and their associated control parameter values without user’s intervention. Furthermore, the Travelling Salesman Problem(TSP) is examined and a literature review of the DE application to it is presented with various approaches. Finally, a brief description of a C code, DeWin, is made.