进化算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。二十世纪六十年代以来被广泛应用于工业工程优化领域,并产生了深远的影响。单体型检测是生物信息学的一个重要分支,其中,单体型组装加权最小字符翻转(WMLF)问题指定个体联配的加权DNA片断数据、翻转权值和最小的SNP位点以推测出该个体的一对单体型。该问题是NP-难的,至今尚无实用的搜索寻优算法。NP-难问题一直是计算机理论研究的热点和难点。分支定界法是常分析求解NP-难问题的一种精确算法。而用分支定界法求解NP-难问题,所得待求解表达式在形式上则表现为回溯算法所衍生的一系列多变量递归。通过分析求解这些多变量递归式,我们可以得出算法的上界或下界,我们把此类问题称为多变量递归求解问题。传统的一些分析方法或者有缺陷,或者太复杂。本文主要的工作是针对上述的两个问题用进化算法来进行优化和求解。1.针对单体型组装的WMLF模型问题,本文提出了一种单目标的进化算法,该算法引入了权值矩阵并且设计了新的适应度函数。衡量算法好坏的评价指标有两个:重构率和运行时间。为了凸现进化算法的优越性又把解决单体型组装问题WMLF模型的经典算法-动态类聚算法来和进化算法作比较,可以从试验图表看出:无论是否存在空隙率,在两种算法运行时间相当的情况下,进化算法的重构率要明显高一些。结论是:用进化算法来处理单体型检测的WMLF模型问题比传统的方法要更加优越。2.针对多变量递归求解问题,相比于传统的分析方法提出了一种更为精确和简单的分析方法:首先引入适当的赋权函数,把多变量递归函数转化为单变量递归函数,然后提出有效的优化模型,把求解单变量递归函数问题进一步转化为一般的带约束条件的函数优化问题。传统的算法求得的解多为局部最优解,而本文采用的多目标进化算法采用多点并行搜索的搜索机制,每次迭代时借助交换和突变产生新个体,不断扩大搜索范围,因此很容易跳过局部最优解,而收敛于全局最优解。实验表明:在十次试验中,各个约束条件和目标函数的取值都是收敛的。从而证明了用进化算法解决此类问题的有效性。