禁忌搜索算法c

‘壹’ 哪个大神有时间帮我对VRP问题用禁忌搜索算法编写一个lingo或者c语言可以

求最短配送路径的话 应该是TSP问题吧，不应该是VRP问题。
LINGO能很好地求解这两类模型，但用的整数规划原理或动态规划原理，不能用禁忌搜索。
禁忌搜索，就用C或许能解决。

‘贰’ 禁忌搜索算法的其他算法

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

‘叁’ 禁忌搜索算法的简介

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

‘肆’ 禁忌搜索算法的介绍

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

‘伍’ 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;
}

‘陆’ 跪求 用禁忌搜索算法解组合优化，5个城市走一遍最优路径，有没有C或c++的源代码

http://www.pudn.com/downloads114/sourcecode/math/detail477511.html

http://wenku..com/view/8de9ac5d3b3567ec102d8aa1.html
你自己改一下吧

‘柒’ 请问关于禁忌搜索算法

禁忌（TabuSearch）算法是一种亚启发式(meta-heuristic)随机搜索算法[1]，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。Tabu表中保存了最近若干次迭代过程中所实现的移动的反方向移动，凡是处于Tabu表中的移动，在当前迭代过程中是不允许实现的，这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解群，从而防止了循环，帮助算法摆脱局部最优解。另外，为了尽可能不错过产生最优解的“移动”，TS搜索还采用“释放准则”的策略。

‘捌’ 禁忌搜索算法源代码

禁忌搜索法：使用一个禁忌表，记录下不允许搜索的元素。在后面的搜索中，根据禁忌表来决定如何处理当前元素。用在约瑟夫环中，我们可以用一个数组记录下已经出圈的人的编号，这样再数数时，可以根据禁忌表来判断此人是否还在圈内。

#define N 100
void yuesefu1(int data[],int result[],int sum,int k)
{
int i=0,j=0,count=0;
int n;
while(count<sum)
{
for(n=0;n<count;n++)/*根据禁忌表判断此人是否还在圈内*/
if(result[n]==data[i])
break;
if(n>=count)/*若此人还在圈内*/
j++;
if(j==k)
{
result[count++]=data[i];/*把出圈的人的编号存入禁忌表*/
j=0;
}
i++;
if(i==sum)
i=0;
}
}

void main()
{
int data[N];
int result[N]={0};
int i,j,total,k;
printf("\nPlease input the number of every people.\n");
for(i=0;i<N;)
{
int input;
scanf("%d",&input);
if(input==0)
break;
for(j=0;j<i;j++)
if(data[j]==input)
break;
if(j>=i&&input>0)
{
data[i]=input;
i++;
}
else
printf("\nData error.Re-input:");
}
total=i;
printf("\nYou have input:\n");
for(i=0;i<total;i++)
{
if(i%10==0)
printf("\n");
printf("%4d",data[i]);
}
printf("\nPlease input a number to count:");
scanf("%d",&k);
yuesefu1(data,result,total,k);
printf("\nThe sequence is:\n");
for(i=0;i<total;i++)
printf("%d ",result[i]);

‘玖’ 禁忌搜索算法的主要思想和特征

禁忌算法是一种亚启发式随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.