Viral systems: A new bio-inspired optimisation approach

The paper presents a new approach to deal with combinatorial problems. It makes use of a biological analogy inspired by the performance of viruses. The replication mechanism, as well as the hosts’ infection processes is used to generate a metaheuristic that allows the obtention of valuable results. The viral system (VS) theoretical context is described and it is applied to a library of medium-to-large-sized cases of the Steiner problem for which the optimal solution is known. The method is compared with the metaheuristics that have provided the best results for the Steiner problem. The VS provides better solutions than genetic algorithms and certain tabu search approaches. For the most sophisticated tabu search approaches (the best metaheuristic approximations to the Steiner problem solution) VS provides solutions of similar quality.     

Evaluation of different initial solution algorithms to be used in the heuristics optimization to solve the energy resource scheduling in smart grids

Over the last years, an increasing number of distributed resources have been connected to the power system due to the ambitious environmental targets, which resulted into a more complex operation of the power system. In the future, an even larger number of resources is expected to be coupled which will turn the day-ahead optimal resource scheduling problem into an even more difficult optimization problem. Under these circumstances, metaheuristics can be used to address this optimization problem. An adequate algorithm for generating a good initial solution can improve the metaheuristic’s performance of finding a final solution near to the optimal than using a random initial solution. This paper proposes two initial solution algorithms to be used by a metaheuristic technique (simulated annealing). These algorithms are tested and evaluated with other published algorithms that obtain initial solution. The proposed algorithms have been developed as modules to be more flexible their use by other metaheuristics than just simulated annealing. The simulated annealing with different initial solution algorithms has been tested in a 37-bus distribution network with distributed resources, especially electric vehicles. The proposed algorithms proved to present results very close to the optimal with a small difference between 0.1%. A deterministic technique is used as comparison and it took around 26 h to obtain the optimal one. On the other hand, the simulated annealing was able of obtaining results around 1 min.     

An improvement on the Migrating Birds Optimization with a problem-specific neighboring function for the multi-objective task allocation problem

Allocating tasks to processors is a well-known NP-Hard problem in distributed computing systems. Due to the lack of practicable exact solutions, it has been attracted by the researchers working on heuristic-based suboptimal search algorithms. With the recent inclusion of multiple objectives such as minimizing the cost, maximizing the throughput and maximizing the reliability, the problem gets even more complex and an efficient approximate method becomes more valuable. In this work, I propose a new solution for the multi-objective task allocation problem. My solution consists in designing a problem-specific neighboring function for an existing metaheuristic algorithm that is proven to be successful in quadratic assignment problems. The neighboring function, namely greedy reassignment with maximum release (GR-MR), provides a dynamic mechanism to switch the preference of the search between the exploration and exploitation. The experiments validate both that the quality of the solutions are close to the optimal and the proposed method performs significantly better comparing to three other metaheuristic algorithms. Neighboring functions being the common reusable components of metaheuristic algorithms, GR-MR can also be utilized by other metaheuristic-based solutions in the future.     

A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time

A variety of metaheuristics have been developed to solve the permutation flow shop problem minimizing total flow time. Iterated local search (ILS) is a simple but powerful metaheuristic used to solve this problem. Fundamentally, ILS is a procedure that needs to be restarted from another solution when it is trapped in a local optimum. A new solution is often generated by only slightly perturbing the best known solution, narrowing the search space and leading to a stagnant state. In this paper, a strategy is proposed to allow the restart solution to be generated from a group of solutions drawn from local optima. This allows an extension of the search space, while maintaining the quality of the restart solution. A multi-restart ILS (MRSILS) is proposed, with the performance evaluated on a set of benchmark instances and compared with six state of the art metaheuristics. The results show that the easily implementable MRSILS is significantly better than five of the other metaheuristics and comparable to or slightly better than the remaining one.     

Self-adapting control parameters in particle swarm optimization

Particle Swarm Optimization (PSO) is a powerful nature-inspired metaheuristic optimization method. Compared to other methods, PSO can determine the optimal solution in fewer evaluations and generally performs more efficiently and effectively. However, researches show that the PSO method suffers from premature convergence and a dependence on the initial control settings. Due to these shortcomings, the application of PSO may lead to failure in obtaining the global optimal solution. In this work, modifications were performed on the original PSO algorithm to adapt the control parameters to the circumstances of the particles at a specific moment. The proposed method is known as the Unique Adaptive Particle Swarm Optimization (UAPSO). In the developed approach, constraints were handled by forcing the particles to learn from their feasible solutions only. Therefore, the constraint handling technique worked in accord with the adapting scheme to ensure that the particles were adapting to the environment by directing itself to the feasible regions. The performance of UAPSO was verified by a comparative study involving eight benchmark constrained optimization problems and a real-world design problem. The numerical results showed the superiority of UAPSO compared to the selected state-of-the-art metaheuristic methods and PSO variants, its ability in avoiding premature convergence and its consistency and efficiency.     

Inverse lighting design for interior buildings integrating natural and artificial sources

In this paper we propose a new method for solving inverse lighting design problems that can include diverse sources such as diffuse roof skylights or artificial light sources. Given a user specification of illumination requirements, our approach provides optimal light source positions as well as optimal shapes for skylight installations in interior architectural models. The well known huge computational effort that involves searching for an optimal solution is tackled by combining two concepts: exploiting the scene coherence to compute global illumination and using a metaheuristic technique for optimization.Results and analysis show that our method provides both fast and accurate results, making it suitable for lighting design in indoor environments while supporting interactive visualization of global illumination.     

A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem

In this paper, we propose a new metaheuristic to solve the Risk constrained Cash-in-Transit Vehicle Routing Problem (Rctvrp). The Rctvrp is a variant of the well-known capacitated vehicle routing problem and models the problem of routing vehicles in the cash-in-transit sector. In the Rctvrp, the risk associated with a robbery represents a critical aspect that is treated as a limiting factor subject to a maximum risk threshold.A new metaheuristic, called aco-lns is developed. It combines the ant colony heuristic for the travelling salesman problem and a variable neighbourhood descent within an large neighbourhood search framework.A new library of Rctvrp instances with known optimal solutions is proposed. The aco-lns is extensively tested on small, medium and large benchmark instances and compared with all existing solution approaches for the Rctvrp.     

A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading

In this paper, we solve the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading. LIFO loading minimizes handling while unloading items from the vehicle: the items are loaded according to a linear stack structure, and an item can only be delivered if it is the one on top of the stack. Three exact branch-price-and-cut algorithms are available for this problem. These can solve instances with up to 75 requests within one hour. We propose a population-based metaheuristic capable of handling larger instances much faster. First, a set of initial solutions is generated with a greedy randomized adaptive search procedure. For each of these solutions, local search is applied in order to first decrease the total number of vehicles and then the total traveled distance. Two different strategies are used to create offspring. The first selects vehicle routes from the solution pool. The second selects two parents to create an offspring with a crossover operator. For both strategies, local search is then performed on the child solution. Finally, the offspring is added to the population and the best survivors are kept. The population is managed so as to maintain good quality solutions with respect to total cost and population diversity. Computational results on medium to large instances confirm the effectiveness of the proposed metaheuristic.     

An electromagnetism metaheuristic for solving the Maximum Betweenness Problem

In this paper we present an electromagnetism (EM) metaheuristic for solving NP hard Maximum Betweenness Problem (MBP). A new encoding scheme with appropriate objective functions is implemented. Specific representation of the individuals enables the EM operators to explore the searching space in a way that achieves high quality solutions. An effective 1-swap based local search procedure improved by the specific caching technique is performed on each EM point. The algorithm is tested both on real and artificial instances from the literature. Experimental results show that the proposed EM approach achieves all previously known optimal solutions, except one, and achieves the best-known solutions or outperforms other approaches on all large-scale instances, except two. Provided statistical analysis indicates that the EM approach is significantly better than other approaches.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

Clustering search algorithm for the capacitated centered clustering problem

The capacitated centered clustering problem (CCCP) consists in partitioning a set of n points into p disjoint clusters with a known capacity. Each cluster is specified by a centroid. The objective is to minimize the total dissimilarity within each cluster, such that a given capacity limit of the cluster is not exceeded. This paper presents a solution procedure for the CCCP, using the hybrid metaheuristic clustering search (CS), whose main idea is to identify promising areas of the search space by generating solutions through a metaheuristic and clustering them into groups that are then further explored with local search heuristics. Computational results in test problems of the literature show that the CS found a significant number of new best-known solutions in reasonable computational times.     

Metaheuristic approaches to grouping problems in high-throughput cryopreservation operations for fish sperm

High-throughput cryopreservation operations of fish sperm is a technology being developed by researchers today. This paper first formulates a grouping problem in high-throughput cryopreservation operations of fish sperm and then develops a heuristic and four metaheuristic algorithms for its solution. The heuristic is modified from one originally proposed for the assembly line balancing problem. The four metaheuristic algorithms include simulated annealing (SA), tabu search (TS), ant colony optimization (ACO), and a hybrid differential evolution (hDE). For each metaheuristic algorithm, four different initialization methods were used. For both SA and TS, five different neighborhood solution generation methods were also studied. Real world data collected from a high-throughput cryopreservation operation was used to test the effectiveness of algorithms with different initialization and neighborhood solution generation methods. For comparison, a base line of grouping by processing order was also established. The results indicate that: (i) all algorithms performed better than the base line; (ii) using the result of the modified heuristic as the initial solution of metaheuristic algorithms lead to a better solution; the amount of improvement varied from algorithm to algorithm; (iii) among the five neighborhood solution generation operators, insertion operator was the best; (iv) among all algorithms tested, the hybrid differential evolution is the best, followed by tabu search in terms of average objective value.     

Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with time windows

A Dynamic Rich Vehicle Routing Problem with Time Windows has been tackled as a real-world application, in which customers requests can be either known at the beginning of the planning horizon or dynamically revealed over the day. Several real constraints, such as heterogeneous fleet of vehicles, multiple and soft time windows and customers priorities, are taken into consideration. Using exact methods is not a suitable solution for this kind of problems, given the fact that the arrival of a new request has to be followed by a quick re-optimization phase to include it into the solution at hand. Therefore, we have proposed a metaheuristic procedure based on Variable Neighborhood Search to solve this particular problem. The computational experiments reported in this work indicate that the proposed method is feasible to solve this real-world problem and competitive with the best results from the literature. Finally, it is worth mentioning that the software developed in this work has been inserted into the fleet management system of a company in Spain.     

Multi-mode renewable resource-constrained allocation in PERT networks

This paper presents a hybrid metaheuristic algorithm (HMA) for Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP) in PERT networks. A PERT-type project, where activities require resources of various types with random duration, is considered. Each activity can be accomplished in one of several execution modes and each execution mode represents an alternative combination of resource requirements of the activity and its duration. The problem is to minimize the regular criterion namely project's makespan by obtaining an optimal schedule and also the amount of different resources assigned to each activity. The resource project scheduling model is strongly NP-hard, therefore a metaheuristic algorithm is suggested namely HMA. In order to validate the performance of new hybrid metaheuristic algorithm, solutions are compared with optimal solutions for small networks. Also the efficiency of the proposed algorithm, for real world problems, in terms of solution quality and CPU time, is compared to one of the well-known metaheuristic algorithms, namely Genetic Algorithm of Hartmann (GAH). The computational results reveal that the proposed method provides appropriate results for small networks and real world problems.     

A metaheuristic approach for selecting a common platform for modular products based on product performance and manufacturing cost

A known strategy to implement Mass Customization is Product Modularization. To take advantage of the benefits of modularity, the selection of a common platform is required. This selection must be done with optimization criteria based on functionality and economics. In this paper we propose metaheuristic procedures to solve the problem of selecting a common platform for a modular product. This selection is based on an aggregate objective function that combines product performance and manufacturing cost. The problem is divided into two hierarchical problems that must be solved sequentially. The mathematical models have a non-linear integer formulation. Because of the computational complexity to solve optimally these models, metaheuristic procedures are proposed to solve each sub-problem. These procedures are based on Scatter Search and Tabu Search. A case study is presented with a small instance that is solved with these procedures and by total enumeration. The results of the metaheuristic procedures coincide with the optimal values found by total enumeration. The run times are reasonable and it is expected a greater benefit for a larger instance with similar results quality.     

Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization

The particle swarm optimization (PSO) is a relatively new generation of combinatorial metaheuristic algorithms which is based on a metaphor of social interaction, namely bird flocking or fish schooling. Although the algorithm has shown some important advances by providing high speed of convergence in specific problems it has also been reported that the algorithm has a tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. The present paper proposes a new variation of PSO model where we propose a new method of introducing nonlinear variation of inertia weight along with a particle's old velocity to improve the speed of convergence as well as fine tune the search in the multidimensional space. The paper also presents a new method of determining and setting a complete set of free parameters for any given problem, saving the user from a tedious trial and error based approach to determine them for each specific problem. The performance of the proposed PSO model, along with the fixed set of free parameters, is amply demonstrated by applying it for several benchmark problems and comparing it with several competing popular PSO and non-PSO combinatorial metaheuristic algorithms.     

A hybrid data mining GRASP with path-relinking

The exploration of hybrid metaheuristics—combination of metaheuristics with concepts and processes from other research areas—has been an important trend in combinatorial optimization research. An instance of this study is the hybrid version of the GRASP metaheuristic that incorporates a data mining process. Traditional GRASP is an iterative metaheuristic which returns the best solution reached over all iterations. In the hybrid GRASP proposal, after executing a significant number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following GRASP iterations in the search through the combinatorial solution space. The hybrid data mining GRASP has been successfully applied for different combinatorial problems: the set packing problem, the maximum diversity problem, the server replication for reliable multicast problem and the p-median problem. In this work, we show that, not only the traditional GRASP, but also GRASP improved with the path-relinking heuristic—a memory-based intensification strategy—could benefit from exploring a data mining procedure. Computational experiments, comparing traditional GRASP with path-relinking and different path-relinking hybrid proposals, showed that employing the combination of path-relinking and data mining made the GRASP find better results in less computational time. Another contribution of this work is the application of the path-relinking hybrid proposal for the 2-path network design problem, which improved the state-of-the-art solutions for this problem.     

A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming

The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQP instances with two and three objectives.     

基于改进自组织临界优化的元启发式灰狼优化算法

针对新型元启发式算法灰狼优化(GWO)算法在寻优过程中易陷入局部最优这一问题,提升该算法获取全局最优解的能力。介绍了该算法的基本原理和建模过程,并在此基础上,结合自组织临界性理论的优点,提出了改进的极值优化(IEO)算法,将IEO融入到GWO模型中,构建基于自组织临界(SOC)优化的改进GWO算法(IEO-GWO)。通过与传统优化算法对于23个基准测试函数在寻优性能上的综合比较,验证了IEO-GWO模型在获取全局最优解性能上的优越性。