{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"Lab 8.3 Επίλυση του 0-1 Knapsack με Γενετικούς Αλγόριθμους.ipynb","provenance":[]},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"zjaIUaJtLZAN"},"source":["# 0-1 Knapsack, ένα δύσκολο πρόβλημα\n","\n","Το πρόβλημα knapsack ή πρόβλημα του σακιδίου είναι ένα κλασσικό πρόβλημα συνδυαστικής βελτιστοποίησης. Με δεδομένο ένα σύνολο αντικειμένων, το καθένα από τα οποία έχει ένα ορισμένο βάρος και αξία, θέλουμε να προσδιορίσουμε το πλήθος κάθε αντικειμένου που πρέπει να συμπεριλάβουμε σε ένα σακίδιο το οποίο έχει ένα μέγιστο όριο βάρους έτσι ώστε η συνολική αξία του σακιδίου να μεγιστοποιηθεί.\n","\n","<img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/486px-Knapsack.svg.png\" width=\"30%\">\n","\n","Υπάρχουν διάφορες παραλλαγές του Knapsack. Το 0-1 (ή διακριτό) Knapsack θεωρεί ότι έχουμε ακριβώς ένα διαθέσιμο αντίτυπο από κάθε αντικείμενο και είτε θα το συμπεριλάβουμε στο σακίδιο είτε όχι, εξού και το 0-1 (υπάρχει και η παραλλαγή χωρίς όρια στο πλήθος του κάθε αντικειμένου και η παραλλαγή με ένα όριο $c$ το πλήθος για κάθε αντικείμενο). Επιπρόσθετα, θεωρούμε ότι κάθε αντικείμενο είναι αδιαίρετο. \n","\n","Με δεδομένο ένα σύνολο $n$ αντικειμένων αριθμημένα από 1 έως n, το καθένα με βάρος $w_i$ και αξία $v_i$, και μια μέγιστη χωρητικότητα W, θέλουμε να μεγιστοποιήσουμε την ποσότητα\n","\n","$\\sum\\limits_{i=1}^{n}v_{i}x_{i}$\n","\n","υπό τον περιορισμό to $\\sum\\limits_{i=1}^{n}w_{i}x_{i}\\leq W$ και $x_{i}\\in \\{0,1\\}$\n","\n","## Δυσκολία\n","\n","Η εύρεση του βέλτιστου συνδυασμού αντικειμένων είναι πρόβλημα NP-complete. Υπό ορισμένες συνθήκες (τα βάρη να είναι μη αρνητικοί ακέραιοι) το πρόβλημα μπορεί να επιλυθεί με δυναμικό προγραμματισμό σε ψεύδο-πολυωνυμικό χρόνο (δηλαδή πολυνωμιακό ως προς το μέγιστο αριθμό που αποτελεί μέρος της εισόδου, εκθετικό όμως σε σχέση με το μήκος της εισόδου).\n","\n","## Επίλυση με Δυναμικό Προγραμματισμό\n","\n","<img src=\"https://preview.ibb.co/bWewu6/knapsack_Page13s.jpg\" width=\"40%\">\n","\n","Σε κάθε βήμα i, θεωρούμε διαθέσιμα τα i πρώτα αντικείμενα. Για όλα τα δυνατά βάρη w απο 0 έως W η τιμή της $V[i,w]$ είναι είτε ίση με $V[i-1,w]$ (αν η προσθήκη οποιουδήποτε αντικειμένου ξεπερνά το βάρος W αυτή είναι η μόνη δυνατότητα), είτε ίση με το μέγιστο που μπορούν να δώσουν τα i αντικείμενα για το βάρος w μείον το βάρος του αντικειμένου i συν την αξία του αντικειμένου i:\n","\n","$V[0,w] = 0$, για $0 \\leq w \\leq W $\n","\n","$V[i,w] = max(V[i-1,w], v_i+V[i-1,w-w_i])$\n","\n","Η πολυπλοκότητα είναι $O(nW)$.\n","\n","Μπορείτε [εδώ](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/RM1BDv71V60) να βρείτε μια ωραία διαδραστική παρουσίαση με κώδικα της επίλυσης του 0-1 Knapsack με δυναμικό προγραμματισμό."]},{"cell_type":"code","metadata":{"id":"hogazUHmLZAQ"},"source":["def DP_knapSack(W, items):\n","    wt = []\n","    val = []\n","    for key, value in items.items():\n","        wt.append(value[0])\n","        val.append(value[1])\n","    n = len(val)\n","    \n","    K = [[0 for x in range(W+1)] for x in range(n+1)]\n"," \n","    # Build table K[][] in bottom up manner\n","    for i in range(n+1):\n","        for w in range(W+1):\n","            if i==0 or w==0:\n","                K[i][w] = 0\n","            elif wt[i-1] <= w:\n","                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])\n","            else:\n","                K[i][w] = K[i-1][w]\n"," \n","    return K[n][W]"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"jaeEWV9NLZAV"},"source":["import random\n","\n","# αρχικοποιήσεις\n","MAX_WEIGHT = 20000 # το μέγιστο βάρος (χωρητικότητα) του σακιδίου\n","NBR_ITEMS = 500 # το πλήθος των διαθέσιμων αντικειμένων\n","MAX_ITEM_WEIGHT= MAX_WEIGHT # το μέγιστο βάρος για κάθε αντικειμένου (το θέτουμε ίσο με το μέγιστο βάρος του σακιδίου). Ακέραιος.\n","MAX_ITEM_VALUE= 10 # η μέγιστη αξία κάθε αντικειμένου\n","\n","SEED = 20000\n","# To assure reproductibility, the RNG seed is set prior to the items\n","# dict initialization. It is also seeded in main().\n","random.seed(SEED)\n","\n","# Create the item dictionary: item name is an integer, and value is \n","# a (weight, value) 2-uple.\n","items = {}\n","# Create random items and store them in the items' dictionary.\n","for i in range(NBR_ITEMS):\n","    items[i] = (random.randint(1, MAX_ITEM_WEIGHT), random.uniform(0, MAX_ITEM_VALUE))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"pfZrC6ojLZAa"},"source":["| MAX_WEIGHT | NBR_ITEMS | COMPLEXITY | RESULT      | WALL TIME (sec) |\n","|------------|-----------|------------|-------------|-----------------|\n","| 20,000      | 500       | 10,000,000   | 163.289787279 | 3.76            |\n","| 20,000      | 1,000      | 20,000,000   | 277.29256589  | 7.72            |\n","| 100,000     | 2,000      | 200,000,000 | 404.624148539  | 77 |\n","| 100,000     | 10,000      | 1,000,000,000 | 804.926256691  | 397 |\n","| 100,000     | 50,000      | 5,000,000,000 |  Memory Error  | Memory Error  |"]},{"cell_type":"code","metadata":{"scrolled":true,"id":"wuhAcQcXLZAb"},"source":["%time print(DP_knapSack(MAX_WEIGHT, items ))"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"TnCcv29aLZAg"},"source":["## Λύση με γενετικό αλγόριθμο πολυκριτηριακής βελτιστοποιήσης (επιλογή με NSGA-II)\n","\n","Η επιλογή βασίζεται στο [μέτωπο Pareto](https://en.wikipedia.org/wiki/Pareto_efficiency). Τα σημεία που βρίσκονται στο μέτωπο Pareto κυριαρχούν (dominate) επί αυτών που δεν βρίσκονται επί του μετώπου δηλαδή αποτελούν καλύτερες λύσεις. Για δύο κριτήρια προς ελαχιστοποίηση το μέτωπο Pareto έχει ως εξής:\n","<img src=\"https://ascelibrary.org/cms/attachment/5545/34309/figure1.jpg\" width=\"25%\">\n","\n","Ο αλγόριθμος επιλογής NSGA-II καταρχάς ξεχωρίζει ως καλύτερα άτομα για αναπαραγωγή τα άτομα που ανήκουν στο Pareto front. Στη συνέχεια ταξινομεί και αυτά με βάση την απόσταση που έχουν μεταξύ τους (τείνει να προτιμά λύσεις που βρίσκονται σε πιο αραιές περιοχές του front)."]},{"cell_type":"code","metadata":{"scrolled":false,"id":"vXhMo4yyLZAh"},"source":["!pip install deap\n","\n","import numpy\n","\n","from deap import algorithms\n","from deap import base\n","from deap import creator\n","from deap import tools\n","\n","IND_INIT_SIZE = int(NBR_ITEMS/100) # το αρχικό πλήθος των αντικειμένων ενός ατόμου (θα αλλάξει κατά την αναπαραγωγή)\n","\n","# ορίζουμε το πρόβλημα ως βελτιστοποίηση δύο κριτηρίων: ελαχιστοποίηση βάρους και μεγιστοποίηση αξίας\n","creator.create(\"Fitness\", base.Fitness, weights=(-1.0, 1.0))\n","# το άτομο κληρονομεί την set και όχι την list\n","creator.create(\"Individual\", set, fitness=creator.Fitness)\n","\n","toolbox = base.Toolbox()\n","\n","# Attribute generator\n","toolbox.register(\"attr_item\", random.randrange, NBR_ITEMS) #ακέραιος αριθμός με μέγιστο τον αριθμό των αντικειμένων\n","\n","# Structure initializers\n","toolbox.register(\"individual\", tools.initRepeat, creator.Individual, toolbox.attr_item, IND_INIT_SIZE)\n","# σημειώστε ότι τα attr_items θα είναι μοναδικά: έαν στο set {1,2} προστεθεί το 2 το set παραμένει {1,2}. Έτσι επιβάλλουμε το 0-1\n","toolbox.register(\"population\", tools.initRepeat, list, toolbox.individual)\n","\n","# η καταλληλότητα υπολογίζεται από τα items (άθροισμα βαρών και αξίας)\n","def evalKnapsack(individual):\n","    weight = 0.0\n","    value = 0.0\n","    for item in individual:\n","        weight += items[item][0]\n","        value += items[item][1]\n","    if weight > MAX_WEIGHT:\n","        return MAX_WEIGHT, 0             # Ensure overweighted bags are dominated\n","    return weight, value\n","\n","def cxSet(ind1, ind2):\n","    \"\"\"Εφαρμόζουμε ένα τελεστή διασταύρωσης πάνω στα σύνολα εισόδου (γονείς). \n","    Το πρώτο παιδί είναι η τομή των δύο συνόλων (η λίστα θεωρείται ως ένα σύνολο), το δεύτερο η διαφορά τους.\n","    \"\"\"\n","    temp = set(ind1)                # Used in order to keep type\n","    ind1 &= ind2                    # Intersection (inplace)\n","    ind2 ^= temp                    # Symmetric Difference (inplace)\n","    return ind1, ind2\n","    \n","def mutSet(individual):\n","    \"\"\"Η μετάλλαξη αφαιρεί ή προσθέτει τυχαία ένα αντικείμενο\"\"\"\n","    if random.random() < 0.5:\n","        if len(individual) > 0:     # We cannot pop from an empty set\n","            individual.remove(random.choice(sorted(tuple(individual))))\n","    else:\n","        tmp  = random.randrange(NBR_ITEMS)\n","        #ψάχνουμε ένα αντικείμενο που να μην υπάρχει στο άτομο\n","        while (tmp in individual):\n","            tmp  = random.randrange(NBR_ITEMS)\n","        individual.add(tmp)\n","    return individual,\n","\n","toolbox.register(\"evaluate\", evalKnapsack)\n","toolbox.register(\"mate\", cxSet)\n","toolbox.register(\"mutate\", mutSet)\n","# η επιλογή γίνεται με τον NSGA-II\n","toolbox.register(\"select\", tools.selNSGA2)\n","\n","def main():\n","    #random.seed(SEED)\n","    NGEN = 200\n","    MU = 50\n","    LAMBDA = 1600\n","    CXPB = 0.2\n","    MUTPB = 0.8\n","    \n","    pop = toolbox.population(n=MU)\n","    hof = tools.ParetoFront()\n","    stats = tools.Statistics(lambda ind: ind.fitness.values)\n","    stats.register(\"avg\", numpy.mean, axis=0)\n","    stats.register(\"std\", numpy.std, axis=0)\n","    stats.register(\"min\", numpy.min, axis=0)\n","    stats.register(\"max\", numpy.max, axis=0)\n","    \n","    # εφαρμόζουμε γενετικο αλγόριθμο στρατηγικής μ+λ. H επιλογή γίνεται στο σύνολο μ γονέων και λ παιδιών \n","    algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,\n","                              halloffame=hof)\n","    \n","    return pop, stats, hof\n","                 \n","if __name__ == \"__main__\":\n","    %time pop, stats, hof = main()"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"TNN15G9nLZAk"},"source":["| ALGORITHM | MAX_WEIGHT | NBR_ITEMS | COMPLEXITY | RESULT      | WALL TIME (sec) | VALUE (RESULT/TIME)|\n","|------------|------------|-----------|------------|-------------|-----------------|-----------------|\n","|DP| 20,000     | 500      |  10,000,000| 163.289787279 | 3.76             | **43.428**|\n","|GA (NGEN = 100, MU = 100, LAMBDA = 1900, CXPB = 0.6, MUTPB = 0.4)| 20,000     | 500      | 10,000,000 | 158.63303462 |     67        | 2.368  |\n","|DP|  20,000      | 1,000      | 20,000,000   | 277.29256589  | 7.72            | **35.919** |\n","|GA (NGEN = 100, MU = 100, LAMBDA = 1900, CXPB = 0.6, MUTPB = 0.4)| 20,000     | 1,000      | 20,000,000 | 228.68608541 |     78        | 2.932  |\n","|DP | 100,000     | 2,000      | 200,000,000 | 404.624148539  | 77 | **5.254** |\n","|GA (NGEN = 150, MU = 25, LAMBDA = 2000, CXPB = 0.8, MUTPB = 0.2)| 100,000     | 2,000      | 200,000,000 | 334.93656337 |     90        | 4.630  |\n","|DP| 100,000     | 10,000      | 1,000,000,000 | 804.926256691  | 397 | 2.0275 |\n","|GA (NGEN = 200, MU = 25, LAMBDA = 1800, CXPB = 0.8, MUTPB = 0.2)| 100,000     | 10,000      |1,000,000,000|  420.3180269 |     114        | **3.687**  |\n","|DP| 100,000     | 50,000      | 5,000,000,000 | Memory Error |\n","|GA (NGEN = 250, MU = 25, LAMBDA = 1600, CXPB = 0.8, MUTPB = 0.2)| 100,000     | 50,000      | 5,000,000,000 | 497.1761053 |     136        | **3.658**  |"]},{"cell_type":"markdown","metadata":{"id":"0WQDYwUWLZAl"},"source":["## Άσκηση\n","Για MAX_WEIGHΤ = 100,000 και NBR_ITEMS = 10,000 (τρέξτε το μπλοκ με τις αρχικοποιήσεις των αντικειμένων με αυτές τις τιμές) δοκιμάστε διαφορετικές παραμέτρους στον γενετικό με NSGA-II για να βελτιώσετε τη μέγιστη αξία του knapsack (σε λογικό χρόνο - κρατήστε τον αριθμό των γενεών στο 200)."]}]}