近代工程优化简答题

1.简述传统优化算法与遗传算法的特点及其优缺点。传统优化算法的特点：A.传统优化算法一般是确定性算法，有固定的结构和参数，计算复杂度和收敛性可做理论分析。B.传统优化算法大多属于凸优化范畴，有唯一明确的全局最优解。C.传统优化算法一般是针对结构化的问题，有较为明确的问题和条件描述，如线性规划、二次规划、整数规划、混合规划、带约束和不带约束等，即有清晰的结构信息。遗传算法的特点：A.遗传算法是对参数的编码进行操作，而不是对参数本身，因而适应于求解复杂的优化问题，应用范围很广。B.遗传算法属于种群搜索算法，易于并行处理，可以有效防止局部搜索过程收敛于局部最优解，而且有较大的可能求得全局最优解。C.遗传算法通过目标函数来计算适应度值，而不需要其他信息，从而对问题的依赖性较小。D.遗传算法使用概率的转变原则，而不是确定性的规则。E.遗传算法在解空间内不是盲目地穷举或完全随机搜索，而是一种启发性搜索，其搜索效率往往优于其它方法。F.遗传算法对于待寻优的函数基本无限制，因而应用范围很广。遗传算法的优点：A.与问题领域无关且具有快速随机的搜索能力。B.搜索从群体出发，具有潜在的并行性，可以进行多个个体的同时比较。C.搜索使用评价函数启发，过程简单D.使用概率机制进行迭代，具有随机性。E.具有可扩展性，容易与其他算法结合。遗传算法的缺点：A.收敛速度慢。B.局部搜索能力较差。C.控制变量较多。D.无确定的终止准则。2.简述遗传算法的基本原理，并给出基本遗传算法的求解步骤和流程图遗传算法的基本原理：遗传算法是模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标（适应度函数）从解群中选择较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行重组，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。基本遗传算法的求解步骤：A.初始化。设置进化代数计数器k=0，设置群体规模，最大进化代数M，交叉概率、变异概率。随机生成pop个个体作为初始种群。B.个体评价。计算群体p(k)中个体的适应度。C.终止条件判断。若kM，则以当前的种群中具有最大适应度的个体作为最优解输出，终止计算。否则，转步骤D。D.选择操作。将选择算子作用于群体。E.交叉操作。将交叉算子作用于群体F.变异操作。将变异算子作用于群体。G.群体p(k)经过选择、交叉和变异操作后得到下一代群体p(k+1)，令k=k+1，转步骤B。3.简述遗传算法中，DeJong提出的两条具体的编码原则。A．有意义积木块编码原则。所采用的编码应易于生成与所求问题相关的低阶、短定义距以及平均适应度高于群体平均适应度的积木块。B．最小字符集编码原则。所采用的编码应采用最小字符集，以使问题得以自然的描述。DeJong基于模式定理和积木块假设提出了原则1。在很多情况下，染色体中的基因的地位并不平等，某些基因的突变将对适应度值带来很大变化，而另一种基因的变化对适应度值的影响较小。影响大的基于成为敏感基因。许多敏感基因家当的组合决定了GA的寻优方向。在实际编码时，按原则1，应将敏感基因排列在一起，形成所谓的密排基因快，这种密排基因快一旦形成，不易被破坏，容易被子代继承。DeJong提出的原则2实际上是一个被广泛采用和认可的原则。最早提出并使用至今的二值编码即符合这一原则。这不仅是因为二值编码是最简单的编码形式，更重要的是二值编码含有更多的模式，更容易找到染色体的相似结构。4.在遗传算法中，对实数变量采用二进制方式编码。假设一维实变量X的取值范围为[XL,XU]，其编码精度为δ，写出二进制编码长度N应满足的数学关系式，以及相应的编码、译码数学关系式。由于参数X的取值范围为[XL,XU]，编码精度为δ，所以将[XL,XU]分为（XU-XL）/δ份，则编码的长度N应满足：2𝑁−1𝑋𝑈−X𝐿δ≤2𝑁−1log2(𝑋𝑈−X𝐿δ+1)≤𝑁log2(𝑋𝑈−X𝐿δ)+1得到串长为N的二进制数，最小整数为0，最大整数为2𝑁−1。所有N位二进制数为0,1,2，……2𝑁−1，共有2𝑁个整数。设串长为N的二进制表示为B=bLbL-1……b2b1，bi∈{0,1}。则它的整数I为I=∑𝑏𝑖×2𝑖−1𝑁𝑖=1。一般地，对定义在区间[XL,XU]上的一维实变量X，用N为二进制码bNbN-1…b2b1,对其进行编码，则X与二进制码之间的关系为X=X𝐿+𝑋𝑈−X𝐿2𝑁−1∑𝑏𝑖×2𝑖−1𝑁𝑖=15.简述进化算法中种群规模和初始种群的设定原则。种群规模是遗传算法的控制参数之一，如何设定种群规模是一个未解决的问题。种群规模太大，计算量增大，影响GA的效率，也会影响交叉策略。而群体规模太小，GA搜索空间有限，会导致未成熟收敛现象。实际中，群体规模在几十到几百之间取值、问题越难。维数越高，种群规模越大。初始种群的设定，一般情况下，GA随机生成初始种群。在有先验知识的情况下，应根据已有的信息生成初始种群。在无任何先验知识的情况下，初始种群应均匀散步在搜索空间中，以增强初始种群的多样性，提高GA求得全局最优解的概率。6.简述遗传算法中常用的适应度比例选择和联赛选择方法，以及其使用的条件。适应度比例选择方法又称为轮盘赌方法，采用该策略选择时，各个个体被选择的概率与其适应度成正比。即选取的概率为该个体的适应值与每个个体适应度总和的比值。条件为适应度函数f(x)0。联赛选择方法它是基于个体适应度值之间大小关系的选择方法，不必满足f(x)0的条件。每次进行适应度值大小比较的个体数目称为联赛的规模。一般联赛规模N=2。过程如下：A．从群体中随机选N个个体进行适应度值大小进行比较，将适应度值最高的个体遗传给下一代。B．将上述过程重复M次，就可得到下一代群体中的M个个体。7.简述遗传算法中常用的两种交叉运算方法，并分别举例说明。遗传算法常用的两种交叉运算为单点交叉和双点交叉。单点交叉又称为简单交叉，当染色体长度为N时，可能有N-1个交叉点，因此可能有N-1个交叉结果。例如两个染色体的序列分别为：xxyxyxxyyx，xyyyyxxyx在第四点进行交叉，则交叉之后的染色体为xxyxyxxyx和xyyyyxxyyx双点交叉是在相互配对的两个个体编码串中随机设置两个交叉点，交换两个个体在所设定两个交叉点之间的部分染色体。例如，两个染色体序列分别为：xx|xxxx|xxx和yy|yyyy|yyy，则交叉后的染色体为xx|yyyy|xxx和yy|xxxx|yyy8.未成熟收敛是遗传算法中不可忽视的问题。请概述该算法中抑制未成熟收敛的对策。需要在编码、适应度函数、遗传操作等设计中考虑未成熟收敛的对策。这些对策有：A．提高变异概率：在进化初期，可增强GA的随机搜索能力。B．调整选择概率：可把选择概率本身作为变量来进行优化，这就是所谓的元GA（metaGA）法。C．合适定标：对适应度函数进行定标。D．维持群体中个体的多样性。方法如下：a．增加种群规模。但要考虑计算量的因素。b．实施局部化：把群体分割成若干个子群体，每个子群体独立地进行选择操作，这样可将不适当的个体产生的未成熟收敛现象局部化。c．实施单一化：把相同的个体单一化，即群体中不允许有相同的个体存在。d．增加配对个体的距离。配对选择一般是随机进行的，其中缺少对个体间的相似度的判断，因此，有可能使交叉未能产生新个体。作为改进可用海明距离测度来判断配对个体的相似度，并由此决定配对与否。上述几个对策的效果各不相同，它们可在进化过程中分阶段使用和交替使用。9.在差分进化算法中，采用“DE/x/y”表示不同版本的变异策略。请写出DE/rand/1”,“DE/best/1”,“DE/rand/2”，“DE/best/2”的变异策略公式。“DE/rand/1”ViG=Xr1,G+F(Xr2,G-Xr3,G)“DE/best/1”ViG=Xbest1,G+F(Xr1,G-Xr2,G)“DE/rand/2”ViG=Xr1,G+F(Xr2,G-Xr3,G)+F(Xr4,G-Xr5,G)“DE/best/2”ViG=Xbest1,G+F(Xr1,G-Xr2,G)+F(Xr3,G-Xr4,G)其中，r1，r2，r3，r4，r5是从[1,NP]中随机选取的正整数，且r1≠r2≠r3≠r4≠r5≠i。Xbest,G是当前代NP个个体中具有最佳适应度值的个体。尺度因子F是一个正实常数，它控制差分向量的缩放，一般F∈[0,2]。F值越大，会导致生成的种群有较高的多样性，而F值越小，可使算法较快的收敛。10.简述差分进化算法的基本原理和求解步骤。差分进化算法的基本原理：DE开始于一个随机选择的初始种群，主要过程包括变异、交叉和选择三个步骤。DE的主要思想是从某一组随机产生的初始种群开始，随机选择两个不同的个体向量相减生成差异向量，将差异向量赋予权值后与第三个随机选择的个体向量相加，产生变异向量。然后将变异向量与预先确定的父代个体向量按一定规则交叉产生试验向量。若试验向量的适应度优于父代个体向量的适应度值，则选用试验向量进入下一代，否则保留父代个体向量。通过不断进化保留优胜的个体，引导搜索过程向最优解逼近。差分进化算法求解步骤：1.初始化种群。DE算法是在D维空间中搜索全局最优解。首先需要选择包含NP个个体的初始化种群。种群中个体向量也称为目标变量，第G代中i个个体可表示为Xi,G=(X1i,G,X2i,G,…XDi,G),其中G=0,1…，Gmax，G=0表示初始种群，Gmax表示最大代数，i=1~NP。事实上，对实际问题，每维参数都有一定的取值范围，假设Xj，min≤Xj≤Xj,max,j=1,2…D。我们希望初始种群尽可能的均匀分布在解空间中。因此，初始种群中第i个个体的第j个参数可写为X=Xj,min+randji(0,1)*(Xj.max-Xj,min)，式中randji(0,1)为在区间（0,1）中均匀分布的随机数。2.变异算子DE算法通过变异操作产生变异向量Vi,G，对每一个个体Xi,j采用一定的变异策略生成相应的变异向量Vi,G=（V1i,G，V2i,G，…，VDi,G）。针对不同的变异策略，发展了不同版本的DE算法。为了区别不同版本的DE算法，采用记号DE/x/y，其中x表示变异策略的类型，y表示差分向量个数。现在DE变异算法主要有DE/rand/1、DE/best/1、DE/rand/2、DE/best/2、DE/rand-to-best/1。3.交叉算子为了增强种群的多样性，引入交叉算子。交叉操作是把每个变异向量Vi,G和个体向量XiG的每一维参数按照一定规则混合产生新的试验变量UiG=（U1i,G,U2i,G,…UDi,G）。在DE算法中，二项式交叉常被采用，其数学表达式为：始终CR∈[0,1]是一个由使用者提供的实值交叉概率常数，同差分缩放因子F一样，是DE算法的控制参数。randj(0,1)是（0,1）中的均匀随机数，k∈[1,D]随机选取，用来确保试验向量UiG中至少有一个是由变异向量Vi,G贡献。在交叉运算之后，通常需要对新生成的试验向量的每一维参数进行检验，若新生成的试验向量中某一维参数超出了给定解的范围，则按照下式对其重新初始化：4.选择算子DE采用贪婪选择策略产生子代个体。经过变异和交叉操作后的试验向量UiG与个体向量Vi,G进行竞争，两者中适应度值更优的个体作为子代个体。选择算子可用如下表示：