現(xiàn)代智能優(yōu)化

現(xiàn)代智能優(yōu)化第1頁(yè)，共70頁(yè)，2023年，2月20日，星期六引言現(xiàn)代優(yōu)化算法包括禁忌搜索（Tabusearch）、模擬退火（Simulatedannealing）、遺傳算法（Geneticalgorithms）等，這些算法涉及生物進(jìn)化、人工智能、數(shù)學(xué)和物理科學(xué)、神經(jīng)系統(tǒng)和統(tǒng)計(jì)力學(xué)等概念，都是以一定的直觀基礎(chǔ)而構(gòu)造的算法，我們稱(chēng)之為啟發(fā)式算法。啟發(fā)式算法的興起與計(jì)算復(fù)雜性理論的形成有密切的聯(lián)系，當(dāng)人們不滿(mǎn)足常規(guī)算法求解復(fù)雜問(wèn)題時(shí)，現(xiàn)代智能優(yōu)化算法開(kāi)始體現(xiàn)其作用?，F(xiàn)代智能優(yōu)化算法自八十年代初興起，至今發(fā)展迅速，這些算法同人工智能、計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)迅速融合，促進(jìn)了復(fù)雜優(yōu)化問(wèn)題的分析和解決。下面我們就簡(jiǎn)要介紹這些算法的基本理論以及MATLAB實(shí)現(xiàn)。第2頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法特點(diǎn)遺傳算法直接以適應(yīng)度作為搜索信息，求解問(wèn)題時(shí)，搜索過(guò)程不受優(yōu)化函數(shù)連續(xù)性的約束，無(wú)需導(dǎo)數(shù)或其他輔助信息；遺傳算法具有很高的并行性，可以同時(shí)搜索解空間的多個(gè)區(qū)域搜索信息，從而降低算法陷入局部最優(yōu)解的可能性；遺傳算法具很強(qiáng)的魯棒性。在待求解問(wèn)題為非連續(xù)、多峰以及有噪聲的情況下，它能夠以很大的可能性收斂到最優(yōu)解或近似最優(yōu)解；遺傳算法具有較高的可擴(kuò)充性。它易于與其它領(lǐng)域的知識(shí)或算法相結(jié)合來(lái)求解特定問(wèn)題；遺傳算法的基本思想簡(jiǎn)單，具有良好的可操作性和簡(jiǎn)單性；遺傳算法具有較強(qiáng)的智能性，可以用來(lái)解決復(fù)雜的非結(jié)構(gòu)化問(wèn)題。第3頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法算法流程第4頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法基本要素問(wèn)題編碼初始群體的設(shè)定適應(yīng)度函數(shù)的設(shè)計(jì)遺傳操作設(shè)計(jì)控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)第5頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法問(wèn)題編碼第6頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法初始群體的設(shè)定遺傳算法是群體型操作，這樣必須為遺傳操作準(zhǔn)備一個(gè)由若干初始解組成的初始群體。初始種群的好壞對(duì)于遺傳算法的計(jì)算結(jié)果的優(yōu)劣和算法的效率有著重要影響。產(chǎn)生初始種群通常有兩種方法。一種是完全隨機(jī)的產(chǎn)生方法，它適用于對(duì)待求解問(wèn)題的解無(wú)任何先驗(yàn)知識(shí)的情況；另一種是把某些先驗(yàn)知識(shí)轉(zhuǎn)化為必須滿(mǎn)足的一組要求，然后在滿(mǎn)足這些要求的解中隨機(jī)的選取。這種選擇初始種群的方法可以使遺傳算法較快地達(dá)到最優(yōu)解。初始群體也稱(chēng)做進(jìn)化的初始代，即第一代（firstgeneration）。第7頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法適應(yīng)度函數(shù)的確定解析性質(zhì)：連續(xù)、非負(fù)

合理性：要求適應(yīng)度函數(shù)設(shè)計(jì)應(yīng)盡可能簡(jiǎn)單近似量?。哼m應(yīng)度函數(shù)對(duì)某一類(lèi)具體問(wèn)題，應(yīng)盡可能通用。目標(biāo)函數(shù)的處理方法第8頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法第9頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法遺傳算子選擇算子交叉算子變異算子第10頁(yè)，共70頁(yè)，2023年，2月20日，星期六選擇算子第11頁(yè)，共70頁(yè)，2023年，2月20日，星期六選擇算子第12頁(yè)，共70頁(yè)，2023年，2月20日，星期六選擇算子第13頁(yè)，共70頁(yè)，2023年，2月20日，星期六交叉算子兩個(gè)步驟首先在新復(fù)制的群體中隨機(jī)選取兩個(gè)個(gè)體；沿著兩個(gè)個(gè)體（字符串）隨機(jī)的取一個(gè)位置，二者互換從該位置起的末尾部分第14頁(yè)，共70頁(yè)，2023年，2月20日，星期六變異算子變異算子模擬了自然界中生物進(jìn)化過(guò)程中個(gè)體的基因突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀。它是指將個(gè)體編碼串中的某些基因位上的基因值用該基因位上的其他等位基因來(lái)替換，從而產(chǎn)生新的個(gè)體。在遺傳運(yùn)算過(guò)程中，當(dāng)交叉操作產(chǎn)生的后代適應(yīng)度值不再進(jìn)化，且沒(méi)有達(dá)到最優(yōu)時(shí)，意味著算法陷入了早熟。早熟的根源在于有效基因的缺損，變異算子在一定程度上克服了這種情況，它可以改善遺傳算法的局部搜索能力，增加種群的多樣性。常見(jiàn)的變異算子包括位點(diǎn)變異、插入變異、對(duì)換變異、邊界變異、非均勻變異和高斯變異等形式。變異操作就是改變?nèi)旧w某個(gè)（些）位上的基因。例如，設(shè)染色體，將其第三位上的0變?yōu)?，即。也可以看做是原染色體的子代染色體。第15頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的參數(shù)設(shè)置第16頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的基本步驟第17頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第18頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第19頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第20頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第21頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第22頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第23頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第24頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第25頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第26頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法求解實(shí)例第27頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)調(diào)用方法x=ga(fitnessfcn,nvars)x=ga(fitnessfcn,nvars,A,b)x=ga(fitnessfcn,nvars,A,b,Aeq,beq)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon)x=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)[x,fval]=ga(...)[x,fval,exitflag]=ga(...)第28頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)輸入?yún)?shù)和輸出參數(shù)

第29頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)控制參數(shù)設(shè)置第30頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)命令詳解第31頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第32頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第33頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第34頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第35頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第36頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第37頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第38頁(yè)，共70頁(yè)，2023年，2月20日，星期六遺傳算法的MATLAB實(shí)現(xiàn)第39頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法第40頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的基本思想第41頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火的原理第42頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法新解的產(chǎn)生和接受第43頁(yè)，共70頁(yè)，2023年，2月20日，星期六冷卻進(jìn)度表參數(shù)第44頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火的算法步驟第45頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的參數(shù)控制問(wèn)題第46頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的參數(shù)控制問(wèn)題第47頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的參數(shù)控制問(wèn)題第48頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的參數(shù)控制問(wèn)題第49頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的應(yīng)用實(shí)例第50頁(yè)，共70頁(yè)，2023年，2月20日，星期六編碼選擇第51頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火新?tīng)顟B(tài)產(chǎn)生函數(shù)的設(shè)計(jì)第52頁(yè)，共70頁(yè)，2023年，2月20日，星期六新?tīng)顟B(tài)接受函數(shù)的設(shè)計(jì)第53頁(yè)，共70頁(yè)，2023年，2月20日，星期六初溫和初始狀態(tài)第54頁(yè)，共70頁(yè)，2023年，2月20日，星期六溫度下降函數(shù)的設(shè)計(jì)第55頁(yè)，共70頁(yè)，2023年，2月20日，星期六溫度修改準(zhǔn)則和算法終止準(zhǔn)則的設(shè)計(jì)第56頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火算法的應(yīng)用實(shí)例第57頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火的MATLAB工具箱求解第58頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火的MATLAB工具箱求解函數(shù)詳解第59頁(yè)，共70頁(yè)，2023年，2月20日，星期六模擬退火的MATLAB工具箱求解第60頁(yè)，共70頁(yè)，2023年，2月20日，星期六禁忌搜索禁忌搜索(tabusearch)算法是局部鄰域搜索算法的推廣，是人工智能在組合優(yōu)化算法中的一個(gè)成功應(yīng)用．G1over在1986年首次提出這一概念，進(jìn)而形成一套完整算法，禁忌按索算法的特點(diǎn)是采用了禁忌技術(shù)．所謂禁忌就是禁止重復(fù)前面的工作。為了回避局部鄰城搜索陷入局部最優(yōu)的主要不足，禁忌搜索算法用一個(gè)禁忌表記錄下已經(jīng)到達(dá)過(guò)的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再或有選擇的搜索這些點(diǎn)，以此來(lái)跳出局部最優(yōu)點(diǎn)。禁忌搜索算法是—種人工智能算法。第61頁(yè)，共70頁(yè)，2023年，2月20日，星期六局部鄰域搜索簡(jiǎn)介第62頁(yè)，共70頁(yè)，2023年，2月20日，星期六局部鄰域搜索簡(jiǎn)介第63頁(yè)，共70頁(yè)，2023年，2月20日，星期六局部鄰域搜索簡(jiǎn)介局部鄰域搜索是基于貪婪算法思想，在當(dāng)前解的鄰域進(jìn)行持續(xù)的搜索，雖然算法比較通用且容易理解實(shí)現(xiàn)，但是搜索的性能完全依賴(lài)于鄰域結(jié)構(gòu)和初始解的選擇，尤其容易陷入局部極小值，而無(wú)法保證全局最優(yōu)。針對(duì)局部鄰域搜索，為了跳出局部最優(yōu)的限制，可以采用的禁忌搜索盡量避免迂回搜索，禁忌搜索是一種人工智能算法，是局部搜索算法的擴(kuò)展，它的一個(gè)重要思想是標(biāo)記已得到的局部最擾解，并在進(jìn)一步的迭代中避開(kāi)這些局部最優(yōu)解，下面我們講解禁忌搜索算法如何避開(kāi)和記憶這些點(diǎn)。第64頁(yè)，共70頁(yè)，2023年，2月20日，星期六禁忌搜索的基本原理第65頁(yè)，共70頁(yè)，2023年，2月20日，星期六禁忌搜索算法流程圖第66頁(yè)，共70頁(yè)，2023年，2月20日，星期六禁忌搜索算法的簡(jiǎn)化步驟第67頁(yè)，共70頁(yè)，2023年，2月20日，星期六禁忌搜索的關(guān)鍵技術(shù)初始解的設(shè)置適應(yīng)度函數(shù)鄰域結(jié)構(gòu)禁忌