算法与复杂性理论

平行搜索算法求解约束问题摘 要：求解非线性方程组。运用数值方法求解，最普遍的是采用牛顿迭代法，当初值发生 微小变动时，用这种方法求解可能会发散或者收敛到一个用户不想要的解。由于设计者在初 始设计阶段的随意性，往往使得系统的初始条件不好，使牛顿法难以收敛。通过分析传统的 数值方法在非线性方程组解中的应用，发现存在两大缺陷：(1)对初始点敏感；(2)求解稳定 性差。文中提出利用混沌算法的遍历性来解决此类问题。关键词：约束求解；单纯形搜索；混沌算法1 引言几何约束问题是基于参数化和特征造型 CAD 系统的核心问题，但由于几何约束求解过程 中的多解性，如何准确捕获设计者的意图，找到满足用户希望的解成为目前研究的热点。问 题的主要难点在于解空间的巨大，一般说来，解的数量和约束的数量成指数级关系。实际上， 即使对于完备的约束系统，找到一个唯一的可行解，被证明为是 NP 难的问题。非线性方程组求解是几何约束问题中最本质的问题，求解几何约束问题的最终都是一个 非线性方程组求解问题。求解非线性方程中常用的方法是数值法，数值法的优点是速度快， 收敛速度是超线性的。但它对于初始点的依赖极强，如果初始点的选取不接近于真实解，算 法有可能找到错误的解1。文中针对非线性方程组求解对初始点敏感、收敛性差、求解不稳定等问题，结合单纯形 法和混沌算法的优点，提出一种用于求解非线性方程组的平行搜索算法 (Parallel Search Algorithm，PS)。新算法分三个阶段：(1) 粗搜索阶段：利用 Logistic 映射生成混沌轨道序列点集，然后转化成优化变量候选 解群体，在候选解群体寻求解存在的领域和方向。(2) 下降搜索阶段：将由粗搜索得到的解小范围内按单纯形算法下降机制进一步搜索， 按目标函数的下降趋势方向进行快速收敛。(3) 细搜索阶段：利用混沌映射在当前优化解邻域进行细致搜索，较准确收敛到全局意 义下的较为满意的解。实验证明新算法中采用的基于混沌的初始化技术比常规的随机法更具 优越性。2 几何约束求解系统解决约束的部分叫约束求解器。国内外很多学者运用数值计算理论、人工智能理论、 图论、自由度分析理论等对约束求解进行了研究，主要有：整体求解法，稀疏矩阵法，连接 分析法，规约构造法，约束传播法，符号代数法和辅助线法等。约束问题可以形式化为(E, C), E = (e , e，e), e表示几何元素，如点、线、1 2 n i圆等。C = (c , c，c), c表示加在这些几何元素之间的约束。一般一个约束对应一1 2 m i个方程，可以表示为：f(xo，X, x2,，xn) =0(1)fm(X0，X1，X2，Xn)=0X = (x0, xl,，xn)Newton-Raphson 是求解非线性方程的有力工具，其迭代公式为：X = x-f (x )-1f(x ), k =0, 1, 2(2)k+l kkk数值法中将 Newton-Raphson 扩展为如下的优化问题来进行求解2-3 。Minf(x) = f(x ， x ， x)12nSub.x = (x , x，x)uS X(3)12n在工程实践中，很多现实设计都涉及到带有多个约束条件的多个目标解集的同时优化。 满足所有约束条件的解空间 S 为可行域，可行域中的解为可行解，在可行域中使目标函 数最小的解称为最优解。当最优解不止一个时定义4：所有目标解的最优解集定义为：满足 约束条件的决策变量使目标向量函数最优，即寻找变量X=(x , x , , x)T，使向量函数12nf(x)最优。其数学描述如下：minf(x) =minf(x) ， f(x) ， fn(x)T12s.t.g(x) =0( 4)式中 f(x) 为目标函数， g(x) 为约束条件。对于变量X*,当且仅当不存在其他的变量X,在不违背约束的条件下满足：Vie 1, 2,n : fi(X*)fi(X) A3je 1, 2,，n : fj(X*) fj(X)则称 fi (X*)优于 fi (X)，记作 fi (X*)三fi X)；也称 fi (X)劣于 fi (X*)，记作 fi (X) Wfi (X*)。变量X*是最优解，最优解往往形成一个解集，称为最优解集。3 单纯形方法工程中许多最优化求解问题存在大规模、高维、非线性、非凸等复杂特性，单纯形搜索 法(SimplexMethod, SM),也称可变多面体搜索法，是一种传统的处理无约束最优化问题的 直接算法，算法首先在 n 维欧氏空间 En 中构造个包含 n+1 个顶点的凸多面体，求出各顶 点的函数值，并确定其中的最大值、次大值和最小值，然后通过反射、扩张、内缩、缩边等 策略求出一个较好解，用之取代最大(差)点，从而构成新的多面体，如此多次迭代则逼近一 个性能较好的极小点。单纯形法的基本思想是Spendley、Hext及Himsworth等人首先提出的，1965年由Nelder 及 Mead 两人加以改进。单纯形法的优点是不必计算目标函数的梯度，它只是在一定的图形 的顶点上，按照一定的规则来进行搜索，算法首先在n维欧氏空间中构造一个包含n+1个顶 点的凸多面体，求出各顶点的函数值，并确定其中的最大值、次最大、最小值，然后通过反 射、收缩、延伸等策略求出一个较好解，取代最大点，从而构成新的多面体，这样重复迭代 可以逼近一个性能较好的极小点。4 混沌的运动特性及产生模型混沌是存在于非线性系统中一种较为普遍的现象，混沌并不是一片混乱，而是有着精致 内在机制结构的一类现象。混沌运动具有遍历性、随机性、规律性等特点，混沌运动能在一 定范围内按照其自身的“规律”不重复地遍历所有状态，因此利用混沌变量进行优化搜索， 会比随机搜索更具优越性，更能实现全局优化解的搜索。利用类似载波的思想，可以将混沌 变量“缩放”为优化变量的约束范围之内，然后利用混沌变量的遍历性、随机性、规律性等 特点，为优化的搜索提供更有利的方法。混沌为非线性系统的一种演变现象，是由确定性规则导致的对初始条件非常敏感的无固 定周期的长期行为5，混沌动力学以简单项奖的规则产生复杂的行为，在一定范围内不重复 地遍历空间所有的点，具有规律性、伪随机性和遍历性。其中混沌的遍历性是指混沌运动在 其混沌吸引域内是各态历经的，即在有限时间内混沌轨道经过混沌区内每一个状态点。混沌优化用类似载波的方法将混沌状态映射到优化变量中，并把混沌运动的遍历范围同 优化变量的取值范围联系起来，然后利用混沌变量进行搜索6。产生混沌的规则很多，文中采用经典 Logistic 映射模型来构造混沌序列，迭代公式如 下：CX (k+i)=p ex (k) (1.0- ex (k) )i =0，1，n(5)i i i其中ex (k)为exi在第k步混沌演变后的值，cxiUO, 1.0, p u 0, 4,当p =4,即i得如下：ex(k+i)=4 ex (1.0- ex (k)i =0, 1, n(6)iii当 ex u (0, 1.0)且 ex 0.25, 0.5, 0.75时，将产生混沌现象，ex 在(0, 1.0)内iii遍历。一般都利用该式来产生混沌，对取值不属于此范围的变量ex u(a , b ),通常可由式ii i(7)、式(8)与混沌变量ex u(0, 1.0)进行往返映射。iex= (x- a)/(b- a)( 7 )ii ii ix= a+ ex(b- a)(8)i ii i i5 平行搜索算法51 算法基本思想平行优化算法(PS)的基本思想主要体现在两个方面：(1) 采用混沌序列初始化个体，利用混沌提高个体的多样性和搜索的遍历性，解决算法 对初值敏感的问题。(2) 以当前整个单纯形搜索到的最优位置为基础产生混沌序列，把产生的混沌序列中的 最优位置替代当前单纯形中的个体的位置。引入混沌序列的搜索算法可在迭代中产生局部最 优解的许多邻域点，以此帮助惰性个体逃离局部极小点，并快速搜寻到最优解。假设待优化的问题有M个参数，个体规模为N,则算法要求为NM+1。在全局寻优过 程中，程序从规模为N的种群中随机抽取M+1个个体作为单纯形的开始，单纯形在计算过程 有可能找到全局最优解，完成计算。如果单纯形法没有找到全局最优解，它经过一定次数(事先给定)的计算后，一般来说也会找到更优秀的模型。如果N大出M很多，在每次早熟时， 则可以多次调用单纯形法，加强对模型空间搜索，然后，把由单纯形产生的新模型回代到混 沌的种群中，并替换掉被单纯形法随机抽取的模型，形成新一代个体，如此交替使用混沌和 SM,直到找到全局最优解。平行算法流程如图1所示。图 1 平行算法流程步骤如下：St epl :参数设置：k =0, r =0.xik= xi(O), x i * = xi(O), air二 ai, bir= bi, 其 中i=0, 1, 2,，n。这里k为混沌变量迭代标志，r为细搜索标志，xj(0)为(0, 1)区间 n个相异的初值，xi*为当前得到的最优混沌变量，当前最优解f*初始化为一个较大的数；St ep2:混沌初始化：Step2.1：随机产生一个n维每个分量数值在01之间的向量，x1=(x11, x12,，x1n), n为目标函数中变量的个数，根据式(5),得到N个向量x1, x2,，xn；Step2.2：将xi的各个分量载波到对应变量的取值区间；Step2.3：计算变量的适应值，并从N个初始群体中选择性能较好的M+1个作为初始解;Step3：通过单纯形搜索，缩小解空间Step4：对最优值fi= (f1, f2,fd)进行混沌优化，将F映射到Logistic方程(6) 的定义域0, 1, xi= (fi- ai)/(bi- ai)(i =1, 2,),然后用Logistic方程进行迭代 产生混沌变量序列xmi(m =1 , 2，)，再把产生的混沌变量序列通 过逆映射f(m)i=ai+(bi-ai)xmi 返回到原解空间，得：f(m)i= (f(m)l,f(m)2,f(m)d),(m=l, 2,);在原解空间对混沌变量经历的每一个可行解 f(m)i，(m =1，2， )计算其适应值，得到性 能最好的可行解f*i ；St ep 5:用f*i取代当前群体中任意一个个体；St ep 6：若满足停止条件，则搜索停止，输出全局最优位置，否则用x*i(i =1，2， m)取代当前群体中m +1个体返回Step3。平行优化过程是一个反复迭代梯度下降搜索收敛的过程，在每次循环中每个自变量同时 在更新，便于平行搜索，在每一次搜索过程中，自变量x的变化主要是由Logistic映射和 单纯形来完成。Logistic映射负责混沌轨道遍历点的生成，实现满映射，单纯形执行在当 前搜索点附近正向和反向寻优，该机制的引入及其本身的遍历性使混沌优化算法具有一定的 跳出局部最优的能力，避免了其它传统经典优化算法对初始值分布过于敏感，而可能收敛到 局部最小点而不是全局最小点。52 算法实现及结果在求解器中画出草图如图2所示。在曲线与截线内，有五个圆和一个椭圆，其中三个圆 和椭圆的半径固定，要求只变动其它两圆大小和截线位置的情况下，使得相邻的图形两两相 切。求解结果如图3所示。用平行搜索策略与牛顿迭代7进行了比较，结果如表1所示。表1 PS和牛顿迭代运算结果比较参数牛顿迭代PS群体规模6061()2()寻找到晟优解的次数/次12313841前25代寻找到最优解的次“进行了 50次实验。从表1中可以看到，在PS用 6个个体实现，牛顿迭代用50个个体 的效果的情况下,PS运行时间仅为牛顿迭代的1/15 ;当PS仅用10个个体即可实现牛顿迭 代50个个体的效果，运行时间仅为后者的1/10 ；在20个个体的情况下，PS的性能全面超 过牛顿迭代，运行时间仅为后者的1/5。图 2 草图图 3 求解器求解之后结果牛顿迭代对这个多元函数计算，发现尽管计算的稳定性对初始值不敏感，但是牛顿迭代 的最终解却极大的依赖于初始值。如果初始值的取值范围偏离最优点较远，则最终解会陷入 局部极小值点。用PS算法进行重新计算，算法能够跳出局部最优解，使得最终解对初始值 不敏感。以上结果说明，引入了混沌机制的单纯形算法，在求解非线性方程组特别是对未知数的 取值敏感的方程组，较牛顿算法的成功率高，这主要是混沌的遍历性为算法的迭代过程提供 了更多的关于优化函数的信息量，增强了每个个体的搜索能力。6 结束语文中使用了具有混沌机制的平行搜索算法来求解非线性方程组。新算法借助于混沌运 动，产生一组与优化变量相同数目的混沌变量，用类似载波的方式将混沌引入优化变量使其 呈现混沌状态，可以将混沌变量“放大”为优化变量的约束范围之内，在一定范围内按照其 自身的“规律”不重复地遍历所有状态，解决了求解中对初值敏感的问题；同时结合单纯形 方法快速收敛的特性，加速在局部空间的收搜索。混合算法搜索变量空间大、计算速度快、 易于实现，对优化问题无需连续性、可微性的要求。既保留了混沌优化的优点，又提高了搜 索速度与精度。当图形变化幅度较大时还可以收敛，是一种很有效的求解几何约束问题的方 法。参考文献：1： Maranas C ， Floudas C。 Finding all solutions of nonlinearlyconstrained systems of equationsJ。 Journal of Global Op-timization， 2005， 72 ：143-182。 2 Robillson S 。 Extension of newtons method to nonlinearfunctionswith values in a coneJ。 Numerical Mathemat-ics， 2009(19)：341-347。3 ：Hentenryck P ， Miehel L， Deville Y。 Nomerica： a modelinglanguage for globaloptimization M。 Cambridge： TheMIT Press， 2007：1-16。4 ：邹秀芬，刘敏忠，吴志健，等。解约束多目标优化问题的一种鲁棒的进化算法J。计算机研究与发展， 2006， 41(6)： 985-990。5 ：褚美茹，崔明勇。混沌遗传算法在配电网无功优化中的应用J。信息技术，2004,28(10)： 48-50。6 ： Ge J X， Chou S C， Gao X S。 Geometrie constraint solvingwith optimizationmethodsJ 。 CAD，2002， 31(14)： 867-879。