【正文】 二進(jìn)制數(shù)速成（ A Quick Lesson in Binary Numbers） 16 8 4 2 個(gè)位 1 1 1 1 數(shù)字 15 如果要把 15寫(xiě)成 8位的二進(jìn)制 ， 則要寫(xiě)成下面這樣的形式 ， 其中高位都是０ ， 但也要把前面寫(xiě)出來(lái) ， 以使整個(gè)長(zhǎng)度達(dá)到８： 00001111 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 38 計(jì)算機(jī)內(nèi)的進(jìn)化 （ Evolution Inside Your Computer ） 遺傳算法工作過(guò)程本質(zhì)上就是模擬生物的進(jìn)化過(guò)程 。 我想 ， 你也會(huì)和我一樣 ， 深深嘆服自然母親的令人著迷 ！ 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 35 本質(zhì)上說(shuō) ， 任何生物機(jī)體就是一大堆細(xì)胞的集合 。 1962年 Holland教授首次 提出了 GA算法的思想 ， 從而吸引了大批的研究者 ， 迅速推廣到優(yōu)化 、 搜索 、 機(jī)器學(xué)習(xí)等方 面 ， 并奠定了堅(jiān)實(shí)的理論基礎(chǔ) 。 研究隊(duì)伍日益壯大 ， 社會(huì)影響越來(lái)越大 。 從系統(tǒng)角度看 ， 有智能計(jì)算機(jī)系統(tǒng)和智能應(yīng)用系統(tǒng)兩大類 。 如符號(hào)智能中又有圖搜索 、 自動(dòng)推理 、 不確定性推理 、 知識(shí)工程 、 符號(hào)學(xué)習(xí)等 。 具體來(lái)講 ， 就是要使計(jì)算機(jī)不僅具有腦智能和群智能 ， 還要具有看 、 聽(tīng) 、 說(shuō) 、 寫(xiě)等感知和交流能力 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 9 符號(hào)智能和計(jì)算智能 1. 符號(hào)智能 符號(hào)智能就是符號(hào)人工智能 ， 它是模擬腦智能的人工智能 ， 也就是所說(shuō)的傳統(tǒng)人工智能或經(jīng)典人工智能 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 6 圖靈測(cè)試和中文屋子 ◆ 圖靈測(cè)試 ” （ Turing Test） 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 7 ◆ 約翰 .西爾勒 (John Searle)的 “ 中文屋子 ” 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 8 腦智能和群智能 腦 （ 主要指人腦 ） 的宏觀心理層次的智能表現(xiàn)稱為 腦智能 （ Brain Intelligence, BI） 。 計(jì)算智能的主要內(nèi)容包括：神經(jīng)計(jì)算 （ Neural Computation， NC） 、 進(jìn)化計(jì)算（ 亦稱演化計(jì)算 ， Evolutionary Computation， EC， 包括遺傳算法 （ Geic Algorithm， GA） 、 進(jìn)化規(guī)劃（ Evolutionary Planning ， EP ） 、 進(jìn)化策略（ Evolutionary Strategies， ES） 等 ） 、 免疫計(jì)算（ immune putation） 、 粒群計(jì)算 （ Particle Swarm Algorithm， PSA） 、 蟻群算法 （ Ant Colony Algorithm，ACA） 、 自然計(jì)算 （ Natural Computation， NC） 以及人工生命 （ Artificial Life， AL） 等 。 人工智能實(shí)際上是一門(mén)綜合性的交叉學(xué)科和邊緣學(xué)科 。 而機(jī)器學(xué)習(xí)又可分為符號(hào)學(xué)習(xí) 、 連接學(xué)習(xí) 、 統(tǒng)計(jì)學(xué)習(xí)等許多研究領(lǐng)域和方向 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 21 人工智能學(xué)科的發(fā)展概況 人工智能學(xué)科的產(chǎn)生 符號(hào)主義途徑發(fā)展概況 連接主義途徑發(fā)展概況 計(jì)算智能異軍突起 智能 Agent方興未艾 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 22 現(xiàn)狀與發(fā)展趨勢(shì) 多種途徑齊頭并進(jìn) ， 多種方法協(xié)作互補(bǔ) 。 朱樓寒雨離歌淚 ， 不堪腸斷雨乘風(fēng) 。 因此 ， 了解一些有關(guān)有生命的機(jī)體如何演化的知識(shí) ，對(duì)理解遺傳算法的演化機(jī)制是是有幫助的 。 常簡(jiǎn)寫(xiě)為 T、 A、 C、 G。 遺傳算法的最大優(yōu)點(diǎn)就是 ， 你不需知道怎么去解決一個(gè)問(wèn)題 。 但 ， 一個(gè)初始的群體已經(jīng)創(chuàng)建完成（ 對(duì)這一例子 ， 不妨設(shè)共有 100個(gè)成員 ） ， 這樣 ， 就可以開(kāi)始做下面列出的一系列工作 。 結(jié)束循環(huán) 以上算法中步驟 1 到步驟 5 的一次循環(huán)稱為一個(gè)代 （ 或世代 ，generation） 。 為了選取一個(gè)染色體 ， 你要做的 ， 就是旋轉(zhuǎn)這個(gè)輪子 ， 并把一個(gè)小球拋入其中 ， 讓它翻來(lái)翻去地跳動(dòng) ， 直到輪盤(pán)停止時(shí) ， 看小球停止在哪一塊上 ， 就選中與它對(duì)應(yīng)的那個(gè)染色體 。 im_iPopSize。 實(shí)驗(yàn)表明這一數(shù)值通常取為 想的 ， 盡管某些問(wèn)題領(lǐng)域可能需要更高一些或較低一些的值 。baby1, vectorint amp。 int cp = RandInt(0, m_iChromoLength 1) ； 沿染色體的長(zhǎng)度隨機(jī)選擇一個(gè)點(diǎn)來(lái)裂開(kāi)染色體。 (mum[i])。vecBits){ for (int curBit=0。 其中 Pc是一個(gè)系統(tǒng)參數(shù) 。 Crossover:交叉算子 ， 以概率 Pc在兩基因鏈上的隨機(jī)位置交換子串 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 52 遺傳算法的結(jié)構(gòu) ： Procedure Geic Algorithm begin t=0 initialize p(t) evaluate p(t) while (not terminationcondition) do begin t=t+1 select p(t) from p(t1) alter p(t) evaluate p(t) end end 二、遺傳算法的主要特征： 圖 1遺傳算法的結(jié)構(gòu) ： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 53 在第次迭代 ， 遺傳算法維持一個(gè)潛在解的群體 },{)( 21 tntt xxxtp ?? 每個(gè)解 tix1?t用其 “ 適應(yīng)值 ” 評(píng)價(jià) 。 (2).它不是從單個(gè)點(diǎn) ， 而是從一個(gè)解族開(kāi)始搜索解空間 ， 與傳統(tǒng) “ 點(diǎn)對(duì)點(diǎn) ” 式的搜索方法不同 。 其它的部分只是上述步驟的循環(huán)重復(fù) 三、遺傳算法的運(yùn)行步驟： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 58 1) 編碼和解碼 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 59 2)產(chǎn)生潛在解初始群體 簡(jiǎn)單地以位的方式隨機(jī)地設(shè)定 pop_size個(gè)染色體 。 1817 21510002 ??2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 66 (010001001011010000111110010100010) 的前 18位 010001001011010000表示 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 67 2) 產(chǎn)生潛在解初始群體： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 68 3)根據(jù)適應(yīng)值評(píng)價(jià)解的適應(yīng)程度并據(jù)此生成新群體： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 69 3)根據(jù)適應(yīng)值評(píng)價(jià)解的適應(yīng)程度并據(jù)此生成新群體： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 70 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 71 4) 雜交 (crossover)和變異 (mutation)—決定新群體的性狀： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 72 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 73 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 74 群體的當(dāng)前版本為： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 75 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 76 表 ： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 77 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 78 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 79 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 80 但是 ， 仔細(xì)檢查整個(gè)運(yùn)行過(guò)程 ， 可以發(fā)現(xiàn)早期代中的某些染色體的適應(yīng)值要好于經(jīng)過(guò) 1000代后的最好染色體值 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 86 第 0 代 交 配 池 第 1 代 i 串 xi 適應(yīng) 值f(xi) F(xi)/? f(xi) 串 f(xi) 雜交點(diǎn) xi f(xi) 1 011 3 011 3 2 010 2 2 001 1 110 6 2 111 7 3 110 6 110 6 － 110 6 4 010 2 010 2 － 010 2 總和 12 17 17 最小值 1 2 2 平均值 最大值 6 6 7 表 4 使用 復(fù)制和雜交算子 的作用結(jié)果 遺傳算法利用復(fù)制和雜交算子可以產(chǎn)生具有更高平均適應(yīng)值和更好個(gè)體的群體 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 87 ： 以一個(gè)很小的概率 pm隨機(jī)改變?nèi)旧w串上的某些位。 從離散點(diǎn) 0到離散點(diǎn) 9， 依次讓它們分別對(duì)應(yīng)于從0000000000000000000000(0) 到1111111111111111111111(41943043)之間的二進(jìn)制編碼 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 93 第七步：確定遺傳算法的運(yùn)行參數(shù)。 例如，添加符號(hào) *表示不確定字母，即 0或 1，考慮串長(zhǎng)為 7的模式H＝ *11*0**，則串 A＝ 0111000是模式 H的一個(gè)表示，對(duì)于基數(shù)為 k的字母表，每一個(gè)串有（ k＋ 1） l 個(gè)模式。 ” (Davis, 1989) 遺傳算法傳統(tǒng)上使用的二進(jìn)制編碼當(dāng)用于多維 、 高精度數(shù)值問(wèn)題時(shí)會(huì)有一些障礙 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 112 (2). “有限困難 ” ： 遺傳算法理論解釋了為什么對(duì)一個(gè)給定的問(wèn)題表達(dá) ， 能收斂到欲求的最優(yōu)點(diǎn) 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 113 Thank you! 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 114 練習(xí) 說(shuō)說(shuō)遺傳算法的基本思想和算法流程 。 主要的原因除了上面的 “ 編碼困難 ” 之外 ， 還有 “ 有限困難 ” ，即：理論假定迭代次數(shù)是無(wú)限的 ， 而實(shí)際上有限制；理論上也假定群體規(guī)模是無(wú)限的 ， 實(shí)際上也有限制 。 這本身會(huì)產(chǎn)生一個(gè)大約是 101000的搜索空間 。在二進(jìn)制中，一個(gè)模式的階就是所有的 1或 0的數(shù)目。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 97 小結(jié) 遺傳算法描述了從第 0代產(chǎn)生第 1代的過(guò)程，然后遺傳算法迭代地執(zhí)行這個(gè)過(guò)程，直到滿足某個(gè)停止準(zhǔn)則。 例如 X： 0000000000001101110001 就表示一個(gè)個(gè)體的基因型 。 例如：選交配池中編號(hào)為 4的串進(jìn)行變異，且變異點(diǎn)在 2，則