A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problem

A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.     

A simple filter-and-fan approach to the facility location problem

The design of effective neighborhood search procedures is a primary issue for the performance of local search and advanced metaheuristic algorithms. Several recent studies have focused on the development of variable depth neighborhoods that generate sequences of interrelated elementary moves to create more complex compound moves. These methods are chiefly conceived to produce an adaptive search as the number of elementary moves in a compound move may vary from one iteration to another depending on the state of the search. The objective is to achieve this goal with modest computational effort. Although ejection chain methods are currently the most advanced methods in this domain, they usually require more complex implementations. The filter-and-fan (F&F) method appears as an alternative to ejection chain methods allowing for the creation of compound moves based on an effective tree search design.     

Clustering Search for the Berth Allocation Problem

This work presents a new approach to the Berth Allocation Problem (BAP) for ships in ports. Due to the increasing demand for ships carrying containers, the BAP can be considered as a major optimization problem in marine terminals. In this paper, the BAP is considered as dynamic and modeled in discrete case and we propose a new alternative to solve it. The proposed alternative is based on applying the Clustering Search (CS) method using the Simulated Annealing (SA) for solutions generation. The CS is an iterative method which divides the search space in clusters and it is composed of a metaheuristic for solutions generation, a grouping process and a local search heuristic. The computational results are compared against recent methods found in the literature.     

Ant colony optimization with partial order reduction for discovering safety property violations in concurrent models

In this article we analyze the combination of ACOhg, a new metaheuristic algorithm, plus partial order reduction applied to the problem of finding safety property violations in concurrent models using a model checking approach. ACOhg is a new kind of ant colony optimization algorithm inspired by the foraging behavior of real ants equipped with internal resorts to search in very large search landscapes. We here apply ACOhg to concurrent models in scenarios located near the edge of the existing knowledge in detecting property violations. The results state that the combination is computationally beneficial for the search and represents a considerable step forward in this field with respect to exact and other heuristic techniques.     

Modified differential evolution algorithm for contrast and brightness enhancement of satellite images

Satellite images normally possess relatively narrow brightness value ranges necessitating the requirement for contrast stretching, preserving the relevant details before further image analysis. Image enhancement algorithms focus on improving the human image perception. More specifically, contrast and brightness enhancement is considered as a key processing step prior to any further image analysis like segmentation, feature extraction, etc. Metaheuristic optimization algorithms are used effectively for the past few decades, for solving such complex image processing problems. In this paper, a modified differential Modified Differential Evolution (MDE) algorithm for contrast and brightness enhancement of satellite images is proposed. The proposed algorithm is developed with exploration phase by differential evolution algorithm and exploitation phase by cuckoo search algorithm. The proposed algorithm is used to maximize a defined fitness function so as to enhance the entropy, standard deviation and edge details of an image by adjusting a set of parameters to remodel a global transformation function subjective to each of the image being processed. The performance of the proposed algorithm is compared with ten recent state-of-the-art enhancement algorithms. Experimental results demonstrate the efficiency and robustness of the proposed algorithm in enhancing satellite images and natural scenes effectively. Objective evaluation of the compared methods was done using several full-reference and no-reference performance metrics. Qualitative and quantitative evaluation results proves that the proposed MDE algorithm outperforms others to a greater extend.     

A systematic mapping study of search-based software engineering for software product lines

ContextSearch-Based Software Engineering (SBSE) is an emerging discipline that focuses on the application of search-based optimization techniques to software engineering problems. Software Product Lines (SPLs) are families of related software systems whose members are distinguished by the set of features each one provides. SPL development practices have proven benefits such as improved software reuse, better customization, and faster time to market. A typical SPL usually involves a large number of systems and features, a fact that makes them attractive for the application of SBSE techniques which are able to tackle problems that involve large search spaces.ObjectiveThe main objective of our work is to identify the quantity and the type of research on the application of SBSE techniques to SPL problems. More concretely, the SBSE techniques that have been used and at what stage of the SPL life cycle, the type of case studies employed and their empirical analysis, and the fora where the research has been published.MethodA systematic mapping study was conducted with five research questions and assessed 77 publications from 2001, when the term SBSE was coined, until 2014.ResultsThe most common application of SBSE techniques found was testing followed by product configuration, with genetic algorithms and multi-objective evolutionary algorithms being the two most commonly used techniques. Our study identified the need to improve the robustness of the empirical evaluation of existing research, a lack of extensive and robust tool support, and multiple avenues worthy of further investigation.ConclusionsOur study attested the great synergy existing between both fields, corroborated the increasing and ongoing interest in research on the subject, and revealed challenging open research questions.     

Water cycle algorithm with evaporation rate for solving constrained and unconstrained optimization problems

This paper presents a modified version of the water cycle algorithm (WCA). The fundamental concepts and ideas which underlie the WCA are inspired based on the observation of water cycle process and how rivers and streams flow to the sea. New concept of evaporation rate for different rivers and streams is defined so called evaporation rate based WCA (ER-WCA), which offers improvement in search. Furthermore, the evaporation condition is also applied for streams that directly flow to sea based on the new approach. The ER-WCA shows a better balance between exploration and exploitation phases compared to the standard WCA. It is shown that the ER-WCA offers high potential in finding all global optima of multimodal and benchmark functions. The WCA and ER-WCA are tested using several multimodal benchmark functions and the obtained optimization results show that in most cases the ER-WCA converges to the global solution faster and offers more accurate results than the WCA and other considered optimizers. Based on the performance of ER-WCA on a number of well-known benchmark functions, the efficiency of the proposed method with respect to the number of function evaluations (computational effort) and accuracy of function value are represented.     

A hybrid artificial bee colony for a nurse rostering problem

The nurse rostering problem (NRP) is a combinatorial optimization problem tackled by assigning a set of shifts to a set of nurses, each has specific skills and work contract, to a predefined rostering period according to a set constraints. The metaheuristics are the most successful methods for tackling this problem. This paper proposes a metaheuristic technique called a hybrid artificial bee colony (HABC) for NRP. In HABC, the process of the employed bee operator is replaced with the hill climbing optimizer (HCO) to empower its exploitation capability and the usage of HCO is controlled by hill climbing rate (HCR) parameter. The performance of the proposed HABC is evaluated using the standard dataset published in the first international nurse rostering competition 2010 (INRC2010). This dataset consists of 69 instances which reflect this problem in many real-world cases that are varied in size and complexity. The experimental results of studying the effect of HCO using different value of HCR show that the HCO has a great impact on the performance of HABC. In addition, a comparative evaluation of HABC is carried out against other eleven methods that worked on INRC2010 dataset. The comparative results show that the proposed algorithm achieved two new best results for two problem instances, 35 best published results out of 69 instances as achieved by other comparative methods, and comparable results in the remaining instances of INRC2010 dataset.     

Solving generalized Nash equilibrium problems through stochastic global optimization

Generalized Nash equilibrium problems address extensions of the well-known standard Nash equilibrium concept, making it possible to model and study more general settings. The main difference lies in that they allow both objective functions and constraints of each player to depend on the strategies of other players. The study of such problems has numerous applications in many fields, including engineering, economics, or management science, for instance. In this work we introduce a solution algorithm based on the Fuzzy Adaptive Simulated Annealing global optimization method (Fuzzy ASA, for short), demonstrating that it is possible to transform the original task into a constrained global optimization problem, which can be solved, in principle, by any effective global optimization algorithm, but in this paper our main tool will be the cited paradigm (Fuzzy ASA). We believe that the main merit of the proposed approach is to offer a simpler alternative for solving this important class of problems, in a less restrictive way in the sense of not demanding very strong conditions on the defining functions. Several case studies are presented for the sake of exemplifying the proposal's efficacy.     

A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem

This paper proposes a hybrid modified global-best harmony search (hmgHS) algorithm for solving the blocking permutation flow shop scheduling problem with the makespan criterion. First of all, the largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Second, an efficient initialization scheme based on the Nawaz-Enscore-Ham (NEH) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. Third, harmony search is employed to evolve harmony vectors in the harmony memory to perform exploration, whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Moreover, a new pitch adjustment rule is developed to well inherit good structures from the global-best harmony vector. Computational simulations and comparisons demonstrated the superiority of the proposed hybrid harmony search algorithm in terms of solution quality.