現(xiàn)代優(yōu)化技術(shù)考試提綱.選擇（2*10）1）構(gòu)筑法盛善法■…這兩者都屬于傳統(tǒng)啟發(fā)式算法（第四章 8頁(yè)）2）探索時(shí)間與解的精度（魚(yú)和熊掌不可兼得：解精度高，所需時(shí)間長(zhǎng)）3）時(shí)間復(fù)雜度理論（NP/NP-hard/多項(xiàng)式/非多項(xiàng)式）（第三章25頁(yè)）計(jì)算復(fù)雜度的表示法：?川+1000〃一>0彷J?log/?+/+1000/r—>O（n3）判前：TOC\o"1-5"\h\z?/?!/O（/7n）? （V）?10/->0（屏）？ （X）?logn—*0（/7）? （X）4）下列哪個(gè)算法是并行算法：選擇遺傳算法6）混合算法現(xiàn)代啟發(fā)式算法與局部搜索法結(jié)合：GA-LS SA-LSTS-LS現(xiàn)代啟發(fā)式算法之I'可的融合： GA-SA SA-TSGA-TS7）模擬退火算法的技術(shù)細(xì)節(jié)8）收斂性9）遺傳算法的技術(shù)細(xì)節(jié).判斷（2*10）1）對(duì)于傳統(tǒng)啟發(fā)式算法的理解2）模擬仿真&（尤化算法3）傳統(tǒng)啟發(fā)式算法---localsearch4）魯棒性能（是指算法的穩(wěn)健性，或稱為普適性）5）模擬退火算法的技術(shù)細(xì)節(jié)7）遺傳算法的設(shè)計(jì)細(xì)節(jié)Dijkstra與NearestAddition的區(qū)別9）遺傳算法的技術(shù)細(xì)節(jié)10）傳統(tǒng)啟發(fā)式算法自適應(yīng)性不是P問(wèn)題，就一定是NP問(wèn)題嗎？ 不是的；P和NP兩個(gè)集合并非是補(bǔ)集的關(guān)系，兩者集合并非全集。.簡(jiǎn)答（5*4）1）算法分析與評(píng)價(jià)指標(biāo)（第四章16頁(yè)）優(yōu)化性能指標(biāo)時(shí)間性能指標(biāo)魯棒性能指標(biāo)2）算法評(píng)價(jià)方法（1）解析的方法

極端場(chǎng)合計(jì)算復(fù)雜性解析平均計(jì)算復(fù)雜性解析與上（下）界值對(duì)比分析（2）實(shí)驗(yàn)的方法iv. 應(yīng)用實(shí)驗(yàn)V. 與基準(zhǔn)問(wèn)題的對(duì)照實(shí)驗(yàn)隨機(jī)生成實(shí)驗(yàn)比較實(shí)驗(yàn)3）計(jì)算量評(píng)價(jià)多項(xiàng)式時(shí)間算法（多項(xiàng)式時(shí)間算法二能用問(wèn)題規(guī)模的多項(xiàng)式函數(shù)來(lái)表示計(jì)算時(shí)間（上限）的算法高效率算法的代名言司）指數(shù)時(shí)間算法（指數(shù)時(shí)間算法二用問(wèn)題規(guī)模的指數(shù)函數(shù)來(lái)表示計(jì)算時(shí)間（上限）的算法非有效算法的代名蔚I）?（算法的實(shí)行時(shí)間）?0（/1）?O（nlogn） 多項(xiàng)式時(shí)間算法?0（,）?O（n3）?0（2"） 指數(shù)時(shí)間算法O（n!）4）K-optforTSP例 ：2-opt3-opt4-opt近鄰的范圍： 狹窄 <=> 寬闊探索時(shí)間： 短時(shí)間 <=> 長(zhǎng)時(shí)間解的質(zhì)量： 精度低 <=> 精度高5）模型、算法、程序Z間的關(guān)系模型（被求解的對(duì)象） 算法（求解的理論）程序（實(shí)現(xiàn)求解的手段）6）用離散隨機(jī)過(guò)程解釋模擬退火算法的收斂性SA接受準(zhǔn)則/GA?子解空間的搜索滿意解11SA接受準(zhǔn)則/GA?子解空間的搜索滿意解1111離散隨機(jī)狀態(tài)隨機(jī)落的跳最終狀態(tài)目標(biāo)函數(shù)的導(dǎo)向性4.算法辨析（20*2）（一）模擬退火算法1）判斷收斂圖試卷上面的那個(gè)圖（波浪形下降）：是模擬退火算法試卷下面的那個(gè)圖（階梯型下降）：算法2（填題中給的那個(gè)）2）判斷算法的優(yōu)劣勢(shì)模擬退火算法： 缺點(diǎn)：計(jì)算速度慢優(yōu)點(diǎn)：但是解收斂的質(zhì)量好算法2（題中給的那個(gè)）：優(yōu)點(diǎn)計(jì)算速度快缺點(diǎn)：解收斂的質(zhì)量不好3）模擬退火算法的步驟STEP1任選一個(gè)初始解；i:二；k:=0;:二（初始溫度）.STEP2若在該溫度達(dá)到內(nèi)循環(huán)停止條件，則到STEP3;否則，從鄰域N⑴中隨機(jī)選-j,計(jì)算A二f（j）—f（i）;若AW0,則i:二j,否則若exp（-A/）>randoni（0,1）時(shí),則i:=j;重復(fù)STEP2.STEP3:=d（）;k二k+1;若滿足停止條件，終止計(jì)算；否則，問(wèn)到STEP2.（二）遺傳算法1）根據(jù)問(wèn)題描述，設(shè)計(jì)一種編碼2）設(shè)計(jì)一種交叉算法（理解）3）遺傳算法的技術(shù)細(xì)節(jié)（本人理解是遺傳算法的步驟）選擇問(wèn)題的一個(gè)編碼；給出一個(gè)有林染色體的初始群體 尸孕（1）,t：=1step2.對(duì)群體皿去（f）中的每一個(gè)染色體砂必（￡）,計(jì)算它的適應(yīng)度函數(shù)fi=fitn&ss{popi（f））st&P3.若停止規(guī)則滿足，則算法停止；否則，計(jì)算概率Pi= -,i= N;并以上述慨率分布從砂八⑴中隨機(jī)選一些染色體構(gòu)成下一種群stepA通過(guò)交叉（概