1. 概述
比赛的难点之一就是要去寻找服务器最佳选址，虽然对于这个问题已经给出了直连的一种解，但是这样的解显然是不可取的（代价很大）。因而在现有初始解的情况下使用启发式的搜索算法对优解进行搜索，便是一种可行的方案。
禁忌搜索算法是组合优化算法的一种，是局部搜索算法的扩展。禁忌搜索算法是人工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。
禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌对象、评价函数、特赦规则等概念。
禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌对象、评价函数、特赦规则等概念。
侯选集合：
针对于今年比赛的题目给定的初始解，在搜索过程中选择的候选的领域，可以是当前解周围的网络节点。
禁忌对象：
对于选择进来的解，可能会导致整体总费用的升高或是使得解变得不可行，就需要将该点加入到禁忌表中了。
评价函数：
对于节点选择带来的效果，使用上一讲中提到的最小费用最大流算法，去计算费用
特赦规则：
当选择的结点使得新解的评价比原来的解效果好，那么就可以考虑对禁忌表中的元素进行解禁
终止准则：
在算法运行的过程中可以采用运行次数的限制，来使程序退出
2. 编码
static int tabu_list_lenth = 0; //禁忌表的长度
static int tabu_max_times = 5000; //禁忌表的最大迭代次数
std::deque<std::vector<int>> tabu_list; //使用双向队列作为禁忌表
//禁忌搜索初始化
void tabu_init()
{
int tabu_lenth = client_node_num*2;//(client_node_num - 1) / 2; //计算禁忌表的长度
tabu_list_lenth = tabu_lenth;
//tabu_list = std::deque<std::vector<int>>(tabu_list_lenth); //定义一个禁忌表长度的双向队列
}
//判断当前交换是否在禁忌表中，存在返回true，不存在返回false
bool is_tabulist(int pos_1, int pos_2)
{
swap_int(pos_1, pos_2);
unsigned int tabu_size(tabu_list.size());
for (unsigned int i=0; i<tabu_size; i++)
{
std::vector<int> vec = tabu_list[i];
if (vec.size()>0)
if ((pos_1==vec[0]) && (pos_2==vec[1])) return true; //该值存在于禁忌表中
}
return false;
}
//更新禁忌表
void flush_tabulist(int pos_1, int pos_2)
{
if (!is_tabulist(pos_1, pos_2)) //不存在于禁忌表中
{
swap_int(pos_1, pos_2); //按照小大次序排列
std::vector<int> vec;
vec.push_back(pos_1);
vec.push_back(pos_2);
if ((int)tabu_list.size() < tabu_list_lenth) //禁忌表没有满
{
tabu_list.push_back(vec);
}
else //禁忌表已经被填满了，删除最先进来的元素，将新的元素添加进来
{
cout << "卧槽，禁忌表都满了！" << endl;
tabu_list.pop_front();
tabu_list.push_back(vec);
}
}
}
//交换两个数的值
void swap_int(int& pos_1, int& pos_2)
{
if (pos_1 > pos_2)
{
int temp = pos_1;
pos_1 = pos_2;
pos_2 = temp;
}
}
//获取该点没有存在于禁忌表中的点
std::vector<int> neighbour_node(int node, std::vector<int>& may_server)
{
node = node > net_node_num ? (node-2*net_node_num) : node; //对于选择该点不存在的情况
std::vector<int> result;
unsigned int temp_size(net_node[node].outnode.size()); //临时记录大小的
for (unsigned int i = 0; i < temp_size; i++)
{
if (!is_tabulist(node, net_node[node].outnode[i]) && CheckIsServer(net_node[node].outnode[i], may_server)) //当前对值没有存在于禁忌表中
result.push_back(net_node[node].outnode[i]);
} //搜索出度
temp_size = net_node[node].innode.size(); //临时记录大小的
for (unsigned int i = 0; i < temp_size; i++)
{
if (!is_tabulist(node, net_node[node].innode[i]) && CheckIsServer(net_node[node].innode[i], may_server)) //当前对值没有存在于禁忌表中
result.push_back(net_node[node].innode[i]);
} //搜索入度
if (!is_tabulist(node, node+2*net_node_num)) //这里判断与不存在的点的配对是指不选择该点
result.push_back(node+2*net_node_num);
return result;
}
//获取low和high范围内的一个随机值
int get_random_pos(int low, int high)
{
int result = static_cast<unsigned int>(rand())%high;
return result;
}
//获取向量中服务器的个数
int get_server_count(std::vector<int> vec)
{
int result(0);
unsigned int temp_size(vec.size());
for (unsigned int i=0; i<temp_size; i++)
{
if (vec[i] < net_node_num)
result++;
}
return result;
}
//去除那些已经排除了的点
std::vector<int> clean_server(std::vector<int> vec)
{
std::vector<int> result;
int temp_size((int)vec.size());
for(int i=0; i<temp_size; i++)
if(vec[i] < net_node_num) result.push_back(vec[i]);
return result;
}
//禁忌搜索
void tabu_search()
{
tabu_init(); //禁忌搜索初始化
int iterator_times = tabu_max_times;
int result_size((int)min_server.size());
std::vector<int> may_server = xjbs_getserver(0); //得到可能会是服务器的节点
srand((unsigned)time(0)); //弄个随机种子
while (iterator_times>0)
{
//运行时间判断
clock_t temp_end = clock();
if(((double)(temp_end-start)/CLOCKS_PER_SEC) > tabu_time) break;
int change_pos = get_random_pos(0, result_size); //随机的产生需要替换掉的点
cout << "需要出去的点：" << min_server[change_pos] << endl;
std::vector<int> neighbours = neighbour_node(change_pos, may_server); //获取该点领域的点
cout << "邻域点的个数：" << neighbours.size() << "\t";
if(neighbours.size()<=0)//邻域的个数为0跳过
{
--iterator_times;
continue;
}
int temp_min_cost(MAXINT), temp_best_node(change_pos);
for (unsigned int i = 0; i < neighbours.size(); i++)
{
min_server[change_pos] = neighbours[i]; //使用领域替换掉指定的点
int flow(0), cost(-1);
my_search_init(clean_server(min_server));
cost = MinCostFlow(net_node_num, (net_node_num + 1), flow);
cost += get_server_count(min_server)*server_cost;
if (flow >= needed_flow)
{
if (temp_min_cost>cost)
{
temp_min_cost = cost;
min_path = path;
temp_best_node = neighbours[i];
}
}
cout << neighbours[i] << "\t";
} //搜寻领域中最佳的点
if (change_pos == temp_best_node) cout << "麻痹，在 " << min_server[change_pos] << " 的领域中没有找到优化的解" << endl;
min_server[change_pos] = temp_best_node; //使用最好的领域替换掉指定的点
if (min_cost>temp_min_cost) //藐视准则
{
count = 0;
cout << "find better: " << temp_min_cost << endl;
min_server[change_pos] = temp_best_node; //使用领域替换掉指定的点
tabu_list.clear();
min_cost = temp_min_cost;
flush_tabulist(change_pos, temp_best_node); //加入到禁忌表中
}
else
{
for (unsigned int i = 0; i < neighbours.size(); i++)
{
flush_tabulist(change_pos, neighbours[i]); //加入到禁忌表中
}
}
--iterator_times;
}
cout << "\nthe result after " << tabu_max_times << " times search" << endl;
cout << "the min_cost is: " << min_cost << endl;
}
注：水平有限，堆码有误不足，欢迎指正。