Μετα-ευρεστικοί αλγόριθμοι βελτιστοποίησης και εφαρμογές σε προβλήματα συνδυαστικής βελτιστοποίησης

Abstract

Η βελτιστοποίηση αποτελεί ένα βασικό θέμα συζητήσεων στην πληροφορική, στην τεχνητή νοημοσύνη, στην επιχειρησιακή έρευνα, ενώ βρίσκει εκπληκτικές εφαρμογές στον τομέα της βιομηχανίας. Τα προβλήματα που συναντώνται στον πραγματικό κόσμο, στη βιομηχανία και την επιστήμη είναι δύσκολα συνδυάστηκα προβλήματα βελτιστοποίηση (NP-hard combinatorial optimization problems). Η επίλυση αυτών των προβλημάτων με τη χρήση κλασσικών αιτιοκρατικών μεθόδων είναι, σχεδόν, αδύνατη. Γι’ αυτό το λόγο η έρευνα κατευθύνθηκε προς τους στοχαστικούς ευρεστικούς αλγόριθμους που προξενούνται ή δημιουργούνται εμπνέονται από φυσικά, κοινωνικά και βιολογικά φαινόμενα. Πρόσφατα, στα πλαίσια της παραπάνω έρευνας, αναπτύχθηκε μια αλγοριθμική πρακτική βασισμένη στη μέθοδο βελτιστοποίησης με αποικίες μυρμηγκιών (ant colony optimization / ACO) η οποία στηρίζεται στη συλλογική συμπεριφορά των μυρμηγκιών κατά την αναζήτηση και τη συγκομιδή της τροφής τους. Η εφαρμογή των αλγορίθμων ACO σε διακριτά αλλά και σε συνεχή προβλήματα, με μεγάλη πρακτική αξία, είναι πολύ ενθαρρυντικά σε σύγκριση με αλγόριθμους πολύ μεγάλης «διάρκειας ζωής». Οι στόχοι αυτής της έρευνας είναι : 1. Να εξερευνήσει και να παρουσιάσει τους μηχανισμούς που διέπουν μια κοινωνία εντόμων, και ειδικά την κοινωνία μυρμηγκιών. Στη συνέχεια να μελετηθεί η συμπεριφορά τους και η συμβολή τους στην ανάπτυξη συστημάτων τεχνικής νοημοσύνης μέσω ενός πανοράματος κυρίων αλγορίθμων. 2. Να δοθεί η μαθηματική θεμελίωση των μοντέλων διαχείρισης φερομόνης μέσω των εξισώσεων διαφορών, καθώς επίσης και εκείνης της εξάτμισης της φερομόνης μέσω γεννητριών συνάρτησης, εξετάζοντας την γεωμετρική και αλγεβρική της σύγκλισης. 3. Να δείξει τα αποτελέσματα της εφαρμογής των αλγορίθμων αποικίας μυρμηγκιών σε μια μεγάλη περιοχή προβλημάτων σημαντικής πρακτικής αξίας. Η αντιμετώπιση και ο τρόπος επίλυσης αυτών των προβλημάτων ανέδειξαν πρωτότυπους αλγορίθμους που συμβάλλουν στην καθολική αποδοχή της αποικίας μυρμηγκιών, σαν εργαλείο μελέτης, έρευνας και καθιέρωσης συγκεκριμένης μεθοδολογίας βελτιστοποίησης. Αυτή αφορά όχι μόνο πρόβλημα συνδυαστικής βελτιστοποίησης, αλλά, και συνεχή ή και συνδυασμό αυτών.