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

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

问题:

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

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


当前回答

我几周前做了这个有趣的小玩意。它生成有趣的互联网图像使用GA。有点傻,但很好笑。

http://www.twitterandom.info/GAFunny/

对此有一些见解。它是一些mysql表。一个用于图像列表及其评分(即适合度),另一个用于子图像及其在页面上的位置。

子图像可以有几个细节,但不是全部实现:+大小,倾斜,旋转,+位置,+image_url。

当人们投票决定这张照片有多有趣时,它或多或少会流传到下一代。如果它存活下来,它会产生5-10个带有轻微突变的后代。目前还没有交叉。

其他回答

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

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

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

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

There was an competition on codechef.com (great site by the way, monthly programming competitions) where one was supposed to solve an unsolveable sudoku (one should come as close as possible with as few wrong collumns/rows/etc as possible).What I would do, was to first generate a perfect sudoku and then override the fields, that have been given. From this pretty good basis on I used genetic programming to improve my solution.I couldn't think of a deterministic approach in this case, because the sudoku was 300x300 and search would've taken too long.

在工作中,我遇到了这样一个问题:给定M个任务和N个dsp,如何将任务分配给dsp是最好的?“最佳”定义为“最大负载DSP的负载最小化”。有不同类型的任务,不同的任务类型有不同的性能分支,这取决于它们被分配到哪里,所以我将一组工作到dsp的分配编码为“DNA字符串”,然后使用遗传算法来“培育”我所能“培育”的最佳分配字符串。

它运行得相当好(比我之前的方法好得多,之前的方法是评估每个可能的组合……对于非平凡问题的大小,它将需要数年才能完成!),唯一的问题是无法判断是否已经达到了最优解。你只能决定当前的“最大努力”是否足够好,或者让它运行更长时间,看看它是否可以做得更好。

我使用遗传算法(以及一些相关技术)来确定风险管理系统的最佳设置,该系统试图阻止淘金者使用偷来的信用卡来购买mmo游戏。该系统将接收数千笔具有“已知”值的交易(欺诈与否),并找出最佳设置组合,以正确识别欺诈交易,而不会产生太多误报。

We had data on several dozen (boolean) characteristics of a transaction, each of which was given a value and totalled up. If the total was higher than a threshold, the transaction was fraud. The GA would create a large number of random sets of values, evaluate them against a corpus of known data, select the ones that scored the best (on both fraud detection and limiting the number of false positives), then cross breed the best few from each generation to produce a new generation of candidates. After a certain number of generations the best scoring set of values was deemed the winner.

创建用于测试的已知数据语料库是该系统的阿喀琉斯之踵。如果你等待退款,你在试图回应欺诈者时就会落后几个月,所以有人必须手动审查大量交易,以建立数据库,而不必等待太长时间。

这最终确定了绝大多数的欺诈行为,但在最容易欺诈的项目上,这一比例无法低于1%(考虑到90%的交易可能是欺诈,这已经相当不错了)。

我用perl完成了所有这些。在一个相当旧的linux机器上运行一次软件需要1-2个小时(20分钟通过WAN链路加载数据,其余时间用于处理)。任何给定代的大小都受到可用RAM的限制。我会一遍又一遍地运行它,稍微改变参数,寻找一个特别好的结果集。

总而言之,它避免了手动调整数十个欺诈指标的相对值所带来的一些失误,并且始终能够提出比我手动创建的更好的解决方案。AFAIK,它仍然在使用(大约3年后我写了它)。

我不知道家庭作业算不算…

在我学习期间,我们推出了自己的程序来解决旅行推销员问题。

我们的想法是对几个标准进行比较(映射问题的难度,性能等),我们还使用了其他技术,如模拟退火。

它运行得很好,但我们花了一段时间来理解如何正确地进行“复制”阶段:将手头的问题建模成适合遗传编程的东西,这对我来说是最难的部分……

这是一门有趣的课程,因为我们也涉猎了神经网络之类的知识。

我想知道是否有人在“生产”代码中使用这种编程。