遗传算法(GA)和遗传规划(GP)是有趣的研究领域.
我想知道你使用GA/GP解决的具体问题,以及你没有使用自己的库/框架.
问题:
您使用GA/GP解决了哪些问题？
您使用了哪些库/框架？
我正在寻找第一手经验,所以除非你有这个经验,否则请不要回答.
不是作业.
我作为专业程序员的第一份工作(1995年)是为S&P500期货编写基于遗传算法的自动交易系统.该应用程序是用Visual Basic 3 [!]编写的,我不知道我当时做了什么,因为VB3甚至没有类.
应用程序从一群随机生成的固定长度字符串("基因"部分)开始,每个字符串对应于标准普尔500期货的每分钟价格数据中的特定形状,以及特定的订单(买入或卖出)和止损和止盈金额.通过3年的历史数据评估每个字符串(或"基因")的利润表现; 只要指定的"形状"与历史数据匹配,我就会假定相应的买入或卖出订单并评估交易的结果.我添加了一个警告,即每个基因都以固定金额开始,因此可能会破裂并完全从基因库中移除.
在对群体进行每次评估之后,幸存者被随机杂交(通过仅混合来自两个亲本的比特),基因被选择作为亲本的可能性与其产生的利润成比例.我还添加了点突变的可能性,以增加一些东西.经过几百代之后,我最终得到了一大堆基因,可以将5000美元变成平均大约10000美元,没有死亡/破产的可能性(当然,历史数据).
不幸的是,我从来没有机会使用这个系统,因为我的老板在不到3个月的时间内以传统的方式损失了近10万美元,他失去了继续这个项目的意愿.回想起来,我认为该系统会带来巨大的利润 - 不是因为我必须做任何事情,而是因为我生产的基因群体恰好偏向买单(而不是卖单)大约5: 1比率.正如我们知道的20/20后见之明,市场在1995年之后有所上升.
我做了一些生活在这个小世界里的小动物.他们有一个神经网络大脑,它接收了来自世界的一些输入,输出是一个用于在其他动作中移动的矢量.他们的大脑是"基因".
该计划始于一群随机大脑的随机人群.输入和输出神经元是静态的,但介于两者之间的不是.
环境包含食物和危险.食物增加能量,当你有足够的能量,你可以交配.危险会减少能量,如果能量为0,他们就会死亡.
最终,这些生物进化到世界各地,寻找食物并避免危险.
然后我决定做一个小实验.我给了生物大脑一个叫做"嘴"的输出神经元和一个叫做"耳朵"的输入神经元.重新开始,并惊讶地发现他们进化到最大化空间,每个相应的生物将留在其各自的部分(食物随机放置).他们学会了彼此合作,而不是互相帮助.总有例外.
然后我尝试了一些有趣的事 我死去的生物会成为食物.试着猜猜发生了什么!两种类型的生物进化,一种类似于群体攻击,一种是高度回避.
那么这里有什么教训呢？沟通意味着合作.一旦你引入一个伤害另一个元素的元素你获得了某些东西,那么合作就会被破坏.
我想知道这是如何反映自由市场和资本主义制度的.我的意思是,如果企业可以伤害他们的竞争并侥幸逃脱,那么很明显他们将竭尽全力干扰竞争.
编辑:
我是用C++编写的,没有使用框架.写了我自己的神经网络和GA代码.埃里克,谢谢你说这是合情合理的.人们通常不相信GA的权力(虽然限制是显而易见的),直到他们玩它.GA简单但不简单.
对于怀疑者来说,神经网络已被证明能够模拟任何函数,如果它们有多个层.GA是一种非常简单的方法来导航解决方案空间,找到本地和潜在的全局最小值.将GA与神经网络相结合,您可以找到找到通用问题近似解的函数.因为我们正在使用神经网络,所以我们正在优化某些输入的功能,而不是某些功能的输入,因为其他输入使用GA
以下是生存示例的演示代码:http://www.mempko.com/darcs/neural/demos/eaters/ 构建说明:
安装darcs,libboost,liballegro,gcc,cmake,make
darcs clone --lazy http://www.mempko.com/darcs/neural/
cd neural
cmake .
make
cd demos/eaters
./eaters
2004年1月,飞利浦新显示技术公司联系了我,他们正在为亚马逊Kindle和美国其他公司在美国市场上销售的第一款商用电子墨水索尼Librie创建电子产品.一个欧洲.
飞利浦工程师遇到了一个重大问题.在产品推向市场的几个月前,他们在更换页面时仍然在屏幕上出现重影.问题是创造静电场的200名司机.这些驱动器中的每一个都有一定的电压,必须设置在0到1000 mV之间或类似的东西.但是,如果你改变了其中一个,它将改变一切.
因此,单独优化每个驱动器的电压是不可能的.可能的值组合的数量是数十亿,并且特殊相机花费大约1分钟来评估单个组合.工程师已经尝试了许多标准的优化技术,但没有什么可以接近的.
首席工程师与我联系,因为我之前已经向开源社区发布了一个遗传编程库.他问GP/GA是否会有所帮助,以及我是否可以参与其中.我做了,大约一个月我们一起工作,编写和调整GA库,合成数据,并将其集成到他们的系统中.然后,一个周末,他们让它与真实的东西一起运行.
接下来的星期一,我收到了他和他们的硬件设计师发来的这些热情洋溢的电子邮件,讲述了没人能相信GA发现的惊人结果.就是这样.那年晚些时候,该产品进入市场.
我没有得到一分钱,但我得到了'吹牛'的权利.他们从一开始就说他们已经超出预算,所以在我开始研究之前我就知道这笔交易是什么.对于GA的应用来说,这是一个很棒的故事.:)
我在婚礼招待会上用GA来优化座位分配.超过10桌的80位客人.评估功能的基础是让人们了解日期,将人们的共同点放在一起,并让人们在不同的桌子上保持极端相反的观点.
我跑了好几次.每一次,我都有九张好桌子,还有一张奇怪的球.最后,我的妻子做了座位任务.
我的旅行推销员优化器使用了染色体到行程的新颖映射,这使得染色体的繁殖和变异变得微不足道,而没有产生无效旅行的风险.
更新:因为有几个人问过怎么...
从一系列来宾(或城市)开始,以一些任意但一致的顺序排列,例如按字母顺序排列.将此称为参考解决方案.将客人的索引视为他/她的座位号.
我们不是试图直接在染色体中编码这种排序,而是编码将参考解决方案转换为新解决方案的指令.具体来说,我们将染色体视为数组中的索引列表进行交换.为了解码染色体,我们从参考解决方案开始并应用染色体指示的所有交换.在数组中交换两个条目总是会产生一个有效的解决方案:每个访客(或城市)仍然只出现一次.
因此,染色体可以随机生成,变异,并与其他染色体交叉,并始终产生有效的解决方案.
我使用遗传算法(以及一些相关技术)来确定风险管理系统的最佳设置,该系统试图阻止黄金农民使用被盗信用卡来支付MMO.该系统将采用"已知"值(欺诈与否)进行数千次交易,并找出最佳组合设置,以正确识别欺诈性交易,而不会产生太多误报.
我们得到了一个事务的几十个(布尔)特征的数据,每个特征都给出了一个值并总计.如果总数高于阈值,则交易是欺诈.GA将创建大量随机值集,根据已知数据集对其进行评估,选择得分最高的(在欺诈检测和限制误报数量上),然后交叉繁殖最好的几个每一代都要产生新一代的候选人.在经过一定代数后,最佳得分值被认为是胜利者.
创建要测试的已知数据的语料库是系统的致命弱点.如果您等待退款,那么在尝试回复欺诈者时,您已经落后了几个月,因此有人必须手动审核大量交易以构建该数据语集而无需等待太长时间.
这最终确定了绝大多数的欺诈行为,但在最容易欺诈的项目上却无法将其降至1%以下(考虑到90%的收到的交易可能是欺诈行为,而且表现相当不错).
我用perl完成了所有这些.在相当旧的Linux机器上运行一次软件需要1-2个小时才能运行(20分钟通过WAN链接加载数据,剩下的时间用于处理).任何给定代的大小都受可用RAM的限制.我会反复对参数进行一次又一次的运行,寻找一个特别好的结果集.
总而言之,它避免了手动试图调整数十个欺诈指标的相对价值所带来的一些失误,并且始终提出了比我手工制作的更好的解决方案.AFAIK,它仍然在使用(我写了大约3年后).
除了一些常见的问题,如旅行商和变化罗杰Alsing的蒙娜丽莎节目,我也写一个渐进的数独解算器(这需要多一点原来以为我的一部分,而不仅仅是重新实现别人的想法).有更可靠的算法来解决Sudokus,但进化方法效果相当好.
在过去的几天里,我一直在玩一个演化程序,在看到Reddit上的这篇文章之后为扑克寻找"冷甲板" .目前还不太令人满意,但我想我可以改进它.
我有自己的框架,我用于进化算法.
足球小费.我建立了一个GA系统来预测AFL(澳大利亚足球规则)中游戏的每周结果.
几年前,我对标准的工作足球池感到厌倦,每个人都只是上网,并从媒体的一些专家那里挑选.所以,我认为打败一大批广播新闻专业并不难,对吧？我的第一个想法是从Massey Ratings获得结果,然后在赛季结束后揭示我赢得名声和荣耀后的策略.然而,由于我从未发现梅西不跟踪AFL的原因.我内心的愤世嫉俗者认为这是因为每个AFL游戏的结果基本上都是随机的,但我对近期规则变化的抱怨属于不同的论坛.
该系统基本上考虑了进攻强度,防守强度,主场优势,每周改进(或缺乏)以及每种改变的速度.这为本赛季的每支球队创建了一组多项式方程.可以计算给定日期的每个匹配的获胜者和分数.目标是找到与所有过去游戏的结果最匹配的系数集合,并使用该集合来预测即将到来的周游戏.
在实践中,该系统将找到准确预测超过90%的过去游戏结果的解决方案.然后,它将成功地为即将到来的一周(即不在训练集中的那一周)挑选约60-80%的游戏.
结果:刚好在包装的中间位置.没有主要的现金奖励,也没有我可以用来击败拉斯维加斯的系统.虽然这很有趣.
我从头开始构建一切,没有使用框架.
我为1992年为货运行业开发的3D激光表面轮廓系统开发了家庭酿造GA.该系统依赖于三维三角测量并使用定制激光线扫描仪,512x512相机(具有自定义捕获功能).相机和激光之间的距离永远不会精确,相机的焦点在你预期的256,256位置是找不到的!
尝试使用标准几何和模拟退火方式方程求解来计算校准参数是一场噩梦.
遗传算法在一个晚上被掀起,我创建了一个校准立方体来测试它.我知道立方体尺寸具有高精度,因此我的想法是我的GA可以为每个扫描单元发展一组定制的三角测量参数,以克服生产变化.
诀窍是一种享受.至少可以说,我大惊小怪!在大约10代之内,我的"虚拟"立方体(从原始扫描生成并从校准参数重新生成)实际上看起来像一个立方体!大约50代之后,我得到了我需要的校准.
当您计划为房屋涂漆时,通常很难获得精确的颜色组合.通常,你会想到一些颜色,但它不是颜色之一,供应商会告诉你.
昨天,我的GA研究员教授在德国提到了一个真实的故事(对不起,我没有进一步的参考,是的,如果有人要求,我可以找到它).这个家伙(让我们称他为色彩人)过去常常从门到门帮助人们找到确切的颜色代码(RGB),这将成为顾客心中的壁橱.以下是他将如何做到这一点:
这个颜色的家伙曾经带着一个使用GA的软件程序.他过去常常用4种不同的颜色开始 - 每种颜色编码为编码的染色体(其解码值为RGB值).消费者选择4种颜色中的1种(这是他/她最接近的颜色).然后程序将为该个体分配最大适应度,并使用突变/交叉移动到下一代.上面的步骤将重复进行,直到消费者找到了确切的颜色,然后用颜色的人告诉他RGB组合!
通过将最大适应度分配给消费者所关注的颜色,颜色家伙的程序正在增加收敛到颜色的机会,消费者已经准备好了.我觉得很有趣!
现在我有一个-1,如果你计划更多的-1,请.阐明这样做的原因!
作为我的本科CompSci学位的一部分,我们被分配了为Jikes研究虚拟机找到最佳jvm标志的问题.这是使用Dicappo基准测试套件评估的,该套件向控制台返回时间.我编写了一个分布式的gentic alogirthm,它可以切换这些标志以改善基准测试套件的运行时间,尽管需要花费数天来补偿影响结果的硬件抖动.唯一的问题是我没有正确地了解编译器理论(这是作业的意图).
我本可以使用现有的默认标志来播种初始种群,但有趣的是该算法发现了与O3优化级别非常相似的配置(但在许多测试中实际上更快).
编辑:我也在Python中编写了我自己的遗传算法框架用于赋值,并且只使用了popen命令来运行各种基准测试,尽管如果它不是一个评估的赋值,我会看看pyEvolve.
首先,乔纳森科扎(亚马逊)的"遗传编程" 几乎是关于遗传和进化算法/编程技术的书,有很多例子.我强烈建议检查一下.
至于我自己使用的遗传算法,我使用(本土种植的)遗传算法来发展用于对象收集/破坏场景的群算法(实际目的可能是清除雷区).这是该论文的链接.我所做的最有趣的部分是多阶段适应度函数,这是必要的,因为简单适应度函数没有为遗传算法提供足够的信息来充分区分群体成员.
几周前,我提出了使用遗传算法解决图形布局问题的SO解决方案.这是约束优化问题的一个例子.
同样在机器学习领域,我从头开始在c/c ++中实现了基于GA的分类规则框架.
我还在一个示例项目中使用GA来训练人工神经网络(ANN),而不是使用着名的反向传播算法.
此外,作为我研究生研究的一部分,我使用GA训练隐马尔可夫模型作为基于EM的Baum-Welch算法的另一种方法(再次使用c/c ++).
我是调查使用Evolutionary Computation(EC)自动修复现有程序中的错误的团队的一员.我们已成功修复了现实世界软件项目中的一些实际错误(请参阅此项目的主页).
我们有两种EC修复技术的应用.
第一个(通过项目页面提供的代码和再现信息)演化了从现有C程序解析的抽象语法树,并使用我们自己的自定义EC引擎在Ocaml中实现.
第二个(通过项目页面提供的代码和复制信息),我个人对项目的贡献,演变了从用多种编程语言编写的程序编译的x86程序集或Java字节代码.此应用程序在Clojure中实现,并且还使用自己的定制EC引擎.
Evolutionary Computation的一个不错的方面是该技术的简单性使得编写自己的自定义实现成为可能,而不会有太多困难.有关遗传编程的免费的免费介绍性文本,请参阅遗传编程实地指南.
我和同事正在研究使用我们公司要求的各种标准将货物装载到卡车上的解决方案.我一直致力于遗传算法解决方案,而他正在使用Branch And Bound进行积极的修剪.我们仍在实施此解决方案,但到目前为止,我们已经取得了良好的效果.
几年前,我使用ga来优化asr(自动语音识别)语法,以获得更好的识别率.我开始的选择非常简单列出了(其中GA是为每个插槽测试的可能条件组合)和我的工作方式,以更加开放和复杂的语法.通过在一种语音距离函数下测量术语/序列之间的分离来确定适应度.我也尝试做一个语法弱等效变化找到一个编译成一个更紧凑的表示(在我的直接算法去年底,它极大地提高了"语言",我们可以在应用程序中使用的大小) .
最近,我使用它们作为默认假设来测试各种算法生成的解决方案的质量.这在很大程度上涉及分类和不同种类的配件问题(即创建解释一组由评审过的数据集(S)作出的选择一个"规则").
京公网安备 11010802040832号 | 京ICP备19059560号-6 