AI - 简单的遗传算法 (GA) 来解决扑克牌问题
4.74/5 (57投票s)
2006年11月8日
5分钟阅读
290209
3579
一个简单的遗传算法（GA），用于解决扑克牌问题。
引言
本文介绍了如何使用遗传算法解决一个逻辑问题。它假设读者对 GA 没有先验知识。事实上，本文有一半篇幅用于解释遗传算法的内部结构。
那么，我们试图解决的问题域是什么呢？
嗯，GA 可以用来解决许多问题。事实上，GA 已被用于生成新的数学语法树、训练多层神经网络，这仅仅是举了几个例子。
然而，在这个例子中，我使用了一个简单的扑克牌分割练习，详细说明如下：
- 你有 10 张扑克牌，编号从 1 到 10。
- 你必须将它们分成两堆，使得
- 第一堆的总和尽可能接近 36。
- 第二堆所有牌的乘积尽可能接近 360。
现在，我并不是说这不能通过人工，使用老式的脑力来完成，它只是更适合 GA，因为它可能需要数百甚至数千种不同的组合才能得到正确的结果。好吧，对于这个简单的问题，可能不需要那么多，但对于更难的问题，肯定需要大量的组合。总之，用 GA 来做很有趣。所以，我们继续吧。
那么，什么是遗传算法？
嗯，维基百科是这样说的：
遗传算法是一种在计算中使用的搜索技术，用于查找优化和搜索问题的真实或近似解决方案，通常缩写为 GA。遗传算法被归类为全局搜索启发式算法。遗传算法是进化算法的一个特定类别，它使用受进化生物学启发的技巧，如遗传、变异、选择和交叉（也称为重组）。
遗传算法被实现为一个计算机模拟，其中对优化问题的候选解决方案（称为个体、生物或表型）的抽象表示（称为染色体或基因型或基因组）的种群朝着更好的解决方案演化。传统上，解决方案以二进制形式表示为 0 和 1 的字符串，但其他编码也是可能的。进化通常从随机生成的个体种群开始，并按代进行。在每一代中，种群中每个个体的适应度都会被评估，多个个体根据其适应度从当前种群中进行随机选择，并进行修改（重组和可能变异）以形成一个新的种群。然后，新种群用于算法的下一次迭代。
明白了吗？如果没明白，我们来试试图表。（请注意，这是一个微生物 GA，有很多种 GA 类型，但我就是喜欢这种，而且这是本文使用的。）
我更愿意将 GA 视为一种非常快速（好吧，也许相当慢，取决于问题）尝试自然界一直拥有的进化编程技术的方法。
那么，这如何转化为一个算法（本文使用微生物 GA，但还有许多其他变体）？
微生物 GA 训练的基本操作如下：
- 随机选择两个基因型。
- 比较分数（适应度）以选出获胜者和失败者。
- 沿着基因型移动，在每个位点（点）。
即：
- 以一定的概率（随机性），从获胜者复制到失败者（覆盖）。
- 以一定的概率（随机性），变异失败者的该位点。
所以，只有失败者会被改变，这免费提供了一个精英主义的版本，确保了优良的品种会留在种群中。
就是这样。这就是完整的算法。
但是，在使用 GA 时，有一些**关键**问题需要注意。
- 对于不同的问题域，基因型**将会**不同。
- 对于不同的问题域，适应度函数**将会**不同。
当指定一个新问题时，这两个项目**必须**重新开发。
例如，如果我们想找出一个人最喜欢的披萨配料，那么基因型和适应度将与本文的问题域不同。
（对于本文的问题域）GA 的这两个关键要素在下面指定。
1. 基因型
//the genes array, 30 members, 10 cards each
private int[,] gene = new int[30, 10];
好吧，对于本文来说，问题域规定我们有 10 张扑克牌。因此，我创建了一个二维基因数组，这是一个 30*10 的数组。30 代表种群大小为 30。我选择了这个。它可以是任何大小，但应该足够大，以允许一些优势基因形成。
2. 适应度函数
请记住，问题域描述说明了以下内容：
- 你有 10 张扑克牌，编号从 1 到 10。
- 你必须将它们分成两堆，使得
- 第一堆的总和尽可能接近 36。
- 第二堆所有牌的乘积尽可能接近 360。
好吧，所有正在做的事情如下：
- 循环遍历种群成员的基因。
- 如果当前正在查看的基因值为 0，则该基因属于总和堆（堆 0），因此将其加到运行计算中。
- 如果当前正在查看的基因值为 1，则该基因属于乘积堆（堆 1），因此将其加到运行计算中。
- 计算该种群成员的总体误差。如果该成员的基因型总体误差为 0.0，则问题域已解决。
//evaluate the the nth member of the population
//@param n : the nth member of the population
//@return : the score for this member of the population.
//If score is 0.0, then we have a good GA which has solved
//the problem domain
private double evaluate(int n)
{
//initialise field values
int sum = 0, prod = 1;
double scaled_sum_error, scaled_prod_error, combined_error;
//loop though all genes for this population member
for (int i = 0; i < LEN; i++)
{
//if the gene value is 0, then put it in the sum (pile 0),
//and calculate sum
if (gene[n,i] == 0)
{
sum += (1 + i);
}
//if the gene value is 1, then put it in the product (pile 1),
//and calculate sum
else
{
prod *= (1 + i);
}
}
//work out how food this population member is, based on an overall error
//for the problem domain
//NOTE : The fitness function will change for every problem domain.
scaled_sum_error = (sum - SUMTARG) / SUMTARG;
scaled_prod_error = (prod - PRODTARG) / PRODTARG;
combined_error = Math.Abs(scaled_sum_error) + Math.Abs(scaled_prod_error);
return combined_error;
}
使用代码
附加的演示项目实际上包含一个 Visual Studio 2005 解决方案，其中包含以下两个类：
Program 类
是 Simple_GeneticAlgorithm 应用程序的主入口点。这个类所做的只是创建一个新的 Simple_GeneticAlgorithm 对象并调用其 run() 方法。
using System;
using System.Collections.Generic;
using System.Text;
namespace Simple_GeneticAlgorithm
{
class Program
{
//main access point
static void Main(string[] args)
{
//create a new Microbial GA
Simple_GeneticAlgorithm GA = new Simple_GeneticAlgorithm();
GA.run();
//read a line, to stop the Console window closing
Console.ReadLine();
}
}
}
Simple_GeneticAlgorithm 类
运行 GA 以解决问题域。
using System;
using System.Collections.Generic;
using System.Text;
namespace Simple_GeneticAlgorithm
{
public class Simple_GeneticAlgorithm
{
//population size
private int POP = 30;
//geneotype
private int LEN = 10;
//mutation rate, change it have a play
private double MUT = 0.1;
//recomination rate
private double REC = 0.5;
//how many tournaments should be played
private double END = 1000;
//the sum pile, end result for the SUM pile
//card1 + card2 + card3 + card4 + card5, MUST = 36 for a good GA
private double SUMTARG = 36;
//the product pile, end result for the PRODUCT pile
//card1 * card2 * card3 * card4 * card5, MUST = 360 for a good GA
private double PRODTARG = 360;
//the genes array, 30 members, 10 cards each
private int[,] gene = new int[30, 10];
//used to create randomness (Simulates selection process in nature)
//randomly selects genes
Random rnd = new Random();
//empty constructor
public Simple_GeneticAlgorithm()
{
}
//Runs the Microbial GA to solve the problem domain
//Where the problem domain is specified as follows
//
//You have 10 cards numbered 1 to 10.
//You have to divide them into 2 piles so that:
//
//The sum of the first pile is as close as possible to 36
//And the product of all in second pile is as close as poss to 360
public void run()
{
//declare pop member a,b, winner and loser
int a, b, Winner, Loser;
//initialise the population (randomly)
init_pop();
//start a tournament
for (int tournamentNo = 0; tournamentNo < END; tournamentNo++)
{
//pull 2 population members at random
a = (int)(POP * rnd.NextDouble());
b = (int)(POP * rnd.NextDouble());
//have a fight, see who has best genes
if (evaluate(a) < evaluate(b))
{
Winner = a;
Loser = b;
}
else
{
Winner = b;
Loser = a;
}
//Possibly do some gene jiggling, on all genes of loser
//again depends on randomness (simulating the
//natural selection
//process of evolutionary selection)
for (int i = 0; i < LEN; i++)
{
//maybe do some recombination
if (rnd.NextDouble() < REC)
gene[Loser, i] = gene[Winner, i];
//maybe do some muttion
if (rnd.NextDouble() < MUT)
gene[Loser, i] = 1 - gene[Loser, i];
//then test to see if the new population member
//is a winner
if (evaluate(Loser) == 0.0)
display(tournamentNo, Loser);
}
}
}
//Display the results. Only called for good GA which has solved
//the problem domain
//@param tournaments : the current tournament loop number
//@param n : the nth member of the population.
private void display(int tournaments, int n)
{
Console.WriteLine("\r\n==============================\r\n");
Console.WriteLine("After " + tournaments +
" tournaments, Solution sum pile " +
"(should be 36) cards are : ");
for (int i = 0; i < LEN; i++) {
if (gene[n,i] == 0) {
Console.WriteLine(i + 1);
}
}
Console.WriteLine("\r\nAnd Product pile " +
"(should be 360) cards are : ");
for (int i = 0; i < LEN; i++) {
if (gene[n,i] == 1) {
Console.WriteLine(i + 1);
}
}
}
//evaluate the the nth member of the population
//@param n : the nth member of the population
//@return : the score for this member of the population.
//If score is 0.0, then we have a good GA which has solved
//the problem domain
private double evaluate(int n)
{
//initialise field values
int sum = 0, prod = 1;
double scaled_sum_error, scaled_prod_error, combined_error;
//loop though all genes for this population member
for (int i = 0; i < LEN; i++)
{
//if the gene value is 0, then put it in
//the sum (pile 0), and calculate sum
if (gene[n,i] == 0)
{
sum += (1 + i);
}
//if the gene value is 1, then put it in
//the product (pile 1), and calculate sum
else
{
prod *= (1 + i);
}
}
//work out how food this population member is,
//based on an overall error
//for the problem domain
//NOTE : The fitness function will change
// for every problem domain.
scaled_sum_error = (sum - SUMTARG) / SUMTARG;
scaled_prod_error = (prod - PRODTARG) / PRODTARG;
combined_error = Math.Abs(scaled_sum_error) +
Math.Abs(scaled_prod_error);
return combined_error;
}
//initialise population
private void init_pop()
{
//for entire population
for (int i = 0; i < POP; i++)
{
//for all genes
for (int j = 0; j < LEN; j++)
{
//randomly create gene values
if (rnd.NextDouble() < 0.5)
{
gene[i,j] = 0;
}
else
{
gene[i,j] = 1;
}
}
}
}
}
}
结果
以找到的最后一个优秀种群成员结果为例，让我们进行测试。
2 + 7 + 8 + 9 + 10 = 36 in Pile 0, this is all good
1 * 3 * 4 * 5 * 6 = 360 in Pile 1, this is all good
关注点
我希望本文能展示如何编写一个简单的 GA 来解决一个我们人类可能觉得手动难以解决的问题。请记住，这是一个简单的问题。如果我们增加问题域的复杂性会怎样？GA 确实是最佳选择。
我很快将发表一篇关于 GA 训练多层神经网络来解决一些逻辑问题的文章。所以，如果你喜欢这类东西，请关注此空间。
历史
- v1.0 - 2006/11/08。