演化计算 作业

演化计算试卷

（Evolutionary Computation 2014） 12级23系李炎PB12210235

1、（a）区别：演化计算算法中操作的每一个个体（或者说可能的解）都是基因型，基因型就是解的表示，而表现型指的是每个解的目标函数（或称适应函数，例如，最优化问题中，想获得最大或者最小值的函数）值。每一个基因型一定有一个表现型，但是每个表现型可能对应多个基因型。 联系：演化计算算法中，演化算子操作于基因型上，但是选择操作于表现型上。演化计算通过选择表现型从而获得较好的基因型（解）。 （b）杂交（crossover）有两个输入作为父母（parents），子代从父母中各获得一部分基因型，组成自己的基因型。这样做可以尽可能获得兼具父母两方优点的，比父代性能优异的子代。与一元操作（如变异）相比，这样产生的子代更有可能具有父母两方的优点（当然也有可能具有父母两方的缺点，但是这样的个体会被选择掉），具有很强的方向性，效率较高。而变异没有方向性，子代是父代随机的改变，没有方向性，效率较低。

（c）协同演化计算（co-evolutionary algorithms）中，会构造两个或者多个种群，建立它们之间的竞争或合作关系，多个种群通过相互作用提高各自性能，以达到种群优化的目的；其个体适应函数是由所有种群个体（而不是只有个体所在的种群或者个体本身）决定的。而普通的演化计算（evolutionary algorithms）一般只涉及一个种群，适应函数由个体本身基因型或者个体与本种群的相互作用决定。 2、（a）不同。1-bit mutation是随机选择解x中的某一位进行翻转，产生新解x1；而bitwise mutation是以一定概率同时翻转解x中的所有位，产生新解x1。

（b）例如x1=00100,x2=11101，若用GA，则通过crossover或（和）mutation产生多个依赖于x1、x2的多个新解（子代），例如11100（仅用crossover，x2前三个，x2后两个）。而EDA先计算每个数字为1的比例（1/2,1/2,1,0,1/2），在根据这个比例随机产生若干个子代。总结来说，EDA删去了GA产生子代的过程，改为学习（learn）每个数字的概率分布，再按照概率分布随机产生新解（或者说，采样（sample）产生新解）。 （c）可以 算法ACO

初始化参数、蚁群等，初始化信息素 while（不满足结束条件）do for 蚁群中的每只蚂蚁 根据信息素分布，修正行动方向 在一定的概率下，对方向进行随机扰动 end for 更新信息素分布及蚁群状态 end while

（d）它们都是将父代的信息转化为概率分布，然后根据概率分布产生子代。在ACO中，每代蚁群不断产生信息素，信息素浓度包含了蚂蚁出现在此处的概率信息，通过信息素浓度决策产生子代；而在EDA中，直接计算每个数字取1的概率，这也可以理解为一种空间概率分布，然后根据这个分布随机产生子代。它们是十分相似的两个算法。 3、（a）优点：简单易行，不需要加入很复杂的运算；与具体演化计算算法无关，适应性强；

在惩罚因子合适时可以在低计算量条件下快速找到最优解。 潜在的问题：合适的惩罚因子难以估计和选取，甚至有时连好的惩罚函数的形式都难以确定。若惩罚因子过小，则惩罚项所占比例较小，不容易产生可行解；若惩罚因子过大，则过于强调解的可行性而较早地收敛到某个局部最优解，不容易跨越不满足约束条件的区域而找到全局最优解。但是，如果为了确定合适的惩罚因子而加大计算量，惩罚函数法简单易行的优点就不复存在。

（b）惩罚因子过小的情形：（图借用了课堂PPT中的图）

图中f(x)为原始的目标函数，Φ1(x)、Φ2(x)为不同惩罚因子下的加入惩罚项的目标函数。我们要寻找令目标函数取最小值的点。Φ1(x)比Φ2(x)的惩罚因子大。考察Φ2(x)的情况，这时加入惩罚函数以后最低点仍在infeasible region，算法很有可能会使种群趋向于这个最低点，从而得到很多无效解，难以获得有效的最优解（这个最低点离应该找到的最低点很远）。总而言之，如果惩罚因子不足以抵消无效区的目标函数优势，则会使找到的解大多为无效解。 惩罚因子过大的情形：

如下图，有两个峰的为加入惩罚因子后的目标函数，仍找最小值。在这种情况中，如果原始种群没有落在两个无效区之间的有效区（A区），那么由于惩罚函数的作用，外部的解将难以跨越两个峰而进入A区，同样难以找到全局最优解。总而言之，如果惩罚因子过大以至于阻挡了两个有效区之间的跨越，则会使解迅速在一个有效区内收敛而难以找到全局最优解。

A infeasible region infeasibleregion （c）不能。如前所述，若惩罚因子较小且在无效区（infeasible region）目标函数表现明显优于有效区（feasible region），那么加入惩罚因子后的新目标函数表现最好的地方会在无效区。如果演化算法性能较好（这是较理想的情况），最后得到的解都会在新目标函数表现最好的地方附近，即无效区内，这样就不能找到一个有效的解。

4、（a）可能。突变算子具有很强的随机性，尽管是相同的突变算子，几次运行的结果也可能相差很多。不过据计算，A、B数据集的标准差相差较多，X=Y的可能性并不大。

（b）不是。A、B的平均值和中位数值都差不多，但是其标准差相差很大（A:25.7,B:5.1），也就是说，A算子比较不稳定，但是更容易找到全局最优解；B算子比较稳定，但是就目前的结果而言，可能较难找到全局最优解。因此，在实际运用中，应该视具体情况进行选择（如，若可以运行多次演化算法，则可以选用A算子以尽可能获得全局最优解）。只比较中位数或者平均数不能反映这个区别。

（c）统计学测试（statistical test）是用统计学的方法，对算法运行的结果进行分析计算，以达到对算法进行评估、比较的目的。

Significant difference指的是，在两个算法相同的假设下，得到该统计结果的概率低于一个临界值α（一般为1%~2%），那么可以认为在一定的置信概率下两个算法是有显著不同的。 平均数和中位数的区别体现在平均数的不足上。平均数对离群点或异常点缺少鲁棒性，且只能用于均衡的分布而不能用于倾斜分布；中位数对离群点或异常点具有鲁棒性，对分布的适用范围也更广。

（d）非参数检验（non-parametric test）。参数检验都是假定数据的分布规律已知，估计参数的值。但是在该问题中，我们不知道数据的分布规律，并且也不能轻易假定是正态的（信息太少），因此不能用参数检验的方法。非参数检验不需要已知分布规律，并且具有更强的鲁棒性。 5、（a）一个solution即一种用若干个确定重量的beam以确定的结构做成一个truss的一种搭法，我们可以用一个表示每个可能的beam位置所用铁质量的向量W=(w1, w2, …, wn)即为一个解。可以约定不用beam的位置w=0。

（b）每个解用实数值来编码（就像（a）中所述的向量一样），用一个定长实数向量代表一个解。这样解空间是一个N维非负实数空间。

（c）搜索操作符由交配（crossover）和突变（mutation）两个操作符组成。Crossover使用intermediate crossover，子代解（向量）每一个分量的值是父代对应分量之间的值（例如，两个父代为3和5，则子代在3~5内取值）。Mutation采用普通的正态分布随机，例如原值为3，则以均值为3的正态分布产生若干个变异后代。用这种方式对解空间进行搜索。 （d）这是一个多目标优化问题。它有两个优化目标：总质量Wtotal=w1+w2+…+wn，这个值要求最小化；总承重F = F(W)，这个函数是由结构计算出承重的函数，这个值要求最大。 （e）使用普通的GA（Genetic Algorithms）应该就能达到较好的效果。考虑到搜索域维度较大，为了加快搜索速度，增大搜索广度，可以采用PSO（ParticleSwarm Optimization），因为这样可以充分运用所有个体优势，并且在该问题中，两个beam的效果有较强的线性叠加性（非线性的程度并不会特别大）。

（f）多个解。因为这是一个多目标优化问题，视实际情况的不同需要，可能需要不同的解。例如，需要提供不同价位（即不同Wtotal），对应不同承重能力（F）的多种商品，以适应市场需要。

（g）可以通过一个简易的EA算法来得到较好的参数，同时采用racing procesures技术，即及早停止计算初期表现不好的解。因为这个问题所需参数较多，包括crossover产生后代个数即分布、mutation产生后代个数及分布（方差）、每次选择个体数等，使用一个简易的EA，短时间运行得到所需参数。

（h）使用统计学测试（statistical test）的方法。运行算法多次（可以每次运行较少代），得到每一次的结果，计算每次Wtotal和F的中位数，考察其分布，检验其是否满足要求。