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

本文内容:遗传算法提供游戏软件 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 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Python科学计算之Pandas

在我看来,对于Numpy以及Matplotlib,Pandas可以帮助创建一个非常牢固的用于数据挖掘与分析的基础。而Scipy(会在接下来的帖子中提及)当然是另...

700
来自专栏nimomeng的自我进阶

探索命名之美(一)

很多新码农在工作中总会被老鸟批评程序命名的陋习,我也被批评过很多次。痛定思过,我决定要研究应该怎么命名,为什么要给函数一个好的命名很难,应该怎么样给函数命名。

693
来自专栏数据结构与算法

13:人民币支付

13:人民币支付 总时间限制: 1000ms 内存限制: 65536kB描述 从键盘输入一指定金额(以元为单位,如345),然后输出支付该金额的各种面额的人...

4005
来自专栏微信公众号:Java团长

写好Java代码的30条经验总结

成为一个优秀的Java程序员,有着良好的代码编写习惯是必不可少的。下面就让我们来看看代码编写的30条建议吧。

652
来自专栏韩伟的专栏

面向对象的代码风格(上)

大家过年好呀!公众号从今天开始恢复更新,感谢大家不离不弃的关注。 今天的文末有投票,以助于我在新的一年里将公众号做得更好,踊跃参加一下吧! 本篇文章分两章发送,...

3598
来自专栏怀英的自我修炼

Java漫谈5

吴军老师有在他的《硅谷来信》中分享过他对于人工智能的看法,吴老师就认为,人工智能不会发展成黑客帝国的那种恐怖境地,原因是当初科学家在创立计算机之前先把人类要解决...

3499
来自专栏AlgorithmDog的专栏

靠默契保证的私有制:Python 中的私有

人类文明开化以来,私有制似乎是人类历史的主流在西方国家,“私有财产神圣不可侵犯” 是很多资本主义国家的立国原则之一。在我国,“私有财产不可侵犯” 也...

1808
来自专栏专知

关关的刷题日记05 —— Leetcode 217. Contains Duplicate 方法1和方法2

题目 Leetcode 217. Contains Duplicate Given an array of integers, find if the arra...

3237
来自专栏数据结构与算法

P1909 买铅笔

题目描述 P老师需要去商店买n支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有 3种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平...

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

【学习】《R实战》读书笔记(第四章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

2855

扫码关注云+社区