《现代优化技术复习吐血整理版x.docx》由会员分享，可在线阅读，更多相关《现代优化技术复习吐血整理版x.docx（5页珍藏版）》请在三一文库上搜索。
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）?log n * 0 （/7） ?（ X ）4）下列哪个算法是并行算法：选择遗传算法5）6）混合算法现代启发式算法与局部搜索法结合：GA-LSSA-LS TS-LS现代启发式算法之I可
2、的融合：GA-SASA-TS GA-TS7）模拟退火算法的技术细节8）收敛性9）遗传算法的技术细节10）2 .判断（2*10）1）对于传统启发式算法的理解2）模拟仿真&（尤化算法3）传统启发式算法-local search4）鲁棒性能（是指算法的稳健性，或称为普适性）5）模拟退火算法的技术细节6）7）遗传算法的设计细节8） Dijkstra 与 Nearest Addition 的区别9）遗传算法的技术细节10）传统启发式算法自适应性不是P问题，就一定是NP问题吗？不是的；P和NP两个集合并非是补集的关系，两者集合并非全集。3 .简答（5*4）1）算法分析与评价指标（第四章16页）优化性能指标
3、时间性能指标鲁棒性能指标2）算法评价方法（1）解析的方法i. 极端场合计算复杂性解析ii. 平均计算复杂性解析iii. 与上（下）界值对比分析（2）实验的方法iv.应用实验V.与基准问题的对照实验vi. 随机生成实验vii. 比较实验3）计算量评价多项式时间算法（多项式时间算法二能用问题规模的多项式函数来表示计算时间（上限）的算法高效率算法的代名言司）指数时间算法（指数时间算法二用问题规模的指数函数来表示计算时间（上限）的算法 非有效算法的代名蔚I）?（算法的实行时间）?0 （/1）? O （n log n）多项式时间算法? 0（,）? O （n3）? 0（2）指数时间算法O（n!）4） K-
4、opt for TSP例： 2-opt 3-opt 4-opt近邻的范围：狭窄宽阔探索时间：短时间长时间解的质量：精度低精度高5）模型、算法、程序Z间的关系 模型（被求解的对象）算法（求解的理论）程序（实现求解的手段）6）用离散随机过程解释模拟退火算法的收敛性SA接受准则/GA?子解空间的搜索满意解1111离散随机状态随机落的跳最终状态目标函数的导向性4.算法辨析（20*2）（一）模拟退火算法1）判断收敛图试卷上面的那个图（波浪形下降）：是模拟退火算法试卷下面的那个图（阶梯型下降）：算法2 （填题中给的那个）2）判断算法的优劣势模拟退火算法：缺点：计算速度慢 优点：但是解收敛的质量好算法2（题
5、中给的那个）：优点 计算速度快 缺点：解收敛的质量不好 3）模拟退火算法的步骤STEP1任选一个初始解；i:二；k: =0;:二（初始温度）.STEP2若在该温度达到内循环停止条件，则到 STEP3;否则，从邻域N中随 机选- j,计算 A 二 f （j） f （i）;若 A W0,则 i:二 j,否则若 exp （-A/） randoni （0,1）时,则 i: =j;重复 STEP2.STEP3 : =d （）; k二k+1;若满足停止条件，终止计算；否则，问到 STEP2.（二）遗传算法1）根据问题描述，设计一种编码2）设计一种交叉算法（理解）3）遗传算法的技术细节（本人理解是遗传算法的步骤）选择问题的一个编码；给出一个有林染色体的初始群体尸孕（1）,t ： = 1step 2.对群体皿去（f ）中的每一个染色体砂必（ ）,计算它的适应度函数fi =fitn&sspop i （f）st&P3.若停止规则满足，则算法停止；否则，计算概率Pi =-, i =N;并以上述慨率分布从砂八中随机选一些染色体构成下一种群stepA通过交叉（概率为耳），得到一个有时个染色体的交叉种群crosspop （t+1）通过变异较小概率为，使得染色体的一个基因发生变异，形成曲（砂遁+ 1）;令 = f+ i,产生一个新的群体