A new metaheuristic for optimization: Optics inspired optimization (OIO)

Due to the law of reflection, a concave reflecting surface/mirror causes the incident light rays to converge and a convex surface/mirror causes the light rays to reflect away so that they all appear to be diverging. These converging and diverging behaviors cause that the curved mirrors show different image types depending on the distance between the object and the mirror. We model such optical phenomena metaphorically into the searching process of numerical optimization by a new algorithm called optics inspired optimization (OIO). OIO treats the surface of the numerical function to be optimized as a reflecting surface in which each peak is assumed to reflect as a convex mirror and each valley to reflect as a concave one. Each individual is assumed to be an artificial object (or light point) that its artificially glittered ray is reflected back by the function surface, given that the surface is convex or concave, and the artificial image is formed (a candidate solution is generated within the search domain) based on the mirror equations adopted from physics of optics. Besides OIO, we introduce different variants of it, called ROIO (Rotation based OIO), and COIO (Convex combination based OIO) algorithms and conduct an extensive computational effort to find out the merit of the new algorithms. Our comparisons on benchmark test functions and a real world engineering design application (i.e., optimization of a centrifuge pump) demonstrate that the new algorithms are efficient and compete better than or similar to most of state of the art optimization algorithms with the advantage of accepting few input parameters.     

Designing a closed-loop supply chain network for citrus fruits crates considering environmental and economic issues

Most cities, notably major and agricultural ones, are faced with environmental and waste problems. Distribution and collection of agricultural crops can be challenging duties as world demand and production are substantially increased. Accordingly, resource depletion, environmental concern, and the importance of the circular economy have convinced this research group to focus on a Closed-Loop Supply Chain (CLSC) network design. In this study, a new mixed linear mathematical model for a CLSC was developed which minimizes the CLSC’s total costs and which tackles and controls air pollution. Contrary to previous works about supply chain network design, we firstly consider citrus fruits’ crates in our model. To solve the model, two leading algorithms, Genetic Algorithm and Simulated Annealing, are employed and a third recently successful method, Keshtel Algorithm, is utilized. Further, two hybridization algorithms stemmed from mentioned ones are applied. Finally, the results are assessed by different criteria and compared, and then the two best algorithms are chosen in this case. Consequently, in order to achieve the most effective result, a real case study of crates was conducted. The results obviously presented applicability and efficiency of the proposed model. Thus, the most suitable network for CLSC of citrus fruits’ crates was designed in which the costs and emissions were reduced.     

Breakout local search for the multi-objective gate allocation problem

The problem of assigning gates to arriving and departing flights is one of the most important problems in airport operations. We take into account the real multi-criteria nature of the problem by optimizing a total of nine gate allocation objectives that are oriented both on convenience for airport/airline services and passenger comfort. As far as we are aware, this is the largest number of objectives jointly optimized in the GAP literature. Given the complexity of the considered problem, we propose a heuristic approach based on the Breakout Local Search (BLS) framework. BLS is a recent variant of the Iterated Local Search (ILS) with a particular focus on the perturbation strategy. Based on some relevant information on search history, it tries to introduce an appropriate degree of diversification by determining adaptively the number and type of moves for the next perturbation phase. Moreover, we use a new memory-based greedy constructive heuristic to generate a starting point for BLS. Benchmark instances used for our experiments and comparisons are based on information provided by Manchester Airport.     

Rule-based meta-heuristics for integrated scheduling of unrelated parallel machines,batches, and heterogeneous delivery trucks

In this article, we deal with an integrated scheduling for unrelated parallel machines, batches, and heterogeneous delivery trucks. In a manufacturing plant, jobs ordered by customers are manufactured by one of several unrelated parallel machines. Then, they are grouped and delivered to the respective customers by heterogeneous trucks with different capacities and travel times. The objective of the problem is to simultaneously determine the machine schedule, batching, and truck-delivery schedule to minimize the make span of the entire process. To solve this problem, we derive a mathematical model to obtain the optimal solution, and we propose rule-based meta-heuristics using single-stage GA framework. Through randomly generated instance examples, the performances of the proposed meta-heuristics are compared.     

Two-sided assembly line balancing problem of type I: Improvements,a simple algorithm and a comprehensive study

Many meta-heuristic methods have been applied to solve the two-sided assembly line balancing problem of type I with the objective of minimizing the number of stations, but some of them are very complex or intricate to be extended. In addition, different decoding schemes and different objectives have been proposed, leading to the different performances of these algorithms and unfair comparison. In this paper, two new decoding schemes with reduced search space are developed to balance the workload within a mated-station and reduce sequence-depended idle time. Then, graded objectives are employed to preserve the minor improvements on the solutions. Finally, a simple iterated greedy algorithm is extended for the two-sided assembly line balancing problem and modified NEH-based heuristic is introduced to obtain a high quality initial solution. And an improved local search with referenced permutation and reduced insert operators is developed to accelerate the search process. Computational results on benchmark problems prove the efficiency of the proposed decoding schemes and the new graded objectives. A comprehensive computational comparison among 14 meta-heuristics is carried out to demonstrate the efficiency of the improved iterated greedy algorithm.     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan

The multistage hybrid flow shop (HFS) scheduling problems are considered in this paper. Hybrid flowshop scheduling problems were proved to be NP-hard. A recently developed cuckoo search (CS) metaheuristic algorithm is presented in this paper to minimize the makespan for the HFS scheduling problems. A constructive heuristic called NEH heuristic is incorporated with the initial solutions to obtain the optimal or near optimal solutions rapidly in the improved cuckoo search (ICS) algorithm. The proposed algorithm is validated with the data from a leading furniture manufacturing company. Computational results show that the ICS algorithm outperforms many other metaheuristics.     

A beginner's guide to tuning methods

Metaheuristic methods have been demonstrated to be efficient tools to solve hard optimization problems. Most metaheuristics define a set of parameters that must be tuned. A good setup of that parameter values can lead to take advantage of the metaheuristic capabilities to solve the problem at hand. Tuning strategies are step by step methods based on multiple runs of the metaheuristic algorithm. In this study we compare four automated tuning methods: F-Race, Revac, ParamILS and SPO. We evaluate the performance of each method using a standard genetic algorithm for continuous function optimization. We discuss about the requirements of each method, the resources used and quality of solutions found in different scenarios. Finally we establish some guidelines that can help to choose the more appropriate tuning procedure.     

Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem

This paper presents the symbiotic organisms search (SOS) heuristic for solving the capacitated vehicle routing problem (CVRP), which is a well-known discrete optimization problem. The objective of CVRP is to decide the routes for a set of vehicles to serve a set of demand points while minimizing the total routing cost. SOS is a simple and powerful metaheuristic that simulates the symbiotic interaction strategies adopted by an organism for surviving in an ecosystem. As SOS is originally developed for solving continuous optimization problems, we therefore apply two solution representations, SR-1 and SR-2, to transform SOS into an applicable solution approach for CVRP and then apply a local search strategy to improve the solution quality of SOS. The original SOS uses three interaction strategies, mutualism, commensalism, and parasitism, to improve a candidate solution. In this improved version, we propose two new interaction strategies, namely competition and amensalism. We develop six versions of SOS for solving CVRP. The first version, SOS_Canonical, utilizes a commonly used continuous to discrete solution representation transformation procedure. The second version is an improvement of canonical SOS with a local search strategy, denoted as SOS_Basic. The third and fourth versions use SR-1 and SR-2 with a local search strategy, denoted as SOS_SR-1 and SOS_SR-2. The fifth and sixth versions, denoted as ISOS_SR-1 and ISOS_SR-2, improve the implementation of SOS_SR-1 and SOS_SR-2 by adding the newly proposed competition and amensalism interaction strategies. The performances of SOS_Canonical, SOS_Basic, SOS_SR-1, and SOS_SR-2 are evaluated on two sets of benchmark problems. First, the results of the four versions of SOS are compared, showing that the preferable result was obtained from SOS_SR-1 and SOS_SR-2. The performances of SOS_SR-1, SOS_SR-2, ISOS_SR-1, and ISOS_SR-2 are then compared, presenting that ISOS_SR-1 and ISOS_SR-2 offer a better performance. Next, the ISOS_SR-1 and ISOS_SR-2 results are compared to the best-known solutions. The results show that ISOS_SR-1 and ISOS_SR-2 produce good VRP solutions under a reasonable computational time, indicating that each of them is a good alternative algorithm for solving the capacitated vehicle routing problem.     

Composing fifth species counterpoint music with a variable neighborhood search algorithm

In this paper, a variable neighborhood search (VNS) algorithm is developed and analyzed that can generate fifth species counterpoint fragments. The existing species counterpoint rules are quantified and form the basis of the objective function used by the algorithm. The VNS developed in this research is a local search metaheuristic that starts from a randomly generated fragment and gradually improves this solution by changing one or two notes at a time. An in-depth statistical analysis reveals the significance as well as the optimal settings of the parameters of the VNS. The algorithm has been implemented in a user-friendly software environment called Optimuse. Optimuse allows a user to input basic characteristics such as length, key and mode. Based on this input, a fifth species counterpoint fragment is generated by the system that can be edited and played back immediately.