学而不思则罔，思而不学则贻。 学习遗传算法这样貌似很神奇的东西，最困难的一点就是把理论知识转化为实际的程序，把头脑里的东西，弄成一个个实际的代码。这个距离有时候尽在咫尺，却挡住了很多人。至少我就被挡住了很多次。（说实话，知道遗传算法的概念已经很久了，但这么多年也没有真正动手过；就算是两天前，都想放弃过，给自己一个借口：反正我已经对遗传算法了解的很多了，理论也基本掌握了，这就差不多了，等以后真正需要再说吧）。我认为这里面有一个界限，那就是你真正去实现一个程序，哪怕这个程序是很简单的，甚至是很简陋的；但如果你完整的实现了，注意，是完整的实现。这或许就是一个质上的变化，至少表示你有能力把有一个概念转化为一个实际的项目。那么概念在头脑里萦绕的时候，你同时也知道如果用代码去实现，哪怕此时的代码是丑陋的，漏洞百出。我想说的是，写一个糟糕的程序，比灌一脑子完美的概念要好的多。
还有一些朋友问学习这些有什么用？这个问题，我只能揣测地把自己体会说一下。首先，我觉得学习这些是对自己思维的一个很好的锻炼，扩展自己的思路。这在平常所做的代码工作中，很难有所突破。因为平时在项目的系统压力下，或者有时候是我们思维定势的影响，总是跳不出来某个圈子。而在一个完全陌生的东西前，一片漆黑地开始编程，或许会发现“原来还可以这样”。其次，遗传算法有很多的实际应用，公交调度，电力网规划等等，都是很重要的应用。
最后说一下我自己的想法，工作中总是发现，但系统的规模增长到一定程度，随着逻辑越来越复杂，对项目的掌控越来越差，按下F5之前，总是要祈祷一下，担心莫名其妙的Bug张牙舞爪地跑出来。说实话，这个感觉很糟糕。我一直希望能够有一个良好的架构，一个解耦的架构，既可以良好地协作工作，也可以让我能集中精力到具体的细节单元，同时希望它们可以并行工作，在当前的多核越来越流行的情况下，能让自己的游戏以优秀的性能脱颖而出。我觉得遗传算法，神经网络，有限元这些有着化繁为简的特性，把一个复杂的系统问题，归结到了一个个单元（基因）这样的东西如果能够运用到游戏架构上来，会给开发者带来很大的好处，另外归结成一个个没有交叉的单元后，使用并行编程是很自然的事情，这就能使SilverlightGame的性能成倍地提高，这是很让人期待的。
目前所做的东西都给予Silverlight来实现，虽然有时候是拿Silverlight但控制台来用的；但用SL可以让我以后扩展的时候更方便一些。
———————————— 自勉以及勉励很多和我一样的程序员朋友
最开始选择了一个寻路的例子想实现，或许那个例子也不难，但尝试了一下，发现有些问题，因为做一个小人在迷宫中行走，至少要涉及到动画，地图敷设，甚至要做一个地图编辑器，碰撞...;这些东西和遗传算法并不是关系很大，但这些东西会牵扯很多的精力，让你很难集中精力注意在你的遗传算法上，我觉得这不是一个好主意，也建议大家在初涉新的知识时候，而且你对它把握不是很大，那么弄一个简单的，目的明确的系统，还是很明智的做法。
我又开始尝试 对函数在区间 [a,b] 内的最大值的遗传算法求解。遗传算法是对问题参数的编码进行操作，而函数本身的参数正好是最好的编码对象。
观察图形，会发现它是存在最优解和局部最优解的。（这个函数看上去很复杂，不过没有关系，它恰恰代表了，我们处理的很多问题可能更复杂，做一个不规则的物理碰撞，一个业务复杂的进销存规则，都可能比这个更复杂，但使用遗传算法恰恰是避免这种探究内部复杂机制，而采取的是探索的方法，这更具有通用性）
我选择了一个更简单的函数 f(x) = x * x 来作为目标。对其在 00000 ～ 11111的区间内求最大值，适应度用来衡量个体对生存环境的适应程度。但适应度的选择是个不容易弄好的问题，有时候是要对适应度函数进行适当变换（可以进行线性变换或者指数变换，幂函数变换等等）。我这里简单的用函数值作为适应度函数，利用适应度函数取得被选择概率，然后应用选择方法，遗传算法中的选择方法很多，轮盘赌是一个常用的选择方法。
在上面一篇文章也提到过轮盘赌选择法。
具体的数据可以是这样的。
童鞋们当然可以用这个思路来做赌轮算法，不过我使用了另外一种利用数组指针来模拟。长话短说吧，以下是全部的代码，说实话，把这样的东西放出来是要做好心理准备的，做好被拍倒的准备。因为这些东西确实很陌生，但请大家念我一腔的开源精神，共同学习。
代码
using System;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;
using System.Threading;
//----------------------------------------------------------------------//
// 在一个区间内用遗传算法寻找某函数的最大值的练习，疏漏多多
// 初学遗传算法，很痛苦，希望朋友们多交流切磋
// 学习代码，随意张贴复制，敬请保留原签名
// http://home.cnblogs.com/GameCode/
// 2010.7.9 Copy By 向恺然 （博客园）
//----------------------------------------------------------------------//
namespace MaxValue
{
public class HandleGene
{
public Chromosome[] chromosomes; //种群
public customFun myFun; //函数
public int maxInt, minInt; //函数取值范围 【00000 ～ 11111】
public int mm;
public List<Chromosome> newChromo; //产生新种群的临时存放地点
//_size 种群初始大小,这个值也很重要，太小不容易产生好的结果，太大计算代价高
//有种说法是种群大小是染色体长度的2～3倍
public HandleGene(int _size,int _max,int _min)
{
chromosomes = new Chromosome[_size];
maxInt = _max;
minInt = _min;
myFun = MyFunction.SquareBinary;
newChromo = new List<Chromosome>();
InitGenomes();
}
public void Epoch()
{
//Match方法每次繁殖出来两个新染色体，所以进行种群数量一半的循环，就产生和种群数量一样的新种群
for (int i = 0; i < chromosomes.Length / 2; i++)
{
Match();
}
int index = 0;
foreach (Chromosome item in newChromo)
{
chromosomes[index] = item;
index++;
}
newChromo.Clear();
UpdateGenome();
}
public void show()
{
foreach (Chromosome item in chromosomes)
{
Debug.WriteLine("{0}:{1}:{2}", item.genesSt, item.genesInt, item.fitness);
}
}
public void InitGenomes()
{
Chromosome chromosom;
for (int i = 0; i < chromosomes.Length; i++)
{
chromosom = new Chromosome();
//给一个不同的种子，可以得到不同的结果，更具有一般性
chromosom.genesSt = GetGeneSt(i-10212);
chromosom.fitness = myFun((double)Convert.ToInt32(chromosom.genesSt, 2));
chromosom.genesInt = Convert.ToInt32(chromosom.genesSt,2);
chromosomes[i] = chromosom;
}
}
//这是最重要的一个方法，用赌轮选择找出概率最大的两个染色体，同时进行杂交或者变异
public void Match()
{
int[] pa = new int[1000];
int max = 0;
int continueInt = 0;
for (int j = 0; j < chromosomes.Length; j++)
{
int p = GetProbability(chromosomes[j].fitness);
chromosomes[j].probability = (double)p / 100.0;
if (p > max)
{
pa[999] = j;
max = p;
}
for (int i = continueInt; i < p + continueInt; i++)
{
pa[i] = j;
}
continueInt += p;
}
Random ran = new Random(Chromosome.Seed);
int point = ran.Next(0,1000);
Debug.WriteLine("{0}--{1}---{2}", Thread.CurrentThread.ManagedThreadId, point,Chromosome.Seed);
Chromosome parent1 = chromosomes[pa[point]];
point = ran.Next(0, 1000);
Debug.WriteLine("{0}--{1}---{2}",Thread.CurrentThread.ManagedThreadId,point,Chromosome.Seed);
Chromosome.Seed++;
Chromosome parent2 = chromosomes[pa[point]];
if (ran.NextDouble() < Chromosome.CrossoverRate)
{
string[] at = Crossover(parent1.genesSt, parent2.genesSt);
parent1.genesSt = at[0];
parent2.genesSt = at[1];
}
newChromo.Add(parent1);
newChromo.Add(parent2);
}
public void UpdateGenome()
{
foreach (Chromosome item in chromosomes)
{
item.genesInt = Convert.ToInt32(item.genesSt, 2);
item.fitness = myFun(item.genesInt);
}
}
//杂交
public string[] Crossover(string _a,string _b)
{
Random ran = new Random();
int pos = ran.Next(0, Convert.ToString(maxInt, 2).Length);
string sub1A = _a.Substring(0, pos);
string sub2A = _a.Substring(pos, _a.Length - pos);
string sub1B = _b.Substring(0, pos);
string sub2B = _b.Substring(pos, _b.Length - pos);
string newA = sub1A + sub2B;
string newB = sub1B + sub2A;
double t = ran.NextDouble();
if (t < Chromosome.MutationRate)
{
Mutation(ref newA);
Mutation(ref newB);
}
return new string[] {newA,newB };
}
//变异
public void Mutation(ref string _gene)
{
Random ran = new Random();
int pos = ran.Next(0, _gene.Length);
string st = _gene.Substring(pos,1);
string st2 = "";
if (st == "0")
{
st = _gene.Remove(pos,1);
st = st.Insert(pos, "1");
}
else
{
st = _gene.Remove(pos,1);
st = st.Insert(pos, "0");
}
}
public string GetGeneSt(int _randSeed)
{
StringBuilder stb = new StringBuilder();
int len = Convert.ToString(maxInt, 2).Length;
Random ran = new Random(_randSeed);
for (int i = 0; i < len; i++)
{
int gene = ran.Next(0, 2);
stb.Append(gene.ToString());
}
return stb.ToString();
}
public int GetProbability(double _fitness)
{
double sum = 0;
foreach (Chromosome item in chromosomes)
{
sum += item.fitness;
}
int a = (int)((_fitness / sum)*1000);
return a;
}
}
public class Chromosome
{
public string genesSt;
public int genesInt;
public double fitness;
public double probability;//被选中的概率
public static int Seed;
//大家可以尝试着改变数值看会有什么结果。
//变异率
public static double MutationRate = 0.01;
//杂交率
public static double CrossoverRate = 0.7;
}
public class MyFunction
{
//函数，这里选择了一个简单的平方函数，其实你选择其他函数也是一样的
//遗传算法的好处也恰恰在这里，不需要十分精确地探寻问题的复杂内部机制
public static double SquareBinary(double _x)
{
return _x * _x;
}
}
public delegate double customFun(double _x);
}
代码
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;
using System.Diagnostics;
using System.Threading;
namespace MaxValue
{
public partial class MainPage : UserControl
{
public MainPage()
{
InitializeComponent();
HandleGene handle = new HandleGene(10, 31, 0);
handle.show();
for (int i = 0; i < 50; i++)
{
Debug.WriteLine("----{0}------",i);
handle.Epoch();
handle.show();
}
}
}
}