Search

The graph coloring problem is an NP-hard problem. Currently, one of the most effective methods to solve this problem is a hybrid evolutionary algorithm. This paper proposes a hybrid evolutionary algorithm NERS_HEAD with a new elite replacement strategy. In NERS_HEAD, a method to detect the local optimal state is proposed so that the evolutionary process can jump out of the local optimal state by introducing diversity on time; a new elite structure and a replacement strategy are designed to increase the diversity of the evolutionary population so that the evolution process can not only converge quickly but also jump out of the local optimal state in time. The comparison experiments with current excellent graph coloring algorithms on 59 DIMACS benchmark instances show that NERS_HEAD can effectively improve the efficiency and success rate of solving graph coloring problems. [ABSTRACT FROM AUTHOR]

A memetic algorithm based on MOEA/D is presented to deal with the uncapacitated multiobjective examination timetabling problem in this paper. The examination timetabling problem is considered as a two-objective optimization problem in this paper, while it is modeled as a single-objective optimization problem generally. The framework of a multiobjective evolutionary algorithm with decomposition (MOEA/D) is first employed to guide the evolutionary process. Two special local search operators are designed to find better individuals. The proposed algorithm is tested on 11 benchmark examination timetabling instances. Experimental results prove that the proposed algorithm can produce a promising set of nondominated solutions for each examination timetabling instance. [ABSTRACT FROM AUTHOR]

This paper presents an evolutionary approach-based solution of multi-objective transportation-p-facility location problem (MOT-p-FLP) that minimizes overall transportation time, cost of transportation, and carbon emission (CE) from available sites to facility sites by seeking transported product quantities and the facility locations in the Euclidean plane. Genetic algorithm (GA), non-dominated sorting genetic algorithm (NSGA-II and NSGA-III), and modified Self-Adaptive Multi-Population Elitism Jaya Algorithm (SAMPE JA) are utilized to solve the problem. We compared obtained compromise solutions of the problem by evolutionary algorithms with population size, the maximum number of generations, crossover probability, mutation probability, and computational time. Sensitivity analysis for supply, demand, and carbon cap parameters is incorporated in the model's solution, which helps the decision maker make the appropriate decision. These evolutionary algorithms (NSGA-II and NSGA-III) give Pareto-optimal solutions, and it helps management decide on the selection of p-facility locations. They could transport their product to the facility locations easily, with minimum transport, CE costs, and transportation time. As a result, management can give equal attention to their profit and environment, which helps to build world market credibility. At last, the paper concludes the results. [ABSTRACT FROM AUTHOR]

Multi-objective evolutionary algorithms (MOEAs) have been successfully employed to solve many scientific and engineering problems. However, many algorithms perform ill in maintaining diversity and convergence simultaneously. In this paper, we devised a novel operator selection framework based on two collaborative indicators, generational distance (GD) and maximum spread (MS) to improve the diversity while maintaining a good convergence. By calculating the variation of GDs and MSs over the past 7 iterations, an instruction is conveyed to select a proper operator to execute next 7 iterations. This process is repeated until it reaches the maximum iteration. Two operators are embedded in this algorithm which are differential evolution operator (DE/rand/1) and our proposed crow search operator which is deemed to be efficient in explorating the search space. MOEA/D is utilized as the basis framework of our proposed algorithm. Experiments indicate that our proposed algorithm is valid and outperforms other famous algorithms in terms of diversity and convergence. In the end, a particular aeroengine maintenance scheduling problem is solved by our proposed algorithm. [ABSTRACT FROM AUTHOR]

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [ABSTRACT FROM AUTHOR]

Evolutionary algorithms (EAs) are usually required to solve problems based on domination relationship among solutions. Often, the domination relationship is almost the sole source of knowledge that EAs can utilize, especially when the problem solving engine concerned is taken as a black box. In this paper, the domination landscape (DL), onto which an optimization problem (OP) can be mapped, is introduced. A DL may correspond to a cluster of OPs, implying that a class of OPs may have the same DL. To illustrate DL, we consider its representation as a directed graph, with its corresponding matrix and function. Of the various properties of DL, the domination-preserving property is used for the analysis of DL-equivalent OPs, and for the basis for classification of OPs. Taking DL as a tool for theoretical analysis, parameters determination for fitness scaling, the convergence property of EAs and the analysis of robustness in light of fitness noise are presented. The study of DL in this paper establishes the necessary theoretical foundation for future applications of DL equality and similarity based optimization. [ABSTRACT FROM AUTHOR]

To solve engineering problems with evolutionary algorithms, many expensive function evaluations (FEs) are required. To alleviate this difficulty, surrogate-assisted evolutionary algorithms (SAEAs) have attracted increasingly more attention in both academia and industry. Most existing SAEAs either waste computational resources due to the lack of accuracy of the surrogate model or easily fall into the local optimum as the dimension increases. To address these problems, this paper proposes an adaptive surrogate-assisted particle swarm optimization algorithm. In the proposed algorithm, a surrogate model is adaptively selected from a single model and an ensemble model by comparing the best existing solution and the latest obtained solution. Additionally, a model output criterion based on the standard deviation is suggested to improve the stability and generalization ability of the ensemble model. To verify the performance of the proposed algorithm, 10 benchmark functions with different modalities from 10 to 50 dimensions are tested, and the results are compared with those of five state-of-the-art SAEAs. The experimental results indicate that the proposed algorithm performs well for most benchmark functions within a limited number of FEs. Moreover, the performance of the proposed algorithm in solving engineering problems is verified by applying the algorithm to the PX oxidation process. [ABSTRACT FROM AUTHOR]

In the established hierarchical distributed evolutionary algorithms (HDEAs), object of global migration is individual. To obtain better solutions of concrete problems, global migration strategy with moving colony is proposed in this paper. In global migration based on the proposed strategy, migration object is subpopulation which moves between groups. Such global migration can increase the efficiency of thereafter local migration. Moreover, realizing it even needs no communication because it can be executed by regrouping subpopulations. In our experiments, the basement of parallelism is an EA for the Traveling Salesman Problem. Outcomes of HDEAs based on proposed scheme which have different global migration topology are compared with those of traditional ones on nine benchmark instances. The results show that a HDEA based on the proposed strategy having the ring global topology performs better than traditional HDEAs for high difficulty instances. However, the advantage of that having the random global topology is not so significant because of conflicting migrations arisen from this topology. [ABSTRACT FROM AUTHOR]

Dynamic multi-objective optimization problems are the multi-objective optimization problems in which the objectives change with environment and time, and the optimization algorithm for solving such problems must be able to track the changed pareto optimal set and further explore the real pareto optimal front. It is a difficult and hot topic in dynamic multi-objective evolutionary algorithm to accurately predict the direction of population movement after environmental changes. In this paper, the ensemble Kalman filter is introduced into dynamic multi-objective optimization problems to predict the population center point after environmental changes. ensemble Kalman filter is a four-dimensional assimilation method that uses Monte Carlo short-term ensemble prediction method to estimate the prediction error covariance and has achieved great success in many fields. In the proposed algorithm, the new population center point is predicted by the ensemble Kalman filter prediction model according to the historical population information when the environment changes, and then the population is reinitialized according to the predicted population center point. The experimental results show that the proposed algorithm is superior to other comparison strategies in most test instances. [ABSTRACT FROM AUTHOR]

Monarch butterfly optimization (MBO), which is a simple and widely used algorithm, has some limitations, such as utilizing the obtained experiential knowledge about the search space inefficiently, the lack of exploration, and being rotational variance. This paper proposes a new variation of MBO, which is called knowledge-based MBO (KMBO), to address these limitations. KMBO is proposed by introducing new operators that are linearized and can utilize the population's experimental knowledge. Furthermore, KMBO adopts the re-initialization operator to enhance the exploration ability and increase the diversity of the population. To verify KMBO's performance, it is tested on 23 well-known optimization benchmark functions and compared with MBO and five other state-of-the-art evolutionary algorithms. Experimental results confirm the superior performance of our proposed algorithm compared with MBO in terms of solution accuracy and convergence speed. Also, results demonstrate that KMBO performs better than or provides competitive performance with the other six algorithms. In addition, the real-world application of KMBO on clustering optimization is presented. The results prove that KMBO is applicable to solve real-world problems and achieve superior results. [ABSTRACT FROM AUTHOR]

Cellular genetic algorithms (cGAs) are a class of evolutionary algorithms in which the population is structured as a grid and interactions between individuals are restricted to the neighbourhood. Like any other optimisation algorithm, the cGA's efficiency lies in its ability to find an adequate balance between its exploratory and exploitive capabilities. The search selection pressure represents a good indicator of the state of that balance. From that point of view, it has been shown that the cGA's grid-to-neighbourhood relationship can be used to reflect this property. Until today, not much has been done in that area of research and many questions still surround this grid-to-neighbourhood effect. This paper describes a systematic study on the effects of that ratio on the efficiency of the cGA. This is done by proposing a dynamic cGA that adapts its ratio through evolving its grid structure using some strategy. The study is conducted using a wide range of dynamic and static ratio-control policies and, for the first time, by considering both synchronous and asynchronous cGAs. As a validation problem, we have opted for a real-world complex problem in advanced cellular networks: the users' mobility management. A wide set of differently sized and realistic instances of this problem have been used, and several comparisons have been conducted against other top-ranked solvers. The experiments showed that the ratio strategy rules the cGA's convergence, efficiency and scalability. Its effectiveness is correlated with the ratio-adaptation policy and the replacement synchronism being used. Indeed, our proposals that are based on deterministic and dynamic strategies with an asynchronous replacement were able to outperform most of the state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

In a multiprocessor system, scheduling is an NP-hard problem, and solving it using conventional techniques demands the support of evolutionary algorithms such as genetic algorithms (GAs). Handling the energy consumption issues, while delivering the desired performance for a system, is also a challenging task. In order to achieve these goals, this paper proposes a GA-based method for optimizing the energy consumption and performance of multiprocessor systems using a weighted-sum approach. A performance optimization algorithm with two different selection operators, namely the proportional roulette wheel selection (PRWS) and the rank-based roulette wheel selection (RRWS), is proposed, and the impact of adding elitism in the GA is investigated. Simulation results show that for a specific task graph, using the considered selection operators with elitism yields, respectively, 16.80, 17.11 and 17.82% reduction in energy consumption with a deviation in finish time of 2.08, 2.01 and 1.76 ms when an equal weight factor of 0.5 is considered. This confirms that the selection operator RRWS is superior to PRWS. It is also seen that using elitism enhances the optimization procedure. For a given specific workload, the average percentage reduction in energy consumption with varying weight vector is in the range 12.57-19.51%, with a deviation in finish time of the schedule varying between 1.01 and 2.77 ms. [ABSTRACT FROM AUTHOR]

This paper discusses the use of direction of improvement in guiding multi-objective evolutionary algorithms (MOEAs) during the search process towards the area of Pareto optimal set. We particularly propose a new version of the Direction based Multi-objective Evolutionary Algorithm (DMEA) and name it as DMEA-II. The new features of DMEA-II includes (1) an adaptation of the balance between convergence and spreading by using an adaptive ratio between the convergence and spreading directions being selected over time; (2) a new concept of ray-based density for niching; and (3) a new selection scheme based on the ray-based density for selecting solutions for the next generation. To validate the performance of DMEA-II, we carried out a case study on a wide range of test problems and comparison with other MOEAs. It obtained quite good results on primary performance metrics, namely the generation distance, inverse generation distance, hypervolume and the coverage set. Our analysis on the results indicates the better performance of DMEA-II in comparison with the most popular MOEAs. [ABSTRACT FROM AUTHOR]

As one of the most popular evolutionary algorithms, differential evolution (DE) has been used for solving a wide range of real-world problems. The performance of DE highly depends on the chosen mutation strategy and control parameter settings. Although the conventional trial-and-error procedure can be used to elaborately select the proper strategy and to tune the parameter values, this procedure is often very time-consuming and is not suitable for practitioners without a priori experience. To tackle this problem, DE with a novel role assignment (RA) scheme is proposed in this paper. In the RA scheme, both the fitness information and positional information of individuals are utilized to dynamically divide the population into several groups. Each group is considered as a role, which has its own mutation strategy and parameter settings and is expected to play a different role in the evolution process. To verify the performance of our approach, experiments are conducted on 23 well-known benchmark functions. Results show that our approach is better than, or at least comparable to, several state-of-the-art DE variants. [ABSTRACT FROM AUTHOR]

Coupling sensors in a sensor network with mobility mechanism can boost the performance of wireless sensor networks (WSNs). In this paper, we address the problem of self-deploying mobile sensors to reach high coverage. The problem is modeled as a multi-objective optimization that simultaneously minimizes two contradictory parameters; the total sensor moving distance and the total uncovered area. In order to resolve the aforementioned deployment problem, this study investigates the use of biologically inspired mechanisms, including evolutionary algorithms and swarm intelligence, with their state-of-the-art algorithms. Unlike most of the existing works, the coverage parameter is expressed as a probabilistic inference model due to uncertainty in sensor readings. To the best of our knowledge, probabilistic coverage of mobile sensor networks has not been addressed in the context of multi-objective bio-inspired algorithms. Performance evaluations on deployment quality and deployment cost are measured and analyzed through extensive simulations, showing the effectiveness of each algorithm under the developed objective functions. Simulations reveal that only one multi-objective evolutionary algorithm; the so-called multi-objective evolutionary algorithm with decomposition survives to effectively tackle the probabilistic coverage deployment problem. It gathers more than 78 % signals from all of the targets (and in some cases reaches 100 % certainty). On the other hand, non-dominated sorting genetic algorithm II, multi-objective particle swarm optimization, and non-dominated sorting particle swarm optimization show inferior performance down to 16-32 %, necessitating further modifications in their internal mechanisms. [ABSTRACT FROM AUTHOR]

In evolutionary algorithm, one of the main issues is how to reduce the number of fitness evaluations required to obtain optimal solutions. Generally a large number of evaluations are needed to find optimal solutions, which leads to an increase of computational time. Expensive cost may have to be paid for fitness evaluation as well. Differential evolution (DE), which is widely used in many applications due to its simplicity and good performance, also cannot escape from this problem. In order to solve this problem a fitness approximation model has been proposed so far, replacing real fitness function for evaluation. In fitness approximation, an ability to estimate accurate value with compact structure is needed for good performance. Therefore in this paper we propose an efficient differential evolution using fitness estimator. We choose k-nearest neighbor (kNN) as fitness estimator because it does not need any training period or complex computation. However too many training samples in the estimator may cause computational complexity to be exponentially high. Accordingly, two schemes with regard to accuracy and efficiency are proposed to improve the estimator. Our proposed algorithm is tested with various benchmark functions and shown to find good optimal solutions with less fitness evaluation and more compact size, compared with DE and DE-kNN. [ABSTRACT FROM AUTHOR]

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) is a recently proposed algorithm which is a research focus in the field of multi-objective evolutionary optimization. It decomposes a multi-objective problem into subproblems by mathematic programming methods and applies evolutionary algorithms to optimize the subproblems simultaneously. MOEA/D is good at finding Pareto solutions which are evenly distributed. However, it can be improved for problems with discontinuous Pareto fronts (PF). Many solutions will assemble in breakpoints in this situation. A method for adjusting weight vectors for bi-objective optimization problems with discontinuous PF is proposed. Firstly, this method detects the weight vectors which need to be adjusted using a property of MOEA/D. Secondly, the reserved vectors are divided into several subsets. Thirdly, after calculating the ideal number of vectors in each subset, vectors are adjusted evenly. Lastly, the corresponding solutions are updated by a linear interpolation. Numerical experiment shows the proposed method obtains good diversity and convergence on approached PF. [ABSTRACT FROM AUTHOR]

The purpose of multi-objective optimization is to simultaneously optimize several objective functions that are usually in conflict with each other. An acceptable solution is one that can strike a trade-off between the results of these functions. Although, multi-objective evolutionary algorithms have a good history in solving multi-objective problems, how to find more accurate and diverse solutions set at an acceptable time is still a challenge. In this study, a quantum-inspired multi-objective harmony search algorithm is proposed to solve multi-objective optimization problems. In this algorithm, a new quantum mutation strategy is proposed, which is a combination of harmony improvisation operators and a quantum adaptive rotation gate. While the use of the rotation gate leads to the move to further solutions and complete coverage of the problem space, the improvisation operators (PAR and BW) trigger tiny impulses and mutate into neighbor solutions. The advantage of such an algorithm is to strengthen the balance between the exploration and exploitation processes. Also, the crowding distance metric of the elitism strategy ensures the production of solutions with maximum variety in the problem space. The results of the implementation of this algorithm on multi-objective benchmark functions indicate significant improvement in criteria such as the distance to Pareto optimal, the scattering, and the convergence rate compared to the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Classification is an essential task in the field of machine learning, where finding a maximum margin classifier is one of its central problems. In this work, an evolutionary algorithm is constructed, relying on the convexity properties of the version space, to evolve a population of perceptron classifiers in order to find a solution that approximates the maximum margin. Unlike other methods whose solutions explore the problem's dual formulation, usually requiring the solution of a linear constraint quadratic programming problem, the proposed method requires only the evaluation of the margin values. Hyperspherical coordinates are used to guarantee feasibility when generating new individuals and for the population to be uniformly distributed through the search space. To control the number of generations, we developed a stop criteria based on a lower bound function which asymptotically approximates the margin curves providing a stop margin that satisfies a β -approximation of the optimal margin. Experiments were performed on artificial and real datasets, and the obtained results indicate the potential to adopt the proposed algorithm for solving practical problems. [ABSTRACT FROM AUTHOR]

A novel adaptive multi-context cooperatively coevolving particle swarm optimization (AM-CCPSO) algorithm is proposed in an attempt to improve the performance on solving large-scale optimization problems (LSOP). Due to the curse of dimensionality, most optimization algorithms show their weaknesses on LSOP, and the cooperative co-evolution (CC) is often utilized to overcome such weaknesses. The basic CC framework employs one context vector for cooperatively, but greedily coevolving different subcomponents, which sometimes fails to find global optimum, especially on some complex non-separable LSOP. In the AM-CCPSO, more than one context vectors are employed to provide robust and effective co-evolution. These vectors are selected with respect to each particle of each subcomponent according to their own adaptive probabilities. In the AM-CCPSO, a new PSO updating rule is also proposed to exploit 'four best positions' via Gaussian sampling. On a comprehensive set of benchmarks (up to 1000 real-valued variables), as well as on a real world application, the performance of AM-CCPSO can rival several state-of-the-art evolutionary algorithms. Experimental results indicate that the novel adaptive multi-context CC framework is effective to improve the performance of PSO on solving LSOP and can be generally extended in other evolutionary algorithms. [ABSTRACT FROM AUTHOR]

The performance of most existing multiobjective evolutionary algorithms deteriorates severely in the face of many-objective problems. Many-objective optimization has been gaining increasing attention, and many new many-objective evolutionary algorithms (MaOEA) have recently been proposed. On the one hand, solution sets with totally different characteristics are obtained by different MaOEAs, since different MaOEAs have different convergence-diversity tradeoff relations. This may suggest the potential usefulness of ensemble approaches of different MaOEAs. On the other hand, the performance of MaOEAs may vary greatly from one problem to another, so that choosing the most appropriate MaOEA is often a non-trivial task. Hence, an MaOEA that performs generally well on a set of problems is often desirable. This study proposes an ensemble of MaOEAs (EMaOEA) for many-objective problems. When solving a single problem, EMaOEA invests its computational budget to its constituent MaOEAs, runs them in parallel and maintains interactions between them by a simple information sharing scheme. Experimental results on 80 benchmark problems have shown that, by integrating the advantages of different MaOEAs into one framework, EMaOEA not only provides practitioners a unified framework for solving their problem set, but also may lead to better performance than a single MaOEA. [ABSTRACT FROM AUTHOR]

The evolutionary algorithms (EAs) became more and more important in solving NP-hard problems in recent years. The representation of specific problems in EAs is very important and it has a great influence on the performance of EAs. The constraint satisfaction problems (CSPs) are typical NP-hard problems and the representation of CSPs can be traditionally divided into two types, namely the direct and indirect representations. The variables in direct representation represent the actual values that they can take, and can be evaluated directly. Whereas in indirect representation, a specific permutation is assigned to variables, and the individual is incapable of being evaluated without a decoder. In order to take advantage of both representations to enforce the ability of EAs in solving CSPs, we propose a combination of these two representations in this article. The minimum conflict decoder is employed to transform indirect representation to direct representation and several new behaviors are designed for agents in multiagent evolutionary algorithms. In experiments, 250 benchmark binary CSPs and 79 graph coloring problems are tested. The comparisons among the direct, indirect and the combined representation methods are conducted. Experimental results illustrate that the method of combined representation outperforms the two other methods. [ABSTRACT FROM AUTHOR]

An important issue in multiobjective optimization is the study of the convergence speed of algorithms. An optimization problem must be defined as simple as possible to minimize the computational cost required to solve it. In this work, we study the convergence speed of seven multiobjective evolutionary algorithms: DEPT, MO-VNS, MOABC, MO-GSA, MO-FA, NSGA-II, and SPEA2; when solving an important biological problem: the motif discovery problem. We have used twelve instances of four different organisms as benchmark, analyzing the number of fitness function evaluations required by each algorithm to achieve reasonable quality solutions. We have used the hypervolume indicator to evaluate the solutions discovered by each algorithm, measuring its quality every 100 evaluations. This methodology also allows us to study the hit rates of the algorithms over 30 independent runs. Moreover, we have made a deeper study in the more complex instance of each organism. In this study, we observe the increase of the archive (number of non-dominated solutions) and the spread of the Pareto fronts obtained by the algorithm in the median execution. As we will see, our study reveals that DEPT, MOABC, and MO-FA provide the best convergence speeds and the highest hit rates. [ABSTRACT FROM AUTHOR]