【正文】 數(shù)學(xué)建模中的智能算法 2 2022/2/11 數(shù)學(xué)建模十大算法 ? 蒙特卡羅算法 ? 數(shù)據(jù)擬合 、 參數(shù)估計(jì) 、 插值等數(shù)據(jù)處理算法 ? 線性規(guī)劃等規(guī)劃類問(wèn)題 ? 圖論算法 ? 動(dòng)態(tài)規(guī)劃 、 回溯搜索 、 分支定界等計(jì)算機(jī)算法 ? 模擬退火 、 神經(jīng)網(wǎng)絡(luò) 、 遺傳算法等最優(yōu)化理論算法 ? 網(wǎng)格算法和窮舉法 ? 一些連續(xù)離散化方法 ? 數(shù)值分析算法 ? 圖像處理算法 3 2022/2/11 3 人工智能優(yōu)化算法 ? 遺傳算法 ? 模擬退火 ? 人工神經(jīng)網(wǎng)絡(luò)算法 ? 粒子群算法 ? 蟻群算法 4 2022/2/11 認(rèn)識(shí)“人工智能” ? 人工智能 (Artificial Intelligence, AI) 概念是 John McCarthy（ 約翰 .麥克斯 ） 于1956年在 Dartmouth學(xué)會(huì)上提出的 。 ? 美國(guó)計(jì)算機(jī)科學(xué)家 ， 因在人工智能領(lǐng)域的重大貢獻(xiàn) ， 被稱為 “ 人工智能之父 ”， 并因此獲得圖靈獎(jiǎng) ? 他于 1948年獲得加州理工學(xué)院數(shù)學(xué)學(xué)士學(xué)位 ， 1951年獲得普林斯頓大學(xué)數(shù)學(xué)博士學(xué)位 John McCarthy 5 2022/2/11 認(rèn)識(shí)“人工智能”（續(xù)） ? 人工智能 ——讓機(jī)器像人一樣思考 ? 人工智能是計(jì)算機(jī)科學(xué)的前沿學(xué)科，是研究、開(kāi)發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué) .計(jì)算機(jī)編程語(yǔ)言和其它計(jì)算機(jī)軟件都因?yàn)橛辛巳斯ぶ悄艿倪M(jìn)展而得以存在。 ? 人工智能 涉及學(xué)科： 哲學(xué)和認(rèn)知科學(xué)，數(shù)學(xué)，神經(jīng)生理學(xué)，心理學(xué)，計(jì)算機(jī)科學(xué)，信息論，控制論，不定性論，仿生學(xué)等 6 2022/2/11 認(rèn)識(shí)“人工智能”（續(xù)） ? 人工智能的目的：通過(guò)研究人腦的組成機(jī)理和思維方式 ， 企圖了解智能的實(shí)質(zhì) ， 并生產(chǎn)出一種能以人類智能相似的方式做出反應(yīng)的智能機(jī)器 ——讓機(jī)器具有智慧 ， 像人一樣思考 . ? 計(jì)算機(jī)的出現(xiàn) ——人類開(kāi)始真正有了一個(gè)可以模擬人類思維的工具 ? 人工智能的領(lǐng)域研究：包括機(jī)器人 、 語(yǔ)言識(shí)別 、 圖像識(shí)別 、 自然語(yǔ)言處理和專家系統(tǒng)等 . 7 2022/2/11 意識(shí)和人工智能的區(qū)別 ? 人工智能就其本質(zhì)而言 ， 是對(duì)人的思維的信息過(guò)程的模擬 . ? 對(duì)于人的思維模擬可以從兩條道路進(jìn)行： 結(jié)構(gòu)模擬：仿照人腦的結(jié)構(gòu)機(jī)制 ， 制造出 “ 類人腦 ” 的機(jī)器； 功能模擬：暫時(shí)撇開(kāi)人腦的內(nèi)部結(jié)構(gòu) ， 而從其功能過(guò)程進(jìn)行模擬 。 現(xiàn)代電子計(jì)算機(jī)的產(chǎn)生便是對(duì)人腦思維功能的模擬 ， 是對(duì)人腦思維的信息過(guò)程的模擬 . ? 人工智能不是人的智能 ， 更不會(huì)超過(guò)人的智能 . 8 2022/2/11 意識(shí)和人工智能的區(qū)別（續(xù)） “機(jī)器思維 ” 同 “ 人類思維 ” 的本質(zhì)區(qū)別： 1. 人工智能純系無(wú)意識(shí)的機(jī)械的物理的過(guò)程 ， 人類智能主要是生理和心理的過(guò)程 . 2. 人工智能沒(méi)有社會(huì)性 . 3. 人工智能沒(méi)有人類的意識(shí)所特有的能動(dòng)的創(chuàng)造能力 . 4. 兩者總是人腦的思維在前 ， 電腦的功能在后 . 9 2022/2/11 經(jīng)典的人工智能成果 ? 人機(jī)對(duì)弈 * 1996年 2月 1017日 , Garry Kasparov以 4:2戰(zhàn)勝 “ 深藍(lán) ” (Deep Blue) * 1997年 5月 311日 , Garry Kasparov以 : “ 深藍(lán) ” * 2022年 2月 Garry Kasparov 3:3戰(zhàn)平 “ 小深 ” (Deep Junior) * 2022年 11月 Garry Kasparov 2:2戰(zhàn)平 “ X3D德國(guó)人 ” (X3DFritz ) ? 模式識(shí)別 指紋識(shí)別 、 人臉識(shí)別 、 語(yǔ)音識(shí)別 、 文字識(shí)別 、 圖像識(shí)別 、 車牌識(shí)別等 10 2022/2/11 經(jīng)典的人工智能成果 (續(xù) ) ? 電 影 中文名：人工智能 片 名： AI 年 代： 2022 國(guó) 家：美國(guó) ? 相關(guān)著作 《 視讀人工智能 》 、 《 人工智能的未來(lái) 》 、 《 人工智能哲學(xué) 》 、 《 人工智能：一種現(xiàn)代的方法 》 …… 11 2022/2/11 ? 遺傳算法 (Geic Algorithm， GA) ? 人工神經(jīng)網(wǎng)絡(luò)算法 (Artificical Neural Network , ANN) ? 模擬退火 (Simulated Annealing, SA) ? 粒子群優(yōu)化算法 (Partical Swam Optimization Algorithm, PSOA) ? 蟻群優(yōu)化算法 (Ant Colony Optimization Algorithm, ACOA) 人工智能優(yōu)化算法 12 2022/2/11 ? 97年 A 題用模擬退火算法 ? 00年 B 題用神經(jīng)網(wǎng)絡(luò)分類算法 ? 01年 B 題這種難題也可以使用神經(jīng)網(wǎng)絡(luò) ? 美國(guó) 89年 A 題也和 BP 算法 有關(guān)系 ? 美國(guó) 03年 B 題 伽馬刀問(wèn)題也是目前研究的課題，目前算法最佳的是遺傳算法 。 遺傳算法 (GA)、模擬退火法 (SA)、神經(jīng)網(wǎng)絡(luò) (NN)、 近幾年的賽題越來(lái)越復(fù)雜，很多問(wèn)題沒(méi)有什么很好的 模型可以借鑒，于是這三類算法很多時(shí)候可以派上用場(chǎng)。 最優(yōu)化理論的三大非經(jīng)典算法 : 13 2022/2/11 ? 遺傳算法 (Geic Algorithm， GA) ? 人工神經(jīng)網(wǎng)絡(luò)算法 (Artificical Neural Network , ANN) ? 模擬退火 (Simulated Annealing, SA) ? 粒子群優(yōu)化算法 (Partical Swam Optimization Algorithm, PSOA) ? 蟻群優(yōu)化算法 (Ant Colony Optimization Algorithm, ACOA) 人工智能優(yōu)化算法 14 2022/2/11 遺傳算法 (Geic Algorithm) ?進(jìn)化算法 (Evolutionary Algorithm) 15 2022/2/11 ? 遺傳算法是一類模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳算法機(jī)理的生物進(jìn)化過(guò)程的 計(jì)算模型 ， 借鑒生物界的進(jìn)化規(guī)律 （ 適者生存 ， 優(yōu)勝劣汰遺傳機(jī)制 ） 演化而來(lái)的 隨機(jī)化搜索最優(yōu)化方法 。 ? 遺傳算法最初由美國(guó)密歇根大學(xué) J. Holland（ 霍蘭德 ） 教授于 1975年首先提出來(lái)的 ， 并出版了頗有影響的專著 《 Adaptation in Natural and Artificial Systems》 , 遺傳算法這個(gè)名稱才逐漸為人所知 ， 通常稱為 “ 簡(jiǎn)單遺傳算法 ” 。 遺傳算法 (Geic Algorithm, GA) 16 2022/2/11 ? 直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作 ， 不存在求導(dǎo)和函數(shù)連續(xù)性的限定； 具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力； 采用概率化的尋優(yōu)方法 ， 能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間 ， 自適應(yīng)地調(diào)整搜索方向 ， 不需要確定的規(guī)則 。 ? 遺傳算法的這些性質(zhì) ， 已被人們廣泛地應(yīng)用于組合優(yōu)化 、 機(jī)器學(xué)習(xí) 、 信號(hào)處理 、 自適應(yīng)控制和人工生命等領(lǐng)域 。 它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù) 。 遺傳算法的主要特點(diǎn) 17 2022/2/11 遺傳算法的定義 ? 遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群 （ population）開(kāi)始的 ， 而一個(gè)種群則由經(jīng)過(guò)基因 （ gene） 編碼的一定數(shù)目的個(gè)體 (individual)組成 。 ? 每個(gè)個(gè)體實(shí)際上是染色體 (chromosome)帶有特征的實(shí)體 。 ? 染色體作為遺傳物質(zhì)的主要載體 ， 即多個(gè)基因的集合 ， 其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合 ， 它決定了個(gè)體的形狀的外部表現(xiàn) ， 如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的 。 因此 ， 在一開(kāi)始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作 。 18 2022/2/11 遺傳算法的定義（續(xù)） ? 由于仿照基因編碼的工作很復(fù)雜 ， 我們往往進(jìn)行簡(jiǎn)化 ， 如二進(jìn)制編碼 ， 初代種群產(chǎn)生之后 ， 按照適者生存和優(yōu)勝劣汰的原理 ， 逐代 （ generation） 演化產(chǎn)生出越來(lái)越好的近似解 。 ? 在每一代 ， 根據(jù)問(wèn)題域中個(gè)體的 適應(yīng)度 （ fitness） 大小選擇 （selection） 個(gè)體 ， 并借助于自然遺傳學(xué)的 遺傳算子 （ geic operators） 進(jìn)行組合 交叉 （ crossover） 和 變異 （ mutation） ， 產(chǎn)生出代表新的解集的種群 。 這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境 ， 末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼 （ decoding） ， 可以作為問(wèn)題近似最優(yōu)解 。 19 2022/2/11 遺傳算法流程圖 實(shí) 際 問(wèn) 題 參 數(shù) 集編 碼群 體 t計(jì) 算 適 應(yīng) 度 值運(yùn) 算 ： 復(fù) 制 、 交 叉 、 變 異群 體 t + 1滿 足 要 求 ？解 碼改 善 或 解 決 實(shí) 際 問(wèn) 題群 體 t + 1代 替 群 體 tY e sN o? 由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計(jì)算是不依賴于梯度信息或其它輔助知識(shí) ， 而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù) ， 所以 遺傳算法提供了一種求解復(fù)雜系統(tǒng)問(wèn)題的通用框架 ， 它不依賴于問(wèn)題的具體領(lǐng)域 ， 對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性 。 20 2022/2/11 遺傳算法的一般算法 ? 遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法 。 1. 創(chuàng)建一個(gè)隨機(jī)的初始狀態(tài)： 初始群是從解中隨機(jī)選擇出來(lái)的 ， 將這些解比喻為染色體或基因 ， 該種群被稱為第一代 。 2. 評(píng)估適應(yīng)度： 對(duì)每一個(gè)解 (染色體 )指定一個(gè)適應(yīng)度的值 ， 根據(jù)問(wèn)題求解的實(shí)際接近程度來(lái)指定 (以便逼近求解問(wèn)題的答案 )。 不要把這些“ 解 ” 與問(wèn)題的 “ 答案 ” 混為一談 ， 可以把它理解成為要得到答案 ，系統(tǒng)可能需要利用的那些特性 。 21