（电路与系统专业论文）基于遗传算法的pcb板元件检测.pdf

基于遗传算法的p c b 板元件检测 摘要 摘要 随着p c b 板制造工艺的发展，电路板上焊接的各种器件越来越多，发生焊 接错误的概率也越来越高。如果在检验过程中不能将这些问题找出来，势必在 p c b 板调试和应用过程中留下安全隐患。目前主要使用两种方法来检测p c b 板 上元件安装质量，一是采用人工检测的方法；二是采用计算机视觉检测技术。 本文针对目前检测方法中的一些不足，提出了一种新的检测方法，即通过图 像模板匹配法逐个检测p c b 板上元器件，详细描述了p c b 板元器件检测的基本 原理，并使用基于f p a g 硬件平台的代间差分遗传算法对图像搜索匹配过程进行 优化，显著降低了系统的成本以及设计复杂度，同时也为遗传算法的实对应用开 辟了新的思路和方法。 本文首先介绍了一般遗传算法的设计方法。然后介绍了p c b 板元器件检测 的基本原理，并采用图像模板匹配算法检测p c b 板上应焊接某一阻值电阻的区 域是否焊接了其他阻值的电阻或者发生漏焊。接着采用简单遗传算法( s g a ) 对 图像搜索匹配过程进行优化。针对简单遗传算法( s g a ) 本身固有的缺陷，提出 利用代间差分遗传算法进步优化其搜索匹配速度，给出了算法实现的全过程， 并验证了代间差分遗传算法可以有效优化图像匹配搜索过程，加快检测的速度。 鉴于用软件实现代间差分遗传算法对检测过程进行优化，存在检测速度相对 较慢，不能满足实时检测的要求，采用传统的p c 机作为实现平台，成本昂贵， 系统设计复杂，无法发挥遗传算法并行性的特点等问题。本文以f p g a 为硬件平 台实现代间差分遗传算法( i d g a ) ，详细介绍了硬件实现流程，同样对图像搜索 匹配过程进行优化，详细描述了系统结构框图以及设计流程，并将实验结果与采 用软件实现的实验结果相比较，验证了采用f p g a 为硬件平台实现代间差分遗传 算法( i d g a ) ，其检测速度和实时性大大优于软件实现方法，完全发挥了遗传算 法的并行性，加快了检测的速度，实现了实时性的要求。 关键词：p c b 板元件，遗传算法，f p g a 基于遗传算法的p c b 板元件检测 a b s t r a c t t h ea p p l i c a t i o no fg e n e t i c a l g o r i t h m i n d e t e c t i n g p r i n t e d a b s t r a c t c i r c u i tb o a r d c o m p o n e n t s b v d a l ll i at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no f t h e r e q u i r e m e n t sf o rt h ed e g r e eo fm a s t e ro fs c i e n c e i n t h e s c h o o lo f i n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y o f t h e f u d a nu n i v e r s i t y w i t ht i l ed e v e l o p m e n to ft h em a n u f a c t u r et e c h n o l o g yo ft h ep c b ，t h e r ea r em o r e a n dm o r ea d p a r a t u st 1 1 a tn e e dt ob es e a l e do nt h ee l e c t r o n i cb o a r d ，t h i sl c a d st oh i g h e r p o s s i b i l i t yo fs e a l i n ge r r o r i ft h e s ep r o b l e m sc a nn o tb ef o u n do u t 1 e r ew i l l n e c e s s a r i l yb eh i d d e ns e c u r i t yt r o u b l ei nt h ep r o c e s so ft h ed e b u g g i n ga n da p p l i c a t i o n o ft h ep c b a tp r e s e n tt h e r ea r et w om e t h o d st ot e s tt h eq u a i l t yo f l ec o m p o n e n t p l a c e do nt h ep c b ，o n ea d o p t sm a n i l a lm e t h o d ，a n dt h eo t h e ra d o p t s 恤ec o m p u t e r v i s u a lc h e c k i n gt e c h n o l o g y i nt h i sp a p e ran e wm e t h o do ft e s t i n gi sp r o p o s e dt ob ea g a i n s tt h ed i s a d v a n t a g e s o ft h ep r e s e n tt e s t i n gm e t h o d s w h i c hi st ot e s tc o m p o n e n t so nt 1 1 ep c bo n eb yo n e b a s e do nt h ei m a g et e m p l a t em a t c h i n gm e t h o d t h ef u n d a m e n t a lt h e o r yo ft h ep c b c o m p o n e n t st e s t i n gi sd e s c r i b e di nd e t a i l a n da no p t i m i z a t i o ni sm a d et ot h ei m a g e t e m p l a t em a t c h i n gp r o c e s su s i n gt h ei d g ab a s e do nt h ef p g ap l a t f o r m w h i c h g r e a t l yr e d u c e st h ec o s to f t h es y s t e ma n dt h ec o m p l e x i t yo ft h es y s t e md e s i g n ，a tt h e s a m et i m ean e ww a ya n dm e t h o do f t h er e a lt i m ea p p l i c a t i o no f g ai sb r o u g h to u t t h es g a sd e s i g nm e 血o di sf i r s t l yi n t r o d u c e d t h ef u n d a m e n t a lt h e o r yo ft h e p c bc o m p o n e n t st e s t i n gi si n t r o d u c e d t h ei m a g et e m p l a t em a t c h i n gm e t h o di s a d o p t e dt ot e s tw h e t h e ro n er e s i s t a n c ei sw r o n g l y s e a l e da n o t h e rr e s i s t a n c ev a l u eo ri s s e a l e du n s u c c e s s f u l l y t h e ns g ai sa d o p t e dt oo p t i m i z et h ei m a g et e m p l a t em e t h o d a c c o r d i n gt ot h ei n h e r e n td e f i c i e n c yo fs g a ，i d g a i sp r o p o s e dt of u r t h e ro p t i m i z e t h es e a r c h i n ga n dm a t c h i n gs p e e da n dt h er e a l i z a t i o no ft h ea l g o r i t h mi sf u l l y i n t r o d u c e d t h a ti d g ac a ne f f i c i e n t l yo p t i m i z et h ei m a g et e m p l a t em a t c h i n ga n dc a n a c c e l e r a t e 也et e s ts p e e da r ep r o v e d 2 基于遗传算法的p c b 板元件检测 t or e a l i z et h eo p t i m i z a t i o no ft h et e s t i n gp r o c e s sb a s e do ns o f t w a r ei d g ah a st h e d e f i c i e n c yo fs l o wt e s t i n gs p e e da n dc a nn o tr e a l i z et h er e a l t i m et e s t i n ga n da tt h e s a m et i m eu s i n gt h et r a d i t i o n a lp cp l a t f o r mc o s t sal o ta n dt h es y s t e md e s i g ni s c o m p l e xa n dc a nn o tr e a l i z et h ep a r a l l e lp r o p e r t yo fg a i nt h i sp a d e rt h ei d g ai s r e a l i z e do nf p g ap l a t f o r n l t h eh a r d w a r er e a l i z a t i o nf l o wi sp a r t i c u l a t l vi n t r o d u c e d a n dt h ei m a g et e m p l a t em a t c h i n gp r o c e s si so p t i m i z e da n dt h es y s t e mf r a m eb l o c ka n d t h ed e s i g nf l o wa r ed e s c r i b e d t h a tt h et e s t i n gs p e e da n d 廿1 er e a l t i m eo ft h ei d g a b a s e do nt h ef p g ah a r d w a r ep l a t f o r ma r eb e t t e rt h a l lt h es o f t w a r er e a l i z a t i o nm e t h o d a r ep r o v e db yc o m p a r i n gt 1 1 er e s u l t so ft h i se x p e r i e n c e 、i mm a to ft h es o f t w a r e r e a l i z a t i o nm e t h o d t h i sm e t h o de n t i r e l yr e a l i z e st h ep a r a l l e lp r o p e r t yo fg aa n d e x p e d i t e st h et e s t i n gs p e e da n dr e a l i z e st h er e q u i r e m e n to f r e a l - t i m e k e y w o r d s ：p c bc o m p o n e n t s ，g e n e t i ca l g o r i t h m ，f p g a 基于遗传算法的p c b 板元件检测 第一章概述 第一章概述 1 1 印刷电路板检测介绍 印刷电路板的生产需要经过多道工序，在焊接元器件这道工序由于焊接元器 件种类多、数量大，是最易发生疏漏的地方。尤其当需要在板上焊接较多元器件 时，更易发生漏焊和焊接错误。如果在检验过程中不能将这些问题找出来，势必 在p c b 板调试和使用过程中留下安全隐患。 目前通常使用两种方法来检测p c b 板上元件安装质量。 一种方法是采用人工检测的方法，显然这种方法速度慢、效率低，无法满足 较大规模生产的需求，同时也无法保证检测质量。 另一种方法就是采用计算机视觉检测技术来实现p c b 板元件的自动检测， 其检测框图如下所示： 图1 1 计算机视觉检测系统 首先选用一块焊接完全正确的p c b 板，通过c c d 传感器对其成像，p c 机通过图 像数字采集卡读入该p c b 板图像数据。对该p c b 板图像进行必要的预处理，如噪声 干扰滤除、对比度增强、边缘增强等，将处理后的图像作为这一批p c b 板的图像 数字模板。在对p c b 板检测时，同样通过c c d 传感器对被测p c b 板进行成像，p c 机 通过图像数字采集卡读入被l 测p c b 板图像数据。经过相应的图像预处理后与模板 图像进行比较。若两幅图像完全相同，则说明焊接正确无错。若在焊接元器件过 程中焊接位置有一定的偏移或者发生漏焊，被测图像与模板图像的差值就会被反 映出来。若在焊接过程中有元器件焊接错误，被测图像与模板图像的差值也会反 映出来。但相对整个p c b 板来说，这个差值就可能比较小。通过设定被测图像与 模板图像差值阈值的方法，来判定被测p c b 板元器件安装是否正确。若被测图像 与模扳图像的差值大于设定阈值，则认为该被狈, j p c b 板元件安装存在问题；若被 测图像与模板图像的差值小于设定闽值，则认为该被澳 j p c b 板元件安装正确无误。 由于当板上焊接了错误元器件时，对于整个图像匹配来说，错误器件图像与正确 基于遗传算法的p c b 板元件检测 第一章概述 器件图像之间的差值比较小，很难被反映出来，因此这种自动检测方法在一定程 度上只能做粗略的检测，检测出是否有元器件漏焊，而对于是否焊接了正确元器 件很难做出精确检测。 本文提出了一种新的检测方法，即通过图像模板匹配法“1 对p c b 板上每个元 件进行逐个检测。 当p c b 板设计完成以后，板上各个元器件的坐标位置已经相对固定。即在此 坐标规定的区域内的应当是该元器件的图像。如果以此元器件表面图像作为图像 模板，则此图像模板应与此坐标点规定区域的图像一致。考虑到在元器件焊接过 程中存在一定的偏移，所以待测元件图像可定位于一定的范围内，将此图像作为 搜索图。把搜索图根据模板大小划分成多个子图，根据子图与图像模板相类似的 程度来判断该坐标位置元器件焊接是否正确。以检a ! | p c b 板上5 l 欧姆贴片电阻为 例，如图1 2 所示，选择5 1 欧姆电阻器件的表面图像“5 1 0 ”作为模板，选择应焊 接5 1 欧姆电阻的坐标定义的图像作为搜索图。 图1 2 模板t 和搜索图i 采用全局搜索法，将模板与搜索图中每个子图做匹配运算，即可判断焊接是 否有问题。但除了最佳匹配子图外，其余模板与子图的匹配运算都是无效运算， 通常需要耗费大量的检测时间。因此有必要通过减少无效运算来加快检测的速 度。遗传算法是一种公认的鲁棒性强的全局优化搜索算法，与传统的搜索方法相 比有很多不同的地方。传统的搜索方法主要有解析法和枚举法。解析法在求解过 程中需要使用目标函数的解析性质，例如一阶导数、二阶导数等，但对于有些欲 求解问题无法给出具体的目标函数解析性质，则无法使用解析法实现。枚举法是 将欲求解问题的所有可能解一一列举出来，做到不重复、不遗漏，最后找到正确 的解。应用枚举法，所得的结果完整、直观，一目了然，但如果欲求解问题中可 能解的数量较大，那么枚举的数量就比较大，求解过程就比较费时。而遗传算法 通过模拟自然界的进化方式，对确定的问题搜寻最佳解决方案。遗传算法采用群 基于遗传算法的p c b 板元件检测 第一章概述 体搜索和概率的变迁规则来指导搜索方向，无需目标函数解析性质，因此能有效 加快搜索的速度。所以本文采用遗传算法来搜索匹配子图，减少匹配过程中的无 效运算，加快检测的速度。 1 2 遗传算法0 4 1 的基本原理 达尔文进化学说的中心内容是自然选择学说。自然选择学说认为每一物种在 发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产 生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能 保留下来。因此生物的进化是一个奇妙的优化过程，它通过选择、淘汰，突然变 异，基因遗传等规律产生适应环境变化的优良物种。而遗传算法就是根据生物进 化这种思想而得出的一种全局优化算法。 假设求解如下极值问题： m i n f ( x ) x x ) ( 1 1 ) 这里是x 上的一个函数，则z 是该极值问题的解空间，它可以是一个有限集合， 也可以是整个实数空间。 遗传算法在求解该问题时是从多个解开始的，即在肖中任意选取一些解作为 解的集合，然后通过一定的规则逐步迭代来不断产生新的解的集合。这个解的集 合采用生物学的名词来命名，称为种群( p o p u l a t i o n ) ，记为p ( ，) ，其中，称为进 化代数。种群p ( t ) 的个体，即解同样用生物学名词命名，称为染色体( c h r o m o s o m e ) 或者个体( i n d i v i d u a l ) ，记为( r ) ，r 2 ( t ) ，等，种群中染色体的个数称为种群规模， 常记为。 为了便于进行一系列的遗传操作，还需要将染色体用编码表示，即通过一定 的变换将x 映射到另外一空间z ，通常将空间z 称为染色体空间。这个编码变 化f ：x - + 要求是可逆的，即存在唯一解码变换f 一：x ，一x 。主要的编码方 式有二进制编码、实数编码等，对不同的问题有其最佳的编码方式。基于这种编 码方式，可确定染色体的结构。 遗传算法的基本流程如图1 3 所示，通过随机产生组编码，其对应的染色 体作为进化起点的第一代群体，并且计算每个个体的适应度值。若种群中有个体 的适应度值达到了适应度值阈值，则算法终止。若种群中没有个体的适应度值达 到适应度闽值，则接着从这些个体中通过一定的选择策略选择出适应度值符合要 求的个体作为下一代的父代样本，即进行选择。然后使用交叉算子和变异算子对 下一代的父代样本的编码进行交叉和变异运算，即进行繁殖。这样通过选择和繁 殖就产生了下代种群。反复上述选择和繁殖过程，直到找到满足适应度要求值 的染色体。 基于遗传算法的p c b 板元件检测 第一章概述 图1 3 遗传算法的基本流程 1 3 遗传算法的主要特点 遗传算法最主要的特点体现在如下三个方面： 第一方面：并行性。遗传算法的基本特征是采用群体的方式进行搜索，它从 多个解出发，通过不断的调整和重组这些解来形成新的解。 第二方面：自适应性。在确定了求解问题的编码方案、遗传算子和适应度值 评估之后，应用遗传算法进行求解，算法将利用进化过程中得到的信息自行组织 搜索。基于“适者生存，不适应者淘汰”的自然选择原则，适应度值大的个体具 有较高的生存概率。通常适应度值大的个体适应环境能力更强，再通过杂交和变 异等遗传操作就可能产生更加适应环境的后代。遗传算法的这种自适应、自繁殖 特征使得它能根据环境的变化自动的适应环境。 第三方面：不确定性。遗传算法的主要步骤选择、杂交和变异操作都带有 定的随机性，伴随随机性而来的就是不确定性，因此遗传算法具有一定的不确定 性。即通过一代一代不断的进化，最终找到的适应度值最高的个体并不一定就是 最优解，可能只是一个局部最优解。 基于遗传算法的p c b 板元件检测第一章概述 1 4 研究现状 目前遗传算法在图像处理中的应用主要集中在两个方面，一是目标图像的检 测与跟踪，利用遗传算法搜索性能强的特点提高检测目标图像的速度；二是图像 的分形压缩，同样也是利用遗传算法搜索性能强的特点寻找最佳匹配的定义域 块。在p c b 板元器件安装质量检测中，需要在搜索图中搜索是否含有与模板图 像相类似的子图，所以可以采用遗传算法来搜索匹配子图。 在采用遗传算法优化搜索匹配子图过程中，主要存在着以下几个问题： 第一：在遗传算法中，适应度函数是用来区分种群中个体好坏的唯一标准， 也是进行选择的唯一依据。适应度函数的优劣就直接影响整个进化搜索过程。在 p c b 板元器件安装质量检测过程中，适应度函数是模板与子图的相似性度量函 数。若适应度值的分布为一个多峰值分步，则会导致遗传算法进入局部收敛，无 法找到匹配子图；若模板与所有子图的适应度值分布为一个单峰连续分布，则非 常有利于遗传算法的收敛，找到匹配予图。所以必须找到较好的相似性度量函数， 使得适应度值的分布呈单峰连续分布。 第二：使用简单遗传算法优化整个搜索匹配子图过程，由于简单遗传算法收 敛速度慢，不确定性较高，会引入较大的误检概率。即器件焊接正确，但由于简 单遗传算法的固有缺陷，导致未能在搜索图中找到匹配子图。所以需要对遗传算 法进行适当的改进，减少这种不确定性，降低误检概率，同时加快收敛速度，提 高检测的速度。 第三：用软件实现遗传算法来优化搜索匹配子图的过程，比全局搜索法，可 明显加快检测速度。但由于软件的速度相对比较慢，当板上有较多元器件时，显 然不能满足实时检测的要求，同时采用传统的p c 机作为实现平台，成本昂贵， 系统设计复杂。 1 5 本文的主要工作及安排内容 基于上述问题，本文先通过介绍p c b 板元器件安装质量检测的基本原理， 引入了一种新的图像相似性度量函数。然后以该函数作为适应度值函数，详细介 绍简单遗传算法搜索匹配子图过程，验证简单遗传算法可以有效优化图像匹配搜 索过程。接着通过改进简单遗传算法的杂交算子，引入代间差分杂交算子，介绍 代间差分遗传算法的具体实现过程。同时采用代间差分遗传算法搜索匹配子图， 验证代间差分遗传算法比简单遗传算法在搜索匹配图像上速度更快、效率更高， 从而可以更加有效的加快检测的速度。最后考虑到软件实现代间差分遗传算法在 实时检测上的不足，以f p g a 为硬件平台实现代间差分遗传算法，详细描述系统 结构框图以及设计流程，并详细介绍代间差分遗传算法的硬件实现流程。将硬件 基于遗传算法的p c b 板元件检测 第一章概述 实现的实验结果与采用软件实现的实验结果相比较，验证采用f p g a 为硬件平台 实现代间差分遗传算法，其检测速度和实时性能大大优于软件实现方法，可完全 实现实时性的要求。 具体的内容安排如下： 第二章：遗传算法的设计，详细介绍一般遗传算法的设计步骤。 第三章：介绍p c b 板元器件安装质量检测的基本原理，通过实现简单遗传 算法优化检测过程，验证其有效性。同时通过改进遗传算子，采用改进型遗传算 法优化检测过程，通过软件仿真结果，证明改进型遗传算法比简单遗传算法更优， 更能加快整个检测过程。 第四章：在f p g a 硬件平台上实现改进型遗传算法，通过硬件实现的实验结 果与采用软件实现的实验结果相比较，验证采用硬件实现方法可满足实时性要 求。 第五章：总结目前的工作，并对未来的研究方向进行展望。 基于遗传算法的p c b 板元件检测 笫= 章遗传算法的设计 第二章遗传算法的设计 2 1 本章概述 本章主要介绍遗传算法的基本设计步骤，包括确定编码方案、确定选择策略、 确定杂交策略、确定变异策略、确定适应度函数和确定遗传算法的终止法则。详 细介绍了遗传算法的各种编码方案、选择策略、交叉策略、变异策略、适应度函 数和遗传算法终止法则。 2 2 遗传算法设计的基本步骤 遗传算法通过模拟自然界的进化方式，对确定的问题搜寻最佳解决方案。与 传统搜索方法相比，遗传算法具有群体搜索和不需要目标函数解析性质的优点， 适用于大规模复杂问题的优化以及无法预测可能解的场合。在设计遗传算法时， 通常按照以下六个步骤： 1 确定编码方案：对欲求解问题的解可采用不同编码方式，编码方式在很大 程度上决定了群体的遗传进化操作以及遗传进化的效率。一个好的编码方法，可 以简单的实现杂交算子、变异算子等遗传操作，使得进化有较高的效率。而一个 差的编码方法，有可能会难以实现杂交算子、变异算子等遗传操作，使得整个进 化过程效率较低。 2 确定选择策略：在生物界中适者生存的法则使得适应性强的物种有较高的 存活机率，同理在遗传算法中适应度值高的个体就有较高的概率被保留，即把当 前群体中适应度值较高的个体选择出来，按某种规则遗传到下一代群体中。选择 的标准就是各个体的适应度值大小，个体的适应度值越高，它被选中的概率越大。 所以不同的选择策略对算法的性能也有较大的影响。 3 确定杂交策略：杂交是产生新个体的主要手段，仿照生物学中杂交的原理， 将两个父代个体通过杂交算子产生新的个体，新个体中保留了父代个体的特性。 通过杂交，遗传算法的搜索能力得以飞跃提高。因此杂交策略在遗传算法中起着 核心作用，不同的杂交算子对性能有非常大的影响。 4 确定变异策略：变异是模拟生物个体的随机变异现象，对个体的值进行随 机改变。变异为新个体的产生提供了机会，保证遗传算法在进化过程中群体的多 样性，是实现遗传算法全局优化性能的重要算子之。 5 确定适应度函数：适应度函数的选取直接影响到遗传算法的收敛速度以及 能否找到最优解。因为遗传算法在进化过程中仅以适应度函数为依据，通过计算 种群中每个个体的适应度值来进行进化。通常整个遗传算法的计算量主要集中在 基于遗传算法的p c b 板元件检测 第二章遗传算法的设计 适应度函数的计算。 6 确定遗传算法的终止法则：由于在进化过程中，遗传算法没有使用目标函 数的梯度信息，所以在整个遗传进化过程中，并不确定个体在解空间中的位置， 所以也就没有办法通过判定算法的收敛与否来终止算法。通常的办法是去判断适 应度值，若在一定的进化代数内适应度值达到了设定的适应度值闽值，则说明找 到了最优解，算法终止；若在进化过程中适应度值在预先规定的一个最大进化代 数内未能达到适应度值阈值或者算法在进化过程中连续多少代以后解的适应度 值没有明显改进，则算法终止。 2 3 编码方案 设计遗传算法的一个重要步骤就是对所求解问题的解进行编码表示，合理准 确的编码方案可以使得遗传算法快速收敛。在遗传算法中通常有两种编码方案： 位串编码和实数编码。 2 3 1 位串编码 位串编码主要采用二进制编码。= 进制编码( b i n a r ye n c o d i n g ) 是将欲求解 问题的解空间映射到位串空间占。= 0 ，1 7 上，然后在位串空间上进行选择、杂交、 变异等遗传算子操作和适应度值评估。得到的遗传结果再通过解码过程还原成解 的表现形式。 在定义域 a ，b 内的任意一个变量x 都可以如下二进制串表示： 肖= ( 1 i 一1 q 以) ，= 0 o f1 ( 2 1 ) 若需将 ：p ，= 1 。 2 4 3 基于局部竞争机制的选择 基于适应度值比例的选择和基于排名的选择都是根据个体适应度值在种群 中所占的比例或者排名来确定选择概率，然后再根据选择概率进行选择。所以当 种群的规模比较庞大时，这两种策略在计算相对适应度值或者排序时就会带来相 当大的计算量。而基于局部竞争机制的选择策略可以在一定程度上避免这些问 题。 基于遗传算法的p c b 板元件检测 第二章遗传算法的设汁 2 4 3 1 锦标赛( m u m a m e m ) 选择 锦标赛选择策略选择时是先随机在种群中选择一组个体，然后将这一组个体 中适应度值最高的个体选择作为父代。这一组个体的数目通常称为竞赛规模。 这种选择策略由于使用的是绝对适应度值，与相对适应度值无关，从而能够 相对避免超级个体的影响，在一定程度上，可以避免局部收敛现象和停滞现象的 发生。 2 4 3 ，2 ( ，旯) 和卢+ 选择 ( ， ) 选择是先从规模为的种群中随机抽取个体通过杂交和变异遗传算子生成 a ( 五卢) 个后代，然后再从这些后代中选取个最优的后代作为新的一代种群。 而卢+ 兄选择则是从这些后代与其父体共p + 兄个中选择个最优的后代。1 。 2 ，5 杂交策略 杂交策略是将选择模块产生的新一代父代进行杂交，产生新一代的子代，是 遗传算法中促进进化的主要手段。由于在遗传算法中通常有两种编码方案：位串 编码和实数编码。所以随着编码方案的不同采用的杂交策略也不同。 2 5 1 二进制编码的杂交 常见的二进制编码杂交策略有单点杂交( o n e p o i n tc r o s s o v e r ) 、两点杂交 ( t w o p o i n tc r o s s o v e r ) 、多点杂交”( m u l t i - p o i n tc r o s s o v e r ) 和均匀杂交 ( u n i f o r mc r o s s o v e r ) 。单点杂交算法的作用方式为：在染色体中随机选取一点 作为杂交位置，然后交换选作父本的两个染色体杂交位置以后的部分，以形成新 的两个染色体。两点杂交和多点杂交与单点杂交类似，不同在于两点杂交随机取 两个点作为杂交位景、多点杂交随机取两个以上不同的点作为杂交位置。均匀杂 交与前面三种算法不同，它是先把染色体均匀分块，然后随机交换块。在图2 2 ( a ) 、( b ) 和( c ) 中列出了在给定父本之后采用单点杂交、两点杂交和均匀杂 交算予所产生的新一代两个染色体： 基于遗传算法的p c b 板元件捡测第二二章遗传算法的设计 p a r e n t l ： p a r e n t 2 ： o f f s p i n g l ： o f f s p i n 9 2 ： p a r e n t l ： 粪一鬻粼蕤骥獭蘸黻麟 0l 1o1o o1o01 l l010 糍瓢瓣鬻黼 o1 10lo 0l0 01 1 1 图2 2 ( a ) 随机数为3 的单点杂交 0lo p a r e n t 2 ：0110lo 0l0 011 1olo o f f s p i n g l ： o f f s p i n 9 2 ： p a r e n t l ： p a r e n t 2 ： r a n d o md a t a ： o f f s p i n g l ： o f f s p i n 9 2 ： 0 11 0l 赣鬻1 1olo 糕0 o oot 碱麟 图2 2 ( b ) 随机数为5 的两点杂交 图2 2 ( c ) 均匀杂交 单点杂交算法对父代染色体的破坏概率比较小，可以使子代有效的继承父代 的优秀基因，但是在种群规模较小时，其搜索能力会受到影响。均匀杂交算法对 父代染色体的破坏概率比较大，可以使产生的种群遍历搜索空间，尤其是在种群 规模较小时，具有较强的搜索能力。所以通常在种群规模较小时，采用均匀杂交 算法遍历搜索空间。而当种群规模比较大时，采用单点杂交算法可以使得算法的 收敛速度更快。 基于遗传算法的p c b 板元件检测 第二章遗传算法的波计 2 5 2 实数编码的杂交 在算法采用实数编码时，解空间考虑的是整个实数空间月。，而不是简单的 二迸制编码中的二进制串，所以解空间的类型量不再是布尔( b o o l e a n ) 型，所 以不能采用二进制编码中的杂交策略。 在实数编码中，杂交算子通常是从同一代群体中随机选择两个个体n ”和 n ，n 和乃分别表示是从第，代中随机选取的染色体个体，然后进行重新组合 产生新个体“，如下式所示： 2 - 。( “ = 口+ 巧砷 ( 2 - 7 ) 其中0 h 7 ，k ，：e ( o ，1 ) ，为种群的规模，即种群中个体的总 数，一般在计算过程中保持不变。这种杂交算子所产生的新个体，j “”仅仅是某一 代种群中现有信息的随机组合。 2 6 变异策略 为了保证染色体的多样性，即防止遗传算法过早收敛和停滞现象的出现，变 异策略根据一定的概率，直接作用于新产生的种群中某些个体，通过改变这个个 体，来保证种群中染色体个体的多样性。针对两种不同的编码方式( 二进制编码 和实数编码) ，变异策略也不同。 2 6 1 二进制编码的变异 当算法采用二进制编码时，变异算子按照变异概率p 。，首先在种群中随机 选择一个个体，对于选中的个体以一定的概率随机地改变其二进制串中某些位的 值，即将该二进制串中选中的某些位取反。同生物界一样，遗传算法中变异发生 的概率很低。变异为新个体的产生提供了机会。变异可以有效防止进化的停滞。 比较低的变异概率就已经可以让基因不断变更，如果变异概率太高会使遗传算法 陷入随机搜索中。 2 6 2 实数编码的变异 当算法采用实数编码时，变异算子的作用不仅仅是像二进制编码时保证生物 的多样性，而成为一个比较重要的搜索算子。常用的一些变异算予是均匀性变异、 正态性变异、非一致性变异、自适应变异和多级变异等。使用最为广泛的是均匀 性变异。 均匀性变异算子主要有两种 基于遗传算法的p c b 板元件检测 第二章遗传算法的设计 l 在父代种群中随机选择一个解，在解空间的定义域 a 阴内随机抽取一 个备选解r ，然后随机产生一个小于1 的正数，最后通过判断该正数与变异概率 p ，的大小来决定是否将随机抽取的数v ，代替父代种群中随机选择的一个解f 。 若该正数大于变异概率p ，则保持父代种群不变；若小于变异概率p 。，则将v ， 代替父代种群中的f 。 2 在父代种群中随机选择一个解t ，随机产生一个较小的数占，然后同样随 机产生一个小于1 的正数，若该正数大于变异概率p ，则同样保持父代种群不变： 若小于变异概率p 。，则采用+ 万代替一，并满足( + 占) a ，b 。 2 7 适应度函数 自然界中，个体的适应度是生物体繁殖能力的体现。在遗传算法中，个体适 应度值是用来区分种群中个体好坏的标准。个体适应度值的差异是种群进化的动 力来源，是进行自然选择的唯一依据。 遗传算法中度量适应度值的方法有很多种，通常是将欲求解问题转化成求某 个目标函数的极值问题，使用目标函数口来反映个体的适应性。目标函数口是一 个代表实际输出和期望输出差值关系的函数，两种常用形式如下： d = 万2 ( f ) j - l d = ) l ( 2 8 ) ( 2 9 ) 其中石( f ) 代表第i 个输入值的系统输出与期望输出之间的差值。则按照目标函数 值的大小即可赋以个体相应的适应度值。 采用目标函数口来反映个体的适应度值，会出现两种情况，一是适应度值 越小越好的情况，称为极小情况；二是适应度值越大越好的情况，称为极大情况。 通常需要根据遗传算法中选择策略来决定是采用极小情况还是极大情况。这往往 需要将目标函数口作一个适当的变换以转换成标准的度量方式，即都转化为极大 情况，并且是适应度值非负。 对于极小情况，标准适应度值可定义为： ，( 彳) = f一，( 盖) ( 2 1 0 ) 其中。是目标函数口的最大值。 对于极大情况，标准适应度值可定义为 基于遗传算法的p c b 板元件检测第二章遗传算法的设计 乞。，( x ) = ，( z ) 一r m i 。 ( 2 1 1 ) 其中。是目标函数口的最小值。 若某个个体的适应度值在一定进化代数内达到了适应度阈值，则认为找到了 最优解，算法终止：若在进化过程中适应度值在预先规定的一个最大进化代数内 未能达到适应度值阈值，算法终止。根据适应度值阀值以及设定的最大进化代数 可最终确定算法的终止条件。 基于遗传算法的p c b 板元件检测 第三章遗传算法的实现与应用 第三章遗传算法的实现与应用 3 1 本章概述 本章主要介绍采用遗传算法检测p c b 板元器件安装质量。首先介绍p c b 板元 器件检测的基本原理。然后介绍简单遗传算法搜索匹配子图的实现。鉴于简单遗 传算法具有较高的不确定性，所以通过改进简单遗传算法的杂交算子，引入代问 差分杂交算子。利用代间差分遗传算法实现搜索匹配子图。并比较代间差分遗传 算法与简单遗传算法搜索匹配子图的性能，证明代间差分遗传算法比简单遗传算 法在搜索匹配子图上速度更快、效率更高。 3 2p c b 板元件检测的基本原理 p c b 板的生产需要经过多道工序，在焊接元器件这道工序，由于焊接元器件 种类多、数量大，容易发生漏焊和焊接错误。依靠传统的人工检验方法容易发生 疏漏，检验速度也无法满足大规模生产的需要。所以般采用图像模板匹配的方 法来实现p c b 板元件的自动检测。其基本原理是将浚器件表面图像作为图像模 板，检测需要焊接该器件的区域是否存在与图像模板相类似的图像，从而来判断 该区域元器件焊接是否正确。该算法无需对图像进行分割和特征提取处理，而只 在原始图像数据上进行运算，从而保留了图像的全部信息。图像模板匹配方法通 常采用全局搜索法，即将模板与搜索图作逐点匹配运算，这种搜索匹配模块的计 算量是非常大的，为了减少计算量，本文使用简单遗传算法对其进行优化，加快 其检测速度。 以检测电阻为例，检测的目的是检查p c b 板上应焊接某一阻值电阻的区域 是否焊接了其他阻值的电阻或者发生漏焊。例如在规定的坐标上应焊接5 l 欧姆 电阻，那么就需检测该区域是否焊接了该阻值的电阻，有没有发生焊接了其他阻 值电阻的情况，或者发生漏焊的情况。如图3 1 所示，以该阻值电阻的数字图像 “5 1 0 ”作为图像模板t ，取应焊接该电阻区域的图像作为搜索图i 。 图3 1 模板t 和搜索图i 2 0 基于遗传算法的p c b 板元件检测 第三章遗传算法的实现与应用 图像匹配算法利用相关函数来计算两幅图像的相关系数值。设搜索图i 的像 素为尸q ，模板t 的像素为m n ，在搜索图i 上取像素为m n 的子图酽y ， ( x ，_ y ) 为这块子图左上角像素点在搜索图i 中的坐标。模板t 和子图f “的相似 程度用d ( x ，y ) 表示， mn d ( x ，y ) = i s 州( ，2 ，n ) - r ( m ，珂) 2 3 - 1 其中r7 伍和，血彬分别为子图铲，和模板t 中坐标池对应的图像像素值。 展开( 3 1 ) 式， mnmnmn d ( x ，y ) = 【s 。“( 川， ) 】2 2 s ”慨甩) t ( m ， ) + r ( 珊，胛) 】2 ( 3 2 ) m = ln = lm = ln = lm = - in = l ( 3 2 ) 式右边的第l 项是子图r 的能量，与( x ，y ) 有关：第3 项是模板t 的能量， 在模板确定时为一个常数；第2 项是子图9 与模板t 的互相关，模板t 与子图 p 匹配时这一项的取值最大。由此可以使用归一化相关函数作为模板和子图的 相似性度量； r ( x ，y ) = mn ( 脚，n ) x t ( m ，玎) ( 3 3 ) 计算搜索图i 中每个子图r7 与模板t 的相关函数r ( x ，y ) 的值，即从左上角 第一个子图开始，从左往右、从上往下每次移动一个像素，计算得到整个图像的 一个相关曲面，如图3 2 所示： 基于遗传算法的p c b 板元件检测第三章遗传算法的实现与应用 图3 2 图像的相关曲面图 从图3 2 中不难发现，相关函数r ( x ，j ，) 的值大于0 6 ，且在多个区域内具有 大于o 8 的较高峰值，使得整个分布呈多极值分布，这样的分布采用遗传算法进 行优化容易出现局部收敛的情况，增加误检测的概率，因此本文将归一化相关函 数r ( x ，y ) 做如下改进； r ( x ，y ) = ( 3 4 ) ( 3 4 ) 式q b s x , y 表示子图p 中所有像素值的平均值，于表示模板t 中所有像素值 的平均值。由此可以得到一个新的整个图像的相关曲砸，如图3 3 所示 图3 3 改进归一化函数后图像的相关曲面图 基于遗传算法的p c b 板元件检测 第三章遗传算法的实现与应用 从图3 3 中可以看出改进归一化相关函数斤的值只有在图像匹配区域附 近具有较高的峰值，其余区域的峰值都相对较小，不高于o 4 。同时峰值附近连 续变化，即在最大相关度值附近的子图p 7 和模板t 的相关度值是逐渐变化的。 那么这种单峰值连续的分布就非常有利于简单遗传算法的快速收敛，找到匹配图 像，降低误检测的概率。 3 3 简单遗传算法( s g a ) 的实现 如果采用全局搜索匹配子图的方法，需要计算 o n t ( ( p 一) 一n ) 0 5 ) 个子图与模板的匹配程度，用归一化相关函数求 图像匹配的计算量非常大，显然需要花费大量的搜索时间。而其中除匹配子图外， 其余计算都是无效计算，因此可利用遗传算法快速寻优、鲁棒性强的特点进行优 化，加快检测速度。 简单遗传算法的实现步骤如第二章所述，即首先对欲求解问题进行编码，基 于这种编码方式，随机产生组染色体作为进化起点的第一代群体，并且计算每 个个体的适应度值。接着从这些个体中通过一定的选择策略选择个体作为父本， 使用杂交算子和变异算子对父本进行交叉和变异，这样通过选择和繁殖就产生了 下一代种群。反复上述选择和繁殖过程，直到找到达到适应度阈值的染色体，即 目标最优解。 3 3 1 确定编码方案 由于一般情况下，实数编码比二进制编码直观、方便，同时更能有效克服采 用二进制编码带来的例如汉明悬崖“。等一系列问题，所以本文中编码方案选择实 数编码。 3 3 2 确定遗传操作算子 遗传操作包括