Axiom selection over large theory based on new first-order formula metrics

Axiom selection is a task that selects the most likely useful axioms from a large-scale axiom set for proving a given conjecture. Existing axiom selection methods either solely take shallow symbols into account or strongly dependent on previous successful proofs from homologous problems. To address these problems, we introduce a new metric to evaluate the dissimilarity between formulae and utilize it as an evaluator in the selection task. Firstly, we propose a substitution-based metric to compute the dissimilarity between terms. It is a pseudo-metric and can capture the in-depth syntactic difference trigged by both functional and variable subterms. We then extend it to atoms and prove the atom metric also to be a pseudo-metric. Treating formulae as atom sets, we define three kinds of dissimilarity metrics between formulae. Finally, we design and implement conjecture-oriented axiom selection methods based on newly proposed formula metrics. The experimental evaluation is conducted on the MPTP2078 benchmark and demonstrates dissimilarity-based axiom selection improves E prover’s performance. In the best case, it increases the ratio of successful proofs from 30.90% to 42.25%.

     

An evolutionary algorithm for resource-constrained projectscheduling

The single-mode, single-project, resource-constrained project-scheduling problem is solved by an evolutionary algorithm. The design of this algorithm is presented. Results of a computational study on two sets of benchmark problems, the first consisting of 330 problem instances and the second 2040, are presented. These results show that the proposed algorithm is effective in terms of the number of times it achieves both the best-known solutions and the average error with respect to these solutions, particularly given that the best-known solutions have been compiled from various sources, using a variety of algorithms. Moreover, the computation time requirements are quite modest     

A Method for Metric Learning with Multiple-Kernel Embedding

Distance metric learning is rather important for measuring the similarity (/dissimilarity) of two instances in many pattern recognition algorithms. Although many linear Mahalanobis metric learning methods can be extended to their kernelized versions for dealing with the nonlinear structure data, choosing the proper kernel and determining the kernel parameters are still tough problems. Furthermore, the single kernel embedded metric is not suited for the problems with multi-view feature representations. In this paper, we address the problem of metric learning with multiple kernels embedding. By analyzing the existing formulations of metric learning with multiple-kernel embedding, we propose a new framework to learn multi-metrics as well as the corresponding weights jointly, the objective function can be shown to be convex and it can be converted to be a multiple kernel learning-support vector machine problem, which can be solved by existing methods. The experiments on single-view and multi-view data show the effectiveness of our method.     

Measuring the impact of adversarial errors on packet scheduling strategies

In this paper, we explore the problem of achieving efficient packet transmission over unreliable links with worst-case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric to measure the efficiency of scheduling strategies in such a setting. To this end, we propose an asymptotic throughput metric which corresponds to the long-term competitive ratio of the algorithm with respect to the optimal. We then explore the impact of the error detection mechanism and feedback delay on our measure. We compare instantaneous with deferred error feedback, which requires a faulty packet to be fully received in order to detect the error. We propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The asymptotic throughput achieved by these algorithms is shown to be close to optimal by deriving lower bounds on the metric and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of communication systems in adverse environments.     

A hybrid multi-population framework for dynamic environments combining online and offline learning

Population based incremental learning algorithms and selection hyper-heuristics are highly adaptive methods which can handle different types of dynamism that may occur while a given problem is being solved. In this study, we present an approach based on a multi-population framework hybridizing these methods to solve dynamic environment problems. A key feature of the hybrid approach is the utilization of offline and online learning methods at successive stages. The performance of our approach along with the influence of different heuristic selection methods used within the selection hyper-heuristic is investigated over a range of dynamic environments produced by a well known benchmark generator as well as a real world problem, referred to as the Unit Commitment Problem. The empirical results show that the proposed approach using a particular hyper-heuristic outperforms some of the best known approaches in literature on the dynamic environment problems dealt with.     

Modeling of a greenhouse prototype using PSO and differential evolution algorithms based on a real-time LabView™ application

In general, to obtain an adequate mathematical model of a greenhouse is a difficult task due to the complexity of the involved equations that describe the dynamics of the system, and the required high number of physical parameters, which are complicated or even impossible to measure. In these situations, estimation methods are commonly used to obtain a suitable approximation for those parameters. This paper presents the application and comparison of a collection of methods based on Particle Swarm Optimization (PSO) and Differential Evolution (DE), using them as the tools to identify the parameters that complete a proposed mathematical model for a greenhouse. These parameters are sought aiming to approximate the dynamic behavior of a greenhouse physical prototype building in CINVESTAV Campus Guadalajara, by using the heuristic algorithms in order to minimize a proposed error function, which considers as arguments estimations and measurements of the two more representative dynamics of the climate conditions inside a greenhouse: namely, the air temperature and relative humidity. Different forms of PSO and DE algorithms are considered and applied in order to select the one that achieves the set of parameters with the lowest evaluation error. The comparison of the selected algorithms is carried out in an offline optimization schedule using real data recorded through the LabView™ SignalExpress application, and a real-time implementation in a LabView™ code, implemented to optimize the model in a sample to sample execution. The proposed model, with its corresponding computed parameters, is validated comparing its results against the real dynamic behavior of the temperature and relative humidity, that are measured directly from the greenhouse prototype, showing a good agreement between real and estimated values. Several tests were executed in order to find PSO and DE best calibration conditions. Experimental results allow us to propose an efficient way to deal with numerical optimization problems of high complexity, applying a two stages scheme based on a first offline pre-identification, where the obtained results are used as initial condition for an online, real-time refinement process.     

An early-stage statement-level metric for energy characterization of embedded processors

This work presents an early stage statement-level metric for energy characterization of embedded processors. Definition and the framework for metric evaluation are provided. In particular, such a metric is based on an existing assembly-level analysis and some profiling activities performed on a given C benchmark, and it is related to the average energy consumption of a generic C statement, for a given target processor. Its evaluation is performed with a one-time effort and, once available, it can be used to rapidly estimate the energy consumption of a given C function for all the considered processors. Two reference embedded processors are then considered in order to show an example of usage of the proposed metric and framework.     

Online eigenvector transformation reflecting concept drift for improving network intrusion detection

Currently, large data streams are constantly being generated in diverse environments, and continuous storage of the data and periodic batch-type principal component analysis (PCA) are becoming increasingly difficult. Various online PCA algorithms have been proposed to solve this problem. In this study, we propose an online PCA methodology based on online eigenvector transformation with the moving average of the data stream that can reflect concept drift. We compared the network intrusion detection performance based on online transformation of eigenvectors with that of offline methods by applying three machine learning algorithms. Both online and offline methods demonstrated excellent performance in terms of precision. However, in terms of the recall ratio, the performance of the proposed methodology with integrated online eigenvector transformation was better; thus, the F1-measure also indicated better performance. The visualization of the principal component score shows the effectiveness of our method.     

Adaptive backstepping control for an engine cooling system with guaranteed parameter convergence under mismatched parameter uncertainties

This paper proposes a novel adaptive backstepping control for a special class of nonlinear systems with both matched and mismatched unknown parameters. The parameter update laws resemble a nonlinear reduced-order disturbance observer. Thus, the convergence of the estimated parameter values to the true ones is guaranteed. In each recursive design step, only single parameter update law is required in comparison to the existing standard adaptive backstepping techniques based on overparametrization and tuning functions. To make a fair comparison with the overparametrization and tuning function methods, a second-order nonlinear engine cooling system is taken as a benchmark problem. This system is subject to both matched and mismatched state-dependent lumped disturbances. Moreover, the proposed model-based controllers are compared with a classical PI control by using performance metrics, i.e., root-mean-square error and control effort. The comparative analysis based on these performance metrics, simulations as well as experiments highlights the effectiveness of the proposed novel adaptive backstepping control in terms of asymptotic tracking, global stability and guaranteed parameter convergence.     

An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness

In this communication, we strive to apply a novel simulated annealing to consider scheduling hybrid flowshop problems to minimize both total completion time and total tardiness. To narrow the gap between the theory and the practice of the hybrid flowshop scheduling, we integrate two realistic and practical assumptions which are sequence-dependent setup and transportation times into our problem. We apply a metaheuristic based on simulated annealing (SA) which strikes a compromise between intensification and diversification mechanisms to augment the competitive performance of our proposed SA. A comprehensive calibration of different parameters and operators are done. We employ Taguchi method to select the optimum parameters with the least possible number of experiments. For the purpose of performance evaluation of our proposed algorithm, we generate a benchmark against which the adaptations of high performing algorithms in the literature are brought into comparison. Moreover, we investigate the impacts of increase of number of jobs on the performance of our algorithm. The efficiency and effectiveness of our hybrid simulated annealing are inferred from all the computational results obtained in various situations.     

A new hybrid approach for dynamic continuous optimization problems

A new hybrid approach for dynamic optimization problems with continuous search spaces is presented. The proposed approach hybridizes efficient features of the particle swarm optimization in tracking dynamic changes with a new evolutionary procedure. In the proposed dynamic hybrid PSO (DHPSO) algorithm, the swarm size is varied in a self-regulatory manner. Inspired from the microbial life, the particles can reproduce infants and the old ones die. The infants are especially reproduced by high potential particles and located near the local optimum points, using the quadratic interpolation method. The algorithm is adapted to perform in continuous search spaces, utilizing continuous movement of the particles and using Euclidian norm to define the neighborhood in the reproduction procedure. The performance of the new proposed approach is tested against various benchmark problems and compared with those of some other heuristic optimization algorithms. In this regard, different types of dynamic environments including periodic, linear and random changes are taken with different performance metrics such as real-time error, offline performance and offline error. The results indicate a desirable better efficiency of the new algorithm over the existing ones.     

On measuring the accuracy of SLAM algorithms

In this paper, we address the problem of creating an objective benchmark for evaluating SLAM approaches. We propose a framework for analyzing the results of a SLAM approach based on a metric for measuring the error of the corrected trajectory. This metric uses only relative relations between poses and does not rely on a global reference frame. This overcomes serious shortcomings of approaches using a global reference frame to compute the error. Our method furthermore allows us to compare SLAM approaches that use different estimation techniques or different sensor modalities since all computations are made based on the corrected trajectory of the robot. We provide sets of relative relations needed to compute our metric for an extensive set of datasets frequently used in the robotics community. The relations have been obtained by manually matching laser-range observations to avoid the errors caused by matching algorithms. Our benchmark framework allows the user to easily analyze and objectively compare different SLAM approaches.     

Signature Detection and Matching for Document Image Retrieval

As one of the most pervasive methods of individual identification and document authentication, signatures present convincing evidence and provide an important form of indexing for effective document image processing and retrieval in a broad range of applications. However, detection and segmentation of free-form objects such as signatures from clustered background is currently an open document analysis problem. In this paper, we focus on two fundamental problems in signature-based document image retrieval. First, we propose a novel multiscale approach to jointly detecting and segmenting signatures from document images. Rather than focusing on local features that typically have large variations, our approach captures the structural saliency using a signature production model and computes the dynamic curvature of 2D contour fragments over multiple scales. This detection framework is general and computationally tractable. Second, we treat the problem of signature retrieval in the unconstrained setting of translation, scale, and rotation invariant nonrigid shape matching. We propose two novel measures of shape dissimilarity based on anisotropic scaling and registration residual error and present a supervised learning framework for combining complementary shape information from different dissimilarity metrics using LDA. We quantitatively study state-of-the-art shape representations, shape matching algorithms, measures of dissimilarity, and the use of multiple instances as query in document image retrieval. We further demonstrate our matching techniques in offline signature verification. Extensive experiments using large real-world collections of English and Arabic machine-printed and handwritten documents demonstrate the excellent performance of our approaches.     

面向层次类型变量的相异度量及其聚类分析

本文在分析传统类型变量相异度量的基础上,定义了“层次类型”的概念,提出了层次类型变量的相异度量计算方法。引入层次类型变量,并结合传统类型变量,设计了具有包括层次类型在内的混合数据类型描述的对象之间的相异度量方法,并基于此实现了此类对象的聚类分析。     

Ensemble of niching algorithms

Although niching algorithms have been investigated for almost four decades as effective procedures to obtain several good and diverse solutions of an optimization problem, no effort has been reported on combining different niching algorithms to form an effective ensemble of niching algorithms. In this paper, we propose an ensemble of niching algorithms (ENA) and illustrate the concept by an instantiation which is realized using four different parallel populations. The offspring of each population is considered by all parallel populations. The instantiation is tested on a set of 16 real and binary problems and compared against the single niching methods with respect to searching ability and computation time. Results confirm that ENA method is as good as or better than the best single method in it on every test problem. Moreover, comparison with other state-of-the-art niching algorithms demonstrates the competitiveness of our proposed ENA.     

A two-stage heuristic method for vehicle routing problem with split deliveries and pickups

The vehicle routing problem （VRP） is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups （VRPSPDP） is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.     

Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems

The offline 2D bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem in which objects with various width and length sizes are packed into minimized number of 2D bins. Various versions of this well-known industrial engineering problem can be faced frequently. Several heuristics have been proposed for the solution of 2DBPP but it has not been possible to find the exact solutions for large problem instances. Next fit, first fit, best fit, unified tabu search, genetic and memetic algorithms are some of the state-of-the-art methods successfully applied to this important problem. In this study, we propose a set of novel hyper-heuristic algorithms that select/combine the state-of-the-art heuristics and local search techniques for minimizing the number of 2D bins. The proposed algorithms introduce new crossover and mutation operators for the selection of the heuristics. Through the results of exhaustive experiments on a set of offline 2DBPP benchmark problem instances, we conclude that the proposed algorithms are robust with their ability to obtain high percentage of the optimal solutions.     

Locally linear metric adaptation with application to semi-supervised clustering and image retrieval

Many computer vision and pattern recognition algorithms are very sensitive to the choice of an appropriate distance metric. Some recent research sought to address a variant of the conventional clustering problem called semi-supervised clustering, which performs clustering in the presence of some background knowledge or supervisory information expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semi-supervised clustering mostly perform global metric learning through a linear transformation. In this paper, we propose a new metric learning method that performs nonlinear transformation globally but linear transformation locally. In particular, we formulate the learning problem as an optimization problem and present three methods for solving it. Through some toy data sets, we show empirically that our locally linear metric adaptation (LLMA) method can handle some difficult cases that cannot be handled satisfactorily by previous methods. We also demonstrate the effectiveness of our method on some UCI data sets. Besides applying LLMA to semi-supervised clustering, we have also used it to improve the performance of content-based image retrieval systems through metric learning. Experimental results based on two real-world image databases show that LLMA significantly outperforms other methods in boosting the image retrieval performance.     

Hybrid teaching–learning-based optimization algorithms for the Quadratic Assignment Problem

Teaching–Learning-Based Optimization (TLBO) is a novel swarm intelligence metaheuristic that is reported as an efficient solution method for many optimization problems. It consists of two phases where all individuals are trained by a teacher in the first phase and interact with classmates to improve their knowledge level in the second phase. In this study, we propose a set of TLBO-based hybrid algorithms to solve the challenging combinatorial optimization problem, Quadratic Assignment. Individuals are trained with recombination operators and later a Robust Tabu Search engine processes them. The performances of sequential and parallel TLBO-based hybrid algorithms are compared with those of state-of-the-art metaheuristics in terms of the best solution and computational effort. It is shown experimentally that the performance of the proposed algorithms are competitive with the best reported algorithms for the solution of the Quadratic Assignment Problem with which many real life problems can be modeled.     

自适应调整峰半径的适应值共享遗传算法

适应值共享遗传算法需要事先给出解空间中峰的数目或峰的半径,这对于某些问题来 说是有困难的.针对这类问题,提出将峰的半径作为决策变量,对其进行编码并放入染色体中参 与演化过程,利用遗传算法的优化能力在对问题进行优化的同时对个体的峰半径进行自适应调 整.用所提出的方法对多个标准测试问题的优化结果表明,采用自适应峰半径调整方法的适应 值共享遗传算法有很强的多峰搜索能力.