面向組合優化問題的程序自動生成

"林舒，中國科學院自動化研究所復雜系統認知與決策國家級重點實驗室助理研究員。於2021年在北京大學獲得計算機軟件與理論專業博士學位。長期致力於組合優化約束建模、運籌問題求解優化、多智能體博弈決策方向學術研究工作，相關論文發表在IJCAI、ESEC/FSE、ITiCSE、DAI等人工智能、軟件工程、計算機教育領域國際知名學術會議。主持或參與了多項智能運籌優化相關科研項目，積極跟進運籌優化的前沿研究工作，並推動關鍵技術在作業調度、無人化設備控制、物流運輸等具體業務場景中完成落地驗證。李文新，北京大學計算機學院計算機科學與工程系系主任、教授，北京大學人工智能研究院副院長，北京市教學名師,北京大學計算機實驗教學中心(國家級示範中心)主任,中國計算機學會傑出會員。她為推動ACM/ICPC競賽在北京大學、中國乃至亞洲的普及做了大量工作，多次獲得ACM/ICPC組織頒發的“區域發展傑出貢獻獎”和“領導力獎”等。她目前的主要研究興趣是遊戲智能體相關領域，包括遊戲和遊戲AI的復雜度分析、遊戲AI的評測方法、遊戲AI的算法、遊戲AI的模仿和傾向性聚類、遊戲AI對局的自動解說等。她帶領團隊自主研發的遊戲Al對戰平臺已經成為國內外知名的遊戲AI對戰平臺。"

目錄

第 1章引言 .............................................................................................1 

1.1程序自動生成概述..........................................................................1 

1.1.1程序自動生成的定義............................................................1 

1.1.2程序自動生成的發展歷史 .....................................................2 

1.1.3程序自動生成的研究方向 .....................................................4 

1.1.4現有程序自動生成研究與本書研究的關系..............................5 

1.2組合優化約束求解概述 ...................................................................5 

1.2.1組合優化約束模型概述 ........................................................5 

1.2.2組合優化問題自動求解算法..................................................7 

1.2.3現有約束求解研究與本書研究的關系 .................................. 15 

1.3基於組合優化約束模型的程序自動生成的引入和研究意義 ............... 15 

1.4本書結構 ..................................................................................... 18

第 2章相關工作的研究進展 .................................................................... 20 

2.1程序自動生成相關工作 ................................................................. 20 

2.1.1終端用戶編程.................................................................... 20 

2.1.2程序變換和代碼生成.......................................................... 21 

2.2約束求解優化技術相關工作 .......................................................... 21 

2.2.1通用約束求解優化技術 ...................................................... 21 

2.2.2動態規劃求解器 ................................................................ 22 

2.2.3自動存表技術.................................................................... 22 

2.3自然語言程序設計相關工作 .......................................................... 22 

2.3.1語義分析 .......................................................................... 22 

2.3.2自動約束編程.................................................................... 23 

2.4計算機科學教育相關工作.............................................................. 23 

2.4.1問題求解能力與計算機科學教育 ......................................... 23 

2.4.2支架式教學工具 ................................................................ 24 

2.5本章小結 ..................................................................................... 24

第 3章問題描述語言 COPDL和程序自動生成方法 COPDL2C ............ 26 

3.1從組合優化約束模型到程序源代碼 ................................................ 26 

面向組合優化問題的程序自動生成 

3.2程序源代碼生成示例 .................................................................... 28 

3.2.1問題描述 .......................................................................... 28 

3.2.2模型分析和程序生成.......................................................... 29 

3.3組合優化約束模型描述語言設計.................................................... 32 

3.3.1 COPDL的核心語法 .......................................................... 32 

3.3.2 COPDL描述各組成部分 ................................................... 33 

3.4經典問題的 COPDL描述示例 ...................................................... 34 

3.4.1最大公約數問題 ................................................................ 35 

3.4.2最短路徑問題.................................................................... 35 

3.5從組合優化約束模型自動產生求解程序源代碼的算法...................... 36 

3.5.1變量類型推導.................................................................... 36 

3.5.2獨立變量選取.................................................................... 36 

3.5.3程序代碼生成.................................................................... 38 

3.6 COPDL及 COPDL2C的有效性驗證實驗設計與結果 .................... 42 

3.6.1數據集.............................................................................. 42 

3.6.2實驗設計及實驗結果.......................................................... 42 

3.7本章小結 ..................................................................................... 43

第 4章程序自動生成方法 COPDL2C中的搜索剪枝和動態規劃優化 ....... 45 

4.1組合優化問題求解的搜索剪枝和動態規劃優化................................ 45 

4.2搜索剪枝優化 .............................................................................. 46 

4.2.1搜索剪枝在 0/1背包問題上的應用示例............................... 47 

4.2.2可行性剪枝優化 ................................................................ 48 

4.2.3最優性剪枝優化 ................................................................ 49 

4.3動態規劃優化 .............................................................................. 52 

4.3.1模型預處理 ....................................................................... 52 

4.3.2約束模型性質檢查 ............................................................. 53 

4.3.3動態規劃優化的生成.......................................................... 56 

4.3.4不同動態規劃求解方法的比較和選擇 .................................. 59 

4.3.5特殊情況處理.................................................................... 60 

4.4優化後的 COPDL2C的性能測試實驗設計與結果........................... 62 

4.4.1優化後的 COPDL2C的有效性評估 .................................... 62 

4.4.2 COPDL2C在求解經典組合問題上的效率 ........................... 63 

4.4.3 COPDL2C優化模型與原始模型在求解效率上的比較........... 66 

目錄 

4.5本章討論 ..................................................................................... 69 

4.6本章小結 ..................................................................................... 70

第 5章從自然語言問題描述產生約束模型的翻譯方法 NL2COPDL ......... 72 

5.1從自然語言描述到約束模型 .......................................................... 72 

5.2組合優化約束模型自然語言描述的特點.......................................... 73 

5.2.1組合優化約束模型自然語言描述的受限性............................ 73 

5.2.2組合優化約束模型自然語言描述的翻譯難點 ........................ 73 

5.2.3組合優化約束模型自然語言描述的翻譯方法 ........................ 73 

5.3建立組合優化問題的自然語言描述數據集 ...................................... 74 

5.4從自然語言描述自動產生 COPDL模型的算法............................... 76 

5.4.1 0/1背包問題自然語言描述示例.......................................... 77 

5.4.2描述處理 .......................................................................... 78 

5.4.3元素提取 .......................................................................... 78 

5.4.4框架生成 .......................................................................... 84 

5.4.5框架模型填充.................................................................... 85 

5.5 NL2COPDL正確性和性能測試實驗設計與結果 ............................. 87 

5.5.1研究問題及實驗設計.......................................................... 87 

5.5.2實驗結果 .......................................................................... 88 

5.6本章小結 ..................................................................................... 92

第 6章問題建模訓練平臺 COPDLOpenJudge的關鍵技術和應用.......... 94 

6.1程序設計類與算法分析類課程中的問題求解能力 ............................ 94 

6.2問題建模訓練平臺 COPDLOpenJudge的設計與實現 ..................... 95 

6.2.1問題建模訓練平臺 COPDLOpenJudge的技術架構.............. 95 

6.2.2問題建模訓練平臺 COPDLOpenJudge的使用方法.............. 97 

6.2.3錯誤提示與反饋信息.......................................................... 98 

6.3 COPDL及 COPDL2C輔助教學效果評估實驗設計與結果.............. 98 

6.3.1實驗設計 .......................................................................... 99 

6.3.2實驗結果 ........................................................................ 101 

6.4本章小結 ................................................................................... 104

第 7章結論和展望 ............................................................................... 105 

7.1本書工作總結 ............................................................................ 105 

7.2未來工作展望 ............................................................................ 106 

面向組合優化問題的程序自動生成

附錄 A COPDL手冊 ........................................................................... 108 

A.1 COPDL簡介............................................................................ 108 

A.2 COPDL實例............................................................................ 108 

A.2.1最大公約數.................................................................... 108 

A.2.2 0/1背包問題 ................................................................. 109 

A.3 COPDL語法............................................................................ 109 

A.3.1基本框架 ....................................................................... 109 

A.3.2變量定義 ....................................................................... 110 

A.3.3基本運算 ....................................................................... 112 

A.3.4復合運算 ....................................................................... 112 

A.3.5量詞.............................................................................. 112 

A.3.6特殊約束關系 ................................................................ 113 

A.4常見錯誤 .................................................................................. 114 

A.4.1編譯錯誤 ....................................................................... 114 

A.4.2其他錯誤 ....................................................................... 115

附錄 B基礎課程期末試題數據集信息及 COPDL2C有效性測試結果...... 116 

B.1計算概論 A課程期末上機考試題詳情及實驗結果 ........................ 116 

B.2程序設計實習課程期末上機考試題詳情及實驗結果 ...................... 117 

B.3數據結構與算法 A課程期末上機考試題詳情及實驗結果 .............. 118

附錄 C包含 40個用自然語言描述的組合優化問題的數據集 .................... 119 

C.1來源於課程例題、作業與測試的 33個問題的自然語言描述 .......... 119 

C.2來源於 MiniZinc教程或標準測試集的 7個問題的自然語言描述 ... 122

參考文獻 ................................................................................................. 124