智能算法簡(jiǎn)單介紹

智能算法智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第1頁(yè)。2課程名稱智能算法教師聯(lián)系方式辦公地點(diǎn)：綜合實(shí)驗(yàn)樓1號(hào)樓610

Tel-mail：jfgu@上課時(shí)間地點(diǎn)（10-17周）

周三3－4節(jié)，綜362

周五7－8節(jié)，綜362教學(xué)信息智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第2頁(yè)。3課程目標(biāo)

1）掌握智能算法的基本概念和原理；

2）學(xué)會(huì)用智能算法解決優(yōu)化問(wèn)題。課程重點(diǎn)應(yīng)用領(lǐng)域 組合優(yōu)化課程要求

了解各主要智能算法的起源、原理、操作和應(yīng)用領(lǐng)域

掌握主要智能算法求解優(yōu)化問(wèn)題的流程

學(xué)會(huì)智能算法在實(shí)際中的應(yīng)用課程介紹智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第3頁(yè)。4課程設(shè)計(jì)論文和課上報(bào)告實(shí)現(xiàn)實(shí)際或者虛擬優(yōu)化問(wèn)題的求解。（鼓勵(lì)與實(shí)際問(wèn)題或者本人未來(lái)研究領(lǐng)域的結(jié)合）在網(wǎng)上下載（一種或多種）智能優(yōu)化程序；如果自己編程實(shí)現(xiàn)更好，(加分)；如果對(duì)網(wǎng)上下載程序或自己的編程進(jìn)行了某種算法上的改進(jìn)也很好（加分）。論文要求：將要優(yōu)化的問(wèn)題、所用智能優(yōu)化方法、計(jì)算結(jié)果及對(duì)結(jié)果的簡(jiǎn)單分析寫成論文，論文格式見(jiàn)樣板論文。報(bào)告要求：簡(jiǎn)要說(shuō)清所要解決問(wèn)題以及所用方法和計(jì)算結(jié)果。(ppt)課程考核智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第4頁(yè)。5課程內(nèi)容§1緒論§2遺傳算法（1）§3遺傳算法（2）§4人工神經(jīng)網(wǎng)絡(luò)§5模擬退火算法§6群智能算法（粒子群，蟻群）§7模糊邏輯§8課程匯報(bào)

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第5頁(yè)。6AndriesP.Engelbrecht,ComputationalIntelligence:AIntroduction,Wiley,NewYork,2002.ISBN0-470-84870-7.丁永生編著，《計(jì)算智能——理論、技術(shù)與應(yīng)用》，科學(xué)出版社，2004.8.ISBN7-03-013902-X.P.481.(TP183/27)褚蕾蕾，陳綏陽(yáng)，周夢(mèng)編著，《計(jì)算智能的數(shù)學(xué)基礎(chǔ)》，科學(xué)出版社，2002.(TP183/15)徐宗本，張講社，鄭亞林，編著，《計(jì)算智能中的仿生學(xué)：理論與算法》，科學(xué)出版社，2003.5，ISBN7-03-010792-6.P.315.(TP183/17)徐宗本，編著，《計(jì)算智能（第一冊(cè)）---模擬進(jìn)化計(jì)算》，高等教育出版社，2004.2，ISBN7-04-013839-5.P.141.王國(guó)俊，編著，《計(jì)算智能（第二冊(cè)）---詞語(yǔ)計(jì)算與Fuzzy集》，高等教育出版社，2005.2，ISBN7-04-016032-3.P.106.(TP183/31:2)羅四維，著，《大規(guī)模人工神經(jīng)網(wǎng)絡(luò)理論基礎(chǔ)》，清華大學(xué)出版社和北方交通大學(xué)出版社，2004.2，ISBN7-81082-174-1.P.177.課程參考書智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第6頁(yè)。7課程參考書HaykinS.NeuralNetworks:AComprehensiveFoundation,Macmillan,IEEEPress,1994.張乃堯、閻平凡編著，《神經(jīng)網(wǎng)絡(luò)與模糊控制》，清華大學(xué)出版社，2002。王小平，曹立明編著，《遺傳算法--理論、應(yīng)用與軟件實(shí)現(xiàn)》，西安交通大學(xué)出版社，2002.1。張穎，劉艷秋等，《軟計(jì)算方法》，科學(xué)出版社，2002。谷荻隆嗣等，《人工神經(jīng)網(wǎng)絡(luò)與模糊信號(hào)處理》，科學(xué)出版社，2003。李士勇等，《蟻群算法及其應(yīng)用》哈爾濱工業(yè)大學(xué)出版社，2004.9陳國(guó)良、王煦法、莊鎮(zhèn)權(quán)等，《遺傳算法及其應(yīng)用》，人民郵電出版社，1995。史忠植，《知識(shí)發(fā)現(xiàn)》，清華大學(xué)出版社，2002。傅京孫等，《人工智能及其應(yīng)用》，清華大學(xué)出版社，1987。蔡自興、徐光佑，《人工智能及其應(yīng)用》清華大學(xué)出版社，1996蔡自興，《智能控制---基礎(chǔ)與應(yīng)用》，國(guó)防工業(yè)出版社，1998。劉金琨編著，《智能控制》，電子工業(yè)出版社，2005.5。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第7頁(yè)。8第一章緒論

智能算法智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第8頁(yè)。9提綱1.1

智能算法1.2

優(yōu)化的概念1.3

優(yōu)化算法1.4

計(jì)算復(fù)雜性1.5

本章小結(jié)智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第9頁(yè)。101.1什么是智能？從感覺(jué)到記憶到思維這一過(guò)程，稱為“智慧”，智慧的結(jié)果就產(chǎn)生了行為和語(yǔ)言，將行為和語(yǔ)言的表達(dá)過(guò)程稱為“能力”，兩者合稱“智能”，將感覺(jué)、去記、回憶、思維、語(yǔ)言、行為的整個(gè)過(guò)程稱為智能過(guò)程，它是智力和能力的表現(xiàn)。它們分別又可以用“智商”和“能商”來(lái)描述其在個(gè)體中發(fā)揮智能的程度。“情商”可以調(diào)整智商和能商的正確發(fā)揮，或控制二者恰到好處地發(fā)揮它們的作用。智能及智能的本質(zhì)是古今中外許多哲學(xué)家、腦科學(xué)家一直在努力探索和研究的問(wèn)題，但至今仍然沒(méi)有完全了解，以致智能的發(fā)生與物質(zhì)的本質(zhì)、宇宙的起源、生命的本質(zhì)一起被列為自然界四大奧秘。近年來(lái)，隨著腦科學(xué)、神經(jīng)心理學(xué)等研究的進(jìn)展，人們對(duì)人腦的結(jié)構(gòu)和功能有了初步認(rèn)識(shí)，但對(duì)整個(gè)神經(jīng)系統(tǒng)的內(nèi)部結(jié)構(gòu)和作用機(jī)制，特別是腦的功能原理還沒(méi)有認(rèn)識(shí)清楚，有待進(jìn)一步的探索。因此，很難對(duì)智能給出確切的定義。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第10頁(yè)。111.1智能的分類根據(jù)加德納的多元智能理論，人類的智能可以分成八個(gè)范疇：

1、語(yǔ)言智能

(Linguisticintelligence）

是指有效的運(yùn)用口頭語(yǔ)言或及文字表達(dá)自己的思想并理解他人，靈活掌握語(yǔ)音、語(yǔ)義、語(yǔ)法，具備用言語(yǔ)思維、用言語(yǔ)表達(dá)和欣賞語(yǔ)言深層內(nèi)涵的能力結(jié)合在一起并運(yùn)用自如的能力。他們適合的職業(yè)是：政治活動(dòng)家，主持人，律師，演說(shuō)家，編輯，作家，記者，教師等。

2、數(shù)學(xué)邏輯智能

(Logical-Mathematicalintelligence)

是指有效地計(jì)算、測(cè)量、推理、歸納、分類，并進(jìn)行復(fù)雜數(shù)學(xué)運(yùn)算的能力。這項(xiàng)智能包括對(duì)邏輯的方式和關(guān)系，陳述和主張，功能及其他相關(guān)的抽象概念的敏感性。他們適合的職業(yè)是：科學(xué)家、會(huì)計(jì)師、統(tǒng)計(jì)學(xué)家、工程師、電腦軟體研發(fā)人員等。

3、空間智能

(Spatialintelligence)

是指準(zhǔn)確感知視覺(jué)空間及周圍一切事物，并且能把所感覺(jué)到的形象以圖畫的形式表現(xiàn)出來(lái)的能力。這項(xiàng)智能包括對(duì)色彩、線條、形狀、形式、空間關(guān)系很敏感。他們適合的職業(yè)是：室內(nèi)設(shè)計(jì)師、建筑師、攝影師、畫家、飛行員等。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第11頁(yè)。121.1智能的分類

4、身體運(yùn)動(dòng)智能

(Bodily-Kinestheticintelligence)

是指善于運(yùn)用整個(gè)身體來(lái)表達(dá)思想和情感、靈巧地運(yùn)用雙手制作或操作物體的能力。這項(xiàng)智能包括特殊的身體技巧，如平衡、協(xié)調(diào)、敏捷、力量、彈性和速度以及由觸覺(jué)所引起的能力。他們適合的職業(yè)是：運(yùn)動(dòng)員、演員、舞蹈家、外科醫(yī)生、寶石匠、機(jī)械師等。

5、音樂(lè)智能

(Musicalintelligence)

是指人能夠敏銳地感知音調(diào)、旋律、節(jié)奏、音色等能力。這項(xiàng)智能對(duì)節(jié)奏、音調(diào)、旋律或音色的敏感性強(qiáng)，與生俱來(lái)就擁有音樂(lè)的天賦，具有較高的表演、創(chuàng)作及思考音樂(lè)的能力。他們適合的職業(yè)是：歌唱家、作曲家、指揮家、音樂(lè)評(píng)論家、調(diào)琴師等。

6、人際智能

(Interpersonalintelligence)是指能很好地理解別人和與人交往的能力。這項(xiàng)智能善于察覺(jué)他人的情緒、情感，體會(huì)他人的感覺(jué)感受，辨別不同人際關(guān)系的暗示以及對(duì)這些暗示做出適當(dāng)反應(yīng)的能力。他們適合的職業(yè)是：政治家、外交家、領(lǐng)導(dǎo)者、心理咨詢師、公關(guān)人員、推銷等。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第12頁(yè)。131.1智能的分類

7、自我認(rèn)知智能

(Intrapersonalintelligence)

是指自我認(rèn)識(shí)和善于自知之明并據(jù)此做出適當(dāng)行為的能力。這項(xiàng)智能能夠認(rèn)識(shí)自己的長(zhǎng)處和短處，意識(shí)到自己的內(nèi)在愛(ài)好、情緒、意向、脾氣和自尊，喜歡獨(dú)立思考的能力。他們適合的職業(yè)是：哲學(xué)家、政治家、思想家、心理學(xué)家等。

8、自然認(rèn)知智能

(Naturalistintelligence)

是指善于觀察自然界中的各種事物，對(duì)物體進(jìn)行辨別和分類的能力。這項(xiàng)智能有著強(qiáng)烈的好奇心和求知欲，有著敏銳的觀察能力，能了解各種事物的細(xì)微差別。他們適合的職業(yè)是：天文學(xué)家、生物學(xué)家、地質(zhì)學(xué)家、考古學(xué)家、環(huán)境設(shè)計(jì)師等。智能是指?jìng)€(gè)體對(duì)客觀事物進(jìn)行合理分析、判斷及有目的地行動(dòng)和有效地處理周圍環(huán)境事宜的綜合能力。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第13頁(yè)。14智能的三個(gè)層次：（1994年，JamesC.Bezdek）

生物智能（BiologicalIntelligence,BI）：由人腦的物理化學(xué)過(guò)程反映出來(lái)的，人腦是有機(jī)物，它是智能的基礎(chǔ)；人工智能（ArtificialIntelligence,AI）：是非生物的，人造的，常用符號(hào)來(lái)表示，AI的來(lái)源是人類知識(shí)的精華。計(jì)算智能（ComputationalIntelligence,CI）：是由數(shù)學(xué)方法和計(jì)算機(jī)實(shí)現(xiàn)的，CI的來(lái)源是數(shù)值計(jì)算的傳感器。

從復(fù)雜性看：

BI>AI>CIAI是CI到BI的過(guò)渡，因?yàn)锳I中除計(jì)算算法之外，還包括符號(hào)表示及數(shù)值信息處理。模糊集合和模糊邏輯是AI到CI的過(guò)渡。1.1智能的層次智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第14頁(yè)。151.1人工智能什么是人工智能？ 能力方面

人工智能就是用人工的方法在機(jī)器（計(jì)算機(jī)）上實(shí)現(xiàn)的智能，或稱機(jī)器智能 學(xué)科方面

是一門研究如何構(gòu)造智能機(jī)器或智能系統(tǒng)，以模擬、延伸和擴(kuò)展人類智能的學(xué)科AI的主要研究和應(yīng)用領(lǐng)域

機(jī)器思維、機(jī)器感知、機(jī)器行為、計(jì)算智能、機(jī)器學(xué)習(xí)、分布智能、智能系統(tǒng)、人工心理與人工情感、人工生命、人工智能的典型應(yīng)用智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第15頁(yè)。161.1計(jì)算智能與人工智能計(jì)算智能和人工智能的聯(lián)系從關(guān)系上說(shuō)，計(jì)算智能屬于人工智能的一個(gè)分支人工智能(AI)符號(hào)主義AI起源于數(shù)理邏輯，人類認(rèn)知的基元是符號(hào)，認(rèn)知過(guò)程是符號(hào)表示上的一種運(yùn)算行為主義AI起源于控制論，智能取決于感知和行為，取決于對(duì)外界復(fù)雜環(huán)境的適應(yīng)，而不是推理聯(lián)結(jié)主義AI起源于仿生學(xué)，特別是人腦模型，人類認(rèn)知的基元是神經(jīng)元，認(rèn)知過(guò)程是神經(jīng)元的連接活動(dòng)過(guò)程智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第16頁(yè)。171.1計(jì)算智能計(jì)算智能（ComputationalIntelligence，CI）是從模擬自然界生物體系和人類智能現(xiàn)象發(fā)展而來(lái)，用計(jì)算機(jī)模擬和再現(xiàn)自然界的某些智能行為，并用于改造自然的工程實(shí)踐的算法總稱，是一種新型人工智能研究領(lǐng)域，也稱為智能算法。計(jì)算智能的三大基本領(lǐng)域包括神經(jīng)計(jì)算、進(jìn)化計(jì)算、模糊計(jì)算。

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第17頁(yè)。181.1計(jì)算智能的分類計(jì)算智能進(jìn)化計(jì)算：神經(jīng)計(jì)算：模糊計(jì)算：?jiǎn)吸c(diǎn)搜索：遺傳算法（進(jìn)化策略，進(jìn)化規(guī)劃）蟻群優(yōu)化算法粒子群優(yōu)化算法免疫算法分布估計(jì)算法Memetic算法…人工神經(jīng)網(wǎng)絡(luò)模糊邏輯模擬退火算法禁忌搜索算法…智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第18頁(yè)。191.1計(jì)算智能研究領(lǐng)域的主要特點(diǎn)研究領(lǐng)域主要特點(diǎn)進(jìn)化計(jì)算模仿生物進(jìn)化過(guò)程和群體智能過(guò)程，模擬大自然的智慧；提供進(jìn)行隨機(jī)搜索和優(yōu)化的能力人工神經(jīng)網(wǎng)絡(luò)模仿人腦的生理構(gòu)造和信息處理的過(guò)程，模擬人類的智慧；提供系統(tǒng)學(xué)習(xí)和適應(yīng)的能力模糊邏輯模仿人類語(yǔ)言和思維中的模糊性概念，模擬人類的智慧；提供處理非精確性和進(jìn)行近似推理的能力智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第19頁(yè)。201.1計(jì)算智能發(fā)展歷程起步階段1950-1969發(fā)展階段1970-1989繼續(xù)發(fā)展1990年之后（1）50年代，美國(guó)學(xué)者Holland，遺傳算法（2）60年代，德國(guó)人Rechenberg和Schwefel，進(jìn)化策略（3）60年代，美國(guó)學(xué)者Fogel，進(jìn)化規(guī)劃（4）50年代，Rosenblatt等人，感知器（神經(jīng)網(wǎng)絡(luò)）（5）60年代，Zadeh，模糊邏輯理論（1）遺傳算法、進(jìn)化策略、進(jìn)化規(guī)劃的理論基礎(chǔ)不斷完善（模式定理），算法之間的區(qū)別越來(lái)越不明顯（2）80年代，模擬退火算法（1983年）、禁忌搜索算法（1986）的提出提供了新的優(yōu)化手段（3）Hopfield前饋型神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)（1982年）、Rumelhart后向傳播學(xué)習(xí)算法（1986年）的提出將神經(jīng)網(wǎng)絡(luò)的研究推向一個(gè)新的學(xué)習(xí)高潮（1）遺傳算法（GA）、進(jìn)化策略（ES）和進(jìn)化規(guī)劃（EP）算法也在不斷的發(fā)展和完美（2）1992年，Dorigo等人提出了蟻群算法（ACO），為解決離散組合優(yōu)化問(wèn)題提供了重要的工具（3）1995年，在Eberhart和Kennedy提出的粒子群優(yōu)化算法（PSO）在連續(xù)優(yōu)化問(wèn)題上得到了廣泛的應(yīng)用智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第20頁(yè)。211.1計(jì)算智能的特征主要特征具體特點(diǎn)智能性包括算法的自適應(yīng)性、自組織性，算法不依賴問(wèn)題本身的特點(diǎn)，具有通用性并行性算法基本上是以群體協(xié)作的方式對(duì)問(wèn)題進(jìn)行優(yōu)化求解，非常適合大規(guī)模并行處理健壯性算法具有很好的容錯(cuò)性，同時(shí)對(duì)初始條件不敏感，能在不同條件下尋找最優(yōu)解智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第21頁(yè)。221.1計(jì)算智能的應(yīng)用已應(yīng)用在優(yōu)化計(jì)算、模式識(shí)別、圖像處理、自動(dòng)控制、經(jīng)濟(jì)管理、機(jī)械工程、電氣工程、通信網(wǎng)絡(luò)和分子生物學(xué)等多個(gè)領(lǐng)域，涉及國(guó)防、科技、經(jīng)濟(jì)、工業(yè)和農(nóng)業(yè)等各個(gè)方面計(jì)算智能的主要應(yīng)用國(guó)防科技經(jīng)濟(jì)工業(yè)農(nóng)業(yè)雷達(dá)天線設(shè)計(jì)衛(wèi)星軌道參數(shù)優(yōu)化戰(zhàn)場(chǎng)模擬軍事物流優(yōu)化干擾抑制…機(jī)器學(xué)習(xí)數(shù)據(jù)挖掘圖像處理模式識(shí)別蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)多目標(biāo)優(yōu)化多播路由…金融數(shù)據(jù)分析證券投資組合企業(yè)現(xiàn)金流管理企業(yè)財(cái)務(wù)分析與預(yù)警…功率電子電路優(yōu)化電磁過(guò)濾輸電網(wǎng)規(guī)劃工作流調(diào)度管理車輛路由交通控制…排灌工程水利水電工程溫室控制水庫(kù)防洪農(nóng)業(yè)工程…智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第22頁(yè)。23優(yōu)化問(wèn)題的數(shù)學(xué)形式為：1.2優(yōu)化問(wèn)題的定義如果沒(méi)有約束，則最優(yōu)化問(wèn)題稱為無(wú)約束最優(yōu)化問(wèn)題X

設(shè)計(jì)變量；f

目標(biāo)函數(shù)；g,h

約束函數(shù)什么是優(yōu)化？就是從各種方案中選取一個(gè)最好的。從數(shù)學(xué)角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)點(diǎn)。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第23頁(yè)。24根據(jù)決策變量xi的取值類型

函數(shù)優(yōu)化組合優(yōu)化混合型優(yōu)化問(wèn)題1.2優(yōu)化問(wèn)題的分類分類標(biāo)志變量個(gè)數(shù)變量性質(zhì)約束條件極值個(gè)數(shù)目標(biāo)個(gè)數(shù)函數(shù)關(guān)系問(wèn)題性質(zhì)時(shí)間變化類型單變量連續(xù)無(wú)約束單峰單目標(biāo)線性確定性靜態(tài)離散隨機(jī)性多變量混合有約束多峰多目標(biāo)非線性模糊性動(dòng)態(tài)智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第24頁(yè)。251.2函數(shù)優(yōu)化問(wèn)題函數(shù)優(yōu)化問(wèn)題對(duì)應(yīng)的決策變量均為連續(xù)變量，優(yōu)化問(wèn)題f的目標(biāo)函數(shù)取決于其對(duì)應(yīng)的連續(xù)變量x1,

x2,…,xn的取值。各個(gè)取值變量可能是獨(dú)立的，也可能是互相關(guān)聯(lián)、互相制約的，他們的取值組合構(gòu)成了一個(gè)問(wèn)題的解。由于決策變量是連續(xù)值，因此對(duì)每個(gè)變量進(jìn)行枚舉是不可能的。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第25頁(yè)。26Benchmark問(wèn)題典型特點(diǎn)單極小非凸非線性多極小高維強(qiáng)振蕩噪聲不可微1.2函數(shù)優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第26頁(yè)。271.2函數(shù)優(yōu)化問(wèn)題

測(cè)試函數(shù)（Benchmark問(wèn)題）（1）SphereModel

其最優(yōu)狀態(tài)和最優(yōu)值為智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第27頁(yè)。28測(cè)試函數(shù)（2）Schwefel’sProblem2.22

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第28頁(yè)。29測(cè)試函數(shù)（3）Schwefel’sProblem1.2

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第29頁(yè)。30測(cè)試函數(shù)（4）Schwefel’sProblem2.21

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第30頁(yè)。31測(cè)試函數(shù)（5）GeneralizedRosenbrock’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第31頁(yè)。32測(cè)試函數(shù)（6）QuarticFunctioni.e.Niose

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第32頁(yè)。33測(cè)試函數(shù)（7）GeneralizedSchwefel’sProblem2.26

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第33頁(yè)。34測(cè)試函數(shù)（7）GeneralizedSchwefel’sProblem2.26

1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第34頁(yè)。35測(cè)試函數(shù)（8）GeneralizedRastrigin’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第35頁(yè)。36測(cè)試函數(shù)（9）Ackley’sFunction

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第36頁(yè)。37測(cè)試函數(shù)（9）Ackley’sFunction

1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第37頁(yè)。38測(cè)試函數(shù)（10）GeneralizedGriewankFunction

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第38頁(yè)。39測(cè)試函數(shù)（10）GeneralizedGriewankFunction

1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第39頁(yè)。40測(cè)試函數(shù)（11）Six-HumpCamel-BackFunction

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第40頁(yè)。41測(cè)試函數(shù)（12）BraninFunction

其最優(yōu)狀態(tài)和最優(yōu)值為1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第41頁(yè)。42測(cè)試函數(shù)（13）J.D.Schaffer

其最優(yōu)狀態(tài)和最優(yōu)值為

1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第42頁(yè)。43測(cè)試函數(shù)（22）J.D.Schaffer

此函數(shù)在距全局最優(yōu)點(diǎn)大約3.14范圍內(nèi)存在無(wú)窮多個(gè)局部極小將其包圍，并且函數(shù)強(qiáng)烈振蕩。1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第43頁(yè)。441：圖解法設(shè)計(jì)空間目標(biāo)函數(shù)等值面約束曲面可行設(shè)計(jì)/不可行設(shè)計(jì)可行區(qū)域1.2函數(shù)優(yōu)化問(wèn)題

有約束的函數(shù)優(yōu)化智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第44頁(yè)。45有約束的函數(shù)優(yōu)化

2:解的影響因素：（1）曲面拓?fù)湫再|(zhì)，線性或凸函數(shù)比無(wú)規(guī)律的函數(shù)更容易求解；（2）可行區(qū)域的疏密程度，通常以可行區(qū)域占整個(gè)搜索空間的比值來(lái)度量；（3）整體最優(yōu)解與可行區(qū)域最優(yōu)解之比；（4）在最優(yōu)解處活躍約束的數(shù)目，活躍約束數(shù)目越多則最優(yōu)解離可行區(qū)域的邊界越近。

1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第45頁(yè)。46有約束轉(zhuǎn)化為無(wú)約束的處理1.2函數(shù)優(yōu)化問(wèn)題

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第46頁(yè)。471.2組合優(yōu)化問(wèn)題數(shù)學(xué)表述通俗定義：所謂組合優(yōu)化，是指在離散的、有限的數(shù)學(xué)結(jié)構(gòu)上，尋找一個(gè)（或一組）滿足給定約束條件并使其目標(biāo)函數(shù)值達(dá)到最大或最小的解。組合優(yōu)化問(wèn)題通常帶有大量的局部極值點(diǎn)，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性問(wèn)題。所屬范疇:

涉及離散事件的最優(yōu)編排、分類、次序篩選等問(wèn)題，是運(yùn)籌學(xué)的一個(gè)重要分支。

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第47頁(yè)。48典型問(wèn)題——旅行商問(wèn)題（Travelingsalesmanproblem,TSP）

管梅谷教授1960年首先提出，國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。問(wèn)題描述：一商人去n個(gè)城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第48頁(yè)。491.2組合優(yōu)化問(wèn)題123412181032使得最小.即尋找一個(gè)排列：π(X)={v1，v2，…，vn}，智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第49頁(yè)。50典型問(wèn)題——旅行商問(wèn)題計(jì)算復(fù)雜度：指數(shù)災(zāi)難城市數(shù)2425262728293031計(jì)算時(shí)間1sec24sec10min4.3hour4.9day136.5day10.8year325year1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第50頁(yè)。51典型問(wèn)題——加工調(diào)度問(wèn)題（Schedulingproblem）

Job-shop：n個(gè)不同的工件在m臺(tái)不同機(jī)器上加工，已知第i個(gè)工件在第j臺(tái)機(jī)器上的操作時(shí)間為Tij。事先給定各工件在各機(jī)器上的加工次序（技術(shù)約束條件），要求確定與技術(shù)約束條件相容的各機(jī)器上所有工件加工順序，使得加工所有工件的性能指標(biāo)達(dá)到最優(yōu)（或時(shí)間最小）

對(duì)工件和機(jī)器的約束：(1)一個(gè)工件不能兩次訪問(wèn)同一機(jī)器；(2)不同工件的工序之間沒(méi)有先后約束；(3)工序一旦進(jìn)行不能中斷；(4)每臺(tái)機(jī)器一次只能加工一個(gè)工件。1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第51頁(yè)。52典型問(wèn)題——0－1背包問(wèn)題（Knapsackproblem）對(duì)于n個(gè)體積為ai、價(jià)值分別為ci的物品，如何將它們裝入總體積為b的背包中，使得所選物品的總價(jià)值最大。數(shù)學(xué)表達(dá)式：1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第52頁(yè)。53典型問(wèn)題——裝箱問(wèn)題（Binpackingproblem）有n個(gè)尺寸為c的箱子，有n個(gè)體積分別為wj（不超過(guò)c）的物品,

如何將這些物品裝入箱子，使得所需箱子的個(gè)數(shù)最少。i為箱子下標(biāo)；j為物品的下標(biāo)。1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第53頁(yè)。54典型問(wèn)題——圖著色問(wèn)題（Graphcoloringproblem）對(duì)于n個(gè)頂點(diǎn)的無(wú)環(huán)圖G，要求對(duì)其各個(gè)頂點(diǎn)進(jìn)行著色，使得任意兩個(gè)相鄰的頂點(diǎn)都有不同的顏色，且所用顏色種類最少。C1：第一種顏色C2：第二種顏色C3：第三種顏色C1C1C2C3C2ABDCE1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第54頁(yè)。55典型問(wèn)題——圖著色問(wèn)題（Graphcoloringproblem）

西澳大利亞北領(lǐng)地南澳大利亞昆士蘭新南威爾士維多利亞塔斯馬尼亞澳大利亞圖形著色問(wèn)題：1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第55頁(yè)。56典型問(wèn)題—圖著色問(wèn)題

中國(guó)政區(qū)圖２３個(gè)?。祩€(gè)自治區(qū)４個(gè)直轄市２個(gè)特別行政區(qū)

1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第56頁(yè)。57典型問(wèn)題——聚類問(wèn)題（Clusteringproblem）

m維空間上的n個(gè)模式{Xi|i=1,2,…,n}，要求聚成k類，使得各類本身內(nèi)的點(diǎn)最相近，如要求其中Rp為第p類的中心，即

其中，p=1,2,…,k，np為第p類中的點(diǎn)數(shù)。1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第57頁(yè)。58典型問(wèn)題——聚類問(wèn)題

選址問(wèn)題：設(shè)要選定一個(gè)供應(yīng)中心的位置,這個(gè)供應(yīng)中心為城市中有固定位置的m個(gè)用戶服務(wù)。供應(yīng)中心的定位準(zhǔn)則是使中心到用戶的某個(gè)距離函數(shù)值最小。如何選定供應(yīng)中心的位置,使其到各個(gè)用戶的距離總和S最小或者最大距離d最小。

,供應(yīng)中心位置為：設(shè)m個(gè)用戶的位置分別為：OR1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第58頁(yè)。59Benchmark問(wèn)題

n城市TSP問(wèn)題（n=30，50，75）

Hopfield-10城市TSP問(wèn)題

Grotschel-442城市TSP問(wèn)題

CarnFlow-shop問(wèn)題（n=1,2,…,8）

RecnFlow-shop問(wèn)題（n=1,3,5,…,39,41）

FTnorMTnJob-shop問(wèn)題（n=6,10,20）

LAnJob-shop問(wèn)題（n=1,6,11,16,21,26,31,36）1.2組合優(yōu)化問(wèn)題智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第59頁(yè)。601.3優(yōu)化算法優(yōu)化算法定義 所謂優(yōu)化算法,其實(shí)就是一種搜索過(guò)程或規(guī)則,它基于某種原理和機(jī)制,通過(guò)一定的途徑或規(guī)則來(lái)得到滿足用戶要求的問(wèn)題的解.優(yōu)化算法分類局部?jī)?yōu)化算法 又可以稱為經(jīng)典優(yōu)化算法，已經(jīng)得到了人們廣泛深入的研究。目前，運(yùn)籌學(xué)（確定論方法）主要包括這些方面的內(nèi)容，線性規(guī)劃、整數(shù)規(guī)劃、0–1規(guī)劃、非線性規(guī)劃、排隊(duì)論、決策論。全局性優(yōu)化算法

習(xí)慣上稱為智能優(yōu)化算法，是20世紀(jì)80年代興起的新型全局性優(yōu)化算法，主要包括禁忌搜索、模擬退火、遺傳算法等，其主要應(yīng)用對(duì)象是優(yōu)化問(wèn)題中的難解問(wèn)題，即NP–hard問(wèn)題。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第60頁(yè)。611.3優(yōu)化算法經(jīng)典算法經(jīng)典優(yōu)化算法主要用于解決凸問(wèn)題或單峰問(wèn)題，通常使用確定性搜索策略，其基本思想是在狀態(tài)轉(zhuǎn)移過(guò)程中，只接受更好的狀態(tài)，拒絕惡化的狀態(tài)。線性問(wèn)題：?jiǎn)渭冃畏āE球算法（多項(xiàng)式算法），內(nèi)點(diǎn)法；無(wú)約束的優(yōu)化算法包括：最速下降法、共軛梯度法、牛頓法、擬牛頓法、信賴域法。約束優(yōu)化算法包括：拉格朗日乘子法，序列二次規(guī)劃等。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第61頁(yè)。621.3最速下降法見(jiàn)右圖。局部極小值是C點(diǎn)(x0)梯度，即導(dǎo)數(shù)，但是有方向，是一個(gè)矢量。曲線情況下，表達(dá)式為如果，f’(x)>0，則x增加，y也增加，相當(dāng)于B點(diǎn)；如果f’(x)<0，則x增加，y減小，相當(dāng)于A點(diǎn)。要搜索極小值C點(diǎn)，在A點(diǎn)必須向x增加方向搜索，此時(shí)與A點(diǎn)梯度方向相反；在B點(diǎn)必須向x減小方向搜索，此時(shí)與B點(diǎn)梯度方向相反?？傊?，搜索極小值，必須向負(fù)梯度方向搜索。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第62頁(yè)。631.3最速下降法一般情況下分析：

y=f(x1,x2,…,xn)假設(shè)只有一個(gè)極小點(diǎn)。初始給定參數(shù)為(x10,x20,…,xn0)。問(wèn)題：從這個(gè)點(diǎn)如何搜索才能找到原函數(shù)的極小值點(diǎn)？智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第63頁(yè)。641.3最速下降法步驟：

1、首先設(shè)定兩個(gè)較小的正數(shù),;2、求當(dāng)前位置處的各個(gè)偏導(dǎo)數(shù)：dy/dx1,dy/dx2,…,dy/dxn;3、按照下述方式修改當(dāng)前函數(shù)的參數(shù)值：

x11x10dy/dx1,x21x20dy/dx2,…,xn1xn0dy/dxn;4、如果超曲面參數(shù)變化量小于，退出；否則返回2。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第64頁(yè)。651.3最速下降法計(jì)算過(guò)程： 任給一個(gè)初始出發(fā)點(diǎn)，設(shè)為x0=-4 (1)首先給定兩個(gè)參數(shù)：=1.5，=0.01；

(2)計(jì)算導(dǎo)數(shù)：dy/dx=x-2 (3)計(jì)算當(dāng)前導(dǎo)數(shù)值：y’=-6 (4)修改當(dāng)前參數(shù)：

x0=-4x1=x0-*y’ =-4-1.5*(-6)=5.0;x0x1智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第65頁(yè)。661.3最速下降法(5)計(jì)算當(dāng)前導(dǎo)數(shù)值：y’=3.0(6)修改當(dāng)前參數(shù)：

x1=5.0x2=5.0–1.5*(3.0) =0.5;(7)計(jì)算當(dāng)前導(dǎo)數(shù)值：

y’=-1.5(8)修改當(dāng)前參數(shù)：

x2=0.5x3=0.5-1.5*(-1.5)=2.75;x0x1x2x3智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第66頁(yè)。671.3最速下降法(9)計(jì)算當(dāng)前導(dǎo)數(shù)值：y’=0.75(10)修改當(dāng)前參數(shù)：

x3=2.75x4=2.75-1.5*(0.75)=1.625;(11)計(jì)算當(dāng)前導(dǎo)數(shù)值：

y’=-0.375(12)修改當(dāng)前參數(shù)：

x4=1.625x5=1.625-1.5*(-0.375)=2.1875;…x0x1x2x3x4x5智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第67頁(yè)。681.3最速下降法可見(jiàn)，當(dāng)=1.5時(shí)，搜索呈現(xiàn)振蕩形式，在極值點(diǎn)附近反復(fù)搜索?？梢宰C明，當(dāng)<1.0時(shí)，搜索將單調(diào)地趨向極值點(diǎn)，不會(huì)振蕩；當(dāng)>2.0時(shí)，搜索將圍繞極值點(diǎn)逐漸發(fā)散，不會(huì)收斂到極值點(diǎn)。為了保證收斂，不應(yīng)當(dāng)太大。但如果過(guò)小，收斂速度將十分緩慢?？梢圆捎米赃m應(yīng)調(diào)節(jié)的方法加快收斂而又不至于發(fā)散。問(wèn)題：為何當(dāng)很小時(shí)搜索總會(huì)成功？智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第68頁(yè)。691.3經(jīng)典算法經(jīng)典算法傳統(tǒng)實(shí)際問(wèn)題的特點(diǎn) 連續(xù)性問(wèn)題——主要以微積分為基礎(chǔ)，且問(wèn)題規(guī)模較小追求準(zhǔn)確 精確解理論的完美 結(jié)果漂亮主要方法 線性與非線性規(guī)劃、動(dòng)態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī) 劃等；排隊(duì)論、庫(kù)存論、對(duì)策論、決策論等。傳統(tǒng)的評(píng)價(jià)方法 算法收斂性（從極限角度考慮） 收斂速度（線性、超線性、二次收斂等）智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第69頁(yè)。701.3智能優(yōu)化算法一個(gè)優(yōu)化問(wèn)題稱為是復(fù)雜的，通常是指具有下列特征： （1）目標(biāo)函數(shù)沒(méi)有明確解析表達(dá)； （2）目標(biāo)函數(shù)雖有明確表達(dá)，但不可能恰好估值； （3）目標(biāo)函數(shù)為多峰函數(shù)； （4）目標(biāo)函數(shù)有多個(gè)，即多目標(biāo)優(yōu)化一個(gè)優(yōu)化問(wèn)題被稱為是困難的，通常是指：目標(biāo)函數(shù)或約束條件不連續(xù)、不可微、高度非線性問(wèn)題本身是困難的組合問(wèn)題。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第70頁(yè)。711.3智能優(yōu)化算法智能優(yōu)化算法主要用于求解非凸問(wèn)題或多峰問(wèn)題通常使用概率性搜索策略，即狀態(tài)轉(zhuǎn)移規(guī)則，這是由于實(shí)際的全局性優(yōu)化問(wèn)題通常沒(méi)有解析表達(dá)式或者解析表達(dá)式非常復(fù)雜難以進(jìn)行理論分析。其基本思想是在可行域中從給定的一個(gè)或多個(gè)隨機(jī)初始點(diǎn)出發(fā)進(jìn)行搜索，利用適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移規(guī)則和合理的概率性狀態(tài)接收規(guī)則搜索新的更優(yōu)點(diǎn)，在確定的時(shí)間或搜索次數(shù)之內(nèi)停止算法。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第71頁(yè)。721.3智能優(yōu)化算法經(jīng)典優(yōu)化算法與智能優(yōu)化算法經(jīng)典算法是以一個(gè)可行解為迭代的初始值，而智能算法是以一組可行解為初始值；經(jīng)典算法的搜索是確定性的，而智能算法的搜索策略是結(jié)構(gòu)化和隨機(jī)化；經(jīng)典算法大多都需要導(dǎo)數(shù)信息，而啟發(fā)式算法僅用到目標(biāo)函數(shù)值的信息；經(jīng)典算法對(duì)函數(shù)性質(zhì)有著嚴(yán)格要求，而啟發(fā)式算法對(duì)函數(shù)性質(zhì)沒(méi)有太大要求；經(jīng)典算法的計(jì)算量要比啟發(fā)式算法小的多。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第72頁(yè)。731.3智能優(yōu)化算法局部性和全局性優(yōu)化算法主要由搜索方向和搜索步長(zhǎng)組成。經(jīng)典算法的搜索方向和搜索步長(zhǎng)是由局部信息（如導(dǎo)數(shù)）決定的所以只能對(duì)局部進(jìn)行有效的深度搜索，而不能進(jìn)行有效的廣度搜索，這就導(dǎo)致易于陷入局部極優(yōu)解而無(wú)法用于解決多峰問(wèn)題；同時(shí)，全局性優(yōu)化算法采用適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移規(guī)則和概率性狀態(tài)接受規(guī)則，能夠避免過(guò)早地陷入局部極優(yōu)解從而搜索到全局性最優(yōu)解，但增加了計(jì)算量。通常，局部?jī)?yōu)化算法能夠快速地收斂到局部極優(yōu)解，而全局性優(yōu)化算法通過(guò)概率搜索可以獲得在概率意義上盡可能好的全局性最優(yōu)解區(qū)域，但是其局部極優(yōu)點(diǎn)搜索能力較低。這是全局搜索算法和局部搜索算法之間的固有矛盾。對(duì)此人們進(jìn)行了多種研究。基本解決方法在于二者的結(jié)合，即利用全局性優(yōu)化算法在整個(gè)可行域中搜索最優(yōu)區(qū)域，利用局部搜索算法搜索最優(yōu)區(qū)域中的最優(yōu)解。智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第73頁(yè)。74現(xiàn)代問(wèn)題的特點(diǎn)離散性問(wèn)題——主要以組合優(yōu)化理論為基礎(chǔ)不確定性問(wèn)題——隨機(jī)性數(shù)學(xué)模型半結(jié)構(gòu)或非結(jié)構(gòu)化的問(wèn)題——計(jì)算機(jī)模擬、決策支持系統(tǒng)大規(guī)模問(wèn)題——并行計(jì)算、大型分解理論、近似理論智能優(yōu)化方法

追求滿意——近似解實(shí)用性強(qiáng)——解決實(shí)際問(wèn)題智能優(yōu)化算法的評(píng)價(jià)方法 計(jì)算復(fù)雜性1.3智能優(yōu)化算法智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第74頁(yè)。751.4計(jì)算復(fù)雜性時(shí)間復(fù)雜性和空間復(fù)雜性概念

算法的時(shí)間復(fù)雜性：算法對(duì)時(shí)間的需要量（加、減、乘、除、比較、讀、寫等操作的總次數(shù)）；

算法的空間復(fù)雜性：算法對(duì)空間的需要量（存儲(chǔ)空間的大小，二進(jìn)制位數(shù)）；

問(wèn)題的時(shí)間復(fù)雜性：所有算法中時(shí)間復(fù)雜性最小的算法時(shí)間復(fù)雜性；

問(wèn)題的空間復(fù)雜性：所有算法中空間復(fù)雜性最小的算法空間復(fù)雜性；按照計(jì)算復(fù)雜性理論研究問(wèn)題求解的難易程度,可把問(wèn)題分為P類、NP類和NP完全類.智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第75頁(yè)。76復(fù)雜性表示方法算法或者問(wèn)題的復(fù)雜性可以表示為問(wèn)題規(guī)模n（如TSP的城市數(shù)）的函數(shù)，時(shí)間復(fù)雜性T(n)，關(guān)鍵操作的次數(shù)；空間復(fù)雜性S(n)，占用的存儲(chǔ)單元數(shù)量；

1.4計(jì)算復(fù)雜性

計(jì)算復(fù)雜性的基本概念

智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第76頁(yè)。771.4計(jì)算復(fù)雜性TSP問(wèn)題的復(fù)雜性計(jì)算智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第77頁(yè)。78多項(xiàng)式算法與非多項(xiàng)式算法若算法A的時(shí)間復(fù)雜性為TA(n)=O(p(n))，O(p(n))為復(fù)雜性函數(shù)p(n)主要項(xiàng)的階，且p(n)為n的多項(xiàng)式函數(shù)，則稱算法A為多項(xiàng)式算法。

當(dāng)不存在多項(xiàng)式函數(shù)p(n)時(shí)，稱相應(yīng)的算法為非多項(xiàng)式時(shí)間算法或指數(shù)時(shí)間算法；隨著變量的增加，多項(xiàng)式函數(shù)增長(zhǎng)的速度比指數(shù)函數(shù)和非多項(xiàng)式函數(shù)增長(zhǎng)的速度要慢得多。1.4計(jì)算復(fù)雜性智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第78頁(yè)。791.4計(jì)算復(fù)雜性設(shè)我們有一臺(tái)每小時(shí)能作M次運(yùn)算的計(jì)算機(jī)，并設(shè)求解某一問(wèn)題已有了兩個(gè)不同的算法。算法A對(duì)規(guī)模為n的實(shí)例約需作n2次運(yùn)算，而算法B則約需作2n次運(yùn)算。于是，運(yùn)用算法A在一小時(shí)內(nèi)大約可解一個(gè)規(guī)模為的實(shí)例，而算法B則只能解一個(gè)規(guī)模為log2M

的問(wèn)題兩者的差別究竟有多大呢？讓我們用數(shù)字來(lái)對(duì)比一下。假如計(jì)算機(jī)每秒鐘可作100萬(wàn)次運(yùn)算，則算法A一小時(shí)大約可解一個(gè)規(guī)模為n=60000的實(shí)例，而算法B在一小時(shí)內(nèi)只能解一個(gè)規(guī)模小于28的實(shí)例且n每增加1，算法B求解時(shí)所化的時(shí)間就將增加1倍。例如算法B求解一個(gè)n=50的實(shí)例將連續(xù)運(yùn)算357年。多項(xiàng)式算法與非多項(xiàng)式時(shí)間算法智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第79頁(yè)。801.4計(jì)算復(fù)雜性幾個(gè)多項(xiàng)式時(shí)間和指數(shù)時(shí)間算法的計(jì)算時(shí)間增長(zhǎng)情況算法要求的計(jì)算量規(guī)模n的近似值101001000N101001000Nlogn336649966N31031061092n10241.27×10301.05×10301N!3628800101584×102567智能算法簡(jiǎn)單介紹全文共89頁(yè)，當(dāng)前為第80頁(yè)。81P類問(wèn)題（deterministicpolynomial）具有多項(xiàng)式時(shí)間求解算法的問(wèn)題類.如果計(jì)算工作量在計(jì)算數(shù)據(jù)規(guī)模n的多項(xiàng)式（如n，n2，n3等）的范圍內(nèi)，則計(jì)算花費(fèi)的機(jī)時(shí)是可以接受的