一种AGENT任务求解联盟形成策略

Agent联盟是一组平等的、协作的、共同承担任务的Agent的集合．联盟的形成往往需要较大的通信开销和计算工作量．本文提出一种Agent形成联盟的策略，该策略在系统运行的初始阶段，保证任务分配的优化解．而在随后的运行中基于成功合作者集形成Agent联盟．该策略保证在接近任务分配优化解的情况下，有效减少系统中的可能联盟数以及联盟形成过程中的通信开销和计算量，避免联盟形成过程中的盲目性，节省协商时间提高协商效率．     

Solving an Inverse Diffusion Problem for Magnetic Resonance Dosimetry by a Fast Regularization Method

An inverse diffusion problem that appears in Magnetic Resonance dosimetry is studied. The problem is shown to be equivalent to a deconvolution problem with a known kernel. To cope with the singularity of the kernel, nonlinear regularization functionals are considered which can provide regular solutions, reproduce steep gradients and impose positivity constraints. A fast deterministic algorithm for solving the involved non-convex minimization problem is used. Accurate restorations on real 256×256 images are obtained by the algorithm in a few minutes on a 266-MHz PC that allow to precisely quantitate the relative absorbed dose.     

GA和HS算法解决电子化配车方法比较

本文针对海尔集团配车系统的业务需求,简要介绍了运用遗传算法(GA)和启发式算法(HS)求解集装箱装载问题的模型,讨论两个模型的建立和求解算法的异同.文中根据实验数据,对两种算法的性能进行了比较和分析,最后提出了有机地结合两种模型的设想.     

GA和HS算法解决电子化配车方法比较

本文针对海尔集团配车系统的业务需求,简要介绍了运用遗传算法(GA)和启发式算法(HS)求解集装箱装载问题的模型,讨论两个模型的建立和求解算法的异同。文中根据实验数据,对两种算法的性能进行了比较和分析,最后提出了有机地结合两种模型的设想。     

A Dual Approach for Solving the Combined Distribution and Assignment Problem with Link Capacity Constraints

In this paper, we consider the combined distribution and assignment (CDA) problem with link capacity constraints modeled as a hierarchical logit choice problem based on random utility theory. The destination and route choices are calculated based on the multi-nominal logit probability function, which forms the basis for constructing the side constrained CDA (SC-CDA) problem as an equivalent mathematical programming (MP) formulation. A dual MP formulation of the SC-CDA problem is developed as a solution algorithm, which consists of an iterative balancing scheme and a column generation scheme, for solving the SC-CDA problem. Due to the entropy-type objective function, the dual formulation has a simple nonlinear constrained optimization structure, where the feasible set only consists of nonnegative orthants. The iterative balancing scheme explicitly makes use of the optimality conditions of the dual formulation to analytically adjust the dual variables and update the primal variables, while a column generation scheme is used to iteratively generate routes to the working route set as needed to satisfy the side constraints. Two numerical experiments are conducted to demonstrate the features of the SC-CDA model and the computational performance of the solution algorithm. The results reveal that imposing link capacity constraints can have a significant impact on the network equilibrium flow allocations, and the dual approach is a practical solution algorithm for solving the complex SC-CDA problem.     

分布式问题求解方案的模糊综合评价模型及其算法实现

为解决现阶段大型复杂工程方案评价缺少实用理论分析工具的问题,文章应用“主因素突出型”和“因素加权型”两种多阶段模糊评判模型,实现了一种适合大型工程分布式协同设计的方案模糊综合评价算法。文中首先分析了大型工程分布式问题求解过程,提出了一种面向工程的分布式问题求解逻辑结构;其次详细分析了多阶段方案模糊评价模型以及模糊综合评价算法的流程框图及其实现过程。     

基于混合蚁群遗传算法的Agent联盟求解

针对混合蚁群遗传算法容易融合时机过早或过晚、种群进化经历的代数过多、效率低等问题,首先改进了蚁群算法,并将改进的蚁群算法和遗传算法结合,应用于Agent联盟求解.提出了基于混合蚁群遗传算法的Agent联盟求解算法(Hybrid Ant Colony and Genetic Algorithm,HAGA),算法的核心是动态寻找两个算法的衔接点,在该点左侧使用遗传算法,右侧使用蚁群算法.与其他传统算法的实验比较,证明了该算法在求解联盟的最优解的时问和精度上都有较高的效果.把HAGA应用于RoboCup 2D龙队客户端程序中,使用比赛分析工具软件SoccerDoctor对比赛结果进行了统计分析,结果显示龙队在诸多技术参数方面均占有明显优势.     

Discretization of the Wave Equation Using Continuous Elements in Time and a Hybridizable Discontinuous Galerkin Method in Space

We provide an error analysis of two methods for time stepping the wave equation. These are based on the Hybridizable Discontinuous Galerkin (HDG) method to discretize in space, and the continuous Galerkin method to discretize in time. Two variants of HDG are proposed: a dissipative method based on the standard numerical flux used for elliptic problems, and a non-dissipative method based on a new choice of the flux involving time derivatives. The analysis of the fully discrete problem is based on simplified arguments using projections rather than explicit interpolants used in previous work. Some numerical results are shown that illuminate the theory.     

A Robust Numerical Method for the Random Interface Grating Problem via Shape Calculus,Weak Galerkin Method,and Low-Rank Approximation

We present an efficient numerical algorithm to solve random interface grating problems based on a combination of shape derivatives, the weak Galerkin method, and a low-rank approximation technique. By using the asymptotic perturbation approach via shape derivative, we estimate the expectation and the variance of the random solution in terms of the magnitude of the perturbation. To effectively capture the severe oscillations of the random solution with high resolution near the interface, we use weak Galerkin method to solve the Helmholtz equation related to the grating interface problem at each realization. To effectively compute the variance operator, we use an efficient low-rank approximation method based on a pivoted Cholesky decomposition to compute the two-point correlation function. Two numerical experiments are conducted to demonstrate the efficiency of our algorithm.     

弹性层中的SH板波传播特性及电磁超声激励方法的研究

研究水平剪切波(Shear Horizontal,简称SH波)的传播特性及激励接收方法对该波在无损检测和声弹性技术范围内的工程应用有着重要的价值.首先,SH波在弹性层中传播的多模态、频散特性在文中作了详细的分析,同时重点研究了电磁超声技术在非铁磁性材料波导中产生SH波的探头结构和基础理论,并以试验的方法验证了其部分电声特性,结果表明,SH板波具有其他类型波所没有的独特特性,而电磁超声技术在SH波的激励接收方面有着很大的优势.     

On Optimization and Parallelization of the Little Algorithm for Solving the Travelling Salesman Problem

The paper describes some ways to speed up solution of the NP-complete Traveling Salesman Problem. The classic Little algorithm, belonging to the class of branch-and-bound methods, can solve it both for directed and undirected graphs. For undirected graphs, however, its speed can be increased by eliminating the branches examined earlier from further consideration. We propose changes to be made in the key operations of the algorithm to speed up execution. In addition, we describe the results of an experiment with a significant increase in the speed of solving of the problem by the advanced algorithm. Another way to speed up the solution procedure is to parallelize the algorithm. For problems of this kind, it is difficult to decompose the task into a sufficient number of subtasks that have comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case, the RPM_ParLib library developed by the author is a good approach, enabling the development of high-performance applications for parallel computing on a local network using any.NET-compatible programming language. We selected C# as the programming language. Parallel applications were developed to implement the basic and modified algorithms, as well as to compare them in terms of speed. Experiments were performed for the graphs with up to 45 vertexes and up to 16 network computers. We also investigated the speed increase that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper.     

On an Evaluation Method for Zeta Constants Based on a Number Theoretic Approach

New formulas for zeta constants are obtained based on a number theoretic approach that is used in proving irrationality of some classical constants. Using these formulas, one can approximate zeta constants and their combinations by rational fractions and construct a new efficient evaluation method for them.

     

基于单纯形法和局部枚举解混合整数线性规划问题

提出了一种基于单纯形法和局部枚举求解整数线性规划问题的新方法。它通过单纯形法得到松弛问题的最优解并确定变量以及目标函数取值范围,然后基于目标函数,进行局部枚举,从而得到其整数线性规划问题的最优解,与现有方法比较,新解法简单,计算量少,尤其是对于大规模整数线性规划问题,计算量少体现地更明显。     

全相位与Geiger算法的岩石声发射源定位方法

Geiger定位算法在岩石定位分析中得到广泛应用,但是对初始值要求非常严格,若初始值选择不当,则很难进入收敛范围。为了提高定位精度,减少迭代次数,针对这些问题,提出全相位与Geiger算法的岩石声发射源定位方法。首先进行花岗岩（50 mm×100 mm×50 mm）断铅实验,接着充分利用全相位FFT相位不变性的优势分析断铅信号,通过相位差法求出时延同时反演声发射源求出Geiger迭代初始值,最后综合最小二乘法与Geiger算法,迭代求出最优解。实验仿真结果显示此算法的平均误差相比美国PCI-2型声发射仪器定位结果降低了约5 mm,有效解决了Geiger初始值选取的问题,能够迅速进入收敛范围,提高了收敛速度和定位精度。     

Searching NK Fitness Landscapes: On the Trade Off Between Speed and Quality in Complex Problem Solving

Problems are often too complex to solve them in an optimal way. The complexity arises from connections between their elements, such that a change in one element influences the performance of other elements. Kauffman’s NK model offers a way to depict such interdependencies and has therefore often been used in economic investigations of the influence of problem or search decomposition on the attainable results. However, papers on the effect of different decompositions on solution quality come to contradictory conclusions. Some observe an initial advantage of over-modularization where others do not. As they also differ in the employed search procedures, but do not base them on empirical findings, the present paper examines the results of more empirically based search strategies. Using algorithms based on innovation strategies derived from patent data, the paper establishes a clear advantage of correct problem decompositions.     

Method of Successive Weighted Averages (MSWA) and Self-Regulated Averaging Schemes for Solving Stochastic User Equilibrium Problem

Although stochastic user equilibrium (SUE) problem has been studied extensively in the past decades, the solution convergence of SUE is generally quite slow because of the use of the method of successive averages (MSA), in which the auxiliary flow pattern generated at each iteration contributes equally to the final solution. Realizing that the auxiliary flow pattern is in fact approaching to the solution point when the iteration number is large, in this paper, we introduce the method of successive weighted averages (MSWA) that includes a new step size sequence giving higher weights to the auxiliary flow patterns from the later iterations. We further develop a self-regulated averaging method, in which the step sizes are varying, rather than fixed, depending on the distance between intermediate solution and auxiliary point. The proposed step size sequences in both MSWA and self-regulated averaging method satisfy the Blum theorem, which guarantees the convergence of SUE problem. Computational results demonstrate that convergence speeds of MSWA and self-regulated averaging method are much faster than those of MSA and the speedup factors are in a manner of magnitude for high accuracy solutions. Besides SUE problem, the proposed methods can also be applied to other fixed-point problems where MSA is applicable, which have wide-range applications in the area of transportation networks.     

A Heuristic Approach to the Multitask-Multiprocessor Assignment Problem using the Empty-Slots Method and Rate Monotonic Scheduling

A heuristic approach to the problem of assigning a set of preemptible resource-sharing and blockable real-time tasks to be executed in a set of heterogeneous processors communicated through an interprocessor network, is presented. The problem is NP-hard. The empty-slots method is used to test the RM schedulability in each processor. There are placement, time, memory, communication and precedence constraints. A general expression for the modification of hard-precedence deadlines of related tasks executing in the same or in different processors is given. The effects of the Average Processor Utilization Factor and the Network Bandwidth on the number of solutions found are shown and discussed through systematic sets of examples. Also, Success Ratios are obtained and plotted vs. Average Processor Utilization Factors for different Network Bandwidths. Results obtained are compared to those obtained by other methods.     

Multiple Robot Rearrangement Planning Using a Territorial Approach and an Extended Project Scheduling Problem Solver

In this paper, we address a multiple robot rearrangement problem. For different applications, problem-solving methods should be able to cope with various working environments. We focus on small working environments in particular with a concentrated arrangement of objects and narrow corridors. In this type of environment, the rearrangement problem can be very complicated because of high computational cost for priority settings to prevent robots from colliding and constraints related to the order of transportation. We propose a practical algorithm that divides a complicated rearrangement problem into simple subproblems. In our method, the rearrangement problem can be reduced to a project scheduling problem using a territorial approach. The application of a territorial approach can relax the complexity of priority settings, but yields new kinds of constraints at the same time. We propose an extended project scheduling problem solver to address these constraints. The solver is constructed on the basis of meta-heuristic strategy and generates the order of transportation that observes constraints. The proposed method is tested in a simulated environment with up to four mobile robots and 12 movable objects. Simulation results show the effectiveness of our method with respect to the applicability and a reasonable calculation time.     

Solving Part-Type Selection and Operation Allocation Problems in an FMS: An Approach Using Constraints-Based Fast Simulated Annealing Algorithm

Production planning of a flexible manufacturing system (FMS) is plagued by two interrelated problems, namely 1) part-type selection and 2) operation allocation on machines. The combination of these problems is termed a machine loading problem, which is treated as a strongly NP-hard problem. In this paper, the machine loading problem has been modeled by taking into account objective functions and several constraints related to the flexibility of machines, availability of machining time, tool slots, etc. Minimization of system unbalance (SU), maximization of system throughput (TH), and the combination of SU and TH are the three objectives of this paper, whereas two main constraints to be satisfied are related to time and tool slots available on machines. Solutions for such problems even for a moderate number of part types and machines are marked by excessive computational complexities and thus entail the application of some random search optimization techniques to resolve the same. In this paper, a new algorithm termed as constraints-based fast simulated annealing (SA) is proposed to address a well-known machine loading problem available in the literature. The proposed algorithm enjoys the merits of simple SA and simple genetic algorithm and is designed to be free from some of their drawbacks. The enticing feature of the algorithm is that it provides more opportunity to escape from the local minimum. The application of the algorithm is tested on standard data sets, and superiority of the same is witnessed. Intensive experimentations were carried out to evaluate the effectiveness of the proposed algorithm, and the efficacy of the same is authenticated by efficiently testing the performance of algorithm over well-known functions