//Logo Image
作者:徐業良(1995-09-15),推薦:徐業良(2001-06-22),最近更新:徐業良(2004-10-29)
附註:本文為元智大學機械工程研究所最佳化設計課程教材,僅限於教學上學生個人使用,原書初版由宏明書局印行。

離散式變數最佳化問題

到目前為止,我們所討論的最佳化設計問題中,都是假設設計變數可以是在可行區間內的任何連續數值,但是通常在實際的工程設計問題上,設計者常常必須面對許多非連續性的設計變數,包括「離散變數」、「整數變數」、以及01的「二元變數」

最明顯的例子,是當設計工程師作一個機械系統設計時,設計者通常只可由標準件手冊或型錄中去選取標準尺寸的零件,舉凡馬達功率、軸承內外徑、齒輪的齒數、鋼板的厚度……等等,都只有固定的一些離散的標準數值可以選擇。因此以要決定的這些零件尺寸為設計變數,建構而成的最佳化設計模型,就會是離散式變數的最佳化設計問題。

整數變數問題和二元變數問題則可以視為離散式變數最佳化設計問題的特例,亦即變數的離散值僅能是整數值,或者01二元數。而整數變數和二元變數的引入,使得在工程最佳化問題中可以處理的設計決策形態豐富許多,例如倘若在設計問題中,設計變數是在決定組合系統所需要某種零件的數目時,所能解得的零件數目最佳值即必須是整數解,在此類問題中的設計變數就是整數式變數。另外如果設計問題中需要從不同的設計中做取捨選擇,這時設計問題決策的決定只能出現“是”或“否”,設計者面對的便是一個二元變數的最佳化設計問題。

離散式變數最佳化設計問題在工程上的應用雖然十分普遍且重要,但是較諸連續式變數的最佳化問題,這類問題是相當難解的,事實上這仍是目前最佳化設計上主要的研究領域之一,到目前為止儘管有許多研究成果發表,但是還沒有一個公認強健而有效率的數值演算法,可以解大規模、非線性離散式變數的最佳化問題。

本章探討內容重點在於離散變數、整數變數、二元變數的一些基本觀念介紹,並介紹解線性離散式變數最佳化問題的演算法-「整數規劃法(integer programming, IP),最後探討已發表的研究文獻中解非線性離散式變數最佳化問題的一般原則。

1.     離散變數、整數變數、與二元變數

前面介紹的連續式變數最佳化設計問題,設計變數不外是設計的尺寸、性能數字等。而引入離散變數、整數變數、與二元變數之後,最佳化設計問題可以作的設計決策(design decision)形態也隨之豐富許多。這一節裡首先對離散變數、整數變數、與二元變數可處理的問題形態作一介紹,並討論離散變數及整數變數問題如何轉換成二元變數問題。接下來則討論解離散式變數最佳化問題的一些基本想法,並介紹所謂「枝界法(branch and bound)解二元變數問題。

1.1 離散式變數問題

作業研究(operation research)這個學科中相當普遍的一本教科書“Introduction to Operation Research” [Hillier and Lieberman, 1990],對二元變數可以處理的問題,一共列出了六種類型,這裡由機械設計問題的觀點將這六種設計決策類型整理如下。

1.      是或否的選擇

設計問題中常常會有幾種不同設計概念都可以產生類似功能的情況,這時“最佳化”問題已經不是在決定某個設計中的尺寸等等因素,而是設計者必須從幾個不同的設計中選取一個性能最好,且符合成本的設計。舉一個簡單的例子,假設設計概念ABC都能達成類似功能,而三者的性能分別可用一性能指標來表示,三種概念的成本則分別為。今設計者要在三個設計中選取一個性能最好的,且其成本要低於,這樣一個最佳化設計問題可以用如下的二元變數形式來表示:

        min. 

        s.t.   

               

                                                                                             (1)

注意此處的集合限制條件,即限制了為二元變數。很明顯的,這些二元變數等於1時表示設計決策為“是”,也就是選擇這個設計,等於0時則表示“否”,不選擇這個設計。另外等式限制條件保證了三個設計變數中只有一個等於1,亦即三個設計概念中只能選擇一個設計,而限制條件則表示不管選擇哪一個設計(不管哪一個二元變數是1),成本均須小於

◇作業1

自行假設一些參數,以GAMS解出上式。其結果是否合理?這個問題與先前討論的最佳化設計問題本質上有何差異?◇

2.      有條件式的限制條件

將前面所舉的例子,再加入一些限制條件,例如設計者從不同的設計概念中做取捨選擇時,如果選擇設計概念A的話,限制條件必須成立,而選擇設計概念B的話,限制條件必須成立,同樣的如果選擇設計概念C的話,限制條件必須成立。這三個有條件式的限制條件,可以表示如下:

       

       

                                                                                               (2)

其中M是一個很大的數字。如此當二元變數等於0,即不選擇這個設計概念時,其所對應的限制條件成為,應自動可以滿足,此限制條件可以視為不存在,而若二元變數等於1,即選擇這個設計概念時,其所對應的限制條件則必須成立。

3.      N個限制條件中必須滿足其中K

將式(2)作進一步推展,在N個限制條件中必須滿足其中K個的情況,也可以用下式簡潔地表示:

         i = 1, ..., N

       

        , i = 1, ..., N                                                                              (3)

其中表示N個二元變數中只有K個等於1,而則表示K個等於1的二元變數,其所對應的限制條件也必須為有效,而其他等於0的二元變數所對應的限制條件則可視為不存在。

4.      固定成本問題

在工廠生產規劃中常會討論到生產的「固定成本(fixed costs)」,生產總成本中有一部份是「變動成本(variable costs)」,這一部份的成本與產量成正比,如生產所需的材料、人工等,產量越大,這部份的成本也就越高;而固定成本則是指不論產量多少,如果生產便必須要開支的成本,如機器設備的投資等。因此生產成本的函數,常常會是以下形式:

                                                                            (4)

其中x為產量,K為固定成本,cx則為變動成本。

如式(4)的函數也可以簡潔地表示成二元變數的函數:

        Cost = Ky + cx,

        ,

        ,                                                                                       (5)

其中M是一個很大的數字,或者可視為在此固定成本投資下的最大產量。當y等於0時,x也等於0,表示不生產,成本為0;而y當等於1時,表示要生產,總成本則為K+cx

5.      以二元變數表示一般離散變數的問題

前面提到二元變數可以看作離散變數的特例,但事實上一般離散變數問題可以輕易改寫成二元變數問題。一般離散變數的問題,可以用一個離散集合限制條件來表示,如變數x僅可屬於m個不同數值,可表示為

                                                                                            (6)

(6)的離散集合限制條件,也可以用二元變數來表示:

       

        , , i = 1, ..., m                                                             (7)

上式中表示m個二元變數中,只有一個可以等於1,而變數x即等於該二元變數相對應的離散值。

6.      以二元變數表示整數變數的問題

整數變數問題也可以輕易改寫成二元變數問題。如果我們知道一個整數變數的上下界,

        ,                                                                                                         (8)

我們可以把這個整數變數改寫為

                                                                                                                                   (9)

其中是二元變數。

◇作業2

某公司董事會正在考慮七個新產品開發案,這七個新產品開發案所需資金和預估之利潤如下表(單位為萬元)

開發案

1

2

3

4

5

6

7

預估利潤

17

10

15

19

7

13

9

所需資金

43

28

34

48

17

32

23

該公司可用於新產品開發的總資金額為一百萬元,且各新產品開發案也各有限制,如開發案12不能同時進行,開發案34也不能同時進行,另外如沒有進行12的話,34都不能進行。建立一個二元變數最佳化問題,決定這家公司的新產品開發案最佳投資組合,以GAMS解出,並闡釋其結果(修改自Hillier and Lieberman, 1990)。◇

1.2 解離散式變數最佳化問題的一些基本想法

直覺上你也許會覺得解離散式變數的非線性最佳化問題應該比解連續式變數問題要容易,因為離散式變數最佳化問題的搜尋空間是「有限的(finite)」,而連續式變數問題的搜尋空間則是「無限的(infinite)」。先前介紹過各種最佳化的數值方法來解連續式變數的最佳化問題,直覺上在解離散式變數最佳化問題時,你也許會先將設計變數假設成連續式變數,解得設計變數連續數值的最佳解後,再檢查連續最佳解相鄰的離散點或整數點的可行性,以決定最佳的離散解或整數解。

這兩個直覺式的想法事實上都有些問題。首先是離散式變數最佳化問題的困難度呈「指數型成長(exponential growth),其解的搜尋空間固然是有限的,但此搜尋空間隨設計變數個數增多而呈指數式的增大。例如一個有n個二元設計變數的最佳化設計問題,需要考慮的搜尋空間有2n個離散值,n=20時便有超過一百萬個離散解,n=30時離散解的個數將超過十億個,變數個數一多,如無特別設計的演算法而採用「竭盡搜尋(exhaustive search)」的話,將不是任何現有的計算器所能處理的。

另外先解得設計變數連續數值的最佳解後,再選擇最佳連續解相鄰的離散點或整數解(例如將連續解四捨五入、無條件捨去或進入),這種直覺的想法雖然可能是解決工程問題最直接、最簡單的作法,但在許多問題中也不盡然可行。首先是不管將連續解四捨五入、無條件捨去或進入,都可能得不到可行解。用以下這個簡單的線性規劃問題做例子:

        min. 

        s.t.   

               

                                                                                                                (10)

這個線性規劃問題的連續最佳解為x1=6.5x2=10,但若將其中x1之值進位或捨去而成為67時(或任何其它整數),可以發現所得解並非可行解,要得到可行解須同時改變x2的值才行。倘若限制條件及設計變數數目很多時,很難判定應如何進位或捨去才能得到可行解,求解過程將變得困難重重,而在連續解附近作竭盡搜尋,又會有前面提到變數個數增加時,搜尋空間將呈指數成長的問題。

這種作法另外一個問題是,即使將連續之最佳解四捨五入而順利地得到一可行解,也仍然無法確認此解是否為最佳的離散解或整數解。事實上最佳離散解或整數解可能並不在連續之最佳解的附近,下面一個例子便常被用來說明這個情況[Hillier and Lieberman, 1990]

        min. 

        s.t.   

               

                                                                                                        (11)

1中可以清楚看出,這個線性規劃問題的設計變數為連續時,在x1=2x2=1.8,有最小目標函數值-11,在這個連續最佳解周圍最好的可行整數解是(x1, x2)=(2, 1),此時目標函數值為-7,然而這個問題的最佳整數解是(x1, x2)=(0, 2)卻不在連續解的附近,這個整數解的最小目標函數值為-10

1. 離散最佳解不一定在連續最佳解的附近

離散式變數最佳化問題在本質上與連續式變數問題其實並不相同,而事實上也比連續式變數問題難解得多。下一節裡便將介紹解二元變數問題一個很基本而重要的方法--「枝界法」。

1.3 枝界法

前面提到離散式變數的問題其搜尋空間是有限的,所以這種問題最“保險”的方法,就是把各離散點所有可能的組合都計算出來,看看哪一種組合能滿足限制條件,且目標函數值最小,便一定是這個最佳化問題的全域最佳解。

這種搜尋的過程中比較有系統的作法,是固定一個變數值,再將其他變數作分枝。例如一個二元變數問題可以表示成如下的樹狀分枝圖:

2. 二元變數問題的樹狀分枝圖

枝界法的「枝(branching)」也就是將離散式變數最佳化問題中的每一個變數,作如圖2有系統的分枝。然而離散式變數問題的搜尋空間隨著變數個數成指數增加,竭盡搜尋通常並不可能。事實上在許多情況下我們並不需要作竭盡搜尋,例如說如果我們知道往這個分枝搜尋下去可以得到最好的解,都不如我們已知的最佳解的話,便可以把這個分枝「捨棄(fathoming),不再繼續搜尋下去。枝界法中的「界(bound)」,就是在求最小值的問題中,往某一分枝搜尋時,計算在這個分枝中可以得到的目標函數值的下界,如果這個下界比現有的最小值為高,意思是往這個分枝搜尋下去可以得到最好的解,其目標函數值都不會小於我們已知最佳解的目標函數值,便可將此分枝捨棄,不必再搜尋下去。以下我們便以一個簡單的二元變數問題作例子,來說明枝界法的程序。

加州製造公司正考慮擴張,在洛杉機或舊金山,甚至兩地同時增設新工廠。該公司同時也考慮增設最多一個新倉庫,但是新倉庫的地點必須在有增設新工廠的城市。在各城市設新廠、新倉庫可獲得之總利潤及所需資本投資如下表所示:

決策                問題                        決策變數                總利潤            資本需求

1.     是否在洛杉機設廠?                                        9百萬           6百萬

2.     是否在舊金山設廠?                                       5百萬           3百萬

3.     是否在洛杉機設倉庫?                                    6百萬           5百萬

4.     是否在舊金山設倉庫?                                   4百萬           2百萬

該公司可用之總資本為一千萬,試找出總利潤最大之可行投資組合[Hillier and Lieberman, 1990]

這個投資組合的決策問題可用如下的二元變數最佳化模型來表示:

        min. 

            s.t.    

                      

               

               

                是二元變數                                                               (12)

其中目標函數f是設新廠、新倉庫所能獲得的總利潤,限制條件限制了總投資額不得超過一千萬元,限制條件表示洛杉機和舊金山兩地僅能設置一個新倉庫,限制條件則表示新倉庫必須要設在有新廠設立的城市。

◇作業3

將前述二元變數問題以GAMS解出,並闡釋其結果。◇

我們便以這個簡單的問題來描述枝界法進行的步驟。首先考慮變數,當,也就是如果決定不在洛杉機設立新廠,我們可以得到如下的子問題:

        min. 

        s.t.   

               

               

                是二元變數                                                                    (13)

在這裡先要討論一個重要的觀念,就是如果將一個最佳化問題的部分限制條件鬆弛的話,最佳化問題的可行區間增大,在較大可行區間中所求得解也必定較佳,因此其目標函數最小值必定小於或等於原始最佳化問題目標函數的最小值。也就是說,這個「鬆弛問題(relaxation)」的目標函數最小值可視為原始最佳化問題目標函數的下界,原始最佳化問題的目標函數,不可能小於鬆弛問題目標函數的最小值。

在式(13)中,如果我們暫時鬆弛是二元變數這個集合限制條件,而以取代,視之為連續式變數,那麼式(13)便成為一個「線性規劃鬆弛問題(LP relaxation),其最佳解為f=-9。因為此時我們暫時鬆弛了是二元變數這個集合限制條件,因此f=-9也是我們往這個分枝繼續搜尋所可能得到的目標函數值的下界,繼續往下搜尋所得到目標函數值不可能比-9更小。

一個巧合的情況是,這個線性規劃鬆弛問題的最佳解正好也滿足二元變數集合限制條件,因此這個鬆弛問題的解對於原始問題式(12)來說,也是一個可行解,因此我們得到了一個「現有最佳可行解(incumbent)」,往這個分枝繼續搜尋下去,其他可行解一定不會比這個解更佳,因此以下的分枝便可以捨棄,不再繼續搜尋下去。

接下來考慮變數的情況,我們可以得到如下另一個子問題:

        min. 

        s.t.   

               

               

               

                是二元變數                                                                    (14)

(14)的線性規劃鬆弛問題的解為f=-16.2,其中因為目標函數各項係數均為整數,不可能得到有小數的值,因此目標函數值小數部分可以捨去成為f=-16,而-16便是繼續往這個分枝搜尋可能得到目標函數最小值的下界。

至此我們可以歸納出解二元變數最佳化問題,枝界法的一般步驟:

步驟一(枝,branching

選定一個變數設其為01,產生兩個子問題。

步驟二(界,bounding

解出每一子問題之線性規劃鬆弛問題,得到在此分枝搜尋時目標函數最小值的下界。

步驟三(捨棄測試,fathoming test

對每一子問題施以以下三個捨棄測試,如符合其中一項測試,則將此分枝捨棄,不繼續往下搜尋:

測試一:此分支目標函數的下界大於現有最佳可行解目標函數最小值。

測試二:線性規劃鬆弛問題無可行解。

測試三:線性規劃鬆弛問題的解亦符合二元變數集合限制條件。

接下來以同樣程序考慮變數兩種情況。時得到子問題的線性規劃鬆弛問題解為f=-13時子問題的線性規劃鬆弛問題解則為f=-16。在這兩個子問題中,前述三個捨棄測試都失敗,因此兩個分枝都可繼續搜尋下去,不過當的分枝下界為-13,而的分枝下界為-16,因此我們先搜尋這一個分枝,的分枝以後可「回溯(backtrack)」回來繼續搜尋。這種選擇較好的分枝繼續搜尋的規則,便叫作「最好下界規則(best bound rule)」,這也是一般各種形態的枝界法最常用來選擇搜尋分枝的方法。

接下來再以同樣的程序考慮變數兩種情況。時得到子問題的線性規劃鬆弛問題解為f=-16時子問題的線性規劃鬆弛問題則無可行解,因此捨棄此分枝,向的分枝繼續搜尋。在此分枝中考慮變數兩種情況,時得到子問題的線性規劃鬆弛問題解為f=-14,這個值小於我們「現有最佳可行解」的目標函數值-9,因此這個解成為我們新的現有最佳可行解。時子問題的線性規劃鬆弛問題則無可行解,因此捨棄此分枝。

這個分枝走到底了,我們再回溯至前面的分枝,但此時發現這個分枝的下界(-13)已經大於我們新的現有最佳可行解的目標函數值(-14),捨棄測試一生效,這個分枝可以被捨棄,不再繼續搜尋。這裡也可以看出採用前述「最好下界規則」選擇優先搜尋的分枝,在後續「回溯」時可能可以直接捨棄尚未被搜尋分枝,節省搜尋時間。

至此我們可以確定這個二元變數最佳化問題的全域最佳解是f=-14,也就是最佳投資組合是在洛杉機、舊金山各設一個新廠,而不設任何新倉庫,此時總利潤為一千四百萬元。以上的搜尋結果可以用圖3的樹狀分枝圖來表示,其中F(1)F(2)F(3)表示此分枝因捨棄測試一、二、或三生效而不繼續往下搜尋。

3. 枝界法解二元變數最佳化問題[Hillier and Lieberman, 1990]

由此圖中可以看出,在四個二元變數十六種可能的組合中,使用枝界法僅須檢查其中三種,大大增加了搜尋效率。然而必須要澄清的是,儘管枝界法只需要搜尋整體二元樹的一小部份(如在此例中僅須搜尋約五分之一),但在二元變數個數很多,整體二元樹極大時,儘管使用枝界法仍是幾乎不可能解的問題。

◇作業4

考慮式(11)中的整數規劃問題。設變數,將此整數規劃問題轉化成一個二元變數問題,用二元變數的枝界法解出其最佳解,並繪出如圖3之步驟。

2.     整數規劃法

整數規劃問題的標準形式,基本上和線性規劃問題十分類似,只是多了一個變數必須屬於整數集合之集合限制條件。如果只有部分變數必須屬於整數集合,其他變數仍是一般連續式變數,這樣的問題也稱作「混合整數規劃(mixed integer programming, MIP)

        min. 

        s.t.   

               

                                                                              (15)

整數規劃問題自然可以先化成二元變數問題,再用前一節介紹的枝界法解出,但是這樣作顯然需要過多二元變數。整數規劃問題僅是線性規劃問題加上了整數的集合限制條件,因此解整數規劃問題一般便將枝界法與解線性規劃化問題的簡算法結合起來。以下面這個簡單的整數規劃問題為例[Belegundu and Arora, 1979]

        min. 

        s.t.   

               

               

                                                                                     (16)

這個整數規劃問題的枝界法求解過程如圖4所示。式(16)的線性規劃鬆弛問題的解為f=-82.7。首先考慮變數,這裡我們所要搜尋的分枝為兩種情況(很明顯的,在這個區間中並沒有可行的整數解)。將這兩個式子分別加入式(16)中,可以得到搜尋分枝的兩個子問題(子問題一、子問題二),而其線性規劃鬆弛問題的解分別為f=-81.5以及f=-80這組解已經是整數解了,根據前面的捨棄測試三,可以予以捨棄,不再繼續往這個分枝搜尋,我們的現有最佳可行解的目標函數值也修正為-80

這個分枝點考慮變數,我們所要搜尋的分枝為兩種情況,將這兩個式子分別再加入子問題一中,又可以得到這個搜尋分枝的兩個新的子問題(子問題三、子問題四),而其線性規劃鬆弛問題的解分別為f=-80以及f=-80也是一個可行的整數解,捨棄測試三生效。可以不再往下搜尋。這個點上目標函數值亦為-80,也就是說繼續往下搜尋可能得到的整數可行解必定大於-80,因此捨棄測試生效,可以不再搜尋下去。注意在這個節點如果要繼續搜尋下去的話,我們應該重新回到變數,將加入子問題四中,形成兩個新的子問題

4. 枝界法解整數規劃問題

因此這個整數規劃問題經由枝界法所得到的最佳整數解是以及,最小目標函數值為-80。許多商用最佳化軟體如LINDOGAMS中的ZOOM(Zero/One Optimization Method)演算法,都已經能有效的處理整數規劃以及混合整數規劃問題,雖然所能處理的整數變數數目仍然有限制。

3.     非線性離散式變數問題

前一節談到的整數規劃法所處理的是線性的問題,然而我們在工程最佳化問題中所面對的都是非線性問題。AroraHuang、和Hsieh[1994]對解非線性離散式變數問題的方法,作了一個很完整的整理,他們將處理「混合離散非線性規劃(mixed-discrete nonlinear programming, MDNLP)問題的演算法分成六大類:

(1)       枝界法。

(2)       模擬退火法(simulated annealing)

(3)       序列線性化方法(sequential linearization method)

(4)       懲罰函數法。

(5)       拉氏鬆弛法(Lagrangian relaxation method)

(6)       其他方法。

這裡便擇要在以下各小節中分別討論這些方法,除了簡單介紹這些方法的基本原理之外,本節最主要目的在討論這些方法在工程最佳化問題上,尤其是有所謂內隱式限制條件的最佳化問題上的適用性,讀者如果需要實際應用這些方法,演算法的詳細程序請查閱本書參考資料中所列之文獻。

3.1 混合離散非線性規劃的枝界法

混合離散非線性規劃的枝界法,原理和前一節中所介紹整數規劃的枝界法是完全相同的,只是在整數規劃枝界法中每一個分枝節點所要解的子問題是線性規劃鬆弛問題,而在混合離散非線性規劃的枝界法中,在每一個分枝節點所要解的子問題是非線性規劃的鬆弛問題,因此也可想而知,這時候解每一個子問題困難度遠超過整數規劃的枝界法。

也正因為如此,當離散變數個數增多時,用枝界法來解混合離散非線性規劃問題更是困難重重,這也是其最重要的缺點,因此如何提升混合離散非線性規劃的枝界法的效率,也是重要的研究問題[Tseng et al., 1992]。然而每一個分枝節點所要解的子問題是非線性規劃的鬆弛問題,使得混合離散非線性規劃的枝界法在工程最佳化問題實際應用上還是十分困難。如果所處理的最佳化問題中,所有目標函數、限制條件都是外顯形式函數,每一個節點上的非線性規劃子問題自然可以用現成的非線性規劃演算法或電腦軟體解出,便沒有什麼問題。但如應用枝界法解有內隱式限制條件的工程最佳化問題時,解其中一個節點上的非線性規劃子問題便已經相當困難,遑論解一系列的有內隱式限制條件子問題了。

◇作業5

再次考慮先前討論過的三連桿結構最佳化問題,其最佳化模型如下式

        min. 

        s.t.   

               

但這裡假設市售標準桿件截面為正方形,且邊長須為由115整數,因此這個最佳化問題中多了一個離散集合的限制條件。試以混合離散非線性規劃的枝界法作幾次迭代,求此問題的離散最小值,並繪出類似圖4的步驟圖。◇

3.2 模擬退火法

模擬退火法是從所謂「統計力學(statistical mechanics)[Metropolis et. al, 1953]的觀念發展而來的。這個方法把最佳化問題求目標函數最小值時各變數的最佳值,比作尋找物質基本狀態(或者說是最低能量狀態)組成形態的過程。通常來說,從高溫急速“淬火”並不能得到這個狀態,而是必須將物質由高溫緩緩“退火”。而在退火過程中每一個溫度都必須保持一段足夠的時間,才能使物質晶粒有足夠時間找到其最低能量的組合形態。

一般最佳化演算法在搜尋過程中,不斷在尋找使目標函數降低的可行解,而模擬退火法則主張,如果在迭代過程中只接受使目標函數降低的可行解,就好比快速淬火的過程,容易困在區域最小值之中。要從區域最小值中脫出,找到整體最小值,迭代過程中必須容許“上坡”,也就是使目標函數些微上升的可行解。

Metropolis根據這些觀念設計了一套模擬退火的數值最佳化演算法,一般也就叫作Metropolis演算法。對於離散式變數問題來說,這套演算法可分為五個步驟[Kincaid and Padula, 1990]

步驟一:

選擇一個初始“溫度”,這個溫度對最佳化問題來說其實就是期望的目標函數最小值。初始溫度不應設得太低,如同退火過程一般,我們希望這個溫度緩緩降低,而在降低過程中每一個溫度都能得到足夠搜尋。另外並選擇一個初始可行設計點,設i=1j=1

步驟二:

在初始可行設計點的周圍尋找一個新的可行設計點,並計算其目標函數值

步驟三:

如果,目標函數有下降,便可取代成為現有最佳可行設計點,直接進入步驟四。如果,模擬退火法中便必須判斷是否接受這個設計點。此時計算下式

                                                                                     (17)

並且產生一個[0, 1]之間的亂數z,如果,則接受這個設計點,進入步驟四。注意在這個步驟中,如果越小,那麼的函數值越大,也就是這個上坡設計點被接受的可能性越大,而溫度越小,那麼的函數值越小,這個上坡設計點被接受的可能性也越小。

步驟四:

i=i+1,如果此時i已經大於一個預設值,表示在“退火”過程中此溫度停留夠久,便可進入步驟五,否則回到步驟二。

步驟五:

進一步降低溫度,設,把溫度進一步降低,如果小於一預設最低溫度值,則整個演算法停止,否則回到步驟二。

注意在溫度較高時,式(17)的函數值較大,上升的設計點被接受的可能性較大,以充分搜尋跳出區域最小值的機會,而隨著溫度逐漸下降,上升的設計點被接受的可能性逐漸變小,演算法也漸漸穩定下來。

模擬退火法最直覺可能發生的問題,是其必須去評估非常多的設計點,在某些工程最佳化問題應用上可能相當困難,不過前面提到枝界法類型的搜尋方法,基本上也仍然是計算成本極高的竭盡搜尋法,反而在一些研究文獻中,模擬退火法在結構最佳化的應用得到不錯的結果[Kincaid and Padula, 1990, Balling, 1991, May and Balling, 1992]

3.3 序列線性化方法

先前介紹過許多序列近似法解非線性規劃的問題,其中一種在工程最佳化問題上的應用相當受歡迎的方法,是所謂序列線性規劃法。這個方法在每一次迭代中,將目標函數、限制條件都在現在的設計點予以線性化,而去解一個線性規劃的子問題。序列線性規劃法延伸應用到混合離散非線性規劃問題,便成了序列離散線性規劃法,也就是說每一次迭代中所要解的線性規劃子問題,加上了離散集合限制條件,而成為整數規劃子問題或二元變數問題。

序列線性化方法之所以在工程問題的應用上受到歡迎,主要是因為其原理簡單,且每一次迭代中所要解的子問題,都是簡單的、外顯形式的線性規劃或整數規劃問題,可以用現成的數值演算法或最佳化電腦軟體解出,在離散式變數問題上,這一類演算法也很普遍[Duran and Grossman, 1986, Kocsis and Grossman, 1987, Loh and Papalambros, 1991]

然而序列線性規劃法有移動限制決定困難,迭代過程收斂性不穩定等缺點,最佳化理論專家一般並不推薦使用這個方法。這些缺點在擴展到序列整數規劃法時更為顯著,首先是移動限制很可能和離散集合限制條件發生衝突,如移動限制小於目前設計點和離散集合中相鄰離散值的差時,目前的設計點即使不是最佳點也無法作任何移動。OlsonVanserplaats[1989]建議使用目前設計點的離散值「截短集合(truncated set)」來限制下次迭代設計變數的位置,也就是限制下次迭代所得的變數值,僅能移動到目前設計點的前一個或後一個離散值,然而還是必須定義某一種形式的移動限制,以免迭代過程中設計點移動到不可行區域而造成發散。

◇作業6

以序列線性化方法,對作業5的三桿件問題做幾次迭代,嘗試求其最小值,並與作業5的結果做一比較。◇

3.4 懲罰函數法

先前介紹過解非線性規劃問題的懲罰函數法的觀念,也可以應用在混合離散非線性規劃問題中。然而這裡除了一般對違反限制條件的懲罰函數外,還必須為離散變數如果不等於特定離散值時定義懲罰函數,使得在演算過程中為了降低懲罰函數值,設計變數能自然趨近到特定的離散值。例如Shin等人為離散變數定義的懲罰函數如下[1990]

                                                  (18)

其中為變數所屬於的離散集合中的兩個值,。式(18)中當時,懲罰函數,當時,,當變數等於其他數值時,懲罰函數則均為正值。

定義懲罰函數時很重要的一點,是注意其是否會造成數值問題,懲罰函數必須至少有一次微分連續性。另外在有內隱式限制條件的工程最佳化問題中,懲罰函數法每次迭代所要解的子問題都十分困難,應用上並不合適。

3.5 拉氏鬆弛法及基因演算法

所謂拉氏鬆弛法基本上也是枝界法的一種,但在每個分枝節點上的子問題是去求其拉氏函數(Lagrangian)的最小值,也就是在每個分枝節點上所解的問題是一個「拉氏鬆弛問題(Lagrangian relaxation)」。這個方法最早是為了解線性的整數規劃問題而發展[Geoffrion, 1974]’80年代初期被修改應用在混合離散非線性規劃問題上,其後並有許多研究文獻發表此法在結構最佳化上的應用[Ringertz, 1988, Grierson and Cameron, 1989, Johnson and Larsson, 1990, Bauer, 1992]

「基因演算法(genetic algorithm)」和模擬退火法類似,都是由統計的觀念發展出來的方法。基因演算法的基本概念,是從達耳文物競天擇、適者生存的生物進化論發展而來的。在這個方法中一個設計點可用一個二元字串來表示,這個二元字串就好比生物的基因DNA。起始時先亂數產生一整組人口(population)不同的設計點,表達這些設計點的基因便可經由「複製(reproduction)」、「交配(crossover)」、「突變(mutation)」等程序,產生下一代。而在產生下一代的過程中,最合適的基因組合(如可行且目標函數小者)會被加強,而不合適的基因組合則會被淘汰。如此經過許多代演化,剩下的基因組合應該都是較佳的設計。

基因演算法在設計點的表示方法上十分適合離散變數的問題,且這是一個零次方法,只需要函數值,不需要函數的一次微分。但和模擬退火法相同,基因演算法在工程問題應用上可能會碰到的困難,是其需要評估的設計點數目太多。基因演算法的發展歷史尚短,但近幾年也有不少基因演算法在工程應用上的研究成果發表(Goldberg and Kuo, 1987, Hajela, 1989, Lin and Hajela, 1992)

參考資料

Belegubdu, A. D., and Arora, J. S., 1979. “Discrete Variable Optimization in Structural Engineering: A Survey.” Technical Report No. 49, Materials Engineering, The University of Iowa.

Hillier, F. S., and Lieberman, G. J., 1990. Introduction to Operation Research, McGraw-Hill, New York.

Arora, J. S., Huang, M. W., and Hsieh, C. C., 1994. “Methods for Optimization of Nonlinear Problems with Discrete Variables: A Review.” Structural Optimization, Vol. 8, pp. 69-85.

Tseng, C. H., Wang, L. W., and Ling, S. F., 1992. “A Numerical Study of the Branch-and-Bound Method in Structural Optimization.” Technical Report, Department of Mechanical Engineering, National Chiao Tung University, Taiwan.

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E., 1953. “Equations of State Calculations by Fast Computing Machines.” Journal of Chemical Physics, Vol. 21, pp. 1087-1092.

Kincaid, R. K., and Padula, S. L., 1990. “Minimizing Distortion and Internal Forces in Truss Structure by Simulated Annealing.” Proceedings, 31st AIAA/ASME/ASCE/AHS/ASC Structures, Structural Materials and Dynamics Conference, held in Long Beach, California, Paper No. AIAA-90-1095-CP, pp. 327-333.

Balling, R. J., 1991. “Optimal Steel Frame Design by Simulated Annealing.” Journal of Structural Engineering, Vol. 117, pp. 1780-1795.

May, S. A., and Balling, R. J., 1992. “A Filtered Simulated Annealing Strategy for Discrete Optimization of 3D Steel Frameworks.” Structural Optimization, Vol. 4, pp.142-148.

Duran, M. A., and Grossman, I. E., 1986. “An Outer Approximation Algorithm for a Class Mixed Integer Nonlinear Programs.” Mathematical Programming, Vol. 36, p. 307-339.

Kocsis, G. R., and Grossman, I. E., 1987. “Relaxation Strategy for the Structural Optimization of Process Flowsheets.” Industrial Engineering and Chemical Research, Vol. 26, No. 9, pp. 1-10.

Loh, H. T., and Papalambros, P. Y., 1991. “A Sequential Linearization Approach for Solving Mixed-Discrete Nonlinear Design Optimization.” ASME Journal of Mechanical Design, Vol. 113, pp. 325-334.

Olsen, G. R., and Vanderplaats, G. N., 1989. “Method for Nonlinear Optimization with Discrete Design Variables”, AIAA Journal, Vol. 27, No. 11, pp. 1584-1589.

Shin, D. D. K., Gurdal, Z., and Griffin, O. H. Jr., 1990. “A Penalty Approach for Nonlinear Optimization with Discrete Variables.” International Journal of Numerical Methods in Engineering, Vol. 23, pp. 1111-1130.

Geoffrion, A. M., 1974. “Lagrangian Relaxation for Integer Programming.” Mathematical Programming Study, Vol. 10, pp. 237-260.

Ringertz, U. T., 1988. “On Methods for Discrete Structural Optimization.” Engineering Optimization, Vol. 13, pp. 47-64.

Grierson, D. E., and Cameron, G. E., 1989. “Microcomputer-based Optimization of Steel Structure in Professional Practice.” Microcomputers in Civil Engineering, Vol. 4, No. 4, pp. 289-296.

Johnson O., and Larsson, T., 1990. “Lagrangian Relaxation and Subgradient Optimization Applied to Optimal Design with Discrete Sizing.” Engineering Optimization, Vol. 16, pp. 221-233.

Bauer, J., 1992. “Algorithms of Nondifferentiable Optimization in Discrete Optimum Structural Design.” ZAMM, Vol. 72, pp. 563-566.

Goldberg, D. E., and Kuo, C. H., 1987. “Genetic Algorithms in Pipeline Optimization.” Journal of Computing in Civil Engineering, Vol. 1, pp. 128-141.

Hajela, P. 1989. “Genetic Search -- An Approach to the Nonconvex Optimization Problems.” Proceedings, 30th AIAA/ASME/ASCE/ASHS Structures, Structural Materials and Dynamics Conference, held in Mobile, Alabama, pp. 165-175.

Lin, C. Y., and Hajela, P., 1992. “Genetic Algorithms in Optimization Problems with Discrete and Integer Design Variables.” Engineering Optimization, Vol. 19, pp. 309-327.