基于遗传算法的图像匹配基于遗传算法的图像匹配遗传算法理论和特点遗传算法理论和特点1、GA的基本原理遗传算法首先采用某种编码方式将解空间映射到编码空间,每个编码对应问题的一个解,称为个体或染色体,再随机确定起始的一群个体,称为种群。在后续迭代中,按照适者生存原理,根据适应度大小挑选个体,并借助各种遗传算子对个体进行交叉和变异,生成代表新的解集的种群,该种群比前代更适应环境,如此进化下去直到满足优化准则。此时末代个体,经过解码,可作为问题近似最优解。22、、GA的理论基础(1)模式定理定义1:出现在模式H中的0或1的数目称为模式H的阶,记作O(H)。如:O(10**1)=3。定义2:模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距,记作δ(H)。如:δ(10**1)=4。模式定理:具有低阶、短定义距和平均适应度高于种群平均适应度的模式在后代中呈指数增长。(2)积木块假设积木块假设:遗传算法通过短定义距、低阶和高平均适应度的模式(积木块),在遗传操作下相互结合,最终接近全局最优解。模式定理保证了遗传算法找到全局最优解的可能性存在,而积木块假设指出了在遗传操作下能生成全局最优解。两者构成了分析遗传算法进化行为的基本理论。遗传算法的特点遗传算法的特点与传统的方法相比,遗传算法以其简单、与传统的方法相比,遗传算法以其简单、鲁棒性强、不需很多先验知识等特点,使鲁棒性强、不需很多先验知识等特点,使它能适应于不同的环境、问题,并且在大它能适应于不同的环境、问题,并且在大多数情况下都能得到最优解。遗传算法多数情况下都能得到最优解。遗传算法具有很强的鲁棒性,这是因为比起普通的具有很强的鲁棒性,这是因为比起普通的优化搜索方法,它采用了许多独特的方法优化搜索方法,它采用了许多独特的方法和技术,归纳起来,主要有以下几个方面和技术,归纳起来,主要有以下几个方面::(1)(1)遗传算法的处理对象不是参数本身,而遗传算法的处理对象不是参数本身,而是对参数集进行了编码的个体,遗传算法是对参数集进行了编码的个体,遗传算法将待优化问题的原始参数集编码成有限字将待优化问题的原始参数集编码成有限字符集上的有限长字符串,然后以一种通用符集上的有限长字符串,然后以一种通用的方式去找出各编码的类似处。这样做的的方式去找出各编码的类似处。这样做的好处是大大减少了约束条件的限制,如连好处是大大减少了约束条件的限制,如连续性、可导性、单峰性等。因此,遗传算续性、可导性、单峰性等。因此,遗传算法是一种框架算法,最适合于解决那些很法是一种框架算法,最适合于解决那些很难用表达式表达出来的问题。难用表达式表达出来的问题。(2)(2)遗传算法是同时处理群体中的多个个体,遗传算法是同时处理群体中的多个个体,即多点搜索,在很多优化算法中,算法总即多点搜索,在很多优化算法中,算法总是按照某种转移准则从参数空间中的一个是按照某种转移准则从参数空间中的一个单点移至下一个单点,这样做很容易在多单点移至下一个单点,这样做很容易在多峰的搜索空间中找到一个非全局最高的峰峰的搜索空间中找到一个非全局最高的峰值,即局部最优值。而遗传算法是从很多值,即局部最优值。而遗传算法是从很多点的集合开始同时搜索的,从而减少了陷点的集合开始同时搜索的,从而减少了陷于局部最优解的风险。于局部最优解的风险。(3)(3)遗传算法仅用适应度函数来指导搜索,以往遗传算法仅用适应度函数来指导搜索,以往很多的搜索方法都需要辅助信息才能正常工作。很多的搜索方法都需要辅助信息才能正常工作。如梯度法需要有关导数的信息才能爬上当前的峰如梯度法需要有关导数的信息才能爬上当前的峰值点,这就要求目标函数可导。而遗传算法则不值点,这就要求目标函数可导。而遗传算法则不需要类似的辅助信息,为了有效地搜索越来越好需要类似的辅助信息,为了有效地搜索越来越好的编码结构,它仅需要与该编码串有关的适应度的编码结构,它仅需要与该编码串有关的适应度函数即可。在适应度值的指导下,个体随着进化函数即可。在适应度值的指导下,个体随着进化代数的增大而不断进化,每一代的结果都优异于代数的增大而不断...