本公开涉及教学演示装备技术领域，特别涉及一种禁忌搜索算法的教学演示系统及方法。
背景技术：
本部分的陈述仅仅是提供了与本公开相关的背景技术，并不必然构成现有技术。
禁忌搜索算法(tabusearch)是一种常见的元启发搜索算法。该算法在局部搜索的基础上，辅以搜索历史的记录，从而具备很强的全局优化的搜索能力。该算法已经被应用到大量的组合优化、整数优化及其他生产生活中的复杂优化问题中并获得了理想的效果。
本公开发明人发现，目前对于禁忌搜索算法的学习和讲授目前一般仍然使用原始的基于文字讲解的方法，由于该算法使用了动态的结构，对于初学者而言传统方法往往不能有效的展示算法的运行机制，从而导致该算法的学习难度较高，需要反复的文字讲授，费时费力。
技术实现要素：
为了解决现有技术的不足，本公开提供了一种禁忌搜索算法的教学演示系统及方法，通过处理器与显示模块的配合，能够清楚的演示标准禁忌搜索算法的完整运行机制，使学习者能够快速和容易的理解算法的原理，较传统的基于文字讲授的方法更加易懂。
为了实现上述目的，本公开采用如下技术方案：
本公开第一方面提供了一种禁忌搜索算法的教学演示系统。
一种禁忌搜索算法的教学演示系统，包括：
处理器以及与处理器连接的显示模块，显示模块用于动态显示处理器推送的演示表格；
演示表格至少包括全局最优解展示表，禁忌搜索算法解向量的数字序号与全局最优解展示表的行对应，解向量的每一个数字量与最优解展示表的列对应。
作为可能的一些实现方式，禁忌搜索算法以得到的冲突的数量最小为目标，通过交换解向量中某两个元素的位置得到最优解。
作为可能的一些实现方式，演示表格还包括搜索禁忌表，采用一个二维矩阵的一半来记录交换点。
作为进一步的限定，用特定颜色进行搜索禁忌表中的禁忌点标识。
作为可能的一些实现方式，演示表格还包括邻域函数值表，用于观察禁忌表对于当前邻域中所有可能的候选解的控制。
作为进一步的限定，采用渐进颜色进行标注，函数值越小的位置颜色越深或者越浅。
作为可能的一些实现方式，演示表格还包括禁忌次数，禁忌次数在显示模块中的界面中为只读的指示性界面。
作为可能的一些实现方式，演示表格还包括禁忌次数，禁忌次数在显示模块中的界面中为能够允许用户输入的交互性界面。
作为可能的一些实现方式，演示表格还包括全局最优解及其对应的函数值。
作为可能的一些实现方式，演示表格还包括当前解及其对应的函数值。
本公开第二方面提供了一种禁忌搜索算法的教学演示方法。
一种禁忌搜索算法的教学演示方法，利用本公开第一方面所述的禁忌搜索算法的教学演示系统，包括以下步骤：
运行添加了与界面更新有关的代码的禁忌搜索算法，搜索循环前预先计算所有邻域中交换点的函数值；
通过演示表格实时显示禁忌搜索算法的全局最优解及函数值、当前解及函数值、禁忌次数、搜索禁忌表和邻域函数值表。
作为可能的一些实现方式，使用下标的和或者差作为一个数组的下标，并利用该数组来存储所有对角线上的元素个数，对于差可能是负数的情况，统一转换为正值作为数组的下标，遍历该数组得到全局最优解展示表某个线上冲突的个数，通过减1操作可得到确定的函数值。
与现有技术相比，本公开的有益效果是：
1、本公开所述的系统及方法，能够清楚的演示标准禁忌搜索算法的完整运行机制，使学习者能够快速和容易的理解算法的原理。
2、本公开所述的系统及方法，较传统的基于文字讲授的方法更加易懂，对于禁忌搜索算法中的禁忌表结构，使用动态的界面来演示每次迭代的变化，够能更加清楚的呈现禁忌表在算法中的作用。
3、本公开所述的系统及方法，对于整体的搜索框架，维护了一个当前解和全局最优解，通过这两个解的对比能够清楚的展现两个解的区别，进而理解算法的非最优搜索原理。
附图说明
构成本公开的一部分的说明书附图用来提供对本公开的进一步理解，本公开的示意性实施例及其说明用于解释本公开，并不构成对本公开的不当限定。
图1为本公开实施例1提供的禁忌搜索算法的教学演示系统的结构示意图。
图2为本公开实施例1提供的解的展示界面1。
图3为本公开实施例1提供的解的展示界面2。
图4为本公开实施例1提供的系统整体界面示意图。
图5为本公开实施例1提供的某次迭代的对话框界面示意图。
具体实施方式
下面结合附图与实施例对本公开作进一步说明。
应该指出，以下详细说明都是例示性的，旨在对本公开提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本公开所属技术领域的普通技术人员通常理解的相同含义。
需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本公开的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
在不冲突的情况下，本公开中的实施例及实施例中的特征可以相互组合。
实施例1：
如图1所示，本公开实施例1提供了处理器以及与处理器连接的显示模块，显示模块用于动态显示处理器推送的演示表格；
演示表格至少包括全局最优解展示表，禁忌搜索算法解向量的数字序号与全局最优解展示表的行对应，解向量的每一个数字量与最优解展示表的列对应。
具体的，包括以下内容：
s1：建立求解问题，确定解的形式，实现问题的评价函数的计算。
尽管对于各种优化问题，禁忌搜索几乎都有对应的应用方案，但作为演示和观察算法的运行机制，尤其是对于禁忌搜索表的控制功能，需要使用在搜索过程中能够容易出现“兜圈”的优化问题。同时不能使得问题模型过于复杂以致不方便观察。
因此，本实施例采用的“n皇后问题”的优化版本。即在棋盘中放置皇后棋子，使得不能发生横线竖线和斜线的冲突。优化版本是可以出现冲突但是要尽量的使冲突的数量降低，本实施例使用了一般计算机均可以实现的网格作为棋盘，使用字母“1”作为棋子，解的示意图界面如图2和图3所示。
如图2和图3所示，使用网格和字符1来概念化的表示棋盘和棋子。根据定义，图2中的冲突数量为4，图3中的冲突数量为3。
对于该问题，这里使用标准的排列向量来表示一个解，向量与棋盘中解得对应关系如下。使用向量中某个元素的位置表示棋盘中的行标，使用元素值表示列标。
假设解向量为v＝(3，2，1，5，7)，是指第一行的棋子放在3列，第2行的棋子放在第2列，第3行的棋子放在第1列，依次类推。图2中的解可以表示为v＝(7，6，5，2，3，1，8，4)。由于禁忌搜索算法是在特定的邻居结构中进行，这里的邻域搜索结构为交换解向量中某两个元素的位置。
在后面的描述中使用“交换点”来表示两个交换元素的位置。例如假如一个解v＝(3，2，1，5，7)在交换点(1，2)进行交换，则交换后的解变为v＝(2，3，1，5，7)。这里采用的邻域则定义为对于一个解进行一次交换后可能变成的解。例如对于一个长度为三的向量，领域中所有的交换点则为(1，2)，(1，3)，(2，3)。搜索算法的目的即为通过交换来查看不同的解，使得冲突的数量最小。
关于冲突的计算实现方式如下：
由于解的表示方法直接可以杜绝横竖方向的冲突，因此这里只计算对角线方向的冲突即可。对于某条对角线，如果在线上的棋子多余1个，则定义冲突的数量为棋子的个数减1。对于具体的目标函数的计算，可使用遍历对角线的方式来检查每个对角线上的棋子数量，或其他可行的方式。
鉴于遍历对角线并不容易实现，本实施例的实现方式如下：
由于对角线上的元素行列下标相加或者相减结果一致，因此可以使用下标的和或者差作为一个数组的下标，并利用该数组来存储所有对角线上的元素个数。对于差可能是负数的情况，可以统一转换为正值作为数组的下标。最后遍历该数组即可得到某个线上冲突的个数，通过减1操作可得到确定的函数值。
s2：建立算法演示界面
界面主要结构如图4所示。界面中使用标签实现每个区域的指示性说明文字。由于是教学演示为目的，系统使用了定长的问题(向量长度或棋盘长度为8)，但不妨碍在其他实现中可以进一步扩展问题的规模。左上角的网格为解的展示界面。下方为全局最优解和当前最优解(及其二者的最优值)。这两个解是禁忌搜索算法中最主要的搜索对象，因此将它们的解向量可视化。
右上部分为禁忌搜索算法中的禁忌表，这里用搜索禁忌表来标识。由于邻域结构是交换两个元素，因此使用一个二维矩阵的一半来记录交换点。为了便于观察，使用与界面相关的控制代码实现颜色的变化。如图中所示，如果某些点是被禁忌的，则使用深色标识。如图中所示，交换点(1，4)，(2，5)和(2，8)是被禁忌的点。
界面右下部分为邻域函数值表，即当前解邻域中所有交换点的函数值。该表的现实是为了便于观察禁忌表对于当前邻域中所有可能的候选解的控制。该表在禁忌表的正下方对应的位置进行显示，并使用相关代码用渐进颜色进行标注。由于这里是最小化问题，因此函数值越小的位置颜色越深。
界面的左下角为算法的参数。由于本实施例的对象是标准的短期记忆禁忌搜索算法，算法中只有禁忌次数这一个参数。在实现过程中，该参数在界面中可以作为只读的指示性界面，也可以作为能够允许用户输入的交互性界面。
其他界面元素包括显示当前迭代次数和候选交换点的提示框对话框。该对话框会在后面的解释中提及。
s3：展示算法的实现
算法1：用于展示的改进的禁忌搜索算法
相关说明：算法主要思路为标准的禁忌搜索算法加上与界面更新有关的代码。例如算法12到15行不属于标准禁忌搜索算法。这里的目的是预先计算所有邻域中交换点的函数值，以便使用者观察。
算法第4行中的迭代上限设定为10的原因是对于该问题，只需要10次循环即可找到最优解，因此不需要太长的次数。
算法中关于对话框相关的界面说明如下。在算法第27行，系统暂定的对话框如图5所示。对话框中会出现本次迭代的实际交换点，即算法中i'和j'的值。对于该值的选择的原因则可以通过观察搜索禁忌表和邻域函数值表来完成。
从图中的邻域函数值表可以看出，在(1，3)点函数值为1。如果作为一般的搜索算法会选择该点。但是由于搜索禁忌表中该点被禁忌，因此不能选择该点。同时注意到同函数值同样为1的(7，8)。该点没有被禁忌，因此如对话框所示，为本次迭代的最终选择点。
本领域内的技术人员应明白，本公开的实施例可提供为方法、系统、或计算机程序产品。因此，本公开可采用硬件实施例、软件实施例、或结合软件和硬件方面的实施例的形式。而且，本公开可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。
本公开是参照根据本公开实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(read-onlymemory，rom)或随机存储记忆体(randomaccessmemory，ram)等。
以上所述仅为本公开的优选实施例而已，并不用于限制本公开，对于本领域的技术人员来说，本公开可以有各种更改和变化。凡在本公开的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本公开的保护范围之内。
1.一种禁忌搜索算法的教学演示系统，其特征在于，包括：
处理器以及与处理器连接的显示模块，显示模块用于动态显示处理器推送的演示表格；
演示表格至少包括全局最优解展示表，禁忌搜索算法解向量的数字序号与全局最优解展示表的行对应，解向量的每一个数字量与最优解展示表的列对应。
2.如权利要求1所述的禁忌搜索算法的教学演示系统，其特征在于，禁忌搜索算法以得到的冲突的数量最小为目标，通过交换解向量中某两个元素的位置得到最优解。
3.如权利要求1所述的禁忌搜索算法的教学演示系统，其特征在于，演示表格还包括搜索禁忌表，采用一个二维矩阵的一半来记录交换点。
4.如权利要求3所述的禁忌搜索算法的教学演示系统，其特征在于，用特定颜色进行搜索禁忌表中的禁忌点标识。
5.如权利要求1所述的禁忌搜索算法的教学演示系统，其特征在于，演示表格还包括邻域函数值表，用于观察禁忌表对于当前邻域中所有可能的候选解的控制。
6.如权利要求5所述的禁忌搜索算法的教学演示系统，其特征在于，采用渐进颜色进行标注，函数值越小的位置颜色越深或者越浅。
7.如权利要求1所述的禁忌搜索算法的教学演示系统，其特征在于，演示表格还包括禁忌次数，禁忌次数在显示模块中的界面中为只读的指示性界面；
或者，
演示表格还包括禁忌次数，禁忌次数在显示模块中的界面中为能够允许用户输入的交互性界面。
8.如权利要求1所述的禁忌搜索算法的教学演示系统，其特征在于，演示表格还包括全局最优解及其对应的函数值；
或者，
演示表格还包括当前解及其对应的函数值。
9.一种禁忌搜索算法的教学演示方法，其特征在于，利用权利要求1-8任一项所述的禁忌搜索算法的教学演示系统，包括以下步骤：
运行添加了与界面更新有关的代码的禁忌搜索算法，搜索循环前预先计算所有邻域中交换点的函数值；
通过演示表格实时显示禁忌搜索算法的全局最优解及函数值、当前解及函数值、禁忌次数、搜索禁忌表和邻域函数值表。
10.如权利要求9所述的禁忌搜索算法的教学演示方法，其特征在于，使用下标的和或者差作为一个数组的下标，并利用该数组来存储所有对角线上的元素个数，对于差可能是负数的情况，统一转换为正值作为数组的下标，遍历该数组得到全局最优解展示表某个线上冲突的个数，通过减1操作可得到确定的函数值。
技术总结