人工智能之技術(shù)與算法

　　人工智能之技術(shù)與算法

　　這篇文章更類似于科普貼，它完全可以作為你學(xué)習(xí)人工智能的入門文章，我的目的是用通俗的語言概括人工智能領(lǐng)域的各項技術(shù)，從而讓讀者有個直觀淺顯的認識

　　隨機（Random）

　　隨機是智能的基礎(chǔ)，人工智能的很多技術(shù)都需要用到隨機，因此有必要把這個提到前面談?wù)?/p>

　　一考慮基于C/C++，般我們都是使用的rand（）等函數(shù)實現(xiàn)隨機，當(dāng)然我們也有吊炸天的boost提供了各種分布范圍的隨機：

　　#include 《boost/random.hpp>

　　uniform_int《> distribution（1， 100） ;

　　mt19937 engine ;variate_generator《mt19937，uniform_int《> > myrandom （engine， distribution）;

　　// uniform_smallint：在小整數(shù)域內(nèi)的均勻分布

　　// uniform_int：在整數(shù)域上的均勻分布

　　// uniform_01：在區(qū)間［0，1］上的實數(shù)連續(xù)均勻分布

　　// uniform_real：在區(qū)間［min，max］上的實數(shù)連續(xù)均勻分布

　　// bernoulli_distribution：伯努利分布

　　// binomial_distribution：二項分布

　　// cauchy_distribution：柯西（洛倫茲）分布

　　// gamma_distribution：伽馬分布

　　// poisson_distribution：泊松分布

　　// geometric_distribution：幾何分布

　　// triangle_distribution：三角分布

　　// exponential_distribution：指數(shù)分布

　　// normal_distribution：正態(tài)分布

　　// lognormal_distribution：對數(shù)正態(tài)分

　　// uniform_on_sphere：球面均勻分布

　　但是這個取到的數(shù)據(jù)都是偽隨機數(shù)，或依靠系統(tǒng)時間，或依靠日期等，顯然這個對于人工智能是不夠的，我們需要真隨機，C++11的std ：：random_device給了我們希望，如名這個的隨機石使用的硬件，linux是讀取dev/urandom硬件設(shè)備，但是windows居然還是調(diào)用的rand_s（）函數(shù)！這個沒什么太多說的，買點專業(yè)硬件即可。

　　狀態(tài)空間啟發(fā)式搜索-A尋路算法（A* Search Algorithm）

　　A尋路算法是A*的退化，所以我不考慮說什么，當(dāng)然如果你想學(xué)習(xí)A星，先學(xué)A是一個不錯的選擇，為此我特意寫了一篇文章詳細講解各種尋路搜索策略http://blog.csdn.net/racaljk/article/details/18887881

　　狀態(tài)空間啟發(fā)式搜索-A星尋路算法（A* Search Algorithm）

　　其實這個標(biāo)題是我自己寫得到，原翻譯顯然沒有”尋路“這兩個字，因為A星算法包括但不僅限于存在于人工智能的尋路中，但是既然標(biāo)題是人工智能，這樣也無傷大雅，在說A*之前有必要說所深度優(yōu)先搜索算法DFS和廣度優(yōu)先搜索算法BFS，假設(shè)一個map上面，有諸多障礙，目前機器人需要做的就是在這個有限的地圖上沒有其他信息支持，需要從起點出發(fā)找到終點，如上所說，這個地圖里面的障礙時允許嘗試的，如果我們使用深度有限算法，他會從起點出發(fā)走一條路并一直走下去，直到遇到障礙或者沒有達成條件-到終點，于是返回重新走，顯然他不會愚蠢到走與之前同樣的錯誤路線，DFS比較耗時，但是如果成功了也就執(zhí)行了這條路線（沒有人為干擾的情況下），而BFS則在遇到障礙時就會向四周試探性的走幾步，一旦試探成功就繼續(xù)走，如此遞歸，直到成功（如果在有限的map下，且存在正確路徑，則必然會成功），簡單來說，我們的理論都是基于二叉樹的條件下，BFS是沿著樹的寬度進行完全變遍歷，而DFS是沿著數(shù)的一條分支一直走下去，直到成功，A*結(jié)合這兩個算法的優(yōu)點，從而實現(xiàn)快速尋路

　　下面這個更直觀：

　　假設(shè)這個是一個地圖，左#表示起點，右#表示終點，@@表示障礙

　　00000000000

　　000000@0000

　　#0000@@000#

　　000000@0000

　　00000000000

　　如果用DFS他會像掃描儀一樣從左至右掃描到終點，如果用DFS他會像掃描一樣從中間向兩邊掃描掃描，而A*則結(jié)合這兩個算法的優(yōu)勢，從而實現(xiàn)最快的尋路，關(guān)于A*算法的源碼請自行百度

　　下面是一個A*的一個動畫演示

　　?

　　D星尋路算法（Dynamic A* Search Algorithm）

　　顧名思義d*也就是動態(tài)A*尋路算法，區(qū)別僅在于A*是局限于A*是生成一條路就一直走下去，但實際情況下有很多突發(fā)情況，比如生成的那條路被堵了，就需要重新生成新的路線，這就需要D*了，D*也就是說動態(tài)生成A*路線。

　　狀態(tài)機（Finite-State Machine）

　　FSM看似很高端，的確我當(dāng)初也被嚇著了，不過看了下面的內(nèi)容就會覺得很簡單，細分狀態(tài)機分為有限狀態(tài)機和模糊狀態(tài)機，也加同步狀態(tài)機和異步狀態(tài)機，兩種狀態(tài)機的區(qū)別在于有限狀態(tài)機在一個時段只能處于一種狀態(tài)，而模糊（也即異步）狀態(tài)機有一個權(quán)重值，根據(jù)這個權(quán)重值我們可以分配給不同的狀態(tài)不同的權(quán)重，比如一個人，有限狀態(tài)機允許人去喝水，模糊狀態(tài)機允許80%去喝水，20%接水。你甚至可以理解為FSM是單線程，F(xiàn)μSM是多線程。有關(guān)狀態(tài)機的資料可以參見：http://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA

　　為了便于理解，現(xiàn)復(fù)制一下基本概念：

　　狀態(tài)（State）指的是對象在其生命周期中的一種狀況，處于某個特定狀態(tài)中的對象必然會滿足某些條件、執(zhí)行某些動作或者是等待某些事件。

　　事件（Event）指的是在時間和空間上占有一定位置，并且對狀態(tài)機來講是有意義的那些事情。事件通常會引起狀態(tài)的變遷，促使?fàn)顟B(tài)機從一種狀態(tài)切換到另一種狀態(tài)。

　　轉(zhuǎn)換（Transition）指的是兩個狀態(tài)之間的一種關(guān)系，表明對象將在第一個狀態(tài)中執(zhí)行一定的動作，并將在某個事件發(fā)生同時某個特定條件滿足時進入第二個狀態(tài)。

　　動作（Action）指的是狀態(tài)機中可以執(zhí)行的那些原子操作，所謂原子操作指的是它們在運行的過程中不能被其他消息所中斷，必須一直執(zhí)行下去。

　　看不懂上面可以看下面：

　　?

　　這里盜用一張UML（http://www.cnblogs.com/ywqu/archive/2009/12/17/1626043.html這是關(guān)于UML比較詳細的介紹）圖片來解釋一下，黑圓圈表示初始狀態(tài)，非規(guī)則長方形表示一個狀態(tài)，Active表示狀態(tài)條件，也就是這種狀態(tài)需要什么條件，Reset表示轉(zhuǎn)換事件

　　我們結(jié)合boost：：statechart可以很容易寫出上述圖片的代碼

　　#include《boost/statechart/state_machine.hpp>

　　#include《boost/statechart/simple_state.hpp>

　　class Mchine_Initiate;//模板必須有一個class作為初始化后的狀態(tài)

　　class Machine ： boost：：statechart：：state_machine《Machine， Mchine_Initiate>{

　　public：

　　Machine（）{std：：cout 《《 “Machine class”;};

　　};

　　class Mchine_Initiate{

　　public：

　　Mchine_Initiate（）{std：：cout 《《 “in”;};

　　~ Mchine_Initiate（）{std：：cout 《《 “out~”};

　　};

　　決策樹（Decision Tree）

　　這個大家應(yīng)該都不陌生，當(dāng)我們遇到一個問題時會有多種處理方法，這符合一個樹狀態(tài)結(jié)構(gòu)，

　　我們會選擇最佳策略進行處理，同樣，人工智能也有類似實現(xiàn)名為決策樹，我們會發(fā)現(xiàn)者似乎與FSM有聯(lián)系，恭喜你你的發(fā)現(xiàn)時正確的，這其實算是靜態(tài)FSM，F(xiàn)SM應(yīng)該冠名為動態(tài)FSM才是最佳的，當(dāng)然這是我個人看法，何謂靜態(tài)，就是既定的方案，這個樹枝都有權(quán)重值，50%A樹枝，50%B樹枝，機器人可以按照這個既定的方案執(zhí)行，因此決策樹可以存儲并分享，而FSM是動態(tài)選擇，有關(guān)決策樹的概念就這么多了，詳細實現(xiàn)大家可以去百度一下。這里提供一篇算法，遺憾的是里面專業(yè)術(shù)語比較多，理解較困難。

　　博弈論（Game Theroy）

　　這是我最感喜歡的部分，某種程度上說沒有博弈論體系的AI算不上AI，博弈論在人工智能中廣泛用于最優(yōu)化策略，從原英文中我們就看得出這個與游戲有關(guān)，對象是單體，著名的例子就是簡化的囚徒困境：

　　兩個囚徒甲和已違法被抓，分別關(guān)押，有如下選擇：

　　如果兩個人都承認，那么都判10年

　　如果一人不承認，另一人承認并指認同伙，那么這個人將無罪釋放，而被指認的那個人將被判20年

　　如果兩個人都不承認，將只是非法帶槍罪判1年。

　　從單體出發(fā)，假設(shè)我是甲，我心里會想：如果我認罪，10年，不認罪20年，10《20，認罪最好。對方認罪我0年，對方不認罪1年，0《1認罪最后

　　以類同，因此選擇認罪各10年

　　在人工智能中我們要窮舉所有可能，并計算最終收益，最后讓收益最大化，這就是人工智能的博弈論理論，博弈論博大精深，這里只是十分基礎(chǔ)的認識

　　人工智能領(lǐng)域的博弈論我們需要考慮兩個東西：期望收益、規(guī)則設(shè)定。比如我們的規(guī)則設(shè)定是機器人比賽，然后機器人要選擇收益最大化，因此我們就要窮舉各種可以執(zhí)行的策略，并最終從這些策略對比使收益最大化，再如田忌賽馬這個強拉硬扯算是博弈論，規(guī)則是上中下等馬比賽，上>中，中>下，然后計算機就要窮舉所有策略，優(yōu)上>良上，優(yōu)上>良中。..。，最終更加這些策略對比使收益最大化，我們可以把這些作為一個樹狀結(jié)構(gòu)實現(xiàn)，稱之為博弈樹，博弈樹廣泛引用于各種棋牌游戲的AI，很多算法如alpha-beta搜索都是基于博弈樹實現(xiàn)的

　　最大最小搜索算法（Max-min search algorithm）

　　最大最小搜索算法基于博弈樹，廣泛應(yīng)用于棋盤較小的棋牌游戲AI中，詳細請看我的文章http://blog.csdn.net/racaljk/article/details/18842545

　　神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks）

　　神經(jīng)網(wǎng)絡(luò)同上是人工智能的智能所在，神經(jīng)網(wǎng)絡(luò)類似于抽象了人類的歷史，請不要反駁遠古時期人類沒有手機這句話，人類的聰明是經(jīng)驗所得，試想一下，假設(shè)機器人前面有一個障礙，這個障礙堵塞了路，機器人就會不斷使用尋路算法嘗試，顯然，這是沒有效果的，因為沒有正確的道路，想想如果是你你會怎么做，你會跳過去，是的，這就是一個神經(jīng)網(wǎng)絡(luò)的實現(xiàn)，你早就經(jīng)歷過這種事情，現(xiàn)在你需要做的就是運用之前的經(jīng)驗來解決這個”新“情況。要想智能，沒有這種經(jīng)驗的學(xué)習(xí)都是紙上談兵（當(dāng)然前提是你得置入跳的動作代碼），當(dāng)機器人用A*嘗試5次都失敗的情況下它就會改變策略，調(diào)整腳部神經(jīng)元閥值，當(dāng)調(diào)節(jié)為1，發(fā)現(xiàn)跳不過，就調(diào)節(jié)為8，如此在一定的區(qū)間內(nèi)隨機直到成功

　　置信網(wǎng)絡(luò)（Belief Network）

　　從分類中可以看出置信網(wǎng)絡(luò)從屬于深度學(xué)習(xí)，而深度學(xué)習(xí)父級是神經(jīng)網(wǎng)絡(luò)，也就是說置信技術(shù)是以神經(jīng)網(wǎng)絡(luò)為基礎(chǔ)的在其基礎(chǔ)上優(yōu)化的一門機器學(xué)習(xí)技術(shù)。

　　置信技術(shù)把人工智能推向了極致，他與博弈論、神經(jīng)網(wǎng)絡(luò)遺傳算法構(gòu)成了AI的核心體系。

　　之前我們的神經(jīng)網(wǎng)絡(luò)和遺傳算法使用窮舉進行嘗試和篩選，而置信網(wǎng)絡(luò)總結(jié)數(shù)據(jù)并試圖發(fā)現(xiàn)規(guī)律，這看起來多麼偉大，同時也多麼不容易，把客觀世界object的規(guī)律映射到智能機器，即使是人類也不一定做好

　　同樣是上面走路的例子，我們假設(shè)了神經(jīng)網(wǎng)絡(luò)的閥值必須要是偶數(shù)*2才能通過，貝葉斯智信網(wǎng)絡(luò)則是用來總結(jié)得出這個規(guī)律，他需要前面的數(shù)據(jù)并進行分析，并把抽象數(shù)據(jù)轉(zhuǎn)化為客觀規(guī)律

　　?

　　上圖就是一個經(jīng)典的置信網(wǎng)絡(luò)，其中紅色圓圈表示未知規(guī)律，藍色為表象

　　置信網(wǎng)絡(luò)可以極大優(yōu)化神經(jīng)網(wǎng)絡(luò)，減少嘗試次數(shù)，比如利用置信網(wǎng)絡(luò)總結(jié)出結(jié)果在偶數(shù)*2中間，通過其他信息比如數(shù)量是家庭垃圾物體數(shù)，神經(jīng)網(wǎng)絡(luò)便可在一個較小的范圍類進行偶數(shù)*2的嘗試

　　遺傳算法（Genetic Algorithm）

　　遺傳算法的理論基礎(chǔ)是達爾文的進化論，他模擬實現(xiàn)凈化論中的自然選擇和遺傳機制，神經(jīng)網(wǎng)絡(luò)無法吸取上次失敗的教訓(xùn)，只是一味的嘗試，遺傳算法由此而生解決這個問題，它吸取群體的智慧于一生，結(jié)合神經(jīng)網(wǎng)絡(luò)實現(xiàn)了更高層次的智能，遺傳算法模擬培養(yǎng)第一代基因，神經(jīng)網(wǎng)絡(luò)進行嘗試，然后進行優(yōu)勝劣汰，如此遞歸，當(dāng)?shù)搅艘粋€很高的層次都無法解決問題的時候他就會考慮基因重組，也就是雜交，因為他認為第一代的優(yōu)秀基因本身就是錯誤的方向，只是錯誤的方向上的優(yōu)秀基因，因此他選擇其他方向的基因用神經(jīng)網(wǎng)絡(luò)嘗試，遺傳算法優(yōu)勝劣汰

　?