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

现代优化技术考试提纲.选择（2*10）1）构筑法盛善法■…这两者都属于传统启发式算法（第四章 8页）2）探索时间与解的精度（鱼和熊掌不可兼得：解精度高，所需时间长）3）时间复杂度理论（NP/NP-hard/多项式/非多项式）（第三章25页）计算复杂度的表示法：?川+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）下列哪个算法是并行算法：选择遗传算法6）混合算法现代启发式算法与局部搜索法结合：GA-LS SA-LSTS-LS现代启发式算法之I'可的融合： GA-SA SA-TSGA-TS7）模拟退火算法的技术细节8）收敛性9）遗传算法的技术细节.判断（2*10）1）对于传统启发式算法的理解2）模拟仿真&（尤化算法3）传统启发式算法---localsearch4）鲁棒性能（是指算法的稳健性，或称为普适性）5）模拟退火算法的技术细节7）遗传算法的设计细节Dijkstra与NearestAddition的区别9）遗传算法的技术细节10）传统启发式算法自适应性不是P问题，就一定是NP问题吗？ 不是的；P和NP两个集合并非是补集的关系，两者集合并非全集。.简答（5*4）1）算法分析与评价指标（第四章16页）优化性能指标时间性能指标鲁棒性能指标2）算法评价方法（1）解析的方法

极端场合计算复杂性解析平均计算复杂性解析与上（下）界值对比分析（2）实验的方法iv. 应用实验V. 与基准问题的对照实验随机生成实验比较实验3）计算量评价多项式时间算法（多项式时间算法二能用问题规模的多项式函数来表示计算时间（上限）的算法高效率算法的代名言司）指数时间算法（指数时间算法二用问题规模的指数函数来表示计算时间（上限）的算法非有效算法的代名蔚I）?（算法的实行时间）?0（/1）?O（nlogn） 多项式时间算法?0（,）?O（n3）?0（2"） 指数时间算法O（n!）4）K-optforTSP例 ：2-opt3-opt4-opt近邻的范围： 狭窄 <=> 宽阔探索时间： 短时间 <=> 长时间解的质量： 精度低 <=> 精度高5）模型、算法、程序Z间的关系模型（被求解的对象） 算法（求解的理论）程序（实现求解的手段）6）用离散随机过程解释模拟退火算法的收敛性SA接受准则/GA?子解空间的搜索满意解11SA接受准则/GA?子解空间的搜索满意解1111离散随机状态随机落的跳最终状态目标函数的导向性4.算法辨析（20*2）（一）模拟退火算法1）判断收敛图试卷上面的那个图（波浪形下降）：是模拟退火算法试卷下面的那个图（阶梯型下降）：算法2（填题中给的那个）2）判断算法的优劣势模拟退火算法： 缺点：计算速度慢优点：但是解收敛的质量好算法2（题中给的那个）：优点计算速度快缺点：解收敛的质量不好3）模拟退火算法的步骤STEP1任选一个初始解；i:二；k:=0;:二（初始温度）.STEP2若在该温度达到内循环停止条件，则到STEP3;否则，从邻域N⑴中随机选-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）设计一种交叉算法（理解）3）遗传算法的技术细节（本人理解是遗传算法的步骤）选择问题的一个编码；给出一个有林染色体的初始群体 尸孕（1）,t：=1step2.对群体皿去（f）中的每一个染色体砂必（£）,计算它的适应度函数fi=fitn&ss{popi（f））st&P3.若停止规则满足，则算法停止；否则，计算概率Pi= -,i= N;并以上述慨率分布从砂八⑴中随机选一些染色体构成下一种群stepA通过交叉（概