模糊控制与智能控制控制论.doc

基于互信息理论遗传算法的图像匹配 遗传算法原理： 遗传算法是一种仿生优化算法，该算法的基本思想来源于达尔文的进化论。遗传算法的基本原理是首先对问题的可行性进行编码，然后随机生成一定规模的初代种群，接着按照适者生存和优胜劣汰的原理，逐代进行进化。在每一代进化中，根据问题域中个体的适应度大小择优挑选个体，并按照一定的概率进行基因交叉和基因变异操作，生成新一代种群。像自然界进化一样，遗传算法的后代种群会比前代种群具有更大的适应度，更加适应环境，即更加接近问题的最优解。最后，对末代种群的最优个体进行编码，即可以作为问题的近似最优解。 图1.遗传算法流程图 1.1基因交叉 交叉是指对选择出来的优良个体通过基因交叉的方法以便生成与父代种群不同的个体，交叉式遗产算法产生新个体的主要手段。其主要的交叉方法有三种：单点交叉、多点交叉、均匀交叉。 单点交叉：令N为个体的基因个数，则单点交叉的实现过程如下：首先产生一个区间为[1，N-1]的随机整数，该随机数就是交叉点，然后以交叉点为界，交换两个个体的基因。 假设两个父个体为： 交叉点为3，则交叉后生成的新个体为： 交叉概率大小直接影响遗传算法的收敛性和有效性；越大，产生新个体的速度就越快，但遗传模式被破坏的可能性就越大，具有较高适应度的个体基因会很快被破坏。越小，搜索速度就越慢，对于本函数可使用自适应交叉概率，其表达式如下： （1） 多点交叉 多点交叉的实现过程与单点交叉类似，不同的是多点交叉有若干个交叉点，在各交叉点间间断地进行两个个体的基因交换。 均匀交叉： 均匀交叉与多点交叉类似，不同的是均匀交叉把每个点都作为潜在的交叉点，其实现过程是：随机的产生与个体基因长度相等的掩码，由掩码决定哪个父个体向子个体提供基因。通常约定掩码中的1辨识由父个体1提供基因，掩码0表示由父个体2提供基因。 父个体1： 1 0 1 0 1 1 0 0 1 0 父个体2： 0 1 0 1 1 0 0 1 0 1 随机产生掩码为: 1 0 1 1 1 0 0 1 0 0 则交叉后生成的新个体为： 子个体1： 1 1 1 0 1 0 0 0 0 1 1.2基因变异 变异是指对交叉后的个体的基因以很小的概率发生改变，通过基因变异同样可以产生与父代种群不同的个体，变异是遗传算法产生新个体的次要手段。变异的实质是一种局部随机搜索，变异概率不能太大，否则遗传算法就退化为随机搜索法。 采用自适应变异概率，其计算表达式为： （2） 表示每代种群的平均适应度值，表示每代种群的最大适应度值，表示待变异个体的适应度值 1.3个体选择 选择是指从父代种群中挑选出优良的个体。当确定了父代种群中的全部个体后，需要通过选择操作来挑选其中的较优个体，以提供后续的交叉和变异使用。由于选择操作时根据个体的适应度进行的，因此在选择前需要计算父代种群全部个体的适应度。其中，三种常用的选择方法为：轮盘赌选择法、随机遍历抽样法、锦标赛选择法。 本文主要介绍轮盘赌选择法：首先根据父代种群中全部个体的适应度计算每个个体的选择概率和积累概率，然后进行若干轮选择。每一轮产生一个范围为[0,1]的随机数，接着将该随机数作为选择指针与积累概率进行比较，指针所在位置对应的个体即为被选中。如，从10个个体中挑选5个个体。10个个体的适应度（Fit）、选择概率（SP）、和积累计算公式如下： （3） 1.4编码和解码 由于变量均为实数且连续，故编码采用二进制编码方案，即个体的基因由一系列0,1 组成的二进制串表示，串的长度由变量长度及求解精度决定。设区间长为，精度要求到小数点后n位，则串长CL的计算公式为： （4） 若要精确到小数点后5为，则需要串长至少为21位。解码时编码的逆操作，即将二进制转换为十进制数。对应的十进制数x可由下列公式计算： （5） 1.5计算适应度 适应度是遗传算法中个体进化的驱动力，是进行自然选择的唯一依据。个体质量的优劣完全由它的适应度高低唯一地评价。适应度越高，则表明个体质量越好，其生存的机会就越大；反之，若适应度越低，则表明个体质量越差，其生存的机会就越小，而被淘汰的机会却增加，本文详细的论述了采用互信息量作为衡量待配准图像和参考图像的相似度的度量，在遗传算法中我们就可以把其作为衡量各个个体适应度的函数。 1.6初始种群的产生 一般来说，种群数目P的取值范围为10到160之间，若P太大虽然可以搜索到更多解，更容易找到全局最优个体，但会增加