2邻域搜索算法

⑴ 智能计算/计算智能、仿生算法、启发式算法的区别与关系

我一个个讲好了，
1）启发式算法：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。意思就是说，启发式算法是根据经验或者某些规则来解决问题，它求得的问题的解不一定是最优解，很有可能是近似解。这个解与最优解近似到什么程度，不能确定。相对于启发式算法，最优化算法或者精确算法（比如说分支定界法、动态规划法等则能求得最优解）。元启发式算法是启发式算法中比较通用的一种高级一点的算法，主要有遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法、变邻域搜索算法、人工神经网络、人工免疫算法、差分进化算法等。这些算法可以在合理的计算资源条件下给出较高质量的解。
2）仿生算法：是一类模拟自然生物进化或者群体社会行为的随机搜索方法的统称。由于这些算法求解时不依赖于梯度信息，故其应用范围较广，特别适用于传统方法难以解决的大规模复杂优化问题。主要有：遗传算法、人工神经网络、蚁群算法、蛙跳算法、粒子群优化算法等。这些算法均是模仿生物进化、神经网络系统、蚂蚁寻路、鸟群觅食等生物行为。故叫仿生算法。
3）智能计算：也成为计算智能，包括遗传算法、模拟退火算法、禁忌搜索算法、进化算法、蚁群算法、人工鱼群算法，粒子群算法、混合智能算法、免疫算法、神经网络、机器学习、生物计算、DNA计算、量子计算、模糊逻辑、模式识别、知识发现、数据挖掘等。智能计算是以数据为基础，通过训练建立联系，然后进行问题求解。
所以说，你接触的很多算法，既是仿生算法，又是启发式算法，又是智能算法，这都对。分类方法不同而已。

这次楼主不要再老花了哈！

⑵ 什么是局部搜索算法

局部搜索算法是从爬山法改进而来的。
简单来说，局部搜索算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。
在计算机科学中，局部搜索是解决最优化问题的一种元启发式算法。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。
1、局部搜索算法的基本思想：
在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
2、局部搜索的优点：
简单、灵活及易于实现，缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。
3、局部搜索广泛应用：
计算机科学（主要是人工智能）、数学、运筹学、工程学、生物信息学中各种很难找到全局最优解的计算问题。

⑶ 邻域法人工神经网络矿产储量计算

李裕伟

（中国地质矿产信息研究院，北京100812）

李林松

（北京计算机一厂，北京100083）

摘要人工神经网络（ANN）技术是一种可用于模式识别的新技术。本文介绍用ANN技术进行矿产储量计算的方法，这种方法基于邻域而不是整个研究区的信息，因而能保证迭代过程的成功。这一ANN方法在一个品位变化很大且样品分布极不规则的金矿床应用后，取得了令人满意的结果。本文还对ANN方法与克里格法的应用效果进行了对比。

关键词储量估计人工神经网络地质统计学邻域

1引言

到目前为止，主要有两种用于储量计算的空间插值方法：距离倒数法和克立格法。前者简便易行，但忽略地质因素的变化；后者不仅考虑到样品的空间构形，而且还考虑到矿床的地质条件变化。在应用克立格法时地质学家往往遇到一些难题，如建立不起合适的变差函数、存在非平稳性等。吴希平和周迎新（1993）曾使用人工神经网络技术估计矿产储量。这显然是一个很好的开端，因为ANN技术同时具备距离倒数法和克立格法的优点：既简便易行，又考虑了地质条件变化。此外，在用ANN方法估计储量时，无需考虑诸如变差函数、平稳性之类的问题。吴希平和周迎新使用ANN方法的范围是整个研究区，全部样品只有48件。如果样品数增加，如超过100件，或者数据构形比较复杂，则将很难达到一个ANN的储量估计解。为了解决上述问题，笔者设计了一个新的估计储量的ANN方案，这种方案基于邻域信息而不是全区信息。

2领域定义

在使用ANN方法估计矿床储量时，之所以使用邻域信息而不是全区信息有两点考虑。其一是对块段的估值只受其邻域样品的影响，因而不需要利用全区样品；其二是只有在一个小的样品集的条件下，ANN迭代作业才有可能取得成功。当使用的样品太多时，ANN的迭代过程可能难以收敛；而当样品数较少时，收敛的可能性加大。据笔者的经验，当样品数少于50时，ANN作业可以顺利地进行。简言之，我们之所以需要一个邻域，是为了从全部样品集中抽取一个有效的数据子集，以便用ANN方法成功地进行块段储量的估计。

在用ANN方法进行储量估计时，邻域的定义与克立格法相似。首先，设计一个由规则块段组成的网络系统。这样问题就化为据某块段邻域内若干样品的观测值来估计该块段的值。为简化起见，可将邻域定义为一个矩形（图1）。该矩形邻域中的样品被用于进行被估块段的储量估计。为了更精确地进行块段估值，可在被估块段中设置若干个估值点。ANN程序对该块段的每个估值点返回一个值。这些估值点的平均值即为该块段的估值（图2）。

图1邻域定义

图2样品及估值

对邻域的大小可以调整，直到其包含50件样品为止。影响块段估值精度的因素有三个。其一是邻域中样品的数据构形。如果样品分布比较均匀，则可能得到一个令人满意的ANN估值。其二是样品的密度。当邻域内有较多样品时，ANN程序将返回一个具有较小误差的估值。其三是输入变量的空间变化。一个空间高度波动起伏的变量将导致较大的估值误差。

3ANN模型

人工神经网络方法是近年来迅速发展的人工智能技术之一，它已被成功地用于模式识别。这一技术的吸引力在于：应用ANN的地质学家需要做的事仅仅是对输入层和输出层进行分析。换句话说，人们无需去研究在输入层和输出层之间所发生的事情，因为那些隐蔽层可以被视为一个“黑箱”。这样一来，需要人们做的仅仅是理解输入与输出的事件，这对地质学家来说恰恰是比较熟悉、比较容易的事；而在输入与输出之间存在的那些极复杂的非线性关系及巨量的计算任务，则交给计算机去处理，这些工作恰恰是人所难以承担的。从这一观点出发，使用ANN技术进行储量估计的地质学家就可以避免遇到许多使用克立格法时所难以解决的问题。

块段估值是一个空间模式识别过程。考虑到上述的ANN技术的优点和前人的启发性工作，本文尝试使用这一新的模式识别技术进行二维储量估计。

所设计的ANN结构包含一个输入层、两个隐蔽层和一个输出层。输入层包含三个变量：x坐标、y坐标和邻域的品位平均值。所谓邻域的品位平均值指的是用最近的四个样品据距离倒数法计算的平均值。在两个隐蔽层中，每层均含有5个神经元。输出层只包含一个变量，即所估计点的矿石品位。图3表示了这一ANN结构。

图3ANN结构

令x_i为下一层第i个神经元的输入值，x_j为上一层第j个神经元的初始输出值，w_ij为下一层第i个神经元和上一层第j个神经元的联结权，则可建立起m个输入神经元和第j个输出神经元之间的关系。

数学地质和地质信息

然后使用以下特性函数

数学地质和地质信息

将初始输出值x_j转换为适配输出值x_j。

所使用的学习算法为简单的反向传播法（BP），其权系数调整方程为

数学地质和地质信息

此方程被用来修改权系数，使其从当前值被修改成下一步的值。式中k为当前所处的迭代次数，η为学习率，δ_j为第j个输出神经元的当前值同其目标值之差，x_j为第j个神经元在第k次迭代中获得的适配输出值。

虽然还可采用一些改进的BP算法或其他更复杂的学习算法，但由于简单的BP算法已能很好地解决本文的问题，因此就不打算再讨论和使用其他的学习算法。

4实例研究

上述的ANN方法被用于研究河南的J矿床。这是一个石英脉型金矿床，以坑探为主，辅之少量钻孔控制。共取得250件样品（图4）。样品分布极不均匀，金品位变化很大。因此，这是一个难以用一般插值方法进行空间描述的矿床。为便于对比，用克立格法和人工神经网络方法对矿床的品位按同一块段系统进行了估计。块段系统由25×9个克立格块段组成，每个克立格块段的大小为50m×50m。被估块段加上由50个样品构成邻近块段组成邻域。每个被估块段有3×3个估值点。根据这些邻域参数与样品数据，我们可以用前面定义的ANN模型来逐个块段地估计金品位。达到指定精度的迭代次数变化范围很大，取决于邻域中样品的数目、构形和变量的空间变化。所设置的临界迭代误差为0.001。当实际的迭代误差小于该临界误差时，迭代过程结束。大多数迭代过程在迭代10000～30000次时终止，但最大迭代次数可达100000次。ANN程序对每个块段的3×3个离散估值点各返回一个金品位估值，再由它们生成块段的平均值。离散点估值及块段平均值都是ANN品位估值的重要结果。

图4样品点位图

图2显示了该金矿床的一个块段。为了便于清晰地了解样品与估值点的关系，只显示了其邻域的一部分。这个部分邻域包含了11个样品，但它们对该块段的估值无疑是最重要的。图中9个小矩形代表估值点。可以看出，ANN程序对每个估值点都返回了一个合理的值。每个估值点的值均同其最近的样品值吻合得很好。由图2还可以看出，用ANN方法所求得的点上的估值仅由最邻近的几个样品所确定，远离该估值点的样品对估值的影响可忽略不计。这就是为什么在使用ANN方法对一个点或块段进行估值时只需邻域而无需整个研究区的理由。对图2所示块段邻域的ANN学习信息列于表1。在通过学习得到权值后，将每个估值点的x坐标、y坐标及邻域平均值代入公式（1）计算初始输出值；然后再将初始输出值代入公式（2）求得适配输出值。对该块段的点估值列于表2。

表1图2所示块段的学习信息

图5和图6分别显示了对整个矿床的点估值与块段估值。可以看出，图6的点估值更好地刻画了该矿床的金品位分布细节。这一点同克立格法的估值结果有很大的区别。一般说来，克立格法的点估值同块段估值区别不大，这是因为克立格法无论是对点估值还是块段估值都会产生很强的圆滑效应，但ANN块段估值却不会产生这么强的圆滑效应。将ANN块段估值（图5）同克立格块段估值（图7）进行对比，虽然全矿床的平均品位非常接近，据ANN法为2.59375，据克立格法为2.49658，但可明显看到克立格法的估值图像被大大地圆滑了。我们知道，地质统计学提供了两种研究空间数据的模型：其一是克立格法模型，它被用来估计一个区域化变量的局域平均值，但不忠实于其空间的变化细节；其二是条件模拟模型，它被用来仔细地刻画一个区域化变量的空间变化，但不能保证得到一个最优的、无偏的局域平均值。ANN方法看来综合了这两种模型的优点，对点估计而言尤其如此。一个ANN制图过程所产生的点估值的空间变化同实际样品的空间变化十分相近。当然，样品点愈密集，点估值的特征与实际特征就愈接近。

表2图2所示块段的点估值

图5ANN法金品位块段估值品位单位：g/t

图6ANN法金品位点估值品位单位：g/t

图7克立格法金品位块段估值品位单位：g/t

为了说明ANN估计的优点，可将图6的ANN点估值同图4的实际样品点位图进行对比。在仔细地研究图上的ANN点估值及其邻域的样品值之间的关系后可以看出，它们之间是非常吻合的。这就表明，ANN可以作为估计矿产储量的一个非常有效的工具。

5结论

人工神经网络技术是一种新的、有效地估计矿产储量的方法。在整个研究区内定义一个估计局域品位的ANN作业可能遭到失败；但如果定义在一个较小的邻域内则可以取得成功。同地质统计学相比，ANN产生的品位图由于圆滑效应很小，更接近于品位空间分布的实际情况。此外，地质学家不再需要为诸如非平稳性、非正态性、非线性、各向异性、不良变差函数等问题而烦恼。应用ANN技术估计矿产储量的主要问题是无法通过ANN方法本身提供估值误差。

参考文献

[1]J.Hertz,A.Krogh,R.G.Palmer.Introction to the Theory of Neural Computation.Addison-Wesley Publ.co.,Redwood City,California,1991.

[2]Xiping Wu and Yingxin Zhou.Reserve Estimation Using Neural Network Techniques.Computers ＆ Geosciences,1993,19（4）.

⑷ 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

⑸ 极小，怎么造句

极小，亦称为最小，最小值。在数学分析中，在给定范围内（相对极值）或函数的整个域（全局或绝对极值），函数的最大值和最小值被统称为极值（极数）。按照该词义造句有：

1, 他脸上的胡子卷成许多极小的圆圈，像是沼地上的青苔。

2，幸福不表现为造成别人的哪怕是极小的一点痛苦，而表现为直接促成别人的快乐和幸福。照我看来，它在这一方面可以最为简明地表达为：幸福在于勿恶、宽恕和热爱他人。托尔斯泰

3，在显微镜下，极小的细菌也是历历可数的。

12，首先，给出整数规划问题的离散局部极小解的定义，并设计找离散局部极小解的邻域搜索算法。

13，极小值时间剖面可直接作时深转换。

14，吉事多专柜有不少圆形或长圆形盆，配合极小的台面，非常秀气。

15, 即使极小的错误都可能会破坏整个项目。例如，过梁裁剪错误就不能正确的安放在石头上面。

16，本文给出了极小化最大函数问题的一个可行方向算法，它把问题归结为求解线性规划问题，并证明了该算法的收敛性。

⑹ 邻域的定义是唯一的吗邻域的定义与搜索效率及结 果有关联吗简要说明你的结

不是。有关联。
邻域：邻域是指集合上的一种基础的拓扑结构。在集合论中，它是以点a为中心的任何开区间，记作：U(a)。在拓扑学和相关的数学领域中，邻域是拓扑空间中的基本概念。有邻域公理（邻域公理是现代数学拓扑结构的基础概念）、开邻域和闭邻域、去心邻域等相关研究的着作。
广义邻域搜索算法的统一结构：
1.对优化过程作两方面分解处理：方面1、基于优化空间的分层（原问题分解为子问题求解，最后将各子问题的解逆向综合为原问题的解）方面2、基于优化进程的分层（进程层次分为若干阶段，各阶段采用不同的搜索算法或邻域函数进行优化）目前混合算法的结构类型主要可归纳为串行、镶嵌、并行及混合结构。
串行结构。
镶嵌结构。
并行结构（又分为同步式并行、异步式并行、网络结构）。
同步式：各子算法相对独立但与主过程的通讯必须同步。
异步式：子算法与主过程的通讯不受其他子算法的限制。
网络结构：各算法分别在独立的存储器上执行独立的搜索，算法间的通信是通过网络相互传递的。

⑺ 搜索算法和j2ee开发两个方向选哪个

局部搜索算法是从爬山法改进而来的。
简单来说，局部搜索算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。
在计算机科学中，局部搜索是解决最优化问题的一种元启发式算法。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。
1、局部搜索算法的基本思想：
在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。
2、局部搜索的优点：
简单、灵活及易于实现，缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。
3、局部搜索广泛应用：
计算机科学（主要是人工智能）、数学、运筹学、工程学、生物信息学中各种很难找到全局最优解的计算问题。

⑻ 基于R、SA和ICP的混合邻域搜索算法的TSP-D路径优化问题代码

摘要 还是要说一点，随机产生两点，塞进新排列头部。其余的按顺序往后逐个塞进去。嗯，来看图片~

⑼ 用极小造句怎么造呀

极小，亦称为最小，最小值。在数学分析中，在给定范围内（相对极值）或函数的整个域（全局或绝对极值），函数的最大值和最小值被统称为极值（极数）。按照该词义造句有：

1，临界点可能是局部极小，局部极大，或者鞍点。

2，首先，给出整数规划问题的离散局部极小解的定义，并设计找离散局部极小解的邻域搜索算法。

3，极小值时间剖面可直接作时深转换。

4，吉事多专柜有不少圆形或长圆形盆，配合极小的台面，非常秀气。

5, 即使极小的错误都可能会破坏整个项目。例如，过梁裁剪错误就不能正确的安放在石头上面。

6，本文给出了极小化最大函数问题的一个可行方向算法，它把问题归结为求解线性规划问题，并证明了该算法的收敛性。

9，由于遍历性可作为避免搜索过程陷入局部极小的有效机制，因此混沌理论已成为一种新颖且有潜力的优化工具。

10，需要大量的烟，但极小量的明火。

11，我家有一只小花猫，它圆圆的脑袋上有一双明亮的眼睛，使它晚上能看清东西。它还有一双灵活的耳朵，极小的声音它都能辨别出来。它的身后长着一条长长的尾巴，走路时总是高高的翘着。

12，因为宇宙的结构是最完善的而且是最明智的上帝的创造，因此，如果在宇宙里没有某种极大的或极小的法则，那就根本不会发生任何事情。

13，紫鹃道：＂我只当是宝二爷再不上我们这门了，谁知这会子又来了。＂宝玉笑道：＂你们把极小的事倒说大了。好好的为什么不来？我便死了，魂也要一日来一百遭。妹妹可大好了？＂

14, 有一种杀人利器“激光枪，”它一次能射出500英里，这种枪体形极小，能随时带在身上。而且不象21世纪的枪，有防弹衣可以配用，现在这种枪只要射中哪里，哪里就会烟消云散。

⑽ 采用准确优化技术和启发式优化技术解决一个问题会存在什么不同

采用准确优化技术和启发式优化技术解决一个问题会存在的不同之处：

①确定性算法和随机性算法是目前求解优化问题的方法。随机性算法一般是对社会行为和自然现象的模拟，具有对优化函数的解析性质要求低的特点，甚至对无显示解析表达式的问题也可以求解，能较好解决优化中的噪声、不可微、高维等问题。

②启发式算法作为随机性算法的一种，其良好的应用更加快了人们对各种优化方法的探索脚步。 近些年来不断有学者将分形应用于优化中来，试图运用分形思想来处理复杂的优化问题。

③其中，分形算法通过对可行域的分形分割来寻优，是一种新颖的确定性算法，但其局限性较大，只适用于低维简单的问题，对于当今社会中高维复杂问题则几乎无能为力，也使得该算法的影响力微乎其微。

④启发式技术是基于特征值扫描技术上的升级,与传统反病毒特征值扫描技术相比,优点在于对未知病毒的防御.是特征值识别技术质的飞跃。

(10)2邻域搜索算法扩展阅读

启发式：简化虚拟机和简化行为判断引擎的结合 Heuristic(启发式技术=启发式扫描+启发式监控) 重点在于特征值识别技术上的更新、解决单一特征码比对的缺陷.目的不在于检测所有的未知病毒,只是对特征值扫描技术的补充.主要针对：木马、间谍、后门、下载者、已知病毒(PE病毒)的变种。

一、启发式发展方向

现代启发式算法的研究,在理论方面还处于不断发展中,新思想和新方法仍不断出现。分析目前的现状和发展方向,其发展方向有如下几个方面:

①整理归纳分散的研究成果,建立统一的算法体系结构。

②在现有的数学方法(模式定理、编码策略、马尔可夫链理论、维数分析理论、复制遗传算法理论、二次动力系统理论、傅立叶分析理论、分离函数理论、Walsh函数分析理论)的基础上寻求新的数学工具。

③开发新的混合式算法及开展现有算法改进方面的研究。

④研究高效并行或分布式优化算法。

二、启发式算法算法机制特点

现代启发式算法在优化机制方面存在一定的差异,但在优化流程上却具有较大的相似性,均是一种“邻域搜索”结构。算法都是从一个(一组)初始解出发,在算法的关键参数的控制下通过邻域函数产生若干邻域解,按准则(确定性、概率性或混沌方式)更新当前状态,而后按关键参数修改准则调整关键参数，一直优化到最优结果。