基于面上DNA计算求解最小集合覆盖问题*

利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。     

Sextic spline collocation methods for nonlinear fifth-order boundary value problems

In this paper, two sextic-spline collocation methods are developed and analysed for approximating solutions of nonlinear fifth-order boundary-value problems. The first method uses a spline interpolant and the second one is based on a spline quasi-interpolant, which are constructed from sextic splines. They are both proved to be second-order convergent. Numerical results confirm the order of convergence predicted by the analysis. It has been observed that the methods developed in this paper are better than the others given in the literature.     

Intelligent computing approach to solve the nonlinear Van der Pol system for heartbeat model

In this work, an intelligent computing algorithm is developed for finding the approximate solution of heart model based on nonlinear Van der Pol (VdP)-type second-order ordinary differential equations (ODEs) using feed-forward artificial neural networks (FF-ANNs) optimized with genetic algorithms (GAs) hybrid through interior-point algorithm (IPA). The mathematical modeling of the system is constructed using FF-ANN models by defining an unsupervised error and unknown weights; the networks are tuned globally with GAs, and local refinement of the results is made with IPA. Design scheme is applied to study the VdP heart dynamics model by varying the pulse shape modification factor, damping coefficients and external forcing factor while keeping the fixed value of the ventricular contraction period. The results of the proposed algorithm are compared with reference numerical solutions of Adams method to establish its correctness. Multiple independent runs are performed for the scheme, and results of statistical analyses in terms of mean absolute deviation, root-mean-square error and Nash–Sutcliffe efficiency illustrate its applicability, effectiveness and reliability.

     

A user's guide to the numerical solution of two-point boundary value problems arising in continuous time dynamic economic models

This paper reviews commonly used numerical methods of solving two-point boundary value problems which frequently arise in economics. Since these problems are often too complex to solve analytically, and since phase diagrams yield limited insights, these numerical methods are a useful addition to the economist's tool kit. Attention is focused on easily obtained algorithms.     

Smoothing for multipoint boundary value models

We show how to solve the linear least-squares smoothing problem for multipoint boundary value models. The complementary model is derived and is used to determine the Hamiltonian equations for the smoothed state estimate and its error covariance. Stable algorithms are obtained using an invariant imbedding/multiple shooting procedure.     

Approximate solutions to a parameterized sixth order boundary value problem

In this paper, the homotopy analysis method (HAM) is applied to solve a parameterized sixth order boundary value problem which, for large parameter values, cannot be solved by other analytical methods for finding approximate series solutions. Convergent series solutions are obtained, no matter how large the value of the parameter is.     

Multi-point boundary value problem for optimal bridge design

Based upon He's homotopy perturbation and variational iteration methods, we present a method for approximate solutions of nonlinear second-order multi-point boundary value problems (BVPs) in bridge design. Two numerical experiments are carried out to demonstrate the efficiency of the present method. The results reveal that the proposed method is very effective for second-order multi-point BVPs in bridge design.     

一种求解哈密尔顿通路问题的新方法*

哈密尔顿通路问题属于典型的NP完全问题。针对NP完全问题的特点提出了一种基于量子计算和混沌动力学的新方法。该方法首先把哈密尔顿问题变换成布尔表达式形式;然后构建了一个新型的量子混沌计算机模型,该模型使用混沌放大器解决了量子状态区分问题;最后得出结论,基于非线性迭代关系的新型量子混沌计算机可以在多项式时间内解决哈密尔顿通路问题。     

How to solve the Santa Claus problem

John Trono (1994) published a new exercise in concurrent programming – the Santa Claus problem – and provided a solution based on semaphores. His solution is incorrect because it assumes that a process released from waiting on a semaphore will necessarily be scheduled for execution. We give a simple solution in Ada 95 using higher-order synchronization primitives: protected objects and rendezvous. We then give a solution in Java, although this solution is not as elegant as the Ada 95 solution because the Java synchronization primitives are rather limited. The problem demonstrates that semaphores, designed for low-level mutual exclusion, are not appropriate for solving difficult concurrent programming problems. © 1998 John Wiley & Sons, Ltd.     

Algorithm to solve the generalized Markowitz problem

A relation between the VaR and CVaR criteria was established in terms of income and loss. Consideration was given to the generalized Markowitz problem, and an algorithm to solve it approximately for the piecewise-linear and bilinear income functions was presented. An analytical solution was given for the case of the scalar bilinear income function under a uniform distribution of income. A numerical algorithm was presented to solve the problem in the case of multivariable bilinear income function under normal distribution of incomes.     

Error analysis of a Galerkin method to solve the forward problem in MEG using the boundary element method

Sources of brain activity, e.g. epileptic foci, can be localized with Magnetoencephalography (MEG) measurements by recording the magnetic field outside the head. For a successful surgery a very high localization accuracy is needed. The most often used conductor model in the source localization is an analytic sphere, which is not always adequate, and thus a realistically shaped conductor model is needed. In this paper we examine a Galerkin method with linear basis functions to solve the forward problem in MEG using the boundary element method. Its accuracy is compared to the collocation method with constant and linear basis functions. The accuracies are determined for a unit sphere for which analytic solutions are available. The Galerkin method gives a clear improvement in the accuracy of the forward problem especially for the tangential component of the magnetic field. At realistic MEG measurement distances from the brain the Galerkin method reaches a given accuracy with lower computational costs than the collocation methods starting from a few hundreds of unknowns. With larger meshes the difference for the Galerkin method increases significantly.     

背包问题的量子计算算法

背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O（n²）。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O（√N/M）步完成对规模为n的背包问题求解（M是解的数目）,而基于原始Grover算法的背包问题量子计算算法计算复杂度为O（√N/M）,成功率是50%～100%。     

求解指派问题的一次性分配算法

匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足。提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足。针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法。     

An algorithm for computing unstable solutions of semilinear boundary value problems

We present a partially interactive algorithm for accurate computation of unstable solutions of semilinear Dirichlet boundary value problems.     

Positive solutions to singular boundary value problem for nonlinear fractional differential equation

In this paper, we consider the existence of positive solutions to the singular boundary value problem for fractional differential equation. Our analysis relies on a fixed point theorem for the mixed monotone operator.     

Using N-D method to solve multi-response problem in Taguchi

Using Taguchi method to achieve a robust experimental design in the study of product quality is an important issue. The Taguchi method is to seek the best factors/levels combination with lowest societal cost solution to achieve customers requirements. However, the Taguchi method can only be used to optimize the single-response problem; it cannot be used to optimize the multi-response problem. This paper submits an optimal procedure, N-D method (Artificial Neural Network and Data Envelopment Analysis), by using artificial neural networks (ANNs) and data envelopment analysis (DEA) to achieve the optimization of multi-response problem. Two case studies in Su and Tong (1997) and Tong and Su (1997) are resolved by the proposed N-D method. The result deriving from the proposed N-D method indicates that it offers an efficient and feasible solution in the multi-response problems.This revised version was published in June 2005 with corrected page numbers.     

Eigenvalue of fourth-order -point boundary value problem with derivatives

This paper deals with the existence of positive solutions for the fourth-order nonlinear ordinary differential equation

subject to the boundary conditions:

where ,β,γ,δ≥0 are constants such that ρ=δ+γ+βδ>0, and . By means of a fixed-point theorem due to Krasnaselskii, some new existence results of positive solutions for the above multi-point boundary value problem are obtained, which improve the main results of Graef et al. [J.R. Graef, C. Qian, B. Yang, A three-point boundary value problem for nonlinear fourth-order differential equations, J. Math. Anal. Appl. 287 (2003) 217–233]. An example is given to demonstrate the main results of this paper.     

一种新的离散粒子群算法在指派问题中的应用

指派问题在组合优化中属NP-Complete问题。提出了一种基于离散粒子群算法的求解方法。算法中每个粒子的位置代表了一种可行的指派方案,在迭代中通过交叉策略和局部搜索策略来更新粒子的位置,这既保证了粒子位置的可行性,又增加了粒子的多样性,避免陷入早熟收敛。通过实例仿真可以看出DPSO算法简洁,较以往算法具有更好的收敛性,能得到更优的解,能够求解匈牙利法不能求解的指派问题。对不同的问题,通过影响参数的调整,可以取得好的收敛效果。     

Genetic algorithms to solve the cover printing problem

Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms.