Assignment1


Part1
First question is very easy. I even found at the first try. So, I did not more complex method.
There are more than one solution for it. Even though solution for the second question also solves it.
I put here a seperate and easy solution.
The solution is :
All elements are initialized to 0. By starting from the first element, I changed the elements to 1. Then
calculate the fitness and check if it is 100. When the fitness is 100, go out the loop. Values of elements is as follows
1111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000
question1.cpp

Part2
Second question is harder. It needs more complex solution. I tried to change the elements sequantially.
I got 80 maximum. After many trial I come with the idea to change the elements randomly one by one.
The solution is :
All elements are initialized to 0 or 1 randomly at the beginning. Then pick an element randomly, change its value,
caculate the fitness, if the new fitness is higher than the previous one then keep the new value, if not change the element
value back. This is an hill climbing method. The algorithm finds the 100 after an average of 5 million trial. Sometimes happens
1 million sometimes 15 million. The values of vector elements for the solution as follows.
1001001001001001001011111111111111111111111111111100000000000000000000000000000000000000000000000000
question2.cpp




Assignment2


I used evolutionary algorithm with crossover and mutation.
Part1
First I generate 8 generations. To make the starting point more elicit
I apply random search with 1000 iteration to each string. I get 64 from some of them.
I sorted the new strings. I keep the highest 4 and crossover them, and then mutate one bit in each string.
For crossover, I picked a random place. For each time that place differ since it is random.
I generated 1000 new generations. In each generation I keep the highest four. I got 64 maximum.
Values of elements is as follows
011001001001101110011100010011100110101100011101100101101001101010011000010110000110100010110001000110001111100010101111001000101010101111100100010111
question1.cpp

Part2
For the second question, since the object file returns too late, I had to change the iteration times.
I used the same algorithm except the part I made random search for first initialization. I excluded this part.
Also I generated 100 generations. I got maximum 64. If generate more, probably I got higher fitness but it takes so long.
But after 100 generations, all strings converged to 64.
The values of vector elements for the solution as follows.
101100101101100011011001110010010110011000011101111001100011111101010111110000110001110001111011010000010010010110000001001110110000111010111001000101
question2.cpp

Assignment2


The graphs for all functions with crossover and mutation combinations are below. I used
ranking based Genetic Algorithm. I choose population size as 100. I am giving different seeds for each run.
I used different files for each question. Initial values are setup at the begining of the code.
It can be tried different values by changing.

function1


crossover = 0.2 probability = 0.0001
crossover = 0.67 probability = 0.001
crossover = 0.99 probability = 0.01

question1.cpp

function2


crossover = 0.2 probability = 0.0001
crossover = 0.67 probability = 0.001
crossover = 0.99 probability = 0.01

question2.cpp

function3


crossover = 0.2 probability = 0.0001
crossover = 0.67 probability = 0.001
crossover = 0.99 probability = 0.01

question3.cpp

function4


crossover = 0.2 probability = 0.0001
crossover = 0.67 probability = 0.001
crossover = 0.99 probability = 0.01

question4.cpp

Assignment2


In this assigment, we try to solve TSP(traveling salesman person) problem using GA. We should find minimum path length.
Each city should be visited only once. I used permutation encoding which is popular method for TSP. I selected
population size as 100. I use elitist approach to select better individuals. For crossover operation, I used single
point crossover[1]. One crossover point is selected, till this point the permutation is copied from the first parent,
then the second parent is scanned and if the number is not yet in the offspring it is added.There are more ways how
to produce the rest after crossover point

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

For mutation I select two point and exchange the cities. The algorithm approches the solution even only with mutation,
but not much. The most important part of algorithm is crossover algorithm. The quality of the crossover operation determines
the quality of overall algorithm. If the chromosome is long, it needs more generation to find the solution.
Also, when the chromosome is long it takes more computation time.
I make 30 runs with different seeds for each problem. I tested on 3 different dataset

eil51
There are 51 cities. Optimum path length is 426. 20%(6) of 30 runs passed 90%(473). 18(60%) of 30 runs passed 85%(501).
The worst case is 530 which corresponds to 80%. The best case is 442 which corresponds to 96%. I made 5000 generation.
Population size is 100. Chromosome length is 51, So speed is proportional to 500000*51.
opt 426
6 %90 mark 473
18 %85 mark 501
worst 530
best 442
speed 500000*51



The graph above show the evolotion of algorithm for this data. It has data for max., ave. and min.

Two graphs below the path. First one is if you go with order. Second one is our solution.





eil76
There are 76 cities. Optimum path length is 426. 20%(6) of 30 runs passed 75%(473). 18(60%) of 30 runs passed 70%(501).
The worst case is 811 which corresponds to 66%. The best case is 442 which corresponds to 83%. I made 10000 generation.
Population size is 100. Chromosome length is 76, So speed is proportional to 500000*76.
opt 538
13 %75 mark 717
21 %70 mark 768
worst 811
best 647
speed 500000*76



The graph above show the evolotion of algorithm for this data. It has data for max., ave. and min.

Two graphs below the path. First one is if you go with order. Second one is our solution.





lin105
There are 105 cities. Optimum path length is 14379. 3%(6) of 30 runs passed 10%(473). 9(30%) of 30 runs passed 15%(501).
The worst case is 33852 which corresponds to 42. The best case is 21972 which corresponds to 65%. I made 10000 generation.
Population size is 100. Chromosome length is 105, So speed is proportional to 500000*105.
opt 14379
1 %60 mark 23965
9 %50 mark 28758
worst 33852
best 21972
speed 500000*105



The graph above show the evolotion of algorithm for this data. It has data for max., ave. and min.

Two graphs below the path. First one is if you go with order. Second one is our solution.





The algorithm works very well with dataset1. It works ok with second dataset. But, it shows a bad performance with dataset3.
The reason is chromosome length is high. It needs more generation to approach to optimum.
1. http://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.php

question.cpp
report