第1章　緒論

1.1　背景及意義

1.1.1　背景

在工業(yè)、農(nóng)業(yè)、國(guó)防、工程、交通、金融、化工、能源和通信等許多領(lǐng)域都存在著大量的“尋優(yōu)”需求。“尋優(yōu)”可簡(jiǎn)要地概括為^[1]：在滿足既定約束條件下，尋找一組比較合適的參數(shù)值，使待研究系統(tǒng)的某些性能指標(biāo)達(dá)到最大或最小。優(yōu)化在資源利用、結(jié)構(gòu)設(shè)計(jì)、調(diào)度管理和后勤供應(yīng)等許多領(lǐng)域已產(chǎn)生了巨大的經(jīng)濟(jì)效益和社會(huì)效益，同時(shí)在結(jié)構(gòu)力學(xué)、生命科學(xué)、材料科學(xué)、環(huán)境科學(xué)、控制論等其他領(lǐng)域也有著非常廣泛的應(yīng)用。優(yōu)化方法是一種以數(shù)學(xué)為基礎(chǔ)，用于求解各種最優(yōu)化問(wèn)題的應(yīng)用技術(shù)，優(yōu)化方法理論和技術(shù)歷來(lái)受到人們的廣泛重視^[1]。最優(yōu)化問(wèn)題根據(jù)優(yōu)化變量的取值類型可分為連續(xù)優(yōu)化問(wèn)題和離散優(yōu)化問(wèn)題兩大類。隨著科學(xué)技術(shù)的日益發(fā)展，離散優(yōu)化問(wèn)題與日俱增，越來(lái)越受到管理科學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)及應(yīng)用數(shù)學(xué)等諸多學(xué)科領(lǐng)域研究人員的高度重視。

在管理科學(xué)、計(jì)算機(jī)科學(xué)和工程學(xué)等學(xué)科及諸多應(yīng)用領(lǐng)域中，不斷涌現(xiàn)出許多大型復(fù)雜優(yōu)化問(wèn)題。面對(duì)這些問(wèn)題，傳統(tǒng)優(yōu)化方法如牛頓法、共軛梯度法、模式搜索法和單純形法等需要遍歷整個(gè)搜索空間，從而產(chǎn)生搜索的組合爆炸，即無(wú)法在多項(xiàng)式時(shí)間內(nèi)完成搜索。大型復(fù)雜優(yōu)化問(wèn)題通常都屬于NP-難問(wèn)題。鑒于實(shí)際工程問(wèn)題的復(fù)雜性、約束性、非線性和建模困難等特點(diǎn)，探索高效的優(yōu)化算法已成為相關(guān)學(xué)科的主要研究方向之一。

自然界中許多自適應(yīng)優(yōu)化現(xiàn)象不斷地啟示著人類^[2]：生物體和自然生態(tài)系統(tǒng)通過(guò)自身演化就能比較滿意地解決許多復(fù)雜問(wèn)題。計(jì)算機(jī)科學(xué)家們不斷地從生物系統(tǒng)研究中獲得靈感，并通過(guò)模仿自然世界的內(nèi)在機(jī)制去獲取解決復(fù)雜優(yōu)化問(wèn)題的新方法。20世紀(jì)80年代以來(lái)，一些智能優(yōu)化方法如遺傳算法（源自達(dá)爾文的自然界進(jìn)化理論）、蟻群算法（模擬螞蟻的集體覓食行為）和神經(jīng)網(wǎng)絡(luò)（模擬大腦結(jié)構(gòu)和思維過(guò)程）等，通過(guò)模擬某些自然現(xiàn)象或過(guò)程而產(chǎn)生、發(fā)展并不斷成熟，為解決復(fù)雜工程問(wèn)題提供了新思路和新手段。智能優(yōu)化方法的出現(xiàn)極大地豐富了最優(yōu)化技術(shù)，也為那些用傳統(tǒng)優(yōu)化技術(shù)難以處理的組合優(yōu)化問(wèn)題提供了切實(shí)可行的解決方案。

智能優(yōu)化方法模擬自然界的生物系統(tǒng)，依賴生物體的自身本能，通過(guò)無(wú)意識(shí)的尋優(yōu)行為來(lái)優(yōu)化其生存狀態(tài)。智能優(yōu)化方法根據(jù)所使用智能體的數(shù)量可分為基于個(gè)體的智能優(yōu)化方法和基于種群的智能優(yōu)化方法，其中模擬退火算法等是基于個(gè)體的智能優(yōu)化方法，而遺傳算法、蟻群算法和粒子群優(yōu)化算法等都是基于種群的智能優(yōu)化方法。基于種群的智能優(yōu)化方法的主要特點(diǎn)可概括為^[2]：

• 是一類不確定的優(yōu)化算法。不確定性體現(xiàn)了自然界生物的生理機(jī)制，并且在求解某些問(wèn)題時(shí)優(yōu)于確定性算法。
• 是一類概率型的全局搜索算法。隨著搜索過(guò)程的不斷推進(jìn)，找到優(yōu)質(zhì)解的概率大于得到劣質(zhì)解的概率，能以更大概率求得全局最優(yōu)解。
• 在優(yōu)化過(guò)程中不依賴于優(yōu)化問(wèn)題本身的某些數(shù)學(xué)特性。如目標(biāo)函數(shù)和約束條件的精確數(shù)學(xué)描述、目標(biāo)函數(shù)的連續(xù)性及可導(dǎo)性等。
• 是一類基于多個(gè)智能體的算法。各個(gè)智能體之間通過(guò)相互協(xié)作來(lái)更好適應(yīng)環(huán)境，以獲取所需性能。
• 具有潛在的并行性。搜索過(guò)程同時(shí)從多點(diǎn)出發(fā)，分布式并行模式極大提高了整個(gè)算法的運(yùn)行效率、魯棒性和反應(yīng)能力。
• 具有學(xué)習(xí)能力。在復(fù)雜的、不確定的、時(shí)變的環(huán)境中，能通過(guò)自我學(xué)習(xí)不斷提高個(gè)體的適應(yīng)性。

智能優(yōu)化方法的現(xiàn)有研究主要集中在三個(gè)方面^[1]：對(duì)現(xiàn)有智能優(yōu)化方法進(jìn)行改進(jìn)并廣泛應(yīng)用，對(duì)其理論進(jìn)行深入研究；開(kāi)發(fā)新的智能優(yōu)化工具，拓寬其應(yīng)用領(lǐng)域，并對(duì)其尋求理論基礎(chǔ)；各種現(xiàn)有智能優(yōu)化方法的混合。算法性能（精度和速度）的提高是永無(wú)止境的，提高現(xiàn)有智能優(yōu)化方法處理各種工程問(wèn)題的性能，并對(duì)其進(jìn)行理論研究已成為當(dāng)前智能優(yōu)化領(lǐng)域研究的首要任務(wù)和熱點(diǎn)問(wèn)題。

1.1.2　動(dòng)機(jī)

根據(jù)搜索方法的發(fā)展歷程（圖1.1），可將現(xiàn)有的搜索方法分為以下三類：古典搜索方法、啟發(fā)式搜索方法和智能優(yōu)化方法。

• 古典搜索方法。如步長(zhǎng)加速法、旋轉(zhuǎn)方向法、單純型調(diào)優(yōu)法、方向加速法、枚舉法和隨機(jī)搜索方法等。古典搜索方法僅通過(guò)比較目標(biāo)函數(shù)值的大小來(lái)移動(dòng)迭代點(diǎn)，它的搜索策略像是“跟著感覺(jué)走”。
• 啟發(fā)式搜索方法。如共軛梯度法、牛頓型方法和變尺度法等。啟發(fā)式搜索方法有一套嚴(yán)密的理論體系，通過(guò)比較目標(biāo)函數(shù)的梯度值來(lái)移動(dòng)迭代點(diǎn)，可看作是“梯度信息啟發(fā)下的簡(jiǎn)單智能搜索”。啟發(fā)式搜索方法將優(yōu)化問(wèn)題的梯度信息引入優(yōu)化過(guò)程中，采用目標(biāo)函數(shù)的梯度值來(lái)引導(dǎo)優(yōu)化方法的尋優(yōu)過(guò)程。相對(duì)于古典搜索方法，啟發(fā)式搜索方法能更快地搜索到優(yōu)化問(wèn)題的最優(yōu)解。

• 智能優(yōu)化方法。如模擬退火算法、遺傳算法、禁忌搜索、進(jìn)化規(guī)劃、進(jìn)化策略和蟻群算法等。智能優(yōu)化方法在優(yōu)化流程上均是一種“鄰域搜索”結(jié)構(gòu)。智能優(yōu)化方法在一定程度上把優(yōu)化問(wèn)題的領(lǐng)域知識(shí)隱含地加入到算法中。如在遺傳算法中，通過(guò)選擇、交叉和變異操作，將優(yōu)化問(wèn)題的較優(yōu)個(gè)體的一些部件特征（component characteristic）逐步地保留下來(lái)；在蟻群算法中，通過(guò)信息素將優(yōu)化問(wèn)題較優(yōu)個(gè)體的一些部件特征逐步地保留下來(lái)。與啟發(fā)式搜索方法相比，智能優(yōu)化方法能較好地解決大規(guī)模復(fù)雜系統(tǒng)中出現(xiàn)的組合爆炸問(wèn)題，不僅具有通用、穩(wěn)健、簡(jiǎn)單、便于并行處理等優(yōu)點(diǎn)，而且有望成為數(shù)值計(jì)算與語(yǔ)義表達(dá)、形象思維等高級(jí)智能行為之間相互聯(lián)系的橋梁。智能優(yōu)化方法的研究在一些采用傳統(tǒng)方法難以解決或無(wú)法解決的應(yīng)用領(lǐng)域中取得了重大突破。

在現(xiàn)有智能優(yōu)化方法中，還沒(méi)有大量直接地挖掘、存儲(chǔ)和應(yīng)用待求解問(wèn)題的相關(guān)領(lǐng)域知識(shí)，還不能最有效地得到最優(yōu)解。在現(xiàn)實(shí)生活中，實(shí)際系統(tǒng)的規(guī)模越來(lái)越大，約束條件越來(lái)越多，系統(tǒng)結(jié)構(gòu)越來(lái)越復(fù)雜，多準(zhǔn)則、非線性、不可微、不確定已成為這些復(fù)雜系統(tǒng)的基本特征。探尋適合大規(guī)模計(jì)算且具有智能特征的問(wèn)題求解方法已成為相關(guān)學(xué)科的研究熱點(diǎn)和重要研究方向。

本書(shū)認(rèn)為在求解復(fù)雜優(yōu)化問(wèn)題時(shí)，可從優(yōu)化過(guò)程中直接挖掘一些待求解問(wèn)題的相關(guān)知識(shí)，然后應(yīng)用知識(shí)來(lái)指導(dǎo)后續(xù)優(yōu)化過(guò)程。本文更多地關(guān)注一些顯性知識(shí)，即能明確表達(dá)的知識(shí)。顯性知識(shí)可采用計(jì)算機(jī)語(yǔ)言來(lái)表示和存儲(chǔ)，其他模型可通過(guò)給定方式對(duì)這些知識(shí)進(jìn)行更新和應(yīng)用。鑒于此，本書(shū)提出一類學(xué)習(xí)型智能優(yōu)化方法：采用知識(shí)模型和智能優(yōu)化模型相結(jié)合的集成建模思路，以智能優(yōu)化模型為基礎(chǔ)，同時(shí)突出知識(shí)模型的作用，將智能優(yōu)化模型和知識(shí)模型進(jìn)行優(yōu)化組合、優(yōu)勢(shì)互補(bǔ)，以提高學(xué)習(xí)型智能優(yōu)化方法的效率。

學(xué)習(xí)型智能優(yōu)化方法研究的難點(diǎn)主要表現(xiàn)在以下方面：

• 學(xué)習(xí)型智能優(yōu)化方法的基本框架。構(gòu)建一種比較通用的優(yōu)化框架，將智能優(yōu)化方法和知識(shí)模型進(jìn)行優(yōu)化組合、優(yōu)勢(shì)互補(bǔ)，以提高學(xué)習(xí)型智能優(yōu)化方法的效率。
• 知識(shí)的定義。構(gòu)建用于實(shí)現(xiàn)學(xué)習(xí)型智能優(yōu)化方法的若干典型知識(shí)，這些典型知識(shí)可輔助學(xué)習(xí)型智能優(yōu)化方法高效地求解復(fù)雜優(yōu)化問(wèn)題。
• 設(shè)計(jì)并實(shí)現(xiàn)若干種比較典型的學(xué)習(xí)型智能優(yōu)化方法。針對(duì)一些連續(xù)優(yōu)化問(wèn)題、組合優(yōu)化問(wèn)題或?qū)嶋H工程問(wèn)題，設(shè)計(jì)并實(shí)現(xiàn)若干種比較典型的學(xué)習(xí)型智能優(yōu)化方法，這些方法稍加修改就可推廣到其他復(fù)雜優(yōu)化問(wèn)題的求解中。