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的资料就可以搞定了，当然最重要的是源程序