tsp禁忌搜索演算法

㈠ 禁忌搜索的禁忌搜索示例

組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於 n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌搜索則希望僅通過探索少數解來得到滿意的優化解。 可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、藐視准則、終止准則等是影響禁忌搜索演算法性能的關鍵。需要指出的是：
（1）首先，由於TS是局部領域搜索的一種擴充，因此領域結構的設計很關鍵，它決定了當前解的領域解的產生形式和數目，以及各個解之間的關系。
（2）其次，出於改善演算法的優化時間性能的考慮，若領域結構決定了大量的領域解（尤其對大規模問題，如TSP的SWAP操作將產生Cn2個領域解），則可以僅嘗試部分互換的結果，而候選解也僅取其中的少量最佳狀態。
（3）禁忌長度是一個很重要的關鍵參數，它決定禁忌對象的任期，其大小直接進而影響整個演算法的搜索進程和行為。同時，以上示例中，禁忌表中禁忌對象的替換是採用FIFO方式（不考慮藐視准則的作用），當然也可以採用其他方式，甚至是動態自適應的方式。
（4）藐視准則的設置是演算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。
（5）對於非禁忌候選狀態，演算法無視它與當前狀態的適配值的優劣關系，僅考慮它們中間的最佳狀態為下一步決策，如此可實現對局部極小的突跳（是一種確定性策略）。
（6）為了使演算法具有優良的優化性能或時間性能，必須設置一個合理的終止准則來結束整個搜索過程。 此外，在許多場合禁忌對象的被禁次數（frequency）也被用於指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。

㈡ 把這偽碼改成JAVA或C#

恩翻譯過來是： 第一個是：模擬退火算，：第二個是：遺傳演算法，第三個是：禁忌搜索演算法（又叫「tabu搜索演算法」）.說白了你的意思就是用JAVA或者C#來實現這些演算法，這些東西你隨便 網路或者google一下文章多的是。這里我貼一個 C#實現一個模擬退火演算法求TSP問題 希望對你有幫助。（不知道你從哪看來的這些 。。- -多多交流：JAVA交流群：53308744 ，C#交流群：62464919）// ******************************************************************************************
// 物體降溫退火過程中，其能量轉移服從Boltzmann distribution規律 P(E) ∝ exp(-E/kT);
// P(E)是系統處於低能E的概率(probability)，k為Boltzmann常數，T為系統溫度。
// 模擬退火演算法原理
// (1)初始溫度T(0) = T0。迭代次數t=0，任意初始狀態做當前解V(0)∈V
// (2)按某一規則有當前狀態產生當前狀態的下一次侯選狀態。
// 計算目標代價變化△C，若△C<0則接受解，(△ delta)
// 否則考慮當前溫度下狀態活動概率 P(△C) = exp(-△C/T);P(△C)≥λ則接受解，否則不接受
// λ(lambda)為預先指定或隨機產生的正數。 (0<λ<1)
// (3)按某種策略對T更新（降溫）。
// (4)按某種標准檢查退火過程是否應該結束，若不滿足則轉(2)
// (5)輸出狀態V(t)做問題解
// ******************************************************************************************

using System;
using System.Drawing;

namespace Algorithm.SimulatedAnnealing
{
public class TravellingSalesmanProblem
{
private Point[] _points;
private double[,] _distanceMatrix;
private double _initialTemperature = 0d;
private double _currentTemperature = 0d;

private int _routerCount;

private int[] _currentRouter;
private int[] _resultRouter;

private Random _rdm;
private bool _IsCalculated = false;
private DateTime calculate_begin;
private DateTime calculate_end;

public TravellingSalesmanProblem(Point[] pts)
{
_points = (Point[])pts.Clone();

_routerCount = _points.Length;
_currentRouter = new int[_routerCount];
_resultRouter = new int[_routerCount];
_distanceMatrix = new double[_routerCount, _routerCount];

_rdm = new Random((int)DateTime.Now.Ticks);

double minDistance = 10000d;
double maxDistance = 0d;

for(int i = 0; i < _points.Length; i++)
{
_currentRouter[i] = i; // init point router 1 > 2 > 3 > n
_resultRouter[i] = i;
for(int j = i + 1; j < _points.Length; j++)
{
double offsetX = (double)(_points[i].X - _points[j].X);
double offsetY = (double)(_points[i].Y - _points[j].Y);
double distance = Math.Sqrt(offsetX * offsetX + offsetY * offsetY); //計算兩點間的距離
_distanceMatrix[i, j] = distance;
_distanceMatrix[j, i] = distance;
if(distance > maxDistance) maxDistance = distance;
if(distance < minDistance) minDistance = distance;
}
}
_initialTemperature = 20 * (_routerCount * maxDistance - _routerCount * minDistance);// 計算起始溫度
_currentTemperature = _initialTemperature;
}

// 得出最優距離
public double GetTotalDistancOptimization()
{
if(!_IsCalculated)
Calculation();
return CalculateTotalDistance(_resultRouter);
}

// 得到最優路由
public int[] GetRouterOptimization()
{
if(!_IsCalculated)
Calculation();
return _resultRouter;
}

public double GetCalculationalTime()
{
if(_IsCalculated)
{
TimeSpan span = calculate_end - calculate_begin;
return span.TotalMilliseconds;
}
else
return 0d;
}

// 求出最優解
private void Calculation()
{
//Random rdm = new Random((int)DateTime.Now.Ticks);
calculate_begin = DateTime.Now;
while(true)
{
int IterCount = 0;
while(true)
{
double totalDistance1 = CalculateTotalDistance(_resultRouter);
BuildRandomRouter(); // change router
double totalDistance2 = CalculateTotalDistance(_currentRouter); double deltaTotalDistance = totalDistance2 - totalDistance1;//delta
//原理見頂部注釋
if(deltaTotalDistance <= 0d)
{
for(int i = 0; i < _resultRouter.Length; i++)
_resultRouter[i] = _currentRouter[i];//賦值到結果路由
}
else
{
//原理見頂部注釋
double probability = Math.Exp( -(deltaTotalDistance/_currentTemperature));
double lambda = ((double)(_rdm.Next() % 10000)) / 10000d;//隨機指定的正數lambda
if(probability > lambda)
{
for(int i = 0; i < _resultRouter.Length; i++)
_resultRouter[i] = _currentRouter[i];
}
}
if(IterCount >= _routerCount * _routerCount * _routerCount) //某一溫度下的循環次數是點個數的三次方
{
break;
}
else
{
IterCount++;
}
}
if(_currentTemperature <= 0.01) //溫度小於等於0.01時跳出外循環
{
break;
}
else
{
_currentTemperature = 0.96 * _currentTemperature;// 溫度下降方式 T（k+1） = K*T（k），K=0.95
}
}
_IsCalculated = true;
calculate_end = DateTime.Now;
} private double CalculateTotalDistance(int[] router)
{
double totalDistance = 0d;
for(int i = 0; i < router.Length - 1; i++)
{
totalDistance += _distanceMatrix[router[i], router[i + 1]];
}
totalDistance += _distanceMatrix[_currentRouter[router.Length - 1], router[0]];
return totalDistance;
} // 按某種概率過程產生新的搜索狀態
// 隨機產生一個新的路由
private void BuildRandomRouter()
{
int rdm1, rdm2;
while(true)
{
rdm1 = _rdm.Next() % _currentRouter.Length - 1;
if(rdm1 >= 0) break;
}
while(true)
{
rdm2 = _rdm.Next() % _currentRouter.Length - 1;
if(rdm1 != rdm2 && rdm2 >= 0)
{
int temp = _currentRouter[rdm1];
_currentRouter[rdm1] = _currentRouter[rdm2];
_currentRouter[rdm2] = temp;
break;
}
}
} }
}

㈢ 向大神求兩道計算機方面的題！

建議將問題發到美國麻省理工學院詢問。

㈣ 數學建模-方法合集

線性規劃（Linear programming,簡稱LP）是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法。研究線性約束條件下線性目標函數的極值問題的數學理論和方法。英文縮寫LP。它是運籌學的一個重要分支，廣泛應用於軍事作戰、經濟分析、經營管理和工程技術等方面。為合理地利用有限的人力、物力、財力等資源作出的最優決策，提供科學的依據。

0-1規劃是決策變數僅取值0或1的一類特殊的整數規劃。在處理經濟管理中某些規劃問題時，若決策變數採用 0-1變數即邏輯變數，可把本來需要分別各種情況加以討論的問題統一在一個問題中討論。

蒙特卡羅法(Monte Carlo method)是以概率與統計的理論、方法為基礎的一種計算方法，蒙特卡羅法將所需求解的問題同某個概率模型聯系在一起，在電子計算機上進行隨機模擬，以獲得問題的近似解。因此，蒙特卡羅法又稱隨機模擬法或統計試驗法。

在生活中經常遇到這樣的問題，某單位需完成n項任務，恰好有n個人可承擔這些任務。由於每人的專長不同，各人完成任務不同(或所費時間)，效率也不同。於是產生應指派哪個人去完成哪項任務，使完成n項任務的總效率最高(或所需總時間最小)。這類問題稱為指派問題或分派問題。

無約束最優化方法是求解無約束最優化問題的方法，有解析法和直接法兩類。

解析法

解析法就是利用無約束最優化問題中目標函數 f(x) 的解析表達式和它的解析性質（如函數的一階導數和二階導數），給出一種求它的最優解 x 的方法，或一種求 x 的近似解的迭代方法。

直接法

直接法就是在求最優解 x*的過程中，只用到函數的函數值，而不必利用函數的解析性質，直接法也是一種迭代法，迭代步驟簡單，當目標函數 f(x) 的表達式十分復雜，或寫不出具體表達式時，它就成了重要的方法。

可用來解決管路鋪設、線路安裝、廠區布局和設備更新等實際問題。基本內容是：若網路中的每條邊都有一個數值（長度、成本、時間等），則找出兩節點（通常是源節點和阱節點）之間總權和最小的路徑就是最短路問題。 [1]

例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹

管道網路中每條邊的最大通過能力（容量）是有限的，實際流量不超過容量。

最大流問題(maximum flow problem)，一種組合最優化問題，就是要討論如何充分利用裝置的能力，使得運輸的流量最大，以取得最好的效果。求最大流的標號演算法最早由福特和福克遜與與1956年提出，20世紀50年代福特(Ford)、(Fulkerson)建立的「網路流理論」，是網路應用的重要組成成分。

最小費用最大流問題是經濟學和管理學中的一類典型問題。在一個網路中每段路徑都有「容量」和「費用」兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經過路徑的流量，可以在流量最大的前提下，達到所用的費用最小的要求。如n輛卡車要運送物品，從A地到B地。由於每條路段都有不同的路費要繳納，每條路能容納的車的數量有限制，最小費用最大流問題指如何分配卡車的出發路徑可以達到費用最低，物品又能全部送到。

旅行推銷員問題（英語：Travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。它是組合優化中的一個NP困難問題，在運籌學和理論計算機科學中非常重要。

最早的旅行商問題的數學規劃是由Dantzig（1959）等人提出，並且是在最優化領域中進行了深入研究。許多優化方法都用它作為一個測試基準。盡管問題在計算上很困難，但已經有了大量的啟發式演算法和精確方法來求解數量上萬的實例，並且能將誤差控制在1%內

計劃評審法(Program Evaluation and Review Technique，簡稱PERT)，是指利用網路分析制訂計劃以及對計劃予以評價的技術。它能協調整個計劃的各道工序，合理安排人力、物力、時間、資金，加速計劃的完成。在現代計劃的編制和分析手段上，PERT被廣泛使用，是現代化管理的重要手段和方法。

關鍵路線法(Critical Path Method，CPM)，又稱關鍵線路法。一種計劃管理方法。它是通過分析項目過程中哪個活動序列進度安排的總時差最少來預測項目工期的網路分析。

人口系統數學模型，用來描述人口系統中人的出生、死亡和遷移隨時間變化的情況，以及它們之間定量關系的數學方程式或方程組，又稱人口模型。

初值問題是指在自變數的某值給出適當個數的附加條件，用來確定微分方程的特解的這類問題。

如果在自變數的某值給出適當個數的附加條件，用來確定微分方程的特解，則這類問題稱為初值問題。

邊值問題是定解問題之一，只有邊界條件的定解問題稱為邊值問題。二階偏微分方程(組)一般有三種邊值問題：第一邊值問題又稱狄利克雷問題，它的邊界條件是給出未知函數本身在邊界上的值；第二邊值問題又稱諾伊曼邊值問題或斜微商問題，它的邊界條件是給出未知函數關於區域邊界的法向導數或非切向導數；第三邊值問題又稱魯賓問題，它的邊界條件是給出未知函數及其非切向導數的組合

目標規劃是一種用來進行含有單目標和多目標的決策分析的數學規劃方法。線性規劃的一種特殊類型。它是在線性規劃基礎上發展起來的，多用來解決線性規劃所解決不了的經濟、軍事等實際問題。它的基本原理、數學模型結構與線性規劃相同，也使用線性規劃的單純形法作為計算的基礎。所不同之處在於，它從試圖使目標離規定值的偏差為最小入手解題，並將這種目標和為了代表與目標的偏差而引進的變數規定在表達式的約束條件之中。

時間序列（或稱動態數列）是指將同一統計指標的數值按其發生的時間先後順序排列而成的數列。時間序列分析的主要目的是根據已有的歷史數據對未來進行預測。

支持向量機(Support Vector Machine，SVM)是Corinna Cortes和Vapnik等於1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現出許多特有的優勢，並能夠推廣應用到函數擬合等其他機器學習問題中。

在機器學習中，支持向量機（SVM，還支持矢量網路）是與相關的學習演算法有關的監督學習模型，可以分析數據，識別模式，用於分類和回歸分析。

聚類分析法是理想的多變數統計技術，主要有分層聚類法和迭代聚類法。 聚類分析也稱群分析、點群分析，是研究分類的一種多元統計方法。

例如，我們可以根據各個銀行網點的儲蓄量、人力資源狀況、營業面積、特色功能、網點級別、所處功能區域等因素情況，將網點分為幾個等級，再比較各銀行之間不同等級網點數量對比狀況。

成分分析（Principal Component Analysis，PCA）， 是一種統計方法。通過正交變換將一組可能存在相關性的變數轉換為一組線性不相關的變數，轉換後的這組變數叫主成分。

在實際課題中，為了全面分析問題，往往提出很多與此有關的變數（或因素），因為每個變數都在不同程度上反映這個課題的某些信息。

主成分分析首先是由K.皮爾森（Karl Pearson）對非隨機變數引入的，爾後H.霍特林將此方法推廣到隨機向量的情形。信息的大小通常用離差平方和或方差來衡量。

因子分析是指研究從變數群中提取共性因子的統計技術。最早由英國心理學家C.E.斯皮爾曼提出。他發現學生的各科成績之間存在著一定的相關性，一科成績好的學生，往往其他各科成績也比較好，從而推想是否存在某些潛在的共性因子，或稱某些一般智力條件影響著學生的學習成績。因子分析可在許多變數中找出隱藏的具有代表性的因子。將相同本質的變數歸入一個因子，可減少變數的數目，還可檢驗變數間關系的假設。

判別分析又稱「分辨法」，是在分類確定的條件下，根據某一研究對象的各種特徵值判別其類型歸屬問題的一種多變數統計分析方法。

其基本原理是按照一定的判別准則，建立一個或多個判別函數，用研究對象的大量資料確定判別函數中的待定系數，並計算判別指標。據此即可確定某一樣本屬於何類。

當得到一個新的樣品數據，要確定該樣品屬於已知類型中哪一類，這類問題屬於判別分析問題。

對互協方差矩陣的一種理解，是利用綜合變數對之間的相關關系來反映兩組指標之間的整體相關性的多元統計分析方法。它的基本原理是：為了從總體上把握兩組指標之間的相關關系，分別在兩組變數中提取有代表性的兩個綜合變數U1和V1（分別為兩個變數組中各變數的線性組合），利用這兩個綜合變數之間的相關關系來反映兩組指標之間的整體相關性。

對應分析也稱關聯分析、R-Q型因子分析，是近年新發展起來的一種多元相依變數統計分析技術，通過分析由定性變數構成的交互匯總表來揭示變數間的聯系。可以揭示同一變數的各個類別之間的差異，以及不同變數各個類別之間的對應關系。

對應分析主要應用在市場細分、產品定位、地質研究以及計算機工程等領域中。原因在於，它是一種視覺化的數據分析方法，它能夠將幾組看不出任何聯系的數據，通過視覺上可以接受的定點陣圖展現出來。

多維標度法是一種將多維空間的研究對象(樣本或變數)簡化到低維空間進行定位、分析和歸類，同時又保留對象間原始關系的數據分析方法。

在市場營銷調研中，多維標度法的用途十分廣泛。被用於確定空間的級數(變數、指標)，以反映消費者對不同品牌的認知，並且在由這些維構築的空間中，標明某關注品牌和消費者心目中理想品牌的位置。

偏最小二乘法是一種數學優化技術，它通過最小化誤差的平方和找到一組數據的最佳函數匹配。 用最簡的方法求得一些絕對不可知的真值，而令誤差平方之和為最小。 很多其他的優化問題也可通過最小化能量或最大化熵用最小二乘形式表達。

系統介紹了禁忌搜索演算法、模擬退火演算法、遺傳演算法、蟻群優化演算法、人工神經網路演算法和拉格朗日鬆弛演算法等現代優化計算方法的模型與理論、應用技術和應用案例。

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

模擬退火演算法來源於固體退火原理，是一種基於概率的演算法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。

傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳演算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(indivial)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭發的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。

The Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) is a multi-criteria decision analysis method, which was originally developed by Hwang and Yoon in 1981[1] with further developments by Yoon in 1987,[2] and Hwang, Lai and Liu in 1993.[3] TOPSIS is based on the concept that the chosen alternative should have the shortest geometric distance from the positive ideal solution (PIS)[4] and the longest geometric distance from the negative ideal solution (NIS).[4]

TOPSIS是一種多准則決策分析方法，最初由Hwang和Yoon於1981年開發[1]，1987年由Yoon進一步開發，[2]和Hwang， 1993年賴和劉。[3] TOPSIS是基於這樣一個概念，即所選擇的方案應該具有離正理想解（PIS）最短的幾何距離[4]和距負理想解（NIS）最遠的幾何距離[4]。

模糊綜合評價法是一種基於模糊數學的綜合評價方法。該綜合評價法根據模糊數學的隸屬度理論把定性評價轉化為定量評價，即用模糊數學對受到多種因素制約的事物或對象做出一個總體的評價。它具有結果清晰，系統性強的特點，能較好地解決模糊的、難以量化的問題，適合各種非確定性問題的解決。

數據包絡分析方法(Data Envelopment Analysis,DEA)是運籌學、管理科學與數理經濟學交叉研究的一個新領域。它是根據多項投入指標和多項產出指標，利用線性規劃的方法，對具有可比性的同類型單位進行相對有效性評價的一種數量分析方法。DEA方法及其模型自1978年由美國著名運籌學家A.Charnes和W.W.Cooper提出以來，已廣泛應用於不同行業及部門，並且在處理多指標投入和多指標產出方面，體現了其得天獨厚的優勢。

對於兩個系統之間的因素，其隨時間或不同對象而變化的關聯性大小的量度，稱為關聯度。在系統發展過程中，若兩個因素變化的趨勢具有一致性，即同步變化程度較高，即可謂二者關聯程度較高；反之，則較低。因此，灰色關聯分析方法，是根據因素之間發展趨勢的相似或相異程度，亦即「灰色關聯度」，作為衡量因素間關聯程度的一種方法。

主成分分析也稱主分量分析，旨在利用降維的思想，把多指標轉化為少數幾個綜合指標（即主成分），其中每個主成分都能夠反映原始變數的大部分信息，且所含信息互不重復。這種方法在引進多方面變數的同時將復雜因素歸結為幾個主成分，使問題簡單化，同時得到的結果更加科學有效的數據信息。在實際問題研究中，為了全面、系統地分析問題，我們必須考慮眾多影響因素。這些涉及的因素一般稱為指標，在多元統計分析中也稱為變數。因為每個變數都在不同程度上反映了所研究問題的某些信息，並且指標之間彼此有一定的相關性，因而所得的統計數據反映的信息在一定程度上有重疊。主要方法有特徵值分解，SVD，NMF等。

秩和比法（Rank-sum ratio，簡稱RSR法），是我國學者、原中國預防醫學科學院田鳳調教授於1988年提出的，集古典參數統計與近代非參數統計各自優點於一體的統計分析方法，它不僅適用於四格表資料的綜合評價，也適用於行×列表資料的綜合評價，同時也適用於計量資料和分類資料的綜合評價。

灰色預測是就灰色系統所做的預測

灰色預測是一種對含有不確定因素的系統進行預測的方法。灰色預測通過鑒別系統因素之間發展趨勢的相異程度，即進行關聯分析，並對原始數據進行生成處理來尋找系統變動的規律，生成有較強規律性的數據序列，然後建立相應的微分方程模型，從而預測事物未來發展趨勢的狀況。其用等時距觀測到的反應預測對象特徵的一系列數量值構造灰色預測模型，預測未來某一時刻的特徵量，或達到某一特徵量的時間。

回歸分析預測法，是在分析市場現象自變數和因變數之間相關關系的基礎上，建立變數之間的回歸方程，並將回歸方程作為預測模型，根據自變數在預測期的數量變化來預測因變數關系大多表現為相關關系，因此，回歸分析預測法是一種重要的市場預測方法，當我們在對市場現象未來發展狀況和水平進行預測時，如果能將影響市場預測對象的主要因素找到，並且能夠取得其數量資料，就可以採用回歸分析預測法進行預測。它是一種具體的、行之有效的、實用價值很高的常用市場預測方法，常用於中短期預測。

包含未知函數的差分及自變數的方程。在求微分方程 的數值解時，常把其中的微分用相應的差分來近似，所導出的方程就是差分方程。通過解差分方程來求微分方程的近似解，是連續問題離散化 的一個例子。

馬爾可夫預測法主要用於市場佔有率的預測和銷售期望利潤的預測。就是一種預測事件發生的概率的方法。馬爾科夫預測講述了有關隨機變數 、 隨機函數與隨機過程。

邏輯性的思維是指根據邏輯規則進行推理的過程；它先將信息化成概念，並用符號表示，然後，根據符號運算按串列模式進行邏輯推理；這一過程可以寫成串列的指令，讓計算機執行。然而，直觀性的思維是將分布式存儲的信息綜合起來，結果是忽然間產生想法或解決問題的辦法。這種思維方式的根本之點在於以下兩點：1.信息是通過神經元上的興奮模式分布儲在網路上；2.信息處理是通過神經元之間同時相互作用的動態過程來完成的。

中文名 神經網路演算法 外文名 Neural network algorithm

㈤ 禁忌搜索演算法淺析

姓名：劉家沐

學號：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．終止規則不以達到局部最優為終止規則，而以最大迭代次數、出現頻率限制或者目標值偏離成都為終止規則

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

㈥ LKH（Lin-Kernighan heuristic ）一種求TSP的鄰域搜索策略

PART I 引入

題主應該指的是1973年的針對TSP的LKH演算法。LKH演算法類似於k-opt方法，常見的2-opt作為一種local search的思想題主應該是知道的，（2-opt的基本變換2-interchange如下圖）。

那麼k-opt的過程，也可以element by element，也就可以通過不計順序的δ-path之間的uv-switch來實現，每個合適的k-opt裡面的exchange都是總和為正的增益值，那麼其每一個合適的exchange的一部分都可以被uv-switch達到，所以可以令每次的G*都大於0，作為stoppingcriteria，從邏輯上來說是合理的，符合作者的element by element，在啟發式所謂的exploitation上也有好的表現力。END

P.S element by element這種思想在其他的演算法也有體現，比如遺傳演算法的改進上也有比如單位點交叉防止收斂解震動。

其他演算法效能上的提升考慮，請依次閱讀文獻[2][1]及其他相關的資料。

綜上，LKH是可以認為基於k-opt成功的改進，無論是運行的速度上，還是搜索的精度上。它在解決TSP問題上，速度和精度上仍舊有較好的表現。

水平有限，隨緣回答，若有錯誤，請指出評論，謝謝！

參考文獻：

理解演算法框架內容，文獻[1]是較好的參考資料，理解演算法細節、討論，可以參考文獻[2]，其指出了backtracking的要求（從數值實驗/作者思考的philosophy上指出：應該從最多幾層開始backtracking，每層y_1, y_2contenders的數量如何，如何進一步refinements，每一次δ-path 變換中y_i怎麼高效選取等問題）

[1] Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.Combinatorial Optimization

[2] S. Lin, B. W. Kernighan,An effective heuristic algorithm for the traveling salesman problem

㈦ tSp Concorder演算法原理

tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。

㈧ 禁忌搜索的局部領域搜索

局部領域搜索是基於貪婪思想持續地在當前解的領域中進行搜索，雖然演算法通用易實現，且容易理解，但其搜索性能完全依賴於領域結構和初解，尤其窺陷入局部極小而無法保證全局優化性。針對局部領域搜索，為了實現全局優化，可嘗試的途徑有：以可控性概率接受劣解來逃逸局部極小，如模擬退火演算法；擴大領域搜索結構，如TSP的2opt擴展到k-opt；多點並行搜索，如進化計算；變結構領域搜索（ Mladenovic et al,1997）；另外，就是採用TS的禁忌策略盡量避免迂迴搜索，它是一種確定性的局部極小突跳策略。
禁忌搜索是人工智慧的一種體現，是局部領域搜索的一種擴展。禁忌搜索最重要的思想是標記對應已搜索的局部最優解的一些對象，並在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環），從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及到鄰域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）、藐視准則（aspiration criterion）等概念;

㈨ 約束條件是怎麼加入禁忌搜索演算法中的

組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌

㈩ 數學建模物流配送問題！

我現在正在解決類似的問題，演算法有很多種，我用的是禁忌搜索演算法，當然還有模擬退火演算法啥的，這類問題都是TSP問題，你查關於TSP的資料就可以搞定了，當然最重要的是源程序