電子發(fā)燒友App
人工智能之技術(shù)與算法
這篇文章更類似于科普貼，它完全可以作為你學(xué)習(xí)人工智能的入門文章，我的目的是用通俗的語言概括人工智能領(lǐng)域的各項(xiàng)技術(shù)，從而讓讀者有個直觀淺顯的認(rèn)識
隨機(jī)（Random）
隨機(jī)是智能的基礎(chǔ)，人工智能的很多技術(shù)都需要用到隨機(jī)，因此有必要把這個提到前面談?wù)?/p>
一考慮基于C/C++，般我們都是使用的rand（）等函數(shù)實(shí)現(xiàn)隨機(jī)，當(dāng)然我們也有吊炸天的boost提供了各種分布范圍的隨機(jī)：
#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í)數(shù)連續(xù)均勻分布
// uniform_real：在區(qū)間［min，max］上的實(shí)數(shù)連續(xù)均勻分布
// bernoulli_distribution：伯努利分布
// binomial_distribution：二項(xiàng)分布
// 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ù)都是偽隨機(jī)數(shù)，或依靠系統(tǒng)時間，或依靠日期等，顯然這個對于人工智能是不夠的，我們需要真隨機(jī)，C++11的std ：：random_device給了我們希望，如名這個的隨機(jī)石使用的硬件，linux是讀取dev/urandom硬件設(shè)備，但是windows居然還是調(diào)用的rand_s（）函數(shù)！這個沒什么太多說的，買點(diǎn)專業(yè)硬件即可。
狀態(tài)空間啟發(fā)式搜索-A尋路算法（A* Search Algorithm）
A尋路算法是A*的退化，所以我不考慮說什么，當(dāng)然如果你想學(xué)習(xí)A星，先學(xué)A是一個不錯的選擇，為此我特意寫了一篇文章詳細(xì)講解各種尋路搜索策略http://blog.csdn.net/racaljk/article/details/18887881
狀態(tài)空間啟發(fā)式搜索-A星尋路算法（A* Search Algorithm）
其實(shí)這個標(biāo)題是我自己寫得到，原翻譯顯然沒有”尋路“這兩個字，因?yàn)锳星算法包括但不僅限于存在于人工智能的尋路中，但是既然標(biāo)題是人工智能，這樣也無傷大雅，在說A*之前有必要說所深度優(yōu)先搜索算法DFS和廣度優(yōu)先搜索算法BFS，假設(shè)一個map上面，有諸多障礙，目前機(jī)器人需要做的就是在這個有限的地圖上沒有其他信息支持，需要從起點(diǎn)出發(fā)找到終點(diǎn)，如上所說，這個地圖里面的障礙時允許嘗試的，如果我們使用深度有限算法，他會從起點(diǎn)出發(fā)走一條路并一直走下去，直到遇到障礙或者沒有達(dá)成條件-到終點(diǎn)，于是返回重新走，顯然他不會愚蠢到走與之前同樣的錯誤路線，DFS比較耗時，但是如果成功了也就執(zhí)行了這條路線（沒有人為干擾的情況下），而BFS則在遇到障礙時就會向四周試探性的走幾步，一旦試探成功就繼續(xù)走，如此遞歸，直到成功（如果在有限的map下，且存在正確路徑，則必然會成功），簡單來說，我們的理論都是基于二叉樹的條件下，BFS是沿著樹的寬度進(jìn)行完全變遍歷，而DFS是沿著數(shù)的一條分支一直走下去，直到成功，A*結(jié)合這兩個算法的優(yōu)點(diǎn)，從而實(shí)現(xiàn)快速尋路
下面這個更直觀：
假設(shè)這個是一個地圖，左#表示起點(diǎn)，右#表示終點(diǎn)，@@表示障礙
00000000000
000000@0000
#0000@@000#
000000@0000
00000000000
如果用DFS他會像掃描儀一樣從左至右掃描到終點(diǎn)，如果用DFS他會像掃描一樣從中間向兩邊掃描掃描，而A*則結(jié)合這兩個算法的優(yōu)勢，從而實(shí)現(xiàn)最快的尋路，關(guān)于A*算法的源碼請自行百度
下面是一個A*的一個動畫演示
?
D星尋路算法（Dynamic A* Search Algorithm）
顧名思義d*也就是動態(tài)A*尋路算法，區(qū)別僅在于A*是局限于A*是生成一條路就一直走下去，但實(shí)際情況下有很多突發(fā)情況，比如生成的那條路被堵了，就需要重新生成新的路線，這就需要D*了，D*也就是說動態(tài)生成A*路線。
狀態(tài)機(jī)（Finite-State Machine）
FSM看似很高端，的確我當(dāng)初也被嚇著了，不過看了下面的內(nèi)容就會覺得很簡單，細(xì)分狀態(tài)機(jī)分為有限狀態(tài)機(jī)和模糊狀態(tài)機(jī)，也加同步狀態(tài)機(jī)和異步狀態(tài)機(jī)，兩種狀態(tài)機(jī)的區(qū)別在于有限狀態(tài)機(jī)在一個時段只能處于一種狀態(tài)，而模糊（也即異步）狀態(tài)機(jī)有一個權(quán)重值，根據(jù)這個權(quán)重值我們可以分配給不同的狀態(tài)不同的權(quán)重，比如一個人，有限狀態(tài)機(jī)允許人去喝水，模糊狀態(tài)機(jī)允許80%去喝水，20%接水。你甚至可以理解為FSM是單線程，F(xiàn)μSM是多線程。有關(guān)狀態(tài)機(jī)的資料可以參見：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)機(jī)來講是有意義的那些事情。事件通常會引起狀態(tài)的變遷，促使?fàn)顟B(tài)機(jī)從一種狀態(tài)切換到另一種狀態(tài)。
轉(zhuǎn)換（Transition）指的是兩個狀態(tài)之間的一種關(guān)系，表明對象將在第一個狀態(tài)中執(zhí)行一定的動作，并將在某個事件發(fā)生同時某個特定條件滿足時進(jìn)入第二個狀態(tài)。
動作（Action）指的是狀態(tài)機(jī)中可以執(zhí)行的那些原子操作，所謂原子操作指的是它們在運(yùn)行的過程中不能被其他消息所中斷，必須一直執(zhí)行下去。
看不懂上面可以看下面：
?
這里盜用一張UML（http://www.cnblogs.com/ywqu/archive/2009/12/17/1626043.html這是關(guān)于UML比較詳細(xì)的介紹）圖片來解釋一下，黑圓圈表示初始狀態(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)，
我們會選擇最佳策略進(jìn)行處理，同樣，人工智能也有類似實(shí)現(xiàn)名為決策樹，我們會發(fā)現(xiàn)者似乎與FSM有聯(lián)系，恭喜你你的發(fā)現(xiàn)時正確的，這其實(shí)算是靜態(tài)FSM，F(xiàn)SM應(yīng)該冠名為動態(tài)FSM才是最佳的，當(dāng)然這是我個人看法，何謂靜態(tài)，就是既定的方案，這個樹枝都有權(quán)重值，50%A樹枝，50%B樹枝，機(jī)器人可以按照這個既定的方案執(zhí)行，因此決策樹可以存儲并分享，而FSM是動態(tài)選擇，有關(guān)決策樹的概念就這么多了，詳細(xì)實(shí)現(xiàn)大家可以去百度一下。這里提供一篇算法，遺憾的是里面專業(yè)術(shù)語比較多，理解較困難。
博弈論（Game Theroy）
這是我最感喜歡的部分，某種程度上說沒有博弈論體系的AI算不上AI，博弈論在人工智能中廣泛用于最優(yōu)化策略，從原英文中我們就看得出這個與游戲有關(guān)，對象是單體，著名的例子就是簡化的囚徒困境：
兩個囚徒甲和已違法被抓，分別關(guān)押，有如下選擇：
如果兩個人都承認(rèn)，那么都判10年
如果一人不承認(rèn)，另一人承認(rèn)并指認(rèn)同伙，那么這個人將無罪釋放，而被指認(rèn)的那個人將被判20年
如果兩個人都不承認(rèn)，將只是非法帶槍罪判1年。
從單體出發(fā)，假設(shè)我是甲，我心里會想：如果我認(rèn)罪，10年，不認(rèn)罪20年，10《20，認(rèn)罪最好。對方認(rèn)罪我0年，對方不認(rèn)罪1年，0《1認(rèn)罪最后
以類同，因此選擇認(rèn)罪各10年
在人工智能中我們要窮舉所有可能，并計算最終收益，最后讓收益最大化，這就是人工智能的博弈論理論，博弈論博大精深，這里只是十分基礎(chǔ)的認(rèn)識
人工智能領(lǐng)域的博弈論我們需要考慮兩個東西：期望收益、規(guī)則設(shè)定。比如我們的規(guī)則設(shè)定是機(jī)器人比賽，然后機(jī)器人要選擇收益最大化，因此我們就要窮舉各種可以執(zhí)行的策略，并最終從這些策略對比使收益最大化，再如田忌賽馬這個強(qiáng)拉硬扯算是博弈論，規(guī)則是上中下等馬比賽，上>中，中>下，然后計算機(jī)就要窮舉所有策略，優(yōu)上>良上，優(yōu)上>良中。..。，最終更加這些策略對比使收益最大化，我們可以把這些作為一個樹狀結(jié)構(gòu)實(shí)現(xiàn)，稱之為博弈樹，博弈樹廣泛引用于各種棋牌游戲的AI，很多算法如alpha-beta搜索都是基于博弈樹實(shí)現(xiàn)的
最大最小搜索算法（Max-min search algorithm）
最大最小搜索算法基于博弈樹，廣泛應(yīng)用于棋盤較小的棋牌游戲AI中，詳細(xì)請看我的文章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ò)類似于抽象了人類的歷史，請不要反駁遠(yuǎn)古時期人類沒有手機(jī)這句話，人類的聰明是經(jīng)驗(yàn)所得，試想一下，假設(shè)機(jī)器人前面有一個障礙，這個障礙堵塞了路，機(jī)器人就會不斷使用尋路算法嘗試，顯然，這是沒有效果的，因?yàn)闆]有正確的道路，想想如果是你你會怎么做，你會跳過去，是的，這就是一個神經(jīng)網(wǎng)絡(luò)的實(shí)現(xiàn)，你早就經(jīng)歷過這種事情，現(xiàn)在你需要做的就是運(yùn)用之前的經(jīng)驗(yàn)來解決這個”新“情況。要想智能，沒有這種經(jīng)驗(yàn)的學(xué)習(xí)都是紙上談兵（當(dāng)然前提是你得置入跳的動作代碼），當(dāng)機(jī)器人用A*嘗試5次都失敗的情況下它就會改變策略，調(diào)整腳部神經(jīng)元閥值，當(dāng)調(diào)節(jié)為1，發(fā)現(xiàn)跳不過，就調(diào)節(jié)為8，如此在一定的區(qū)間內(nèi)隨機(jī)直到成功
置信網(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)化的一門機(jī)器學(xué)習(xí)技術(shù)。
置信技術(shù)把人工智能推向了極致，他與博弈論、神經(jīng)網(wǎng)絡(luò)遺傳算法構(gòu)成了AI的核心體系。
之前我們的神經(jīng)網(wǎng)絡(luò)和遺傳算法使用窮舉進(jìn)行嘗試和篩選，而置信網(wǎng)絡(luò)總結(jié)數(shù)據(jù)并試圖發(fā)現(xiàn)規(guī)律，這看起來多麼偉大，同時也多麼不容易，把客觀世界object的規(guī)律映射到智能機(jī)器，即使是人類也不一定做好
同樣是上面走路的例子，我們假設(shè)了神經(jīng)網(wǎng)絡(luò)的閥值必須要是偶數(shù)*2才能通過，貝葉斯智信網(wǎng)絡(luò)則是用來總結(jié)得出這個規(guī)律，他需要前面的數(shù)據(jù)并進(jìn)行分析，并把抽象數(shù)據(jù)轉(zhuǎn)化為客觀規(guī)律
?
上圖就是一個經(jīng)典的置信網(wǎng)絡(luò)，其中紅色圓圈表示未知規(guī)律，藍(lán)色為表象
置信網(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ò)便可在一個較小的范圍類進(jìn)行偶數(shù)*2的嘗試
遺傳算法（Genetic Algorithm）
遺傳算法的理論基礎(chǔ)是達(dá)爾文的進(jìn)化論，他模擬實(shí)現(xiàn)凈化論中的自然選擇和遺傳機(jī)制，神經(jīng)網(wǎng)絡(luò)無法吸取上次失敗的教訓(xùn)，只是一味的嘗試，遺傳算法由此而生解決這個問題，它吸取群體的智慧于一生，結(jié)合神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了更高層次的智能，遺傳算法模擬培養(yǎng)第一代基因，神經(jīng)網(wǎng)絡(luò)進(jìn)行嘗試，然后進(jìn)行優(yōu)勝劣汰，如此遞歸，當(dāng)?shù)搅艘粋€很高的層次都無法解決問題的時候他就會考慮基因重組，也就是雜交，因?yàn)樗J(rèn)為第一代的優(yōu)秀基因本身就是錯誤的方向，只是錯誤的方向上的優(yōu)秀基因，因此他選擇其他方向的基因用神經(jīng)網(wǎng)絡(luò)嘗試，遺傳算法優(yōu)勝劣汰
?
工商網(wǎng)監(jiān)
評論