Two-Dimensional Bin Packing Problem Under Multiple Constraints — Code Analysis for Finding the Optimal Layout of Cairo Ramen Shop (Part 3)

Population Class: Population

Properties

The first thing the population class needs to store is the original genes mentioned in the previous article; second, in order to apply the elite preservation strategy, worst-individual assignment, and so on, it needs to record information related to the best individual; at the same time, when calculating crossover and mutation probabilities, a method for obtaining the average fitness is needed, so to simplify calculation, storing each individual's fitness is quite necessary.

/// <summary>
/// 个体列表
/// </summary>
public List<Individual> ind;

/// <summary>
/// 原始基因
/// </summary>
private List<Store> gene_pool;

/// <summary>
/// 最优个体
/// </summary>
public Individual Fmax;

/// <summary>
/// 最优个体适应值
/// </summary>
public int fmax;

/// <summary>
/// 最优个体对应索引
/// </summary>
public int fmax_index;

/// <summary>
/// 每个个体的适应值
/// </summary>
public int[] fit_count;

Methods

Update the Best Individual and Update Fitness

In both the elite preservation strategy and the worst-individual assignment strategy, the population's best individual needs to be found, so what needs to be done here is to update the information related to the best individual, and incidentally update the individuals' fitness values.

/// <summary>
/// 更新种群最优个体，并更新适应度
/// </summary>
public void update_max()
{
    int fit;
    for (int i = 0; i < ind.Count; i++)
    {
        fit = ind[i].fit_count();
        fit_count[i] = fit;
        if (fit > fmax)
        {
            fmax_index = i;
            fmax = fit;
            Fmax = ind[i];
        }
    }
}

Crossover Probability

In the paper I mainly referenced (freeloaded), crossover probability is defined as follows:

where Pc1=0.9, Pc2=0.6, f' is the larger fitness of the two individuals participating in crossover, favg is the population's average fitness, and fmax is the population's maximum fitness.

To get the average fitness, we have to write a small method to compute it; other than that, it's just plugging into the formula.

/// <summary>
/// 计算种群平均适应度
/// </summary>
/// <returns>平均适应值</returns>
public float avg()
{
    float ans = 0;
    foreach (var i in ind)
    {
        ans += i.fit_count();
    }

    return ans / ind.Count;
}

/// <summary>
/// 计算交叉概率
/// </summary>
/// <param name="ind1">个体一</param>
/// <param name="ind2">个体二</param>
/// <param name="Pc1">参数一</param>
/// <param name="Pc2">参数二</param>
/// <returns>交叉概率</returns>
public double cros_probability(Individual ind1, Individual ind2, double Pc1 = 0.9, double Pc2 = 0.6)
{
    int fit1 = ind1.fit_count(), fit2 = ind2.fit_count(), f;
    float fit_avg = avg();
    update_max();
    if (fit1 > fit2)
    {
        f = fit1;
    }
    else
    {
        f = fit2;
    }

    double ans = Pc1;
    if (f >= fit_avg)
    {
        ans -= (Pc1 - Pc2) * (f - fit_avg) / (fmax - fit_avg);
    }

    return ans;
}

Mutation Probability

Mutation probability is defined as follows:

where Pm1=0.1, Pm2=0.01, and f is the fitness of the individual undergoing mutation.

/// <summary>
/// 变异概率
/// </summary>
/// <param name="ind1">个体</param>
/// <param name="Pm1">参数一</param>
/// <param name="Pm2">参数二</param>
/// <returns>变异概率</returns>
public double mut_probability(Individual ind1, double Pm1 = 0.1, double Pm2 = 0.01)
{
    int f = ind1.fit_count();
    float fit_avg = avg();
    update_max();

    double ans = Pm1;
    if (f >= fit_avg)
    {
        ans -= (Pm1 - Pm2) * (fmax - f) / (fmax - fit_avg);
    }

    return ans;
}

Generating Random Numbers

In the crossover operator and mutation operator, generating a random integer is used extensively; in the roulette-wheel algorithm as well as the genetic algorithm, a random real number also needs to be generated.

/// <summary>
/// 生成随机整数
/// </summary>
/// <param name="a">下限</param>
/// <param name="b">上限</param>
/// <returns>随机整数</returns>
public static int rand_int(int a, int b)
{
    byte[] buffer = Guid.NewGuid().ToByteArray();
    int iSeed = BitConverter.ToInt32(buffer, 0);
    Random ran = new Random(iSeed);
    return ran.Next(a, b);
}

/// <summary>
/// 生成（0,1）上的随机实数
/// </summary>
/// <returns>随机实数</returns>
public static double rand_double()
{
    byte[] buffer = Guid.NewGuid().ToByteArray();
    int iSeed = BitConverter.ToInt32(buffer, 0);
    Random ran = new Random(iSeed);
    return ran.NextDouble();
}

Find the Worst Individual in the Population

The worst-individual assignment strategy needs to find the worst individual in the population.

/// <summary>
/// 找出最差个体对应索引
/// </summary>
/// <returns>最差个体对应索引</returns>
public int find_min_index()
{
    int index = 0, fmin = int.MaxValue;
    for (int i = 0; i < ind.Count; i++)
    {
        if (fit_count[i] < fmin)
        {
            index = i;
            fmin = fit_count[i];
        }
    }

    return index;
}

Decoder

As mentioned earlier, the decoder is the method that restores gene encodings back into genes. Because random ordering operations and random rotation operations are performed based on this population's original genes, and there is no need to change the original genes themselves, it needs to call the Store class's clone to perform a deep copy, so as to keep the original genes "pure".

/// <summary>
/// 解码器，由两个基因片段编码生成个体的基因
/// </summary>
/// <param name="gene_order">基因片段编码一</param>
/// <param name="gene_rotate">基因片段编码二</param>
/// <returns>基因</returns>
public List<Store> decode(int[] gene_order, bool[] gene_rotate)
{
    List<Store> ans = new List<Store>();
    gene_pool.ForEach(i => ans.Add(i.Clone()));

    for (int i = 0; i < gene_rotate.Length; i++)
    {
        if (gene_rotate[i])
        {
            ans[i].rotate();
        }
    }

    return ans.OrderBy(e =>
    {
        var index = 0;
        index = Array.IndexOf(gene_order, e.id);
        if (index != -1)
        {
            return index;
        }

        return int.MaxValue;
    }).ToList();
}

Roulette Wheel

The roulette-wheel algorithm is implemented as follows: normalize each individual's fitness (that is, divide by the sum of the population's fitness values), then generate a random number, and see which interval this random number falls into to select that individual. For example, suppose there are four individuals with fitness values 1, 2, 3, and 4 respectively; after normalization they are 0.1, 0.2, 0.3, 0.4. I generate a random real number r=0.61826 on (0,1), which falls in the interval (0.1+0.2+0.3,0.1+0.2+0.3+0.4), so the fourth individual is selected.

It can be seen quite intuitively that individuals with larger fitness occupy a larger sector area and are thus more likely to be selected. This is precisely the purpose of roulette wheel — survival of the fittest. This helps improve the genetic algorithm's convergence speed, yet due to its randomness, the algorithm is not prone to falling into a local optimum. This is the first manifestation of the unique charm of genetic algorithms.

One more point to note: to guarantee the "purity" of the best individual and try not to disrupt the structure of the best individual, the best individual does not participate in the roulette wheel.

/// <summary>
/// 轮盘赌算法，随机选择个体
/// </summary>
/// <returns>随机选择的个体</returns>
public int roulette()
{
    Dictionary<int, double> dict = new Dictionary<int, double>();
    for (int i = 0; i < ind.Count; i++)
    {
        if (i != fmax_index)
        {
            dict[i] = (double) fit_count[i] / (fit_count.Sum()-fmax);
        }
    }


    double r = rand_double(), sum = 0.0;
    int index = 0;
    foreach (var k in dict)
    {
        sum += k.Value;
        if (sum > r)
        {
            index = k.Key;
            break;
        }
    }

    return index;
}