Я использую генетический алгоритм для решения проблемы расписания. После нескольких итераций мои показатели пригодности начинают становиться одинаковыми.
Я пытался настроить частоту кроссовера и мутации, но безрезультатно.
Состав:
Каждая хромосома содержит несколько классов. В основном каждая хромосома - это расписание.
Я реализовал генетический алгоритм.
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)
}
Я ожидаю более низкие значения пригодности с каждой итерацией.
Я получаю постоянные значения после нескольких итераций, т. Е. 7. Все хромосомы (в одной популяции) имеют одинаковые значения!
Спасибо!
Edit:
Оппс Извините,
Вот код:
Основной класс:
/*
* 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:
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
}
Выход:
//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