崔明義

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

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

崔明義

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

1 引言

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

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

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

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

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

2.1 正交共軛濾波器

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

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

定義的函數(shù)為：

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

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

定義1如果U滿足：

引理1如果

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

引理2如果是一個(gè)正交共軛過(guò)濾器，也是正交共軛過(guò)濾器。

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

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

該定理的證明見(jiàn)文獻(xiàn)[13]。

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

定理2與低通濾波器{ }

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

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

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

步驟1設(shè)

步驟2對(duì)于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，使矩陣：為一個(gè)正交矩陣。

步驟4

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

4 應(yīng)用實(shí)例

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

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

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

圖1 FPRGA運(yùn)行結(jié)果

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

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

5 結(jié)束語(yǔ)

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

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

酉變換；多小波；浮點(diǎn)數(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ù)研究計(jì)劃（No.102300410109）；河南省教育廳自然科學(xué)研究計(jì)劃項(xiàng)目（No.2011A520002）。

崔明義（1958—），男，博士，教授，主要研究方向?yàn)橛?jì)算智能、云計(jì)算、計(jì)算實(shí)驗(yàn)。

2012-02-06

2012-03-22

1002-8331（2013）15-0119-04