遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。

我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。

问题:

你用GA/GP解决过什么问题? 你使用了哪些库/框架?

我在寻找第一手的经验,所以请不要回答,除非你有。


当前回答

几周前,我提出了一个关于SO的解决方案,使用遗传算法来解决图布局的问题。这是一个约束优化问题的例子。

同样在机器学习领域,我用c/c++从头开始实现了一个基于ga的分类规则框架。 我还在一个示例项目中使用了GA来训练人工神经网络(ANN),而不是使用著名的反向传播算法。

此外,作为我研究生研究的一部分,我已经使用GA来训练隐马尔可夫模型,作为基于em的Baum-Welch算法的额外方法(还是在c/c++中)。

其他回答

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

实际上,只要有一点热情,每个人都可以很容易地将通用框架的代码适应任意的多目标优化问题。

In 2007-9 I developed some software for reading datamatrix patterns. Often these patterns were difficult to read, being indented into scratched surfaces with all kinds of reflectance properties, fuzzy chemically etched markings and so on. I used a GA to fine tune various parameters of the vision algorithms to give the best results on a database of 300 images having known properties. Parameters were things like downsampling resolution, RANSAC parameters, amount of erosion and dilation, low pass filtering radius, and a few others. Running the optimisation over several days this produced results which were about 20% better than naive values on a test set of images unseen during the optimisation phase.

这个系统完全是从零开始编写的,我没有使用任何其他库。我并不反对使用这些东西,只要它们能提供可靠的结果,但是您必须注意许可兼容性和代码可移植性问题。

我构建了一个简单的GA,用于在音乐播放时从频谱中提取有用的模式。输出用于驱动winamp插件中的图形效果。

输入:一些FFT帧(想象一个二维浮点数组) 输出:单个浮点值(输入的加权和),阈值为0.0或1.0 基因:输入权重 适应度函数:占空比、脉宽、BPM在合理范围内的组合。

我将一些ga调整到频谱的不同部分以及不同的BPM限制,所以它们不会趋向于收敛到相同的模式。来自每个种群的前4个的输出被发送到渲染引擎。

一个有趣的副作用是,整个人群的平均健康状况是音乐变化的一个很好的指标,尽管通常需要4-5秒才能发现。

Several years ago I used ga's to optimize asr (automatic speech recognition) grammars for better recognition rates. I started with fairly simple lists of choices (where the ga was testing combinations of possible terms for each slot) and worked my way up to more open and complex grammars. Fitness was determined by measuring separation between terms/sequences under a kind of phonetic distance function. I also experimented with making weakly equivalent variations on a grammar to find one that compiled to a more compact representation (in the end I went with a direct algorithm, and it drastically increased the size of the "language" that we could use in applications).

最近,我将它们用作默认假设,以此来测试由各种算法生成的解决方案的质量。这主要涉及分类和不同类型的拟合问题(即创建一个“规则”,解释审查员对数据集所做的一组选择)。

没有家庭作业。

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.