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

1、多目標優(yōu)化問題的求解算法 2017.12.06目錄一、多目標優(yōu)化問題概述二、基于蟻群算法的多目標優(yōu)化 多目標優(yōu)化問題多目標優(yōu)化問題(MULTI-OBJECTIVE OPTIMIZATION (MULTI-OBJECTIVE OPTIMIZATION PROBLEM,MOPPROBLEM,MOP) )是是由由VILFREDOPARETOVILFREDOPARETO首次首次從數(shù)學的角度提出的。從數(shù)學的角度提出的。一、多目標優(yōu)化問題概述 單目標優(yōu)化問題，只有一個目標函數(shù)，人們只需要尋找滿足該目標函數(shù)的單目標優(yōu)化問題，只有一個目標函數(shù)，人們只需要尋找滿足該目標函數(shù)的最優(yōu)解即可最優(yōu)解即可。 多目標優(yōu)化問

2、題，由于存在多個目標函數(shù)和約束條件，所以當一個目標達多目標優(yōu)化問題，由于存在多個目標函數(shù)和約束條件，所以當一個目標達到最優(yōu)就很有可能令其它目標最劣，各個目標彼此間互相牽制和影響的，難以到最優(yōu)就很有可能令其它目標最劣，各個目標彼此間互相牽制和影響的，難以實現(xiàn)所有目標的最優(yōu)化，所以不能根據(jù)一個目標是否達到來評價函數(shù)解的優(yōu)劣實現(xiàn)所有目標的最優(yōu)化，所以不能根據(jù)一個目標是否達到來評價函數(shù)解的優(yōu)劣程度，因此通常用一個最優(yōu)解的集合來表示多目標優(yōu)化問題的解。這種解稱作程度，因此通常用一個最優(yōu)解的集合來表示多目標優(yōu)化問題的解。這種解稱作ParetoPareto最優(yōu)解。最優(yōu)解。 1.多目標多目標優(yōu)化問題與單目標優(yōu)

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

4、3. 3.多目標優(yōu)化問題的多目標優(yōu)化問題的定義定義 4. 4.多目標優(yōu)化問題的基本方法多目標優(yōu)化問題的基本方法 現(xiàn)有的研究多目標優(yōu)化問題的基本方法往往是把各個目標通過帶權重系數(shù)現(xiàn)有的研究多目標優(yōu)化問題的基本方法往往是把各個目標通過帶權重系數(shù)的的方式轉化為單目標優(yōu)化問題，如線性加權法、約束法、目標規(guī)劃法、分層序列方式轉化為單目標優(yōu)化問題，如線性加權法、約束法、目標規(guī)劃法、分層序列法法等。等。 這幾種方法存在一些局限性，如有些方法計算效率較低，無法逐一與所有這幾種方法存在一些局限性，如有些方法計算效率較低，無法逐一與所有可可行解的目標值進行比較，有些方法需要進行多次優(yōu)化，加權值法帶有較強的主行解的

5、目標值進行比較，有些方法需要進行多次優(yōu)化，加權值法帶有較強的主觀觀性，有失科學性。性，有失科學性。 4. 4.多目標優(yōu)化問題的基本方法多目標優(yōu)化問題的基本方法 因此，隨著實際中多目標優(yōu)化問題的日益復雜，也為了使優(yōu)化更符合實際因此，隨著實際中多目標優(yōu)化問題的日益復雜，也為了使優(yōu)化更符合實際情況，許多對多目標綜合模型的優(yōu)化開始轉向運用智能啟發(fā)式算法。情況，許多對多目標綜合模型的優(yōu)化開始轉向運用智能啟發(fā)式算法。 運用較多的有遺傳算法、蟻群算法、粒子群算法等，這些智能方法普遍具運用較多的有遺傳算法、蟻群算法、粒子群算法等，這些智能方法普遍具有高效性，較強的全局搜索的能力，將其應用到大型復雜網(wǎng)絡系統(tǒng)問題

6、中具有有高效性，較強的全局搜索的能力，將其應用到大型復雜網(wǎng)絡系統(tǒng)問題中具有一定研究價值。一定研究價值。 二、基于蟻群算法的多目標優(yōu)化1. 1.基本原理基本原理 蟻群算法(Ant colony algorithm,ACA)由M. Dorigo，V Maniezzo等人提出的是一種智能優(yōu)化算法。蟻群算法是模擬螞蟻覓食過程中總是能夠找到從蟻穴到食物之間的最短路徑的行為過程。 我們用“信息素”來描述螞蟻在搜索食物的過程中產(chǎn)生的物質，這種物質能夠被后續(xù)的螞蟻感知并該物質的濃度來指導其前進的方向。螞蟻選擇某條路徑的概率就是根據(jù)該路徑上的信息素濃度，濃度高被螞蟻選擇的概率就越大。依照這種信息交流的方式，螞蟻

7、最終尋找到最短的搜索到食物的路徑。 2.TSP2.TSP問題案例問題案例 3. 3.多目標優(yōu)化作用機理多目標優(yōu)化作用機理 本文以基本蟻群算法為基礎，采用了基于多種群的蟻群優(yōu)化算法。本文以基本蟻群算法為基礎，采用了基于多種群的蟻群優(yōu)化算法。 多種群優(yōu)化算法解決多目標優(yōu)化問題的基本思想是多種群優(yōu)化算法解決多目標優(yōu)化問題的基本思想是: :將蟻群按照目標函數(shù)將蟻群按照目標函數(shù)的個數(shù)分成對應的種群數(shù)，假如有的個數(shù)分成對應的種群數(shù)，假如有MM個目標函數(shù)那么將蟻群分成個目標函數(shù)那么將蟻群分成MM個種群個種群，各各個種群搜索時彼此是獨立的，按照一定的規(guī)則進行路徑的選擇、信息素的更新，個種群搜索時彼此是獨立的，

8、按照一定的規(guī)則進行路徑的選擇、信息素的更新，使各種群之間相互作用，最終找到使各種群之間相互作用，最終找到ParetoPareto最優(yōu)解。最優(yōu)解。 在對多目標問題的研究中，有的是把多目標轉化成單目標優(yōu)化問題。而在對多目標問題的研究中，有的是把多目標轉化成單目標優(yōu)化問題。而實際工程項目中，成本、工期、質量及安全之間不能用簡單的線性或者非線實際工程項目中，成本、工期、質量及安全之間不能用簡單的線性或者非線性關系來描述，所以本文為了更符合實際情況，將協(xié)同化思想引入到蟻群算性關系來描述，所以本文為了更符合實際情況，將協(xié)同化思想引入到蟻群算法中，針對四個目標建立四個蟻群，各種群在各自的目標要求下搜索法中，

9、針對四個目標建立四個蟻群，各種群在各自的目標要求下搜索ParetoPareto解解集。集。 （1 1）問題的抽象及算法的定義問題的抽象及算法的定義 把建筑工程項目中每一道工序作為完成整個工程項目所必須經(jīng)過的路徑，那把建筑工程項目中每一道工序作為完成整個工程項目所必須經(jīng)過的路徑，那么所有工序的順序序列構成一條完整的工程項目的全通路。即人工螞蟻搜索的路么所有工序的順序序列構成一條完整的工程項目的全通路。即人工螞蟻搜索的路徑是由徑是由n n道工序構成的施工網(wǎng)絡圖。由于每道工序有不同種工作模式道工序構成的施工網(wǎng)絡圖。由于每道工序有不同種工作模式( (即實施方案即實施方案) )，一個。道工序的工程項目就

10、構成了一個一個。道工序的工程項目就構成了一個 n x m n x m的矩陣的矩陣( (如下所示如下所示) )，螞蟻就是在該矩，螞蟻就是在該矩陣中進行搜索。矩陣中，陣中進行搜索。矩陣中，lmlm表示第表示第i i道工序的第道工序的第m m種工作模式。種工作模式。 那么螞蟻的搜索路徑可以表示如下那么螞蟻的搜索路徑可以表示如下: : 每邊可以采用三元組來表示，每邊可以采用三元組來表示，如如( (i i，J1J1，J2)J2)表示第表示第i i個工作單元采個工作單元采用的第用的第J1J1，各實施方案，第，各實施方案，第i+1i+1個工個工作單元采用的是第作單元采用的是第J2J2個實施方案。個實施方案。

11、圖中的每一條從一行到圖中的每一條從一行到n n行的線路行的線路表示整個項目的一個實施計劃方案，表示整個項目的一個實施計劃方案，工期、成本、質量及安全的多目標工期、成本、質量及安全的多目標優(yōu)化問題實際上就是在圖中找出一優(yōu)化問題實際上就是在圖中找出一條從一行到條從一行到n n行的線路，使得四大行的線路，使得四大目標協(xié)同最優(yōu)。目標協(xié)同最優(yōu)。 （2 2）路徑選擇策略路徑選擇策略 根據(jù)建筑工程項目施工管理中的工期、成本、質量和安全四大目標，將螞蟻根據(jù)建筑工程項目施工管理中的工期、成本、質量和安全四大目標，將螞蟻分為四個種群。假設一共有分為四個種群。假設一共有N N只螞蟻，每只螞蟻的行走路徑代表一個施工項

12、目的只螞蟻，每只螞蟻的行走路徑代表一個施工項目的實施計劃方案，螞蟻每做一次選擇就是為某項工序選擇一種施工方案，依次為每實施計劃方案，螞蟻每做一次選擇就是為某項工序選擇一種施工方案，依次為每個工作單元選擇一種施工方案。個工作單元選擇一種施工方案。 選取其中一只螞蟻選取其中一只螞蟻k k為例，把每個工作單元的節(jié)點當作一個起始點，螞蟻根據(jù)為例，把每個工作單元的節(jié)點當作一個起始點，螞蟻根據(jù)各邊上的信息素強度來選擇下一步的移動方向，在完成工序各邊上的信息素強度來選擇下一步的移動方向，在完成工序i i的第的第J1J1個實施方案后個實施方案后繼續(xù)選擇工序繼續(xù)選擇工序i+1i+1的第的第J2J2種實施方案的概

13、率為種實施方案的概率為: : （3 3）信息素更新方式信息素更新方式 所有螞蟻完成一次循環(huán)后，各邊的信息素強度按照下式更新所有螞蟻完成一次循環(huán)后，各邊的信息素強度按照下式更新: : （4 4）種群間信息素的協(xié)調方式種群間信息素的協(xié)調方式 協(xié)同進化思想是由協(xié)同進化思想是由EhrlichEhrlich和和RavenRaven首先的提出的，主要研究的是植物和植物性首先的提出的，主要研究的是植物和植物性昆蟲互相作用時會對彼此進化產(chǎn)生的影響。昆蟲互相作用時會對彼此進化產(chǎn)生的影響。 協(xié)同進化是指當存在多個種群時，任何一個種群和其它種群之間存在相互作協(xié)同進化是指當存在多個種群時，任何一個種群和其它種群之間存

14、在相互作用，其它種群會對該種群造成影響，能夠促進對該種群在當前環(huán)境中的進化。用，其它種群會對該種群造成影響，能夠促進對該種群在當前環(huán)境中的進化。 本文把協(xié)同進化的思想引入到多種群蟻群算法中，從而解決基于多種種群的本文把協(xié)同進化的思想引入到多種群蟻群算法中，從而解決基于多種種群的蟻群算法的多目標優(yōu)化問題。蟻群算法的多目標優(yōu)化問題。 本文采用的是多種群蟻群算法，考慮到每個種群存在不同的搜索目標，本文采用的是多種群蟻群算法，考慮到每個種群存在不同的搜索目標，彼此之間相互影響，例如在起初尋找最低成本的路徑和最高質量的路徑的進彼此之間相互影響，例如在起初尋找最低成本的路徑和最高質量的路徑的進化方向就是相

15、反的，為了避免各目標向目標的反方向進行，從協(xié)同進化的角化方向就是相反的，為了避免各目標向目標的反方向進行，從協(xié)同進化的角度考慮，把各種群搜索求得的解，分別代入四個目標函數(shù)中求解出對應的函度考慮，把各種群搜索求得的解，分別代入四個目標函數(shù)中求解出對應的函數(shù)值，并與目標值進行比較，當存在種群的目標函數(shù)值不滿足目標值時，對數(shù)值，并與目標值進行比較，當存在種群的目標函數(shù)值不滿足目標值時，對滿足的路徑上的信息素可以進行交叉或者變異操作，防止已經(jīng)滿足要求的種滿足的路徑上的信息素可以進行交叉或者變異操作，防止已經(jīng)滿足要求的種群群“背道而馳背道而馳”，使得后續(xù)迭代的種群能夠朝著有利路徑逼近最優(yōu)解，使得后續(xù)迭代

16、的種群能夠朝著有利路徑逼近最優(yōu)解。 本文中，為每個目標設定一個目標閥值，各種群都在該工程的施工網(wǎng)絡本文中，為每個目標設定一個目標閥值，各種群都在該工程的施工網(wǎng)絡可靠性框圖上進行搜索，把每個種群每搜索得到的新解可靠性框圖上進行搜索，把每個種群每搜索得到的新解( (一個實施方案的工序一個實施方案的工序組合組合) )依次代入目標函數(shù)中，所得值和預先設定閥值進行比較分析依次代入目標函數(shù)中，所得值和預先設定閥值進行比較分析。 產(chǎn)生以下幾種情況產(chǎn)生以下幾種情況: : 若四個種群搜索的解對應的函數(shù)值都優(yōu)于目標值的，就把把該解加到入若四個種群搜索的解對應的函數(shù)值都優(yōu)于目標值的，就把把該解加到入解集中，再按照公

17、式解集中，再按照公式(4-15)(4-15)進行更新。若搜索出的解和非支配解集中的某個解相進行更新。若搜索出的解和非支配解集中的某個解相同，就對這條路徑上的信息素進行一定比例減少，防止陷入局部最優(yōu)。同，就對這條路徑上的信息素進行一定比例減少，防止陷入局部最優(yōu)。 若有三個目標函數(shù)值優(yōu)于設定的目標值，就將這三個目標種群在其對應若有三個目標函數(shù)值優(yōu)于設定的目標值，就將這三個目標種群在其對應的路徑上選取其中某段路徑，對此路徑上的信息素進行變異處理。的路徑上選取其中某段路徑，對此路徑上的信息素進行變異處理。 若有兩個目標函數(shù)值優(yōu)于設定的目標值，那么將這兩個目標種群在其對若有兩個目標函數(shù)值優(yōu)于設定的目標值

18、，那么將這兩個目標種群在其對應的路徑上選擇其中某一段的信息素進行變異處理。應的路徑上選擇其中某一段的信息素進行變異處理。 若只有一個目標函數(shù)值優(yōu)于設定的目標閥值，就把這個種群在這條路徑若只有一個目標函數(shù)值優(yōu)于設定的目標閥值，就把這個種群在這條路徑的的信息素和其它三個種群相同段上的信息素進行交叉處理。的的信息素和其它三個種群相同段上的信息素進行交叉處理。 除了以上幾種情況之外，當四個目標函數(shù)值均劣于目標值時，就根據(jù)如除了以上幾種情況之外，當四個目標函數(shù)值均劣于目標值時，就根據(jù)如下公式更新信息素，并進行下一次的迭代搜索。下公式更新信息素，并進行下一次的迭代搜索。 （5 5）路徑對螞蟻的吸引程度路徑

19、對螞蟻的吸引程度 （6 6）非支配解集的構造非支配解集的構造 在求解多目標優(yōu)化問題時，在向在求解多目標優(yōu)化問題時，在向ParetoPareto前沿逼近前沿逼近的過程中往往需要構造非支配解集，即利用多目標的過程中往往需要構造非支配解集，即利用多目標優(yōu)化算法不斷尋找最優(yōu)和收斂的過程。群體進化過優(yōu)化算法不斷尋找最優(yōu)和收斂的過程。群體進化過程中形成的最優(yōu)個體集合就構成了非支配解集。因程中形成的最優(yōu)個體集合就構成了非支配解集。因此，求解多目標優(yōu)化問題的此，求解多目標優(yōu)化問題的ParetoPareto最優(yōu)解，可理解成最優(yōu)解，可理解成是構造非支配解集的過程是構造非支配解集的過程。 為防止搜索過程中出現(xiàn)相同的

20、非支配解的情況，在算法中設置為防止搜索過程中出現(xiàn)相同的非支配解的情況，在算法中設置了一個外部集合了一個外部集合A(t)A(t)用來存放當前搜索到的非支配解，從而更好地用來存放當前搜索到的非支配解，從而更好地指導螞蟻對可行區(qū)域的搜索。通過和目標值比較，判斷是否將該解指導螞蟻對可行區(qū)域的搜索。通過和目標值比較，判斷是否將該解存放于存放于A(t)A(t)中，當搜索到一個滿足條件的解，但與中，當搜索到一個滿足條件的解，但與A(t)A(t)解集中的解相解集中的解相同時，就不再存放于同時，就不再存放于A(t)A(t)中。中。 （1 1）搜索禁忌表的構造搜索禁忌表的構造4. 4.算法的實現(xiàn)算法的實現(xiàn) 就建筑工程項目施工過程而言，有些活動可能會制約其他活動的執(zhí)行，每項就建筑工程項目施工過程而言，有些活動可能會制約其他活動的執(zhí)行，每項工序都受到其緊前緊后工序的制約，為了防止螞蟻搜索出的路徑不符合實際工程工序都受到其緊前