标签: genetic-algorithm

所以我被赋予了使用遗传算法编写5x5x5井字游戏的问题.我的方法是从3x3开始,使其工作,然后扩展到5x5,然后扩展到5x5x5.

它的工作方式是这样的:

• 模拟一大堆游戏,并在每个游戏的每个回合中,在相应的表(X表或实现为c ++ stdlib映射的O表)中查找响应.如果电路板不存在,请将电路板添加到表中.否则,进行随机响应.

• 在我有完整的表格后,我初始化了一堆玩家(每个玩家都有一个董事会表格副本,用随机响应进行初始化),然后让他们互相对抗.

• 使用他们的胜利/损失来评估健康状况,我保持一定的最佳百分比,然后他们继续前进.冲洗并重复X代,最佳玩家应该出现.

为3×3,贴现板即是反射/其它板的旋转,和电路板,其中所述移动可以是"取胜"或"阻断取胜",板的总数I会遇到要么53或38,这取决于是否你去第一或第二.太棒了!在一小时内生成了最佳玩家.很酷!

使用相同的5x5策略,我知道表的大小会增加,但没有意识到它会大幅增加.即使折扣旋转/反射和强制移动,我的表格约为360万条,看不到尽头.

好吧,这显然不会起作用,我需要一个新的计划.如果我不列举所有的电路板,只是一些电路板,该怎么办？好吧,似乎这也不会起作用,因为如果每个玩家只有一小部分他们可能看到的可能的板,那么他们将会做出很多随机动作,显然是在最优化的相反方向.

实现这一目标的现实方法是什么？我会被困在使用电路板功能吗？目标是尽可能少地编写游戏功能.

我一直在做研究,但我读到的所有内容都会导致最小/最大,AB修剪是唯一可行的选择.我当然可以这样做,但GA真的很酷,我现在的方法只是在这里超过现实.

编辑问题已经解决了:

使用结合开放空间的汉明距离的相似性函数,可能的获胜条件以及一些其他措施使得桌子降低到可管理的2500种可能性,其std::map在几分之一秒内处理.

从我到目前为止看到的它们看起来非常相似.差分进化使用浮点数代替,解决方案称为向量？我不太清楚这意味着什么.如果有人可以提供一些关于两者的优点和缺点的概述.

我试图根据我从"用于游戏程序员的AI技术"一书中选择的技术编写遗传算法,该技术使用二进制编码和适应度比例选择(也称为轮盘赌选择)对人群的基因进行在程序中以二维数组随机生成.

我最近遇到了一个伪代码,并试图实现它,但是我遇到了一些问题,我需要做些什么.我检查过一些书籍和一些开源代码,但仍在努力取得进展.我明白我必须得到总人口的总体适应度的总和,在总和与零之间选择一个随机数,然后如果数字大于父母要覆盖它,但我正在努力实施这些想法.

由于我的Java生疏,因此非常感谢任何帮助实现这些想法.

在模拟退火(使用bean搜索)和遗传算法之间,在性能和用例方面有哪些相关差异？

我知道SA可以被认为是人口规模只有一个的GA,但我不知道两者之间的关键区别.

此外,我正在考虑一种情况,即SA将胜过GA或GA将胜过SA.只有一个简单的例子可以帮助我理解就足够了.

我正在尝试使用基本遗传算法(随机通用采样,1点交叉,Canonical GA)来演化迭代囚徒困境的最优策略.我在Haskell中实现了这个算法,并且最近添加了图表输出.不幸的是,生成的图表不符合此问题的预期模式,因此看起来我有一个错误.

我在这个问题上看到的所有拟合图都看起来像这样:

其他例子可以在关于迭代囚徒困境的演化稳健策略中看到,PJ Darwen和X. Yao(1993)p6-7

但是我的输出看起来像这样:

如果我将突变率设置为1,我得到:

或许暗示我的选择功能并不像我想象的那么随机,因为图表意味着同质人口.

如果您想检查它,我的代码就在这个git存储库中.

现在提出一个问题:你们中的任何人都可以在我的GA实现中提出我可能做错的事情,使图表看起来像这样吗？

例如,我认为它不太可能是适应度函数,因为我使用相同的适应度函数进行输出,它正在最大化,因此即使适应度函数在某种程度上是错误的,它仍然会最大化错误的函数(尽管我是我确定在这里错了,我对遗传算法很陌生)

我想要了解哪些功能的建议,我正试图解决这个问题.

编辑:在我的组合函数中添加了一些调试代码后,它似乎总是被传递给相同的个体(即使突变设置为1),所以推测选择在某处出错.

编辑:选择出错了,但这并没有引起所有问题,只是人口中的同质性.

问题

我试图找到一个经典2D包装问题的变体的解决方案 - 类似于这个问题.

给定任意多边形P和短语W,我想使用平移,缩放和90度旋转将W的字母"打包" 到P中,这样:

• W的字母尽可能覆盖P ;
• W的字母通常按顺序保留(也就是说,当W可以被分解成更小的序列时,该序列中的字母应保持可读).

我想要实现的一些例子:

目前的方法

我已经开始建立一个遗传算法来尝试解决这个问题,它采用以下方法:

• 在网格内映射P256x256 ;
• 为W中的每个字母创建一个简化的边界多边形;
• 使用每个字母的位置,旋转和比例作为染色体(作为灰色编码的二进制字符串,每个x位置,y位置和比例为8位,旋转2位,产生大小26*length(W)位的染色体);
• 采用交叉战略,需要n从信一和length(W) - n信从乙 ;
• 使用简单的突变策略,其中每个位在被选择用于突变的个体中发生突变的概率是1 / 26;
• 目前,基于边界字母多边形所覆盖的P的量来评估适应度.

目前,算法正在运行并找到解决方案,尽管它们并不特别漂亮,因为适应度函数没有考虑字母之间的重叠或可读性约束.

它也很慢,因为适应性评估需要大量的几何计算(我在Ruby中编写算法,但使用C扩展来处理几何体).我正在考虑使用神经网络(或者可能是SVM)来生成符合本文和本文中的想法的适应度估计.

问题

关于到目前为止我做了什么,我有几个问题:

• 首先,整体方法是否有意义？显然,大部分的工作和计算时间都在调整适应度函数,但在我深入研究之前,我想检查一下我是朝着正确的方向前进,并且没有一种不同的方法可以解决这个问题.更好.

• 如何制定适应度函数来解释字母排序/可读性约束？

• 我是否可以对健身功能进行任何优化以改善我可以计算的世代数？

任何其他想法或建议也将非常感激.我已经阅读了大多数关于类似主题的现有SO问题,并阅读了很多关于该主题的论文,但没有涉及任何专门处理文本包装的问题.

谢谢!

我对进化算法有很好的基础,所以现在我开始阅读人工神经网络.我在http://www.ai-junkie.com/ann/evolved/nnt2.html上看到了这个教程 ,展示了如何使用人工神经网络来发展收集地雷的坦克.它使用GA来演化每个神经元的输入权重.

我知道我可以使用GA(没有ANN)来解决同样的问题.我已经使用GA创建了一个俄罗斯方块机器人,以优化网格评估功能中的权重(查看我的博客http://www.bitsrandomicos.blogspot.com.br/).

我的问题是:在我可以单独使用GA的情况下,使用ANN + GA之间的概念/实际区别是什么？我的意思是,我的俄罗斯方块机器人是神经网络吗？(我不这么认为).

有几个相关的问题,但我找不到答案:

进化算法和神经网络是否在相同的域中使用？

何时使用遗传算法与何时使用神经网络？

谢谢!

我是人工神经网络和NeuroEvolution算法的新手.我正在尝试实现名为NEAT(NeuroEvolution of Augmented Topologies)的算法,但原始公共报纸中的描述错过了如何演化网络权重的方法,它说"连接权重在任何NE系统中变异,与每一个连接在每一代都是否受到干扰".

我已经做了一些关于如何在NE系统中改变权重的搜索,但遗憾的是找不到任何详细的描述.

我知道在训练NE时,通常使用反向传播算法来校正权重,但只有在您拥有固定的拓扑(结构)代数并且您知道问题的答案时,它才有效.在NeuroEvolution中你不知道答案,你只有健身功能,所以在这里不可能使用反向传播.

我正在用Python研究遗传算法。在我的问题中，我将个人存储在这样的列表中：

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

在每次迭代中，每个个体都有一定的死亡概率，因此将从列表中删除。

更重要的是，在每次迭代中，个体随机配对，例如：

[1, 5], [7, 10], [3, 4], [6, 8], [2, 9]

并且这些对有可能有一个孩子，该孩子将作为下一个数字（11、12 等）添加到列表中

每对可能只出现一次，所以我必须存储每对，并在随机选择两个个体后，检查它们是否还不是一对。

我设法做到了这一切：

reproducing_prob = 0.1 #probability of reproduction
death_prob = 0.1 #probability of death
pop_size = 10 #starting population size
pop_start = list(range(1, pop_size+1))
used_pairs = set() #storing pairs that already appeared
new_creature = 10

for day in range(10):
    
    print("\nDay ", day)
    print("Population: ", pop_start)
    dead_creatures = []
    
    for creature in pop_start: #iterating …

我尝试为我的项目学习并实现一个简单的遗传算法库.在这个时候,人口的进化,选择已经准备就绪,我正在尝试为Java和Scala中的遗传进化引擎实现一个简单的好变异算子,如高斯变异算子(GMO).

我在基于多目标进化算法的Pareto排名(PM Mateo,I.Alberto),第6页和第7页的论文A变异算子中找到了关于高斯变异算子(GMO)的一些信息.

但我有一些问题需要找到有关如何在Java中实现此高斯变异算子和此运算符的其他有用变体的其他信息.我该怎么办？

我正在使用random.nextGaussian()随机Java util 的功能,但此方法仅返回0到1之间的随机数.

所以,

a)在这种情况下,如何修改返回编号的精度？(例如,我想获得一个介于0和1之间的随机双数,步长等于0.00001.)

b)我如何指定mu和sigma使用这个函数,因为我想在本地搜索我的基因组的值,而不是在-1和1之间.我怎样才能调整我的基因组价值的本地研究？

经过研究,我找到了b)问题的答案.我似乎可以取代高斯随机数,如下所示:

 newGenomeValue = oldGenomeValue + (( gaussiandRndNumber * sigma ) + mean )

其中mean=我的基因组价值.

(参见底部的方法如何生成具有正态或高斯分布的随机数？)