第1章 緒論

1.1 最優(yōu)化問(wèn)題的研究意義

最優(yōu)化問(wèn)題與方法研究源于運(yùn)籌學(xué)（Operational Research），學(xué)者們稱(chēng)它為數(shù)學(xué)規(guī)劃（Mathematical Programming），是運(yùn)籌學(xué)的主要分支之一[1]。在處理實(shí)際問(wèn)題的時(shí)候，往往會(huì)遇到存在多個(gè)解的情況，如何根據(jù)問(wèn)題本身的特點(diǎn)選擇出一個(gè)最優(yōu)或者次最優(yōu)解，這是科學(xué)領(lǐng)域的最優(yōu)化問(wèn)題。本章將從單目標(biāo)最優(yōu)化問(wèn)題、多目標(biāo)優(yōu)化問(wèn)題、約束優(yōu)化問(wèn)題和離散優(yōu)化問(wèn)題4個(gè)方面進(jìn)行闡述。

單目標(biāo)最優(yōu)化問(wèn)題（Simple-Objective Optimization Problem，SOP）是“最優(yōu)化問(wèn)題”中較簡(jiǎn)單的一種情況，從一個(gè)問(wèn)題所有可能的備選方案中，選擇出一種最優(yōu)的解決方案。從數(shù)學(xué)上來(lái)講，最優(yōu)化問(wèn)題是研究一個(gè)給定的集合S上泛函J(u)的極小化或極大化問(wèn)題；廣義上來(lái)講，最優(yōu)化問(wèn)題包括數(shù)學(xué)規(guī)劃、圖和網(wǎng)絡(luò)、組合最優(yōu)化、庫(kù)存論、決策論、排隊(duì)論、最優(yōu)控制等；狹義上來(lái)講，最優(yōu)化問(wèn)題僅指數(shù)學(xué)規(guī)劃。最優(yōu)化問(wèn)題的解決方法廣泛應(yīng)用于生產(chǎn)管理、經(jīng)濟(jì)規(guī)劃、工程設(shè)計(jì)、系統(tǒng)控制科學(xué)研究等領(lǐng)域。

然而大多數(shù)工程設(shè)計(jì)和科學(xué)研究領(lǐng)域中普遍存在的優(yōu)化決策問(wèn)題是多屬性的，一般是對(duì)多個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化，從而找到滿(mǎn)足多個(gè)目標(biāo)的較好的設(shè)計(jì)方案，這就是所謂的多目標(biāo)優(yōu)化問(wèn)題（Multi-Objective Optimization Problem，MOP）。MOP中的各個(gè)優(yōu)化目標(biāo)之間往往是相互聯(lián)系但又彼此制約的，一個(gè)優(yōu)化目標(biāo)性能提升的同時(shí)往往會(huì)造成其他優(yōu)化目標(biāo)性能的降低甚至退化，即所求解的MOP中所有優(yōu)化目標(biāo)很難同時(shí)獲得最優(yōu)結(jié)果[2]。

現(xiàn)實(shí)生活中的優(yōu)化問(wèn)題大多是多目標(biāo)優(yōu)化問(wèn)題，例如分布式電源選址方案的優(yōu)化問(wèn)題。分布式電源接入電網(wǎng)的做法改變了傳統(tǒng)電網(wǎng)的運(yùn)行模式，降低了電力損耗，提高了電力系統(tǒng)的穩(wěn)定性和靈活性。如何選址建造分布式電源，同時(shí)保證電網(wǎng)損耗、電壓穩(wěn)定性及建造成本的最優(yōu)，就是一個(gè)MOP[3]。又如當(dāng)消費(fèi)者購(gòu)買(mǎi)汽車(chē)時(shí)，不同舒適度的汽車(chē)對(duì)應(yīng)不同的價(jià)格，只是專(zhuān)注價(jià)格的消費(fèi)者只需要挑選最便宜的汽車(chē)即可，同理只關(guān)注舒適度的消費(fèi)者只需要挑選最舒適的即可。但在實(shí)際生活中，消費(fèi)者總是想在滿(mǎn)足自己舒適度要求的前提下選擇最優(yōu)惠的汽車(chē)，或者在自己可以承受的價(jià)格范圍內(nèi)，挑選舒適度最高的汽車(chē)，這就構(gòu)成了一個(gè)雙目標(biāo)問(wèn)題：一個(gè)是最小化價(jià)格目標(biāo)問(wèn)題，另一個(gè)是最大化舒適度目標(biāo)問(wèn)題。再如，在工業(yè)設(shè)計(jì)問(wèn)題上，生產(chǎn)廠(chǎng)商會(huì)提出工業(yè)產(chǎn)品的造價(jià)最低、表現(xiàn)最優(yōu)、穩(wěn)定性最好等一系列目標(biāo)，這些目標(biāo)同時(shí)考慮優(yōu)化就構(gòu)成了多目標(biāo)優(yōu)化問(wèn)題[4]。因此，可以說(shuō)多目標(biāo)優(yōu)化問(wèn)題在現(xiàn)實(shí)生活中隨處可見(jiàn)，研究這類(lèi)問(wèn)題的求解方法具有非常重要的現(xiàn)實(shí)意義。MOP在工程應(yīng)用等現(xiàn)實(shí)生活中非常普遍，并且處于非常重要的地位。隨著科技的快速發(fā)展及全球經(jīng)濟(jì)競(jìng)爭(zhēng)的不斷加強(qiáng)，現(xiàn)實(shí)生活的問(wèn)題變得越來(lái)越復(fù)雜，往往需要同時(shí)考慮多個(gè)目標(biāo)的優(yōu)化，因此，多目標(biāo)優(yōu)化逐漸發(fā)展為最優(yōu)化問(wèn)題研究范疇中一個(gè)極其重要的熱點(diǎn)與方向。自20世紀(jì)60年代早期以來(lái)，MOP吸引了越來(lái)越多不同背景的研究人員的注意，盡管針對(duì)MOP提出了很多算法，這些算法也在一定程度上表現(xiàn)出令人滿(mǎn)意的求解效果，但在某些問(wèn)題的求解上仍存在諸如收斂速度慢、搜索能力差、早熟收斂等常見(jiàn)問(wèn)題，目前，沒(méi)有哪一種算法能夠解決所有的優(yōu)化問(wèn)題。針對(duì)具體問(wèn)題的特點(diǎn)，通過(guò)設(shè)計(jì)或改進(jìn)算法的運(yùn)行機(jī)制來(lái)解決不同類(lèi)型的問(wèn)題是非常有意義的。因此，針對(duì)MOP的研究是一個(gè)十分具有挑戰(zhàn)性和重要意義與價(jià)值的課題。

MOP與SOP的不同之處在于單目標(biāo)的優(yōu)化結(jié)果是一個(gè)最優(yōu)解，而對(duì)于MOP而言，不存在唯一的或者絕對(duì)的最優(yōu)解。解決MOP的一個(gè)較好的辦法就是對(duì)其中相互制約的各個(gè)目標(biāo)予以綜合考慮，即在多個(gè)目標(biāo)之間進(jìn)行協(xié)調(diào)并找出滿(mǎn)意的非劣最優(yōu)解，即Pareto最優(yōu)解。由于Pareto最優(yōu)解通常為一系列折衷解的集合，故將該集合稱(chēng)之為Pareto最優(yōu)解集（Pareto Optimal Set）[1]。

但是現(xiàn)實(shí)生活中的大多數(shù)優(yōu)化問(wèn)題需要找到一個(gè)解，該解不僅要滿(mǎn)足最優(yōu)性，而且要滿(mǎn)足一個(gè)或多個(gè)約束條件，這些問(wèn)題統(tǒng)稱(chēng)為約束優(yōu)化問(wèn)題（Constrained Optimization Problem，COP）。通常來(lái)說(shuō)，大多數(shù)約束優(yōu)化問(wèn)題是具有挑戰(zhàn)性的，且難以求解。如何有效地求解約束優(yōu)化問(wèn)題被認(rèn)為是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)和優(yōu)化理論中極具挑戰(zhàn)性的研究課題之一。本質(zhì)上，約束優(yōu)化問(wèn)題可以看成約束處理和最優(yōu)化問(wèn)題的結(jié)合。

目前，根據(jù)進(jìn)化計(jì)算中約束處理方法的研究進(jìn)展，約束處理方法主要分為3類(lèi)：罰函數(shù)方法、可行規(guī)則方法和多目標(biāo)方法[5]。因原理簡(jiǎn)單和易于實(shí)現(xiàn)，罰函數(shù)方法是目前應(yīng)用最廣泛的約束處理方法之一。罰函數(shù)方法是指在目標(biāo)函數(shù)中加入一個(gè)懲罰函數(shù)，將約束問(wèn)題轉(zhuǎn)換成一個(gè)無(wú)約束問(wèn)題，該方法的難點(diǎn)在于罰參數(shù)的選擇。可行規(guī)則方法建立在可行解要優(yōu)于不可行解的偏好基礎(chǔ)上，這里需滿(mǎn)足3條比較規(guī)則：可行解要優(yōu)于不可行解；當(dāng)兩個(gè)解都是可行時(shí)，選擇目標(biāo)函數(shù)值小的；當(dāng)兩個(gè)解都是不可行解時(shí)，選擇違反約束小的。最近幾年，多目標(biāo)概念的思想已經(jīng)被越來(lái)越多地用于進(jìn)化計(jì)算中的約束處理，這種思想是將約束轉(zhuǎn)換成一個(gè)或多個(gè)目標(biāo)。根據(jù)處理約束的不同原則，有兩類(lèi)多目標(biāo)方法：一類(lèi)是有兩個(gè)目標(biāo)的——源目標(biāo)函數(shù)和所有約束違反程函數(shù)；另一類(lèi)是將每個(gè)約束看成一個(gè)目標(biāo)。因此，對(duì)于有m個(gè)約束的多目標(biāo)問(wèn)題來(lái)說(shuō)，加上原有的目標(biāo)函數(shù)，總共有m+1個(gè)目標(biāo)函數(shù)[6]。

隨著社會(huì)的發(fā)展和經(jīng)濟(jì)的進(jìn)步，優(yōu)化問(wèn)題出現(xiàn)了規(guī)模大、復(fù)雜多峰、非線(xiàn)性、不可微等特點(diǎn)，傳統(tǒng)的優(yōu)化算法已經(jīng)無(wú)法快速、高效地解決此類(lèi)優(yōu)化問(wèn)題，因此在傳統(tǒng)的優(yōu)化算法的基礎(chǔ)之上，探索出更高效的現(xiàn)代化算法具有十分重要的意義。一般的優(yōu)化方法只能求得連續(xù)變量的最優(yōu)解，而傳統(tǒng)的求離散問(wèn)題的最優(yōu)解是先用連續(xù)變量?jī)?yōu)化設(shè)計(jì)方法求連續(xù)變量的最優(yōu)解，然后取整到離散值上，這就存在一些弊端，即得不到可行最優(yōu)解，或者所得的解不是離散的最優(yōu)解。然而，現(xiàn)實(shí)生活中很多問(wèn)題常常涉及離散的屬性值，這類(lèi)問(wèn)題被稱(chēng)為離散問(wèn)題。當(dāng)代的學(xué)者們針對(duì)這些離散問(wèn)題提出了許多離散優(yōu)化方法，如決策樹(shù)、關(guān)聯(lián)規(guī)則等，因此設(shè)計(jì)高性能、實(shí)用的離散優(yōu)化方法對(duì)于社會(huì)具有非常重要的現(xiàn)實(shí)意義。