人工智能專業算法設計與分析課程教學內容探討

摘" 要： 針對人工智能專業算法設計與分析課程中經典算法與前沿人工智能算法缺乏聯系而影響學生學習積極性的問題，探討了將前沿人工智能算法技術中與經典算法思想相同的算法納入到課程中。具體而言，選取了具有“剪枝”思想、“局部最優”思想和“遞推”思想的安全強化學習算法及其求解懸崖行走問題作為課程補充材料。調查問卷結果顯示：該教學設計有助于提高學生對算法設計與分析課程重要性的認同感和學習積極性。

關鍵詞： 人工智能專業； 算法設計與分析課程； 前沿人工智能算法； 學習積極性

中圖分類號：G642.0" " " " " 文獻標識碼：A" " "文章編號：1006-8228（2023）12-217-04

Teaching content exploration of algorithm design and analysis course for AI major

Yu Liang

（College of Automation and College of Artificial Intelligence， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu 210003， China）

Abstract： In existing algorithm design and analysis courses， just some classical algorithms are involved， which affects the learning initiative for the students majored in AI since there is lack of connection between classic algorithms and cutting-edge AI algorithms. Thus， the teaching design of incorporating the algorithms in the cutting-edge AI algorithmic technology with the same ideas as the classical algorithms into the course is explored. Specifically， the safe reinforcement learning algorithm with the ideas of \"pruning\"， \"local optimization\" and \"recursion\"， and its application to the cliff walking problem are selected as supplementary materials for the course. The survey questionnaire results show that this teaching design can help students to improve their learning initiative.

Key words： artificial intelligence （AI） major; algorithm design and analysis course; cutting-edge AI algorithms; learning initiative

0 引言

“算法設計與分析”課程是高等學校信息技術相關專業（如：計算機科學與技術、通信工程、電子信息工程、物聯網工程、人工智能、智能科學與技術）的核心基礎課程，對于培養學生利用計算機分析和解決實際問題的能力具有非常重要的作用。然而，由于該課程具有理論性和實踐性強、抽象性高、與實際問題聯系不足等特點，給課程的有效教學帶來了很大的挑戰。為此，許多教師做了有益探索[1-5]。例如，彭雷等針對課程教學方式單一、學生能力培養不足、學生學習效果不佳等現狀，提出了該課程三維立體教學模式方法[1]。余亮等針對算法分析與設計課程中不同年級學生專業基礎差別大和重點/難點掌握程度低的問題，提出了基于強化學習思想的重點/難點教學方法[2]。黃隆華等針對算法分析與設計課程難以培養學生學習興趣的現狀，通過對“百錢買百雞問題”進行教學設計，有效提高了學生的學習興趣[3]。何高奇等針對學生不能靈活運用算法解決實際問題的現狀，提出了聚焦計算思維的算法分析與設計課程教學改革方法[4]。盡管上述研究取得了一定的教學效果，但大都針對計算機專業學生，并不一定適用于其他專業。

針對歷年學生對“算法設計與分析”課程的認識偏差，即該課程所講授的經典算法（如分治法、貪心法、動態規劃法、分枝限界法和回溯法）都是很古老的算法，與其所學專業聯系不足、課程用處不大、重要性認同感不強。本文針對人工智能專業，將強化學習這一前沿人工智能算法技術中與經典算法思想相同的代表性算法及其應用納入到課程介紹的講授中，使得學生明白前沿人工智能算法的核心思想與經典算法的核心思想存在密切關聯，學習好經典算法是未來學好前沿人工智能算法（如研究生階段開設的深度強化學習技術等課程）的基石，進而降低學生對經典算法的抵觸和排斥感，提高學生課堂投入和參與度，實現教學質量的提升。具體而言，本文將與算法分析與設計課程中四種經典算法（即貪心法、動態規劃法、分枝限界法和回溯法）具有相同思想的安全強化學習算法納入到算法設計與分析的課程介紹講解中，并結合及應用進行具體闡述。教學效果調查問卷顯示，98.5%的學生認為算法設計與分析課程中經典算法的學習重要性大，可為后續前沿人工智能算法的學習（如深度強化學習）打下堅實鋪墊。

1 安全強化學習基本思想

作為人工智能的重要分支，機器學習受到了廣泛關注。作為機器學習的三大分支之一，強化學習擅長求解不確定性環境下的多階段決策問題，目前已廣泛應用于圍棋、機器人控制、推薦系統、無人駕駛等。在2017年，強化學習被《麻省理工科技評論》評為全球十大突破性技術，它也是AlphaGo系統（曾打敗人類世界圍棋冠軍）的核心技術，以強化學習為主體并結合深度學習強大感知表征能力的深度強化學習已成為目前最為前沿的通用人工智能算法技術。在強化學習中，整個學習過程可以用馬爾可夫決策過程進行描述（如圖1所示）。其中：兩大主體為智能體和環境。智能體觀測環境狀態，并根據策略選擇動作。然后，將動作作用于環境，驅動環境轉移到新的狀態。環境返回新狀態和獎勵給智能體。上述過程重復進行，智能體的目標是不斷更新自身策略（即從狀態到動作的概率分布映射）從而實現其獲得的累計折扣獎勵期望值最大化。在學習最優策略過程中，智能體采用探索和利用的方式與環境進行交互，這可能導致選取的動作超出安全域。在某些對可靠性要求極高的領域（如無人駕駛、智能電網），智能體隨機選取的動作可能帶來嚴重的負面影響，如人員傷亡、重大經濟損失等。為使動作具有可控性，安全強化學習被提出。其核心思想是根據人類知識設計動作的安全域，通過安全域引導智能體學習安全動作。安全強化學習可用受限的馬爾可夫決策過程來描述。具體而言，為了使得動作盡可能地滿足安全域，需要對違背安全域的動作進行限制，進而逐步減小其選擇不安全動作的概率。

2 安全強化學習求解懸崖行走問題

本節首先描述了懸崖行走問題，然后給出安全強化學習中的代表性算法——安全Q學習算法偽代碼（即算法描述的“第一語言”）。緊接著，對安全Q學習這一先進人工智能算法與算法設計與分析課程中經典算法之間的密切聯系進行剖析，使學生意識到經典算法的學習重要性，提高學習積極性。

懸崖行走問題如圖2所示，其中：智能體從起點（左下角）出發，試圖學習到最優策略，進而找到一條通往終點的最短路徑（如圖2中箭頭所示）。在每個格子，智能體有4個動作可以選取，即“向上”、“向下”、“向左”和“向右”，每走一步懲罰成本為1，如果走入懸崖區域，則懲罰成本為100。當智能體走進懸崖區域（陰影部分所示）或走到終點G后，一輪學習過程終止。通過多輪學習，智能體學習獲得最優值函數，進而通過最優值函數間接獲得最優策略找到從起點到終點懲罰成本最短的路徑。下面介紹如何利用安全強化學習技術來幫助智能體學到上述最優策略。

安全Q學習算法的偽代碼和測試結果分別如表1和圖2所示。其中：由圖2的訓練獎勵曲線（50組實驗的平均獎勵）可知，安全Q學習算法相比傳統的Q學習算法[6]具有更快的收斂速度和更穩定的收斂性能。例如：安全Q學習算法僅需100輪學習即可穩定且收斂獎勵水平更高，最高獎勵為-13，其相反數等于最優路徑的懲罰權重之和，最優路徑箭頭如圖2所示。

在表1中，可以根據懸崖區域的三個坐標點[0，0，6，1，（11，0）]構建一個安全區域邊界：

[cx=cx1，x2=-x21+11x1-30x2]，[C=0]

其中：[0≤x1≤11，0≤x2≤3]。當[cxlt;0]時在曲線上方均為安全區域。否則，曲線下方為不安全區域（如圖2中曲線）。通過估計下一個狀態下的安全值[c（x'）]，并將其估計值[cx+du]與[C]進行比較后得到值函數的安全懲罰項[λc]（如第8行）。為了降低隨機探索導致的懸崖掉入概率，每次選取動作根據獎勵最大和最安全原則，即選擇值函數和安全懲罰項加權和最大值所對應的動作[u]。從表1可以發現，與算法設計與分析課程中四種經典算法相同的思想，即與分枝限界法和回溯法相同的“剪枝”思想、與動態規劃法貝爾曼最優方程相同的“遞歸”思想、與貪心法相同的“局部極大值”思想。具體而言，第5～8行體現了“剪枝”思想和“局部極大值”思想，通過將違背安全懲罰與值函數疊加并選取最大值對應的動作有助于“剪去”不安全的動作。正如圖3所示，100輪學習后安全Q學習算法不會采取“不安全”的動作（即導致跌入懸崖的動作），而Q學習算法下的智能體動作仍然有可能跌入懸崖，因而獎勵曲線不斷抖動。與動態規劃法貝爾曼最優方程相同的“遞歸”思想體現在第10行中，當[Qx，u*]不再更新時，時間差分誤差[r+γmaxuQx'，u-Qx，u*]接近0，則有[Qx，u*≈r+γmaxuQx'，u]，該式為動態規劃法求解狀態動作值函數的貝爾曼最優方程（Q（x，u）=[E][[r+γmaxu'Q（x'，u'）]]）的近似（即用單個樣本代替均值），其中：[E]表示針對[r]和[x']的期望運算，[u']為下一個狀態[x']下采取的動作。

結合上述素材，對人工智能專業算法設計與分析課程教學內容進行了改革。具體而言，在第一次課上進行課程介紹時，圍繞課程即將講授的幾大經典算法解釋其核心思想，并將其核心思想與前沿的人工智能算法進行聯系，使得學生明白算法設計與分析課程是未來前沿人工智能算法的“基石”，進而提高課程認同感和學習積極性。針對人工智能專業學生的調查問卷結果顯示，98.5%的學生經過課程介紹的講解后認為算法設計與分析課程對本專業非常重要，這有助于后續開展經典算法的教學。

3 結束語

本文針對現有“算法設計與分析”課程中主要講解經典算法會影響人工智能專業學生學習積極性的問題，提出了將與經典算法核心思想有密切聯系的先進人工智能算法——安全Q學習算法及其應用納入算法課程介紹中，幫助學生意識到算法設計與分析課程中經典算法的重要性并提高學習經典算法的積極性，為后續學習前沿人工智能算法做好堅實的鋪墊。

未來將在課程中引入更多具有趣味性和啟發性，并與經典算法“一脈相承”的前沿人工智能算法，不斷開闊學生的算法視野和提高人工智能專業人才培養質量。同樣，針對人工智能專業的上述做法可供其他專業（如通信工程專業、物聯網工程專業）的算法設計與分析課程進行借鑒。

參考文獻（References）：

[1] 彭雷，宋志明，陳曉宇，等.算法設計與分析課程三維立體教育

模式創新[J].計算機教育，2023（7）：128-132.

[2] 余亮，張騰飛.基于強化學習的算法分析與設計課程重難點

教學方法探索[J].計算機教育，2022（5）：185-188，195.

[3] 黃隆華，陳志輝.算法設計與分析課程的“百錢買百雞問題”

趣用[J].計算機教育，2016（3）：143-145.

[4] 何高奇，肖春蕓，陳蕾，等.聚焦計算思維的算法分析與設計課

程教育改革[J].計算機教育，2023（1）：86-90.

[5] 余亮，柯昌博，趙學健.貪心法求解一般背包問題的教學探討[J].

計算機時代，2016（1）：71-72.

[6] Richard S. Sutton and Andrew G. Barto， Reinforcement

Learning： An Introduction[M].second edition，Cambridge： The MIT Press，2018：131-132.