禁忌演算法流程

㈠ c++ 求禁忌搜索演算法與遺傳演算法結合的代碼

//個體編碼方案：十進制的數列，1至26代表A至Z
//交配方法：使用整數編碼的交配規則的常規交配法，
//變異方法 ：使用基於次序的變異，隨機的產生兩個變異位，然後交換這兩個變異位上的基因
//新種群構成方法：輪盤賭法進行篩選
//演算法結束條件：種群不再發生變化時停止
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<time.h>
#define random(x) (rand()%x)//隨機整數
#define initial {0,2,11,1,8,16,5,19,12,4,15,17,6,18,14,9,7,3,10,13}//隨機初值

using namespace std;
//參數
int city_number;
double pm = 0.92;
double initiall = 280;//種群數量
double length_table[26][26];
double pc = 0.02;
struct node
{
char name;
int num;
double x;
double y;
};
struct answer
{
int i;
int jie[26];// 十進制的數列，1至26代表A至Z
double length;
};
double f(int* x)
{
double fi = 0;
for(int i = 0; i < city_number-1; i++)
{
fi = fi + length_table[x[i]][x[i+1]];
}
fi = fi + length_table[x[city_number-1]][x[0]];
return fi;
}
double p(double fi,double fj,double t)
{
double P = exp(-(fj-fi)/t);
return P;
}

int main(int argc,char*argv[])
{
time_t tm; time(&tm);
int flag1 = tm;
int cities;
ifstream in(argv[1]);
in >> cities;
city_number = cities;
node* nodes = new node[city_number];
for(int i = 0; i < cities; i++)
{
in >> nodes[i].name >> nodes[i].x >> nodes[i].y;
nodes[i].num = i;
}
//cout << cities<<endl;
//for(int i = 0; i < cities; i++)
// cout <<nodes[i].name <<" "<< nodes[i].x <<" "<< nodes[i].y<<endl;
int i,j;
for(i = 0; i < cities; i++)
{
length_table[i][i] = (double)INT_MAX;
for(j = i+1; j < cities; j++)
{
length_table [i][j] = length_table[j][i] =sqrt(
(nodes[i].x - nodes[j].x) * (nodes[i].x - nodes[j].x) +
(nodes[i].y - nodes[j].y) * (nodes[i].y - nodes[j].y) );
//cout << length_table [i][j]<<endl;
}
}
ofstream out(argv[2]);
///////////////////////////////////////////////////////////初始設定
double t= initiall;//種群數量
int* temp = new int[cities]; answer* Ans1 = new answer;//群體
answer* Ans2 = new answer;//種群
int text[20] = initial;
int* son1 = new int[cities];
int* son2 = new int[cities];
for(int i = 0; i < cities; i++) {
temp[i] = i; Ans1->jie[i] = temp[i];
Ans2->jie[i] = text[i];
//cout << Ans2->jie[i]<<endl;
}
Ans1->length = f(Ans1->jie);
Ans2->length = f(Ans2->jie);
if(cities<15)Ans2->length =10000;
//cout << Ans2->length;
Ans1->i = random(cities);
//cout <<Ans1->i<<endl;
int pre_length = 0;
//
while(Ans1->length!=pre_length)//種群不再發生變化時停止
{
time(&tm);
double fenmu = 0;//輪盤賭法進行選擇
for(int i = 0; i < cities*cities; i++)
{
fenmu = fenmu + 1/Ans1->length;
}
int j1 = 0;double s1 = 0;int r1 = rand();
while(s1*32767<=r1) { s1 = s1 + (1/Ans1->length)/fenmu; j1++; }
int j2 = 0;double s2 = 0;int r2 = rand();
while(s2*32767<=r2) { s2 = s2 + (1/Ans1->length)/fenmu; j2++; }
if(tm-flag1>270)break;
pre_length = Ans1->length;
for(int i = 0; i < 100*cities; i++)//
{
int j = random(cities);
int text = temp[Ans1->i]; temp[Ans1->i] = temp[j]; temp[j] = text;
double length = f(temp);//f(j)
if(length < Ans1->length)
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
else if(p(length,Ans1->length,t)*32767 > rand())
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
}
t = t * pm;int point = random(cities);
//使用整數編碼的交配規則的常規交配法
for(int z = 0;z < point;z++) { son1[z] = Ans1->jie[z]; son2[z] = Ans1->jie[z]; }
int text1 = point;int text2 = point;int flag = 0;
for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son1[c])flag=1;
}
if(flag==0){ son1[text1] = Ans1->jie[x]; text1++; }
}

for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son2[c])flag=1;
}
if(flag==0){ son2[text2] = Ans1->jie[x]; text2++; }
}
if(Ans1->length<Ans2->length)
{
for(int m = 0; m < cities; m++)
Ans2->jie[m] = Ans1->jie[m];
Ans2->length = Ans1->length;
}
}
for(int l = 0; l < cities; l++)
{
out << char(Ans2->jie[l]+65)<<" ";
}
out <<Ans2->length<<endl;
return 0;
}

㈡ （轉）物流優化演算法處理流程及演算法服務平台建設

轉自：吉勍Personal

http://www.jiqingip.com/page9001?article_id=94

演算法處理流程

物流方向的大多數業務演算法處理流程基本是按照模型建立、演算法開發、演算法測試流程進行，具體步驟如下：

模型建立

大多數優化問題都能構建成線性規劃、非線性規劃或混合整數規劃等數學模型。這些模型需要根據實際業務確定，模型主要包含以下因素：

1）  優化目標

2）  決策變數

3）  約束條件

演算法開發

模型的求解可根據實際的業務情況（問題復雜程度、數據規模、計算時效要求）等採用合適的精確演算法和近似的最優化演算法進行求解。

模型精確計算

模型精確求解有一些商業和開源的求解器，如下：Gurobi、Cplex、SCIP、OR-Tools、Glpk等，可以根據實際情況選擇合適的求解器。

最優化演算法計算

最優化演算法也有很多，比如變鄰域搜索演算法、自適應大鄰域搜索演算法、禁忌搜索演算法、模擬退火演算法、遺傳演算法、蟻群優化演算法、粒子群優化演算法、人工魚群演算法、人工蜂群演算法等，可以根據適用情況選擇。

業務相關開放項目計算

解物流領域的某些項目可以利用一些開放性的項目來求解，如求解車輛路徑問題的jsprit、求解排程類問題的optaplanner等，這類問題在模型建立好之後可以調用這些開放性項目來求解。

演算法測試

生產數據測試

物流方向的項目基本都是優化類型的項目，每個項目對應的業務環節一直在運行，涉及到的優化問題或者是業務系統簡單處理，或者人為計算，對於演算法有效性的檢測可以把這部分生產數據獨立抽離出來，經過優化演算法計算之後跟原有系統數據進行相關的對比，來評價演算法的優化效果。

模擬測試

物流的優化不像互聯網應用可以採用流量灰度的方式進行直接的驗證，並且物流系統的鏈路非常長，單點的改變可能引起上下游的變化。在決策優化的過程中需要同時使用優化求解及模擬技術來驗證或提供決策依據。模擬測試驗證大致需要以下過程：

1）  定義模擬模型確定績效指標體系

2）  輸入演算法結果數據到模擬模型進行模擬計算

3）  根據模擬模型的模擬結果計算績效指標，以反饋演算法的優化效果。

演算法服務平台建設

實際業務中的很多應用場景都可以抽象成同一類演算法問題。演算法在解決不同應用場景業務問題時，相關模型、處理流程及計算方法也都大致相同，因此可以對這類問題的演算法，按照其處理流程從業務中剝離出來，封裝好演算法的輸入、輸出及計算邏輯，構建統一的演算法服務平台。

VRP演算法服務

比較經典的VRP問題就會應用到很多業務場景，即時配、大件配送、冷鏈配送、門店補貨等。這些業務場景對於大型零售商來說是比較常見的，因此構建可靈活配置的VRP演算法服務平台，可達成一次構建，多場景應用的效果。

排班演算法服務

排班問題也是一樣，無論是生產線工人排班、司機排班、客服排班還是門店工作人員排班，這些都是排班問題應用的業務場景。通過構建可靈活配置的排班演算法服務平台，可解決多個業務場景的排班問題。

裝箱演算法服務

裝箱問題也有著豐富的應用場景，無論是商品配送的車輛裝箱、運輸網路的車型推薦及包裝作業的包材推薦都是裝箱問題的業務場景。構建靈活的裝箱演算法服務平台，可通過配置有效的解決各業務場景的裝箱問題。

運籌規劃演算法服務

無論是上面提到的一些演算法服務還是其他組合優化問題，都可以構建成運籌優化問題來解決。大家熟知的google or-tools就是組合優化問題的工具包。我們也可以根據自身的業務特點構建適合業務場景的運籌規劃演算法服務，底層可以調用不同的求解器，可以是商業求解器，如gurobi、cplex等，也可以是開源求解器，如scip、glpk等；也可以是一些最優化演算法，如鄰域搜索等。

㈢ 什麼是禁忌搜索遺傳演算法

http://book.idoican.com.cn/detail/DefaultView.aspx?BookId=ISBN7-111-08090-4.1

㈣ 禁忌搜索演算法與傳統優化演算法的區別

背景：禁忌搜索演算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優的搜尋方法。在解決最優問題上，一般區分為兩種方式：一種是傳統的方法，另一種方法則是一些啟發式搜索演算法。
使用傳統的方法，我們必須對每一個問題都去設計一套演算法，相當不方便，缺乏廣泛性，優點在於我們可以證明演算法的正確性，我們可以保證找到的答案是最優的；而對於啟發式演算法，針對不同的問題，我們可以套用同一個架構來尋找答案，在這個過程中，我們只需要設計評價函數以及如何找到下一個可能解的函數等，所以啟發式演算法的廣泛性比較高，但相對在准確度上就不一定能夠達到最優，但是在實際問題中啟發式演算法那有著更廣泛的應用

㈤ 禁忌搜索演算法的簡介

又名「tabu搜索演算法」
為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。禁忌搜索就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較，珠穆朗瑪峰脫穎而出。
當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。

㈥ 禁忌搜索演算法的其他演算法

禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的.
遺傳演算法是基於生物進化的原理發展起來的一種廣為應用的、高效的隨機搜索與優化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴於梯度信息。
螞蟻演算法是群體智能可用於解決其他組合優化問題,比如有n個城市，需要對所有n個城市進行訪問且只訪問一次的最短距離。

㈦ 禁忌搜索演算法的介紹

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

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

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&gt;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的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。