啟發(fā)式算法
什么是算法？從枚舉到貪心再到啟發(fā)式（上）
目標(biāo)：要優(yōu)化的東西
決策：根據(jù)目標(biāo)做出的決策
約束：進(jìn)行決策時(shí)必須遵循的條件
算例：?jiǎn)栴}參數(shù)的具體化
枚舉法：將問題所有的解一一枚舉出來(lái)，挨個(gè)去評(píng)價(jià)，選出最好的那個(gè)
1.枚舉法能夠找到問題的最優(yōu)解
2.枚舉法求解時(shí)間隨問題規(guī)模增長(zhǎng)而呈爆炸式增長(zhǎng)
貪心法：利用“構(gòu)造”的方式生成解，速度相對(duì)而言會(huì)非?？?，同時(shí)不會(huì)隨著問題規(guī)模的增長(zhǎng)而大幅度增加，是平緩的線性增長(zhǎng)
什么是算法？從枚舉到貪心再到啟發(fā)式（下）
啟發(fā)式算法：在一個(gè)合理的求解資源范圍內(nèi)（合理的時(shí)間，合理的內(nèi)存開銷等）求得一個(gè)較為滿意的解。目前主要包括鄰域搜索和群體仿生兩大類。
解空間：所有該問題的解的集合，包括可行解和不可行解
局部搜索：不完全遍歷解空間，只選擇一部分進(jìn)行遍歷，進(jìn)而大大降低搜索需要的資源。為了提高局部搜索的質(zhì)量，大部分局部搜索算法都會(huì)在搜索的時(shí)候不斷地抓取多個(gè)區(qū)域進(jìn)行搜索，直到滿足算法終止條件。
鄰域：在鄰域結(jié)構(gòu)定義下的解的集合，它是一個(gè)相對(duì)的概念，即鄰域肯定是基于某個(gè)解產(chǎn)生的
鄰居解：鄰域內(nèi)某個(gè)解的稱呼
鄰域結(jié)構(gòu)：定義了一個(gè)解的鄰域
鄰域結(jié)構(gòu)的設(shè)計(jì)在啟發(fā)式算法中非常重要，它直接決定了搜索的范圍，對(duì)最終的搜索結(jié)構(gòu)有著重要的影響，直接決定了最終結(jié)果質(zhì)量的好壞
搜索過程
- 初始解生成
一般初始解都采用構(gòu)造法進(jìn)行生成，比如隨機(jī)構(gòu)造、貪心構(gòu)造 - 鄰域生成
根據(jù)所定義的鄰域結(jié)構(gòu)生成鄰域 - 評(píng)價(jià)
在解的鄰域范圍內(nèi)對(duì)鄰居解進(jìn)行評(píng)價(jià)，然后選出需要的鄰居解進(jìn)行“移動(dòng)”。一般而言，有兩種評(píng)價(jià)的模式：
first improve：首次提升原則，即在鄰域內(nèi)對(duì)解一一進(jìn)行評(píng)價(jià)，一旦發(fā)現(xiàn)比當(dāng)前解更優(yōu)的鄰居解立馬進(jìn)行“移動(dòng)”。
best improve：最優(yōu)提升原則，遍歷整個(gè)鄰域，找出最好的鄰居解進(jìn)行“移動(dòng)”。
若初始解即生成在了一個(gè)局部最優(yōu)上面，通常選擇鄰域中一個(gè)最好的鄰居解進(jìn)行移動(dòng)（盡管它比當(dāng)前解還要差），避免徹底陷入局部最優(yōu)
擾動(dòng)是跳出局部最優(yōu)一個(gè)非常有效的做法，通常的實(shí)現(xiàn)方式是利用隨機(jī)或者其他方式，對(duì)當(dāng)前解進(jìn)行重組，使其結(jié)構(gòu)發(fā)生較大的改變?；蛘咧苯訏仐壆?dāng)前解，重新生成一個(gè)解進(jìn)行后續(xù)的鄰域搜索。 - 移動(dòng)
當(dāng)前解變換到剛剛評(píng)價(jià)選擇的鄰居解的過程 - 記錄全局最優(yōu)解
如果當(dāng)前解比全局最優(yōu)解還要優(yōu)，那么更新全局最優(yōu)解
不斷重復(fù)步驟2-步驟5，直到滿足終止條件，最后輸出全局最優(yōu)解
所有的啟發(fā)式找到的都是滿意解，不能說是最優(yōu)解（即便真的是），因?yàn)樗闅v的是解空間的局部。
一般情況下，啟發(fā)式算法的時(shí)間是隨著問題規(guī)模增長(zhǎng)而呈線性增長(zhǎng)的
干貨 | 想學(xué)習(xí)優(yōu)化算法，不知從何學(xué)起？
鄰域搜索類
迭代局部搜索算法
模擬退火算法
變鄰域搜索算法
禁忌搜索
自適應(yīng)大鄰域搜索
群體仿生類
遺傳算法
蟻群算法
粒子群算法
人工魚群算法
算法應(yīng)用
禁忌搜索算法求解帶時(shí)間窗的車輛路徑問題
基于樹表示法的變鄰域搜索算法求解考慮后進(jìn)先出的取派貨旅行商問題
變鄰域搜索算法求解Max-Mean dispersion problem
遺傳算法求解混合流水車間調(diào)度問題
