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

Looking For Something at vustudents.ning.com? Click Here to Search


+ Link For Assignments, GDBs & Online Quizzes Solution


+ 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

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

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



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.



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.



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




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?




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





+ How to Follow the New Added Discussions at Your Mail Address?

+ 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?

See Your Saved Posts Timeline

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)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

+ Click Here To Join (Our facebook study Group)

Replies to This Discussion

Spring 2013_CS607_3


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.


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... :)


NAYAB is our BHAI ;)

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

good luck

and please share your idea's with clear heart


 MahiL apki attachement open nae ho rahai

SIS in questions ka kay karna hy any body tell me 

please reload


© 2020   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service