implement 0/1 knapsack genetic algorithm
0/1 Knapsack · Binary encoding. · Fitness function: Summing the weights and values if the gene is turned on for the current item. If the weight totals more than the knapsack capacity then the value is set at zero, otherwise it is the value of the sum of the values of the items in the knapsack. · Selection: Roulette wheel + Elitism. · Crossover: two-point or single-point crossover. · Mutation: Randomly flip every bit. The program can be in C or java. It should be a single program implemented either in C or java. Sample output: The output of our code should be like this: Input file: test1.txt Number of items: 50 Knapsack capacity: 500 Knapsack items: 1 11 13 15 19 26 27 29 30 31 34 36 37 Population size: 1000 Crossover rate: 0.95 Mutation rate: 0.05 Stop after generations: 100 The best solution is 7818/482 Knapsack items: 1 11 13 15 26 27 29 30 31 34 36 37 48 Another GA run? y Population size: 1000 Crossover rate: 0.95 Mutation rate: 0.05 Stop after generations: 1000 The best solution is 8204/488 Knapsack items: 1 11 13 15 19 26 27 29 30 31 34 36 37 Another GA run? test1.txt – this is the input file that contains the number of items. 500 50 975 192 915 67 200 191 679 160 594 234 259 60 363 191 398 83 373 144 160 156 545 249 694 27 193 121 552 15 802 215 623 30 384 194 538 135 178 146 518 55 456 193 533 195 107 205 394 233 555 120 475 139 659 25 582 42 225 213 709 34 252 7 803 83 869 159 218 85 556 12 816 184 512 3 829 88 280 155 97 56 776 209 933 143 740 109 286 129 648 242 991 249 326 225 533 199 132 49 240 188 Test2.txt- this is another input file that contains the number of paired items. 500 50 806 116 420 184 844 5 783 32 253 45 293 103 293 108 770 18 148 8 15 86 868 104 611 14 202 30 952 161 455 96 55 77 297 53 284 95 630 29 362 14 580 177 422 131 743 175 910 39 617 178 406 185 994 97 633 4 817 40 674 117 965 55 532 146 201 53 403 163 881 167 713 153 418 92 332 27 327 32 50 49 166 189 428 91 470 32 355 12 644 58 559 6 755 122 870 18 905 192 787 55 Programming project (Part of your final) Implement the 0/1 Knapsack genetic algorithm discussed in this lecture, with the following parameters: • Population size : input. • Mutation rate: 0.05 • Crossover rate: 0.95 • Terminal condition: an input number of generations. Programming pr oject (Part of your final) Implement the 0/1 Knapsack genetic algorithm discussed in this lecture, with the following parameters: •Population size : input. •Mutation rate: 0.05 •Crossover rate: 0.95 •Terminal condition: an input number of generations. Programming project conti. Notes: • Your program should be able to handle Knapsack problems with 64 items, i.e. each individual should be represent by a 64-bit integer. • Use comments to indicate where in your program you do – Create initial population. – Select individuals for reproduction. – Crossover. – Mutation. • You need to turn in hardcopies of your source code and sample outputs. • You need to email a softcopy of your source code to the instructor. Programming pr oject conti. Notes: •Your program should be able to handle Knapsack problems with 64 items, i.e. each individual should be represent by a 64-bit integer. •Use comments to indicate where in your program you do –Create initial population. –Select individuals for reproduction. –Crossover. –Mutation. •You need to turn in hardcopies of your source code and sample outputs. •You need to email a softcopy of your source code to the instructor. Introduction to Genetic Algorithms Introduction to Genetic Algorithms Genetic Algorithms - History Pioneered by John Holland in the 1970’s Got popular in the late 1980’s Based on Darwin’s evolution theory “survival of the fittest”. In nature, competition among individuals for meagre resources results in the fittest individuals dominating over the weaker ones. Can be used to solve a variety of problems that are not easy to solve using other techniques. The Basic Concept of GA GAs are the ways of solving problems by mimicking the process nature uses, i.e. selection, crossover, and mutation. GAs are adaptive heuristic search based on evolutionary ideas on natural selection and genetics. In GAs, solving problems becomes looking for solutions which is best among others. A General Genetic Algorithm g = 0; // generation number Initialize Population 0; while(terminal condition isn’t met) { Evaluate fitness of each individual in Population g; Create Population g+1{ Based on fitness, select individuals for reproduction; Perform crossover and mutation on the selected individuals. } g++; } Return the best solution in the current generation. Implementation Details How to represent an individual, i.e. solution. Determine the size of the population (a collection of individuals). How to initialize the population. How to evaluate fitness. How to select individuals for reproduction. How to perform crossover. How to perform mutation. Determine the crossover rate and mutation rate. Decide when to terminate. Encoding of a Chromosome (Representation of a solution) 1. Binary encoding (1011 ... 0100) 2. Value encoding(19.3, 45.1, -12.9, ... 6.2) 3. Permutation encoding(1,4,2,7,5,9,3,6,8) Cross Over Crossover selects genes from parent chromosomes and creates a new offspring. Two-point crossover 10101011 10011011 11011001 11101001 One point crossover 10101011 10011001 11011001 11101011 Cross Over conti. Order Crossover parents children P1:[2 1 3 9 5 4 8 7 6] C2:[6 8 7 9 5 4 1 3 2] P2:[5 3 2 6 8 9 7 1 4] C1:[5 4 7 6 8 9 2 1 3] Remove 9, 5, 4 from P2 Rotate. Insert “954” to the resulting list. P2:[5 3 2 6 8 9 7 1 4] [3 2 6 8 7 1] [1 3 2 6 8 7 ] [1 3 2 6 8 7 9 5 4] Mutation Mutation is to prevent solutions in the population from falling into a local optimum of the solved problem. Mutation changes the new offspring randomly. For the binary encoding, with a mutation probability, we randomly flip bits. 00110101 00011101 For permutation encoding Randomly interchange a pair of numbers. Randomly reverse a segment of the permutation. Selection Roulette Wheel Selection Parents are selected according to their fitness. The better the chromosomes are, the more chances to be selected they have. Imagine a roulette wheel where are placed all chromosomes in the population accordingly to their fitness functions, like on the following picture. Then a marble is thrown there and selects the chromosome. Chromosomes with bigger fitnesses will be selected more times. Selection conti. Rank Selection When the fitnesses differ very much, e.g. if the best chromosome fitness is 90% of all the roulette wheel then the other chromosomes will have very few chances to be selected. Rank selection first ranks the population and then every chromosome receives fitness from this ranking. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population). Selection conti. Elitism When creating a new population by crossover and mutation, we have a big chance, that we will loose the best chromosome. Elitism is name of method, which first copies the best chromosome (or a few best chromosomes) to new population. The rest is done in classical way. Elitism can very rapidly increase performance of GA, because it prevents losing the best found solution. An Illustrative Example To find the value of x, 0 ≤ x ≤ 255, that maximize f(x) = sin(x* π/256). Represent solutions to the problem Binary encoding. Since a solution is a number between 0 and 255, we can represent each individual using 8 bits. For example, 189 is represented as 10111101. Determine the size of a population In general, it could be thousands. In this simple example we use 8. How to evaluate fitness Since our goal is to maximize f(x), we use f(x) as the fitness of individual x. Numbers with bigger f values are more fit. Select individual for reproduction Roulette Wheel Selection. Since it’s a probabilistic selection, best is not always pick and the worst is not necessarily excluded. In our example, we use cumulative normed f(x) to determine individuals’ probabilities. IndividualXf(x)Normed f(x)Cumulative normed f(x) 10111101189.733.144.144 11011000216.471.093.237 0110001199.937.184.421 11101100236.243.048.469 10101110174.845.166.635 0100101074.788.155.790 0010001135.416.082.872 0011010153.650.1281.00 How to do crossover With a crossover possibility, crossover the parents to form new offspring. If no crossover was performed, offspring is the exact copy of parents. Two-point crossover 10101011 10011011 11011001 11101001 One point crossover 10101011 10011001 11011001 11101011 How to do mutation With a mutation probability, randomly flip every bit. 00110101 00011101 Another Example: TSP Given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting every city once and only once and returning to the starting city. Represent solutions to the problem A solution is a tour, i.e. a sequence of cities. So, we represent a solution as a permutation of cities. [c1, c2, c3, .... cn] How to evaluate fitness The fitness is the cost of the tour. Tours with smaller costs are more fit. Select individual for reproduction Roulette Wheel Selection.