A review of procedures to evolve quantum algorithms

There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attributed to the non-intuitive nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into evolving quantum algorithms has shown promise. This paper provides an introduction into quantum and evolutionary algorithms for the computer scientist not familiar with these fields. The exciting field of using evolutionary algorithms to evolve quantum algorithms is then reviewed.

Genetic algorithms for sequencing problems in mixed model assembly lines

Mixed model assembly lines are a type of production line where a variety of product models similar in product characteristics are assembled. The effective utilisation of these lines requires that a schedule for assembling the different products be determined. In this paper, the performance of genetic algorithms for sequencing problems in mixed model assembly lines is investigated. The problem first considered is a comparison between a existing heuristic and the proposed genetic algorithm to get the constant usage of every part used by the line considering variation at multi levels (Number of levels fixed as four. level 1—product, level 2—subassembly, level 3—component, level 4—raw-materials) for various test-bed problems. The algorithms proposed by Miltenburg and Sinnamon hereafter referred to as MS 1992 [IIE Trans. 24 (1992) 121] and the proposed genetic algorithm (GA) applied to mixed model assembly line are compared. Results of evaluation indicate that the GA performs better over MS1992 on 25 of the 40 problems investigated.

The other problem solved is a multiple objective sequencing problem in mixed model assembly lines. Three practically important objectives are minimizing total utility work keeping a constant rate of part-usage, minimizing the variability in parts usage and minimizing total setup cost. In this paper, the performance of the selection mechanisms, the Pareto stratum-niche cubicle and the selection based on scalar fitness function value are compared with respect to the objective of minimising variation in part-usage, minimising total utility work and minimising the setup cost. Results of evaluation indicate that the genetic algorithm that uses the Pareto stratum-niche cubicle performs better than the genetic algorithm with the other selection mechanisms.     

Genetic algorithms to solve the power system restoration planning problem

This study reports the use of a Genetic Algorithm (GA) to solve the Power System Restoration Planning Problem (PSRP). The solution to the PSRP is described by a series of operations or a plan to be used by the Power System operator immediately on the occurrence of a blackout in the electrical power supply. Our GA uses new initialization and crossover operators based on the electrical power network, which are able to generate and maintain the plans feasible along GA runs. This releases the Power Flow program, which represents the most computer demanding component, from computing the fitness function of unfeasible individuals. The method was designed for large transmission systems and results for three different electrical power networks are shown: IEEE 14-Bus, IEEE 30-Bus, and a large realistic system.     

Genetic algorithms for match-up rescheduling of the flexible manufacturing systems

Scheduling plays a vital role in ensuring the effectiveness of the production control of a flexible manufacturing system (FMS). The scheduling problem in FMS is considered to be dynamic in its nature as new orders may arrive every day. The new orders need to be integrated with the existing production schedule immediately without disturbing the performance and the stability of existing schedule. Most FMS scheduling methods reported in the literature address the static FMS scheduling problems. In this paper, rescheduling methods based on genetic algorithms are described to address arrivals of new orders. This study proposes genetic algorithms for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by resequencing operations, respectively. The basic idea of the match-up approach is to modify only a part of the initial schedule and to develop genetic algorithms (GAs) to generate a solution within the rescheduling horizon in such a way that both the stability and performance of the shop floor are kept. The proposed non-reshuffle and reshuffle strategies have been evaluated and the results have been compared with the total-rescheduling method.     

Genetic algorithms to solve the cover printing problem

Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms.     

Genetic algorithms for delays evaluation in networked automation systems

In this paper, we present an approach to evaluate end-to-end delays in packets switching networked automation systems. Since Client-Server paradigm is considered for communication between the field devices, the existing methods of network delays evaluation are hardly applicable to assess realistic upper bounds of these delays. In an effort to enhance these delays evaluation, we propose an alternative method. Two algorithms, usually used for optimization problems, exhaustive and genetic algorithms, are then developed to achieve this purpose. While a formal proof about the capacity of the former one to ensure the worst delay overestimation is given, the latter proves to provide faster and more accurate results at the same time. This is shown on a practical case study while comparing the results of the two methods.     

Genetic algorithms for task scheduling problem

The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several genetic algorithms have been developed to solve this problem. A common feature in most of them has been the use of chromosomal representation for a schedule. However, these algorithms are monolithic, as they attempt to scan the entire solution space without considering how to reduce the complexity of the optimization process. In this paper, two genetic algorithms have been developed and implemented. Our developed algorithms are genetic algorithms with some heuristic principles that have been added to improve the performance. According to the first developed genetic algorithm, two fitness functions have been applied one after the other. The first fitness function is concerned with minimizing the total execution time (schedule length), and the second one is concerned with the load balance satisfaction. The second developed genetic algorithm is based on a task duplication technique to overcome the communication overhead. Our proposed algorithms have been implemented and evaluated using benchmarks. According to the evolved results, it has been found that our algorithms always outperform the traditional algorithms.     

Genetic algorithms for approximate similarity queries

Algorithms to query large sets of simple data (composed of numbers and small character strings) are constructed to retrieve the exact answer, retrieving every relevant element, so the answer said to be exact. Similarity searching over complex data is much more expensive than searching over simple data. Moreover, comparison operations over complex data usually consider features extracted from each element, instead of the elements themselves. Thus, even if an algorithm retrieves an exact answer, it is ‘exact’ regarding the extracted features, not regarding the original elements themselves. Therefore, trading exact answering with query time response can be worthwhile. In this work we developed two search strategies based on genetic algorithms to allow retrieving approximate data indexed by Metric Access Methods (MAM) within a limited, user-defined, amount of time. These strategies allow implementing algorithms to answer both range and k-nearest neighbor queries, and allow also to estimate the precision obtained for the approximate answer. Experimental evaluation shows that very good results (corresponding to what the user would expect) can be obtained in a fraction of the time required to obtain the exact answer.     

Genetic algorithms in classifier fusion

An intense research around classifier fusion in recent years revealed that combining performance strongly depends on careful selection of classifiers to be combined. Classifier performance depends, in turn, on careful selection of features, which could be further restricted by the subspaces of the data domain. On the other hand, there is already a number of classifier fusion techniques available and the choice of the most suitable method depends back on the selections made within classifier, features and data spaces. In all these multidimensional selection tasks genetic algorithms (GA) appear to be one of the most suitable techniques providing reasonable balance between searching complexity and the performance of the solutions found. In this work, an attempt is made to revise the capability of genetic algorithms to be applied to selection across many dimensions of the classifier fusion process including data, features, classifiers and even classifier combiners. In the first of the discussed models the potential for combined classification improvement by GA-selected weights for the soft combining of classifier outputs has been investigated. The second of the proposed models describes a more general system where the specifically designed GA is applied to selection carried out simultaneously along many dimensions of the classifier fusion process. Both, the weighted soft combiners and the prototype of the three-dimensional fusion–classifier–feature selection model have been developed and tested using typical benchmark datasets and some comparative experimental results are also presented.     

Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach

In general, distributed scheduling problem focuses on simultaneously solving two issues: (i) allocation of jobs to suitable factories and (ii) determination of the corresponding production scheduling in each factory. The objective of this approach is to maximize the system efficiency by finding an optimal planning for a better collaboration among various processes. This makes distributed scheduling problems more complicated than classical production scheduling ones. With the addition of alternative production routing, the problems are even more complicated. Conventionally, machines are usually assumed to be available without interruption during the production scheduling. Maintenance is not considered. However, every machine requires maintenance, and the maintenance policy directly affects the machine's availability. Consequently, it influences the production scheduling. In this connection, maintenance should be considered in distributed scheduling. The objective of this paper is to propose a genetic algorithm with dominant genes (GADG) approach to deal with distributed flexible manufacturing system (FMS) scheduling problems subject to machine maintenance constraint. The optimization performance of the proposed GADG will be compared with other existing approaches, such as simple genetic algorithms to demonstrate its reliability. The significance and benefits of considering maintenance in distributed scheduling will also be demonstrated by simulation runs on a sample problem.     

Genetic algorithms for designing loop layout manufacturing systems

A common layout for flexible manufacturing system is loop network with machines arranged in a cycle and materials transported in only one direction around the cycle. Congestion is a common measure for evaluating a loop layout. This paper investigates the problem of designing loop layout system with both of minsum and minmax congestion measures. A hybrid heuristic of genetic algorithms and neighborhood search is developed for solving such problem and preliminary computational results are reported.     

Genetic algorithms in computer aided design

Design is a complex engineering activity, in which computers are more and more involved. The design task can often be seen as an optimization problem in which the parameters or the structure describing the best quality design are sought.Genetic algorithms constitute a class of search algorithms especially suited to solving complex optimization problems. In addition to parameter optimization, genetic algorithms are also suggested for solving problems in creative design, such as combining components in a novel, creative way.Genetic algorithms transpose the notions of evolution in Nature to computers and imitate natural evolution. Basically, they find solution(s) to a problem by maintaining a population of possible solutions according to the ‘survival of the fittest’ principle. We present here the main features of genetic algorithms and several ways in which they can solve difficult design problems. We briefly introduce the basic notions of genetic algorithms, namely, representation, genetic operators, fitness evaluation, and selection. We discuss several advanced genetic algorithms that have proved to be efficient in solving difficult design problems. We then give an overview of applications of genetic algorithms to different domains of engineering design.     

Genetic production systems for intelligent problem solving

The paper discusses an evolutionary knowledge approach to intelligent problem solving. A rule-based production system is used to model the problem and the means by which the problem space should be searched. Search heuristics are modelled as production rules. These rules are redundant as there may be more than one view on the best method for building solutions. Some rules may have complex reasoning for their actions, others have none. Deciding which rule is most appropriate is solved by a genetic algorithm and ultimately only the fitter rules will survive. The approach eliminates the necessity of designing problem specific search or variation operators, leaving the genetic algorithm to process patterns independent of the problem at hand. Learning methods and how they aid evolution is also discussed: they are Lamarckian learning and the Baldwin effect. The approach is tested on a scheduling problem.     

Genetic algorithms in mesh optimization for visualization and finite element models

This paper investigates the use of a genetic algorithm (GA) to perform the large-scale triangular mesh optimization process. This optimization process consists of a combination of mesh reduction and mesh smoothing that will not only improve the speed for the computation of a 3D graphical or finite element model, but also improve the quality of its mesh. The GA is developed and implemented to replace the original mesh with a re-triangulation process. The GA features optimized initial population, constrained crossover operator, constrained mutation operator and multi-objective fitness evaluation function. While retaining features is important to both visualization models and finite element models, this algorithm also optimizes the shape of the triangular elements, improves the smoothness of the mesh and performs mesh reduction based on the needs of the user.     

多目标遗传算法在混流装配线排序中的应用

混流装配线实现在一条流水线上装配多种不同类型的产品。该文在总结混流装配线排序问题的基础上建立了二种排序的目标函数：最小化工作站的闲置与超载时间和保持均匀的零部件消耗速率。引入了基于Pareto理论和小生镜单元技术的适应度函数及选择算子构建了多目标遗传算法用于混流装配线的排序优化问题。通过一个混流装配线的多目标排序实验,验证了该方法的有效性。     

Applying genetic algorithms to zone design

Genetic algorithms (GA) have been found to provide global near optimal solutions in a wide range of complex problems. In this paper genetic algorithms have been used to deal with the complex problem of zone design. The zone design problem comprises a large number of geographical tasks, from which electoral districting is probably the most well known. The electoral districting problem is described and formalized mathematically. Different problem encodings, suited to GA optimization, are presented, together with different objective functions. A practical real world example is given and tests performed in order to evaluate the effectiveness of the GA approach.     

Using genetic algorithms for early schedulability analysis and stress testing in real-time systems

Reactive real-time systems have to react to external events within time constraints: Triggered tasks must execute within deadlines. It is therefore important for the designers of such systems to analyze the schedulability of tasks during the design process, as well as to test the system's response time to events in an effective manner once it is implemented. This article explores the use of genetic algorithms to provide automated support for both tasks. Our main objective is then to automate, based on the system task architecture, the derivation of test cases that maximize the chances of critical deadline misses within the system; we refer to this testing activity as stress testing. A second objective is to enable an early but realistic analysis of tasks' schedulability at design time. We have developed a specific solution based on genetic algorithms and implemented it in a tool. Case studies were run and results show that the tool (1) is effective at identifying test cases that will likely stress the system to such an extent that some tasks may miss deadlines, (2) can identify situations that were deemed to be schedulable based on standard schedulability analysis but that, nevertheless, exhibit deadline misses.

Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots

This paper describes the use of a genetic algorithm (GA) for the problem of offline point-to-point autonomous mobile robot path planning. The problem consists of generating “valid” paths or trajectories, for an Holonomic Robot to use to move from a starting position to a destination across a flat map of a terrain, represented by a two-dimensional grid, with obstacles and dangerous ground that the Robot must evade. This means that the GA optimizes possible paths based on two criteria: length and difficulty. First, we decided to use a conventional GA to evaluate its ability to solve this problem (using only one criteria for optimization). Due to the fact that we also wanted to optimize paths under two criteria or objectives, then we extended the conventional GA to implement the ideas of Pareto optimality, making it a multi-objective genetic algorithm (MOGA). We describe useful performance measures and simulation results of the conventional GA and of the MOGA that show that both types of GAs are effective tools for solving the point-to-point path-planning problem.     

A coevolutionary approach to adapt the genotype-phenotype map in genetic algorithms

This article introduces a coevolutionary approach to genetic algorithms (GAs) for exploring not only within a part of the solution space defined by the genotype-pheno-type map, but also the map itself. In canonical GAs with a fixed map, how large an area of the solution space can be covered by possible genomes, and consequently how better solutions can be found by a GA, rely on how well the geotype-phenotype map in designed, but it is difficult for designers of the algorithms to design the map without a priori knowledge of the solution space. In the proposed algorithm, the genotype-phenotype map is improved adaptively during the search process for solution candidates. It is applied to 3-bit deceptive problems such as of typical combinatorial optimazation problems. These are well known because their difficulty for GAs can be controlled by the genotype-phenotype map, and this shows a fairly good performance compared with a conventional GA. This work was presented in part at the Sixth International Symposium on Artificial Life and Robotics, Tokyo, January 15–17, 2001.