图15 minesweeper工程的程序流程图
// 保存扫雷机的向量
vector<CMinesweeper> m_vecSweepers;
// 保存地雷的向量
vector<SVector2D> m_vecMines;
// 指向遗传算法对象的指针
CGenAIg* m_pGA;
int m_NumSweepers;
int m_NumMines;
// 神经网络中使用的权重值的总数
int m_NumWeightsInNN;
// 存放扫雷机形状各顶点的缓冲区
vector<SPoint> m_SweeperVB;
// 存放地雷形状各顶点的缓冲区
vector<SPoint> m_MineVB;
// 存放每一代的平均适应性分数，供绘图用
vector<double> m_vecAvFitness;
// 存放每一代的最高适应性分
vector<double> m_vecBestFitness;
// 我们使用的各种不同类型的画笔
HPEN m_RedPen;
HPEN m_BluePen;
HPEN m_GreenPen;
HPEN m_OldPen;
// 应用程序窗口的句柄
HWND m_hwndMain;
// 切换扫雷机程序运行的速度
bool m_bFastRender;
// 每一代的帧数（滴答数）
int m_iTicks;
// 代的计数
int m_iGenerations;
// 窗体客户区的大小
int cxClient，cyClient;
// 本函数在运行过程中画出具有平均-，和最优适应性值的图
void PlotStats(HDC surface);
public:
CController(HWND hwndMain);
~CController();
void Render(HDC surface);
void WorldTransform(vector<SPoint> &VBuffer,
SVector2D vPos);
bool Update();
// 几个公用的访问方法
bool FastRender() { return m_bFastRender; }
void FastRender(bool arg){ m_bFastRender = arg; }
void FastRenderToggle() { m_bFastRender = !m_bFastRender; }
};
当创建CController类的某个实例时，会有一系列的事情发生：
创建CMinesweeper对象。
统计神经网络中所使用的权重的总数，然后此数字即被利用来初始化遗传算法类的一个实例。
从遗传算法对象中随机提取染色体(权重)并(利用细心的脑外科手术)插入到扫雷机的经网络中。
创建了大量的地雷并被随机地散播到各地。
为绘图函数创建了所有需要用到的GDI画笔。
为扫雷机和地雷的形状创建了顶点缓冲区。
所有的一切现都已完成初始化，由此Update方法就能在每一帧中被调用来对扫雷机进行演化。
4.8.1 CController::Update Method（控制器的更新方法）
控制器更新方法CController::Update方法（或函数）在每一帧中都要被调用。当调用update函数时，函数
的前一半通过对所有扫雷机进行循环，如发现某一扫雷机找到了地雷，就update该扫雷机的适应性分数。由于m_vecThePopulation包含了所有基因组的拷贝，相关的适应性分数也要在这时进行调整。如果为完成一个代（generation）所需要的帧数均已通过，本方法就执行一个遗传算法的时代(epoch)来产生新一代的权重。这些
权重被用来代替扫雷机神经网络中原有的旧的权重，使扫雷机的每一个参数被重新设置，从而为进入新一generation做好准备。
bool CController::Update()
{
// 扫雷机运行总数为CParams::iNumTicks次的循环。在此循环周期中，扫雷机的神经网络
// 不断利用它周围特有的环境信息进行更新。而从神经网络得到的输出，使扫雷机实现所需的
// 动作。如果扫雷机遇见了一个地雷，则它的适应性将相应地被更新，且同样地更新了它对应
// 基因组的适应性。
if (m_iTicks++ < CParams::iNumTicks)
{
for (int i=O; i<m_NumSweepers; ++i)
{
//更新神经网络和位置
if (!m_vecSweepers[i].Update(m_vecMines))
{
//处理神经网络时出现了错误，显示错误后退出
MessageBox(m_hwndMain, 'Wrong amount of NN inputs!",
"Error", MB_OK);
return false;
}
// 检查这一扫雷机是否已经发现地雷
int GrabHit = m_vecSweepers[i].CheckForMine(m_vecMines，
CParams::dMineScale);
if (GrabHit >= 0)
{
// 扫雷机已找到了地雷，所以要增加它的适应性分数
m_vecSweepers[i].IncrementFitness();
// 去掉被扫雷机找到的地雷，用在随机位置放置的一个新地雷来代替
m_vecMines[GrabHit] = SVector2D(RandFloat() * cxClient，
RandFloat() * cyClient);
}
// 更新基因组的适应性值
m-vecThePopulation[i].dFitness = m_vecSweepers[i].Fitness();
}
}
// 一个代已被完成了。
// 进入运行遗传算法并用新的神经网络更新扫雷机的时期
else
{
// 更新用在我们状态窗口中状态
m_vecAvFitness.push_back(m_pGA->AverageFitness());
m_vecBestFitness.push_back(m_pGA->BestFitness());
// 增加代计数器的值
++m_iGenerations;
// 将帧计数器复位
m_iTicks = 0;
// 运行GA创建一个新的群体
m-vecThePopulation = m_pGA->Epoch(m_vecThePopulation);
// 在各扫雷机中从新插入新的（有希望）被改进的大脑
// 并将它们的位置进行复位，等
for(int i=O; i<m_NumSweepers; ++i)
{m_vecSweepers[i].m_ItsBrain.PutWeights(m_vecThePopulation[i].vecWeights);
m_vecSweepers[i].Reset();
}
}
returen true;
}
概括起来，程序为每一世代做的工作是:
l．为所有扫雷机和为iNumTicks个帧组织循环，调用Update函数
并根据情况增加扫雷机适应值的得分。
2．从扫雷机神经网络提取权重向量。
3．用遗传算法去演化出一个新的网络权重群体。
4．把新的权重插入到扫雷机神经网络。
5．转到第1步进行重复，直到获得理想性能时为止。
最后，表3列出了Smart Sweepers工程 v1.0版所有缺省参数的设置值。
表3 Smart Sweepers v1.0工程的缺省设置
神经网络
参 数 设 置 值
输入数目 4
输出数目 2
隐藏层数目 1
隐藏层神经元数目 10
激励响应 1
遗 传 算 法
参 数 设 置 值
群体大小 30
选择类型 旋转轮
杂交类型 单点
杂交率 0.7
突变率 0.1
精英设置（on/off） On
精英数目（N/copies） 4/1
总 体 特 性
参 数 设 置 值
每时代的帧数 2000
4.9 运行此程序 (Running the Program)
当你运行程序时，“F”键用来切换2种不同的显示状态，一种是显示扫雷机怎样学习寻找地雷，一种是
示在运行期中产生的最优的与平均的适当性分数的统计图表。 当显示图表时，程序将会加速运行。
游戏编程中的人工智能技术
.
<神经网络入门>
.
(连载之六)
4.10 功能的两个改进 (A Couple of Improvements)
尽管扫雷机学习寻找地雷的本领十分不错，这里我仍有两件事情要告诉你，它们能进一步改进扫雷机的性能。
4.10.1 改进一（Improvement Number One）
首先，单点crossover算子留下了许多可改进的余地。按照它的规定，算子是沿着基因组长度任意地方切开的，这样常有可能使个别神经细胞的基因组在权重的中间被一刀两段地分开。
为清楚起见，我们来考察图16的权重。这是我们以前在说明基因组如何编码时看过的一个简单网络。 在这
里，杂交算子可以沿向量长度的任意一处切开，这样，就会有极大几率在某个神经细胞（如第二个）的权重中
间断开，也就是说，在权重0.6和-0.1之间某处切开。这可能不会是我们想要的，因为，如果我们把神经细胞作
为一个完整的单元来看待，则它在此以前所获得的任何改良就要被骚扰了。事实上，这样的杂交操作有可能非
常非常象断裂性突变（disruptive mutation）操作所起的作用。
图16 简单的网络
与此针锋相对，我已创建了另一种类型的杂交运算，它只在神经细胞的边界上进行切开。在图16的例子中，
就是在第3、4或第6、7的两个基因之间切开，如小箭头所示。 为了实现这一算法，我已在CNeuralNet类中补
充了另一个切割方法: CalculateSplitPoints。这一方法创建了一个用于保存所有网络权重边界的矢量，它的代
码如下:
vector<int> CNeuralNet::CalculateSplitPoints() const
{
vector<int> SplitPoints;
int WeightCounter = 0;
// 对每一层
for (int i=O; i<m_NumHiddenLayers + 1; ++i)
{
// 对每一个神经细胞
for (int j=O; j<m_vecLayers[i].m_NumNeurons; ++j)
{
// 对每一个权重
for (int k=O; k<m_vecLayers[i].m_vecNeurons[j].m_NumInputs; ++k)
{
++WeightCounter;
}
SplitPoints.push_back(WeightCounter - 1);
}
}
return SplitPoints;
}
这一方法是CController类构造函数在创建扫雷机并把断裂点向量传递给遗传算法类时调用的。它们被存储
在一个名叫m_vecSplitPoints的std::vector向量中。然后遗传算法就利用这些断裂点来实现两点杂交操作，其代
码如下:
void CGenAlg::CrossoverAtSplits(const vector<double> &mum,
const vector<double> &dad,
vector<double> &babyl,
vector<double> &baby2)
{
// 如果超过了杂交率，就不再进行杂交，把2个上代作为2个子代输出
// 如果2个上辈相同，也把它们作为2个下辈输出
if ( (RandFloat() > m_dCrossoverRate) || (mum == dad))
{
baby1 = mum;
baby2 = dad;
return;
}
// 确定杂交的2个断裂点
int index1 = RandInt(0, m_vecSplitPoints.size()-2);
int index2 = RandInt(Index1, m_vecSplitPoints.size()-1);
int cp1 = m_vecSplitPoints[Index1];
int cp2 = m_vecSplitPoints[Index2];
// 创建子代
for (int i=0; i<mum.size(); ++i)
{
if ( (i<cp1) || (i>=cp2) )
{
// 如果在杂交点外，保持原来的基因
babyl.push_back(mum[i]);
baby2.push_back(dad[i]);
}
else
{
// 把中间段进行交换
baby1.push_back(dad[1]);
baby2.push_back(mum[1]);
}
}
return;
}
根据我的经验，我已发现，在进行杂交时，把神经细胞当作一个不可分割的单位，比在染色体长度上任意
一点分裂基因组，能得到更好的结果。
4.10.2 改进二（Improvement Number Two）
我想和你讨论的另一个性能改进，是用另一种方式来观察网络的那些输入。在你已看到的例子中，我们为
网络使用了4个输入参数: ２个用于表示扫雷机视线方向的向量,另外２个用来指示扫雷机与其最靠近的地雷的方
向的向量。然而，有一种办法，可以把这些参数的个数减少到只剩下一个。
其实你想一想就可知道，扫雷机为了确定地雷的位置，只要知道从它当前的位置和朝向出发，需要向左或
向右转动多大的一个角度这一简单的信息就够了(如果你已经考虑到了这一点，那我在这里要顺便向您道贺了)。
由于我们已经计算了扫雷机的视线向量和从它到最邻近地雷的向量，再来计算它们之间的角度(θ)应是一件极为
简单的事情 – 这就是这两个向量的点积，这我们在第6章“使登陆月球容易一点”中已讨论过。见图17。
图17 计算到最邻近地雷的转动角度。
不幸的是，点积仅仅给出角度的大小; 它不能指示这一角度是在扫雷机的那一侧。因此，我已写了另一个向
量函数返回一个向量相对于另一个向量的正负号。该函数的原型如下所示:
inline int Vec2DSign(SVector2D &v1,SVector2D &v2);
如果你对它的机理感兴趣，你可以在文件SVector2D.h中找到它的源码。但它的基本点就是: 如果v1至v2是
按顺时针方向转的，则函数返回 +1；如果v1至v2是按逆时针方向转，则函数返回 -1。
把点积和Vec2Dsign二者联合起来，就能把输入的精华提纯出来，使网络只需接受一个输入就行了。下面
就是新的CMinesweeper::Update函数有关段落的代码形式:
// 计算到最邻近地雷的向量
SVector2D vClosestMine = GetClosestMine(mines);
// 将它规范化
Vec2DNormalize(vClosestMine);
// 计算扫雷机视线向量和它到最邻近地雷的向量的点积。它给出了我们要面对
// 最邻近地雷所需转动的角度
double dot = Vec2DDot(m_vLookAt, vClosestMine);
// 计算正负号
int sign = Vec2DSign(m_vLookAt, vClosestMine);
Inputs.push_back(dot*sign);
运行一下光盘Chapter7/Smart Sweepers v1.1目录下的可执行程序executable，你就知道经过以上２个改
进，能为演化过程提速多少。
需要注意的一桩重要事情是，带有4个输入的网络要花很长时间进行演化，因为它必须在各输入数据之间找
出更多的关系才能确定它应如何行动。事实上，网络实际就是在学习怎么做点积并确定它的正负极性。因此，当
你设计自己的网络时，你应仔细权衡一下，是由你自己预先来计算许多输入数据好呢(它将使CPU负担增加，但
导致进化时间加快)还是让网络来找输入数据之间的复杂关系好(它将使演化时间变长，但能使CPU减少紧张)？
5 结束语（last words）
我希望你已享受到了你第一次攻入神经网络这一奇妙世界的快乐。我打赌你一定在为如此简单就能使用它
们而感到惊讶吧，对吗？我想我是猜对了。
在下面几章里我将要向你介绍更多的知识，告诉你一些新的训练手段和演绎神经网络结构的更多的方法。
但首先请你利用本章下面的提示去玩一下游戏是有意义的。
6 练习题 (Stuff to Try)
1。 在v1.0中，不用look-at向量作为输入，而改用旋转角度θ作为输入，由此就可以使网络的输入个数减少
成为1个。请问这对神经网络的演化有什么影响？你对此的看法怎样？
2。 试以扫雷机的位置（x1,y1）、和扫雷机最接近的地雷的位置（x2,y2）、以及扫雷机前进方向的向量
（x3,y3）等6个参数作为输入，来设计一个神经网络，使它仍然能够演化去寻找地雷。
3。 改变激励函数的响应。试用O.1 - O.3 之间的低端值，它将产生和阶跃函数非常相像的一种激励函数。
然后再试用高端值，它将给出较为平坦的响应曲线。考察这些改变对演化进程具有什么影响？
4。 改变神经网络的适应性函数，使得扫雷机不是去扫除地雷，而是要演化它，使它能避开地雷。
