算法与复杂性理论

《算法与复杂性理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、平行搜索算法求解约束问题摘　要：求解非线性方程组。运用数值方法求解，最普遍的是采用牛顿迭代法，当初值发生微小变动时，用这种方法求解可能会发散或者收敛到一个用户不想要的解。由于设计者在初始设计阶段的随意性，往往使得系统的初始条件不好，使牛顿法难以收敛。通过分析传统的数值方法在非线性方程组解中的应用，发现存在两大缺陷：(1)对初始点敏感；(2)求解稳定性差。文中提出利用混沌算法的遍历性来解决此类问题。关键词：约束求解；单纯形搜索；混沌算法1　引言几何约束问题是基于参数化和特征造型CAD系统的核心问题，但由于几何约束求解过程中的多解性，如何准确捕获设计者的意图，找到满足用户希望的解成为目前

2、研究的热点。问题的主要难点在于解空间的巨大，一般说来，解的数量和约束的数量成指数级关系。实际上，即使对于完备的约束系统，找到一个唯一的可行解，被证明为是NP难的问题。非线性方程组求解是几何约束问题中最本质的问题，求解几何约束问题的最终都是一个非线性方程组求解问题。求解非线性方程中常用的方法是数值法，数值法的优点是速度快，收敛速度是超线性的。但它对于初始点的依赖极强，如果初始点的选取不接近于真实解，算法有可能找到错误的解[1]。文中针对非线性方程组求解对初始点敏感、收敛性差、求解不稳定等问题，结合单纯形法和混沌算法的优点，提出一种用于求解非线性方程组的平行搜索算法(ParallelSe

3、archAlgorithm，PS)。新算法分三个阶段：(1)粗搜索阶段：利用Logistic映射生成混沌轨道序列点集，然后转化成优化变量候选解群体，在候选解群体寻求解存在的领域和方向。(2)下降搜索阶段：将由粗搜索得到的解小范围内按单纯形算法下降机制进一步搜索，按目标函数的下降趋势方向进行快速收敛。(3)细搜索阶段：利用混沌映射在当前优化解邻域进行细致搜索，较准确收敛到全局意义下的较为满意的解。实验证明新算法中采用的基于混沌的初始化技术比常规的随机法更具优越性。2　几何约束求解系统解决约束的部分叫约束求解器。国内外很多学者运用数值计算理论、人工智能理论、图论、自由度分析理论等对约束求

4、解进行了研究，主要有：整体求解法，稀疏矩阵法，连接分析法，规约构造法，约束传播法，符号代数法和辅助线法等。约束问题可以形式化为(E，C)，E=(e1，e2，…，en)，ei表示几何元素，6如点、线、圆等。C=(c1，c2，…，cm)，ci表示加在这些几何元素之间的约束。一般一个约束对应一个方程，可以表示为：f1(x0，x1，x2，…，xn)=0　…（1）fm(x0，x1，x2，…，xn)=0X=(x0，x1，…，xn)Newton-Raphson是求解非线性方程的有力工具，其迭代公式为：Xk+1=xk-[f′(xk)]-1f(xk)，k=0，1，2（2）数值法中将Newton-Rap

5、hson扩展为如下的优化问题来进行求解[2-3]。Minf(x)=f(x1，x2，…，xn)Sub.x=(x1，x2，…，xn)∈SX（3）在工程实践中，很多现实设计都涉及到带有多个约束条件的多个目标解集的同时优化。满足所有约束条件的解空间S为可行域，可行域中的解为可行解，在可行域中使目标函数最小的解称为最优解。当最优解不止一个时定义[4]：所有目标解的最优解集定义为：满足约束条件的决策变量使目标向量函数最优，即寻找变量X=(x1，x2，…，xn)T，使向量函数f(x)最优。其数学描述如下：minf(x)=min[f1(x)，f2(x)，…，fn(x)]Ts.t.g(x)=0（4）式

6、中f(x)为目标函数，g(x)为约束条件。对于变量X*，当且仅当不存在其他的变量X，在不违背约束的条件下满足："i∈{1，2，…，n}∶fi(X*)≤fi(X)∧$j∈{1，2，…，n}∶fj(X*)

7、首先在n维欧氏空间En中构造—个包含n+1个顶点的凸多面体，求出各顶点的函数值，并确定其中的最大值、次大值和最小值，然后通过反射、扩张、内缩、缩边等策略求出一个较好解，用之取代最大(差)点，从而构成新的多面体，如此多次迭代则逼近一个性能较好的极小点。单纯形法的基本思想是Spendley、Hext及Himsworth等人首先提出的，1965年由Nelder及Mead两人加以改进。单纯形法的优点是不必计算目标函数的梯度，它只是在一定的图形的顶点上，按照一定的规