西北工业大学算法设计实验三.doc

实验三：遗传算法VS回溯法
一、问题分析
回溯法可以处理货郎担问题，遗传算法也可以处理货郎担问题，回溯法和遗传算法哪个算法处理货郎担问题效率更高呢？在相同计算时间内，哪个算法得到的解更好呢？
实现遗传算法，通过随机产生10个不同规模的算例（城市数量分别为10，20，40，80，100，120，160，180，200，500，或者其它规模），比较上次实验实现的回溯法和遗传算法。
二、算法基本思想
1、回溯法
从初始状态出发，搜索其所能到达的所有“状态”，
当一条路走到尽头 ，再后退一步或若干步，从另外一种状态出发，继续搜索，直到所有的路径都搜索过。这种不断前进 、不断回溯寻找解的方法叫回溯法。
回溯法通常将问题解空间组织成“树”结构，采用系统的方法搜索解空间树，从而得到问题解。
搜索策略：
深度优先为主，也可以采用广度优先、函数优先、广度深度结合等。
避免无效搜索策略：
约束函数：在扩展结点处剪去不满足约束条件的子树
界限函数：在扩展结点处剪去得不到最优解的子树

2、遗传算法
首先针对遗传算法要有种群，个体，适应度函数，选择，交叉，变异。对于种群是由若干个个体组成，其中个体的编码可以用走过的每一个城市的路径表示。适应度函数用一个路径的代价的倒数表示。使用轮盘赌的方式进行选择下一代个体。其中轮盘赌的方式可以转换为每一个个体的适应度与种群的适应度的比例进行比较。先随机选择两个个体，根据交叉的概率进行单点交叉，将较优的交叉结果保留下来。接着在种群中选择一个个体，根据变异概率来判断是否变异，将该个体保留，根据生成的子代的个数重复上述的运算。根据指定的代数，重复上述的运算。

三、算法设计
1、回溯法
TSP问题的目的是得到一条路径，即一个解向量（X1,X2...Xn），为排列树问题。
对所有城市进行编号后，按大小顺序存储于数组path中，构造一个交换函数swap（）；对数组path进行遍历，判断当前城市与目标城市是否连通，若连通，通过swap函数对当前节点和目标城市进行交换，即树的节点拓展。若不连通则恢复，并进入下一次的循环，循环到叶子节点时，判断叶是否与初始节点相连，并计算代价cost是否小于当前最小代价bestc，若小于，则更新bestc，再返回上一节点，知道遍历完树中的所有节点。

核心代码：
public void backtrack(int depth){//depth深度

if(depth==size){
if(map[path[depth-1]][path[depth]] != -1 && map[path[depth]][path[1]]!= -1
&& cost +map[path[depth]][path[1]]<bestc){
bestp=path.clone();
bestc = cost + map[path[depth]][path[1]];
//bestc = cost +a[path[i-1]][path[i]]+a[path[i]][path[1]];
//重复计算了上一边
}
}else{
for(int j =depth;j<=size;j++){
if(map[path[depth]][path[j]]!=-1){
swap(path,depth+1,j);
cost +=map[path[depth]][path[depth+1]];
//System.out.println(Arrays.toString(x)+":"+cost);
backtrack(depth+1);
cost -=map[path[depth]][path[depth+1]];
swap(path,depth+1,j);
}
}
}
}

2、 遗传算法
先设计个体，个体里面用城市的邻接矩阵map[][]表示，当前路径path[]，当前路径的代价cost，适应度值。主要方法有随机初始化当前路径，计算路径代价，适应度值的求解。
针对旅行商的问题，设计初始化种群，生成下一代种群，生成下一代种群包含选择，交叉，变异的方法。在交叉的结果会产生同一个城市重复两次，所以需要一个修复方法。

核心代码：
public void solve() {
int i;
int k;
// 初始化种群
initGroup();
// 计算初始化种群适应度，Fitness[max]
for (k = 0; k < scale; k++) {
fitness[k] = evaluate(oldPopulation[k]);
// System.out.println(fitness[k]);
}
// 计算初始化种群中各个个体的累积概率，Pi[max]
countRate();
System.out.println("初始种群...");
for (k = 0; k < scale; k++) {
for (i = 0; i < size; i++) {
System.out.print(oldPopulation[k][i] + ",");
}
System.out.println();
System.out.println("----" + fitness[k] + " " + Pi[k]);
}

for (t = 0; t < MAX_GEN; t++) {
//evolution1();
evolution();
// 将新种群newGroup复制到旧种群oldGroup中，准备下一代进化
for (k = 0; k < scale; k++) {
for (i = 0; i < size; i++) {
oldPopulation[k][i] = newPopulation[k][i];
}
}
// 计算种群适应度
for (k = 0; k < scale; k++) {
fitness[k] = evaluate(oldPopulation[k]);
}
// 计算种群中各个个体的累积概率
countRate();
}

System.out.println("最后种群...");
for (k = 0; k < scale; k++) {
for (i = 0; i < size; i++) {
System.out.print(oldPopulation[k][i] + ",");
}
System.out.println();
System.out.println("---" + fitness[k] + " " + Pi[k]);
}
System.out.println("最佳长度出现代数：");
System.out.println(bestT);
System.out.println("最佳长度");
System.out.println(bestc);
System.out.println("最佳路径：");
for (i = 0; i < size; i++) {
System.out.print(bestp[i] + ",");
}
}
public static void main(String[] args) throws IOException {
long startTime = System.currentTimeMillis(); //获取开始时间
System.out.println("Start....");
ycTSP yc = new ycTSP(30, 40, 1000, 0.8f, 0.9f);
yc.init("C://data.txt");
yc.solve();
System.out.println("");
long endTime = System.currentTimeMillis();
//获取程序运行时间
System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
}
}
五、算法复杂性理论分析
1、回溯法
TSP问题是排列树问题，因而该算法的时间复杂度为O(n!)。
2、遗传算法

六、算法代码（单独文件提交）
见项目文件
七、算法复杂性实验分析
遗传算法中种群规模为30，运行代数为1000，交叉率为0.8，变异率为0，9
问题规模
回溯法
遗传算法
5
3ms
44ms
10
10ms
87ms
20
272510ms
110ms
25
--
124ms
30
--
141ms
40
--
188ms

八、实验中的问题总结
回溯法：
优点：采用深度优先，可以快速的找到一组解，并依此为参照（bestc）。当搜索完解空间时便可以得最优解。
缺点：需要搜索大量的结点，工程浩大，速度慢，而且随着结点的个数不断地增加之后，解空间按照阶乘的增长速度增加，算法效率较低。

遗传算法：
遗传算法在问题规模较小的时候，不一定会比回溯法快，但在问题规模大的时候，就会有较明显的优势，虽然不一定会给出最优解，但会有一个较好的解。