{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"Lab 9.1 Εξελικτική βελτιστοποίηση με Γενετικούς Αλγόριθμους.ipynb","provenance":[]},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"code","metadata":{"id":"imdbZtWOms6L"},"source":["import matplotlib.pyplot as plt\n","%matplotlib inline"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"pUCqS61P9JIV"},"source":["# πρέπει να υπάρχει το auxiliary.py\n","!ls\n","#!rm auxiliary.py*"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"829ExOhdms6T"},"source":["# Εισάγουμε τις βοηθητικές συναρτήσεις απο το auxiliary.py\n","from auxiliary import *"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"egITKEzqms6Y"},"source":["# Επίλυση προβλήματος βελτιστοποίησης με γενετικούς αλγορίθμους\n","\n"]},{"cell_type":"markdown","metadata":{"id":"Y0ZhniqnnT8l"},"source":["\n","## 1 Ένα απλό παράδειγμα προβλήματος ελαχιστοποίησης\n","\n","Ας θεωρήσουμε ότι ψάχνουμε να βρούμε την ελάχιστη τιμή της συνάρτησης\n","$$\n","   y(x) = -x \\, \\sin{(x)}\n","$$\n","στο διάστημα $[0, 4\\,\\pi]$.\n","\n","Η συνάρτηση $y(x)$ είναι η *συνάρτηση μοντέλο* και σχετίζεται άμεσα με την *αντικειμενική συνάρτηση* που θα εξηγήσουμε πιο κάτω. Η έξοδός της μας χρησιμεύει για να υπολογίζουμε τις *αντικειμενικές τιμές* που αποτελούν το βασικό στοιχείο για να αποφασίσουμε αν μια τιμή $x$ είναι καλή ή κακή.\n","\n","Εκτυπώνουμε τη συνάρτηση:"]},{"cell_type":"code","metadata":{"id":"G1U9qncSms6Z"},"source":["# model function\n","def y(x): return -x * sin(x)\n","\n","# plot model function\n","xcurve = linspace(0.0, 4*pi, 101)\n","plt.plot(xcurve, y(xcurve), label='y(x)')\n","Gll('x', 'y')\n","plt.grid(True)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"p2NKma_6ms6h"},"source":["Παρατηρούμε ότι η συνάρτηση στο διάστημα που εξετάζουμε έχει τόσο τοπικό ελάχιστο όσο και ολικό ελάχιστο. Το πρώτο είναι περίπου στο $x=2$ και το δεύτερο περίπου στο $x=8$ (για την ακρίβεια το ολικό ελάχιστο που προκύπτει αναλυτικά στο συγκεκριμένο διάστημα ορισμού είναι $-7.9167$ για $x=7.9786$ περίπου). Η παρουσία τοπικών ελαχίστων μπορεί να δυσκολέψει συμβατικές μεθόδους επίλυσης, εκεί που  ακόμα και απλοί γενετικοί αλγόριθμοι μπορούν να επιτύχουν."]},{"cell_type":"code","metadata":{"id":"eCm1dcr7ms6i"},"source":["# initialise random numbers generator\n","seed(1234) # use a fixed seed, so every time we run this code\n","           # we will get the same results\n","\n","# population\n","ninds = 10                   # number of individuals: population size\n","xmin, xmax = 0.0, 4.0*pi      # limits\n","X = Random(ninds, xmin, xmax) # generate numbers between 0 and 4*pi\n","\n","# just for the sake of showing nice numbers in this notebook:\n","X = array(X, dtype=int)    # truncate values\n","X = array(X, dtype=float)  # revert to float\n","print('Population:\\n', X)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"EghWTdilms6h"},"source":["## 2 Πληθυσμός\n","\n","Ξεκινάμε θεωρώντας ότι δεν έχουμε καμία ιδέα για το ποια μπορεί να είναι η λύση, δηλαδή το $x$ τέτοιο ώστε το $y(x)$ να είναι ένα ολικό ελάχιστο.\n","\n","Για αρχή ας δημιουργήσουμε τιμές του $x$ μεταξύ $0$ και $4\\,\\pi$ ελπίζοντας ότι κάποιες θα είναι καλές υποψήφιες λύσεις:"]},{"cell_type":"markdown","metadata":{"id":"2uqOlDFtms6l"},"source":["Για λόγους οπτικοποίησης θα τυπώσουμε αυτές τις τιμές του  **αρχικού πληθυσμού** πάνω στη γραφική παράσταση της συνάρτησης:"]},{"cell_type":"code","metadata":{"id":"Wi5M6hZzms6l"},"source":["plt.plot(xcurve, y(xcurve), label='y(x)')\n","plt.plot(X, y(X), 'ro', label='population')\n","Gll('x', 'y', 'upper left')\n","plt.grid(True)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"1xDlHf8Kms6o"},"source":["Διαπιστώνουμε ότι στο διάστημα $0$ με $4\\,\\pi$ έχουμε τρεις καλές υποψήφιες λύσεις $x=7$, $x=9$ και ξανά $x=9$\n","\n","Στην ορολογία των γενετικών, κάθε μια από αυτές τις τιμές $x \\in X$ αποτελεί ένα *άτομο* και το σύνολό τους συνιστά έναν **πληθυσμό**."]},{"cell_type":"markdown","metadata":{"id":"3g4DmZ1rms6p"},"source":["## 3 Χρωμοσώματα\n","\n","Κάθε άτομο μπορεί να διαιρεθεί περαιτέρω σε **γονίδια**, το σύνολο των οποίων ορίζει το **χρωμόσωμα** του ατόμου. Θα μπορούσαμε να χρησιμοποιήσουμε διαφόρων τύπων υποδιαιρέσεις του $x$ αλλά εδώ θα χρησιμοποιήσουμε μια απλή τυχαία υποδιαίρεση.\n","\n","Για παράδειγμα, για $x=10$ μπορούμε να πάρουμε το χρωμόσωμά του ως εξής:"]},{"cell_type":"code","metadata":{"id":"RFrvwUPcms6p"},"source":["ngenes = 5\n","c10 = SimpleChromo(10, ngenes)\n","print (c10, ' sum(c10) =', sum(c10))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"DTxuoXekms6s"},"source":["όπου η ποσότητα 10 έχει χωριστεί σε 5 τιμές το άθροισμα των οποίων δίνει ξανά 10. Συνεπώς το **μοντέλο αναπαράστασης** που αντιστοιχίζει τα γονίδια και το χρωμόσωμα στο άτομο είναι μια απλή πρόσθεση.\n","\n","Ορίζουμε για μελλοντική χρήση δύο συναρτήσεις που μας δίνουν το χρωμόσωμα από ένα άτομο  και το άτομο από ένα χρωμόσωμα:"]},{"cell_type":"code","metadata":{"id":"Zrw6zuETms6t"},"source":["# compute chromosome from x\n","def cFcn(x): return SimpleChromo(x, ngenes)\n","\n","# compute x from chromosome\n","def xFcn(c): return sum(c)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"X7pRhsDqms6v"},"source":["Κατά τη διαδικασία της *αναπαραγωγής* τα γονίδια των χρωμοσωμάτων από τους διάφορους γονείς θα αναμειχθούν και θα τροποποιηθούν με τις διαδικασίες της διασταύρωσης και της μετάλλαξης.\n","\n","Υπολογίζουμε στον πίνακα C τα χρωμοσώματα για όλα τα άτομα του πληθυσμού $Χ$:"]},{"cell_type":"code","metadata":{"id":"WZjTfj3-ms6w"},"source":["C = array([cFcn(x) for x in X])\n","print(C)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"zFFazsamms6z"},"source":["## 4 Αντικειμενική συνάρτηση\n","\n","Η **αντικειμενική συνάρτηση** (ή συνάρτηση αποτίμησης) είναι όμοια με τη *συνάρτηση μοντέλο* αλλά επιπρόσθετα επιβάλλει και τον περιορισμό του διαστήματος $0 \\leq x \\leq 4\\,\\pi$. Για να το επιτύχουμε αυτό, μια τεχνική είναι να επιβάλουμε μια υψηλή ποινή στις τιμές που είναι εκτός του διαστήματος. \n","\n","Επιπρόσθετα είναι βολικό να υλοποιήσουμε την αντικειμενική συνάρτηση ως συνάρτηση του χρωμοσώματος.\n","\n","Μια επιλογή αντικειμενικής συνάρτησης θα μπορούσε να είναι: "]},{"cell_type":"code","metadata":{"id":"Kf6wTDuqms60"},"source":["def objFcn(c):\n","    x = xFcn(c)\n","    if x < xmin or x > xmax: return 100.0*(1.0+abs(x))\n","    return y(x)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"B82kODl3ms62"},"source":["όπου χρησιμοποιούμε την τιμή $100(1+|x|)$ ως ποινή για τιμές του $x$ εκτός $[0, 4\\,\\pi]$.\n","\n","Μπορούμε να τυπωσουμε όλες τις  **αντικειμενικές τιμές** ως εξής:"]},{"cell_type":"code","metadata":{"id":"TjlKcEgDms62"},"source":["Y = array([objFcn(c) for c in C]) # objective values\n","PrintPop(C, Y, xFcn, showC=True)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"jWN4drPims65"},"source":["όπου $x$ τα *άτομα*, $y$ οι *αντικειμενικές τιμές* και οι τελευταίες 5 στήλες το *χρωμόσωμα* κάθε ατόμου με τα 5 *γονίδια*."]},{"cell_type":"markdown","metadata":{"id":"79AiXTf4ms66"},"source":["## 5 Καταλληλότητα και ταξινόμηση\n","\n","Πριν το στάδιο της αναπαραγωγής θα πρέπει να επιλεχθούν άτομα (σε ζευγάρια) από τον πληθυσμό. Για το λόγο αυτό πρέπει να οριστεί μία συνάρτηση *καταλληλότητας* (fitness function).\n","\n","Για το πρόβλημα ελαχιστοποίησής μας, η συνάρτηση καταλληλότητας $f(x)$ μπορεί να είναι απλά μια συνάρτηση που αντιστοιχίζει γραμμικά τα $y(x)$ στο διάστημα  $[0, 1]$ με τον ακόλουθο τρόπο:\n","$$\n","    f(x) = \\frac{y_{max} - y(x)}{y_{max} - y_{min}}\n","$$\n","Κατά αυτό τον τρόπο, αν το $x_{best}$ είναι τέτοιο ώστε $y(x_{best})=y_{min}$, τότε  $f(x_{best})=1$. Αντίθετα, αν το $x_{worst}$ είναι τέτοιο ώστε $y(x_{worst})=y_{max}$, τότε $f(x_{worst})=0$. Συνεπώς, $1$ σημαίνει \"καλό\" άτομο (καταλληλότερο) και $0$ σημαίνει \"κακό\".\n","\n","Επιπρόσθετα, για τους επόμενους υπολογισμούς ο πληθυσμός πρέπει να **ταξινομηθεί** σε φθίνουσα σειρά καταλληλότητας, δηλαδή στην κορυφή να βρίσκονται τα καλύτερα άτομά του.\n","\n","Μπορούμε να υπολογίσουμε την καταλληλότητα των ατόμων και να τα ταξινομήσουμε ως εξής:"]},{"cell_type":"code","metadata":{"id":"Oqah5bZgms66"},"source":["# compute fitness from objective values\n","F = Fitness(Y) \n","\n","\n","# sort in decreasing order of fitness\n","C, Y, F = SortPop(C, Y, F)\n","PrintPop(C, Y, xFcn, F)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"wYl_e6XRms6-"},"source":["Διαπιστώνουμε ότι τα άτομα με $x=7$ και $x=9$ (υπάρχουν δύο τέτοια άτομα) είναι μεταξύ των καλύτερων (μικρότερη τιμή $y$). Αυτό το είχαμε διαπιστώσει και οπτικά στη γραφική παράσταση καθώς τα αντίστοιχα σημεία είναι κοντά στο ολικό ελάχιστο."]},{"cell_type":"markdown","metadata":{"id":"IK2990Bbms7A"},"source":["## 6 Πιθανότητες\n","\n","Το επόμενο βήμα πριν επιλέξουμε άτομα είναι να υπολογίσουμε την **πιθανότητα** κάθε ατόμο να εισέλθει στο στάδιο της αναπαραγωγής. Αυτό το επιτυγχάνουμε με απλό τρόπο διαιρώντας την κάθε τιμή καταλληλότητας με το άθροισμα όλων των τιμών καταλληλότητας:\n","$$\n","p_i = \\frac{f_i}{\\sum_k^{nind} f_k}\n","$$\n","όπου $p_i$ είναι η πιθανότητα του ατόμου $i$ με $x_i$.\n","\n","Στη συνέχεια θα μας χρειαστεί και η συσσωρευτική πιθανότητα οπότε χρησιμοποιούμε το $Μ$ για για να αποθηκεύσουμε τις αντίστοιχες τιμές."]},{"cell_type":"code","metadata":{"id":"-SQWn2b7ms7A"},"source":["# probabilities\n","P = F / sum(F)\n","\n","# cumulated probabilities\n","M = cumsum(P)\n","PrintPop(C, Y, xFcn, F, P, M)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"iPxguAhXms7D"},"source":["## 7 (Φυσική) Επιλογή\n","\n","Στην απλή μορφή ενός γενετικού αλγόριθμου είναι σύνηθες να αντικαθιστούμε έναν πληθυσμό με τον ίδιο αριθμό ατόμων. Συνεπώς για έναν πληθυσμό με $N_{ind}$ άτομα πρέπει να διαλέξουμε $N_{ind}/2$ ζευγάρια.\n","\n","Η επιλογή πρέπει να γίνει κατά τέτοιο τρόπο ώστε η γενετική πληροφορία των καταλληλότερων ατόμων να έχει μεγαλύτερες πιθανότητες επιβίωσης, δηλαδή να περάσει στην επόμενη γενιά. Για να το πετύχουμε αυτό θα χρησιμοποιήσουμε τις πιθανότητες (επιβίωσης) των ατόμων που υπολογίσαμε προηγουμένως.\n","\n","Μια απλή μέθοδος για να να πραγματοποιήσουμε μια τέτοια μεροληπτική επιλογή είναι ο αποκαλούμενος **μηχανισμός ρουλέτας**. Στη μέθοδο αυτή, μπορούμε να φανταστούμε ότι η ρουλέτα είναι έτσι φτιαγμένη ώστε κάθε τμήμα της (θα ήταν αριθμός σε μια κανονική ρουλέτα) που αντιστοιχεί σε κάθε άτομο είναι φτιαγμένο έτσι ώστε να έχει μέγεθος ανάλογο της πιθανότητας του αριθμού. Η ρουλέτα περιστρέφεται προς τη μία κατεύθυνση και η μπίλια ρίχνεται μέσα της προς την αντίθετη κατεύθυνση. Ένα άτομο επιλέγεται όταν η μπίλια κάτσει στο τμήμα που του αντιστοιχεί. Η διαδικασία επαναλαμβάνεται ώστε να διαλέξουμε περισσότερα άτομα. Προφανώς μπορεί να διαλέξουμε το ίδιο άτομο περισσότερες φορές. \n","\n","Για να οπτικοποιήσουμε τον αλγόριθμο επιλογής του μηχανισμού ρουλέτας, δημιουργούμε το ακόλουθο γράφημα όπου τα τμήματα που αντιστοιχούν στα άτομα κατανέμονται κατά τον οριζόντιο άξονα:"]},{"cell_type":"code","metadata":{"id":"7G92aw3pms7D"},"source":["X = xFcn(C.T) # we first sort the individuals by decreasing fitness value\n","PlotProbBins(X, P)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"TNGDoGKjms7G"},"source":["Παρατηρούμε ότι τα τμήματα με $x=7$ και $x=9$ είναι τα μεγαλύτερα.\n","\n","Ας υποθέσουμε ότι θέλουμε να διαλέξουμε 5 άτομα. Πρώτα δημιουργούμε 5 τυχαίους αριθμούς στο $[0, 1)$ "]},{"cell_type":"code","metadata":{"id":"dzm9jcqEms7H"},"source":["sample = random(5)\n","print(sample)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"ervzVJBMms7J"},"source":["Στη συνέχεια με τη βοήθεια του σχήματος και των συσσωρευτικών πιθανοτήτων βλέπουμε ποια άτομα επιλέγονται με βάση τους τυχαίους αριθμούς. \n","\n","Το βοηθητικό αρχείο auxiliary.py περιλαμβάνει μια συνάρτηση που υλοποιεί το μηχανισμό ρουλέτας:"]},{"cell_type":"code","metadata":{"id":"Pdr025Xems7K"},"source":["S = RouletteSelect(M, 5, sample)\n","print('indices of selected individuals:\\n', S)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"L7Qul1Cpms7N"},"source":["## 8 Διασταύρωση\n","\n","Αφού επιλεχθούν τα άτομα υπάρχει πιθανότητα ($p_{c}$) το γενετικό τους υλικό να αναμειχθεί κατά την αναπαραγωγή. Αυτή η διαδικασία είναι γνωστή ως *διασταύρωση*. Υπολογιστικά η διασταύρωση πραγματοποιείται επιλέγοντας τυχαία το σημείο διασταύρωσης ($pos$) μεταξύ των γονιδίων το οποίο χρησιμοποιείται για να αντιγράψουμε μερικώς το χρωμόσωμα κάθε γονέα στη νέα γενιά.\n","\n","Ένα παράδειγμα θα ήταν το ακόλουθο:"]},{"cell_type":"code","metadata":{"id":"AHip_FKtms7O"},"source":["# crossover between the first two individuals\n","pos = randint(1, ngenes-1)\n","A, B = C[0], C[1]\n","a = hstack([A[:pos], B[pos:]])\n","b = hstack([B[:pos], A[pos:]])\n","print('pos =', pos)\n","print('parent A =', A)\n","print('parent B =', B)\n","print('child  a =', a)\n","print('child  b =', b)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"yuncBWB-ms7Q"},"source":["το οποίο μπορούμε να απεικονίσουμε και σχηματικά:"]},{"cell_type":"code","metadata":{"id":"fIH9CI-cms7R"},"source":["DrawCrossover(A, B, a, b, pos)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"tkbql3PSms7T"},"source":["όπου βλέπουμε ότι οι απόγονοι έχουν γενετικό υλικό και από τους δύο γονείς."]},{"cell_type":"markdown","metadata":{"id":"4p7lSgkqms7T"},"source":[" ## 9 Μετάλλαξη\n","\n","Με μικρή πιθανότητα ($p_m$) και αρκετά σπάνια τα γονίδια του χρωμοσώματος τροποποιούνται τυχαία. Αυτό αντιπροσωπεύει το φαινόμενο της *μετάλλαξης* και βοηθάει στην ανακάλυψη νέων τιμών δεδομένων που ιδανικά θα μας είναι χρήσιμα (θα είναι πιο κοντά στο βέλτιστο). Φυσικά η μετάλλαξη μπορεί να οδηγήσει και σε χειρότερα άτομα, ωστόσο η φυσική επιλογή θα μας προστατεύσει από το να επιβιώσουν τέτοια χειρότερα άτομα σε επόμενες γενεές.\n","\n","Η επίδραση του φαινομένου της μετάλλαξης είναι να διευρύνει το **χώρο αναζήτησης λύσεων** και είναι βασικός παράγοντας για να αποφεύγουμε να παγιδευόμαστε σε τοπικά ελάχιστα.\n","\n","Μαθηματικά θα μπορούσαμε να χρησιμοποιήσουμε πάρα πολλές διαφορετικές στρατηγικές μετάλλαξης. Ωστόσο, γενικά η στρατηγική προκύπτει από την ανάλυση κάθε διαφορετικού προβλήματος ξεχωριστά.\n","\n","Στο παράδειγμά μας μοντελοποιούμε τη μετάλλαξη απλά προσθέτωντας ή αφαιρώντας από ένα τυχαίο γονίδιο 110% της τιμής του μεγαλύτερου γονιδίου:"]},{"cell_type":"code","metadata":{"id":"3TmYmOOqms7U"},"source":["# apply mutation to new individual 'a'\n","print('before: a =', a)\n","pos = randint(0, ngenes) # position\n","bmax = max(a)\n","if FlipCoin(0.5): a[pos] += bmax * 1.1\n","else:             a[pos] -= bmax * 1.1\n","print('after:  a =', a)\n","print('pos =', pos, ' bmax =', bmax)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"0MR8FsDxms7W"},"source":["## 10 Εξέλιξη\n","\n","Τα προηγούμενα βήματα συνδυάζονται σε ένα βρόχο που αντιπροσωπεύει την **εξέλιξη**, δηλαδή την επαναλαμβανόμενη διαδοχική αντικατάσταση πληθυσμών με νεότερους.\n","\n","Μετά από έναν αριθμό γενεών $n_{gen}$ (δηλαδή επαναλήψεις του βρόχου), τα άτομα του πληθυσμού αναμένουμε να είναι πιο κοντά στη βέλτιση λύση. Ωστόσο, όπως και στη φύση, δεν υπάρχει τρόπος να πούμε \"η εξέλιξη πρέπει να σταματήσει\". Συνεπώς δεν είναι προφανές το πώς αποφασίζουμε για το μέγιστο αριθμό γενεών.\n","\n","Μια στρατηγική θα μπορούσε να είναι η ταχύτητα σύγκλισης της βέλτιστης αντικειμενικής τιμής. Μπορούμε επίσης ακόμα πιο απλά να πάρουμε έναν \"επαρκή\" αριθμό γενεών.\n","\n","Τα βήματα της διασταύρωσης και μετάλλαξης συνήθως αποκαλούνται φάση της **αναπαραγωγής**.\n","\n","Μπορούμε επίσης να εξετάσουμε αν ο αλγόριθμος αποδίδει καλύτερα αν σε κάθε γενιά αντιγράψουμε αυτούσιο το καλύτερο άτομο της προηγούμενης γενιάς στη θέση του χειρότερου ατόμου της νέας γενιάς. Με αυτό τον τρόπο, οι βέλτιστες λύσεις που βρίσκονται σε κάποια γενιά δεν καταστρέφονται ποτέ. Αυτό το βήμα αντιστοιχεί στη διαδικασία του **ελιτισμού**. Φυσικά στρατηγικές ελιτισμού μπορουν να υλοποιηθούν και με περισσότερα (βέλτιστα) άτομα.\n","\n","Το προϊόν του συνδυασμού όλων των παραπάνω είναι ο **Απλός Γενετικός Αλγόριθμος** (SGA) που ακολουθεί:"]},{"cell_type":"code","metadata":{"id":"9LBsNPaMms7W"},"source":["def Evolve(C, xFcn, objFcn, ngen=10, elite=True, pc=0.8, pm=0.01, verb=False, showC=False):\n","\n","    # objective values\n","    Y = array([objFcn(c) for c in C]) # objective values\n","    ninds = len(C)\n","    ngenes = len(C[0])\n","\n","    # fitness and probabilities (sorted)\n","    F = Fitness(Y)\n","    C, Y, F = SortPop(C, Y, F)\n","    P = F / sum(F)\n","    M = cumsum(P)\n","\n","    # results\n","    OV = zeros(ngen+1)\n","    OV[0] = Y[0] # best first objective value\n","\n","    # evolution\n","    for gen in range(ngen):\n","\n","        # best individual\n","        bestC = C[0].copy()\n","        bestY = Y[0]\n","\n","        # print generation\n","        if gen==0 or verb:\n","            print\n","            PrintPop(C, Y, xFcn, F, showC=showC)\n","\n","        # selection\n","        S = RouletteSelect(M, ninds)\n","        idxA, idxB = FilterPairs(S)\n","        \n","        # reproduction\n","        Cnew = [] # new chromosomes\n","        for k in range(ninds//2):\n","\n","            # parents\n","            A, B = C[idxA[k]], C[idxB[k]]\n","\n","            # crossover\n","            if FlipCoin(pc):\n","                pos = randint(1, ngenes-1)\n","                a = hstack([A[:pos], B[pos:]])\n","                b = hstack([B[:pos], A[pos:]])\n","            else:\n","                a, b = A.copy(), B.copy()\n","\n","            # mutation\n","            if FlipCoin(pm):\n","                pos  = randint(0, ngenes)\n","                bmax = max(a)\n","                if FlipCoin(0.5): a[pos] += bmax * 1.1\n","                else:             a[pos] -= bmax * 1.1\n","\n","            # new individuals\n","            Cnew.append(a)\n","            Cnew.append(b)\n","\n","        # new population\n","        C = array(Cnew)\n","        Y = array([objFcn(c) for c in C]) # objective values\n","        F = Fitness(Y)\n","\n","        # elitism\n","        if elite:\n","            I = F.argsort()[::-1] # the [::-1] is a trick to reverse the sorting order\n","            best  = I[0]\n","            worst = I[len(I)-1]\n","            if bestY < Y[worst]:\n","                C[worst] = bestC\n","                Y[worst] = bestY\n","                F = Fitness(Y)\n","\n","        # probabilities (sorted)\n","        C, Y, F = SortPop(C, Y, F)\n","        P = F / sum(F)\n","        M = cumsum(P)\n","\n","        # objective values\n","        OV[gen+1] = Y[0] # best current objective value\n","\n","    # results\n","    return C, Y, OV"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"tCli0Zfjms7Y"},"source":["τον οποίο μπορούμε να χρησιμοποιήσουμε ως εξής:"]},{"cell_type":"code","metadata":{"id":"7H4hZbVVms7Z"},"source":["# input data\n","#ninds  = 10    # number of individuals: population size\n","#ngenes = 5     # number of genes in the chromosome\n","ngen   = 100    # number of generations\n","pc     = 0.8   # probability of crossover\n","pm     = 0.01  # probability of mutation\n","elite  = 1     # use elitism\n","verb   = True # verbose\n","\n","# run GA\n","C, Y, OV = Evolve(C, xFcn, objFcn, ngen, elite, verb=verb, showC=False)\n","X = [xFcn(c) for c in C]\n","\n","# print and plot\n","plt.subplot(2, 1, 1)\n","plt.plot(xcurve, y(xcurve), label='y(x)')\n","\n","print ('\\nFinal population:')\n","PrintPop(C, Y, xFcn)\n","sol = '\\nSolution: x=%g y=%g' % (X[0], Y[0])\n","print (sol)\n","\n","# plot results\n","plt.subplot(2, 1, 1)\n","plt.plot(X, Y, 'k*', label='final population')\n","Gll('x', 'y', 'upper left')\n","plt.grid(True)\n","\n","# plot convergence graph\n","plt.subplot(2, 1, 2)\n","G = range(ngen+1)\n","plt.plot(G, OV, 'b.-', label=sol)\n","Gll('generation', 'y(x)')\n","plt.grid(True)\n","plt.show()"],"execution_count":null,"outputs":[]}]}