基于分治策略和蚁群算法的最大团问题的研究

最大团问题是经典的NP-hard问题,对该问题求解方法的研究在理论上、实践上都具有一定的意义.蚁群算法已成功地求解出许多组合优化难题.通过使用分治法,将图分解成子图,对各子图应用蚁群算法求解,提出一种求解最大团问题的蚁群算法.它减小了问题的求解规模,使求解变得容易,且实验取得了较好的结果.     

解大规模矩阵内部特征问题的简单调和Arnoldi方法

给出了调和Arnoldi算法的一种等价变形.利用求解Krylov子空间和其位移子空间的基之间的巧妙关系式,作者以较少的运算量将原大规模矩阵特征问题转化为一个标准特征问题求解,比原来调和Arnoldi算法求解广义特征问题要简单.简要分析了新方法收敛的充要条件.数值试验表明了新方法比调和Arnoldi算法有效,尤其是当求解子空间维数较小时,新方法的优越性更明显.     

移频算法在加速子空间迭代法中的应用

基于子空间迭代法,采用移频加速算法,开发了一个高效、稳定、内存消耗低的移频子空间迭代特征值求解器SSubspace. 给出了详细的移频子空间迭代法求解广义特征值问题的步骤及关键参数的选取. 对刚度矩阵奇异时特征值的求解进行了探讨,实现了对刚体模态的求解. 与Intel MKL特征值求解器(FEAST v2.1)相比,SSubspace的求解效率高于FEAST,且内存消耗低于FEAST. SSubspace理论上可以求解出所有阶的特征值,且计算时间随特征值数的增加近似成线性增长关系,可用于求解大阶数特征值问题、大型矩阵的全特征值问题.     

求解信赖域子问题的一个光滑牛顿法

信赖域子问题的有效求解是实现信赖域算法的关键.利用光滑Fischer-Bermeister NCP函数提出了一个求解信赖域子问题的光滑牛顿法.数值实验表明所提出的算法是有效的.     

基于遗传算法的产品分配方案研究

建立了产品分配的时变模型 ,并将其分为两层子问题 .下层子问题为基本的运输问题 ,按一般的线性方程求解 ;上层子问题则求系统的最小成本 ,采用遗传算法进行求解 .同时 ,还进行了大量的计算机实验 ,并在实验过程中将遗传算法与实现产品分配时常用的算法进行了比较 .结果表明 :采用本研究所建模型 ,并利用遗传算法进行求解 ,可以取得相当好的效果 ,具有实现简单、收敛时间短等优点 .     

求解非线性方程组的非单调滤子算法

提出了一个新的求解非线性方程组的滤子算法,首先把非线性方程组的求解转化成一个非线性优化问题,然后借助非单调技术和滤子技术求解该问题,从而得到了原方程组的解.在适当的条件下,证明了该算法的全局收敛性,初步的数值试验表明了该算法的有效性.     

解变分不等式问题的一类滤子SQP算法

针对一般形式的变分不等式问题,考虑将其转化为约束优化问题求解.对于这种特定的约束优化问题,提出了一类新的滤子序列二次规划(SQP)求解方法.基于变分不等式与约束优化问题的不同,在滤子条件中采用了一个二次价值函数作为目标函数,使得一般的变分不等式问题均可用滤子算法求解.采用SQP方法结合滤子方法获取试探步,只需要计算两个简单不等式判断试探步,算法易实现,计算量小.在较弱的条件下证明了算法的全局收敛性.最后,给出了算法的数值算例,与同类算法比较,结果良好.     

一类多出发点多旅行商问题规划算法

提出了一种基于K-means聚类算法的多出发点多旅行商问题求解的新方法.算法定义了节点的吸引度,通过节点吸引度矩阵进行子环游节点集的归类,并对各子环游应用单旅行商启发式算法进行求解.实例表明,此规划算法能很好地求解多出发点多旅行商问题.     

列车运行调整问题的分解协调计算模型

针对列车运行调整问题集中式求解方法的不足,构建多目标优化列车运行调整的数学模型,并设计分解协调计算模型来求解.分解协调计算模型将求解过程分为4个层次,分别是将待调整列车分解为子调整列车集的协调分组层,确定子列车集优化目标的目标设定层,完成子调整问题求解的优化计算层和将各子问题解还原为原问题解的结果还原层.该计算模型能适应多种线路条件,也能适应不同列车调度员指挥的习惯偏好,并能快速求出优化解.     

变截面压杆稳定问题半解析解

介绍变截面压杆稳定问题的半解析求解方法 ,在这一方法中应用了模态摄动法 .首先以均匀梁的低阶纵向振动模态函数构成求解子空间 ,然后在此子空间中把变截面压杆稳定由变系数偏微分方程描述的求解问题转化为非线性代数方程组的求解 ,从而简化了计算过程 .通过算例比较 ,说明本方法简便实用 ,且有良好的近似性 .     

具有一般角形结构大系统目标规划问题最优解的存在

将具有一般角形结构的大系统目标规划问题分解为若干个子问题, 研究各个子问题最优解之间以及原问题与子问题最优解之间的关系, 并讨论了原问题最优解的存在性.     

梯形结构大系统多目标规划子问题解的关系

将具有梯形结构的大系统多目标规划问题分解为若干个子问题,研究了子问题之间以及子问题与大系统问题之间有效解的关系.在一定条件下,证明了(I-1)个子问题MPT(Bi,Ai+1)的有效解构成大系统问题(MPT)的有效解.     

具有特殊原方块角形结构的大系统多目标规划有效解的存在性

将具有特殊原方块角形结构的大系统多目标规划问题分解为若干个子问题,研究了子问题与大系统问题有效解之间的关系,并讨论了大系统问题有效解的存在性.     

具有梯形结构大系统目标规划模型的双向分解及解的关系

采用“双向分解”方式将梯形结构大系统目标规划模型分解为若干个子问题,研究子问题之间以及子问题与大系统问题之间最优解的关系,在一定条件下,证明了横向和纵向分解子问题的最优解可构成大系统问题的最优解.     

有功和无功交替优化的电力系统最佳潮流计算

本文把电力系统最佳潮流的计算分离为有功(P)和无功(Q)两个子优化系统。把等式和不等式约束也分成两部分在相应的子优化中考虑。通过有功和无功的交替优化,结合潮流计算统一起来,达到两者同时优化的目的。在每一个子优化中,控制变量和状态变量相对的要减少一些。特别是在无功优化时,控制变量可以任选Q或V,使收敛性得到了较大改善。在计算方法上,采用共轭梯度法。     

半导体制造系统优化调度模型的分解和简化方法

在半导体制造系统流体网络模型的基础上,建立了以减小平均在制品水平为目标的可分解的优化调度模型,利用其可分解的特性,把整个调度周期划分为若干等长的子区间,把原调度问题分解为这些子区间上的子问题。在半导体制造环境下,这些子问题可以进一步简化,因此通过求解这些子问题得到了原调度问题的解。这种算法的计算量与调度周期成正比,而且应用实例表明,其性能有很大提高。     

求解一类二次规划反问题的同伦交替方向法

对一类带不等式约束的二次规划反问题的求解方法进行研究。首先表示出此类二次规划对应的反问题形式，将该反问题转化为目标函数变量可分离优化问题，将其中约束写成KKT条件的形式之后，该反问题等同于一个等式约束优化问题。综合以上，考虑使用交替方向乘子法进行迭代，在此基础之上，将同伦思想应用于算法每步迭代的子问题中，以此避免近端算子选取的敏感性，又可保证算法的收敛速度。针对子问题，使用逐次超松弛法进行求解，并获取算法的收敛性。最后，将该算法与SDPT3和Sedumi两种方法进行比较，数值结果表明，该算法无论在速度上还是效率上都优于以上两种方法。     

双对称矩阵的一类约束逆特征值问题及其逼近问题

根据双对称矩阵的性质,将双对称矩阵的一类约束逆特征值问题及其逼近问题分解成具有较小阶数的实对称矩阵的同类子问题,然后利用实对称矩阵的结果导出双对称矩阵的这两个问题的解.     

求解可分离凸优化问题的非精确混合分裂算法

针对一类有四个块变量的可分离凸优化问题,提出一种非精确混合分裂算法.在每一轮迭代中,该算法需要求解四个子问题,根据子问题计算工作量的大小,将四个子问题分为两组,每组包含工作量相当的两个子问题.算法在组内执行平行分裂方法,两组间执行交替方向方法,并允许迭代子问题的非精确求解.在适当的条件下,证明了所提出的混合分裂算法具有全局收敛性.     

面向多目标优化问题的基于Species的遗传算法

为了能够快速准确地获得多目标优化问题的一组非支配解,提出了一种基于Species的多目标遗传算法.该算法采用Tchebycheff方法构建一定数量的子问题,进而基于Species机制构造多种群实现了对多个子问题的并行求解.这种采用多个体对一个最优解的搜索方式提高了算法的探索能力和开发能力.最后,对一组标准测试函数进行仿真实验,结果表明所提出的算法能够快速准确地获得一定数量的非支配解.