融合改进Tent混沌和模拟退火的灰狼算法

针对标准灰狼算法种群多样性差、后期收敛速度慢、易陷入局部最优的缺陷,提出一种改进灰狼算法.利用改进Tent混沌映射初始化种群,增加种群多样性;引入螺旋函数,提高算法收敛速度;融合模拟退火思想,避免陷入局部最优;设置搜索阈值,平衡全局搜索与局部搜索;利用改进Tent混沌映射产生新个体,替换性能较差个体并进行高斯扰动,增加寻优精度;将当前解和新解进行算术杂交,以保留当前解优点并减小扰动差异.使用基准测试函数和共享单车停车点选址及期初配置模型测试算法性能.结果表明,改进灰狼算法较标准灰狼算法、遗传算法和粒子群算法,收敛速度更快,寻优精度更高,性能更优越,并将该算法应用到共享单车停车选址上,验证了算法的有效性.     

A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such “combinatorial augmentation algorithm” for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The “pivots” in the algorithm are determined by choosing an >0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by . In this sense, it generalizes the cycle cancelling algorithms for (single source) mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.     

An alternate implementation of Goldfarb's minimization algorithm

Goldfarb's algorithm, which is one of the most successful methods for minimizing a function of several variables subject to linear constraints, uses a single matrix to keep second derivative information and to ensure that search directions satisfy any active constraints. In the original version of the algorithm this matrix is full, but by making a change of variables so that the active constraints become bounds on vector components, this matrix is transformed so that the dimension of its non-zero part is only the number of variablesless the number of active constraints. It is shown how this transformation may be used to give a version of the algorithm that usually provides a good saving in the amount of computation over the original version. Also it allows the use of sparse matrix techniques to take advantage of zeros in the matrix of linear constraints. Thus the method described can be regarded as an extension of linear programming to allow a non-linear objective function.     

Mathematical modeling of a steam generator for sensor fault detection

A dynamic model for a nuclear power plant steam generator (vertical, preheated, U-tube recirculation-type) is formulated as a sixth-order nonlinear system. The model integrates nodal mass and energy balances for the primary water, the U-tube metal and the secondary water and steam. The downcomer flow is determined by a static balance of momentum. The mathematical system is solved using transient input data from the Philippsburg 2 (FRG) nuclear power plant. The results of the calculation are compared with actual measured values. The proposed model provides a low-cost tool for the automatic control and simulation of the steam generating process. The “parity-space” algorithm is used to demonstrate the applicability of the mathematical model for sensor fault detection and identification purposes. This technique provides a powerful means of generating temporal analytic redundancy between sensor signals. It demonstrates good detection rates of sensor errors using relatively few steps of scanning time and allows the reconfiguration of faulty signals.     

A novel algorithm for area traffic capacity control with elastic travel demands

A non-linear area traffic control system with limited capacity is considered in this paper. Optimal signal settings and link capacity expansions can be determined while trip distribution and network flow are in equilibrium. This problem can be formulated as a non-linear mathematical program with equilibrium constraints. For the objective function a non-linear constrained optimization program for signal settings and link capacity expansion is determined. For the constraint set the elastic user equilibrium traffic assignment obeying Wardrop’s first principle can be formulated as a variational inequality. Since the constrained optimization problem is non-convex, only local optima can be obtained. In this paper, a novel algorithm using a non-smooth trust region approach is proposed. Numerical tests are performed using a real data city network and various example test networks in which the effectiveness and robustness of the proposed method are confirmed as compared to other well-known solution methods.     

The {\cal {D Q R}} algorithm, basic theory, convergence, and conditional stability

Summary. We describe a fast matrix eigenvalue algorithm that uses a matrix factorization and reverse order multiply technique involving three factors and that is based on the symmetric matrix factorization as well as on –orthogonal reduction techniques where is computed from the given matrix . It operates on a similarity reduction of a real matrix to general tridiagonal form and computes all of 's eigenvalues in operations, where the part of the operations is possibly performed over , instead of the 7–8 real flops required by the eigenvalue algorithm. Potential breakdo wn of the algorithm can occur in the reduction to tridiagonal form and in the –orthogonal reductions. Both, however, can be monitored during the computations. The former occurs rather rarely for dimensions and can essentially be bypassed, while the latter is extremely rare and can be bypassed as well in our conditionally stable implementation of the steps. We prove an implicit theorem which allows implicit shifts, give a convergence proof for the algorithm and show that is conditionally stable for general balanced tridiagonal matrices . Received April 25, 1995 / Revised version received February 9, 1996     

Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Meshless local Petrov-Galerkin (MLPG) approximation to the two dimensional sine-Gordon equation

During the past few years, the idea of using meshless methods for numerical solution of partial differential equations (PDEs) has received much attention throughout the scientific community, and remarkable progress has been achieved on meshless methods. The meshless local Petrov-Galerkin (MLPG) method is one of the “truly meshless” methods since it does not require any background integration cells. The integrations are carried out locally over small sub-domains of regular shapes, such as circles or squares in two dimensions and spheres or cubes in three dimensions. In this paper the MLPG method for numerically solving the non-linear two-dimensional sine-Gordon (SG) equation is developed. A time-stepping method is employed to deal with the time derivative and a simple predictor-corrector scheme is performed to eliminate the non-linearity. A brief discussion is outlined for numerical integrations in the proposed algorithm. Some examples involving line and ring solitons are demonstrated and the conservation of energy in undamped SG equation is investigated. The final numerical results confirm the ability of proposed method to deal with the unsteady non-linear problems in large domains.     

A new formalism for the dynamic modelling of cables

This article proposes a new formalism for the dynamic modelling of cables that can even be applied when they are submitted to cross flow of water or air. An important application is the case of umbilical cables used in remotely operated vehicles. The primary basis for the formulation is to assume that the continuous flexibility is represented by a discrete approach, consisting of rigid links connected by elastic joints, allowing movement in three dimensions. Each elastic joint allows three independent movements, called elevation, azimuth and torsion (twist). A significant contribution of the proposed formalism is the development of a compact equation that allows obtaining the Lagrangian of the system directly and automatically, regardless of the number of links chosen to form a chain of rigid bodies connected by flexible joints to represent the continuous flexibility of the cable. This formulation allows the construction of an algorithm for obtaining the equations of the dynamic model of flexible cables.     

Interval Branch and Bound with Local Sampling for Constrained Global Optimization

In this article, we introduce a global optimization algorithm that integrates the basic idea of interval branch and bound, and new local sampling strategies along with an efficient data structure. Also included in the algorithm are procedures that handle constraints. The algorithm is shown to be able to find all the global optimal solutions under mild conditions. It can be used to solve various optimization problems. The local sampling (even if done stochastically) is used only to speed up the convergence and does not affect the fact that a complete search is done. Results on several examples of various dimensions ranging from 1 to 100 are also presented to illustrate numerical performance of the algorithm along with comparison with another interval method without the new local sampling and several noninterval methods. The new algorithm is seen as the best performer among those tested for solving multi-dimensional problems.     

The structure of roll waves in two-layer flows

The structure of non-linear waves in a two-layer flow of an incompressible fluid in extended channels is investigated. Periodic discontinuous solutions, describing roll waves of finite amplitude, are constructred for the equations of two-layer shallow water. “Anomalous” waves of limited amplitude are found which correspond to the transition from stratified to slug flow conditions.     

Smooth boundary integration method in a linear two-dimensional problem of incompressible fluid and solid

This paper presents a new application of a theoretical and computational method of smooth boundary integration which belongs to the methods of boundary integral equations. Smooth integration is not a method of approximation. In its final analytical form, a smooth-kernel integral equation is computerized easily and accurately.

Smooth integration is associated with a “pressure-vorticity” formulation which covers linear problems in elasticity and fluid mechanics. The solution presented herein is essentially the same as that reported in an earlier paper for regular elasticity. The constraint of incompressibility does not cause difficulties in the pressure-vorticity formulation.

The linear fluid mechanics problem formulated and solved in this paper covers Stokes' problem of a slow viscous flow, and has a wider interpretation. The translational inertia forces are incorporated in the linear problem, as in Euler's dynamic theory of inviscid flow. The centrifugal inertia forces are left for the non-linear problem. The linear problem is perceived as a step in solution of the non-linear problems.     

A Hybrid grey wolf optimizer and genetic algorithm for minimizing potential energy function

In this paper, we propose a new hybrid algorithm between the grey wolf optimizer algorithm and the genetic algorithm in order to minimize a simplified model of the energy function of the molecule. We call the proposed algorithm by Hybrid Grey Wolf Optimizer and Genetic Algorithm (HGWOGA). We employ three procedures in the HGWOGA. In the first procedure, we apply the grey wolf optimizer algorithm to balance between the exploration and the exploitation process in the proposed algorithm. In the second procedure, we utilize the dimensionality reduction and the population partitioning processes by dividing the population into sub-populations and using the arithmetical crossover operator in each sub-population in order to increase the diversity of the search in the algorithm. In the last procedure, we apply the genetic mutation operator in the whole population in order to refrain from the premature convergence and trapping in local minima. We implement the proposed algorithm with various molecule size with up to 200 dimensions and compare the proposed algorithm with 8 benchmark algorithms in order to validate its efficiency for solving molecular potential energy function. The numerical experiment results show that the proposed algorithm is a promising, competent, and capable of finding the global minimum or near global minimum of the molecular energy function faster than the other comparative algorithms.     

A flexible CMRH algorithm for nonsymmetric linear systems

A flexible version of the CMRH algorithm is presented that allows varying preconditioning at every step of the algorithm. A consequence of the flexibility of this new variant is that any iterative methods can be incorporated as a preconditioner in the inner steps. Theoretical results that relate the residual norm of the new algorithm and the flexible GMRES, the new algorithm with CMRH itself, are given. Numerical experiments are carried out to illustrate the effectiveness of the proposed algorithm in comparison with the standard CMRH algorithm, ILU-preconditioned CMRH variants and the flexible GMRES algorithm.     

A dynamic genetic algorithm based on continuous neural networks for a kind of non-convex optimization problems

This paper presents a kind of dynamic genetic algorithm based on a continuous neural network, which is intrinsically the steepest decent method for constrained optimization problems. The proposed algorithm combines the local searching ability of the steepest decent methods with the global searching ability of genetic algorithms. Genetic algorithms are used to decide each initial point of the steepest decent methods so that all the initial points can be searched intelligently. The steepest decent methods are employed to decide the fitness of genetic algorithms so that some good initial points can be selected. The proposed algorithm is motivated theoretically and biologically. It can be used to solve a non-convex optimization problem which is quadratic and even more non-linear. Compared with standard genetic algorithms, it can improve the precision of the solution while decreasing the searching scale. In contrast to the ordinary steepest decent method, it can obtain global sub-optimal solution while lessening the complexity of calculation.     

An input relaxation measure of efficiency in stochastic data envelopment analysis

We introduce stochastic version of an input relaxation model in data envelopment analysis (DEA). The input relaxation model, recently developed in DEA, is useful to resource management [e.g. G.R. Jahanshahloo, M. Khodabakhshi, Suitable combination of inputs for improving outputs in DEA with determining input congestion, Appl. Math. Comput. 151(1) (2004) 263–273]. This model allows more changes in the input combinations of decision making units than those in the observed inputs of evaluating decision making units. Using this extra flexibility in input combinations we can find better outputs. We obtain a non-linear deterministic equivalent to this stochastic model. It is shown that under fairly general conditions this non-linear model can be replaced by an ordinary deterministic DEA model. The model is illustrated using a real data set.     

Scaling laws and fractality in the framework of a phenomenological approach

Phenomenological Universality (PUN) represents a new tool for the classification and interpretation of different non-linear phenomenologies in the context of cross-disciplinary research. Also, they can act as a “magnifying glass” to finetune the analysis and quantify the difference among similarly looking datasets. In particular, the class U2 is of special relevance since it includes, as subcases, most of the commonly used growth models proposed to date. In this contribution we consider two applications of special interest in two subfields of Elasto-dynamics, i.e. Fast- and Slow-Dynamics, respectively. The results suggest that new equations should be adopted for the fitting of the experimental results and that fractal-dimensioned variables should be used to recover the scaling invariance, which is invariably lost due to non-linearity.     

Implicit QR algorithms for palindromic and even eigenvalue problems

In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques. D. S. Watkins partly supported by Deutsche Forschungsgemeinschaft through Matheon, the DFG Research Center Mathematics for key technologies in Berlin.