Search

Solution representation is an important aspect of the development of a meta-heuristic. However, most meta-heuristics focus on the algorithm aspect rather than the solution representation. As the scale of the optimization problem under study rises, the solution representation becomes ever more crucial because the computational performance tends to deteriorate for three reasons: (1) increased landscape complexity, (2) exponential growth of search space, and (3) costly function evaluation. In this study, data compression of solution representation is explored to improve the performance of meta-heuristics in terms of compression efficiency and solution quality. A proposed new data compression scheme – variable-length solution representation compression for meta-heuristics – is developed and tested against benchmarked problem instances from the quadratic assignment problem library (QAPLIB) and additional large problem instances. The analyzed results indicate that the compressed solution representation scheme under a meta-heuristic framework performs well against the QAPLIB and large problem instances with less space complexity and computation time.

This paper concerns the design of optimized single-finger keyboard layouts on smartphones. In the literature, the optimization problem associated with assigning characters to keys on a single-finger keyboard is denoted as single-finger keyboard layout problem (SK-QAP), which can be seen as a variant of the quadratic assignment problem (QAP), a classical combinatorial optimization problem. To solve it, we propose a simple yet effective local search-based metaheuristic which is composed of three neighborhood structures. Two of them were previously applied to solve the SK-QAP, whereas the third one consists of an adaptation of a QAP neighborhood and it was introduced in this work. In addition, two perturbation mechanisms were developed as diversification procedures and together with the latter neighborhood structure, they revealed to be highly beneficial for improving the performance of the algorithm. Computational experiments were carried out on benchmark instances for English, French, Italian and Spanish. The results obtained were extremely competitive both in terms of solution quality and CPU time, such that all best known solutions were found in a matter of seconds. Moreover, we developed and solved benchmark instances for Portuguese, which currently has more than 230 million speakers, as a first or second language, and also uses the Latin alphabet. We have also proposed and solved bilingual instances, combining English, one of the top spoken languages in the world, with each of the remaining four ones. In addition, we quantify the potential practical benefits of adopting alternative and smartphone-oriented optimized single-finger keyboards, when compared to well-known layouts, namely QWERTY and AZERTY, for the five languages and bilingual variants considered. Finally, we show the efficiency of the proposed algorithm when generating layouts based on other existing arrangements, namely Metropolis and FITALY.

A differential improvement modification to Hybrid Genetic Algorithms is proposed. The general idea is to perform more extensive improvement algorithms on higher quality solutions. Our proposed Differential Improvement (DI) approach is of rather general character. It can be implemented in many different ways. The paradigm remains invariant and can be easily applied to a wider class of optimization problems. Moreover, the DI framework can also be used within other Hybrid metaheuristics like Hybrid Scatter Search algorithms, Particle Swarm Optimization, or Bee Colony Optimization techniques. Extensive experiments show that the new approach enables to improve significantly the performance of Hybrid Genetic Algorithms without adding extra computer time. Additional experiments investigated the trade-off between the number of generations and the number of iterations of the improvement algorithm. These experiments yielded six new best known solutions to benchmark quadratic assignment problems. Many other variants of the proposed algorithm are suggested for future research.

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies - studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances - provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems - which are important abstractions of many real-world problems - we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.

The problem of designing new keyboard layouts able to improve the typing speed of an average message has been widely considered in the literature of the Ergonomics domain. Empirical tests with users and simple optimization criteria have been used to propose new solutions. On the contrary, very few papers in Operations Research have addressed this optimization problem. In this paper we firstly resume the most relevant problems in keyboard design, enlightening the related Ergonomics aspects. Then we concentrate on keyboards that must be used with a single finger or stylus, like that of portable data assistant, smartphones and other small devices. We show that the underlying optimization problem is a generalization of the well-known quadratic assignment problem (QAP). We recall some of the most effective metaheuristic algorithms for QAP and we propose some non-trivial extensions to the keyboard design problem. We compare the new algorithms through computational experiments with instances obtained from word lists of the English, French, Italian and Spanish languages. We provide on the web benchmark instances for each language and the best solutions we obtained.

Cross-entropy has been recently proposed as a heuristic method for solving combinatorial optimization problems. We briefly review this methodology and then suggest a hybrid version with the goal of improving its performance. In the context of the well-known max-cut problem, we compare an implementation of the original cross-entropy method with our proposed version. The suggested changes are not particular to the max-cut problem and could be considered for future applications to other combinatorial optimization problems.

The Quadratic Assignment Problem (QAP) is one of the classical combinatorial optimization problems and is known for its diverse applications. In this paper, we suggest a genetic algorithm for the QAP and report its computational behavior. The genetic algorithm incorporates many greedy principles in its design and, hence, we refer to it as a greedy genetic algorithm. The ideas we incorporate in the greedy genetic algorithm include (i) generating the initial population using a randomized construction heuristic; (ii) new crossover schemes; (iii) a special purpose immigration scheme that promotes diversity; (iv) periodic local optimization of a subset of the population; (v) tournamenting among different populations; and (vi) an overall design that attempts to strike a balance between diversity and a bias towards fitter individuals. We test our algorithm on all the benchmark instances of QAPLIB, a well-known library of QAP instances. Out of the 132 total instances in QAPLIB of varied sizes, the greedy genetic algorithm obtained the best known solution for 103 instances, and for the remaining instances (except one) found solutions within 1% of the best known solutions. Scope and purpose Genetic Algorithms (GAs) are one of the most popular heuristic algorithms to solve optimization problems and is an extremely useful tool in an OR toolkit. For solving combinatorial optimization problems, GAs in their elementary forms are not competitive with other heuristic algorithms such as simulated annealing and tabu serach. In this paper, we have investigated the use of several possible enhancements to GAs and illustrated them using the Quadratic Assignment Problem (QAP), one of the hardest nut in the field of combinatorial optimization. Most of our enhancements use some greedy criteria to improve the quality of individuals in the population. We found that the overall performance of the GA for the QAP improves by using greedy methods but not their overuse. Overuse of greedy methods adversely affects the diversity in the population. By striking a right balance between the greedy methods that improve the quality of the solution and the methods that promote diversity, we can obtain fairly effective heuristic algorithms for solving combinatorial optimization problems.

We have previously developed an adaptation of the simulated annealing for multi-objective combinatorial optimization (MOCO) problems to construct an approximation of the efficient set of such problem. In order to deal with large-scale problems, we transform this approach to propose an interactive procedure. The method is tested on the multi-objective knapsack problem and the multi-objective assignment problem. Scope and purpose Meta-heuristics methods are intensively used with success to solve optimization problems and especially combinatorial problems (Pirlot. EJOR 1996;92:493–511). In the case of a single objective problem, such methods compute an approximation to the unique optimal solution. Recently, some meta-heuristics have been adapted to treat multi-objective problems. These methods construct an approximation of the set of all efficient solutions. For large-scale multi-objective combinatorial problems, the number of efficient solutions may become very large. In order to help a decision maker to make a choice between these solutions, an interactive procedure is developed in this paper.