精华内容
下载资源
问答
  • 面试之排序算法

    千人学习 2019-12-24 15:54:46
    排序算法是我们面试被问到最多的基础算法,本课程详细介绍了七种排序算法,包括插入排序、选择排序、冒泡排序、谢尔排序、快速排序、堆积排序和二路并归排序。每种算法都详细介绍了核心思想、详细步骤、时间复杂度和...
  • 遗传算法

    万次阅读 多人点赞 2019-04-06 21:41:47
    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下: 1、问题描述 编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示: 用MATLAB...

    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下:

    1、问题描述

    编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示:
    在这里插入图片描述
    用MATLAB做出函数的图像如下:
    在这里插入图片描述

    2、算法描述及实现

    2.1、遗传算法概述

    遗传算法(GA,Genetic Algorithm),也称为进化算法。遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作,因此不同于其他求解最优解的算法,遗传算法不存在求导和对函数连续性的限定,采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。

    以上是对遗传算法相对抽象的总结,为了更具体形象的解释遗传算法的一般原理,我们首先介绍一些生物学上的概念

    ①种群:不同生物个体形成的群体,生物的进化以群体的形式进行,这样的一个群体称为种群;

    ②个体:组成种群的单个生物;

    ③基因:带有遗传信息的DNA片段,可以通俗的将基因理解为一段信息,这段信息决定的生物个体的性状;

    ④表现型:根据基因形成的个体的外部表现;

    ⑤适应度:生物个体对于生存环境的适应程度,越适应那么其得以存活和繁衍的概率就越大;

    ⑥遗传:通过繁殖过程,子代将从父母双方各获取一部分基因,形成新的自己的基因,这个过程中,会发生基因的复制、交叉,也会以较低的概率发生基因突变;

    ⑦自然选择:物竞天择,适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少;

    ⑧进化:种群通过代际繁衍不断适应生存环境的过程,在这个过程中,以对外界环境的适应度为评判标准,生物的性状不断得到改良。

    了解了这些术语的含义,我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的,即生物只能改变自己去适应环境,那么在自然选择的过程中,适应度低的个体会被淘汰,适应度高的个体被保留,高适应度的父体与母体又有更高的概率繁衍出适应度高的子代,因此在一代又一代的繁衍之后,高适应度的个体在种群中所占的比例越来越大,种群就这样完成了进化。

    现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此,遗传算法的思路是,将要解决的问题模拟成一个生物进化的过程,通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例

    将(x, y)这一可能的解作为一个个体;将多峰函数的函数值f(x, y)作为个体的适应度;对(x, y)进行编码作为个体的基因;以适应度为标准不断筛选生物个体;通过遗传算子(如复制、交叉、变异等)不断产生下一代。如此不断循环迭代,完成进化。最终,根据设定的迭代次数,可得到最后一代种群,该种群中的个体适应度都较高,而多峰函数的最大值就有比较大的概率存在于这一群解中,以种群中适应度最高的个体作为问题的解,则可以说该解有比较高的概率就是我们希望求得的最优解。

    文字述说终究还是不如图表好理解,因此还是看图吧(下图将本题与自然遗传联系了起来):
    在这里插入图片描述
    通过以上描述,我们不难看出,遗传算法不能保证一定能求得最优解,而只能以一定的概率求最优解。但是使用遗传算法时,我们可以不用关心具体如何去找最优解,要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。

    2.2、算法的流程

    通过上文的阐述,对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤,并一一解析:

    第一步:随机产生一个种群,作为问题的初代解(通常,初代解可能与最优解相差较大,这是可以容忍的,只要保证初代解是随机产生的,以确保个体基因的多样性即可);

    第二步:寻找一种合适的编码方案对种群中的个体进行编码,可以选择如浮点数编码或二进制编码等常用编码方案(需要指出的是,不同的编码方案直接影响后续遗传算子的实现细节);

    第三步:以多峰函数的函数值 作为个体的适应度,计算种群中每个个体的适应度(算出的适应度将为后续的个体选择提供依据);

    第四步:根据适应度的高低选择参与繁衍的父体与母体,选择的原则是适应度越高的个体越可能被选中(以此不断淘汰适应度低的个体);

    第五步:对被选出的父体与母体执行遗传操作,即复制父体与母体的基因,并采用交叉、变异等算子产生出子代(在较大程度保留优秀基因的基础上,变异增加了基因的多样性,从而提高找到最优解的概率);

    第六步:根据一定的准则判断是继续执行算法,还是找出所有子代中适应度最高个体作为解返回并结束程序(判断的准则可以是设定的解的阈值、指定的迭代次数等)。
    在这里插入图片描述

    2.3、算法的编码实现

    2.3.1、编码

    本文采用的是二进制编码方式,这种编码方式编解码过程简单易行,相应的交叉算子、变异算子等操作用位运算即可实现。当然,它也有一定的缺点,比如连续性不够强。为保证求解的精度,本文使用14个bit为 编码,使用11个bit为 编码,两者组合成25个bit的最终结果。不难算出,该方式的编码精度可达千分位。具体的编码操作可总结为,将 或 的取值区间映射到0~2n-1这一整数范围,其中n表示编码位数, 或 在其取值区间的某点,相应的映射到整数区间中的某点,改点即为 或 的基因编码。程序如下:

    /*
        基因编码
        gene1       输入型参数,待编码的基因段1
        gene2       输入型参数,待编码的基因段2
        gene_code   输出型参数,基因编码
    
        返回值:当输入的基因不符合要求时返回false,否则返回true
    */
    static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code)
    {
        /* 判断基因是否合法 */
        if (!is_gene_legal(gene1, gene2))
            return false;
    
        /* 若基因合法则对其进行编码 */
        unsigned int gene1_code = (gene1 - GENE1_RANGE_LEFT) * (GENE1_CODE_MAX - 1) / (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT);
        unsigned int gene2_code = (gene2 - GENE2_RANGE_LEFT) * (GENE2_CODE_MAX - 1) / (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT);
        
        /* 组合基因片段 */
        *gene_code = (gene1_code << 11) | gene2_code;
    
        return true;
    }
    

    2.3.2、解码

    解码是编码的逆过程,无需赘述,程序如下:

    /*
        基因解码
        gene_code   输入型参数,基因编码
        gene1       输出型参数,解码后的基因段1
        gene2       输出型参数,解码后的基因段2
    
        返回值:当输入的基因编码不符合要求时返回false,否则返回true
    */
    static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2)
    {
        /* 判断基因编码是否合法 */
        if (!is_gene_code_legal(gene_code))
            return false;
    
        /* 若基因编码合法则对其进行解码 */
        unsigned int gene1_code = GET_GENE1_CODE(gene_code);
        unsigned int gene2_code = GET_GENE2_CODE(gene_code);
    
        *gene1 = (double)gene1_code * (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT) / (GENE1_CODE_MAX - 1) + GENE1_RANGE_LEFT;
        *gene2 = (double)gene2_code * (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT) / (GENE2_CODE_MAX - 1) + GENE2_RANGE_LEFT;
    
        return true;
    }
    

    2.3.3、计算适应度

    适应度函数也称评价函数,通常用于区分群体中个体好坏的标准。适应度高的,也就是优秀的个体有更大的几率参与繁衍,遗传自己的基因。一般的,适应度函数根据目标函数来确定,有时候直接将目标函数值作为适应度。这里,考虑到待求解的多峰函数,尖峰分布密集而且峰的直径很窄,这不利于遗传算法的收敛,因此本文不直接将多峰函数值作为适应度,而是利用对数函数将多峰函数进行平缓,并将平缓后的函数值作为目标函数。具体做法是,将多峰函数进行两次求对数,因此,多峰函数与适应度的关系可如下表示:
    在这里插入图片描述
    用MATLAB做出适应度函数图像如下:
    在这里插入图片描述
    对比前文中的图不难看出,图像得到了有效的平缓,同时不同峰之间也保持着一定的高低之别。值得一提的是,这里更主要的是给出优化遗传算法的一个思路,即可以在适应度函数上做文章。本题的适应度函数只是对多峰函数本身做了一个简单的变换,读者不妨思考一下,就本题而言有没有什么非常好的适应度函数。

    据上文所述,适应度求值函数如下:

    /*
        多峰函数:z = 21.5 + x *sin(4 * 3.1415926 * x) + y * sin(20 * 3.1415926 * y)
        适 应 度:log(log(z))
        约    束:-3.0 <= x <= 12.1; 4.1 <= y <= 5.8
        精    度:精确到千分位
    */
    double get_fitness(const double x, const double y)
    {
        return log(log(21.5 + x * sin(4 * PI * x) + y * sin(20 * PI * y)));
    }
    

    2.3.4、选择算子

    本文的选择算法采用了非常常用的“轮盘赌算法”,赌盘算法的原理非常简单明了。创建赌盘时,我们将种群中所有个体的适应度求和,不妨将得到的结果称为总和适应度。然后,将每个个体的适应度除以总和适应度,然后将得到的商逐个累加,每加一次就得到赌盘的一个边界,累加完成后总和为1。如下的饼状图可以更形象的表明赌盘的原理:
    在这里插入图片描述
    由上文所述,赌盘创建函数可如下编写:

    /*
        创建赌盘
        ga      遗传算法器指针
    */
    static void create_roulette(GA *ga)
    {
        /* 计算赌盘中的概率 */
        ga->roulette[0] = ga->fitness[0] / ga->sum_fitness;
    
        for (int num = 1; num < ga->population_num - 1; num++)
        {
            ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness;
        }
    
        ga->roulette[ga->population_num - 1] = 1.0;
    }
    

    再回到选择算子,选择算子需要赌盘作为基础,其运行时,会产生一个0到1的随机数,然后在赌盘中找到该数所在的区间,这个区间对应的个体即为被选中的个体。因此,适应度越高的个体被选中的几率越大,这是合理的。当然,也存在较小的概率选出适应度较低的个体,为了避免这种情况,本文引入了竞争机制,即一次选择的过程选出2个个体,再取其中适应度较高的那个个体,具体的程序如下:

    /*
        基因选择函数
        ga      遗传算法器指针
        返回值:返回使用轮盘赌的方式选出的个体(编号)
        说  明:选择策略为轮盘赌+随机竞争
    */
    static unsigned int select(GA *ga)
    {
        unsigned int index1 = 0, index2 = 0;
    
        /* 产生一个[0.0, 1.0]之间的浮点数 */
        double selector1 = rand() * 1.0 / RAND_MAX;
        double selector2 = rand() * 1.0 / RAND_MAX;
    
        /* 找出被选中的个体的索引 */
        for (; selector1 > ga->roulette[index1]; index1++);
        for (; selector2 > ga->roulette[index2]; index2++);
    
        return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2);
    }
    

    2.3.5、交叉算子

    遗传算法的交叉操作实质上是按某种方式交换父体和母体的部分基因,常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉及算术交叉等。本文选用两点交叉法,实现过程既不复杂,也有较好的随机性,该方法可由下图示意:
    在这里插入图片描述
    图中虚线指出的两个交叉点是随机产生的。具体程序如下:

    /*
        交叉函数
        ga          遗传算法器指针
        one         输出型参数,待交叉基因
        another     输出型参数,待交叉基因
        说明:
        1.对传入的基因编码执行两点交叉操作
    */
    static void cross(GA *ga, unsigned int *one, unsigned int *another)
    {
        /* 1.随机产生两个交叉点的位置 */
        unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char min_pos = min(pos1, pos2);
        unsigned char max_pos = max(pos1, pos2);
    
        /* 2.截出需要交换的基因段 */
        unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1);
        unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1);
        unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1));
    
        /* 3.执行交叉操作 */
        *one = (*one & mask) | another_gene_seg;
        *another = (*another & mask) | one_gene_seg;
    }
    

    2.3.6、变异算子

    在自然界中,基因变异可以增加个体的多样性,这对于遗传算法来说是增加了个体的随机性,可以增加找到最优解的概率。本文采用的变异算子所做的操作是随机选择基因的某一位进行反转,程序如下:

    /*
        变异函数
        gene_code       输入型参数
        说明:
        1.对传入的基因编码执行变异操作
        2.随机选择基因编码中的一位做反转操作
    */
    static void mutate(unsigned int *gene_code)
    {
        unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH);
        *gene_code ^= mutate_bit;
    }
    

    2.3.7、繁殖函数及进化函数

    遗传算法的主要算子都在上文中分析过了,下面要做的就是根据遗传算法的流程将这些算子整合起来以实现算法功能。在本文中,这其中涉及到两个关键的函数,即繁殖函数和进化函数。繁殖函数包括基因的复制、交叉及变异,同时本文还采用了子代竞争策略,即父代产生的两个子代个体仅保留适应度最高的,程序如下:

    /*
        繁殖函数
        ga       遗传算法器指针
        father   从种群中选出的父体
        mother   从种群中选出的母体
        返回值:  适应度最高的子代的基因编码
        说明: 
        1.一对父体与母体将繁殖出一对子代
        2.选择出适应性更好的子代返回
    */
    static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother)
    {
        unsigned int son1 = ga->gene_code[father];
        unsigned int son2 = ga->gene_code[mother];
    
        /* 1.交叉 */
        cross(ga, &son1, &son2);
    
        /* 2.变异 */
        mutate(&son1);
        mutate(&son2);
    
        /* 3.子代竞争 */
        double son1_gene1, son1_gene2, son2_gene1, son2_gene2;
        gene_decode(son1, &son1_gene1, &son1_gene2);
        gene_decode(son2, &son2_gene1, &son2_gene2);
    
        return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2;
    }
    

    进化函数则实现了遗传算法的一次完整的迭代过程,根据上文给出的遗传算法流程图,不难进行如下编码:

    /*
        进化函数
        ga      遗传算法器指针
    */
    static void evolve(GA *ga)
    {
        /* 1.申请暂存子代基因编码的内存 */
        unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int));
        
        /* 2.精英保留(将上一代中适应度最高的个体的基因编码保留) */
        descendants[0] = ga->gene_code[ga->best_individual];
        
        /* 3.选择合适的父体与母体 */
        unsigned int father = select(ga);
        unsigned int mother = select(ga);
    
        /* 4.繁殖(包含交叉与变异) */
        for (int num = 1; num < ga->population_num; num++)
            descendants[num] = inherit(ga, father, mother);
    
        /* 5.将子代记录到ga中并进行基因解码(使新一代的基因编码与基因对应) */
        for (int num = 0; num < ga->population_num; num++)
        {
            ga->gene_code[num] = descendants[num];
            gene_decode(ga->gene_code[num], &ga->gene[num].gene1, &ga->gene[num].gene2);
        }
        
        /* 5.更新种群适应度 */
        fit(ga);
        
        /* 6.更新赌盘 */
        create_roulette(ga);
    
        /* 7.释放之前申请的空间 */
        free(descendants);
    }
    

    3、运行结果及分析

    至此,本文已经给出了一个遗传算法的C语言实现的所有关键程序。下面就调用编写的遗传算法进行测试。本文将创建含有100个个体的种群,并进行100代迭代以求解多峰函数的最大值,一次完整的调用本文实现的遗传算法的程序如下所示:

    /* 创建遗传算法器 */
    GA *ga = create_ga(get_fitness, 100);
    
    /* 初始化遗传算法器 */
    ga->init(ga);
    
    /*迭代100代*/
    for (int i = 0; i < 100; i++)
    ga->evolve(ga);
    
    /*销毁遗传算法器*/
    delete_ga(ga);
    

    经多次调用测试,算法执行的结果较为稳定,所得的多峰函数最大值大多在38以上,多次运行结果中最好的解为38.849744,对应的坐标为(11.625331, 5.725256)。将迭代求得的最大值用MATLAB作图如下:
    在这里插入图片描述
    为验证是否找到了最优解,用MATLAB遍历求出该多峰函数在给定定义域内的最大值为38.8501,与本文求出的结果相差0.000356,可见本文实现的遗传算法表现还不算太差。

    文中给出的程序比较散,这里给出完整程序的下载链接

    展开全文
  • 生物信息算法笔记

    万次阅读 2018-05-19 22:14:17
    入门生物信息学,选了一条比较难的路,直接从底层算法开始,这种做法其实不太明智。读了"Algorithms on Strings, Trees and Sequences",一本厚厚的算法书,后半部分其实读得有些粗糙。今天读完了第一遍,...

    入门生物信息学,选了一条比较难的路,直接从底层算法开始,这种做法其实不太明智。读了"Algorithms on Strings, Trees and Sequences",一本厚厚的算法书,后半部分其实读得有些粗糙。今天读完了第一遍,总的来说还是有些收获,将笔记记录于此。

    全书总共分为四部分:基本字符串算法、后缀树算法、非精确匹配算法、映射与测序。基本字符串算法以KMP为代表,这个是基本功,而且很久之前的博客竟然正好记录了这个算法;后缀树算法在前几篇博客专门进行了描述;非精确匹配以动态规划为基础,这个也算是老朋友,近期的博客也专门讨论了这个主题,本文也将继续延伸这个话题;映射与测序,也将在此进行讨论。因此本文分为两大部分:非精确匹配的进一步讨论、映射与测序。

    整理得有点乱,甚至有些部分直接用的截图,以后有机会再进一步整理。本文的主要目的是记录一些核心思路,方便今后回顾。

     

    非精确匹配的进一步讨论

    Refining Core String Edits and Alignments

    空间优化:Computing alignments in only linear space

    那么转移方程可以写成如下形式:

    由转移方程可知,空间可压缩一维。

     

    时间优化:Faster algorithms when the number of differences is bounded 

    之前在后缀树的应用里讨论过 k-mismatch的问题,这里讲讨论 k-difference 的问题,区别在于:前者只允许替换,而后者还允许增删。

    两类特殊的 k-difference问题:

    k-difference global alignment 

    下图为动态规划转移表,(0, 0)开始的对角线为主对角线,其左下方的为负对角线,其右上方的为正对角线。若最多允许k 个不同,则最终结果必然从 -k对角线 至 k对角线 之间的条带中的状态推导而来,因为这个条带以外的状态,其匹配已经出现了超过k个不同的字符。

     

    Exclusion methods: fast expected running time 

    先排除一些不可能匹配成功的片段,进而优化计算速度。总的思路如下:

    具体的算法很多,这里描述两个典型的:BYP算法、CL算法。

    BYP算法:

     

    CL算法:

     

    Yet more suffix trees and more hybrid dynamic programming 

    有两个典型的问题。

    The P-against-all problem Given strings P and T, compute the edit distance between P and every substring T' of T. 

    The threshold all-against-all problem Given strings P and T and a threshold d, find every pair of substrings P' of P and T' of T such that the edit distance between P' and T' is less than d. 

    思路:

    对于P-against-all 问题,可以先构建出T的后缀树,在这个后缀树上计算与P的编辑距离,即在后缀树上进行深度优先的动态规划。优点在于可以省去很多重复计算。对于all-against-all 问题,请参考书上相关章节(12.4.2)。

     

    LCS 的快速算法

    其实就是将LCS 问题转化为LIS 问题,而LIS 可以在O(N*logN) 内实现,因此LCS 也变成了O(N*logN)。

    LIS的O(N*logN)算法

    D为数字序列,D的一个cover定义为D的下降序列的集合,且这个集合涵盖了S的序列全部。cover的大小为这个集合中下降序列的个数。

    如:S= 5, 3, 4, 9, 6, 2, 1, 8, 7, 10。则 {5, 3, 2, 1}; {4}; {9, 6}; {8, 7}; {10} 是S 的一个cover,这个cover的大小为5。

    根据定理12.5.4可知,构建最小cover的过程可以采用二分搜索法,因此最终的时间复杂度为O(N*logN)。

     

    如何将LCS 问题转归为LIS 问题

    定义:r(i)表示S1[i]这个字符 在S2中出现过多少次,r=∑r(i)。

    定义:t(x)表示x 这个字符在S2 中出现的位置的列表,并且顺序为从大到小排列。

    举例:S1=abacx, S2=baabca,则 r=3+2+3+1+0=9,t(a)=(6,3,2),t(b)=(4,1)。

    基于S1构建列表SS:对于S1中每个位置i,用t(S1[i])列表进行替换,最终可以得到长度为r的新列表SS。

    举例:对于以上S1和S2,构建的SS为:(6,3,2,4,1,6,3,2,5)。

    定理:SS的LIS 与S1和S2的LCS对应。

     

    拓展:多个字符串的LCS问题,可以用类似的方法转换成LIS问题。

     

    Extending the Core Problem

    主要讨论了3个问题:Parametric sequence alignment 、Computing suboptimal alignments  和 Chaining diverse local alignments。此处主要看下 Parametric sequence alignment。

    实际工作中,会遇到不少带参数的字符串匹配问题。

     

    Multiple String Comparison

    将字符串对齐问题(非精确匹配)从2个字符串拓展到多个字符串,即为多字符串比较问题。实际上从生物学角度来看,多个字符串的问题与两个字符串的问题是相反的。

    两个生物学事实。

    The first fact of biological sequence analysis: In biomolecular sequences (DNA, RNA, or amino acid sequences), high sequence similarity usually implies significant functional or structural similarity. 

    The second fact of biological sequence comparison: Evolutionarily and functionally related molecular strings can differ significantly throughout much of the string and yet preserve the same three-dimensional structure(s), or the same two-dimensional substructure(s) (motifs, domains), or the same active sites, or the same or related dispersed residues (DNA or amino acid). 

    第一个事实是两个字符串问题的生物学基础,第二个事实是间隔问题及多个字符串问题的生物学基础。

    Multiple String Comparison的3大应用:蛋白家族(及超级家族)的呈现、DNA或蛋白质中与结构(或功能)相关的保守片段的识别和呈现、DNA或蛋白质的进化史的推导(进化树的形式呈现)(进化树的内容本文略去)。

     

    Family and superfamily representation

    常用的呈现方式有3种:profile representations, consensus sequence representations, and signature representations. 

     

    profile representations

    定义:Given a multiple alignment of a set of strings, a profile for that multiple alignment specifies for each column the frequency that each character appears in the column. A profile is sometimes also called a weight matrix in the biological literature. 

    举例:下图是对齐后的结果。

    对每列的各个字符计算出现频率,得到下表,即为profile representations。

    对于新字符串aabbc,其相对于profile的最佳对齐方式应当如下图所示。

    解决思路:

    For a character y and column j, let p(y, j) be the frequency that character y appears in column j of the profile, and let S(x, j) denote ∑y[s(x, y) x p(y, j)], the score for aligning x with column j. 

    Let V(i, j) denote the value of the optimal alignment of substring S[l..i] with the first j columns of C. 

    初始条件:

     

    转移方程:

     

    signature representations

    一些保守序列可以用类似于正则表达式的形式表示,这种表示即为signature representations。如某个motif 可表示如下:

    [&H][&A]D[DE]xn[TSN]x4[QK]Gx7[&A]

    "&" stands for any amino acid from the group (/, L,V, M, F, Y, W), "x" stands for any amino acid, and alternative amino acids are bracketed together. The subscript on x gives the length of a permitted substring; "n" indicates that any length substring is possible. 

     

    consensus sequence representations

    找一个公认的有代表性序列,作为该蛋白家族的呈现,即为consensus sequence representations。

    Steiner consensus strings 

    D(Si, Sj) denotes the weighted edit distance of strings Si, and Sj. 

    Given a set of strings S, and given another string S', the consensus error of a string S' relative to S is E(S') = ∑si∈s D(S' Si). Note that S' need not be from S. 

    Given a set of strings S, an optimal Steiner string S* for <S is a string that minimizes the consensus error E(S*) over all possible strings. 

     

    Multiple string alignments 的计算

    给定一种对齐方式,对于其中任意两个字符串计算分值,最后将所有分值求和,得到总分值SP(sum of pairs),目标是使得SP最小化。

    这个问题虽然可以使用动态规划准确求解,但是时间复杂度是指数级的,这是个NP 完全问题。书上给出了三个字符串的SP求解示例程序(pascal语言)。

    此外,书中还给出了bounded-error approximation 的方法(界定误差的近似求法)——center star法。感兴趣的请直接参考章节14.6.2。

     

    Sequence Databases and Their Uses

    这个部分介绍了常见的几个数据库 及其背后的部分算法,如:FASTA、BLAST、PAM、BLOCKS和BLOSUM 等。

    本文此处不进行记录,直接看书吧,或者在实际操作中去领会。

     

    映射与测序

    Mapping

    概念

    以下概念摘自网络资源(具体来源不详)。

    遗传图谱(genetic maps):某一物种的染色体图谱(也就是我们所知的连锁图谱),显示所知的基因和/或遗传标记的相对位置,而不是在每条染色体上特殊的物理位置。采用遗传学分析方法将基因或其它DNA标记按一定的顺序排列在染色体上,这一方法包括杂交实验,家系分析。标记间的距离(遗传图距)用减数分裂中的交换频率来表示,单位为厘摩Centi-Morgan, cM), 每单位厘摩定义为1%交换率。遗传学图谱的解像度(分辨率)低,大约只能达到100万碱基对(1Mb)的水平。

    物理图谱(physical maps):顾名思义,是DNA中一些可识别的界标(如限制性酶切位点、基因等)在DNA上的物理位置,图距是物理长度单位,如染色体的带区、核苷酸对的数量等。

    两者异同:
      ①遗传图谱是基于重组频率,物理图谱是基于直接测量的DNA结构。
      ②减数分裂重组的频率并不统一沿大多数染色体。有一些热点和冷点在重组和/或突变。热点和冷点会导致相当大的格律失真时,遗传图谱和物理地图并排排列时。
      ③遗传图谱表示的是基因或标记间的相对距离,以重组值表示,单位CM
      ④物理图谱表示的是基因或标记间的物理距离,距离的单位为长度单位,如μm或者碱基对数(bp或kp)等。

    简而言之,前者是描述的基因相对位置,后者是具体的碱基位置。

    STS是序列标记位点(sequence-tagged site)的缩写,是指染色体上位置已定的、核苷酸序列已知的、且在基因组中只有一份拷贝的DNA短片断,一般长200bp-500bp。它可用PCR方法加以验证。将不同的STS依照它们在染色体上的位置依次排列构建的图为STS图。在基因组作图和测序研究时,当各个实验室发表其DNA测序数据或构建成的物理图时,可用STS来加以鉴定和验证,并确定这些测序的DNA片段在染色体上的位置;还有利于汇集分析各实验室发表的数据和资料,保证作图和测序的准确性。

    EST是表达序列标签(expressed sequence tag)的缩写,在人类基因组测序工作中,有一个区别于"全基因组战略"的"cDNA战略",即只测定转录的DNA序列。此时,须从cDNA文库中获取一些长为300-400各碱基序列作为表达序列标签,其作用相当于全基因组测序时的序列标记位点(STS),即可用来验证和整理不同实验室发表的cDNA测序资料。两端又重叠序列的EST可以装配成全长的cDNA序列。特定的EST序列有时可代表特定的cDNA。

    辐射性杂交制图技术(radiation-hybrid mapping)是一种体细胞杂交技术,适用于构建人类基因组长范围内的高分辨率连续物理图谱。利用高剂量的X射线将候选染色体打断成若干片段,含有这种片段的细胞可与仓鼠细胞形成杂交克隆。在这种杂交中,人类染色体片段被插入到仓鼠染色体的中间部分,因此大部分克隆片段在进行有丝分裂时处于稳定的状态。

    利用类似于遗传重组原理和最大似然性的统计学方法来计算存在于DNA片段上的多态性或非多态性标记之间的断点频率,以此估计标记之间的距离,并建立人类基因组拷贝库---体细胞杂交系统。可根据不同要求构建出断裂程度不同的多套拷贝,从而得到不同分辨率的放射杂交图。总之,辐射性杂交是建立在受到X射线照射的供体细胞与非放射线处理的受体细胞融合基础上的一种体细胞遗传学方法。

    Physical mapping:STS-content mapping and ordered clone libraries

    下图中有4个STS,其真实顺序如下图所示,但是这个顺序我们事先是不知道的,需要结合后面的计算去推断出来。下图还包含3个clone片段。

    匹配出3个片段各自包含了哪些STS之后,可得到下图的01矩阵,由于事先并不知道各个STS的排列顺序,因此此时顺序是打乱的。

    找出一种排列顺序,使得每行中的1具有连续性,成为一个独立的块。这也就实现了STS顺序的重建。

    Physical mapping: radiation-hybrid mapping 

    这个是加强版的STS顺序问题,每个细胞具有多个不相邻的片段,如下图所示。

    由于不知道真实顺序,匹配各个STS后,得到以下的01矩阵。

    重建STS顺序的方法:traveling salesman tour。

    构建无向图,边 e(u ,v)表示编号为u与v的STS 列,之间有几个01值不相同。为了方便起见,此处略去5-7这3个STS,构建的无向图如下所示。

    找一个从S出发且经历所有节点的路径,且经历的路径总长度(即所有e(u ,v)之和)最短,这条路径的顺序很可能就是STS的顺序。上图求得的最短路径为:S-3-1-4-2,长度为6,对应的连续块的数量为4。遗憾的是并不是真实的顺序1234(真实顺序的连续块的数量竟然更大…)。(期待更好的方法解决这个问题)

    Physical mapping: fingerprinting for general map construction 

    探针问题与STS问题类似,但是探针在DNA序列中可以重复出现,如下图所示。

    上图最终构造的01矩阵是5*4的规模,重建出其真实顺序的难度比较大。有不少文章提出过解决方案,书中描述了一种贪心方法,请参考章节16.8。

     

    Sequencing

    引物步移(primer walking):一种长链DNA测序的策略。根据已测出的序列结构设计测序引物,按第一轮测序得出的新序列,再设计引物进行第二轮测序,如此重复,直至获得全序列。

    嵌套缺失法(Nested deletion) : 该法基本原理是基因DNA链的一端与载体相连固定,另一端在核酸外切酶的作用下随着时间的延长,较匀速地消化变短。这样可人为获得一组长度不等(如依次相差200~250 bp)的从一端开始缺失的DNA片段。它们从缺失端开始的测序可读部分宛如拉杆天线的一段套管,最长片段(未被核酸外切酶作用的DNA)相当于拉杆天线的全长,它的可读部分相当于拉杆天线的最远端的套管。这些DNA片段从长至短虽然依次相差200~250 bp,但从缺失端可读取300~500 bp序列,重叠部分便可准确无误地将相邻段重合拼接。测序中,它们的引物相同因而可以很方便地首先读出引物序列,找出该DNA片段的起始,起始段DNA序列也正是前一较长DNA片段可读的后一部分序列,它们如此重叠嵌套,便可准确测出整个基因(或长DNA链)的序列。

    书中还提到了 "Top-down, bottom-up sequencing( the picture using YACs)" 、"Shotgun DNA sequencing" 等方法的描述。这些东西将会重新学习一遍,之后会系统地学一下WGS的知识。

     

    ----------------------------------------------------------------------------------

    2018/10/02 补充

    学习路上吃了很多亏,无法及时的将所学的东西运用起来。时间不够用啊,我的专业不是这个方向,有很多事情等着我去做呢,这个时候最高效的方式是先了解如何使用,然后练习即可。学有余力再去专研其理论知识(人生苦短)。以今天的经验教训来看,本文的这些东西(包括之前字符串的非精确匹配、3篇后缀树系列博客),以后不要再纠结了,尽量不要把时间花在这方面。

     

    展开全文
  • 详解遗传算法(含MATLAB代码)

    万次阅读 多人点赞 2019-05-29 11:30:47
    一、遗传算法概述 二、遗传算法的特点和应用 三、遗传算法的基本流程及实现技术 3.1 遗传算法的基本流程 3.2 遗传算法的实现技术 1.编码 2.适应度函数 3.选择算子 4.交叉算子 5.变异算子 6.运行参数 四、...

    目录

    一、遗传算法概述

    二、遗传算法的特点和应用

    三、遗传算法的基本流程及实现技术

    3.1 遗传算法的基本流程

    3.2 遗传算法的实现技术

    1.编码

    2.适应度函数

    3.选择算子

    4.交叉算子

    5.变异算子

    6.运行参数

    四、遗传算法的基本原理

    4.1 模式定理

    4.2 积木块假设

    五、遗传算法编程实例(MATLAB)


    一、遗传算法概述

            遗传算法(Genetic Algorithm,GA)是进化计算的一部分,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法简单、通用,鲁棒性强,适于并行处理。

    二、遗传算法的特点和应用

       遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法,与传统的优化算法相比,具有以下特点:

    1. 以决策变量的编码作为运算对象。

        传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算,但遗传算法是使用决策变量的某种形式的编码作为运算对象。这种对决策变量的编码处理方式,使得我们在优化计算中可借鉴生物学中染色体和基因等概念,可以模仿自然界中生物的遗传和进化激励,也可以很方便地应用遗传操作算子。

    2. 直接以适应度作为搜索信息。

        传统的优化算法不仅需要利用目标函数值,而且搜索过程往往受目标函数的连续性约束,有可能还需要满足“目标函数的导数必须存在”的要求以确定搜索方向。

        遗传算法仅使用由目标函数值变换来的适应度函数值就可确定进一步的搜索范围,无需目标函数的导数值等其他辅助信息。直接利用目标函数值或个体适应度值也可以将搜索范围集中到适应度较高部分的搜索空间中,从而提高搜索效率。

    3. 使用多个点的搜索信息,具有隐含并行性

        传统的优化算法往往是从解空间的一个初始点开始最优解的迭代搜索过程。单个点所提供的搜索信息不多,所以搜索效率不高,还有可能陷入局部最优解而停滞;

        遗传算法从由很多个体组成的初始种群开始最优解的搜索过程,而不是从单个个体开始搜索。对初始群体进行的、选择、交叉、变异等运算,产生出新一代群体,其中包括了许多群体信息。这些信息可以避免搜索一些不必要的点,从而避免陷入局部最优,逐步逼近全局最优解。

    4. 使用概率搜索而非确定性规则。

       传统的优化算法往往使用确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移方向和转移关系,这种确定性可能使得搜索达不到最优店,限制了算法的应用范围。

       遗传算法是一种自适应搜索技术,其选择、交叉、变异等运算都是以一种概率方式进行的,增加了搜索过程的灵活性,而且能以较大概率收敛于最优解,具有较好的全局优化求解能力。但,交叉概率、变异概率等参数也会影响算法的搜索结果和搜索效率,所以如何选择遗传算法的参数在其应用中是一个比较重要的问题

    综上,由于遗传算法的整体搜索策略和优化搜索方式在计算时不依赖于梯度信息或其他辅助知识,只需要求解影响搜索方向的目标函数和相应的适应度函数,所以遗传算法提供了一种求解复杂系统问题的通用框架。它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于各种领域,包括:

    • 函数优化
    • 组合优化生产调度问题
    • 自动控制
    • 机器人学
    • 图像处理(图像恢复、图像边缘特征提取......)
    • 人工生命
    • 遗传编程
    • 机器学习

    三、遗传算法的基本流程及实现技术

       基本遗传算法(Simple Genetic Algorithms,SGA)只使用选择算子、交叉算子和变异算子这三种遗传算子,进化过程简单,是其他遗传算法的基础。

    3.1 遗传算法的基本流程

    1.  通过随机方式产生若干由确定长度(长度与待求解问题的精度有关)编码的初始群体;
    2. 通过适应度函数对每个个体进行评价,选择适应度值高的个体参与遗传操作,适应度低的个体被淘汰;
    3. 经遗传操作(复制、交叉、变异)的个体集合形成新一代种群,直到满足停止准则(进化代数GEN>=?);
    4. 将后代中变现最好的个体作为遗传算法的执行结果。

                                                       

    其中,GEN是当前代数;M是种群规模,i代表种群数量。

    3.2 遗传算法的实现技术

    基本遗传算法(SGA)由编码、适应度函数、遗传算子(选择、交叉、变异)及运行参数组成。

    1.编码

    (1)二进制编码

    二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。

    优点:编、解码操作简单,遗传、交叉便于实现

    缺点:长度大

    (2)其他编码方法

    格雷码、浮点数编码、符号编码、多参数编码等

    2.适应度函数

    适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。

    3.选择算子

    通过选择算子模拟“优胜劣汰”,适应度高的个体被遗传到下一代的概率较大,适应度低的算子被遗传到下一代的概率较小。

    常用的选择算法:轮盘赌选择法,即令\sum f_i表示群体的适应度函数值的总和,f_i表示群体中第i个染色体的适应度值,则它产生后代的能力刚好为其适应度值所占的份额\frac{f_i}{\sum f_i}

    4.交叉算子

    • 交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体;
    • 交叉运算是遗传算法区别于其他进化算法的重要特征,是产生新个体的主要方法。

    在交叉之前需要将群体中的个体进行配对,一般采取随机配对原则。

    常用的交叉方式:

    • 单点交叉
    • 双点交叉(多点交叉,交叉点数越多,个体的结构被破坏的可能性越大,一般不采用多点交叉的方式)
    • 均匀交叉
    • 算术交叉

    5.变异算子

    遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。

    就遗传算法运算过程中产生新个体的能力方面来说,交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力;而变异运算只是产生新个体的辅助方法,但也是必不可少的一个运算步骤,它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索,从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。

    6.运行参数

    • 编码长度。编码长度取决于问题解的精度,精度越高,编码越长;
    • 种群规模。规模小,收敛快但降低了种群的多样性,N=20-200
    • 交叉概率。较大的交叉概率容易破坏种群中已形成的优良结构,使搜索具有太大随机性;较小的交叉概率发现新个体的速度太慢,一般取值为P_c=0.4-0.99
    • 变异概率。变异概率太小,则变异操作产生新个体的能力和抑制早熟现象的能力会较差;变异概率过高随机性过大,一般建议取值范围为0.005~0.01
    • 终止进化代数。算法运行结束的条件之一,一般取100~1000

    四、遗传算法的基本原理

    4.1 模式定理

    定义1:模式H是由{0,1,*}中的元素组成的一个编码串,其中“*”表示通配符,既能被当作0,也能被当作1。e.g. H=10**1

    定义2:模式的阶,是指模式中所含有0,1的数量,记作O(H)  e.g. O(11*00**)=4

    定义3:模式的矩,即模式的长度,是指模式中从左到右第一个非*位和最后一个非*位之间的距离,记作\delta (H)

              e.g. \delta (01**1)=3;\delta (**0*1)=2;\delta (***1**)=1

    定义4:模式的适应度值,是群体中所包含的全部个体的适应度值的平均值。

    定义5:在选择、交叉、变异遗传算子的作用下,低阶、长度短、超过群体平均适应值的模式的生存数量,将随迭代次数以指数规律增长。

    模式定理不仅说明基因块的样本呈指数增长,也说明用遗传算法寻求最优样本的可能性,但它并未指出遗传算法一定能够寻求到最优解,积木块假设说明了遗传算法的寻找最优解的能力。

    4.2 积木块假设

    具有低阶、定义长度短,且适应度值高于群体平均适应度值的模式称为基因块或积木块。

    积木块假设:个体的基因块通过选择、交叉、变异等遗传算子的作用,能够相互拼接在一起,形成适应度更高的个体编码串。

    积木块假设说明了用遗传算法求解各类问题的基本思想,即通过积木块直接相互拼接在一起能够产生更好的解。

    五、遗传算法编程实例(MATLAB)

    https://github.com/strawberry-magic-pocket/Genetic-Algorithm.git

     

    展开全文
  • 蚁群算法原理以及应用

    万次阅读 多人点赞 2019-03-09 09:05:12
    本文首先对启发式算法和蚁群算法的由来以及含义做简要介绍,然后讲述蚁群算法的求解原理,再分别用两个案例解释蚁群算法,观察蚁群算法的求解结果;通过对蚁群算法的使用方法做简要介绍,可以了解近似解的含义以及正...

    关键词:启发式算法 蚁群算法 迭代 正反馈
    1.蚁群算法(ant colony algorithm,ACA)起源和发展历程
    Marco Dorigo等人在研究新型算法的过程中,发现蚁群在寻找食物时,通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标,于是在1991年在其博士论文中首次系统地提出一种基于蚂蚁种群的新型智能优化算法“蚂蚁系统(Ant system,简称AS)”,后来,提出者及许多研究者对该算法作了各种改进,将其应用于更为广泛的领域,如图着色问题、二次分配问题、工件排序问题、车辆路径问题、车间作业调度问题、网络路由问题、大规模集成电路设计等。近些年来,M.Dorigo等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化(Ant Colony Optimization,简称ACO)”,并将所有符合ACO框架的算法称为“蚁群优化算法(ACO algorithm)”。
    初始蚁群爬行路线最终蚁群爬行路线
    具体来说,各个蚂蚁在没有事先告知食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)信息素能够让其他蚂蚁感知从而起到一个引导的作用。通常多个路径上均有信息素时,蚂蚁会优先选择信息素浓度高的路径,从而使浓度高的路径信息素浓度更高,形成一个正反馈。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。最终,信息素浓度最高的路径即是最终被蚂蚁选中的最优路径。
    与其他算法相比,蚁群算法是一种比较年轻的算法,具有分布式计算、无中心控制、个体之间异步间接通信等特点,并且易于与其他优化算法相结合,经过不少仁人志士的不断探索,到今天已经发展出了各式各样的改进蚁群算法,不过蚁群算法的原理仍是主干。
    2蚁群算法的求解原理
    基于上述对蚁群觅食行为的描述,该算法主要对觅食行为进行以下几个方面模拟:
    1模拟的图场景中包含了两种信息素,一种表示家,一种表示食物的地点,并且这两种信息素都在以一定的速率进行挥发。
    2 每个蚂蚁只能感知它周围的小部分地方的信息。蚂蚁在寻找食物的时候,如果在感知范围内,就可以直接过去,如果不在感知范围内,就要朝着信息素多的地方走,蚂蚁可以有一个小概率不往信息素多的地方走,而另辟蹊径,这个小概率事件很重要,代表了一种找路的创新,对于找到更优的解很重要。
    3、蚂蚁回窝的规则与找食物的规则相同。
    4、蚂蚁在移动时候首先会根据信息素的指引,如果没有信息素的指引,会按照自己的移动方向惯性走下去,但也有一定的机率改变方向,蚂蚁还可以记住已经走过的路,避免重复走一个地方。
    5、蚂蚁在找到食物时留下的信息素最多,然后距离食物越远的地方留下的信息素越少。找到窝的信息素留下的量的规则跟食物相同。蚁群算法有以下几个特点:正反馈算法、并发性算法、较强的鲁棒性、概率型全局搜索、不依赖严格的数学性质、搜索时间长,易出现停止现象。
    蚂蚁转移概率公式:
    在这转移概率公式里插入图片描述
    公式中:是蚂蚁k从城市i转移到j的概率;α,β分别为信息素和启发式因子的相对重要程度;为边(i,j)上的信息素量;为启发式因子;为蚂蚁k下步允许选择的城市。上述公式即为蚂蚁系统中的信息素更新公式,是边(i,j)上的信息素量;ρ是信息素蒸发系数,0<ρ<1;为第k只蚂蚁在本次迭代中留在边(i,j)上的信息素量;Q为一正常系数;为第k只蚂蚁在本次周游中的路径长度。
    在蚂蚁系统中,信息素更新公式为:
    信息素更新公式
    3蚁群算法的求解步骤
    1.初始化参数在计算之初,需要对相关参数进行初始化,如蚁群规模(蚂蚁数量)m、信息素重要程度因子α、启发函数重要程度因子β、信息素会发银子ρ、信息素释放总量Q、最大迭代次数iter_max、迭代次数初值iter=1。
    1. 构建解空间将各个蚂蚁随机地置于不同的出发点,对每个蚂蚁k(k=1,2,3…m),按照(2-1)计算其下一个待访问城市,直到所有蚂蚁访问完所有城市。
    2. 更新信息苏计算每个蚂蚁经过路径长度Lk(k=1,2,…,m),记录当前迭代次数中的最优解(最短路径)。同时,根据式(2-2)和(2-3)对各个城市连接路径上信息素浓度进行更新。
    3. 判断是否终止若iter<iter_max,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。
    4. 判断是否终止若iter<iter_max,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。3. 判断是否终止若iter<iter_max,则令iter=iter+1,清空蚂蚁经过路径的记录表,并返回步骤2;否则,终止计算,输出最优解。
    蚁群算法流程简图
    4简单案例–依据蚁群算法的步骤求解二元函数最小值优化二元函数:
    (4-1)优化思路:首先,通过对约束条件求解, 我们可以得到满足约束条件的可行解所构成的搜索空间。这是一个二维的凸空间,如果把各个分量的范围搜索等分成离散的点,那么空间整个的大小可以由分量xi的划分粗细来确定。假设,xi被划分成了Ni份,那么整个搜索空间就有2*Ni个。而且为了求得精确解将分量 xi 的区间划分得很细, 那么搜索空间将变得十分巨大, 这也正是问题求解的困难所在,当然这种划分区间的方法也是许多优化算法所一般采用的方法。)将每个分量的取值区间等分成N个点,那么xi就有N种选择二维决策量x就有N^2种选择组合。并将每个分量的N个取值点看作N个城市City。最开始将m个蚂蚁Ant随机地放到x1的N中的m个City上。搜索开始后,Ant按照转移概率进行城市选择。在第一次选择时,用rand函数随机选择,之后可按照选择概率转移。
    本案例的具体步骤为:(1)求解约束条件得出各分量的区间,由题意知[-1,1];(2)将分量区间细化,建立搜索空间,本案例细分成73份,xi=[-1,-1+2/73,…1];(3)判断精度是否满足要求,若满足,则输出最优解并结束, 否则继续(4);(4)每个路径上设置信息量初始值;(5)随机选择路径求解;(6)每个蚂蚁按照选择概率来选择路径求解;
    (7)若每个蚂蚁都找到解,则继续(8),否则转(4);(8)将当前最优解的分量再细化, 转(2)。

    展开全文
  • TDOA定位 chan算法和Taylor算法比较仿真 matlab

    万次阅读 热门讨论 2019-06-23 17:09:32
    最近在学习TDOA定位算法,需要比较chan(查恩算法)和Taylor(泰勒级数算法)的定位效果。 分别实现的效果图: 运动目标从零点开始沿x=y做匀速运动。 观测站坐标如下: 在不同的雷达测距误差下的定位误差为: ...
  • 目前推荐系统研宄的主要趋势是从单一的、独立的推荐系统算法逐渐向组合多种推荐算法形成混合式的综合推荐算法方向发展,越来越多的结合用户标签数据、社交网络数据、上下文信息、地理位置信息。群体推荐也成为一个...
  • 图像融合算法(像素级)

    万次阅读 多人点赞 2019-10-25 09:26:06
    图像融合技术可以提取自然光图像和红外图像的互补信息,获得对同一场景描述解释更为准确、全面和可靠的图像。像素级融合是常用于灰度图像与可见光图像的融合。基于源图像的彩色化就是源图像和目标图像的融合过程,使...
  • 图像识别算法

    万次阅读 多人点赞 2019-08-15 17:36:40
    图像特征提取是图像分析与图像识别的前提,它是将高维的图像数据进行简化表达最有效的方式,从一幅图像的的数据矩阵中,我们看不出任何信息,所以我们必须根据这些数据提取出图像中的关键信息,一些基本元件以及它们...
  • 多目标优化算法——多目标粒子群算法实战分享

    万次阅读 多人点赞 2019-03-09 12:34:24
    运筹学优化领域,多目标优化算法,多目标自适应粒子群优化算法;并简要介绍了开源多目标优化算法框架jMetal。 基本的粒子群优化算法可参照博主的一篇文章粒子群算法实战分享-附原版动画PPT(技术分享也可以文艺范...
  • 【优化算法】简述灰狼优化算法(GWO)原理

    万次阅读 多人点赞 2019-03-25 21:10:34
    系列优化算法简述: OP_1. 简述遗传算法(GA)原理 OP_2 简述灰狼优化算法(GWO)原理 前言: 灰狼优化算法(Grey Wolf Optimizer,GWO)由澳大利亚格里菲斯大学学者 Mirjalili 等人于2014年提出来的一种群智能...
  • 鸟群寻找食物的过程中,鸟与鸟之间存在着信息的交换,每只鸟搜索目前离食物最近的鸟的周围区域是找到食物的最简单有效的办法。 粒子群算法(以下简称PSO)就是模拟鸟群觅食行为的一种彷生算法 。 解=粒子=鸟 (鸟的...
  • 蚁群算法---matlab代码

    万次阅读 多人点赞 2017-08-03 00:39:50
    蚁群算法—matlab代码文明转帖,代码摘自:FPGA机器学习之蚁群算法 matlab程序蚁群算法简介 蚁群是自然界中常见的一种生物,人们对蚂蚁的关注大都是因为“蚁群搬家,天要下雨”之类的民谚。然而随着近代仿生学的...
  • 机器人控制算法

    千次阅读 多人点赞 2019-09-11 16:43:20
    机器人的算法大方向可以分为感知算法与控制算法,感知算法一般是环境感知、路径规划,而控制算法一般分为决策算法、运动控制算法。环境感知算法获取环境各种数据,通常指以机器人的视觉所见的图像识别等,当然还有...
  • 机器学习算法 综述(入门)

    万次阅读 多人点赞 2019-06-16 21:59:28
    学习了一个学期机器学习算法,从什么都不懂到对十个机器学习算法有一定的了解,下面总结一下十大机器学习算法,从算法的概念、原理、优点、缺点、应用等方面来总结,如果有错误的地方,欢迎指出。 目录 1.决策树...
  • 粒子群优化算法

    千次阅读 多人点赞 2018-12-02 18:23:02
    文章目录粒子群优化算法1、简介2、思想粒子群优化算法分析粒子群优化算法应用总结 粒子群优化算法 1、简介 粒子群算法,也称粒子群优化算法或鸟群觅食算法,英文为:Particle Swarm Optimization,缩写为 PSO, 是由...
  • 多目标优化-Pareto遗传算法

    万次阅读 多人点赞 2019-10-25 16:02:17
    这里写自定义目录标题多目标优化的应用背景遗传算法自适应遗传算法Pareto遗传算法Pareto遗传算法的求解 这里写自定义目录标题多目标优化的应用背景遗传算法自适应遗传算法Pareto遗传算法Pareto遗传算法的求解遗传...
  • 机器人路径规划_蚁群算法

    万次阅读 2015-12-17 16:24:02
    机器人路径规划_蚁群算法 原理 蚁群算法是模拟自然界中蚂蚁的觅食行为而形成的一种群体智能化算法。蚂蚁个体之间信息的传递是通过一种称为信息素的化学物质进行的。蚂蚁在寻找食物的过程中会释放一定量的信息...
  • 基于用户的协同过滤推荐算法实现原理及实现代码

    万次阅读 多人点赞 2019-11-09 09:35:39
    基于用户的协同过滤推荐算法基于用户的协同过滤推荐算法实现原理及实现代码一、基于用户的协同过滤推荐算法实现原理二、...1.根据用户历史行为信息构建用户-项目评分矩阵,用户历史行为信息包括项目评分、浏览历史、...
  • BP神经网络算法改进

    万次阅读 2018-04-22 21:26:13
    试设计一个算法,能通过动态调整学习率显著提升收敛速度,编程实现该算法,并选择两个UCI数据集与标准的BP算法进行实验比较。 1.方法设计 传统的BP算法改进主要有两类: - 启发式算法:如附加动量法,自适应...
  • 遗传算法(python版)

    万次阅读 多人点赞 2017-05-27 16:59:52
    介绍了遗传算法并给出了Python版的GA算法
  • PSO-粒子群优化算法

    千次阅读 2017-03-31 10:43:22
    PSO算法 粒子集群算法1. 常见的群体智能优化算法分类常见的群体智能优化算法主要有如下几类: (1)蚁群算法(Ant Colony Optimization,简称ACO)[1992年提出]; (2)粒子群优化算法(Particle Swarm ...
  • 算法工程师的日常工作到底是在干嘛? 平常看起来似乎还挺闲的,工资还那么高。 有时候算法工程师好像又和大数据工程师是一样的工作?   这到底是怎么回事呢?   大约整理出以下几个疑问: 1、 软件工程师、...
  • 音频信息隐藏算法

    千次阅读 2018-12-28 17:12:20
    主要特点是:嵌入及提取水印速度快,算法简单,容易实现,音频信号中可编码的数据量大;其缺陷是稳健性差。       2、相位隐藏法。 在相位编码中,隐藏的信息是用相位谱中特定的相位或相对相位来表示的,可...
  • SIFT算法原理

    万次阅读 多人点赞 2019-03-16 21:33:58
    SIFT算法 SIFT即尺度不变特征变换,是用于图像处理领域的一种描述。这种描述具有尺度不变性...2、区分性好,能够在海量特征数据库中进行快速准确的区分信息进行匹配 3、多量性,就算只有单个物体,也能产生大量特征...
  • 盲源分离算法学习笔记

    千次阅读 2019-12-07 10:41:29
    麦克风阵列算法有两大类,一类是波束形成算法,另一类是盲源分离算法,两者互有优劣。本篇博客先介绍盲源分离的优缺点,盲源分离的基础知识,然后分别介绍盲源分离的常见实现方式。
  • 运动目标跟踪算法

    万次阅读 多人点赞 2019-02-17 12:53:17
    本文介绍了一般的目标跟踪算法,对几个常用的算法进行对比,并详细介绍了粒子滤波算法和基于轮廓的目标跟踪算法。最后简单介绍了目标遮挡的处理、多摄像头目标跟踪和摄像头运动下的目标跟踪。 一、一般的目标跟踪...
  • 从字面上就可以看出,1:1是用户提前上传个人照片储存于系统中,每次验证时,线下拍照与系统中存储的照片信息进行对比,进而确定“你是不是你”。 举个例子,我们在车站过安检时,检票员拿着你的身份证跟你本人做...
  • 这些优化算法都是为针对一个目标值的最大或最小的寻找,前三种算法都属于概率性原理的算法(区别于工程优化里面的梯度下降,牛顿算法等连续直接的搜索算法,可以参考我这篇文章,求多元函数极值的情况分类与对应的...
  • 蚁群算法总结

    千次阅读 2019-02-04 12:14:22
    蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的方法。 蚁群算法是一种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,403,464
精华内容 561,385
关键字:

信息算法