遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。
我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。
问题:
你用GA/GP解决过什么问题? 你使用了哪些库/框架?
我在寻找第一手的经验,所以请不要回答,除非你有。
遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。
我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。
问题:
你用GA/GP解决过什么问题? 你使用了哪些库/框架?
我在寻找第一手的经验,所以请不要回答,除非你有。
当前回答
几周前,我提出了一个关于SO的解决方案,使用遗传算法来解决图布局的问题。这是一个约束优化问题的例子。
同样在机器学习领域,我用c/c++从头开始实现了一个基于ga的分类规则框架。 我还在一个示例项目中使用了GA来训练人工神经网络(ANN),而不是使用著名的反向传播算法。
此外,作为我研究生研究的一部分,我已经使用GA来训练隐马尔可夫模型,作为基于em的Baum-Welch算法的额外方法(还是在c/c++中)。
其他回答
几周前,我提出了一个关于SO的解决方案,使用遗传算法来解决图布局的问题。这是一个约束优化问题的例子。
同样在机器学习领域,我用c/c++从头开始实现了一个基于ga的分类规则框架。 我还在一个示例项目中使用了GA来训练人工神经网络(ANN),而不是使用著名的反向传播算法。
此外,作为我研究生研究的一部分,我已经使用GA来训练隐马尔可夫模型,作为基于em的Baum-Welch算法的额外方法(还是在c/c++中)。
我使用遗传算法(以及一些相关技术)来确定风险管理系统的最佳设置,该系统试图阻止淘金者使用偷来的信用卡来购买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年后我写了它)。
在工作中,我遇到了这样一个问题:给定M个任务和N个dsp,如何将任务分配给dsp是最好的?“最佳”定义为“最大负载DSP的负载最小化”。有不同类型的任务,不同的任务类型有不同的性能分支,这取决于它们被分配到哪里,所以我将一组工作到dsp的分配编码为“DNA字符串”,然后使用遗传算法来“培育”我所能“培育”的最佳分配字符串。
它运行得相当好(比我之前的方法好得多,之前的方法是评估每个可能的组合……对于非平凡问题的大小,它将需要数年才能完成!),唯一的问题是无法判断是否已经达到了最优解。你只能决定当前的“最大努力”是否足够好,或者让它运行更长时间,看看它是否可以做得更好。
我开发了一个基于多线程摆动的模拟机器人导航通过一组随机网格地形的食物源和矿山,并开发了一个基于遗传算法的策略,探索机器人行为的优化和机器人染色体的适者生存基因。这是使用每个迭代周期的图表和映射来完成的。
从那以后,我发展了更多的游戏行为。我最近为自己构建的一个示例应用程序是一个遗传算法,用于解决在英国寻找路线时的旅行销售人员问题,考虑到起始和目标状态,以及一个/多个连接点,延误,取消,建筑工程,高峰时间,公共罢工,考虑最快和最便宜的路线。然后为某一天的路线提供一个平衡的建议。
一般来说,我的策略是使用基于POJO的基因表示,然后为选择、突变、交叉策略和标准点应用特定的接口实现。我的适应度函数就会变得非常复杂,这是基于我需要作为启发式测量应用的策略和标准。
我还研究了将遗传算法应用于代码中的自动化测试,使用系统突变周期,其中算法理解逻辑,并尝试确定带有代码修复建议的错误报告。基本上,这是一种优化我的代码并提供改进建议的方法,以及一种自动发现新编程代码的方法。我还尝试将遗传算法应用于音乐制作和其他应用。
一般来说,我发现进化策略就像大多数元启发式/全局优化策略一样,一开始学习很慢,但随着解决方案越来越接近目标状态,只要你的适应度函数和启发式很好地对齐,在你的搜索空间内产生收敛,它们就会开始学习。
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.