Information theoretic approach to man-machine interface complexityevaluation

We analyze the interactions between human operators and control room equipment and find that several factors affect the information-gathering and decision-making processes of operators: contents of the provided information, the way information is provided, and knowledge of the operators. These factors contribute to the perceived cognitive complexity by human operators in plant operation. Based on the information theory concept, we propose an integrated framework for evaluating this complexity. The proposed framework is designed to be applied to various types of control room equipment which have different types of man-machine interface and contain different types of information. An experimental verification for the proposed framework is performed and its result shows that the framework successfully integrates various aspects of man-machine interface systems and estimates the mental workload of human operators     

A high performing metaheuristic for job shop scheduling with sequence-dependent setup times

This paper investigates scheduling job shop problems with sequence-dependent setup times under minimization of makespan. We develop an effective metaheuristic, simulated annealing with novel operators, to potentially solve the problem. Simulated annealing is a well-recognized algorithm and historically classified as a local-search-based metaheuristic. The performance of simulated annealing critically depends on its operators and parameters, in particular, its neighborhood search structure. In this paper, we propose an effective neighborhood search structure based on insertion neighborhoods as well as analyzing the behavior of simulated annealing with different types of operators and parameters by the means of Taguchi method. An experiment based on Taillard benchmark is conducted to evaluate the proposed algorithm against some effective algorithms existing in the literature. The results show that the proposed algorithm outperforms the other algorithms.     

A new bidding framework for combinatorial e-auctions

Bidding languages define the means through which participants in an electronic auction define bids and express requirements on their execution. The current state of combinatorial auction market design indicates that no existing bidding language is general enough to support auctions of both divisible and indivisible commodities. In this paper, we propose a novel bidding framework based on a two-level representation of a combined bid. At the inner level, bidding operators impose conditions on the executed proportions of packages of atomic single-item bids. Partial bids defined this way are then recursively combined through logical operators to produce a final combined bid that is submitted to the auctioneer. We present a formal specification of the framework, and analyze how it impacts the mathematical programming formulation of the allocation problem. An application in the context of combinatorial auctions of financial assets illustrates the utilization of the proposed bidding framework.     

一种求解TSP问题的离散蝙蝠算法

蝙蝠算法是一种新型的群智能优化算法,在求解连续域优化问题上取得了较好的优化效果,但在离散优化领域的应用较少。研究了求解TSP问题的离散蝙蝠算法,设计了相关操作算子实现算法的离散化,并引入逆序操作使算法跳出局部最优。对TSPLIB标准库中若干经典实例进行测试并与粒子群和遗传算法进行对比分析,结果表明设计的离散蝙蝠算法无论在求解质量还是求解效率上都有明显优势,是一种高效的优化算法。     

Multidimensional statistical analysis of the parameterization of a genetic algorithm for the optimal ordering of tables

The optimal table row and column ordering can reveal useful patterns to improve reading and interpretation. Recently, genetic algorithms using standard crossover and mutation operators have been proposed to tackle this problem. In this paper, we carry out an experimental study that adds to this genetic algorithm crossover and mutation operators specially designed to deal with permutations and includes other parameters (initialization, replacement policy, mutation and crossover rates and stopping criteria) not examined in previous works. A proper analysis of the results must take into account all the parameters simultaneously, since the wrong conclusions can be drawn by studying each separately from the others. This is why we propose a framework for a multidimensional analysis of the results. This includes multiple hypothesis testing and a regression tree that builds a parsimonious and predictive model of the suitable configurations of the parameters.     

A genetic algorithm with proper parameters for manufacturing cell formation problems

One fundamental problem in cellular manufacturing is the formation of product families and machine cells. Many solution methods have been developed for the cell formation problem. Since efficient grouping is the prerequisite of a successful Cellular Manufacturing installation the research in this area will likely be continued. In this paper, we consider the problem of cell formation in cellular manufacturing systems with the objective of maximizing the grouping efficacy. We propose a Genetic Algorithm (GA) to obtain machine-cells and part-families. Developed GA has three different selection and crossover operators. The proper operators and parameters of the GA were determined by design of experiments. A set of 15 test problems with various sizes drawn from the literature is used to test the performance of the proposed algorithm. The corresponding results are compared to several well-known algorithms published. The comparative study shows that the proposed GA improves the grouping efficacy for 40% of the test problems.     

基于包簇映射的云计算资源分配框架

在云计算资源调度中存在着结构复杂、数据量庞大的可扩展问题,针对该问题提出了一种基于包簇映射的资源管理框架。该框架下包内允许资源共享,当指定资源共享使用模式后,资源调配更具灵活性。将改进的基于包的遗传算法运用到该框架中,采用染色体组方式和资源方式进行编码,根据染色体长度变化设计交叉算子和变异算子,将簇的个数与包的资源相互整合,并且通过抽象模型来降解问题规模。实验结果表明,在基于包簇映射框架下的遗传算法与传统的以虚拟机为中心框架下的遗传算法和基于包簇框架的首次适应算法相比,在CPU利用率方面分别平均提高9%和5%,在内存利用率方面分别平均提高14%和7%。实验结果表明,所提出的包簇框架下的遗传算法能有效减少簇节点的使用数量,提高资源利用率。     

Genetic algorithm–based training for semi-supervised SVM

The Support Vector Machine (SVM) is an interesting classifier with excellent power of generalization. In this paper, we consider applying the SVM to semi-supervised learning. We propose using an additional criterion with the standard formulation of the semi-supervised SVM (S ³ VM) to reinforce classifier regularization. Since, we deal with nonconvex and combinatorial problem, we use a genetic algorithm to optimize the objective function. Furthermore, we design the specific genetic operators and certain heuristics in order to improve the optimization task. We tested our algorithm on both artificial and real data and found that it gives promising results in comparison with classical optimization techniques proposed in literature.     

Consensus controller for multi-UAV navigation

In this paper, we design consensus algorithms for multiple unmanned aerial vehicles (UAV). We mainly focus on the control design in the face of measurement noise and propose a position consensus controller based on the sliding mode control by using the distributed UAV information. Within the framework of Lyapunov theory, it is shown that all signals in the closed-loop multi-UAV systems are stabilized by the proposed algorithm, while consensus errors are uniformly ultimately bounded. Moreover, for each local UAV, we propose a mechanism to define the trustworthiness, based on which the edge weights are tuned to eliminate negative influence from stubborn agents or agents exposed to extremely noisy measurement. Finally, we develop software for a nano UAV platform, based on which we implement our algorithms to address measurement noises in UAV flight tests. The experimental results validate the effectiveness of the proposed algorithms.     

Structural pattern recognition using genetic algorithms with specialized operators

This paper presents a genetic algorithm (GA)-based optimization procedure for structural pattern recognition in a model-based recognition system using attributed relational graph (ARG) matching technique. The objective of our work is to improve the GA-based ARG matching procedures leading to a faster convergence rate and better quality mapping between a scene ARG and a set of given model ARGs. In this study, potential solutions are represented by integer strings indicating the mapping between scene and model vertices. The fitness of each solution string is computed by accumulating the similarity between the unary and binary attributes of the matched vertex pairs. We propose novel crossover and mutation operators, specifically for this problem. With these specialized genetic operators, the proposed algorithm converges to better quality solutions at a faster rate than the standard genetic algorithm (SGA). In addition, the proposed algorithm is also capable of recognizing multiple instances of any model object. An efficient pose-clustering algorithm is used to eliminate occasional wrong mappings and to determine the presence/pose of the model in the scene. We demonstrate the superior performance of our proposed algorithm using extensive experimental results.     

Some issues of designing genetic algorithms for traveling salesman problems

This paper demonstrates that a robust genetic algorithm for the traveling salesman problem (TSP) should preserve and add good edges efficiently, and at the same time, maintain the population diversity well. We analyzed the strengths and limitations of several well-known genetic operators for TSPs by the experiments. To evaluate these factors, we propose a new genetic algorithm integrating two genetic operators and a heterogeneous pairing selection. The former can preserve and add good edges efficiently and the later will be able to keep the population diversity. The proposed approach was evaluated on 15 well-known TSPs whose numbers of cities range from 101 to 13509. Experimental results indicated that our approach, somewhat slower, performs very robustly and is very competitive with other approaches in our best surveys. We believe that a genetic algorithm can be a stable approach for TSPs if its operators can preserve and add edges efficiently and it maintains population diversity.     

Ensemble mating selection in evolutionary many-objective search

Traditional multi-objective evolutionary algorithms have encountered difficulties when handling many-objective problems. This is due to the loss of selection pressure incurred by the growing size of objective space. A variety of environmental selection operators have been proposed to address the issue, each has its distinct benefits and drawbacks. We develop a novel ensemble framework to enhance the effectiveness and robustness of many-objective optimization. The framework incorporates multiple environmental selection operators to guide the search, which are then viewed as voters to construct a mating pool. We design an ensemble mating selection strategy that makes decisions based on the preference information provided by the voters: individuals elected by more voters will be assigned larger possibilities to enter the mating pool. By doing so, high quality offspring can be reproduced from the elected promising candidates. To accommodate the multiple selection operators for voting, the framework maintains multiple parallel populations, where each population is updated by one of the selection operators. An instantiation of the framework with three popular operators is presented as a prime example. Extensive experiments have been conducted on a number of many-objective problems to examine the effectiveness of the proposed approach. Experimental results show that the mating selection strategy is capable of improving the quality of the obtained solution set.     

A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems

In this paper, we propose a genetic algorithm using priority-based encoding (pb-GA) for linear and nonlinear fixed charge transportation problems (fcTP) in which new operators for more exploration are proposed. We modify a priority-based decoding procedure proposed by Gen et al. [1] to adapt with the fcTP structure. After comparing well-known representation methods for a transportation problem, we explain our proposed pb-GA. We compare the performance of the pb-GA with the recently used spanning tree-based genetic algorithm (st-GA) using numerous examples of linear and nonlinear fcTPs. Finally, computational results show that the proposed pb-GA gives better results than the st-GA both in terms of the solution quality and computation time, especially for medium- and large-sized problems. Numerical experiments show that the proposed pb-GA better absorbs the characteristics of the nonlinear fcTPs.     

加热炉优化调度模型及算法研究

加热炉是热轧生产中主要的能源消耗设备,其合理调度对于降低生产过程的能耗和生产成本都具有重要作用.根据加热炉的生产工艺和约束条件建立了加热炉优化调度数学模型,针对模型特点提出了分散搜索（scattersearch,SS）算法,设计了基于随机变量序列的投票组合算子和单点交叉组合算子.根据国内某钢铁企业加热炉生产过程的实绩随机生成40个测试案例,进行实验,分析了参考集规模及不同组合算子对SS算法性能的影响,并与遗传局域搜索（genetic local search,GLS）算法的求解结果进行了比较.结果表明所提出的模型和算法对解决本文研究的加热炉调度问题有效.     

Edge sets: an effective evolutionary coding of spanning trees

The fundamental design choices in an evolutionary algorithm (EA) are its representation of candidate solutions and the operators that will act on that representation. We propose representing spanning trees in EAs for network design problems directly as sets of their edges and we describe initialization, recombination, and mutation operators for this representation. The operators offer locality, heritability, and computational efficiency. Initialization and recombination depend on an underlying random spanning-tree algorithm. Three choices for this algorithm, based on the minimum spanning-tree algorithms of Prim and Kruskal and on random walks, respectively, are examined analytically and empirically. We demonstrate the usefulness of the edge-set encoding in an EA for the NP-hard degree-constrained minimum spanning-tree problem. The algorithm's operators are easily extended to generate only feasible spanning trees and to incorporate local, problem-specific heuristics. Comparisons of this algorithm to others that encode candidate spanning trees via the Blob Code, with network random keys, and as strings of weights indicate the superiority of the edge-set encoding, particularly on larger instances.     

基于时态测试器的实时分支时态逻辑模型检测

基于自动机理论的模型检测技术在形式化验证领域处于核心地位, 然而传统自动机在时态算子上不具备可组合性, 导致各种时态逻辑的模型检测算法不能有机整合.本文为了实现集成限界时态算子的实时分支时态逻辑RTCTL*的高效模型检测, 提出一种RTCTL*正时态测试器构造方法, 以及相关符号化模型检测算法.证明了所提出的RTCTL*正时态测试器构造方法是完备的.也证明了该算法时间复杂度与被验证系统呈线性关系, 与公式长度呈指数关系.我们基于JavaBDD软件包成功开发了该算法的模型检测工具MCTK 2.0.0.我们完成了MCTK与著名的符号化模型检测工具nuXmv之间的实验对比分析工作, 结果表明MCTK虽然在内存消耗上要多于nuXmv, 但是MCTK的时间复杂度双指数级小于nuXmv, 使得利用MCTK验证大规模系统的实时时态性质成为可能.     

Interactive shape modeling using Lagrangian surface flow

In this paper, we propose a new shape-modeling paradigm based on the concept of Lagrangian surface flow. Given an input polygonal model, the user interactively defines a distance field around regions of interest; the locally or globally affected regions will then automatically deform according to the user-defined distance field. During the deformation process, the model can always maintain its regularity and can properly modify its topology by topology merging when collisions between two different parts of the model occur. Comparing with level-set based methods, our algorithm allows the user to work directly on existing polygonal models without any intermediate model conversion. Besides closed polygonal models, our algorithm also works for mesh models with open boundaries. Within our framework, we developed a number of shape-modeling operators including blending, cutting, drilling, free-hand sketching, and mesh warping. We applied our algorithm to a variety of examples that demonstrate the usefulness and efficacy of the new technique in interactive shape design and surface deformation.     

Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm

In real life applications we often have the following problem: How to find the reasonable assignment strategy to satisfy the source and destination requirement without shipping goods from any pairs of prohibited sources simultaneously to the same destination so that the total cost can be minimized. This kind of problem is known as the transportation problem with exclusionary side constraint (escTP). Since this problem is one of nonlinear programming models, it is impossible to solve this problem using a traditional linear programming software package (i.e., LINDO). In this paper, an evolutionary algorithm based on a genetic algorithm approach is proposed to solve it. We adopt a Prüfer number to represent the candidate solution to the problem and design the feasibility of the chromosome. Moreover, to handle the infeasible chromosome, here we also propose the repairing procedure. In order to improve the performance of the genetic algorithm, the fuzzy logic controller (FLC) is used to dynamically control the genetic operators. Comparisons with other conventional methods and the spanning tree-based genetic algorithm (st-GA) are presented and the results show the proposed approach to be better as a whole.     

An algorithmic framework of discrete particle swarm optimization

Particle swarm optimization (PSO) was originally developed for continuous problem. To apply PSO to a discrete problem, the standard arithmetic operators of PSO are required to be redefined over discrete space. In this paper, a concept of distance over discrete solution space is introduced. Under this notion of distance, the PSO operators are redefined. After reinterpreting the composition of velocity of a particle, a general framework of discrete PSO algorithm is proposed. As a case study, we illustrate the application of the proposed discrete PSO algorithm to number partitioning problem (NPP) step by step. Preliminary computational experience is also presented. The successful application shows that the proposed algorithmic framework is feasible.     

Spherical evolution for solving continuous optimization problems

In these years, more and more nature-inspired meta-heuristic algorithms have been proposed; search operators have been their core problem. The common characteristics or mechanism of search operators in different algorithms have not been represented by a standard format. In this paper, we first propose the concept of a search pattern and a search style represented by a mathematical model. Second, we propose a new search style, namely a spherical search style, inspired by the traditional hypercube search style. Furthermore, a spherical evolution algorithm is proposed based on the search pattern and spherical search style. At the end, 30 benchmark functions of CEC2017 and a real-world optimization problem are tested. Experimental results and analysis demonstrate that the proposed method consistently outperforms other state-of-the-art algorithms.