I m implementing genetic algorithm to solve timetable problem. After a few iterations , my fitness values start becoming same. I have tried adjusting crossover rate & mutation, but to no avail.
Structure: Each chromosome contains multiple classes. Basically each chromosome is a timetable. I have implemented genetic algorithm.
Pseudo Code:
random_population=generate_random_population(Data);
while(criteria not reached){
foreach(chromosome in random_population)
fitness_value=calculate_fitness(chromosome)
selected_population contains top 10 fittest chromosomes (selected through
fitness values)
random_population=perform_crossover_mutation(selected_population)
}
I m expecting lower fitness values with each iteration.
I m getting constant values after a few iterations i.e. 7. All the chromosomes(in a single population) have same values !
Thank you !
Edit: Opps Sorry, Here's the code:
Main Class:
/*
* GA Implementation
*
* */
//Creating Random Population
Class[][] random_population = chromoSome.generate_random_chromosomes(otherData.Total_rooms);
//Playing Game with random population created above
int no_of_times=0;
int no_of_times_max = mainForm.total_no_of_times;
while (no_of_times < no_of_times_max) //Criteria
{
int n = 10; //Top 10 fittest chromosomes will be selected from population
Class[][] selected_chromoSomes = new Class[20][]; //fittest chromosomes array
double[] fitness_values = new double[n];// fittest values array
//Initializing array values
for(int ij = 0; ij < n; ++ij)
{
fitness_values[ij] = -100000000;
}
//Playing Game
for (int i = 0; i < random_population.Length; ++i)
{
//On each chromomsome applying fitness function
//Storing fitness values in fitness_values array with respective chromosomes in selected chromosome array
int fitness = chromoSome.fitness_fun(random_population[i], otherData,teacher_count);
System.Console.Writeln("Fitness value :"+fitness);
//This step is used to store fittest chromosomes
for (int r = 0; r < 10; ++r) //Only storing 10 fittest chromosomes
{
if (fitness >= fitness_values[r])
{
fitness_values[r] = fitness;
selected_chromoSomes[r] = random_population[i];
r = 10;
}
}
}
//To prevent local maxima , I m initializing other selected chromosomes with random population
for (int i = n; i <selected_chromoSomes.Length; ++i)
{
if (selected_chromoSomes[i] == null)
{
int rand = rnd.Next(0, random_population.Length);
selected_chromoSomes[i] = random_population[rand];
}
}
//Applying crossover & mutation
int create_n = mainForm.total_generations; //create_n tells how much new chromosomes be created from selected_chromosomes. It is 100 by default.
random_population = chromoSome.apply_crossover_mutation(selected_chromoSomes, create_n, mainForm.crossover_rate);//Generating 100 new chromosomes from selected_chromosomes
++no_of_times;
}
ChromoSome Class:
public int fitness_fun(Class[] population,OtherData oD,int teachers_count)
{
//A teacher cannot teach more than 1 class at a time
int score = 0;
for (int t = 1; t <= teachers_count; ++t)
{
List<int> times = new List<int>();
List<String> days = new List<String>();
for (int i3 = 0; i3 < population.Length; ++i3)
{
if (population[i3].Teacher_id.Equals(t)) //Storing teacher day & times in which his/her classes are scheduled
{
times.Add(population[i3].TimeStart);
days.Add(population[i3].Day);
}
}
for (int i = 0; i < times.Count; ++i)
{
for (int j = i + 1; j < times.Count; ++j)
{
if (times[i] == times[j] && days[i]==days[j]) //Teacher time & day is same for 2 or more classes !
{
--score;
}
}
}
}
return score; //returns the fitness value
}
public Class[][] apply_crossover_mutation(Class[][] selected_chromosomes, int n_chromosomes, double ratio)
{
//ratio is by default 0.8. That means new populated is created using crossover of 80% selected chromosomes & using mutation of 20% selected chromosomes.
int selected_length = selected_chromosomes.Length; //its 20 btw
Class[][] all_chromosomes = new Class[n_chromosomes][];// New Population
Class[][] crossover_chromosomes = new Class[Convert.ToInt32(n_chromosomes * ratio)][]; //Chromosomes generated through crossover
Class[][] mutation_chromosomes = null; //Chromosomes generated through mutation
if (ratio != 1)
{
if(ratio%2==0)
mutation_chromosomes = new Class[Convert.ToInt32(n_chromosomes * (1 - ratio))][];
else
{
mutation_chromosomes = new Class[Convert.ToInt32(n_chromosomes * (1 - ratio))+1][];
}
}
//Crossover Chromosomes(One point)
int index = 0;
if (ratio > 0)
{
for (int j = 0; j < n_chromosomes * ratio; ++j)
{
int element1 = rnd.Next(0, selected_length);
int element2 = rnd.Next(0, selected_length);
int pos1 = rnd.Next(0, selected_chromosomes[0].Length);
int pos2 = rnd.Next(pos1, selected_chromosomes[0].Length);
Class[] chromosome = selected_chromosomes[element2];
for (int i = pos1; i < pos2; ++i)
{
chromosome[i] = selected_chromosomes[element1][i];
}
crossover_chromosomes[index] = chromosome;
++index;
}
}
//Mutation Chromosomes(Swap Mutation)
if (ratio != 1)
{
index = 0;
for (int j = 0; j < n_chromosomes * (1 - ratio); ++j)
{
int element2 = rnd.Next(0, selected_length);
Class[] chromosome = selected_chromosomes[element2];
int pos1 = rnd.Next(0, selected_chromosomes[0].Length);
int pos2 = rnd.Next(pos1, selected_chromosomes[0].Length);
//Simply swapping values !
int t1 = chromosome[pos1].TimeStart;
int t2 = chromosome[pos1].TimeEnd;
String day = chromosome[pos1].Day;
int room_no = chromosome[pos1].RoomNo;
int teacher_id = chromosome[pos1].Teacher_id;
int course_id = chromosome[pos1].Course_id;
double duration = chromosome[pos1].Class_duration;
Batch_Sec bs = chromosome[pos1].Bs;
chromosome[pos1].TimeStart = chromosome[pos2].TimeStart;
chromosome[pos1].TimeEnd = chromosome[pos2].TimeEnd;
chromosome[pos1].Day = chromosome[pos2].Day;
chromosome[pos1].RoomNo = chromosome[pos2].RoomNo;
chromosome[pos1].Teacher_id = chromosome[pos2].Teacher_id;
chromosome[pos1].Course_id = chromosome[pos2].Course_id;
chromosome[pos1].Bs = chromosome[pos2].Bs;
chromosome[pos1].Class_duration = chromosome[pos2].Class_duration;
chromosome[pos2].TimeStart = t1;
chromosome[pos2].TimeEnd = t2;
chromosome[pos2].Day = day;
chromosome[pos2].RoomNo = room_no;
chromosome[pos2].Teacher_id = teacher_id;
chromosome[pos2].Course_id = course_id;
chromosome[pos2].Bs = bs;
chromosome[pos2].Class_duration = duration;
//Storing in mutation array
mutation_chromosomes[index] = chromosome;
++index;
}
}
//Copying crossover & mutation chromosomes in all_chromosomes
int j1 = 0;
for (int i = 0; i < Convert.ToInt32(n_chromosomes * ratio); ++i)
{
all_chromosomes[j1] = crossover_chromosomes[i];
++j1;
}
for (int i = 0; i < Convert.ToInt32(n_chromosomes * (1 - ratio)); ++i)
{
all_chromosomes[j1] = mutation_chromosomes[i];
++j1;
}
return all_chromosomes;//New Population
}
Output:
//First Iteration
Fitness value: -175
Fitness value: -197
Fitness value: -183
Fitness value: -176
Fitness value: -176
Fitness value: -191
Fitness value: -188
Fitness value: -185
Fitness value: -182
Fitness value: -191
Fitness value: -184
Fitness value: -185
Fitness value: -185
Fitness value: -186
Fitness value: -177
Fitness value: -164
Fitness value: -173
Fitness value: -198
Fitness value: -197
Fitness value: -178
Fitness value: -211
Fitness value: -198
Fitness value: -186
Fitness value: -193
Fitness value: -196
..........
//Last Iteration
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
Fitness value: -199
..............Same values
Okay the solution was that as the iterations increase , I had to increase the crossover & mutations, otherwise I was getting stuck at local minima !
Please see this link for further information: WebLink R. Logesh: Repetition of population cannot be avoided in genetic algorithm. In fact one of the indicators that the result is converging to a solution is repetition of population. If you want more combinations of population you need to increase cross over probability and mutatio probability. It is recommended to have crossover probability above 0.8 and mutation below 0.3 for good convergence.