Some preconditioners for elliptic PDE-constrained optimization problems

For the structured systems of linear equations arising from the Galerkin finite element discretizations of elliptic PDE-constrained optimization problems, some preconditioners are proposed to accelerate the convergence rate of Krylov subspace methods such as GMRES for both cases of the Tikhonov parameter $\beta$ not very small (equal or greater than 1e?6) and sufficiently small (less than 1e?6), respectively. We derive the explicit expressions for the eigenvalues and eigenvectors of the corresponding preconditioned matrices. Numerical results show that the corresponding preconditioned GMRES methods perform and match well with the theoretical results.     

Parallelizing implicit algorithms for time-dependent problems by parabolic domain decomposition

Applications of the multidomain Local Fourier Basis method [1], for the solution of PDEs on parallel computers are described. The present approach utilizes, in an explicit way, the rapid (exponential) decay of the fundamental solutions of elliptic operators resulting from semi-implicit discretizations of parabolic time-dependent problems. As a result, the global matching relations for the elemental solutions are decoupled into local interactions between pairs of solutions in neighboring domains. Such interactions require only local communications between processors with short communication links. Thus the present algorithm overcomes the global coupling, inherent both in the use of the spectral Fourier method and implicit time discretization scheme.This research is supported partly by a grant from the French-Israeli Binational Foundation for 1991–1992.     

Optimized Schwarz methods without overlap for highly heterogeneous media

In this paper an original variant of the Schwarz domain decomposition method is introduced for heterogeneous media. This method uses new optimized interface conditions specially designed to take into account the heterogeneity between the sub-domains on each sides of the interfaces. Numerical experiments illustrate the dependency of the proposed method with respect to several parameters, and confirm the robustness and efficiency of this method based on such optimized interface conditions. Several mesh partitions taking into account multiple cross points are considered in these experiments.     

A finite difference non-matching domain decomposition algorithm for the parabolic equation

A finite difference domain decomposition algorithm on a non-overlapping non-matching grid for the parabolic equation is discussed. The basic procedure is to define the explicit scheme at the interface points with a larger mesh spacing H, then the implicit schemes with different mesh spacings are applied on the non-matching subdomains, respectively. The stability bound is released both for the one-dimensional and two-dimensional parabolic problem. Finally, numerical experiments are also presented.     

Restricted overlapping balancing domain decomposition methods and restricted coarse problems for the Helmholtz problem

Overlapping balancing domain decomposition methods and their combination with restricted additive Schwarz methods are proposed for the Helmholtz equation. These new methods also extend previous work on non-overlapping balancing domain decomposition methods toward simplifying their coarse problems and local solvers. They also extend restricted Schwarz methods, originally designed to overlapping domain decomposition and Dirichlet local solvers, to the case of non-overlapping domain decomposition and/or Neumann and Sommerfeld local solvers. Finally, we introduce coarse spaces based on partitions of unity and planes waves, and show how oblique projection coarse problems can be designed from restricted additive Schwarz methods. Numerical tests are presented.     

Approximation algorithms for combinatorial multicriteria optimization problems

The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and # P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability.     

多频段时域分解的行为识别特征优选方法

为了降低外界环境对移动用户行为识别的影响,保留行为敏感特征、提高行为识别的准确率,提出了一种多频段时域分解的人体行为识别特征优选方法.该方法对行为样本数据进行多频段分解,计算样本数据在不同频段信号的特征,利用遗传算法以决策树作为分类器进行特征优选,在多组特征中搜索出近似最优的特征组合.实验结果表明,该方法优选出的特征组合能有效提高行为识别的准确率.     

Explicit/implicit and Crank–Nicolson domain decomposition methods for parabolic partial differential equations

Two parallel non-overlapping domain decomposition algorithms for solving parabolic partial differential equations are proposed. The algorithms combine Crank–Nicolson scheme with implicit Galerkin finite element methods in sub-domains and explicit flux approximation along inner boundaries at each time step. Thus, parallelism can be easily achieved. $L^2$-norm error estimates for these explicit/implicit procedures are presented, in which time step constraints are proved to be less severe than that of fully explicit schemes. Numerical experiments are also performed to verify the theoretical analysis.     

整数规划问题智能求解算法综述*

为了对大规模整数规划问题的求解方法提供参考,对基于智能算法求解整数规划问题的研究进行了分析和评述。鉴于现有算法的缺陷与不足,讨论了应用智能算法求解整数规划问题未来可能的研究方向。     

Evolutionary algorithms for optimization problems with uncertainties and hybrid indices

Many optimization problems in real-world applications contain both explicit (quantitative) and implicit (qualitative) indices that usually contain uncertain information. How to effectively incorporate uncertain information in evolutionary algorithms is one of the most important topics in information science. In this paper, we study optimization problems with both interval parameters in explicit indices and interval uncertainties in implicit indices. To incorporate uncertainty in evolutionary algorithms, we construct a mathematical uncertain model of the optimization problem considering the uncertainties of interval objectives; and then we transform the model into a precise one by employing the method of interval analysis; finally, we develop an effective and novel evolutionary optimization algorithm to solve the converted problem by combining traditional genetic algorithms and interactive genetic algorithms. The proposed algorithm consists of clustering of a large population according to the distribution of the individuals and estimation of the implicit indices of an individual based on the similarity among individuals. In our experiments, we apply the proposed algorithm to an interior layout problem, a typical optimization problem with both interval parameters in the explicit index and interval uncertainty in the implicit index. Our experimental results confirm the feasibility and efficiency of the proposed algorithm.     

Multi-operator based evolutionary algorithms for solving constrained optimization problems

Over the last two decades, many sophisticated evolutionary algorithms have been introduced for solving constrained optimization problems. Due to the variability of characteristics in different COPs, no single algorithm performs consistently over a range of problems. In this paper, for a better coverage of the problem characteristics, we introduce an algorithm framework that uses multiple search operators in each generation. The appropriate mix of the search operators, for any given problem, is determined adaptively. The framework is tested by implementing two different algorithms. The performance of the algorithms is judged by solving 60 test instances taken from two constrained optimization benchmark sets from specialized literature. The first algorithm, which is a multi-operator based genetic algorithm (GA), shows a significant improvement over different versions of GA (each with a single one of these operators). The second algorithm, using differential evolution (DE), also confirms the benefit of the multi-operator algorithm by providing better and consistent solutions. The overall results demonstrated that both GA and DE based algorithms show competitive, if not better, performance as compared to the state of the art algorithms.     

基于模型分解的多机带时间窗口任务规划算法

针对多机带时间窗口任务规划问题,提出了基于模型分解的规划求解算法。通过引入基于逻辑的Benders分解方法,将经典Benders分解算法应用扩展至带离散时间窗口的混合线性整数规划模型,实现模型分解。采用工艺级商业软件MOSEK与GECODE分别求解主、子问题,同时给出Benders剪枝函数生成方法,以迭代方式收敛解空间获得可行解。实现算法并设计测试案例,实验结果验证了算法的有效性。     

基于网格的一种新的动态演化算法

近年来,越来越多的演化计算研究者对动态优化问题产生了很大的兴趣,并产生了很多解决动态优化问题的方法。提出一种新的动态演化算法,与传统的演化算法有所不同,它是建立在划分网格基础上的,故而称它为网格优化算法。通过测试典型的动态优化问题,并与经典的SOS算法进行比较,证明了算法的有效性。     

Efficient algorithms for computing two nearest-neighbor problems on a rap

This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N^1/2 × N^1/2 image using N^1/2 × N^1/2 processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.     

A comparison between optimization algorithms applied to synchronization of bilateral teleoperation systems against time delay and modeling uncertainties

The goal of this paper is to achieve optimal performance for synchronization of bilateral teleoperation systems against time delay and modeling uncertainties, in both free and contact motions. Time delay in bilateral teleoperation systems imposes a delicate tradeoff between the conflicting requirements of stability and transparency. To this reason, in this paper, population-based optimization algorithms are employed to tuning the proposed controller parameters. The performance of tuned controllers is compared with the gains obtained by Cuckoo Optimization Algorithm (COA), Biogeography-Based Optimization (BBO), Imperialist Competitive Algorithm (ICA), Artificial Bee Colony (ABC), Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Ant Colony Optimization with continuous domain (ACOR), Self-adaptive Differential Evolution with Neighborhood Search (SaNSDE), Adaptive Differential Evolution with Optional External Archive (JADE), Differential Evolution with Ensemble of Parameters and mutation strategies (EPSDE) and Cuckoo Search (CS). Through numerical simulations, the validity of the proposed method is illustrated. It is also shown that the COA algorithm is able to solve synchronization problem with high performance in stable transparent bilateral teleoperation systems.     

Compromise utilitarian solutions in multi-criteria optimization problems as a guide for evolutionary algorithms

Multi-criteria optimization problems are considered where the decision maker is unable to determine the exact weights of importance of the criteria but can provide some imprecise information about these weights. Two solution concepts are studied in this framework: the optimistic min–max solution and the compromise utilitarian solution, both of which can be exactly computed for linear problems. For general problems, it is shown that these solutions can be approximated by means of a slight modification of the evolutionary algorithm NSGA-II.     

旁域更新智能水滴算法软时间窗车辆路径优化

利用智能水滴算法（IWD）特点,设计了基于IWD算法的车辆路径优化算法框架。针对标准IWD算法在泥土更新上过于单一的缺点,设计了旁域更新的泥土含量更新机制,考虑整个河道的泥土信息变化,增加了其他水滴到达目标节点的概率;提出了车辆路径IWD算法的编码方式,基于改进的旁域更新IWD算法设计了软时间窗车辆路径优化算法;通过实验仿真,对比旁域IWD算法与标准算法及粒子群算法的车辆路径优化结果,显示该算法相比对比算法具有更高的收敛精度和更快的收敛时间。     

A hybrid ant colony optimization approach for finite element mesh decomposition

This paper examines the application of the ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite element analysis. The concept of the ant colony optimization technique for finding approximate solutions to combinatorial optimization problems is described.The application of ant colony optimization for partitioning finite element meshes based on triangular elements is described.A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh decomposition is carried out using normal and predictive modes for which the predictive mode uses a trained multilayered feed-forward neural network which estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite element meshes is examined by decomposing two mesh examples.     

Greedy algorithms for eigenvalue optimization problems in shape design of two-density inhomogeneous materials

This paper studies the eigenvalue optimization problems in the shape design of the two-density inhomogeneous materials. Two types of greedy algorithms are proposed to solve three optimization problems in finite element discretization. In the first type, the whole domain is initialized by one density. For each problem of the eigenvalue optimizations, we define a measurement of the element, which is the criterion to determine the ‘best’ element. We change the density of the ‘best’ element to the other density. Then the algorithm repeats the procedure until the area constraint is satisfied. In the second type, the algorithm begins with the density distribution satisfying the area constraint. Also, according to the measurement of the element, the algorithm finds a pair of the ‘best’ elements and exchanges their densities between each other. Furthermore, the accelerating greedy algorithms are proposed to speed up both two types. Three numerical examples are provided to illustrate the results.