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

Individual Class: Individual

Properties

The most critical attributes of an individual in a genetic algorithm are the gene encoding and the phenotype. For this, we also need to introduce a definition of the original gene (when I was writing the code I called this thing a gene pool, but later when I looked it up I found that a gene pool is used to store elite individuals and improve population quality, which is not the same as the role it plays here, so I made a correction). The original gene is the 12 shops given in the problem, and when generating an individual's genes we simply perform a random reordering operation and a random rotation operation on this original gene; the phenotype is a feasible solution obtained by taking the gene after these two operations and running it through the BL algorithm or the enhanced BL algorithm, that is, a shop layout. Therefore, the attributes the Individual class should store are the phenotype, the encoding of the gene segments, and the width and height of the region.

/// <summary>
/// 性状
/// </summary>
public List<Store> character;

/// <summary>
/// 地区宽度
/// </summary>
public int Width;

/// <summary>
/// 地区高度
/// </summary>
public int Height;
/// <summary>
/// 基因片段一
/// </summary>
public int[] gene_order;

/// <summary>
/// 基因片段二
/// </summary>
public bool[] gene_rotate;

Methods

Checking Whether the Current Solution Is Feasible

This part mainly addresses constraints 2, 3, and 4, that is, checking whether there is overlap, whether anything is out of bounds, and whether every entrance has a path. The first two are not hard to implement. For constraint 4, the method I used is as follows: first use a 2D bool array to record whether the current cell is walkable. This array is first initialized so that everything is walkable, then I change the area covered by every shop in the current solution to unwalkable, that is, "walls." This is somewhat like walking a maze; what you need to do is determine whether you can walk out of the maze. I use a stack to store the coordinates of the cells that currently need to be searched. Starting from this shop's entrance, I push this entrance onto the stack, then start looping. Each iteration first pops the top of the stack; if the popped cell is not walkable, do nothing; if it is walkable, push the coordinates of the cells in all four directions—up, down, left, and right—onto the stack, until the cell I pop is on the boundary or there are no cells left in the stack, at which point I break out of the loop. Note that the logic here is as follows: as long as there exists a path that can reach the region boundary, this shop is feasible; as long as any one shop is infeasible, the solution is infeasible.

/// <summary>
/// 判断店铺之间是否有重叠
/// </summary>
/// <param name="data">店铺数据</param>
/// <returns>有重叠返回false，没有返回true</returns>
static bool if_end_overlap(List<Store> data)
{
    int i = data.Count - 1;
    for (int j = 0; j < i; j++)
    {
        if (!data[i].overlap_pro(data[j]))
        {
            return false;
        }
    }

    return true;
}

/// <summary>
/// 判断布局是否为可行解
/// </summary>
/// <param name="data">布局数据</param>
/// <returns>可行解返回true，不可行返回false</returns>
public bool is_feasible(List<Store> data)
{
    for (int i = 0; i < data.Count; i++)
    {
        if (data[i].point.X < 0 || data[i].point.Y < 0)
        {
            return false;
        }
    }

    if (!if_end_overlap(data))
    {
        return false;
    }

    bool flag1 = true;
    int[,] direction = new int[4, 2] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    Point p;
    for (int i = 0; i < data.Count; i++)
    {
        Stack<Point> sta = new Stack<Point>();
        bool flag2 = false;
        bool[,] area = area_initialize(data);
        sta.Push(new Point(data[i].door.X + data[i].point.X, data[i].door.Y + data[i].point.Y));
        while (sta.Count > 0)
        {
            p = sta.Pop();
            if (area[p.X, p.Y])
            {
                if (p.X == 0 || p.X == Width - 1 || p.Y == 0 || p.Y == Height - 1)
                {
                    flag2 = true;
                    break;
                }

                area[p.X, p.Y] = false;
                for (int j = 0; j < 4; j++)
                {
                    sta.Push(new Point(p.X + direction[j, 0], p.Y + direction[j, 1]));
                }
            }
        }

        if (!flag2)
        {
            flag1 = false;
            break;
        }
    }

    return flag1;
}

/// <summary>
/// 生成布局的布尔类型二维数组
/// </summary>
/// <param name="data">布局数据</param>
/// <returns>生成的数组</returns>
public bool[,] area_initialize(List<Store> data)
{
    bool[,] area = new bool[Width, Height];
    for (int i = 0; i < Width; i++)
    {
        for (int j = 0; j < Height; j++)
        {
            area[i, j] = true;
        }
    }

    for (int i = 0; i < data.Count; i++)
    {
        for (int j = data[i].point.X; j < data[i].point.X + data[i].width; j++)
        {
            for (int k = data[i].point.Y; k < data[i].point.Y + data[i].height; k++)
            {
                area[j, k] = false;
            }
        }
    }

    return area;
}

The BL Algorithm and the Enhanced BL Algorithm

The ideas and so on for this part have already been pretty much covered earlier, so I'll just show the code here.

/// <summary>
/// BL算法
/// </summary>
/// <param name="data">拉面店数据</param>
/// <returns>铺好的拉面店</returns>
public List<Store> BL(List<Store> data)
{
    List<Store> ans = new List<Store>(), data1 = new List<Store>();
    data.ForEach(i => data1.Add(i.Clone()));
    bool flag1, flag2, flag3, flag = true;
    for (int box = 0; box < data1.Count; box++)
    {
        if (data1[box].set(Width, Height, ans))
        {
            while (true)
            {
                int move_down = data1[box].go_down(ans);
                int move_left = data1[box].go_left(ans);
                if (move_down == 0 && move_left == 0)
                {
                    break;
                }
            }

            ans.Add(data1[box]);
            while (true)
            {
                flag1 = if_go_a_down(ans);
                flag2 = if_go_a_left(ans);
                flag3 = if_go_down_and_left(ans);
                if (!flag1 && !flag2)
                {
                    break;
                }

                if (flag1 && !flag2 && !flag3)
                {
                    ans[ans.Count - 1].point.Y -= 1;
                }

                if (!flag1 && flag2 && !flag3)
                {
                    ans[ans.Count - 1].point.X -= 1;
                }

                if (flag3)
                {
                    ans[ans.Count - 1].point.X -= 1;
                    ans[ans.Count - 1].point.Y -= 1;
                }

                if (flag1 && flag2 && !flag3)
                {
                    ans[ans.Count - 1].point.Y -= 1;
                }
            }
        }
    }

    return ans;
}

/// <summary>
/// 判断是否能下移一格
/// </summary>
/// <param name="data">已填充的店铺数据</param>
/// <returns>能下移返回true，不能返回false</returns>
public bool if_go_a_down(List<Store> data)
{
    List<Store> data1 = new List<Store>();
    data.ForEach(j => data1.Add(j.Clone()));
    int i = data1.Count - 1;
    data1[i].point.Y -= 1;
    return is_feasible(data1);
}

/// <summary>
/// 判断是否能左移一格
/// </summary>
/// <param name="data">已填充的店铺数据</param>
/// <returns>能左移返回true，不能返回false</returns>
public bool if_go_a_left(List<Store> data)
{
    List<Store> data1 = new List<Store>();
    data.ForEach(j => data1.Add(j.Clone()));
    int i = data.Count - 1;
    data1[i].point.X -= 1;
    return is_feasible(data1);
}

/// <summary>
/// 判断是否能同时下移和左移
/// </summary>
/// <param name="data">已填充的店铺数据</param>
/// <returns>能的话返回true，不能返回false</returns>
public bool if_go_down_and_left(List<Store> data)
{
    List<Store> data1 = new List<Store>();
    data.ForEach(j => data1.Add(j.Clone()));
    int i = data1.Count - 1;
    data1[i].point.X -= 1;
    data1[i].point.Y -= 1;
    return is_feasible(data1);
}

/// <summary>
/// BL算法加强版
/// </summary>
/// <param name="data">拉面店数据</param>
/// <returns>铺好的拉面店</returns>
public List<Store> BL_plus(List<Store> data)
{
    List<Store> data1 = new List<Store>();
    data.ForEach(j => data1.Add(j.Clone()));
    List<Store> ans = new List<Store>();
    bool flag1, flag2, flag3;
    for (int box = 0; box < data1.Count; box++)
    {
        if (data1[box].set(Width, Height, ans))
        {
            while (true)
            {
                Point p = data1[box].BL_plus_move(ans);
                if (p.X == 0 && p.Y == 0)
                {
                    break;
                }
            }

            ans.Add(data1[box]);
            while (true)
            {
                flag1 = if_go_a_down(ans);
                flag2 = if_go_a_left(ans);
                flag3 = if_go_down_and_left(ans);
                if (!flag1 && !flag2)
                {
                    break;
                }

                if (flag1 && !flag2 && !flag3)
                {
                    ans[ans.Count - 1].point.Y -= 1;
                }

                if (!flag1 && flag2 && !flag3)
                {
                    ans[ans.Count - 1].point.X -= 1;
                }

                if (flag3)
                {
                    ans[ans.Count - 1].point.X -= 1;
                    ans[ans.Count - 1].point.Y -= 1;
                }

                if (flag1 && flag2 && !flag3)
                {
                    ans[ans.Count - 1].point.Y -= 1;
                }
            }
        }
    }

    return ans;
}

Calculating Individual Fitness

The fitness of an individual is the sum of the areas of all shops in the trait. It is very simple, but also very important.

/// <summary>
/// 计算本个体的适应度
/// </summary>
/// <returns>适应度</returns>
public int fit_count()
{
    int sum = 0;
    for (int i = 0; i < character.Count; i++)
    {
        sum += character[i].width * character[i].height;
    }

    return sum;
}

The above is the implementation of the individual class; next comes the slightly more complex population class.