标签: evolutionary-algorithm

这一切都在标题中,但对于任何对进化算法感兴趣的人来说,这是一个细分:

在EA中,基本前提是你随机生成一定数量的生物(实际上只是参数集),针对问题运行它们,然后让最佳表现者生存.

然后,你将幸存者的杂交组合,幸存者的突变以及一定数量的新随机生物重新组合起来.

做了几千次,有效的生物出现了.

有些人也会做一些事情,比如引入多个生物群的"岛屿",这些生物群是一段时间允许杂交的单独种群.

所以,我的问题是:什么是最佳的再增殖百分比？

我一直保持前10%的表现,并重新种植30%的杂交和30%的突变.剩余的30%用于新生物.

我也尝试了多岛理论,我也对你的结果感兴趣.

对我来说,这绝不是EA可以解决的问题类型.你知道有人在尝试吗？

提前致谢!

我不打算在我的博客上放一个链接,但我没有任何其他方法来澄清我的真正含义.这篇文章很长,它的三个部分(1,2,3),但是如果你很好奇,这是值得阅读.

很久以前(至少5年)我编写了一个生成"数学细菌"的python程序.这些细菌是python对象,具有简单的基于操作码的遗传密码.您可以使用数字为它们提供数据,并根据其代码的执行返回一个数字.我随机生成他们的遗传密码,并将环境选择应用于那些产生类似于预定义预期值的结果的对象.然后我让他们复制,引入突变,并进化它们.结果非常有趣,因为他们的遗传密码基本上学习如何解决简单方程,即使对于训练数据集的不同值也是如此.

现在,这件事只是一个玩具.我有时间浪费,我想满足自己的好奇心.但是,我认为在研究方面已经做了一些事情......我希望我在这里重新发明轮子.你是否意识到更多认真尝试制造像我编程的细菌一样的细菌？

请注意,这不是真正的"遗传算法".遗传算法是指您使用进化/选择来改进针对给定评分函数的参数向量.这有点不同.我针对给定的评分函数优化代码而不是参数.

我需要开发一个课程时间表软件,可以有效地分配时间段和房间.这是一个基于课程的例程,而不是基于后期注册.并且有效地意味着课程根据工作人员的时间偏好分配时间段,并且还需要最小化第1年 - 第2年课程重叠,以便第2年学生可以重新学习他们未能通过的课程.(以及3至4年级的学生) .

现在,起初我认为这将是一个容易的问题,但现在看起来不同了.我看过的大多数论文都使用遗传算法/ PSO /模拟退火或这些类型的算法.我仍然无法将问题解释为GA问题.令我困惑的是为什么几乎没有人建议使用DFS或图形着色算法？

如果使用DFS/graph-coloring,有人可以解释这个场景吗？或者为什么不建议或尝试他们.

我想实现一个用于生成音乐的交互式进化算法(可能只是简单的旋律开始).

我想用JFugue.它的网站声称它非常适合进化音乐,但我找不到任何进化的例子.

我已经有了一个框架提供进化机制.我正在寻找的是一些简单的,有效的代码,它演示了音乐部分的可行方法(例如适用于演化曲调的编码和进化算子).

我有一些想法可以实现它,但我对音乐理论并不是特别了解,所以首先我想重新实现已知可行的东西.

那么,是否有任何人拥有或知道任何免费提供的代码(任何语言都很好),它们演示了一种或多种进化音乐方法？

编辑:我特别寻找进化代码而不是其他可用于音乐合成的技术.

我正在写一个遗传算法,我打算从轮盘选择转到锦标赛选择,但我怀疑我的理解可能有缺陷.

如果我只选择人口中的n/2最佳解决方案,那么我的人口肯定会很快耗尽吗？

我对算法的理解是:

for(Member m in currentPopulation){
    Member randomMember1 = random member of currentPopulation which is then removed from currentPopulation
    Member randomMember2 = as above;
    //Mutate and crossover

    if(randomMember1.getScore() > randomMember2.getScore()){
        nextGeneration.add(randomMember1);
    } else {
        nextGeneration.add(randomMember2);
    }
}

我理解正确吗？

上下文

这个问题的背景是我想要使用基因表达式编程(GEP),这是一种使用Erlang的进化算法.GEP使用基于字符串的DSL称为" Karva表示法 ".Karva表示法很容易翻译成表达式解析树,但是翻译算法假定一个实现具有可变对象:在翻译过程的早期创建不完整的子表达式,并且他们自己的子表达式随后用值填充.在他们被创建时不知道.

Karva表示法的目的是保证在没有任何昂贵的编码技术或遗传密码校正的情况下创建语法正确的表达式.问题是,使用像Erlang这样的单任务编程语言,我必须在每个子表达式被填充时不断重新创建表达式树.这需要一个便宜的 - O(n)？ - 更新操作并将其转换为在指数时间内完成的操作(除非我弄错了).如果我找不到将K表达式转换为表达式树的有效函数算法,那么GEP的一个引人注目的特性就会丢失.

问题

我很欣赏K表达式翻译问题非常模糊,所以我想要的是如何将一个固有的非功能性算法(利用可变数据结构的算法)转换为不具备这种算法的算法.纯函数式编程语言如何适应计算机科学早期生成的许多算法和数据结构,这些算法和数据结构依赖于可变性来获得所需的性能特征？

决策问题不适用于进化算法,因为无法优化/演化简单的正确/错误适应度量.那么,将决策问题转换为优化问题的方法/技术是什么？

例如,我目前正在研究一个问题,即个人的适应性在很大程度上取决于它产生的输出.根据基因的排序,个体要么不产生输出,要么产生完美的输出 - 没有"介于两者之间"(因此,没有爬山).个体基因排序的一个小变化会对个体的适应性产生巨大影响,因此使用进化算法基本上等于随机搜索.

如果你知道的话,一些文献参考会很好.

这是一个普遍感兴趣的问题,因为我并不想解决具体问题.我环顾四周试图找到一些涵盖这个领域的文章,但我甚至在努力拼凑一些好的搜索词.

让我们从我所知道的开始:我在人工智能方面接受了大学水平的教育,包括遗传编程和更广泛的进化算法,尽管自从我十年前毕业以来,我还没有玩过很多.我想知道这些方法是否可用于创建机器代码来解决问题(可能是x86,或者某些'任意'指令集).我们可以自己进化算法,例如可以计算平方根,还是在屏幕上绘制令人愉悦的图像？是否可以使用进化算法来创建可以创建优化代码的整个编译器(用于大小,速度等)？

此外,我经常认为遗传编程或进化算法本身并不是物种进化的良好证据.涉及进化算法的问题解决方法似乎总是需要将智能写入其中.一个人如何以真正发生真正有趣和令人惊讶的结果的方式创建一个真正的进化算法？

TLDR:可以使用的进化算法永远是在创造一种机器代码有用,以及是否有进化算法前面的例子中,一般生产真正有趣和令人惊讶的结果？

缺口

我为我正在做的边项目实现了差分进化算法.因为交叉步骤似乎涉及很多参数选择(例如交叉概率),所以我决定跳过它并仅使用变异.该方法似乎工作正常,但我不确定如果我介绍交叉,我是否会获得更好的性能.

主要问题:将差异引入差异进化的动机是什么？您能提供一个玩具示例,其中介绍交叉超出纯变异吗？

我的直觉是,交叉会在二维中产生类似下面的内容.假设我们有两个父矢量(红色).均匀交叉可以在其中一个蓝点处产生新的试验向量.

我不确定为什么这种探索会被认为是有益的.事实上,如果高适应度解决方案遵循一些线性趋势,这似乎会使性能变差.在下图中,假设红点是当前的总体,最佳解决方案是在右下角.人口正在山谷中行进,使得右上角和左下角产生不良解决方案.左上角产生"好"但不是最理想的解决方案.注意均匀交叉如何产生与改进方向正交的试验(蓝色).我使用了1的交叉概率和忽略的变异来说明我的观点(见代码).我想这种情况可能会在优化问题中经常出现,但可能会误解某些东西.

注意:在上面的例子中,我隐含地假设群体在这个空间中被随机初始化(均匀),并且已经开始收敛到中心谷(正左上到右下)的正确解.

这个玩具示例是凸的,因此差分演化甚至不是合适的技术.然而,如果这个主题嵌入在多模态健身景观中,那么交叉似乎可能是有害的.虽然交叉确实支持探索,这可能是有益的,但我不确定为什么人们会选择在这个特定的方向上进行探索.

以上示例的R代码:

N = 50

x1 <- rnorm(N,mean=2,sd=0.5)
x2 <- -x1+4+rnorm(N,mean=0,sd=0.1)
plot(x1,x2,pch=21,col='red',bg='red',ylim=c(0,4),xlim=c(0,4))

x1_cx = list(rep(0, 50))
x2_cx = list(rep(0, 50))
for (i in 0:N) {
  x1_cx[i] <- x1[i]
  x2_cx[i] <- x2[sample(1:N,1)]
}

points(x1_cx,x2_cx,pch=4,col='blue',lwd=4)

后续问题:如果交叉在某些情况下是有益的,是否有合理的方法来a)确定您的特定问题是否会受益于交叉,以及b)如何调整交叉参数以优化算法？

一个相关的stackoverflow问题(我正在寻找更具体的东西,例如玩具示例):在差分进化算法中跨越的重要性是什么？

一个类似的问题,但不是特定的差异演化:遗传算法中的交叉效率

我对比赛选择的理解是:

对于给定的锦标赛大小,t,从群体中随机选择t个体并将该锦标赛的获胜者确定为具有最大适应度函数值的个体.

我的问题是:

" 二元锦标赛选择 "和" 锦标赛选择 " 之间是否存在差异,或者它们是否可以互换？