遺傳規(guī)劃GeneticProgramming概述

1、遺傳規(guī)劃GeneticProgramming概述1 概述一、GA的局限性 （1）不能描述層次化問題： 許多問題的自然描述往往是一種層次化的計算機程序。 例： 但在許多情況下，程序的結(jié)構(gòu)和大小在問題解決之前無法知道用何種函數(shù)逼近。 （2）不能描述計算機程序： 即使程序確定，采用定長的字符串方法也不能描述 計算機程序。例：求 的程序（3）缺少動態(tài)可變性 定長的字符串描述不具備動態(tài)可變性 。二、遺傳規(guī)劃的基本知識 例：某地10月份降雨量與預(yù)報因子的實例數(shù)據(jù)： 年號1234567891011121314151617預(yù)報因子97479584961132416473742142335278596降雨量實測

2、值34172825315286149133141093648 用函數(shù)擬合，以便進(jìn)行預(yù)報 （1） （2） （3） （4） 找到一種函數(shù)能最好地擬合表中的數(shù)據(jù)。 a、初始群體的形成 初始群體由隨機產(chǎn)生的計算機程序組成，而計算 機程序又由函數(shù)和變量組成。 如上例： b、個體適應(yīng)性測度： 群體中的個體的適應(yīng)度取決于其逼近真實解的好壞程度，這種測度稱為適應(yīng)度： 年號預(yù)報因子實測值計 算 機 程 序 返 回 值xy個體1個體2個體3個體4197.00034.000113.070653.299-4.63440.185247.00017.00052.57018.766-5.91523.169395.00028

3、.000110.650566.816-4.67139.554484.00025.00097.340259.572-4.88836.022596.00031.000111.860608.523-4.65239.8706113.00052.000132.4302034.560-4.36445.130724.0008.00024.7403.666-7.10313.902816.0006.00015.0602.077-7.81910.215947.00014.00052.57018.766-5.91523.1691037.0009.00040.4709.226-6.33719.3181142.0001

4、3.00046.52013.158-6.11321.2711214.0003.00012.6401.802-8.0559.2301323.00014.00023.5303.415-7.17813.4601435.00010.00038.0508.005-6.43618.5191527.0009.00028.3704.536-6.89415.2041685.00036.00098.550278.672-4.86736.3481796.00048.000111.860608.523-4.65239.87.誤差絕對值總和753.2805123.380457.493118.518c、復(fù)制和交換操作 復(fù)

5、制操作根據(jù)適應(yīng)度的比例原則。 交換操作： 從當(dāng)代群體中選擇雙親個體進(jìn)行交換產(chǎn)生新 的個體，在交換過程中由于雙親個體可能具 有不同的結(jié)構(gòu)和大小，產(chǎn)生的子代也會大不 相同。 例：將個體2淘汰，個體4被復(fù)制分?jǐn)?shù)為2 復(fù)制操作：根據(jù)適應(yīng)度比例原則，個體適應(yīng)度越好進(jìn)行 交換的概率就越大。假定2、3交換，1、4交換：部分交換 計算適應(yīng)度年 號預(yù)報因子實測值計 算 機 程 序 返 回 值xy個體1個體2個體3個體4197.00034.00034.85044.4715.682120.474247.00017.00018.27320.2544.78258.374395.00028.00034.23543.572

6、5.656117.990484.00025.00030.79438.5465.503104.328596.00031.00034.54344.0225.669119.2326113.00052.00039.66751.5075.871140.346724.0008.0009.2447.0653.94729.808816.0006.0005.6521.8183.44419.872947.00014.00018.27320.2544.78258.3741037.0009.00014.52014.7724.48545.9541142.00013.00016.42317.5524.64252.1641

7、214.0003.0004.6920.4153.27817.3881323.00014.0008.813604353.89428.5661435.00010.00013.74213.6354.41643.4701527.0009.00010.5128.9184.09333.5341685.00036.00031.11139.0095.518105.5701796.00048.00034.54344.0225.669119.232誤差絕對值總和75.31498.908276.225857.676d、遺傳規(guī)劃的重要特征： （1）產(chǎn)生的結(jié)果具有層次化特征。 （2）隨著進(jìn)化的延續(xù)，個體不斷朝問題答 案

8、的方向動態(tài)地發(fā)展。 （3）不需要先確定或限制最終答案的結(jié)構(gòu) 或大小。 （4）輸入中間結(jié)果和輸出是問題的自然描 述。三、遺傳規(guī)劃的一般方法和步驟： （1）隨機產(chǎn)生初始群體，即產(chǎn)生眾多函數(shù)和變量隨機組成 的計算機程序。 （2）運行群體中的每一個計算機程序（個體），計算適應(yīng) 度。 （3）生成下一代群體。 根據(jù)適應(yīng)度隨機復(fù)制新一代個體 通過在雙親個體隨機選定的部位進(jìn)行交換產(chǎn)生新的 個體，雙親個體也依據(jù)適應(yīng)度隨機選定。 （4）迭代執(zhí)行（2）（3）直到終止準(zhǔn)則滿足為止。 流程圖：2 遺傳規(guī)劃的基本原理一、個體的描述方法 用一系列可行的函數(shù)對個體進(jìn)行描述： 個函數(shù)： 終止符個數(shù)： 函數(shù) 有 個自交點。 函數(shù)

9、集內(nèi)的函數(shù)可以是： （1）算術(shù)運算符： 、 、 、 （2）標(biāo)準(zhǔn)數(shù)學(xué)函數(shù)：SIN 、COS、EXP、LOG （3）布爾運算符：AND、OR、NOT （4）條件表達(dá)式：IFTHENELSE （5）可迭代函數(shù)：DOUNTIL、REPEAT （6）可遞歸函數(shù) （7）自定義函數(shù)：終止符：變量： 常量：（布爾型NIL）例： 函數(shù)集：F=AND、OR、NOT 終止符集：T=DO、DI DO、DI 布爾變量，無 自變量。F與T的并集：考慮：若函數(shù)有偶個自變量則該函數(shù)返回“T”否則“NIL”： 二、初始群體的生成 a、初始個體生成原理 用隨機方法產(chǎn)生所需解決問題的各種符號表達(dá)式（算法樹）。 在函數(shù)集合F中按均勻

10、分布隨機選出一個函數(shù)作為算法樹的根結(jié)點。 例 ： 隨機選取“”兩個自變量 從函數(shù)F與T終止符中的并集隨機選取一個元素作為尾結(jié)點。 如：“”若是終止符，則該結(jié)點不在生長。A、B、C為終 止符，不斷重復(fù)直到一棵完整的樹。b、初始個體生成的幾種方法 （1）完全法：每一葉子的深度都等于給定的最大深度。 實現(xiàn)方法：若待定結(jié)點的深度小于給定結(jié)點的最大深 度，則該結(jié)點的選擇限制在函數(shù)集內(nèi) F。 （2）生長法：每一葉子的深度不一定等于給定的最大深度。 實現(xiàn)方法：若待定結(jié)點的深度小于給定的最大深度， 則該結(jié)點選擇限制在FUT。 （3）混合法：完全法和混合法的綜合。 初始個體的深度在2至給定的最大深度之間 均勻選

11、取。三、適應(yīng)性度量 a、原始適應(yīng)度（Raw Fitness）計算個體值與實測 值之間的距離。 子代t 在某一個體i： 適應(yīng)度： ：個體i在適應(yīng)度計算試?yán)齤下的返回值； ：適應(yīng)度計算試?yán)龜?shù)； ：適應(yīng)度試?yán)齤的實測值或正確值 ；b、標(biāo)準(zhǔn)適應(yīng)度（Standardized Fitness） 適應(yīng)度最大越好的問題：c、調(diào)整適應(yīng)度d、歸一化適應(yīng)度四、基本算子 a、復(fù)制 （1）適應(yīng)度比例選擇法： 復(fù)制概率： （2）貪婪選擇法： 當(dāng)群體中的個體數(shù)超過1000時，進(jìn)化過程耗時大 長將個體分為兩組、。（ 組適應(yīng)度高，組適應(yīng) 度低 ）80的時間在組選擇，20的時間在組選 擇。 （3）級差選擇法： 按適應(yīng)度將個體分成

12、等級，個體根據(jù)級別進(jìn)行選擇。 （4）競爭選擇法： 首先從群體中隨機選取一組個體，然后從該組中 選出具有較高適應(yīng)度的個體。 b、交換 交換的實現(xiàn)方法：在父代群體隨機選取兩個個體。 在選中的個體中隨機選取一個交換 節(jié)點。 例：交換后：c、終止準(zhǔn)則 最大代數(shù)G 滿足給定的條件3 輔組算子一、突變（Mutation） 依適應(yīng)值或比例的概率隨機選一個體； 在算法樹上隨機選定一個結(jié)點； 然后刪去突變結(jié)點及以下的子樹； 用隨機方法產(chǎn)生一棵子樹插入到突變處。二、排列（Permutation） 隨機選取一個體； 隨機選定個體的算法樹的內(nèi)結(jié)點； 如果該結(jié)點有k個自變量，那么可以ki排列中隨機選； 出一種，對自變量進(jìn)行隨機排列。三、編輯（Editing） 隨機選取一個