業(yè)務(wù)]第三部分用遺傳算法求解問題(編輯修改稿)
2025-02-13 10:51 本頁面
【文章內(nèi)容簡介】 傳算法求解問題s 選擇選擇 (selection)選擇即從當(dāng)前群體中選出個(gè)體以生成交配池（ mating pool）的過程。所選出的這些個(gè)體具有良好的特征，以便產(chǎn)生優(yōu)良的后代。3. 基于局部競(jìng)爭(zhēng)機(jī)制的選擇基于局部競(jìng)爭(zhēng)機(jī)制的選擇亢米娜漣鑰虞乘羞惶小操襲薦參淘須道燈膘耶情鉗卵妥暇堯毛年美黑晉侶第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s（ 1）繁殖池選擇 相對(duì)適應(yīng)值： 每個(gè)個(gè)體的繁殖量： Ni=round(reli?N)（ 2）轉(zhuǎn)盤賭選擇 2πpi現(xiàn)生成一個(gè) [0， 1]內(nèi)的隨機(jī)數(shù) r，若 p1+p2+…+pi1r≤p1+p2+…+pi ，則選擇個(gè)體 i。 末逆角晌揉蘭佰穗斷似穗跡蚜糟歐憲級(jí)擅剝好四漓說誤晌榴害輸銜札鑷致第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s（ 1）線性排名選擇 首先假設(shè)群體成員按適應(yīng)值大小從好到壞依次排列為 x1， x2， … ， xN，然后根據(jù)一個(gè)線性函數(shù)分配選擇概率 pi。 設(shè)線性函數(shù) pi＝（ a－ bi/（ N +1）） / N， i=1，2， … ， N，其中 a， b為常數(shù)。由于，易得， b=2(a－ 1)。又要求對(duì)任意 i=1， 2， … ， N，有 pi0，且p1≥p2≥…≥ pN，故限定 1≤a≤2。通常使用的值為a=。雨詛拙媳箍探墾節(jié)牽播軒抗器怯澈詣捆增裹躍撕薩矯焦導(dǎo)老姻迄冷功透滁第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s（ 2）非線性排名選擇 將群體成員按適應(yīng)值從好到壞依次排列，并按下式進(jìn)行分配選擇概率：其中 q是常數(shù)，表示最好的個(gè)體的選擇概率。滿涌僑摳存居絞圓強(qiáng)儈頤匝謬醚宛撬奮縷壟輸造粳疲塞夕們壹椽蹦掩鎮(zhèn)一第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s3. 基于局部競(jìng)爭(zhēng)機(jī)制的選擇基于局部競(jìng)爭(zhēng)機(jī)制的選擇（ 1）錦標(biāo)賽選擇 (tournament selection) 選擇時(shí)，先隨機(jī)地選擇在群體中選擇 k個(gè)個(gè)體（放回或不放回）進(jìn)行比較，適應(yīng)值最好的個(gè)體將被選擇作為生成下一代的父體。反復(fù)執(zhí)行該過程，直到下一代個(gè)體數(shù)量達(dá)到預(yù)定的群體規(guī)模。參數(shù) k稱為競(jìng)賽規(guī)模，一般取 k=2。（ 2） (μ， λ)和 μ+λ選擇 (μ， λ)選擇是先從規(guī)模為 μ種群中隨機(jī)選取個(gè)體通過交叉和變異生成 λ（ ≥μ）個(gè)后代，然后再從這些后代中選取 μ個(gè)最優(yōu)的后代作為新的一代種群。 μ+λ選擇則是從這些后代與其父體共 μ+λ個(gè)后代中選取 μ個(gè)最優(yōu)的后代。鄂解紫討蔬鷹祖滯疽銻頸酋拿驚乏膝詐洲瑣墜僅未困春纜蠱擋札妓粉鈍控第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s 交叉操作交叉操作 (crossover)交叉的具體步驟為：– 從交配池中隨機(jī)取出要交配的一對(duì)個(gè)體；從交配池中隨機(jī)取出要交配的一對(duì)個(gè)體；– 根據(jù)位串長度根據(jù)位串長度 L，對(duì)要交配的一對(duì)個(gè)體，對(duì)要交配的一對(duì)個(gè)體，隨機(jī)選取隨機(jī)選取 [1， L1]中一個(gè)或多個(gè)的整數(shù)中一個(gè)或多個(gè)的整數(shù) k作為交作為交叉點(diǎn)；叉點(diǎn)；– 根據(jù)交叉概率根據(jù)交叉概率 pc(0pc≤1)實(shí)施交叉操作，實(shí)施交叉操作，配對(duì)個(gè)體在交叉點(diǎn)處，相互交換各自的部分內(nèi)配對(duì)個(gè)體在交叉點(diǎn)處，相互交換各自的部分內(nèi)容，從而形成新的一對(duì)個(gè)體。容，從而形成新的一對(duì)個(gè)體。對(duì)二進(jìn)制編碼常用的交叉算子有對(duì)二進(jìn)制編碼常用的交叉算子有 單點(diǎn)交叉單點(diǎn)交叉 、 多點(diǎn)多點(diǎn)交叉交叉 和和 均勻交叉均勻交叉 。繹歹薪咸攀剿瑯盟酣祟信早伏蕉堂翠虐街殖蘆臍意彝氣宙鯨照撾彰惋種捅第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s1. 單點(diǎn)交叉單點(diǎn)交叉 對(duì)于從交配池中隨機(jī)選擇的兩個(gè)串s1=a11a12… a1l1a1l2… a1L， s2=a21a22… a2l1a2l2… a2L， 隨機(jī)選擇一個(gè)交叉位 x ?[1， 2， … ， L－ 1] ，不妨設(shè) l1≤ x≤l2，對(duì)兩個(gè)位串中該位置右側(cè)部分的染色體位串進(jìn)行交換，產(chǎn)生兩個(gè)子位串個(gè)體為：s’1=a11a12… a1l1 a2l2… a2L， s’2=a21a22… a2l1 a1l2… a1L例例 考慮如下兩個(gè) 11位變量的父?jìng)€(gè)體：父?jìng)€(gè)體 1： 0 1 1 1 0 0 1 1 0 1 0父?jìng)€(gè)體 2： 1 0 1 0 1 1 0 0 1 0 1交叉點(diǎn)在位置 5，交叉后生成兩個(gè)子個(gè)體：子個(gè)體 1： 0 1 1 1 0 1 0 0 1 0 1子個(gè)體 2： 1 0 1 0 1 0 1 1 0 1 0節(jié)愿兵忙燒氦糯魚榔糊埃宵狂勺綸諜貶痙憑櫻菇屢誨皺壟林肩督漾頁禍洽第三部分 用遺傳算法求解問題s第三部分 用遺傳算法求解問題s2. 多點(diǎn)交叉 對(duì)于選定的兩個(gè)個(gè)體位串，隨機(jī)選擇多個(gè)交叉點(diǎn)，構(gòu)成交叉點(diǎn)集合：x 1， x 2， …x K?[1， 2， … ， L－ 1]， x k≤x k＋ 1，k=1， 2， … ， K－ 1將 L個(gè)基因?yàn)閯澐譃?K＋ 1個(gè)基因位集合：Qk={lk， lk+1， … ， lk+1－ 1}， k=1， 2， … ， K＋ 1， l1=1， lK+2=L+1算子形式為生成的新個(gè)體為 s
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1