浙江大学秋季期末考试智能算法考试重点总结
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
浙江大学秋季期末考试智能算法考试重点总结 1. 什么是多项式问题（P问题）？ 记问题的一个实例为I，实力规模为l(I)，算法A在求解I时的计算量（基本计算总次数）为CA(i)。对于给定的一个优化问题，若存在一个求最优解的算法、一个多项式函数g(x)和常数，使得则给定的优化问题是多项式时间可解问题，或简称多项式问题。CA(I)g(l(I))对所有的实例成立，所有多项式问题的集合记为P。 2. 简要叙述模拟退火算法中温度t，接受概率Rk ，局部最优或全局最优解的关系；由此，在应用模拟退火算法时齐算法到具体问题时，我们在选取初始温度，确定同一温度的迭代步数等方面应注意什么？ 温度t是重要的参数，其大小控制了随机过程向局部或全局最优解移动的快慢。温度t升高，接受概率Rk ，有利于全局搜索，但收敛速度慢。温度t降低，接受概率Rk 减小，收敛速度快，可能陷入局部最优。 确定同一温度的迭代步数等方面应注意：1.当温度很高时，每一个状态都接受的频率基本相同，而且几乎所有的状态都能被接受，此时，在同一温度应使迭代的步数尽量少；2.当温度渐渐更低时，越来越多的状态被拒绝。如果在此温度的迭代太少，则可能造成过早的陷入局部最优状态，比较直观和有效的方法随着温度的下降，将同一温度的迭代步增加。 3. 简述BP网络和Hopfield网络有何异同？ 1) 两者都可以取离散或连续变量，但Hopfield网络考虑输入与输出在时间上的滞后效应，要用动态方程描述； 2) BP网络采用梯度算法，收敛速度慢，Hopfield网络采用Hebb规则，收敛速度很快； 3) Hopfield网络有类似BP网络的应用，但在优化计算方面应用更加突出。 4. 遗传算法的特点是什么？ （一）处理的对象不是参数本身，是对参数集进行了编码的个体； （二）同时对搜索空间的多个解进行评估后搜索 （三）GA基本不应搜索空间的知识或辅助信息，仅用适应度函数来评估个体； （四）GA不是采用编码性规则，用概率变迁来指导搜索方向； 或者，遗传算法以有限的代价解决搜索和优化，其与传统搜索方法的区别主要在于： 遗传算法直接处理问题参数的适当编码而不是参数集本身。 遗传算法的本质的并行性，遗传算法按并行方式搜索一个种群数目的点，而不是单点。 遗传算法不需要求导或其他辅助知识，只需要适应度函数值。 遗传算法使用概率转换规则，而非确定的转换规则知道搜索。 遗传算法在搜索过程中不易陷入局部最优，有较好的全局优化能力。 5. 模式理论的实质是什么？ 模式理论是奇偶基于简单遗传算法，主要从一种结构的角度介绍遗传算法的收敛性。（模板理论）假设群体在t时刻含有模板H样本数为N（H，t），经选择、交叉、变异后，在t+1时刻，群体中具有N(H,t1)N(H,t)H的样本数为：f(H)Pc(H)1(1P(H,t))1Pm0(H)fn1N(H,t)f(H)Pc(H)(1P(H,t))Pm0(H)1fn1 说明具有低阶、短定义矩，以及平均适应度高于群体适应度的模板在子代中将得到指数级增长。 6. 说明SGA搜索寻优的过程。如何体现遗传、进化和适应性？为什么是有效的？SGA的参数有哪些？ SGA的一般流程： a. 随机产生一定数目的初始种群，每个个体表示为染色体的基因编码； b. 计算每个个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解并word专业资料-可复制编辑-欢迎下载 结束计算，否则转向第3步； c. 依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度底的个体可能被淘汰； d. 执行交叉和变异操作，生成新的个体； e. 得到新一代的种群，返回第2步。 遗传：通过交配产生一组新解的过程。 进化：变异编码的某一分量发生变化的过程使解有更大的遍历性。 适应性：适应函数值 交配使得算法能够搜到更好的解，但受基因的限制，只能搜索已有的所有基因的组合，变异是扩大染色体选择范围的一个手段，可以得到一些新的基因。 SGA的参数：群体规模、迭代次数及各种遗传概率（交叉概率、变异概率）等。 7. 标准遗传算法SGA（standard genetic algorithm）有哪些不足？交叉率Pc，变异率Pm，自适应调整的算法和解决问题是什么？ SGA有哪些不足： （一）编码问题：对于不同的问题，编码选择不当，可能导致积木块假设不成立而使GA很难收敛到最优解。编码不规范及编码表示的不正确性，单一的遗传编码不能全面地将优解问题的约束表示出来。 （二）早熟收敛：指群体过早失去多样性而收敛到局部最优解。 （三）进化时间长：进化过程中产生大量数据，计算大，时间长。 （四）参数选择问题：目前参数选择是根据经验来确定，缺乏理论依据。 Kc(fmaxfc),fcfavg PcfmaxfavgKc,fcfavgKm(fmaxfm),fmfavgPmfmaxfavg Km,fmfavg其中Kc，Km为小于1的常数，fc是要交叉的两个个体中适应值大的一个，fm是变异个体的适应值，fmaxfavg体现了群体的收敛性，此值小，说明群体趋向收敛应加大Pc,Pm。 Srinvias提出自适应遗传算法：Pc,Pm能够随适应度自动改变。思想：当种群各个体适应度趋向于局部最优解时，使Pc,Pm增加，当群体适应度分散时Pc,Pm减小。同时，对于适应度高于群体平均适应度的个体，取较低的Pc,Pm，而低于群体平均适应度的个体，取较高的Pc,Pm，使该解淘汰。 适应度函数解决的问题： 遗传进化初期，通常会产生一些超群个体，若按比例选择，超群个体因竞争力突出而控制选择过程，影响算法的全局最优；遗传进化后期，算法接近收敛，由于种群个体适应度差异较小，继续优化的潜能低，不能获得局部最优。 8. 支持向量机有哪些特点？ （一）专门针对有限样本的情况，目标是得到现有信息下的最优解而不是样本数趋于无穷大的最优解。 （二）算法最终转化为一个二次寻优问题，从理论上说将得到的是全局最优点。 （三）算法将实际问题通过非线性变换转化到高维的特征空间，在高维的空间中构造线性判别函数来实现原空间中非线性问题，巧妙解决了维数问题，算法复杂度与样本维数无关。 9. 粒子群（PSO）算法的特点？ （一）粒子群算法是一种基于迭代的优化工具； （二）随机初始化种群； （三）使用适应值来评价系统； （四）根据适应值进行一定的随机搜索； （五）不能保证能够找到最优解； （六）根据自己的速度来决定搜索； （七）粒子群算法还有一个重要的特点，就是有记忆功能； （八）信息的单向流动，整个搜索更新过程是跟随当前最优解的过程，可能会列出转移概率和信息素更新公式。 10. 蚁群算法求解TSP问题的步骤。要求会列出转移概率和信息素更新公式。 蚁群算法求解TSP问题的步骤： （一）对n个 城市的TSP问题，N1,2,,n,A(i,j)i,jN，城市间的距离D(dij)nn，为TSP图中每一条弧（i，j）赋信息素痕迹初值ij(0)1A，假设有m只蚂蚁在工作，所有的蚂蚁从同一个城市i0出发，i:1。当前最好解W(1,2,,n)。 （二）（外循环）如果满足算法的停止规则，停止计算并输出计算得到的最好解，否则，让蚂蚁s从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集，1sm。 （三）（内循环）按蚂蚁1sm的顺序分别计算。当蚂蚁在城市i，若L(s)N或l(i,j)A,lL(s)，完成第s只Tl(i,j)A,lL(s)i则以概率 0蚂蚁的计算。否则，若L(s)N且ij(kl)jT Pijij(kl)lTjT0,到达j,L(s)L(s)j,i:j； 若L(s)N且Tl(i,j)A,lL(s)i0，则到达i0,L(s)L(s)i0,i:i0；重复步骤三 （四）对1sm，若L(s)N,按L(s)中城市的顺序计算路径长度；若L(s)N，路径长度是一个充分大的数。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若f(L(t))f(W)，则W:L(t)。用下式对W路径上的弧信息素痕迹加强，对其他弧的信息素痕迹挥发， k1(1)(k1),i,j)为W的一条弧（k1ij ijW其他(1k1)ij(k1),得到新的ij(k),k:k1，重复步骤二 Q,若第k只蚂蚁时刻t和t1之间经过i，jk ij否则0, 本文来源：https://www.wddqw.com/doc/e8e22200954bcf84b9d528ea81c758f5f61f2999.html