智能優(yōu)化方法

智能優(yōu)化方法第六章智能優(yōu)化理論和方法6.1智能優(yōu)化理論和方法概述6.2遺傳算法介紹6.3遺傳算法算例6.4遺傳算法應(yīng)用第2頁,共25頁，星期六，2024年，5月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)行繁雜的一維搜索，而是通過大量簡單的信息傳播和演變方法來得到問題的最優(yōu)解。這些算法具有全局性、自適應(yīng)性、離散化的特點(diǎn)。第3頁,共25頁，星期六，2024年，5月6.1智能優(yōu)化理論和方法概述——續(xù)神經(jīng)網(wǎng)絡(luò)優(yōu)化方法人工神經(jīng)網(wǎng)絡(luò)（artificalneuralnetwork,ANN）是指由大量簡單人工神經(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ī)視覺、語言識別、智能控制、模式識別等。第4頁,共25頁，星期六，2024年，5月6.1智能優(yōu)化理論和方法概述——續(xù)遺傳學(xué)算法是模擬自然界生物進(jìn)化的一種隨機(jī)、并行和自適應(yīng)搜索算法。它將優(yōu)化參數(shù)表示成的編碼串群體，根據(jù)適應(yīng)度函數(shù)進(jìn)行選擇、交叉和變異遺傳操作。遺傳算法廣泛應(yīng)用于自動控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖像處理、機(jī)器學(xué)習(xí)、信號處理、人工生命等領(lǐng)域。第5頁,共25頁，星期六，2024年，5月6.2遺傳算法介紹遺傳算法的一次迭代稱為一代，每一代都有一組解。新的一組解不但可以有選擇的保留一些適度值高的舊的解，而且可以包括一些由其他解結(jié)合得到的新解。最初的一組解（初始群體）是隨機(jī)生成的，之后的每組新解由遺傳操作生成。每個解都通過一個與目標(biāo)函數(shù)相關(guān)的適應(yīng)度函數(shù)給予評價，通過遺傳過程不斷重復(fù)，達(dá)到收斂，而獲得問題的最優(yōu)解。第6頁,共25頁，星期六，2024年，5月6.2遺傳算法介紹——續(xù)現(xiàn)代生物遺傳學(xué)中描述的生物進(jìn)化理論:遺傳物質(zhì)的主要載體是染色體，染色體主要由DNA和蛋白質(zhì)組成。其中DNA為最主要的遺傳物質(zhì)?；蚴怯羞z傳效應(yīng)的片斷,它存儲著遺傳信息,可以準(zhǔn)確地復(fù)制,也能發(fā)生突變,并可通過控制蛋白質(zhì)的合成而控制生物的狀態(tài).生物自身通過對基因的復(fù)制和交叉的操作時其性狀的遺傳得到選擇和控制。生物的遺傳特性,使生物界的物種能保持相對的穩(wěn)定;生物的變異特性,使生物個體產(chǎn)生新的性狀,以至于形成了新的物種(量變積累為質(zhì)變),推動了生物的進(jìn)化和發(fā)展。

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

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

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