用遗传算法解决梵塔问题

1. matlab,遗传算法，求大佬帮忙

用遗传算法求最大值问题，可以这样来解决。

1、将最大值问题转换为最小值问题，即 max Z =- min Z；

2、建立其自定义函数，即

z=-(f1*40^1.5/1+f2*30^1.5/2+f2*20^1.5/2+。。。+f12*127^1.5/2+f12*5^1.5/4)

其中：f1,f2,f3,。。。f11,f12为0，1变量，可以用sign（）符号函数来处理。

3、用遗传算法ga（）函数求解，使用方法

objectivef=@ga_func;

nvars=12;

[x, fval] =ga(objectivef,nvars)

4、编程运行后得到

f1=1,f2=1,f3=1,f4=0,f5=1,f6=0,f7=1,f8=1,f9=1,f10=1,f11=1,f12=1

Zmax=27329.5018

2. 什么是梵塔

讲讲什么是梵塔问题，梵塔问题起源于中东地区的一个古老的传说：在梵城（Hana）地下有一个僧侣的秘密组织，他们有3个大型的塔柱，左边的塔柱上由方到小套着64个金盘。僧侣们的工作是要把这64个金盘从左边塔柱转移到右边塔柱上去。但转移过程有规定的：

1、每次只能搬动一只盘子，盘十只能在3个塔柱上安放，不允许放在地上；

2、在每个塔柱上，只允许把小盘十叠在大盘上，反之不允许。

据传说，僧侣们完成这个任务时，世界的末日就来临了。

19世纪，法国的一位数学家对该课题进行过研腊伏究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：

264-1=18446744073709551615（20位）

假设僧侣们个个身强力壮，每烂尺天24小时不知头疲倦地工作，而且一秒钟移动一个金盘，那么，完成这个任务也得花5800亿年。

为什么264-1是解决梵塔问题的最小步数呢？我想，是这样的，如果我们假设只有两个盘，有A（始塔），B（终塔），C（中间塔），那么从A→B只需3次轮历携；如果有三个盘，那么先将前二个盘以C塔为目标圆柱，解放出第三个盘则需（X2+1）次，再重复两个盘时的情况，那么只需（X2+1+X2=2X2+1）次；以此类推则：

X2=2+1→X3=X2+1+X2→……→Xn=Xn-1+1+Xn-1

即Xn=2（Xn-1+1）-1=2n-1

3. 遗传算法可以解决哪些问题

遗传算法主要是用来求解最优化问题的。
一般来讲可以求解函数的最大、最小值问题，还可以结合其它一些方法解决（非）线性回归、分类问题等等。

但遗传算法有两个缺点，一是时间长，二是初值的选择会影响收敛的效果。

它的本质，实际上还是随机搜索算法，还是属于所谓的蒙特卡罗式的方法。

4. tSp Concorder算法原理

tsp问题遗传算法将多目标按照线性加权的方式转化为单目标，然后应用传统遗传算法求解
其中w_i表示第i个目标的权重，f_k表示归一化之后的第i个目标值。我们很容易知道，这类方法的关键是怎么设计权重。比如，Random Weight Genetic Algorithm (RWGA) 采用随机权重的方式，每次计算适应度都对所有个体随机地产生不同目标的权重，然后进行选择操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基于线性加权的多目标遗传算法。如果有K个目标，VEGA 会随机地将种群分为K个同等大小子种群，在不同的子种群按照不同的目标函数设定目标值，然后再进行选择操作。VEGA 实质上是基于线性加权的多目标遗传算法。VEGA 是第一个多目标遗传算法，开启了十几年的研究潮流。
1.TSP问题是指假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。本文使用遗传算法解决att30问题，即30个城市的旅行商问题。旅行商问题是一个经典的组合优化问题。一个经典的旅行商问题可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。TSP问题可以分为对称和不对称。在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图，而不对称TSP则形成有向图。对称性TSP问题可以将解的数量减少了一半。所以本次实验的TSP问题使用att48数据，可在tsplib中下载数据包。演化算法是一类模拟自然界遗传进化规律的仿生学算法，它不是一个具体的算法，而是一个算法簇。遗传算法是演化算法的一个分支，由于遗传算法的整体搜索策略和优化计算是不依赖梯度信息，所以它的应用比较广泛。我们本次实验同样用到了遗传算法（用MATLAB编写）来解决TSP问题。

5. 移梵塔问题中，若将3根柱子改为4根，该怎么做

用递归算法可以简单的写出来~！！滚咐
hannoi(int n,char a,char b,char c)
{if(n==1)
return a->c;
else return hannoi(n-1,b,a,c);
}
#include"stdio.h"
void main()
{hannoi(n,a,b,c);
scanf("%d",&n);
printf("%c->%c",a->b);
printf("%c->%c",b->大银纯c);
printf("%c->%c"搏衡,c->a);
}
时间长了我记不太清了，大致是这样吧~！

6. 如何确定CIR模型中的参数以及将模型用matlab实现

确定适应值函数后，将需要的变量编码为基因正和，然后执行遗传算法举激盯解决问题。这类优化算法是不考虑问题铅碰本身的。

7. 遗传算法的主要步骤

为了使用遗传算法来解决优化问题，准备工作分为以下四步^{［56，57，61］}。

7.4.1 确定问题的潜在解的遗传表示方案

在基本的遗传算法中，表示方案是把问题的搜索空间中每个可能的点表示为确定长度的特征串（通常是二进制串）。表示方案的确定需要选择串长l和字母表规模k。在染色体串和问题的搜索空间中的点之间选择映射有时容易实现，有时又非常困难。选择一个便于遗传算法求解问题的表示方案经常需要对问题有深入的了解。

7.4.2 确定适应值的度量

适应值度量为群体中每个可能的确定长度的特征串指定一个适应值，它经常是问题本身所具有的。适应值度量必须有能力计算搜索空间中每个确定长度的特征串的适应值。

7.4.3 确定控制该算法的参数和变量

控制遗传算法的主要参数有群体规模Pop-Size、算法执行的最大代数N-Gen、交叉概率P_c、变异概率P_m和选择策略R等参数。

（1）群体规模Pop-Size。群体规模影响到遗传算法的最终性能和效率。当规模太小时，由于群体对大部分超平面只给出了不充分的样本量，所以得到的结果一般不佳。大的群体更有希望包含出自大量超平面的代表，从而可以阻止过早收敛到局部最优解；然而群体越大，每一代需要的计算量也就越多，这有可能导致一个无法接受的慢收敛率。

（2）交叉率P_c。交叉率控制交叉算子应用的频率，在每代新的群体中，有P_c·Pop-Size个串实行交叉。交叉率越高，群体中串的更新就越快。如果交叉率过高，相对选择能够产生的改进而言，高性能的串被破坏得更快。如果交叉率过低，搜索会由于太小的探查率而可能停滞不前。

（3）变异率P_m。变异是增加群体多样性的搜索算子，每次选择之后，新的群体中的每个串的每一位以相等的变异率进行随机改变。对于M进制串，就是相应的位从1变为0或0变为1。从而每代大约发生P_m·Pop-Size·L次变异，其中L为串长。一个低水平的变异率足以防止整个群体中任一给定位保持永远收敛到单一的值。高水平的变异率产生的实质是随机搜索。

比起选择和交叉，变异在遗传算法中是次要的，它在恢复群体中失去的多样性方面具有潜在的作用。例如，在遗传算法执行的开始阶段，串中一个特定位上的值1可能与好的性能紧密联系，也就是说从搜索空间中某些初始随机点开始，在那个位上的值1可能一致地产生适应性度量好的值。因为越好的适应值与串中那个位上的值1相联系，复制作用就越会使群体的遗传多样性损失。当达到一定程度时，值0会从整个群体中的那个位上消失，然而全局最优解可能在串中那个位上是0。一旦搜索范围缩小到实际包含全局最优解的那部分搜索空间，在那个位上的值0就可能正好是达到全局最优解所需的。这仅仅是一种说明搜索空间是非线性的方式，这种情形不是假定的，因为实际上所有我们感兴趣的问题都是非线性的。变异作用提供了一个恢复遗传多样性的损失的方法。

（4）选择策略R。有两种选择策略。一是利用纯选择，即当前群体中每个点复制的次数比与点的性能值成比例。二是利用最优选择，即首先执行纯选择，且具有最好性能的点总是保留到下一代。在缺少最优选择的情况下，由于采样误差、交叉和变异，最好性能的点可能会丢失。

通过指定各个参数Pop-Size、P_c、P_m和R的值，可以表示一个特定的遗传算法。

7.4.4 确定指定结果的方法和停止运行的准则

当遗传的代数达到最大允许代数时，就可以停止算法的执行，并指定执行中得到的最好结果作为算法的结果。

基本的遗传算法

1）随机产生一个由固定长度字符串组成的初始群体。

2）对于字符串群体，迭代地执行下述步骤，直到选择标准被满足为止。

①计算群体中的每个个体字符串的适应值；

②实施下列三种操作（至少前两种）来产生新的群体，操作对象的选取基于与适应度成比例的概率。

选择：把现有的个体串按适应值复制到新的群体中。

交叉：通过遗传重组随机选择两个现有的子串进行遗传重组，产生两个新的串。

变异：将现有串中某一位的字符随机变异产生一个新串。

3）把在后代中出现的最好适应值的个体串指定为遗传算法运行的结果。这一结果可以是问题的解（或近似解）。

基本的遗传算法流程图如图7-1所示。

8. 怎样解决“梵塔”问题

1．设金片只有一片。显然，只要移动1次即可。

2．设金片只有二片。可先将较小金片移至乙针上，较大金片移至丙针上，再将较小金片从乙针移至丙针上，共移动3次。

3．设金片有三片。可先将上面两片金片移到乙上。按2可知，共需移动3次。再把第三片移至丙，又移一次。下面把乙上两片移至丙同2，还需三次。以上共需

2·3+1=7（次）。

4．设金片有四片。先把上面三片移至乙，按3需7次。再把第四片从甲移到丙上，又移一次。最后，把较小的三片从乙移至丙，又需移7次。以上共需移动

2·7+1=15（次）。

依此递推下去。设有k片金片，先将k-1片移至乙，需移动Sk-1次。然后再把第k片移至丙，又移一次。最后把k-1片从丙移至乙，又需Sk-1次。以上共需移动

（2·Sk-1+1）次。

这样，我们可以得到如下的递推式：

Sk=2·Sk-1+1。

根据这个递推公式，分别令k=1，2，3，……，64，得

S1=1＝21-1；

S2=2S1+1=2（21-1）+1=22-1；

S3＝2S2+1=2（22-1）+1=23-1；

S4=2S3+1=2（23-1）+1=24-1；

………………

S64=264-1=18446744073709551615。

如果僧侣移动金片一次需要1秒钟，移动这么多次共需约5845亿年。把这个寓言和现代科学推测对比一下倒是有意思的。按照现代的宇宙进化论，恒星、太阳、行星（包括地球）是在三十亿年前由不定形物质形成的。我们还知道，给恒星特别是给太阳提供能量的“原子燃料”还能维持100～150亿年。因此，我们太阳系的整个寿命无疑要短于二百亿年。可见远不等僧侣们完成任务，地球早已毁灭了。

呵呵，很难理解吧！

9. 什么是梵塔难题人工智能领域里面一般用什么方法解决梵塔难题

梵塔难题
问题 有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆薯猛袭叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
归约过程
（1）移动圆盘A和B至柱子2的双圆盘难题；
（2）移动圆盘C至柱子3的单圆盘难题；
（3）移动圆盘A和B至柱子3的双圆盘难题。
由上可以看出简化了难题每一个都比数兄原始难题容易，所以问题都会变成易解的本原问题。
讲述：梵塔问题的来源。
提问：知拍一圆盘问题要走几步？两圆盘问题要走几步？三个、四个．．．等？