分块分层优化的旅游路线规划问题研究

针对旅游路线规划决定着自驾旅游者的旅游成败问题,利用分块分层优化的思想解决了旅游路线规划这一网络优化问题。用赋权图和近邻聚类的思想构建分块网络加权图,建立考虑旅游时间、行车时间和游览时间的改进旅行商优化模型,规划区块内景点的自驾旅游路线;然后将各区块视为节点、区块间旅游时间作为时间权值之一,建立改进的多旅行商优化模型,并用模拟退火算法规划出区块间的自驾旅游路线;其次,用类比一维装箱问题的思想,建立了求最少旅游年数的一维装箱模型,并用交叉装填算法求得其最小值;最后,应用提出的方法为西安市的自驾旅游爱好者规划出了满足多种约束的游遍全国201个5A级景区的最佳旅游路线。     

A short range many-body potential for modelling bcc metals

The problem considered is the fitting of a many-body interaction potential to bulk crystal data. A parameterisation of the potential is assumed which is based on physical considerations. The free parameters are determined by using global optimization to perform a least squares fit, to a large number of crystal properties. This has been achieved for body centered cubic (bcc) materials. The approach adopted here fits the bcc crystal structure, as the preferred minimum energy configuration for tungsten, and also fits the dimer energetics and the elastic properties of crystalline tungsten.     

QMQSAR: utilization of a semiempirical probe potential in a field-based QSAR method

A semiempirical quantum mechanical approach is described for the creation of molecular field-based QSAR models from a set of aligned ligand structures. Each ligand is characterized by a set of probe interaction energy (PIE) values computed at various grid points located near the surface of the ligand. Single-point PM3 calculations afford these PIE values, which represents a pool of independent variables from which multilinear regression models of activity are built. The best n-variable fit is determined by constructing an initial regression using standard forward stepwise selection, followed by refinement using a simulated annealing technique. The resulting fit provides an easily interpreted 3D physical model of ligand binding affinity. Validation against three literature datasets demonstrates the ability of the semiempirical potential to model critical binding interactions in diverse systems.     

Finite-Time Performance Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Current theoretical results are based on the assumption that the goal when addressing such problems is to find a globally optimal solution. However, from a practical point of view, solutions that are close enough to a globally optimal solution (where close enough is measured in terms of the objective function value) for a discrete optimization problem may be acceptable. This paper introduces -acceptable solutions, where is a value greater than or equal to the globally optimal objective function value. Moreover, measures for assessing the finite-time performance of GHC algorithms, in terms of identifying -acceptable solutions, are defined. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using these measures. S²A uses a fixed cooling schedule during the algorithm's execution. Though S²A is provably nonconvergent, its finite-time performance can be assessed using the finite-time performance measures defined in terms of identifying -acceptable solutions. Computational results with a randomly generated instance of the traveling salesman problem are reported to illustrate the results presented. These results show that upper and lower estimates for the number of iterations to reach a -acceptable solution within a specified number of iterations can be obtained, and that these estimates are most accurate for moderate and high fixed temperature values for the S²A algorithm.     

用迈克尔逊干涉仪测气体浓度的方法

本介绍用迈克尔逊干涉仪测量气体浓度的一种方法。     

On the Convergence of Inhomogeneous Markov Chains Approximating Equilibrium Placements of Flexible Objects

This paper deals with the minimization of local forces in two-dimensional placements of flexible objects within rigid boundaries. The objects are disks of the same size but, in general, of different materials. Potential applications include the design of new amorphous polymeric and related granular materials as well as the design of package cushioning systems. The problem is considered on a grid structure with a fixed step size w and for a fixed diameter of the discs, i.e., the number of placed disks may increase as the size of the placement region increases. The near-equilibrium configurations have to be calculated from uniformly distributed random initial placements. The final arrangements of disks must ensure that any particular object is deformed only within the limits of elasticity of the material. The main result concerns -approximations of the probability distribution on the set of equilibrium placements. Under a natural assumption about the configuration space, we prove that a run-time of n+log^O(1)(1/} is sufficient to approach with probability 1 – the minimum value of the objective function, where depends on the maximum of the escape depth of local minima within the underlying energy landscape. The result is derived from a careful analysis of the interaction among probabilities assigned to configurations from adjacent distance levels to minimum placements. The overall approach for estimating the convergence rate is relatively independent of the particular placement problem and can be applied to various optimization problems with similar properties of the associated landscape of the objective function.     

Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included.     

Molecular conformation on the CM-5 by parallel two-level simulated annealing

In this paper, we propose a new kind of simulated annealing algorithm calledtwo-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100,000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.Also a researcher at the Army High Performance Computing Research Center, University of Minnesota, Minneapolis, MN 55415     

Robust priors for smoothing and image restoration

The Bayesian method for restoring an image corrupted by added Gaussian noise uses a Gibbs prior for the unknown clean image. The potential of this Gibbs prior penalizes differences between adjacent grey levels. In this paper we discuss the choice of the form and the parameters of the penalizing potential in a particular example used previously by Ogata (1990,Ann. Inst. Statist. Math.,42, 403–433). In this example the clean image is piecewise constant, but the constant patches and the step sizes at edges are small compared with the noise variance. We find that contrary to results reported in Ogata (1990,Ann. Inst. Statist. Math.,42, 403–433) the Bayesian method performs well provided the potential increases more slowly than a quadratic one and the scale parameter of the potential is sufficiently small. Convex potentials with bounded derivatives perform not much worse than bounded potentials, but are computationally much simpler. For bounded potentials we use a variant of simulated annealing. For quadratic potentials data-driven choices of the smoothing parameter are reviewed and compared. For other potentials the smoothing parameter is determined by considering which deviations from a flat image we would like to smooth out and retain respectively.     

A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem

A quantitative study is presented of the typical behavior of the simulated annealing algorithm based on a cooling schedule presented previously by the authors. The study is based on the analysis of numerical results obtained by systematically applying the algorithm to a 100-city traveling salesman problem. The expectation and the variance of the cost are analyzed as a function of the control parameter of the cooling schedule. A semiempirical average-case performance analysis is presented from which estimates are obtained on the expectation of the average final result obtained by the simulated annealing algorithm as a function of the distance parameter, which determines the decrement of the control parameter.