禁忌算法流程

㈠ c++ 求禁忌搜索算法与遗传算法结合的代码

//个体编码方案：十进制的数列，1至26代表A至Z
//交配方法：使用整数编码的交配规则的常规交配法，
//变异方法 ：使用基于次序的变异，随机的产生两个变异位，然后交换这两个变异位上的基因
//新种群构成方法：轮盘赌法进行筛选
//算法结束条件：种群不再发生变化时停止
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<time.h>
#define random(x) (rand()%x)//随机整数
#define initial {0,2,11,1,8,16,5,19,12,4,15,17,6,18,14,9,7,3,10,13}//随机初值

using namespace std;
//参数
int city_number;
double pm = 0.92;
double initiall = 280;//种群数量
double length_table[26][26];
double pc = 0.02;
struct node
{
char name;
int num;
double x;
double y;
};
struct answer
{
int i;
int jie[26];// 十进制的数列，1至26代表A至Z
double length;
};
double f(int* x)
{
double fi = 0;
for(int i = 0; i < city_number-1; i++)
{
fi = fi + length_table[x[i]][x[i+1]];
}
fi = fi + length_table[x[city_number-1]][x[0]];
return fi;
}
double p(double fi,double fj,double t)
{
double P = exp(-(fj-fi)/t);
return P;
}

int main(int argc,char*argv[])
{
time_t tm; time(&tm);
int flag1 = tm;
int cities;
ifstream in(argv[1]);
in >> cities;
city_number = cities;
node* nodes = new node[city_number];
for(int i = 0; i < cities; i++)
{
in >> nodes[i].name >> nodes[i].x >> nodes[i].y;
nodes[i].num = i;
}
//cout << cities<<endl;
//for(int i = 0; i < cities; i++)
// cout <<nodes[i].name <<" "<< nodes[i].x <<" "<< nodes[i].y<<endl;
int i,j;
for(i = 0; i < cities; i++)
{
length_table[i][i] = (double)INT_MAX;
for(j = i+1; j < cities; j++)
{
length_table [i][j] = length_table[j][i] =sqrt(
(nodes[i].x - nodes[j].x) * (nodes[i].x - nodes[j].x) +
(nodes[i].y - nodes[j].y) * (nodes[i].y - nodes[j].y) );
//cout << length_table [i][j]<<endl;
}
}
ofstream out(argv[2]);
///////////////////////////////////////////////////////////初始设定
double t= initiall;//种群数量
int* temp = new int[cities]; answer* Ans1 = new answer;//群体
answer* Ans2 = new answer;//种群
int text[20] = initial;
int* son1 = new int[cities];
int* son2 = new int[cities];
for(int i = 0; i < cities; i++) {
temp[i] = i; Ans1->jie[i] = temp[i];
Ans2->jie[i] = text[i];
//cout << Ans2->jie[i]<<endl;
}
Ans1->length = f(Ans1->jie);
Ans2->length = f(Ans2->jie);
if(cities<15)Ans2->length =10000;
//cout << Ans2->length;
Ans1->i = random(cities);
//cout <<Ans1->i<<endl;
int pre_length = 0;
//
while(Ans1->length!=pre_length)//种群不再发生变化时停止
{
time(&tm);
double fenmu = 0;//轮盘赌法进行选择
for(int i = 0; i < cities*cities; i++)
{
fenmu = fenmu + 1/Ans1->length;
}
int j1 = 0;double s1 = 0;int r1 = rand();
while(s1*32767<=r1) { s1 = s1 + (1/Ans1->length)/fenmu; j1++; }
int j2 = 0;double s2 = 0;int r2 = rand();
while(s2*32767<=r2) { s2 = s2 + (1/Ans1->length)/fenmu; j2++; }
if(tm-flag1>270)break;
pre_length = Ans1->length;
for(int i = 0; i < 100*cities; i++)//
{
int j = random(cities);
int text = temp[Ans1->i]; temp[Ans1->i] = temp[j]; temp[j] = text;
double length = f(temp);//f(j)
if(length < Ans1->length)
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
else if(p(length,Ans1->length,t)*32767 > rand())
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
}
t = t * pm;int point = random(cities);
//使用整数编码的交配规则的常规交配法
for(int z = 0;z < point;z++) { son1[z] = Ans1->jie[z]; son2[z] = Ans1->jie[z]; }
int text1 = point;int text2 = point;int flag = 0;
for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son1[c])flag=1;
}
if(flag==0){ son1[text1] = Ans1->jie[x]; text1++; }
}

for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son2[c])flag=1;
}
if(flag==0){ son2[text2] = Ans1->jie[x]; text2++; }
}
if(Ans1->length<Ans2->length)
{
for(int m = 0; m < cities; m++)
Ans2->jie[m] = Ans1->jie[m];
Ans2->length = Ans1->length;
}
}
for(int l = 0; l < cities; l++)
{
out << char(Ans2->jie[l]+65)<<" ";
}
out <<Ans2->length<<endl;
return 0;
}

㈡ （转）物流优化算法处理流程及算法服务平台建设

转自：吉勍Personal

http://www.jiqingip.com/page9001?article_id=94

算法处理流程

物流方向的大多数业务算法处理流程基本是按照模型建立、算法开发、算法测试流程进行，具体步骤如下：

模型建立

大多数优化问题都能构建成线性规划、非线性规划或混合整数规划等数学模型。这些模型需要根据实际业务确定，模型主要包含以下因素：

1）  优化目标

2）  决策变量

3）  约束条件

算法开发

模型的求解可根据实际的业务情况（问题复杂程度、数据规模、计算时效要求）等采用合适的精确算法和近似的最优化算法进行求解。

模型精确计算

模型精确求解有一些商业和开源的求解器，如下：Gurobi、Cplex、SCIP、OR-Tools、Glpk等，可以根据实际情况选择合适的求解器。

最优化算法计算

最优化算法也有很多，比如变邻域搜索算法、自适应大邻域搜索算法、禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法、人工鱼群算法、人工蜂群算法等，可以根据适用情况选择。

业务相关开放项目计算

解物流领域的某些项目可以利用一些开放性的项目来求解，如求解车辆路径问题的jsprit、求解排程类问题的optaplanner等，这类问题在模型建立好之后可以调用这些开放性项目来求解。

算法测试

生产数据测试

物流方向的项目基本都是优化类型的项目，每个项目对应的业务环节一直在运行，涉及到的优化问题或者是业务系统简单处理，或者人为计算，对于算法有效性的检测可以把这部分生产数据独立抽离出来，经过优化算法计算之后跟原有系统数据进行相关的对比，来评价算法的优化效果。

仿真测试

物流的优化不像互联网应用可以采用流量灰度的方式进行直接的验证，并且物流系统的链路非常长，单点的改变可能引起上下游的变化。在决策优化的过程中需要同时使用优化求解及仿真技术来验证或提供决策依据。仿真测试验证大致需要以下过程：

1）  定义仿真模型确定绩效指标体系

2）  输入算法结果数据到仿真模型进行仿真计算

3）  根据仿真模型的仿真结果计算绩效指标，以反馈算法的优化效果。

算法服务平台建设

实际业务中的很多应用场景都可以抽象成同一类算法问题。算法在解决不同应用场景业务问题时，相关模型、处理流程及计算方法也都大致相同，因此可以对这类问题的算法，按照其处理流程从业务中剥离出来，封装好算法的输入、输出及计算逻辑，构建统一的算法服务平台。

VRP算法服务

比较经典的VRP问题就会应用到很多业务场景，即时配、大件配送、冷链配送、门店补货等。这些业务场景对于大型零售商来说是比较常见的，因此构建可灵活配置的VRP算法服务平台，可达成一次构建，多场景应用的效果。

排班算法服务

排班问题也是一样，无论是生产线工人排班、司机排班、客服排班还是门店工作人员排班，这些都是排班问题应用的业务场景。通过构建可灵活配置的排班算法服务平台，可解决多个业务场景的排班问题。

装箱算法服务

装箱问题也有着丰富的应用场景，无论是商品配送的车辆装箱、运输网络的车型推荐及包装作业的包材推荐都是装箱问题的业务场景。构建灵活的装箱算法服务平台，可通过配置有效的解决各业务场景的装箱问题。

运筹规划算法服务

无论是上面提到的一些算法服务还是其他组合优化问题，都可以构建成运筹优化问题来解决。大家熟知的google or-tools就是组合优化问题的工具包。我们也可以根据自身的业务特点构建适合业务场景的运筹规划算法服务，底层可以调用不同的求解器，可以是商业求解器，如gurobi、cplex等，也可以是开源求解器，如scip、glpk等；也可以是一些最优化算法，如邻域搜索等。

㈢ 什么是禁忌搜索遗传算法

http://book.idoican.com.cn/detail/DefaultView.aspx?BookId=ISBN7-111-08090-4.1

㈣ 禁忌搜索算法与传统优化算法的区别

背景：禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。
使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用

㈤ 禁忌搜索算法的简介

又名“tabu搜索算法”
为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。
当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。

㈥ 禁忌搜索算法的其他算法

禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.
遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。
蚂蚁算法是群体智能可用于解决其他组合优化问题,比如有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。

㈦ 禁忌搜索算法的介绍

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

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

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