人工智能課程報告

1、武漢輕工大學數(shù)計學院人工智能課設報告名 稱: 人工智能算法的應用 班 級: 信計1201 姓 名: 張相軍 學 號: 1205130122 指導教師: 曾山 學年學期: 2015 2016 學年 第 一 學期 2015 年 12 月 11 日目 錄1 知識簡介32發(fā)展概況.4 3研究與應用 54遺傳算法的研究65 實驗結果76 課設總結87 附錄文件9 181知識簡介人工智能概述人工智能（Artificial Intelligence，簡稱AI），是相對自然人的天然智能而言，即用人工的方法和技術，模仿、延伸和擴展人的智能，實現(xiàn)某些“機器思維”。作為計算機學科的一個重要分支，是由 McCarth

2、y 于1956 年在 Dartmouth 學會上正式提出，在當前被人們稱為世界三大尖端技術之一。美國斯坦福大學著名的人工智能研究中心尼爾遜（Nilson）教授這樣定義人工智能“人工智能是關于知識的學科怎樣表示知識以及怎樣獲得知識并使用知識的學科”，另一名著名的美國大學 MIT的 Winston 教授認為“人工智能就是研究如何使計算機去做過去只有人才能的智能的工作”。除此之外，還有很多關于人工智能的定義，今尚未統(tǒng)一，但這些說法均反映了人工智能學科的基本思想和基本容,由此可以將人工智能概括為研究人類智能活動的規(guī)律，構造具有一定智能行為的人工系統(tǒng)。2發(fā)展概況人工智能 ( Artificial Int

3、elligence)自1956 年正式問世以來的五十年間已經取得了長足的進展, 由于其應用的極其廣泛性及存在的巨大研究開發(fā)潛力, 吸引了越來越多的科技工作者投入人工智能的研究中去。尤其是八十年代以來出現(xiàn)了世界范圍的開發(fā)新技術的高潮, 許多發(fā)達國家的高科技計劃的重要內容是計算機技術, 而尤以人工智能為其基本重要組成部分。人工智能成為國際公認的當代高技術的核心部分之一。人工智能的發(fā)展歷史自古以來,人類就力圖根據(jù)自己的認識水平和當時的技術條件,企圖用機器來代替人的部分腦力勞動,以提高征服自然的能力。公元 850 年,古希臘就有制造機器人幫助人們勞動的傳說。在我國公元前900多年,也有歌舞機器人傳說的

4、記載, 這說明古代人就有人工智能的幻想。隨著歷史的發(fā)展, 到十二世紀末至十三世紀初, 西班牙的神學家和邏輯學家 Romen Luee 試圖制造能解決各種問題的通用邏輯機。十七世紀法國物理學家和數(shù)學家 BPascal制成了世界第一臺會演算的機械加法器并獲得實際應用。隨后德國數(shù)學家和哲學家 GWLeibniz 在這臺加法器的基礎上發(fā)展并制成了進行全部四則運算的計算器。他還提出了邏輯機的設計思想, 即通過符號體系, 對對象的特征進行推理, 這種 “萬能符號” 和 “推理計算” 的思想是現(xiàn)代化 “思考” 機器的萌芽, 因而他被后人譽為數(shù)理邏輯的第一個奠基人。 接著, 英國數(shù)學家、 邏輯學家 Boole

5、 初步實現(xiàn)了 LeibniZ 關于思維符號化和數(shù)學化的思想,提出了一種嶄新的代數(shù)系統(tǒng), 這就是后來在計算機上廣泛應用的布爾代數(shù)。十九世紀末英國數(shù)學和力學家 C Babbage 致力于差分機和分析機的研究, 雖因條件限制未能完全實現(xiàn), 但其設計思想不愧為當年人工智能的最高成就。進入二十世紀后, 人工智能相繼出現(xiàn)若干開創(chuàng)性的工作。1936 年, 年僅 24 歲的英國數(shù)學家 AMTuring 在他的一篇 “理想計算機” 的論文中, 就提出了著名的圖林機模型, 1945 年他進一步論述了電子數(shù)字計算機的設計思想, 1950 年他又在“計算機能思維嗎? ”一文中提出了機器能夠思維的論述, 可以說這些都是

6、圖林為人工智能所作的杰出貢獻。1946 年美國科學家 JWMauchly等人制成了世界上第一臺電子數(shù)字計算機 ENIAC。隨后又有不少人為計算機的實用化不懈奮斗, 其中貢獻卓著的應當是 VonNeomann 。目前世界上占統(tǒng)治地位的依然是馮諾依曼計算機。電子計算機的研制成功是許多代人堅持不懈地努力的結果。這項劃時代的成果為人工智能研究奠定了堅實的物質基礎。同一時代,美國數(shù)學家 NWiener控制論的創(chuàng)立, 美國數(shù)學家 CEShannon信息論的創(chuàng)立, 英國生物學家 WRAshby所設計的電腦等, 這一切都為人工智能學科的誕生作了理論和實驗工具的巨大貢獻。1.1 形成時期 ( 1956- 196

7、1 年)1956 年夏季, 在美國 Dartmouth 大學, 由年青數(shù)學助教 JMdarthy 和他的三位朋友 Mminsky 、N Lochester 和 CShannor 共同發(fā)起, 邀請 IBM 公司的 TMore 和 ASamuel、MIT的OSelf-ridge 和RSolomonff 以及 RAND 公司和 Carnagie 工科大學的 ANewell 和HASimon 等人參加夏季學術討論班, 歷時兩個月。這十位學者都是在數(shù)學神經生理學、 心理學、 信息論和計算機科學等領域中從事教學和研究工作的學者, 在會上他們第一次正式使用了人工智能 ( AI ) 這一術語, 從而開創(chuàng)了人工

8、智能的研究方向。這次歷史性的聚會被認為是人工智能學科正式誕生的標志, 從此在美國開始形成了以人工智能為研究目標的幾個研究組: 如Newell 和 Simon 的 Carnegie- RAND 協(xié) 作 組 ; Samuel 和 Gelernter的 IBM 公司工程課題研究組; Minsky 和 Mccarthy 的 MIT 研究組等, 這一時期人工智能的主要研究工作有下述幾個方面:1957 年 ANewell、JShaw 和HSiomon 等人的心理學小組編制出一個稱為邏輯理論機 LT(The Logic Theory Machine) 的數(shù)學定理證明程序, 當時該程序證明了 BAWRusse

9、ll 和ANWhitehend 和“數(shù)學原理”一書第二章中的38 個定理。 后來他們又揭示了人在解題時的思維過程大致可歸結為三個階段:( 1 ) 先想出大致的解題計劃;( 2 ) 根據(jù)記憶中的公理、定理和推理規(guī)則組織解題過程;( 3 ) 進行方法和目的分析, 修正解題計劃。這種思維活動不僅解數(shù)學題時如此, 解決其他問題時也大致如此?；谶@一思想他們于 1960 年又編制了能解十種類型不同課題的通用問題求解程序 GPS(General Problem Solving) ,另外他們還發(fā)明了編程的表處理技術和 NSS 國際象棋機,和這些工作有聯(lián)系的 Newell關于自適應象棋機的論文和 Simon

10、關于問題求解和決策過程中合理選擇和環(huán)境影響的行為理論的論文, 也是當時信息處理研究方面的巨大成就。1956 年 Samuel 研究的具有自學習、自組織、自適應能力的西洋跳棋程序是 IBM 小組有影響的工作,這個程序可以像一個優(yōu)秀棋手那樣,向前看幾步來下棋。它還能學習棋譜,在分析大約175000 幅不同棋局后,可猜測出書上所有推薦的走步,準確度達48% ,這是機器模擬人類學習過程卓有成就的探索。1959 年這個程序曾戰(zhàn)勝設計者本人,1962 年還擊敗了美國一個州的跳棋大師。在 MIT 小組, 1959 年 Mccarthy 發(fā)明的表 ( 符號) 處理語言LISP ,成為人工智能程序設計的主要語言

11、,至今仍被廣泛采用。1958 年 Mccarthy 建立的行動計劃咨詢系統(tǒng)以及 1960 年 Minsky的論文 “走向人工智能的步驟”,對人工智能的發(fā)展都起了積極的作用。此外, 1956 年 NChomsky的文法體系, 1958年Selfridge等人的模式識別系統(tǒng)程序等 ,都對人工智能的研究產生有益的影響。這些早期成果, 充分表明人工智能作為一門新興學科正在茁壯成長。1.2 發(fā)展時期 (1961年以后)上世紀六十年代以來,人工智能的研究活動越來越受到重視。為了揭示智能的有關原理,研究者們相繼對問題求解、博弈、定理證明、程序設計、機器視覺、 自然語言理解等領域的課題進行了深入的研究。四十多

12、年來,不僅使研究課題有所擴展和深入,而且還逐漸搞清了這些課題共同的基本核心問題以及它們和其他學科間的相互關系。1974 年 NJNillson對發(fā)展時期的一些工作寫過一篇綜述論文,他把人工智能的研究歸納為四個核心課題和八個應用課題。這四個具有一般意義的核心課題是:( 1 ) 知識的模型化和表示方法;( 2 ) 啟發(fā)式搜索理論;( 3 ) 各種推理方法 ( 演繹推理、 規(guī)劃、 常識性推理、 歸納推理等) ;( 4 ) 人工智能系統(tǒng)結構和語言。這些課題的新成果極大地推動了人工智能應用課題的研究。這八個應用課題是:( 1 ) 自然語言理解 ( Natural Language Under-stand

13、ing ) (2) 數(shù) 據(jù) 庫 的 智 能 檢 索 ( Intelligent Retrieval fromDatabase )( 3 ) 專家咨詢系統(tǒng) ( Expert Consulting Systems ) (4) 定理證明 ( Theorem Proving ) (5) 博 弈 ( Game Playing ) (6) 機 器 人 學( Robotics ) (7) 自動程序設計 ( Automatic Programming ) (8) 組合調度問題 ( Combinatorial and Scheduling Problems ) 。這一時期學術交流的發(fā)展對人工智能的研究有很大推動

14、作用。 1969 年國際人工智能聯(lián)合會成立, 并舉行第一次學術會議IJCAI- 69 ( International Joint Conference On Artificial Intelligence )以后每兩年召開一次。隨著人工智能研究的發(fā)展, 1974 年又成立了歐洲人工智能學會,并召開第一次會議 ECAI ( European Con-ference On Artificial Intelligence ) ,也是相隔兩年召開一次。此外,許多國家也都有本國的人工智能學術團體。在人工智能刊物方面, 1970 年創(chuàng)辦了 Artificial Intelligence 國際性期刊,愛丁堡

15、大學還不定期出版 雜志, 還有 IJCAI 會議文集, ECAI 會議文集等。另外許多國際知名刊物也刊載人工智能的論著。1.3 繁榮時期上世紀九十年代以來, 人工智能研究出現(xiàn)了新的高潮。這一方面是因為在人工智能理論方面有了新的進展, 另一方面也是因為計算機硬件突飛猛進的發(fā)展。隨著計算機速度的不斷提高、 存儲容量的不斷擴大、價格的不斷降低以及網絡技術的不斷發(fā)展,許多原來無法完成的工作現(xiàn)在已經能夠實現(xiàn)。因此, 人工智能研究也就進入繁榮期。目前人工智能研究的3個熱點是 :智能接口、數(shù)據(jù)挖掘、 主體及多主體系統(tǒng)。其中某些技術已經實用化。技術的發(fā)展總是超乎人們的想象, 從目前的一些前瞻性研究可以看出未來

16、人工智能可能會向以下幾個方面發(fā)展: 模糊處理、并行化、神經網絡和機器情感。人工智能一直處于計算機技術的前沿,人工智能研究的理論和發(fā)現(xiàn)在很大程度上將決定計算機技術的發(fā)展方向。今天, 已經有很多人工智能研究的成果進入人們的日常生活。將來,人工智能技術的發(fā)展將會給人們的生活、工作和教育等帶來更大的影響。人工智能是計算機科學、控制論、信息論、神經生理學、心理學、語言學等多種學科互相滲透而發(fā)展起來的一門綜合性學科,就其本質而言,它是研究如何制造出人造的智能機器或智能系統(tǒng), 來模擬人類智能活動的能力,以延伸人們智能的科學。計算機所要模擬的人類智能活動的能力,具體地可以概括為:( 1 ) 通過視覺、 聽覺、

17、 觸覺等感官活動, 接受并理解文字、 圖象、 聲音、 語言等各種外界的 “自然信息” , 這就是認識和理解世界環(huán)境的能力。 ( 2 ) 通過人腦的生理與心理活動以及有關的信息處理過程,將感性知識抽象為理性知識, 并能對事物運動的規(guī)律進行分析, 判斷和推理, 這就是提出概念, 建立方法, 進行演繹和歸納推理, 作出決策的能力。 ( 3 ) 通過教育、 訓練和學習過程, 日益豐富自身的知識和技能, 這就是學習的能力。 ( 4 ) 對變化多端的外界環(huán)境條件, 如干擾、 刺激等作用能靈活地作出反應, 這就是自我適應的能力。針對以上人類智能活動的能力,目前研究人工智能主要有兩條途徑。一條是心理學家、生理

18、學家們希望搞清大腦信息處理過程的機理。他們認為大腦是智能活動的物質基礎,要揭示人類智能的奧秘,就必須弄清大腦的結構,也就是要從大腦的神經元模型著手研究。顯然由于人腦有上百億神經元,而且現(xiàn)階段要進行人腦的物理模擬實驗很困難,因而完成這個任務極其艱巨。但是這一學派試圖創(chuàng)立“信息處理的智能理論”作為實現(xiàn)人工智能的長遠研究目標, 這個觀點是值得重視的。另一條是計算機科學家們提出的從模擬人腦功能的角度來實現(xiàn)人工智能, 也就是通過計算機程序的運行,從效果上達到和人們智能行為活動過程相類似作為研究目標, 因而這派學者只是局限于解決“建造智能機器或系統(tǒng)為工程目標的有關原理和技術”作為實現(xiàn)人工智能的近期目標,這

19、個觀點比較實際,目前引起較多人的注意?？傊徽搹氖裁唇嵌葋硌芯咳斯ぶ悄?都是通過計算機來實現(xiàn),因此可以說人工智能的中心目標是要搞清楚實現(xiàn)人工智能的有關原理,使計算機有智慧、更聰明、更有用。美國是人工智能的發(fā)源地, 隨著人工智能的發(fā)展,世界各國有關學者也都相繼加入這一行列。英國在 60 年代就起步人工智能的研究,到 70 年代,在愛丁堡大學還成立了人工智能 系,日本和西歐一些國家雖起步較晚,但發(fā)展都較快, 前蘇聯(lián)對人工智能研究也給予重視。我國是從 1978 年才開始人工智能課題的研究,主要在定理證明、漢語自然語言理解、機器人及專家系統(tǒng)方面設立課題, 并取得一些初步成果。八十年代國內也相應成立了中

20、國人工智能學會, 中國計算機學會人工智能和模式識別專業(yè)委員會, 中國自動化學會模式識別與機器智能專業(yè)委員會, 開展這方面的學術交流。作為“86.3”高科技計劃的重要內容, 國家著手興建了若干個人工智能研究中心實驗室, 極大地促進了我國人工智能的研究, 縮短了我國人工智能技術與世界先進水平的差距, 也為未來的發(fā)展奠定了技術和人才基礎。 獲得首屆國家最高科學獎的數(shù)學家吳文俊院士, 就是因為其研究領域主要集中在運用計算機進行定理證明方面。人工智能這門新興學科也曾一度陷入低谷,遭到某些人的攻擊和非難。但是隨著高科技競爭的愈演愈烈,以及人工智能學者的艱苦卓絕的探索,它最終沖破迷霧以先鋒的姿態(tài)披荊斬棘,乘

21、風破浪,成為二十一世紀的前衛(wèi)學科。也許在不遠的將來,我們會無法分辨誰是機器人,誰是自然人。3研究與應用3.1 問題求解問題求解，即解決管理活動中由于意外引起的非預期效應或與預期效應之間的偏差。能夠求解難題的下棋 (如國際象棋 )程序的出現(xiàn)，是人工智能發(fā)展的一大成就。在下棋程序中應用的推理，如向前看幾步，把困難的問題分成一些較容易的子問題等技術，逐漸發(fā)展成為搜索和問題歸約這類人工智能的基本技術。搜索策略可分為無信息導引的盲目搜索和利用經驗知識導引的啟發(fā)式搜索，它決定著問題求解的推理步驟中，使用知識的優(yōu)先關系。另一種問題的求解程序，是把各種數(shù)學公式符號匯編在一起,其性能已達到非常高的水平并正在被許

22、多科學家和工程師所應用，甚至有些程序還能夠用經驗來改善其性能。例如，1993 年美國發(fā)布的一個叫做 MACSYMA 的軟件,它能夠進行較復雜的數(shù)學公式符號運算。如前所述 ,尚未解決的問題包括人類棋手具有的表達的能力，如國際象棋大師們洞察棋局的能力；另一個未解決的問題涉及問題的原概念，在人工智能中叫做問題表示的選擇。人們常常能夠找到某種思考問題的方法從而使求解變得容易而最終解決該問題。3.2 專家系統(tǒng)專家系統(tǒng) ES （Expert System）是人工智能研究領域中另一重要分支，它將探討一般的思維方法轉入到運用專門知識求解專門問題，實現(xiàn)了 人工智能從理論研究向實際應用的重大突破；專家系統(tǒng)可看作一

23、類具有專門知識的計算機智能程序系統(tǒng)，它能運用特定領域中專家提供的專門知識和經驗，并采用人工智能中的推理技術來求解和模擬通常由專家才能解決的各種復雜問題。總的來說，專家系統(tǒng)是一種具有智能的軟件，它求解方法是一種啟發(fā)式方法，專家系統(tǒng)所要解決的問題一般無算法解，并且與傳統(tǒng)的計算機程序上不同之處在于，它要經常在不完全、不精確或不確定的信息基礎上做出結論。在近年來的專家系統(tǒng)或“知識工程的研究中，已經出現(xiàn)了成功和有效應用人工智能技術的趨勢，具有有代表性的是用戶與專家系統(tǒng)進行“咨詢對話”，如同其與專家面對面的進行對話是一樣的：解釋問題并建議進行某些試驗，向專家系統(tǒng)詢問以期得到有關解答等。當前的實驗系統(tǒng)，在比

24、如化學和地質數(shù)據(jù)分析、計算機系統(tǒng)結構、建筑工程以及醫(yī)療診斷等咨詢任務方面，已達到很高的水平。另外，還有很多研究主要是集中在讓專家系統(tǒng)能夠說明推理的能力，從而使咨詢更好地被用戶接受，同時還能幫助人類發(fā)現(xiàn)系統(tǒng)推理過程中所出現(xiàn)的差錯。發(fā)展專家系統(tǒng)的關鍵在于表達和運用專家知識，即來自人類專家的且已被證明能夠解決某領域內的典型問題的有用的事實和過程。不同領域與不同類型的專家系統(tǒng)，它們的體系結構和功能是有一定的差異的，但它們的組成基本一致。一個基本的專家系統(tǒng)主要由知識庫、數(shù)據(jù)庫、推理機、解釋機制、知識獲取和用戶界面六部分組成，如圖1 所示。3.3 機器學習機器學習 （Machine Learning）是研

25、究如何使用計算機模擬或實現(xiàn)人類的學習活動。它是繼專家系統(tǒng)之后人工智能的又一重要應用領域，是使計算機具有智能的根本途徑，也是人工智能研究的核心課題之一，它的應用遍及人工智能的各個領域。學習是人類智能的重要特征，是獲得知識的基本手段，而機器學習也是使計算機具有智能的根本途徑，如香克所說：“一臺計算機若不會學習，就不能稱為具有智能的 ?！背酥?，機器學習還有助于發(fā)現(xiàn)人類學習的機理和揭示人腦的奧秘。學習是一個有特定目的的知識獲取過程，它的內部主要表現(xiàn)為新知識結構的不斷建立和修改，外部表現(xiàn)為性能的改善。一個學習過程本質上講，就是學習系統(tǒng)把導師 （或專家）提供的信息轉換成能被系統(tǒng)理解并應用的形式的過程。

26、按照系統(tǒng)對導師的依賴程度可將學習方法分類為:機械式學習 （Rotelearning）、講授式學習（Learning from instruction）、類比學習（Learning by analogy）、歸納學習（Learning from induction）、觀察發(fā)現(xiàn)式學習 （learning by observation and discovery）等。此外，近年來又發(fā)展了基于解釋、事例、概念、神經網絡的學習和遺傳學習等學習方法。3.4 神經網絡人工神經網絡（Aficial Neural Network）,是由大量處理單元即神經元互連而成的網絡，也常簡稱為神經網絡或類神經網絡。神經網絡是

27、一種由大量的節(jié)點 （或稱神經元）和之間相互聯(lián)接構成的運算模型，是對人腦或自然神經網絡一些基本特性的抽象和模擬，其目的在于模擬大腦的某些機理與機制，從而實現(xiàn)某些方面的功能。通俗地講，人工神經網絡是仿真研究生物神經網絡的結果。詳細地說，人工神經網絡是為獲得某個特定問題的解，根據(jù)所掌握的生物神經網絡機理，按照控制工程的思路及數(shù)學描述方法，建立相應的數(shù)學模型并采用適當?shù)乃惴ǎ嗅槍π缘卮_定數(shù)學模型參數(shù)的技術。神經網絡的信息處理是由神經元之間的相互作用實現(xiàn)的：知識與信息的存貯主要表現(xiàn)為網絡元件互連間分布式的物理聯(lián)系 。人工神經網絡具有很強的自學習能力，它可以不依賴于 “專家” 的頭腦， 而自動從已有的

28、實驗數(shù)據(jù)中總結規(guī)律。由此，人工神經網絡擅長于處理復雜多維的非線性問題，不但可以解決定性問題，也可解決定量的問題，同時還具有大規(guī)模并行處理和分布的信息存儲能力，具有良好的自適應、自組織性以及很強的學習、聯(lián)想、容錯和較好的可靠性 。3.5 模式識別計算機人工智能所研究的模式識別是指用計算機代替人類或幫助人類感知模式。其主要的研究對象是計算機模式識別系統(tǒng)，也就是讓計算機系統(tǒng)能夠模擬人類通過感覺器官對外界產生的各種感知能力。較早的模式識別研究工作集中在對文字和二維圖像的識別方面，并取得了不少成果。自20世紀60年代中期起,機器視覺方面的研究工作開始轉向解釋和描述復雜的三維景物這一更困難的課題。羅伯斯特

29、 ( Robest ) 于1965年發(fā)表的論文奠定了分析由棱柱體組成的景物的方向，邁出了用計算機將三維圖像解釋成三維景物的一個單眼視圖的第一步，即所謂的積木世界。接著，機器識別由積木世界進入識別更復雜的景物和在復雜環(huán)境中尋找目標以及室外景物分析等方面的研究。目前研究的熱點是活動目標(如飛行器)的識別和分析，它是景物分析走向實用化研究的一個標志。語音識別技術的研究始于20世紀50年代初期，發(fā)展到20世紀70年代，各種語音識別裝置相繼出現(xiàn)，性能良好的能夠識別單詞的聲音識別系統(tǒng)已進入實用階段，神經網絡用于語音識別也已取得成功。作為一門新興學科，模式識別在不斷發(fā)展，其理論基礎和研究范圍也在不斷發(fā)展。當

30、前模式識別正處于大發(fā)展的階段，隨著其應用范圍的逐漸擴大及計算機科學的發(fā)展，模式識別技術將在今后有更大的發(fā)展，并且量子計算技術也將用于模式識別的研究。3.6 人工生命人工生命 ( Artificial Life, 簡稱 AL) 是由美國圣菲研究所非線性研究組的計算機科學家 Christopher Langton 于1987 年與 Los Alamos National Laboratory 召開的 “生成以及模擬生命系統(tǒng)的國際會議”上首先提出的。它主要是通過人工模擬生命系統(tǒng)來研究生命的領域。AL 的概念主要包括兩方面內容：1）計算機科學領域的虛擬生命系統(tǒng)，主要涉及計算機軟件工程和人工智能技術 ；

31、 2）基因工程技術人工改造生物的工程生物系統(tǒng)，主要涉及合成生物學技術。相比于傳統(tǒng)的人工智能和神經網絡，人工生命不論在理論上還是方法上都有很大的區(qū)別。人工生命主要是通過計算機仿真生命現(xiàn)象來體現(xiàn)自適應機理，對相關非線性對象進行更真實的動態(tài)描述以及動態(tài)特征研究。人工生命學科主要包括仿生系統(tǒng)、人工建模與仿真、人工生命的計算理論、進化動力學、進化與學習綜合系統(tǒng)以及人工生命的應用等研究內容?，F(xiàn)階段比較典型的人工生命研究有：計算機病毒、計算機進程、進化機器人、自催化網絡、細胞自動機、人工核苷酸和人工腦等。4遺傳算法的研究1遺傳算法概述遺傳算法(GeneticAlgorithm,GA)是模擬生物進化論的自然選

32、擇和遺傳學進化過程的計算模型,是一種通過模擬自然進化過程隨機搜索最優(yōu)解的方法,體現(xiàn)了適者生存、優(yōu)勝劣汰的進化原則,其主要特點是直接對結構對象進行操作,不存在求導和函數(shù)連續(xù)性的限定,具有并行性和較強的全局尋優(yōu)能力。遺傳算法把問題的解表示成染色體,求解步驟如下:(1)編碼:定義問題的解空間到染色體編碼空間的映射,一個候選解(個體)用一串符號表示。(2)初始化種群:在一定的限制條件下初始化種群,該種群是解空間的一個子空間。(3)設計適應度函數(shù):將種群中的每個染色體解碼成適于適應度函數(shù)的形式,計算其數(shù)值。(4)選擇:根據(jù)適應度大小選擇優(yōu)秀個體繁殖下一代,適應度越高,選擇概率越大。(5)交叉:隨機選擇兩

33、個用于繁殖下一代的個體的相同位置,在選中的位置實行交換。(6)變異:對某個串中的基因按突變概率進行翻轉。(7)從步驟4開始重復進行,直到滿足某一性能指標或規(guī)定的遺傳代數(shù)。GA在圖像分割領域應用最為成熟,只要有兩種應用,一是在多種分割結果中搜索最佳分割結果,二是搜索圖像分割算法的最優(yōu)參數(shù),如用來確定圖像最佳分割閡值。Jincong等使用最小誤差概率做為適應度函數(shù)來搜索圖像最佳分割閡值,Leesu將GA用于分割閡值計算,提高了分割效率,Bhanu使用GA在多個分割參數(shù)空間中搜索最優(yōu)分割參數(shù),提出了動態(tài)環(huán)境中圖像分割系統(tǒng),大大提高了環(huán)境適應性,iaJgniTan一ihz使用GA搜索最優(yōu)細胞輪廓模型參

34、數(shù),對高噪聲細胞圖像進行分割,chunDaeN使用GA對灰度圖像的區(qū)域進行模糊測量,搜索一最佳區(qū)域。GA在圖像增強方面的應用主要是搜索最優(yōu)或次優(yōu)控制參數(shù)的過程。GA在圖像恢復中的應用主要解決高噪聲圖像的恢復。在圖像壓縮中,GA能有效解決分形壓縮的最優(yōu)匹配問題,提高了壓縮比和精度,可用于低比特率的圖像壓縮。GA在圖像匹配方面的應用主要解決速度問題,通過減少搜索位置的數(shù)量來減少計算量,提高效率。遺傳算法是一類借鑒生物界自然選擇和自然選擇機制的隨機化搜索方法,有美國JHolhdn教授提出,他的主要特點是能夠提供群體的搜索方案和實現(xiàn)群體里面?zhèn)€體之間的信息交換,且搜索不會依賴于梯度信息。它尤其適用于處理

35、傳統(tǒng)搜索方法難于解決的復雜和非線性的問題,可廣泛應用于組合優(yōu)化、機器學習、自適應控制、規(guī)劃設計和圖像處理等多個方面,是二十一世紀的智能計算的關鍵技術之一。2遺傳方法在圖像處理中的應用2.1在圖像增強中的應用。圖像增強技術是將不清晰的圖像經過優(yōu)化處理變一張比之前更加清楚,或者變成一張使得特點更加鮮明的照片,以便于對圖像再進行后期的加工。目前圖像增強方法主要包括將圖像進行某種變換的頻域法和對直接對原始圖像進行處理的空域法兩種。而基于遺傳算法的圖像增強技術的實現(xiàn)則是利用遺傳的選擇方法找到一個最優(yōu)或者局部最優(yōu)的方法。具體的操作方法是,首先將每一個目標值設置一個基位,用實數(shù)進行編碼,這樣問題就轉化成求解

36、這個目標基位組合的題目。然后,對適應度進行設計,適應度設計為個體進化提供動力,在設置適應度的時候既要考慮圖像的整體和局部的質量問題,也要將結構和細節(jié)考慮進去。再后,對遺傳算子進行設計,先根據(jù)前面設置的適應度值將個體從大到小進行排列,從中選擇優(yōu)秀的個體進入下一個程序當中;為了防止遺傳算法在計算的過程中過早收斂,對種群的多樣性進行保護,在計算過程中采用交叉操作的方法產生新的個體;對進化方向進行微調,采用變異操作的方法,對一個被選中的變異操作來說,就是采用“1”一“0”和“1”一“0”的方式進行變異。最后,設置算法的結束條件,一般算法的結束條件就是迭代次數(shù)達到了最大進化代數(shù)或者最大適應度的值變化不明

37、顯。2.2圖像恢復技術。圖像恢復技術的目的就是降一些退化的圖像經過技術處理使得圖像的本來面目得到恢復。作為數(shù)字圖像處理技術的一個分支,他的恢復方法有很多,包括維納濾波法,逆濾波法、最大嫡恢復法和奇異值分解偽逆法等。但是,上述方法在應用過程中都有自己的缺陷,圖像退化原因的不確定性和無確定的函數(shù)表達式,會導致上述算法過于復雜,計算量過大和約束條件過多等情況的出現(xiàn)。采用遺傳算法進行圖像恢復,突破了原有理論的縛,能夠更好的與其他一些計算方法進行融合,使得計算率和精確度都有很大的提高。由于遺傳算法具有功能強大的全局搜索能力,采用遺傳算法結合其他算法處理過的圖像在客服噪影響方面具有很大的優(yōu)勢,同時也能使得

38、圖像邊緣不會出現(xiàn)條紋效應、過的更加平滑,整體感覺好。2.3圖像重建技術。圖像重建是由在某種觀測方式下得到的攜帶圖像信息的數(shù)據(jù)恢復出原圖像的過程。圖像重建技術的方法也有很多種,主要是根據(jù)取得圖像信息的方法不同,使用重建方法也不同,有迭代法、代數(shù)法和傅里葉變換法等法。遺傳算法在圖像重建中的應用主要是解決帶有噪聲的投影數(shù)據(jù)的圖像處理問題。遺傳算法在這方面的處理方法有很多,包括利用最小化被測像素值和計算的線總和之間的差的方法;利用松弛迭代的傅里葉變換算法來解決計算過程中出現(xiàn)的停滯現(xiàn)象;假定目標組合點分散的條件下,使用線性擬合方式來重建高分辨雷達圖像數(shù)據(jù)。2.4圖像壓縮技術。圖像壓縮技術最主要的原理就是

39、將擁有自相似性的對象用這一組簡單的代數(shù)關系式進行表達的過程。將互相不重疊的小塊定義為值域塊,然后進行編碼,并使經過映射后的定義域塊與值域塊的距離在某種度量值下最小,在分解和處理過程中,由于值域塊的數(shù)量過于龐大,壓縮搜索過程任務繁重,遺傳算法的強大全局搜索能力就能很好的派上用場,發(fā)揮良好的效果。遺傳算法的基本原理遺傳算法(GA)是基于“適者生存”的一種高度并行、隨機和自適應的優(yōu)化算法,它將問題的求解表示成“染色體”的適者生存過程,通過“染色體”群的一代代不斷進化,包括復制、交叉和變異等操作,最終收斂到“最適應環(huán)境”的個體,從而求得問題的最優(yōu)解或滿意解。其中選擇、交叉和變異是遺傳算法的三個主要操作

40、算子。具體操作步驟圖如下:l)在一定編碼方案下,隨機產生一個初始種群;2)用相應的解碼方法將編碼后的個體轉換成問題空間的決策變量,并求個體的適應值;3)按照個體適應值的大小,從種群中選出適應值較大的一些個體構成交配池;4)由交叉和變異這兩個遺傳算子對交配池中的個體進行操作,并形成新一的種群;5)反復執(zhí)步驟2)一4),直至滿足收斂判據(jù)為止。GA是一種通用的優(yōu)化算法,其編碼技術和遺傳操作比較簡單,優(yōu)化不受限制性條件的約束,其搜索過程是從問題解的一個集合開始的,而不是從單個個體開始的,具有隱含并行搜索特性,也就大大減小了陷人局部極小值的可能。正是由于其具有以上突出的優(yōu)點,遺傳算法幾乎滲透到從工程到社

41、會科學的各個領域。為了驗證遺傳算法的全局尋優(yōu)能力,本文將運用基于MATLAB編制的遺傳算法來求解數(shù)值優(yōu)化和旅行商問題。遺傳算法概述遺傳算法(GeneticAlgorithm,GA)是借鑒生物界自然選擇和群體進化機制形成的一種全局尋優(yōu)算法。與傳統(tǒng)的優(yōu)化算法相比,遺傳算法具有如下優(yōu)點1:1)不是從單個點,而是從多個點構成的群體開始搜索;2)在搜索最優(yōu)解過程中,只需要由目標函數(shù)值轉換得來的適應值信息,而不需要導數(shù)等其它輔助信息;3)搜索過程不易陷入局部最優(yōu)點。目前,該算法已滲透到許多領域,并成為解決各領域復雜問題的有力工具2。在遺傳算法中,將問題空間中的決策變量通過一定編碼方法表示成遺傳空間的一個個

42、體,它是一個基因型串結構數(shù)據(jù);同時,將目標函數(shù)值轉換成適應值,它用來評價個體的優(yōu)劣,并作為遺傳操作的依據(jù)。遺傳操作包括三個算子:選擇、交叉和變異。選擇用來實施適者生存的原則,即把當前群體中的個體按與適應值成比例的概率復制到新的群體中,構成交配池(當前代與下一代之間的中間群體)。選擇算子的作用效果是提高了群體的平均適應值。由于選擇算子沒有產生新個體,所以群體中最好個體的適應值不會因選擇操作而有所改進。交叉算子可以產生新的個體,它首先使從交配池中的個體隨機配對,然后將兩兩配對的個體按某種方式相互交換部分基因。變異是對個體的某一個或某一些基因值按某一較小概率進行改變。從產生新個體的能力方面來說,交叉

43、算子是產生新個體的主要方法,它決定了遺傳算法的全局搜索能力;而變異算子只是產生新個體的輔助方法,但也必不可少,因為它決定了遺傳算法的局部搜索能力。交叉和變異相配合,共同完成對搜索空間的全局和局部搜索。遺傳算法的基本步驟3如下:1)在一定編碼方案下,隨機產生一個初始種群;2)用相應的解碼方法,將編碼后的個體轉換成問題空間的決策變量,并求得個體的適應值;3)按照個體適應值的大小,從種群中選出適應值較大的一些個體構成交配池;4)由交叉和變異這兩個遺傳算子對交配池中的個體進行操作,并形成新一代的種群;5)反復執(zhí)行步驟24,直至滿足收斂判據(jù)為止。使用遺傳算法需要決定的運行參數(shù)有:編碼串長度、種群大小、交

44、叉和變異概率。編碼串長度由優(yōu)化問題所要求的求解精度決定。種群大小表示種群中所含個體的數(shù)量,種群較小時,可提高遺傳算法的運算速度,但卻降低了群體的多樣性,可能找不出最優(yōu)解;種群較大時,又會增加計算量,使遺傳算法的運行效率降低。一般取種群數(shù)目為20100。交叉概率控制著交叉操作的頻率,由于交叉操作是遺傳算法中產生新個體的主要方法,所以交叉概率通常應取較大值;但若過大的話,又可能破壞群體的優(yōu)良模式。一般取0.40.99。變異概率也是影響新個體產生的一個因素,變異概率小,產生新個體少;變異概率太大,又會使遺傳算法變成隨機搜索。一般取變異概率為0.00010.1。遺傳算法常采用的收斂判據(jù)有:規(guī)定遺傳代數(shù)

45、;連續(xù)幾次得到的最優(yōu)個體的適應值沒有變化或變化很小等。3 用MATLAB 實現(xiàn)遺傳算法MATLAB 是Matwork公司的產品,是一個功能強大的數(shù)學軟件,其優(yōu)秀的數(shù)值計算能力使其在工業(yè)界和學術界的使用率都非常高。MATLAB還十分便于使用,它以直觀、簡潔并符合人們思維習慣的代碼給用戶提供了一個非常友好的開發(fā)環(huán)境。利用MATLAB處理矩陣運算的強大功能來編寫遺傳算法程序有著巨大的優(yōu)勢。3. 1 編碼遺傳算法不對優(yōu)化問題的實際決策變量進行操作, 所以應用遺傳算法首要的問題是通過編碼將決策變量表示成串結構數(shù)據(jù)。 本文中我們采用最常用的二進制編碼方案, 即用二進制數(shù)構成的符號串來表示一個個體, 用下面

46、的 encoding 函數(shù)來實現(xiàn)編碼并產生初始種群:functionbin-gen,bits=encoding(min-var,max-var,scale-var,popsize)bits=ceil(log2( max-var-min-var)./scale-var);bin-gen=randint(popsize,sum(bits);在上面的代碼中, 首先根據(jù)各 決策變量的下界(min-var)、上界(max-var)及其搜索精度scale-var來確定表示各決策變量的二進制串的長度 bits, 然后隨機產生一個種群大小為 popsize 的初始種群 bin - gen。 編碼后的實際搜索精

47、度為scale-dec=(max-var-min-var)/(2bits-1), 該精度會在解碼時用到。3. 2 解碼編碼后的個體構成的種群bin-gen必須經過解碼,以轉換成原問題空間的決策變量構成的種群var - gen,方能計算相應的適應值。我們用下面的代碼實現(xiàn)。functionvar-gen,fitness=decoding(funname,bin-gen,bits,min-var,max-var)num-var=length(bits);popsize=size(bin-gen,1);scale-dec=(max-var-min-var)./(2.bits-1);bits=cumsu

48、m(bits);bits=0bits;fori=1:num-varbin-vari=bin-gen(:,bits(i)+1:bits(i+1);vari=sum(ones(popsize,1)2.(size(bin-vari,2)-1:-1:0).bin-vari,2).scale-dec(i)+min-var(i);endvar-gen=var1,:;fori=1:popsizefitness(i)=eval(funname,(var-gen(i,:);end解碼函數(shù)的關鍵在于先由二進制數(shù)求得對應的十進制數(shù) D, 并根據(jù)下式求得實際決策變量值 X:X=Dscale-dec+min-var3.

49、 3 選擇選擇過程是利用解碼后求得的各個體適應值大小, 淘汰一些較差的個體而選出一些比較優(yōu)良的個體,以進行下一步的交叉和變異操作。 選擇算子的程序如下:functionevo-gen,best-indiv,max-fitness=selection(old-gen,fit-ness)popsize=length(fitness);max-fitness,index1=max(fitness);min-fitness,index2=min(fitness);best-indiv=old-gen(index1,:);index=1:popsize;index(index1)=0;index(index2)=0;index=nonzeros(index);evo-gen=old-gen(index,:);evo-fitness=fitness(index,:);evo-popsize=popsize-2;ps=evo-fitne