求解包含复杂关联约束的JSSP 的二级嵌套混合算法

作业车间调度问题(JSSP)包含“设备分配”和“工序排序” 2 个相互耦合的子问题,目 前的研究主要集中于工序串行的小规模问题。如果工序之间还存在并行、甚至嵌套等复杂关联 约束,则可行域性状非常复杂,当规模较大时,甚至难以求得可行解。针对以上难点问题,在 分别发挥遗传算法求解“分配问题”和蚁群算法求解“排序问题”的优势基础上,提出了二级嵌套 模型及其基本思路。通过一系列改进策略,如：基于工序的整数编码策略、基于设备类型的多 节点交叉策略、设备类别区间内基因互换的变异策略、基于逆向遍历的可行路径形成策略、基 于最短加工时间的信息素播洒与更新策略等等,构造了集成遗传算法与蚁群算法于同一循环体 的二级嵌套混合算法。针对中等规模问题,分别采用遗传算法、蚁群算法、二级嵌套蚁群算法、 遗传算法与蚁群算法相结合的二级嵌套混合算法,进行了对比试验研究。结果验证了所提算法 的可靠性和优越性,为求解包含复杂关联约束的JSSP 提供了新思路和新方法。     

使用基于SVM的局部潜在语义索引进行文本分类

潜在语义索引(LSI)通过奇异值分解(SVD)获得原始词—文档矩阵的潜在语义结构,在一定程度上解决了一词多义和多词一义问题。但目前文本分类中使用LSI方法的效果并不理想,这是因为没有充分考虑分类信息。为解决该问题,提出一种改进的局部潜在语义索引(LLSI)方法,使用支持向量机(SVM)来产生局部区域。实验结果表明,该方法是有效的。     

The Ising genetic algorithm with Gibbs distribution sampling: Application to FIR filter design

In this paper the design of maximally flat linear phase finite impulse response (FIR) filters is considered. The problem with using the genetic algorithm (GA) in this kind of problems is the high cost of evaluating the fitness for each string in the population. The designing of optimum FIR filters under given constraints and required criteria includes exhaustive number of evaluations for filter coefficients, and the repetitive evaluations of objective functions that implicitly constitutes construction of the filter transfer functions. This problem is handled here with acceptable results utilizing Markov random fields (MRF's) approach. We establish a new theoretical approach here and we apply it on the design of FIR filters. This approach allows us to construct an explicit probabilistic model of the GA fitness function forming what is called the “Ising GA” that is based on sampling from a Gibbs distribution. Ising GA avoids the exhaustive design of suggested FIR filters (solutions) for every string of coefficients in every generation and replace this by a probabilistic model of fitness every gap (period) of iterations. Experimentations done with Ising GA of probabilistic fitness models are less costly than those done with standard GA and with high quality solutions.     

A high-performance parallel implementation of the certified reduced basis method

The certified reduced basis method (herein RB method) is a popular approach for model reduction of parametrized partial differential equations. In this paper we introduce new techniques that are required to efficiently implement the Offline “Construction stage” of the RB method on high-performance parallel supercomputers. This enables us to generate certified RB models for large-scale three-dimensional problems that can be evaluated on standard workstations and other “thin” computing resources with speedup of many orders of magnitude compared to the corresponding full order model. We use our implementation to perform detailed numerical studies for two computationally expensive model problems: a natural convection fluid flow problem and a “many parameter” heat transfer problem. In the heat transfer problem, we exploit the computational efficiency of the RB method to perform a detailed study of “snapshot” selection in the Greedy algorithm, and we also examine statistics of the output sensitivity derivatives to obtain a “global” view of the relative importance of the parameters.     

On improving normal boundary intersection method for generation of Pareto frontier

Gradient-based methods, including Normal Boundary Intersection (NBI), for solving multi-objective optimization problems require solving at least one optimization problem for each solution point. These methods can be computationally expensive with an increase in the number of variables and/or constraints of the optimization problem. This paper provides a modification to the original NBI algorithm so that continuous Pareto frontiers are obtained “in one go,” i.e., by solving only a single optimization problem. Discontinuous Pareto frontiers require solving a significantly fewer number of optimization problems than the original NBI algorithm. In the proposed method, the optimization problem is solved using a quasi-Newton method whose history of iterates is used to obtain points on the Pareto frontier. The proposed and the original NBI methods have been applied to a collection of 16 test problems, including a welded beam design and a heat exchanger design problem. The results show that the proposed approach significantly reduces the number of function calls when compared to the original NBI algorithm.     

Graphical models for optimal power flow

Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for “smart grid” applications like control of distributed energy resources. Numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.     

A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass models

A new recursive branch-and-bound algorithm is presented for solving the quadratic discrete optimization problem, which is related physically to that of finding the exact ground state of a finite Ising spin-glass model. Computational results are reported for systems with dimensions up to n = 60.     

General-purpose vision chip architecture for real-time machine vision

To solve the I/O bottleneck problem in existing vision systems and to realize versatile processing adaptive to various and changing environments, we propose a new vision chip architecture for applications such as robot vision. The chip has general-purpose processing elements (PEs) with each PE being directly connected to a photo detector (PD) and can implement various visual processing algorithms. We developed and simulated some sample programs for the chip and proved that they can be processed within 1 ms/frame, a rate that is high enough for high-speed visual feedback for robot control. Aiming to complete the chip, we are now developing test chips based on the architecture. The latest design has 8 x 8 PEs and PDs in an area 3.3 mm x 3.0 mm using a 0.8 μm CMOS process.     

A hybrid optimization approach for layout design of unequal-area facilities

A hybrid optimization approach is presented for the layout design of unequal-area facilities. Simulated annealing is used to optimize a randomly generated initial placement on an “extended plane” considering the unequal-area facilities enclosed in magnified envelop blocks. An analytical method is then applied to obtain the optimum placement of each envelop block in the direction of steepest descent. Stepwise reduction of the sizes of the envelop blocks allows controlled convergence in a multi-phase optimization process. The presented test problems include two large size benchmark problems of 50 and 100 facilities of unequal areas. The results indicate that although the computational cost is relatively quite high, the technique is a significant improvement over previously published techniques for unequal-area facilities and can yield solutions of the same quality as obtained by PLANOPT, a general-purpose layout optimization program based on pseudo-exhaustive search.     

A memory based differential evolution algorithm for unconstrained optimization

In optimization, the performance of differential evolution (DE) and their hybrid versions exist in the literature is highly affected by the inappropriate choice of its operators like mutation and crossover. In general practice, during simulation DE does not employ any strategy of memorizing the so-far-best results obtained in the initial part of the previous generation. In this paper, a new “Memory based DE (MBDE)” presented where two “swarm operators” have been introduced. These operators based on the pBEST and gBEST mechanism of particle swarm optimization. The proposed MBDE is employed to solve 12 basic, 25 CEC 2005, and 30 CEC 2014 unconstrained benchmark functions. In order to further test its efficacy, five different test system of model order reduction (MOR) problem for single-input and single-output system are solved by MBDE. The results of MBDE are compared with state-of-the-art algorithms that also solved those problems. Numerical, statistical, and graphical analysis reveals the competency of the proposed MBDE.     

The problem of fair division for a hybrid resource

We propose an elementary solution to the apartment rent division problem. This problem belongs to the class of problems of “fair division,” but differs from its standard setting by “heterogeneity,” i.e., the presence of both a conventional continuous component and a discrete one, a fixed set of rooms. A combinatorial-topological approach to solving this problem in a finite number of steps (each of which requires a survey of all participants), actively used in the literature, allows to obtain an approximate decision only. We propose a fundamentally different setting, based on a priori estimates of each room by the participants and allowing, in principle, to consider various optimization tasks as well. Our approach is particularly relevant in the case of a large number of participants. We also note that the proposed approach allows to find a solution in a number of cases where the combinatorial-topological approach does not work.     

Ensemble particle swarm optimizer

According to the “No Free Lunch (NFL)” theorem, there is no single optimization algorithm to solve every problem effectively and efficiently. Different algorithms possess capabilities for solving different types of optimization problems. It is difficult to predict the best algorithm for every optimization problem. However, the ensemble of different optimization algorithms could be a potential solution and more efficient than using one single algorithm for solving complex problems. Inspired by this, we propose an ensemble of different particle swarm optimization algorithms called the ensemble particle swarm optimizer (EPSO) to solve real-parameter optimization problems. In each generation, a self-adaptive scheme is employed to identify the top algorithms by learning from their previous experiences in generating promising solutions. Consequently, the best-performing algorithm can be determined adaptively for each generation and assigned to individuals in the population. The performance of the proposed ensemble particle swarm optimization algorithm is evaluated using the CEC2005 real-parameter optimization benchmark problems and compared with each individual algorithm and other state-of-the-art optimization algorithms to show the superiority of the proposed ensemble particle swarm optimization (EPSO) algorithm.     

A dedicated algorithm for calculating ground states for the triangular random bond Ising model

In the presented article we present an algorithm for the computation of ground state spin configurations for the 2d random bond Ising model on planar triangular lattice graphs. Therefore, it is explained how the respective ground state problem can be mapped to an auxiliary minimum-weight perfect matching problem, solvable in polynomial time. Consequently, the ground state properties as well as minimum-energy domain wall (MEDW) excitations for very large 2d systems, e.g. lattice graphs with up to N=384×384 spins, can be analyzed very fast.Here, we investigate the critical behavior of the corresponding T=0 ferromagnet to spin-glass transition, signaled by a breakdown of the magnetization, using finite-size scaling analyses of the magnetization and MEDW excitation energy and we contrast our numerical results with previous simulations and presumably exact results.     

Analytical expressions for a finite-size 2D Ising model

Numerical methods are used to examine the thermodynamic characteristics of the twodimensional Ising model as a function of the number of spins N. Onsager’s solution is generalized to a finite-size lattice, and experimentally validated analytical expressions for the free energy and its derivatives are computed. The heat capacity at the critical point is shown to grow logarithmically with N. Due to the finite extent of the system the critical temperature can only be determined to some accuracy.     

Methods for interfacing analysis software to optimization software

Three methods are presented for interfacing analysis software to optimization software to create design software. These methods are referred to as the “conventional interface”, the “pro-gramming-free interface”, and the “generalized interface”. The latter two methods introduce new ideas which are attractive from the user's standpoint. The programming-free interface simplifies the interface process by eliminating the necessity for tlie user to modify the analysis source code. The generalized interface allows one to create a general-purpose design package from a general-purpose analysis package. Support for the methods has been implemented in a software package named OPTDES.BYU. Use of the methods with this package is illustrated with a simple example.     

Non-Hermitian quantum annealing in the antiferromagnetic Ising chain

A non-Hermitian quantum optimization algorithm is created and used to find the ground state of an antiferromagnetic Ising chain. We demonstrate analytically and numerically (for up to $N=1,024$ spins) that our approach leads to a significant reduction in the annealing time that is proportional to $\ln N$ , which is much less than the time (proportional to $N^2$ ) required for the quantum annealing based on the corresponding Hermitian algorithm. We propose to use this approach to achieve similar speed-up for NP-complete problems by using classical computers in combination with quantum algorithms.     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

基于生成对抗双网络的虚拟到真实驾驶场景的视频翻译模型

针对虚拟到真实驾驶场景翻译中成对的数据样本缺乏以及前后帧不一致等问题，提出一种基于生成对抗网络的视频翻译模型。为解决数据样本缺乏问题，模型采取“双网络”架构，将语义分割场景作为中间过渡分别构建前、后端网络。在前端网络中，采用卷积和反卷积框架，并利用光流网络提取前后帧的动态信息，实现从虚拟场景到语义分割场景的连续的视频翻译；在后端网络中，采用条件生成对抗网络框架，设计生成器、图像判别器和视频判别器，并结合光流网络，实现从语义分割场景到真实场景的连续的视频翻译。实验利用从自动驾驶模拟器采集的数据与公开数据集进行训练和测试，在多种驾驶场景中能够实现虚拟到真实场景的翻译，翻译效果明显好于对比算法。结果表明，所提模型能够有效解决前后帧不连续和动态目标模糊的问题，使翻译的视频更为流畅，并且能适应多种复杂的驾驶场景。     

A multi-objective optimization approach for integrated production planning under interval uncertainties in the steel industry

This paper investigates one of the key decision-making problems referring to the integrated production planning (IPP) for the steelmaking continuous casting-hot rolling (SCC-HR) process in the steel industry. The complexities of the practical IPP problem are mainly reflected in three aspects: large-scale decision variables; multiple objectives and interval-valued uncertain parameters. To deal with the difficulty of large-scale decision variables, we introduce a new concept named “order-set” for modeling. In addition, considering the multiple objectives and uncertainties of the given IPP problem, we construct a multi-objective optimization model with interval-valued objective functions to optimize the throughput of each process, the hot charge ratio of slabs, the utilization rate of tundishes and the additional cost of technical operations. Furthermore, we propose a novel approach based on a modified interval multi-objective optimization evolutionary algorithm (MI-MOEA) to solve the problem. The proposed model and algorithm were tested with daily production data from an iron and steel company in China. Computational experiments demonstrate that the proposed method generates quite effective and practical solutions within a short time. Based on the IPP model and MI-MOEA, an IPP system has been developed and implemented in the company.     

A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization

This paper presents a novel model for a time dependent vehicle routing problem when there is a competition between distribution companies for obtaining more sales. In a real-world situation many factors cause the time dependency of travel times, for example traffic condition on peak hours plays an essential role in outcomes of the planned schedule in urban areas. This problem is named as “Time dependent competitive vehicle routing problem” (TDVRPC) which a model is presented to satisfy the “non-passing” property. The main objectives are to minimize the travel cost and maximize the sale in order to serve customers before other rival distributors. To solve the problem, a Modified Random Topology Particle Swarm Optimization algorithm (RT-PSO) is proposed and the results are compared with branch and bound algorithm in small size problems. In large scales, comparison is done with original PSO. The results show the capability of the proposed RT-PSO method for handling this problem.