禁忌搜索演算法的缺點

⑴ 請教選址研究問題！

物流配送中心選址方法研究綜述

內容摘要：物流配送中心的選址決策在物流運作中有著重要的地位。本文對近年來國內外有關配送中心選址方法的文獻進行梳理和研究。研究結果發現：各種選址方法有著各自的優缺點和一定的適用范圍，各種方法的組合是未來該領域研究的趨勢。
關鍵詞：物流配送中心 選址 文獻綜述

在物流系統的運作中，配送中心的選址決策發揮著重要的影響。配送中心是連接工廠與客戶的中間橋梁，其選址方式往往決定著物流的配送距離和配送模式，進而影響著物流系統的運作效率。因此，研究物流配送中心的選址具有重要的理論和現實應用意義。
本文對近年來國內外有關物流配送中心選址方法的文獻進行了梳理和研究，並對各種方法進行了比較。選址方法主要有定性和定量的兩種方法。定性方法有專家打分法、Delphi法等，定量方法有重心法、P中值法、數學規劃方法、多准則決策方法、解決NP hard問題（多項式復雜程度的非確定性問題）的各種啟發式演算法、模擬法以及這幾種方法相結合的方法等。由於定性研究方法及重心法、P中值法相對比較成熟，因此，本文將主要分析定量方法中的數學規劃、多准則決策、解決NP hard問題的各種啟發式演算法、模擬在配送中心選址中應用的研究狀況。
數學規劃方法
數學規劃演算法包括線性規劃、非線性規劃、整數規劃、混合整數規劃和動態規劃、網路規劃演算法等。在近年來的研究中，規劃論中常常引入了不確定性的概念，由此進一步產生了模糊規劃、隨機規劃、模糊隨機規劃、隨機模糊規劃等等。不確定性規劃主要是在規劃中的C(價值向量)、A(資源消耗向量)、b(資源約束向量)和決策變數中引入不確定性，從而使得不確定規劃更加貼近於實際情況，得到廣泛地實際應用。
國內外學者對於數學規劃方法應用於配送中心的選址問題進行了比較深入的研究。姜大元(2005)應用Baumol-wolf模型，對多物流節點的選址問題進行研究，並通過舉例對模型的應用進行了說明，該模型屬於整數規劃和非參數規劃結合的模型。各種規劃的方法在具體的現實使用中，常常出現NP hard問題。因此，目前的進一步研究趨勢是各種規劃方法和啟發式演算法的結合，對配送中心的選址進行一個綜合的規劃與計算。
多准則決策方法
在物流系統的研究中，人們常常會遇到大量多准則決策問題，如配送中心的選址、運輸方式及路線選擇、供應商選擇等等。這些問題的典型特徵是涉及到多個選擇方案(對象)，每個方案都有若干個不同的准則，要通過多個准則對於方案(對象)做出綜合性的選擇。對於物流配送中心的選址問題，人們常常以運輸成本及配送中心建設、運作成本的總成本最小化，滿足顧客需求，以及滿足社會、環境要求等為准則進行決策。多准則決策的方法包括多指標決策方法與多屬性決策方法兩種，比較常用的有層次分析法(AHP)、模糊綜合評判、數據包絡分析(DEA),TOPSIS、優序法等等。
多准則決策提供了一套良好的決策方法體系，對於配送中心的選址不管在實務界還是理論方面的研究均有廣泛的應用與研究。關志民等(2005)提出了基於模糊多指標評價方法的配送中心選址優化決策。從供應鏈管理的實際需要分析了影響配送中心選址的主要因素，並建立相應的評價指標體系，由此給出了一種使定性和定量的方法有機結合的模糊多指標評價方法。Chen-Tung Chen(2001)運用了基於三角模糊數的模糊多准則決策對物流配送中心的選址問題進行了研究。文章以投資成本、擴展的可能性、獲取原材料的便利性、人力資源、顧客市場的接近性為決策准則，並對各個准則採用語義模糊判定的方式進行了權重上的集結。
有關多准則決策方法，特別是層次分析法和模糊綜合評判的方法，在配送中心的選址研究中有著廣泛的應用。但是，這兩種方法都是基於線性的決策思想，在當今復雜多變的環境下，線性的決策思想逐漸地暴露出其固有的局限性，非線性的決策方法是今後進一步的研究的重點和趨勢。
啟發式演算法
啟發式演算法是尋求解決問題的一種方法和策略，是建立在經驗和判斷的基礎上，體現人的主觀能動作用和創造力。啟發式演算法常常能夠比較有效地處理NP hard問題，因此，啟發式演算法經常與其它優化演算法結合在一起使用，使兩者的優點進一步得到發揮。目前，比較常用的啟發式演算法包括：遺傳演算法；神經網路演算法；模擬退火演算法。
（一）遺傳演算法
遺傳演算法（genetic algorithm, GA）是在 20 世紀 60 年代提出來的，是受遺傳學中自然選擇和遺傳機制啟發而發展起來的一種搜索演算法。它的基本思想是使用模擬生物和人類進化的方法求解復雜的優化問題，因而也稱為模擬進化優化演算法。遺傳演算法主要有三個運算元：選擇；交叉；變異。通過這三個運算元，問題得到了逐步的優化，最終達到滿意的優化解。
對於物流配送中心的選址研究，國內外有不少學者將遺傳演算法同一般的規劃方法結合起來對其進行了研究。蔣忠中等（2005）在考慮各種成本(包括運輸成本等)的基礎上，結合具體的應用背景，建立的數學規劃模型(混合整數規劃或是一般的線性規劃)。由於該模型是一個組合優化問題，具有NP hard問題，因此，結合了遺傳演算法對模型進行求解。通過選擇恰當的編碼方法和遺傳運算元，求得了模型的最優解。
遺傳演算法作為一種隨機搜索的、啟發式的演算法，具有較強的全局搜索能力，但是，往往比較容易陷入局部最優情況。因此，在研究和應用中，為避免這一缺點，遺傳演算法常常和其它演算法結合應用，使得這一演算法更具有應用價值。
（二）人工神經網路
人工神經網路(artificial neural- network, ANN)是由大量處理單元(神經元)廣泛互連而成的網路，是對人腦的抽象、簡化和模擬，反應人腦的基本特徵。可以通過對樣本訓練數據的學習，形成一定的網路參數結構，從而可以對復雜的系統進行有效的模型識別。經過大量樣本學習和訓練的神經網路在分類和評價中，往往要比一般的分類評價方法有效。
對於神經網路如何應用於物流配送中心的選址，國內外不少學者進行了各種有益的嘗試。韓慶蘭等（2004）用BP網路對物流配送中心的選址問題進行了嘗試性地研究，顯示出神經網路對於解決配送中心選址問題具有一定的可行性和可操作性。
這一研究的不足是神經網路的訓練需要大量的數據，在對數據的獲取有一定的困難的情況下，用神經網路來研究是不恰當的。在應用ANN時，我們應當注意網路的學習速度、是否陷入局部最優解、數據的前期准備、網路的結構解釋等問題，這樣才能有效及可靠地應用ANN解決實際存在的問題。
（三）模擬退火演算法
模擬退火演算法(Simulated Annealing, SA)又稱模擬冷卻法、概率爬山法等，於1982年由Kirpatrick提出的另一種啟發式的、隨機優化演算法。模擬退火演算法的基本思想由一個初始的解出發，不斷重復產生迭代解，逐步判定、舍棄，最終取得滿意解的過程。模擬退火演算法不但可以往好的方向發展,也可以往差的方向發展,從而使演算法跳出局部最優解,達到全局最優解。
對於模擬退火演算法應用於物流配送中心選址的研究，大量的文獻結合其它方法（如多准則決策、數學規劃等）進行了研究。任春玉(2006)提出了定量化的模擬退火遺傳演算法與層次分析法相結合來確定配送中心地址的方法。該方法確保總體中個體多樣性以及防止遺傳演算法的提前收斂，運用層次分析法確定 物流配送中心選址評價指標權重，並與專家評分相結合進行了綜合評價。該演算法對於解決物流配送中心的選址具有較好的有效性和可靠性。
除以上三種比較常用的方法之外，啟發式演算法還包括蟻群演算法、禁忌搜索演算法、進化演算法等。各種演算法在全局搜索能力、優缺點、參數、解情況存在著一定的差異。各種啟發式演算法基本上帶有隨機搜索的特點，已廣泛地應用於解決NP hard問題，同時也為物流配送中心選址的智能化處理提供了可能。用解析的方法(包括線性規劃等)建立數學模型，然後運用啟發式演算法進行求解是目前以及未來研究物流配送中心選址的一種較為可行和可操作的研究方法。
模擬方法
模擬是利用計算機來運行模擬模型，模擬時間系統的運行狀態及其隨時間變化的過程，並通過對模擬運行過程的觀察和統計，得到被模擬系統的模擬輸出參數和基本特徵，以此來估計和推斷實際系統的真實參數和真實性能。國內外已經不少文獻將模擬的方法運用於物流配送中心選址或是一般的設施選址的研究，研究結果相對解析方法更接近於實際的情況。
張雲鳳等(2005)對汽車集團企業的配送中心選址運用了模擬的方法進行了研究。先確定了配送中心選址的幾種方案，應用了Flexim軟體對各方案建立了模擬模型，根據模擬結果進行了分析和方案的選擇。該方法為集團企業配送中心選址問題提供了一種較為理想的解決方法。薛永吉等(2005)通過建立數學模型對物流中心的最優站台數問題進行研究，在一定假設和一系列限制條件下，求解最優站台數量，並針對數學模型的復雜性和求解的種種不足，以ARENA模擬軟體為平台，建立模擬模型確定了最優化方案。Kazuyoshi Hidaka等(97)運用模擬對大規模的倉庫選址進行了研究。該研究對倉庫的固定成本、運輸成本，和同時滿足6800名顧客進行了模擬，以求得臨近的最優解(near-optimal solution)。在求解的過程中，結合了貪婪－互換啟發式演算法(Greedy-Interchange heuristics)和氣球搜索演算法(Balloon Search)兩種啟發式演算法進行求解。該演算法能比較有效地避免陷入局部最優解和得到比較滿意的選址方案。但是，研究的結果容易受到運輸車輛的平均速度變化的影響。
模擬方法相對解析的方法在實際應用中具有一定的優點，但是，也存在一定的局限性。如模擬需要進行相對比較嚴格的模型的可信性和有效性的檢驗。有些模擬系統對初始偏差比較敏感，往往使得模擬結果與實際結果有較大的偏差。同時，模擬對人和機器要求往往比較高，要求設計人員必須具備豐富的經驗和較高的分析能力，而相對復雜的模擬系統，對計算機硬體的相應要求是比較高的。關於未來的研究，各種解析方法、啟發式演算法、多准則決策方法與模擬方法的結合，是一種必然的趨勢。各種方法的結合可以彌補各自的不足，而充分發揮各自的優點，從而提高選址的准確性和可靠性。
物流配送中心的選址決策對於整個物流系統運作和客戶滿意情況有著重要的影響。本文在對國內外有關物流配送中心選址方法文獻研究的基礎上，對比分析了數學規劃方法、多准則決策、啟發式演算法、模擬方法在配送中心選址中的應用。研究發現數學規劃方法、多屬性決策方法、啟發式演算法、模擬方法各自有自己的優缺點和一定的適用范圍，各種方法的組合研究是未來研究的一種趨勢。同時，由於選址問題本身具有的動態性、復雜性、不確定性等特性，因此，開發和研究新的模型與方法也是進一步解決配送中心選址問題的必需途徑。

參考文獻：
1.蔣忠中，汪定偉.B2C電子商務中配送中心選址優化的模型與演算法(J).控制與決策，2005
2.韓慶蘭，梅運先.基於BP人工神經網路的物流配送中心選址決策(J).中國軟科學，2004

⑵ 哪個大神有時間幫我對VRP問題用禁忌搜索演算法編寫一個lingo或者c語言可以

求最短配送路徑的話 應該是TSP問題吧，不應該是VRP問題。
LINGO能很好地求解這兩類模型，但用的整數規劃原理或動態規劃原理，不能用禁忌搜索。
禁忌搜索，就用C或許能解決。

⑶ 禁忌搜索演算法淺析

姓名：劉家沐

學號：19011210553

網路來源，有刪減

【嵌牛導讀】：針對TSP問題等類似的NP-hard 問題，如果能在盡量少的計算量的情況下找到一個最優或者是較優的解成為當前一個熱門的討論話題，禁忌搜索演算法便是其中之一

【嵌牛鼻子】：禁忌搜索演算法   最優化問題    TSP問題

【嵌牛正文】：

背景：禁忌搜索演算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優的搜尋方法。在解決最優問題上，一般區分為兩種方式：一種是傳統的方法，另一種方法則是一些啟發式搜索演算法。

使用傳統的方法，我們必須對每一個問題都去設計一套演算法，相當不方便，缺乏廣泛性，優點在於我們可以證明演算法的正確性，我們可以保證找到的答案是最優的；而對於啟發式演算法，針對不同的問題，我們可以套用同一個架構來尋找答案，在這個過程中，我們只需要設計評價函數以及如何找到下一個可能解的函數等，所以啟發式演算法的廣泛性比較高，但相對在准確度上就不一定能夠達到最優，但是在實際問題中啟發式演算法那有著更廣泛的應用。 

禁忌搜索是一種亞啟發式隨機搜索演算法，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向。 TS是人工智慧的一種體現，是局部領域搜索的一種擴展。禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中涉及鄰域 、禁忌表、禁忌長度、候選解、藐視准則等影響禁忌搜索演算法性能的關鍵因素。迄今為止，TS演算法在組合優化等計算機領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，並大有發展的趨勢。

局域搜索：在一個小的搜索范圍里，進行搜索，或者根據結果逐步擴大搜索范圍，但是這樣會容易陷入局部最優

為了獲得好解，可以採用的策略有(1)擴大鄰域結構，(2)變鄰域結構    ，(3)多初始點。但這些策略依然無法保證演算法具備跳出局優的能力。

禁忌搜索：

為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。 禁忌搜索 就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較， 珠穆朗瑪峰 脫穎而出。

當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。

主要思路：

1、在搜索中，構造一個短期循環記憶表-禁忌表，禁忌表中存放剛剛進行過的 |T|（T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。

2、禁忌表中的移動稱為禁忌移動。對於進入禁忌表中的移動， 在以後的 |T| 次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。|T| 次循環後禁忌解除。

3、禁忌表是一個循環表，在搜索過程中被循環的修改，使禁忌表始終保持 |T| 個移動。

4、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止准則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它時，演算法停止。

總結：

與傳統的優化演算法相比，TS演算法的主要特點是：

 1．從移動規則看，每次只與最優點比較，而不與經過點比較，故可以爬出局部最優。

 2．選優規則始終保持曾經達到的最優點，所以即使離開了全局最優點也不會失去全局最優性。

 3．終止規則不以達到局部最優為終止規則，而以最大迭代次數、出現頻率限制或者目標值偏離成都為終止規則

禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。因而在計算搜索領域有著廣泛應用。

⑷ 禁忌搜索演算法的主要思想和特徵

禁忌演算法是一種亞啟發式隨機搜索演算法1，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。 禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的.

⑸ 最大團問題的應用背景

MCP問題是現實世界中一類真實問題，在市場分析、方案選擇、信號傳輸、計算機視覺、故障診斷等領域具有非常廣泛的應用。自1957年Hararv和Ross首次提出求解最大團問題的確定性演算法以來，研究者們已提出了多種確定性演算法來求解最大團問題。但隨著問題規模的增大（頂點增多和邊密度變大），求解問題的時間復雜度越來越高，確定性演算法顯得無能為力，不能有效解決這些NP完全問題。
20世紀80年代末，研究者們開始嘗試採用啟發式演算法求解最大團問題，提出了各種各樣的啟發式演算法，如順序貪婪啟發式演算法、遺傳演算法、模擬退火演算法、禁忌搜索演算法、神經網路演算法等，並且取得了令人滿意的效果。在時間上，由於採用了啟發式信息，啟發式演算法的運算時間與確定性演算法的運算時間之間的比值會隨著圖的頂點、邊密度的增加而變得越來越小。唯一的缺點就是不一定能找到最優值，有時只能找到近優值。
近年來研究表明，單獨使用一種啟發式演算法求解最大團問題，演算法性能往往並不是很好，因此，常借鑒演算法之間優勢互補策略，形成新的混合啟發式演算法來求解最大團問題。當前求解該問題最好的啟發式演算法有反作用禁忌搜索（Reactive Tabu Search, RTS）演算法、基於遺傳演算法的簡單啟發式演算法（Simple Heuristic Based Genetic Algorithm, HGA）、DLS-MC演算法等。

⑹ TS演算法是什麼

就是禁忌搜索演算法，又名「tabu搜索演算法」，是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。
禁忌（Tabu Search）演算法是一種亞啟發式(meta-heuristic)隨機搜索演算法，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。

⑺ 禁忌搜索演算法的介紹

禁忌（Tabu Search）演算法是一種亞啟發式(meta-heuristic)隨機搜索演算法1，它從一個初始可行解出發，選擇一系列的特定搜索方向（移動）作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。

⑻ 有什麼演算法可以同時解決車輛路徑優化的VRPTW和SDVRP，數學模型怎麼達到

智能優化演算法，比如粒子群演算法、蟻群演算法、禁忌搜索演算法。優點是對問題和模型要求低，搜索速度快；缺點是容易陷入局部最優解。

⑼ 禁忌搜索演算法的偽碼表達

procere tabu search;
begin
initialize a string vc at random,clear up the tabu list;
cur:=vc;
repeat
select a new string vn in the neighborhood of vc;
if va>best_to_far then {va is a string in the tabu list}
begin
cur:=va;
let va take place of the oldest string in the tabu list;
best_to_far:=va;
end else
begin
cur:=vn;
let vn take place of the oldest string in the tabu list;
end;
until (termination-condition);
end;
以上程序中的關鍵在於： 禁忌對象：可以選取當前的值（cur）作為禁忌對象放進tabu list，也可以把和當前值在同一「等高線」上的都放進tabu list。 為了降低計算量，禁忌長度和禁忌表的集合不宜太大，但是禁忌長度太小容易循環搜索，禁忌表太大容易陷入「局部極優解」。 上述程序段中對best_so_far的操作是直接賦值為最優的「解禁候選解」，但是有時候會出現沒有大於best_so_far的，候選解也全部被禁的「死鎖」狀態，這個時候，就應該對候選解中最佳的進行解禁，以能夠繼續下去。 終止准則：和模擬退火，遺傳演算法差不多，常用的有：給定一個迭代步數；設定與估計的最優解的距離小於某個范圍時，就終止搜索；當與最優解的距離連續若干步保持不變時，終止搜索； 鄰域：由偽碼 select a new string vn in the neighborhood of vc,可以看出,系統總是在初始點的鄰域搜索可能解的,因而必須定義適合的鄰域空間,如果解空間存在一個最優解X*,初始搜索點為S0,那麼如果S0不存在到達X*的通路,就會使搜索陷入S0的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。

⑽ 禁忌搜索解決任務分配問題（matlab)

function main()
clear
taskNum = 50;
machNum = 8;
densityV = [0.2]%,0.5,0.8];
ccrV = [0.5]%,1,2];
saSHH = [];
SAtimeHH = [];
for density = densityV
for ccr = ccrV
[ETC,adjMatrix,memReq,memCap] = instance(taskNum,machNum,ccr,density); %% taskH,machH,ccr,density,type
SAresultHH = [];
tSAHH = [];
for iter = 1:5
SAStart = cputime;
[SACost,IteratorSolution] = SA(ETC,adjMatrix,memReq,memCap);
SAresultHH = [SAresultHH,SACost];
SAtime = cputime - SAStart;
tSAHH = [tSAHH,SAtime];

end
saSHH = [saSHH;SAresultHH];
SAtimeHH = [SAtimeHH;tSAHH];
end
end
meanSAsHH = mean(saSHH')

stdSAsHH = std(saSHH')

meanSAtHH = mean(SAtimeHH')

col_sa = length(IteratorSolution);
plot(1:col_sa,IteratorSolution,'-x','linewidth',1.0);
xlabel('Evaluation number');
ylabel('Fitness value');
legend('SA');

function [bestCost,IteratorSolution] = SA(ETC,adjMatrix,memReq,memCap,speed,machRelia,linkRelia)
[taskNum,machNum] = size(ETC);
S = randint(1,taskNum,[1,machNum]); %initial the s randomly
T = IniTemp(S,ETC,adjMatrix,memReq,memCap); %initial the temprature
% Tlow = IniTemp(S,ETC,adjMatrix,memReq,memCap,0.50001);
[cost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap);
Alpha = 0.9; %the value of Alpha
Bita = 1.05; %the value of Bita
Nrep = taskNum * machNum; %the count of inner loop
IteratorSolution = []; %record the change among the loop
bestS = S;
bestCost = cost;
deadline1 = 0; %the count of the outer loop
while deadline1 <= 20
findBest = 0;
iter = 1;
deadline2 = 0;
while (iter <= Nrep)
triS = S;
triCost = cost;
t = fix(1 + rand * taskNum);
p = triS(t);
q = fix(1 + rand * machNum);
while p == q
q = fix(1 + rand * machNum);
end
triS(t) = q;
triCost = triCost - ETC(t,p) + ETC(t,q);
adjTask = find(adjMatrix(t,:));
for k = adjTask %alter communication cost
switch triS(k)
case q
triCost = triCost - adjMatrix(t,k);
case p
triCost = triCost + adjMatrix(t,k);
end
end
if (memLoad(p) > memCap(p)) %calculate violation
if (memLoad(p) - memReq(t)) <= memCap(p)
triCost = triCost - (memLoad(p) - memCap(p));
else
triCost = triCost - memReq(t);
end
end
% there exists no memory violation before migration
if (memLoad(q) + memReq(t)) > memCap(q)
if memLoad(q) <= memCap(q)
triCost = triCost + (memLoad(q) + memReq(t) - memCap(q));
else % there exists memory violation before migration
triCost = triCost + memReq(t);
end
end
Dita = triCost - cost;
if Dita < 0
S = triS;
cost = triCost;
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
if (triCost < bestCost)
bestS = triS;
bestCost = triCost;
deadline2 = 0;
findBest = 1;
end
else
if rand < exp(-Dita/T)
S = triS;
cost = triCost;
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
end
deadline2 = deadline2 + 1;
if deadline2 >= taskNum * machNum
break;
end
end
iter = iter + 1;
IteratorSolution = [IteratorSolution,cost];
end
T = Alpha * T;
Nrep = Bita * Nrep;
if findBest
deadline1 = 0;
else
deadline1 = deadline1 + 1;
end
end

function [totalCost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap)
[tN,mN] = size(ETC);
totalCost = 0;
memLoad = zeros(1,mN);
for t = 1:tN
totalCost = totalCost + ETC(t,S(t));
memLoad(S(t)) = memLoad(S(t)) + memReq(t);
for k = t+1:tN %t or t+1?
if (adjMatrix(t,k)>0) && (S(k) ~= S(t))
totalCost = totalCost + adjMatrix(t,k);
end
end
end
for m = 1:mN
if memLoad(m) > memCap(m)
totalCost = totalCost + (memLoad(m) - memCap(m));
end
end

function [ETC,adjMatrix,memReq,memCap] = instance(taskNum,machNum,ccr,density)

ETC = fix(1 + 200 * rand(taskNum,machNum));
for i = 1:taskNum-1
for j = i+1:taskNum
if (rand < density)
adjMatrix(i,j) = fix(2 * (1 + 200 * rand) * ccr / ((taskNum-1) * density));
else
adjMatrix(i,j) = 0;
end
adjMatrix(j,i) = adjMatrix(i,j);
end
end
% memory requirement of each task
memReq = fix(1 + 50 * rand(1,taskNum));
% memory capacity of each processor
memCap = fix((1 + rand(1,machNum)) * sum(memReq) / machNum);

function T = IniTemp(S,ETC,adjMatrix,memReq,memCap)
[taskNum,machNum] = size(ETC);
SumCi = 0;
AccValue = 0.9;
Ci = 0;
Cr = 0;
[cost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap); % calculate the total cost
for countNum = 1:200
triS = S;
triCost = cost;
t = fix(1 + taskNum * rand);
p = triS(t);
q = fix(1 + machNum * rand);
while p == q
q = fix(1 + machNum * rand);;
end
triS(t) = q;
triCost = triCost - ETC(t,p) + ETC(t,q);
adjTask = find(adjMatrix(t,:));
for k = adjTask %alter communication cost
switch triS(k)
case q
triCost = triCost - adjMatrix(t,k);
case p
triCost = triCost + adjMatrix(t,k);
end
end
if (memLoad(p) > memCap(p)) %calculate violation
if (memLoad(p) - memReq(t)) <= memCap(p)
triCost = triCost - (memLoad(p) - memCap(p));
else
triCost = triCost - memReq(t);
end
end
% there exists no memory violation before migration
if (memLoad(q) + memReq(t)) > memCap(q)
if memLoad(q) <= memCap(q)
triCost = triCost + (memLoad(q) + memReq(t) - memCap(q));
else % there exists memory violation before migration
triCost = triCost + memReq(t) ;
end
end
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);

Dita = triCost - cost;
if Dita > 0
Ci = Ci + 1;
SumCi = SumCi + Dita;
else
Cr = Cr + 1;
end;
S = triS;
cost = triCost;
end;
Ca = SumCi / Ci;
T = -Ca / (log((AccValue - 1) * Cr / Ci + AccValue));

function T = calculateT(ETC,adjMatrix,tN,mN,solNum)
sol = fix(1+mN*rand(solNum,tN));
for i = 1:solNum
Fitness(i) = fitnessCal(ETC,adjMatrix,sol(i,:),tN);
end
T = max(Fitness) - min(Fitness);

% ***** the following function has no relation with the above ***** %
function machLoad = calcLoad(A,ETC,adjMatrix) % Objective 2
[tN,mN] = size(ETC);
machLoad = zeros(1,mN);
for k = 1:tN
machLoad(A(k)) = machLoad(A(k)) + ETC(k,A(k));
for h = k+1:tN
if (adjMatrix(k,h) > 0 && A(k) ~= A(h))
machLoad(A(k)) = machLoad(A(k)) + adjMatrix(k,h);
machLoad(A(h)) = machLoad(A(h)) + adjMatrix(k,h);
end
end
end