計算智能-遺傳算法

1、實例實例1：3-PRR并聯(lián)定位平臺的運動學標定 工作空間：工作空間：50mm，10 PRO/EPRO/E中的機械設計圖中的機械設計圖 3-PRR3-PRR并聯(lián)平臺實物樣機并聯(lián)平臺實物樣機 實例實例1：3-PRR并聯(lián)定位平臺運動學模型 由并聯(lián)平臺矢量約束關系 iiiiii OPPCOAA BB C lllll 可得到動平臺在工作空間內任意 位姿下，三個直線超聲電機的運 動學逆解 實例實例1：3-PRR并聯(lián)定位平臺運動學標定 令上式等號左邊為Ei，i=1,2,3 選取N組位形，求得相應電機輸出，驅動電機 到理論位置測得實際平臺位形，基于粒子群算 法求得使J小于一定誤差時的 實例實例1：3-PRR并

2、聯(lián)定位平臺運動學標定 1. Zhang Q, Mills J K, Cleghorn W L, et al. Dynamic model and input shaping control of a flexible link parallel manipulator considering the exact boundary conditionsJ. Robotica, 2015, 33(06): 1201-1230. 2.周麗平, 張泉, 孫志峻. 直線超聲電機驅動的平面 3-PRR 并聯(lián)平臺的運動學標定J. 機器人, 2014, 36(4): 485-490. 實例實例2：柔順機構的非

3、線性運動學建模：柔順機構的非線性運動學建模 5 拓撲優(yōu)化法設計的平面三拓撲優(yōu)化法設計的平面三 自由度柔順微動平臺自由度柔順微動平臺 微動平臺實驗系統(tǒng)微動平臺實驗系統(tǒng) 該平臺平移行程約該平臺平移行程約40m40m，分辨率，分辨率1nm 1nm 以內以內，轉角行程約轉角行程約4rad4rad，分辨率，分辨率 0.2rad0.2rad。 思考：思考：如何建立如何建立 輸入輸出模型？輸入輸出模型？ 實例實例2：柔順機構的非線性運動學建模：柔順機構的非線性運動學建模 基于雙隱含層基于雙隱含層BPBP神經網絡的非線性模型辨識神經網絡的非線性模型辨識 計算智能計算智能 n 計算智能涉及神經計算、模糊計算、進

4、化計算和人 工生命等領域，這些研究領域體現出生命科學與信息 科學的緊密結合，也是廣義人工智能力圖研究和摹仿 人類和動物智能(主要是人類的思維過程和智力行為) 的重要進展。 n 把計算智能理解為智力的低層認知，它主要取決于 數值數據而不依賴于知識。人工智能是在計算智能的 基礎上引入知識而產生的智力中層任知。生物智能， 尤其是人類智能，則是最高層的智能。即CIAIBI。 計算智能計算智能 1. 概述 2. 遺傳算法 3. 粒子群算法 4. 神經網絡 1. 概述概述 什么是計算智能，它與傳統(tǒng)的人工智能的區(qū)別？ 第一個對計算智能的定義是由貝茲德克(Bezdek)于 1992年提出的。他認為，從嚴格意義

5、上講，計算智能 取決于制造者提供的數值數據，而不依賴于知識；另 一方面，人工智能則應用知識精品。 1. 概述概述 總結： 計算智能是一種智力方式的低層認知，它與人工智能的區(qū) 別只是認知層次從中層下降到低層而已。中層系統(tǒng)含有知識(精 品)，低層系統(tǒng)則沒有。 若一個系統(tǒng)只涉及數值(低層)數據，含有模式識別部分，不 應用人工智能意義上的知識，而且能夠呈現出：計算適應性； 計算容錯性；接近人的速度；誤差率與人相近，則該系 統(tǒng)就是計算智能系統(tǒng)計算智能系統(tǒng)。 若一個智能計算系統(tǒng)以非數值方式加上知識(精品)值，即成 為人工智能系統(tǒng)人工智能系統(tǒng)。 圖靈測試圖靈測試 圖靈測試一詞來源于計算機科學和密碼學的先驅阿

6、 蘭麥席森圖靈：1950年設計出這個測試，其內容是， 如果電腦能在5分鐘內回答由人類測試者提出的一系 列問題，且其超過30%的回答讓測試者誤認為是人類 所答，則電腦通過測試。 2014年6月7日是計算機科學之父阿蘭圖靈（Alan Turing）逝世60周年紀念日。這一天，在英國皇家學 會舉行的“2014圖靈測試”大會上，聊天程序“尤 金古斯特曼”（Eugene Goostman）首次“通過”了 圖靈測試。 圖靈測試圖靈測試 上述兩種對話的區(qū)別在于，第一種可明顯地感到回答者是從知 識庫里提取簡單的答案，第二種則具有分析綜合的能力，回答 者知道觀察者在反復提出同樣的問題。 2. 2. 遺傳算法遺傳

7、算法 遺傳算法是源于達爾文生物進化理論的“自然選擇 ”、“適者生存”法則而提出的一種搜索尋優(yōu)算法搜索尋優(yōu)算法?；?本思想：將每個可能的問題解表示成“染色體”，從而 得到一個由染色體組成的“群體”，這個群體被限制在 問題特定的環(huán)境里，根據預定的目標函數對每個個體進 行評價，給出了一個合適度值。開始時總是隨即地產生 一些個體，即侯選解，利用遺傳算法對這些個體按”適 者”有更多的機會生存的原則進行交叉組合產生后代， 后代由于繼承了父代的一些優(yōu)良性狀，因而明顯優(yōu)于上 一代，這樣“染色體”的群體將逐步朝著更優(yōu)解的方向 進化。 2. 2. 遺傳算法遺傳算法 遺傳算法的基本步驟：遺傳算法的基本步驟： 第1步

8、 根據由問題確定的編碼規(guī)則，隨即產生初始群體； 第2步.計算群體中每個個體的適應度值； 第3步.如果解滿足要求或遺傳代數超過指定代數，則結束； 否則繼續(xù)執(zhí)行第4步； 第4步.根據適應值進行選擇復制產生新一代； 第5步.根據事先確定的交叉和變異概率選擇部分個體進行交 叉和變異，轉第2步； 2. 2. 遺傳算法遺傳算法 遺傳算法的基本過程：遺傳算法的基本過程： begin 1. 1. 選擇適當表示，生成初始群體；選擇適當表示，生成初始群體； 2. 2. 評估群體；評估群體； 3.3. While 未達到要求的目標未達到要求的目標 do begin 1. 1. 選擇作為下一代群體的各個體；選擇作為下

9、一代群體的各個體； 2. 2. 執(zhí)行交換和突變操作；執(zhí)行交換和突變操作； 3. 3. 評估群體；評估群體； end end 2. 2. 遺傳算法遺傳算法 對于一個對于一個SGA算法來說主要涉及以下內容：算法來說主要涉及以下內容： 編碼和初始群體生成；編碼和初始群體生成； 群體的評價；群體的評價； 個體的選擇；個體的選擇； 交換；交換； 突變；突變； 2. 2. 遺傳算法遺傳算法 在講解中會結合如下的貨郎擔問題(Travelling Salesman Problem，簡記為TSP)：設有n個城市，城市i和城市j之間的距 離為d(i，j) i, j=1,.,nTSP問題是要找遍訪每個域市恰好一次

10、的一條回路，且其路徑總長度為最短。 2.1 2.1 遺傳算法的基本機理遺傳算法的基本機理 一一. .編碼與解碼編碼與解碼 許多應用問題的結構很復雜，但可以化為簡單的位串形式 編碼表示。 1.編碼編碼:將問題結構變換為位串形式編碼表示的過程； 2.解碼解碼(或譯碼):而相反將位串形式編碼表示變換為原問題 結構的過程。 把位串形式編碼表示叫染色體染色體，有時也叫個體個體。 3.常用的編碼方法： .二進制編碼 假設某一參數的取值范圍是A,B,用長度為l的二進制串來 表示該參數，將A,B等分成2l-1個子部分，記每一等分的長度 為，則它能夠產生2l個不同的編碼，如下： 00000=0 A 00001=

11、1 A + 其中 11111=2l-1 B 假設某一個體的編碼是：X:xlxl-1xl-2x2x1 則二進制編碼所對應的解碼公式為 缺點:長度較大 B - A = 2l - 1 B A l x=A + .xi.2i-1 2l 1 i=1 例，x屬于0,1023用長度為10的二進制進行編碼，則 x=0010101111，表示一個個體，對應175，編碼精度為1. 3.常用的編碼方法： .浮點數編碼 個體的每個染色體用某一范圍內的一個浮點數來表示,個 體的編碼長度等于其變量的個數。 .格雷碼 連續(xù)的兩個整數所對應的編碼值之間只有一個碼位是不相 同的，其余碼位都完全相同。 (4).符號編碼 用無實際意

12、義的符號進行編碼，如A，B,C，D，或1，2， 3，4，5，6 二.適應度函數 為了體現染色體的適應能力而引入的對問題中的每一個染色體 都能進行度量的函數。通過適應度函數來決定染色體的優(yōu)、劣程 度，它體現了自然進化中的優(yōu)利劣汰原則。 例如： 對優(yōu)化問題，適應度函數就是目標函數。 TSP的目標是路徑總長度為最短，路徑總長度的倒數就可以為TSP的適應度函 數： 適應度函數要有效反映每一個染色體與問題的最優(yōu)解染色體之 間的差距，一個染色體與問題的最優(yōu)解染色體之間的差距小，則對 應的適應度函數值之差就小，否則就大。遺傳算法中的適應度函數 以越大越接近最優(yōu)解為準，這與他輪盤概率選擇下一代相關。 三.遺傳

13、操作 簡單遺傳算法的遺傳操作主要有三種:選擇(selection)、交叉(crossover)、變 異(mutation)。改進的遺傳算法大量擴充了遺傳操作，以達到更高的效率。 1.選擇操作選擇操作 也叫復制操作，對自然界對自然界“適者生存適者生存”的模擬的模擬。根據個體的適應度函數值所度 量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。 一般地說，選擇將使適應度較大(優(yōu)良)個體有較大的存在機會，而適應度較 ?。ǖ土樱┑膫€體繼續(xù)存在的機會也較小。簡單遺傳算法采用賭輪選擇機制， 令fi表示群體的適應度值之總和，fi表示種群中第i個染色體的適應度值，它產 生后代的能力正好為其適應度值所占份額fif

14、i。 2.交叉交叉 是GA中最主要的遺傳操作，其工作于選擇過程結束后產生的下一代群體。 交叉操作應用于從這一群體中隨機選擇的一系列個體對（串對）。 SGA采用的是單點交換。設串長為L，交換操作將隨機選擇一個交換點 （對應于從1到L-1的某個位置序號），緊接著兩串交換點右邊的子串互換，從 而產生了兩個新串。例如，設1，2為要交換的串，交換點被隨機選擇為7 （串長為10）。 11000011111 21111111011 交換得新串1，2： 11000011011 21111111111 當然，并非所有選中的串對都會發(fā)生交換。這些串對發(fā)生交換的概率是Pc。 Pc為事先指定的01之間的值，稱為交換率

15、。 3.變異變異 一般在交換后進行。突變操作的對象是個體（即串），旨在改 變串中的某些位的值，即由0變?yōu)?，或由1變?yōu)?。并非所有位都 能發(fā)生變化，每一位發(fā)生變化的概率是Pm。Pm為事先指定的0 1之間的某個值，稱為變異率。串中每一位的突變是獨立的，即某 一位是否發(fā)生突變并不影響其它位的變化。變異的作用是引進新變異的作用是引進新 的遺傳物質或恢復已失去的遺傳物質的遺傳物質或恢復已失去的遺傳物質。例如，若群體的各串中每 一位的值均為0，此時無論如何交換都不能產生有1的位，只有通 過突變。 例如：10100110 對從右往左的第5位進行變異操作 10110110 四四.控制參數控制參數 1.交叉概

16、率和變異概率交叉概率和變異概率 并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定 的概率進行，一般在程序設計中交叉發(fā)生的概率要比變異發(fā)生的概率選取得大 若干個數量級，交叉概率取0.6至0.95之間的值；變異概率取0.001至0.01之間的 值。 2.種群規(guī)模種群規(guī)模 指種群的染色體總數，它對算法的效率有明顯的影響，規(guī)模太小不得于 進化，而規(guī)模太大將導致程序運行時間長。對不同的問題可能有各自適合的種 群規(guī)模，通常種群規(guī)模為30至100。 3.個體長度個體長度 有定長和變長兩種。它對算法的性能也有影響。 舉例舉例： 來說明遺傳算法的一個進化循環(huán)。設每一串的長度為10，共有4個串組成

17、第一 代群體（POP1），目標函數（適應函數）為各位值之和 2.2 2.2 遺傳算法的求解步驟遺傳算法的求解步驟 一一.遺傳算法的特點遺傳算法的特點 遺傳算法是一種基于空間搜索的算法，它通過自然選擇、遺 傳、變異等操作以及達爾文適者生存的理論，模擬自然進化過程 來尋找所求問題的解答。遺傳算法具有以下特點： 1. 遺傳算法是對參數集合的編碼而非針對參數本身進行進化； 2. 遺傳算法是從問題解的編碼組開始而非從單個解開始搜索； 3. 遺傳算法利用目標函數的適應度這一信息而非利用導數或其 它輔助信息來指導搜索； 4. 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī) 則進行隨機操作。 2.2 2

18、.2 遺傳算法的求解步驟遺傳算法的求解步驟 最主要的特點體現在下述兩個方面最主要的特點體現在下述兩個方面: : .智能性 進化算法的智能性包括自組織、自適應和自學習等。應用進化算法求 解問題時,在確定了編碼方案、適應值函數和遺傳算子以后，算法將利用進 化過程中獲得的信息自行組織搜索。進化算法的這種智能性特征同時賦予 了它具有根據環(huán)境的變化自動發(fā)現環(huán)境的特性和規(guī)律的能力。 .本質并行性 進化算法的本質并行性表現在兩個方面:一是進化算法是內在并行的， 即進化算法本身非常適合大規(guī)模并性。二是進化算法的內含并行性，由于 進化算法采用種群的方式組織搜索，因而它可以搜索解空間內的多個區(qū)域， 并相互交流信息

19、。 2.2 2.2 遺傳算法的求解步驟遺傳算法的求解步驟 一般遺傳算法的主要步驟如下：一般遺傳算法的主要步驟如下： (1) 隨機產生一個由確定長度的特征字符串組 成的初始群體。 (2)對該字符串群體迭代的執(zhí)行下面的步(a)和 (b)，直到滿足停止標準： (a) 計算群體中每個個體字符串的適應值； (b) 應用復制、交叉和變異等遺傳算子產生下 一代群體。 (3)把在后代中出現的最好的個體字符串指定為 遺傳算法的執(zhí)行結果，這個結果可以表示問題的 一個解。 2.2 2.2 遺傳算法的求解步驟遺傳算法的求解步驟 三三. .遺傳算法求解舉例遺傳算法求解舉例 用遺傳算法求解函數 f(x)=x.sin(10

20、.x)+1.0 的最大值，其中x-1,2。 首先用高等數學的方法求解， 先求導數，令其為0， 最后求得 x1.85 f(x)2.85 2.2 2.2 遺傳算法的求解步驟遺傳算法的求解步驟 1.1.方案表示方案表示 用二進制矢量表示一個染色體。 假設精度取小數點后6位數。-1，2將被均勻地分為31000000個等長 的區(qū)間。因為 2097152=2213000000222=4194304，每個染色體由22位字 節(jié)的二進制矢量表示。 二進制串和區(qū)間-1，2中的x之間的映射關系為 將二進制串轉化為相應的十進制： 21 ()2=(bi.2i)10=x i=0 找到相應的實數x: x=-1.0 + x*3/(222-1) 例如：二進數(10001011101101010001