亿万僵尸修改器专题之游戏中的数学与编程之一：亿万僵尸 （2）进化计算

接着，暴力搜索随着游戏时间的延长，计算量增加了一倍。15小时8小时后计算时间需要20多分钟。

再往上时间太长等不了，这在游戏中才五天，而游戏要求守住一百天，或一百五十天。成倍增长的话，别说是普通笔记本不行，换上超级计算机天河二号也是无济于事的，必须要找到时间消耗线性增长的算法。这似乎是不可能完成的任务，好在就有一种算法，它就好像无限非概率引擎一样，就是用来完成不可能的任务的，这就是进化计算。

进化计算是模拟生物进化的一种算法，先设计好DNA，本题中先是初始游戏状态，然后有若干动作可选，每种动作会导致新的状态，然后又可以采取新的动作，直到结束。假如要模拟100天的游戏进程，就是300个8小时。那么一种解决方案就是连续299个动作，我们就可以把这连续的299个动作当作一个DNA。

DNA有了，我们要生成一个种群，比如说1000个生物体。这个可以用随机的方式生成，在上文中某个状态下，我们先算出所有可能的动作组合，然后从中随机选一种，然后算出下一个状态，如此循环，就可以生成1000个随机的DNA。

这1000个DNA可以分别计算出最终状态，它们的弓手数肯定不同。按弓手数进行排序，选前300个进行繁殖。其余700个淘汰掉。300个中间随机选取2个进行交配，我们用最简单的办法，生成一个2到298之间的随机数，用这个随机数作为交叉点，两个父代A的前一段，和B的后一段组合成新的DNA。

然后进行突变，在新的DNA中按一定比率（百分之一以内），选几个DNA进行突变，突变的方法就是随机选DNA中的一个动作组合进行随机的修改。

然后检查，从开头起，到繁殖交叉点，和最靠前的突变点中，这两点选一个靠前的。此点之前的半段肯定是合格的不要查了，此点之后半段，要逐个计算中间状态，然后看所采取的动作是否是合理动作，合理的保留，不合理的重新随机选取一个。就按这种方式用这300个父代，繁殖出997个新的DNA，再选出300个父代中最好的3个组成1000个子代。

按照上面的方法，循环比如300代，然后从最后一代中选最好的作为本题结果。

我们分析一下上述的方法，首先这个方法不用计算所有的动作组合，它只需要从中随机的选取一种就行，所以不会有组合爆炸的情况。正因为如此，它才有可能算出299个动作序列后的状况。

其次这个DNA看起来很不靠谱，我们知道生物的DNA不可能是完全随机的，比如说两个人，DNA肯定不同，但是差别很小，可能只有百分之一。甚至人和香蕉的DNA差别也只有百分之四十多。

然后繁殖方式是单点交叉，随机突变，然后检查其中的后半段，不合理的要重新选择。这看起来也很不靠谱，因为要调整的似乎太多了。实际的生物繁殖不可能是这样的，比这个复杂得多，而且生成新的DNA后也不可能再去做那么大的调整。

所以说要很好的模拟生物进化，是很难的，毕竟生物进化本身还有很多谜团，具体到这个问题，如何设计DNA，如何设计繁殖方式，都有很大的讲究。不过我们没有必要一开始就要求太高，不要太纠结了，先用上述简单的设计。先看看效果再说。

下面是具体的程序，是vs 2017 免费社区版的c++ 代码 ，注意由于游戏简化太过了，导致金币等数字增加太快，所以用了long long这种数据类型，因为long最大只能表示20多亿的数，不够用，long long 可以表示几百亿亿的数，就足够了。的然后是运行的结果和一些分析：

//

#include ";

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <iomanip>

#include <random>

using namespace std;

using std::string;

using std::vector;

struct action {

string name;

int costGold;

int dGold;

int dHour;

int dTant;

int dBuildingBarrack;

int dArcher;

};

struct gameState {

int hour;

long long gold;

long long dGold;

long long tant;

long long barrack;

long long buildingBarrack;

long long archer;

long long fromActionArray[3];//三个元素分别代表bTant，bBarrack，bArcher三个动作的个数。

int fromStateIndex;

};

long long random_unint( long min, long long max)

{

std::random_device rd; //Will be used to obtain a seed for the random number engine

std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()

//cout << max << " ";

std::uniform_int_distribution<long long> dis(min, max);

return dis(gen);

}

//从某状态随机选出一个可能的动作，返回新的状态

gameState randomState(action pActionArray[3],gameState pWorkState) {

gameState workState = pWorkState;

//先找出每个动作最大次数

long long maxAction[3] = { 0,0,0 };

for (int i = 0; i < 3; i++) {

maxAction[i] = workS / pActionArray[i].costGold;

//archer可训练数还和军营数有关

if (i == 2) {

if (maxAction[i] > workS) {

maxAction[i] = workS;

}

}

}

long long sumCost = 0;

do {

//列出所有可能的动作组合，从中随机选取一个

sumCost = 0;

for (int j = 0; j < 3; j++) { //产生行动组合

workS[j] = random_unint(0, maxAction[j]);

sumCost += workS[j] * pActionArray[j].costGold;

}

} while (sumCost > workS);//花费够用就是个合理的动作组

workS += 8;

workS += 1;

return workState;

}

int main()

{

gameState iniState = { 0,100,200,0,0,0,0,{0,0,0},-1 };

action bTant = { "bTant",30,8,8,1,0,0 };

action bBarrack = { "bBarrack",450,-14,16,0,1,0 };

action bArcher = { "bArcher",120,-1,8,0,0,1 };

action actionArray[3] = { bTant,bBarrack,bArcher };

int gameTime = 0;

int workIndex = 0;

int max8hour = 12;//停止标记 17用时约10小时，16用时约2.5小时，15约30分钟

long long maxArcher = 0;

int maxStep = 16; //long long 类型才能满足算这么多步骤的要求

int generations = 100;

const int groupSize = 6000;

const int winSize = 300;

float variation = 0.1;//变异系数

vector<gameState> states[groupSize];

//生成初始随机种群

for(int g = 0;g<groupSize;g++){

states[g].push_back(iniState);

for (int s = 0; s < maxStep; s++) { //生成DNA

gameState workState = states[g][s];

//随机产生新的状态，然后加入states

gameState newState = randomState(actionArray,workState);//花费够用就是个合理的动作组合

long long sumCost = 0;

for (int j = 0; j < 3; j++) { //计算行动组合的花费

sumCost += newS[j] * actionArray[j].costGold;

}

//上一个状态采取本状态的动作组合后，经过8小时之后的各项数据

newS += newS – sumCost;

newS += newS[0] * 8 – newS * 14 – newS[2];

newS += newS[0];

newS += newS;

newS = newS[1];

newS += newS[2];

states[g].push_back(newState);

}

}

//选择较好的winSize个,进行繁殖，生成下一代种群，如此循环300代

for (int g = 0; g < generations; g++) {

//冒泡排序，选出最好的winSize个DNA

for (int i = 0; i < winSize; i++) {

for (int j = groupSize -1; j > i ; j–) {

if (states[j][maxStep-1].archer > states[j – 1][maxStep-1].archer) {

states[j – 1].swap(states[j]);

}

}

}

std::cout << "generation:" << g << " archer:" << states[0][maxStep – 1].archer << "n";//输出空行

//存到临时数组

vector<gameState> tmpStates[winSize];

for (int i = 0; i < winSize; i++) {

tmpStates[i].assign(states[i].begin(), states[i].end());

}

//从前winSize个中，随机选两个进行单点交叉繁殖

for (int i = 3; i < groupSize; i++) { //前3个最大的保留

int pf, pm, cp,vc,vp;

pf = random_unint(0, winSize -1);//父本

pm = random_unint(0, winSize -1);//母本

cp = random_unint(1, maxStep -1);//交叉点,交叉点本身属于后半段

//取前半段 复制区间是 [ begin , cp )

states[i].assign(tmpStates[pf].begin(), tmpStates[pf].begin() + cp);

//取后半段

states[i].insert(states[i].end(), tmpStates[pm].begin() + cp, tmpStates[pm].end());

//变异

vc = random_unint(0, 100000);//判断是否要变异

if (vc < variation * 100000) {

vp = random_unint(1, maxStep – 1);//变异点

states[i][vp] = randomState(actionArray, states[i][vp – 1]);//变异点重新随机一个动作组合

if (vc < cp) {

vc = cp;

}

}

//调整后半段

for (int j = cp; j < maxStep; j++) {

long long sumCost = 0;

for (int k = 0; k < 3; k++) { //计算行动组合的花费

sumCost += states[i][j].fromActionArray[k] * actionArray[k].costGold;

}

//判读动作是否合理

if (states[i][j – 1].gold < sumCost || states[i][j – 1].barrack < states[i][j].fromActionArray[2]) {

//不合理就重新随机选取一个动作

states[i][j] = randomState(actionArray, states[i][j – 1]);//花费够用就是个合理的动作组合

sumCost = 0;

for (int k = 0; k < 3; k++) { //计算行动组合的花费

sumCost += states[i][j].fromActionArray[k] * actionArray[k].costGold;

}

}

states[i][j].gold = states[i][j-1].gold + states[i][j-1].dGold – sumCost;

states[i][j].dGold = states[i][j-1].dGold + states[i][j].fromActionArray[0] * 8 –

states[i][j-1].buildingBarrack * 14 – states[i][j].fromActionArray[2];

states[i][j].tant = states[i][j-1].tant + states[i][j].fromActionArray[0];

states[i][j].barrack = states[i][j-1].barrack + states[i][j-1].buildingBarrack;

states[i][j].buildingBarrack = states[i][j].fromActionArray[1];

states[i][j].archer = states[i][j-1].archer + states[i][j].fromActionArray[2];

}

}

}

//冒泡排序，选出最好的winSize个DNA

for (int i = 0; i < groupSize; i++) {

for (int j = groupSize – 1; j > i; j–) {

if (states[j][maxStep – 1].archer > states[j – 1][maxStep – 1].archer) {

states[j – 1].swap(states[j]);

}

}

}

//输出最大的Archer的建造方案

vector<int> barrackCounts;

maxArcher = states[0][maxStep – 1].archer;

std::cout << maxArcher << "n";//输出空行

for (int i = maxStep – 1; i >= 0 && states[0][i].archer == maxArcher; i–) {

if (find(), barrackCoun(), states[0][i].barrack) == barrackCoun()) {

barrackCoun(states[0][i].barrack); //记录此barrackCount

int tmpIndex = i;

do {//输出此建造方案

std::cout << "时间:" << std::setw(5) << states[0][tmpIndex].hour

<< " 金币:" << std::setw(5) << states[0][tmpIndex].gold

<< " 收入:" << std::setw(5) << states[0][tmpIndex].dGold

<< " 营地:" << std::setw(5) << states[0][tmpIndex].tant

<< " 兵营:" << std::setw(5) << states[0][tmpIndex].barrack

<< " 弓手:" << std::setw(5) << states[0][tmpIndex].archer << "n";

tmpIndex = states[0][tmpIndex].fromStateIndex;

} while (tmpIndex != -1);

std::cout << "n";//输出空行

}

}

}

下面是地15个8小时的模拟结果，可以和上文的结果对看：

时间: 120 金币: 840 收入: 682 营地: 70 兵营: 4 弓手: 22

时间: 112 金币: 634 收入: 686 营地: 70 兵营: 4 弓手: 18

时间: 104 金币: 690 收入: 634 营地: 63 兵营: 4 弓手: 14

时间: 96 金币: 798 收入: 582 营地: 56 兵营: 4 弓手: 10

时间: 88 金币: 806 收入: 562 营地: 53 兵营: 4 弓手: 6

时间: 80 金币: 625 收入: 571 营地: 52 兵营: 3 弓手: 3

时间: 72 金币: 728 收入: 587 营地: 52 兵营: 2 弓手: 1

时间: 64 金币: 696 收入: 602 营地: 52 兵营: 1 弓手: 0

时间: 56 金币: 644 收入: 592 营地: 49 兵营: 0 弓手: 0

时间: 48 金币: 540 收入: 584 营地: 48 兵营: 0 弓手: 0

时间: 40 金币: 488 收入: 472 营地: 34 兵营: 0 弓手: 0

时间: 32 金币: 396 收入: 392 营地: 24 兵营: 0 弓手: 0

时间: 24 金币: 308 收入: 328 营地: 16 兵营: 0 弓手: 0

时间: 16 金币: 246 收入: 272 营地: 9 兵营: 0 弓手: 0

时间: 8 金币: 240 收入: 216 营地: 2 兵营: 0 弓手: 0

时间: 0 金币: 100 收入: 200 营地: 0 兵营: 0 弓手: 0

可见结果不是最优解，最优解是24，但是这个是次优解，再看17个8小时的结果：

时间: 136 金币: 1160 收入: 812 营地: 91 兵营: 6 弓手: 32

时间: 128 金币: 1100 收入: 810 营地: 90 兵营: 6 弓手: 26

时间: 120 金币: 1042 收入: 808 营地: 89 兵营: 6 弓手: 20

时间: 112 金币: 1100 收入: 782 营地: 85 兵营: 6 弓手: 14

时间: 104 金币: 1051 收入: 769 营地: 81 兵营: 5 弓手: 9

时间: 96 金币: 1194 收入: 787 营地: 81 兵营: 4 弓手: 5

时间: 88 金币: 1219 收入: 785 营地: 77 兵营: 2 弓手: 3

时间: 80 金币: 1572 收入: 787 营地: 77 兵营: 2 弓手: 1

时间: 72 金币: 890 收入: 802 营地: 77 兵营: 1 弓手: 0

时间: 64 金币: 752 收入: 768 营地: 71 兵营: 0 弓手: 0

时间: 56 金币: 586 收入: 736 营地: 67 兵营: 0 弓手: 0

时间: 48 金币: 572 收入: 584 营地: 48 兵营: 0 弓手: 0

时间: 40 金币: 406 收入: 496 营地: 37 兵营: 0 弓手: 0

时间: 32 金币: 366 收入: 400 营地: 25 兵营: 0 弓手: 0

时间: 24 金币: 384 收入: 312 营地: 14 兵营: 0 弓手: 0

时间: 16 金币: 224 收入: 280 营地: 10 兵营: 0 弓手: 0

时间: 8 金币: 210 收入: 224 营地: 3 兵营: 0 弓手: 0

时间: 0 金币: 100 收入: 200 营地: 0 兵营: 0 弓手: 0

结果是32这也是次优解，最优的是36。

就是说进化计算在这个问题上，它找不到最优解，但是可以在可接受的时间内，找到一个次优解，或者说可接受解。

我们再看看299个步骤后的结果，这个运行时间稍稍长一点，但是还可以接受。这用暴力搜索是不可能完成的，哪怕是用天河二号也不行。

代数:00 弓手:691325020424

代数:10 弓手:963879362614

代数:20 弓手:1140890241449

代数:30 弓手:1232597316982

代数:40 弓手:1407188453159

代数:50 弓手:36

代数:60 弓手:1681485217236

代数:70 弓手:1774207796044

代数:80 弓手:53

代数:90 弓手:1943306063715

代数:99 弓手:2018465076009

时间: 2392 金币:33790087518572 收入:29571744988423 营地:4323190539722 兵营:2 弓手:2021840385545

可以看到随着种群代数增加，弓手数不断增长，就是说结果在不断的优化，最后结果2018465076009是个很大的数，这不是算法的问题，这是游戏简化掉了很多制约条件造成的。

我们已经验证了进化计算可以行得通，下一篇文章就要用这个方法，来最终解决原来的问题，而不是现在这个过度简化后的。