游戏开发中的人工智能:遗传算法

本文内容:遗传算法提供游戏软件 AI 演化的可能。虽然遗传算法不是经常被应用于游戏中,但是它们在某些特定应用方面的潜力是值得令人期待的,尤其是结合其他方法使用的时候。

遗传算法

在真实世界中,物种会不断进化,使其能更好的适应环境,这些物种也是最适宜继续存活下去的生物。

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

通过使用遗传算法,如同真实世界那样,游戏世界中的元素也可以演化,并适应不同的环境,更加智能。

演化过程

游戏中遗传算法的实现分成四个步骤,如图 15-3 所示。

1.建立第一代:整个族群会载入一组起始特征

2.适合度分等:该族群开始和环境互动后,必须以某种方式对个体做等级分类,这将告诉我们族群中的哪些个体最为优良

3.选择:选出族群中的某些个体繁衍后代,用上一代最为优良的特征繁殖下一代

4.演化:结合这些特征繁衍出适应力更强的下一代的过程

遗传算法实际上是一种最佳化过程,我们试着找出适应力最强的一组特征,即我们要找特定问题的最佳解决方案。

第一代

第一代族群中的每个个体,都代表当下问题的可能解决方案之一。建立第一代的方法之一,是随机配置染色体。

编码是把染色体存储在计算机中某数据结构中的过程。遗传算法常用的是字符串、数组、列表以及树结构。

图15-4 是花朵的第一代实例,这些假象的花,含有一些随机染色体,从而影响其在环境中的生长。

适合度分等 这一步是评估族群中的每一个个体。我们试着找出族群中最优良的个体,通常我们用适合度函数完成这项工作。适合度函数的目的是替族群中的个体分等,继而得知,哪些个体是解决当下问题的最佳答案。

图15-5 是花朵进行适合度分等的结果。在此,假设长的最高的,就是最能适应的花朵。

选择

在选择过程中,我们选择适合度最高的哪些个体繁殖下一代。在生物世界中,通常是父母双亲贡献染色体给后代。在游戏开发中,双亲如何组合都可以。例如,可以组合最优等个体的前两个、五个或十个个体的特征。

图15-6 是利用适合度函数算出的分等情况,选择最优的个体产生下一代,就此例而言,就是选出两朵长得最高的花。

演化

演化是利用选择步骤,建立新个体的过程。我们取出族群中适合度最佳的个体的个别染色体,然后开始组合它们的染色体。此时,也要注意引入随机突变(真实世界中也会有染色体突变)。一旦演化过程完成后,就再回到适合度分等的步骤中。

就此例而言,我们组合了两朵最高的花朵的染色体,用来建立新花朵,在此过程中也引入了两个随机突变,如图15-7 所示。

植物生命的演化

第一个实例是,如何应用遗传算法让花朵不断地繁衍后代,在其环境中生长下去。

我们定义了一系列假设的环境条件,让花朵在其中生长。每朵花都包含基因信息,表示出其理想的生长环境。花朵的理想生长环境和实际条件最接近的,就会长的最高。

最高的花朵会被视为适合度最好,其基因信息就会传递给下一代。这会让花朵繁衍后代时,在高度上不断地有所增长。

替花朵数据编码

我们定义了六个假设的环境,视为花朵生长环境的实际条件,如例15-1 所示。

//例15-1:编码

class ai_World

{

public:

int currentTemperature; //目前温度

int currentWater; //目前水质

int currentSunlight; //目前阳光

int currentNutrient; //目前养分

int currentBeneficialInsect;//目前益虫

int currentHarmfulInsect; //目前害虫

ai_World();

~ai_World();

};

编码是把染色体存储在计算机结构中的过程。例15-2 是我们在花朵演化实例中的结构。

//例15-2:环境条件

#define kMaxFlowers 11

class ai_World

{

public:

int temperature[kMaxFlowers];

int water[kMaxFlowers];

int sunlight[kMaxFlowers];

int nutrient[kMaxFlowers];

int beneficialInsect[kMaxFlowers];

int harmfulInsect[kMaxFlowers];

int currentTemperature;

int currentWater;

int currentSunlight;

int currentNutrient;

int currentBeneficialInsect;

int currentHarmfulInsect;

ai_World();

~ai_World();

};

如例15-2 所示,我们用六个数组表示六种环境条件,包括 currentTemperature,currentWater,currentSunlight,currentNutrient,currentBeneficialInsect,currentHarmfulInsect。每种环境条件都含有一个染色体,指出每朵花的理想情况。

第一代花朵

如同所有遗传算法一样,首先必须建立第一代。如果把遗传过程,当做搜寻问题的最佳解决方案,第一代就是猜测的解法集。例15-3 是建立第一代的代码。

//例15-3:第一代花朵

void ai_World::Encode(void)

{

int i;

for (i=1;i

{

temperature[i]=tb_Rnd(1,75);

water[i]=tb_Rnd(1,75);

sunlight[i]=tb_Rnd(1,75);

nutrient[i]=tb_Rnd(1,75);

beneficialInsect[i]=tb_Rnd(1,75);

harmfulInsect[i]=tb_Rnd(1,75);

}

currentTemperature=tb_Rnd(1,75);

currentWater=tb_Rnd(1,75);

currentSunlight=tb_Rnd(1,75);

currentNutrient=tb_Rnd(1,75);

currentBeneficialInsect=tb_Rnd(1,75);

currentHarmfulInsect=tb_Rnd(1,75);

}

如例15-3 所示,一开始是随机替花朵的染色体进行编码。我们以六个数组表示花朵族群中,每个成员的理想生长条件。这些数组有 temperature,water,sunlight,nutrient,beneficialInsect,harmfulInsect。每个数组的值介于 1~75 之间。

当实际条件最接近编写在花朵染色体内理想的生长条件时,花朵长的最好。我们用 for 循环设定每个数组中的随机值。这样可以确保花朵族群足够多样化。一旦 for 循环执行完成后,就给当前条件赋值,包括 currentTemperature,currentWater,currentSunlight,currentNutrient,currentBeneficialInsect,currentHarmfulInsect。

花朵适合度分等

就此基因仿真程序的目的而言,假设适合度最高的花朵,就是在当前环境条件下最茁壮的花朵。花朵里的染色体资料,编入了各自理想的生长条件。本质上,要估算每朵花的理想条件,和实际条件有多接近。哪些条件最接近的花,长的最高。

花朵适合度函数如例15-4 所示。

//例15-4:花朵适合度函数

int ai_World::Fitness(int flower)

{

int theFitness;

theFitness=fabs(temperature[flower]-currentTemperature);

theFitness=theFitness+fabs(water[flower]-currentWater);

theFitness=theFitness+fabs(sunlight[flower]-currentSunlight);

theFitness=theFitness+fabs(nutrient[flower]-currentNutrient);

theFitness=theFitness+fabs(beneficialInsect[flower]-currentBeneficialInsect);

theFitness=theFitness+fabs(harmfulInsect[flower]-currentHarmfulInsect);

return (theFitness);

}

我们用 Fitness( ) 函数计算当前环境条件与每朵花要茁壮生长的理想条件之间的总偏差量。一开始,把 theFitness 设为0。然后,将每朵花的理想条件和当前条件之间的差值的绝对值加上去。最后得到的 theFitness,即所有生长条件的总偏差量了。

花朵演化

花朵演化,除了让适合度最佳的花朵的染色体交叉外,还引入了随机突变。例15-5 的 Evolve( ) 函数有交叉和随机突变两个步骤。

//例15-5:花朵演化

void ai_World::Evolve(void)

{

int fitTemperature[kMaxFlowers];

int fitWater[kMaxFlowers];

int fitSunlight[kMaxFlowers];

int fitNutrient[kMaxFlowers];

int fitBeneficialInsect[kMaxFlowers];

int fitHarmfulInsect[kMaxFlowers];

int i;

int leastFit=0;

int leastFitIndex;

for (i=1;i

if (Fitness(i) >leastFit)

{

leastFit=Fitness(i);

leastFitIndex=i;

}

temperature[leastFitIndex]=temperature[tb_Rnd(1,10)];

water[leastFitIndex]=water[tb_Rnd(1,10)];

sunlight[leastFitIndex]=sunlight[tb_Rnd(1,10)];

nutrient[leastFitIndex]=nutrient[tb_Rnd(1,10)];

beneficialInsect[leastFitIndex]=beneficialInsect[tb_Rnd(1,10)];

harmfulInsect[leastFitIndex]=harmfulInsect[tb_Rnd(1,10)];

for (i=1;i

{

fitTemperature[i]=temperature[tb_Rnd(1,10)];

fitWater[i]=water[tb_Rnd(1,10)];

fitSunlight[i]=sunlight[tb_Rnd(1,10)];

fitNutrient[i]=nutrient[tb_Rnd(1,10)];

fitBeneficialInsect[i]=beneficialInsect[tb_Rnd(1,10)];

fitHarmfulInsect[i]=harmfulInsect[tb_Rnd(1,10)];

}

for (i=1;i

{

temperature[i]=fitTemperature[i];

water[i]=fitWater[i];

sunlight[i]=fitSunlight[i];

nutrient[i]=fitNutrient[i];

beneficialInsect[i]=fitBeneficialInsect[i];

harmfulInsect[i]=fitHarmfulInsect[i];

}

for (i=1;i

{

if (tb_Rnd(1,100)==1)

temperature[i]=tb_Rnd(1,75);

if (tb_Rnd(1,100)==1)

water[i]=tb_Rnd(1,75);

if (tb_Rnd(1,100)==1)

sunlight[i]=tb_Rnd(1,75);

if (tb_Rnd(1,100)==1)

nutrient[i]=tb_Rnd(1,75);

if (tb_Rnd(1,100)==1)

beneficialInsect[i]=tb_Rnd(1,75);

if (tb_Rnd(1,100)==1)

harmfulInsect[i]=tb_Rnd(1,75);

}

}

游戏开发人员不必受生物世界的局限性的制约。在生物世界中,交叉牵涉到双亲的染色体。在游戏开发中,交叉可以牵涉任何数目的花朵。就此花朵演化实例而言,要找出族群中最少最高适应度的成员。第一个 for 循环调用 Fitness( ) 函数,以找出族群中最少最高是印度的成员。然后,把最少适应度花朵的特征,重新赋给族群中随机成员的特征。接下来两个 for 循环,随机混合族群的特征。本质上,已重新赋给最高适应度花朵的特征,所以此时,花群整体应该比上一代要进步。但是,因为传递的还是相同的特征,所以需要随机突变的方式来超越前代。在最后一个 for 循环中,每朵花的每个特征有 1% 的随机突变机会。如果突变成功,则其特征有可能传给下一代。

转自: Jurbo的博客

权威发布有关Imagination公司CPU,GPU以及连接IP、无线IP最新资讯,提供有关物联网、可穿戴、通信、汽车电子、医疗电子等应用信息,每日更新大量信息,让你紧跟技术发展,欢迎关注!伸出小手按一下二维码我们就是好朋友!

本文来自企鹅号 - Imagination Tech媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

如何向小白介绍何谓机器学习和数据挖掘?买回芒果他就懂了

  买芒果   嘴馋的你想吃芒果了,于是你走到水果摊,挑了几个让老板过过秤,然后你再根据芒果的斤两付钱走人。   显然,买芒果你当然是挑着最甜、最熟的来买(因为...

3367
来自专栏吉浦迅科技

【手撕深度学习算法】(3月23日群讨论笔记)关于Sigmoid和活化函数

1手撕深度学习算法答疑微信群建立了! 为了更好地服务于关注于我们手撕深度学习算法讲座的学员,我们成立专门的答疑微信群。4月8日后,我们将再继续释放LSTM后半部...

5117
来自专栏专知

【论文推荐】最新十篇目标跟踪相关论文—多帧光流跟踪、动态图学习、MV-YOLO、姿态估计、深度核相关滤波、Benchmark

4668
来自专栏大数据文摘

神作:深入浅出傅里叶变换

1444
来自专栏量子位

三位一体的纯正视频换脸术,拒绝别人的嘴替我说话 | SIGGRAPH 2018

各位说不定还记得,之前有个导演,模仿奥巴马的声音吐槽了川普,还把自己的嘴完好地贴到了奥巴马脸上。

992
来自专栏陈树义

数学归纳法

  传统上,根据前提所考察对象范围的不同,把归纳推理分为完全归纳推理和不完全归纳推理。完全归纳推理考察了某类事物的全部对象,不完全归纳推理则仅仅考察了某类事物的...

3469
来自专栏媒矿工厂

HDR关键技术:HEVC/H.265编码优化

与传统标准动态范围(SDR)视频相比,高动态范围(HDR)视频由于比特深度的增加提供了更加丰富的亮区细节和暗区细节。最新的显示技术通过清晰地再现HDR视频内容使...

1680
来自专栏Y大宽

TBtools基因家族分析详细教程(1)

一共分为4个部分 TBtools基因家族分析详细教程(1) TBtools基因家族分析详细教程(2)基因家族成员的基本分析 TBtools基因家族分析详细...

6752
来自专栏机器学习和数学

[有意思的数学] 傅里叶变换和卷积与图像滤波的关系(1)

开始之前,说个事情,这个公众号的发文的频率是不确定的哈,有时候我可能不方便,或者比较忙的时候,就不更新了,这几天刚开始,我写着写着还有点上瘾,哈哈,所以每天都会...

35311
来自专栏Python中文社区

Kaggle搭积木式刷分大法:特征工程部分

專 欄 ❈本文作者:王勇,目前感兴趣项目商业分析、Python、机器学习、Kaggle。17年项目管理,通信业干了11年项目经理管合同交付,制造业干了6年项目...

4799

扫码关注云+社区