A honey-bee mating optimization algorithm for educational timetabling problems

In this work, we propose a variant of the honey-bee mating optimization algorithm for solving educational timetabling problems. The honey-bee algorithm is a nature inspired algorithm which simulates the process of real honey-bees mating. The performance of the proposed algorithm is tested over two benchmark problems; exam (Carter’s un-capacitated datasets) and course (Socha datasets) timetabling problems. We chose these two datasets as they have been widely studied in the literature and we would also like to evaluate our algorithm across two different, yet related, domains. Results demonstrate that the performance of the honey-bee mating optimization algorithm is comparable with the results of other approaches in the scientific literature. Indeed, the proposed approach obtains best results compared with other approaches on some instances, indicating that the honey-bee mating optimization algorithm is a promising approach in solving educational timetabling problems.     

An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

A differential evolution algorithm with cooperative coevolutionary selection operation for high-dimensional optimization

Although different kinds of evolutionary algorithms (EAs) have been designed and achieved great success on many optimization problems, they are usually limited to some small-scale problems, e.g. with less than 100 decision variables, which may be quite small comparing to the requirements of real-world applications. Therefore, scaling EAs to large size problems have attracted more and more interest. Conventional EAs mimic the seemingly random natural processes by which species evolve. These evolution processes are slow or inefficient. Now, genetic engineering has enabled man to increase both the yields and quality of some crops fast by modifying some part of their genome precisely. In this paper, inspired by the ideas of the genetic engineering, we designed a local selection operator by decomposing the high-dimensional problem into some subcomponents and assigning a local fitness function to evaluate each subcomponent. Then a new differential evolution (DE) is proposed by inserting the local selection operator into the framework of DE. Numerical experiments were carried out to evaluate the performance of the new algorithm on a large number of benchmark functions. The results show that the new algorithm is effective and efficient for high-dimensional optimization.     

The analysis of evolutionary algorithms on sorting and shortest paths problems

The analysis of evolutionary algorithms is up to now limited to special classes of functions and fitness landscapes. E.g., it is not possible to characterize the set of TSP instances (or another NP-hard combinatorial optimization problem) which are solved by a generic evolutionary algorithm (EA) in an expected time bounded by some given polynomial. As a first step from artificial functions to typical problems from combinatorial optimization, we analyze simple EAs on well-known problems, namely sorting and shortest paths. Although it cannot be expected that EAs outperform the well-known problem specific algorithms on these simple problems, it is interesting to analyze how EAs work on these problems. The following results are obtained:– Sorting is the maximization of sortedness which is measured by one of several well-known measures of presortedness. The different measures of presortedness lead to fitness functions of quite different difficulty for EAs.– Shortest paths problems are hard for all types of EA, if they are considered as single-objective optimization problems, whereas they are easy as multi-objective optimization problems.     

Application of honey-bee mating optimization algorithm on clustering

Cluster analysis is one of attractive data mining technique that use in many fields. One popular class of data clustering algorithms is the center based clustering algorithm. K-means used as a popular clustering method due to its simplicity and high speed in clustering large datasets. However, K-means has two shortcomings: dependency on the initial state and convergence to local optima and global solutions of large problems cannot found with reasonable amount of computation effort. In order to overcome local optima problem lots of studies done in clustering. Over the last decade, modeling the behavior of social insects, such as ants and bees, for the purpose of search and problem solving has been the context of the emerging area of swarm intelligence. Honey-bees are among the most closely studied social insects. Honey-bee mating may also be considered as a typical swarm-based approach to optimization, in which the search algorithm is inspired by the process of marriage in real honey-bee. Honey-bee has been used to model agent-based systems. In this paper, we proposed application of honeybee mating optimization in clustering (HBMK-means). We compared HBMK-means with other heuristics algorithm in clustering, such as GA, SA, TS, and ACO, by implementing them on several well-known datasets. Our finding shows that the proposed algorithm works than the best one.     

On the limitations of classical benchmark functions for evaluating robustness of evolutionary algorithms

Although evolutionary algorithms (EAs) have some operators which let them explore the whole search domain, still they get trapped in local minima when multimodality of the objective function is increased. To improve the performance of EAs, many optimization techniques or operators have been introduced in recent years. However, it seems that these modified versions exploit some special properties of the classical multimodal benchmark functions, some of which have been noted in previous research and solutions to eliminate them have been proposed.In this article, we show that quite symmetric behavior of the available multimodal test functions is another example of these special properties which can be exploited by some EAs such as covariance matrix adaptation evolution strategy (CMA-ES). This method, based on its invariance properties and good optimization results for available unimodal and multimodal benchmark functions, is considered as a robust and efficient method. However, as far as black box optimization problems are considered, no special trend in the behavior of the objective function can be assumed; consequently this symmetry limits the generalization of optimization results from available multimodal benchmark functions to real world problems. To improve the performance of CMA-ES, the Elite search sub-algorithm is introduced and implemented in the basic algorithm. Importance and effect of this modification is illustrated experimentally by dissolving some test problems in the end.     

Empirical analysis of evolutionary algorithms with immigrants schemes for dynamic optimization

In recent years, there has been a growing interest in studying evolutionary algorithms (EAs) for dynamic optimization problems (DOPs). Among approaches developed for EAs to deal with DOPs, immigrants schemes have been proven to be beneficial. Immigrants schemes for EAs on DOPs aim at maintaining the diversity of the population throughout the run via introducing new individuals into the current population. In this paper, we carefully examine the mechanism of generating immigrants, which is the most important issue among immigrants schemes for EAs in dynamic environments. We divide existing immigrants schemes into two types, namely the direct immigrants scheme and the indirect immigrants scheme, according to the way in which immigrants are generated. Then experiments are conducted to understand the difference in the behaviors of different types of immigrants schemes and to compare their performance in dynamic environments. Furthermore, a new immigrants scheme is proposed to combine the merits of two types of immigrants schemes. The experimental results show that the interactions between the two types of schemes reveal positive effect in improving the performance of EAs in dynamic environments.     

A multilevel image thresholding using the honey bee mating optimization

Image thresholding is an important technique for image processing and pattern recognition. Many thresholding techniques have been proposed in the literature. Among them, the maximum entropy thresholding (MET) has been widely applied. In this paper, a new multilevel MET algorithm based on the technology of the honey bee mating optimization (HBMO) is proposed. This proposed method is called the maximum entropy based honey bee mating optimization thresholding (MEHBMOT) method. Three different methods such as the particle swarm optimization (PSO), the hybrid cooperative-comprehensive learning based PSO algorithm (HCOCLPSO) and the Fast Otsu’s method are also implemented for comparison with the results of the proposed method. The experimental results manifest that the proposed MEHBMOT algorithm can search for multiple thresholds which are very close to the optimal ones examined by the exhaustive search method. In comparison with the other three thresholding methods, the segmentation results using the MEHBMOT algorithm is the best and its computation time is relatively low. Furthermore, the convergence of the MEHBMOT algorithm can rapidly achieve and the results validate that the proposed MEHBMOT algorithm is efficient.     

Handling equality constraints in evolutionary optimization

Over the last few decades several methods have been proposed for handling functional constraints while solving optimization problems using evolutionary algorithms (EAs). However, the presence of equality constraints makes the feasible space very small compared to the entire search space. As a consequence, the handling of equality constraints has long been a difficult issue for evolutionary optimization methods. This paper presents a Hybrid Evolutionary Algorithm (HEA) for solving optimization problems with both equality and inequality constraints. In HEA, we propose a new local search technique with special emphasis on equality constraints. The basic concept of the new technique is to reach a point on the equality constraint from the current position of an individual solution, and then explore on the constraint landscape. We believe this new concept will influence the future research direction for constrained optimization using population based algorithms. The proposed algorithm is tested on a set of standard benchmark problems. The results show that the proposed technique works very well on those benchmark problems.     

Finding the shortest path with honey-bee mating optimization algorithm in project management problems with constrained/unconstrained resources

Effective project management requires the development of a realistic plan and a clear communication of the plan from the beginning to the end of the project. The critical path method (CPM) of scheduling is the fundamental tool used to develop and interconnect project plans. Ensuring the integrity and transparency of those schedules is paramount for project success. The complex and discrete nature of the solution domain for such problems causes failing of traditional and gradient-based methods in finding the optimal or even feasible solution in some cases. The difficulties encountered in scheduling construction projects with resource constraints are highlighted by means of a simplified bridge construction problem and a basic masonry construction problem. The honey-bee mating optimization (HBMO) algorithm has been previously adopted to solve mathematical and engineering problems and has proven to be efficient for searching optimal solutions in large-problem domains. This paper presents the HBMO algorithm for scheduling projects with both constrained and unconstrained resources. Results show that the HBMO algorithm is applicable to projects with or without resource constraints. Furthermore, results obtained are promising and compare well with those of well-known heuristic approaches and gradient-based methods.     

Particle swarm optimization with age-group topology for multimodal functions and data clustering

This paper proposes particle swarm optimization with age-group topology (PSOAG), a novel age-based particle swarm optimization (PSO). In this work, we present a new concept of age to measure the search ability of each particle in local area. To keep population diversity during searching, we separate particles to different age-groups by their age and particles in each age-group can only select the ones in younger groups or their own groups as their neighbourhoods. To allow search escape from local optima, the aging particles are regularly replaced by new and randomly generated ones. In addition, we design an age-group based parameter setting method, where particles in different age-groups have different parameters, to accelerate convergence. This algorithm is applied to nonlinear function optimization and data clustering problems for performance evaluation. In comparison against several PSO variants and other EAs, we find that the proposed algorithm provides significantly better performances on both the function optimization problems and the data clustering tasks.     

Genetic algorithm with automatic termination and search space rotation

In the last two decades, numerous evolutionary algorithms (EAs) have been developed for solving optimization problems. However, only a few works have focused on the question of the termination criteria. Indeed, EAs still need termination criteria prespecified by the user. In this paper, we develop a genetic algorithm (GA) with automatic termination and acceleration elements which allow the search to end without resort to predefined conditions. We call this algorithm “Genetic Algorithm with Automatic Termination and Search Space Rotation”, abbreviated as GATR. This algorithm utilizes the so-called “Gene Matrix” (GM) to equip the search process with a self-check in order to judge how much exploration has been performed, while maintaining the population diversity. The algorithm also implements a mutation operator called “mutagenesis” to achieve more efficient and faster exploration and exploitation processes. Moreover, GATR fully exploits the structure of the GM by calling a novel search space decomposition mechanism combined with a search space rotation procedure. As a result, the search operates strictly within two-dimensional subspaces irrespective of the dimension of the original problem. The computational experiments and comparisons with some state-of-the-art EAs demonstrate the effectiveness of the automatic termination criteria and the space decomposition mechanism of GATR.     

Enhancing performance of particle swarm optimization through an algorithmic link with genetic algorithms

Evolutionary Algorithms (EAs) are emerging as competitive and reliable techniques for several optimization tasks. Juxtapositioning their higher-level and implicit correspondence; it is provocative to query if one optimization algorithm can benefit from another by studying underlying similarities and dissimilarities. This paper establishes a clear and fundamental algorithmic linking between particle swarm optimization (PSO) algorithm and genetic algorithms (GAs). Specifically, we select the task of solving unimodal optimization problems, and demonstrate that key algorithmic features of an effective Generalized Generation Gap based Genetic Algorithm can be introduced into the PSO by leveraging this algorithmic linking while significantly enhance the PSO’s performance. However, the goal of this paper is not to solve unimodal problems, neither is to demonstrate that the modified PSO algorithm resembles a GA, but to highlight the concept of algorithmic linking in an attempt towards designing efficient optimization algorithms. We intend to emphasize that the evolutionary and other optimization researchers should direct more efforts in establishing equivalence between different genetic, evolutionary and other nature-inspired or non-traditional algorithms. In addition to achieving performance gains, such an exercise shall deepen the understanding and scope of various operators from different paradigms in Evolutionary Computation (EC) and other optimization methods.     

A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design

Multi-objective particle swarm optimization (MOPSO) is an optimization technique inspired by bird flocking, which has been steadily gaining attention from the research community because of its high convergence speed. On the other hand, in the face of increasing complexity and dimensionality of today’s application coupled with its tendency of premature convergence due to the high convergence speeds, there is a need to improve the efficiency and effectiveness of MOPSO. In this paper a competitive and cooperative co-evolutionary approach is adapted for multi-objective particle swarm optimization algorithm design, which appears to have considerable potential for solving complex optimization problems by explicitly modeling the co-evolution of competing and cooperating species. The competitive and cooperative co-evolution model helps to produce the reasonable problem decompositions by exploiting any correlation, interdependency between components of the problem. The proposed competitive and cooperative co-evolutionary multi-objective particle swarm optimization algorithm (CCPSO) is validated through comparisons with existing state-of-the-art multi-objective algorithms using established benchmarks and metrics. Simulation results demonstrated that CCPSO shows competitive, if not better, performance as compared to the other algorithms.     

Natural laminar flow shape optimization in transonic regime with competitive Nash game strategy

The Natural Laminar Flow (NLF) airfoil/wing design optimization is an efficient method which can reduce significantly turbulence skin friction by delaying transition location at high Reynolds numbers. However, the reduction of the friction drag is competitively balanced with the increase of shock wave induced drag in transonic regime. In this paper, a distributed Nash Evolutionary Algorithms (EAs) is presented and extended to multi-level parallel computing, namely multi-level parallel Nash EAs. The proposed improved methodology is used to solve NLF airfoil shape design optimization problem. It turns out that the optimization method developed in this paper can easily capture a Nash Equilibrium (NE) between transition delaying and wave drag increasing. Results of numerical experiments demonstrate that both wave drag and friction drag performances of a NE are greatly improved. Moreover, performance of the NE is equivalent to that of cooperative Pareto-optimum solutions, but it is more efficient in terms of CPU time. The successful application validates efficiency of algorithms in solving complex aerodynamic optimization problem.     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

On the utility of randomly generated functions for performance evaluation of evolutionary algorithms

Previous researches have disclosed that the excellent performance of some evolutionary algorithms (EAs) highly depends on existence of some properties in the structure of the objective function. Unlike classical benchmark functions, randomly generated multimodal functions do not have any of these properties. Having been improved, a function generator is utilized to generate a number of six benchmarks with random structure. Performance of some EAs is evaluated on these functions and compared to that evaluated on results from classical benchmarks, which are available in literature. The comparison reveals a considerable drop in the performance, even though some of these methods have all possible invariances. This demonstrates that in addition to properties, classical benchmarks have special patterns which may be exploited by EAs. Unlike properties, these patterns are not eliminated under linear transformation of the coordinates or the objective function; hence, limitations should be considered while generalizing performance of EAs on classical benchmarks to practical problems, where these properties or patterns do not necessarily exist.     

Self Balanced Differential Evolution

Differential Evolution (DE) is a well known and simple population based probabilistic approach for global optimization. It has reportedly outperformed a few Evolutionary Algorithms (EAs) and other search heuristics like the Particle Swarm Optimization (PSO) when tested over both benchmark and real world problems. But, DE, like other probabilistic optimization algorithms, sometimes behave prematurely in convergence. Therefore, in order to avoid stagnation while keeping a good convergence speed for DE, two modifications are proposed: one is the introduction of a new control parameter, Cognitive Learning Factor (CLF) and the other is dynamic setting of scale factor. Both modifications are proposed in mutation process of DE. Cognitive learning is a powerful mechanism that adjust the current position of individuals by a means of some specified knowledge. The proposed strategy, named as Self Balanced Differential Evolution (SBDE), balances the exploration and exploitation capability of the DE. To prove efficiency and efficacy of SBDE, it is tested over 30 benchmark optimization problems and compared the results with the basic DE and advanced variants of DE namely, SFLSDE, OBDE and jDE. Further, a real-world optimization problem, namely, Spread Spectrum Radar Polly phase Code Design, is solved to show the wide applicability of the SBDE.     

A chaos-based evolutionary algorithm for general nonlinear programming problems

In this paper we present a chaos-based evolutionary algorithm (EA) for solving nonlinear programming problems named chaotic genetic algorithm (CGA). CGA integrates genetic algorithm (GA) and chaotic local search (CLS) strategy to accelerate the optimum seeking operation and to speed the convergence to the global solution. The integration of global search represented in genetic algorithm and CLS procedures should offer the advantages of both optimization methods while offsetting their disadvantages. By this way, it is intended to enhance the global convergence and to prevent to stick on a local solution. The inherent characteristics of chaos can enhance optimization algorithms by enabling it to escape from local solutions and increase the convergence to reach to the global solution. Twelve chaotic maps have been analyzed in the proposed approach. The simulation results using the set of CEC’2005 show that the application of chaotic mapping may be an effective strategy to improve the performances of EAs.