【正文】 是不可能的，比如曾有人估計(jì)，西洋跳棋完整的博弈樹約有 10的 40次方個節(jié)點(diǎn)。 2022/8/21 80 ? 最常使用的分析方法是極小極大分析法。其基本思想或算法是： (1) 設(shè)博弈的雙方中一方為 MAX，另一方為 MIN。然后為其中的一方 (例如 MAX)尋找一個最優(yōu)行動方案。 (2) 為了找到當(dāng)前的最優(yōu)行動方案，需要對各個可能的方案所產(chǎn)生的后果進(jìn)行比較 ,具體地說，就是要考慮每一方案實(shí)施后對方可能采取的所有行動，并計(jì)算可能的得分。 (3) 為計(jì)算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時估算出來的得分稱為靜態(tài)估值。 2022/8/21 81 ? (4) 當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來后，再推算出父節(jié)點(diǎn)的得分，推算的方法是：對“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案；對“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為倒推值。 (5) 如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動方案。 2022/8/21 82 ? 在博弈問題中，每一個格局可供選擇的行動方案都有很多，因此會生成十分龐大的博弈樹。試圖利用完整的博弈樹來進(jìn)行極小極大分析是困難的。可行的辦法是只生成一定深度的博弈樹，然后進(jìn)行極小極大分析 ,找出當(dāng)前最好的行動方案。在此之后，再在已選定的分支上擴(kuò)展一定深度，再選最好的行動方案。如此進(jìn)行下去，直到取得勝敗的結(jié)果為止，至于每次生成博弈樹的深度，當(dāng)然是越大越好，但由于受到計(jì)算機(jī)存儲空間的限制，只好根據(jù)實(shí)際情況而定。 2022/8/21 83 一字棋游戲極小極大分析法 ? 設(shè)有九個空格，由 MAX， MIN二人對弈，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成“三子成一線” (同一行或列或?qū)蔷€全是某人的棋子 )，誰就取得了勝利。 ? 用叉號表示 MAX，用圓圈代表 MIN。 ? 比如右圖中就是 MIN取勝的棋局。 2022/8/21 84 ? 為了不致于生成太大的博弈樹，假設(shè)每次僅擴(kuò)展兩層。估價函數(shù)定義如下： ? 設(shè)棋局為 P，估價函數(shù)為 e(P)。 ? (1) 若 P對任何一方來說都不是獲勝的位置，則 e(P)=e(那些仍為 MAX空著的完全的行、列或?qū)蔷€的總數(shù) )e(那些仍為 MIN空著的完全的行、列或?qū)蔷€的總數(shù) ) ? (2) 若 P是 MAX必勝的棋局，則 e(P)＝ +∞。 ? (3) 若 P是 B必勝的棋局，則 e(P)＝ ∞。 比如 P如右圖示 ,則 e(P)=64=2 2022/8/21 85 ? 要注意利用棋盤位置的對稱性 ,在生成后繼節(jié)點(diǎn)的位置時，下列博弈結(jié)局由于右圖所示位置具有最大的倒推值，它應(yīng)當(dāng)選取為 MAX的第一步（正好是MAX的最好的優(yōu)先走步）。 2022/8/21 86 2022/8/21 87 ? 現(xiàn)在我們假設(shè) MAX走了這一步，而 MIN的回步是直接在 X上方的空格里放上一個圓圈 (對 MAX來說這是一步壞棋，他一定沒有采用好的搜索策略 )。下一步， MAX又在新的格局下搜索兩層，產(chǎn)生如圖 。 2022/8/21 88 2022/8/21 89 2022/8/21 90 ? 現(xiàn)在圖中 MAX有兩個可能“最好的”優(yōu)先走步，假設(shè) MAX走了圖上指明的那一步。而 MIN為了避免立即敗北被迫走了另一步，從而產(chǎn)生如下棋局： MAX再次搜索，產(chǎn)生如圖 。 2022/8/21 91 2022/8/21 92 ? 在這棵樹中某些端節(jié)點(diǎn) (例如其中一個標(biāo)記著 A)代表 MIN獲勝，因此它們的估值為 — ∞。當(dāng)這些估值被倒推回去時，可看到 MAX的最好的也是唯一能使他避免立即失敗的一個走步。現(xiàn)在， MIN可以看出 MAX必然在他的下一走步中獲勝，因此， MIN只好認(rèn)輸。 2022/8/21 93 α β 剪枝技術(shù) ? 首先分析極小極大分析法效率，上述的極小極大分析法，實(shí)際是先生成一棵博弈樹，然后再計(jì)算其倒推值，至使極小極大分析法效率較低。于是在極小極大分析法的基礎(chǔ)上提出了 αβ剪枝技術(shù)。 αβ剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計(jì)算評估各節(jié)點(diǎn)的倒推值，并且根據(jù)評估出的倒推值范圍，及時停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率 2022/8/21 94 具體的剪枝方法如下 ： ? (1) 對于一個與節(jié)點(diǎn) MIN，若能估計(jì)出其倒推值的上確界 β，并且這個 β值不大于 MIN的父節(jié)點(diǎn) (一定是或節(jié)點(diǎn) )的估計(jì)倒推值的下確界 α，即 α≥β，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對 MIN父節(jié)點(diǎn)的倒推值已無任何影響 了 )。這一過程稱為 α剪枝。 (2) 對于一個或節(jié)點(diǎn) MAX，若能估計(jì)出其倒推值的下確界 α，并且這個 α值不小于 MAX的父節(jié)點(diǎn) (一定是與節(jié)點(diǎn) )的估計(jì)倒推值的上確界 β，即 α≥β，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了 (因?yàn)檫@些節(jié)點(diǎn)的估值對 MAX父節(jié)點(diǎn)的倒推值已無任何影響 了 )。這一過程稱為 β剪枝。 2022/8/21 95 ? 從算法中看到： (1) MAX節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 α值永不減少； (2) MIN節(jié)點(diǎn) (包括起始節(jié)點(diǎn) )的 β值永不增加。 在搜索期間， α和 β值的計(jì)算如下 ： (1) 一個 MAX節(jié)點(diǎn)的 α值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。 (2) 一個 MIN節(jié)點(diǎn)的 β值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。 2022/8/21 96 例：對圖 α 和 β 值計(jì)算方法。假設(shè)以深度優(yōu)先方式進(jìn)行搜索。 2022/8/21 97 ? 畫出根節(jié)點(diǎn)、節(jié)點(diǎn) A及 5個兒子，計(jì)算并標(biāo)上這些節(jié)點(diǎn)的靜態(tài)估值， A的 5個兒子節(jié)點(diǎn)的靜態(tài)估值的最小值是 1，因此節(jié)點(diǎn) A的倒推值為 1，從而起始節(jié)點(diǎn)的倒推值的下界α定為 1，當(dāng)然有可能比 1更小，因?yàn)樗衅渌膬鹤庸?jié)點(diǎn)。 畫出節(jié)點(diǎn) B及它的第一個兒子節(jié)點(diǎn) C，算出節(jié)點(diǎn) C的靜態(tài)值為 1，于是節(jié)點(diǎn) B的倒推值不會比 1大，又注意到節(jié)點(diǎn) B的最終倒推值不會小于起始節(jié)點(diǎn)的 α值，由此可肯定最終倒推值 β=1。由于 α值不比 β值小，故可以終止節(jié)點(diǎn) B的搜索。 2022/8/21 98 ? 例： αβ剪枝技術(shù)的例子，圖 。圖中所生成的搜索樹共有六層 (我們規(guī)定首先生成最左面的節(jié)點(diǎn)。 MAX節(jié)點(diǎn)用方塊表示， MIN節(jié)點(diǎn)用圓圈表示 )。圖中還給出了端節(jié)點(diǎn)的靜態(tài)估值?，F(xiàn)在假設(shè)我們采用 αβ剪枝技術(shù)來引導(dǎo)深度優(yōu)先搜索。由 αβ剪枝技術(shù)生成的子樹在圖中用粗樹枝表示。發(fā)生修剪的那些節(jié)點(diǎn)用“ ”表示。 2022/8/21 99 2022/8/21 100 ? 我們注意到原先 41個端節(jié)點(diǎn)只有 18個必須估值，可見說明 αβ方法能夠有效地提高效率。 下面讓我們對 αβ剪枝技術(shù)的搜索效率再作一些分析。要進(jìn)行 αβ修剪，必須至少使某一部分的搜索樹生長到最大深度，因?yàn)?α和 β值必須以端節(jié)點(diǎn)的靜態(tài)估值為依據(jù)。因此采用 αβ剪枝技術(shù)通常都要使用某種深度優(yōu)先的搜索方法。而且在一次搜索期間修剪的枝數(shù)取決于早期的 α、β值與最終倒推值之間的近似程度。 起始節(jié)點(diǎn)的最終倒推值等于某個端節(jié)點(diǎn)的靜態(tài)估值。如果在深度優(yōu)先搜索過程中第一次就遇到這個端節(jié)點(diǎn)，則修剪枝數(shù)最大。當(dāng)前修剪枝數(shù)最大時，需要生成和估計(jì)的端節(jié)點(diǎn)數(shù)就最少。 αβ剪枝技術(shù)的搜索效率還可通過數(shù)學(xué)公式進(jìn)行估算。 2022/8/21 101 遺傳算法 ? 遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類搜索算法，從某種程度上說遺傳算法是對生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。霍蘭德 (Holland)在他的著作 《 Adaptation in Natural and Artificial Systems》 首次提出遺傳算法，并主要由他和他的學(xué)生發(fā)展起來的。 ? 生物種群的生存過程普遍遵循達(dá)爾文進(jìn)化準(zhǔn)則，群體中的個體根據(jù)對環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進(jìn)化過程的結(jié)果反映在個體的結(jié)構(gòu)上，其染色體包含若干基因，相應(yīng)的表現(xiàn)型和基因型的聯(lián)系體現(xiàn)了個體的外部特性與內(nèi)部機(jī)理間邏輯關(guān)系。通過個體之間的交叉、變異來適應(yīng)大自然環(huán)境。生物染色體用數(shù)學(xué)方式或計(jì)算機(jī)方式來體現(xiàn)就是一串?dāng)?shù)碼，仍叫染色體，有時也叫個體；適應(yīng)能力是對應(yīng)著一個染色體的一個數(shù)值來衡量；染色體的選擇或淘汰則按所面對的問題是求最大還是最小來進(jìn)行。 2022/8/21 102 ? 遺傳算法自從 1965年提出以來，在國際上已經(jīng)形成了一個比較活躍的研究領(lǐng)域，已召開了多次比較重要的國際會議和創(chuàng)辦了很多相關(guān)的國際刊物。 遺傳算法已用于求解帶有應(yīng)用前景的一些問題，例如遺傳程序設(shè)計(jì)、函數(shù)優(yōu)化、排序問題、人工神經(jīng)網(wǎng)絡(luò)、分類系統(tǒng)、計(jì)算機(jī)圖像處理和機(jī)器人運(yùn)動規(guī)劃等。 2022/8/21 103 遺傳算法的結(jié)構(gòu) ? 霍蘭德 (Holland)的遺傳算法通常被稱為 簡單遺傳算法 (簡稱 SGA)，我們以此作為討論主要對象，加上適應(yīng)的改進(jìn)，分析遺傳算法的結(jié)構(gòu)和機(jī)理。 我們首先介紹主要的概念。我們在講解中會結(jié)合如下的貨郎擔(dān)問題 (Travelling Salesman Problem，簡記為 TSP)：設(shè)有 n個城市，城市 i和城市 j之間的距離為 d(i， j) i, j=1,...,n． TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短。 2022/8/21 104 ? 許多應(yīng)用問題結(jié)構(gòu)很復(fù)雜，但可以化為簡單的位串形式編碼表示，我們將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫 編碼 ；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫 譯碼 。我們把位串形式編碼表示叫 染色體 ，有時也叫個體。 對 TSP可以按一條回路城市的次序進(jìn)行編碼，比如碼串 134567829表示從城市 1 開始，依次是城市3,4,5,6,7,8,2,9，最后回到城市 1。一般情況是從城市 w1開始，依次經(jīng)過城市 w2,…… ， wn，最后回到城市 w1，我們就有如下編碼表示： w1 w2 …… w n 由于是回路，記 wn+1= w1。它其實(shí)是 1， …… ， n的一個循環(huán)排列。要注意 w1,w2 ,…… ， wn是互不相同的。 2022/8/21 105 ? 為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)利劣汰原則。對優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。 TSP的目標(biāo)是路徑總長度為最短，路徑總長度的倒數(shù)就可以為 TSP的適應(yīng)度函數(shù)： 2022/8/21 106 ? 請注意其中 wn+1= w1。適應(yīng)度函數(shù)要有效反映每一個染色體與問題的最優(yōu)解染色體之間的差距，一個染色體與問題的最優(yōu)解染色體之間的差距小，則對應(yīng)的適應(yīng)度函數(shù)值之差就小，否則就大。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。 2022/8/21 107 ? 簡單遺傳算法的遺傳操作主要有三種 :選擇 (selection)、交叉 (crossover)、變異 (mutation)。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。 選擇操作也叫復(fù)制操作，根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應(yīng)度較大 (優(yōu)良 )個體有較大的存在機(jī)會，而適應(yīng)度較?。ǖ土樱┑膫€體繼續(xù)存在的機(jī)會也較小。簡單遺傳算法采用賭輪選擇機(jī)制，令 Σfi表示群體的適應(yīng)度值之總和， fi表示種群中第 i個染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額 fi／Σfi。 2022/8/21 108 ? 交叉操作的簡單方式是將被選擇出的兩個個體 P1和 P2作為父母個體，將兩者的部分碼值進(jìn)行交換。假設(shè)有如下八位長的二個體： 2022/8/21 109 ? 產(chǎn)生一個在 1到 7之間的隨機(jī)數(shù) c，假如現(xiàn)在產(chǎn)生的是 3，將 P1和 P2的低三位交換： P1的高五位與 P2的低三位組成數(shù)串 10001001，這就是 P1和 P2的一個后代 Q1個體； P2的高五位與 P1的低三位組成數(shù)串 11011110，這就是 P1和 P2的一個后代 Q2個體。其交換過程如下圖所示： 2022/8/21 110 ? 變異操作的簡單方式是改變數(shù)碼串的某個位置上的數(shù)碼。我們先以最簡單的二進(jìn)制編碼表示方式來說明，二進(jìn)制編碼表示的每一個位置的數(shù)碼只有 0與 1這兩個可能，比如有如下二進(jìn)制編碼表示： ? 其碼長為 8，隨機(jī)產(chǎn)生一個 1至 8之間的數(shù) k，假如現(xiàn)在 k=5，對從右往左的第 5位進(jìn)行變異操作，將原來的 0變?yōu)?1，得到如下數(shù)碼串（紅