Assignment # 03
Artificial Intelligence, Fall 2012
Department of Computer Science & Software Engineering, IIUI
Submission Deadline: Monday 04:30 PM, December 10, 2012
The above diagram illustrates the working of Genetic
Algorithm. For example the number 24748552 depict the position of the queens.
The below diagram explain all.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
1
|
||||||||
2
|
Q
|
Q
|
||||||
3
|
||||||||
4
|
Q
|
Q
|
||||||
5
|
Q
|
Q
|
||||||
6
|
||||||||
7
|
Q
|
|||||||
8
|
Q
|
A pair of queen is attacking pair directly or indirectly if both
are in same row or same column or in same diagonal.
You are required to perform following task
- Take four states of the Queen table as Initial population. You are required to use to rand function to produce the position of each queen in each column in all four states.
- Find the number of non-attacking pairs (fitness) for each state.
- Perform selection step. The selection should be random in which one state can come either zero time or more than one times.
- The cut for cross over should be decided randomly on each pair.
- In mutation, mute only single element of each state.
- Calculate the fitness again. If the fitness of even single state is better than all states in initial population then stop and display that state, otherwise repeat step 3 to 6
//////////////////////////////////////////////////////
GENETIC ALGORITHM
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
using System.Threading;
namespace Genetic_Algo
{
class Program
{
public int selected1,selected2,selected3,selected4;
int[] arr1, arr2, arr3, arr4 = new int[9];
public static int[] Original = new int[5];
public static int[] Calculated = new int[5];
public int[] array1=new int[9];
public int[] array2=new int[9];
public int[] array3=new int[9] ;
public int[] array4=new int[9];
public static Random random_num = new Random();
static int collision_pairs=0;
///////////////////////////////////////////////////////////////////
public void Initial_Population()
// Generate Four States of the Queen
initial population
{
double percentage = 0;
for (int j = 1; j < 9; j++)
{
array1[j]=random_num.Next(1,9);
array2[j] =
random_num.Next(1, 9);
array3[j] =
random_num.Next(1, 9);
array4[j] =
random_num.Next(1, 9);}
//
Initial Fitness Values Stored in Original array
EvaluateCollision(array1);
Original[1] = 28 -
collision_pairs;
EvaluateCollision(array2);
Original[2] = 28 -
collision_pairs;
EvaluateCollision(array3);
Original[3] = 28 -
collision_pairs;
EvaluateCollision(array4);
Original[4] = 28 -
collision_pairs;
////////////////////////////////////Calculate
the Original Values Percentages
percentage
= (double)Original[1]/(Original[1]+Original[2]+Original[3]+Original[4]);
percentage
= percentage * 100; percentage = Math.Round(percentage);
Original[1]
= (int)percentage;
percentage
= (double)Original[2]
/ (Original[1] + Original[2] + Original[3] + Original[4]);
percentage
= percentage * 100; percentage = Math.Round(percentage);
Original[2]
= (int)percentage;
percentage
= (double)Original[3]
/ (Original[1] + Original[2] + Original[3] + Original[4]);
percentage
= percentage * 100; percentage = Math.Round(percentage);
Original[3]
= (int)percentage;
percentage
= (double)Original[4]
/ (Original[1] + Original[2] + Original[3] + Original[4]);
percentage = percentage * 100;
percentage = Math.Round(percentage);
Original[4] = (int)percentage;
///////////////////////////////
Write Initial Population on Screen
Console.WriteLine("Initial
Population:" + " " + "Non-Attacking Queens
Pairs %"); Console.WriteLine("-------------------
-----------------------------");
for (int w = 1; w < 9; w++) { Console.Write(array1[w]); } Console.WriteLine(" "+Original[1]);
for (int w = 1; w < 9; w++) { Console.Write(array2[w]); } Console.WriteLine(" "+Original[2]);
for (int w = 1; w < 9; w++) { Console.Write(array3[w]); } Console.WriteLine(" "+Original[3]);
for (int w = 1; w < 9; w++) { Console.Write(array4[w]); } Console.WriteLine(" "+Original[4]); }
///////////////////////////////////////////////////////////////////
public void EvaluateCollision(int[] array) //Function to count attacking queens
{
collision_pairs = 0;
for (int i = 1; i <= 8; i++)
for (int j = i + 1; j <= 8; j++)
if (Math.Abs(i - j) == Math.Abs(array[i] - array[j]))
collision_pairs++;
for (int j = 1; j < 8; j++)
{
for (int k = j + 1; k < 9; k++)
{
if (array[j] == array[k])
{
collision_pairs++;
}}}}
//////////////////////////////////////////////////////////////////
public void Fitness_Function()
//Calculate the Fitness again and again
{
Console.ForegroundColor = ConsoleColor.DarkCyan;
Console.Write("Performing
Fitness Step");
for (int i = 1; i <= 6; i++)
{
Console.Write(".");
Thread.Sleep(50);
} Console.WriteLine();
double percentage = 0;
EvaluateCollision(arr1);
Calculated[1] = 28 - collision_pairs;
EvaluateCollision(arr2);
Calculated[2] = 28 - collision_pairs;
EvaluateCollision(arr3);
Calculated[3] = 28 - collision_pairs;
EvaluateCollision(arr4);
Calculated[4] = 28 - collision_pairs;
//////////////////////////////////////// //Calculate Percentages
percentage=(double)Calculated[1]/(Calculated[1]
+ Calculated[2] + Calculated[3] + Calculated[4]);
percentage
= percentage * 100; percentage = Math.Round(percentage);
Calculated[1]
= (int)percentage;
percentage
= (double)Calculated[2]
/ (Calculated[1] + Calculated[2] + Calculated[3] + Calculated[4]);
percentage
= percentage * 100; percentage = Math.Round(percentage);
Calculated[2]
= (int)percentage;
percentage
= (double)Calculated[3]
/ (Calculated[1] + Calculated[2] + Calculated[3] + Calculated[4]);
percentage
= percentage * 100; percentage = Math.Round(percentage);
Calculated[3] = (int)percentage;
percentage = (double)Calculated[4] /
(Calculated[1] + Calculated[2] + Calculated[3] + Calculated[4]);
percentage = percentage * 100; percentage =
Math.Round(percentage);
Calculated[4] = (int)percentage;}
//////////////////////////////////////////////////////////////////
public void Selection() //Make Random Selection of States
{
Console.ForegroundColor = ConsoleColor.Green;
Console.Write("Performing
Selection Step");
for (int i = 1; i <= 6; i++)
{ Console.Write(".");
Thread.Sleep(50);
} Console.WriteLine();
selected1 = random_num.Next(1,5);
selected2 = random_num.Next(1,5);
selected3 = random_num.Next(1,5);
selected4 = random_num.Next(1,5);
if (selected1 == 1) { arr1 = array1; }; if (selected1 == 2) { arr1 =
array2; }; if
(selected1 == 3) { arr1 = array3; };
if (selected1 == 4) { arr1 = array4; }
if (selected2 == 1) { arr2 = array1; }; if (selected2 == 2) { arr2 =
array2; }; if
(selected2 == 3) { arr2 = array3; };
if (selected2 == 4) { arr2 = array4; }
if (selected3 == 1) { arr3 = array1; }; if (selected3 == 2) { arr3 =
array2; }; if
(selected3 == 3) { arr3 = array3; };
if (selected3 == 4) { arr3 = array4; }
if (selected4 == 1) { arr4 = array1; }; if (selected4 == 2) { arr4 =
array2; }; if
(selected4 == 3) { arr4 = array3; };
if (selected4 == 4) { arr4 = array4; }
}
//////////////////////////////////////////////////////////////////
public void Cross_Over() //Mark Cut Randomly in States
{
Console.ForegroundColor = ConsoleColor.DarkYellow;
Console.Write("Performing
Cross-Over Step");
for (int i = 1; i < 6; i++)
{
Console.Write(".");
Thread.Sleep(50);
} Console.WriteLine();
int[] temp = new int[9];
int cut1, cut2;
cut1 = random_num.Next(1,9);
cut2 = random_num.Next(1,9);
for (int loop1 = cut1 + 1; loop1 < 9; loop1++)
{ temp[loop1] = arr1[loop1];
arr1[loop1] = arr2[loop1];
arr2[loop1] = temp[loop1];
}
for (int loop2 = cut2 + 1; loop2 < 9;loop2++ )
{
temp[loop2] = arr3[loop2];
arr3[loop2] = arr4[loop2];
arr4[loop2] = temp[loop2];
}}
//////////////////////////////////////////////////////////////////
public void Mutation() //Change a number at random position by a random number
{
Console.ForegroundColor = ConsoleColor.Yellow;
Console.Write("Performing
Mutation Step");
for (int i = 1; i <= 6; i++)
{
Console.Write(".");
Thread.Sleep(50);
} Console.WriteLine();
arr1[random_num.Next(1, 9)] =
random_num.Next(1, 9);
arr2[random_num.Next(1, 9)] =
random_num.Next(1, 9);
arr3[random_num.Next(1, 9)] =
random_num.Next(1, 9);
arr4[random_num.Next(1, 9)] =
random_num.Next(1, 9);
}
//////////////////////////////////////////////////////////////////
public static void Main(string[] args)
{
bool flag = false;
Program obj = new Program();
Console.ForegroundColor = ConsoleColor.Red;
obj.Initial_Population();
Console.WriteLine("---------------------------------------------------");
obj.Selection();
obj.Cross_Over();
obj.Mutation();
while (true)
{
int[] State_Solution = new int[9];
obj.Fitness_Function();
for (int a = 1; a < 5; a++)
{
int curr = Calculated[a];
if (curr > Original[1] && curr > Original[2]
&& curr > Original[3] && curr > Original[4])
{
Console.ForegroundColor = ConsoleColor.Magenta;
Console.WriteLine("-------------------------------");
Console.Write("Resultant State: ");
Console.WriteLine("Non-Attacking Queens %");
if (a == 1) { State_Solution = obj.arr1; } if (a == 2) { State_Solution =
obj.arr2; }
if (a == 3) { State_Solution =
obj.arr3; } if (a == 4) { State_Solution = obj.arr4; }
for (int write = 1; write < 9; write++)
{
Console.Write(State_Solution[write]);}
obj.EvaluateCollision(State_Solution);
Console.WriteLine(" "+Calculated[a]);
flag = true;
break;
} }
if(flag==false)
{
obj.Selection();
obj.Cross_Over();
obj.Mutation();
}
if (flag == true)
{
Console.ReadLine();
break; } }}}}
