1. GRASP算法的基本思想
??GRASP算法是一個(gè)多起點(diǎn)的迭代過程轴或，每一次迭代由兩個(gè)階段組成：一是產(chǎn)生可行解的構(gòu)造階段；二是尋找局部最優(yōu)解的局搜索階段频蛔。如果局部最優(yōu)解S比當(dāng)前搜索到的最優(yōu)解S還要優(yōu)的話灵迫，就更新S。
??該算法的基本架構(gòu)如下：
??在該算法中帽驯，Max_Iterations是迭代次數(shù)，迭代之前先貪心隨機(jī)構(gòu)造一個(gè)解书闸，然后判斷可行不可行尼变，若不可行則進(jìn)入Repair函數(shù)進(jìn)行修正，對可行解進(jìn)行局部搜索浆劲，然后更新最優(yōu)解嫌术。
2 Greedy Randomized Construction過程偽代碼
??在每次迭代之前，初始化可行解S為空牌借，并且初始化候選集C并對候選集的每一個(gè)元素進(jìn)行評估度气，作為進(jìn)入限制候選列表的依據(jù)。每次迭代從候選集中選部分元素構(gòu)成限制候選列表RCL膨报。每次從限制候選列表RCL中隨機(jī)選擇一個(gè)元素與可行解S進(jìn)行合并磷籍，然后更新候選集的元素，同時(shí)對里面的每一個(gè)元素進(jìn)行重新評估现柠。
2.1 影響GRASP性能的因素
1.參數(shù)α的選擇
??α = 1院领，對應(yīng)完全隨機(jī)的過程
??α = 0，對應(yīng)完全貪心的過程
2.RCL的大小
??如果RCL中含有很多元素够吩，就會(huì)產(chǎn)生很多不同的解比然，產(chǎn)生解的范圍就比較大。設(shè)置RCL的大小可以采用動(dòng)態(tài)調(diào)整法周循，即根據(jù)候選集C中滿足給定條件的元素個(gè)數(shù)動(dòng)態(tài)調(diào)整RCL的大小强法。這是GRASP算法中自適應(yīng)功能的體現(xiàn)万俗。
3 貪心函數(shù)
??貪心函數(shù)用來評估每一個(gè)候選元素，結(jié)果作為進(jìn)入RCL的依據(jù)饮怯。
??局部搜索階段的偽代碼如下：
??GRASP算法構(gòu)造階段得到的可行解質(zhì)量通常不高闰歪，所以要在該可行解的鄰域內(nèi)進(jìn)行局部搜索。
??基本思想是以持續(xù)不斷的迭代方式在可行解的鄰域內(nèi)尋找替換它的最優(yōu)解硕淑。
3.1 影響局部搜索性能的兩個(gè)因素：
??一是鄰域結(jié)構(gòu)
??二是選擇相鄰解的策略：有最優(yōu)適應(yīng)和首次適應(yīng)兩種课竣。最優(yōu)適應(yīng)策略要求所有的相鄰解都被考察之后將最優(yōu)解的相鄰解替換可行解。首次適應(yīng)策略則是置媳，當(dāng)?shù)谝淮嗡阉鞯奖瓤尚薪夂玫南噜徑忉層谡粒瑒t用該相鄰解替換可行解，并以此作為新的起點(diǎn)進(jìn)行局部搜索拇囊。
