一类混合0-1非凸二次约束二次规划问题的近似算法

研究一类混合0-1非凸二次约束二次规划问题的近似算法.该问题是在M个非凸二次约束与一个基数约束下,求解一个n维向量的极小范数,变量包含M个0-1变量与一个n维连续向量.该问题是NP-难的.在求解其半正定规划(SDP)松弛问题的基础上,提出了一种随机舍入算法,能够得到原始的问题的一个可行解.数值仿真实验结果表明该方法是十分有效的.     

交通信号控制的二层规划模型与算法研究

本文研究了交叉口信号控制的二层规划模型的求解算法．上层模型采用了一种直接处理约束的改进的粒子群算法，下层则采用仿射尺度内点算法，得到了一种信号控制二层规划模型．并对模拟路网进行了数值实验，表明算法是有效的和可行的．     

带学习效应的两台平行机时间表长问题

研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.     

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.     

带最小交易单位的Markowitz模型及算法

在证券交易市场中,交易规则要求购买的股票数量为整数.基于这种情况,将Markowitz模型中资产的投资比例改进为资产的投资数量,构造了一个二次整数规划模型.设计了求解该模型的算法,经过实证分析,算法是有效的.     

求解中大规模复杂凸二次整数规划问题的新型分枝定界算法

针对现有分枝定界算法在求解高维复杂二次整数规划问题时所存在的诸多不足，本文通过充分挖掘二次整数规划问题的结构特性来设计选择分枝变量与分枝方向的新方法，并将HNF算法与原问题松弛问题的求解相结合来寻求较好的初始整数可行解，由此导出可用于有效求解中大规模复杂二次整数规划问题的改进型分枝定界算法．数值试验结果表明所给算法大大改进了已有相关的分枝定界算法，并具有较好的稳定性与广泛的适用性．     

基于自组织映射和模糊隶属度的财务危机预警研究

良好的财务危机预警模型能够有效监控企业运营情况,避免企业倒闭或被重组的悲剧发生。本文结合自组织映射模型和模糊C均值的模糊隶属度,构造模糊自组织映射模型,并应用到财务危机预警中。该模型将模糊隶属度带入到学习率函数中,在计算过程中自动更新获胜节点邻域范围,并在迭代过程中采用批学习算法,提高预测精度、稳定输出结果。对沪深两市上市公司的财务指标进行实证研究,通过与传统预警模型对比,得出模糊自组织映射模型在财务危机预警方面具有更优越的预测性能。     

二维逆散射问题探测方法的数值实现

探测方法是最近发展起来的逆散射问题的一种重要的求解方法,其主要思想是由散射波测量数据构造一个带有散射体外面参数点的指示函数,当参数点靠近散射体的边界时,指示函数爆破,由此重建散射体的边界．本文对具有Sound-soft边界的二维散射体给出了探测方法的数值实现．在给出标志函数的构造的基础上,进一步提出了利用模拟数据实现探测法的一个改进的逼近方法．为了更清楚地检验所提出的方法的数值结果,我们直接从Ω边界上的 D-to-N映射来研究探测方法的数值解．     

二维非线性对流扩散方程的非振荡特征差分方法

１．引言 近十几年来,双曲守恒律问题的高分辨率格式已取得很大发展,具有局部自适应选取节点的非振荡插值算法（如 ＵＮＯ［１］, ＥＮＯ［２］等）在这些格式的构造中起着重要的作用．特征差分法是求解对流扩散问题的一种较为有效方法,但在求解具有陡峭前线问题时,也会产生非物理振荡阻（见４）．本文将把特征差分法与非振荡插值算法相结合构造对流扩散问题的高分辨率差分格式． ［１］中的 ＵＮＯ及［２］中的 ＥＮＯ插值都是一维的,有关讨论二维 ＵＮＯ及ＥＮＯ插值的文章还不多见,本文将构造二维基于六节点的二次非振荡插值以及…     

投影三角分解法定价带随机波动率的美式期权

考虑数值求解Heston随机波动率美式期权定价问题,通过在空间方向采用中心差分格式离散二维偏微分算子,在时间方向利用隐式交替方向格式,将美式期权定价问题转化成求解每个时间层上的若干个线性互补问题.针对一般美式期权定价模型离散得到的线性互补问题,构造出投影三角分解法进行求解,并在理论上给出算法的收敛条件.数值实验表明,所构造的数值方法对于求解美式期权定价问题是有效的,并且优于经典的投影超松弛迭代法和算子分裂方法.     

Protein folding in the HP model on grid lattices with diagonals

The protein folding problem, i.e., the computational prediction of the three-dimensional structure of a protein from its amino acid sequence, is one of the most important and challenging problems in computational biology. Since a complete simulation of the folding process of a protein is far too complex to handle, one tries to find an approximate solution by using a simplified, abstract model. One of the most popular models is the so-called HP model, where the hydrophobic interactions between the amino acids are considered to be the main force in the folding process, and furthermore the folding space is modeled by a two- or three-dimensional grid lattice.In this paper, we will present some approximation algorithms for the protein folding problem in the HP model on an extended grid lattice with plane diagonals. The choice of this kind of lattice removes one of the major drawbacks of the original HP model, namely the bipartiteness of the grid which severely restricts the set of possible foldings. Our algorithms achieve an approximation ratio of for the two-dimensional and of for the three-dimensional lattice. This improves significantly over the best previously known approximation ratios for the protein folding problem in the HP model on any lattice.     

A filter-and-fan approach to the 2D HP model of?the?protein folding problem

We examine a prominent and widely-studied model of the protein folding problem, the two-dimensional (2D) HP model, by means of a filter-and-fan (F&F) solution approach. Our method is designed to generate compound moves that explore the solution space in a dynamic and adaptive fashion. Computational results for standard sets of benchmark problems show that the F&F algorithm is highly competitive with the current leading algorithms, requiring only a single solution trial to obtain best known solutions to all problems tested, in contrast to a hundred or more trials required in the typical case to evaluate the performance of the best of the alternative methods.     

Global energy minimisation and cotranslational protein folding of HP models

The globally minimum energy configurations of simple HP lattice models (which use only two amino acid types, positioned on the vertices of a square lattice) of proteins have been established for short sequences. Here we investigate the folding of such proteins to this globally minimum energy configuration, both cotranslationally (as they are manufactured, sequentially, in the ribosome) and starting from a fully extended state. In order to do this we model the folding process and develop a heuristic method for finding local energy minima. Two main results emerge. First, some sequences do fold better cotranslationally than from a fully extended state and second, this can be due to cotranslational folding leading to an initial local energy minimum from which movement to the global minimum is efficient. Sequences for which this is true tend to have a higher density of hydrophobic residues at the start than at the finish. Structural properties of sequences that fold better cotranslationally than from a fully extended state are also identified.     

A polynomial time upper bound for the number of contacts in the HP-model on the face-centered-cubic lattice (FCC)

Lattice protein models are a major tool for investigating principles of protein folding. For this purpose, one needs an algorithm that is guaranteed to find the minimal energy conformation in some lattice model (at least for some sequences). So far, there are only algorithm that can find optimal conformations in the cubic lattice. In the more interesting case of the face-centered-cubic lattice (FCC), which is more protein-like, there are no results. One of the reasons is that for finding optimal conformations, one usually applies a branch-and-bound technique, and there are no reasonable bounds known for the FCC. We will give such a bound for Dill's HP-model on the FCC, which can be calculated by a dynamic programming approach.     

Isotropic effective energy simulated annealing searches for low energy molecular cluster states

The search for low energy states of molecular clusters is associated with the study of molecular conformation and especially protein folding. This paper describes a new global minimization algorithm which is effective and efficient for finding low energy states and hence stable structures of molecular clusters. The algorithm combines simulated annealing with a class of effective energy functions which are transformed from the original energy function based on the theory of renormalization groups. The algorithm converges to low energy states asymptotically, and is more efficient than a general simulated annealing method.     

Evaluating Kohonen’s learning rule: An approach through genetic algorithms

This paper examines the technical foundations of the self-organising map (SOM). It compares Kohonen’s heuristic-based training algorithm with direct optimisation of a locally-weighted distortion index, also used by Kohonen. Direct optimisation is achieved through a genetic algorithm (GA). Although GAs have been used before with the SOM, this has not been done in conjunction with the distortion index. Comparing heuristic-based training and direct optimisation for the SOM is analogous to comparing the Backpropagation algorithm for feedforward networks with direct optimisation of RMS error. Our experiments reveal lower values of the distortion index with direct optimisation. As to whether the heuristic-based algorithm is able to provide an approximation to gradient descent, our results suggest the answer should be in the negative. Theorems for one-dimensional and for square maps indicate that different point densities will emerge for the two training approaches. Our findings are in accordance with these results.     

一般分布区间型符号数据的SOM聚类方法

区间型符号数据是一种重要的符号数据类型,现有文献往往假设区间内的点数据服从均匀分布,导致其应用的局限性。本文基于一般分布的假设,给出了一般分布区间型符号数据的扩展的Hausdorff距离度量,基于此提出了一般分布的区间型符号数据的SOM聚类算法。随机模拟试验的结果表明,基于本文提出的基于扩展的Hausdorff距离度量的SOM聚类算法的有效性优于基于传统Hausdorff距离度量的SOM聚类算法和基于μσ距离度量的SOM聚类算法。最后将文中方法应用于气象数据的聚类分析,示例文中方法的应用步骤与可操作性,并进一步评价文中方法在解决实际问题中的有效性。     

A new method based on SOM network to generate coarse meshes for overlapping unstructured multigrid algorithm

A new method to generate coarse meshes for overlapping unstructured multigrid algorithm based on self-organizing map (SOM) neural network is presented in this paper. The application of SOM neural network can overcome some limitations of conventional methods and which is designed to pursuit the best structure relation between fine and coarse unstructured meshes with the object to ensure robust convergence for overlapping unstructured multigrid algorithm. Besides, this method can automate the generation of unstructured meshes and is suitable for both two and three dimensions conditions.     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

低秩张量填充的加速随机临近梯度算法

本文提出了一种求解低秩张量填充问题的加速随机临近梯度算法.张量填充模型可以松弛为平均组合形式的无约束优化问题,在迭代过程中,随机选取该组合中的某一函数进行变量更新,有效减少了张量展开、矩阵折叠及奇异值分解带来的较大的计算花费.本文证明了算法的收敛率为$O (1/k^{2})$.最后,随机生成的和真实的张量填充实验结果表明新算法在CPU时间上优于现有的三种算法.