Two-Dimensional Bin Packing Problem with Multiple Constraints — Code Analysis for Finding the Optimal Layout of Cairo Ramen Shop (Part 5) Genetic Algorithm Analysis

Preface

I mentioned some ideas about the genetic algorithm in the opening article; here is the specific process:

1. Generate two populations, using the BL algorithm and the BL_plus algorithm respectively;
2. Start iterating
3. Call the update_max() function of both populations to update the best individuals
4. If either population has an optimal solution (that is, all 12 shops have been placed), break out of the loop and return that individual;
5. If the number of iterations is reached, break out of the loop and return the best individuals of both populations;
6. If the exchange iteration count is reached, then: Assume the fitness of population P1's best individual is fbest1, and the fitness of P2's best individual is fbest2 (1) If fbest1>fbest2, replace P2's worst individual with P1's best individual; (2) If fbest1<fbest2, replace P1's worst individual with P2's best individual;
7. Perform selection, crossover, and mutation on the two populations respectively

8. Update the best individuals of the two new populations
9. If the fitness of a new population's best individual is less than that of the old population's best individual, replace the new population's worst individual with the old population's best individual.

Core Code

/// <summary>
/// 遗传算法
/// </summary>
/// <param name="path">店铺数据位置</param>
/// <param name="w">地区宽度</param>
/// <param name="h">地区高度</param>
/// <param name="iterations">迭代次数</param>
/// <param name="size">种群大小</param>
/// <param name="change">交换迭代次数</param>
/// <param name="crossover_frequency">交叉频率</param>
/// <param name="Pc1">用于计算交叉概率的参数一</param>
/// <param name="Pc2">用于计算交叉概率的参数二</param>
/// <param name="Pm1">用于计算变异概率的参数一</param>
/// <param name="Pm2">用于计算变异概率的参数二</param>
/// <param name="op_int">在基因片段一上的交叉算子</param>
/// <param name="op_bool">在基因片段二上的交叉算子</param>
/// <param name="va_int">在基因片段一上的变异算子</param>
/// <param name="va_bool">在基因片段二上的变异算子</param>
/// <returns>最优个体</returns>
public static Individual Inheritance(string path, int w, int h, int iterations, int size, int change,
    double crossover_frequency, double Pc1, double Pc2, double Pm1, double Pm2, operator_int op_int,
    operator_bool op_bool, variation_int va_int, variation_bool va_bool)
{
    Population pop1 = new Population(path, w, h, size, "BL");
    Population pop2 = new Population(path, w, h, size, "BL_plus");
    int fbest;
    for (int iteration = 0; iteration < iterations; iteration++)
    {
        pop1.update_max();
        pop2.update_max();
        fbest = pop1.fmax > pop2.fmax ? pop1.fmax : pop2.fmax;
        Console.WriteLine("第{0}次迭代，最优解的适应度为：{1}", iteration, fbest);
        if (pop1.Fmax.character.Count == 12)
        {
            return pop1.Fmax;
        }
    
        if (pop2.Fmax.character.Count == 12)
        {
            return pop2.Fmax;
        }
    
        if ((iteration + 1) % change == 0)
        {
            int min_index_1 = pop1.find_min_index();
            int min_index_2 = pop2.find_min_index();
            if (pop1.fmax > pop2.fmax)
            {
                pop2.ind[min_index_2] = pop1.Fmax;
                pop2.update_max();
            }
            else if (pop1.fmax < pop2.fmax)
            {
                pop1.ind[min_index_1] = pop2.Fmax;
                pop1.update_max();
            }
        }
    
        int crossover_times = (int) (size * crossover_frequency);
        double cros_prob, r, var_prob;
        Individual parent1, parent2;
        List<Individual> new_ind = new List<Individual>();
        List<int[]> gene_int;
        List<bool[]> gene_bool;
    
        //处理pop1
        for (int i = 0; i < crossover_times; i++)
        {
            parent1 = pop1.ind[pop1.roulette()];
            parent2 = pop1.ind[pop1.roulette()];
            cros_prob = pop1.cros_probability(parent1, parent2, Pc1, Pc2);
            r = Population.rand_double();
            if (r <= cros_prob)
            {
                gene_int = op_int(parent1.gene_order, parent2.gene_order);
                gene_bool = op_bool(parent1.gene_rotate, parent2.gene_rotate);
                Individual child;
                int[] ge_int;
                bool[] ge_bool;
                for (int j = 0; j < 2; j++)
                {
                    child = new Individual(w, h, gene_int[j], gene_bool[j], "BL",
                        pop1.decode(gene_int[j], gene_bool[j]));
                    var_prob = pop1.mut_probability(child, Pm1, Pm2);
                    r = Population.rand_double();
                    if (r < var_prob)
                    {
                        ge_int = va_int(gene_int[j]);
                        ge_bool = va_bool(gene_bool[j]);
                        child = new Individual(w, h, ge_int, ge_bool, "BL",
                            pop1.decode(ge_int, ge_bool));
                    }
    
                    new_ind.Add(child);
                }
            }
        }
    
        while (new_ind.Count < size)
        {
            new_ind.Add(pop1.ind[pop1.roulette()]);
        }
    
        int index, fmax = 0;
        for (int i = 0; i < size; i++)
        {
            if (new_ind[i].fit_count() > fmax)
            {
                fmax = new_ind[i].fit_count();
            }
        }
    
        if (fmax < pop1.fmax)
        {
            index = 0;
            int fmin = int.MaxValue;
            for (int i = 0; i < size; i++)
            {
                if (new_ind[i].fit_count() < fmin)
                {
                    index = i;
                    fmin = new_ind[i].fit_count();
                }
            }
    
            new_ind[index] = pop1.Fmax;
        }
    
        pop1.ind = new_ind;
    
        //处理pop2
        new_ind = new List<Individual>();
        for (int i = 0; i < crossover_times; i++)
        {
            parent1 = pop2.ind[pop2.roulette()];
            parent2 = pop2.ind[pop2.roulette()];
            cros_prob = pop2.cros_probability(parent1, parent2, Pc1, Pc2);
            r = Population.rand_double();
            if (r <= cros_prob)
            {
                gene_int = op_int(parent1.gene_order, parent2.gene_order);
                gene_bool = op_bool(parent1.gene_rotate, parent2.gene_rotate);
                Individual child;
                int[] ge_int;
                bool[] ge_bool;
                for (int j = 0; j < 2; j++)
                {
                    child = new Individual(w, h, gene_int[j], gene_bool[j], "BL_plus",
                        pop2.decode(gene_int[j], gene_bool[j]));
                    var_prob = pop2.mut_probability(child, Pm1, Pm2);
                    r = Population.rand_double();
                    if (r > var_prob)
                    {
                        ge_int = va_int(gene_int[j]);
                        ge_bool = va_bool(gene_bool[j]);
                        child = new Individual(w, h, ge_int, ge_bool, "BL_plus",
                            pop2.decode(ge_int, ge_bool));
                    }
    
                    new_ind.Add(child);
                }
            }
        }
    
        while (new_ind.Count < size)
        {
            new_ind.Add(pop2.ind[pop2.roulette()]);
        }
    
        fmax = 0;
        for (int i = 0; i < size; i++)
        {
            if (new_ind[i].fit_count() > fmax)
            {
                fmax = new_ind[i].fit_count();
            }
        }
    
        if (fmax < pop2.fmax)
        {
            index = 0;
            int fmin = int.MaxValue;
            for (int i = 0; i < size; i++)
            {
                if (new_ind[i].fit_count() < fmin)
                {
                    index = i;
                    fmin = new_ind[i].fit_count();
                }
            }
    
            new_ind[index] = pop2.Fmax;
        }
    
        pop2.ind = new_ind;
    }

    if (pop1.fmax > pop2.fmax)
    {
        return pop1.Fmax;
    }

    return pop2.Fmax;
}

Finally

That's the entire process of my search for the optimal solution of Cairo Ramen Shop! Along the way I took many detours, and I even prepared a dozen or so parameters ready for tuning—I didn't expect a result after only a little over 130 iterations. Very lucky! But it's actually quite understandable, because the initial solutions generated by my improved algorithm were already not far from the optimum, so fast convergence is only natural.

Finally, here are the two optimal solutions I found: