本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
4-4 Evolutionary Computation
Loading...
Del curso dictado por National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
144 calificaciones
National Taiwan University
144 calificaciones
De la lección
Non-classic search
Conoce a los instructores
于天立副教授（Associate Professor）
電機工程學系(Electrical Engineering)
好，接下來我們談論 Evolutionary
computation，這是、 也是 Non-classical Search 的一支。
那其實我們剛剛從 Steepest descent 一直到 Simulated annealing，還有我們現在要談的 Evolutionary
computation 這一整支其實有一個通稱，稱為 Metaheuristics。
那如果對這一類 Search algorithm
有興趣的同學可以去查這樣的關鍵字，你還可以找到出我們這門課 所、 所、 所講的其他的一些 Metaheuristics 的做法。
那之所以稱為 Metaheuristics 就是有點像我們之前講 Informed search
裡面的 Heuristic search，但是它的 Heuristic 不是那麼的 直接跟問題有關，不是直接拿問題的特性。
我們那時候是說一個 Heuristic 估計這一步、 那一步，它可能用的是一個
local 的 gradient 的資訊，像我們剛剛講的 Steepest descent，或是我們現在要講的這些。
那所以通稱為 Metaheuristics，就是有點像 Heuristic，但是它不在 Heuristic，直接跟 Heuristic
還是有程度的差別。
好演化式計算、 Evolutionary computation
那是我個人的研究範圍，那這一支 其實整個借重的其實就是達爾文的演化論。
那其實你在講演化論的時候，其實 也要注意一下，就有些、
就演化論其實有很多流派啦，因為我正在學、 學演化這一塊的、 都會知道。
那我們講達爾文演化論是比較其中、 其中的一種講法。
好那 它裡面其實演化本身，它只是在講的就是我們這邊寫就是一個在不同的世代，over
generations 然後那些 我們叫物種它的一個變異，這個過程我們就稱為 演化。
演化論其實在達爾文之前就一直存在，達爾文在裡面 做了一些假設，做了一些理論。
那我們來看一下，達爾文他所、 所，他、 他的、
他的貢獻當然很多了，我們這邊直接縮、 縮減起來就是四個很重要的部份。
一個是所謂的 Natural selection，我們叫物競天擇，就是 你有一個，有一個
fitness 這個東西來決定誰留下來，誰淘汰。
就是適應 度好的留下來，適應度不好的淘汰。
然後接下來有個、 有件事也蠻重要的，就是 Struggle
to survive，就是你一定是要在資源不夠的情況下，
然後你必須因為，你必須要 fitness 好的你才能、 會留下來。
就你 如果沒有這個條件的話，基本上你就算 fitness 差，你只要資源很夠，大家還是一樣留下了嗎，大家都
食物只要非常充足，那不管你能力強或弱，應該都能吃、 都能吃到飽，喝得足。
好那接下來就會這兩個 條件就會造成 Survival of the fittest，就是我們剛才講的適者生存，不適者淘汰。
那最後一個就是，很重要是 遺傳變異。
遺傳變異就是說，我們造成這個 物種能力的差異的來源，來自基因。
那這個基因 就是如果 survive 下來的這些個體，它其實含有比較 能適應當時環境的基因。
那這個東、 這個基因是可以留到下一代的，這個是很重要 的東西。
那如果沒有這樣的話，整個物種，整個、 整個演化也不會朝著更 適應這個環境的方向去演化。
好那這整個東西跟 我們 search
有什麼關係呢？原則就是因為我們現在要問的是這樣，就是回到我們最初的 black box 上面這一 optimization。
就是我有一個我未知的、 不知道的 f，我丟給你 給 x，然後你會給我一個 y。
那我們要問的是說哪一個 x 會給我最好的 y。
我們剛才談了一些 search 的演算法，但是今天如果我們把這個 f 當作是 環境，把 x 當作是一種物種。
把 x 當作就某一種物種，那我可以，我不同的 sample，不同的點就像是這個物種裡面，我有各種不同的個體。
好之後我想跟這些，就是譬如說我有 100 個種，100 個點，就 100 個不同的
x，它都是不同的個體，經過未知 的 function，就是函數值算出來以後，你拿到它的
y，這個 y 就代表這 100 個個體對當時這個環境的適應度嗎。
那我們譬如說最簡單，我們可以用 selection 把比較適應、 比較好的 50 個個體留下來，然後 50 個個體淘汰掉。
那你剩下好的這些個體，我們相信它的基因裡面包含著一些 特性使得這個、 使得它們的
f 值比較高，那我們再讓它們互相去產生 下一代，互相作用去產生下一代。
那這下、 就是從這 50 個比較好的點，然後再設法產生新的 50 個子代。
那我們希望這 新產生 50 個子代裡面，它含有那個 f 會比，讓它們 f 會比較高的可能性。
那這個概念 基本上就是 60、 90 年代由 John Holland
提出來的，那這個簡單， 這個演算法稱為，有翻譯成"基因遺傳演算法"，有人翻譯成"遺傳演算 法"。
那這個概念，我們這邊講的，後來被稱為一個 Simple GA。
那 因為基本上這個 Simple GA 從 60、 70 年代一直到
90 左右，就是從 typically 以它的，以 John Holland
所寫的書來做分水嶺的話，大概是 75 年，然後 90 年代 大部份的、 大部份的研究都 focus 在這個 Simple GA 上，那在這個
Simple GA 上，它、 它基本上對一個問題，它有個特性就是第一件事情的問題，它不是直接作
用在你的 problem instance，而是你會先把問題做編碼。
這個編碼可能是， 可以有很多種，可能是 binary，可能、 你可以把你的問題變成二進位嗎，你也可以把它變成
Χ-ary， 就是整數的 1、 2、 3、 4、 5，你也可以是一種 permutation，譬如說我們剛才
TSP，它的每一個個體就是一個 permutation，那你也可以是 real-valued 等等。
好甚至像 John Koza 在 2000 （年）左右，提出來它還可以是一個 program。
你如果希望你的 program 要做某些事，你甚至可以對程式本身去做這樣的演化。
好那接下來有一個 Initialization， 就是產生一個 population，就是一整個、
一個 population of chromosomes，就是 chromosome 是染色體嗎。
我們就是 編碼完以後，我們就把那一個 solution，那一個點我們稱為，借用生物學的名詞啦，就是一個 染色體。
然後這個 Initialization 可以 base 在你的 human knowledge，如果你覺得問題、 知道哪些點可能比較好，你可以 把那些點放上去。
你也可以是，如果沒有 knowledge 的話，你也可以 purely random，你可以 random 產生這些 initial 點。
那接下來做 Evaluation，就是你去 call 它的 fitness function，其實就是我們剛剛畫的那個 f 啦。
就是你要、 你要做的這個 f。
我談了 100 個點，你如果去 call f，拿到它 100 個 y，然後之後做 selection， 就是適者生存，不適者淘汰。
那這個 selection 裡面當然有很多不同的 selection。
有、 有一些譬如說像我剛剛講的，你可以看一半，譬如說 100 個好的，你可以砍掉
50 個不好的丟掉，50 個好的留下來，那這是蠻早期的一種、 一種做法。
那比較近期的一種做法是，譬如說你可以 random，這 100 個點裡面，random 挑兩個出來，然後好的留下來，壞的淘汰。
好那樣、 這樣在這個過程裡面，加了一些 randomness，而且你知道 f 越高的， 它生存的機率就越高。
它裡面做個類似線性的一個組合。
好，那最後一件事稱為 Recombination，但某些教科書可能會 如果是 GA 的教科書，可能會分成 crossover 跟 mutation。
Crossover 基本上就是把、 把我們 solution，就是你可能挑一個父親，挑一個當母親，然後去對它們染色體做一些組合-
，這個稱為 crossover。
那 mutation 的話是可能你 crossover 出來的子代呢，你做一些突變，就是你希望
增、 增加它們的 exploration 的能力，那你可以做一些 mutation 的動作。
那因為近年來， 從 90 年代之後，其實 GA 做了很多變化。
那有些比較新興的 GA，它並不是只 focus 在這兩個
operator，那我們，所以 generally 我們把它稱為 Recombination。
那而且之後，90 年代之後，很多 GA 它也不一定會挑 一個 solution 做父親，一個 solution 做母親。
它甚至有時候是把整個族群的資訊拿來， 然後用這整個族群所帶、
帶領的資訊來產生新的子代， 所以 generally 我們稱為 Recombination。
而今後我們就這樣一代一代做下去，就產生新的子代以後，我們 某個程度去把一部份取代父代，然後再做
Evaluation，再 讓適者生存，不適者淘汰，這樣一代一代演化下去，我們希望最後能產生一個 若干個 x。
那它 x 如果比較高的，y 值就是比較高的適應函數。
好，啊這邊是我，就是為了讓大家理解我們剛剛，實際上理解我們剛 剛講的這些東西。
我們、 我做了一個、 一、 一個 generation 的 simulation，就是一個 Simple GA 的 simulation。
那這邊我的 fitness、 fitness function 是一個，我們、 我們在，這是一個很簡單的問
題啦，在我們這個領域，我們稱為 ONEMAX problem。
好那這個基本上就是 我們 chromosome 我們假設是 binary，那這個 ONEMAX problem 基本上就是、 就寫成這個樣啦。
其實就是它的 f 就是你的 bit string 裡面有多少個 1？好如果我、 像我這個例子很短的，就 6 個
bit，因為 要過短才能比較好畫了，實際問題當然我們做的都是幾千幾萬以上。
好那 6 個 bit 的 problem，那當然這個 iii 就是 6 個 1 嗎，我要最大化的話，就 6 個 1 fitness 是 6。
OK，fitness 是 6 這樣。
好，那我們看一下這個例子，那一開始這是 Initialization，就是你對每一個 bit string，你
不知道的話，你就隨便 random assign 嗎，每個 bit 是 0 或 1，你就隨便、 隨便選。
好那我如果這是一個 population，是 4，就是 我有 4 個個體。
好然後你 random initialize 的時候，你算一下平均，平均 fitness，這個、
這個、 像這個有 4 個 1 嗎，它的 f 是 4，然後這個 3 個 1，f 是 3，然後等等，這個 2 個 1， f
是 2，那你平均一下它的平均值是 3，這 蠻合理的嗎，就是我有 6 個 bit，你 random initialize 的話，它平均大概在 3 左右。
好 那接下來你做的事情就是你做 selection。
那像我剛剛舉的例子就是一個很簡單的 selection，就是 你可能、 可能看一半，然後把這個丟掉。
你可能、 可能、 可能有人問，譬如說 3 和 3 不是一樣嗎，那決定誰生存下，誰丟掉，這其實
你可以用 random 啦，那實際上會發生它們一樣的，fitness 一樣的機率很低啦。
實際上我們用的 population 都是 幾千幾萬，這樣然後可能是real value，所以你傳回來的F值機率其實很低的。
那如果你真的有一樣的話，其實 在實作上不管你選擇哪一個應該都差不多。
好那之後呢我們去做F的iii的 結果，我們稱為mating
pool，就是這些科目總會讓它們去crossover 那好，那這邊我們用的是一個，crossover有很多種，那crossover
我們這裡用的是稱為單點crossover，one-point crossover
one-point crossover其實就是接著發明人將後人提出來，那現在
有很多別的，那這簡單講就是這邊用random 取一個 cross
set 好，選一個位置然後把這個染色體數交換，把這視為 染色體，這些0，1 就是基因嘛。
好就基因，其實就是AGTC嘌呤 術語生物術語叫嘌呤嘛。
就是模擬用0，1 模擬它的A，G，T，C 這些東西
那這邊是選擇的是這個點去做 crossover，看我的顏色就知道這是
右邊這邊是crossover后的結果，好那一做crossover 以後，基本就產生了4個不同的
子代，然後我們再做multation，multation原則上如果在iii的話，你- 可以想像用很低的機率
讓beat 去0 變1 ，1 變0，那在這個示意圖可能每個iii我就挑了一個
random選一個beat然後把它0 變1 ，1 變0，在random選擇之後我們可以很故意，在這個例子越多越好，你可以看一下就是
比如說這邊有兩個1 嘛，把兩個0變1，把兩個1
變0，就這個樣子 好，這是random multation的做法。
做完以後這是最後的結果，這就是4個子代。
那如果要再做 進行下一個generation的話，就是可能就是拿著4個子代，你可以做直接替換掉那-
4個負五代，也就是說 下一個generation就是用4個，那你也可以從這8個裏面你選比較好的
4個出來，這也是可以，可行的做法，那各有利弊。
那我們今天不 細一步的做探討，但是我們我看一下這個結果。
就是你去算它的F的話，這個分別是3， 4，5 ，2 好，你可以看到第一件事情就是它的平均是3.
5，從一開始平均是3 經過這樣一個generation一代以後，平均值的females從3 成長到3.
5。
那第二件事一個是它的最高的females，之前最好的是4，那現在是 現在最好是5，那有慢慢在成長。
那這只是一個generation，如果我們在run下一個generation 可以看得出來，很容易可能3 會丟掉嘛，那2 會丟掉，這是比較糟的。
那你可能會去做4 和5 的cross over，那4
和5 因為已經有很多個1了，那它crossover出來的子代可能1也不少，那加上mult-
ation，很可能就會創造出6個 iiii，好那這是simple
Gene的整個流程，那我這邊因為這邊是我自己的 專業。
那課本上，按課本上說提的gene的部份，大家就 僅局限於90年代之前的，我們稱為simple
gene，那我這邊 很簡單用頁頭影片給各位講一下從90年代到現在，20快5年
25年的gene重要的方向，重要的研究方向在什麽地方
好，在90年之前，我們稱為simple gene，它的recombination即使
cross 和multation有各種不同說，one-point 之外還有很多比如說突破性 crossover，還有uniform
crossover 等等，但是基本上它都屬於一種random crossover。
random 就是我拿一個父親母親說 他們的產生子代的方式就是對他們的基因做一種我們稱為crosss的一種shuffle-
，有些crossover shuffle的比較嚴重，有些cross shuffle的 比較輕微，但是anyway，都是一種random，但是
在90年的時候，Gober他提出了一個很重要的看法 那影響了後來gene的研究方向，那主要他提的一個
很，就是90年之前iii界已經實用的蠻多的，包含
很多應用都有在用gene了，那順便可以提一下那像日本新幹線的火車頭 車頭的那個形狀就是用simple
gene做出來 iiii當然就是90年代之後的事了，一直到現在simple
gene還是很popular，但是我們 在想的一件事是說，ok，simple gene work 的不錯。
那麼我們 我們當然這個演算法，那我們當然針對這個演算法就會challenge說
什麼樣的問題你可能會做不好？好我們challenge你這個這個演算法。
那我們這邊提一種，一個例子叫 稱為，在我們的領域稱為trap function，trap function的長相是這個樣子，就是
它基本上你要定義在某一個若干個beat上，我這邊舉個例子3個beat 如果這3個beat的trap
function它長得就是3個1的時候，若這3個beat等於1，我給你F等於1 那3個0的時候，我給你F等於0.
9。 也就是說其實正解是一樣。
1 是我們的最佳解，0.
9 是次佳解，那其他的 其他的話就，你看下這個圖也就是說只要你的 三個beat如果是11，我給你1。
還有兩個1，比如說 這3個就是110， 101，011，我給你最差的值
也就說我故意把它iii一起來，故意把它的1 個1 iii在一起來，那
在其他地方只要不是3 個1 之外，你會發現這很像一個很緩的hill
這樣，我這邊另一代3 實際上我們真的測出來可能是在5或6以上 好，這是一個trap
function，反正就是一個function的定義，那如果我今天將這3個 beat 沒什麽可以解的，基本上你試八次全部就出來了。
那如果今天給你一個譬如說 30 個beat好了。
30 個 beat problem 已經是noniii problem
因為還蠻大的，你全部要試完要二三十次方，這在大部份目前的電腦都還不太容易 不是很容易做當然要花一點時間。
那我當然還有更長的，這30個beat假設我是 我是把它其實是3乘10個部份，也就是說這個F其實是 3個beat，3個beat這樣
trap為一組，然後我總共有10個component，然後我把它們的 直接當，females以後直接相加起來。
那直接相加的，我全如果指的是次序 你不知道，比如又是像這個一樣，就是可能x1，x10，x22 這樣進去。
好那這樣的話問題是說你可能是說你可能有一個負五代 譬如說這3個beat，這3個beat可能是很好
對不起，可能這3個，這是負五代，就是父親你可能取得是這個樣
另外這邊是000，然後母親可能取得這邊是錯的，這邊是對的 好這個情況下你如果做one-point
crossover，如果你能cross在 是在這邊的話，那很棒，你就組合出來一個完整的6個1
好可是實際上用我的beat是這樣random ，對不對
這是rand，也就是你一刀砍下去以後基本上你大致上 10個這樣3個beat
一組的，其實全部被你砍爆了，比如說我切刀到x1 到x2 之間 好，那基本上這邊就x1
來自父親然後剩下來自母親，好剩下來是x2 來自母親然後剩下來自父親。
好基本上已經被砍亂了 好那這樣的話，你如果一個很好的
已經是正解的111，還有一個不是正解的000，你這個crossover之後的結果
你就會產生兩個更差的數值，好這個的iii是1，這個是
iii其實是不正確，但是也還算還好，你crossover 的結果是 0，這一個是0.
4。
好這些發生的事情就是我設計的我們設計的 一個function，這個function的重點就是你不可去切割它，你如果切割-
它的時候 兩個給你還不錯的解，你做組合的結果會組出兩個很差的解 好這是我們故意設計的。
所以90年代以後我們大部份的接下來的研究就focus在 怎麼樣去辨認這三個是一組，是不可被分
割的？那這個概念我們稱為一種building block。
那反映到 iii其實就是一種problem iii，我們就主要研究在這邊，利用的就是machine learning的技巧
就是基本上F就是個黑盒子嘛，但是你如果丟過一百萬次x，讓它吐出一百萬個y給你，其實- 你對那個F
是有某種程度上的瞭解，你可以去用machine learning來去論說這個黑盒子F大概會長什麽樣子，然後利用這個資訊你去做
問題結構。
也就是如果我今天是一個100 beat problem，如果100 beat problem你全部都要試完的話，基本上是二的一百次方嘛
這個你要試 大部份是十的三次方這麼多，但是今天我們 你能夠論出來這個100 beat
problem其實是20個 5個beat的problem，就是它每一個單位是5個beat，當然我們不知道那5個-
beat是 長什麽樣子，但是你要實驗就試的很少，基本上你要解掉那幾個beat就只要二的五次方
就是你試三十二次你就可以解出來，然後接下來你就要乘 20個，那基本上只要試640次就可以解完。
好這是近年來gene的發展狀態是這個樣子 [音樂]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
