三角分解

关键词： 进化 优化 目标 算法

三角分解（精选三篇）

三角分解 篇1

Zhang和Li[2]通过预先产生均匀分布的权值向量将多目标优化问题转换为一组单目标子问题,并为每个子问题分配一个个体,从而提出了MOEA/D(Multiobjective Evolutionary Algorithm based on Decomposition)[3]。在进化的过程中使用了差分算子,实验表明,该算法能有效地处理高维问题及决策空间不连续问题[3]]。

使用差分算子解决多目标优化问题时,对于多目标优化问题,简单的运用差分算子进行全局搜索,面临着全局的搜索能力较差的问题,并不能够使算法得到更好的结果。有鉴于此我们引入三角差分算子运用基于分解的多目标优化算法。

1 改进的MOEA/D算法

MOEA/D在将多目标优化问题分解为一组单目标子问题并为每个子问题分配一个个体,由各个子问题上的个体组成初始种群,通过均匀的并行进化各个子问题而得到一组解集。基于邻域的进化是MOEA/D的有效搜索机制之一。此外,为了计算适应度,MOEA/D算法成功地将数学规划中常用的分解方法引入到进化多目标领域,使用分解方法计算适应度可以直接采用求解单目标优化问题时的适应度分配和多样性保持策略[3]。目前最常用的分解方法有:Weighted Sum、Tchebycheff和Penalty-based Boundary Intersection(PBI)。

1)Weighted Sum分解方法

2)Tchebycheff分解方法

3)PBI分解方法

其中,θ>0为预设参数。

MOEA/D的算法流程如下:

基于目标空间分解的多目标进化算法(MOEA/D)

2 差分算法与三角差分算法

DE有三个主要操作称为变异(Mutation)、交叉(Crossover)和选择(Selection),但这些操作的实现和其它的进化算法是完全不同的。设群体规模为NP,向量的维度为D,那么群体中的目标向量可以用xi=[xi1,xi2,⋯,xiD](i=1,⋯,NP)表示。对于任意一个目标向量xi而言,按下面公式生成变异向量vi:

vi=xr1+F×(xr2-xr3),i=1,⋯,NP(1)其中xr1,xr2,xr3是群体中随机选择的三个个体,并且r1≠r2≠r3≠i。F是一个介于[0,2]间的实型常量因子,用于控制差向量(xr2-xr3)的影响,一般称为放缩因子。显然xr2和xr3之间的差向量越小,扰动也就越小,这意味着如果群体靠近优化值,扰动会自动减小。

DE的交叉操作的目的是通过变异向量vi和目标向量xi的结合来提高变异向量的多样性。算法通过下面公式生成新的向量ui=[ui1,ui2,⋯,uiD]]

这里,randb是[0,1]间的随机数;CR是范围在[0,1]间的常数,称为交叉常量,CR值越大,发生交叉的可能就越大,CR=0表示没有交叉;randr是在[1,D]随机选择的整数,它保证ui至少要从vi中获得一个元素,否则就不会有新的向量生成,群体也就不会发生变化。在本文中CR我们取1。

由上可知,差分算子的搜索空间由差向量决定,而在三个个体之间产生下一代个体时,三个个体之间无法取到,缩小了搜索范围,由此在解决多目标优化问题时,我们改进其空间取值其公式如下:

3 算法测试及结果分析

算法的所有参数都采用文献[3]所给出的参数,为了说明算法的有效性,实验采用综合性能指标IGD(Inverted Generational Distance)[4]来评价算法的性能,IGD能够给出算法的收敛性和分布性,计算如下:

P*是目标空间中均匀分布在真实Pareto面上的点的集合,P为待评价点的集合,d(v,P)是v到P的最小欧几里德距离。

在与原算法对比时选取测试函数如下:

F1:

其中J1={j|j是奇数},J2={j|j是奇数},变量的范围为[0 1]

F2:

其中J1={j|j是奇数},J2={j|j是奇数},变量的范围为[0 1]

F3:

其中J1={j|j是奇数},J2={j|j是奇数},变量的范围为[0 1]

从上表中可以看出,在三个测试函数中无论是平均值还是最小值,本文所提出的改进算法都要优于原始的算法。我们的算法是有效的。

4 结论

本文指出多目标演化算法在解决多目标优化问题时,由于给每个子问题均衡的分配各个计算性资源,导致进化时各个子问题的分配不同,而使算法难以得到的效果不好,从而提出了一种,非均衡的分配方案,实验结果证明了改进的策略的有效性。

参考文献

[1]郑金华.多目标进化算法及其应用[M].北京:科学出版社,2007.

[2]Deb K,Pratap A,Agarwal S.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on EvolutionaryComputation,2002,2:182-197.

[3]Zhang Q,Li H.MOEA/D:A Multiobjective Evolutionary Algorithm Based on Decomposition[J].IEEE transactions on evolution ary computation,2007,11:712-731.

巧用因式分解，妙解三角形问题 篇2

求证：△ABC为等边三角形.

解析：要证△ABC为等边三角形，只需证 == .根据等式的结构特征，可以把等式变形为（）2 + （）2 + （）2 = 0，则 == .

证明过程如下

由题意，得 2 + 2 + 2 = 0.

则22 + 22 + 22222 = 0.

即（）2 + （）2 + （）2 = 0.

∴ == .

即△ABC为等边三角形.

例2 已知 、、 是△ABC的三边长，且满足4 + 22= 4 + 2 2，试判断 △ABC的形状.

阅读下面解题过程：

解：由4 + 22= 4 + 2 2，得

44 = 2 222. ①

（2 + 2）（22）= 2（22）. ②

即2 + 2 = 2. ③

∴△ABC为直角三角形. ④

试问：以上解题过程是否正确？_________；若不正确，请指出错在哪一步.（填代号）_________；错误原因是______________________；本题的结论应为______________.

解析：本题以阅读理解的形式出现，难度降低了.仔细观察解答过程会发现，在②到 ③的过程中忽略了（22）为0的情况，当 = 时，等式②也是成立的，此时三角形为等腰三角形.故三角形为直角三角形或等腰三角形.

三角分解 篇3

在过去的十几年中,基于单位分解的概念,学者们提出了许多不同种类的数值近似方法,有单位分解法[1]、hp 云团法[2]、广义有限元法[3]等。单位分解有限元法较普通有限元的优点是能够自由地选择局部近似函数,这使其便于分析复杂问题。另外,单位分解法不需增加额外的结点,就能构造高阶的场函数。但是,单位分解法存在线性相关问题。为了克服这个问题,学者们提出了抑制高阶自由度、调整单元形状等方法。但是这些方法不能完全消除线性相关问题,而且实施过程复杂。

本文采用线性三角形形函数作为单位分解函数,利用最小二乘法建立局部近似场函数。该单元能够消除线性相关问题,能够像普通的有限元一样直接施加位移边界条件,并且其精度优于传统的线性三角形单元和线性四边形等参元。

1 有限元无网格耦合三角形单元公式

1.1 有限元无网格耦合三角形单元的形函数

对于二维线弹性问题,采用三角形网格离散问题域,如图1所示。单元内任一点的位移可表示成:

$u(x,y)={{\rm N}}^{\prime }u{}^e(1)$

式(1)中,N′=[N1N2N3]是传统的线性三角形单元的形函数矩阵。ue={u1(x,y) u2(x,y) u3(x,y)}T是局部结点位移函数。在该结点处等于其位移值,即:ui(xi,yi)=ui,i=1,2,3。局部结点位移函数ui(x,y)利用Rajendran等[4]中使用的最小二乘点插值无网格法(LSPIM),由i点的支持域内的结点值拟合得到:

$u{}_i(x,y)=\mathit{\Phi }{}_{\mathit{i}}\mathit{u}{}_{\mathit{i}},i=1,2,3(2)$

式(2)中,$\Phi {}_i=[\begin{array}{ccccc}\Phi {}_1^i& \Phi {}_2^i& \Phi {}_3^i& \cdots & \Phi {}_{{\rm N}}^i\end{array}],i=1,2,3$,$u{}_i=[\begin{array}{ccccc}u{}_1& u{}_2& u{}_3& \cdots & u{}_{{\rm N}}\end{array}]{}^{\text{Τ}}$。

其中Φi是LSPIM法的关于结点i的形函数矩阵,ui是结点i支持域内结点的位移参数向量,N是结点i支持域内的所有结点数。对于该单元内的其他结点,N可能不同。一个单元所有结点支持域的合集构成了一个单元的支持域Ω。

结点支持域和单元支持域的定义分别如图1所示。

将方程式(2)带入式(1)得:

$u(x,y)={\mathit{{\rm N}}}^{\prime }(\mathit{\Phi }\mathit{u})=({\mathit{{\rm N}}}^{\prime }\mathit{\Phi })\mathit{u}=\mathit{\Psi }\mathit{u}(3)$

从方程(3)中,可以得到该单元的形函数矩阵,设单元支持域Ω内的结点数为M:

$\underset{1\times {\rm M}}{{\displaystyle \mathit{\Psi }}}=\underset{1\times 3}{{\displaystyle {\mathit{{\rm N}}}^{\prime }}}\underset{3\times {\rm M}}{{\displaystyle \mathit{\Phi }}}=\left[\begin{array}{cccccc}\Psi {}_1& \Psi {}_2& \Psi {}_3& |\Psi {}_4& \cdots & \Psi {}_{{\rm M}}\end{array}\right](4)$

1.2 局部结点位移函数的形函数Φi

局部结点位移可以写成下列形式:

$\underset{{\rm N}\times 1}{{\displaystyle u{}_i}}=\underset{\mathit{{\rm N}}\times 6}{{\displaystyle \mathit{{\rm P}}}}\underset{6\times 1}{{\displaystyle a}}(5)$

式(5)中

式(5)中使用了二次多项式基(1,x,y,xy,x2,y2),也可以取前四项线性多项式基(1,x,y,xy)。

为方便起见,该单元的第一个结点记为结点i。

由于传统的最小二乘近似a=(PTP)-1PTui使得结点i的位移近似值不等于该点的位移值,即$u{}_i\ne p\left(x{}_i,y{}_i\right)a$,导致位移条件施加比较困难。故为了使节点i的位移近似值等于该点的位移值,利用方程(5)中的第一个方程解出a1,再从方程(5)其余的方程中消去a1,可得

$\underset{\left({\rm N}-1\right)\times 1}{{\displaystyle \overline{\mathit{u}{}_i}}}=\underset{\left({\rm N}-1\right)\times 5}{{\displaystyle \overline{\mathit{{\rm P}}}}}\underset{5\times 1}{{\displaystyle \overline{\mathit{a}}}}(6)$

式(6)中

则由最小二乘法得,

$\overline{a}=\overline{Q}\overline{u{}_i}(7)$

式(7)中,$\overline{\mathit{Q}}=\left(\overline{\mathit{{\rm P}}}{}^{\text{Τ}}\overline{\mathit{{\rm P}}}\right){}^{-1}\overline{\mathit{{\rm P}}}{}^{\text{Τ}}$

节点i邻域内位移又可以表示为

$u{}_i(x,y)=a{}_1+\overline{\mathit{p}}(x,y)\overline{\mathit{a}}(8)$

则,$u{}_i=a{}_1+\overline{\mathit{p}}(x{}_i,y{}_i)\overline{\mathit{a}}(9)$

并将式(7)、式(9)带入式(8)可得ui(x,y)表达式

$u{}_i(x,y)=u{}_i+\overline{q}\overline{\mathit{Q}}\overline{\mathit{u}{}_{\mathit{i}}}(10)$

式(10)中,$\overline{\mathit{q}}\equiv \overline{\mathit{q}}(x,y)=\overline{\mathit{p}}(x,y)-\overline{\mathit{p}}(x{}_i,y{}_i)$,$\overline{\mathit{p}}(x,y)=\left[\begin{array}{ccccc}x& y& x{}^2& xy& y{}^2\end{array}\right]$,$\overline{\mathit{p}}(x{}_i,y{}_i)=\left[\begin{array}{ccccc}x{}_i& y{}_i& x{}_i^2& x{}_{i}y{}_i& y{}_i^2\end{array}\right]$。

ui(x,y)表达式(10)可简写成:

$u{}_i(x,y)=\mathit{\Phi }{}_{\mathit{i}}\mathit{u}{}_{\mathit{i}}(11)$

此处,Φi为局部节点位移函数的形函数,可写成:

$\underset{1\times \text{Ν}}{{\displaystyle \mathit{\Phi }{}_{\mathit{i}}}}=\left[\begin{array}{l}\\ \end{array}1-\left(\underset{1\times 5}{{\displaystyle \overline{\mathit{q}}}}\underset{5\times ({\rm N}-1)}{{\displaystyle \overline{\mathit{Q}}}}\underset{\left({\rm N}-1\right)\times 1}{{\displaystyle 1}}\right)|\underset{1\times 5}{{\displaystyle \overline{\mathit{q}}}}\underset{5\times \left({\rm N}-1\right)}{{\displaystyle \overline{\mathit{Q}}}}\right](12)$

式(12)中1为所有元素均为1的(N-1)行列向量,利用式(4)进而可以求出单元的形函数矩阵Ψ。

从式(10)可以看出,对于(xi,yi)点存在$\overline{\mathit{q}}(x{}_i,y{}_i)=0$,则可得,$\underset{1\times {\rm N}}{{\displaystyle \mathit{\Phi }{}_{\mathit{i}}}}=[\begin{array}{cccc}1& 0& 0& \cdots \end{array}]$,再根据式(4)可得$\mathit{\Psi }=[\begin{array}{cccccc}1& 0& 0& |0& \cdots & 0\end{array}]$。同理对于i=2,3点,存在$\mathit{\Psi }=[\begin{array}{ccccccc}0& 1& 0& |0& \cdots & 0& \end{array}]$,$\mathit{\Psi }=[\begin{array}{cccccc}0& 0& 1& |0& \cdots & 0\end{array}]$。故该有限元无网格耦合三角形单元的形函数具有Kronecker delta性质,能够像普通的有限元一样直接施加位移边界条件。

该有限元无网格耦合三角形单元的刚度矩阵和荷载向量与普通的有限单元类似,只是位移应变矩阵B它的维数是3×2M,M为单元支持域Ω内的节点数。

2 数值检验

根据上述内容,用MATLAB编写了有限元无网格耦合三角形单元的程序,检验该单元的线性相关性和计算精度。单元刚度矩阵积分使用二维三点Hammer积分。

2.1 线性相关性检验

正如上文所述,单位分解有限元的一个主要缺点是线性相关问题。检验本文所提出的有限元无网格耦合三角形单元是否具有线性相关性,采用Tian R等[5]使用的方法。首先,计算没有施加位移边界条件的整体刚度矩阵的特征值,记录下零特征值数。其次,对单元施加最少的约束以限制刚体运动,再检查整体刚度矩阵是否存在零特征值,如果没有零特征值,则该单元不存在线性相关问题。

算例的网格和边界条件如图2所示,考虑平面应力问题。弹性模量E=1,泊松比v=0.25,局部节点位移函数采用二次多项式基。结果列于表1。

△限制x,y方向位移;○限制y方向位移

从表1可以看出,在施加位移边界条件前,有三个零特征值,反映了系统的三个刚体位移模式;在施加位移边界条件后,没有零特征值。这表明本文所提出的有限元无网格耦合三角形单元没有线性相关问题。

2.2 受抛物线型剪力作用的悬臂梁

如图3(a)所示悬臂梁,端部剪力为P=1 000, 弹性模量E=3×107,泊松比v=0.3,考虑平面应力问题。该问题的解析解由Timoshenko和Goodier[6]给出。为便于和四边形等参元比较,采用如图3(b)形式的网格划分(2×8×2=32个三角形网格)。有限元无网格耦合三角形单元考虑了使用线性基和二次基两种情况。该模型使用五种网格 2×2×2、2×8×2、4×16×2、6×24×2、8×32×2。

(a)几何尺寸;(b) 2×8×2网格示例

为了研究该单元的收敛性,定义如下的位移误差范数:

$\parallel u\parallel =\left({\displaystyle {\int }_{\Omega }}u{}^{\text{Τ}}\cdot u\text{d}\Omega \right){}^{\frac{1}{2}}(13)$

相对位移误差为:

$r{}_u=\frac{\parallel u{}^{\text{数}\text{值}}-u{}^{\text{解}\text{析}}\parallel }{\parallel u{}^{\text{解}\text{析}}\parallel }(14)$

图4绘出了随着网格加密,四种单元收敛的情况。从图4上可以看出,使用线性基的有限元无网格耦合三角形单元精度比线性三角形单元高,略低于四边形等参元;而使用二次基的有限元无网格耦合三角形单元精度远高于线性三角形单元和四边形等参元。

2.3 cook变截面梁

如图5(a)所示,Cook提出右端边界受均匀分布剪力的变截面悬臂梁问题。与上例类似,采用2×2×2, 4×4×2, 8×8×2的网格划分模型。图5(b)为采用4×4×2网格的示例。弹性模量E=1,泊松比v为1/3。C点的竖向位移结果列于表2。

(a) 几何尺寸;(b) 4×4×2网格示例

从表2中可以看出,由于此问题中使用了畸变的四边形网格,使得四边形等参元的精度降低了,而使用线性基和二次基的有限元无网格耦合三角形单元都显示了较好的收敛性,它们的结果均优于线性三角形单元和四边形等参元,其中二次基的有限元无网格耦合三角形单元精度最高。

3 结论

本文基于单位分解法,提出了一种新的有限元无网格耦合三角形单元。该单元使用多项式基函数用来作局部近似,三角形形函数作单位分解函数,其形函数具有Kronecker delta性质,能够直接施加位移边界条件。通过特征值问题的分析,可以看出该三角形单元能够消除普通单位分解有限元中存在的线性相关问题。悬臂梁的算例表明,该三角形单元具有较高的计算精度,其中使用二次基的该三角形单元均优于普通的线性三角形单元和四边形等参元。本文使用有限元无网格耦合三角形单元分析了线弹性问题,由于三角形网格生成简单,各种算法成熟,并且其能适应任意复杂的形状,故还可以将本文提出的有限元无网格耦合三角形单元应用到大变形问题、弹塑性问题和裂纹扩展问题中。

参考文献

[1] Babuska I, Melenk J M. The partition of unity method. International Journal for Numerical Methods in Engineering, 1997;40(4): 727—758

[2] Oden J T,Duarte C A,Zienkiewicz O C.A new cloud-based hp-fi-nite element method.Computer Methods in Applied Mechanics andEngineering,1998;153(1-2):117—126

[3] Strouboulis T,Babuska I,Copps K.The design and analysis of thegeneralized finite element method.Computer Methods in Applied Me-chanics and Engineering,2000;181(1-3):43—69

[4] Rajendran S,Zhang B R A.“E-meshfree”QUAD4 element based onpartition of unity.Computer Methods in Applied Mechanics and Engi-neering,2007;197(1-4):128—147

[5] Tian R,Yagawa G,Terasaka H.Linear dependence problems of par-tition of unity-based generalized FEMs.Computer Methods in AppliedMechanics and Engineering,2006;195(37-40):4768—4782

[6] Timoskenko S P, Goodier J N. Theory of Elasticity. third ed. New York:McGraw-Hill, 1970