禁忌搜索算法的缺点

⑴ 请教选址研究问题！

物流配送中心选址方法研究综述

内容摘要：物流配送中心的选址决策在物流运作中有着重要的地位。本文对近年来国内外有关配送中心选址方法的文献进行梳理和研究。研究结果发现：各种选址方法有着各自的优缺点和一定的适用范围，各种方法的组合是未来该领域研究的趋势。
关键词：物流配送中心 选址 文献综述

在物流系统的运作中，配送中心的选址决策发挥着重要的影响。配送中心是连接工厂与客户的中间桥梁，其选址方式往往决定着物流的配送距离和配送模式，进而影响着物流系统的运作效率。因此，研究物流配送中心的选址具有重要的理论和现实应用意义。
本文对近年来国内外有关物流配送中心选址方法的文献进行了梳理和研究，并对各种方法进行了比较。选址方法主要有定性和定量的两种方法。定性方法有专家打分法、Delphi法等，定量方法有重心法、P中值法、数学规划方法、多准则决策方法、解决NP hard问题（多项式复杂程度的非确定性问题）的各种启发式算法、仿真法以及这几种方法相结合的方法等。由于定性研究方法及重心法、P中值法相对比较成熟，因此，本文将主要分析定量方法中的数学规划、多准则决策、解决NP hard问题的各种启发式算法、仿真在配送中心选址中应用的研究状况。
数学规划方法
数学规划算法包括线性规划、非线性规划、整数规划、混合整数规划和动态规划、网络规划算法等。在近年来的研究中，规划论中常常引入了不确定性的概念，由此进一步产生了模糊规划、随机规划、模糊随机规划、随机模糊规划等等。不确定性规划主要是在规划中的C(价值向量)、A(资源消耗向量)、b(资源约束向量)和决策变量中引入不确定性，从而使得不确定规划更加贴近于实际情况，得到广泛地实际应用。
国内外学者对于数学规划方法应用于配送中心的选址问题进行了比较深入的研究。姜大元(2005)应用Baumol-wolf模型，对多物流节点的选址问题进行研究，并通过举例对模型的应用进行了说明，该模型属于整数规划和非参数规划结合的模型。各种规划的方法在具体的现实使用中，常常出现NP hard问题。因此，目前的进一步研究趋势是各种规划方法和启发式算法的结合，对配送中心的选址进行一个综合的规划与计算。
多准则决策方法
在物流系统的研究中，人们常常会遇到大量多准则决策问题，如配送中心的选址、运输方式及路线选择、供应商选择等等。这些问题的典型特征是涉及到多个选择方案(对象)，每个方案都有若干个不同的准则，要通过多个准则对于方案(对象)做出综合性的选择。对于物流配送中心的选址问题，人们常常以运输成本及配送中心建设、运作成本的总成本最小化，满足顾客需求，以及满足社会、环境要求等为准则进行决策。多准则决策的方法包括多指标决策方法与多属性决策方法两种，比较常用的有层次分析法(AHP)、模糊综合评判、数据包络分析(DEA),TOPSIS、优序法等等。
多准则决策提供了一套良好的决策方法体系，对于配送中心的选址不管在实务界还是理论方面的研究均有广泛的应用与研究。关志民等(2005)提出了基于模糊多指标评价方法的配送中心选址优化决策。从供应链管理的实际需要分析了影响配送中心选址的主要因素，并建立相应的评价指标体系，由此给出了一种使定性和定量的方法有机结合的模糊多指标评价方法。Chen-Tung Chen(2001)运用了基于三角模糊数的模糊多准则决策对物流配送中心的选址问题进行了研究。文章以投资成本、扩展的可能性、获取原材料的便利性、人力资源、顾客市场的接近性为决策准则，并对各个准则采用语义模糊判定的方式进行了权重上的集结。
有关多准则决策方法，特别是层次分析法和模糊综合评判的方法，在配送中心的选址研究中有着广泛的应用。但是，这两种方法都是基于线性的决策思想，在当今复杂多变的环境下，线性的决策思想逐渐地暴露出其固有的局限性，非线性的决策方法是今后进一步的研究的重点和趋势。
启发式算法
启发式算法是寻求解决问题的一种方法和策略，是建立在经验和判断的基础上，体现人的主观能动作用和创造力。启发式算法常常能够比较有效地处理NP hard问题，因此，启发式算法经常与其它优化算法结合在一起使用，使两者的优点进一步得到发挥。目前，比较常用的启发式算法包括：遗传算法；神经网络算法；模拟退火算法。
（一）遗传算法
遗传算法（genetic algorithm, GA）是在 20 世纪 60 年代提出来的，是受遗传学中自然选择和遗传机制启发而发展起来的一种搜索算法。它的基本思想是使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。遗传算法主要有三个算子：选择；交叉；变异。通过这三个算子，问题得到了逐步的优化，最终达到满意的优化解。
对于物流配送中心的选址研究，国内外有不少学者将遗传算法同一般的规划方法结合起来对其进行了研究。蒋忠中等（2005）在考虑各种成本(包括运输成本等)的基础上，结合具体的应用背景，建立的数学规划模型(混合整数规划或是一般的线性规划)。由于该模型是一个组合优化问题，具有NP hard问题，因此，结合了遗传算法对模型进行求解。通过选择恰当的编码方法和遗传算子，求得了模型的最优解。
遗传算法作为一种随机搜索的、启发式的算法，具有较强的全局搜索能力，但是，往往比较容易陷入局部最优情况。因此，在研究和应用中，为避免这一缺点，遗传算法常常和其它算法结合应用，使得这一算法更具有应用价值。
（二）人工神经网络
人工神经网络(artificial neural- network, ANN)是由大量处理单元(神经元)广泛互连而成的网络，是对人脑的抽象、简化和模拟，反应人脑的基本特征。可以通过对样本训练数据的学习，形成一定的网络参数结构，从而可以对复杂的系统进行有效的模型识别。经过大量样本学习和训练的神经网络在分类和评价中，往往要比一般的分类评价方法有效。
对于神经网络如何应用于物流配送中心的选址，国内外不少学者进行了各种有益的尝试。韩庆兰等（2004）用BP网络对物流配送中心的选址问题进行了尝试性地研究，显示出神经网络对于解决配送中心选址问题具有一定的可行性和可操作性。
这一研究的不足是神经网络的训练需要大量的数据，在对数据的获取有一定的困难的情况下，用神经网络来研究是不恰当的。在应用ANN时，我们应当注意网络的学习速度、是否陷入局部最优解、数据的前期准备、网络的结构解释等问题，这样才能有效及可靠地应用ANN解决实际存在的问题。
（三）模拟退火算法
模拟退火算法(Simulated Annealing, SA)又称模拟冷却法、概率爬山法等，于1982年由Kirpatrick提出的另一种启发式的、随机优化算法。模拟退火算法的基本思想由一个初始的解出发，不断重复产生迭代解，逐步判定、舍弃，最终取得满意解的过程。模拟退火算法不但可以往好的方向发展,也可以往差的方向发展,从而使算法跳出局部最优解,达到全局最优解。
对于模拟退火算法应用于物流配送中心选址的研究，大量的文献结合其它方法（如多准则决策、数学规划等）进行了研究。任春玉(2006)提出了定量化的模拟退火遗传算法与层次分析法相结合来确定配送中心地址的方法。该方法确保总体中个体多样性以及防止遗传算法的提前收敛，运用层次分析法确定 物流配送中心选址评价指标权重，并与专家评分相结合进行了综合评价。该算法对于解决物流配送中心的选址具有较好的有效性和可靠性。
除以上三种比较常用的方法之外，启发式算法还包括蚁群算法、禁忌搜索算法、进化算法等。各种算法在全局搜索能力、优缺点、参数、解情况存在着一定的差异。各种启发式算法基本上带有随机搜索的特点，已广泛地应用于解决NP hard问题，同时也为物流配送中心选址的智能化处理提供了可能。用解析的方法(包括线性规划等)建立数学模型，然后运用启发式算法进行求解是目前以及未来研究物流配送中心选址的一种较为可行和可操作的研究方法。
仿真方法
仿真是利用计算机来运行仿真模型，模拟时间系统的运行状态及其随时间变化的过程，并通过对仿真运行过程的观察和统计，得到被仿真系统的仿真输出参数和基本特征，以此来估计和推断实际系统的真实参数和真实性能。国内外已经不少文献将仿真的方法运用于物流配送中心选址或是一般的设施选址的研究，研究结果相对解析方法更接近于实际的情况。
张云凤等(2005)对汽车集团企业的配送中心选址运用了仿真的方法进行了研究。先确定了配送中心选址的几种方案，应用了Flexim软件对各方案建立了仿真模型，根据仿真结果进行了分析和方案的选择。该方法为集团企业配送中心选址问题提供了一种较为理想的解决方法。薛永吉等(2005)通过建立数学模型对物流中心的最优站台数问题进行研究，在一定假设和一系列限制条件下，求解最优站台数量，并针对数学模型的复杂性和求解的种种不足，以ARENA仿真软件为平台，建立仿真模型确定了最优化方案。Kazuyoshi Hidaka等(97)运用仿真对大规模的仓库选址进行了研究。该研究对仓库的固定成本、运输成本，和同时满足6800名顾客进行了仿真，以求得临近的最优解(near-optimal solution)。在求解的过程中，结合了贪婪－互换启发式算法(Greedy-Interchange heuristics)和气球搜索算法(Balloon Search)两种启发式算法进行求解。该算法能比较有效地避免陷入局部最优解和得到比较满意的选址方案。但是，研究的结果容易受到运输车辆的平均速度变化的影响。
仿真方法相对解析的方法在实际应用中具有一定的优点，但是，也存在一定的局限性。如仿真需要进行相对比较严格的模型的可信性和有效性的检验。有些仿真系统对初始偏差比较敏感，往往使得仿真结果与实际结果有较大的偏差。同时，仿真对人和机器要求往往比较高，要求设计人员必须具备丰富的经验和较高的分析能力，而相对复杂的仿真系统，对计算机硬件的相应要求是比较高的。关于未来的研究，各种解析方法、启发式算法、多准则决策方法与仿真方法的结合，是一种必然的趋势。各种方法的结合可以弥补各自的不足，而充分发挥各自的优点，从而提高选址的准确性和可靠性。
物流配送中心的选址决策对于整个物流系统运作和客户满意情况有着重要的影响。本文在对国内外有关物流配送中心选址方法文献研究的基础上，对比分析了数学规划方法、多准则决策、启发式算法、仿真方法在配送中心选址中的应用。研究发现数学规划方法、多属性决策方法、启发式算法、仿真方法各自有自己的优缺点和一定的适用范围，各种方法的组合研究是未来研究的一种趋势。同时，由于选址问题本身具有的动态性、复杂性、不确定性等特性，因此，开发和研究新的模型与方法也是进一步解决配送中心选址问题的必需途径。

参考文献：
1.蒋忠中，汪定伟.B2C电子商务中配送中心选址优化的模型与算法(J).控制与决策，2005
2.韩庆兰，梅运先.基于BP人工神经网络的物流配送中心选址决策(J).中国软科学，2004

⑵ 哪个大神有时间帮我对VRP问题用禁忌搜索算法编写一个lingo或者c语言可以

求最短配送路径的话 应该是TSP问题吧，不应该是VRP问题。
LINGO能很好地求解这两类模型，但用的整数规划原理或动态规划原理，不能用禁忌搜索。
禁忌搜索，就用C或许能解决。

⑶ 禁忌搜索算法浅析

姓名：刘家沐

学号：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，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.

⑸ 最大团问题的应用背景

MCP问题是现实世界中一类真实问题，在市场分析、方案选择、信号传输、计算机视觉、故障诊断等领域具有非常广泛的应用。自1957年Hararv和Ross首次提出求解最大团问题的确定性算法以来，研究者们已提出了多种确定性算法来求解最大团问题。但随着问题规模的增大（顶点增多和边密度变大），求解问题的时间复杂度越来越高，确定性算法显得无能为力，不能有效解决这些NP完全问题。
20世纪80年代末，研究者们开始尝试采用启发式算法求解最大团问题，提出了各种各样的启发式算法，如顺序贪婪启发式算法、遗传算法、模拟退火算法、禁忌搜索算法、神经网络算法等，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、边密度的增加而变得越来越小。唯一的缺点就是不一定能找到最优值，有时只能找到近优值。
近年来研究表明，单独使用一种启发式算法求解最大团问题，算法性能往往并不是很好，因此，常借鉴算法之间优势互补策略，形成新的混合启发式算法来求解最大团问题。当前求解该问题最好的启发式算法有反作用禁忌搜索（Reactive Tabu Search, RTS）算法、基于遗传算法的简单启发式算法（Simple Heuristic Based Genetic Algorithm, HGA）、DLS-MC算法等。

⑹ TS算法是什么

就是禁忌搜索算法，又名“tabu搜索算法”，是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。
禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

⑺ 禁忌搜索算法的介绍

禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

⑻ 有什么算法可以同时解决车辆路径优化的VRPTW和SDVRP，数学模型怎么达到

智能优化算法，比如粒子群算法、蚁群算法、禁忌搜索算法。优点是对问题和模型要求低，搜索速度快；缺点是容易陷入局部最优解。

⑼ 禁忌搜索算法的伪码表达

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的邻域的局部最优解。可以证明如果邻域满足对称性条件，则在假设禁忌表足够长的情况下必然可搜索到全局最优解。

⑽ 禁忌搜索解决任务分配问题（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