0/1 Knapsack
· Binary encoding.
· Fitness function: Summing the weights and values if the gene is turned on for the cu
ent 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
epresent 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
epresent 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 numbe
Initialize Population 0;
while(terminal condition isn’t met) {
Evaluate fitness of each individual in Population g;
Create Population g+1{
XXXXXXXXXXBased on fitness, select individuals for reproduction;
XXXXXXXXXXPerform crossover and mutation on the selected individuals.
}
g++;
}
Return the best solution in the cu
ent 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 XXXXXXXXXX)
2. Value encoding (19.3, 45.1, -12.9, XXXXXXXXXX)
3. Permutation encoding (1,4,2,7,5,9,3,6,8)
Cross Ove
Crossover selects genes from parent chromosomes and creates a new offspring.
Two-point crossove
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
One point crossove
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
Cross Over conti.
Order Crossove
XXXXXXXXXXparents XXXXXXXXXXchildren
P1:[ XXXXXXXXXX] C2:[ XXXXXXXXXX]
P2:[ XXXXXXXXXX] XXXXXXXXXXC1:[ XXXXXXXXXX]
Remove 9, 5, 4 from P2
Rotate.
Insert “954” to the resulting list.
P2:[ XXXXXXXXXX] [ XXXXXXXXXX] [ XXXXXXXXXX ]
[ XXXXXXXXXX]
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.
XXXXXXXXXX XXXXXXXXXX
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 ma
le 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 XXXXXXXXXX.
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.
Individual X f(x) Normed f(x) Cumulative normed f(x)
XXXXXXXXXX 189 .733 .144 .144
XXXXXXXXXX 216 .471 .093 .237
XXXXXXXXXX 99 .937 .184 .421
XXXXXXXXXX 236 .243 .048 .469
XXXXXXXXXX 174 .845 .166 .635
XXXXXXXXXX 74 .788 .155 .790
XXXXXXXXXX 35 .416 .082 .872
XXXXXXXXXX 53 .650 .128 1.00
How to do crossove
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 crossove
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
One point crossove
XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
How to do mutation
With a mutation probability, randomly flip every bit.
XXXXXXXXXX XXXXXXXXXX
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.