禁忌搜索演算法代碼
⑴ 禁忌搜索解決任務分配問題（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
⑵ 禁忌搜索演算法淺析
姓名：劉家沐
學號：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、在搜索中，構造一個短期循環記憶表-禁忌表，禁忌表中存放剛剛進行過的 |T|（T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。
2、禁忌表中的移動稱為禁忌移動。對於進入禁忌表中的移動， 在以後的 |T| 次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。|T| 次循環後禁忌解除。
3、禁忌表是一個循環表，在搜索過程中被循環的修改，使禁忌表始終保持 |T| 個移動。
4、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止准則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它時，演算法停止。
⑷ 禁忌搜索演算法的偽碼表達
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的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。
⑸ 學習Python需要掌握哪些技術
Python學習路線。
第一階段Python基礎與Linux資料庫。這是Python的入門階段，也是幫助零基礎學員打好基礎的重要階段。你需要掌握Python基本語法規則及變數、邏輯控制、內置數據結構、文件操作、高級函數、模塊、常用標准庫模塊、函數、異常處理、MySQL使用、協程等知識點。
學習目標：掌握Python基礎語法，具備基礎的編程能力；掌握Linux基本操作命令，掌握MySQL進階內容，完成銀行自動提款機系統實戰、英漢詞典、歌詞解析器等項目。
第二階段WEB全棧。這一部分主要學習Web前端相關技術，你需要掌握HTML、CSS、JavaScript、jQuery、BootStrap、Web開發基礎、VUE、Flask Views、Flask模板、 資料庫操作、Flask配置等知識。
學習目標：掌握WEB前端技術內容，掌握WEB後端框架，熟練使用Flask、Tornado、Django，可以完成數據監控後台的項目。
第三階段數據分析+人工智慧。這部分主要是學習爬蟲相關的知識點，你需要掌握數據抓取、數據提取、數據存儲、爬蟲並發、動態網頁抓取、scrapy框架、分布式爬蟲、爬蟲攻防、數據結構、演算法等知識。
學習目標：可以掌握爬蟲、數據採集，數據機構與演算法進階和人工智慧技術。可以完成爬蟲攻防、圖片馬賽克、電影推薦系統、地震預測、人工智慧項目等階段項目。
第四階段高級進階。這是Python高級知識點，你需要學習項目開發流程、部署、高並發、性能調優、Go語言基礎、區塊鏈入門等內容。
學習目標：可以掌握自動化運維與區塊鏈開發技術，可以完成自動化運維項目、區塊鏈等項目。
按照上面的Python學習路線圖學習完後，你基本上就可以成為一名合格的Python開發工程師。當然，想要快速成為企業競聘的精英人才，你需要有好的老師指導，還要有較多的項目積累實戰經驗。
自學本身難度較高，一步一步學下來肯定全面且扎實，如果自己有針對性的想學哪一部分，可以直接跳過暫時不需要的針對性的學習自己需要的模塊，可以多看一些不同的視頻學習。
⑹ 禁忌搜索的禁忌搜索示例
組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於 n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌搜索則希望僅通過探索少數解來得到滿意的優化解。 可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、藐視准則、終止准則等是影響禁忌搜索演算法性能的關鍵。需要指出的是：
（1）首先，由於TS是局部領域搜索的一種擴充，因此領域結構的設計很關鍵，它決定了當前解的領域解的產生形式和數目，以及各個解之間的關系。
（2）其次，出於改善演算法的優化時間性能的考慮，若領域結構決定了大量的領域解（尤其對大規模問題，如TSP的SWAP操作將產生Cn2個領域解），則可以僅嘗試部分互換的結果，而候選解也僅取其中的少量最佳狀態。
（3）禁忌長度是一個很重要的關鍵參數，它決定禁忌對象的任期，其大小直接進而影響整個演算法的搜索進程和行為。同時，以上示例中，禁忌表中禁忌對象的替換是採用FIFO方式（不考慮藐視准則的作用），當然也可以採用其他方式，甚至是動態自適應的方式。
（4）藐視准則的設置是演算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。
（5）對於非禁忌候選狀態，演算法無視它與當前狀態的適配值的優劣關系，僅考慮它們中間的最佳狀態為下一步決策，如此可實現對局部極小的突跳（是一種確定性策略）。
（6）為了使演算法具有優良的優化性能或時間性能，必須設置一個合理的終止准則來結束整個搜索過程。 此外，在許多場合禁忌對象的被禁次數（frequency）也被用於指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。
⑺ 禁忌搜索演算法的主要思想和特徵
禁忌演算法是一種亞啟發式隨機搜索演算法1，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。 禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的.