Galactic Swarm Optimization: A new global optimization metaheuristic inspired by galactic motion

This paper proposes a new global optimization metaheuristic called Galactic Swarm Optimization (GSO) inspired by the motion of stars, galaxies and superclusters of galaxies under the influence of gravity. GSO employs multiple cycles of exploration and exploitation phases to strike an optimal trade-off between exploration of new solutions and exploitation of existing solutions. In the explorative phase different subpopulations independently explore the search space and in the exploitative phase the best solutions of different subpopulations are considered as a superswarm and moved towards the best solutions found by the superswarm. In this paper subpopulations as well as the superswarm are updated using the PSO algorithm. However, the GSO approach is quite general and any population based optimization algorithm can be used instead of the PSO algorithm. Statistical test results indicate that the GSO algorithm proposed in this paper significantly outperforms 4 state-of-the-art PSO algorithms and 4 multiswarm PSO algorithms on an overwhelming majority of 15 benchmark optimization problems over 50 independent trials and up to 50 dimensions. Extensive simulation results show that the GSO algorithm proposed in this paper converges faster to a significantly more accurate solution on a wide variety of high dimensional and multimodal benchmark optimization problems.     

A fuzzy-neural approach for estimating the monthly output of a semiconductor manufacturing factory

The customer order scheduling problem (COSP) is defined as to determine the sequence of tasks to satisfy the demand of customers who order several types of products produced on a single machine. A setup is required whenever a product type is launched. The objective of the scheduling problem is to minimize the average customer order flow time. Since the customer order scheduling problem is known to be strongly NP-hard, we solve it using four major metaheuristics and compare the performance of these heuristics, namely, simulated annealing, genetic algorithms, tabu search, and ant colony optimization. These are selected to represent various characteristics of metaheuristics: nature-inspired vs. artificially created, population-based vs. local search, etc. A set of problems is generated to compare the solution quality and computational efforts of these heuristics. Results of the experimentation show that tabu search and ant colony perform better for large problems whereas simulated annealing performs best in small-size problems. Some conclusions are also drawn on the interactions between various problem parameters and the performance of the heuristics.     

Multipoint combinatorial optimization method with a search strategy in higher structure solution space

We propose a multipoint combinatorial optimization method that aims to realize efficient search in consideration of intensification and diversification in higher structure solution space by sharing information between search points. We evaluated the performance of the proposed method through numerical experiments using benchmark problems.     

The boolean quadratic programming problem with generalized upper bound constraints

We consider the boolean quadratic programming problem with generalized upper bound constraints (BQP-GUB) which subsumes the well-known quadratic semi-assignment problem. BQP-GUB has applications in engineering, production planning and biology. We present various complexity results on the problem along with different metaheuristic algorithms. Results of extensive experimental analysis are presented demonstrating the efficacy of our proposed algorithms.     

A local search based approach for solving the Travelling Thief Problem: The pros and cons

The Travelling Thief Problem (TTP) is a novel problem that aims to provide a benchmark model of combinatorial optimization problems with multiple interdependent components. The TTP combines two other well known benchmark problems: the Travelling Salesman Problem (TSP) and the Knapsack Problem (KP). The aim of this paper is to study the interdependence between the TTP's components, and how it makes solving each sub-problem independently from the other useless for solving the overall problem. A local search approach is proposed to solve the TTP. Two simple iterative neighborhood algorithms based on our approach are presented, analyzed, and compared to other algorithms. Initialization strategies are empirically investigated. The experimental results confirm that our approach was able to find new better solutions for many TTP instances.     

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.     

Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness

This paper studies the flowshop scheduling problem with a complex bicriteria objective function. A weighted sum of makespan and maximum tardiness subject to a maximum tardiness threshold value is to be optimized. This problem, with interesting potential applications in practice, has been sparsely studied in the literature. We propose global and local dominance relationships for the three-machine problem and a fast and effective genetic algorithm (GA) for the more general m$m$-machine case. The proposed GA incorporates a novel three-phase fitness assignment mechanism specially targeted at dealing with populations in which both feasible as well as infeasible solutions might coexist. Comprehensive computational and statistical experiments show that the proposed GA outperforms the two most effective existing heuristics by a considerable margin in all scenarios. Furthermore, the proposed GA is also faster and able to find more feasible solutions. It should be noted that when the weight assigned to maximum tardiness is zero, then the problem is reduced to minimizing makespan subject to a maximum tardiness threshold value. Heuristics for both problems have been provided in the literature recently but they have not been compared. Another contribution of this paper is to compare these recent heuristics with each other.     

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.     

A new modeling and solution approach for the set-partitioning problem

The set-partitioning problem (SPP) is widely known for both its application potential and its computational challenge. This NP-hard problem is known to pose considerable difficulty for classical solution methods such as those based on LP technologies. In recent years, the unconstrained binary quadratic program has proven to perform well as a unified modeling and solution framework for a variety of IP problems. In this paper we illustrate how this unified framework can be applied to SPP. Computational experience is presented, illustrating the attractiveness of the approach.     

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.