Solving multi-objective parallel machine scheduling problem by a modified NSGA-II

In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominated sorting Genetic Algorithm-II (NSGA-II) for a parallel machine scheduling problem with three objectives. The objectives are – (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-II (Non-dominated Sorting Genetic Algorithm–II), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-II as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-II. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-II is observed to perform better than the original NSGA-II. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results.     

Multiobjective evolutionary algorithms for complex portfolio optimization problems

This paper investigates the ability of Multiobjective Evolutionary Algorithms (MOEAs), namely the Non-dominated Sorting Genetic Algorithm II (NSGA-II), Pareto Envelope-based Selection Algorithm (PESA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), for solving complex portfolio optimization problems. The portfolio optimization problem is a typical bi-objective optimization problem with objectives the reward that should be maximized and the risk that should be minimized. While reward is commonly measured by the portfolio’s expected return, various risk measures have been proposed that try to better reflect a portfolio’s riskiness or to simplify the problem to be solved with exact optimization techniques efficiently. However, some risk measures generate additional complexities, since they are non-convex, non-differentiable functions. In addition, constraints imposed by the practitioners introduce further difficulties since they transform the search space into a non-convex region. The results show that MOEAs, in general, are efficient and reliable strategies for this kind of problems, and their performance is independent of the risk function used.     

Heuristic optimization methods for motion planning of autonomous agricultural vehicles

In this paper, two heuristic optimization techniques are tested and compared in the application of motion planning for autonomous agricultural vehicles: Simulated Annealing and Genetic Algorithms. Several preliminary experimentations are performed for both algorithms, so that the best neighborhood definitions and algorithm parameters are found. Then, the two tuned algorithms are run extensively, but for no more than 2000 cost function evaluations, as run-time is the critical factor for this application. The comparison of the two algorithms showed that the Simulated Annealing algorithm achieves the better performance and outperforms the Genetic Algorithm. The final optimum found by the Simulated Annealing algorithm is considered to be satisfactory for the specific motion planning application.     

Scatter Search in software testing,comparison and collaboration with Estimation of Distribution Algorithms

One of the main tasks software testing includes is the generation of the test cases to be used during the test. Due to its expensive cost, the automatization of this task has become one of the key issues in the area. The field of Evolutionary Testing deals with this problem by means of metaheuristic search techniques.An Evolutionary Testing based approach to the automatic generation of test inputs is presented. The approach developed involves different possibilities of the usage of two heuristic optimization methods, namely, Scatter Search and Estimation of Distribution Algorithms. The possibilities comprise pure Scatter Search options and Scatter Search—Estimation of Distribution Algorithm collaborations. Several experiments were conducted in order to evaluate and compare the approaches presented with those in the literature. The analysis of the experimental results raises interesting conclusions, showing these alternatives as a promising option to tackle this problem.     

Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing

Simulated Annealing and Genetic Algorithms are important methods to solve discrete optimization problems and are often used to find approximate solutions for diverse NP-complete problems. They depend on randomness to change their current configuration and transition to a new state. In Simulated Annealing, the random choice influences the construction of the new state as well as the acceptance of that new state. In Genetic Algorithms, selection, mutation and crossover depend on random choices. We experimentally investigate the robustness of the two generic search heuristics when using pseudorandom numbers of limited quality. To this end, we conducted experiments with linear congruential generators of various period lengths, a Mersenne Twister with artificially reduced period lengths as well as quasi-random numbers as the source of randomness. Both heuristics were used to solve several instances of the Traveling Salesman Problem in order to compare optimization results. Our experiments show that both Simulated Annealing and the Genetic Algorithm produce inferior solutions when using random numbers with small period lengths or quasi-random numbers of inappropriate dimension. The influence on Simulated Annealing, however, is more severe than on Genetic Algorithms. Interestingly, we found that when using diverse quasi-random sequences, the Genetic Algorithm outperforms its own results using quantum random numbers.     

New fitness sharing approach for multi-objective genetic algorithms

A novel fitness sharing method for MOGA (Multi-Objective Genetic Algorithm) is proposed by combining a new sharing function and sided degradations in the sharing process, with preference to either of two close solutions. The modified MOGA adopting the new sharing approach is named as MOGAS. Three different variants of MOGAS are tested; MOGASc, MOGASp and MOGASd, favoring children over parents, parents over children and solutions closer to the ideal point, respectively. The variants of MOGAS are compared with MOGA and other state-of-the-art multi-objective evolutionary algorithms such as IBEA, HypE, NSGA-II and SPEA2. The new method shows significant performance improvements from MOGA and is very competitive against other Evolutionary Multi-objective Algorithms (EMOAs) for the ZDT and DTLZ test functions with two and three objectives. Among the three variants MOGASd is found to give the best results for the test problems.     

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.     

基于最优保存和自适应性的混合遗传算法

1 引 言遗传算法（Genetic Algorithm,GA）是由Michigan大学Holland等创立的.常用的遗传算法一般有以下三种:简单遗传算法（Simple Genetic Algorithm,SGA）或称标准遗传算法（Canonical Genetic Algorithm,CGA）、最优保存简单遗传算法（Optimum MaintainingSimple Genetric Algorithm,OMSGA）和自适应遗传算法（Adaptive Genetic Algorithm,AGA）.     

Crossing Over Genetic Algorithms: The Sugal Generalised GA

Sugal is a major new public-domain software package designed to support experimentation with, and implementation of, Genetic Algorithms. Sugal includes a generalised Genetic Algorithm, which supports the major popular versions of the GA as special cases. Sugal also has integrated support for various datatypes, including real numbers, and features to make hybridisation simple. This paper discusses the Sugal GA, showing how recombining the features of the popular algorithms results in the creation of a number of useful hybrid algorithms.     

The Robust Set Covering Problem with interval data

We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.     

Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems

In this paper, a novel genetic algorithm is developed by generating artificial chromosomes with probability control to solve the machine scheduling problems. Generating artificial chromosomes for Genetic Algorithm (ACGA) is closely related to Evolutionary Algorithms Based on Probabilistic Models (EAPM). The artificial chromosomes are generated by a probability model that extracts the gene information from current population. ACGA is considered as a hybrid algorithm because both the conventional genetic operators and a probability model are integrated. The ACGA proposed in this paper, further employs the “evaporation concept” applied in Ant Colony Optimization (ACO) to solve the permutation flowshop problem. The “evaporation concept” is used to reduce the effect of past experience and to explore new alternative solutions. In this paper, we propose three different methods for the probability of evaporation. This probability of evaporation is applied as soon as a job is assigned to a position in the permutation flowshop problem. Experimental results show that our ACGA with the evaporation concept gives better performance than some algorithms in the literature.     

Optimization of Mechanically Coupled Composite Pipes by Genetic Algorithms

The optimization of composite components with regard to minimum weight and maximum load bearing capacity in consideration of multiple constraints is an optimization problem of rather high complexity. Genetic Algorithms are a good choice for solving such problems. In this paper the formulation of a Genetic Algorithm for the simultaneous optimization of two thin walled, mechanically coupled composite pipes subjected to a combination of thermal and mechanical loads is presented. The optimization goal is the minimization of the total mass of the pipe arrangement taking into account multiple design constraints. It is shown that Genetic Algorithms are valueable tools for solving optimization problems with a large number of parameters. Furthermore, it is possible to find additional, perhaps practicable, close‐to‐optimal configurations as a byproduct of the optimization process. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

SASEGASA: A New Generic Parallel Evolutionary Algorithm for Achieving Highest Quality Results

This paper presents a new generic Evolutionary Algorithm (EA) for retarding the unwanted effects of premature convergence. This is accomplished by a combination of interacting generic methods. These generalizations of a Genetic Algorithm (GA) are inspired by population genetics and take advantage of the interactions between genetic drift and migration. In this regard a new selection scheme is introduced, which is designed to directedly control genetic drift within the population by advantageous self-adaptive selection pressure steering. Additionally this new selection model enables a quite intuitive heuristics to detect premature convergence. Based upon this newly postulated basic principle the new selection mechanism is combined with the already proposed Segregative Genetic Algorithm (SEGA), an advanced Genetic Algorithm (GA) that introduces parallelism mainly to improve global solution quality. As a whole, a new generic evolutionary algorithm (SASEGASA) is introduced. The performance of the algorithm is evaluated on a set of characteristic benchmark problems. Computational results show that the new method is capable of producing highest quality solutions without any problem-specific additions.     

Ant colony optimization and local search for bin packing and cutting stock problems

The Bin Packing Problem and the Cutting Stock Problem are two related classes of NP-hard combinatorial optimization problems. Exact solution methods can only be used for very small instances, so for real-world problems, we have to rely on heuristic methods. In recent years, researchers have started to apply evolutionary approaches to these problems, including Genetic Algorithms and Evolutionary Programming. In the work presented here, we used an ant colony optimization (ACO) approach to solve both Bin Packing and Cutting Stock Problems. We present a pure ACO approach, as well as an ACO approach augmented with a simple but very effective local search algorithm. It is shown that the pure ACO approach can compete with existing evolutionary methods, whereas the hybrid approach can outperform the best-known hybrid evolutionary solution methods for certain problem classes. The hybrid ACO approach is also shown to require different parameter values from the pure ACO approach and to give a more robust performance across different problems with a single set of parameter values. The local search algorithm is also run with random restarts and shown to perform significantly worse than when combined with ACO.     

A pruning heuristic for use with multisource product design

Products can be improved by integrating multiple viewpoints during the design process. A model has been developed that uses conjoint data from consumers and designers and optimizes a product design based on the total share-of-choices. Because the problem becomes very difficult to solve as size increases, a heuristic is developed, based on pruning techniques, to solve the problem to near-optimality in a shorter period of time as compared to complete enumeration. The performance of the heuristic is demonstrated through the use of test data and by comparison to a Genetic Algorithm (GA) based heuristic and Tabu search. Structural results for the heuristic are also provided.     

混沌遗传算法

利用混沌序列来构造遗传算子,使不同代之间从短期看似随机的,而从长期看则存在着一种“精致”地内在关系,由此获得了一系列基于混沌序列的遗传算法,这些算法对克服标准遗传算法中的一些不足是有利的,更重要是将混沌引入遗传算法的新思路。     

A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm

Swarm intelligence is a research branch that models the population of interacting agents or swarms that are able to self-organize. An ant colony, a flock of birds or an immune system is a typical example of a swarm system. Bees’ swarming around their hive is another example of swarm intelligence. Artificial Bee Colony (ABC) Algorithm is an optimization algorithm based on the intelligent behaviour of honey bee swarm. In this work, ABC algorithm is used for optimizing multivariable functions and the results produced by ABC, Genetic Algorithm (GA), Particle Swarm Algorithm (PSO) and Particle Swarm Inspired Evolutionary Algorithm (PS-EA) have been compared. The results showed that ABC outperforms the other algorithms.     

Registrar: a complete-memory operator to enhance performance of genetic algorithms

We examine the concept of storing all evaluated chromosomes and directly reuse them in Genetic Algorithms (GAs). This is achieved by a fully encapsulated operator, called Registrar, which is effortlessly placed between the GA and the objective function. The Registrar does not approximate the objective function. Instead, it replaces the chromosomes requested by the GA with similar ones taken from the registry, bypassing the function evaluation. Unlike other methods that use external memory to increase genetic diversity, our simple implementation encourages revisits in order to avoid evaluations in an aggressive manner. Significant increase in performance is observed which is present even at the early stages of evolution, in accordance with the Birthday Problem of probability theory. Implementation with Standard GA shows great promise, while the encapsulation of the code facilitates implementation with other Evolutionary Algorithms.     

A comparison of the performance of artificial intelligence techniques for optimizing the number of kanbans

This paper discusses the use of modern heuristic techniques coupled with a simulation model of a Just in Time system to find the optimum number of kanbans while minimizing cost. Three simulation search heuristic procedures based on Genetic Algorithms, Simulated Annealing, and Tabu Search are developed and compared both with respect to the best results achieved by each algorithm in a limited time span and their speed of convergence to the results. In addition, a Neural Network metamodel is developed and compared with the heuristic procedures according to the best results. The results indicate that Tabu Search performs better than the other heuristics and Neural Network metamodel in terms of computational effort.