第一篇：人工智能作業(yè)1
通過學(xué)習(xí)《高中信息技術(shù)“人工智能初步”模塊教學(xué)研究》課程，分析您教學(xué)中學(xué)生的專家系統(tǒng)作品（或課程學(xué)習(xí)的參考資料的學(xué)生作品），就學(xué)生作品中存在的問題，談?wù)勛约涸诮虒W(xué)中如何更好地開展人工智能的教學(xué)。
通過學(xué)習(xí)《高中信息技術(shù)“人工智能初步”模塊教學(xué)研究》課程，談?wù)勀趯?shí)施該模塊教學(xué)過程中遇到的問題及解決方法，未實(shí)施過該模塊教學(xué)的教師可談?wù)勯_展人工智能模塊教學(xué)的設(shè)想。
按教材的順序，應(yīng)該先講人工智能的基本概念，然后講解知識(shí)及其表示的理論知識(shí)，再講解推理與專家系統(tǒng)和人工智能語言。但是這種傳統(tǒng)教學(xué)方法對于中學(xué)生來說太晦澀難懂了，教師還沒把理論知識(shí)講完，學(xué)生已對人工智能徹底失去興趣了。所以我們在講理論知識(shí)的過程中，要加入有趣的實(shí)例。所以我們要打破常規(guī)的教學(xué)順序，對教材進(jìn)行重組。盡量減少概念和純理論知識(shí)的講解時(shí)間，通過讓學(xué)生制作一個(gè)有實(shí)用價(jià)值的個(gè)性化的簡易專家系統(tǒng)來帶動(dòng)人工智能的理論知識(shí)學(xué)習(xí)。在“做”的過程中，掌握知識(shí)的表達(dá)及推理機(jī)制等理論知識(shí)。讓學(xué)生在完成一個(gè)簡單專家系統(tǒng)作品的過程中，不知不覺中學(xué)習(xí)了相應(yīng)的理論知識(shí)。我們要做到通過人工智能教學(xué)，能夠吸引更多的學(xué)生能投身于人工智能的研究中。
通過對學(xué)生作品—疾病診斷治療專家系統(tǒng)的分析，我覺得在以后的人工智能教學(xué)中，要做到以下幾個(gè)方面：
（1）教師要以平等友好的心態(tài)，微笑溫和的話語與學(xué)生交流，尊重、理解每個(gè)學(xué)生的權(quán)利、價(jià)值觀和感覺，保全學(xué)生的面子，杜絕直接的批評、奚落、嘲弄、諷刺，保證學(xué)生在課堂上的情緒安全感。
（2）盡量減少概念和純理論知識(shí)的講解時(shí)間，通過讓學(xué)生制作一個(gè)有實(shí)用價(jià)值的個(gè)性化的簡易專家系統(tǒng)來帶動(dòng)人工智能的理論知識(shí)學(xué)習(xí)。在“做”的過程中，掌握知識(shí)的表達(dá)及推理機(jī)制等理論知識(shí)。讓學(xué)生在完成一個(gè)簡單專家系統(tǒng)作品的過程中，不知不覺中學(xué)習(xí)了相應(yīng)的理論知識(shí)。
（3）展人工智能的教學(xué)，重點(diǎn)要放在讓學(xué)生能夠體驗(yàn)，老師最好能以現(xiàn)實(shí)中的例子來給學(xué)生做講演,有直觀的印象,學(xué)起來更容易現(xiàn)解。
（4）在教學(xué)中要利用好因特網(wǎng)這個(gè)大資源庫，并以小組合作學(xué)習(xí)的形式，相互交流，相互幫助，老師再及時(shí)指導(dǎo)與評價(jià)。
第二篇：人工智能心得體會(huì)大作業(yè)
我眼中的人工智能
人，沒有熊一樣的力量，卻能把熊關(guān)進(jìn)籠子，這籠子的鑰匙，叫智慧。人類一直在思考如何讓自然界的其它事物為自己所用，而不是只想著如何獲取食物來填飽肚子，人類之所以會(huì)凌駕于食物鏈頂端，就在于對于資源的使用。為了減輕胃的消化負(fù)擔(dān)，人類開始學(xué)會(huì)使用火，讓蛋白質(zhì)在進(jìn)入胃之前就變質(zhì)而變得更好消化易于吸收。經(jīng)歷了漫長的手工制造業(yè)歷程，為了提高生產(chǎn)效率，也為了減輕工人手工勞作的負(fù)擔(dān)，人們開始了工業(yè)革命，無數(shù)的機(jī)器流水線取代了效率低下的廉價(jià)勞動(dòng)力，也正是從此刻起，人類使用資源的能力有了質(zhì)的發(fā)展，由使用已有資源，到創(chuàng)造新的資源。第一臺(tái)計(jì)算機(jī)應(yīng)運(yùn)而生，人類開啟了無限創(chuàng)造的時(shí)代。時(shí)至今日，計(jì)算機(jī)技術(shù)幾乎延伸到了生活的每個(gè)領(lǐng)域，甚至成了人們的生活必需品。計(jì)算機(jī)能幫助人們完成人類不可能完成的計(jì)算，但一直致力于創(chuàng)造的人們當(dāng)然不會(huì)停止對計(jì)算機(jī)的要求。人們不光需要計(jì)算機(jī)做人類做不了的計(jì)算，還漸漸開始要求計(jì)算機(jī)做人類能做的事，這便催生了人工智能。人類就是這樣一步步用自己的智慧讓自己過上傻瓜一樣的生活。
人工智能目前還沒有在人們生活中普及，但是已經(jīng)出現(xiàn)萌芽。最典型是的一些語音識(shí)別系統(tǒng)，如蘋果公司的Siri可能是目前人們接觸最多的基于人工智能和云計(jì)算技術(shù)的產(chǎn)品，相信這種人機(jī)交互系統(tǒng)的雛形經(jīng)過時(shí)間的磨練會(huì)在未來形成一套完善的從界面到內(nèi)核的智能體系。在社會(huì)生活方面，與數(shù)字圖像處理技術(shù)緊密結(jié)合的人工智能已經(jīng)開始應(yīng)用于攝像頭的圖像捕捉和識(shí)別，而模式識(shí)別技術(shù)的發(fā)展則使得人工智能在更廣闊的領(lǐng)域得以實(shí)現(xiàn)成為了可能。一些大公司在人工智能領(lǐng)域的投入和研究對于推動(dòng)人工智能的發(fā)展起到了很大的作用，最值得一提的就是谷歌。谷歌的免費(fèi)搜索表面上是為了方便人們的查詢，但這款搜索引擎推出的初衷，就是為了幫助人工智能的深度學(xué)習(xí)，通過上億的用戶一次又一次地查詢，來鍛煉人工智能的學(xué)習(xí)能力，由于我的水平還很低，對于深度學(xué)習(xí)還不敢妄自拽測。但是，近年來谷歌公司在人工智能方面的突破一項(xiàng)接著一項(xiàng)，為人們熟知的便是智能汽車。不得不說，人工智能想要進(jìn)一步發(fā)展，必須依靠這些大公司的研究和不斷推廣，由經(jīng)濟(jì)促創(chuàng)新。
縱覽時(shí)間長河，很多新生的技術(shù)在一開始都是舉步維艱的，人工智能也不例外，但幸運(yùn)的是，人們接受和學(xué)會(huì)使用新技術(shù)所需要的時(shí)間越來越短，對于人工智能產(chǎn)品的投入市場是有益的。因此，在我看來，將已開發(fā)出來但還需完善的人工智能產(chǎn)品投放市場，使其進(jìn)入人們的生活只是時(shí)間的問題，但要想真正掌握人工智能，開發(fā)出完全符合研發(fā)人想法的智能產(chǎn)品還需各方面的努力。至于現(xiàn)在討論熱烈的“人工智能統(tǒng)治人類”的問題，我的看法是，人工智能的開發(fā)和應(yīng)用是需要監(jiān)管的，但并不能阻止人工智能即將影響世界的趨勢。
由于我對于人工智能的理解還只是皮毛，對于文中出現(xiàn)的紕漏和錯(cuò)誤還希望老師指正！
第三篇：江蘇大學(xué) 人工智能作業(yè)
課學(xué)生姓學(xué)專業(yè)班指導(dǎo)教
計(jì)算機(jī)科學(xué)與通信工程學(xué)院
程
人工智能
名
號
級 師
人工智能技術(shù)發(fā)展歷程及應(yīng)用前景
摘要： “人工智能”(Artificial Intelligence)一詞最初是在1956年的達(dá)特茅斯學(xué)會(huì)上提出的。人工智能又名機(jī)器智能，智能模擬，在日本叫做FGCS。它是一門通過計(jì)算過程力圖理解和模仿只能行為的學(xué)科（Schalkoff，1990）。可實(shí)現(xiàn)判斷、推理、證明、識(shí)別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動(dòng)的自動(dòng)化。（Bellman，1978）。現(xiàn)如今時(shí)代發(fā)展，人類社會(huì)中的許多問題越來越難以使用常規(guī)的計(jì)算機(jī)系統(tǒng)解決問題。人工智能企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應(yīng)的智能機(jī)器。目前能夠用來研究人工智能的主要物質(zhì)手段以及能夠?qū)崿F(xiàn)人工智能技術(shù)的機(jī)器就是計(jì)算機(jī)，人工智能的發(fā)展歷史是和計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展史聯(lián)系在一起的。
關(guān)鍵詞：人工智能 發(fā)展
一、人工智能的定義
“人工智能”(Artificial Intelligence)一詞最初是在1956年的達(dá)特茅斯學(xué)會(huì)上提出的。人工智能又名機(jī)器智能，智能模擬，在日本叫做FGCS。它是一門通過計(jì)算過程力圖理解和模仿只能行為的學(xué)科（Schalkoff，1990）。可實(shí)現(xiàn)判斷、推理、證明、識(shí)別、感知、理解、通信、設(shè)計(jì)、思考、規(guī)劃、學(xué)習(xí)和問題求解等思維活動(dòng)的自動(dòng)化。（Bellman，1978）。現(xiàn)如今時(shí)代發(fā)展，人類社會(huì)中的許多問題越來越難以使用常規(guī)的計(jì)算機(jī)系統(tǒng)解決問題。人工智能企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應(yīng)的智能機(jī)器。目前能夠用來研究人工智能的主要物質(zhì)手段以及能夠?qū)崿F(xiàn)人工智能技術(shù)的機(jī)器就是計(jì)算機(jī)，人工智能的發(fā)展歷史是和計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展史聯(lián)系在一起的。人工智能理論進(jìn)入21世紀(jì)，正醞釀著新的突破。人工智能的研究成果將能夠創(chuàng)造出更多高級的智能產(chǎn)品，極大的方便我們的生活。并為發(fā)展國民經(jīng)濟(jì)和改善人類生活做出更大貢獻(xiàn)。即將到來的信息時(shí)代絕非一般性地推廣使用常規(guī)計(jì)算機(jī)，而是發(fā)展人工智能。
二、人工智能的發(fā)展階段
第一階段：孕育期
早在計(jì)算機(jī)出現(xiàn)之前，科學(xué)家們就已經(jīng)希望能夠制造出可以模擬人類思維的機(jī)器了。而在更加久遠(yuǎn)的神話中，也有自動(dòng)機(jī)的記載。對這些東西我們已經(jīng)無從考證，但他們還是反應(yīng)了人們的期望。今天我們的計(jì)算機(jī)所使用的邏輯基礎(chǔ)正是由數(shù)學(xué)家布爾與其他杰出的科學(xué)家們在計(jì)算機(jī)出現(xiàn)之前的那個(gè)年代通過研究一起奠定的。
毫無疑問，圖靈的機(jī)器智能思想是人工智能的直接起源之一。在1937年他年僅24歲時(shí)就在一篇關(guān)于“理想計(jì)算機(jī)”的論文中提出了極好的設(shè)想，這就是為眾人所熟知的圖靈機(jī)。他于1950年發(fā)表了《計(jì)算機(jī)器與智能》。他在這篇論文中提出的“圖靈測試”則指出，如果測試者在與被測試者）隔開的情況下，通過一些裝置向被測試者隨意提問，進(jìn)行多次測試后，如果有超過30%的測試者不能確定出被測試者是人還是機(jī)器，那么這臺(tái)機(jī)器就通過了測試，并被認(rèn)為具有人工智能。
第二階段：人工智能基礎(chǔ)技術(shù)的研究與形成
1956年，在美國漢諾威的達(dá)特茅斯大學(xué)舉辦了一次暑期討論會(huì)。在交流探討中，與會(huì)者萌發(fā)了一個(gè)樸素的思想：設(shè)法使得電子計(jì)算機(jī)具有人的只能。他們大膽的預(yù)言，在25年之后這一設(shè)想將會(huì)初見成效。這次會(huì)議籌備者之一的達(dá)特茅斯大學(xué)數(shù)學(xué)系助教麥卡錫提出了人工智能（artificial intelligence）這一名稱。從那時(shí)起，人工智能的名字才正式確立。這次會(huì)議在人工智能歷史上不是巨大的成功，但是這次會(huì)議給人工智能奠基人相互交流的機(jī)會(huì)，并為未來人工智能的發(fā)展起了鋪墊的作用。在此以后，人工智能的重點(diǎn)開始變?yōu)榻?shí)用的能夠自行解決問題的系統(tǒng)，并要求系統(tǒng)有自學(xué)習(xí)能力。
1957年，香農(nóng)和另一些人又開發(fā)了一個(gè)程序稱為General Problem Solver(GPS)，它對Wiener的反饋理論有一個(gè)擴(kuò)展，并能夠解決一些比較普遍的問題。
紐厄爾、西蒙、嘯鳥心理學(xué)小組的工作是這一時(shí)期的一個(gè)開創(chuàng)性工作。他們于1953年創(chuàng)立了證明數(shù)學(xué)定理的LT邏輯推理程序。機(jī)器以此證明了羅素、懷德海所著《數(shù)學(xué)原理》一書中的38個(gè)定理。基于相同的思想，他們在1960年又編制了可以解出十種不同性質(zhì)課題的“通用問題求解機(jī)”程序。西蒙還發(fā)表了兩篇著名的論文：理想選擇的行為理論和問題求解的決策過程中環(huán)境的影響。他為此還獲得了1978年的諾貝爾獎(jiǎng)金。他們所做的開創(chuàng)性工作是人工智能向前發(fā)展的決定性步驟。
在這種環(huán)境下LISP應(yīng)運(yùn)而生。它是第一種聲明式系內(nèi)函數(shù)式程序設(shè)計(jì)語言。用具有智能的程序闡述了數(shù)學(xué)和數(shù)理邏輯相互作用的許多問題，為譯碼機(jī)打下了基礎(chǔ)。
第三階段：發(fā)展和實(shí)用化 DENDRAL化學(xué)質(zhì)譜分析系統(tǒng)、MYCIN疾病診斷和治療系統(tǒng)、PROSPECTIOR探礦系統(tǒng)、Hearsay-II語音理解系統(tǒng)等專家系統(tǒng)的研究和開發(fā)，將人工智能引向了實(shí)用化。并且，1969年成立了國際人工智能聯(lián)合會(huì)議（International Joint Conferences on Artificial Intelligence即IJCAI）。
70年代之后，人們一方面繼續(xù)進(jìn)行機(jī)器翻譯、模式識(shí)別等的開發(fā)工作，一邊又著手進(jìn)行定理證明、自然語言理解、專家系統(tǒng)等新領(lǐng)域的研究。科學(xué)家們還創(chuàng)辦了《人工智能》雜志，這為開展協(xié)作研究重大核心問題、制定研究方向，推動(dòng)其他國家的學(xué)者一起展開研究起到了積極作用。
1976年在美國的一次州國際象棋錦標(biāo)賽中，由西北大學(xué)設(shè)計(jì)的弈棋程序在B級水平的較量中戰(zhàn)勝了所有對手。在經(jīng)過改進(jìn)之后它于次年參加了第84屆明尼蘇達(dá)州國際象棋公開賽，挫敗名手拔得頭籌。從此機(jī)器弈棋名聲大振，西北大學(xué)應(yīng)西歐各國之邀巡回比賽，歷時(shí)一個(gè)多月載譽(yù)而歸。
雖然模式識(shí)別技術(shù)已經(jīng)初步用于醫(yī)療診斷、遙感圖像分析、信件分揀等方面，但正如人工智能專家尼爾·格雷厄姆（Neill Graham）所言，即使計(jì)算機(jī)稱得上是一個(gè)基本稱職的翻譯，并且能在弈棋比賽中與人分庭抗禮，但在模式識(shí)別方面與人的差距仍舊十分遙遠(yuǎn)。在這一時(shí)間段，由于國家的需求，機(jī)器人的研究和開發(fā)獲得了媚果國家宇航局等的大力支持。很快的第二代機(jī)器人得到批量生產(chǎn)，第三代機(jī)器人——可以一邊工作一邊擬定自己工作計(jì)劃的智能機(jī)器人也進(jìn)入了應(yīng)用研究階段。日本從70年代末起在這一領(lǐng)域突飛猛進(jìn)，其擁有機(jī)器人的總數(shù)已經(jīng)超越了美國。
70年代以來，Comad等人研究人工仿生系統(tǒng)中的自適應(yīng)、進(jìn)化和群體動(dòng)力學(xué)，提出了不斷完善的“人工世界”模型。80年代人工神經(jīng)網(wǎng)絡(luò)再度興起，促進(jìn)了人工生命的發(fā)展。其主要研究方法有信息模型法和工作原理法。其研究途徑分為工程技術(shù)途徑和生物科學(xué)途徑。
1987年，美國召開第一次神經(jīng)網(wǎng)絡(luò)國際會(huì)議，宣告了這一新學(xué)科的誕生。此后，各國在神經(jīng)網(wǎng)絡(luò)方面的投資逐漸增加，神經(jīng)網(wǎng)絡(luò)迅速發(fā)展起來。
專家系統(tǒng)于九十年代興起，其重點(diǎn)在于模擬對于人類專家的模擬和知識(shí)庫的改進(jìn)與歸納。在其諸多模型中，人工神經(jīng)網(wǎng)絡(luò)模型的應(yīng)用最為廣泛。由于Hopfield多層神經(jīng)網(wǎng)絡(luò)模型的提出，使人工神經(jīng)網(wǎng)絡(luò)研究與應(yīng)用出現(xiàn)了欣欣向榮的景象。人工智能已深入到社會(huì)生活的各個(gè)領(lǐng)域。
隨著計(jì)算機(jī)硬件和人工智能理論的發(fā)展，上世紀(jì)九十年代以來人工智能的研究出現(xiàn)了新的高潮。人工智能研究的三個(gè)熱點(diǎn)是：智能接口、數(shù)據(jù)挖掘和主體及多主體系統(tǒng)。
智能接口技術(shù)研究如何使人們能夠方便自然地與計(jì)算機(jī)交流。數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過程。主體是具有信念、愿望、意圖、能力、選擇、承諾等心智狀態(tài)的實(shí)體，比對象的粒度更大，智能性更高，而且具有一定自主性。多主體系統(tǒng)主要研究在邏輯上或物理上分離的多個(gè)主體之間進(jìn)行協(xié)調(diào)智能行為，最終實(shí)現(xiàn)問題求解。多主體系統(tǒng)試圖用主體來模擬人的理性行為，主要應(yīng)用在對現(xiàn)實(shí)世界和社會(huì)的模擬、機(jī)器人以及智能機(jī)械等領(lǐng)域。
三、人工智能的發(fā)展前景
AI與各門學(xué)科不斷的融合。其中信息技術(shù)的地位最為重要。其他方面，如心理學(xué)、語言學(xué)、認(rèn)知科學(xué)，還有社會(huì)學(xué)、人類學(xué)、哲學(xué)以及系統(tǒng)科學(xué)也與AI進(jìn)行著越來越頻繁的交流。
AI應(yīng)用問題需要開發(fā)復(fù)雜的軟件系統(tǒng)，這將促進(jìn)軟件工程學(xué)科的發(fā)展。軟件工程為一定類型的問題求解提供標(biāo)準(zhǔn)化程序；知識(shí)軟件為AI問題求解提供有效的編程手段。AI系統(tǒng)的開發(fā)也將發(fā)展為一個(gè)完整的應(yīng)用系統(tǒng)。
在當(dāng)前的AI應(yīng)用方法研究中，有幾大前沿課題格外引人注目：即多種方法混合技術(shù)、多專家系統(tǒng)、機(jī)器學(xué)習(xí)(尤以神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)和知識(shí)發(fā)現(xiàn))方法、硬軟件一體化以及并行分布處理技術(shù)等。其中對人腦機(jī)理和分布式AI（或MAS）的研究，將會(huì)確立新一代計(jì)算機(jī)的基礎(chǔ)。
四、心得體會(huì)
在進(jìn)入大學(xué)校園乃至于學(xué)習(xí)這門課程之前，人工智能對我來講都更像是科幻電影中才會(huì)存在的事物。在那里人工智能往往都站在人類陣營的對立面，這令我對人工智能這一領(lǐng)域充滿了敬畏和恐懼。但通過學(xué)習(xí)，我發(fā)現(xiàn)它其實(shí)并不會(huì)離我們的生活那么遙遠(yuǎn)。人工智能本身也不如想象中的那么可怕。人工智能的存在使現(xiàn)代生活變得更加便捷舒適，而且它也成為了人們茶余飯后的談資。比如IBM的沃森在問答節(jié)目《危機(jī)邊緣》中取得冠軍，再比如谷歌的無人駕駛汽車和kiva的智能倉儲(chǔ)系統(tǒng)。盡管與此同時(shí)它也為我們帶來了一些麻煩。但畢竟過度的悲觀和樂觀都將會(huì)影響我們對于人工智能的正確判斷，所以我覺得我們還是應(yīng)該辯證的去看待這一問題。相信隨著科技的發(fā)展，人工智能一定會(huì)克服那些問題從而更好的為人類服務(wù)。
通過對這門課程的學(xué)習(xí)，我了解到了一些新的前沿的領(lǐng)域，對自己所學(xué)習(xí)的專業(yè)有了進(jìn)一步的認(rèn)識(shí)，并且對已經(jīng)學(xué)習(xí)的某些課程有了更加進(jìn)一步的認(rèn)識(shí)。同時(shí)這也讓我在進(jìn)一步深造的專業(yè)選擇中有了更多的想法。
參考文獻(xiàn)：
[1]趙賽坡.人工智能的過去和未來[J].互聯(lián)網(wǎng)經(jīng)濟(jì)，2016.[2]是兆雄.人工智能：歷史、現(xiàn)狀及展望[J].自然雜志，1987.[3]渠川璐.人工智能的歷史、現(xiàn)狀和發(fā)展前景[J]河北大學(xué)學(xué)報(bào)（自然科學(xué)版），1984 [4]曾雪峰.論人工智能的研究與發(fā)展[J].現(xiàn)代商貿(mào)工業(yè)，2009，(13).[5]林堯瑞，魏宏森.人工智能研究的發(fā)展歷史及若干問題的初步探討[J].國外自動(dòng)化，1981 [6]余妹蘭，張永輝.人工智能的歷史和未來[J]信息與電腦（理論版），2010
第四篇：人工智能大作業(yè)解讀
實(shí)現(xiàn)遺傳算法的0-1背包問題求解
目錄
摘要.........................................................................................................2 一．問題描述..........................................................................................2 二．遺傳算法特點(diǎn)介紹...........................................................................2 三．使用基本遺傳算法解決0-1背包問題..............................................3 四．基本遺傳算法解決0-1背包問題存在的不足...................................4 五．改進(jìn)的遺傳算法解決0-1背包問題..................................................6 六．心得體會(huì)..........................................................................................9 七．參考文獻(xiàn).........................................................................................10 八．程序代碼.........................................................................................10
摘要：研究了遺傳算法解決0-1背包問題中的幾個(gè)問題：
1）
對于過程中不滿足重量限制條件的個(gè)體的處理,通過代換上代最優(yōu)解保持種群的進(jìn)化性 2）對于交換率和變異率的理解和處理方法,采用逐個(gè)體和逐位判斷的處理方法
3）對于早熟性問題,引入相似度衡量值并通過重新生成個(gè)體替換最差個(gè)體方式保持種群多樣性。4）一種最優(yōu)解只向更好進(jìn)化方法的嘗試。
通過實(shí)際計(jì)算比較表明,本文改進(jìn)遺傳算法在背包問題求解中具有很好的收斂性、穩(wěn)定性和計(jì)算效率。通過實(shí)例計(jì)算，表明本文改進(jìn)遺傳算法優(yōu)于簡單遺傳算法和普通改進(jìn)的遺傳算法。關(guān)鍵詞：遺傳算法；背包問題 ；優(yōu)化
一、問題描述
0-1背包問題屬于組合優(yōu)化問題的一個(gè)例子，求解0-1背包問題的過程可以被視作在很多可行解當(dāng)中求解一個(gè)最優(yōu)解。01背包問題的一般描述如下：
給定n個(gè)物品和一個(gè)背包，物品i的重量為Wi，其價(jià)值為Vi，背包的容量為C。選擇合適的物品裝入背包，使得背包中裝入的物品的總價(jià)值最大。注意的一點(diǎn)是，背包內(nèi)的物品的重量之和不能大于背包的容量C。在選擇裝入背包的物品時(shí)，對每種物品i只有兩種選擇：裝入背包或者不裝入背包，即只能將物品i裝入背包一次。稱此類問題為0/1背包問題。其數(shù)學(xué)模型為：
0-1背包問題傳統(tǒng)的解決方法有動(dòng)態(tài)規(guī)劃法、分支界限法、回溯法等等。傳統(tǒng)的方法不能有效地解決0-1背包問題。遺傳算法（Genetic Algorithms）則是一種適合于在大量的可行解中搜索最優(yōu)（或次優(yōu)）解的有效算法。
二、遺傳算法特點(diǎn)介紹:
遺傳算法(Genetic Algorithm, GA)是1962年Holland教授首次提出了GA算法的思想是近年來隨著信息數(shù)據(jù)量激增，發(fā)展起來的一種嶄新的全局優(yōu)化算法，它借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳、變異等作用機(jī)制，實(shí)現(xiàn)各個(gè)個(gè)體的適應(yīng)性的提高。基本遺傳算法求解步驟：
Step 1 參數(shù)設(shè)置：在論域空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；
Step 2 初始種群：隨機(jī)產(chǎn)生U中的N個(gè)染色體s1, s2, …, sN，組成初始種群S={s1, s2, …, sN}，置代數(shù)計(jì)數(shù)器t=1；
Step 3 計(jì)算適應(yīng)度：S中每個(gè)染色體的適應(yīng)度f()；
Step 4 判斷：若終止條件滿足，則取S中適應(yīng)度最大的染色體作為所求結(jié)果，算法結(jié)束。Step 5 選擇-復(fù)制：按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選定1個(gè)染色體并將其復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1；
Step 6 交叉：按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；
Step 7 變異：按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；
Step 8 更新：將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；
遺傳算法是一種仿生算法, 即模擬生命演化的算法，它從一個(gè)代表問題初始解的初始種群出發(fā), 不斷重復(fù)執(zhí)行選擇, 雜交和變異的過程, 使種群進(jìn)化越來越接近某一目標(biāo)既最優(yōu)解，如果視種群為超空間的一組點(diǎn), 選擇、雜交和變異的過程即是在超空間中進(jìn)行點(diǎn)集之間的某種變換, 通過信息交換使種群不斷變化，遺傳算法通過模擬達(dá)爾文“優(yōu)勝劣汰, 適者生存”的原理激勵(lì)好的結(jié)構(gòu), 同時(shí)尋找更好的結(jié)構(gòu), 作為一種隨機(jī)的優(yōu)化與搜索方法, 遺傳算法有著其鮮明的特點(diǎn)。
—遺傳算法一般是直接在解空間搜索, 而不像圖搜索那樣一般是在問題空間搜索, 最后才找到解(如果搜索成功的話)。
—遺傳算法的搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集, 而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn), 所以遺傳算法是一種隨機(jī)搜索算法。
—遺傳算法總是在尋找優(yōu)解(最優(yōu)解或次優(yōu)解), 而不像圖搜索那樣并非總是要求優(yōu)解, 而一般是設(shè)法盡快找到解(當(dāng)然包括優(yōu)解), 所以遺傳算法又是一種優(yōu)化搜索算法。
—遺傳算法的搜索過程是從空間的一個(gè)點(diǎn)集(種群)到另一個(gè)點(diǎn)集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。因而它實(shí)際是一種并行搜索, 適合大規(guī)模并行計(jì)算, 而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。
—遺傳算法的適應(yīng)性強(qiáng), 除需知適應(yīng)度函數(shù)外, 幾乎不需要其他的先驗(yàn)知識(shí)。
—遺傳算法長于全局搜索, 它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性, 能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解。
三、使用基本遺傳算法解決0-1背包問題：
1: 打開數(shù)據(jù)文件
2: 設(shè)置程序運(yùn)行主界面 3: 調(diào)用初始化種群模塊
3-1: 按照一定的種群規(guī)模和染色體長度以基因?yàn)閱挝挥秒S機(jī)產(chǎn)生的0-1對個(gè)體賦值 3-2: 調(diào)用計(jì)算適應(yīng)度函數(shù)
4: 以最大進(jìn)化代數(shù)為循環(huán)終止條件開始進(jìn)行循環(huán) 4-1: 調(diào)用產(chǎn)生新一代個(gè)體的函數(shù) 4-1-1: 調(diào)用選擇函數(shù) 4-1-2: 調(diào)用交叉函數(shù) 4-1-3: 調(diào)用變異函數(shù)
4-1-4: 調(diào)用計(jì)算適應(yīng)度函數(shù)
5: 調(diào)用計(jì)算新一代種群統(tǒng)計(jì)數(shù)據(jù)函數(shù) 6: 調(diào)用輸出新一代統(tǒng)計(jì)數(shù)據(jù)函數(shù) 7: 返回到第四步, 直至循環(huán)結(jié)束
四、基本遺傳算法解決0-1背包問題存在的不足：
1.對于過程中不滿足重量限制條件的個(gè)體的處理
在用基本遺傳算法解決0-1背包問題的時(shí)候，在初始化或者交叉變異后可能會(huì)產(chǎn)生不滿足重量約束條件的偽解，而對于這些偽解，基本遺傳算法沒有給出一個(gè)很好的處理方法，而只是又隨機(jī)生成了一個(gè)滿足約束條件的解作為新的個(gè)體從而替換掉原來的個(gè)體。根據(jù)遺傳算
法的根本思想“優(yōu)勝劣汰，適者生存”的原則，可以將不滿足條件的個(gè)體用已有的最優(yōu)個(gè)體來進(jìn)行替換，這樣，既使得種群中所有的個(gè)體均滿足重量的約束條件，又保留了較優(yōu)解，符合遺傳算法的思想。具體做法為：
在程序中加入一個(gè)變量保存每代的最優(yōu)解，當(dāng)前代在進(jìn)行選擇、復(fù)制、交叉、變異后如果有不滿足約束條件的個(gè)體，則在種群更新時(shí)采用這個(gè)最優(yōu)值作為替代。
具體做法為：在每代遺傳后通過函數(shù)FindBestandWorstIndividual()找到當(dāng)前最優(yōu)值并保存bestindividual中，在計(jì)算適應(yīng)度函數(shù)CalculateFitnessValue()中加入：
if(w>KW)X[i]=bestindividual;
//如果不是解，找最好的一個(gè)解代之
其中w為當(dāng)前個(gè)體的總重量，KW為背包最大承重量，X[i]表示種群中第i個(gè)個(gè)體，bestindividual為保存的個(gè)體最優(yōu)解。
2.對于交換率和變異率的理解和處理方法
根據(jù)遺傳算法的基本步驟的交叉和變異操作
Step 6 交叉：按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；
Step 7 變異：按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的 新染色體代替原染色體，得群體S3； 可以有兩種處理方法：
其一，采用先確定數(shù)目在隨機(jī)選取的方法，步驟如下：
對于交叉操作： 對于變異操作：
1,根據(jù)交叉率確定應(yīng)該交叉的個(gè)體數(shù)目1,根據(jù)變異率確定應(yīng)該變異的染色體數(shù)n 目n 2,在種群中進(jìn)行n次循環(huán) 2,在種群中進(jìn)行n次循環(huán) 2-1隨機(jī)選中種群中的一個(gè)個(gè)體a 2-1隨機(jī)選中種群中的一個(gè)個(gè)體的染2-2隨機(jī)選中種群中異于a的一個(gè)個(gè)色體a 體b
2-2隨機(jī)選中染色體a的某位基因
2-3隨機(jī)確定交叉位數(shù) 2-4進(jìn)行交叉
2-3對進(jìn)行0-1互換變異
其二，采用對每個(gè)操作單元分別進(jìn)行特定概率下處理的方法，步驟如下：
對于交叉操作：
1,在種群中進(jìn)行S次循環(huán),其中S代表種群中個(gè)體的數(shù)量
2,對于每一個(gè)個(gè)體X[i]（X為種群數(shù)組）做如下操作
2-1生成隨機(jī)數(shù)p[0,1],判斷p與的大小關(guān)系 2-2如果p說明X[i]需要交換
對于變異操作：
1,在種群中進(jìn)行S次循環(huán),其中S代表種群中個(gè)體的數(shù)量
2,對每一個(gè)個(gè)體X[i]做N次循環(huán)，其中N為染色體位數(shù)
2-1對染色體的每一位
3-1生成隨機(jī)數(shù)q[0,1],判斷q與 的大小關(guān)系
說明需要進(jìn)行0-1互換說明不需要變
2-2-1 隨機(jī)在種群中找到異于X[i]的另一個(gè)體進(jìn)行交換 2-3如果p 說明X[i]不需要交換
3-2如果q
變異2-3如果q分析這兩種處理方法可知：方法一沒有很好地體現(xiàn)隨機(jī)機(jī)會(huì)均等的思想，因?yàn)樵诓襟E1中確
定的需要操作的數(shù)目n后，總體上是保證了交叉或者變異的數(shù)目，但不是對于每一個(gè)個(gè)體而言的，因而會(huì)出現(xiàn)有的個(gè)體被選擇交叉或者變異多次而有的沒有機(jī)會(huì)交叉或者變異的情況，而如果采用方法二，就體現(xiàn)了機(jī)會(huì)的均等性，即要求對每一個(gè)單元操作目標(biāo)進(jìn)行概率的驗(yàn)證，以確定是否變異或者交叉。在程序中具體的實(shí)現(xiàn)方法體現(xiàn)在交叉和變異函數(shù)中：
void CrossoverOperator(void)//交叉操作 for(i=0;i q=rand()%S;}while(p==q); int w=1+rand()%N;//[1,N]交換的位數(shù) double p=(rand()%1001)/1000.0;if(p<=Pc) for(j=0;j void MutationOperator(void)//變異操作 for(i=0;i for(j=0;j q=(rand()%1001)/1000.0;//產(chǎn)生q[0,1] if(q if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;else X[i].chromsome[j]=1;1.對于算法早熟性的分析及解決方法 遺傳算法中種群中的個(gè)體由初始化時(shí)的具有多樣性，可能會(huì)由于在進(jìn)化過程中一些超常個(gè)體限制其它個(gè)體的進(jìn)化——這個(gè)個(gè)體的適應(yīng)度大大優(yōu)于種群內(nèi)的其它值，由于適者生存原則這個(gè)個(gè)體被不斷復(fù)制從而充滿了整個(gè)種群，使得種群的多樣應(yīng)大大降低，進(jìn)化停滯，從而出現(xiàn)算法收斂于局部最優(yōu)解的現(xiàn)象，稱為早熟現(xiàn)象。早熟現(xiàn)象的可能解法： 1）通過提高變異率來增加種群的多樣性，以期更優(yōu)解的出現(xiàn)，這也是最簡單基本遺傳算法中不添加相關(guān)操作的情況下唯一的一種方法，然而這種方法有明顯的弊端：在提高變異率獲得多樣性種群的同時(shí)，個(gè)體變異的機(jī)會(huì)增加，使得較優(yōu)解發(fā)生變異，從而遺傳算法喪失了其優(yōu)于其它算法的優(yōu)越性，所以這種方法不是很好地解決方法。2）引入多樣性衡量和處理 基本思路：在出現(xiàn)進(jìn)化停滯現(xiàn)象時(shí)要引入新的個(gè)體來增強(qiáng)種群的多樣性。做法：1,判斷是否達(dá)到早熟現(xiàn)象 對于種群中S個(gè)個(gè)體，判斷等位基因的相等程度，即引入一個(gè)參數(shù)值same,如果same達(dá)到一定的 理論值大小就可以認(rèn)為達(dá)到了早熟現(xiàn)象。 2,早熟現(xiàn)象的處理，即引入新的個(gè)體。 處理過程中應(yīng)該不違反適者生存的原則，所以應(yīng)該保留較好的個(gè)體，所以首先選中適應(yīng)度最小的 個(gè)體執(zhí)行刪除操作，然后隨機(jī)生成一個(gè)新的符合重量限制且打破早熟現(xiàn)象的新個(gè)體。 具體實(shí)現(xiàn)見函數(shù)：void checkalike(void) //相似度校驗(yàn) for(i=0;i for(j=0;j if(temp!=X[k].chromsome[j]) break;if(j==N)same++;if(same>N*0.5)//大于50%作為判定為早熟 //確定最小 int minindex=0;for(intn=0;n if(X[n].fitness bool m=(rand()%10<5)?0:1;X[minindex].chromsome[j]=m;X[minindex].weight+=m*weight[j];//個(gè)體的總重量 X[minindex].fitness+=m*value[j]; //個(gè)體的總價(jià)值 2.一種最優(yōu)解只向更好進(jìn)化方法的嘗試 基本思路為：每一組的最優(yōu)解是一個(gè)獨(dú)特的個(gè)體，我們求解的問題最終的最優(yōu)解或者近似解都產(chǎn)生于這個(gè)特殊的個(gè)體，最優(yōu)解只向更好進(jìn)化方法中規(guī)定：每代中選出一個(gè)最優(yōu)解并做好相應(yīng)的記錄或者標(biāo)記，最優(yōu)解參與交叉和變異，只是在交叉或者變異時(shí)對最優(yōu)解進(jìn)行前后適應(yīng)度的比較，如果發(fā)現(xiàn)交叉或者變異后適應(yīng)度大于操作前適應(yīng)度，則保存操作后的結(jié)果，如果發(fā)現(xiàn)交叉或者變異后適應(yīng)度小于操作前適應(yīng)度，則禁止最優(yōu)解的操作，而不禁止與最優(yōu)解進(jìn)行交叉的個(gè)體的變化。這樣，每一代中的最優(yōu)解的特性可以通過交叉?zhèn)鬟f給同代中的其它個(gè)體，而保證種群一定會(huì)向更好的方向進(jìn)化。做法在交叉后和變異后調(diào)用以下函數(shù)判斷： int comp(individual bestindividual,individual temp)//比較函數(shù) { } int fit=0,w=0;//第一種不變:操作后不滿足重量函數(shù)，第二種:操作后適應(yīng)度小于操作前 for(int i=0;i 五、改進(jìn)的遺傳算法解決0-1背包問題： 1、參數(shù)設(shè)置： #define S 500 #define Pc 0.8 #define Pm 0.01 #define KW 878 #define N #define T 1000 //種群的規(guī)模 //交叉概率 //突變概率 //背包最大載重 //物體總數(shù) //最大換代數(shù) 2個(gè)體的表示和染色體編碼 用變量i代表物件, i = 1, 2, ,n 定義變量xi，其含義為： xi= 1表示：第i個(gè)物件被選入背包, xi = 0表示第i個(gè)物件沒有被選入背包。考慮n 個(gè)物件的選擇與否, 就可以得到一個(gè)長度為n的0, 1序列。由此可見遺傳算法應(yīng)用于上述背包問題時(shí),采用簡單二進(jìn)制編碼較為適宜1 每一組編碼即為某一個(gè)個(gè)體的基因表示, 稱其為染色體, 染色體長度取決于待分配的物件的個(gè)數(shù)n.在編碼形式的表示方法中,形如二進(jìn)制編碼 10010101 表示為一個(gè)待分配的物件的個(gè)數(shù)為8（編碼長度）的一個(gè)背包問題的一個(gè)解, 則該個(gè)體對應(yīng)于選擇了物件1, 4, 6, 8，即第1, 4, 6, 8個(gè)物品被放入了背包。用數(shù)據(jù)格式表示為： struct individual { bool chromsome[N];double fitness; double weight;}; //個(gè)體結(jié)構(gòu)體 //染色體編碼 //適應(yīng)度//即本問題中的個(gè)體所得價(jià)值 //總重量 2產(chǎn)生初始種群 n個(gè)待分配的物件隨機(jī)產(chǎn)生S個(gè)長度為n的二進(jìn)制串, 即種群中個(gè)體的染色體編碼的每一位按等概率在0與1中選擇S 指的是種群規(guī)模, 即種群中的個(gè)體數(shù)目.void GenerateInitialPopulation(void);//初始種群 3適應(yīng)度函數(shù) 背包內(nèi)物件的總重量為a1x1 + a2x2 + ,anxn, 物件的總價(jià)值為c1x1 + c2x2 + , + cn xn 0-1背包問題中采用每個(gè)個(gè)體的總價(jià)值作為適應(yīng)度，在滿足背包容量的條件下，價(jià)值越大，適應(yīng)度越高。所以適應(yīng)度求解方法為： f i = c1x1 + c2x2 + , + cnxn(當(dāng)t a1x1 + a2x 2 + , + anxn < = c，xj = 0, 1)考慮到會(huì)有不不滿足容量條件的個(gè)體則： f i = 0(當(dāng)a1x1 + a2x2 + , + anxn > c，xj = 0, 1) 上述適應(yīng)度函數(shù)基于一個(gè)考慮違背約束條件的懲罰處理，根據(jù)上述具體問題適應(yīng)度函數(shù)值不可能為零, 所以當(dāng)隨機(jī)產(chǎn)生的某個(gè)個(gè)體違背約束條件時(shí), 通過把其適應(yīng)度函數(shù)值罰為0而達(dá)到淘汰該個(gè)體的目的。4選擇-復(fù)制操作 參照適應(yīng)度函數(shù)值和約束條件用賭輪選擇法進(jìn)行模擬，具體為: (1)根據(jù)適應(yīng)度函數(shù)值和約束條件, 罰掉部分個(gè)體（前述不滿足容量條件的個(gè)體） (2)對于滿足約束條件的個(gè)體, 根據(jù)適應(yīng)度函數(shù)值計(jì)算個(gè)體被選中的概率,稱為選擇概率： 公式為: P = p()稱為染色體xi(i=1, 2, …, n)的選擇概率 (3)根據(jù)輪盤賭累計(jì)公式為： iq?P(xj) i ? j?1 稱為染色體xi(i=1, 2, …, n)的積累概率 (4)對已得到的累計(jì)概率作如下處理，完成選擇操作： 1）在［0, 1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r。2）若r≤q1,則染色體x1被選中。 3）若qk-1 (1)隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)的位置 (2)隨機(jī)選取當(dāng)前代中的兩個(gè)個(gè)體作為父個(gè)體 (3)根據(jù)交叉點(diǎn)的位置, 做單點(diǎn)交叉 6變異操作: 根據(jù)變異率Pm (1)隨機(jī)產(chǎn)生變異點(diǎn)的位置 (2)在變異點(diǎn)位置作0-1翻轉(zhuǎn) 8、算法終止 程序中定義了一個(gè)最優(yōu)值，stop= 一般情況下這個(gè)最優(yōu)值達(dá)不到，一旦程序在執(zhí)行過程中達(dá)到此最優(yōu)值，也就沒有必要在執(zhí)行下去，因?yàn)檫@必定是最好的解，所以保存最優(yōu)值和最優(yōu)解，結(jié)束。 如果程序的最優(yōu)值達(dá)不到理想情況下的stop，那么根據(jù)最大換代次數(shù)來結(jié)束程序，在結(jié)束后的種群中找到一個(gè)最好的解作為本問題的最優(yōu)解，程序結(jié)束。 4算例 1.小規(guī)模問題的算例： 算例1-1：設(shè)定物品價(jià)值value={50,30,60,80,20}重量weight{35,40,40,20,15}背包的最大承重量為100 遺傳算法中參數(shù)：群體大小S=5，交叉率Pc=0.8,變異率Pm=0.05,最大換代次數(shù)T=20, 通過多次試驗(yàn)比較本文改進(jìn)后遺傳算法和其他得到結(jié)果如下表所示： 本文改進(jìn)的遺傳算法： 實(shí)驗(yàn)總次數(shù)：30 達(dá)到全局最優(yōu)解次數(shù)：27 未達(dá)到全局最優(yōu)解：3 由實(shí)驗(yàn)結(jié)果可知在小規(guī)模算例中，本文改進(jìn)的遺傳算法優(yōu)于前兩者。2．較大規(guī)模問題求解算例： 遺傳算法中參數(shù)： 群體大小S=5，交叉率Pc=0.8,變異率Pm=0.05,最大換代次數(shù)T=800，相似度取5% 實(shí)例1： 價(jià)值value：{ 92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58} 重量weight：{ {44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}} 背包的最大承重量：878 實(shí)例2： 價(jià)值value： {220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88, 82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}; 重量weight: {80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65, 20,25,30,10,20,25,15,10,10,10,4,4,2,1}; 背包最大承重量：1000 本文改進(jìn)遺傳算法實(shí)驗(yàn)結(jié)果： 實(shí)例1： 實(shí)例2： 由此得出結(jié)論：遺傳算法優(yōu)于前兩種。 六.心得體會(huì)： 遺傳算法是一種模擬生物進(jìn)化在解中求解最優(yōu)值的方法，實(shí)現(xiàn)起來方便，適于處理大宗數(shù)據(jù)，然而基于簡單基本遺傳算法在求解不同問題時(shí)應(yīng)該具體問題具體分析，找的結(jié)合所解問題的優(yōu)化方法，例如本文分析的遺傳算法解決0-1背包問題，雖然簡單基本遺傳算法可以求出一個(gè)比較好的解出來，但是分析可知，結(jié)果并不令人滿意，在對問題進(jìn)行細(xì)致的分析、查閱相關(guān)資料和深入思考后，我提出了自己認(rèn)為比較好的改進(jìn)方法并通過實(shí)踐結(jié)合具體的算例把改進(jìn)后的遺傳算法和與原來的簡單遺傳算法和參考文獻(xiàn)中的一種改進(jìn)方法進(jìn)行了比較，結(jié)果顯示本文改進(jìn)的遺傳算法無論在小規(guī)模數(shù)據(jù)處理還是較大規(guī)模數(shù)據(jù)處理方面均優(yōu)于前兩者，這一點(diǎn)很令人高興。通過本次實(shí)踐，我也深刻體會(huì)到對于算法分析和改進(jìn)的重要性，往往一個(gè)算法經(jīng)過認(rèn)真地分析和合理的改進(jìn)后會(huì)獲得性能上的提高時(shí)間復(fù)雜度或者空間復(fù)雜度的降低，而且能夠獲得更好的解。 七.參考文獻(xiàn)： 《用基本遺傳算法解決0-1背包問題》 八.程序?qū)崿F(xiàn)： 已通過vc6.0編譯后運(yùn)行 #include //種群的規(guī)模 #define N //物體總數(shù) #define Pc 0.8 //交叉概率 #define Pm 0.05 //突變概率 #define KW //背包最大載重 #define T //最大換代數(shù) #define ALIKE 0.05 //判定相似度 int stop=0; //初始化函數(shù)中初始化為所有價(jià)值之和 int t=0; //目前的代數(shù) int weight[]={35,40,40,20,15}; //物體重量 int value[]={50,30,60,80,20}; //物體價(jià)值 /*實(shí)例1*********************************************************************** #define S //種群的規(guī)模 #define N //物體總數(shù) #define Pc 0.8 //交叉概率 #define Pm 0.05 //突變概率 #define KW 878 //背包最大載重 #define T 800 //最大換代數(shù) #define ALIKE 0.05 //判定相似度 int stop=0; //初始化函數(shù)中初始化為所有價(jià)值之和 int t=0; //目前的代數(shù) int weight[]={44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63};//物體重量 int value[]={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58};//物體價(jià)值 /*實(shí)例2*********************************************************************** #define S //種群的規(guī)模 #define Pc 0.8 //交叉概率 #define Pm 0.05 //突變概率 #define KW 1000 //背包最大載重1000 #define N //物體總數(shù) #define T 800 //最大換代數(shù) #define ALIKE 0.05 //判定相似度 int stop=0; //初始化函數(shù)中初始化為所有價(jià)值之和 int t=0; //目前的代數(shù) int vaue[]={ 220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1};int weight[]={ 80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,25,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1};/*實(shí)例3***********************************************************************/ #define S //種群的規(guī)模 #define Pc 0.8 //交叉概率 #define Pm 0.05 //突變概率 #define KW 6718 //背包最大載重1000 #define N //物體總數(shù) #define T 800 //最大換代數(shù) #define ALIKE 0.05 //判定相似度 int stop=0; //初始化函數(shù)中初始化為所有價(jià)值之和 int t=0; //目前的代數(shù) int vaue[]={ 597,596,593,586,581,568,567,560,549,548,547,529,529,527,520,491,482,478,475,475,466,462,459,458,454,451,449,443,442,421,410,409,395,394,390,377,375,366,361,347,334,322,315,313,311,309,296,295,294,289,285,279,277,276,272,248,246,245,238,237,232,231,230,225,192,184,183,176,171,169,165,165,154,153,150,149,147,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,27,22,12,6,250};Int weight[]={ 54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,6,140,86,30,91,156,31,70,199,142,98,178,16,140,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,209,164,177,177,129,146,17,53,64,146,43,170,180,171,130,183,5,113,207,57,13,163,20,63,12,24,9,42,6,109,170,108,46,69,43,175,81,5,34,146,148,114,160,174,156,82,47,126,102,83,58,34,21,14};/************************************************************************/ struct individual { //個(gè)體結(jié)構(gòu)體 bool chromsome[N];//染色體編碼 double fitness; //適應(yīng)度//即本問題中的個(gè)體所得價(jià)值 double weight; //總重量 };int best=0;int same=0;individual X[S],Y[S],bestindividual;// /************************************************************************/ int comp(individual bestindividual,individual temp);//比較函數(shù) void checkalike(void); //檢查相似度函數(shù) void GenerateInitialPopulation(void); //初始種群 void CalculateFitnessValue(void); //適應(yīng)度 void SelectionOperator(void); //選擇 void CrossoverOperator(void); //交叉 void MutationOperator(void); //變異 void FindBestandWorstIndividual(void); //尋找最優(yōu)解 void srand(unsigned int seed); //隨機(jī)生成 /************************************************************************/ int comp(individual bestindividual,individual temp)//比較函數(shù) { int fit=0,w=0;//第一種不變:操作后不滿足重量函數(shù)，第二種:操作后適應(yīng)度小于操作前 for(int i=0;i void Checkalike(void){ int i=0,j=0; for(i=0;i if(temp!=X[k].chromsome[j]) break;} } if(j==N)same++;} if(same>N*ALIKE)//大于ALIKE作為判定為早熟 { int minindex=0;for(int n=0;n if(X[n].fitness X[minindex].weight+=m*weight[j];//個(gè)體的總重量 X[minindex].fitness+=m*value[j];//個(gè)體的總價(jià)值 } } } /************************************************************************/ void GenerateInitialPopulation(void)//初始種群,保證每個(gè)值都在符合條件的解 { int i=0,j=0;bool k; for(i=0;i k=(rand()%10<5)?0:1; X[i].chromsome[j]=k; w+=k*weight[j];//個(gè)體的總重量 v+=k*value[j];//個(gè)體的總價(jià)值 } if(w>KW)i--; //如果不是解，重新生成else { X[i].fitness=v;X[i].weight=w; if(v==stop){bestindividual=X[i];return;}//這種情況一般不會(huì)發(fā)生 } } } /************************************************************************/ void CalculateFitnessValue(){ int i=0,j=0; for(i=0;i int w=0,v=0; for(j=0;j { w+=X[i].chromsome[j]*weight[j];//個(gè)體的總重量 v+=X[i].chromsome[j]*value[j];//個(gè)體的總價(jià)值 } X[i].fitness=v; X[i].weight=w; if(v==stop){bestindividual=X[i];return;}//符合條件情況下最優(yōu)解這種情況一般不會(huì)發(fā)生 if(w>KW)X[i]=bestindividual; //如果不是解，找最好的一個(gè)解代之 } } /************************************************************************/ void SelectionOperator(void){ int i, index;double p, sum=0.0;double cfitness[S];//選擇、累積概率 individual newX[S];for(i=0;i for(i=0;i for(i=1;i for(i=0;i p=(rand()%1001)/1000.0;//產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù) index=0; while(p>cfitness[index])//輪盤賭進(jìn)行選擇 { index++; } newX[i]=X[index];} for(i=0;i void CrossoverOperator(void)//交叉操作 { int i=0, j=0,k=0;individual temp; for(i=0;i int p=0,q=0; do { p=rand()%S;//產(chǎn)生兩個(gè)[0，S]的隨機(jī)數(shù) q=rand()%S; }while(p==q); int w=1+rand()%N;//[1,N]表示交換的位數(shù) double r=(rand()%1001)/1000.0;//[0,1] if(r<=Pc) { for(j=0;j { temp.chromsome[j]=X[p].chromsome[j];//將要交換的位先放入臨時(shí)空間 X[p].chromsome[j]=X[q].chromsome[j]; X[q].chromsome[j]=temp.chromsome[j]; } } if(p==best) if(-1==comp(bestindividual,X[p]))//如果變異后適應(yīng)度變小 X[p]=bestindividual; if(q==best) if(-1==comp(bestindividual,X[q]))//如果變異后適應(yīng)度變小 X[q]=bestindividual;} } /************************************************************************/ void MutationOperator(void){ int i=0, j=0,k=0,q=0;double p=0;for(i=0;i { for(j=0;j { p=(rand()%1001)/1000.0; if(p { if(X[i].chromsome[j]==1)X[i].chromsome[j]=0; else X[i].chromsome[j]=1; } } if(i==best) if(-1==comp(bestindividual,X[i]))//如果變異后適應(yīng)度變小 X[i]=bestindividual;} } /************************************************************************/ void FindBestandWorstIndividual(void){ int i;bestindividual=X[0];for(i=1;i if(X[i].fitness>bestindividual.fitness) { bestindividual=X[i]; best=i; } } } /*主函數(shù)*****************************************************************/ void main(void){ srand((unsigned)time(0)); t=0; GenerateInitialPopulation();//初始群體包括產(chǎn)生個(gè)體和計(jì)算個(gè)體的初始值 while(t<=T) { FindBestandWorstIndividual();//保存當(dāng)前最優(yōu)解 SelectionOperator(); //選擇 CrossoverOperator(); //交叉 MutationOperator(); //變異 Checkalike(); //檢查相似度 CalculateFitnessValue();//計(jì)算新種群適應(yīng)度 t++; } FindBestandWorstIndividual(); //找到最優(yōu)解 cout< < for(int k=0;k cout< 讀書的好處 1、行萬里路，讀萬卷書。 2、書山有路勤為徑，學(xué)海無涯苦作舟。 3、讀書破萬卷，下筆如有神。 4、我所學(xué)到的任何有價(jià)值的知識(shí)都是由自學(xué)中得來的。——達(dá)爾文 5、少壯不努力，老大徒悲傷。 6、黑發(fā)不知勤學(xué)早，白首方悔讀書遲。——顏真卿 7、寶劍鋒從磨礪出，梅花香自苦寒來。 8、讀書要三到：心到、眼到、口到 9、玉不琢、不成器，人不學(xué)、不知義。 10、一日無書，百事荒廢。——陳壽 11、書是人類進(jìn)步的階梯。 12、一日不讀口生，一日不寫手生。 13、我撲在書上，就像饑餓的人撲在面包上。——高爾基 14、書到用時(shí)方恨少、事非經(jīng)過不知難。——陸游 15、讀一本好書，就如同和一個(gè)高尚的人在交談——歌德 16、讀一切好書，就是和許多高尚的人談話。——笛卡兒 17、學(xué)習(xí)永遠(yuǎn)不晚。——高爾基 18、少而好學(xué)，如日出之陽；壯而好學(xué)，如日中之光；志而好學(xué)，如炳燭之光。——?jiǎng)⑾?/p> 19、學(xué)而不思則惘，思而不學(xué)則殆。——孔子 20、讀書給人以快樂、給人以光彩、給人以才干。——培根 人工智能原理與應(yīng)用大作業(yè) （1）簡單函數(shù)優(yōu)化的遺傳算法C代碼，把代碼調(diào)通，計(jì)算出結(jié)果。 （2）編程實(shí)現(xiàn)第6章習(xí)題第13題（2個(gè)學(xué)生做） （3）編程實(shí)現(xiàn)第6章習(xí)題第14題（2個(gè)學(xué)生做） （4）寫出調(diào)研報(bào)告“人工智能的發(fā)展歷史” （5）寫出麥卡錫(J.McCarthy)的傳記 （6）寫出明斯基(M.Minsky)的傳記 （7）寫出調(diào)研符號主義學(xué)派的報(bào)告 （8）寫出調(diào)研行為主義學(xué)派的報(bào)告 （9）寫出調(diào)研聯(lián)結(jié)主義學(xué)派的報(bào)告 （10）寫出使用經(jīng)典邏輯推理成功的人工智能案例 （11）寫出使用搜索方法推理成功的人工智能案例 （12）寫出使用遺傳算法推理成功的人工智能案例 （13）寫出使用神經(jīng)網(wǎng)絡(luò)推理成功的人工智能案例 （14）寫出使用專家系統(tǒng)推理成功的人工智能案例 （15）寫出除上面幾種方法以外的人工智能方法的調(diào)研報(bào)告。 （16）編程實(shí)現(xiàn)P132例5.1梵塔問題，畫圖實(shí)現(xiàn)。（由王小高帶2個(gè)學(xué)生做） （17）編程實(shí)現(xiàn)P135例5.3九宮重排問題，采用廣度搜索法。（由張延令帶2個(gè)學(xué)生做） （18）編程實(shí)現(xiàn)P133例5.2傳教士和野人問題，采用廣度搜索法。（由賈路寬帶2個(gè)學(xué)生 做） （19）寫出退火算法的調(diào)研報(bào)告。 （20）寫出蟻群算法的調(diào)研報(bào)告。 （21）寫出人工智能在中國的發(fā)展的調(diào)研報(bào)告。 （22）寫出中國人工智能協(xié)會(huì)的調(diào)研報(bào)告。 （23）寫出機(jī)器學(xué)習(xí)的調(diào)研報(bào)告 （24）寫出搜索引擎的調(diào)研報(bào)告 （25）寫出模式識(shí)別的調(diào)研報(bào)告 （26）人工智能在農(nóng)業(yè)方面的應(yīng)用 （27）人工智能在工業(yè)方面的應(yīng)用 （28）人工智能在軍事方面的應(yīng)用 （29）人工智能在機(jī)器人方面的應(yīng)用 （30）人工智能在航空航天方面的應(yīng)用 （31）人工智能在醫(yī)療方面的應(yīng)用 （32）人工智能在商業(yè)方面的應(yīng)用 （33）人工智能在電力業(yè)方面的應(yīng)用第五篇：人工智能原理與應(yīng)用大作業(yè)
點(diǎn)擊咨詢 