CS607 Assignment no 03 Spring 2013

Assignment No. 03
Semester: Spring 2013

CS607: Artificial Intelligence

Due Date: 21/05/2013

Instructions

Please read the following instructions carefully before submitting assignment:

It should be clear that your assignment will not get any credit if:

• The assignment is submitted after due date.
• The submitted assignment does not open or file is corrupt.
• Solution is copied from any other source.

Objective

The objective of this assignment is to enhance your knowledge about;

• Genetic Algorithms and its application.

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.

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.

Graph Partitioning Problem

It’s a very interesting problem in which a graph G is divided into partitions such that minimum number of edges are running across the partitions. Following is the simplified version of the same problem for better understanding.

Let’s consider we have a Graph of 30 nodes as given below.

Figure 2: Sample randomly generated Graph of 30 nodes.

 


We want to divide this graph into 2 disjoint partitions with minimum cut-size. Cut-size is defined as the total number of edges connecting nodes in different partitions. Let say, I do simple partitioning by randomly placing 15 nodes in one partition and remaining 15 nodes in other partition. The resultant partitioning is shown in figure below.

Figure 3: Random Partitioning…Cut-size=34.

Cut size of above simple partitioning = 34 (as total 34 edges are running across the partitions)

I have implemented a Genetic Algorithm based solution for such graphs. After applying GA, I have the following picture. (this is of course not the best/optimal solution)

Figure 4: After applying GA…Cut-size=16.

Your task is to devise a solution using GA that shall minimize/reduce the cut-size and answer the following questions.

Questions

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.

Q. No. 2: Describe your Fitness function for the given problem. How it will calculate fitness value of intermediate solutions.

Q. No. 3: Describe your strategy for Crossover operation. How intermediate solutions will generate new solutions?

Q. No. 4: Describe your strategy for Mutation operation. How newly generated solutions will be mutated?

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

Submission

You are required to submit your solution in MS Word format through LMS.