在 C# 中使用遗传算法解决八皇后问题
4.84/5 (28投票s)
使用遗传算法解决八皇后问题的 C# 代码
引言
解决 NP-hard 问题有多种方法。遗传算法是一种解决此类问题的简单方法。本文将介绍如何使用 C# 中的遗传算法解决八皇后问题。
八皇后问题是在一个 8×8 的棋盘上放置八个国际象棋皇后，使得任意两个皇后都不能互相攻击。因此，解决方案要求任意两个皇后都不能在同一行、同一列或同一对角线上。
要使用遗传算法，必须定义交叉算子、变异算子、染色体和基因。
问题表示
基因：基因是一个从 0 到 7 的数字，表示皇后所在的行号。基因在染色体中的位置表示皇后的列号。由于棋盘上的皇后数量与列/行数量相同，因此必须保证每列每行都有一个皇后。
染色体：染色体是一组 8 个基因。假设染色体中没有重复的基因。
示例
0|1|4|2|3|6|7|5 八个皇后位于以下单元格。
(0,0), (1,1), (2,4), (3,2), (4,3), (5,6), (6,7), (7,5)
变异：变异是通过将要变异的基因与同一染色体中随机选择的一个基因（当前要变异的基因除外）进行交换来完成的。
交叉：以 0.5 的概率从两个父代染色体中抽取基因。从一个父代抽取一个基因，并将其附加到子代染色体。在另一个父代中删除相应的基因。重复此步骤，直到两个父代染色体都为空，并且子代包含所有涉及的基因。
适应度函数：碰撞是指两个皇后能够互相攻击。这意味着它们在同一对角线、同一行或同一列。由于染色体没有重复基因，并且保证了 2 个皇后不会在同一列，因此只需计算对角线碰撞。因此，可能发生的最多碰撞次数为 28。适应度函数是一个“越高越好”的函数，因此可以通过从 28 中减去当前状态下发生的碰撞次数来计算。解决方案将有 0 次碰撞，适应度为 28。
Using the Code
类和结构
classGeneticAlgo：负责遗传算法所有操作的类。classFitnessComparator：一个比较器类，用于按适应度值对染色体进行排序，以便在表中显示最终种群。struct Chromosome：表示染色体的结构，包括基因、适应度和其平均适应度累积。class MainFrame：负责处理用户界面并创建初始种群以传递给遗传算法的类。class Board：负责棋盘的图形视图和操作的类。
变量
private const int存储最大适应度。MAX_FIT= 28;
函数
private List<chromosome> GetInitialPopulation(int population)
{
List<chromosome> initPop = new List<chromosome>();
GeneticAlgo RandomGen = new GeneticAlgo();
for (int i = 0; i < population; i++)
{
List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});
Chromosome chromosome = new Chromosome();
chromosome.genes = new int[8];
for (int j = 0; j < 8; j++)
{
int geneIndex = (int)(RandomGen.GetRandomVal
(0,genes.Count-1)+0.5);//randomly select a gene
chromosome.genes[j] = genes[geneIndex];
genes.RemoveAt(geneIndex);//remove selected gene
}
initPop.Add(chromosome);
}
return initPop;
}
此函数以种群大小作为参数，并返回一个包含随机生成的基因的染色体列表。基因的值是从包含 0 到 7 的列表中随机选择的。在从列表中选择值时，会删除选定的值，以避免染色体中出现重复基因。列表的大小等于种群的大小。使用此函数创建初始种群后，将返回的染色体列表发送到 DoMating 函数。
public void DoMating(ref List<Chromosome> initPopulation,
int generations, double probCrossver, double probMutation)
{
int totalFitness = 0;
CalcFitness(ref initPopulation, ref totalFitness);
for (int generation = 0; generation < generations; generation++)
{
PrepareRuletteWheel(ref initPopulation,totalFitness);
Crossover(ref initPopulation, probCrossver);
Mutate(ref initPopulation, probMutation);
CalcFitness(ref initPopulation, ref totalFitness);
if (initPopulation[initPopulation.Count - 1].fitness == 28)
break;
if (progress != null)
{
progress(generation + 1);
}
}
initPopulation.Sort(new FitnessComparator());
}
此函数以染色体列表作为初始种群，以我们愿意在算法中进行的代数为参数，以及交叉概率和变异概率。此函数的负责是调用 CalcFitness、PrepareRuletteWheel、Crossover 和 Mutate 函数来处理传播到所需代数。
public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)
{
int collisions = 0;
totalFitness = 0;
for (int k = 0; k < chromosome.Count; k++)
{
for (int i = 0; i < chromosome[k].genes.Length - 1; i++)
{
int x = i;
int y = chromosome[k].genes[i];
for (int j = i + 1; j < chromosome[k].genes.Length; j++)
{
if (Math.Abs(j - x) == Math.Abs
(chromosome[k].genes[j] - y))
collisions++;
}
}
Chromosome temp = chromosome[k];
temp.fitness = MAX_FIT - collisions;
chromosome[k] = temp;
totalFitness += chromosome[k].fitness;
collisions = 0;
}
}
此函数计算每个染色体的适应度，并将适应度值分配给每个染色体的 fitness 属性。通过计算碰撞次数并从最大碰撞次数中减去它来计算适应度，因为在此代码中，适应度是一个“越高越好”的函数。在为每个染色体计算适应度的同时，此函数还计算种群的总适应度，因为我们在下一步需要它来计算每个染色体的适应度比例。
private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)
{
int currentTotalFitness=0;
for (int i = 0; i < parents.Count; i++)
{
currentTotalFitness += parents[i].fitness;
Chromosome temp = parents[i];
temp.cumAvgFitness = currentTotalFitness / (double)total;
parents[i] = temp;
}
}
使用基于染色体适应度的轮盘赌来选择要配对的父代以生成新一代。此函数负责准备轮盘赌，它以染色体列表作为当前种群，以种群总适应度作为参数。该函数计算每个染色体适应度与总适应度的比例，然后计算其累积值，并将其分配给染色体的 cumAvgFitness 属性。
public void Crossover(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offspring = new List<Chromosome>();
for (int i = 0; i < parents.Count; i++)
{
if (Assay(probability)) //if the chance is to crossover
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);
List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5)) //select from parentX
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains
(parentX.genes[k]))//instead of
//deleting the similar genes
//from parents select the
//next non-contained number
{
child.Add(parentX.genes[k]);
break;
}
}
}
else //select from parentY
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains
(parentY.genes[k]))//instead of
//deleting the similar genes from
//parents select the next
//non-contained number
{
child.Add(parentY.genes[k]);
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
offspring.Add(offSpr);
}
else //else the chance is to clone
{
Chromosome parentX = AssayRuletteWheel(parents);
offspring.Add(parentX);
}
}
while (offspring.Count > parents.Count)
{
offspring.RemoveAt((int)GetRandomVal(0, offspring.Count - 1));
}
parents = offspring;
}
此函数负责交叉和克隆操作。该函数以染色体列表作为当前种群，以交叉概率作为参数。Assay(int probability) 函数以给定的概率返回 true，因此它与交叉概率一起用于确定操作是交叉还是克隆。
if (Assay(probability)) //if the chance is to crossover
{
Chromosome parentX = AssayRuletteWheel(parents);
Chromosome parentY = AssayRuletteWheel(parents);
List<int> child = new List<int>();
for (int j = 0; j < 8; j++)
{
if (Assay(0.5)) //select from parentX
{
for (int k = 0; k < parentX.genes.Length; k++)
{
if (!child.Contains(parentX.genes[k]))//instead of
//deleting the similar genes from parents
//select the next non-contained number
{
child.Add(parentX.genes[k]);
break;
}
}
}
else //select from parentY
{
for (int k = 0; k < parentY.genes.Length; k++)
{
if (!child.Contains(parentY.genes[k]))//instead of
//deleting the similar genes from parents
//select the next non-contained number
{
child.Add(parentY.genes[k]);
break;
}
}
}
}
Chromosome offSpr = new Chromosome();
offSpr.genes = child.ToArray();
offspring.Add(offSpr);
}
这部分代码来自上面的函数，负责交叉两个父代 parentX 和 parentY。为了创建子代，以 0.5 的概率从两个父代中选择基因，同时避免染色体中的基因重复。
在克隆操作中，一个父代直接被带到下一代。
public void Mutate(ref List<Chromosome> parents, double probability)
{
List<Chromosome> offsprings = new List<Chromosome>();
for (int i = 0; i < parents.Count; i++)
{
Chromosome offspring = parents[i];
for (int mutatePosition = 0; mutatePosition < 8; mutatePosition++)
{
if (Assay(probability)) //if the chance is to mutate
{
int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);
if (newGeneIndex>=mutatePosition)
{
newGeneIndex += 1;
}
int swapTemp = offspring.genes[mutatePosition];
offspring.genes[mutatePosition] =
offspring.genes[newGeneIndex];
offspring.genes[newGeneIndex] = swapTemp;
}
}
offsprings.Add(offspring);
}
parents = offsprings;
}
此函数以给定的概率应用变异算子。它在遍历当前种群的染色体基因时评估变异的机会。如果必须对基因应用变异，则其值与同一染色体中随机选择的一个基因（要变异的基因除外）进行交换。
当找到解决方案时，包含解决方案的染色体中的基因数组可以设置为 Board 类中名为 Genes 的属性。
如何使用
该程序允许您指定种群大小、代数、交叉概率和变异概率。可以使用开始按钮执行算法。如果种群大小和代数过大，请使用进度条指示当前代数。但这会显著减慢算法速度。
最后一代表的染色体都显示在表中，图形化的棋盘显示最佳结果。
源代码可供下载。