智能優(yōu)化方法

智能優(yōu)化方法第一頁，共二十五頁，編輯于2023年，星期六第六章智能優(yōu)化理論和方法6.1智能優(yōu)化理論和方法概述6.2遺傳算法介紹6.3遺傳算法算例6.4遺傳算法應(yīng)用第二頁，共二十五頁，編輯于2023年，星期六6.1智能優(yōu)化理論和方法概述隨著仿生學(xué)、遺傳學(xué)和人工智能科學(xué)的發(fā)展，從20世紀(jì)70年代以來，研究人員相繼將遺傳學(xué)、神經(jīng)網(wǎng)絡(luò)科學(xué)的原理和方法應(yīng)用到最優(yōu)化領(lǐng)域，形成了一系列的最優(yōu)化方法如人工神經(jīng)網(wǎng)絡(luò)算法，遺傳算法，蟻群算法等。這些算法不需要構(gòu)造精確的數(shù)學(xué)搜索方向，不需要進(jìn)行繁雜的一維搜索，而是通過大量簡(jiǎn)單的信息傳播和演變方法來得到問題的最優(yōu)解。這些算法具有全局性、自適應(yīng)性、離散化的特點(diǎn)。第三頁，共二十五頁，編輯于2023年，星期六6.1智能優(yōu)化理論和方法概述——續(xù)神經(jīng)網(wǎng)絡(luò)優(yōu)化方法人工神經(jīng)網(wǎng)絡(luò)（artificalneuralnetwork,ANN）是指由大量簡(jiǎn)單人工神經(jīng)元互聯(lián)而成的一種計(jì)算結(jié)構(gòu)。它可以在某種程度上模擬生物神經(jīng)系統(tǒng)的工作過程，從而具備解決問題的能力。人工神經(jīng)網(wǎng)絡(luò)由于其大規(guī)模并行處理、學(xué)習(xí)、聯(lián)想和記憶等功能，以及它的高度自組織和自適應(yīng)能力，已成為解決許多問題的有力工具，近年來得到了飛速的發(fā)展。迄今為止，已有數(shù)十種不同的人工神經(jīng)網(wǎng)絡(luò)模型被提出，分別適用于不同的問題領(lǐng)域，如計(jì)算機(jī)視覺、語言識(shí)別、智能控制、模式識(shí)別等。第四頁，共二十五頁，編輯于2023年，星期六6.1智能優(yōu)化理論和方法概述——續(xù)遺傳學(xué)算法是模擬自然界生物進(jìn)化的一種隨機(jī)、并行和自適應(yīng)搜索算法。它將優(yōu)化參數(shù)表示成的編碼串群體，根據(jù)適應(yīng)度函數(shù)進(jìn)行選擇、交叉和變異遺傳操作。遺傳算法廣泛應(yīng)用于自動(dòng)控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖像處理、機(jī)器學(xué)習(xí)、信號(hào)處理、人工生命等領(lǐng)域。第五頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹遺傳算法的一次迭代稱為一代，每一代都有一組解。新的一組解不但可以有選擇的保留一些適度值高的舊的解，而且可以包括一些由其他解結(jié)合得到的新解。最初的一組解（初始群體）是隨機(jī)生成的，之后的每組新解由遺傳操作生成。每個(gè)解都通過一個(gè)與目標(biāo)函數(shù)相關(guān)的適應(yīng)度函數(shù)給予評(píng)價(jià)，通過遺傳過程不斷重復(fù)，達(dá)到收斂，而獲得問題的最優(yōu)解。第六頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹——續(xù)現(xiàn)代生物遺傳學(xué)中描述的生物進(jìn)化理論:遺傳物質(zhì)的主要載體是染色體，染色體主要由DNA和蛋白質(zhì)組成。其中DNA為最主要的遺傳物質(zhì)。基因是有遺傳效應(yīng)的片斷,它存儲(chǔ)著遺傳信息,可以準(zhǔn)確地復(fù)制,也能發(fā)生突變,并可通過控制蛋白質(zhì)的合成而控制生物的狀態(tài).生物自身通過對(duì)基因的復(fù)制和交叉的操作時(shí)其性狀的遺傳得到選擇和控制。生物的遺傳特性,使生物界的物種能保持相對(duì)的穩(wěn)定;生物的變異特性,使生物個(gè)體產(chǎn)生新的性狀,以至于形成了新的物種(量變積累為質(zhì)變),推動(dòng)了生物的進(jìn)化和發(fā)展。

第七頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹——續(xù)遺傳學(xué)算法和遺傳學(xué)中的基礎(chǔ)術(shù)語比較：第八頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹——續(xù)與傳統(tǒng)優(yōu)化方法相比，遺傳算法的優(yōu)點(diǎn)是：群體搜索不需要目標(biāo)函數(shù)的導(dǎo)數(shù)概率轉(zhuǎn)移準(zhǔn)則第九頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹——續(xù)遺傳算法研究熱點(diǎn)收斂性證明新型高效的遺傳算子設(shè)計(jì)遺傳算法與局部?jī)?yōu)化算法的結(jié)合遺傳算法在各領(lǐng)域的應(yīng)用研究軟計(jì)算與計(jì)算智能中的遺傳算法第十頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹——續(xù)遺傳算法的準(zhǔn)備工作:

1)數(shù)據(jù)轉(zhuǎn)換操作：包括表現(xiàn)型到基因型的轉(zhuǎn)換和基因型到表現(xiàn)型的轉(zhuǎn)換。2)確定適應(yīng)度計(jì)算函數(shù)：可以將個(gè)體值經(jīng)過該函數(shù)轉(zhuǎn)換為該個(gè)體的適應(yīng)度,該適應(yīng)度的高低要能充分反映該個(gè)體對(duì)于解得優(yōu)秀程度。第十一頁，共二十五頁，編輯于2023年，星期六6.2遺傳算法介紹——續(xù)遺傳算法的基本步驟：1)編碼,創(chuàng)建初始群體（初始解）2)群體中個(gè)體適應(yīng)度計(jì)算3)評(píng)估適應(yīng)度4)根據(jù)適應(yīng)度選擇個(gè)體5)被選擇個(gè)體進(jìn)行交叉繁殖,6)在繁殖的過程中引入變異機(jī)制7)繁殖出新的群體,回到第2）步第十二頁，共二十五頁，編輯于2023年，星期六6.3遺傳算法算例遺傳算法簡(jiǎn)單算例：求下述二元函數(shù)的最大值：第十三頁，共二十五頁，編輯于2023年，星期六6.3遺傳算法算例——續(xù)遺傳算法程序?qū)崿F(xiàn)：第十四頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域。所以，廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一此主要應(yīng)用領(lǐng)域。函數(shù)優(yōu)化組合優(yōu)化生產(chǎn)調(diào)度問題自動(dòng)控制機(jī)器人學(xué)圖像處理人工生命數(shù)據(jù)挖掘等第十五頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測(cè)試函數(shù)。連續(xù)、離散、凸函數(shù)、凹函數(shù)、低維函數(shù)、高維函數(shù)，確定函數(shù)、隨機(jī)函數(shù)、單峰值函數(shù)、多峰值函數(shù)等。算法的本質(zhì)效果而對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解。而遺傳算法卻可以方便地得到較好的結(jié)果第十六頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)組合優(yōu)化隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大。有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問題，人們已意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、圖形劃分問題等各種具有NP難度的問題得到成功的應(yīng)用。第十七頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下建立起來的數(shù)學(xué)模難以精確求解，即使經(jīng)過一些簡(jiǎn)化之后可以進(jìn)行求解.也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。目前在現(xiàn)實(shí)生產(chǎn)中主要是靠一些經(jīng)驗(yàn)來進(jìn)行調(diào)度。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效下具。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。第十八頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)自動(dòng)控制：在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解。遺傳算法已在其中得到了初步的應(yīng)用，并顯示出良好的效果。例如用遺傳算法進(jìn)行：航空控制系統(tǒng)的優(yōu)化、設(shè)計(jì)空間交會(huì)控制器模糊控制器的優(yōu)化設(shè)計(jì)參數(shù)辨識(shí)、模糊控制規(guī)則的學(xué)習(xí)人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等。第十九頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)數(shù)據(jù)挖掘：數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價(jià)值的知識(shí)和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化.直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。Sunil已成功地開發(fā)了一個(gè)基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對(duì)兩個(gè)飛機(jī)失事的真實(shí)數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?yàn)，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。

第二十頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)遺傳算法在應(yīng)用中關(guān)鍵的問題:1．串的編碼方式一般把問題的各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。串長(zhǎng)度及編碼形式對(duì)算法收斂影響極大。雖然二進(jìn)制編碼適于進(jìn)行遺傳操作，但在求解高精度問題時(shí)，運(yùn)行性能差，也不便于反映所求問題的特定特性決策變量需要采用浮點(diǎn)型編碼，等。第二十一頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)遺傳算法在應(yīng)用中關(guān)鍵的問題:2．適應(yīng)函數(shù)的確定適應(yīng)函數(shù)(fitnessfunction)也稱對(duì)象函數(shù)(objectfunction)，這是問題求解品質(zhì)的測(cè)量函數(shù)；往往也稱為問題的“環(huán)境”。一般可以把問題的模型函數(shù)作為對(duì)象函數(shù)；但有時(shí)需要另行構(gòu)造。第二十二頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)遺傳算法在應(yīng)用中關(guān)鍵的問題:3．遺傳算法自身參數(shù)設(shè)定遺傳算法自身參數(shù)有3個(gè)：群體大小n、交叉概率Pc和變異概率Pm。群體大小n太小時(shí)難以求出最優(yōu)解，太大則增長(zhǎng)收斂時(shí)間,一般n＝30-160。交叉概率Pc太小時(shí)難以向前搜索，太大則容易破壞高適應(yīng)值的結(jié)構(gòu)，一般取Pc=0.25-0.75(0.4-0.9)。變異概率Pm太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索，一般取Pm＝0．01—0．2(0.01-0.1)。第二十三頁，共二十五頁，編輯于2023年，星期六6.4遺傳算法應(yīng)用——續(xù)遺傳算法在應(yīng)用中關(guān)鍵的問題:4選擇策略輪盤賭選