【文章內(nèi)容簡(jiǎn)介】 表達(dá)式樹(shù) ET 評(píng)價(jià) 表達(dá)式樹(shù) 計(jì)算適應(yīng)度 新一代 染色體 復(fù) ,插 ,變 , 重 , 移 , 在形成活體前變化 被選種機(jī)會(huì)按適應(yīng)度作輪盤(pán)賭，遺傳操作 Yes No 已經(jīng)進(jìn)化成為現(xiàn)代人 ? ?大自然（ God)算法， ?下頁(yè)解釋輪盤(pán)賭，轉(zhuǎn)糖餅 ?結(jié)束條件：進(jìn)化代數(shù) ?或精度 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 37/141 輸出現(xiàn)代人 亞當(dāng)，夏娃 染色體 Chromosomes0 染色體 ? 表達(dá)式樹(shù) ET 評(píng)價(jià) 表達(dá)式樹(shù) 計(jì)算適應(yīng)度 新一代 染色體 復(fù) ,插 ,變 , 重 , 移 , 在形成活體前變化被選種機(jī)會(huì)按適應(yīng)度作輪盤(pán)賭，遺傳操作 Yes No 已經(jīng)進(jìn)化成為現(xiàn)代人 ? 創(chuàng)新點(diǎn)？ 道法自然，外思物化 內(nèi)得心源 ?創(chuàng)新點(diǎn)， 轉(zhuǎn)基因技術(shù) ?1 多代積累的傳統(tǒng)不輕拋。 ?2 將要成熟時(shí)幫一把。（新浪：外星人幫人類(lèi)加基因） ?新的適應(yīng)度函數(shù) ?重疊基因 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 38/141 輸出現(xiàn)代人 亞當(dāng)，夏娃 染色體 Chromosomes0 染色體 ? 表達(dá)式樹(shù) ET 評(píng)價(jià) 表達(dá)式樹(shù) 計(jì)算適應(yīng)度 新一代 染色體 復(fù) ,插 ,變 , 重 , 移 , 在形成活體前變化被選種機(jī)會(huì)按適應(yīng)度作輪盤(pán)賭，遺傳操作 Yes No 已經(jīng)進(jìn)化成為現(xiàn)代人 ? 創(chuàng)新點(diǎn) 道法自然，外思物化， 內(nèi)得心源 ?創(chuàng)新點(diǎn)， 轉(zhuǎn)基因技術(shù) ?并列， 多基因， 因子分解 ?重疊基因 ?帶回溯控制的 GEP ?返祖現(xiàn)象 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 39/141 輪盤(pán)賭，轉(zhuǎn)糖餅，按適應(yīng)度大小 分配份額 ? 用途： 這里，按概率決定是否作某個(gè)遺傳操作。 ?小餅 ?龍 ?虎 ?政策向 ”優(yōu)良 ” 品種傾斜 ?適應(yīng)度大的，站的份額多 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 40/141 輪盤(pán)賭算法 用上頁(yè)的例子 ? 1 按 龍、虎、 ./小糖餅的份額（適應(yīng)度） 設(shè)計(jì)分割數(shù)組，分辨率 1度 ? 如 【 0—180】 標(biāo)記為 糖餅 占用 180/360=50% ? 【 90100】 標(biāo)記為 龍 占 100/360=1/36， …… ? ….. 【 340360】 標(biāo)記為 虎 占 20/360=2/36 ? 用多個(gè) if 語(yǔ)句或不等式比較， 可從角度得到對(duì)應(yīng)的標(biāo)記 ? Int GetLabel（ Alpha) { 容易實(shí)現(xiàn)，略去代碼 } ? LabelType ={糖餅 ,龍 , …., 虎 } ? 算法 ? LabelType Diece ( ) // 返回 首選標(biāo)記 ? { Radomize( )； ? Alpha = Radom(360)。 ? Return( GetLabel（ Alpha)) ? } ?調(diào)用這個(gè)函數(shù) ?這根份額可能是動(dòng)態(tài)的 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 41/141 輪盤(pán)賭算法 的另一種表述 （不如 前一種形象） step 1: Calculate the total fitness for the population ???Sizepopkkev alF1)( vstep 2: Calculate selection probability pk for each chromosome vk SizepopkFev alp kk ,. ..,2,1,)(= ?vstep 3: Calculate cumulative probability qk for each chromosome vk pop Siz ekpqkjjk ,...,2,1,=1???step 4: Generate a random number r from the range [0, 1]. step 5: If r ? q1, then select the first chromosome v1。 otherwise, select the kth chromosome vk (2 ? k ? popSize) such that qk1 r ? qk . input: population P(t1), C(t1) output: population P(t), C(t) Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 42/141 下頁(yè)解釋輪盤(pán)賭，轉(zhuǎn)糖餅，適應(yīng)度大小分配比例 ? ?小餅 ?龍 ?虎 ?不公平賭博，政策向 ”優(yōu)良 ” 品種傾斜 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 43/141 通過(guò)隨機(jī) 實(shí)現(xiàn)遺傳公平 ? 生物特性，強(qiáng)烈希望 通過(guò)繁殖，延續(xù)自己的屬性。 遺傳 ? 生存機(jī)會(huì)少時(shí)，誰(shuí)有遺傳權(quán)利？ 打一仗， 優(yōu)勝劣汰。 ? GEP中，程序員 是上帝，簡(jiǎn)單優(yōu)勝劣汰， 不太公平，不太長(zhǎng)遠(yuǎn)。加上隨機(jī)抽簽，給弱者留一線(xiàn)生機(jī)，以觀后效。 ? 現(xiàn)實(shí)生活中的比喻： ? 抽簽 決定 PK group,決定出場(chǎng)次序，彩票等等。（無(wú)某人的主觀干預(yù)，聽(tīng)天由命） ? 設(shè)計(jì) 一個(gè) 抽簽函數(shù) (下頁(yè)）既體現(xiàn)隨機(jī)的公平（客觀或運(yùn)氣），又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應(yīng)度 ）。 ? 想一想？ 有職改奮勇的嗎？ 來(lái)講。（下頁(yè)揭曉） Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 44/141 通過(guò)隨機(jī) 實(shí)現(xiàn)遺傳公平 ? 生物特性，強(qiáng)烈希望 通過(guò)繁殖，延續(xù)自己的屬性。 遺傳 ? 生存機(jī)會(huì)少時(shí)，誰(shuí)有遺傳權(quán)利？ 打一仗， 優(yōu)勝劣汰。 ? GEP中，程序員 是上帝，簡(jiǎn)單優(yōu)勝劣汰， 不太公平，不太長(zhǎng)遠(yuǎn) (生物多樣性）。用隨機(jī)抽簽，給弱者留一線(xiàn)生機(jī)，以觀后效。 ? 現(xiàn)實(shí)生活中的比喻： ? 抽簽 決定 PK group,決定出場(chǎng)次序，彩票等等。（無(wú)某人的主觀干預(yù)，聽(tīng)天由命） ? 設(shè)計(jì) 一個(gè) 抽簽函數(shù) (下頁(yè)）既體現(xiàn)隨機(jī)的公平（客觀或運(yùn)氣），又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應(yīng)度 ）。 ? 想一想？ who自告奮勇？ go ahead ! （下頁(yè)揭曉） Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 45/141 通過(guò)隨機(jī) 實(shí)現(xiàn)遺傳公平 ? 設(shè)計(jì) 一個(gè) 抽簽函數(shù) (下頁(yè)） ? 既體現(xiàn)隨機(jī)的公平（客觀或運(yùn)氣）， ? 又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應(yīng)度 ）。 ? 為什么需要這個(gè)函數(shù)？ ? 否則 ? 庶民個(gè)體會(huì)問(wèn)： 王侯將相 寧有種乎？ Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 46/141 通過(guò)隨機(jī) 實(shí)現(xiàn)遺傳公平 ? 設(shè)計(jì) 一個(gè) 抽簽函數(shù) (下頁(yè)） ? 既體現(xiàn)隨機(jī)的公平（客觀或運(yùn)氣）， ? 又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應(yīng)度 ）。 ? 為什么需要這個(gè)函數(shù)？ ? 龍生龍，鳳生鳳， 則 庶民個(gè)體 會(huì)問(wèn)： ? 王侯將相 ，寧有種乎？ ? 專(zhuān)業(yè)術(shù)語(yǔ)： 種群多樣性不好，進(jìn)化收斂慢 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 47/141 機(jī)會(huì)留 給有準(zhǔn)備的個(gè)體 （主觀 +客觀） ? 設(shè)計(jì) 一個(gè) 機(jī)遇函數(shù)既體現(xiàn)隨機(jī)的公平（客觀或運(yùn)氣），又體現(xiàn)主觀努力，優(yōu)勝劣汰（適應(yīng)度 ）。 ? 每次運(yùn)行，每個(gè)個(gè)體有 Rate = 的機(jī)會(huì)參加變異 ? Bool GetChance( Rate, Fitness， Threshold) ? { redomaize( )。 ? chance=Radom(1)。 //及格分?jǐn)?shù)線(xiàn)達(dá) ? return = ( Chancerate) amp。amp。 (Fitness = Threshold) ? } ||| …… ..| ? 0 chance rate =% 1 ?適應(yīng)度高于門(mén)限優(yōu)勝 ?機(jī)遇 Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 48/141 GEP 中嬰兒會(huì)不會(huì)夭折， 計(jì)劃生育，可保持種群穩(wěn)定 。 ? 種群規(guī)模 P 10（簡(jiǎn)單問(wèn)題） ,100（通常） ,300（復(fù)雜問(wèn)題） ? 如果用靜態(tài)數(shù)組保存種群，種群數(shù)目不變。 ? GEP遺傳操作 ? 交叉 （有性繁殖 ,單點(diǎn)， 多點(diǎn)交叉）：一對(duì)父母，一對(duì)兒女 ? 變異（單點(diǎn)，多點(diǎn)）插刪串也可看成變異 ? 可視為 無(wú)性繁殖：一個(gè)前輩，只一個(gè)后代 ? 比喻 鳳凰涅槃，金蟬脫殼 ? GEP中嬰兒會(huì)不會(huì)夭折？ 不會(huì) . （在 GA,GP中 會(huì)大量死亡 ,90%） ? 多種操作產(chǎn)生的后代中，選擇適應(yīng)度高的 P個(gè)作下一代。 GEP基本定理 . Ｇ EP中 一個(gè)很寬松的約束 t=2h1， 個(gè)體在遺傳操作的折騰下 全部存活， 得到 新生 （ zuoamp。tang 2022) Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 49/141 GEP 中嬰兒會(huì)不會(huì)夭折， 可以計(jì)劃生育，節(jié)約時(shí)間 ? containing all parents and offspring P6P3P1P1’P6’c ross ov ermutati onpopul ati onreplac ementP3’P6 ’P1 ’new popul ati ons el e c ti onSe le ctio n b ased on en l arg e d sa mpl i ng spa c eP1’P6’P3’? 鳳凰涅槃 ?金蟬脫殼 ?一對(duì)父母，一對(duì)兒女 ?P=2N，雜交生成 2N個(gè)，變異生成 2N個(gè)，從 4N個(gè)中選出 2N個(gè)，實(shí)現(xiàn)時(shí) 有靈活性，在質(zhì)量和速度之間平衡 直接選 間接選？ Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 50/141 ? Example of Geic Algorithm for Unconstrained Numerical Optimization (Michalewicz, 1996) 避免局部 優(yōu) 化 （ 變 異可使 個(gè)體在全空 間 中跳 動(dòng) ） 1 .0 2 .0x? ? ? Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 51/141 單點(diǎn)交叉算法偽碼 （把直觀上很形象的動(dòng)作嚴(yán)格表述 ? Procedure of Onecut Point Crossover: procedure: Onecut Point Crossover input: pC, parent Pk, k=1, 2, ..., popSize output: offspring Ck begin for k ? 1 to do // popSize: population size if pc ? random [0, 1] then // pC: the probability of crossover i ? 0。 j ? 0。 repeat i ? random [1, popSize]。 j ? random [1, popSize]。 until (i≠j ) p ? random [1, l 1]。 // p: the cut position, l: the length of chromosome Ci ? Pi [1: p1] // Pj [p: l ]。 Cj ? Pj [1: p1] // Pi [p: l ]。 end end output offspring Ck。 end ? ?2/popSize Univ. 自然計(jì)算模型 SCUPHD 2022/2/1 52/141 變 異 Mutation 的直觀 解釋 v1 = [100110110100101101000000010111001] c1 = [100110110100101000000010101001000] mutating point at 16th gene Univ. 自然計(jì)算模型