基于遗传算法的多对象优化在CFD中的应用

基于遗传算法的多对象优化在CFD中的应用摘要：这份报告涉及到在空气动力学优化结构设计中的多对象优化设计问题。这种所使用的优化算法是一种半随机更加精确的遗传算法。遗传算法是一种十分健全的优化算法对于以下几种问题十分适合：（1）初始值不确定（2）所要优化的参数不是相同的类型（二进制变量，整数，实数，函数）（3）所处理的成本函数有多个极小值（4）多个标准要被考虑在列（多个物理变量，效率，成本，质量....).在多对象优化设计问题中，并没有一个最优解，而是一些列的有可能的关于多个变量同时考虑的最优解决方案。这些概念明确以后，遗传算法就可以运用和被验证于学术问题上了，然后数值试验就可以开始进行来解决多目标结构优化从而设计在欧拉流动中的机翼设计。关键字：多对象优化设计帕氏最优状态遗传算法欧拉方程结构参数化同步计算1简介在我们日常生活中，我们通常都会遇到多对象优化的问题，比如买一个电视机要同时考虑到价格与质量的因素，或者选择最节省时间和距离的上班路线。在航空工程师协会，科学家努力用最小的花费设计出最优化的飞行器（最小的重量，最大的安全性...）在经济领域里，经济学家试图调节商品的使用和消费来谋取最大的对于每个人社会福利。优化问题中普遍的问题是要求我们把几个标准要求同时考虑。在这些问题中，考虑单一变量的优化方法已经不再适用，而是应该采用多对象优化的计算方法。大量的多对象优化方法的实力已经在书面上体现了出来，Cohon的书就是一个对于这个问题的很好的背景参考。在一个简单的优化问题中，优化问题的概念是很直接的，我们寻找一个函数的最值（最大或最小。然而在一个多对象优化问题中，最优解的概念就不是那么明显了。实现如果我们假设我们不能把两个事物的价值联系起来（比如我们不能比较苹果和橘子）那么，我们就要构造一个考虑到所有限制条件的最优解的新的定义，然后帕雷托优化算法就出现了。当然关于多变量问题，没有一个方案是最适合的，而是存在一系列的最优解比现在的方案好。这一系列的解叫做帕雷托优化解系或者叫做不受控制解系。与之相对应的解系叫做受控制解系。属于帕雷托优化解系的解彼此之间相互独立，他们之间是不可以比较的，这些解系中的每一个解都叫做可行解。选择解的依据是要求我们对这个所解决的问题有足够的知识储备和对这个解决问题的相关知识有足够多的了解，所以，不同的决策者就会做出不同的决策。有两种解决多目标优化问题的方法，第一种是建立对于各个变量的加权函数关系，然后求这个加权函数的最值。当然，这种方法有两个最主要的缺点：（1）并不能找到所有的解（2）在补偿函数中，对于一些标准所赋予的权重并不适合这个函数并且有可能导致函数的无意义。另一方面，遗传算法作用于整个可能解的范围（之所以是可能性，应为这些解都属于可行空间内），然后，在优化算法中，遗传算法会遍历可行区间，建立解的云数据库。当云没有跟多的演变，云函数此时收敛，然后，就求出了帕雷托优化解系。在此篇论文里，我们在第二部分对遗传算法做了一个简要的介绍（当然有很多遗传算法的相关书籍）。在第三部分，我们详细的给出了多对象优化问题的定义以及其详细的应用法则。最后在第五部分，我们会阐述遗传算法解决多对象结构优化设计在计算流体力学当中的应用。2关于遗传算法的简介2.1简介遗传算法是基于自然选择规律和达尔文著名的物竞天择理论的推演。遗传算法在以下方面区别于其他的优化算法：1.遗传算法同时作用于整个可能解的区域（也叫做染色体或个体）而不是周期性的产生重复的元素。2.染色体是由双螺旋结构决定遗传物质的。3.对已目标价值函数的斜率计算是不必要的。4.遗传算法有更大的潜力在整个探索区间里探索并且寻找局部最大值最后汇集成为整体坐标最值（从点到点的方式在局部优化中可能会遇到麻烦）5.遗传算法，一种半随机的算法，在没有微分，多种方式或者凸函数的情况下被证实是一种健全的算法。2.2遗传算法是怎样运作的一个物种的染色体通过一代一代的连续的进化和不断对问题的优化而变成更好的个体，所有的种群都适用于三种基因工具：选择，转型，突变。一个种群要么生存，繁衍，或者死亡。这一切都是取决于他们的价值函数的优化以及自身的健康值。2.3遗传算子选择操作——根据他们的价值函数，一个染色体会复制，生存，或者死亡。这是按以下两种方式选择的：1.旋转轮：每一个个体被赋予一个合适度值以此来模拟一个带权重的旋转轮，每一个遗传链条都对应在旋转轮上占一定的比例，这个比例正比于他的适应度值。为了产生一个新的物种，这个旋转轮会旋转n次，这里n是指这个物种的总量。在最大化问题中，很显然拥有在旋转轮上更大比例的个体比其他个体更有机会存活或繁衍。（见图一）2.联赛选择：最通用的策略是两两竞争，同样也被叫做亮点竞争。它包含了首先从总体中选出两个个体，然后比较他们两个个体。优秀的那一个被保留下来，并且获得繁殖权利。这个过程反复进行，直到新的物种产生。交叉算子——由于选择并不能创造新的物种，交叉互换就是一种必要的产生新的物种的方式。这种情况发生的概率特别大。两个个体被随机的选择并发生交叉互换。然后取一个介于1到L-1（L是这个染色体链的长度）的整数K（K表示交叉互换发生的位置）。两条新的链（叫做后代）就通过交换从K+1位置到L位置的所有遗传信息。如图二突变算子——突变算子是十分重要的，因为在选择和交叉变换中，会有重要的遗传信息偶然的丢失（1或0的在某一个位置的突变）。这种变化只在很小的程度上的小概率事件（概率接近0.001），它包含了从1变为0和从0变为1两种方式。3多对象优化问题3.1对对象问题简述一个面向多对象优化设计的问题包括了多个需要同时考虑优化的对象和一定的相等的不相等的限制条件（可参照Cohon的书获取更多背景知识）这样的问题可以用一下形式表示：其中的是目标函数的表达式，N是目标的个数，是一个含有p个部件的向量，而向量的变化随着这些部件的构成或决定而变化。在一个求最小值问题当中,一个向量被称作不大于另一个向量当满足以下条件的时候并且至少存在一个i似的。我们就说支配举个例子，比如谁一个关于两个变量的最小值问题：我们可以说支配当存在以下条件时：3.2解决多对象问题的一种经典方法解决多对象问题的一个普遍困难是多个对象之间的互相冲突：总的说来，就是指没有一个可行解相对于所有的对象来说是最优的，当然，帕雷托解系会使各个对象的冲突最小化。其中最经典的一种求解方法是在九十年代被广泛应用于经济领域的对象权重法（参看Cohon【1】），多对象目标函数通过函数以以下的形式彼此关联起来：很显然，对于每一个目标的喜好可以通过改变相应的目标权重来调节。另一方面，我们会看到我们把每个对象加以权重必然会导致信息的大量浪费。这种方法唯一的优点是每一个目标都可以拿来互相比较并且比较所得到的优化解属于帕雷托解系。这个方法主要的缺点是我们并不能找到所有的解，另外，有可能对所研究的优化问题中的对象给出完全不符合逻辑的权重系数。3.3遗传算法的应用3.3.1排名靠前的优秀算法遗传算法通过适应度函数的值选择个体，然而，在多对象优化问题中，都是多个标准同时考虑的，对一个个体的评估就要求我们用一个特殊的适应度值，这个以某种合适的方法所确定的适应度值就被叫做模拟适应度。为了达到此目的，染色体首先以它们的开头被分类，这些在总体中不受控制的个体被记为1开头，然后，在剩下的个体中，不被控制的个体记为2开头，以此类推，直到以f开头的个体。为了解释清楚这个问题，我们设想由两个控制变量J1和J2所决定的30个个体，我们将他们分类，随机选取J1和J2的数值然后赋给30个个体。图三显示了这个分组情况。从这个例子我们可以看出以开头的的个体比以开头的个体更有机会繁衍下去。图三一旦一个个体被排名标记了以后，那么他的适应度值就被以下公式所赋予其中r是这个个体所赋予的排名值。3..3.2一个早期的关于遗传算法在多对象优化设计当中的应用由于遗传算法适用于整个种群的个体，它的构架结构决定了这种算法能够找到属于优化解系的所有解或者更精确的非支配性的帕雷托解。就我们所知道的的而言，遗传算法的最早应用被记载于斯卡夫在他1984年的学位论文中，之后，horn和Nafpliotis，Srinivas和Deb以及Golderberg做了与斯卡夫相近的方法，这种方法叫做向量评估遗传算法。斯卡夫的任务是减少开支和提高可靠性。为了达到目的，他将原始的种群分成两个数量相同的亚种群，并对两个亚种群给以优化选择。在经过数代衍化之后，两个种群的优化选择趋于相同。这个方法开启了研究多对象问题的新的篇章。所得到的结果是振奋人心的，但是所得到的的解最后只收敛到了帕雷托解系当中的一个点，这两个点与所给条件所要求的最优解释相符的。所以，向量遗传评估法给我们提供了充分的证据，即所有的种群都应该以物种的形式来予以区分。而为了保持多元化，一种与共享技术结合的非支配排序方法就因运而生了。我们的多对象优化结果是基于和的叫做非支配排序遗传算法。在接下来的章节里，我们具体讨论非支配排序遗传算法（NSGA）。3.4非支配排序遗传算法（NSGA）非支配排序的过程利用了强调优化值排名的选择方法。这种算法被用来使亚种群达到一个比较稳定良好的优化值。我们之所以这样做，是应因为在遗传算法多对象优化问题中的一个主要缺点是与可能提前收敛。在某些状况下，遗传算法会很快的收敛在某个帕雷托解系的点上，并且由于这个相关的解由于其他的解（这个被叫做超级个体），这个个体繁衍后代并且，经过一定代数的繁衍后，一个只有这个物体复制出来的种群就会出现！相同的，我们有可能得到的一组帕雷托解只由一小部分元素构成（就像在VGEA例子中只由两个点元素构成）。为了避免这种情况的发生，非支配排序技术结合了小生境方法当有解在多个复制个体中被发现的时候。然后，适应度值减少，然后在下一代中，一个新的解就会出现即使他的竞争力并不是那么强。适应度值之所以减少，是由于选择的不同的优化方案有着不同的niche值。这种方法按以下步骤进行：1.在对可选方案进行选择以前，我们要首先列出符合非支配条件的个体（根据标准确定）就如同在图3.1所表示的那样，这些个体以1开头，那么他们可以繁衍的几率就会比较大。2.接下来，我们把相同的虚拟适应度值赋予每个有1开头的非支配个体（总的来说，虚拟适应度值等于1）3.为了保持多样性，属于每个个体的适应度值就会被拆分：分配的规则是在一定半径内与这个范围内所有的个体数成正比。如果一个个体有许多个邻居的话，就有许多的相似解系存在，并且适应度值就会被分配到下一代中，以保持遗传多样性。我们叫这种现象为生态位。用以下方式定量表示：其中，i是每个个体的索引，M是这个个体所属的开头的数字，是共享函数，是关于d的线性递减函数，定义如下：其中：是理论上两个个体要组成一组生态位的最大距离，它的值的确定是由操作者根据具体情况实际分析给出的。在Goldberg的方法中，采用了一种适应性生态位策略来克服共享函数的限制。是两个个体i和j的距离。在多对象优化问题当中，常常用到汉明距。它是指基因型的距离并且这个距离的计算包括了基因链的首尾。这种距离的概念应用于电磁学优化设计领域。在这种情况下，汉明距就有十分实际的意义因为这里的1,0并不表示实际意义上的编码，而是反映了所控制元素的激活与否。然而处理双链结构的问题中，汉明距离有可能会有偏差因为两个相邻解可能会有一个很大的汉明距（0111和1000所对应的事7和8，它们是相邻的，然而却具有最大的汉明距）。在这种情况下，表型距离就应运而生了，欧几里得距离按以下形式表示：其中np是定义染色体i和j的参数，是i染色体的价值数k；并且，M是属于目前链上的个体总数。定义完了生态位之后，我们就可以对每一个个体赋予一个新的虚拟适应度值了即。在上面的分配进行完之后，非支配个体就可以占时从总体中忽略了，对于这条新的端头，我们首分配属于每个个体相同的虚拟适应度值，这个适应度值是上个开头中的最小值。我们重复这个过程，知道整个种群中的每个个体都遍历到。现在，虚拟适应度函数都被分配到了种群中的每个个体，所以，选择，交叉互换，和突变就可以正常的进行了，相应的方