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

开篇：润墨网以专业的文秘视角，为您筛选了一篇禁忌搜索算法应用于解整数线性规划问题的实践范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

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

[关键词] 禁忌搜索算法 整数线性规划问题 技术处理

1 算法的技术问题

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

2 整数线性规划问题及其技术处理

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

,；

，

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

，

， ，

整数线性规划问题从计算复杂性划分，它属于NP问题。

采用禁忌搜索算法，有关的技术问题作如下的预处理：

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

对于禁忌对象的选择，可以以改变数值的分量位置、或目标值、或可行解 作为禁忌对象。禁忌对象全体组成的集合称为禁忌表 。其中每一个元素都附有当前的禁忌代数，禁忌代数随着迭代次数变化而变化，一旦其数值超过禁忌长度时，该元素将解除禁忌。

本文的局部最优解候选集 是新的局部最优可行解的搜索区域， 就是从 的邻域

中去掉禁忌表中相应的元素而得。禁忌长度 取 或 。

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

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

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

3 算法流程图

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

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

② 生成禁忌表 、

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

查寻新的禁忌对象：如果 ，则 ， ，相应的禁忌长度置初值1。

如果 的邻居 满足条件：0，而且相应的 不在 中出现，则

， 。

③ 执行特赦命令，修正

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

4 实践与探讨

针对以下问题，采用适当的建立邻域的规则，使用C语言将算法编制成程序，在计算机上运行，得到较好结果。

例1

， ，是整数。

技术处理：取初始可行解 。 定义为可行解 恰有一个分量数值增加1的可行解全体构成集合，＝3， ＝8，禁忌长度取3。计算过程列表如下：

计算结束，得到最优解 ＝ ，相应的目标值 =12，其中 中向量的第1个分量是禁忌评价值，第2个分量是禁忌代数。

例2

， ， ，

技术处理：取初始可行解 ， 定义为可行解 恰有一个分量数值在0、1之间变化的可行解全体构成集合，＝3， ＝8，禁忌长度取3，计算过程列表如下。得到最优解 = ，相应的目标值 =2。

参考文献：

[1] 邢文训, 谢金星. 现代优化计算方法[M]. 北京: 清华大学出版社, 2003.