现代优化技术复习吐血整理版

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

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）混合算法现代启发式算法与局部搜索法结合：GA-LSSA-LSTS-LS现代启发式算法之I'可的融合：GA-SASA-TS

2、GA-TS7）模拟退火算法的技术细节8）收敛性9）遗传算法的技术细节10）2.判断（2*10）1）对于传统启发式算法的理解2）模拟仿真&优化算法3）传统启发式算法localsearch4）鲁棒性能（是指算法的稳健性，或称为普适性）5）模拟退火算法的技术细节6）7）遗传算法的设计细节8）Dijkstra与NearestAddition的区别9）遗传算法的技术细节10）传统启发式算法自适应性不是P问题，就一定是NP问题吗？不是的；P和NP两个集合并非是补集的关系，两者集合并非全集。3.简答（5*4）1）算法分析与评价指标（第四章16页）优化性能指标时间性能指标鲁棒性能指标2）算法评价方法（1）解

3、析的方法i.极端场合计算复杂性解析ii.平均计算复杂性解析iii.与上（下）界值对比分析（2）实验的方法iv.应用实验v.与基准问题的对照实验vi.随机生成实验vii.比较实验3）计算量评价多项式时间算法（多项式时间算法二能用问题规模的多项式函数來表示计算时间（上限）的算法高效率算法的代名詞）指数时间算法（指数时间算法二用问题规模的指数函数来表示计算时间（上限）的算法非有效算法的代名詞）•（算法的实行时间）•0（/1）•O（nlogn）多项式时间算法•0（，）•O（n3）・0(2")指数时间算法O(n!)4)K-optforTSP例:2-opt3-opt4-opt近邻的范围：狭窄<=>宽阔探

4、索时间:短时间<=>长时间解的质量:精度低<=>精度高5）模型、算法、程序Z间的关系模型（被求解的对象）算法（求解的理论）程序（实现求解的手段）6）用离散随机过程解释模拟退火算法的收敛性解SA接受准则/GA»子解空间的搜索满意解11車t11离散随机状态状态转移概率矩阵随机幫的跳最终状态目标函数的导向性1.算法辨析（20*2）（一）模拟退火算法1）判断收敛图试卷上面的那个图(波浪形下降)：是模拟退火算法试卷下面的那个图(阶梯型下降)：算法2(填题中给的那个)2)判断算法的优劣势模拟退火算法：缺点：计算速度慢优点：但是解收敛的质量好算法2(题屮给的那个)：优点计算速度快缺点：解收敛的质量不好3)

5、模拟退火算法的步骤STEP1任选一个初始解；i：二；k：=0；：二(初始温度).STEP2若在该温度达到内循环停止条件，则到STEP3；否则，从邻域N(i)中随机选一j,计算A二f(j)—f(i)；若AW0,则i：二j,否则若exp(-A/)>randoni(0,1)时，则i：=j；重复STEP2.STEP3:=d()；k二k+1；若满足停止条件，终止计算；否则，冋到STEP2.(二)遗传算法1)根据问题描述，设计一种编码2)设计一种交叉算法(理解)父代：L于代3)遗传算法的技术细节(本人理解是遗传算法的步骤)选择问题的一个编码；给出一个有林染色体的初始群体戸孕(1),t：=1step2.对

6、群体皿去(f)中的每一个染色体砂必(£)，计算它的适应度函数fi=fitn&ss{popi(f))st&P3.若停止规则满足，则算法停止；否则，计算概率Pi=—,i=N;并以上述慨率分布从砂^(f)中随机选一些染色体构成下一种群stepA.通过交叉(槪率为耳),得到一个有时个染色体的交叉种群crosspop(t+1)通过变异〔较小槪率为，使得染色体的一个基因发生变异,形成曲(砂遊+1)；令f=f+i,产生一个新的群体pop(t)=mutpQp(t)