论文部分内容阅读
摘 要对采集到的图像进行预处理后，利用遗传算法识别煤气表数字，用二进制编码的方法，按照优胜劣汰和适者生存的原理，逐代演化产生出越来越好的近似解，在图像区域内进行快速搜索，不需提取任何图像特征，就可以对数字进行识别，快速有效。
关键词遗传算法；数字识别；二进制编码
中图分类号TP 文献标识码A文章编号1673-9671-(2011)111-0209-01
在对煤气表数字进行识别之前，需对采集的图像进行预处理，包括：对图像进行灰度化、二值化、号码区域定位和倾斜矫正，接下来，采用遗传算法对数字进行识别。
1遗传算法包括三个基本操作：选择、交叉和变异
选择是确定重组或交叉的个体，被选个体将产生多少个子代个体，先要计算适应度。基因重组是结合来自父代交配种群的信息产生新的个体，依据个体编码表示方法发的不同有实值重组和二进制交叉两种方法。交叉之后的变异，是子代基因按小概率扰动产生的变化，分为实值变异和二进制变异。
利用遗传算法时，要事先选择一些参数，其中包括：染色体的长度、种群大小、交叉率、变异率等，这些参数对遗传算法的性能有重要的影响。选择数目较大的初始种群可以同时处理更多的解，比较容易找到全局最优解，但是缺点是增加迭代时间，一般取20-100。变异率通常取很小的值，如取高变异率，可能会引起不稳定。交叉操作的频率越高，越能快速的收敛到最有希望的最优解，因此一般选较大的交叉率，取值0.4-0.9。问题求解的精度越高，染色体长度越长，同时种群要设置大一些。对于具体问题，参数是否设置恰当，要根据多次运行的收敛和解的质量来判断。
2遗传算法求解的过程
1）编码。GA在搜索前，将问题解空间的可行解表示成遗传空间的基因型串结构数据，串结构数据的不同组合构成了不同的可行解。
2）生成初始种群。随即产生n个初始串结构数据，n个个体组成一个群体，GA以该群体作为初始迭代点。
3）适应度的评价。不同的问题，适应度函数定义方式也不相近相同，根据标准计算适应度，个体解的优劣性通过适应性函数表明。
4）选择。从当前群体中选择优良的个体，使它们有机会被选中进入下一次迭代，作为父代繁衍子孙。
5）交叉。得到新一代个体，体现信息的交换。
6）变异。随机选择一个个体，对这个个体随机改变个体某位基因的值。
7）对子代重复进行3）到6）的操作，进行新一轮的遗传过程，直到找到最优解或准最优解。
主程序设计多次运行遗传算法的过程，每次运行时输入不同的参数，运行结束后把进化过程的统计结果写入输出数据文件中。首先进行初始化initilaize( )，初始化包括：获取算法参数，计算染色体字节长度，分配数据空间，产生初始种群，输出初始代统计信息等。然后进入进化计算，每一代进化计算调用generation( )函数产生新一代种群，调用statistics( )计算新一代种群的统计信息，将统计信息写入输出数据文件。
3算法实现步骤
3.1问题的描述
设检索数字标准模式用序列P描述为：
P={p（x1，y1），p（x2，y2），…p（xn，yn）}
二值图像，定义代检索标准模式与图像中相似图形的匹配率R作为检索性能的评价指标，0≤R≤1。
R=nb/N
式中nb为点序列Q中满足p（xi*，yi*）=p（xi，yi）（i=1，2，…，N）的点个数。
如果匹配率R越大，表明检索到标准模式程度越高。
3.2染色体编码
定义遗传算法的个体Ik（k=1，2，…）基因型Gk为：
Gk=（xck，yck，Mk）其中xck，yck平移位置，Mk为模式放大倍数，对其分别用二进制进行编码。基因型Gk可看做三维空间中的一点，表现型
Hk为：
Hk={hk1（xk1*，yk1*），hk2 （xk2*，yk2*），…hkn（xkn*，ykn*）}
式中（xkj*，ykj*）=M*（xkj，ykj）+（xkc，ykc），（j=1，2，…，N）
为简化问题，假设图像搜索区域的大小是256×256。搜索的标准模式变化的参数范围是：xkc∈[0，255]，ykc∈[0，255]，Mk∈[0，15]。Mk表示在标准模式中的序号，对标准模式不进行放大缩小的计算，用16种大小的标准模式去搜索，基因型Mk表示标准模式的序号。在实际应用中这些参数可依据实际情况进行调整，编码总长度定义为20位。
3.3适应度定义
适应度函数是遗传算法中关键的一部分，好的适应度函数能从非最优个体进化到最优的个体，解决一些遗传算法中的问题，如过早收敛与过慢结束的矛盾。遗传算法的适应度函数不受连续可微的约束。
对二值图像来说，使用标准模式在搜索图像中匹配的点数与标准模式本身具有的点数之比，即：
R=nb/N
3.4遗传操作设定
将当代种群的个体按适应度按照由大到小的顺序进行排列，然后将一定比例的下位个体淘汰掉，淘汰比例一般为40%。实行两点交叉的方法，将生成的子个体填补到种群中，用这种方式来使种群规模保持不变，最后实行变异操作，变异概率设定位0.2，生成子代种群。
参考文献
[1]李晶皎等译.模式识别(第二版)[M].北京:电子工业出版社,2004.
[2]耿西伟,张猛.基于结构特征的分类BP网络的手写数字识别[J].计算机技术与发展,2007,17(l):35-36.
[3]Juliusz L,Kulikowski.The Role of Ontological Models in Pattern Recognition[J].Computer Recognition Systems,2005,30(3):43-52.
[4]田浩,等译.数字图像处理原理与应用[M].北京:清华大学出版社,2007.
[5]王小平,曹立明.遗传算法理论、应用于软件实现[M].西安:西安交通大学出版社,2002.
[6]彭文斌.基于Hopfield的脱机手写数字识别理论及算法[J].中国科技信息,
2009,6:87-90.
关键词遗传算法；数字识别；二进制编码
中图分类号TP 文献标识码A文章编号1673-9671-(2011)111-0209-01
在对煤气表数字进行识别之前，需对采集的图像进行预处理，包括：对图像进行灰度化、二值化、号码区域定位和倾斜矫正，接下来，采用遗传算法对数字进行识别。
1遗传算法包括三个基本操作：选择、交叉和变异
选择是确定重组或交叉的个体，被选个体将产生多少个子代个体，先要计算适应度。基因重组是结合来自父代交配种群的信息产生新的个体，依据个体编码表示方法发的不同有实值重组和二进制交叉两种方法。交叉之后的变异，是子代基因按小概率扰动产生的变化，分为实值变异和二进制变异。
利用遗传算法时，要事先选择一些参数，其中包括：染色体的长度、种群大小、交叉率、变异率等，这些参数对遗传算法的性能有重要的影响。选择数目较大的初始种群可以同时处理更多的解，比较容易找到全局最优解，但是缺点是增加迭代时间，一般取20-100。变异率通常取很小的值，如取高变异率，可能会引起不稳定。交叉操作的频率越高，越能快速的收敛到最有希望的最优解，因此一般选较大的交叉率，取值0.4-0.9。问题求解的精度越高，染色体长度越长，同时种群要设置大一些。对于具体问题，参数是否设置恰当，要根据多次运行的收敛和解的质量来判断。
2遗传算法求解的过程
1）编码。GA在搜索前，将问题解空间的可行解表示成遗传空间的基因型串结构数据，串结构数据的不同组合构成了不同的可行解。
2）生成初始种群。随即产生n个初始串结构数据，n个个体组成一个群体，GA以该群体作为初始迭代点。
3）适应度的评价。不同的问题，适应度函数定义方式也不相近相同，根据标准计算适应度，个体解的优劣性通过适应性函数表明。
4）选择。从当前群体中选择优良的个体，使它们有机会被选中进入下一次迭代，作为父代繁衍子孙。
5）交叉。得到新一代个体，体现信息的交换。
6）变异。随机选择一个个体，对这个个体随机改变个体某位基因的值。
7）对子代重复进行3）到6）的操作，进行新一轮的遗传过程，直到找到最优解或准最优解。
主程序设计多次运行遗传算法的过程，每次运行时输入不同的参数，运行结束后把进化过程的统计结果写入输出数据文件中。首先进行初始化initilaize( )，初始化包括：获取算法参数，计算染色体字节长度，分配数据空间，产生初始种群，输出初始代统计信息等。然后进入进化计算，每一代进化计算调用generation( )函数产生新一代种群，调用statistics( )计算新一代种群的统计信息，将统计信息写入输出数据文件。
3算法实现步骤
3.1问题的描述
设检索数字标准模式用序列P描述为：
P={p（x1，y1），p（x2，y2），…p（xn，yn）}
二值图像，定义代检索标准模式与图像中相似图形的匹配率R作为检索性能的评价指标，0≤R≤1。
R=nb/N
式中nb为点序列Q中满足p（xi*，yi*）=p（xi，yi）（i=1，2，…，N）的点个数。
如果匹配率R越大，表明检索到标准模式程度越高。
3.2染色体编码
定义遗传算法的个体Ik（k=1，2，…）基因型Gk为：
Gk=（xck，yck，Mk）其中xck，yck平移位置，Mk为模式放大倍数，对其分别用二进制进行编码。基因型Gk可看做三维空间中的一点，表现型
Hk为：
Hk={hk1（xk1*，yk1*），hk2 （xk2*，yk2*），…hkn（xkn*，ykn*）}
式中（xkj*，ykj*）=M*（xkj，ykj）+（xkc，ykc），（j=1，2，…，N）
为简化问题，假设图像搜索区域的大小是256×256。搜索的标准模式变化的参数范围是：xkc∈[0，255]，ykc∈[0，255]，Mk∈[0，15]。Mk表示在标准模式中的序号，对标准模式不进行放大缩小的计算，用16种大小的标准模式去搜索，基因型Mk表示标准模式的序号。在实际应用中这些参数可依据实际情况进行调整，编码总长度定义为20位。
3.3适应度定义
适应度函数是遗传算法中关键的一部分，好的适应度函数能从非最优个体进化到最优的个体，解决一些遗传算法中的问题，如过早收敛与过慢结束的矛盾。遗传算法的适应度函数不受连续可微的约束。
对二值图像来说，使用标准模式在搜索图像中匹配的点数与标准模式本身具有的点数之比，即：
R=nb/N
3.4遗传操作设定
将当代种群的个体按适应度按照由大到小的顺序进行排列，然后将一定比例的下位个体淘汰掉，淘汰比例一般为40%。实行两点交叉的方法，将生成的子个体填补到种群中，用这种方式来使种群规模保持不变，最后实行变异操作，变异概率设定位0.2，生成子代种群。
参考文献
[1]李晶皎等译.模式识别(第二版)[M].北京:电子工业出版社,2004.
[2]耿西伟,张猛.基于结构特征的分类BP网络的手写数字识别[J].计算机技术与发展,2007,17(l):35-36.
[3]Juliusz L,Kulikowski.The Role of Ontological Models in Pattern Recognition[J].Computer Recognition Systems,2005,30(3):43-52.
[4]田浩,等译.数字图像处理原理与应用[M].北京:清华大学出版社,2007.
[5]王小平,曹立明.遗传算法理论、应用于软件实现[M].西安:西安交通大学出版社,2002.
[6]彭文斌.基于Hopfield的脱机手写数字识别理论及算法[J].中国科技信息,
2009,6:87-90.