禁忌搜索算法应用于解整数线性规划问题的实践

龙源期刊网 http://www.qikan.com.cn

禁忌搜索算法应用于解整数线性规划问题的实践

作者：陈 伟

来源：《海峡科学》2009年第03期

[摘要] 禁忌搜索算法的技术问题预处理，关系到算法计算结果的优劣。该文探讨禁忌搜索算法应用于解整数线性规划问题及其技术处理，得到最优解。 [关键词] 禁忌搜索算法 整数线性规划问题 技术处理 1 算法的技术问题

禁忌搜索算法的技术问题主要有：可行解的形式、解邻域的定义、禁忌的对象、禁忌的长度、局部最优解候选集、计算终止条件等等。对于这些技术问题的预处理，关系到算法计算结果的优劣。这些技术问题没有固定的模式生搬硬套，可以因问题而异，因人对问题的认识理解而异，从而产生的算法结果也有差异。 2 整数线性规划问题及其技术处理

整数线性规划问题的数学模型为：求解 维向量 ，使之满足： ,； ，

设 ， ， ，则整数线性规划问题可以表示为： ， ， ，

整数线性规划问题从计算复杂性划分，它属于NP问题。 采用禁忌搜索算法，有关的技术问题作如下的预处理：

对于可行解采用通常的 维向量表示法。任取初始可行解 。 表示可行解 的邻域，这里 定义为可行解 的恰有一个分量的数值改变的可行解全体构成集合，这样的 至多含有 个元素。

龙源期刊网 http://www.qikan.com.cn

对于禁忌对象的选择，可以以改变数值的分量位置、或目标值、或可行解 作为禁忌对象。禁忌对象全体组成的集合称为禁忌表 。其中每一个元素都附有当前的禁忌代数，禁忌代数随着迭代次数变化而变化，一旦其数值超过禁忌长度时，该元素将解除禁忌。 本文的局部最优解候选集 是新的局部最优可行解的搜索区域， 就是从 的邻域 中去掉禁忌表中相应的元素而得。禁忌长度 取 或 。

取评价函数选择目标函数为之。在 中根据评价函数搜索新的可行解 。

特赦原则基于评价函数值的原则。即当= 时，从 中释放出使得评价函数值最小的禁忌对象。

计算终止条件为： = 或最大迭代上限或最佳评价值出现的频数，当而且仅当其中一个条件满足时，计算终止，输出结果。 3 算法流程图

流程图如下所示。其中，生成邻域 、禁忌表 、 的算法如下：

① 生成邻域 。设置数组 ， 的第 个分量变化后，得到新的可行解，否则 置 －1，而且 ， 。

② 生成禁忌表 、

本文以评价值为禁忌对象。如果，则 的所有元素禁忌长度分别加1，长度为 的禁忌元被释放；

查寻新的禁忌对象：如果 ，则 ， ，相应的禁忌长度置初值1。 如果 的邻居 满足条件：0，而且相应的 不在 中出现，则 ， 。

③ 执行特赦命令，修正

如果，则要执行特赦。特赦时重点考虑释放对象的影响力及承担最小的错误诸原则。在 中查找使得评价值最小的禁忌元作为特赦对象，相应的可行解添加到 中。 4 实践与探讨

本文来源：https://www.bwwdw.com/article/lyc3.html