1.2 Παραδοσιακες μεθοδοι αναζητησης και βελτιστοποιησης
Οι μέθοδοι αναζήτησης και βελτιστοποίησης που παρουσίασαν αξιόλογα αποτελέσματα, όσον αφορά την εφαρμογή τους σε υπολογιστικές μηχανές και κυριάρχησαν για πολλά χρόνια είναι οι εξής [8]:
· Μέθοδοι βασισμένες στο λογισμό (calculus-based methods): Έχουν γίνει αντικείμενο ευρείας μελέτης. Χωρίζονται σε δύο βασικές κατηγορίες: τις έμμεσες και τις άμεσες. Οι έμμεσες ασχολούνται με την εύρεση τοπικών ακρότατων επιλύνοντας συνήθως ένα σύνολο μη γραμμικών συναρτήσεων. Οι άμεσες από την πλευρά τους, ψάχνουν για τοπικά ακρότατα κάνοντας μικρά άλματα στη συνάρτηση (hill-climbing). Αν και αρκετά δοκιμασμένες και οι δύο κατηγορίες παρουσιάζουν σημαντικά μειονεκτήματα. Το βασικότερο από αυτά είναι ότι εμφανίζουν τοπικότητα στην εμβέλεια. Το ακρότατο το οποίο βρίσκουν είναι το καλύτερο στη γειτονιά ενός σημείου.
· Απαριθμηστικές (enumerative) ή τυχαίες (random) μέθοδοι: Συναντώνται σε πολλές μορφές και σε διάφορα προβλήματα. Μέσα σε ένα πεπερασμένο (ή άπειρα διακριτό) χώρο αναζήτησης, αναζητούνται κάποια βέλτιστα σημεία με ένα προς ένα ψάξιμο. Παρ' όλο που η απλότητα εδώ είναι ελκυστική, η αποδοτικότητα είναι προφανές ότι είναι πολύ χαμηλή κάτι που δεν τις κάνει ιδιαίτερα δημοφιλείς. Σχεδόν ποτέ δεν χρησιμοποιούνται μόνες τους, αλλά σε συνδυασμό με άλλες αποδοτικότερες μεθόδους.
· Μέθοδοι επαναληπτικής αναζήτησης (iterated search): Πρόκειται για ένα παραγωγικό συνδυασμό των μεθόδων των δύο προηγουμένων κατηγοριών. Μόλις το hill-climbing εντοπίσει μια κορυφή (τοπικό μέγιστο ή ελάχιστο), επιλέγεται τυχαία ένα νέο σημείο και αρχίζει ξανά η ίδια διαδικασία για τον εντοπισμό μιας νέας κορυφής. Αυτό γίνεται αρκετές φορές κρατώντας πάντα την καλύτερη τιμή που έχει βρεθεί. Η τεχνική αυτή έχει το πλεονέκτημα της απλότητας, δεν υπάρχει περίπτωση παγίδευσης, αλλά όταν τα τοπικά μέγιστα είναι πολλά η απόδοσή της πέφτει σημαντικά.
· Simulated annealing: Αποτελεί μια τροποποιημένη έκδοση του hill-climbing. Τα μειονεκτήματά του είναι ότι ασχολείται με μόνο μια λύση σε κάθε βήμα, ενώ δεν κάνει αξιοποίηση της πληροφορίας που έχει υποστεί επεξεργασία σε προηγούμενα στάδια, μη αποκτώντας έτσι μια γενική εικόνα του χώρου αναζήτησης [62,68].
· Δυναμικός προγραμματισμός (dynamic programming): Αποτελεί προγραμματιστική τεχνική που βρίσκει εφαρμογή σε περιορισμένη περιοχή προβλημάτων. Χρησιμοποιείται κυρίως για τη βελτιστοποίηση της λύσης ενός προβλήματος πολλαπλών φάσεων, για κάθε μία από τις οποίες είναι διαθέσιμος ένας αριθμός εναλλακτικών αποφάσεων. Είναι αυτονόητο ότι δεν αποτελεί ισχυρό εργαλείο βελτιστοποίησης λόγω της υπερβολικής εξειδίκευσης για μικρό εύρος προβλημάτων [11].
· Ευρετικές μέθοδοι (heuristic methods): Ευρετική ονομάζεται κάθε μη αλγοριθμική μέθοδος επίλυσης προβλημάτων, στην οποία η πορεία προς ένα τελικό αποδεκτό αποτέλεσμα στηρίζεται σε μια σειρά προσεγγιστικών αποτελεσμάτων. Αν και οι ευρετικές μέθοδοι δίνουν απλές και ικανοποιητικές λύσεις σε μερικά προβλήματα, τίποτα δεν εγγυάται ότι αυτές οι λύσεις είναι οι καλύτερες δυνατές. Συνήθως δίνουν προσεγγίσεις των βέλτιστων λύσεων και κάποιες φορές προτιμούνται επειδή δίνουν αποδεκτές απαντήσεις σε μικρό χρόνο. Συνεπώς δεν μπορούν να αποτελέσουν κύριο εργαλείο βελτιστοποίησης.