現(xiàn)代優(yōu)化算法學(xué)習(xí)心得(正式).doc

現(xiàn)代優(yōu)化算法學(xué)習(xí)心得年級：2009級工程碩士 姓名：龔強 學(xué)號：G0843011200091090102在科技高度發(fā)展的今天，計算機在人們之中的作用越來越突出。在這個學(xué)期里，我專門學(xué)習(xí)了現(xiàn)代優(yōu)化算法?，F(xiàn)代優(yōu)化算法包括禁忌搜索（tabu search）、模擬退火（simu-lated annclaing)、遺傳算法（genetic algorithms）、神經(jīng)網(wǎng)絡(luò)(neural networks)、拉格朗日松弛等算法。這些算法涉及生物進化、人工智能、數(shù)學(xué)和物理科學(xué)、神經(jīng)系統(tǒng)和統(tǒng)計力學(xué)等概念，都是以一定的直觀基礎(chǔ)而構(gòu)成的算法，我們稱之為啟發(fā)算法。啟發(fā)算法的興起于計算復(fù)雜性理論的形式有密切的聯(lián)系，當人們不滿足常規(guī)算法求解復(fù)雜問題時，現(xiàn)代優(yōu)化算法開始體現(xiàn)其作用。我在這里就以禁忌搜索這種算法來談?wù)劕F(xiàn)代優(yōu)化算法在計算復(fù)雜性理論問題時所體現(xiàn)的優(yōu)越性。禁忌搜索(rabu scarch)算法是局部鄰域搜運算法的推廣，是人工智能在組合優(yōu)化算法中的一個成功應(yīng)用。Glover 在1986年首次提出這一概念，進而形成一套完整算法，詳見文獻2，3。禁忌搜索算法的特點是采用了禁忌技術(shù)。所謂禁忌就是禁止重復(fù)前面的工作。為了回避局部鄰域搜索陷入局部最優(yōu)的主要不足，禁忌搜索算法用一個禁忌表記錄下已達到過的局部最優(yōu)點，在下一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點，以此來跳出局部最優(yōu)點。禁忌搜索算法是一種人工智能的算法，因此，從以下方面來談?wù)劷伤阉魉惴ā?局部搜索除特別強調(diào)外，我們都假設(shè)算法用以解決如下組合最優(yōu)化問題：其中為目標數(shù)，g（x）為約束方程，D為定義域。因為禁忌搜索算法中用到局部搜索算法，我們首先介紹局部搜索算法。該算法可以簡單的表示為：局部搜索算法STEP1 選下一個初始可行解x0；記錄當前最優(yōu)解xbest：= x0，令P=N（xbest）；STEP2 當P=時，或滿足其他停止運算準則時，輸出計算結(jié)果，停止運算；否則，從N（xbest）中選一集合S，得到S中的最優(yōu)解 xbest；若xbestxbest，則xbest：=xnow，P：= N（xbest）；否則，P：=P-S；重復(fù)STEP2。 在局部搜索算法中，STEP1的初始可行解選擇可以采用隨機的方法，也可用一些經(jīng)驗的方法或是其他算法所得到的解。STEP2中的集合S選取可以大到是N（xbest）本身，也可以小到只有一個元素，如用隨機的方法在N（xbest）中選一點，從直觀可以看出，S選取得小將使每一步的計算量減少，但可比較的范圍很?。籗選取大時每一步計算時間增加，比較的范圍自然增加，這兩種情況的應(yīng)用效果依賴于實際問題。在STEP2中，其他停止準則是除STEP2的P=以外的其他準則。這些準則的給出往往取決于人們對算法的計算時間、計算結(jié)果的要求，通過下面的例子來理解局部搜索算法。例21 5個城市的對稱TSP數(shù)據(jù)如圖2.1對應(yīng)的距離矩陣為 初始解為xbest=（ABCDE），f（xbest）=45。在本例中，鄰域映射定義為對換兩個城市位置的2-OPT，選定A城市為起點，我們用兩種情況解釋局部搜索算法。情況1 全部域搜運，即S=- N（xbest）。此時，P= N（xbest）S為空集，于是所得解為（ADCBE），目標值為43。情況2 一步隨機搜索xbest=（ABCDE），f xbest=45第一循環(huán)：由于采用N（xbest）中的一步隨機搜索，可以不再計算N（xbest）中每一點的值，若從中隨機選一點，如xnow=（ACBDE）。因f（xbest）=4345，所以xbest：=（ACBDE）。第二循環(huán)：若從N（xbest）中又隨機選一點xnow=（ACBDE），f（xnow）=4443。P= N（xbest）-xnow，最后得到的解為（ACBDE）。局部搜索算法的優(yōu)點是簡單易行，容易理解，但其缺點是無法保證全局最優(yōu)性。2.禁忌搜索禁忌搜索是一種人工智能算法，是局部搜索算法的擴展，它的一個重要思想是標記已得到的局部最優(yōu)解，并在進一步的選代中避開這些局部最優(yōu)解，如何避開和記憶這些點是本章主要討論的問題，首先，用一個示例來理解禁忌搜索算法。例2.3（例2.2續(xù)）假設(shè)：初始解x0=（ABCD），鄰域映射為兩個城市位置對換，始終點都為A城市，目標值為f（x0）-4，城市間的距離為：第1步：解的形式 禁忌對象及長度 候選集此處評價值為目標值，由天假設(shè)了A城市為起終點，故候選集中最多有兩兩城市對換對3個。分別對換城市順序并按目標值由小到大排列，三個評價值劣于原值，在原有的局部搜索算法中，此時已達到局部最優(yōu)解而停止，但現(xiàn)在，我們允許從候選集中選一個最好的對換CD城市的位置交換，用標記入選的對換，此時，解從（ABCD）變化為（ABDC），目標值上升，但此法可能跳出局部最優(yōu)。第2步：由于第1步中選擇了CD交換，于是，我們希望這樣的交換在下面的若干次迭代中不再出現(xiàn)，以避免計算中的循環(huán)，CD成為禁忌對象并限定在3次迭代計算中不允許CD或DC對換。在對應(yīng)位置記錄3，在N（x1）中又出現(xiàn)被禁忌的CD對換，故用T標記而不選此交換。在選擇最佳的候選對換后，到第3步。第3步：新選的BC對換被禁后，CD在被禁一次后還有二次禁忌，雖說候選集中的評價值都變壞，但為達到全局最優(yōu)，還是從中選取，由于BC和CD對換被禁，只有BD對換入選。第4步：此時，所有候選對換被禁，怎么辦？通過這一個示例，我們會產(chǎn)生如下問題：本例禁忌對象是對換，如BC對換造成ABCD到ACBD的變化，禁忌BC對換包括如下城市間順序的對換：ACBD到ABCD、ABCD到ACBD、ADBC到ADCB、ADCB到ADBC、ADBC到ACDB、ACDB到ABDC等的變化，若ACBD是剛才由ABCD變化而來的，結(jié)合解的變化，禁忌ACBD到ABCD和ABCD到ACDB的變化是可以接受的，但對其他變化的禁忌是否會影響求解的效率？如ADBC到ADCB是否允許？這一個問題說明禁忌對象是禁忌算法中一個基本的因素。禁忌的次數(shù)如何選??？若在例2.3中將禁忌次數(shù)從3更改為2，則有下列情形：例2.4第4步：第5步：再迭代一步，又回到狀態(tài)（ABCD），此時出現(xiàn)循環(huán)。由例2.3和例2.4的計算可以看出，禁忌搜索算法是局部搜索算法的變形，應(yīng)該注意到禁忌搜索算法計算中的關(guān)鍵點：禁忌對象、長度和候選集成為算法的主要特征，圍繞這些特征需要考慮下列因素。（1）是否有其他形式的候選集？上面的例子是將所有可對換的城市對作為候選集，再從候選集中沒有被禁的對換對中選最佳，對n個城市的TSP，這樣構(gòu)造候選集使得每個集中有C2n 1個交換對。為了節(jié)省每一步的計算時間，有可能只在鄰域中隨機選一些對換，而不一定是比較鄰域中的所有對換。（2）禁忌的長度如何確定？如果在算法中記憶下搜索到的當前最優(yōu)解，極端的兩種情況是：一是將所有的對換個數(shù)作為禁忌長度，此時等價于將候選集中的所有的對換遍歷；另外則取為1，這等價于局部搜索算法。（3）是否有評價值的其他替形式？上面例中用目標值作為評價值，有時計算目標值的工作量較大，或無法接受計算目標值所花費的時間，于是需要其他的方法。（4）被禁的對換能否再一次解禁？如在例2.3的第4步中，候選集中的交換都被禁忌，若此時停止，得到的解甚至不是一個局部最優(yōu)解，候選集中BD對換的評價值最小，是否不考慮對BD的禁忌而選擇這個對換？有這樣的直觀現(xiàn)象，當搜索到一個局部最優(yōu)解后，它鄰域中的其他狀態(tài)都被禁，我們是否解禁一些狀態(tài)以便跳出局部最優(yōu)？解禁的功能就是為了獲得更大的搜索范圍，以免陷入局部最優(yōu)。（5）如何利用更多的信息？在禁忌搜索算法中，還可記錄其他一些信息，如一個被禁對象（交換）被禁的次數(shù)，評價值變化的大小等，如果在例2.3中記憶同一個對換出現(xiàn)的此數(shù)，我們可以得到如下的一個有關(guān)禁忌對象的信息，其中，矩陣右上角記錄禁忌的長度，矩陣的左下角部分出現(xiàn)的數(shù)據(jù)表示對換被選為最佳的次數(shù)。B與C對應(yīng)5表示BC交換5次成為最佳候選。這些數(shù)字提供了狀態(tài)出現(xiàn)的頻率，反映解的一些性質(zhì)。（6）終止原則，即一個算法停止的條件，怎樣給出？綜合上面的討論，禁忌算法的特征由禁忌對象和長、候選集和評價函數(shù)、停止規(guī)則和一些計算信息組成，禁忌表特別指禁忌對象及其被禁的長度，禁忌對象是指變化的狀態(tài)，如上面例子中的兩個城市的對換，候選集中的元素依評價函數(shù)而確定，根據(jù)評價函數(shù)的規(guī)劃和其他一些特殊規(guī)則，在后續(xù)部分將介紹一個特殊規(guī)則特赦原則。計算中的一些信息，如被禁對象對應(yīng)的評價值、被禁的頻率等，對禁忌的長度和停止規(guī)劃提供幫助。禁忌搜索算法STEP1 選下一個初始解xnow及給以禁忌表H=；STEP2 若滿足停止規(guī)則，停止計算；否則，在xnow的鄰域N（H，xnow）中選出滿足禁忌要求的候選集Can-N（xnow）；在Can-N（xnow）中選一個評價值最佳的解xbext，xnow：= xbext，更新歷史記錄II，重復(fù)STEP2。 禁忌算法的STEP2中，xnow的鄰域N（H（xnow）中滿足禁忌要求的元素包含兩類：一類是那些沒有被禁忌的元素，另一類是可以被解除禁忌的元素，詳細的技術(shù)問題將在2.3節(jié)討論。比較局部搜索算法，蒙特卡羅算法和禁忌搜索算法，它們的主要區(qū)別是第二步對接受點選擇的原則不同。為了給出禁忌搜索算法的全局最優(yōu)定理，先介紹連通的概念。定義2.1 集合C稱為相對鄰域映射N：XC2c是連通的,若對C中的任意兩點X,Y,存在X=X1;X2X1=Y，使得N（x）（X1+1）；i=1，2,l-1。定理2.1（最優(yōu)定理）在禁忌搜運計算法中，若可行解區(qū)域相對Can-N（xnow）是連通的，且H的記錄充分大，則一定可以達到全局最優(yōu)解。證明非常直觀，雖說從理論上保證全局最優(yōu)，但若使得H的記錄充分大，也就是遍歷所有的狀態(tài)，這不是我們希望的，我們的期望是用更少的花費得到我們期望的解。3技術(shù)問題禁忌搜索算法是一種人工智能算法，因此，實現(xiàn)的技術(shù)問題是算法的關(guān)鍵，本節(jié)按禁忌對象、候選集合的構(gòu)成、評價函數(shù)的構(gòu)造、特赦規(guī)則、記憶頻率信息和終止規(guī)劃等分別給予介紹和討論。3.1禁忌對象、長度與候選集 禁忌表中的兩個主要指標是禁忌對象和禁忌長度，順名思義，禁忌對象指的是禁忌表中被禁的那些變化元素，因為首先需要了解狀態(tài)是怎樣變化的，我們將狀態(tài)的變化分為解的簡單變化，解向量分量的變化和目標值變化三種情況，在這三種變化的基礎(chǔ)上，討論禁忌對象，本小節(jié)同時介紹禁忌長度和候選集確定的經(jīng)驗方法。 1、解和簡單變化這種變化最為簡單，假設(shè)x，yD，其中D為優(yōu)化問題的定義域，則簡單解變化為xy是從一個解變化到另一個解，這種變化在局部搜索算法中經(jīng)常采用，如例2.1第一循環(huán)中從（ABCDE）變化到（ACBDE），這種變化將問題的解看成變化最基本因素。2、向量分量的變化這種變化考慮的更為精細，以解向量的每一個分量為變化的最基本因素，僅以（ABCDE）變化到（ACBDE）為例，它的變化實際是由B和C的對換引起，但B和C對換可以引起更多解的簡單變化，如：（ABCDE）（ACBDE）（ABDCE）（ACDBE）（ACBED）（ABCED）等。設(shè)原有的解向量為（X1X1-1, X1+1Xn）,用數(shù)學(xué)表達式來描述向量分量的最基本變化為：（X1Xi 1, Xi ，X1+1Xn）（X1Xi 1, yi ，X1+1Xn）即只有第i個分量發(fā)生變化，向量的分量變化包含多個分量發(fā)生變化的情形。部分優(yōu)化問題的解可以用一個向量形式x-（X1，X2Xn）r0,1n表示。解與解之間的變化可以表示某些分量的變化，如用分量從X1=0變化為X1=1或從XK 變化為XK=0，或是兩者的結(jié)合，可以通過下面兩個例子理解。例2.5 例1.1的01背包問題的狀態(tài)變化是向量分量變化形式，如果每次只允許一個變量變化，即，N；xDN（x）y-Xi12n，則變化的變量只可能由Xj=0。例2.6 TSP問題采用例1.28R 2 opt位置交換規(guī)劃，以例2.2的四城市TSP數(shù)據(jù)為例，當一個解為（ABCD）時，兩個城市BD的交換可以理解為：用一個0，1n（n-1）的向量表示解，則（XAB=1；XBC=1，XCD=1，XDA=1）其他分量為零；分量的變化是：由XAB=1變化為XBB=0，；XBC=1變化為XBC=0；XCD=1變化為XCD=0；XDA=1變化為XDA=0，由XDA=0變化為XDA=1；由XAD=0變化為XAD=1，由XBC=0變化為XBC=1；由Xcb=0變化為Xcb=1, 由XDA=0變化為XBA=1,于是，一個2-opt交換共需8個分量發(fā)生變化，這種情況歸類于多個分量變化的結(jié)合。3、目標值變化在優(yōu)化問題的求解過程中，我們非常關(guān)心目標值是否發(fā)生變化，是否接近最優(yōu)目標值，這就產(chǎn)生一種觀察狀態(tài)變化的方式：觀察目標值或評價值的變化，就猶如等位線的道理一樣，把處在同一等位線的解視為相同，這種變化是考察。II（a）=xDf（X）=a其中，f（x）為目標函數(shù)，它的表面是兩個目標值的變化，即從ab，但隱含著兩個解集合的各種變化的可能。例2.7 考慮目標函數(shù)f（x）- x2的目標值從1變化到4，這里隱含著解空間中四個變化的可能以上三種狀態(tài)變化的情形，第一種的變化比較單一，而第二和第三種變化則隱含著多個解變化的可能，因此在選擇禁忌對象時，可以根據(jù)實際問題采用適當?shù)淖兓?禁忌對象的選取由上面關(guān)于狀態(tài)變化三種形式的討論，禁忌的對象就可以是上面的任何一種，現(xiàn)用示例來分別理解，第一種情況考慮解為簡單變化，當解從xy時，y可能是局部最優(yōu)解，為了避開局部最優(yōu)解，禁忌y這一個解再度出現(xiàn)，禁忌的規(guī)則是：當y的鄰域中有比它更優(yōu)的點時，則選擇更優(yōu)的解；當y為N（y）的局部最優(yōu)時，不再選y，而選擇比y較差的解。見例2.8禁忌對象為簡單的解變化，禁忌表H只記憶三個被禁的解，即禁忌長度為3，從2-opt鄰域N（II，xnow）中選出最佳的五個解組成候選集Can.N（xnow）；初始解xnow=xo=（ABCDE），（x0）=45由于H為空集，從候選集中選最好的一個。如果禁忌第2種變化，則觀察下例。例2.9（例2.8續(xù)）數(shù)據(jù)同例2.8H只記憶三對對換時，從2-opt鄰域N（H，xnow）- xnow中選出最佳的五個狀態(tài)對應(yīng)的交換對組成候選集Can.N（xnow），這一瞇不同于例 2.8，因為受禁的是交換對，因此不考虎沒有變化的xnow，初始解xnow= xo=（ABCDE），（x0）=45由于H為空集，從候選集中選最好的一個，它是B與C的對換構(gòu)成。前兩步計算同例2.8的前兩步相同，但第3步同例2.8的第3步不同，因為根據(jù)禁忌表中的條件，禁忌選取由(ABCED)經(jīng)BC對換后的解（ABCED）。由此看出禁忌對換的范圍要大于例2.8只對簡單解禁忌的范圍。例2.9的鄰域定義和禁忌決定了：當一對元素X和y被禁忌后，包含兩個元素的兩種對換X與Y交換和Y與X交換，如禁忌B和C對換后，禁忌C與B對換和B與C對換。禁忌C與B對換的出發(fā)點是：上一步已經(jīng)對換的兩個元素不能再對換回去，以免還原到原有的解，還以例2.9為例，假設(shè)在例2.9問題中，某一步得到解為（ABCDE），迭代一步得到xnow）=（ABCDE）時，此時，應(yīng)該考慮禁忌C與B的對換，否則，可能回到（ABCDE），禁忌B與C對換的出發(fā)點是：上一步已經(jīng)對B與C的對換進行了分析和評價，希望搜索有較大的遍歷性，因此，我們不再考慮B與C的對換，即禁忌這個對換。在有些情況下，更細地將一對元素X與Y對換分成X與Y對換和Y與X對換兩種情形，即考慮對換的方向，因此，我們可以考慮只禁忌一個方向的對換，如X與Y的對換或Y與X的對換。例2.10（例2.9續(xù)）以第三種目標值的變化情形來繼續(xù)觀察例2.9.II只記憶三組元素（解及其目標值），從2-otp鄰域N（II，xnow）中選出最佳的五個元素為候選集 Can.N（xnow）中選一個目標最佳的解xbest初始解xnow=xo=(ABCDE) （x0）=45由于函數(shù)值43受禁,選候選集中不受禁的最佳函數(shù)值44的狀態(tài).在此例中,采用禁忌目標值的方法所禁忌的范圍比例2.8和例2.9的受禁范圍更大,這在這一例中明顯地體現(xiàn).所謂禁忌就是禁止重復(fù)前面達到局部最優(yōu)的狀態(tài),由于計算過程中解的狀態(tài)在不斷地變化,因此我們對造成狀態(tài)的變化的對象進行禁忌,上面已經(jīng)討論,狀態(tài)變化的主要因素歸結(jié)一種形式,簡單的解的變化.針對三種不同的狀態(tài)變化方式,例2.8、例2.9和例2.10體現(xiàn)了禁忌搜索算法在計算中的不同，實際應(yīng)用中，應(yīng)根據(jù)具體問題采用一種方法，從上面示例的計算中也可以看出，解的簡單變化比解的分量變化和目標值變化的受禁忌范圍要小，這可能造成計算時間的增加，但它也給予了較大的搜索范圍。解分量的變化和目標值變化的禁忌范圍要大，這減少了計算的時間，可能引發(fā)的問題是禁忌的范圍太大以至陷在局部最優(yōu)點。由此可以得知，禁忌搜索算法中的技術(shù)很強，因為NP-hard問題不可能奢望計算得到最優(yōu)解，在算法的構(gòu)造和計算的過程中，一方面要求盡量少的占用機器內(nèi)存，這就要求禁忌長度、候選集合盡量小，正好相反，禁忌長度過短造成搜索的循環(huán)，候選集合過小造成過早地陷入局部最優(yōu)。5、禁忌長度的確定禁忌長度是被禁對象不允許選取的迭代次數(shù)，一般是給被禁對象X一個數(shù)（禁忌長度）t，要求對象X在t步迭代內(nèi)被禁，在禁忌表中采用tabu（X）=t記憶，每迭代一步，該項指標做運算tabu（X）=t-1，直到tabu（X）=0時解禁。于是，我們可將所有元素分成兩類，被禁元素和自由元素，有關(guān)禁忌長度t的選取，可以歸納為下面幾種情況：（1）t為常數(shù),如t=10,t=,其中n為鄰居的個數(shù),這種規(guī)則容易在算法中實現(xiàn).(2)ttmin, tmix,此時t是可以變化的數(shù),它的變化是依據(jù)被禁對象的目標值和鄰域的結(jié)構(gòu),此時tmin, tmix是確定的,確定tmin, tmix的常用方法是根據(jù)問題的規(guī)模T,限定變化區(qū)間a,(0a，也可用鄰域中鄰居的個數(shù)n確定變化區(qū)間a， (0a)當給定了變化區(qū)間,確定t的大小主要依據(jù)實際問題、實驗和設(shè)計者的經(jīng)驗，如從直觀可見，當函數(shù)值下降較大時，可能谷較深，欲跳出局部最優(yōu)，希望被禁的長度較大。（3）tmin, tmix的動態(tài)選取，有的情況下，用tmin, tmix的變化能達到更好的解，它的基本思想同（2）類似。禁忌長度的選取同實際問題、實驗和設(shè)計者的經(jīng)驗有緊密的聯(lián)系，同時它決定了計算的復(fù)雜性，過短會造成循環(huán)的出現(xiàn)，如f（1）-1，f（2）=3.5；f（3）=2.5，f（4）=2,f(5)=3，f（6）=6，極端情況禁忌長度是1，鄰域為相距不超過1的整數(shù)點，一旦陷入局部最優(yōu)點x=4，則出現(xiàn)循環(huán)而無法跳出局部最優(yōu)，過長又造成計算時間較長。上面（2）中給出的區(qū)間估計參數(shù)都是一些經(jīng)驗的估計。6、候選集合的確定候選集合由鄰域中的鄰居駔成，常規(guī)的方法是從鄰域中選擇若干個目標值或評價值最佳的鄰居人選，如上面的TSP中采用2opt鄰域定義，一個狀態(tài)的鄰域中菜有C2n個鄰居，計算目標值后，例2.8、例2.9和例2.10選 擇五個目標值最佳的鄰居人選。 有時認為上面的計算量還是太大，則不在鄰域中所有鄰居中選擇，而是在鄰域中的一部分中選擇若干個目值或評價值最佳的狀態(tài)入選。也可以用隨機選取的方法實現(xiàn)部分鄰居的選取。3.2評價函數(shù)評價函數(shù)是候選集合元素選取的一個評價公式，候選集合的元素通過評價函數(shù)值來選取，以目標函數(shù)作為評價函數(shù)是比較容易理解的。目標值是一個非常直觀的指標，但有時為了方便或易于理解，會采用其他函數(shù)來取代目標函數(shù)，我們將評價函數(shù)分為基于目標函數(shù)和其他方法兩類。1、基于目標函數(shù)的評價函數(shù)這一類主要包含以目標函數(shù)的運算所得到的評價方法，如記評價函數(shù)為p（x）目標函數(shù)為f（x），則評價函數(shù)可以采用目標函數(shù)P（x）=f（x）目標函數(shù)值與xnow目標值的差值P（x）=f（x）-（xnow）其中xnow是上一次迭代計算的解；目標函數(shù)值與當面最優(yōu)解xbest目標值的差值P（x）=f（x）-（xbest）其中xbest是目前計算中的最好解。基于目標函數(shù)的評價函數(shù)的形成主要通過對目標數(shù)進行簡單的運算，它的變形很多。2、其他方法有時計算目標值比較復(fù)雜或耗時較多，解決這一問題的方法之一是采用替代的評價函數(shù)，替代的評價函數(shù)還應(yīng)該反映原目標函數(shù)的一些特征，如原目標函數(shù)對應(yīng)的最優(yōu)點還應(yīng)該是替代函數(shù)的最優(yōu)點。構(gòu)造替代函數(shù)的目標是減少計算的復(fù)雜性，具體問題的替代函數(shù)構(gòu)造依問題而定，它的一個例子是在生產(chǎn)計劃中的約束批量計劃與調(diào)度（Gapacitated lotsize planning and scheduling）模型中的應(yīng)用。例：2.11簡單的生產(chǎn)計劃批量問題，一個工廠安排n個產(chǎn)品在T個計劃時段里加工，其各個產(chǎn)品的需求量、加工費用和加工能力等之間的關(guān)系用下面數(shù)學(xué)模型（PP）描述。其中，Si表示生產(chǎn)i產(chǎn)品需耗的生產(chǎn)準備費用； Hi表示單位i產(chǎn)品需耗的庫存費用；Pi表示生產(chǎn)單位i產(chǎn)品需耗的費用；Xn表示第t時段，i產(chǎn)品的生產(chǎn)批量；Iit表示第t時段，i產(chǎn)品的庫存量；Dit表示第t時段，i產(chǎn)品的外部需求量；ai表示生產(chǎn)單位i產(chǎn)品需耗的資源量；Ct表示i時段能力的提供量；上面模型中Xn，Iit為決策變量，所有參數(shù)為非負值，目標（2.1）要求生產(chǎn)，生產(chǎn)準備有庫存費用三項費用和最小，（2.2）為外部需求、生產(chǎn)和庫存之間的平衡關(guān)系，（2.3）為資源約束，要求每個時段生產(chǎn)占用的能力不超過可提供的能力，PP模型是一個混合整數(shù)規(guī)劃問題，因為yit取0.1兩個值，當Yn=（yit）的值選定后，PP模型為一個線性規(guī)劃問題，對應(yīng)的最優(yōu)目標值為Z（Y0）。這樣，禁忌搜索算法可以只將（yit）看成決策變量進行計算求解，如果采用基于目標函數(shù)的評價函數(shù)方法，對應(yīng)每一個Yn-（yit）要解一個線性規(guī)劃問題，雖說線性規(guī)劃問題有多項式時間的最優(yōu)算法，但對每一個給定的Y0求解一次Z（Y0）還是很費時的，一個簡單位替代方法是對給定的Y0，用啟發(fā)式的算法求解PP，其本思想是根據(jù)Y0、Dit和Ct安排各時段的生產(chǎn)（可參見文獻4），最后得到一個啟發(fā)式算法的目標值ZH（Y0），以此為評價函數(shù)值。 求解的基本思想是：當沒有資源約束（2.3）時，PP模型存在一個最優(yōu)解滿足當增加（2.3）資源約束后，從最后一個時段T開始按資源約束逐個時段驗證解（2.5）是否滿足（2.3），當不滿足時，將超出資源約束的部分前移一個時段加工，如此修正，最后若第一個時段資源不足時，則認為無可行解，此時目標值記為充分大的一個數(shù)，若可行，則按修正后的解用（2.1）計算目標函數(shù)值，這個目標值作為評價值。例2.11用一個啟發(fā)式算法解的目標值替代最優(yōu)值，取代的主要原因是認為線性規(guī)劃算法的計算時間還是太長，如果計算目標值比較復(fù)雜或所發(fā)費的時間較長，可以用替代的方法，應(yīng)該注意的是替代函數(shù)應(yīng)盡可能地反映原目標函數(shù)的特性。3.3特赦規(guī)則在禁忌搜索算法的迭代過程中，會出現(xiàn)候選中的全部對象都被禁忌，或有一對象被禁，但若解禁則期目標值將有非常大的下降情況，在這樣的情況下，為了達到全局的最優(yōu)，我們會讓一些禁忌對象重新可選，這種方法稱為特赦，相應(yīng)的規(guī)劃稱為特赦規(guī)劃（aspiration criteria）.先用下面的例子理解特赦規(guī)則的應(yīng)用。例2.12五城市的TSP，其城市間的距離為：假設(shè)初始解為：（ACBDE），類似例2.3，經(jīng)過一步運算，得到一個解是（ABCDE），目標值為10，假設(shè)在計算的某一步，得到目前的一個解為（AEDBC）；f（AEDBC）=24，此時被禁的對換還包括BC，若交換BC，得目標值5；這個目標值好于前面的任何一個最佳候選解，有理由解禁BC對換，這是一種特赦規(guī)則。以下羅列三種常用的特赦規(guī)則，在下面的討論中，認為評價值越小越好。（1）基于評價值的規(guī)則，例2.12就是這樣的規(guī)劃，在整個計算過程中，記憶已出現(xiàn)的最好解xbext，當候選集中出現(xiàn)一個解xnow，其評價值（可能是目標值）滿足、c（xbext）c（xnow）時，雖說從xbext達到xnow的變化是被禁忌的，此時，解禁xnow使其自由，直觀理解，我們得到一個更好的解。（2）基于最小錯誤的規(guī)則，當候選集中所有的對象都被禁忌時，而（1）的規(guī)則又無法使程序繼續(xù)下去，為了得到更好的解，從候選集的所有元素中選一下評價值最小的狀態(tài)解禁。（3）基于影響力的規(guī)則，有些對象的變化對目標值的影響很大，而有的變化對目標值的變化較小，我們應(yīng)該關(guān)注影響大的變化。從這個角度理解，如果一個影響大的變化成為被禁對象，我們應(yīng)該使其自由，這樣才能得到問題的一個更好的解，需要注意的是，我們不能理解為：對象的變化對目標影響大就一定使得目標（或是評價值）變小，它只是一個影響力指標。這一規(guī)則應(yīng)結(jié)合禁忌長度和評價函數(shù)值使用。如在候選集中目標值都不及時當前的最好解，而一個禁忌對象的影響指標很高且很快將被解禁時，我們可以通過解禁這個狀態(tài)以期望得到更好的解，下面用0-1背包問題的一禁忌搜索算法理解影響力指標。例213 0-1背包問題的禁忌搜索算法解的形式為：X0,1X，鄰域定義為：這樣的鄰域定義要求每次最多只能有一個變量變化，從0變?yōu)?或是從1變?yōu)?，直觀理解是裝一個物品進去或是取一個物品出來。評價值選擇目標值，此時目標值越大越好，在計算的每一個迭代過程中，需要驗證能力的可行性，當所裝物品體積大于包的容積時為不可行解，其目標值定義為-K（K是一個充分大的整數(shù)，表示得到的解為不可行解）。除了目標值以外，一個有影響力的指標是物品的大小，取出一個體積大的物品可以裝時多個小的物品，裝進一個大的物品很快使包的容積變小。假設(shè)剛裝進一個大的物品，此時包正好裝滿，馬上取出是應(yīng)該禁忌的。如五個物品的0-1背包問題，它們的體積和價值ai，ci（i=1，2，3，4，5）分別為4，4、2，4、1，1，5、3，4、1，5，4，包的容積為6，假設(shè)計算過程中得到一個解為X1=Xf=1和X2= X3= X4=0；X1：10和X3：0解禁，這樣其他物品就有裝包的可能性。3.4記憶頻率信息計算的過程中，記憶一些信息對解決問題是有利的，如一個最好的目標值出現(xiàn)的頻率很高，這使我們有理由推測：現(xiàn)有參數(shù)的算法可能無法再得到更好的解，因為重復(fù)的次數(shù)過高，使我們認為可能出現(xiàn)了多次循環(huán)，根據(jù)解決問題的需要，我們可以記憶解集合、有序被禁對象組、目標值集合等的出現(xiàn)頻率，一般可以根據(jù)狀態(tài)的變化將頻率信息分為兩類：靜態(tài)和動態(tài)。靜態(tài)的頻率信息主要是某些變化，諸如解、對換或目標值在計算中出現(xiàn)的頻率，求解它們的頻率相對比較簡單，如可以記錄它們在計算中出現(xiàn)的次數(shù)，出現(xiàn)的次數(shù)與總的迭代數(shù)的比率，從一個狀態(tài)出發(fā)再回到該狀態(tài)的迭代次數(shù)等，這些信息有助于我們了解一些解、對換或目標值的重要性，是否出現(xiàn)循環(huán)和循環(huán)的次數(shù)，在禁忌搜索中，為了更充分的利用信息，一定要記憶目前最優(yōu)解。動態(tài)的頻率信息主要是從一個解、對換或目標值到另一個解、對換或目標值的變化趨勢，如記憶一個解序列的變化，或記一個解序列變化的若干個點等，由于記錄比較復(fù)雜，因此，它提供的信息量也較大，在計算動態(tài)頻率時，通常采用的方法為：（1）一個序列的長度，即序列中元素個數(shù)，在記錄若干個關(guān)鍵點的序列中，按這些關(guān)鍵點的序列長度的變化的進行計算；（2）從序列中后個元素出發(fā)，再回到該序列該元素的迭代次數(shù)；（3）一個序列的平均目標（評價）值，從序列中一個元素到另一個元素目標（評價）值的變化情況；（4）該序列出現(xiàn)的頻率頻率信息有助于進一步加強禁忌搜索的效率，我們可以根據(jù)頻率信息動態(tài)控制禁忌的長度，當一個元素或一個序列重復(fù)出現(xiàn)，我們可以增加禁忌長度以避開循環(huán)，當一個序列的目標（評價）值變化較小時，有必要增加該序列每一個對象的禁忌長度，反之，減少每一個對象的禁忌長度，一個最佳的目標值出現(xiàn)的頻率很高，有理由終止計算而將一值認為是最優(yōu)值。3.5終止規(guī)則無論如何，禁忌搜索算法是一個啟發(fā)式算法，我們不可能讓禁忌長度充分大，只希望在可接受的時間里給出一個滿意的解，于是很多直觀、易干燥的原則包含在終止規(guī)則中，下面給出常用的終止規(guī)則；（1）確定步數(shù)終止，給定一個充分大的數(shù)N，總的迭代次數(shù)不超過N步，即使算法中包含其他的終止原則，算法的總迭代次數(shù)有保證，這種原則的優(yōu)點是易于操作和可控計算時間，但無法保證解的效果，在采用這個規(guī)則時，應(yīng)記錄當前最優(yōu)解。（2）頻率控制原則，當某一個解、目標值或元素序列的頻率超過一個給定的標準時，如果算法不做改進，只會造成頻率的增加，此時的循環(huán)對解的改進已無作用，因此，終止計算，這一規(guī)則認為；如果不改進算法，解不會再改進。（3）目標值變化控制原則，在禁忌搜索算法中，提倡記憶當前最優(yōu)解，如果在一個給定的步數(shù)內(nèi)，目標值沒有改變，同（2）相同的觀點，如果算法沒有其他改進，解不會改進，此時，停止運算。（4）目標值偏離程度原則，對一些問題可以簡單地計算出它們的下界（目標為極?。?，我們在第6章將介紹一種求解下界的拉格朗日（Lagrange）松馳算法，記一個問題的下界為ZLB，目標值為f（x）對給定的充分小的正數(shù)，當f（x）- ZLB時，終止計算，這表示目前計算得到的解與最優(yōu)值很接近。4.應(yīng)用實例本節(jié)介紹兩個應(yīng)用實例，一個是比較簡單的圖節(jié)點著色(nodccoloring)問題，另一個是車間作業(yè)調(diào)度，也稱為車間作業(yè)排序問題，從兩個實例中可以了解禁忌搜索算法應(yīng)用的一些理論和技術(shù)問題。4.1圖節(jié)點著色問題給定一個無向圖G=（V，E），其中V是節(jié)點集V=1，2n，E是邊集，表示有連接i，J的一個邊，若內(nèi)部的任何兩個節(jié)點沒有E中的邊直接相連，則稱（V1，V2Vk）為V的一個劃分，圖的節(jié)點著色問題可以描述為：求一個最小的K，使得（V1，V2Vk）為V的一個劃分。例：2.14 如圖2.3所示的五節(jié)點無向圖G=（V，E），它的一個劃分是：V3=C，當然V1=A；V2=B，V3=C， V4=D，E也是一個劃分。對給定n個節(jié)點的無向圖，禁忌搜算法求解圖節(jié)點覆蓋問題可以分為兩步，第一步是給定一個常數(shù)k，考慮目標函數(shù)。其中ij表示第j節(jié)點在ij集合中。解的第X個分量變化為：即還原到有狀態(tài)，這種禁忌考慮了變化的方向。每一個解S的鄰域由那些滿足上面的變化且只有一個分量變化的解組成，共有nk個鄰居（包含自身），每一個節(jié)點（分量）可以選擇k個劃分集之一。禁忌：即還原到原有狀態(tài)，這種禁忌考慮了變化的方向。特赦規(guī)則：若xn是當前最優(yōu)解，當一個受禁的鄰居X滿足f（x）f（xn）-1時，則受禁的變化特赦。因為目標值為非負整數(shù)，條件f（x）f（xn）-1表示X的目標值小于當前最優(yōu)解xn的目標值，本例采用基于評價值的特赦規(guī)則（1）。Herrx和Werra5在集合的劃分數(shù)給定的情況下，給出的程序框架如下 已知劃分集合數(shù)K，解的形式S，目標函數(shù)f，解的變化，鄰域映射N（s），禁忌長度，目標值下界f*，兩個目標值沒有改進的最大允許迭代次數(shù)nbmax開始。任選一個初始解；nbiter;=0(*當前的迭代步*)bestiter:=0;(*當前最優(yōu)解所在的迭代步*)bestsol；=S（*當前的最優(yōu)解*）令Z=f（s） A（z）=Z-1（特赦值）初始化禁忌表H：繼續(xù)結(jié)束。輸出：計算中的最優(yōu)解。 在文獻5中，隨機產(chǎn)生實例的參數(shù)為：無向圖共有1000個節(jié)點，邊集的密度是50%（大約是C21000/2個邊），禁忌表長度H=7，候選解個數(shù)V*=-V/2。最終對上面規(guī)模實例的計算結(jié)算是平均可用87種顏色劃分，概率分析的理論結(jié)果是85種顏色。4.2 車間作業(yè)調(diào)度問題1、問題的描述車間作業(yè)調(diào)度（job shop scheduling）問題可以簡單地描述為n個工件（job）（這是一個統(tǒng)稱），J1，J2，Jn，在m臺機器（machine（也是統(tǒng)稱）M1，M2，MN上加工。每一個工作Ji有nI個工序（opertion），O1，O2，ON，第ON工序的加工時間為P1J必須按工序進行加工且每一工序必須一次加工完成（無搶占，noorccmption）。一臺機器在任何時刻最多只能加工一個產(chǎn)品，一個工件不能同時在兩臺機器上加工，如何在上面的條件下使最后一個完工的工件完工時間最短？車間作業(yè)問題可以用析取圖（disjunctivc graph ）表示：在圖2.4中，S和E是虛擬的起終點，實線弧表示兩個工序的前后關(guān)系，這是不允許改變的，每一行表示一個工件的所有工序。虛線邊暫時是沒有方向的。一個虛線邊表示連接的節(jié)點（工序）在同一臺機器上加工，如O11，O22的連接線表示它倆在同一臺機器上加工，車間作業(yè)的一個調(diào)度是給予所有虛線邊一個方向，成為一個虛線弧，一個虛線弧所指方向表示加工遵照的順序，尋找車間作業(yè)調(diào)度問題的一個可行解就是在圖2.4中給虛線邊賦方向。使其成為一個有向且無圈的圖。車間作業(yè)調(diào)度問題在兩個工作時是存在多項式時間的最優(yōu)算法，參考文獻6，但當工作數(shù)超過2時，問題的復(fù)雜性是NP-hard證明見文獻7。非常直觀，問題的一個解對應(yīng)m臺機器上的一個加工排序。在應(yīng)用禁忌搜索之前，由于車間作業(yè)的鄰域構(gòu)造有較強的代表性，我們首先考慮問題的鄰域構(gòu)造，第一種方法是選一臺機器上的兩個工序交換位置加工，如一臺機器上原有的加工序為（a，b，c，d，e，交換ac序后，新的加工序為（c，b，a，d，e。這樣的鄰域映射使得一個解有個鄰居。進一步推廣上面的方法，可以使得若干個位置交換，一種特殊的情況是將一個工序移到另一個位置加工，如在一臺機器上原有的加工序是（abcdef）,現(xiàn)將f移到第一個位置加工，則加工序為（fabcde），這些是我們常見的方法。第二種方法是關(guān)鍵路（crirical path）法。這種方法所依賴的一個基本思想是：在第一種方法中，一些交換對目標值沒有影響，這些交換浪費計算時間，應(yīng)抓住最長的、加工中沒有時間空閑的一條路（即關(guān)鍵路），交換同在這條路上且同在一臺機器上加工的兩個加工工件的位置。2、關(guān)鍵路的理論例215 三個工件在兩臺機器上加工的車間作業(yè)問題，其加工如圖2.5。關(guān)鍵路是：O11O22O32長度為14，以較粗的線標記在圖2.5上，從圖2.6可以看出，交換O3，O22的加工位置對最長完工時間沒有影響，但交換關(guān)鍵路上的一個工件，如O11O31交換，則如圖2.7關(guān)鍵路是：O31O11O12O32，長度為18，由此可以看到，關(guān)鍵路上的加工工件的位置改變對目標值有直接影響。定義2.2 在關(guān)鍵路上，滿足下列條件的相鄰節(jié)點集為塊（block）：（1）由關(guān)鍵路上的相鄰節(jié)點組成，至少包含兩個工序；（2）集合中的所有工序在一臺機器上加工；（3）增加一個工序后，不滿足（1）或（2）。定理2.2 若一解的關(guān)鍵路不包含塊，則一定是最優(yōu)解。證明 由定理的條件，關(guān)鍵路上不包含塊，由圖2.4，同一臺機器的相鄰工序由虛線相連，由此可知，任意相鄰兩個工序由一條實線連接，這條關(guān)鍵路長度某一個工件的所有工序加工時間和，是車間作業(yè)完工時間的一個下界，因此定理結(jié)論成立。若Y是車間作業(yè)的一個可行解，則對應(yīng)Y，圖2.4為一個有向無圈圖，若Y和Y是作業(yè)調(diào)度的兩個可行解，且Y和Y對應(yīng)的有向圈S和S,當圖S的關(guān)鍵路P的長度小于圖S的關(guān)鍵路P的長度時，稱可行解Y改進了Y。定理2.3 若Y和Y是車間作業(yè)調(diào)度的兩個可行解，且Y和Y對應(yīng)的有向圖為S和S，若Y改進Y，則一定滿足下面的