ΥΠΟΛΟΓΙΣΤΙΚΗ ΝΟΗΜΟΣΥΝΗ ΙΙ
Πολύ συχνά στα προβλήματα βελτιστοποίησης που καλούνται να δώσουν λύσεις οι Γ.Α., οι αντικειμενικές συναρτήσεις έχουν κάποιους περιορισμούς, όσον αφορά το πεδίο ορισμού τους, που πρέπει αυστηρά να ικανοποιούνται. Το γεγονός αυτό πρέπει να λαμβάνεται υπ' όψη στο σχεδιασμό ενός Γ.Α., ώστε να είναι δυνατός ο εντοπισμός νόμιμων λύσεων.
Οι περιορισμοί στις
αντικειμενικές συναρτήσεις εκφράζονται συνήθως με δύο τρόπους: με ισότητες και
ανισότητες (ή ανισο-ισότητες). Ωστόσο, αυτές οι δύο κατηγορίες περιορισμών
μπορούν να αναχθούν σε μία, αφού κάθε ισότητα μπορεί να μετατραπεί σε δύο
ανισότητες (π.χ. η ικανοποίηση της ισότητας
μετατρέπεται στην ταυτόχρονη ικανοποίηση των ανισοτήτων
και
). Συνεπώς, μιλώντας για περιορισμούς εννοούμε ανισότητες.
Εκ πρώτης όψεως, ίσως να δημιουργείται η απορία γιατί προκαλεί αναστάτωση ο χειρισμός των περιορισμών. Θα μπορούσε κάποιος να υποστηρίξει ότι, όταν προκύπτουν λύσεις που είναι έξω από το πεδίο ορισμού της συνάρτησης ικανότητας, να αγνοούνται από τον αλγόριθμο (αφού δεν ορίζεται γι' αυτές τιμή απόδοσης) και στη θέση τους να παράγονται άλλες που είναι αποδεκτές.
Η ιδέα αυτή δεν είναι άσχημη, αλλά αποδεικνύεται ανεπαρκής για περιπτώσεις προβλημάτων με πολύ μεγάλο αριθμό περιορισμών, στα οποία ο εντοπισμός ενός νόμιμου σημείου μπορεί να είναι ανάλογης δυσκολίας με τον εντοπισμό του ζητούμενου βέλτιστου σημείου. Σε τέτοια προβλήματα συμφέρει τα μη νόμιμα σημεία να αντιμετωπίζονται ως σημεία χαμηλής απόδοσης και να μην αγνοούνται εντελώς. Αντιμετωπίζονται δηλαδή τα μη νόμιμα σημεία ως φορείς πληροφορίας που αξιοποιείται αποδοτικά από τον Γ.Α. Αυτό υλοποιείται με την εκχώρηση σε αυτά αποδόσεων χαμηλής απόδοσης που είναι ανάλογη του βαθμού παραβίασης των περιορισμών. Η μέθοδος αυτή ενσωμάτωσης των περιορισμών σε ένα Γ.Α. ονομάζεται μέθοδος της ποινής (penalty method).
Με την εφαρμογή αυτής της μεθόδου ένα πρόβλημα με περιορισμούς εύκολα μετατρέπεται σε ένα ισοδύναμο χωρίς περιορισμούς: απλά κάθε παραβίαση περιορισμού συσχετίζεται με ένα κόστος (μια ποινή). Για παράδειγμα, έστω το ακόλουθο πρόβλημα ελαχιστοποίησης:
ελαχιστοποίησε το
με τον περιορισμό
,
όπου
διάνυσμα διάστασης
.
To πρόβλημα αυτό μετατρέπεται στο ακόλουθο ισοδύναμο:
ελαχιστοποίησε το
,
όπου η συνάρτηση ποινής και
ο συντελεστής ποινής.
Τα
και
καθορίζονται από τον σχεδιαστή του Γ.Α.