袁 杭, 李林林, 孫良旭, 王 剛, 吳登權(quán), 劉夢(mèng)迪

(遼寧科技大學(xué) 軟件學(xué)院, 遼寧 鞍山 114051)

人工智能(artificial intelligence,AI) 是研究人類智能模擬和擴(kuò)展的理論、方法、技術(shù)及應(yīng)用的科學(xué)。國(guó)內(nèi)召開(kāi)的人工智能教育論壇,進(jìn)一步促進(jìn)了“人工智能+教育”研究的深入和應(yīng)用推廣,同時(shí)也為人工智能向“人工智能+教育”發(fā)展提供了技術(shù)基礎(chǔ)[1]。人工智能輔助教學(xué)系統(tǒng)是現(xiàn)代科研的重要成果,是新技術(shù)的體現(xiàn),人工智能技術(shù)應(yīng)用于教育教學(xué),有利于促進(jìn)學(xué)生和教師的發(fā)展,促進(jìn)教育領(lǐng)域方面的改革[2-3]。教育人工智能則是人工智能與學(xué)習(xí)科學(xué)相結(jié)合而形成的一個(gè)新領(lǐng)域[4]。目前多數(shù)院校的計(jì)算機(jī)編程課程教學(xué)還存在著一些問(wèn)題, 無(wú)法滿足學(xué)生的發(fā)展需求[5-7]。國(guó)內(nèi)的學(xué)者也提出了新的實(shí)驗(yàn)教學(xué)方法,例如以建構(gòu)主義學(xué)習(xí)理論為依據(jù)、參照任務(wù)驅(qū)動(dòng)和成就驅(qū)動(dòng)的方法、結(jié)合教學(xué)過(guò)程中的實(shí)踐經(jīng)驗(yàn)提出的一種新的分層實(shí)驗(yàn)教學(xué)方法[8]。雖然在現(xiàn)有的計(jì)算機(jī)編程類綜合性實(shí)驗(yàn)中能夠體現(xiàn)問(wèn)題導(dǎo)向、任務(wù)驅(qū)動(dòng)等好的實(shí)驗(yàn)教學(xué)方法,但是問(wèn)題或者任務(wù)本身多是數(shù)值計(jì)算或者信息管理問(wèn)題,缺少新穎性和娛樂(lè)性,算法難度偏低、業(yè)務(wù)邏輯簡(jiǎn)單、技術(shù)實(shí)現(xiàn)容易,無(wú)法達(dá)到實(shí)踐能力訓(xùn)練的工作量和難度要求,而且相關(guān)的技術(shù)難點(diǎn)可能超過(guò)課程現(xiàn)有知識(shí),需要開(kāi)源項(xiàng)目支持。隨著開(kāi)源項(xiàng)目的大力發(fā)展,現(xiàn)在很多項(xiàng)目開(kāi)發(fā)都需要開(kāi)源項(xiàng)目支持,有必要在實(shí)驗(yàn)中訓(xùn)練學(xué)生如何使用開(kāi)源項(xiàng)目解決實(shí)際問(wèn)題。

人工生命計(jì)算是一種以人工生命為形式、研究人工生命的信息表達(dá)和處理機(jī)制、提取相應(yīng)的計(jì)算模型、嵌入相應(yīng)的計(jì)算方法模擬自然界生物進(jìn)化過(guò)程與信息處理機(jī)制來(lái)求解與優(yōu)化問(wèn)題的智能計(jì)算方法[9]。本文選擇人工智能研究領(lǐng)域新穎有趣的人工生命模擬作為研究問(wèn)題,設(shè)計(jì)和實(shí)現(xiàn)簡(jiǎn)單人工魚(yú)模擬綜合性實(shí)驗(yàn),具體描述算法理論基礎(chǔ)、類庫(kù)設(shè)計(jì)和算法實(shí)現(xiàn),為解決計(jì)算機(jī)編程類課程綜合性實(shí)驗(yàn)設(shè)計(jì)問(wèn)題提供一個(gè)新穎的案例參考。

1 人工生命理論基礎(chǔ)

1.1 人工生命概念和特征

人工生命(artificial life，AL) 首先由計(jì)算機(jī)科學(xué)家Christopher Langton在1987年召開(kāi)的“生成以及模擬生命系統(tǒng)的國(guó)際會(huì)議”上提出。人工生命的概念屬于計(jì)算機(jī)科學(xué)領(lǐng)域的虛擬生命系統(tǒng),涉及計(jì)算機(jī)軟件工程與人工智能技術(shù)。人工生命是借助計(jì)算機(jī)實(shí)現(xiàn)一個(gè)具有生物系統(tǒng)特征的過(guò)程或系統(tǒng),特征主要包括：

(1) 繁殖和死亡。

(2) 進(jìn)化和選擇。

(3) 信息交換和處理。

(4) 決策。

1.2 遺傳算法

遺傳算法(genetic algorithm, GA)是受達(dá)爾文進(jìn)化論的啟發(fā),借鑒生物進(jìn)化過(guò)程而提出的一種啟發(fā)式搜索算法。將要解決的問(wèn)題模擬成一個(gè)生物進(jìn)化的過(guò)程,通過(guò)復(fù)制、交叉、突變等操作產(chǎn)生下一代的解,并逐步淘汰適應(yīng)度低的解,保留適應(yīng)度高的解。這樣進(jìn)化N代后就很有可能會(huì)進(jìn)化出適應(yīng)度很高的個(gè)體。

遺傳算法有3個(gè)最基本的操作：選擇、交叉、變異。

(1) 選擇。選擇一些染色體來(lái)產(chǎn)生下一代。

(2) 交叉。2條染色體交換部分基因來(lái)構(gòu)造下一代的2條新的染色體。

(3) 變異。在繁殖過(guò)程,新產(chǎn)生的染色體中的基因會(huì)以一定的概率出錯(cuò)。

1.3 BP神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)

BP(back propagation)神經(jīng)網(wǎng)絡(luò)是1986年由Rumelhart和McClelland為首的科學(xué)家提出的概念[10],是一種按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò),是目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)。

強(qiáng)化學(xué)習(xí)(reinforcement learning, RL)是近年來(lái)機(jī)器學(xué)習(xí)和智能控制領(lǐng)域的主要方法之一,增強(qiáng)學(xué)習(xí)關(guān)注的是智能體如何在環(huán)境中采取一系列行為,從而獲得最大的累積回報(bào)[11]。通過(guò)增強(qiáng)學(xué)習(xí),一個(gè)智能體知道在什么狀態(tài)下應(yīng)該采取什么行為。

2 人工魚(yú)綜合性實(shí)驗(yàn)設(shè)計(jì)

人工魚(yú)具有自己的神經(jīng)網(wǎng)絡(luò)、顏色、大小、移動(dòng)速度和食物感知器官,每一條人工魚(yú)的染色體包括體質(zhì)基因和智慧基因。體質(zhì)基因描述人工魚(yú)的大小、移動(dòng)速度和顏色特征,采用列表方式描述；智慧基因描述人工魚(yú)的智慧特征,采用神經(jīng)網(wǎng)絡(luò)形式表示。移動(dòng)速度大的人工魚(yú)移動(dòng)更快,尺寸大的人工魚(yú)需要更多食物,顏色對(duì)人工魚(yú)沒(méi)有影響。通過(guò)食物感知器官獲取食物與人工魚(yú)之間的角度和距離信息,將這些信息作為神經(jīng)網(wǎng)絡(luò)輸入。計(jì)算神經(jīng)網(wǎng)絡(luò)輸出、控制人工魚(yú)的朝向和速度、找到食物的位置,循環(huán)反復(fù),實(shí)現(xiàn)人工魚(yú)在模擬環(huán)境中的生存。通過(guò)遺傳變異、強(qiáng)化學(xué)習(xí)和適當(dāng)選擇,使人工魚(yú)學(xué)習(xí)如何找到食物。通過(guò)2條人工魚(yú)的染色體之間配對(duì),產(chǎn)生變異的后代。

2.1 人工魚(yú)相關(guān)類定義

人工魚(yú)相關(guān)類包括Fish類、FishChromozomes類和FishLearn類。類的字段和方法定義如圖1所示。

圖1 人工魚(yú)相關(guān)類定義

Fish類定義了人工魚(yú)的基本信息、位置信息、智慧能力和生存行為?；鞠挲g、大小、生命力、移動(dòng)速度、染色體、吃食量；位置信息包括坐標(biāo)位置、頭和身體朝向；智慧能力包括神經(jīng)網(wǎng)絡(luò)、食物感知、自我學(xué)習(xí)；生存行為包括搜索食物、吃食、前進(jìn)、邊界檢測(cè)。

FishChromozomes類在基因類和染色體類定義基礎(chǔ)上,定義了人工魚(yú)的體質(zhì)染色體、智慧染色體和繁殖交配行為。

FishLearn類定義了人工魚(yú)的覓食學(xué)習(xí)。

2.2 食物相關(guān)類定義

食物相關(guān)類包括Food類、FoodSensor類和FoodGnerator類,類的字段和方法定義如圖2所示。

圖2 食物相關(guān)類定義

Food類定義食物的基本信息,包括坐標(biāo)位置和提供的生命力。

FoodSensor類根據(jù)人工魚(yú)和食物之間角度和距離信息,定義了食物感知計(jì)算的功能。

FoodGenerator類定義了隨機(jī)在不同位置生產(chǎn)食物的功能。

2.3 人工魚(yú)生存算法設(shè)計(jì)

2.3.1 人工魚(yú)覓食強(qiáng)化學(xué)習(xí)

設(shè)計(jì)人工魚(yú)具有短期記憶,通過(guò)隊(duì)列可以保存最近的n個(gè)行為。當(dāng)成功搜索到食物后,使用這n個(gè)行為對(duì)其神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練,以使其更好地按照上述n個(gè)行為進(jìn)行食物搜索,這就是人工魚(yú)的覓食強(qiáng)化學(xué)習(xí)過(guò)程。在仿真過(guò)程中,由于覓食強(qiáng)化學(xué)習(xí),每條人工魚(yú)的神經(jīng)網(wǎng)絡(luò)將發(fā)生連續(xù)不斷的變化,描述人工魚(yú)最新的覓食行為。

2.3.2 人工魚(yú)繁殖遺傳處理

人工魚(yú)的基因存在概率突變,當(dāng)2條人工魚(yú)進(jìn)行繁殖時(shí),他們的基因會(huì)進(jìn)行合并和組合,產(chǎn)生一個(gè)具有不同基因特征的新個(gè)體。在仿真生存環(huán)境中,如果人工魚(yú)吃到食物,生命力會(huì)增加,說(shuō)明其具有更好的覓食能力,生存環(huán)境適應(yīng)度更好；如果人工魚(yú)沒(méi)有吃到食物,生命力會(huì)持續(xù)下降,說(shuō)明其具有較差的覓食能力,生存環(huán)境的適應(yīng)度較差。通過(guò)定義每代人工魚(yú)的繁殖閾值條件,例如定時(shí)器,選擇覓食能力強(qiáng)、生存環(huán)境適應(yīng)度好的人工魚(yú)進(jìn)行繁殖交配,產(chǎn)生新的個(gè)體,實(shí)現(xiàn)人工魚(yú)進(jìn)化。由于每一條人工魚(yú)的神經(jīng)網(wǎng)絡(luò)都是不同的,所以它們的后代將具有唯一的神經(jīng)網(wǎng)絡(luò),具有不同的覓食行為。

對(duì)于使用普通列表描述的體質(zhì)基因,根據(jù)列表長(zhǎng)度隨機(jī)選擇一個(gè)交叉點(diǎn),按照交叉點(diǎn),將2個(gè)基因列表在交叉點(diǎn)兩個(gè)相反方向上分別進(jìn)行拷貝,如圖3所示。

圖3 體質(zhì)基因遺傳處理

人工魚(yú)繁殖交配時(shí),對(duì)使用神經(jīng)網(wǎng)絡(luò)描述的智慧基因,選擇一個(gè)交叉點(diǎn)將2條人工魚(yú)的神經(jīng)網(wǎng)絡(luò)進(jìn)行遺傳處理,如圖4所示。

圖4 智慧基因遺傳處理

為了能夠最大限度遺傳有利生存的基因到下一代,一般選擇從多條好的人工魚(yú)中選擇2條進(jìn)行繁殖交配,產(chǎn)生后代。

2.3.3 人工魚(yú)生存模擬

在人工魚(yú)生存模擬中,一開(kāi)始固定數(shù)量的食物隨機(jī)在不同位置生成,一旦食物被人工魚(yú)吃掉,都會(huì)自動(dòng)重新在另一個(gè)隨機(jī)位置生成。人工魚(yú)彼此之間默認(rèn)是不可見(jiàn)的,但是在任何時(shí)候都可以感知所有的食物信息。每條人工魚(yú)獲取的食物感知信息經(jīng)過(guò)計(jì)算,作為其神經(jīng)網(wǎng)絡(luò)輸入,獲取神經(jīng)網(wǎng)絡(luò)輸出,計(jì)算魚(yú)頭的朝向和前進(jìn)速度,執(zhí)行覓食行為。每條人工魚(yú)根據(jù)覓食情況,處于健康生長(zhǎng)或者逐漸死亡的狀態(tài)。當(dāng)每代進(jìn)化閾值條件滿足時(shí),選擇好的人工魚(yú)進(jìn)行繁殖交配,產(chǎn)生下一代人工魚(yú)群,完成下一代生存模擬。

3 人工魚(yú)綜合性實(shí)驗(yàn)實(shí)現(xiàn)

3.1 實(shí)現(xiàn)技術(shù)

人工魚(yú)綜合性實(shí)驗(yàn)可以在Visual Studio 2015開(kāi)發(fā)環(huán)境中使用C#編程實(shí)現(xiàn),其中人工魚(yú)生存環(huán)境的圖形化動(dòng)態(tài)界面可以使用WPF的Canvas類編程繪制完成,使用Background Worker類實(shí)現(xiàn)人工魚(yú)的多線程生存模擬,通過(guò)人工魚(yú)、食物、邊界之間坐標(biāo)關(guān)系的幾何計(jì)算,獲取人工魚(yú)的食物感知信息,包括距離和角度,作為人工魚(yú)神經(jīng)網(wǎng)絡(luò)輸入。

由于學(xué)生普遍缺乏神經(jīng)網(wǎng)絡(luò)和增強(qiáng)學(xué)習(xí)相關(guān)算法的理論知識(shí),直接通過(guò)編寫(xiě)代碼實(shí)現(xiàn)上述算法非常困難。為了解決該問(wèn)題,利用開(kāi)源項(xiàng)目Neural Networks,該項(xiàng)目提供了基于.NET Framework的并行神經(jīng)網(wǎng)絡(luò)庫(kù)實(shí)現(xiàn),其中Backpropagation Network類實(shí)現(xiàn)BP神經(jīng)網(wǎng)絡(luò),可以用于實(shí)現(xiàn)人工魚(yú)的強(qiáng)化學(xué)習(xí)。

因此,人工魚(yú)智慧基因使用開(kāi)源項(xiàng)目Neural Networks的Backpropagation Network類來(lái)實(shí)現(xiàn)BP神經(jīng)網(wǎng)絡(luò),獲取食物感知信息作為輸入,完成人工魚(yú)覓食行為決策,最近n個(gè)行為作為輸入輸出,完成人工魚(yú)覓食行為學(xué)習(xí)。

3.2 實(shí)現(xiàn)效果

人工魚(yú)綜合性實(shí)驗(yàn)的實(shí)現(xiàn)程序運(yùn)行效果如圖5所示。

圖5 人工魚(yú)生存模擬

一開(kāi)始人工魚(yú)幾乎不知道如何找到食物,有些魚(yú)在不停地打轉(zhuǎn)。逐漸地,經(jīng)過(guò)多代進(jìn)化,人工魚(yú)逐漸獲得了吃到更多食物的行為。種群中適應(yīng)度可以描述為人工魚(yú)消耗的總食物量,隨著進(jìn)化代數(shù)持續(xù)增加,通過(guò)優(yōu)勢(shì)個(gè)體的基因遺傳,成功地產(chǎn)生了覓食能力更強(qiáng)的個(gè)體,能夠找到更多的食物,程序模擬的效果與現(xiàn)實(shí)中的魚(yú)群生存過(guò)程一致。

4 結(jié)語(yǔ)

本文針對(duì)計(jì)算機(jī)編程類課程缺乏新穎有趣的綜合性實(shí)驗(yàn)問(wèn)題,選擇人工智能的人工生命作為問(wèn)題背景,以人工魚(yú)生存模擬為例,詳細(xì)描述了該綜合性實(shí)驗(yàn)的理論基礎(chǔ)、實(shí)驗(yàn)設(shè)計(jì)和編程實(shí)現(xiàn)過(guò)程。該綜合性實(shí)驗(yàn)完全可以滿足計(jì)算機(jī)編程類課程對(duì)學(xué)生基礎(chǔ)語(yǔ)法、數(shù)據(jù)結(jié)構(gòu)和算法的訓(xùn)練,具有一定的技術(shù)難度,又不失趣味性,同時(shí)讓學(xué)生了解了利用開(kāi)源項(xiàng)目解決實(shí)際問(wèn)題的方式,為解決目前計(jì)算機(jī)編程類課程綜合性實(shí)驗(yàn)中存在的問(wèn)題提供了一個(gè)新穎的解決方案。