搜索
一、遗传算法简介1、概念遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。2、思想遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。3、过程遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型：式中x为决策变量，式2-1为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。遗传算法也是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一种。这种启发式通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。遗传算法的基本运算过程如下：a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。二、遗传算法在图像处理方面的应用1、基于遗传算法的图像增强遗传算法(geneticalgorithm,GA)是一种自适应启发式群体型概率性迭代式的全局收敛搜索算法,其基本思想来源于生物进化论和群体遗传学,体现了适者生存、优胜劣汰的进化原则。使用遗传算法求解科学研究工作和工程技术中各种组合搜索和优化计算问题这一基本思想早在20世纪60年代初期就由美国Michigan大学的Holland教授提出,其数学框架也于20世纪60年代中期形成。由于GA的整体搜索策略和优化计算不依赖于梯度信息,所以它的应用范围非常广泛,尤其适合于处理传统方法难以解决的高度复杂的非线性问题。它在自适应控制、组合优化、模式识别、机器学习、规划策略、信息处理和人工生命等领域的应用中越来越展示出优越性。图像处理是计算机视觉中的一个重要研究领域,在图像处理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求,GA在这些图像处理中的优化计算方面找到了用武之地,目前已在图像分割、图像恢复、图像重建、图像检索和图像匹配等方面得到了广泛的应用[1～3]。图像增强就是将原来不清楚的图像变得清晰或把某些特征强调出来,以改善图像的视觉效果或便于对图像进行其他处理[1]。图像增强技术主要有频域法、空域法。频域法是把原图像进行某种变换如傅里叶变换,小波变换),在变换域中进行处理以达到增强的目的,空域法直接对原始图像进行处理,主要包括直接灰度变换、直方图均衡、平滑滤波等。基于GA的图像增强技术的实现过程实际上是一个寻找控制参数的最优或次优解的过程,因此,首先要选择一个参数模型。卢丽敏等人[5]采用如下的参数模型:设错误!未找到引用源。是图像在x行y列的像素值,错误!未找到引用源。为增强后的图像在对应点的像素值,则有其中,错误!未找到引用源。是一个对比扩展函数,错误!未找到引用源。为x行y列处像素点在它的某个领域内的局部均值,错误!未找到引用源。是一个控制参数,其大小影响到图像的处理质量,因此图像增强过程转化为寻求最优参数k的过程。文献[6]则把问题转化为另外的模型,确定不同的参数来达到同样的目的。文献[7]对图像进行模糊增强处理,给出一种新的模型,使用GA对图像模糊增强的灰度阈值进行优化选择,同时改进了GA。文献[8]采用GA来确定Beta函数错误!未找到引用源。中α,β值,实现图1中所示的4类变换曲线的自动拟合。提出了自适应多位变异算子,很好地把二进制与十进制编码的优点相结合,使GA搜索性能更加优良,提高了种群的稳定性。实验证明该方法不仅具备较强的自适应能力,在获得最优或近似最优解时,极大节约处理时间,明显优于穷举法,适合对大图像库的自动化处理。图1变换曲线GA用于图像增强能得到更好的增强效果,但从时间上考虑,对图像进行寻优速度较慢,可考虑用并行GA,是一个值得研究的课题。2、基于遗传算法的图像恢复图像恢复就是把一个退化(或劣化)图像尽量恢复到它的原始面目,是数字图像处理中的一个重要分支。目前已提出许多有效的图像恢复方法,如逆滤波法、维纳滤波法、奇异值分解伪逆法、最大熵恢复法等[10]。由于引起图像退化的原因未知或不能用函数表达,使得上述方法面临较多的约束问题或是计算量过大问题,由于难以确定退化函数h,限制了其实际应用的效果。GA用于灰度图像的恢复,一般将染色体编码成以各像素的灰度值为元素的2维矩阵,即一个染色体就代表一幅图像,每个基因对应一个像素,采用自然数编码。每个个体的适应度函数为2()*iiFfghf其中,fi为个体i代表的推测恢复图像,g为观测到的退化图像,h为退化过程,函数值越大表示个体越好。在交叉操作时一般采用窗口交叉,即在父代染色体矩阵中选择相同大小的窗口,进行交换。变异操作采用临近小范围内的平均值替换需要变异的某一基因值。文献[11]以图像中像素的灰度相对等级作为模糊特征,把图像模糊特征矩阵中的元素(隶属度),转换成遗传空间上的基因;即基因为Pij/Xij表示图像中第(i,j)点像素具有某种特征的程度,相应的适应度函数为~~~(())*defiiGyfGghf其中,G(*)表示模糊集*的重心;if是第i个个体代表的推测图像模糊集,g是观测到的退化图像模糊集。文献[12]针对上述问题提出一种基于多种群遗传算法的图像恢复方法,低层遗传保证了搜索的充分性和收敛结果的全局最优性;高层遗传使各子群能共享低层遗传所得的优良基因模式,以防止向局部最优收敛。此外,GA也用于彩色图像的恢复[13],取得了很好的效果。基于GA的图像恢复方式,突破了原有的理论,而且其开放的结构易于与其他方式融合,如与模糊逻辑相结合的模糊GA等。利用GA恢复图像不仅较好的克服了噪声的影响,而且使图像更平滑,边缘没有条纹效应,视觉效果好。强大的全局搜索能力是遗传算法图像恢复方法行之有效的主要原因。值得指出的是,用GA进行图像恢复的计算量很大,而且图像恢复属于不良设定问题,解又不是唯一的,因此应改进编码技术,解决通常GA“早熟”问题,以及使用大的群体规模,依赖于选择和交叉算子来提高图像恢复的质量。3、遗传算法在图像重建中的应用图像重建是由在某种观测方式下得到的携带图像信息的数据恢复出原图像的过程。获得目标投影数据的不同方法,决定了图像重建问题求解的方法学。由这种方法学所产生的重建方法主要有代数法、迭代法和傅里叶变换法等。GA应用于图像重建主要解决从带有噪声的投影数据恢复图像。Knoll等人[14]提出一种遗传重建算法(GRA)。GRA主要用来最小化被测像素值0ijkZ和计算的射线总和0ijkS之间的差。染色体定义为体素(voxel)值,初始种群的染色体随机取[1,255]区间的值,适应度函数为200,,111()xyznnnRayijkijkijkxyzEZSnnn其中,i,j,k分别表示被测目标的x,y和z坐标,成像设备的角度位置表示为θ;,,xyznnn表示被测3维目标的矩阵尺寸;射线总和0ijkS按下面条件计算:0corrijkijkijkijkijkIfvoxelVRaySSvVijkijkelseSS为了提高搜索速度,采用并行的遗传算法来实现,对有噪声的数据集进行实验,效果特别好。Susumu等人[15]提出了一种遗传松弛迭代傅里叶变换算法(GRIFTA),解决图像重建时产生停滞现象的问题,即重建图像的效果受初始集合选择的影响。染色体直接采用图像的2维遗传编码;适应度函数定义为2()nnnJfPff;选择合适的种群规模、交叉率和变异率。仿真实验结果证明,上述方法可以正确重建图像而不依赖初始集合的选择,另外该算法比常规的迭代傅里叶变换算法速度更快。Yu等人[16]在假设组成目标的点是分散情况下,用线性模型拟合方式来重建高分辨率雷达图像。利用GA的全局寻优特性来最小化拟合的误差,实验结果证实能得到非常精确的结果。将GA应用于图像的重建还是一个正在探索的课题,目前给出的方法都是有益的尝试,存在一些问题,比如速度一般较慢、重建出的图像边缘不清等,还需要进一步改进。【参考文献】[1]章毓晋著.图像处理和分析(第1版)[M].北京:清华大学出版社,1999.[2]林磊,王晓龙,刘家锋.基于遗传算法的手写体汉字识别系统优化方法的研究[J].计算机研究与发展,2001,38(6):658～661.[3]刘智明,周激流.基于遗传算法的有效人脸检测法[J].计算机辅助设计与图形学学报,2002,14(10):940～944.[4]陈国良,王熙法,庄镇泉等著.遗传算法及其应用[M].北京:人民邮电出版社,1996.[5]卢丽敏,周海银.一种基于遗传算法的图像增强方法[J].数学理论与应用,2003,23(1):82～88.[6]李宏贵,李兴国,李国桢等.一种基于遗传算法的红外图像增强方法[J].系统工程于电子技术,1999,21(7):44～46.[7]陈佳娟,陈晓光,纪寿文等.基于遗传算法的图像模糊增强处理方法的研究[J].计算机工程与应用,2001,37(21):109～111.[8]周激流,吕航.一种基于新型遗传算法的图像自适应增强算法的研究[J].计算机学报,2001,24(9):959～964