【摘要】： 采用優(yōu)化來描述各種問題盡管不是最佳的表述方式,但是它是一個相對簡單和通用的手段——至少從原則來講各種問題可以被表示為優(yōu)化問題。本文采用優(yōu)化來表征一個帶求解的問題,進(jìn)而以它為對象,對問題求解系統(tǒng)進(jìn)行設(shè)計(jì)和分析。 針對采用搜索機(jī)制進(jìn)行對問題的求解的直接優(yōu)化方法,前人曾做過大量的理論研究和實(shí)際應(yīng)用。這些研究最終產(chǎn)生了演化計(jì)算這一領(lǐng)域。它通過模仿自然界或社會系統(tǒng)中的各式各樣的自適應(yīng)和學(xué)習(xí)機(jī)制來引導(dǎo)搜索過程的進(jìn)行,從而實(shí)現(xiàn)優(yōu)化這一目標(biāo)。 早期的演化計(jì)算理論不論是模式理論、馬爾科夫模型和動態(tài)系統(tǒng)模型還是統(tǒng)計(jì)力學(xué)模型,它們都著力于模仿給定的計(jì)算模型的動態(tài)行為。但是這些理論在最終應(yīng)用時,都面臨著無法承受的計(jì)算負(fù)擔(dān)。我們把其原因歸結(jié)為這些理論過于一般化脫離了了待求問題的特點(diǎn)和實(shí)際求解要求。由于演化算法的核心機(jī)制是隨機(jī)和啟發(fā)式方法,因此單純的模仿算法運(yùn)行很難拿到針對特定問題求解時的準(zhǔn)確或者說必然的結(jié)論。 另一方面,在當(dāng)前演化計(jì)算領(lǐng)域的研究中,人們都集中于直接模仿在然界和社會中存在的各類演化和學(xué)習(xí)機(jī)制,依賴于所模仿的機(jī)制的上下文,將各種仿真演化的模型設(shè)計(jì)成為特定名稱的演化算法。隨著這些求解模型的不斷提出,名詞術(shù)語上的多樣性導(dǎo)致了研究和工程應(yīng)用的障礙。很明顯,現(xiàn)象的多樣性不一定就說明內(nèi)在自適應(yīng)機(jī)制的多樣性,相反一些新命名的仿真演化模型在本質(zhì)上有相通和相似的機(jī)制。 以上談及的這兩個趨勢突出說明了建立一個通用的演化系統(tǒng)環(huán)境的必要性。這個通用的演化系統(tǒng)要能夠應(yīng)用各種演化機(jī)制來設(shè)計(jì)求解技術(shù),進(jìn)而能綜合這些求解技術(shù)到某個整合的演化系統(tǒng)環(huán)境中定制特定系統(tǒng)來對特定的問題求解。其核心思想在于忽略單純的模仿某種演化機(jī)制,而是根據(jù)待求問題的特點(diǎn)綜合利用各類自適應(yīng)機(jī)制和有效的搜索技術(shù)來設(shè)計(jì)問題求解的系統(tǒng)。 在研究提出綜合系統(tǒng)之前,我們首先總結(jié)并討論了各類演化搜索算法的核心策略包括隨機(jī)策略和啟發(fā)式策略,以及根本指導(dǎo)原則包括最優(yōu)性原理和評估等價(jià)性原理;進(jìn)而總結(jié)并抽取出各類演化仿真系統(tǒng)中的本質(zhì)運(yùn)行機(jī)制。針對隨機(jī)策略我們導(dǎo)論了其特點(diǎn)和特性,并且給出了全局搜索和局部搜索的實(shí)現(xiàn)機(jī)制;針對啟發(fā)式策略我們闡述了其內(nèi)涵和歸納了其種類和各類實(shí)現(xiàn)方式。我們給出了最優(yōu)性原理中的基本收斂模式。我們依據(jù)文獻(xiàn)[89,91]的討論框架給出了評估等價(jià)性原理,通過此原理重新闡述了各類NFL定理的結(jié)論。這些理論結(jié)論為系統(tǒng)綜合的原理和方法奠定了基本的依據(jù)。 對前人工作的總結(jié),特別是在各類演化算法中總結(jié)出根本原則和計(jì)算模型是接下來提出演化計(jì)算系統(tǒng)和提出相關(guān)理論和方法的基礎(chǔ)。在理論研究和工程應(yīng)用過程中人們提出了大量的演化計(jì)算模型,因此我們不是采用枚舉當(dāng)前演化計(jì)算領(lǐng)域各類模型,而是總結(jié)并抽取其三類本質(zhì)的種群演化搜索模式。它們分別是基于遺傳信息的演化、個體行為演化和社會行為演化。前者本質(zhì)是編碼空間搜索模式,另外兩個分別是個體局部搜索學(xué)習(xí)和種群分布函數(shù)演化。在傳統(tǒng)的演化計(jì)算領(lǐng)域里,這三類演化和學(xué)習(xí)機(jī)制被用于獨(dú)立的創(chuàng)立各式計(jì)算模型,但是在我們將提出的綜合演化環(huán)境中,他們將被利用于設(shè)計(jì)演化搜索算子,并集成在綜合系統(tǒng)中進(jìn)行合作協(xié)調(diào)搜索。 接下來,我們提出了‘演化計(jì)算系統(tǒng)'的概念。作為系統(tǒng)綜合環(huán)境的演化計(jì)算系統(tǒng)將被定制為各種實(shí)現(xiàn)用于具體問題的求解。變化算子集、控制算子集和能夠獨(dú)立維護(hù)搜索信息的演化個體是演化計(jì)算系統(tǒng)的根本組元。該系統(tǒng)之所以稱為‘演化'是由于它使用演化和學(xué)習(xí)機(jī)制作為其搜索算子構(gòu)建的核心機(jī)制;而要說明的是盡管稱其為‘計(jì)算系統(tǒng)',但是它不同于傳統(tǒng)意義下的算法,它使能夠與外部計(jì)算系統(tǒng)甚至專家直接交換信息,實(shí)現(xiàn)交互式計(jì)算。 所謂的‘綜合'是指系統(tǒng)設(shè)計(jì)依賴于求解問題的特點(diǎn)和求解要求,同時拋開各類描述演化機(jī)制的名詞術(shù)語界限強(qiáng)調(diào)綜合應(yīng)用和協(xié)調(diào)各類求解技術(shù),定制針對問題特點(diǎn)的特定求解系統(tǒng)。為了實(shí)現(xiàn)這一目標(biāo),需要建立兩個根本橋梁:其一,待求問題的特點(diǎn)和演化搜索算子的設(shè)計(jì)的關(guān)系;其二,求解要求和組織搜索算子和演化個體的控制算子之間的關(guān)系。 緊緊圍繞著這兩個紐帶,我們提出了演化計(jì)算系統(tǒng)綜合設(shè)計(jì)的理論。首要的工作是算子設(shè)計(jì)的理論和模型。對于變化算子,我們詳細(xì)討論了其功能性和基本構(gòu)建機(jī)制。依賴使用演化個體的個數(shù),變化算子被分為個體學(xué)習(xí)型和全局學(xué)習(xí)型;依賴其搜索的功能性,它可被分為挖掘型和探索型。構(gòu)建演化搜索算子的核心機(jī)制有隨機(jī)搜索,啟發(fā)式搜索和問題數(shù)學(xué)結(jié)構(gòu)相關(guān)的傳統(tǒng)搜索機(jī)制�？刂扑阕影俗兓阕舆x擇控制,個體選擇控制,種群維護(hù)和交互接口控制幾大類。我們分別給出了設(shè)計(jì)機(jī)制和性能。需要特殊說明的是,演化個體獨(dú)立維護(hù)變化信息的機(jī)制是多個演化搜索算子共同協(xié)作的前提。 綜合設(shè)計(jì)理論的核心工作是系統(tǒng)綜合的理論和模型。系統(tǒng)綜合的基本實(shí)現(xiàn)手段是通過組織和協(xié)調(diào)參與演化搜索的各個變化算子和各類控制組元。在這一部分里,我們首先給出了有關(guān)綜合目標(biāo)和求解條件。接下來圍繞著建立這兩個基本橋梁,我們分別探討了最優(yōu)性原則和綜合設(shè)計(jì)模式,以及可靠性原則和實(shí)現(xiàn)綜合系統(tǒng)。 針對最優(yōu)性原則,我們給出了兩個收斂定理,并且依據(jù)這兩個收斂定理提供的條件提出了兩套綜合模式,即綜合模式Ⅰ和Ⅱ。綜合模式Ⅰ本質(zhì)應(yīng)用窮舉的策略以達(dá)到求取最優(yōu)解,它的運(yùn)行的低效性使得其常應(yīng)用于修正一個不收斂的演化計(jì)算系統(tǒng)為收斂的系統(tǒng)。比較來講,綜合模式Ⅱ則給出了一個有效的綜合方案,通過協(xié)調(diào)配和使用挖掘型演化搜索算子和探索型演化搜索算子,系統(tǒng)可以在保證最優(yōu)性的前提下實(shí)現(xiàn)高效的搜索求解。 求解可靠性原則更關(guān)心在給定的求解時間內(nèi)求取到滿意解。求解過程雖然是質(zhì)量與時間的一個平衡過程,但是我們可以抽取其兩個極值的情形作為綜合的標(biāo)準(zhǔn),即求解速度可靠性和求解質(zhì)量的可靠性。針對系統(tǒng)綜合,我們提供了四類總體實(shí)現(xiàn)方案,同時針對每種方案我們給出了相應(yīng)的設(shè)計(jì)指導(dǎo)原則和一般性能的討論。 為了舉例說明我們給出的演化計(jì)算系統(tǒng)和綜合理論的各方面設(shè)計(jì)原理和步驟,我們給出了三個挑戰(zhàn)性的工程優(yōu)化問題。它們分別是立體旋轉(zhuǎn)貨架的揀選作業(yè)調(diào)度優(yōu)化問題,本構(gòu)方程系統(tǒng)的參數(shù)標(biāo)定問題,以及目標(biāo)形狀設(shè)計(jì)優(yōu)化問題。其中第一個問題屬于控制優(yōu)化問題類,后兩個問題屬于設(shè)計(jì)優(yōu)化問題類。 針對問題一,我們突出說明了如何依賴具體問題的信息設(shè)計(jì)高效的挖掘型演化搜索算子,以及如何使用探索型搜索算子協(xié)調(diào)搜索行為�；诰C合模式Ⅱ,最優(yōu)性和可靠性標(biāo)準(zhǔn)在系統(tǒng)綜合設(shè)計(jì)中得到實(shí)現(xiàn);在比較實(shí)驗(yàn)中得到了經(jīng)驗(yàn)驗(yàn)證。 針對問題二,我們強(qiáng)調(diào)了多個演化搜索算子共同協(xié)調(diào)進(jìn)行演化搜索的工作模式。系統(tǒng)綜合模式Ⅱ作為基本執(zhí)行框架得到了實(shí)現(xiàn)。同時,針對挖掘型算子的特點(diǎn),我們配合設(shè)計(jì)了一種探索性搜索算子。實(shí)驗(yàn)環(huán)節(jié)以一套29個參數(shù)的系統(tǒng)進(jìn)行標(biāo)定,我們依據(jù)問題定制的演化計(jì)算系統(tǒng)給出了求解該問題目前最好的結(jié)論。 針對問題三,我們補(bǔ)充說明了除主要系統(tǒng)綜合理論之外的附屬型組元的設(shè)計(jì)和有關(guān)考慮。其中突出說明了利用交互式接口,讓專家擔(dān)當(dāng)智能變化算子,直接參與演化搜索。同時有關(guān)解空間表達(dá)問題、評估函數(shù)的設(shè)計(jì)問題、和策略參數(shù)的初始化等問題也給出了例證。 最后,我們總結(jié)了本文實(shí)現(xiàn)的主要工作和貢獻(xiàn),并給出下一步工作的兩個關(guān)鍵研究內(nèi)容。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2008
【分類號】：TP302.1

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前1條

1 常靖宇;基于演化計(jì)算的多峰函數(shù)研究[D];武漢理工大學(xué);2010年

，

本文編號：2708423