啟發(fā)式與元啟發(fā)式算法

啟發(fā)式與元啟發(fā)式算法第一頁(yè)，共十八頁(yè)，編輯于2023年，星期五定義一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)(指計(jì)算時(shí)間、占用空問(wèn)等)下給出待解決優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)啟發(fā)式算法是一種技術(shù)，這種技術(shù)使得在可接受的計(jì)算費(fèi)用內(nèi)去尋找最好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至大多數(shù)情況下，無(wú)法闡述所得解同最優(yōu)解的近似程度元啟發(fā)式算法：?jiǎn)l(fā)式算法的改進(jìn)，隨機(jī)方法與局部搜索算法相結(jié)合。第二頁(yè)，共十八頁(yè)，編輯于2023年，星期五啟發(fā)式與元啟發(fā)式算法優(yōu)勢(shì)(1)有些難的優(yōu)化問(wèn)題可能還沒有找到最優(yōu)算法，即使存在，由算法復(fù)雜性理論，得知它們的計(jì)算時(shí)間是無(wú)法接受或不實(shí)際的(2)一些啟發(fā)式算法可用在最優(yōu)算法中，如在分支定界算法中，可用啟發(fā)式算法估界．(3)簡(jiǎn)單易行，比較直觀；易被使用者接受，(4)速度快，在適時(shí)控制中非常重要．(5)多數(shù)情況下，程序簡(jiǎn)單，因此易于修改．第三頁(yè)，共十八頁(yè)，編輯于2023年，星期五啟發(fā)式與元啟發(fā)式算法不足(1)不能保證求得最優(yōu)解．(2)表現(xiàn)不穩(wěn)定．啟發(fā)式算法在同一問(wèn)題的不同實(shí)例計(jì)算中會(huì)有不同的效果．有些解很好，而有些則很差．在實(shí)際應(yīng)用中，這種不穩(wěn)定性造成計(jì)算結(jié)果不可信(3)算法的好壞依賴于實(shí)際問(wèn)題、經(jīng)驗(yàn)和設(shè)計(jì)者的技術(shù)．這點(diǎn)很難總結(jié)規(guī)律，同時(shí)使不同算法之間難以比較第四頁(yè)，共十八頁(yè)，編輯于2023年，星期五啟發(fā)式與元啟發(fā)式算法遺傳算法模擬退火粒子群算法禁忌搜索神經(jīng)網(wǎng)絡(luò)第五頁(yè)，共十八頁(yè)，編輯于2023年，星期五13.1遺傳算法遺傳算法包含以下的主要處理步驟．首先是對(duì)優(yōu)化問(wèn)題的解進(jìn)行編碼，此處，我們稱一個(gè)解的編碼為一個(gè)染色體，組成編碼的元素稱為基因。編碼的目的主要是用于優(yōu)化問(wèn)題解的表現(xiàn)形式和用于之后遺傳算法中的計(jì)算．第二是適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)函數(shù)基本上依據(jù)優(yōu)化問(wèn)題的目標(biāo)函數(shù)而定．當(dāng)適應(yīng)函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)函數(shù)值的大小決定的概率分布來(lái)確定哪些染色體適應(yīng)生存，哪些被淘汰．生存下來(lái)的染色體組成種群．形成一個(gè)可以繁衍下一代的群體．第三是染色體的結(jié)合．雙親的遺傳基因結(jié)合通過(guò)編碼之間的交配(crossover)達(dá)到下一代的產(chǎn)生。新一代的產(chǎn)生是一個(gè)生殖過(guò)程，它產(chǎn)生了一個(gè)新解．最后是變異．新解產(chǎn)生過(guò)程中可能發(fā)生基因變異，變異使某些解的編碼發(fā)生變化，使解有更歷的遍歷性．第六頁(yè)，共十八頁(yè)，編輯于2023年，星期五生物遺傳概念在遺傳算法中的對(duì)應(yīng)關(guān)系第七頁(yè)，共十八頁(yè)，編輯于2023年，星期五例1用遺傳算法求解的最大值x為整數(shù)．解：一個(gè)簡(jiǎn)單的表示解的編碼是二進(jìn)制編碼，由于變量的最在值是31，因此可以采用5位數(shù)的二進(jìn)制碼，如以上的5位字符串稱為染色體．每一個(gè)分量稱為基因，每個(gè)基因有兩種狀態(tài)0或1。模擬生物進(jìn)化，首先要產(chǎn)生一個(gè)群體，可以隨機(jī)取4個(gè)染色體組成一個(gè)群體，如x1=(00000)，x2=(1l001),x3=(Ollll)，x4=(O1OOO)．群體有4個(gè)個(gè)體．適應(yīng)函數(shù)可以依據(jù)目標(biāo)函數(shù)而定，如適應(yīng)函數(shù)fitness(x)=f(x)=x2。于是第八頁(yè)，共十八頁(yè)，編輯于2023年，星期五例1定義第i個(gè)個(gè)體入選種群的概率為于是，適應(yīng)函數(shù)值大的染色體個(gè)體的生存概率自然較大．若群體中選4個(gè)個(gè)體成為種群，則極有可能競(jìng)爭(zhēng)上的是x2=(11001),x2=(11001),x3=(01111),x4=(01000)。若它們結(jié)合，采用如下的交配方式，稱為簡(jiǎn)單交配即交換第二個(gè)位置以后的基因，得到y(tǒng)1,y2,y3和y4。若y4的第一個(gè)基因發(fā)生變異，則變成y4=(11001)第九頁(yè)，共十八頁(yè)，編輯于2023年，星期五簡(jiǎn)單遺傳算法輪盤賭第十頁(yè)，共十八頁(yè)，編輯于2023年，星期五簡(jiǎn)單遺傳算法第十一頁(yè)，共十八頁(yè)，編輯于2023年，星期五例2求由于對(duì)連續(xù)變量求解，要解決的一個(gè)問(wèn)題是如何編碼。假設(shè)對(duì)解的誤差要求是1/16，則可以4位二進(jìn)制編碼，對(duì)應(yīng)關(guān)系為執(zhí)行一步計(jì)算，結(jié)果見下表解：第十二頁(yè)，共十八頁(yè)，編輯于2023年，星期五簡(jiǎn)單遺傳算法簡(jiǎn)單遺傳算法可以理解為：求解的問(wèn)題是極大目標(biāo)函數(shù)的優(yōu)化問(wèn)題；采用0-1二進(jìn)制編碼；pop(t)中的染色體個(gè)數(shù)是一個(gè)常數(shù)；初始群體隨機(jī)選取；適應(yīng)函數(shù)數(shù)為口標(biāo)函數(shù)；按輪盤賭方法選取染色體個(gè)數(shù)同pop(t)相同的種群；交配按例2的常規(guī)交配方法——一對(duì)染色體按隨機(jī)位交換位后的基因；染色體中的每一個(gè)基因都以相同的概率變異第十三頁(yè)，共十八頁(yè)，編輯于2023年，星期五關(guān)鍵問(wèn)題(1)解的編碼和解碼．遺傳算法的基礎(chǔ)工作之一是解的編碼，只有在編碼之后才可能有其他的計(jì)算(2)初始群體的選取和計(jì)算中群體的大小．一般采用隨機(jī)產(chǎn)生初始群體或通過(guò)其他方法先構(gòu)造一個(gè)初始群．通過(guò)其他方法構(gòu)造的初始群體可能會(huì)節(jié)省進(jìn)化的代數(shù)，但也能過(guò)早地陷人局部最優(yōu)群體中．我們稱過(guò)早地陷入局部最優(yōu)群中的現(xiàn)象為早熟(premature)現(xiàn)象群體中個(gè)體的個(gè)數(shù)稱為群體維數(shù)．群體的維數(shù)越大其代表性越廣泛，最終進(jìn)化到最優(yōu)解的能性越大第十四頁(yè)，共十八頁(yè)，編輯于2023年，星期五關(guān)鍵問(wèn)題(3)適應(yīng)函數(shù)的確定．一般情況，適應(yīng)函數(shù)同目標(biāo)函數(shù)相關(guān)，以保證較優(yōu)的解有較大的生存機(jī)會(huì)(4)三個(gè)算子。遺傳算法的三個(gè)算子是：種群選取、交配和變異（突變）第十五頁(yè)，共十八頁(yè)，編輯于2023年，星期五遺傳算法的優(yōu)越性(1)遺傳算法適合數(shù)值求解那此帶有多參數(shù)、多變量、多目標(biāo)和在多區(qū)域但連通性較差的NP-hard優(yōu)化問(wèn)題．遺傳算法是一個(gè)有普適性的方法，對(duì)目標(biāo)函數(shù)的性質(zhì)幾乎沒有要求，甚至都不一定要顯式地寫出目標(biāo)函數(shù)。遺傳算法所具有的特點(diǎn)是記錄一個(gè)群體，它可以記錄多個(gè)解而不同于局部搜索、禁忌搜索和模擬退火僅僅是一個(gè)解，這多個(gè)解的進(jìn)化過(guò)程正好適合多目標(biāo)優(yōu)化問(wèn)題的求解第十六頁(yè)，共十八頁(yè)，編輯于2023年，星期