遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。
我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。
问题:
你用GA/GP解决过什么问题? 你使用了哪些库/框架?
我在寻找第一手的经验,所以请不要回答,除非你有。
遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。
我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。
问题:
你用GA/GP解决过什么问题? 你使用了哪些库/框架?
我在寻找第一手的经验,所以请不要回答,除非你有。
当前回答
没有家庭作业。
1995年,我作为专业程序员的第一份工作是为标准普尔500指数期货编写一个基于遗传算法的自动交易系统。该应用程序是用Visual Basic 3 [!我不知道我当时是怎么做的,因为VB3甚至没有课程。
The application started with a population of randomly-generated fixed-length strings (the "gene" part), each of which corresponded to a specific shape in the minute-by-minute price data of the S&P500 futures, as well as a specific order (buy or sell) and stop-loss and stop-profit amounts. Each string (or "gene") had its profit performance evaluated by a run through 3 years of historical data; whenever the specified "shape" matched the historical data, I assumed the corresponding buy or sell order and evaluated the trade's result. I added the caveat that each gene started with a fixed amount of money and could thus potentially go broke and be removed from the gene pool entirely.
在对种群的每一次评估之后,幸存者被随机杂交(通过混合来自两个亲本的片段),一个基因被选择为亲本的可能性与它产生的利润成正比。我还添加了点突变的可能性,让事情变得有趣一点。经过几百代这样的基因,我最终得到了一个基因群,它可以把5000美元变成平均约10000美元,而且没有死亡/破碎的可能性(当然是在历史数据上)。
Unfortunately, I never got the chance to use this system live, since my boss lost close to $100,000 in less than 3 months trading the traditional way, and he lost his willingness to continue with the project. In retrospect, I think the system would have made huge profits - not because I was necessarily doing anything right, but because the population of genes that I produced happened to be biased towards buy orders (as opposed to sell orders) by about a 5:1 ratio. And as we know with our 20/20 hindsight, the market went up a bit after 1995.
其他回答
我是一个研究使用进化计算(EC)来自动修复现有程序中的错误的团队的成员。我们已经在现实世界的软件项目中成功地修复了一些真实的错误(参见本项目的主页)。
这种EC修复技术有两种应用。
The first (code and reproduction information available through the project page) evolves the abstract syntax trees parsed from existing C programs and is implemented in Ocaml using our own custom EC engine. The second (code and reproduction information available through the project page), my personal contribution to the project, evolves the x86 assembly or Java byte code compiled from programs written in a number of programming languages. This application is implemented in Clojure and also uses its own custom built EC engine.
进化计算的一个优点是技术的简单性,使得编写自己的自定义实现不太困难。有关遗传规划的一个很好的免费的介绍性文本,请参阅遗传规划的现场指南。
在读完《盲人钟表匠》之后,我对道金斯所说的帕斯卡程序产生了兴趣,他开发了一个可以随着时间进化的生物模型。我对使用Swarm编写自己的程序很感兴趣。我没有画出他画的那些奇特的生物图形,但我的“染色体”控制着影响生物体生存能力的特征。他们生活在一个简单的世界里,可以与彼此和环境决一死战。
生物的生存或死亡部分取决于偶然性,但也取决于它们如何有效地适应当地环境,如何有效地消耗营养物质以及如何成功地繁殖。这很有趣,但也向我妻子证明了我是一个极客。
除了一些常见的问题,如《旅行推销员》和Roger Alsing的《蒙娜丽莎》程序的变体,我还编写了一个进化数独求解器(这需要我自己更多的原创想法,而不仅仅是重新实现别人的想法)。解决数独游戏有更可靠的算法,但进化方法效果相当好。
在过去的几天里,在Reddit上看到这篇文章后,我一直在玩一个进化程序来寻找扑克的“冷牌”。目前还不太令人满意,但我想我可以改进。
我有自己的进化算法框架。
As part of my thesis I wrote a generic java framework for the multi-objective optimisation algorithm mPOEMS (Multiobjective prototype optimization with evolved improvement steps), which is a GA using evolutionary concepts. It is generic in a way that all problem-independent parts have been separated from the problem-dependent parts, and an interface is povided to use the framework with only adding the problem-dependent parts. Thus one who wants to use the algorithm does not have to begin from zero, and it facilitates work a lot.
你可以在这里找到代码。
你可以用这个算法找到的解决方案已经在科学工作中与最先进的算法SPEA-2和NSGA进行了比较,并且已经证明 算法的性能相当,甚至更好,这取决于您用来衡量性能的指标,特别是取决于您正在关注的优化问题。
你可以在这里找到它。
同样,作为我的论文和工作证明的一部分,我将这个框架应用于项目组合管理中的项目选择问题。它是关于选择对公司增加最大价值的项目,支持公司的战略或支持任何其他任意目标。例如,从特定类别中选择一定数量的项目,或最大化项目协同作用,……
我的论文将该框架应用于项目选择问题: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf
之后,我在一家财富500强公司的投资组合管理部门工作,在那里他们使用了一种商业软件,该软件还将GA应用于项目选择问题/投资组合优化。
更多资源:
框架文档: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf
mPOEMS演示论文: http://portal.acm.org/citation.cfm?id=1792634.1792653
实际上,只要有一点热情,每个人都可以很容易地将通用框架的代码适应任意的多目标优化问题。
几周前,我提出了一个关于SO的解决方案,使用遗传算法来解决图布局的问题。这是一个约束优化问题的例子。
同样在机器学习领域,我用c/c++从头开始实现了一个基于ga的分类规则框架。 我还在一个示例项目中使用了GA来训练人工神经网络(ANN),而不是使用著名的反向传播算法。
此外,作为我研究生研究的一部分,我已经使用GA来训练隐马尔可夫模型,作为基于em的Baum-Welch算法的额外方法(还是在c/c++中)。