We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# Assignment No. 03 Semester: Spring 2013 CS607: Artificial Intelligence:Due Date: 21/05/2013

Assignment No. 03
Semester: Spring 2013

CS607: Artificial Intelligence

Total Marks: 20

Due Date: 21/05/2013

Instructions

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

• 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.

 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.

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.

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 6805

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

### Replies to This Discussion

Spring 2013_CS607_3

Attachments:

Hy koi jo mari help kary PLZ PLZ PLZ

g brother kia hua..

lecture 13 is useful for this assignment

its tricky but i hope we will done.

inshAllah

Sis can u tell me iss main karna kay hy sir kay questions ki sumaj nahi a rahey

zain ul abdeen

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?

kiya koi diagram bnani ha ic men? YA in five question ka theoretically ans dena ha?

YOU HAVE TO write the method of GA step by step solution about above problem

sis nahi bro... :)

hehehehhe

NAYAB is our BHAI ;)

Here is very helpful matirial to understand and solve this tricky assignment

good luck

Attachments:

MahiL apki attachement open nae ho rahai

SIS in questions ka kay karna hy any body tell me

## Latest Activity

+ ! ! AɳƓєℓ ❥ liked M r . H a a D i . . . ! ! !'s blog post Today was cool
10 minutes ago
10 minutes ago
+ ! ! AɳƓєℓ ❥ liked zohaib iftikhar's blog post ...* DOST ...*
10 minutes ago
10 minutes ago
10 minutes ago
+ ! ! AɳƓєℓ ❥ liked + + + Haniya + + +'s discussion HAZRAT ALI (R.A)
11 minutes ago
+ ! ! AɳƓєℓ ❥ liked + + + Haniya + + +'s discussion WAQT DOST OR RELATION
11 minutes ago
+ ! ! AɳƓєℓ ❥ liked + + + Haniya + + +'s discussion FOR MY BEST FRIEND
11 minutes ago
+ ! ! AɳƓєℓ ❥ liked + ! ! ! ! ! branded billi ! ! +'s discussion soochieeee
11 minutes ago
+ ! ! AɳƓєℓ ❥ liked Rumz zahra's discussion Allah
11 minutes ago
11 minutes ago
11 minutes ago

1

2

3