Η παρούσα διπλωματική εργασία εστιάζει σε αλγόριθμους υπολογισμού κυρτού περιβλήματος (convex hull). Γίνεται μία προσπάθεια εύρεσης εναλλακτικών τρόπων βελτίωσης του υπολογισμού του κυρτού περιβλήματος με την χρήση εξελικτικού υπολογισμού και συγκεκριμένα με γενετικούς αλγόριθμους. Το κυρτό περίβλημα αποτελεί μια βασική γεωμετρική κατασκευή για την ανάπτυξη εφαρμογών που σχετίζονται με τη δημιουργία χαρτών, υπολογισμού περιμέτρων, αποστάσεων διαφόρων δικτυωμένων οντοτήτων (ανθρώπων, κτιρίων, αισθητήρων). Καθώς οι απαιτήσεις αυξάνονται με εκθετικούς ρυθμούς, η ανάγκη βελτιστοποίησης του τρόπου υπολογισμού του κυρτού περιβλήματος είναι επιβεβλημένη. Αν και υπάρχει πλήθος παραδοσιακών αλγόριθμων υπολογισμού, θα πρέπει να αναζητηθούν εναλλακτικοί τρόποι προσέγγισης ώστε να επιτρέπουν αντίστοιχη κλιμάκωση στα νέα δεδομένα, χωρίς την απώλεια σημαντικής ακρίβειας.

Αρχικά μελετήθηκε η βιβλιογραφία σχετικά με τους υπάρχοντες αλγόριθμους υπολογισμού του κυρτού περιβλήματος. Στη συνέχεια μελετήθηκαν οι εξελικτικοί αλγόριθμοι καθώς και εφαρμογές που επιλύουν γεωμετρικά προβλήματα με τη χρήση εξελικτικού υπολογισμού. Ως αποτέλεσμα της μελέτης, η έρευνα επικεντρώθηκε στην χρήση γενετικών αλγόριθμων για την προσπάθεια βελτιστοποίησης του υπολογισμού του κυρτού περιβλήματος. Έτσι υλοποιήθηκε εφαρμογή σε γλώσσα προγραμματισμού Python. Η εφαρμογή παίρνει ως είσοδο τις συντεταγμένες ενός συνόλου σημείων του επιπέδου. Ακολούθως ταξινομεί τα σημεία και δημιουργεί τον αρχικό πληθυσμό που θα αποτελέσει τη βάση για την εφαρμογή του γενετικού αλγόριθμου. Η κωδικοποίηση των ατόμων που έχει επιλεγεί δημιουργεί δυαδικές ακολουθίες με μέγεθος ίσο με το πλήθος των σημείων του συνόλου και η θέση του κάθε ψηφίου αντιστοιχεί σε συγκεκριμένο σημείο. Έπειτα εφαρμόζονται οι γενετικοί τελεστές για να δημιουργήσουν την επόμενη γενιά που αποτελείται από βελτιωμένα άτομα. Μέσα από κάθε γενιά (επανάληψη) επιτυγχάνεται η προσέγγιση της επιθυμητής βελτιστοποίησης. Στην τελευταία γενιά μας επιστρέφει το βέλτιστο άτομο που, ανάλογα με την πλήρωση των κριτηρίων τερματισμού, μπορεί να έχει εντοπίσει ή προσεγγίσει ικανοποιητικά το κυρτό περίβλημα. Η εφαρμογή παρουσιάζει μεγάλο βαθμό επιτυχίας αλλά ο χρόνος εκτέλεσης υπολείπεται σημαντικά των παραδοσιακών αλγορίθμων.  

This thesis focuses on convex hull computation algorithms. An attempt is made to find ways to improve the convex hull computation by using evolutionary computation and in particular genetic algorithms. The convex hull is a basic geometric structure for the development of applications related to the creation of maps, calculation of perimeters, distances of various networked entities (people, buildings, sensors). As the requirements are increasing exponentially, the need to optimize the way of computing the convex hull is imperative. Although there is a multitude of traditional computation algorithms, alternative approaches should be sought to allow corresponding scaling to new data without losing significant accuracy.

Initially, the literature on existing algorithms for calculating the convex hull was reviewed. Next, evolutionary algorithms were studied as well as applications that solve geometric problems using evolutionary computation. As a result of the study, the research focused on the use of genetic algorithms to attempt to optimize the computation of the convex hull, as through genetic processes they can approximate optimal solutions. Thus, an application in Python programming language was implemented. The application takes as input the coordinates of a set of points in the plane. Then it sorts the points and creates the initial population that will form the basis for the genetic algorithm. The coding of the selected individuals generates binary sequences with size equal to the number of points in the set and the position of each digit corresponds to a specific point. Genetic operators are then applied to create the next generation consisting of improved atoms. Through each generation (iteration) the approximation of the desired optimization is achieved. In the last generation returns the best individual that, depending on the fulfilment of the termination criteria, may have satisfactorily identified or approximated the convex hull. The implementation exhibits a high degree of success but the execution time falls significantly short of traditional algorithms.