程序设计实验室
微信公众号
个体类：Individual
属性
一个个体在遗传算法中最关键的属性是基因编码和性状，为此还需要引出一个原始基因的定义（在敲代码的时候我把这玩意儿叫做基因库，但是后来查资料才发现，基因库是用来储存优秀个体，提高种群质量的，和我这里的作用并不相同，所以作出修正）。原始基因就是题目给定的这12个店铺，而在生成个体的基因的时候就只是单纯的在这条原始基因上进行随机重排序操作和随机旋转操作；性状则是进行这两个操作后得到的基因再通过BL算法或BL算法加强版得到的一个可行解，也就是一个店铺布局。因此，个体类应该储存的属性应该有性状、基因片段的编码、区域的宽度和高度。
/// <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;
方法
判断当前解是不是可行解
这一部分主要是针对约束条件2、3、4，也就是判断有没有重叠、有没有出界、入口是不是都有路。前两者都不难实现，对于约束条件4，我采用的方法是这样的：首先用一个bool二维数组来记录当前格子是否可以走，这个数组先是初始化为全部都可以走，然后我将当前解里的每一家店铺覆盖的区域都改为不能走，也就是“墙”，这样有点类似于走迷宫，你要做的就是判断能不能从迷宫里走出来。我用一个栈来储存当前需要搜索的格子坐标，先从这家店铺的入口开始，我把这个入口push进这个栈里，然后开始循环，每次循环先把栈顶pop出来，如果pop出来的这个格子不能走，就不操作，能走的话，就把上下左右四个方向的格子坐标全部push进栈，直到我pop出来的这个格子是边界或者栈里没有格子才跳出循环。要注意这里的一个逻辑是这样的：只要存在一条路径能够到达区域边界，这个店铺就是可行的；只要有一家店铺不可行，这个解就是不可行的。
/// <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;
}
BL算法与BL算法加强版
这一部分的思路啥的前面已经讲的七七八八了，这里直接上代码。
/// <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;
}
计算个体适应值
个体适应值是性状中所有店铺面积之和，十分简单，但也十分关键。
/// <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;
}
以上就是个体类的实现，下面就是稍微复杂一点的种群类了。