海事大学现代优化技术吐血整理版

《海事大学现代优化技术吐血整理版》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、现代优化技术考试提纲1.选择（2*10）1）构筑法&改善法■…这两者都属于传统启发式算法（第四章8页）2）探索时间与解的精度（鱼和熊掌不可兼得：解精度高，所需时间长）3）时间复杂度理论（NP/NP-hard/多项式/非多项式）（第三章25页）计算复杂度的表示法：•川+1000〃一>0彷J•log/?+/+1000/r—>O（n3）判前：•/?!—>O（/7n）?（V）•10/->0（屛）？（X）•logn—*0（/7）?（X）4）下列哪个算法是并行算法：选择遗传算法5）6）混合算法现代启发式算法与局部搜索法结合

2、：GA-LSSA-LSTS-LS现代启发式算法之I'可的融合：GA-SASA-TSGA-TS7）模拟退火算法的技术细节8）收敛性9）遗传算法的技术细节10）2.判断（2*10）1）对于传统启发式算法的理解2）模拟仿真&优化算法3）传统启发式算法localsearch4）鲁棒性能（是指算法的稳健性，或称为普适性）5）模拟退火算法的技术细节6）7）遗传算法的设计细节8）Dijkstra与NearestAddition的区别9）遗传算法的技术细节10）传统启发式算法自适应性不是P问题，就一定是NP问题吗？不是的；P和

3、NP两个集合并非是补集的关系，两者集合并非全集。3.简答（5*4）1）算法分析与评价指标（第四章16页）优化性能指标时间性能指标鲁棒性能指标2）算法评价方法（1）解析的方法i.极端场合计算复杂性解析ii.平均计算复杂性解析i.与上（下）界值对比分析（2）实验的方法ii.应用实验iii.与基准问题的对照实验iv.随机生成实验v.比较实验3）计算量评价多项式时间算法（多项式时间算法二能用问题规模的多项式函数來表示计算时间（上限）的算法高效率算法的代名詞）指数时间算法（指数时间算法二用问题规模的指数函数来表示计算时间

4、（上限）的算法非有效算法的代名詞）•（算法的实行时间）•0（/0•O（/tlogn）多项式时间算法•0（/）・0（》）•0(2")指数时间算法O(w!)4)K-optforTSP例:2-opt3-opt4-opt近邻的范围：狭窄<=>宽阔探索时间：短时间O长时间解的质量：精度低O精度高5）模型、算法、程序Z间的关系模型（被求解的对彖）算法（求解的理论）程序（实现求解的手段）6）用离散随机过程解释模拟退火算法的收敛性解SA接受准则/GA#子解空间的拽索满意解XtXC离敵随机状态状态蹲啓的践最终状态目标函数的导向性

5、1.算法辨析（20*2）（一）模拟退火算法1）判断收敛图试卷上面的那个图（波浪形下降）：是模拟退火算法试卷下面的那个图（阶梯型下降）：算法2（填题屮给的那个）2）判断算法的优劣势模拟退火算法：缺点：计算速度慢优点：但是解收敛的质量好算法2（题屮给的那个）：优点计算速度快缺点：解收敛的质量不好3）模拟退火算法的步骤STEP1任选一个初始解i0；i：%；k：=0；=tmax（初始温度）.STEP2若在该温度达到内循环停止条件，则到STEP3；否则，从邻域N（i）中随机选一j，计算A£j二f（j）—f（i）；若A£j

6、W（）,则i：=j,否则若exp（-Af^/tk）>random（0,1）时，则i：=j；重复STEP2.STEP3S+i：=d（tQ;k=k+l；若满足停止条件，终止计算;否则，回到STEP2.（二）遗传算法1）根据问题描述，设计--种编码2）设计一种交叉算法（理解）乂代NV代工K-■■■■■■■■■■■■■■■■■■I653）遗传算法的技术细节（本人理解是遗传算法的步骤）step.选择问题的一个编码；给岀一个有林染色体的初始群体py⑴，t:=1step2对群体pop（£）中的每一个染色体pop（/）,计算

7、它的适应度函数fi=fitness^pop^（£））step3若停止规则满足，则算法停止；否则，计算概率Pi=,i=1,…,M并以上述慨率分布从pop。）中随机选一三力些染色体构成下一种群step4通过交叉（慨率为几），得到一个有N个染色体的交叉种群crosspop（t+1）stepS通过变异（较小慨率为久《）,使得染色体的一个基因发生变异，形成曲切op。+1）；令f=f+1,产生一个新的群体pop（t）=fnutpopity,返回step2.