人工智能07蟻群算法及其應(yīng)用

第七章蟻群算法及其應(yīng)用蟻群算法的背景20世紀(jì)50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)。提出了許多用以解決復(fù)雜優(yōu)化問題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問題。蟻群算法從螞蟻覓食得到啟發(fā)。蟻群算法的背景仿生算法集群智能算法概率型算法遺傳算法、進(jìn)化算法粒子群算法（課程論文2）、蟻群算法用來解決眾多NP-hard問題蟻群算法的背景自然蟻群的自組織行為特征高度結(jié)構(gòu)化的組織——雖然螞蟻的個(gè)體行為極其簡單，但由個(gè)體組成的蟻群卻構(gòu)成高度結(jié)構(gòu)化的社會(huì)組織，螞蟻社會(huì)的成員有分工，有相互的通信和信息傳遞。自然優(yōu)化——蟻群在覓食過程中，在沒有任何提示下總能找到從蟻巢到食物源之間的最短路徑；當(dāng)經(jīng)過的路線上出現(xiàn)障礙物時(shí)，還能迅速找到新的最優(yōu)路徑。信息正反饋——螞蟻在尋找食物時(shí)，在其經(jīng)過的路徑上釋放信息素（外激素）。螞蟻基本沒有視覺，但能在小范圍內(nèi)察覺同類散發(fā)的信息素的軌跡，由此來決定何去何從，并傾向于朝著信息素強(qiáng)度高的方向移動(dòng)。自催化行為——某條路徑上走過的螞蟻越多，留下的信息素也越多（隨時(shí)間蒸發(fā)一部分），后來螞蟻選擇該路徑的概率也越高。蟻群算法的背景概念原型 各個(gè)螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。 當(dāng)一只找到食物以后，它會(huì)向環(huán)境釋放一種揮發(fā)性分泌物pheromone(稱為信息素,該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠(yuǎn)近)來實(shí)現(xiàn)的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會(huì)找到食物。 有些螞蟻并沒有像其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。

最后，經(jīng)過一段時(shí)間運(yùn)行，就可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。蟻群算法的提出算法的提出 蟻群算法（AntColonyOptimization,ACO），又稱螞蟻算法——一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。 它由MarcoDorigo于1992年在他的博士論文“Antsystem:optimizationbyacolonyofcooperatingagents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。最早用于解決著名的旅行商問題(TSP,travelingsalesmanproblem)。蟻群算法的提出基本原理

蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。蟻群算法的提出簡化的螞蟻尋食正反饋過程

螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條路線分配一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。蟻群算法的提出

本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。蟻群算法的提出

假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。蟻群算法的提出人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群在選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。人工蟻群VS自然蟻群蟻群算法的特征

蟻群算法采用了分布式正反饋并行計(jì)算機(jī)制,易于與其他方法結(jié)合,并具有較強(qiáng)的魯棒性。（1）其原理是一種正反饋機(jī)制或稱增強(qiáng)型學(xué)習(xí)系統(tǒng)；它通過信息素的不斷更新達(dá)到最終收斂于近似最優(yōu)路徑上；（2）它是一種通用型隨機(jī)優(yōu)化方法；但人工螞蟻決不是對(duì)實(shí)際螞蟻的一種簡單模擬，它融進(jìn)了人類的智能；（3）它是一種分布式的優(yōu)化方法；不僅適合目前的串行計(jì)算機(jī)，而且適合未來的并行計(jì)算機(jī)；（4）它是一種全局優(yōu)化的方法；不僅可用于求解單目標(biāo)優(yōu)化問題，而且可用于求解多目標(biāo)優(yōu)化問題；（5）它是一種啟發(fā)式算法；計(jì)算復(fù)雜性為O(NC*m*n2)，其中NC是迭代次數(shù)，m是螞蟻數(shù)目，n是目的節(jié)點(diǎn)數(shù)目。蟻群算法的特征算法優(yōu)點(diǎn)：（1）求解問題的快速性——由正反饋機(jī)制決定（2）全局優(yōu)化性——由分布式計(jì)算決定，避免蟻群在尋優(yōu)空間中過早收斂（3）有限時(shí)間內(nèi)答案的合理性——由貪婪式搜索模式?jīng)Q定，使能在搜索過程的早期就找到可以接受的較好解蟻群算法的基本思想算法流程圖：開始初始化迭代次數(shù)Nc=Nc+1螞蟻k=1螞蟻k=k+1按照狀態(tài)轉(zhuǎn)移概率公式選擇下一個(gè)元素修改禁忌表K>=螞蟻總數(shù)m？按照公式進(jìn)行信息量更新滿足結(jié)束條件？輸出程序計(jì)算結(jié)果結(jié)束YYNN蟻群算法的基本思想以TSP問題為例：1、根據(jù)具體問題設(shè)置多只螞蟻，分頭并行搜索。

2、每只螞蟻完成一次周游后，在行進(jìn)的路上釋放信息素，信息素量與解的質(zhì)量成正比。

3、螞蟻路徑的選擇根據(jù)信息素強(qiáng)度大?。ǔ跏夹畔⑺亓吭O(shè)為相等），同時(shí)考慮兩點(diǎn)之間的距離，采用隨機(jī)的局部搜索策略。這使得距離較短的邊，其上的信息素量較大，后來的螞蟻選擇該邊的概率也較大。蟻群算法的基本思想4、每只螞蟻只能走合法路線（經(jīng)過每個(gè)城市1次且僅1次），為此設(shè)置禁忌表來控制。

5、所有螞蟻都搜索完一次就是迭代一次，每迭代一次就對(duì)所有的邊做一次信息素更新，原來的螞蟻死掉，新的螞蟻進(jìn)行新一輪搜索。

6、更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加。

7、達(dá)到預(yù)定的迭代步數(shù)，或出現(xiàn)停滯現(xiàn)象（所有螞蟻都選擇同樣的路徑，解不再變化），則算法結(jié)束，以當(dāng)前最優(yōu)解作為問題的解輸出。蟻群算法的數(shù)學(xué)模型TSP算例分析旅行商問題（TSP）給定n個(gè)城市和兩個(gè)兩個(gè)城市之間的距離，要求確定一條經(jīng)過所有城市僅一次的最短路徑。第一步:初始化將m只螞蟻隨機(jī)放到n個(gè)城市，每只螞蟻的禁忌表為螞蟻當(dāng)前所在城市，各邊信息素初始化為c。禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會(huì)走重復(fù)道路，提高了效率。蟻群算法的數(shù)學(xué)模型

第二步:選擇路徑路徑在t時(shí)刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：蟻群算法的數(shù)學(xué)模型

蟻群算法的數(shù)學(xué)模型蟻群的規(guī)模和停止規(guī)則蟻群大小:

一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。終止條件:1給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；

3目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。第四步：輸出結(jié)果若未達(dá)到終止條件則轉(zhuǎn)步驟二，否則，輸出目前的最優(yōu)解。TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例TSP應(yīng)用舉例改進(jìn)的蟻群優(yōu)化算法▲最優(yōu)解保留策略螞蟻系統(tǒng)（帶精英策略的螞蟻系統(tǒng)ASelite）▲蟻群系統(tǒng)（ACS）▲最大-最小螞蟻系統(tǒng)（MMAS）▲基于優(yōu)化排序的螞蟻系統(tǒng)（ASrank）▲最優(yōu)最差螞蟻系統(tǒng)（BWAS）▲一種新的自適應(yīng)蟻群算法（AACA）▲基于混合行為的蟻群算法（HBACA）改進(jìn)的蟻群算法一般蟻群算法的框架主要有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在轉(zhuǎn)移概率公式和信息素更新公式。（一）帶精英策略的螞蟻系統(tǒng)特點(diǎn)——在信息素更新時(shí)給予當(dāng)前最優(yōu)解以額外的信息素量，使最優(yōu)解得到更好的利用。找到全局最優(yōu)解的螞蟻稱為“精英螞蟻”?！⑽浵佋谶吷显黾拥男畔⑺亓?；——精英螞蟻個(gè)數(shù)；——當(dāng)前全局最優(yōu)解路徑長度。特點(diǎn)１、狀態(tài)轉(zhuǎn)移規(guī)則——偽隨機(jī)比率規(guī)則

設(shè)為常數(shù)，為隨機(jī)數(shù)，如果，則螞蟻轉(zhuǎn)移的下一座城市是使取最大值的城市；若，仍按轉(zhuǎn)移概率確定。２、全局更新規(guī)則——只有精英螞蟻才允許釋放信息素，即只有全局最優(yōu)解所屬的邊才增加信息素。３、局部更新規(guī)則——螞蟻每次從城市轉(zhuǎn)移到城市后，邊上的信息素適當(dāng)減少。一般，取值較大。（二）蟻群系統(tǒng)

規(guī)則１和２都是為了使搜索過程更具有指導(dǎo)性，即使螞蟻的搜索主要集中在當(dāng)前找出的最好解鄰域內(nèi)。規(guī)則３則是為了使已選的邊對(duì)后來的螞蟻具有較小的影響力，以避免螞蟻收斂到同一路徑。（三）最大最小螞蟻系統(tǒng)

關(guān)于的取值，沒有確定的方法，有的書例子中取為0.01，10；有的書提出一個(gè)在最大值給定的情況下計(jì)算最小值的公式。1、每次迭代后，只對(duì)最優(yōu)解所屬路徑上的信息素更新。特點(diǎn)2、對(duì)每條邊的信息素量限制在范圍內(nèi)，目的是防止某一條路徑上的信息素量遠(yuǎn)大于其余路徑，避免過早收斂于局部最優(yōu)解。（四）基于優(yōu)化排序的螞蟻系統(tǒng)特點(diǎn)：每次迭代完成后，螞蟻所經(jīng)路徑由小到大排序，并根據(jù)路徑長度賦予不同的權(quán)重，路徑越短權(quán)重越大。信息素更新時(shí)對(duì)考慮權(quán)重的影響。特點(diǎn)：主要是修改了ACS中的全局更新公式，增加對(duì)最差螞蟻路徑信息素的更新，對(duì)最差解進(jìn)行削弱，使信息素差異進(jìn)一步增大。（五）最優(yōu)最差螞蟻系統(tǒng)（六）一種新的自適應(yīng)蟻群算法特點(diǎn)：將ACS中的狀態(tài)轉(zhuǎn)移規(guī)則改為自適應(yīng)偽隨機(jī)比率規(guī)則，動(dòng)態(tài)調(diào)整轉(zhuǎn)移概率，以避免出現(xiàn)停滯現(xiàn)象。說明：在ACS的狀態(tài)轉(zhuǎn)移公式中，是給定的常數(shù)；在AACA中，是隨平均節(jié)點(diǎn)分支數(shù)ANB而變化的變量。ANB較大，意味著下一步可選的城市較多，也變大，表示選擇信息素和距離最好的邊的可能性增大；反之減小。（七）基于混合行為的蟻群算法特點(diǎn)：按螞蟻的行為特征將螞蟻分成4類，稱為4個(gè)子蟻群，各子蟻群按各自的轉(zhuǎn)移規(guī)則行動(dòng)，搜索路徑，每迭代一次，更新當(dāng)前最優(yōu)解，按最優(yōu)路徑長度更新各條邊上的信息素，如此直至算法結(jié)束。螞蟻行為——螞蟻在前進(jìn)過程中，用以決定其下一步移動(dòng)到哪個(gè)狀態(tài)的規(guī)則集合。1、螞蟻以隨機(jī)方式選擇下一步要到達(dá)的狀態(tài)。2、螞蟻以貪婪方式選擇下一步要到達(dá)的狀態(tài)。3、螞蟻按信息素強(qiáng)度選擇下一步要到達(dá)的狀態(tài)。4、螞蟻按信息素強(qiáng)度和城市間距離選擇下一步要到達(dá)的狀態(tài)。螞蟻行為蟻群算法與遺傳、模擬退火算法的比較實(shí)驗(yàn)結(jié)果表明：1、蟻群算法所找出的解的質(zhì)量最高，遺傳算法次之，模擬退火算法最低。2、蟻群算法的收斂速度最快，遺傳算法次之，模擬退火算法最慢。蟻群算法之所以能夠快速收斂到全局最優(yōu)解，是因?yàn)樵撍惴ǖ膫€(gè)體之間不斷進(jìn)行信息交流和傳遞。單個(gè)個(gè)體容易收斂于局部最優(yōu)，多個(gè)個(gè)體通過合作可以很快地收斂于解空間的最優(yōu)解的附近。蟻群算法的應(yīng)用應(yīng)用領(lǐng)域 蟻群算法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。 現(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑。蟻群算法的應(yīng)用

蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時(shí)，ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。目前這方面的應(yīng)用研究仍在升溫，因?yàn)橥ㄐ啪W(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動(dòng)態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與ACO的算法本質(zhì)和特性非常相似。蟻群算法的應(yīng)用

基于群智能的聚類算法起源于對(duì)蟻群蟻卵的分類研究。Lumer和Faieta將Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)路徑附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)則將其放置在該位置，然后繼續(xù)移動(dòng)，重復(fù)上述數(shù)據(jù)搬運(yùn)過程。按照這樣的方法可實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的聚類。蟻群算法的應(yīng)用 ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如二次規(guī)劃問題（QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（GraphColoring）等問題。 經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實(shí)際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計(jì)劃（Job-shopScheduling）問題中的應(yīng)用實(shí)例已經(jīng)出現(xiàn)，這說明了AS在此領(lǐng)域的應(yīng)用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過實(shí)驗(yàn)中的計(jì)算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當(dāng)。利用ACO實(shí)現(xiàn)對(duì)生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應(yīng)用價(jià)值。蟻群算法的應(yīng)用

許多研究者將ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無線電頻率自動(dòng)分配、Bayesiannetworks的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。Costa和Herz還提出了一種AS在規(guī)劃問題方面的擴(kuò)展應(yīng)用——圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。應(yīng)用舉例：基于實(shí)時(shí)流媒體框架的用戶接入問題問題描述（1）類似于傳統(tǒng)結(jié)構(gòu)，視頻源依舊首先根據(jù)其到NVS的延時(shí)、帶寬以及NVS負(fù)載情況選擇接入某個(gè)NVS。（2）然后，用戶請(qǐng)求該NVS所接入的視頻源并計(jì)算得出合適的proxy接入選擇（也可能直接接入該NVS）。（3）隨后，視頻內(nèi)容由該NVS通過proxy傳輸轉(zhuǎn)發(fā)交付用戶（或直接傳輸，對(duì)應(yīng)于用戶直連NVS情形）。問題描述適應(yīng)函數(shù)應(yīng)用舉例：以減排為目標(biāo)的發(fā)電調(diào)度問題2023/4/947污染物排放除硫、除硝、除塵設(shè)備排放到大氣中二氧化硫（SO2）氮氧化物（NOx）煙塵解決方案2023/4/948……調(diào)度控制中心電廠1電廠n單機(jī)優(yōu)化從發(fā)電機(jī)組設(shè)計(jì)角度減少排污整體調(diào)度優(yōu)化設(shè)計(jì)實(shí)時(shí)發(fā)電優(yōu)化調(diào)度算法全廠優(yōu)化在滿足全廠發(fā)電任務(wù)的前提下對(duì)發(fā)電任務(wù)再優(yōu)化調(diào)度算法本文算法：蟻群算法優(yōu)化目標(biāo)：路徑構(gòu)造：將調(diào)度任務(wù)生成分配序列……調(diào)度算法選擇概率：信息素更新規(guī)則：算法偽代碼演講完畢，謝謝觀看！附錄資料：人工智能簡介?AboutTeachingPlan基本要求：人工智能是計(jì)算機(jī)科學(xué)中涉及研究、設(shè)計(jì)和應(yīng)用智能機(jī)器的一個(gè)分支，是目前迅速發(fā)展的一門新興學(xué)科，新思想新方法層出不窮。其基本思想是利用機(jī)器來模仿和執(zhí)行人腦的功能，如判斷、推理、證明、識(shí)別、感知、理解、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動(dòng)。對(duì)于培養(yǎng)學(xué)生計(jì)算機(jī)技術(shù)的應(yīng)用能力，開闊思路和視野，有重要意義。

?AboutTeachingPlan因此，要求學(xué)生掌握知識(shí)表示和問題求解的幾種常用方法，尤其是不確定性推理；掌握機(jī)器學(xué)習(xí)基本概念，了解幾種機(jī)器學(xué)習(xí)方法尤其是神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)方法；掌握專家系統(tǒng)的概念，了解專家系統(tǒng)設(shè)計(jì)方法，掌握一些智能控制方法，了解國內(nèi)外人工智能研究尤其是機(jī)器人的最新進(jìn)展；具有一定的人工智能編程設(shè)計(jì)能力（利用Lisp或Prolog語言）。?AboutTeachingPlan課程內(nèi)容以及學(xué)時(shí)分配人工智能引論(1) 人工智能概念及與計(jì)算機(jī)的關(guān)系，研究途徑、內(nèi)容和應(yīng)用領(lǐng)域概況介紹，其他最新材料。符號(hào)主義、連接主義、行為主義三大流派人工智能數(shù)學(xué)基礎(chǔ)(1)知識(shí)表示方法（2） 狀態(tài)空間法、問題歸約法，謂詞邏輯法、產(chǎn)生式表示法（動(dòng)物識(shí)別系統(tǒng)）；CLIPS語言；語義網(wǎng)絡(luò)法、框架法（這是結(jié)構(gòu)化表示）；劇本、過程、Petri網(wǎng)、面向?qū)ο蟮谋硎尽?AboutTeachingPlan 搜索技術(shù)和策略（3-4）狀態(tài)空間法，盲目搜索和啟發(fā)式搜索，A*算法；海伯倫理論、消解原理和策略；與\或形推理和搜索策略；其他求解技術(shù)。 不確定推理技術(shù)（3-4）主觀Bayes理論；可信度方法和證據(jù)理論；系統(tǒng)組織技術(shù)；非單調(diào)推理；Rete快速算法；模糊推理技術(shù)；基于語義網(wǎng)絡(luò)和框架不確定推理； 專家系統(tǒng)（2）專家系統(tǒng)概念、結(jié)構(gòu)和知識(shí)獲??；黑板模型、知識(shí)組織、管理及系統(tǒng)建造和開發(fā)工具；專家系統(tǒng)舉例及編程。

人工智能程序設(shè)計(jì)（1）人工智能語言基本機(jī)制：LISP和PROLOG。?AboutTeachingPlan 模式識(shí)別導(dǎo)論（3）模式識(shí)別專題：概率模式識(shí)別。模式識(shí)別專題：結(jié)構(gòu)模式識(shí)別 機(jī)器學(xué)習(xí)（1）：機(jī)械,解釋經(jīng)驗(yàn),事例,歸納,概念,類比學(xué)習(xí)等；統(tǒng)計(jì),結(jié)構(gòu),模糊模式識(shí)別。 專題講座（3次） 1)神經(jīng)網(wǎng)絡(luò)基本理論和應(yīng)用 (史奎凡課程：安排于人工智能理論與應(yīng)用課程內(nèi))； 2)智能體（Agent）； 3)自然語言處理； 4)智能控制和機(jī)器人科學(xué) 智能控制的結(jié)構(gòu)理論和研究領(lǐng)域，智能控制系統(tǒng)及應(yīng)用示例；機(jī)器人規(guī)劃、機(jī)器視覺和自然語言理解等。?AboutTeachingPlan 實(shí)踐：1) 搜索技術(shù)和策略2) 不確定推理技術(shù)3) 專家系統(tǒng)：動(dòng)物識(shí)別系統(tǒng)4) 模式識(shí)別技術(shù)5) 調(diào)研： 搜索技術(shù)和策略、不確定推理技術(shù)、統(tǒng)計(jì)模式識(shí)別、機(jī)器學(xué)習(xí)等四個(gè)領(lǐng)域進(jìn)展報(bào)告。?ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是當(dāng)前科學(xué)技發(fā)展的一門前沿學(xué)科，同時(shí)也是一門新思想，新觀念，新理論，新技術(shù)不斷出現(xiàn)的新興學(xué)科以及正在發(fā)展的學(xué)科。它是在計(jì)算機(jī)科學(xué)，控制論，信息論，神經(jīng)心理學(xué)，哲學(xué)，語言學(xué)等多種學(xué)科研究的基礎(chǔ)發(fā)展起來的，因此又可把它看作是一門綜合性的邊緣學(xué)科。它的出現(xiàn)及所取得的成就引起了人們的高度重視,并取得了很高的評(píng)價(jià)。有的人把它與空間技術(shù)，原子能技術(shù)一起并譽(yù)為20世紀(jì)的三大科學(xué)技術(shù)成就。?Intelligence智能是知識(shí)與智力的總合。 知識(shí)——智能行為的基礎(chǔ)； 智力——獲取知識(shí)并運(yùn)用知識(shí)求解問題的能力。智能具有以下特征：(1)具有感知能力——指人們通過視覺、聽覺、觸覺、味覺、嗅覺等感覺器官感知外部世界的能力；(2)具有記憶與思維的能力——這是人腦最重要的功能，亦是人之所以有智能的根本原因；(3)具有學(xué)習(xí)能力及自適應(yīng)能力；(4)具有行為能力。ArtificialIntelligence人工智能——計(jì)算機(jī)科學(xué)的一個(gè)分支，是智能計(jì)算機(jī)系統(tǒng)，即人類智慧在機(jī)器上的模擬，或者說是人們使機(jī)器具有類似于人的智慧（對(duì)語言能理解、能學(xué)習(xí)、能推理）。?2.BriefHistoryofAI (1) 孕育（1956年前）古希臘的Aristotle（亞里士多德）（前384-322），給出了形式邏輯的基本規(guī)律。英國的哲學(xué)家、自然科學(xué)家Bacon（培根）（1561-1626），系統(tǒng)地給出了歸納法?！爸R(shí)就是力量”德國數(shù)學(xué)家、哲學(xué)家Leibnitz（布萊尼茨）（1646-1716）。提出了關(guān)于數(shù)理邏輯的思想，把形式邏輯符號(hào)化，從而能對(duì)人的思維進(jìn)行運(yùn)算和推理。做出了能做四則運(yùn)算的手搖計(jì)算機(jī)英國數(shù)學(xué)家、邏輯學(xué)家Boole（布爾）（1815-1864）實(shí)現(xiàn)了布萊尼茨的思維符號(hào)化和數(shù)學(xué)化的思想，提出了一種嶄新的代數(shù)系統(tǒng)——布爾代數(shù)。?美籍奧地利數(shù)理邏輯學(xué)家Godel（哥德爾）（1906-1978），證明了一階謂詞的完備性定；任何包含初等數(shù)論的形式系統(tǒng)，如果它是無矛盾的，那么一定是不完備的。意義在于，人的思維形式化和機(jī)械化的某種極限，在理論上證明了有些事是做不到的。英國數(shù)學(xué)家Turing(圖靈)（1912-1954）,1936年提出了一種理想計(jì)算機(jī)的數(shù)學(xué)模型（圖靈機(jī)），1950年提出了圖靈試驗(yàn)，發(fā)表了“計(jì)算機(jī)與智能”的論文。圖靈獎(jiǎng)。美國數(shù)學(xué)家Mauchly，1946發(fā)明了電子數(shù)字計(jì)算機(jī)ENIAC美國神經(jīng)生理學(xué)家McCulloch，建立了第一個(gè)神經(jīng)網(wǎng)絡(luò)數(shù)學(xué)模型。美國數(shù)學(xué)家Shannon（香農(nóng)）,1948年發(fā)表了《通訊的數(shù)學(xué)理論》，代表了“信息論”的誕生。? (2) 形成（1956-1969）1956年提出了“ArtificialIntelligence（人工智能）”1956年夏由麻省理工學(xué)院的J.McCarthy、M.L.Minsky,IBM公司信息研究中心的N.Rochester,貝爾實(shí)驗(yàn)室的C.E.Shannon共同發(fā)起，邀請(qǐng)了Moore,Samuel,Selfridge,Solomonff,Simon,Newell等人，10位數(shù)學(xué)家、信息學(xué)家、心理學(xué)家、神經(jīng)生理學(xué)家、計(jì)算機(jī)科學(xué)家，在Dartmouth大學(xué)召開了一次關(guān)于機(jī)器智能的研討會(huì)，會(huì)上McCarthy提議正式采用了ArtificialIntelligence（人工智能）這一術(shù)語。這次會(huì)議，標(biāo)志著人工智能作為一門新興學(xué)科正式誕生了。 McCarthy（麥卡錫）——人工智能之父。這次會(huì)議之后的10年間，人工智能的研究取得了許多引人矚目的成就.機(jī)器學(xué)習(xí)方面：塞繆爾于1956年研制出了跳棋程序，該程序能從棋譜中學(xué)習(xí)，也能從下棋實(shí)踐中提高棋藝；?在定理證明方面：王浩于1958年在IBM機(jī)上證明了《數(shù)學(xué)原理》中有關(guān)命題演算的全部定理（220條），還證明了謂詞演算中150條定理85%；1965年，魯賓遜（Robinson）提出了消解原理；在模式識(shí)別方面：1959年塞爾夫里奇推出了一個(gè)模式識(shí)別程序；1965年羅伯特（Robert）編制出可辨別積木構(gòu)造的程序；在問題求解方面：1960年紐厄爾等人通過心理學(xué)試驗(yàn)總結(jié)出了人們求解問題的思維規(guī)律，編制了通用問題求解程序GPS,可以用來求解11種不同類型的問題；在專家系統(tǒng)方面：斯坦福大學(xué)的費(fèi)根鮑姆（E.A.Feigenbaum）自1965年開始進(jìn)行專家系統(tǒng)DENDRAL（化學(xué)分析專家系統(tǒng)），1968年完成并投入使用；在人工智能語言方面：1960年McCarthy等人建立了人工智能程序設(shè)計(jì)語言Lisp，該語言至今仍是建造智能系統(tǒng)的重要工具；1969年成立了國際人工智能聯(lián)合會(huì)議（InternationalJointConferencesOnArtificialIntelligence）? (3) 發(fā)展（1970年以后）70年代，開始從理論走向?qū)嵺`，解決一些實(shí)際問題。同時(shí)很快就發(fā)現(xiàn)問題：歸結(jié)法費(fèi)時(shí)、下棋贏不了全國冠軍、機(jī)器翻譯一團(tuán)糟。以Feigenbaum為首的一批年輕科學(xué)家改變了戰(zhàn)略思想，1977年提出知識(shí)工程的概念，以知識(shí)為基礎(chǔ)的專家咨詢系統(tǒng)開始廣泛的應(yīng)用。著名專家系統(tǒng)的有：DENDRAL化學(xué)分析專家系統(tǒng)（斯坦福大學(xué)1968）MACSYMA符號(hào)數(shù)學(xué)專家系統(tǒng)（麻省理工1971）MYCIN診斷和治療細(xì)菌感染性血液病的專家咨詢系統(tǒng)（斯坦福大學(xué)1973）CASNET(CausalASsciationalNetwork)診斷和治療青光眼的專家咨詢系統(tǒng)（拉特格爾斯（Rutgers）大學(xué)70年代中）CADUCEUS(原名INTERNIST)醫(yī)療咨詢系統(tǒng)（匹茲堡大學(xué)）；HEARSAYI和II語音理解系統(tǒng)（卡內(nèi)基-梅隆大學(xué)）PROSPECTOR地質(zhì)勘探專家系統(tǒng)（斯坦福大學(xué)1976）XCON計(jì)算機(jī)配置專家系統(tǒng)（卡內(nèi)基-梅隆大學(xué)1978）??80年代，人工智能發(fā)展達(dá)到階段性的頂峰。?87,89年世界大會(huì)有６－７千人參加。硬件公司有上千個(gè)。并進(jìn)行Lisp硬件、Lisp機(jī)的研究。?在專家系統(tǒng)及其工具越來越商品化的過程中,國際軟件市場(chǎng)上形成了一門旨在生產(chǎn)和加工知識(shí)的新產(chǎn)業(yè)——知識(shí)產(chǎn)業(yè)。應(yīng)該說，知識(shí)工程和專家系統(tǒng)是近十余年來人工智能研究中最有成就的分支之一。?同年代，1986年Rumlhart領(lǐng)導(dǎo)的并行分布處理研究小組提出了神經(jīng)元網(wǎng)絡(luò)的反向傳播學(xué)習(xí)算法，解決了神經(jīng)網(wǎng)絡(luò)的根本問題之一。從此，神經(jīng)網(wǎng)絡(luò)的研究進(jìn)入新的高潮。?90年代，計(jì)算機(jī)發(fā)展趨勢(shì)為小型化、并行化、網(wǎng)絡(luò)化、智能化。?人工智能技術(shù)逐漸與數(shù)據(jù)庫、多媒體等主流技術(shù)相結(jié)合，并融合在主流技術(shù)之中，旨在使計(jì)算機(jī)更聰明、更有效、與人更接近。?日本政府于1992年結(jié)束了為期十年的稱為“知識(shí)信息處理體統(tǒng)”的第五代計(jì)算機(jī)系統(tǒng)研究開發(fā)計(jì)劃。并開始了為期十年的實(shí)況計(jì)算（RealWordComputing）計(jì)劃。?3.ResearchObjectsandMainContents

(1)人工智能的研究目標(biāo)

人工智能的長期研究目標(biāo)：構(gòu)造智能計(jì)算機(jī)。

人工智能的近期研究目標(biāo)：使現(xiàn)有的電子計(jì)算機(jī)更聰明，更有用，使它不僅能做一般的數(shù)值計(jì)算及非數(shù)值信息的數(shù)據(jù)處理，而且能運(yùn)用知識(shí)處理問題，能模擬人類的部分智能行為。?(2)人工智能研究的基本內(nèi)容

1.機(jī)器感知以機(jī)器視覺與機(jī)器聽覺為主。機(jī)器感知是機(jī)器獲取外部信息的基本途徑，是使機(jī)器具有智能不可或缺的組成部分，對(duì)此人工智能中已形成兩個(gè)專門的研究領(lǐng)域——

模式識(shí)別和自然語言理解。2.機(jī)器思維指通過感知的外部信息及機(jī)器內(nèi)部的各種工作信息進(jìn)行有目的的處理。主要開展以下幾方面的研究：(1)知識(shí)表示(2)知識(shí)的組織，累計(jì)，管理技術(shù)(3)知識(shí)的推理(4)各種啟發(fā)式搜索及控制策略(5)神經(jīng)網(wǎng)絡(luò)，人腦的結(jié)構(gòu)及其工作原理?3.機(jī)器學(xué)習(xí)

使計(jì)算能自動(dòng)獲取知識(shí)，能直接向書本學(xué)習(xí)，能通過與人談話學(xué)習(xí)，能通過對(duì)環(huán)境的觀察學(xué)習(xí)，并能在實(shí)踐中自我完善。4.機(jī)器行為機(jī)器行為主要指計(jì)算機(jī)的表達(dá)能力，即“說”、“寫”、“畫”等，對(duì)智能機(jī)器人，還應(yīng)該有人的四肢功能，即能走路，能取物，能操作等。5.智能系統(tǒng)及智能計(jì)算機(jī)的構(gòu)造技術(shù)?4.ResearchObjectsandMainContents人工智能面世以來，其研究途徑存在兩種不同的觀點(diǎn)：以符號(hào)處理為核心的方法——主張通過運(yùn)用計(jì)算機(jī)科學(xué)的方法進(jìn)行研究，實(shí)現(xiàn)人工智能在計(jì)算機(jī)的模擬。以網(wǎng)絡(luò)連接為主的連接機(jī)制方法——主張用生物學(xué)的方法進(jìn)行研究，搞清楚人類智能的本質(zhì)。(1)以符號(hào)處理為核心的方法該方法起源于紐厄爾等人的通用問題求解系統(tǒng)（GPS），用于模擬人類求解問題的心理過程，逐漸形成為物理符號(hào)系統(tǒng)，這種方法認(rèn)為： 人類研究的目標(biāo)是實(shí)現(xiàn)機(jī)器智能，而計(jì)算機(jī)自身具有符號(hào)處理能力，這種能力本身就蘊(yùn)含著演繹推理的內(nèi)涵，因而可通過運(yùn)行相應(yīng)的程序來體現(xiàn)某種基于邏輯思維的智能行為，達(dá)到模擬人類智能活動(dòng)的效果。目前人工智能的大部分研究成果都是基于這種方法實(shí)現(xiàn)的。?

該方法的主要特征是：

?立足于邏輯運(yùn)算和符號(hào)操作，適合于模擬人的邏輯思維過程，解決需要進(jìn)行邏輯推理的復(fù)雜問題；

?知識(shí)可用顯式的符號(hào)表示；

?便于模塊化；?能與傳統(tǒng)的符號(hào)數(shù)據(jù)庫鏈接；?可對(duì)推理結(jié)論做出解釋，便于對(duì)各種可能性進(jìn)行選擇。

但該方法不適合于形象思維；而且在用符號(hào)表示概念時(shí)其有效性在很大程度上取決于符號(hào)表示的正確性，且對(duì)帶噪聲的信息及不完整的信息難以處理。(2)以網(wǎng)絡(luò)連接為主的連接機(jī)制方法該方法是在人腦神經(jīng)元及其相互連接而成網(wǎng)絡(luò)的啟示下，試圖通過多人工神經(jīng)元間的并行協(xié)同作用來實(shí)現(xiàn)對(duì)人類智能的模擬。該方法認(rèn)為：大腦是人類一切智能活動(dòng)的基礎(chǔ)，因而從大腦神經(jīng)元及其連接機(jī)制著手進(jìn)行研究，搞清楚大腦的結(jié)構(gòu)及它進(jìn)行信息處理的過程及機(jī)理，可望揭示人類智能的奧秘，從而真正實(shí)現(xiàn)人類智慧在機(jī)器上的模擬。?該方法的主要特征：?通過神經(jīng)元之間的并行協(xié)同作用實(shí)現(xiàn)信息處理，處理過程具有并行性、動(dòng)態(tài)性、全局性；?通過神經(jīng)元間分布式的物理聯(lián)系存儲(chǔ)知識(shí)和信息，因而可以實(shí)現(xiàn)聯(lián)想功能，對(duì)于帶有噪聲、缺損、變形的信息能進(jìn)行有效地處理。近期的一些研究表明，該方法在模式識(shí)別、圖像信息壓縮等方面取得了一些研究成果；?通過神經(jīng)元間連接強(qiáng)度的動(dòng)態(tài)調(diào)整來實(shí)現(xiàn)對(duì)人類學(xué)習(xí)、分類等的模擬；?適合于模擬人類的形象思維過程；?求解問題時(shí)，可以比較快地球的一個(gè)近似解。該方法不適合于模擬人的邏輯思維過程，而且就目前神經(jīng)網(wǎng)絡(luò)的研究現(xiàn)狀來看，由固定的體系