多目標(biāo)優(yōu)化問題的求解算法

多目的優(yōu)化問題的求解算法

第一頁，共32頁。目錄一、多目的優(yōu)化問題概述二、基于蟻群算法的多目的優(yōu)化第二頁，共32頁。多目的優(yōu)化問題(Multi-objectiveOptimizationProblem,MOP)是由VilfredoPareto首次從數(shù)學(xué)的角度提出的。一、多目的優(yōu)化問題概述第三頁，共32頁。

單目的優(yōu)化問題，只有一個目的函數(shù)，人們只需要尋找滿足該目的函數(shù)的最優(yōu)解即可。多目的優(yōu)化問題，由于存在多個目的函數(shù)和約束條件，所以當(dāng)一個目的到達(dá)最優(yōu)就很有可能令其它目的最劣，各個目的彼此間互相牽制和影響的，難以實現(xiàn)所有目的的最優(yōu)化，所以不能根據(jù)一個目的是否到達(dá)來評價函數(shù)解的優(yōu)劣程度，因此通常用一個最優(yōu)解的集合來表示多目的優(yōu)化問題的解。這種解稱作Pareto最優(yōu)解。1.多目的優(yōu)化問題與單目的優(yōu)化問題的不同點第四頁，共32頁。

工程工程施工過程中，多目的已經(jīng)成為當(dāng)今施工管理的一大特點，不能看某一目的要求是否實現(xiàn)來評價這個施工方案的合理與否，只有滿足平衡好多個目的要求的施工方案才是好的施工方案。因此，選取最優(yōu)解集中的一個或多個解作為所求問題的解，并據(jù)此確定出對應(yīng)的最優(yōu)施工方案。2.施工管理的一大特點第五頁，共32頁。

3.多目的優(yōu)化問題的定義第六頁，共32頁。

4.多目的優(yōu)化問題的根本方法現(xiàn)有的研究多目的優(yōu)化問題的根本方法往往是把各個目的通過帶權(quán)重系數(shù)的方式轉(zhuǎn)化為單目的優(yōu)化問題，如線性加權(quán)法、約束法、目的規(guī)劃法、分層序列法等。這幾種方法存在一些局限性，如有些方法計算效率較低，無法逐一與所有可行解的目的值進(jìn)展比較，有些方法需要進(jìn)展屢次優(yōu)化，加權(quán)值法帶有較強(qiáng)的主觀性，有失科學(xué)性。第七頁，共32頁。

4.多目的優(yōu)化問題的根本方法因此，隨著實際中多目的優(yōu)化問題的日益復(fù)雜，也為了使優(yōu)化更符合實際情況，許多對多目的綜合模型的優(yōu)化開場轉(zhuǎn)向運用智能啟發(fā)式算法。運用較多的有遺傳算法、蟻群算法、粒子群算法等，這些智能方法普遍具有高效性，較強(qiáng)的全局搜索的才能，將其應(yīng)用到大型復(fù)雜網(wǎng)絡(luò)系統(tǒng)問題中具有一定研究價值。第八頁，共32頁。

二、基于蟻群算法的多目的優(yōu)化1.根本原理蟻群算法(Antcolonyalgorithm,ACA)由M.Dorigo，VManiezzo等人提出的是一種智能優(yōu)化算法。蟻群算法是模擬螞蟻覓食過程中總是可以找到從蟻穴到食物之間的最短途徑的行為過程。我們用“信息素〞來描繪螞蟻在搜索食物的過程中產(chǎn)生的物質(zhì)，這種物質(zhì)可以被后續(xù)的螞蟻感知并該物質(zhì)的濃度來指導(dǎo)其前進(jìn)的方向。螞蟻選擇某條途徑的概率就是根據(jù)該途徑上的信息素濃度，濃度高被螞蟻選擇的概率就越大。按照這種信息交流的方式，螞蟻最終尋找到最短的搜索到食物的途徑。第九頁，共32頁。

問題案例第十頁，共32頁。

第十一頁，共32頁。

第十二頁，共32頁。3.多目的優(yōu)化作用機(jī)理本文以根本蟻群算法為根底，采用了基于多種群的蟻群優(yōu)化算法。多種群優(yōu)化算法解決多目的優(yōu)化問題的根本思想是:將蟻群按照目的函數(shù)的個數(shù)分成對應(yīng)的種群數(shù)，假設(shè)有M個目的函數(shù)那么將蟻群分成M個種群，各個種群搜索時彼此是獨立的，按照一定的規(guī)那么進(jìn)展途徑的選擇、信息素的更新，使各種群之間互相作用，最終找到Pareto最優(yōu)解。

第十三頁，共32頁。在對多目的問題的研究中，有的是把多目的轉(zhuǎn)化成單目的優(yōu)化問題。而實際工程工程中，本錢、工期、質(zhì)量及平安之間不能用簡單的線性或者非線性關(guān)系來描繪，所以本文為了更符合實際情況，將協(xié)同化思想引入到蟻群算法中，針對四個目的建立四個蟻群，各種群在各自的目的要求下搜索Pareto解集。

第十四頁，共32頁。〔1〕問題的抽象及算法的定義把建筑工程工程中每一道工序作為完成整個工程工程所必須經(jīng)過的途徑，那么所有工序的順序序列構(gòu)成一條完好的工程工程的全通路。即人工螞蟻搜索的途徑是由n道工序構(gòu)成的施工網(wǎng)絡(luò)圖。由于每道工序有不同種工作形式(即施行方案)，一個。道工序的工程工程就構(gòu)成了一個nxm的矩陣(如下所示)，螞蟻就是在該矩陣中進(jìn)展搜索。矩陣中，lm表示第i道工序的第m種工作形式。

第十五頁，共32頁。那么螞蟻的搜索途徑可以表示如下:

每邊可以采用三元組來表示，如(i，J1，J2)表示第i個工作單元采用的第J1，各施行方案，第i+1個工作單元采用的是第J2個施行方案。圖中的每一條從一行到n行的線路表示整個工程的一個施行方案方案，工期、本錢、質(zhì)量及平安的多目的優(yōu)化問題實際上就是在圖中找出一條從一行到n行的線路，使得四大目的協(xié)同最優(yōu)。第十六頁，共32頁?！?〕途徑選擇策略根據(jù)建筑工程工程施工管理中的工期、本錢、質(zhì)量和平安四大目的，將螞蟻分為四個種群。假設(shè)一共有N只螞蟻，每只螞蟻的行走途徑代表一個施工工程的施行方案方案，螞蟻每做一次選擇就是為某項工序選擇一種施工方案，依次為每個工作單元選擇一種施工方案。選取其中一只螞蟻k為例，把每個工作單元的節(jié)點當(dāng)作一個起始點，螞蟻根據(jù)各邊上的信息素強(qiáng)度來選擇下一步的挪動方向，在完成工序i的第J1個施行方案后繼續(xù)選擇工序i+1的第J2種施行方案的概率為:

第十七頁，共32頁。第十八頁，共32頁。〔3〕信息素更新方式

所有螞蟻完成一次循環(huán)后，各邊的信息素強(qiáng)度按照下式更新:

第十九頁，共32頁。

第二十頁，共32頁。

第二十一頁，共32頁?！?〕種群間信息素的協(xié)調(diào)方式協(xié)同進(jìn)化思想是由Ehrlich和Raven首先的提出的，主要研究的是植物和植物性昆蟲互相作用時會對彼此進(jìn)化產(chǎn)生的影響。協(xié)同進(jìn)化是指當(dāng)存在多個種群時，任何一個種群和其它種群之間存在互相作用，其它種群會對該種群造成影響，可以促進(jìn)對該種群在當(dāng)前環(huán)境中的進(jìn)化。本文把協(xié)同進(jìn)化的思想引入到多種群蟻群算法中，從而解決基于多種種群的蟻群算法的多目的優(yōu)化問題。

第二十二頁，共32頁。本文采用的是多種群蟻群算法，考慮到每個種群存在不同的搜索目的，彼此之間互相影響，例如在起初尋找最低本錢的途徑和最高質(zhì)量的途徑的進(jìn)化方向就是相反的，為了防止各目的向目的的反方向進(jìn)展，從協(xié)同進(jìn)化的角度考慮，把各種群搜索求得的解，分別代入四個目的函數(shù)中求解出對應(yīng)的函數(shù)值，并與目的值進(jìn)展比較，當(dāng)存在種群的目的函數(shù)值不滿足目的值時，對滿足的途徑上的信息素可以進(jìn)展穿插或者變異操作，防止已經(jīng)滿足要求的種群“背道而馳〞，使得后續(xù)迭代的種群可以朝著有利途徑逼近最優(yōu)解。

第二十三頁，共32頁。本文中，為每個目的設(shè)定一個目的閥值，各種群都在該工程的施工網(wǎng)絡(luò)可靠性框圖上進(jìn)展搜索，把每個種群每搜索得到的新解(一個施行方案的工序組合)依次代入目的函數(shù)中，所得值和預(yù)先設(shè)定閥值進(jìn)展比較分析。

產(chǎn)生以下幾種情況:①假設(shè)四個種群搜索的解對應(yīng)的函數(shù)值都優(yōu)于目的值的，就把把該解加到入解集中，再按照公式(4-15)進(jìn)展更新。假設(shè)搜索出的解和非支配解集中的某個解一樣，就對這條途徑上的信息素進(jìn)展一定比例減少，防止陷入部分最優(yōu)。②假設(shè)有三個目的函數(shù)值優(yōu)于設(shè)定的目的值，就將這三個目的種群在其對應(yīng)的途徑上選取其中某段途徑，對此途徑上的信息素進(jìn)展變異處理。第二十四頁，共32頁。③假設(shè)有兩個目的函數(shù)值優(yōu)于設(shè)定的目的值，那么將這兩個目的種群在其對應(yīng)的途徑上選擇其中某一段的信息素進(jìn)展變異處理。④假設(shè)只有一個目的函數(shù)值優(yōu)于設(shè)定的目的閥值，就把這個種群在這條途徑的的信息素和其它三個種群一樣段上的信息素進(jìn)展穿插處理。⑤除了以上幾種情況之外，當(dāng)四個目的函數(shù)值均劣于目的值時，就根據(jù)如下公式更新信息素，并進(jìn)展下一次的迭代搜索。

第二十五頁，共32頁?！?〕途徑對螞蟻的吸引程度

第二十六頁，共32頁?！?〕非支配解集的構(gòu)造

在求解多目的優(yōu)化問題時，在向Pareto前沿逼近的過程中往往需要構(gòu)造非支配解集，即利用多目的優(yōu)化算法不斷尋找最優(yōu)和收斂的過程。群體進(jìn)化過程中形成的最優(yōu)個體集合就構(gòu)成了非支配解集。因此，求解多目的優(yōu)化問題的Pareto最優(yōu)解，可理解成是構(gòu)造非支配解集的過程。

第二十七頁，共32頁。為防止搜索過程中出現(xiàn)一樣的非支配解的情況，在算法中設(shè)置了一個外部集合A(t)用來存放當(dāng)前搜索到的非支配解，從而更好地指導(dǎo)螞蟻對可行區(qū)域的搜索。通過和目的值比較，判斷是否將該解存放于A(t)中，當(dāng)搜索到一個滿足條件的解，但與A(t)解集中的解一樣時，就不再存放于A(t)中。

第二十八頁，共32頁?！?〕搜索禁忌表的構(gòu)造4.算法的實現(xiàn)就建筑工程工程施工過程而言，有些活動可能會制約其他活動的執(zhí)行，每項工序都受到其緊前緊后工序的制約，為了防止螞蟻搜索出的途徑不符合實際工程情況，設(shè)立了一個搜索禁忌表，使螞蟻只能搜索禁忌表內(nèi)允許的節(jié)點。隨著螞蟻遍歷過程的不斷更新，搜索禁忌表也不斷更新。如第k只螞蟻的搜索禁忌表為allowed，當(dāng)螞蟻經(jīng)過工序節(jié)點i后，就將其已經(jīng)經(jīng)過的節(jié)點存放在、isited集(表示螞蟻已經(jīng)遍歷的節(jié)點的集合)中，并且更新該只螞蟻的allowed。第二十九頁，共32頁。根本思路〔2〕算法的實現(xiàn)及流程圖