Γράφουν οι:
ΓΙΑΝΝΗΣ ΜΑΡΙΝΑΚΗΣ*
ΜΑΓΔΑΛΗΝΗ ΜΑΡΙΝΑΚΗ*
KΩΝΣΤΑΝΙΝΟΣ ΖΟΠΟΥΝΙΔΗΣ*
1. Εισαγωγή
Τα τελευταία χρόνια έχουν αναπτυχθεί στο χώρο των εφαρμοσμένων μαθηματικών πολλές μέθοδοι βελτιστοποίησης (μεγιστοποίηση κέρδους ή ελαχιστοποίηση κόστους) που βασίζονται είτε στους μηχανισμούς της φυσικής επιλογής και της γενετικής είτε σε αλγόριθμους που στηρίζονται σε διαδικασίες εμπνευσμένες από τη φύση είτε τέλος σε αλγορίθμους οι οποίοι εμπνέονται από το φυσικό ανοσοποιητικό σύστημα του ανθρώπου.
Οι μέθοδοι Βελτιστοποίησης αυτής της μορφής είναι οι Γενετικοί Αλγόριθμοι, ο Αλγόριθμος Βελτιστοποίησης Αποικίας Μυρμηγκιών και ο Αλγόριθμος Επιλογής Κλώνων. Όλες αυτές οι μεθοδολογίες έχουν εφαρμοστεί με μεγάλη επιτυχία και με πολύ καλά αποτελέσματα σε διάφορα προβλήματα, όπως αυτά του σχεδιασμού και βελτιστοποίησης της εφοδιαστικής αλυσίδας (για παράδειγμα στο πρόβλημα του πλανόδιου πωλητή, στο πρόβλημα δρομολόγησης οχημάτων (Marinakis and Marinaki, 2010), σε χρηματοοικονομικά προβλήματα (για παράδειγμα στο πρόβλημα της αξιολόγησης του πιστωτικού κινδύνου (Marinakis et al., 2009a), στο πρόβλημα ομαδοποίησης (Marinakis et al., 2009b), σε ιατρικά προβλήματα (για παράδειγμα στο πρόβλημα ταξινόμησης των κυττάρων που λαμβάνονται κατά το τεστ Παπανικολάου (Marinakis et al., 2009c) και αλλού.
2. Γενετικοί Αλγόριθμοι
Οι Γενετικοί Αλγόριθμοι (Genetic Algorithms) είναι διαδικασίες αναζήτησης που βασίζονται στους μηχανισμούς της φυσικής επιλογής και της γενετικής. Ο πρώτος γενετικός αλγόριθμος αναπτύχθηκε από τον John H. Holland τη δεκαετία του 1960, για να δώσει τη δυνατότητα στους ηλεκτρονικούς υπολογιστές να παράγουν λύσεις σε δύσκολα προβλήματα αναζήτησης και συνδυαστικής βελτιστοποίησης, όπως η ελαχιστοποίηση συναρτήσεων και η μηχανική μάθηση (Holland, 1975). Οι γενετικοί αλγόριθμοι είναι μια ιδιαιτέρως ελκυστική προσέγγιση για προβλήματα όπως το πρόβλημα επιλογής χαρακτηριστικών (feature subset selection) καθώς είναι γενικά πολύ αποτελεσματικοί για γρήγορη ολική αναζήτηση μεγάλων μη γραμμικών και όχι πλήρως κατανοητών χώρων. Επιπλέον, είναι πολύ αποτελεσματικοί στην επίλυση προβλημάτων μεγάλης κλίμακας. Οι γενετικοί αλγόριθμοι (Goldberg, 1989) μιμούνται τη διαδικασία εξέλιξης στη φύση. Βασίζονται σε μια μίμηση της βιολογικής διαδικασίας στην οποία νέοι και καλύτεροι πληθυσμοί μεταξύ διαφορετικών ειδών αναπτύσσονται κατά τη διάρκεια της εξέλιξης. Έτσι, σε αντίθεση με τους περισσότερους ευρετικούς αλγορίθμους, οι γενετικοί αλγόριθμοι κατά τη διάρκεια της αναζήτησης μιας καλύτερης λύσης χρησιμοποιούν πληροφορίες από ένα πληθυσμό λύσεων, που ονομάζονται άτομα (individuals). Ένας γενετικός αλγόριθμος είναι μια στοχαστική επαναληπτική διαδικασία που διατηρεί το μέγεθος του πληθυσμού σταθερό σε κάθε επανάληψη, η οποία ονομάζεται γενιά (generation). Η βασική τους λειτουργία είναι το ταίριασμα δύο λύσεων με στόχο να δημιουργηθεί μια νέα λύση. Για να δημιουργηθεί μια νέα λύση εφαρμόζονται δύο τελεστές, ένας δυαδικός τελεστής που ονομάζεται διασταύρωση (crossover), και ένας μοναδιαίος τελεστής που ονομάζεται μετάλλαξη (mutation) (Reeves, 1995; 2003). Η διασταύρωση παίρνει δύο άτομα που ονομάζονται γονείς (parents) και παράγει με την ανταλλαγή τμημάτων των γονέων δύο νέα άτομα που ονομάζονται απόγονοι (offspring). Ο αλγόριθμος έχει εφαρμοστεί στο πρόβλημα της αξιολόγησης του πιστωτικού κινδύνου και σε προβλήματα σχεδιασμού και βελτιστοποίησης της εφοδιαστικής αλυσίδας.
3. Αλγόριθμος Βελτιστοποίησης Αποικίας Μυρμηγκιών
Η Βελτιστοποίηση Αποικίας Μυρμηγκιών (Ant Colony Optimization) είναι μια σχετικά νέα στρατηγική για την επίλυση προβλημάτων συνδυαστικής βελτιστοποίησης που πρωτοπαρουσιάστηκε από τους Dorigo, Maniezzo και Colorni (Dorigo et al., 1996; Dorigo and Stutzle, 2004). Η Βελτιστοποίηση Αποικίας Μυρμηγκιών είναι ένα σύστημα που μιμείται τη συμπεριφορά των πραγματικών μυρμηγκιών κατά τη διαδικασία της εύρεσης της τροφής τους. Τα μυρμήγκια αναπτύσσουν μια τεχνική για να βρουν τη συντομότερη διαδρομή από τη φωλιά τους προς την πηγή της τροφής τους και αντίθετα. Τα μυρμήγκια ξεκινούν την αναζήτηση της τροφής γύρω από την πηγή με τυχαίο τρόπο και καθώς κινούνται αφήνουν μια ποσότητα μιας ουσίας που ονομάζεται φερομόνη και με αυτό τον τρόπο μαρκάρουν το μονοπάτι που έχουν διανύσει. Η ποσότητα της φερομόνης στο κάθε μονοπάτι εξαρτάται από την απόσταση, την ποιότητα και την ποσότητα της τροφής που βρέθηκε. Το επόμενο μυρμήγκι που θα φύγει από τη φωλιά του είναι πολύ πιθανό να ακολουθήσει τη φερομόνη που θα υπάρχει σε κάποιο μονοπάτι, αφήνοντας μια ποσότητα φερομόνης στο ίδιο μονοπάτι. Καθώς η ποσότητα φερομόνης στο συγκεκριμένο μονοπάτι όλο και αυξάνεται όλο και περισσότερα μυρμήγκια ακολουθούν αυτό το μονοπάτι. Όμως καθώς η ώρα περνάει η φερομόνη, ιδιαίτερα από τα μονοπάτια που δεν πηγαίνουν πολλά μυρμήγκια, ελαττώνεται. Τελικά από όλα τα υπόλοιπα μονοπάτια η φερομόνη εξαφανίζεται και όλα τα μυρμήγκια ακολουθούν τελικά το ίδιο μονοπάτι, που είναι και η βέλτιστη ή η σχεδόν – βέλτιστη λύση.
Η κύρια ιδέα της Βελτιστοποίησης Αποικίας Μυρμηγκιών είναι να μοντελοποιηθεί το πρόβλημα ως πρόβλημα εύρεσης μονοπατιού ελαχίστου κόστους σε ένα γράφημα. Κάθε μυρμήγκι αποτελεί μια λύση για το πρόβλημα. Ο αλγόριθμος αποτελείται από ένα αριθμό από επαναλήψεις, όπου σε κάθε επανάληψη κάθε μυρμήγκι ξεκινάει να κατασκευάσει μια λύση με βάση την εμπειρία που έχει αποκτηθεί από τις λύσεις που δημιούργησαν τα προηγούμενα μυρμήγκια. Στο τέλος των επαναλήψεων όλα ή σχεδόν όλα τα μυρμήγκια ακολουθούν την ίδια διαδρομή η οποία κρατείται ως βέλτιστη λύση. Ο αλγόριθμος έχει εφαρμοστεί στο πρόβλημα της αξιολόγησης του πιστωτικού κινδύνου και σε προβλήματα ομαδοποίησης.
4. Τεχνητά Ανοσοποιητικά συστήματα
Τα Τεχνητά Ανοσοποιητικά Συστήματα (Artificial Immune Systems) (Dasgupta, 1998; De Castro and Timmis, 2002) εμπνέονται από τα φυσικά ανοσοποιητικά συστήματα (Natural Immune Systems) προκειμένου να δημιουργηθούν αλγόριθμοι βελτιστοποίησης και ταξινόμησης. Ο στόχος κατά το σχεδιασμό των τεχνητών ανοσοποιητικών συστημάτων είναι η εξαγωγή ιδεών και μεταφορών από τον τρόπο λειτουργίας του φυσικού ανοσοποιητικού συστήματος οι οποίες μπορούν να χρησιμοποιηθούν προκειμένου να επιλυθούν πραγματικά προβλήματα. Οι διαφορετικές θεωρίες για τη λειτουργική και οργανωτική συμπεριφορά του φυσικού ανοσοποιητικού συστήματος ενέπνευσαν τη μοντελοποίηση του φυσικού ανοσοποιητικού συστήματος στο τεχνητό ανοσοποιητικό σύστημα και την εφαρμογή του σε μη βιολογικά περιβάλλοντα.
Οι ικανότητες του φυσικού ανοσοποιητικού συστήματος τις οποίες εκμεταλλεύεται το τεχνητό ανοσοποιητικό σύστημα, είναι (Engelbrecht, 2007):
1. το φυσικό ανοσοποιητικό σύστημα χρειάζεται να γνωρίζει μόνο τα φυσιολογικά κύτταρα,
2. το φυσικό ανοσοποιητικό σύστημα μπορεί να ξεχωρίσει τα φυσιολογικά από τα ξένα κύτταρα,
3. ένα ξένο κύτταρο μπορεί να χαρακτηριστεί σαν επιβλαβές ή μη επιβλαβές,
4. τα λεμφοκύτταρα κλωνοποιούνται και μεταλλάσσονται προκειμένου να προσαρμοστούν με τα ξένα κύτταρα που αντιμετωπίζει ο οργανισμός,
5. το φυσικό ανοσοποιητικό σύστημα έχει γρήγορη αντίδραση σε αντιγόνα (δηλ. ξένα μόρια τα οποία εκφράζονται από ένα παθογόνο το οποίο πυροδοτεί την αντίδραση του ανοσοποιητικού συστήματος) που ο οργανισμός έχει ήδη αντιμετωπίσει, η οποία οφείλεται στα κύτταρα μνήμης.
Το φυσικό ανοσοποιητικό σύστημα έχει πολλαπλά επίπεδα υπεράσπισης. Η πρώτη γραμμή υπεράσπισης ουσιαστικά μπλοκάρει την απορρόφηση παθογόνων (δηλ. των ξένων σωματιδίων, για παράδειγμα ιών, βακτηρίων, μυκήτων κλπ.) και είναι για παράδειγμα το δέρμα και οι ρινικές τρίχες. Η παραπάνω ζώνη ενισχύεται από τη φυσιολογική άμυνα, υγρά για παράδειγμα τα οποία εκκρίνονται από το σώμα (σάλιο, ιδρώτας και δάκρυα) τα οποία απομακρύνουν τα παθογόνα από το σώμα και μπορεί να περιέχουν διασπαστικά ένζυμα. Επιπρόσθετα, οι άνθρωποι διαθέτουν έμφυτη και προσαρμόσιμη ανοσοποίηση. Το έμφυτο ανοσοποιητικό σύστημα χρησιμοποιεί ένα πλήθος μοριακών προτύπων προκειμένου να αναγνωρίζει τα παθογόνα, υφίσταται από τη γέννηση και δεν προσαρμόζεται κατά τη διάρκεια της ζωής ενός ατόμου. Σε περίπτωση που το έμφυτο ανοσοποιητικό σύστημα δεν μπορεί να απομακρύνει ένα παθογόνο που προσπαθεί να εισβάλλει στον οργανισμό μας, το επίκτητο ανοσοποιητικό σύστημα λαμβάνει δράση. Το επίκτητο ανοσοποιητικό σύστημα κατευθύνεται ενάντια συγκεκριμένων παθογόνων και τροποποιείται από την έκθεση σε αυτά. Με αυτό τον τρόπο το ανοσοποιητικό σύστημα δημιουργεί και διατηρεί ένα ιστορικό των εισβολέων και των τρόπων μέσω των οποίων μπορούν να αντιμετωπιστούν (Abbas, 2004).
Ο σημαντικότερος αλγόριθμος που έχει προταθεί και που βασίζεται στη προσομοίωση του φυσικού ανοσοποιητικού συστήματος είναι ο αλγόριθμος επιλογής κλώνων (Clonal Selection Algorithm). Ο αλγόριθμος της επιλογής κλώνων εμπνέεται από την επιλογή κλώνων και τη διαδικασία μετάλλαξης των Β-κυττάρων από τη στιγμή που το ανοσοποιητικό σύστημα εντοπίσει ένα παθογόνο. Ο σκοπός της διαδικασίας επιλογής κλώνων είναι η δημιουργία μιας μεγάλης ποσότητας αντισωμάτων (τα αντισώματα είναι γλυκοπρωτεΐνες (πρωτεΐνες και υδρογονάνθρακες) οι οποίες εκκρίνονται στο αίμα σαν απάντηση σε ένα ερέθισμα που προέρχεται από ένα αντιγόνο και εξουδετερώνουν το αντιγόνο μέσω της σύνδεσης τους με αυτό) τα οποία θα ταιριάζουν σε μεγάλο βαθμό με συγκεκριμένα αντιγόνα. Προσαρμόζοντας την παραπάνω έννοια προκειμένου να δημιουργήσουμε ένα αλγόριθμο, τα αντισώματα μπορεί να θεωρηθεί ότι είναι οι πιθανές λύσεις, τα αντιγόνα είναι τα δεδομένα δοκιμής ενώ ο βαθμός ταιριάσματος μεταξύ ενός αντισώματος και ενός αντιγόνου αναπαριστά την καταλληλότητα ή την ποιότητα της λύσης. Ο στόχος είναι η δημιουργία ενός αρχικού πληθυσμού, η εφαρμογή του αλγορίθμου με το σύνολο των δεδομένων και η επαναληπτική χρήση του αλγορίθμου προκειμένου να βελτιωθεί η ποιότητα των λύσεων στον πληθυσμό. Ο αλγόριθμος έχει εφαρμοστεί στο πρόβλημα της αξιολόγησης του πιστωτικού κινδύνου.
* Λέκτορας, Εργαστήριο Συστημάτων Υποστήριξης Αποφάσεων, Τμήμα Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Πολυτεχνειούπολη, 73100 Χανιά, E-mail: marinakis@ergasya.tuc.gr
* Ερευνήτρια, Εργαστήριο Ελέγχου Βιομηχανικών Συστημάτων, Τμήμα Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Πολυτεχνειούπολη, 73100 Χανιά, E-mail: magda@dssl.tuc.gr
* Καθηγητής και Διευθυντής του Εργαστηρίου Συστημάτων Χρηματοοικονομικής Διοίκησης, Τμήμα Μηχανικών Παραγωγής και Διοίκησης, Πολυτεχνείο Κρήτης, Πολυτεχνειούπολη, 73100 Χανιά, E-mail: kostas@dpem.tuc.gr
Βιβλιογραφία
Abbas, A. K., Lichtman, A. H. (2004). Basic Immunology: Functions and Disorders of the Immune System, Saunders.
Dasgupta, D. (Ed.) (1998). Artificial Immune Systems and their Application, Springer, Heidelberg.
De Castro, L.N., Timmis, J. (2002). Artificial Immune Systems: A New Computational Intelligence Approach, Springer, Heidelberg.
Dorigo, M., Maniezzo, V., Colorni, A. (1996). The Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, 26, 1-13.
Dorigo, M., Stutzle, T., (2004). Ant Colony Optimization, A Bradford Book, The MIT Press Cambridge, Massachusetts, London, England.
Engelbrecht Andries P. (2007). Artificial Immune Models, Computational Intelligence. An introduction, Publisher John Wiley & Sons.
Goldberg D. E., Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, INC, Massachussets, 1989.
Holland J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.
Marinakis, Y., Marinaki, M. (2010). A Hybrid Genetic – Particle Swarm Algorithm for the Vehicle Routing Problem, Expert Systems with Applications, 37, 1446-1455.
Marinakis, Y., Marinaki, M., Doumpos, M., Zopounidis, C. (2009a). Ant Colony and Particle Swarm Optimization for Financial Classification Problems, Expert Systems with Applications, 36, 7, 10604-10611.
Marinakis, Y., Marinaki, M., Doumpos, M., Matsatsinis, N., Zopounidis, C. (2009b). A Hybrid ACO-GRASP Algorithm for Clustering Analysis, Annals of Operations Research, (available on line ? DOI: 10.1007/s10479-009-0519-2).
Marinakis, Y., Marinaki, M., Dounias, G., Jantzen, J., Bjerregaard, B. (2009c). Intelligent and Nature Inspired Optimization Methods in Medicine: The Pap-Smear Cell Classification Problem, Expert Systems. The Journal of Knowledge Engineering, 26, 5, 433-457.
Reeves, C. R., Genetic Algorithms, Modern Heuristic Techniques for Combinatorial Problems, Reeves, C. R. (ed.), McGraw – Hill, London, 1995, 151-196.
Reeves C. R., Genetic Algorithms, Handbooks of Metaheuristics, F. Glover, G.A. Kochenberger (eds.), Kluwer Academic Publishers, Dordrecht, 2003, 55-82.
