Reply With Quoteyarrrrrrrrrrr koi tou solution day
CS607 Artificial Intelligence Assignment No.3 Solution Spring Semester 2013
View more random threads:
- CS302 Digital Logic Design Assignment Semester Fall 2014
- CS301 Assignment # 4
- HRM 624 Assignment Solution required
- ACC501 Business Finance Assignment No.2 Solution Spring...
- Artificial Intelligence cs607 5th ASsignment July, 2010
- first assignement of MGT111 fall 2010
- CS410 Visual Programming Assignment No.2 Fall Semester 23rd...
- CS410 Visual Programming Assignment # 2 May 6,2010
- CS601 Assignment 3 Solution, June 2010
- Eco401 Economics Assignment 2 Deadline 9 July 2010
CS607 Artificial Intelligence Assignment No.3 Solution Spring Semester 2013
Assignment No. 03
Semester: Spring 2013
CS607: Artificial Intelligence
Total Marks: 20
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.
Crossover/
/ Time-over
Figure 1: Flow chart of steps in Genetic Algorithm.
Important things to consider in application of GA
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.
Population Size: It is the number of chromosomes that we need to initialize and carry forward in every generation.
Fitness function: This is a way to evaluate the goodness of current chromosomes/solutions.
Crossover: This is required to define how existing chromosomes/solutions will generate new chromosomes/solutions (hopefully improved).
Mutation: How to make small random change in new generated chromosomes/solutions.
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
Sponsored Links
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.
yarrrrrrrrrrr koi tou solution day
es ki to last date b ab guzer gai hai
There are currently 1 users browsing this thread. (0 members and 1 guests)
Posting Permissions
