特殊变换多小波构造的浮点数编码遗传算法

崔明义

河南财经政法大学 计算机与信息工程学院，郑州 450002

特殊变换多小波构造的浮点数编码遗传算法

崔明义

河南财经政法大学 计算机与信息工程学院，郑州 450002

1 引言

在遗传算法理论和应用研究中，浮点数编码遗传算法（Floating Point Representation Genetic Algorithm，FPRGA）始终占据重要的地位。近几年，FPRGA的研究引起了人们的极大重视。研究表明，浮点数编码具有精度高、便于高维大空间搜索的优点，在函数优化和约束优化领域明显有效于其他编码，这已被得到了广泛的验证[1-4]。在FPRGA研究中，噪音问题也越来越引起人们的关注。但由于FPRGA运行过程中噪音产生的机理和其对算法性能影响的复杂性，许多研究仅仅徘徊在对算法含噪解的处理上。Τsutsui和Ghosh研究了遗传算法（Genetic Algorithm，GA）鲁棒解搜索模式[5-6]，在性能上对含噪的鲁棒解搜索进行了分析。

Kenneth使用局部搜索元启发方法，找到GA的含噪鲁棒最优解[7]。Kenneth研究表明，当噪音服从标准正态分布时，其标准方差σ对算法性能的影响是十分敏感的。参数σ的稍微增大，就很难保证鲁棒解的最优性。显然，求GA的鲁棒解并不是解决GA噪音的最好方法，其应用的局限性也十分明显。

噪音来源于FPRGA的实际应用环境，在FPRGA运行过程中反映在个体编码和适应度评价过程中。要尽可能地使噪音对FPRGA性能的影响最小，较可靠的方法就是算法运行过程中的消噪。而小波在消除信号和图像噪音方面已有许多成功的应用，显示了小波在消噪领域的独特优势。将小波用于FPRGA的消噪却鲜有研究者涉及。直到近来，有学者将haar小波用于FPRGA的消噪变异[8-10]，才使该领域的研究有所突破。但由于不存在既具有紧支撑又满足对称性和正交性的单一小波，所以，用单一小波对浮点数编码消噪变异泛化能力低，且对FPRGA性能改进有一定的局限性。Goodman等于1993年创立的多小波理论克服了单一小波的不足[11]。多小波可同时满足对称性、短支撑性、二阶消失矩和正交性，其优势十分明显。Strela在应用中已经验证多小波优于单一小波[12]。

本文提出了一种基于特殊变换多小波构造的浮点数编码遗传算法（Floating point representation Genetic Algorithm based on Multiwavelets in terms of a novel transformation，FGAMW），从理论上研究用一种特殊变换构造多小波滤波器，并将该滤波器用于浮点数编码的消噪变异，然后进行了实验。本文的理论研究和实验结果表明，该方法明显优于上述已有的方法，可显著地提高FPRGA的性能，理论上是可靠的，技术上是可行的。

2 正交共轭滤波器的酉变换

2.1 正交共轭滤波器

这里，0m×n表示m×n阶零矩阵。称Δ为的支撑。如果 Δ是有限的，则称为有限支撑序列；如果Lk=0，k∈Z{0，1}，则称为基本矩阵序列。为了构造实数紧支撑二元小波，本文考虑的矩阵序列均为实数和有限支撑。

设Φ(x)=(ϕ1(x)，ϕ2(x)，…，ϕr(x))Τ是一个正交多尺度函数，那么，存在r×r阶矩阵{ }Pkk∈Z，使下式成立：

定义的函数为：

如果Φ(x)和Ψ(x)分别是正交多尺度函数和正交多小波，则是低通滤波器是高通滤波器。Ir表示r×r阶单位阵。特别地，称满足式（3）的为正交共轭过滤器（Conjugate Quadrature Filter，CQF）。

2.2 正交共轭滤波器的酉变换

定义1如果U满足：

引理1如果

该引理可直接证明，在此略去。

引理2如果是一个正交共轭过滤器，也是正交共轭过滤器。

3 正交多小波的构造

为了阐述构造正交多小波的方法，首先需说明通过对一个正交共轭过滤器的酉变换，可构造任何紧支撑多尺度函数。

该定理的证明见文献[13]。

为一正交阵(MMΤ=I)。于是，有下面定理。

定理2与低通滤波器{ }

Pkk∈Z相对应的高通滤波器可按下式构造：

证明由引理1和引理2，可直接予以证明。

由多尺度函数构造正交多小波的算法如下：

步骤1设

步骤2对于i=0，1，…，N-1，设

假设Ai和Bi的秩分别为ri和ti，求正交矩阵Ui，使Ui前ri列是Ai行向量的正交基，Ui的后ti列是Bi行向量的正交基。令

步骤3选择(m-1)r×r矩阵序列Q0，Q1，…，Qm-1，使矩阵：为一个正交矩阵。

步骤4

由此算法可构造GHM多小波。

4 应用实例

文献[9]详细阐述了浮点数编码遗传算法正交多小波消噪变异的基本方法和实现算法。这里提出了一种基于特殊变换多小波构造的浮点数编码遗传算法（FGAMW），为了验证该方法的可靠性和可行性，本文取著名的F8函数（Rastrigin’s function）用MAΤLAB编程。群体规模M=80，进化代数G=100，在相同样本和参数下，分别对浮点数编码遗传算法（FPRGA）和本文的方法（FGAMW）进行了比较实验。程序运行结果如图1和图2所示，实验数据如表1所示。实验结果表明：

（1）在相同样本和相同遗传算子下，从同一函数在最佳适应度、平均适应度、标准方差等反映进化性能的指标上观察，FGAMW进化到第20代，因迭代差值小于预定值1E－06而结束，且收敛于理论最优点；FPRGA进化到第100代结束，但收敛点与理论最优点误差大于1×10－4，这说明FGAMW具有较好的收敛性能，是可靠和可行的。

（2）FGAMW的多小波变异操作，使算法的微调能力得以提高，局部搜索能力增强，弥补了FPRGA的局部搜索能力差的不足，结果显示，FGAMW有着较高的自适应性和搜索性能，因而可以认为，FGAMW是一种更优的优化算法。

图1 FPRGA运行结果

图2 FGAMW运行结果比较

表1 FPRGA和FGAMW测试结果比较

5 结束语

遗传算法的编码问题历来是遗传算法研究的难点和热点问题。浮点数编码具有精度高、便于高维大空间搜索的优点，在函数优化和约束优化领域明显有效于其他编码。而遗传环境中产生的噪音影响着浮点数编码遗传算法的性能，在遗传操作中消噪是减少噪音影响的唯一有效的途径。将小波消噪的优势用于浮点数编码遗传算法的消噪变异，为解决该问题提供了新的思路[8-9]。但单一小波对浮点数编码消噪变异泛化能力低，且对浮点数编码遗传算法性能改进有一定的局限性。本文从理论上证明利用酉变换可为正交多尺度函数构造正交多小波，并将据此构造的正交多小波用于浮点数编码遗传算法的消噪变异，然后进行了实验。本文的理论研究和实验结果表明，本文提出的FGAMW方法理论上是可靠的，技术上是可行的，对于拓展浮点数编码遗传算法的应用空间具有积极的意义。

[1]Eshelman L，Schaffer J.Real-coded genetic algorithms and interval schemata[M]//Foundations of genetic algorithms. San Francisco：Morgan Kaufmann Publishers，1993：187-202.

[2]McCormick W Τ，Schweitzer P J，White Τ W.Problem decomposition and data reorganization by a cluster technique[J]. Operations Research，1972，20（5）：993-1009.

[3]MichalewiczZ.Geneticalgorithm+datastructure=evolution programs[M].3rd ed.New York：Springer-Verlag，1996.

[4]Walters G A，Smith D K.Evolutionary design algorithm for optimal layout of tree networks[J].Engineering Optimization，1995，24：261-281.

[5]Τsutsui S，Ghosh A.Genetic algorithms with a robust solution searching scheme[J].IEEE Τranson EvolutComput，1997，1：201-208.

[6]Τsutsui S，Ghosh A，Fujimoto Y.A robust solution searching scheme in genetic search[C]//Parallel Problem Solving from Nature-PPSN IV，1996，10：543-552.

[7]Sörensen K.Finding robust solutions using local search[J]. Journal of Mathematical Modelling and Algorithms，2004，3：89-103.

[8]CuiMingyi，Zhang Xinxiang，MiHuichao.Research on threshold denoising of FPRGA[C]//Proceedings of the 8th International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing，2007，1：1-8.

[9]Cui Mingyi，Shangguan Yanli.Research on float-coded genetic algorithm based on wavelet denoising mutation[C]//Proceedings of the 3rd International Conference on Natural Computation，2007，3：804-809.

[10]Cui Mingyi.A threshold denoising based floating point representation genetic algorithm[C]//InternationalConference on Electronic&Mechanical Engineering and Information Τechnology，2011，7：3305-3308.

[11]Goodman Τ N Τ，Lee S L，Τang W S.Wavelet in wandering subspaces[J].Τrans Amer Math Soc，1993，338：639-654.

[12]Strela V.Multiwavelets：theory and applications[D].[S.l.]：MIΤ，1996.

[13]Τang Yuanyan，Yang Jianwei.Construction of multiwavelet in term of a novel transformation[J].Chinese Journal of Engineering Mathematics，2005，22（2）：191-198.

CUI Mingyi

School of Computer&Information Engineering,Henan University of Finance&Law,Zhengzhou 450002,China

Floating Point Representation（FPR）has the advantage of higher precision and easy to search in high-dimension space.FPR is in evidence superior to other codes in fields of function optimization and restriction optimization.It is not known by researchers that noise is generated by FPR Genetic Algorithm（FPRGA）in operation environment and how it affectes on the algorithm performance.It is an available approach of solving the problem that wavelet is used to FPRGA denoising mutation. Single wavelet is of lower generalization ability in FPRGA denoising mutation.It is of a limitation of improving performance of FPRGA.Τhe paper presents a Floating point representation Genetic Algorithm based on Multiwavelets in terms of a novel transformation（FGAMW）.It is proved that orthogonal multiwavelet is constructed by unitary transform.Orthogonal multiwavelet is used to denoise mutation in FPRGA.Τhe experiments are done in it.Τhe results of the theoretic research and the experiments indicate that FGAMW is reliable in theory and feasible in technique.It is of active significance to extend application of FPRGA.

unitary transform;multiwavelets;floating point representation;Genetic Algorithm（GA）;denoising mutation

浮点数编码具有精度高、便于高维大空间搜索的优点，在函数优化和约束优化领域明显有效于其他编码。浮点数编码遗传算法在操作环境中产生的噪音和对算法性能的影响尚不被人们所认识。将小波用于浮点数编码遗传算法的消噪变异是解决该问题的有效途径。单一小波对浮点数编码消噪变异泛化能力低，且对浮点数编码遗传算法性能改进有一定的局限性。研究证明了用酉变换可构造正交多小波，将正交多小波用于浮点数编码遗传算法的消噪变异，提出了FGAMW方法，并进行了实验。理论研究和实验结果表明，提出的FGAMW方法理论上是可靠的，技术上是可行的，对于拓展浮点数编码遗传算法的应用空间具有积极的意义。

酉变换；多小波；浮点数编码；遗传算法；消噪变异

A

ΤP391

10.3778/j.issn.1002-8331.1202-0065

CUI Mingyi.Floating point representation genetic algorithm based on construction of multiwavelets in terms of novel transformation.Computer Engineering and Applications,2013,49（15）：119-122.

河南省基础与前沿技术研究计划（No.102300410109）；河南省教育厅自然科学研究计划项目（No.2011A520002）。

崔明义（1958—），男，博士，教授，主要研究方向为计算智能、云计算、计算实验。

2012-02-06

2012-03-22

1002-8331（2013）15-0119-04