Greedy Randomized Adaptive Search 算法超詳細(xì)解析鹉梨，附代碼實(shí)現(xiàn)TSP問題求解
GRASP（貪婪隨機(jī)自適應(yīng)搜索）
介紹
- 在算法的每次迭代中奥洼，主要由兩個階段組成：構(gòu)造（construction）和局部搜索（ local search）
- 構(gòu)造（construction）階段主要用于生成一個可行解鲤氢，而后該初始可行解會被放進(jìn)局部搜索進(jìn)行鄰域搜索摇予，直到找到一個局部最優(yōu)解為止
整體框架
偽代碼
GRASP偽代碼
- Greedy_Randomized_Construction：在貪心的基礎(chǔ)上汽绢，加入一定的隨機(jī)因素，構(gòu)造初始可行解侧戴。
- Local Search：對上面構(gòu)造的初始可行解進(jìn)行鄰域搜索宁昭，直到找到一個局部最優(yōu)解。
貪婪隨機(jī)構(gòu)造偽代碼
- 一開始解是一個空集酗宋。
- 初始化候選元素的集合积仗，這里候選元素是指能放進(jìn)Solution的元素（也就是目前Solution里面沒有的），比如１蜕猫，２寂曹，３……。
- 對候選集合的每個元素進(jìn)行評估，計(jì)算將元素x放入Solution會導(dǎo)致目標(biāo)函數(shù)f改變量△x隆圆。
- 根據(jù)△x對各個元素排序漱挚，選取部分較好的候選元素組成RCL表（貪心性體現(xiàn)在這里）。
- 隨機(jī)在RCL中選取一個元素放進(jìn)Solution渺氧。（算法的隨機(jī)性）
- 更新候選元素集合旨涝，然后對每個元素進(jìn)行重新評估計(jì)算△值。（算法的自適應(yīng)性體現(xiàn)在這里）
α參數(shù)主要是控制RCL的長度
- 當(dāng)α=0時(shí)侣背，純貪心白华，只能選取最優(yōu)的候選元素。
- 當(dāng)α=1時(shí)贩耐，純隨機(jī)弧腥，所有候選元素都可隨機(jī)選。
