1 前言
三維裝箱問題（Three Dimensional Container Loading Poblem）指在滿足容積限制、外形幾何限制和穩定性限制等條件的情況下，把一定數量體積較小的物品放入具有較大容量的一個或多個箱子，達到所用箱子數量最少、空間使用率最高、穩定性最好、裝載價值最高、容重比最高等目的組合優化的問題。三維裝箱問題廣泛存在于運輸和包裝等行業的物資裝載過程中，是以，如何針對實際應用需求設計具有較高操作性和裝載效率的三維裝箱求解算法，對于提高社會經濟效益具有積極作用。
自20世紀60年代開始，三維裝箱問題便因切割庫存問題而提出，引起了學者關注，并被證明是具有較高複雜度的NP難問題。經過多年發展，三維裝箱問題的求解不僅在枚舉法、分支定界法等确定性算法上取得了進步。随着元啟發式算法、遺傳算法、粒子群算法等現代啟發式算法的崛起，三維裝箱問題的研究更加深入，逐漸出現了帶有多種現實限制和求解目标的複雜算法。其中，近年來具有代表性的相關研究如下所述。
Lodi等[9]受到一維裝箱問題求解算法的啟發，針對三維裝箱問題提出了基于“先高後面積”（Height First-Area Second）的分層政策的結構式禁忌搜尋算法，實驗證明算法在分層堆放的情況下能得到較好的結果。Crainic等考慮了裝載盒子時箱子剩餘空間的描述和備標明位點的重要作用，為尋找每次裝載時的合适空間位置和最優定位點，提出了極點（Extreme Points,EPS）的概念和計算方法，并設計了基于極點的三維裝箱啟發式算法。Karabulut[12]和Kang[13]等先後以規則長方體箱裝載最大量規則長方體盒為研究目标，在設計深度、底部和左部方向優先裝載（Deepest Bottom Left with Fill）物資裝載政策的基礎上，提出了基于遺傳算法的三維裝箱政策求解算法，2個研究的差別在于後者在前者的基礎上，對裝載剩餘空間進行了更為細緻的描述。Ramos等重點考慮了運輸行業貨物裝載時靜止時的縱向穩定性和行進時的橫向穩定性，并提出了具有較高操作性的穩定性評價名額和基于順序的貨物裝載啟發式算法。
盡管三維裝箱問題研究的深度和廣度在不斷延伸，相關研究的模型建立、算法設計和實際應用也取得了衆多成果，但是一些現實限制仍難以滿足，解決方法也存在較大的局限性。其中，現有求解三維裝箱問題較為常用的遺傳算法，在交叉算子設計、變異算子設計和進化性能等方面表現不足。
1 問題描述
1.1 基本問題描述
除球體、非規則立方體等形狀盒子的裝箱特例外，經典的三維裝箱問題（見圖1）可描述為：用一定數量的長寬高分别為Li,Wi和Hi的箱子（Container），按照一定順序和裝載規則根據不同轉向逐個裝入一定數量的長、寬、高分别為lj,wj和hj的盒子（Box）中，實作箱子容量的使用率最大、盒子堆放的穩定性最好、裝載價值最高或容重比最恰當等其一或多種目标，并滿足外形限制、容積限制、穩定性限制、盒子屬性相關性限制、載重限制等實際限制。
圖1 三維裝箱問題示意
根據文獻對三維裝箱問題的分類法，該研究以SBSBPP類（Single Bin-Size Bin Packing Problem，有限數量單類型箱體三維裝載問題）為研究對象，研究如何在單個規則長方體箱子中裝載盡量多的盒子（這些盒子具有相似度較小且分散較大的特點），以最大限度地提高箱子的空間使用率。此研究旨在解決每個盒子應以何種順序、何種方向放置在具體空間位置的問題，即提供具體的盒子裝載方案。此過程需滿足如下現實限制。
1）外形限制。進行裝載時，所有盒子的幾何頂點不能位于箱子之外，裝進箱子的盒子在空間上不能發生重疊。
2）容積限制。裝載盒子的總體積不能超過箱子的容積。
3）穩定性限制。裝載盒子的堆放需滿足重心要求，不能出現懸空或重心偏移的情況。
基本假設：盒子品質均勻分布，其質心位于其幾何中心；不考慮盒子總品質超載的問題；盒子裝載時應與箱子的邊長方向平行（即不斜放）。
1.2 箱體最大剩餘空間描述
最大剩餘空間（Allowable Packing Area，簡寫為APA）指進行盒子裝載前的最大長方體形閑置空間，每個最大剩餘空間可用最靠近原點的長方體頂點三維坐标和最遠離原點的長方體頂點三維坐标合并表示，全部的最大剩餘空間即構成最大剩餘空間集（簡寫為APAs）。盒子的裝載是在箱子的最大剩餘空間中按照一定規則進行的，最大剩餘空間的刻畫關系到盒子的放置和空間容納能力，對于盒子的裝載至關重要。該研究采用文獻中的I-DBLF算法，完成最大剩餘空間的描述。每裝入一個箱子，其最大剩餘空間将按照盒子的邊界和x,y,z軸進行劃分和更新。如圖2a所示，空置箱子的最大剩餘空間隻有1個，表示為(0,0,0),(Li,Wi,Hi)；在臨原點位置裝入一個長、寬、高分别為lj,wj和hj的盒子後，最大剩餘空間更新為3個（見圖2b—d），最大剩餘空間集為{((Li-lj,0,0),(Li,Wi,Hi)),((0,0,Hi-hj),(Li,Wi,Hi)),((0,Wi-wj,0),(Li,Wi,Hi))}。最大剩餘空間的計算過程較為複雜，因篇幅所限，此處不做贅述，具體可見文獻。
圖2 剩餘空間示意
2 三維裝箱問題求解的改進遺傳算法設計
三維裝箱問題本身具有較高的抽象性和複雜度，特别是解的構造、剩餘空間更新、剩餘空間描述等裝載過程的模組化為精确求解方法帶來了較大難度。随着載重限制等限制條件和穩定性等求解目标的增加，分支定界和動态規劃等正常方法更是無法求解。以遺傳算法為代表的啟發式算法在解的構造和最優解的全局搜尋方面具有先天優勢。此外，遺傳算法通過模仿自然界物競天擇的進化機理，具有較高的自組織、自适應和自學習性。該研究以文獻]所提出的編碼方式和總體架構為基礎，提出基于優先保持政策的改進遺傳算法對三維裝箱問題進行求解，以期獲得更為優異的求解結果。
2.1 算法總體設計
基于優先保持政策改進遺傳算法的總體流程見圖3。需要說明的是，該算法以待裝載盒子的順序為算法的編碼方式，在解碼階段完成具體裝載順序和裝載方案的計算和生成。
圖3 基于優先保持政策遺傳算法總體流程
2.2 初始化
初始化是進行資料預處理、實作實際問題有效轉化（将對象資料轉化為遺傳算法能識别和直接使用的形式）并完成運作環境設定的過程，此算法的初始化過程主要包括初始種群生成和計算環境初始化。
其中，計算環境初始化主要完成包括廢棄變量和備援資料的清除、算法實驗資料（如箱子種類和數量、空間屬性及載品質屬性，盒子種類及數量、外形屬性及重點等資料）的讀入和算法基本參數（如疊代次數、種群數量、交叉和變異機率等）的設定，為遺傳算法的運作做好準備。
種群的初始化是在編碼政策的指導下完成合法初始種群的生成過程。編碼是将具體的求解問題轉化為遺傳算法能夠直接識别和操作的符号的過程，是遺傳算法的核心和關鍵步驟。該算法采用長度等于Nb+Nc（待裝載盒子數和箱子數之和）的自然數順序編碼，編碼分為前後2段，分别由代表盒子順序和箱子順序的順序串組成。如在一個裝載過程中，假設有7個待裝載的盒子和3個可用的箱子，則該編碼為自然數1—7和1—3分别随機排序組成的10位數編碼，如編碼（6 1 4 2 5 7 3 2 3 1）表示按照盒子6最優先、盒子1次優先…盒子3末優先的順序以一定規則（具體見“2.3解碼”）裝入箱子2，待達到體積、載品質或長寬高限制後，剩餘盒子裝入箱子3，以此類推。假設本遺傳算法的種群由p個個體組成，則文中算法的種群初始化結果應為p*(Nb+Nc)個自然數組成的二維數組。
需要說明的是，此研究雖然隻研究單個箱子的裝載最大化，但編碼中多個箱子的考量可為研究的大幅拓展和内容豐富帶來更大空間，不影響該研究結果的情況下能為未來的研究打下基礎。
2.3 解碼
解碼的目的在于将遺傳算法的解空間轉化到現實的問題空間，對于文中算法而言，解碼的目的是翻譯和解釋每條染色體所代表的裝箱方案（即每個盒子應按照何種順序、裝在哪個箱子、采用何種角度并放在什麼位置的具體問題）。解碼是該算法實作的核心，解碼涉及包括APAs排序、盒子方向調整、盒子位置确定和APAs更新在内的具體的裝載政策及實施方法，基本邏輯過程如下所示。
解碼的基本過程：
輸入參數中，Nb和Nc分别代表待裝載盒子和箱子的數量，Chr為某個體（染色體），Boxes和Cons分别為包含長度、寬度、高度、品質、載品質等所有個體屬性在内的盒子和箱子屬性的集合。
在Step3中，完成箱子目前剩餘空間集的生成和計算，為下一步的盒子裝載提供可能的長方體形的備選空間；Step4中，依據最大剩餘空間與箱子原點距離的遠近對所有剩餘空間進行排序，即考慮将盒子優先放置于箱子靠近原點的底部，實作緊湊裝載的目的（對應于圖3中的“APAs排序”）；Step6中，若盒子的長寬高有任意條件不滿足該最大剩餘空間的要求，則考慮将該盒子嘗試裝載到下一個最大剩餘空間；Step7中選擇最佳放置角度的原因在于調整盒子的裝載方向，至少使得裝載後的最大剩餘空間在一個方向上保持最小，即保持最小的裝載間隙，減少空間的浪費（對應于圖3中的“盒子方向調整”）；Step8中，将最大剩餘空間的原點作為裝載盒子的原點，增加為盒子的裝載屬性（對應于圖3中的“盒子位置确定”）；Step9中，通過計算裝載盒子後相關最大剩餘空間的合法新增，并判定新增最大剩餘空間與原最大剩餘空間集是否存在包含關系，實作裝載後最大剩餘空間集元素的新增、删除和更新等操作（對應于圖3中的“APAs更新”）。
2.4 交叉算子
通過分析不難得知，裝箱過程中盒子裝載後所形成的剩餘空間集會對後續裝載過程産生較大影響，特别是裝載靠前的盒子其裝載順序的改變會為後續裝載過程帶來一系列“連鎖反應”。為保證算法交叉時在遺傳父代主要表現特征的同時避免陷入不易收斂的不穩定态，本研究在以往普通單點交叉方法的基礎上，提出了面向優先保持的交叉算子。另外，如圖5所示，與其他算法的交叉實作的控制不同，考慮到箱子順序的改變會對整個疊代過程造成根本性的改變，是以文中交叉算子的實作由2個差異較大的交叉機率獨立控制，即染色體盒子段（前Nb個基因）和染色體箱子段的交叉機率分别設計為pcb和數值更小的pcc。
在進行交叉時，染色體盒子段和染色體箱子段均采用基于優先保持政策的交叉法，見圖4。在Step1中，2條待交叉的染色體首先分别分割為染色體盒子段和染色體箱子段，分别用2個獨立的随機數對比pcb和pcc的大小（圖4示例中，所生成的随機數隻滿足染色體盒子段交叉的條件，隻進行前段染色體的交叉）；Step2主要完成交叉點的選擇，并由此将待交叉染色體串分别分割為m1,m2和n1,n2兩子串；Step3首先完成兩染色體子串主體部分的交叉，而後通過重複性檢驗判斷交叉而來的染色體子串中的非法基因，将這些非法基因進行位置标記（如圖4中ch’11存在重複基因“9”和“7”，代表盒子9和7裝載了2次，顯然非法），并按順序存入待修複基因集；Step4中，分别用待修複基因集中的基因按順序對對方非法基因位置的基因進行替換（如圖4中修複基因序列c1和c2正好分别是ch’12和ch’11所缺失的基因，按修複基因順序進行基因替換的意義在于最大限度的保持其裝載先後的變現特征），完成染色體段的修複和合法化；Step5中，拼接染色體箱子段，完成交叉，傳回新的子代。
2.5 其他算子的設計和選擇
1）變異算子。研究采用基因位随機交換的方式進行變異操作，即按一定機率（變異率，盒子段和箱子段分别為pmb和pmc）和比例（變異比例，盒子段和箱子段分别為rmb和rmc），從待變異的染色體盒子段和箱子段的基因中随機選擇一定數量的基因（即分别為Nbrmb和Ncrmc個基因），通過位置随機互換的方式完成變異。值得注意的是，變異算子同樣遵守交叉算子中的染色體分段和分别判定變異機率的基本原則，以較小的染色體盒子段變異率保證總群的基本穩定和總體收斂。
2）個體适應值的計算。研究以單個箱子裝載空間使用率最大為目标，逐個完成每個箱子的裝載任務，直到所有待裝載盒子完成裝載，是以，僅需将裝載使用率最大的其中1個盒子作為分析對象，即可得出相關裝載結論。個體适應值的計算設定為盒子剩餘空間的比例的倒數，即：适應值=箱子容積/（箱子容積-已裝載盒子總體積），适應值越大，該個體越優。
3）選擇算子。研究在一般錦标賽選擇法的基礎上，采用精英保持的政策完成子代種群的選擇與生成，即在選擇過程中，為保持種群優異個體能良好保持，首先選擇少數（設為比例值re）适應值居于前列的個體進入子代種群，然後再采用正常錦标賽選擇法進行操作。
1 引言
2 遺傳算法理論
2.1 遺傳算法的生物學基礎
2.2 遺傳算法的理論基礎
2.3 遺傳算法的基本概念
2.4 标準的遺傳算法
2.5 遺傳算法的特點
2.6 遺傳算法的改進方向
3 遺傳算法流程
4 關鍵參數說明
模拟退火算法(Simulated Annealing，SA)的思想最早由Metropolis等人于1953年提出：Kirkpatrick于1983年第一次使用模拟退火算法求解組合最優化問題[1] 。模拟退火算法是一種基于MonteCarlo疊代求解政策的随機尋優算法， 其出發點是基于實體中固體物質的退火過程與一般組合優化問題之間的相似性。其目的在于為具有NP(Non-deterministic Polynomial) 複雜性的問題提供有效的近似求解算法，它克服了其他優化過程容易陷入局部極小的缺陷和對初值的依賴性。
模拟退火算法是一種通用的優化算法，是局部搜尋算法的擴充。它不同于局部搜尋算法之處是以一定的機率選擇鄰域中目标值大的劣質解。從理論上說，它是一種全局最優算法。模拟退火算法以優化問
題的求解與實體系統退火過程的相似性為基礎， 它利用Metropolis算法并适當地控制溫度的下降過程來實作模拟退火，進而達到求解全局優化問題的目的[2].
模拟退火算法是一種能應用到求最小值問題的優化過程。在此過程中，每一步更新過程的長度都與相應的參數成正比，這些參數扮演着溫度的角色。與金屬退火原理相類似，在開始階段為了更快地最小
化，溫度被升得很高，然後才慢慢降溫以求穩定。
目前，模拟退火算法迎來了興盛時期，無論是理論研究還是應用研究都成了十分熱門的課題[3-7]。尤其是它的應用研究顯得格外活躍，已在工程中得到了廣泛應用，諸如生産排程、控制工程、機器學習、神經網絡、模式識别、圖像處理、離散/連續變量的結構優化問題等領域。它能有效地求解正常優化方法難以解決的組合優化問題和複雜函數優化問題，适用範圍極廣。
模拟退火算法具有十分強大的全局搜尋性能，這是因為比起普通的優化搜方法，它采用了許多獨特的方法和技術：在模拟退火算法中，基本不用搜尋空間的知識或者其他的輔助資訊，而隻是定義鄰域
結構，在其鄰域結構内選取相鄰解，再利用目标函數進行評估：模拟退火算法不是采用确定性規則，而是采用機率的變遷來指導它的搜尋方向，它所采用的機率僅僅是作為一種工具來引導其搜尋過程朝着更優化解的區域移動。是以，雖然看起來它是一種盲目的搜尋方法，但實際上有着明确的搜尋方向。
2 模拟退火算法理論
模拟退火算法以優化問題求解過程與實體退火過程之間的相似性為基礎，優化的目标函數相當于金屬的内能，優化問題的自變量組合狀态空間相當于金屬的内能狀态空間，問題的求解過程就是找一個組
合狀态， 使目标函數值最小。利用Me to polis算法并适當地控制溫度的下降過程實作模拟退火，進而達到求解全局優化問題的目的[8].
2.1實體退火過程
模拟退火算法的核心思想與熱力學的原理極為類似。在高溫下，液體的大量分子彼此之間進行着相對自由移動。如果該液體慢慢地冷卻，熱能原子可動性就會消失。大量原子常常能夠自行排列成行，形成一個純淨的晶體，該晶體在各個方向上都被完全有序地排列在幾百萬倍于單個原子的距離之内。對于這個系統來說，晶體狀态是能量最低狀态，而所有緩慢冷卻的系統都可以自然達到這個最低能量狀态。實際上，如果液态金屬被迅速冷卻，則它不會達到這一狀态，而隻能達到一種隻有較高能量的多晶體狀态或非結晶狀态。是以，這一過程的本質在于緩慢地冷卻，以争取足夠的時間，讓大量原子在喪失可動性之前進行重新分布，這是確定能量達到低能量狀态所必需的條件。簡單而言，實體退火過程由以下幾部分組成：加溫過程、等溫過程和冷卻過程。
加溫過程
其目的是增強粒子的熱運動，使其偏離平衡位置。當溫度足夠高時，固體将熔解為液體，進而消除系統原先可能存在的非均勻态，使随後進行的冷卻過程以某一平衡态為起點。熔解過程與系統的能量增
大過程相聯系，系統能量也随溫度的升高而增大。
等溫過程
通過實體學的知識得知，對于與周圍環境交換熱量而溫度不變的封閉系統，系統狀态的自發變化總是朝着自由能減小的方向進行：當自由能達到最小時，系統達到平衡态。
冷卻過程
其目的是使粒子的熱運動減弱并逐漸趨于有序，系統能量逐漸下降，進而得到低能量的晶體結構。
2.2 模拟退火原理
模拟退火算法來源于固體退火原理，将固體加溫至充分高，再讓其徐徐冷卻。加溫時，固體内部粒子随溫升變為無序狀，内能增大：而徐徐冷卻時粒子漸趨有序，在每個溫度上都達到平衡态，最後在常
溫時達到基态，内能減為最小。模拟退火算法與金屬退火過程的相似關系如表7.1所示。根Metropolis準則， 粒子在溫度7時趨于平衡的機率為exp(-▲E/T) ， 其中E為溫度7時的内能， ▲E為其改變量。用
固體退火模拟組合優化問題，将内能E模拟為目标函數值，溫度7演化成控制參數，即得到解組合優化問題的模拟退火算法：由初始解%和控制參數初值7開始，對目前解重複“産生新解→計算目标函數差一接受或舍棄”的疊代，并逐漸減小T值，算法終止時的目前解即為所得近似最優解， 這是基MonteCarlo疊代求解法的一種啟發式随機搜尋過程。退火過程由冷卻進度表控制，包括控制參數的初值7及其衰
減因子K、每個7值時的疊代次數I和停止條件。
2.3 模拟退火算法思想
模拟退火的主要思想是：在搜尋區間随機遊走(即随機選擇點)，再利用Metropolis抽樣準則， 使随機遊走逐漸收斂于局部最優解。而溫度是Metropolis算法中的一個重要控制參數，可以認為這個參數的大小控制了随機過程向局部或全局最優解移動的快慢。Metropolis是一種有效的重點抽樣法， 其算法為：系統從一個能量狀态變化到另一個狀态時，相應的能量從E變化到E，其機率為
這樣經過一定次數的疊代，系統會逐漸趨于一個穩定的分布狀态。
重點抽樣時，新狀态下如果向下，則接受(局部最優)；若向上(全局搜尋)，則以一定機率接受。模拟退火算法從某個初始解出發，經過大量解的變換後，可以求得給定控制參數值時組合優化問題的相對最優解。然後減小控制參數7的值， 重複執行Metropolis算法，就可以在控制參數T趨于零時，最終求得組合優化問題的整體最優解。控制參數的值必須緩慢衰減。溫度是Metropolis算法的一個重要控制參數， 模拟退火可視為遞減控制參數7時Metro pl is算法的疊代。開始時7值大， 可以接受較差的惡化解；随着7的減小，隻能接受較好的惡化解；最後在7趨于0時，就不再接受任何惡化解了。
在無限高溫時，系統立即均勻分布，接受所有提出的變換。T的衰減越小， 7到達終點的時間越長； 但可使馬爾可夫(Markov) 鍊減小，以使到達準平衡分布的時間變短。
2.4 模拟退火算法的特點
模拟退火算法适用範圍廣，求得全局最優解的可靠性高，算法簡單，便于實作；該算法的搜尋政策有利于避免搜尋過程因陷入局部最優解的缺陷，有利于提高求得全局最優解的可靠性。模拟退火算法具
有十分強的魯棒性，這是因為比起普通的優化搜尋方法，它采用許多獨特的方法和技術。主要有以下幾個方面：
(1)以一定的機率接受惡化解。
模拟退火算法在搜尋政策上不僅引入了适當的随機因素，而且還引入了實體系統退火過程的自然機理。這種自然機理的引入，使模拟退火算法在疊代過程中不僅接受使目标函數值變“好”的點，而且還能夠以一定的機率接受使目标函數值變“差”的點。疊代過程中出現的狀态是随機産生的，并且不強求後一狀态一定優于前一狀态，接受機率随着溫度的下降而逐漸減小。很多傳統的優化算法往往是确定性
的，從一個搜尋點到另一個搜尋點的轉移有确定的轉移方法和轉移關系，這種确定性往往可能使得搜尋點遠達不到最優點，因而限制了算法的應用範圍。而模拟退火算法以一種機率的方式來進行搜尋，增加了搜尋過程的靈活性。
(2)引進算法控制參數。
引進類似于退火溫度的算法控制參數，它将優化過程分成若幹階段， 并決定各個階段下随機狀态的取舍标準， 接受函數由Metropolis算法給出一個簡單的數學模型。模拟退火算法有兩個重要的步驟：一
是在每個控制參數下，由前疊代點出發，産生鄰近的随機狀态，由控制參數确定的接受準則決定此新狀态的取舍，并由此形成一定長度的随機Markov鍊； 二是緩慢降低控制參數， 提高接受準則， 直至控制參數趨于零，狀态鍊穩定于優化問題的最優狀态，進而提高模拟退火算法全局最優解的可靠性。
(3)對目标函數要求少。
傳統搜尋算法不僅需要利用目标函數值，而且往往需要目标函數的導數值等其他一些輔助資訊才能确定搜尋方向：當這些資訊不存在時，算法就失效了。而模拟退火算法不需要其他的輔助資訊，而隻是
定義鄰域結構，在其鄰域結構内選取相鄰解，再用目标函數進行評估。
2.5模拟退火算法的改進方向
在確定一定要求的優化品質基礎上，提高模拟退火算法的搜尋效率，是對模拟退火算法改進的主要内容[9-10]。有如下可行的方案：選擇合适的初始狀态；設計合适的狀态産生函數，使其根據搜尋程序的
需要表現出狀态的全空間分散性或局部區域性：設計高效的退火過程；改進對溫度的控制方式：采用并行搜尋結構；設計合适的算法終止準則：等等。
此外，對模拟退火算法的改進，也可通過增加某些環節來實作。
主要的改進方式有：
(1)增加記憶功能。為避免搜尋過程中由于執行機率接受環節而遺失目前遇到的最優解，可通過增加存儲環節，将到目前為止的最好狀态存儲下來。
(2)增加升溫或重升溫過程。在算法程序的适當時機，将溫度适當提高，進而可激活各狀态的接受機率，以調整搜尋程序中的目前狀态，避兔算法在局部極小解處停滞不前。
(3)對每一目前狀态，采用多次搜尋政策，以機率接受區域内的最優狀态，而不是标準模拟退火算法的單次比較方式。
(4)與其他搜尋機制的算法(如遺傳算法、免疫算法等)相結合。可以綜合其他算法的優點，提高運作效率和求解品質。
3 模拟退火算法流程
模拟退火算法新解的産生和接受可分為如下三個步驟：
(1)由一個産生函數從目前解産生一個位于解空間的新解；為便于後續的計算和接受，減少算法耗時，通常選擇由目前解經過簡單變換即可産生新解的方法。注意，産生新解的變換方法決定了目前新解
的鄰域結構，因而對冷卻進度表的選取有一定的影響。
(2)判斷新解是否被接受，判斷的依據是一個接受準則，最常用的接受準則是Metropolis準則：若AK 0， 則接受X作為新的目前解否則， 以機率exp(-▲E/7) 接受X”作為新的目前解X.
(3)當新解被确定接受時，用新解代替目前解，這隻需将目前解中對應于産生新解時的變換部分予以實作，同時修正目标函數值即可。此時，目前解實作了一次疊代，可在此基礎上開始下一輪試驗。若當新解被判定為舍棄，則在原目前解的基礎上繼續下一輪試驗。模拟退火算法求得的解與初始解狀态(算法疊代的起點)無關，具有漸近收斂性，已在理論上被證明是一種以機率1收斂于全局最優解的優化算法。模拟退火算法可以分解為解空間、目标函數和初始解三部分。該算法具體流程如下[8]：
(1)初始化：設定初始溫度7(充分大)、初始解狀态%(是算
法疊代的起點)、每個7值的疊代次數L：
(2)對k=1，…，L做第(3)至第(6)步；
(3)産生新解X；
(4) 計算增量A BE(X) -E(X) ， 其中E() ) 為評價函數：
(5)若AK0，則接受X作為新的目前解，否則以機率
exp(-▲E/7) 接受X作為新的目前解；
(6)如果滿足終止條件，則輸出目前解作為最優解，結束程式：
(7)7逐漸減小，且T→0，然後轉第(2)步。
模拟退火算法流程如圖7.1所示。
模拟退火算法的性能品質高，它比較通用，而且容易實作。不過，為了得到最優解，該算法通常要求較高的初溫以及足夠多次的抽樣，這使算法的優化時間往往過長。從算法結構知，新的狀态産生函
數、初溫、退溫函數、Markov鍊長度和算法停止準則， 是直接影響算法優化結果的主要環節。
狀态産生函數
設計狀态産生函數應該考慮到盡可能地保證所産生的候選解遍布全部解空間。一般情況下狀态産生函數由兩部分組成，即産生候選解的方式和産生候選解的機率分布。候選解的産生方式由問題的性質決
定，通常在目前狀态的鄰域結構内以一定機率産生。
初溫
溫度7在算法中具有決定性的作用，它直接控制着退火的走向。由随機移動的接受準則可知：初溫越大，獲得高品質解的幾率就越大，且Metropolis的接收率約為1。然而， 初溫過高會使計算時間增加。
為此，可以均勻抽樣一組狀态，以各狀态目标值的方差為初溫。
退溫函數
退溫函數即溫度更新函數，用于在外循環中修改溫度值。目前，最常用的溫度更新函數為指數退溫函數， 即T(n+1) =KXT(n) ， 其中0<K1是一個非常接近于1的常數。
Markov鍊長度L的選取
Markov鍊長度是在等溫條件下進行疊代優化的次數， 其選取原則是在衰減參數7的衰減函數己標明的前提下，L應選得在控制參數的每一取值上都能恢複準平衡，一般L取100~1000.
算法停止準則
算法停止準則用于決定算法何時結束。可以簡單地設定溫度終值T，當F=T，時算法終止。然而，模拟火算法的收斂性理論中要求T趨向于零，這其實是不實際的。常用的停止準則包：設定終止溫度的阈
值，設定疊代次數門檻值，或者當搜尋到的最優值連續保持不變時停止搜尋。
1 matlab版本
2014a
2 參考文獻
[1] 包子陽,餘繼周,楊杉.智能優化算法及其MATLAB執行個體（第2版）[M].電子工業出版社，2016.
[2]張岩,吳水根.MATLAB優化算法源代碼[M].清華大學出版社，2017.
[3]周品.MATLAB 神經網絡設計與應用[M].清華大學出版社，2013.
[4]陳明.MATLAB神經網絡原理與執行個體精解[M].清華大學出版社，2013.
[5]方清城.MATLAB R2016a神經網絡設計與應用28個案例分析[M].清華大學出版社，2018.