Search

In this research, we present a Binary Cat Swarm Optimization for solving the Manufacturing Cell Design Problem (MCDP). This problem divides an industrial production plant into a certain number of cells. Each cell contains machines with similar types of processes or part families. The goal is to identify a cell organization in such a way that the transportation of the different parts between cells is minimized. The organization of these cells is performed through Cat Swarm Optimization, which is a recent swarm metaheuristic technique based on the behavior of cats. In that technique, cats have two modes of behavior: seeking mode and tracing mode, selected from a mixture ratio. For experimental purposes, a version of the Autonomous Search algorithm was developed with dynamic mixture ratios. The experimental results for both normal Binary Cat Swarm Optimization (BCSO) and Autonomous Search BCSO reach all global optimums, both for a set of 90 instances with known optima, and for a set of 35 new instances with 13 known optima.

The Sudoku problem is a well-known logic-based puzzle of combinatorial number-placement. It consists in filling a n(2) × n(2) grid, composed of n columns, n rows, and n subgrids, each one containing distinct integers from 1 to n(2). Such a puzzle belongs to the NP-complete collection of problems, to which there exist diverse exact and approximate methods able to solve it. In this paper, we propose a new hybrid algorithm that smartly combines a classic tabu search procedure with the alldifferent global constraint from the constraint programming world. The alldifferent constraint is known to be efficient for domain filtering in the presence of constraints that must be pairwise different, which are exactly the kind of constraints that Sudokus own. This ability clearly alleviates the work of the tabu search, resulting in a faster and more robust approach for solving Sudokus. We illustrate interesting experimental results where our proposed algorithm outperforms the best results previously reported by hybrids and approximate methods.

The Sudoku is a famous logic-placement game, originally popularized in Japan and today widely employed as pastime and as testbed for search algorithms. The classic Sudoku consists in filling a 9 × 9 grid, divided into nine 3 × 3 regions, so that each column, row, and region contains different digits from 1 to 9. This game is known to be NP-complete, with existing various complete and incomplete search algorithms able to solve different instances of it. In this paper, we present a new cuckoo search algorithm for solving Sudoku puzzles combining prefiltering phases and geometric operations. The geometric operators allow one to correctly move toward promising regions of the combinatorial space, while the prefiltering phases are able to previously delete from domains the values that do not conduct to any feasible solution. This integration leads to a more efficient domain filtering and as a consequence to a faster solving process. We illustrate encouraging experimental results where our approach noticeably competes with the best approximate methods reported in the literature.

Evolutionary algorithms have been widely used to solve large and complex optimisation problems. Cultural algorithms (CAs) are evolutionary algorithms that have been used to solve both single and, to a less extent, multiobjective optimisation problems. In order to solve these optimisation problems, CAs make use of different strategies such as normative knowledge, historical knowledge, circumstantial knowledge, and among others. In this paper we present a comparison among CAs that make use of different evolutionary strategies; the first one implements a historical knowledge, the second one considers a circumstantial knowledge, and the third one implements a normative knowledge. These CAs are applied on a biobjective uncapacitated facility location problem (BOUFLP), the biobjective version of the well-known uncapacitated facility location problem. To the best of our knowledge, only few articles have applied evolutionary multiobjective algorithms on the BOUFLP and none of those has focused on the impact of the evolutionary strategy on the algorithm performance. Our biobjective cultural algorithm, called BOCA, obtains important improvements when compared to other well-known evolutionary biobjective optimisation algorithms such as PAES and NSGA-II. The conflicting objective functions considered in this study are cost minimisation and coverage maximisation. Solutions obtained by each algorithm are compared using a hypervolume S metric.

The set covering problem is a formal model for many practical optimization problems. In the set covering problem the goal is to choose a subset of the columns of minimal cost that covers every row. Here, we present a novel application of the artificial bee colony algorithm to solve the non-unicost set covering problem. The artificial bee colony algorithm is a recent swarm metaheuristic technique based on the intelligent foraging behavior of honey bees. Experimental results show that our artificial bee colony algorithm is competitive in terms of solution quality with other recent metaheuristic approaches for the set covering problem.

Metaheuristics are multi-purpose problem solvers devoted to particularly tackle large instances of complex optimization problems. However, in spite of the relevance of metaheuristics in the optimization world, their proper design and implementation to reach optimal solutions is not a simple task. Metaheuristics require an initial parameter configuration, which is dramatically relevant for the efficient exploration and exploitation of the search space, and therefore to the effective finding of high-quality solutions. In this paper, the authors propose a variation of the water cycle inspired metaheuristic capable of automatically adjusting its parameter by using the autonomous search paradigm. The goal of our proposal is to explore and to exploit promising regions of the search space to rapidly converge to optimal solutions. To validate the proposal, we tested 160 instances of the manufacturing cell design problem, which is a relevant problem for the industry, whose objective is to minimize the number of movements and exchanges of parts between organizational elements called cells. As a result of the experimental analysis, the authors checked that the proposal performs similarly to the default approach, but without being specifically configured for solving the problem. [ABSTRACT FROM AUTHOR]

Constraint programming effectively solves constraint satisfaction and optimization problems by basically building, pruning, and exploring a search tree of potential solutions. In this context, a main component is the enumeration strategy, which is responsible for selecting the order in which variables and values are selected to build a possible solution. This process is known to be quite important; indeed a correct selection can reach a solution without failed explorations. However, it is well known that selecting the right strategy is quite challenging as their performance is notably hard to predict. During the last years, adaptive enumeration appeared as a proper solution to this problem. Adaptive enumeration allows the solving algorithm being able to autonomously modifying its strategies in solving time depending on performance information. In this way, the most suitable order for variables and values is employed along the search. In this paper, we present a new and more lightweight approach for performing adaptive enumeration. We incorporate a powerful classification technique named Top-k in order to adaptively select strategies along the resolution. We report results on a set of well-known benchmarks where the proposed approach noticeably competes with classical and modern adaptive enumeration methods for constraint satisfaction. [ABSTRACT FROM AUTHOR]

We present a hybridization of two different approaches applied to the well-known Capacitated Facility Location Problem (CFLP). The Artificial Bee algorithm (BA) is used to select a promising subset of locations (warehouses) which are solely included in the Mixed Integer Programming (MIP) model. Next, the algorithm solves the subproblem by considering the entire set of customers. The hybrid implementation allows us to bypass certain inherited weaknesses of each algorithm, which means that we are able to find an optimal solution in an acceptable computational time. In this paper we demonstrate that BA can be significantly improved by use of the MIP algorithm. At the same time, our hybrid implementation allows the MIP algorithm to reach the optimal solution in a considerably shorter time than is needed to solve the model using the entire dataset directly within the model. Our hybrid approach outperforms the results obtained by each technique separately. It is able to find the optimal solution in a shorter time than each technique on its own, and the results are highly competitive with the state-of-the-art in large-scale optimization. Furthermore, according to our results, combining the BA with a mathematical programming approach appears to be an interesting research area in combinatorial optimization. [ABSTRACT FROM AUTHOR]

In this paper, we integrate the autonomous search paradigm on a swarm intelligence algorithm in order to incorporate the auto-adjust capability on parameter values during the run. We propose an independent procedure that begins to work when it detects a stagnation in a local optimum, and it can be applied to any population-based algorithms. For that, we employ the autonomous search technique which allows solvers to automatically re-configure its solving parameters for enhancing the process when poor performances are detected. This feature is dramatically crucial when swarm intelligence methods are developed and tested. Finding the best parameter values that generate the best results is known as an optimization problem itself. For that, we evaluate the behavior of the population size to autonomously be adapted and controlled during the solving time according to the requirements of the problem. The proposal is testing on the dolphin echolocation algorithm which is a recent swarm intelligence algorithm based on the dolphin feature to navigate underwater and identify prey. As an optimization problem to solve, we test a machine-part cell formation problem which is a widely used technique for improving production flexibility, efficiency, and cost reduction in the manufacturing industry decomposing a manufacturing plant in a set of clusters called cells. The goal is to design a cell layout in such a way that the need for moving parts from one cell to another is minimized. Using statistical non-parametric tests, we demonstrate that the proposed approach efficiently solves 160 well-known cell manufacturing instances outperforming the classic optimization algorithm as well as other approaches reported in the literature, while keeping excellent robustness levels. [ABSTRACT FROM AUTHOR]

Metaheuristics are smart problem solvers devoted to tackling particularly large optimization problems. During the last 20 years, they have largely been used to solve different problems from the academic as well as from the real-world. However, most of them have originally been designed for operating over real domain variables, being necessary to tailor its internal core, for instance, to be effective in a binary space of solutions. Various works have demonstrated that this internal modification, known as binarization, is not a simple task, since the several existing binarization ways may lead to very different results. This of course forces the user to implement and analyze a large list of binarization schemas for reaching good results. In this paper, we explore two efficient clustering methods, namely KMeans and DBscan to alter a metaheuristic in order to improve it, and thus do not require on the knowledge of an expert user for identifying which binarization strategy works better during the run. Both techniques have widely been applied to solve clustering problems, allowing us to exploit useful information gathered during the search to efficiently control and improve the binarization process. We integrate those techniques to a recent metaheuristic called Crow Search, and we conduct experiments where KMeans and DBscan are contrasted to 32 different binarization methods. The results show that the proposed approaches outperform most of the binarization strategies for a large list of well-known optimization instances. [ABSTRACT FROM AUTHOR]

The Software Project Scheduling Problem is a specific Project Scheduling Problem present in many industrial and academic areas. This problem consists in making the appropriate worker-task assignment in a software project so the cost and duration of the project are minimized. We present the design of a Max–Min Ant System algorithm using the Hyper-Cube framework to solve it. This framework improves the performance of the algorithm. We illustrate experimental results and compare with other techniques demonstrating the feasibility and robustness of the approach, while reaching competitive solutions. [ABSTRACT FROM AUTHOR]

Abstract: Cell formation consists in organizing a plant as a set of cells, each of them containing machines that process similar types or families of parts. The idea is to minimize the part flow among cells in order to reduce costs and increase productivity. The literature presents different approaches devoted to solve this problem, which are mainly based on mathematical programming and on evolutionary computing. Mathematical programming can guarantee a global optimal solution, however at a higher computational cost than an evolutionary algorithm, which can assure a good enough optimum in a fixed amount of time. In this paper, we model and solve this problem by using state-of-the-art constraint programming (CP) techniques and Boolean satisfiability (SAT) technology. We present different experimental results that demonstrate the efficiency of the proposed optimization models. Indeed, CP and SAT implementations are able to reach the global optima in all tested instances and in competitive runtime. [Copyright &y& Elsevier]