遗传算法：为什么我的随机种群适应度值相同？

Question

我正在实施遗传算法来解决时间表问题。几次迭代后，我的健身值开始变得相同。我试过调整交叉率和突变，但无济于事。

结构：每条染色体包含多个类。基本上每条染色体都是一个时间表。我实现了遗传算法。

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。所有染色体（在一个群体中）具有相同的值！

谢谢！

编辑：抱歉，这是代码：

主要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;                   
            }

染色体 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
    }

输出：

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

Answer 1

如@Stefan 所述，请将实际代码作为起点。那就是说我可以建议你比较最佳适应度和平均适应度，如果这两个值太接近（配置阈值）随机化人口中的几个元素，直到 bestFitness - averageFitness > threshold

Answer 2

好的解决方案是随着迭代次数的增加，我必须增加交叉和突变，否则我会陷入局部最小值！

请参阅此 link 了解更多信息： WebLink R. 洛格什：遗传算法无法避免种群的重复。事实上，结果收敛于解决方案的指标之一是人口的重复。如果你想要更多的人口组合，你需要增加交叉概率和突变概率。建议交叉概率在0.8以上，变异在0.3以下，收敛性好。

遗传算法：为什么我的随机种群适应度值相同？

Genetic Algorithm: Why my random population fitness values are same?

c#

artificial-intelligence

timetable

genetic-algorithm