遗传算法简介

Question

首先，让我澄清一下，我已经看到了This Genetic Algorithm Resource问题，但它没有回答我的问题。

我正在做一个生物信息学的项目。我必须获取有关细胞(E.Coli)的核磁共振谱的数据，并找出细胞中存在的不同分子(代谢物)。

为了做到这一点，我将使用R语言中的遗传算法。我没有时间去阅读关于遗传算法的大量书籍。见鬼！我甚至没有时间浏览小书(这是linked question不能回答的问题)。

因此，我需要了解一些资源，这些资源可以帮助我快速了解遗传算法是做什么的，以及它们是如何做到的。我已经阅读了Wikipedia entry，this webpage和一些关于这个主题的IEEE论文。

R中的任何工作代码(即使是在C中)或指向R模块(如果有的话)的指针都会很有帮助。

Answer 1

遗传算法的简要介绍(和自以为是的)在http://www.burns-stat.com/pages/Tutor/genetic.html

一个用R编写的简单GA可以在http://www.burns-stat.com/pages/Freecode/genopt.R上找到。“文档”在'S Poetry‘http://www.burns-stat.com/pages/Spoetry/Spoetry.pdf和代码中。

Answer 2

从你的问题中，我假设你有一些函数F(metabolites)，它会产生一个spectrum，但是你没有反函数F'(spectrum)来返回metabolites。metabolites的搜索空间很大，所以您希望尝试一种近似方法(例如遗传算法)，这样可以进行更有效的随机搜索，而不是强行使用它。

为了应用任何这样的近似方法，你必须定义一个得分函数，它比较目标光谱和试验光谱之间的相似性。这个函数越平滑，搜索效果就越好。如果它只能产生真/假，这将是一个纯粹的随机搜索，你最好使用暴力。

给定F和您的得分(也称为适应度)函数，您所需要做的就是构建一个可能的代谢物组合的群体，通过F运行它们，对所有结果谱进行评分，然后使用交叉和变异来生成一个结合了最佳候选者的新群体。选择如何进行交叉和突变通常是特定于领域的，因为您可以通过避免创建无意义的基因组来大大加快这一过程。最好的变异率将非常小，但也需要针对您的域进行调整。

在不了解你的领域的情况下，我不能说你的群体中的单个成员应该是什么样子，但它可以仅仅是代谢物的列表(如果这很有趣，它允许排序和重复)或所有可能的代谢物上的布尔值字符串(它的优点是顺序不变，并产生明显的交叉和突变可能性)。该字符串的缺点是，过滤掉无意义基因的成本可能更高(例如，只有1个代谢物或超过1000个代谢物可能没有意义)。避免制造无稽之谈要比仅仅赋予它低适合度更快。

如果你有F和你的评分函数，还有其他的近似方法。最简单的可能是Simulated Annealing。另一个我没有尝试过的是Bees Algorithm，它似乎是一种多起点模拟退火，其工作量由适应度加权(某种程度上介于SA和GA之间)。

Answer 3

我找到了PeterJ.Denning (American Scientist, vol 80, 1, pp 12-14)的文章“计算的科学:遗传算法”。如果你想了解遗传算法是做什么的，这篇文章是简单而有用的，而且只有3页可读！