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

本文内容:遗传算法提供游戏软件 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课数据科学社区

一文读懂遗传算法工作原理(附Python实现)

几天前,我着手解决一个实际问题——大型超市销售问题。在使用了几个简单模型做了一些特征工程之后,我在排行榜上名列第 219 名。

2534
来自专栏数据和云

神马?SQL竟然可以解脑筋急转弯的题目?

我在很多公开演讲中都明目张胆的羡慕过一类人,他们把SQL当做艺术,把旁人眼中的枯燥演绎成经典,云和恩墨专家团队中的杨廷琨、罗海雄就都是这样的SQL专家。 今天,...

3204
来自专栏大数据挖掘DT机器学习

用GA算法设计22个地点之间最短旅程-R语言实现

某毕业班共有30位同学,来自22个地区,我们希望在假期来一次说走就走的旅行,将所有同学的家乡走一遍。算起来,路费是一笔很大的花销,所以希望设计一个旅行方案,确保...

3074
来自专栏AI科技大本营的专栏

计算机如何理解我们的语言?NLP is fun!

【导读】我们从日常每天都会用到的推荐系统到现在研究火热的开放性聊天、对话机器人,越来越多的产品与应用的背后都需要自然语言处理(NLP)和知识图谱的技术。也有越来...

883
来自专栏JackieZheng

Java豆瓣电影爬虫——使用Word2Vec分析电影短评数据

  在上篇实现了电影详情和短评数据的抓取。到目前为止,已经抓了2000多部电影电视以及20000多的短评数据。   数据本身没有规律和价值,需要通过分析提炼成知...

4448
来自专栏华章科技

大白话讲解遗传算法

种群(Population):生物的进化以群体的形式进行,这样的一个群体称为种群。

881
来自专栏Python中文社区

Python自然语言处理分析倚天屠龙记

最近在了解到,在机器学习中,自然语言处理是较大的一个分支。存在许多挑战。例如: 如何分词,识别实体关系,实体间关系,关系网络展示等。

1735
来自专栏数据派THU

自然语言处理数据集免费资源开放(附学习资料)

作者:Jason Brownlee 翻译:梁傅淇 本文长度为1500字,建议阅读3分钟 本文提供了七个不同分类的自然语言处理小型标准数据集的下载链接,对于有志于...

3746
来自专栏Data Analysis & Viz

乱炖“简书交友”数据之代码

上一篇文章乱炖数据之2700余篇“简书交友”专题文章数据的花式玩法发布后,不少人想学习下代码,由于此前不曾在GitHub上开源过,流程还不熟悉,再者本项目中很多...

701
来自专栏WOLFRAM

版本11.2——追求极致的极限

2004

扫码关注云+社区