遺傳算法在建立預(yù)測(cè)預(yù)報(bào)模型中的應(yīng)用研究

[摘要] 預(yù)測(cè)預(yù)報(bào)是人們對(duì)客觀事物發(fā)展變化的一種認(rèn)識(shí)與估計(jì)。對(duì)某個(gè)對(duì)象系統(tǒng)選擇哪一種方法來(lái)建立預(yù)測(cè)預(yù)報(bào)模型，關(guān)鍵在于用此方法建立的預(yù)測(cè)模型的計(jì)算值與實(shí)際值的擬合程度。近幾年發(fā)展起來(lái)的遺傳算法(GA， Genetic Algorithm)是借鑒生物遺傳機(jī)制的一種隨機(jī)化搜索算法，其主要特點(diǎn)是群體搜索和群體中的個(gè)體之間的信息交換。遺傳算法尤其適用于處理傳統(tǒng)方法難以解決的復(fù)雜的和非線(xiàn)性的問(wèn)題，己在許多領(lǐng)域有廣泛的應(yīng)用，它將成為智能計(jì)算的主要技術(shù)之一。文章以某企業(yè)各年度資金實(shí)際需要量動(dòng)態(tài)數(shù)列為例，探討了基于遺傳算法的時(shí)序預(yù)測(cè)模型的建模方法及預(yù)測(cè)精度的有效性。

[關(guān)鍵詞] 遺傳算法 預(yù)測(cè) 建模 擬合 精度

預(yù)測(cè)預(yù)報(bào)是人們對(duì)客觀事物發(fā)展變化的一種認(rèn)識(shí)與估計(jì)。預(yù)測(cè)預(yù)報(bào)對(duì)人類(lèi)社會(huì)的重要性早己為人們所認(rèn)識(shí)，“凡事預(yù)則立，不預(yù)則廢”，說(shuō)明了人們對(duì)預(yù)測(cè)的重要性的認(rèn)識(shí)。預(yù)測(cè)可采用的方法很多，例如，傳統(tǒng)的回歸分析方法、基于灰色理論的灰色模型(Grey Model)，以及近幾年發(fā)展起來(lái)的遺傳算法和人工神經(jīng)網(wǎng)絡(luò)模型等。對(duì)某個(gè)對(duì)象系統(tǒng)選擇哪一種方法來(lái)建立預(yù)測(cè)預(yù)報(bào)模型，關(guān)鍵在于用此方法建立的預(yù)測(cè)模型的計(jì)算值與實(shí)際值的擬合程度。

遺傳算法(GA，Genetic Algorithm)是借鑒生物遺傳機(jī)制的一種隨機(jī)化搜索算法，其主要特點(diǎn)是群體搜索和群體中的個(gè)體之間的信息交換遺傳算法尤其適用于處理傳統(tǒng)方法難以解決的復(fù)雜的和非線(xiàn)性的問(wèn)題，己在許多領(lǐng)域有廣泛的應(yīng)用，它將成為智能計(jì)算的主要技術(shù)之一。

一、遺傳算法原理綜述

1.基本術(shù)語(yǔ)

遺傳算法是遺傳學(xué)和計(jì)算機(jī)科學(xué)相互結(jié)合滲透而成的新的計(jì)算方法，它使用了遺傳學(xué)的一些概念和基本術(shù)語(yǔ)來(lái)描述它的計(jì)算方法。

生物遺傳物質(zhì)的主要載體是染色體，最主要的遺傳物質(zhì)是DNA。染色體由基因組成，染色體中基因的位置稱(chēng)為基因座，基因所取的值稱(chēng)為等位基因。基因和基因座決定了染色體的特征，也決定了生物個(gè)體的性狀。

染色體有兩種表示模式，即基因型(genetype)表示模式和表現(xiàn)型(phenotype)表示模式。表現(xiàn)型是指生物個(gè)體所表現(xiàn)出來(lái)的性狀。基因型是指與生物個(gè)體表現(xiàn)出來(lái)的性狀密切相關(guān)的基因組成。同一種基因型的生物個(gè)體在不同的環(huán)境條件下表現(xiàn)出來(lái)的性狀會(huì)有差異，因此，表現(xiàn)型是基因型與環(huán)境條件相互作用的結(jié)果。

2.編譯碼操作

在遺傳算法中，與染色體相對(duì)應(yīng)的是數(shù)據(jù)或數(shù)組。在標(biāo)準(zhǔn)的遺傳算法中，染色體可用一維的串結(jié)構(gòu)數(shù)據(jù)來(lái)表示，串的各個(gè)位置對(duì)應(yīng)染色體的基因座，各位置上所取的值對(duì)應(yīng)等位基因。遺傳算法對(duì)染色體進(jìn)行處理，或者稱(chēng)為對(duì)基因型個(gè)體(individuals)進(jìn)行處理。一定數(shù)量的個(gè)體組成群體(population)，群體中的個(gè)體數(shù)稱(chēng)為群體大小(population size)或群體規(guī)模。各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度稱(chēng)為適應(yīng)度(fitness)。

執(zhí)行遺傳算法時(shí)有兩個(gè)必需的數(shù)據(jù)轉(zhuǎn)換操作，一個(gè)操作是把搜索空間中的參數(shù)或解數(shù)據(jù)轉(zhuǎn)換成遺傳空間的染色體或個(gè)體，或者說(shuō)是把染色體數(shù)據(jù)從表現(xiàn)型表示轉(zhuǎn)換成基因型表示，這個(gè)過(guò)程稱(chēng)為編碼操作；另一個(gè)操作稱(chēng)為譯碼操作，它是同編碼操作相反的數(shù)據(jù)轉(zhuǎn)換操作，譯碼操作把染色體數(shù)據(jù)從基因型表示轉(zhuǎn)換成表現(xiàn)型表示。

3.算法流程

遺傳算法的基本流程如下圖所示。遺傳算法以群體中的所有個(gè)體為對(duì)象，選擇(selection)、雜交(crossbreed)和變異(mutation)是遺傳算法的三個(gè)主要操作算子，它們構(gòu)成了所謂的遺傳操作(Genetic Operations)，使遺傳算法具有了其他傳統(tǒng)方法所沒(méi)有的特征。

4.基本要素

應(yīng)用遺傳算法求解問(wèn)題，需要根據(jù)求解的具體問(wèn)題進(jìn)行下述五個(gè)方面的工作，這是遺傳算法的核心內(nèi)容，也稱(chēng)為遺傳算法的五個(gè)基本要素:

(1)參數(shù)編碼的格式設(shè)定及參數(shù)編碼

(2)初始群體的設(shè)定

(3)適應(yīng)度函數(shù)的設(shè)計(jì)

(4)遺傳操作設(shè)計(jì)

(5)控制參數(shù)設(shè)計(jì)，主要是指群體規(guī)模和遺傳操作中所需使用的有關(guān)控制參數(shù)的設(shè)定和設(shè)計(jì)

二、應(yīng)用遺傳算法建立預(yù)測(cè)預(yù)報(bào)模型

下面是一個(gè)用來(lái)說(shuō)明遺傳算法在建立預(yù)測(cè)預(yù)報(bào)模型中的應(yīng)用實(shí)例。

例：己知某企業(yè)從1985年～2006年各年的資金實(shí)際需要量(萬(wàn)元)如下表所示，應(yīng)用遺傳算法建立該企業(yè)資金年需要量預(yù)測(cè)模型。

1.建模分析

由表給出的1985年～2006年的資金實(shí)際需要量，可作出如下圖所示的年資金實(shí)際需要量曲線(xiàn)。由此曲線(xiàn)可見(jiàn)，企業(yè)年資金實(shí)際需要量的總趨勢(shì)在增長(zhǎng)，但有準(zhǔn)周期性的振蕩，因此，年資金實(shí)際需要量預(yù)測(cè)模型應(yīng)考慮曲線(xiàn)總體增長(zhǎng)趨勢(shì)的描述和振蕩規(guī)律的描述兩部分組成。

(1)企業(yè)年資金需要量總體增長(zhǎng)趨勢(shì)的描述。

在一個(gè)企業(yè)的成長(zhǎng)發(fā)展時(shí)期中，企業(yè)年資金需要量的變化情況可分為發(fā)生、發(fā)展、成熟三個(gè)階段。在發(fā)生階段，隨著企業(yè)基礎(chǔ)設(shè)施和管理的到位，年資金需要量增長(zhǎng)速度較慢，并逐漸加大增長(zhǎng)趨勢(shì)；在發(fā)展階段，隨著企業(yè)品牌形象的逐步形成，年資金需要量增長(zhǎng)速度較快，并維持一段時(shí)間后進(jìn)入成熟期；在成熟階段，其增長(zhǎng)速度將逐漸變慢，增長(zhǎng)趨于飽和。企業(yè)年資金需要量的這種總體發(fā)展變化規(guī)律可采用Logistic生長(zhǎng)曲線(xiàn)描述。Logistic生長(zhǎng)曲線(xiàn)是下述非線(xiàn)性常微分方程：

的解：

式中各參數(shù)在本例中的含義是：Y是年資金需要量，t是時(shí)間(年)，a是年資金需要量增長(zhǎng)速度系數(shù)，b是企業(yè)年資金需要量的極限值，m和c是與a，b有關(guān)的參數(shù)。

Logistic生長(zhǎng)曲線(xiàn)如下圖所示，可用于反映一般處于成長(zhǎng)發(fā)展時(shí)期中的對(duì)象系統(tǒng)隨時(shí)間的生長(zhǎng)情況。由于Logistic曲線(xiàn)符合企業(yè)年資金需要量隨企業(yè)打拼發(fā)展的變化規(guī)律，所以采用Logistic曲線(xiàn)描述企業(yè)年資金需要量的總體增長(zhǎng)趨勢(shì)是比較合適的。

考慮到1985年以前的年資金需要量應(yīng)對(duì)Logistic生成曲線(xiàn)的起點(diǎn)定位及其預(yù)測(cè)值有“抬高”的影響，故對(duì)Logistic曲線(xiàn)進(jìn)行如下修改：

(2)企業(yè)年資金需要量振蕩規(guī)律的描述。

由企業(yè)年資金需要量曲線(xiàn)可見(jiàn)，從1985年～2006年，實(shí)際年資金需要量的變化與Logistic曲線(xiàn)有較大差異。實(shí)際年資金需要量曲線(xiàn)有較大幅度的振蕩，是一個(gè)多峰曲線(xiàn)。企業(yè)年資金需要量出現(xiàn)振蕩多峰的原因是復(fù)雜的，但是，我們這里并不需要去探討振蕩的原因及其各種原因是如何影響預(yù)測(cè)模型的，只需要在預(yù)測(cè)模型中給出振蕩規(guī)律的大致描述。

由圖所示的實(shí)際年資金需要量曲線(xiàn)的振蕩具有準(zhǔn)周期性衰減，周期性可以用正弦函數(shù)描述，幅值的衰減性可以用負(fù)指數(shù)函數(shù)描述。因此，考慮到年資金需要量曲線(xiàn)的振蕩特征后，需要對(duì)由Logistic曲線(xiàn)表示的年資金需要量總體增長(zhǎng)趨勢(shì)乘以一個(gè)振蕩修正因子，即有：

式中，p為相對(duì)振蕩幅值，h為振蕩半周期長(zhǎng)度(年)，u為振蕩的初始幅角，g為振蕩衰減系數(shù)。

上式中含有8個(gè)待定參數(shù)b，c，d.m，p，g，h和u。我們采用遺傳算法求解這8個(gè)參數(shù)，從而得出企業(yè)年資金需要量的預(yù)測(cè)模型y(t)。

2.采用遺傳算法求解模型的待定參數(shù)

(1)編碼

把待定的8個(gè)參數(shù)表示成一維數(shù)組x=(b，c，d，m，p，g，h，u)，數(shù)組各元為帶符號(hào)的十進(jìn)制數(shù)。

(2)初始群體的隨機(jī)生成

設(shè)群體規(guī)模為n，隨機(jī)生成初始群體的n個(gè)個(gè)體xi=（ai1，ai2，ai3，ai4，ai5，ai6，ai7，ai8），i=1，2， …，n。個(gè)體xi中基因座k上的基因值aik(1≤k≤8)就是數(shù)組xi的第k個(gè)元的值。

(3)適應(yīng)度函數(shù)

待定參數(shù)的確定應(yīng)使得預(yù)測(cè)模型的年資金需要量計(jì)算值y(t)與年資金需要量實(shí)際值y*(t)的擬合最好，即從1985年～2006年共22年的計(jì)算值y(t)與實(shí)際值y*(t)的誤差累計(jì)最小。故建立適應(yīng)度函數(shù)為:

(4)選擇操作

為減小計(jì)算的復(fù)雜程度，可直接選擇適應(yīng)度f(wàn)i最小的個(gè)體xi作為優(yōu)良個(gè)體，對(duì)其復(fù)制一次，并淘汰適應(yīng)度最大的一個(gè)個(gè)體。對(duì)規(guī)模較大的群體，優(yōu)良個(gè)體被選擇的次數(shù)可多于兩次，并相應(yīng)淘汰多個(gè)劣質(zhì)個(gè)體，以保持群體規(guī)模n不變。

(5)雜交操作

對(duì)配對(duì)池MP=(x1，…，xi，…，xj，…，xn)中的n個(gè)個(gè)體隨機(jī)配對(duì)進(jìn)行雜交繁殖。若隨機(jī)選擇xi=（ai1，ai2，ai3，ai4，ai5，ai6，ai7，ai8）與xj=（aj1，aj2，aj3，aj4，aj5，aj6，aj7，aj8）配對(duì)，則雜交操作為:

其中，雜交參數(shù)β可以是一個(gè)隨機(jī)數(shù)，β的取值范圍為0<β<1，a`ik是個(gè)體xi與xj雜交生成的后代個(gè)體x`k中第k個(gè)基因的值， a`jk是個(gè)體xj與xi雜交生成的后代個(gè)體x`j中第k個(gè)基因的值。

(6)變異操作

本例選取的變異操作的概率為1%，即每次對(duì)群體中的8n個(gè)基因隨機(jī)選擇8n×1%個(gè)基因進(jìn)行變異操作。若隨機(jī)選擇基因aik進(jìn)行變異操作，則變異后的基因?yàn)?

式中，變異參數(shù)η可以是一個(gè)隨機(jī)數(shù)，η的取值范圍為0<η<1。

(7)算法終止條件

遺傳算法是一種迭代算法，對(duì)生成的后代群體的n個(gè)個(gè)體繼續(xù)進(jìn)行選擇、雜交和變異操作，直至滿(mǎn)足算法終止條件。理想的算法終止條件是連續(xù)若干代(例如10代)不再產(chǎn)生適應(yīng)度更小的個(gè)體，即不再能繁殖出更優(yōu)良的個(gè)體。這個(gè)終止條件是比較嚴(yán)格的，需要迭代計(jì)算許多次。為了減少算法運(yùn)算的時(shí)空開(kāi)銷(xiāo)，比較一般的終止條件可為:若fi≤ε，則算法終止，相應(yīng)的個(gè)體xi即是問(wèn)題的解。xi中的8個(gè)基因值即分別為待定的8個(gè)參數(shù)值。ε為指定的擬合精度誤差。

三、結(jié)束語(yǔ)

由上例討論可見(jiàn)，為了建立任何一個(gè)對(duì)象系統(tǒng)的時(shí)序預(yù)測(cè)模型，只要能先用一個(gè)參數(shù)待定的非線(xiàn)性函數(shù)來(lái)大致描述該對(duì)象系統(tǒng)的變化規(guī)律，無(wú)論這個(gè)非線(xiàn)性函數(shù)有多復(fù)雜，都可以用一組實(shí)際值作為實(shí)例，采用遺傳算法來(lái)訓(xùn)練模型，求解出模型的待定參數(shù)，從而建立起這個(gè)模型。另外，適應(yīng)度函數(shù)和算法終止條件能保證建立的模型的計(jì)算值與實(shí)際值會(huì)有很好的擬合精度，所以基于遺傳算法的時(shí)序預(yù)測(cè)模型的建模方法與傳統(tǒng)建模方法比較，前者建立的預(yù)測(cè)模型會(huì)有較高的預(yù)測(cè)精度，尤其是近期預(yù)測(cè)。

參考文獻(xiàn):

[1]高巖位耀光付冬梅張蔚:免疫遺傳算法的研究及其在函數(shù)優(yōu)化中的應(yīng)用[J].微計(jì)算機(jī)信息，2007，(6):183～184

[2]吉根林:遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2004，21(2):69～73

[3]尹朝慶尹皓:人工智能與專(zhuān)家系統(tǒng)[M].北京:中國(guó)水利水電出版社，2002:286～294

[4]王煦法:遺傳算法及其應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng)，1995，16(2):59～64

[5]S. G. Ponnambalam，P. Aravindan ，G. Mogileeswar Naidu.A Multi-Objective Genetic Algorithm for Solving Assembly Line Balancing Problem[J].The Intenational Journal of Advanced Manufacture Technology，2000，16:341～352