遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。
我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。
问题:
你用GA/GP解决过什么问题? 你使用了哪些库/框架?
我在寻找第一手的经验,所以请不要回答,除非你有。
遗传算法(GA)和遗传规划(GP)是一个有趣的研究领域。
我想知道你使用GA/GP解决的具体问题,以及如果你没有自己的库/框架,你使用了什么库/框架。
问题:
你用GA/GP解决过什么问题? 你使用了哪些库/框架?
我在寻找第一手的经验,所以请不要回答,除非你有。
当前回答
几周前,我提出了一个关于SO的解决方案,使用遗传算法来解决图布局的问题。这是一个约束优化问题的例子。
同样在机器学习领域,我用c/c++从头开始实现了一个基于ga的分类规则框架。 我还在一个示例项目中使用了GA来训练人工神经网络(ANN),而不是使用著名的反向传播算法。
此外,作为我研究生研究的一部分,我已经使用GA来训练隐马尔可夫模型,作为基于em的Baum-Welch算法的额外方法(还是在c/c++中)。
其他回答
我年轻时就尝试过GA。我用Python写了一个模拟器,工作原理如下。
这些基因编码了神经网络的权重。
神经网络的输入是检测触摸的“天线”。较高的数值表示非常接近,0表示不接触。
输出是两个“轮子”。如果两个轮子都向前,这个人也向前。如果轮子方向相反,他就会转向。输出的强度决定了车轮转动的速度。
生成了一个简单的迷宫。这真的很简单,甚至很愚蠢。屏幕下方是起点,上方是球门,中间有四面墙。每面墙都有一个随机的空间,所以总是有一条路。
一开始我只是随机挑选一些人(我认为他们是bug)。只要有一个人达到了目标,或者达到了时间限制,就会计算适合度。它与当时到目标的距离成反比。
然后我把它们配对,“培育”它们来创造下一代。被选择繁殖的概率与它的适应性成正比。有时,这意味着如果一个人具有非常高的相对适应性,就会与自己反复繁殖。
I thought they would develop a "left wall hugging" behavior, but they always seemed to follow something less optimal. In every experiment, the bugs converged to a spiral pattern. They would spiral outward until they touched a wall to the right. They'd follow that, then when they got to the gap, they'd spiral down (away from the gap) and around. They would make a 270 degree turn to the left, then usually enter the gap. This would get them through a majority of the walls, and often to the goal.
我添加的一个功能是在基因中放入一个颜色矢量来跟踪个体之间的相关性。几代之后,它们的颜色都是一样的,这说明我应该有更好的繁殖策略。
我试着让他们制定更好的策略。我把神经网络复杂化了——增加了记忆和其他东西。这没有用。我总是看到同样的策略。
我尝试了各种方法,比如建立单独的基因库,在100代之后才重新组合。但没有什么能促使他们采取更好的策略。也许这是不可能的。
另一个有趣的事情是绘制适应度随时间变化的图表。有明确的模式,比如最大适合度在上升之前会下降。我从未见过一本进化论的书谈到这种可能性。
在大学期间,我们使用NERO(神经网络和遗传算法的结合)来教游戏中的机器人做出智能决策。非常酷。
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.
我曾经使用一个GA来优化内存地址的哈希函数。这些地址的页面大小为4K或8K,因此它们在地址的位模式中显示出一定的可预测性(最低有效位全为0;最初的哈希函数是“粗笨的”——它倾向于每第三个哈希桶聚集一次命中。改进后的算法具有近乎完美的分布。
首先,Jonathan Koza的《遗传编程》(在亚马逊上)几乎是一本关于遗传和进化算法/编程技术的书,有很多例子。我强烈建议你去看看。
As for my own use of a genetic algorithm, I used a (home grown) genetic algorithm to evolve a swarm algorithm for an object collection/destruction scenario (practical purpose could have been clearing a minefield). Here is a link to the paper. The most interesting part of what I did was the multi-staged fitness function, which was a necessity since the simple fitness functions did not provide enough information for the genetic algorithm to sufficiently differentiate between members of the population.