task1.ipynb

{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"task1.ipynb","version":"0.3.2","provenance":[]},"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"}},"cells":[{"metadata":{"id":"_cye3ASDSdX4","colab_type":"text"},"cell_type":"markdown","source":["# Στοιχεία ομάδας\n","# Ομάδα Β3\n","# Μπάκος Παναγιώτης ( 03113014 )\n","# Φώτος Νικόλαος ( 03113122 )\n","\n","---"]},{"metadata":{"id":"QcQcDqQhSdX6","colab_type":"code","outputId":"21073826-6f69-4e16-8192-bf80e9678e8b","executionInfo":{"status":"ok","timestamp":1551182307388,"user_tz":-120,"elapsed":5395,"user":{"displayName":"Νtdark 13","photoUrl":"","userId":"09958224867973618888"}},"colab":{"base_uri":"https://localhost:8080/","height":34}},"cell_type":"code","source":["!pip install deap\n","from deap import base, creator\n","from deap import tools\n","import random\n","import time\n","from math import *\n","from deap import algorithms\n","import numpy as np"],"execution_count":2,"outputs":[{"output_type":"stream","text":["Requirement already satisfied: deap in /usr/local/lib/python3.6/dist-packages (1.2.2)\n"],"name":"stdout"}]},{"metadata":{"collapsed":true,"id":"tIi8dDKBSdYA","colab_type":"text"},"cell_type":"markdown","source":["# Άσκηση 3: Βελτιστοποίηση συναρτήσεων με Γενετικούς Αλγόριθμους\n","v1.1, 16/02/2018\n","\n","<img src=\"http://infinity77.net/global_optimization/_images/Alpine01.png\" alt=\"Alpine01\" style=\"width: 500px;\"/>\n","\n","Στόχος της άσκησης είναι η βελτιστοποίηση συναρτήσεων χωρίς παραγώγους (derivative free optimization) με χρήση Γενετικών Αλγόριθμων μέσω της βιβλιοθήκης DEAP. Η βελτιστοποίηση χωρίς παραγώγους είναι ιδιαίτερα χρήσιμη σε περιπτώσεις όπου η αντικειμενική συνάρτηση $f$ δεν είναι διαθέσιμη (black-box optimization) ή σε περίπτωσεις που είναι, είναι δύσκολο ή μη πρακτικό να υπολογιστούν οι παράγωγοί της. Για παράδειγμα η  $f$ μπορεί να μην είναι διαφορίσιμη, η παραγώγιση της μπορεί να είναι δύσκολη ή να απαιτεί πολύ χρόνο,  η $f$ να περιέχει θόρυβο έτσι ώστε οι μέθοδοι που βασίζονται σε απειροστικές διαφορές να μην είναι αποτελεσματικές ή να υπάρχουν πολλά τοπικά ελάχιστα μεταξύ άλλων. \n","\n","Για περισσότερα πάνω στη βελτιστοποίηση χωρίς παραγώγους και τις εφαρμογές της, μπορείτε να συμβουλευτείτε το [\"Gradient Free Optimization\"](http://adl.stanford.edu/aa222/lecture_notes_files/chapter6_gradfree.pdf).\n","\n","---\n","\n","## Συναρτήσεις προς βελτιστοποίηση\n","Στην ομάδα μας ανατέθηκαν οι εξής συναρτήσεις :\n","* η μη-κλιμακούμενη συνάρτηση (non-scalable, δηλαδή ορίζεται για συγκεκριμένες διαστάσεις του πεδίου ορισμού) συνάρτηση **Keane** (69)\n","* η κλιμακούμενη (scalable, μπορεί να οριστεί για οποιαδήποτε διάσταση D) συνάρτηση **Stepint** (141)\n","\n","Όλες οι συναρτήσεις είναι προς **ελαχιστοποίηση**.\n","\n","Θα χρησιμοποιήσουμε ως γονίδια πραγματικούς αριθμούς και ως χρωμοσώματα λίστες γονιδίων μήκους ίσο με τη διάσταση του πεδίου ορισμού της συνάρτησης.\n","\n","---\n","\n","## Επιλογή κατάλληλου Γενετικού Αλγόριθμου\n","\n","Ο κάθε Γενετικός Αλγόριθμος χαρακτηρίζεται α) από τους γενετικούς τελεστές του δηλαδή τον ορισμό της διασταύρωσης, μετάλλαξης και επιλογής και β) από τη στρατηγική εξέλιξης που καθορίζει την εξέλιξη του πληθυσμού μέσω της διαδικασίας επιλογής, καθώς και των  πιθανοτήτων διασταύρωσης και μετάλλαξης.\n","\n","Όπως πολύ συχνά ισχύει σε προβλήματα Μηχανικής Μάθησης, η επιλογή του κατάλληλου αλγόριθμου εξαρτάται από το κάθε πρόβλημα και τα δεδομένα του. Συνεπώς για κάθε συνάρτηση θα πρέπει να δοκιμαστούν διαφορετικοί συνδυασμοί τελεστών και στρατηγικών.\n","\n","### Αξιολόγηση Γενετικών Αλγόριθμων\n","\n","Μπορούμε να πούμε ότι ένας ΓΑ είναι πιθανόν να έχει καλύτερα χαρακτηριστικά για ένα δεδομένο πρόβλημα αν:\n","- βρίσκει τη λύση (βέλτιστη τιμή) με μεγαλύτερη συχνότητα\n","- βρίσκει τη βέλτιστη λύση με μικρότερο αριθμό αποτιμήσεων της συνάρτησης καταλληλότητας\n","\n","Πρακτικά, για να αξιολογήσουμε τους αλγόριθμους της άσκησης θα φτιάξουμε μια συνάρτηση που θα αναλύει τα logfiles ως εξής:  \n","\n","Για ένα μέγιστο αριθμό γύρων (MAX_ROUNDS)  \n","&nbsp;&nbsp;&nbsp;&nbsp;Για ένα μέγιστο αριθμό γενεών (MAX_GENS)  \n","&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Για κάθε ΓΑ με δεδομένους γενετικούς τελεστές και στρατηγική εξέλιξης υπολογίζουμε τα εξής μεγέθη:\n","\n"," \n","- **avg.min:** ο μέσος όρος της ελάχιστης τιμής που πέτυχε για όλους τους γύρους.\n","- **avg.evals:** o μέσος όρος των συνολικών αποτιμήσεων (άθροιση όλων των γενεών) που έκανε για όλους τους γύρους.\n","- **avg.time:** ο μέσος χρόνος εκτέλεσης των γύρων. \n","\n","Επιπρόσθετα, επειδή δεν είναι εφικτό για κάθε συνάρτηση να αναμένουμε ότι σε λογικά χρονικά διαστήματα (ή και γενικά) θα βρούμε την ακριβή βέλτιστη λύση, ορίζουμε ως επιτυχία την ποσότητα *GOAL + DELTA*, όπου GOAL το ελάχιστο της συνάρτησης (δίνεται στο pdf) και DELTA μια θετική ποσότητα που θα ορίζουμε εμείς κάθε φορά (διαφορετική για κάθε συνάρτηση και διαφορετική ανάλογα του πόσο κοντά στη λύση θέλουμε να φτάσουμε). Με βάση την ποσότητα GOAL + DELTA ορίζουμε επιπλέον τα εξής μεγέθη:\n","- **successes:** αριθμός φορών που o ΓΑ βρήκε τιμή μικρότερη του GOAL + DELTA. Προφανώς το βέλτιστο είναι MAX_ROUNDS.\n","- **success avg. gen:** o μέσος όρος των γενεών που χρειάστηκε ο αλγόριθμος για να πέσει κάτω από GOAL + DELTA, για τους γύρους με επιτυχία. Ουσιαστικά μας ενδιαφέρει η πρώτη γενιά που πετυχαίνει τιμή κάτω από GOAL + DELTA. Σε περίπτωση που δεν πετυχαίνει αυτό το στόχο καμία γενιά, θέτουμε ‘None’ σε αυτή την ποσότητα.\n","- **success avg. min:** ο μέσος όρος των ελαχίστων των πρώτων επιτυχημένων γενεών για τους γύρους με επιτυχία. Παρόμοια, θέτουμε ‘None’ σε περίπτωση αποτυχίας.\n","- **success avg. evals:** ο μέσος όρος αποτιμήσεων που χρειάστηκαν για να πάρουμε την πρώτη τιμή κάτω από GOAL + DELTA. Και πάλι  θέτουμε ‘None’ σε περίπτωση αποτυχίας.\n","\n","Φτιάχνουμε τέλος μια βοηθητική συνάρτηση που τυπώνει συγκεντρωτικά τα αποτελέσματα ως εξής:\n","\n","| operators                      | strategy                      | successes | s.avg.min | s.avg.evals | s.avg.gens | avg.evals | avg.min   | avg.time |\n","|--------------------------------|-------------------------------|-----------|-----------|-------------|------------|-----------|-----------|----------|\n","| cxBlendLow,muGauLow,selTourLow | eaSimple 200 0.8 0.2          | 1         | 8.508e-42 | 16487       | 96         | 17014     | 9.115e-34 | 1.898    |\n","| cxBlendLow,muGauLow,selTourLow | eaMuPlusLambda 50 150 0.8 0.2 | 1         | 3.885e-41 | 14750       | 98         | 15050     | 1.631e-21 | 1.591    \n","\n","\n","---\n","\n","## 1. Βελτιστοποίηση μη κλιμακούμενης συνάρτησης\n","\n","Ο τύπος της μη-κλιμακούμενης συνάρτησης που μας ανατέθηκε είναι ο εξής :\n","\n","\\begin{equation}\n","    f(x_1,x_2) = - \\frac{\\sin^2{(x_1-x_2)}\\sin^2{(x_1+x_2)}}{\\sqrt{x_1^2+x_2^2}} , 0 \\leq x_1,x_2 \\leq 10\n","\\end{equation}\n","---\n","\n","## Βασικές έννοιες: Creator, Base, Fitness\n","\n","Οι δύο βασικές έννοιες του DEAP είναι οι Creator και Base. \n","\n","O **Creator** είναι ένα μέτα - εργοστάσιο δημιουργίας κλάσεων που θα χρησιμεύσουν στον γενετικό αλγόριθμο. Η **Base** είναι ένα δομοστοιχείο που παρέχει δύο βασικές δομές (κλάσεις) για την κατασκευή του γενετικού: το **Toolbox**, που θα χρησιμοποιήσουμε για να αποθηκέυσουμε (εισάγουμε) τους τελεστές και την (εικονική) κλάση **Fitness** που θα χρησιμοποιήσουμε για να κατασκευάσουμε το μέλος καταλληλότητας του κάθε ατόμου.\n","\n","Ας πούμε ότι θέλουμε να ορίσουμε μια συνάρτηση καταλληλότητας προς *ελαχιστοποίηση*:\n","\n","Η συνάρτηση `create` λαμβάνει τουλάχιστον __δύο ορίσματα__: το όνομα της κλάσης που θα δημιουργήσουμε και τη βασική κλάση από την οποία θα κληρονομίσει. Τα ακόλουθα ορίσματα αποτελούν χαρακτηριστικά της κλάσης. Στην περίπτωση του παραδείγματος, η νέα κλάση `FitnessMin` κληρονομεί την `base.Fitness` με χαρακτηριστικό την πλειάδα weights (-1.0,). Το (-1.0,) σημαίνει ότι θέλουμε να ελαχιστοποιήσουμε ένα μόνο κριτήριο (την τιμή της συνάρτησης f(x<sub>1</sub>,x<sub>2</sub>) ).\n","\n","Στη συνέχεια ορίζουμε την κλάση του **ατόμου** το οποίο κληρονομεί από τον τύπο *list* και περιλαμβάνει το χαρακτηρηστικό `FitnessMin`:"]},{"metadata":{"id":"DjzFExMBSdYB","colab_type":"code","colab":{}},"cell_type":"code","source":["creator.create(\"FitnessMin\", base.Fitness, weights=(-1.0,))\n","creator.create(\"Individual\", list, fitness=creator.FitnessMin)"],"execution_count":0,"outputs":[]},{"metadata":{"id":"kL1KIaUxSdYE","colab_type":"text"},"cell_type":"markdown","source":["Μπορούμε τώρα να ορίσουμε ένα στιγμιότυπο ατόμου και να υπολογίσουμε/ορίσουμε την καταλληλότητα του:"]},{"metadata":{"id":"0wTHMRFWSdYG","colab_type":"code","colab":{"base_uri":"https://localhost:8080/","height":129},"outputId":"59243aec-7968-4697-f58b-4de7734ad058","executionInfo":{"status":"error","timestamp":1551182334405,"user_tz":-120,"elapsed":798,"user":{"displayName":"Νtdark 13","photoUrl":"","userId":"09958224867973618888"}}},"cell_type":"code","source":["ind = creator.Individual([-3.02,4.59])\n","#ind.fitness.values = (sum(ind),)\n","\n","print(ind)\n","print type(ind)\n","print type(ind.fitness)\n","#print ind.fitness.values"],"execution_count":5,"outputs":[{"output_type":"error","ename":"SyntaxError","evalue":"ignored","traceback":["\u001b[0;36m  File \u001b[0;32m\"<ipython-input-5-06e86b006a11>\"\u001b[0;36m, line \u001b[0;32m5\u001b[0m\n\u001b[0;31m    print type(ind)\u001b[0m\n\u001b[0m             ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"]}]},{"metadata":{"id":"6rF6wPmcSdYL","colab_type":"text"},"cell_type":"markdown","source":["---\n","\n","### Εύρεση βέλτιστου συνδυασμού τελεστών - στρατηγικής\n","\n","\n","* Ως συνάρτηση καταλληλότητας \"evaluate\" εγγράφουμε την **`evalKeaneFunc`** που εμείς ορίσαμε προηγουμένως. \n","\n","* Στη συνέχεια εγγράφουμε ως \"mate\" τον τελεστή διασταύρωσης . Επιλέγουμε να δοκιμάσουμε τους τελεστές [**`cxUniform`**](http://deap.readthedocs.io/en/master/api/tools.html#deap.tools.cxUniform)(με τιμές για την indpb 0.05, 0.4) και [**`cxBlend`**](http://deap.readthedocs.io/en/master/api/tools.html#deap.tools.cxBlend)(με τιμές για την alpha 0.1, 0.5). \n","\n","* Στη συνέχεια ορίζουμε τον τελεστή μετάλλαξης \"mutate\".  Επιλέγουμε να δοκιμάσουμε τους τελεστές [**`mutGaussian`**](http://deap.readthedocs.io/en/master/api/tools.html#deap.tools.mutGaussian)(με τιμές για την indpb 0.01, 0.3) και [**`mutShuffleIndexes`**](http://deap.readthedocs.io/en/master/api/tools.html#deap.tools.mutShuffleIndexes)(με τιμές για την indpb 0.01, 0.3). \n","\n","* Τέλος επιλέγουμε εγγράφουμε τον τελεστή επιλογής \"select\" που χρησιμοποιεί την [**`selTournament`**](http://deap.readthedocs.io/en/master/api/tools.html#deap.tools.selTournament) . Η υπερπαράμετρος που θα δοκιμάζουμε εδώ είναι το μέγεθος διοργάνωσης. Δοκιμάζουμε τις τιμές 4 και 12, κάτι που σημαίνει ότι θα διαλέξουμε 4 και 12 αντίστοιχα τυχαία άτομα του πληθυσμού, τα συγκρίνουμε και κρατάμε το καλύτερο (ένας ακόμη τρόπος να υλοποιήσουμε το survival of the fittest).\n","\n","Έχουμε δηλαδή συνολικά 32 συνδυασμούς τελεστών για να αξιολογήσουμε.\n","\n","Για κάθε συνδυασμό τελεστών θα εξετάσουμε τρεις στρατηγικές: τον [**απλό ΓΑ**](http://deap.readthedocs.io/en/master/api/algo.html#deap.algorithms.eaSimple) και τις στρατηγικές εξέλιξης [**“μ+λ”**](http://deap.readthedocs.io/en/master/api/algo.html#deap.algorithms.eaMuPlusLambda) και [**“μ,λ”**](http://deap.readthedocs.io/en/master/api/algo.html#deap.algorithms.eaMuCommaLambda).\n","\n","Αρχικά θα προσδιορίσουμε τους καταλληλότερους συνδυασμούς τελεστών-στρατηγικών. Για το λόγο αυτό θα θέσουμε ένα σχετικά μικρό αριθμό γύρων (π.χ. 5-10) και μέγιστων γενεών (π.χ. 50-100-150) και σταθερές τιμές στις παραμέτρους πληθυσμού και τις πιθανότητες διασταύρωσης και μετάλλαξης.\n","\n","---\n","\n","Πρώτα θα ορίσουμε όλες τις απαραίτητες συναρτήσεις. \n","\n","Αρχικά ορίζουμε τη συνάρτηση καταλληλότητας, την ίδια τη συνάρτηση Keane δηλαδή.\n","\n","Ο βασικός τρόπος για να επιβάλουμε περιορισμούς όσον αφορά το πεδίο ορισμού της συνάρτησης είναι να επιβάλουμε μια ποινή στην τιμή της καταλληλότητας στα άτομα που είναι εκτός των ορίων που έχουμε θέσει. Ορίζουμε δύο συναρτήσεις, τη \"feasible\" που μας επιστρέφει True αν όλα τα $x_i$ είναι εντός του διαστήματος και False αλλιώς και την \"distance\" που μας ποσοτικοποιεί πόσο εκτός ορίων είναι ένα άτομο. Συγκεκριμένα επιλέγουμε η απόσταση να είναι το απόλυτο άθροισμα σε όλες τις διαστάσεις της απόστασης από το όριο. Θα μπορούσαμε να κάνουμε και άλλες επιλογές όπως πχ να χρησιμοποιήσουμε μια τετραγωνική συνάρτηση της απόστασης.\n","\n"]},{"metadata":{"id":"dLVW6_YKSdYM","colab_type":"code","colab":{}},"cell_type":"code","source":["def evalKeaneFunc(ind):\n","    x1 = ind[0];\n","    x2 = ind[1];\n","    val = -pow(sin(x1-x2),2) * pow(sin(x1+x2),2) / sqrt(x1*x1+x2*x2)\n","    return (val,)\n","\n","MIN_BOUND = np.array([0]*2) #όσες και οι διαστάσεις της συνάρτησης\n","MAX_BOUND = np.array([10]*2)\n","\n","def feasible( indiv ):\n","    if any( indiv < MIN_BOUND) or any( indiv > MAX_BOUND):\n","        return False\n","    return True\n","\n","def distance( indiv ) :\n","    dist = 0.0\n","    for i in range (len( indiv )) :\n","        penalty = 0\n","        if ( indiv [i] < MIN_BOUND[i]) : penalty = 0 - indiv [i]\n","        if ( indiv [i] > MAX_BOUND[i]) : penalty = indiv [i] - 10\n","        dist = dist + penalty\n","    return dist"],"execution_count":0,"outputs":[]},{"metadata":{"id":"4i5rPF2tSdYQ","colab_type":"text"},"cell_type":"markdown","source":["Θα ορίσουμε τώρα μία συνάρτηση που θα ελέγχει την αποτελεσματικότητα ενός συνδυασμού."]},{"metadata":{"id":"IsT1ohCdSdYQ","colab_type":"code","colab":{}},"cell_type":"code","source":["def one_combo_test(c_var,m_var,s_var,c_flag,m_flag,flag,MAX_GENS,POPULATION,delta_penalty,target,CXPB,MUTPB):\n","    VERBOSE = False #print log\n","\n","    toolbox = base.Toolbox()\n","    toolbox.register(\"attr_real\", random.uniform, 0, 10) #range των x1 & x2 variables\n","    toolbox.register(\"individual\", tools.initRepeat, creator.Individual, toolbox.attr_real, 2)  #όσες και οι διαστάσεις της συνάρτησης\n","    toolbox.register(\"population\", tools.initRepeat, list, toolbox.individual) \n","\n","    toolbox.register( \"evaluate\", evalKeaneFunc)\n","    toolbox.decorate( \"evaluate\", tools.DeltaPenality (feasible, delta_penalty, distance))\n","\n","    pop = toolbox.population(n=POPULATION)\n","    hof = tools.HallOfFame(1)\n","    stats = tools.Statistics(lambda ind: ind.fitness.values)\n","    stats.register(\"avg\", np.mean)\n","    stats.register(\"min\", np.min)\n","    stats.register(\"max\", np.max)\n","\n","    if (c_flag==0):\n","        toolbox.register(\"mate\", tools.cxUniform, indpb = c_var)\n","    else:\n","        toolbox.register(\"mate\", tools.cxBlend, alpha = c_var)\n","\n","    if(m_flag==0):\n","        toolbox.register(\"mutate\", tools.mutGaussian, mu = 0, sigma=1.0, indpb=m_var)\n","    else:\n","        toolbox.register(\"mutate\", tools.mutShuffleIndexes, indpb=m_var)\n","\n","\n","    toolbox.register(\"select\", tools.selTournament, tournsize=s_var)\n","\n","    t_start = time.time()\n","    if(flag==0): \n","        pop_new, logbook = algorithms.eaSimple(pop, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=MAX_GENS, stats=stats, halloffame=hof, verbose=VERBOSE)\n","    elif(flag==1): \n","        pop_new, logbook =  algorithms.eaMuPlusLambda(pop, toolbox, mu=POPULATION/5, lambda_=4*POPULATION/5, cxpb=CXPB, mutpb=MUTPB, ngen=MAX_GENS, stats=stats, halloffame=hof, verbose=VERBOSE)\n","    elif(flag==2):\n","        pop_new, logbook = algorithms.eaMuCommaLambda(pop, toolbox, mu=POPULATION/5, lambda_=4*POPULATION/5, cxpb=CXPB, mutpb=MUTPB, ngen=MAX_GENS, stats=stats, halloffame=hof, verbose=VERBOSE)\n","    t_finish = time.time()\n","\n","    success = 0\n","    if ( evalKeaneFunc(hof[0])[0] <=target ):\n","        success = 1 #οταν ο ΓΑ βρίσκει τιμή μικρότερη του GOAL+DELTA\n","\n","    curr_tot_evals =  0\n","    curr_min_first_gen = 0\n","    curr_min_first_val = 0\n","    for j in range(MAX_GENS-1, -1, -1):\n","        curr_tot_evals += logbook[j]['nevals']\n","        # θα κρατήσουμε την μικρότερη γενιά για την οποία ισχύει ότι ο ΓΑ πέτυχε τιμή μικρότερη από GOAL+DELTA, για γύρο που στέφθηκε με επιτυχία\n","        if( logbook[j]['min'] <= target ):\n","            curr_min_first_gen = j+1\n","            curr_min_first_val = logbook[j]['min']\n","    curr_min_evals = 0\n","    for j in range(0,curr_min_first_gen,1):\n","        curr_min_evals += logbook[j]['nevals']\n","\n","    return evalKeaneFunc(hof[0])[0], curr_tot_evals, t_finish-t_start,success,curr_min_first_gen, curr_min_first_val, curr_min_evals"],"execution_count":0,"outputs":[]},{"metadata":{"id":"Adey9D-tSdYU","colab_type":"text"},"cell_type":"markdown","source":["Θα ορίσουμε τώρα μία συνάρτηση που θα ελέγξει την αποτελεσματικότητα των 32 συνδυασμών που αναφέρθηκαν προηγουμένως.\n","\n","Οι συγκεκριμένοι 32 συνδυασμοί είναι οι εξής : \n","\n","|A/A|crossover hyperparameter|mutation hyperparameter|selection hyperparameter|\n","|---|------------------------|-----------------------|------------------------|\n","|1  |cxUniformLow            |muGauLow               |selTourLow              |\n","|2  |cxUniformLow            |muGauLow               |selTourHigh             |\n","|3  |cxUniformLow            |muGauHigh              |selTourLow              |\n","|4  |cxUniformLow            |muGauHigh              |selTourHigh             |\n","|5  |cxUniformHigh           |muGauLow               |selTourLow              |\n","|6  |cxUniformHigh           |muGauLow               |selTourHigh             |\n","|7  |cxUniformHigh           |muGauHigh              |selTourLow              |\n","|8  |cxUniformHigh           |muGauHigh              |selTourHigh             |\n","|9  |cxBlendLow              |muGauLow               |selTourLow              |\n","|10 |cxBlendLow              |muGauLow               |selTourHigh             |\n","|11 |cxBlendLow              |muGauHigh              |selTourLow              |\n","|12 |cxBlendLow              |muGauHigh              |selTourHigh             |\n","|13 |cxBlendHigh             |muGauLow               |selTourLow              |\n","|14 |cxBlendHigh             |muGauLow               |selTourHigh             |\n","|15 |cxBlendHigh             |muGauHigh              |selTourLow              |\n","|16 |cxBlendHigh             |muGauHigh              |selTourHigh             |\n","|17 |cxUniformLow            |muShuIndLow            |selTourLow              |\n","|18 |cxUniformLow            |muShuIndLow            |selTourHigh             |\n","|19 |cxUniformLow            |muShuIndHigh           |selTourLow              |\n","|20 |cxUniformLow            |muShuIndHigh           |selTourHigh             |\n","|21 |cxUniformHigh           |muShuIndLow            |selTourLow              |\n","|22 |cxUniformHigh           |muShuIndLow            |selTourHigh             |\n","|23 |cxUniformHigh           |muShuIndHigh           |selTourLow              |\n","|24 |cxUniformHigh           |muShuIndHigh           |selTourHigh             |\n","|25 |cxBlendLow              |muShuIndLow            |selTourLow              |\n","|26 |cxBlendLow              |muShuIndLow            |selTourHigh             |\n","|27 |cxBlendLow              |muShuIndHigh           |selTourLow              |\n","|28 |cxBlendLow              |muShuIndHigh           |selTourHigh             |\n","|29 |cxBlendHigh             |muShuIndLow            |selTourLow              |\n","|30 |cxBlendHigh             |muShuIndLow            |selTourHigh             |\n","|31 |cxBlendHigh             |muShuIndHigh           |selTourLow              |\n","|32 |cxBlendHigh             |muShuIndHigh           |selTourHigh             |\n","Αργότερα θα αναφερθούμε σε αυτούς με τους Α/Α τους."]},{"metadata":{"id":"ESeDdSYISdYV","colab_type":"code","colab":{}},"cell_type":"code","source":["def combination_testing(un_list,bl_list,ga_list,sh_list,se_list,target,flag,MAX_GENS,POPULATION,CXPB,MUTPB,rnd,mute):\n","    delta_penalty = 5.0\n","    # crossover hyperparameters (low,high)\n","    cxUniform_indpb_list = un_list\n","    cxBlend_alpha_list = bl_list\n","    # mutation hyperparameters (low,high)\n","    mutGaussian_indpb_list = ga_list\n","    mutShuffleIndexes_indpb_list = sh_list\n","    #selection hyperparameters (low,high)\n","    selTournament_tour_list = se_list\n","\n","    ## Μετρικές απόδοσης\n","    min_val = []        # ελάχιστη τιμή που πέτυχε ο ΓΑ στο συγκεκριμένο γύρο\n","    tot_evals = []     # συνολικές αποτιμήσεις(άθροιση όλων των γενεών) του συγκεκριμένου γύρου\n","    time_of_round = [] # χρόνος εκτέλεσης τou γύρou. \n","\n","    #Επιπρόσθετα, επειδή δεν είναι εφικτό για κάθε συνάρτηση να αναμένουμε ότι σε λογικά χρονικά διαστήματα (ή και γενικά)\n","    #θα βρούμε την ακριβή βέλτιστη λύση, ορίζουμε ως επιτυχία την ποσότητα *GOAL + DELTA*, όπου GOAL το ελάχιστο της συνάρτησης\n","    #(δίνεται στο pdf) και DELTA μια θετική ποσότητα που θα ορίζουμε εμείς κάθε φορά (διαφορετική για κάθε συνάρτηση και \n","    #διαφορετική ανάλογα του πόσο κοντά στη λύση θέλουμε να φτάσουμε). Με βάση την ποσότητα GOAL + DELTA ορίζουμε επιπλέον τα εξής μεγέθη:\n","    success = []       # 1 αν ο ΓΑ βρήκε τιμή μικρότερη του GOAL+DELTA.\n","    min_first_gen = [] # γενιά στην οποία ο ΓΑ πέτυχε να πέσει κάτω από GOAL+DELTA\n","    min_first_val = [] # τιμή που πέτυχε ο ΓΑ στην πρώτη γενιά που κατάφερε να πέσει κάτω απο GOAL+DELTA\n","    min_evals = []     # συνολικές αποτιμήσεις που χρειάστηκαν για να πάρουμε την πρώτη τιμή κάτω από GOAL + DELTA\n","\n","    round_start = time.time()\n","    ##############################################################################################################################################################################################\n","    ## CROSSOVER : UNIFORM, MUTATION : GAUSSIAN\n","    for curr1 in cxUniform_indpb_list:\n","        for curr2 in mutGaussian_indpb_list:\n","            for curr3 in selTournament_tour_list:\n","                f1,f2,f3,f4,f5,f6,f7 = one_combo_test(curr1,curr2,curr3,0,0,flag,MAX_GENS,POPULATION,delta_penalty,target,CXPB,MUTPB)\n","                min_val.append(f1)  ;  tot_evals.append(f2)   ;  time_of_round.append(f3)  ;  success.append(f4)  ;  min_first_gen.append(f5)  ;  min_first_val.append(f6)  ;  min_evals.append(f7)                \n","    ###############################################################################################################################################################################################\n","    ## CROSSOVER : BLEND, MUTATION : GAUSSIAN\n","    for curr1 in cxBlend_alpha_list:\n","        for curr2 in mutGaussian_indpb_list:\n","            for curr3 in selTournament_tour_list:\n","                f1,f2,f3,f4,f5,f6,f7 = one_combo_test(curr1,curr2,curr3,1,0,flag,MAX_GENS,POPULATION,delta_penalty,target,CXPB,MUTPB)\n","                min_val.append(f1)  ;  tot_evals.append(f2)   ;  time_of_round.append(f3)  ;  success.append(f4)  ;  min_first_gen.append(f5)  ;  min_first_val.append(f6)  ;  min_evals.append(f7)                \n","    ###############################################################################################################################################################################################\n","    ## CROSSOVER : UNIFORM, MUTATION : SHUFFLE_INDEXES\n","    for curr1 in cxUniform_indpb_list:\n","        for curr2 in mutShuffleIndexes_indpb_list:\n","            for curr3 in selTournament_tour_list:\n","                f1,f2,f3,f4,f5,f6,f7 = one_combo_test(curr1,curr2,curr3,0,1,flag,MAX_GENS,POPULATION,delta_penalty,target,CXPB,MUTPB)\n","                min_val.append(f1)  ;  tot_evals.append(f2)   ;  time_of_round.append(f3)  ;  success.append(f4)  ;  min_first_gen.append(f5)  ;  min_first_val.append(f6)  ;  min_evals.append(f7)                \n","    ###############################################################################################################################################################################################       \n","    ## CROSSOVER : BLEND, MUTATION : SHUFFLE_INDEXES\n","    for curr1 in cxBlend_alpha_list:\n","        for curr2 in mutShuffleIndexes_indpb_list:\n","            for curr3 in selTournament_tour_list:\n","                f1,f2,f3,f4,f5,f6,f7 = one_combo_test(curr1,curr2,curr3,1,1,flag,MAX_GENS,POPULATION,delta_penalty,target,CXPB,MUTPB)\n","                min_val.append(f1)  ;  tot_evals.append(f2)   ;  time_of_round.append(f3)  ;  success.append(f4)  ;  min_first_gen.append(f5)  ;  min_first_val.append(f6)  ;  min_evals.append(f7)                  \n","    ###############################################################################################################################################################################################\n","    round_finish = time.time()\n","\n","    if (mute==False):\n","        print('Round {:<3} finished. Elapsed time: {:<6}'.format(rnd+1,str(round(round_finish-round_start,6))))\n","    return min_val,tot_evals,time_of_round,success,min_first_gen,min_first_val,min_evals"],"execution_count":0,"outputs":[]},{"metadata":{"id":"u0QZEPj0SdYY","colab_type":"text"},"cell_type":"markdown","source":["Στη συνέχεια ορίζουμε μία συνάρτηση που ελέγχει για κάθε στρατηγική την απόδοση των πιο πάνω συνδυασμών, τρέχοντας την πιο πάνω συνάρτηση `MAX_ROUNDS` φορές. Θα κρατήσουμε μέσους όρους των μετρικών που επιστρέφονται από τη συνάρτηση `combination_testing`"]},{"metadata":{"id":"SyxAYgV5SdYZ","colab_type":"code","colab":{}},"cell_type":"code","source":["def strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,CXPB,MUTPB,un_list,bl_list,ga_list,sh_list,se_list,mute):\n","    tot_combos = len(un_list)*len(ga_list)*len(se_list) + len(un_list)*len(sh_list)*len(se_list) + len(bl_list)*len(ga_list)*len(se_list) + len(bl_list)*len(sh_list)*len(se_list)\n","    ev_strategies = ['SimpleEA','Mu+Lambda','Mu,Lambda']\n","    target = goal+delta # ψάχνουμε τη βέλτιστη με έναν βαθμό ανοχής λύση\n","\n","    #cummulative arrays\n","    sum_min_val = [0]*tot_combos\n","    sum_tot_evals = [0]*tot_combos\n","    sum_time_of_round = [0]*tot_combos\n","    sum_success = [0]*tot_combos # αριθμός φορών που o ΓΑ βρήκε τιμή μικρότερη του GOAL + DELTA. Προφανώς το βέλτιστο είναι MAX_ROUNDS.\n","    sum_min_first_gen = [0]*tot_combos\n","    sum_min_first_val = [0]*tot_combos\n","    sum_min_evals = [0]*tot_combos\n","\n","    for k in range(0,MAX_ROUNDS,1):\n","        min_val,tot_evals,time_of_round,success,min_first_gen,min_first_val,min_evals =  combination_testing(un_list,bl_list,ga_list,sh_list,se_list,target,flag,MAX_GENS,POPULATION,CXPB,MUTPB,k,mute)\n","\n","        sum_min_val = [x+y for x,y in zip(min_val,sum_min_val)]\n","        sum_tot_evals = [x+y for x,y in zip(tot_evals,sum_tot_evals)]\n","        sum_time_of_round = [x+y for x,y in zip(time_of_round,sum_time_of_round)]\n","        \n","        sum_success = [x+y for x,y in zip(success,sum_success)]\n","        sum_min_first_gen = [x+y for x,y in zip(min_first_gen,sum_min_first_gen)]\n","        sum_min_first_val = [x+y for x,y in zip(min_first_val,sum_min_first_val)]\n","        sum_min_evals = [x+y for x,y in zip(min_evals,sum_min_evals)]\n","\n","\n","    avg_min_val =       [i/MAX_ROUNDS for i in sum_min_val]       # ο μέσος όρος της ελάχιστης τιμής που πέτυχε για όλους τους γύρους.\n","    avg_tot_evals =     [i/MAX_ROUNDS for i in sum_tot_evals]     # o μέσος όρος των συνολικών αποτιμήσεων (άθροιση όλων των γενεών) που έκανε για όλους τους γύρους.\n","    avg_time_of_round = [i/MAX_ROUNDS for i in sum_time_of_round] # ο μέσος χρόνος εκτέλεσης των γύρων.\n","\n","    avg_min_first_gen = [0]*tot_combos # o μέσος όρος των γενεών που χρειάστηκε ο αλγόριθμος για να πέσει κάτω από GOAL + DELTA, για τους γύρους με επιτυχία. \n","                               # Ουσιαστικά μας ενδιαφέρει η πρώτη γενιά που πετυχαίνει τιμή κάτω από GOAL + DELTA. Σε περίπτωση που δεν πετυχαίνει \n","                               # αυτό το στόχο καμία γενιά, θέτουμε ‘None’ σε αυτή την ποσότητα.\n","    avg_min_first_val = [0]*tot_combos # ο μέσος όρος των ελαχίστων των πρώτων επιτυχημένων γενεών για τους γύρους με επιτυχία. Θέτουμε ‘None’ σε περίπτωση αποτυχίας.\n","    avg_min_evals = [0]*tot_combos     # ο μέσος όρος αποτιμήσεων που χρειάστηκαν για να πάρουμε την πρώτη τιμή κάτω από GOAL + DELTA. Θέτουμε ‘None’ σε περίπτωση αποτυχίας.\n","\n","    for i in range(0,tot_combos,1): #αν sum_success[i]==0, τότε ποτέ δεν είχαμε επιτυχία για το συγκεκριμένο συνδυασμό\n","        if (sum_min_first_gen[i]==0):\n","            avg_min_first_gen[i] = None\n","            avg_min_first_val[i] = None\n","            avg_min_evals[i] = None\n","\n","        else:\n","            avg_min_first_gen[i] = sum_min_first_gen[i]/sum_success[i]\n","            avg_min_first_val[i] = sum_min_first_val[i]/sum_success[i]\n","            avg_min_evals[i]     = sum_min_evals[i]/sum_success[i]\n","    print('-'*103)\n","    print '\\n\\nPresenting Statistics for Evolution Strategy={:<9} |  MAX_ROUNDS={:<3} | MAX_GENS={:<3} | POPULATION={:<4} | delta={:<6} | CXPB={:<3} | MUTPB={:<6}'.format(ev_strategies[flag],MAX_ROUNDS,MAX_GENS,POPULATION,delta,CXPB,MUTPB)\n","    print '\\n\\n{:<3}| {:<9} | {:<15} | {:<11} | {:<10} | {:<9} | {:<16} | {:<8}'.format('Comb.', 'Successes', 's.avg.min','s.avg.evals','s.avg.gens','avg.evals','avg.min','avg.time')\n","    print '-'*103\n","    for i in range(0,tot_combos,1):\n","        print '{:<4} | {:<9} | {:<15} | {:<11} | {:<10} | {:<9} | {:<16} | {:<8}'.format(i+1, sum_success[i], avg_min_first_val[i],avg_min_evals[i],avg_min_first_gen[i],avg_tot_evals[i],avg_min_val[i],round(avg_time_of_round[i],5))\n","    print '-'*103,'\\n\\n'\n"],"execution_count":0,"outputs":[]},{"metadata":{"id":"AiTFrecYSdYd","colab_type":"text"},"cell_type":"markdown","source":["Ώρα να δοκιμάσουμε διάφορες τιμές στις παραμέτρους `MAX_ROUNDS`, `MAX_GENS`, `POPULATION`, `delta`, και για διαφορετικές τιμές του `flag`(διαφορετικές στρατηγικές εξέλιξης)\n","\n","1) Αρχικά δοκιμάσαμε για 10 γύρους, 30 γενιές, και πληθυσμό 30. Η τιμή του delta είχε οριστεί στο 0.01. Όπως είναι φυσικό, πήραμε αρκετά successes, αλλά με κακή προσέγγιση του ελαχίστου. Πολλοί συνδυασμοί εμφάνισαν επιτυχία, αλλά οι περισσότεροι σε πολύ χαμηλό ποσοστό όσον αφορά το πλήθος των γύρων που τρέξαμε (~10-20%)\n","    \n","2) Αυξήσαμε τις γενιές στις 45. Παρατηρήσαμε κάποιοιυς συνδυασμούς να μην εμφανίζουν επιτυχία, αναμενόμενο. Αυξάνοντας κι άλλο τις γενιές στις 60 συνεχίζεται το ίδιο μοτίβο. Πάντα παρατηρούμε και μια μικρή αύξηση στο χρόνο. Εμφανίζονται σιγά σιγά συνδυασμοί που εμφανίζουν επιτυχία για όλους τους γύρους που τους δοκιμάσαμε.\n","    \n","3) Πλέον με τις 60 γενιές, ώρα να κάνουμε το delta 10 φορές μικρότερο. Ο χρόνος όπως είναι αναμενόμενο παραμένει ίδιος. Αλλά τα αποτελέσματα όσον αφορά την επιτυχία πέφτουν, καθώς θεωρούμε επιτυχή μία πρόβλεψη πιο σπάνια (σε μικρότερο εύρος αριθμών γύρω από το ελάχιστο) . Δεν έχουμε συνδυασμό με 100% επιτυχία, αλλά τα αποτελέσματα που παίρνουμε είναι όλο και πιο κοντά στο ελάχιστο.\n","\n","4) Δοκιμάζουμε να αυξήσουμε τις γενιές στις 75. Αύξηση στο χρόνο, αλλά και καλύτερα αποτελέσματα. Με delta ίσο με 0.0005 και 100 γενιές εμφανίζεται max 70% επιτυχία στους εξεταζόμενους συνδυασμούς. Επιλέγουμε όμως τελικά τα παρακάτω combinations, καθώς θα βελτιωθούν παραπάνω για μεγαλύτερο πληθυσμό, γενιές και γύρους εκτέλεσης (και άλλες υπερπαραμέτρους που θα εξετάσουμε αργότερα).\n","\n","\n","Όσον αφορά τις διαφορετικές στρατηγικές εξέλιξης, η καλύτερη είναι ο απλός εξελικτικός αλγόριθμος `SimpleEA`. Οι υπόλοιποι δεν καταφέρνουν να εμφανίσουν μεγάλη επιτυχία."]},{"metadata":{"id":"kXZ0HCQVSdYf","colab_type":"code","colab":{}},"cell_type":"code","source":["flag = 0 # simpleEA ###flag = 1 ### M+L #flag = 2 # M,L\n","MAX_ROUNDS = 10\n","MAX_GENS = 75\n","POPULATION = 40\n","goal = -0.673667521146855 # http://benchmarkfcns.xyz/benchmarkfcns/kealefcn.html\n","delta = 0.0005\n","CXPB = 0.7\n","MUTPB = 0.3\n","mute = False\n","\n","un_list=[0.05, 0.35]\n","bl_list=[0.15 , 0.5]\n","ga_list=[0.01, 0.3]\n","sh_list=[0.01, 0.3]\n","se_list=[3,10]\n","\n","strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,CXPB,MUTPB,un_list,bl_list,ga_list,sh_list,se_list,mute)"],"execution_count":0,"outputs":[]},{"metadata":{"scrolled":false,"id":"HVj68PRwSdYi","colab_type":"code","colab":{}},"cell_type":"code","source":["flag=1 #M+L\n","strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,CXPB,MUTPB,un_list,bl_list,ga_list,sh_list,se_list,mute)\n","flag=2 #M,L\n","strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,CXPB,MUTPB,un_list,bl_list,ga_list,sh_list,se_list,mute)"],"execution_count":0,"outputs":[]},{"metadata":{"id":"mwsxEDrrSdYm","colab_type":"text"},"cell_type":"markdown","source":["### Τελική βελτιστοποίηση\n","\n","#### Βελτιστοποίηση πιθανοτήτων διασταύρωσης και μετάλλαξης\n","\n","Παρατηρούμε από τα παραπάνω ότι ο καλύτερος συνδυασμός είναι ο **16**. Στο συγκεκριμένο χρησιμοποιούμε τον τελεστή `Blend` για διασταύρωση(alpha=0.5), τον `Gaussian` για μετάλλαξη(indpb=0.3) και την τιμή 10 για τον Tournament Selector. Καλά αποτελέσματα εμφανίζει επίσης ο συνδυασμός **15**, o οποίος απλά έχει μικρότερο tournament size, τον οποίο δεν προτιμούμε όμως λόγω του μικρού tournament size.\n","\n","Για το συνδυασμό αυτό τελεστών-στρατηγικής και σταθερό αριθμό γύρων, πληθυσμού και γενεών, κάνουμε grid search στους τελεστές διασταύρωσης και μετάλλαξης στο διάστημα [0.1 0.9] (να αθροίζουν στη μονάδα) για να βρούμε το βέλτιστο συνδυασμό τους."]},{"metadata":{"scrolled":true,"id":"HcQ854RHSdYn","colab_type":"code","colab":{}},"cell_type":"code","source":["flag = 0 # simpleEA ###flag = 1 ### M+L #flag = 2 # M,L\n","MAX_ROUNDS = 25\n","MAX_GENS = 75\n","POPULATION = 50\n","goal = -0.673667521146855 # http://benchmarkfcns.xyz/benchmarkfcns/kealefcn.html\n","delta = 0.0001\n","mute = True\n","\n","# κρατάμε μόνο τον συνδυασμό που μας ενδιαφέρει\n","un_list=[]\n","bl_list=[0.5]\n","ga_list=[0.3]\n","sh_list=[]\n","se_list=[10]\n","\n","CXPB_arr = np.arange(0.1,0.95,0.05)\n","for curr_cxpb in CXPB_arr:\n","    curr_mutpb = 1-curr_cxpb\n","    strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,curr_cxpb,curr_mutpb,un_list,bl_list,ga_list,sh_list,se_list,mute)"],"execution_count":0,"outputs":[]},{"metadata":{"id":"XxCqWitbSdYr","colab_type":"text"},"cell_type":"markdown","source":["Οι μεταβλητές `CXPB` και `MUTPB` συμβολίζουν τα εξής :\n","- CXPB  : ποσοστό κληρονομικότητας από γονείς\n","- MUTPB : ποσοστό τυχαίας μετάλλαξης\n","\n","Παρατηρούμε πως το καλύτερο αποτέλεσμα το παίρνουμε για τις τιμές του `CXPB` στο διάστημα 0.45 έως 0.55, με τις αντίστοιχες τιμές για το `MUTPB`, ώστε πάντα `CXPB+MUTPB=1`\n","\n","Έχοντας λοιπόν καταλήξει και σε κατάλληλα `CXPB=0.45` και `MUTPB=0.55`, μπορούμε να τρέξουμε τον αλγόριθμό μας με βέλτιστες παραμέτρους και να ελέγξουμε το αποτέλεσμα."]},{"metadata":{"id":"HZudVpVpSdYr","colab_type":"text"},"cell_type":"markdown","source":["#### Εύρεση βέλτιστης τιμής\n","\n","Κάνουμε ένα run του βέλτιστου αλγόριθμου που προέκυψε στα προηγούμενα βήματα με ένα μεγάλο αριθμό γενεών και πληθυσμού για να πάρετε μια βέλτιστη τιμή για τη συνάρτηση (σε λογικά χρονικά πλαίσια). Τυπώνουμε τη βέλτιστη τιμή, το συνολικό αριθμό αποτιμήσεων και το χρόνο εκτέλεσης."]},{"metadata":{"scrolled":false,"id":"2p0D-z6LSdYt","colab_type":"code","colab":{}},"cell_type":"code","source":["flag = 0 # simpleEA ###flag = 1 ### M+L #flag = 2 # M,L\n","MAX_ROUNDS = 30\n","MAX_GENS = 200\n","POPULATION = 150\n","goal = -0.673667521146855 # http://benchmarkfcns.xyz/benchmarkfcns/kealefcn.html\n","delta = 0.000001\n","CXPB = 0.45\n","MUTPB = 0.55\n","mute = False\n","\n","# κρατάμε μόνο τον συνδυασμό που μας ενδιαφέρει\n","un_list=[]\n","bl_list=[0.5]\n","ga_list=[0.3]\n","sh_list=[]\n","se_list=[10]\n","\n","strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,CXPB,MUTPB,un_list,bl_list,ga_list,sh_list,se_list,mute)"],"execution_count":0,"outputs":[]},{"metadata":{"scrolled":false,"id":"f1PosV4MSdYx","colab_type":"code","colab":{}},"cell_type":"code","source":["flag = 0 # simpleEA ###flag = 1 ### M+L #flag = 2 # M,L\n","MAX_ROUNDS = 30\n","MAX_GENS = 200\n","POPULATION = 150\n","goal = -0.673667521146855 # http://benchmarkfcns.xyz/benchmarkfcns/kealefcn.html\n","delta = 0.0000001\n","CXPB = 0.45\n","MUTPB = 0.55\n","mute = False\n","\n","# κρατάμε μόνο τον συνδυασμό που μας ενδιαφέρει\n","un_list=[]\n","bl_list=[0.5]\n","ga_list=[0.3]\n","sh_list=[]\n","se_list=[10]\n","\n","strategy_round_testing(flag,goal,delta,MAX_ROUNDS,MAX_GENS,POPULATION,CXPB,MUTPB,un_list,bl_list,ga_list,sh_list,se_list,mute)"],"execution_count":0,"outputs":[]},{"metadata":{"id":"8AhGsxvLSdY8","colab_type":"text"},"cell_type":"markdown","source":["Πετύχαμε προσέγγιση μέχρι και το 6ο δεκαδικό ψηφίο, με επιτυχία σε κάθε γύρο για την εύρεση του ελαχίστου.\n","\n","Όταν επιχειρήσαμε να κάνουμε προσέγγιση μέχρι και το 7ο δεκαδικό ψηφίο, το πλήθος των επιτυχιών έπεσε στις 26/30. Και πάλι το αποτέλεσμα κρίνεται αρκετά ικανοποιητικό.\n","\n","Πετύχαμε επομένως την εύρεση ελαχίστου για τη μη-κλιμακούμενη συνάρτηση **`Keane`**, μέσα σε λογικά χρονικά πλαίσια, και με ικανοποιητική προσέγγιση ως προς τα δεκαδικά ψηφία.\n","\n","---\n","\n","---\n","\n","---\n","\n","\n","## 2. Μελέτη κλιμακούμενης συνάρτησης\n","Η κλιμακούμενη συνάρτηση που θα μελετήσουμε είναι η **Stepint** :\n","\\begin{equation}\n","f(\\mathbf{x}) = 25 + \\sum_{i=1}^{D}{\\lfloor x_i \\rfloor}, -5.12 \\leq x_1 , \\ldots , x_D \\leq 5.12\n","\\end{equation}\n","---\n","\n","### Για D=2\n","- α) Εκτυπώστε ένα “3D” γράφημα της συνάρτησης $f(x1,x2)$ και περιγράψτε σύντομα τη μορφή της.\n","\n","- β) Με την διαδικασία που ακολουθήσαμε προηγουμένως για τη μη κλιμακούμενη συνάρτηση, βρίσκουμε τον βέλτιστο γενετικό αλγόριθμο για το πρόβλημα. Προσαρμόζουμε τον κώδικα του πρώτου μέρους της άσκησης. Μπορεί να αντιγράφουμε ήδη έτοιμο κώδικα, αλλά το κάνουμε για να είναι ανεξάρτητες οι δύο ασκήσεις.\n","\n","### Για D=1,10,20,50 και μεγαλύτερες διαστάσεις\n","\n","Για τον βέλτιστο αλγόριθμο (που βρήκατε για 2 διαστάσεις) και για διαφορετικές τιμές/τάξεις μεγέθους D=1,10,20,50,... των διαστάσεων του πεδίου ορισμού (σταθερά MAX_GENS, MAX_ROUNDS>=10) τυπώστε πίνακα με: **αριθμό διαστάσεων**, **αριθμό επιτυχιών**, **μέσο ολικό ελάχιστο**, **μέσο αριθμό αποτιμήσεων** και **μέσο χρόνο** (προφανώς βασιστείτε στην αρχική βοηθητική συνάρτηση εκτύπωσης αποτελεσμάτων). Σημειώστε ότι οποιαδήποτε ποινή για άτομα εκτός ορισμού καθώς και τo DELTA προκειμένου να είναι αποτελεσματικά θα πρέπει εμπειρικά να οριστούν συναρτήσει του πλήθους των διαστάσεων.\n","\n","- Σχολιάστε τα αποτελέσματα του πίνακα. Ποιες είναι οι αιτίες του φαινομένου; Πώς μπορούμε να βελτιώσουμε τα αποτελέσματα σε μεγάλες διαστάσεις για σταθερό αριθμό γενεών, τουλάχιστον ως προς το σκέλος της μέσης βέλτιστης τιμής (κυρίως) καθώς και των επιτυχιών;\n","- Κάντε μια δοκιμή (σε λογικά πλαίσια χρόνου) των αλλαγών που προτείνετε, τυπώστε εκ νέου τον πίνακα και σχολιάστε.\n","\n","## Βιβλιογραφία\n","\n","- Jamil, Momin, and Xin-She Yang. \"A literature survey of benchmark functions for global optimisation problems.\" International Journal of Mathematical Modelling and Numerical Optimisation 4.2 (2013): 150-194. [link](https://goo.gl/qAhxNf)\n","\n","- Whitley, Darrell, et al. \"Evaluating evolutionary algorithms.\" Artificial intelligence 85.1-2 (1996): 245-276. [link](https://www.sciencedirect.com/science/article/pii/0004370295001247/pdf?md5=41088a944920336e5d8493160de27800&pid=1-s2.0-0004370295001247-main.pdf&_valck=1)\n","\n","- \"Gradient Free Optimization\". Stanford AA222 - Introduction to Multidisciplinary Design Optimization handouts. [link](http://adl.stanford.edu/aa222/Lecture_Notes_files/chapter6_gradfree.pdf) \n","\n","- [DEAP Benchmarks functions](http://deap.readthedocs.io/en/master/api/benchmarks.html)\n","\n","- [Global Optimization Test Functions Index](http://infinity77.net/global_optimization/test_functions.html)\n","\n","\n","## Σημείωσεις για την υλοποίηση\n","\n","- Λόγω των πολλών επαναλήψεων είναι απαραίτητη και θα αξιολογηθεί η **εκτεταμένη χρήση συναρτήσεων**.\n","- Για απορίες και διευκρυνίσεις ως συνήθως συμβουλευτείτε πρώτα το [FAQ](https://goo.gl/igxHTY) και στη συνέχεια αν χρειαστεί μπορείτε να στείλετε mail στο [nnlab@islab.ntua.gr](mailto:nnlab@islab.ntua.gr)"]}]}