# CS607 Artificial Intelligence Assignment 2 Solution Fall 2013

Objective

• Genetic Algorithms and its application.
• Reading and understanding research papers.

Genetic Algorithm

Dear Student, you have studied about Genetic Algorithm (GA) and its application on several sample problems. Here in this assignment you are given another problem and you have to devise your solution using GA. This will help in testing your understanding and improving your knowledge about GA. Following is the simple flowchart of GA.

 Crossover/
 / Time-over

Figure 1: Flow chart of steps in Genetic Algorithm.

Important things to consider in application of GA

1. Defining chromosome structure / Problem solution encoding: The first thing we need to do in GA application is to define chromosome structure. Each chromosome represents an intermediate solution.
2. Population Size: It is the number of chromosomes that we need to initialize and carry forward in every generation.
3. Fitness function: This is a way to evaluate the goodness of current chromosomes/solutions.
4. Crossover: This is required to define how existing chromosomes/solutions will generate new chromosomes/solutions (hopefully improved).
5. Mutation: How to make small random change in new generated chromosomes/solutions.
6. Stopping condition/No. of generations/iterations: This may be a threshold fitness value used to terminate the loop iteration. Often, it’s very difficult to define a threshold fitness value and that’s why loop is terminated after a fixed number of iterations/generations.

Travelling Salesman Problem

It’s a very interesting problem in which a Salesman has to visit a list of given cities. He knows the distances between each pair of cities and wants to plan the shortest possible route so that he can visit each city exactly once and returns to the origin city.

For this assignment, I have restricted this problem to 20 cities, labeled as A, B…T and Grid view of its map is given below. You can easily find intercity distance using the grid co-ordinates e.g. distance between city A and B is 40 Km and distance between city A and G is 72.11 Km (using simple distance formula) and so on. We are considering straight line routes are available between each pair of cities. This Map was intentionally made little complex so that you shall not think on solving it manually. In real-world, problems are often very complex and therefore we choose to develop computer’s based solutions.

Figure 2: Grid view of the map of 20 cities labeled as A, B…T.

Salesman can start his visit from any city and wants to plan the shortest possible route so that he can visit each other city exactly once and returns to the city from where he took the start. Let’s say, Salesman chooses a random route which may look as shown in figure below. The route of the Salesman is like A-D-G-L…C-A i.e. Salesman starts his journey from city A, have a visit of all cities exactly once and finally return back to city A.

Figure 3: Initial sample random route.

Let’s say we have implemented a Genetic Algorithm based solution for this Travelling Salesman Problem. After applying GA, we may have a better route; of course, that may be not the best solution.

Your task is to devise a solution using GA that shall find the optimal (not best) route and answer the following questions. Be brief and to the point while answering the given questions.

Questions

Solution Idea is given below:

Q. No. 1: Describe your Chromosome structure / solution encoding scheme. How it will represent initial and intermediate solutions? Give your representation for the partitions given in Figure-3 and Figure-4.

Answer: For chromosome structure, I choose to define an array of size equal to the number of nodes. For 30 nodes, our array size =30. Initially, array is filled randomly with 0’s and 1’s where 0 indicate that the current index node belongs to first partition and 1 indicate that it belongs to second partition. Our array contents will look as below for the given random distribution of nodes in Figure-3.

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1

As you can see in above, Node ID…2,4,5,8,10,12,13,15,18,19,21,23,26,27,30 has 0 value which indicate that these nodes belong to first partition and all other nodes belong to second partition.

Similarly, array configuration after apply GA when the cut-size was reduced as shown in Figure-4 is given below.

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0

As you can see in above, Node ID…3,7,8,9,10,12,14,17,22,23,24,26,28,30,31 has 0 value which indicate that these nodes belong to first partition and all other nodes belong to second partition.

Q. No. 2: Describe your Fitness function for the given problem. What will be the fitness value of the sample random route given in Figure-3? (4 Marks)

Solution:

Cut-size will determine fitness value of our intermediate solutions which is calculated as below:

Loop For all nodes in Array (current chromosome)
If node value = 0
Place this node in Set A
If node value = 1
Place this node in Set B
Repeat Loop

Initialize Cut-size=0

Outer Loop For all nodes in Set A
Inner Loop For all nodes in Set B
Check in Graph, if there exist an edge between current node of set A and set B
Increment Cut-size
Repeat Inner Loop
Repeat Outer Loop

Return Cut-size

Q. No. 3: Describe your strategy for Crossover operation for the given problem with example. How intermediate solutions will generate new solutions? (4 Marks)

Solution:

First, we will choose two best solutions which results in least cut-size using their fitness value. Later we generate a random number for every crossover between 1-30 to select crossover point…let’s say if my random number is 8 this implies that I will choose first 8 array items from first solution and remaining 22 array items from second solution to generate a new solution e.g.

My first best solution is

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1

My second best solution is

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0

Let’s say Crossover point is 8 (randomly generated each time) so our new solution will look as below…

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0

Above technique is expected to better explore the search space for alternate best solutions.

Q. No. 4: Describe your strategy for Mutation operation for the given problem with example. How newly generated solutions will be mutated? (4 Marks)

Answer: I randomly choose 3 array items and reverse their values…from 0 to 1 and from 1 to 0…reversing this value results in changing its partition e.g. let’s say I have the following solution…

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0

Suppose my three randomly selected indices are 5, 16, and 22. After applying mutation it will look as below…

 Index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Node ID 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Value 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0

=> Before mutation, 1 value of node 5 indicates that it belong to second partition and after mutation its value was changed to 0 which makes node 5 a member of first partition. Similarly, node 16 and 22 were belonging to first partition before mutation and they ended up in second partition after mutation.

Q. No. 5: Describe your Stopping condition. How you choose to stop/terminate execution of your GA? (4 Marks)

Answer: As you know that in GA, we repeatedly generate new solutions from existing solution by performing crossover and mutation operations. We expect some improvement toward the desired solution after every iteration. I choose to stop my GA algorithm, if all my current solutions give no improvement (reduction in cut-size) in 3 successive iterations then it is assumed that we have arrived at optimal solution and we stop GA and current best solution is returned.

Q. No. 6 (Bonus Question): In this 20-cities example, how many different routes are possible in total, staring from a particular city (say city A)? (4 Marks)