An Evolutionary-Strategy-Based CHC Genetic Algorithm and Its Application to Rock Spectrum Discrimination
-
摘要: 野外实测岩性波谱数据的数据挖掘可以为高光谱遥感建模提供依据.针对实测波谱数据的特点, 设计了一种基于Monte Carlo抽样进化机制的CHC (cross generation elitist selection, heterogeneous recombination, cataclysmic mutation , 跨世代精英选拔、异物种重组、灾变变异) 遗传算法用于多类岩性判别.应用于云南北衙金矿蚀变岩的识别, 表明该方法具有快速高效性.Abstract: Data mining from field rock spectrums is important for hyper-spectral remote sensing modeling. The characteristics of the field spectrum data are used to reform and combine evolutionary strategies with CHC (cross generation elitist selection, heterogeneous recombination and cataclysm mutation) and to design a genetic algorithm to conduct rock spectrum discrimination: to build a linear discriminating equation with many variables (wavelength intervals). Floating encoding is used for the coefficients of the equation (genes). Two optimization objectives are compared with each other: one is to maximize the right-judgment ratio of known samples, and the other is to minimize the ratio of in-class versus between-class distances. The results show that the former is briefer and faster while both of them are effective. Monte Carlo sampling is employed to adjust searching spaces. Uniform and Gaussian distribution models are employed to produce new-generation genes, showing that the former model has better performance, because the genes have various unknown distributions. An experimental study is presented based on the data of 1 823 wavelength intervals from Beiya gold deposit, Yunnan, China, obtained with the FieldSpectr Fr equipment (ASD Co. US). The algorithm proves high efficiency in identification of altered dolomitic limestone, a potentially gold-bearing rock, from other rocks.
-
0. 引言
CHC GA (cross generation elitist selection, heterogeneous recombination, cataclysmic mutation, genetic algorithm) 是Eshelman[1]1991年提出的一种对传统遗传算法的改进算法, 它有3个特点: 跨世代精英选拔(将父代和子代个体混合起来选择新一代个体)、异物种重组(当2个父代个体有充分差异时才进行交叉, 否则该2个体之间不交叉) 和灾变变异(随机选择部分个体进行完全初始化, 而不是个体个别位值的翻转).进化策略(evolutionary strategies, ES) 是进化计算的一种[2], 它通过搜索方向和步长的自适应调节, 直接在解空间上进行交叉、变异等操作.
随着高光谱遥感的兴起, 光谱数据挖掘成为近年来的一个研究热点[3].野外实测岩性波谱数据与高光谱遥感数据虽然随测量仪器设备不同而在波长分辨率、波段范围、光谱变质情况等方面会有一定差异, 但其基本内容方面是一致的.前者对于岩性识别具有高度可靠性, 是建立高光谱遥感地面模型的重要依据.我们利用美国ASD公司生产的野外光谱仪FieldSpectr Fr, 在云南北衙金矿获取了不同岩性露头的一批波谱数据.本文以这些数据为试验对象, 将ES和CHC结合起来并加以改造, 设计了一种适于岩性光谱识别的独特的遗传算法, 显示了很好的应用效果.
1. 野外光谱数据及岩性识别数学模型
1.1 数据
FieldSpectr Fr野外光谱仪测量的数据是岩石露头(及其他地物) 在350~2 500 nm范围内各波长点上的太阳光反射率与白色标准板反射率的比值.在可见光-近红外波段(350~1 050 nm) 取样间隔为0.7 nm, 光谱分辨率3 nm; 在短波红外线(900~2 500 nm) 部分, 采样间隔为2 nm, 光谱分辨率为10~12 nm.仪器对数据自动进行插值处理, 使全部取样间隔都表现为1 nm.在约1 350~1 420 nm和1 850~1 920 nm 2个大气水吸收带, 标准白板和地物反射率都很低, 其比值波动剧烈、信噪比难以掌握, 故分析时避开了这些波段.由于野外光谱测量中影响因素很多, 波谱数据一般只有相对准确性, 光谱曲线的高低不能准确反映岩石露头实际反射率大小, 而曲线形态反映不同波长上反射率相对大小比较可靠.为了弱化绝对值影响而突出曲线形态的作用, 笔者采用求一阶、二阶导数和相对吸收指数的方法进行数据预处理.例如一个典型样品的相对反射率及其一阶导数曲线(图 1).
图 1 深灰色白云质灰岩露头的相对反射率及其规格化一阶导数曲线Fig. 1. Spectrum curves of relative reflectance and its normalized one-order differential of a dark gray dolomitic limestone outcrop1.2 数学模型
为进行岩性识别, 构造包含一个线性判别函数和一个判别得分阀值向量的多类判别模型.设共有S个已知样品(岩石露头), 分为G类.线性判别函数及阀值向量为:
(1) 其中xj为每个波长点上的反射率比值一阶导数(也可为其他预处理结果), cj和c0是系数和常数项.阀值向量T将实数值域分为G个区间, 每一类对应一个区间, 使各已知样品的目标值fi尽量落在它们所属的类所对应的区间内.为了获得T、c0和cj, 采用以下2种优化方案: (1) 直接以已知样品的判对率最大为优化目标. (2) 以距离比指标I尽量大为优化目标.I的计算如下:
(2) 式中DInterG表示目标值f的平均类间距离; DInterG, max和DInterG, min表示组间距离的最大和最小值; DInG为组内离差平方和的平均值.当I值达到足够大时, 各类样品的目标值将分别集中于其重心附近, 而不同类之间距离将会拉开, 此时, 按重心值排序后, 取各对相邻类重心的中值为临界值, 可以期待较好的判对率.这里I比一般Fisher准则[4]多考虑了组间距离的极差.在多于两类判别的情况下, 考虑到类间距离的极差有助于在优化过程中使类间距离趋向均匀, 避免使其中有些类之间相距远到无必要的程度, 而另一些类之间很近以致无法区分.
2. 遗传算法设计
遗传算法的一般过程是, 在一系列算法设置如编码方法、染色体定义、群体规模、适应度定义、搜索终止条件等之后, 按照“生成初始种群→计算适应度→终止条件判断→选择→交叉→变异→计算适应度”的步骤循环搜索[5].笔者针对岩石波谱数据特点, 各环节设计如下.
2.1 算法设置和初始种群
由于变量很多(在剔除大气水吸收带后仍有约2 000个), 故为典型的高维搜索, 此时采用一般的二进制编码是不合适的[6].笔者采用实数编码, 根据前述2种优化方案来定义适应度、染色体(个体) 和基因: 当直接以判对率为优化目标时, 判对率即为适应度; 以距离比为优化目标时, I值为适应度.2种方案均以系数向量和相应的阀值向量共同构成染色体, 这些向量的实值元素为基因.群体规模(用p表示) 对搜索效率有影响, 本文的大量试算表明, p=120左右是较好的选择.终止条件除最大世代数、最长搜索时间外, 2种方案均当达到满意判对率时终止.这是因为当以距离比为适应度时, 常在I值尚未达到其极值前的某些世代, 各类间距离已充分变大, 类内离差也已充分缩小, 达到了最好判对率, 此时的多类判别函数已具备了准确判别的效能, 不必继续搜索(若继续搜索, 很可能使判对率回落); 另外, I的极大值不可预知, 不能用I确定适当的满意适应度.初始种群用一定区间内的随机数来产生: 设用符号R (a, b) 表示区间(a, b) 上均匀分布的随机数, r为任意选择的10.0~100.0之间的一个正数, 我们用R (-r, r) 来初始化每个基因.
2.2 判对率的计算
无论采用上述哪种适应度定义, 计算判对率之前都需进行局部搜索以获取最佳的阀值向量.对应于每个个体的系数向量C, 求出所有已知样品的判别目标值并求出各类重心, 将类重心从小到大排序, 设排序后2个相邻类重心为ak和ak+1, 生成p个随机数tki=R (ak, ak+1) 作为阀值向量中第k个候选阀值, 从而得到阀值向量的群体, 选其中判对率最大者为本世代与C关联的阀值向量.
2.3 选择
选择的具体方法因下述交叉算子的不同而不同.若采用“均匀分布交叉”, 直接从父代群体中选择最好(适应度最大) 的p/2个体; 若采用“高斯分布交叉”, 则只选择2个父代个体, 一个是最好的个体, 另一个代表本世代平均水平(按适应度排序后取第p/2个).
2.4 交叉
不同于一般遗传算法中截取交换位串的交叉方法, 我们通过Monte Carlo抽样来实现交叉.交叉操作仅作用于系数向量(而阀值向量则如上述, 通过局部搜索得到), 方法有2种:
(1) 均匀分布交叉.将所选出的p/2个个体随机两两配对, 每对生4个孩子, 取代2个父代个体, 最终得到p个子代个体.用符号max (a, b) 和min (a, b) 分别表示2个数a和b中较大和较小者, 生成子代个体方法如下: 设2个父代个体的第j个基因分别为aj和bj, 整个父代种群中最好个体的第j个基因为vj, 欲产生的子代个体的第j个基因为xj, 按下式生成xj:
(3) 其中h=|aj-bj|/2.0.
(2) 高斯分布交叉.用N (m, d) 表示均值为m, 标准差为d的正态分布随机数.设所选出的最好父代个体的第j个基因aj, 代表父代种群中平均水平的个体的第j个基因为bj, 欲产生的子代个体的第j个基因为xj, 按下式生成p个xj:
(4) 以上2种交叉算子都通过调整搜索区间而体现了算法的自适应进化, 同时, 每个世代每个基因都会在不同的(可能重叠的) 区间内进行搜索, 由此体现“异物种重组”.这里借鉴了Georges等[7]1999年提出的压缩遗传算法(compact GA) 中独立处理每个基因的思路, 实验证明效率很高.
2.5 变异
采用如下的灾变变异策略: 从交叉后产生的子代群体中随机选择R (1, p/4) 个个体进行变异.设欲生成的个体的第j个基因为xj, 整个父代群体中第j个基因的最大值和最小值分别为cj, max和cj, min, 则xj=R (cj, min-r/2, cj, max+r/2).这意味着在更大的区间内随机初始化.
2.6 跨世代精英选拔
为确保每代最好个体不差于父代, 随机选一个子代个体, 用父代最好个体取而代之.这样可能恰好去掉了一个比父代最好个体还好的子代个体, 但这种风险不大, 因为如果群体规模p>100, 则该事件发生的概率将小于0.01.
图 2 4种流程的进化曲线1.流程①进化曲线; 2.流程②进化曲线; 3.流程③进化曲线; 4.流程④进化曲线; 5.流程③判对率曲线; 6.流程④判对率曲线Fig. 2. Evolutionary curves of the four algorithms2.7 算法流程
2种交叉方法和2种适应度定义可相互组合形成4种算法流程: ①均匀分布重组-判对率; ②高斯分布重组-判对率; ③均匀分布重组-距离比; ④高斯分布重组-距离比.这些流程的其他环节一致.
3. 应用及结论
以云南北衙金矿笔架山18个露头波谱岩性识别为例, 共3类岩性, 故分为3类判别问题.选每类岩性的部分样品为已知样品, 留一部分假设为“未知”样品, 用于检验识别效果.数据预处理方法为求一阶导数, 选350~1 320, 1 450~1 820和1 920~2 400 nm共1 823个波长点(变量) 参与计算.取群体规模p=120, 种群初始化时取r=50.0, 满意判对率0.95. 4种流程的进化曲线如图 2, 岩性识别结果如图 3.
图 3 4种流程的岩性识别结果1, 2, 3类岩性分别为深灰色白云质灰岩、红灰色蚀变破碎白云质灰岩及灰白色风化正长斑岩; 各方框下面3行为3类已知样品回判结果; 各方框最上面1行为“未知”样品判别结果, “1/1”表示本来属于第1类而被判为第1类, 其余类推Fig. 3. Rock discrimination results of four algorithms由图 2可见, 流程①、②在第1和第2世代时即达到搜索目标, 流程③、④分别在第7代和第14代时达到搜索目标(已知样品判对率达100%, 超过满意判对率).运行效率都很高(运行时间最长的流程④约需1s), 但总的来说, 直接以判对率为适应度比以距离比为适应度要好, 前者可以更充分地体现遗传算法黑箱式自适应进化的特点; 均匀分布交叉比高斯分布交叉效果好, 后者较多地强调了每一世代父代群体中最好个体的利用, 这在进化的初期是不利的, 因为在进化初期的若干世代, 每代的最好解都很可能远不是最终的最好解.
由图 3可见, 各个算法流程对7个“未知”样品的判别都达到85%以上的正确率, 说明这些算法可以较有效地用于岩性波谱识别.尤其可以区分出蚀变白云质灰岩, 在北衙金矿该类岩性是重要含矿岩性, 故本文所论述的遗传算法在类似地区高光谱遥感找矿中将会有较好的应用前景.
野外工作得到云南地质三队和北衙金矿的大力帮助, 在此深表谢意 -
图 1 深灰色白云质灰岩露头的相对反射率及其规格化一阶导数曲线
Fig. 1. Spectrum curves of relative reflectance and its normalized one-order differential of a dark gray dolomitic limestone outcrop
图 2 4种流程的进化曲线
1.流程①进化曲线; 2.流程②进化曲线; 3.流程③进化曲线; 4.流程④进化曲线; 5.流程③判对率曲线; 6.流程④判对率曲线
Fig. 2. Evolutionary curves of the four algorithms
-
[1] Eshelman L J. The CHC adaptive search algorithm: how to have safe search when engaging in non-traditional genetic recombination[A]. In: Gregory J E, ed. Foundations of genetic algorithms[C]. San Meteo, CA: Morgan Kaufmann Publishers, 1991. 265-283. [2] Back T, Hoffmeister F, Schwefel H P. A survey of evolution strategies[A]. In: ICGA, ed. Proceedings of the fourth international conference on genetic algorithms [C]. San Meteo, CA: Morgan Kaufmann Publishers, 1991. 2-9. [3] Mustard J F, Sunshine J M. Spectral analysis for earth science: investigations using remote sensing data[A]. In: Renz A N, ed. Remote sensing for the earth science: manual of remote sensing(vol. 3)[C]. New York: John Wiley & Sons, 1999. 251-360. [4] 王学仁. 地质数据的多变量统计分析[M]. 北京: 科学出版社, 1982. 147-155.WANG X R. Multi-variable statistics for geological data [M]. Beijing: Science Press, 1982. 147-155. [5] Goldberg D E. Genetic algorithms in search, optimization and learning[M]. New Nork: Addison-Wesley, 1989. 1-83. [6] 王秀峰. 实数编码的遗传算法及其在逆变器馈电交流电机中的应用[J]. 自动化学报, 1998, 24(2): 250-253. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO802.018.htmWANG X F. Genetic algorithm using floating encoding and its application to inverter-fed induction machines[J]. Acta Automatica Sinica, 1998, 24(2): 250-253. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO802.018.htm [7] Georges R H, Fernando G L, David E. The compact genetic algorithm[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 287-297. https://ieeexplore.ieee.org/document/797971 -
下载:
下载:
点击查看大图
计量
- 文章访问数: 3378
- HTML全文浏览量: 71
- PDF下载量: 1
- 被引次数: 0
