特殊變換多小波構(gòu)造的浮點數(shù)編碼遺傳算法

崔明義

河南財經(jīng)政法大學(xué) 計算機與信息工程學(xué)院，鄭州 450002

特殊變換多小波構(gòu)造的浮點數(shù)編碼遺傳算法

崔明義

河南財經(jīng)政法大學(xué) 計算機與信息工程學(xué)院，鄭州 450002

1 引言

在遺傳算法理論和應(yīng)用研究中，浮點數(shù)編碼遺傳算法（Floating Point Representation Genetic Algorithm，F(xiàn)PRGA）始終占據(jù)重要的地位。近幾年，F(xiàn)PRGA的研究引起了人們的極大重視。研究表明，浮點數(shù)編碼具有精度高、便于高維大空間搜索的優(yōu)點，在函數(shù)優(yōu)化和約束優(yōu)化領(lǐng)域明顯有效于其他編碼，這已被得到了廣泛的驗證[1-4]。在FPRGA研究中，噪音問題也越來越引起人們的關(guān)注。但由于FPRGA運行過程中噪音產(chǎn)生的機理和其對算法性能影響的復(fù)雜性，許多研究僅僅徘徊在對算法含噪解的處理上。Τsutsui和Ghosh研究了遺傳算法（Genetic Algorithm，GA）魯棒解搜索模式[5-6]，在性能上對含噪的魯棒解搜索進行了分析。

Kenneth使用局部搜索元啟發(fā)方法，找到GA的含噪魯棒最優(yōu)解[7]。Kenneth研究表明，當噪音服從標準正態(tài)分布時，其標準方差σ對算法性能的影響是十分敏感的。參數(shù)σ的稍微增大，就很難保證魯棒解的最優(yōu)性。顯然，求GA的魯棒解并不是解決GA噪音的最好方法，其應(yīng)用的局限性也十分明顯。

噪音來源于FPRGA的實際應(yīng)用環(huán)境，在FPRGA運行過程中反映在個體編碼和適應(yīng)度評價過程中。要盡可能地使噪音對FPRGA性能的影響最小，較可靠的方法就是算法運行過程中的消噪。而小波在消除信號和圖像噪音方面已有許多成功的應(yīng)用，顯示了小波在消噪領(lǐng)域的獨特優(yōu)勢。將小波用于FPRGA的消噪?yún)s鮮有研究者涉及。直到近來，有學(xué)者將haar小波用于FPRGA的消噪變異[8-10]，才使該領(lǐng)域的研究有所突破。但由于不存在既具有緊支撐又滿足對稱性和正交性的單一小波，所以，用單一小波對浮點數(shù)編碼消噪變異泛化能力低，且對FPRGA性能改進有一定的局限性。Goodman等于1993年創(chuàng)立的多小波理論克服了單一小波的不足[11]。多小波可同時滿足對稱性、短支撐性、二階消失矩和正交性，其優(yōu)勢十分明顯。Strela在應(yīng)用中已經(jīng)驗證多小波優(yōu)于單一小波[12]。

本文提出了一種基于特殊變換多小波構(gòu)造的浮點數(shù)編碼遺傳算法（Floating point representation Genetic Algorithm based on Multiwavelets in terms of a novel transformation，F(xiàn)GAMW），從理論上研究用一種特殊變換構(gòu)造多小波濾波器，并將該濾波器用于浮點數(shù)編碼的消噪變異，然后進行了實驗。本文的理論研究和實驗結(jié)果表明，該方法明顯優(yōu)于上述已有的方法，可顯著地提高FPRGA的性能，理論上是可靠的，技術(shù)上是可行的。

2 正交共軛濾波器的酉變換

2.1 正交共軛濾波器

這里，0m×n表示m×n階零矩陣。稱Δ為的支撐。如果 Δ是有限的，則稱為有限支撐序列；如果Lk=0，k∈Z{0，1}，則稱為基本矩陣序列。為了構(gòu)造實數(shù)緊支撐二元小波，本文考慮的矩陣序列均為實數(shù)和有限支撐。

設(shè)Φ(x)=(?1(x)，?2(x)，…，?r(x))Τ是一個正交多尺度函數(shù)，那么，存在r×r階矩陣{ }Pkk∈Z，使下式成立：

定義的函數(shù)為：

如果Φ(x)和Ψ(x)分別是正交多尺度函數(shù)和正交多小波，則是低通濾波器是高通濾波器。Ir表示r×r階單位陣。特別地，稱滿足式（3）的為正交共軛過濾器（Conjugate Quadrature Filter，CQF）。

2.2 正交共軛濾波器的酉變換

定義1如果U滿足：

引理1如果

該引理可直接證明，在此略去。

引理2如果是一個正交共軛過濾器，也是正交共軛過濾器。

3 正交多小波的構(gòu)造

為了闡述構(gòu)造正交多小波的方法，首先需說明通過對一個正交共軛過濾器的酉變換，可構(gòu)造任何緊支撐多尺度函數(shù)。

該定理的證明見文獻[13]。

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

定理2與低通濾波器{ }

Pkk∈Z相對應(yīng)的高通濾波器可按下式構(gòu)造：

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

由多尺度函數(shù)構(gòu)造正交多小波的算法如下：

步驟1設(shè)

步驟2對于i=0，1，…，N-1，設(shè)

假設(shè)Ai和Bi的秩分別為ri和ti，求正交矩陣Ui，使Ui前ri列是Ai行向量的正交基，Ui的后ti列是Bi行向量的正交基。令

步驟3選擇(m-1)r×r矩陣序列Q0，Q1，…，Qm-1，使矩陣：為一個正交矩陣。

步驟4

由此算法可構(gòu)造GHM多小波。

4 應(yīng)用實例

文獻[9]詳細闡述了浮點數(shù)編碼遺傳算法正交多小波消噪變異的基本方法和實現(xiàn)算法。這里提出了一種基于特殊變換多小波構(gòu)造的浮點數(shù)編碼遺傳算法（FGAMW），為了驗證該方法的可靠性和可行性，本文取著名的F8函數(shù)（Rastrigin’s function）用MAΤLAB編程。群體規(guī)模M=80，進化代數(shù)G=100，在相同樣本和參數(shù)下，分別對浮點數(shù)編碼遺傳算法（FPRGA）和本文的方法（FGAMW）進行了比較實驗。程序運行結(jié)果如圖1和圖2所示，實驗數(shù)據(jù)如表1所示。實驗結(jié)果表明：

（1）在相同樣本和相同遺傳算子下，從同一函數(shù)在最佳適應(yīng)度、平均適應(yīng)度、標準方差等反映進化性能的指標上觀察，F(xiàn)GAMW進化到第20代，因迭代差值小于預(yù)定值1E－06而結(jié)束，且收斂于理論最優(yōu)點；FPRGA進化到第100代結(jié)束，但收斂點與理論最優(yōu)點誤差大于1×10－4，這說明FGAMW具有較好的收斂性能，是可靠和可行的。

（2）FGAMW的多小波變異操作，使算法的微調(diào)能力得以提高，局部搜索能力增強，彌補了FPRGA的局部搜索能力差的不足，結(jié)果顯示，F(xiàn)GAMW有著較高的自適應(yīng)性和搜索性能，因而可以認為，F(xiàn)GAMW是一種更優(yōu)的優(yōu)化算法。

圖1 FPRGA運行結(jié)果

圖2 FGAMW運行結(jié)果比較

表1 FPRGA和FGAMW測試結(jié)果比較

5 結(jié)束語

遺傳算法的編碼問題歷來是遺傳算法研究的難點和熱點問題。浮點數(shù)編碼具有精度高、便于高維大空間搜索的優(yōu)點，在函數(shù)優(yōu)化和約束優(yōu)化領(lǐng)域明顯有效于其他編碼。而遺傳環(huán)境中產(chǎn)生的噪音影響著浮點數(shù)編碼遺傳算法的性能，在遺傳操作中消噪是減少噪音影響的唯一有效的途徑。將小波消噪的優(yōu)勢用于浮點數(shù)編碼遺傳算法的消噪變異，為解決該問題提供了新的思路[8-9]。但單一小波對浮點數(shù)編碼消噪變異泛化能力低，且對浮點數(shù)編碼遺傳算法性能改進有一定的局限性。本文從理論上證明利用酉變換可為正交多尺度函數(shù)構(gòu)造正交多小波，并將據(jù)此構(gòu)造的正交多小波用于浮點數(shù)編碼遺傳算法的消噪變異，然后進行了實驗。本文的理論研究和實驗結(jié)果表明，本文提出的FGAMW方法理論上是可靠的，技術(shù)上是可行的，對于拓展浮點數(shù)編碼遺傳算法的應(yīng)用空間具有積極的意義。

[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，F(xiàn)ujimoto 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

浮點數(shù)編碼具有精度高、便于高維大空間搜索的優(yōu)點，在函數(shù)優(yōu)化和約束優(yōu)化領(lǐng)域明顯有效于其他編碼。浮點數(shù)編碼遺傳算法在操作環(huán)境中產(chǎn)生的噪音和對算法性能的影響尚不被人們所認識。將小波用于浮點數(shù)編碼遺傳算法的消噪變異是解決該問題的有效途徑。單一小波對浮點數(shù)編碼消噪變異泛化能力低，且對浮點數(shù)編碼遺傳算法性能改進有一定的局限性。研究證明了用酉變換可構(gòu)造正交多小波，將正交多小波用于浮點數(shù)編碼遺傳算法的消噪變異，提出了FGAMW方法，并進行了實驗。理論研究和實驗結(jié)果表明，提出的FGAMW方法理論上是可靠的，技術(shù)上是可行的，對于拓展浮點數(shù)編碼遺傳算法的應(yīng)用空間具有積極的意義。

酉變換；多小波；浮點數(shù)編碼；遺傳算法；消噪變異

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.

河南省基礎(chǔ)與前沿技術(shù)研究計劃（No.102300410109）；河南省教育廳自然科學(xué)研究計劃項目（No.2011A520002）。

崔明義（1958—），男，博士，教授，主要研究方向為計算智能、云計算、計算實驗。

2012-02-06

2012-03-22

1002-8331（2013）15-0119-04