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

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

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

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

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

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

I used a simple genetic algorithm to optimize the signal to noise ratio of a wave that was represented as a binary string. By flipping the the bits certain ways over several million generations I was able to produce a transform that resulted in a higher signal to noise ratio of that wave. The algorithm could have also been "Simulated Annealing" but was not used in this case. At their core, genetic algorithms are simple, and this was about as simple of a use case that I have seen, so I didn't use a framework for generation creation and selection - only a random seed and the Signal-to-Noise Ratio function at hand.

我年轻时就尝试过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代之后才重新组合。但没有什么能促使他们采取更好的策略。也许这是不可能的。

另一个有趣的事情是绘制适应度随时间变化的图表。有明确的模式，比如最大适合度在上升之前会下降。我从未见过一本进化论的书谈到这种可能性。

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

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

在大学期间，我们使用NERO(神经网络和遗传算法的结合)来教游戏中的机器人做出智能决策。非常酷。

我开发了一个基于多线程摆动的模拟机器人导航通过一组随机网格地形的食物源和矿山，并开发了一个基于遗传算法的策略，探索机器人行为的优化和机器人染色体的适者生存基因。这是使用每个迭代周期的图表和映射来完成的。

从那以后，我发展了更多的游戏行为。我最近为自己构建的一个示例应用程序是一个遗传算法，用于解决在英国寻找路线时的旅行销售人员问题，考虑到起始和目标状态，以及一个/多个连接点，延误，取消，建筑工程，高峰时间，公共罢工，考虑最快和最便宜的路线。然后为某一天的路线提供一个平衡的建议。

一般来说，我的策略是使用基于POJO的基因表示，然后为选择、突变、交叉策略和标准点应用特定的接口实现。我的适应度函数就会变得非常复杂，这是基于我需要作为启发式测量应用的策略和标准。

我还研究了将遗传算法应用于代码中的自动化测试，使用系统突变周期，其中算法理解逻辑，并尝试确定带有代码修复建议的错误报告。基本上，这是一种优化我的代码并提供改进建议的方法，以及一种自动发现新编程代码的方法。我还尝试将遗传算法应用于音乐制作和其他应用。

一般来说，我发现进化策略就像大多数元启发式/全局优化策略一样，一开始学习很慢，但随着解决方案越来越接近目标状态，只要你的适应度函数和启发式很好地对齐，在你的搜索空间内产生收敛，它们就会开始学习。