用遺傳演算法解決梵塔問題

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的雙圓盤難題。
由上可以看出簡化了難題每一個都比數兄原始難題容易，所以問題都會變成易解的本原問題。
講述：梵塔問題的來源。
提問：知拍一圓盤問題要走幾步？兩圓盤問題要走幾步？三個、四個．．．等？