Instance space analysis for a personnel scheduling problem

Annals of Mathematics and Artificial Intelligence - This paper considers the Rotating Workforce Scheduling Problem, and shows how the strengths and weaknesses of various solution methods can be...     

Relating instance hardness to classification performance in a dataset: a visual approach

Machine Learning - Machine Learning studies often involve a series of computational experiments in which the predictive performance of multiple models are compared across one or more datasets. The...     

A cross-entropy method for optimising robotic automated storage and retrieval systems

In this paper, we consider a robotic automated storage and retrieval system (AS/RS) where a Cartesian robot picks and palletises items onto a mixed pallet for any order. This robotic AS/RS not only retrieves orders in an optimal sequence, but also creates an optimal store ready pallet of any order. Adapting the Travelling Salesman Problem to warehousing, the decision to be made includes finding the optimal sequence of orders, and optimal sequence of items inside each order, that jointly minimise total travel times. In the first phase, as a control problem, we develop an avoidance strategy for the robot (or automatic stacker crane) movement sequence. This approach detects the collision occurrence causing unsafe handling of hazardous items and prevents the occurrence of it by a collision-free robot movement sequence. Due to the complexity of the problem, the second phase is attacked by a Cross-Entropy (CE) method. To evaluate the performance of the CE method, a computational analysis is performed over various test problems. The results obtained from the CE method are compared to those of the optimal solutions obtained using CPLEX. The results indicate high performance of the solution procedure to solve the sequencing problem of robotic AS/RSs.     

Algorithm selection and instance space analysis for curriculum-based course timetabling

Journal of Scheduling - We propose an algorithm selection approach and an instance space analysis for the well-known curriculum-based course timetabling problem (CB-CTT), which is an important...     

Automatic age estimation based on facial aging patterns

While recognition of most facial variations, such as identity, expression and gender, has been extensively studied, automatic age estimation has rarely been explored. In contrast to other facial variations, aging variation presents several unique characteristics which make age estimation a challenging task. This paper proposes an automatic age estimation method named AGES (AGing pattErn Subspace). The basic idea is to model the aging pattern, which is defined as the sequence of a particular individual' s face images sorted in time order, by constructing a representative subspace. The proper aging pattern for a previously unseen face image is determined by the projection in the subspace that can reconstruct the face image with minimum reconstruction error, while the position of the face image in that aging pattern will then indicate its age. In the experiments, AGES and its variants are compared with the limited existing age estimation methods (WAS and AAS) and some well-established classification methods (kNN, BP, C4.5, and SVM). Moreover, a comparison with human perception ability on age is conducted. It is interesting to note that the performance of AGES is not only significantly better than that of all the other algorithms, but also comparable to that of the human observers.     

Instance spaces for machine learning classification

This paper tackles the issue of objective performance evaluation of machine learning classifiers, and the impact of the choice of test instances. Given that statistical properties or features of a dataset affect the difficulty of an instance for particular classification algorithms, we examine the diversity and quality of the UCI repository of test instances used by most machine learning researchers. We show how an instance space can be visualized, with each classification dataset represented as a point in the space. The instance space is constructed to reveal pockets of hard and easy instances, and enables the strengths and weaknesses of individual classifiers to be identified. Finally, we propose a methodology to generate new test instances with the aim of enriching the diversity of the instance space, enabling potentially greater insights than can be afforded by the current UCI repository.     

Method for optimizing coating properties based on an evolutionary algorithm approach

In industry as well as many areas of scientific research, data collected often contain a number of responses of interest for a chosen set of exploratory variables. Optimization of such multivariable multiresponse systems is a challenge well suited to genetic algorithms as global optimization tools. One such example is the optimization of coating surfaces with the required absolute and relative sensitivity for detecting analytes using devices such as sensor arrays. High-throughput synthesis and screening methods can be used to accelerate materials discovery and optimization; however, an important practical consideration for successful optimization of materials for arrays and other applications is the ability to generate adequate information from a minimum number of experiments. Here we present a case study to evaluate the efficiency of a novel evolutionary model-based multiresponse approach (EMMA) that enables the optimization of a coating while minimizing the number of experiments. EMMA plans the experiments and simultaneously models the material properties. We illustrate this novel procedure for materials optimization by testing the algorithm on a sol-gel synthetic route for production and optimization of a well studied amino-methyl-silane coating. The response variables of the coating have been optimized based on application criteria for micro- and macro-array surfaces. Spotting performance has been monitored using a fluorescent dye molecule for demonstration purposes and measured using a laser scanner. Optimization is achieved by exploring less than 2% of the possible experiments, resulting in identification of the most influential compositional variables. Use of EMMA to optimize control factors of a product or process is illustrated, and the proposed approach is shown to be a promising tool for simultaneously optimizing and modeling multivariable multiresponse systems.     

Discovering the suitability of optimisation algorithms by learning from evolved instances

The suitability of an optimisation algorithm selected from within an algorithm portfolio depends upon the features of the particular instance to be solved. Understanding the relative strengths and weaknesses of different algorithms in the portfolio is crucial for effective performance prediction, automated algorithm selection, and to generate knowledge about the ideal conditions for each algorithm to influence better algorithm design. Relying on well-studied benchmark instances, or randomly generated instances, limits our ability to truly challenge each of the algorithms in a portfolio and determine these ideal conditions. Instead we use an evolutionary algorithm to evolve instances that are uniquely easy or hard for each algorithm, thus providing a more direct method for studying the relative strengths and weaknesses of each algorithm. The proposed methodology ensures that the meta-data is sufficient to be able to learn the features of the instances that uniquely characterise the ideal conditions for each algorithm. A case study is presented based on a comprehensive study of the performance of two heuristics on the Travelling Salesman Problem. The results show that prediction of search effort as well as the best performing algorithm for a given instance can be achieved with high accuracy.