Spin-flip symmetry and synchronization

In the context of optimization by evolutionary algorithms (EAs), epistasis, deception, and scaling are well-known examples of problem difficulty characteristics. The presence of one such characteristic in the representation of a search problem indicates a certain type of difficulty the EA is to encounter during its search for globally optimal configurations. In this paper, we claim that the occurrence of symmetry in the representation is another problem difficulty characteristic and discuss one particular form, spin-flip symmetry, characterized by fitness invariant permutations on the alphabet. Its usual effect on unspecialized EAs, premature convergence due to synchronization problems, is discussed in detail. We discuss five different ways to specialize EAs to cope with the symmetry: adapting the genetic operators, changing the fitness function, using a niching technique, using a distributed EA, and attaching a highly redundant genotype-phenotype mapping.     

Probabilistic tree-based representation for solving minimum cost integer flow problems with nonlinear non-convex cost functions

The minimum cost flow problem (MCFP) is the most generic variation of the network flow problem which aims to transfer a commodity throughout the network to satisfy demands. The problem size (in terms of the number of nodes and arcs) and the shape of the cost function are the most critical factors when considering MCFPs. Existing mathematical programming techniques often assume the cost functions to be linear or convex. Unfortunately, the linearity and convexity assumptions are too restrictive for modelling many real-world scenarios. In addition, many real-world MCFPs are large-scale, with networks having a large number of nodes and arcs. In this paper, we propose a probabilistic tree-based genetic algorithm (PTbGA) for solving large-scale minimum cost integer flow problems with nonlinear non-convex cost functions. We first compare this probabilistic tree-based representation scheme with the priority-based representation scheme, which is the most commonly-used representation for solving MCFPs. We then compare the performance of PTbGA with that of the priority-based genetic algorithm (PrGA), and two state-of-the-art mathematical solvers on a set of MCFP instances. Our experimental results demonstrate the superiority and efficiency of PTbGA in dealing with large-sized MCFPs, as compared to the PrGA method and the mathematical solvers.     

Problem reduction representation for the linguistic analysis of waveforms

This paper shows how the nondirectional structural analysis of pattern data can be performed by matching a problem reduction representation (PRR) of pattern structure with sample data, using a best-first state space search algorithm called SSS*. The end result of the matching algorithm is a tree whose nodes represent recognized structures in the data. Tip nodes of the tree structure correspond to primitives which are recognized in the raw data by curve fitting routines. The operators of the algorithm allow the tree to be constructed with a combination of top-down or bottom-up steps. The matching of the structure tree to waveform segments need not be done in a left-right sequence. Moreover ambiguous matches are pursued in a best first order by using state space search with partial parse trees as states. A software system called WAPSYS (for waveform parsing system) is described, which implements this structural analysis paradigm. Experience using WAPSYS to analyze carotid pulse waves is also discussed.     

Redundancy and computational efficiency in Cartesian genetic programming

The graph-based Cartesian genetic programming system has an unusual genotype representation with a number of advantageous properties. It has a form of redundancy whose role has received little attention in the published literature. The representation has genes that can be activated or deactivated by mutation operators during evolution. It has been demonstrated that this "junk" has a useful role and is very beneficial in evolutionary search. The results presented demonstrate the role of mutation and genotype length in the evolvability of the representation. It is found that the most evolvable representations occur when the genotype is extremely large and in which over 95% of the genes are inactive.     

Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm

In real life applications we often have the following problem: How to find the reasonable assignment strategy to satisfy the source and destination requirement without shipping goods from any pairs of prohibited sources simultaneously to the same destination so that the total cost can be minimized. This kind of problem is known as the transportation problem with exclusionary side constraint (escTP). Since this problem is one of nonlinear programming models, it is impossible to solve this problem using a traditional linear programming software package (i.e., LINDO). In this paper, an evolutionary algorithm based on a genetic algorithm approach is proposed to solve it. We adopt a Prüfer number to represent the candidate solution to the problem and design the feasibility of the chromosome. Moreover, to handle the infeasible chromosome, here we also propose the repairing procedure. In order to improve the performance of the genetic algorithm, the fuzzy logic controller (FLC) is used to dynamically control the genetic operators. Comparisons with other conventional methods and the spanning tree-based genetic algorithm (st-GA) are presented and the results show the proposed approach to be better as a whole.     

An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes

This paper addresses the problem of scheduling jobs with non-identical sizes on a single batch processing machine. A batch processing machine is one which can process multiple jobs simultaneously as a batch as long as the total size of jobs being processed does not exceed the machine capacity. The batch processing time is equal to the longest processing time among all jobs in the batch. For the simultaneous minimization of the bi-criteria of makespan and maximum tardiness, we propose two different multi-objective genetic algorithms based on different representation schemes. While the first algorithm do search via generating sequences of jobs using genetic operators and then batching jobs keeping their order in the sequence, the second algorithm uses the idea of generating batches of jobs directly using genetic operators and ensures feasibility through using heuristic procedures. The type of representation used in the second algorithm allows introducing heuristics with the ability of biasing the search towards each objective and also allows hybridization with a local search heuristic that gives the ability of finding Pareto-optimal or locally efficient Pareto-solutions. Computational results show that the non-dominated solutions obtained by the latter algorithm are very superior in closeness to the true Pareto-optimal solutions and to keep diversity in the obtained Pareto-set, as the problem size increases.     

Crew pairing optimization by a genetic algorithm with unexpressed genes

We propose a genetic algorithm to solve the pairing optimization problem for subway crew scheduling. Our genetic algorithm employs new crossover and mutation operators specially designed to work with the chromosomes of set-oriented representation. To enhance the efficiency of the search with the newly designed genetic operators, we let a chromosome consist of an expressed part and an unexpressed part. While the genes in both parts evolve, only the genes in the expressed part are used when an individual is evaluated. The purpose of the unexpressed part is to preserve information susceptible to be lost by the application of genetic operators, and thus to maintain the diversity of the search. Experiments with real-world data have shown that our genetic algorithm outperforms other local search methods such as simulated annealing and tabu search. Received: June 2005/Accepted: December 2005     

Event tree based sampling

We develop a new sampling method, called an event tree-based sampling, which is suitable for the multistage stochastic programming formulation for the asset liability management. We find that our method captures a special structure inherited in the binomial lattice representation of an event tree, which is the essential part of the stochastic formulation of asset liability management under uncertainty.     

Hybrid genetic algorithms for constrained placement problems

When solving real-world problems, often the main task is to find a proper representation for the candidate solutions. Strings of elementary data types with standard genetic operators may tend to create infeasible individuals during the search because of the discrete and often constrained search space. This article introduces a generally applicable representation for 2D combinatorial placement and packing problems. Empirical results are presented for two constrained placement problems, the facility layout problem and the generation of VLSI macro-cell layouts. For multiobjective optimization problems, common approaches often deal with the different objectives in different phases and thus are unable to efficiently solve the global problem. Due to a tree structured genotype representation and hybrid, problem-specific operators, the proposed approach is able to deal with different constraints and objectives in one optimization step     

The property analysis of evolutionary algorithms applied to spanning tree problems

The search behavior of an evolutionary algorithm depends on the interactions between the encoding that represents candidate solutions to the target problem and the operators that act on that encoding. In this paper, we focus on analyzing some properties such as locality, heritability, population diversity and searching behavior of various decoder-based evolutionary algorithm (EA) frameworks using different encodings, decoders and genetic operators for spanning tree based optimization problems. Although debate still continues on how and why EAs work well, many researchers have observed that EAs perform well when its encoding and operators exhibit good locality, heritability and diversity properties. We analyze these properties of various EA frameworks with two types of analytical ways on different spanning tree problems; static analysis and dynamic analysis, and then visualize them. We also show through this analysis that EA using the Edge Set encoding (ES) and the Edge Window Decoder encoding (EWD) indicate very good locality and heritability as well as very good diversity property. These are put forward as a potential explanation for the recent finding that they can outperform other recent high-performance encodings on the constrained spanning tree problems.     

Deriving Event-Based Document Transformers from Tree-Based Specifications

Structured documents are usually processed by tree-based document transformers, which transform the document tree representing the structure of the input document into another tree structure. Event-based document transformers, by contrast, recognize the input as a stream of parsing events, i.e., lexical tokens, and process the events one by one in an event-driven manner. Event-based document transformers have advantages that they need less memory space and that they are more tolerant of large inputs, compared to tree-based transformers, which construct the intermediate tree representation.This paper proposes an algorithm which derives an event-based transformer from a given specification of a document transformation over a tree structure. The derivation of an event-based transformer is carried out in the framework of attribute grammars. We first obtain an attribute grammar which processes a stream of parsing events, by applying a deforestation method; We then derive an attribute evaluation scheme relevant to the event-based transformation. Using this algorithm, one can develop event-based document transformers in a more declarative style than directly programming over the stream of parsing events.     

A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems

In this paper, we propose a genetic algorithm using priority-based encoding (pb-GA) for linear and nonlinear fixed charge transportation problems (fcTP) in which new operators for more exploration are proposed. We modify a priority-based decoding procedure proposed by Gen et al. [1] to adapt with the fcTP structure. After comparing well-known representation methods for a transportation problem, we explain our proposed pb-GA. We compare the performance of the pb-GA with the recently used spanning tree-based genetic algorithm (st-GA) using numerous examples of linear and nonlinear fcTPs. Finally, computational results show that the proposed pb-GA gives better results than the st-GA both in terms of the solution quality and computation time, especially for medium- and large-sized problems. Numerical experiments show that the proposed pb-GA better absorbs the characteristics of the nonlinear fcTPs.     

Solving High-Order Boolean Parity Problems with Smooth Uniform Crossover, Sub-Machine Code GP and Demes

We propose and study new search operators and a novel node representation that can make GP fitness landscapes smoother. Together with a tree evaluation method known as sub-machine-code GP and the use of demes, these make up a recipe for solving very large parity problems using GP. We tested this recipe on parity problems with up to 22 input variables, solving them with a very high success probability.     

基于开放读码框架的GEP遗传算子

基因表达式编程（GEP）采用的已有单点重组、两点重组、插串等遗传操作有很大概率发生在基因的非编码区,导致搜索过程中遗传操作前后的基因解码成相同的表达式树,这在一定程度上影响了GEP的搜索性能。为解决这一问题,提出了一类基于开放读码框架的遗传算子,这类算子从基因的编码区中选取作用点,以保证遗传操作将改变编码区中的基因片段,从而使遗传操作后的基因能解码成不同的表达式树。实验结果表明,与已有的同类遗传算子相比,提出的遗传算子缩短了GEP算法进化代数,提高了算法的成功率。     

An adaptive hybrid genetic algorithm for the three-matching problem

This paper presents a hybrid genetic algorithm (GA) with an adaptive application of genetic operators for solving the 3-matching problem (3MP), an NP-complete graph problem. In the 3MP, we search for the partition of a point set into minimal total cost triplets, where the cost of a triplet is the Euclidean length of the minimal spanning tree of the three points. The problem is a special case of grouping and facility location problems. One common problem with GA applied to hard combinatorial optimization, like the 3MP, is to incorporate problem-dependent local search operators into the GA efficiently in order to find high-quality solutions. Small instances of the problem can be solved exactly, but for large problems, we use local optimization. We introduce several general heuristic crossover and local hill-climbing operators, and apply adaptation to choose among them. Our GA combines these operators to form an effective problem solver. It is hybridized as it incorporates local search heuristics, and it is adaptive as the individual recombination/improvement operators are fired according to their online performance. Test results show that this approach gives approximately the same or even slightly better results than our previous, fine tuned GA without adaptation. It is better than a grouping GA for the partitioning considered. The adaptive combination of operators eliminates a large set of parameters, making the method more robust, and it presents a convenient way to build a hybrid problem solver     

An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II

In this study, we consider the assembly line worker assignment and balancing problem of type-II (ALWABP-2). ALWABP-2 arises when task times differ depending on operator skills and concerns with the assignment of tasks and operators to stations in order to minimize the cycle time. We developed an iterative genetic algorithm (IGA) to solve this problem. In the IGA, three search approaches are adopted in order to obtain search diversity and efficiency: modified bisection search, genetic algorithm and iterated local search. When designing the IGA, all the parameters such as construction heuristics, genetic operators and local search operators are adapted specifically to the ALWABP-2. The performance of the proposed IGA is compared with heuristic and metaheuristic approaches on benchmark problem instances. Experimental results show that the proposed IGA is very effective and robust for a large set of benchmark problems.     

VLSI placement and area optimization using a genetic algorithm tobreed normalized postfix expressions

We present a genetic algorithm (GA) that uses a slicing tree construction process for the placement and area optimization of soft modules in very large scale integration floorplan design. We have overcome the serious representational problems usually associated with encoding slicing floorplans into GAs and have obtained excellent (often optimal) results for module sets with up to 100 rectangles. The slicing tree construction process used by our GA to generate the floorplans has a runtime scaling of O(n lg n). This compares very favorably with other recent approaches based on nonslicing floorplans that require much longer runtimes. We demonstrate that our GA outperforms a simulated annealing implementation with the same representation and mutation operators as the GA     

Scheduling parallel-machine batch operations to maximize on-time delivery performance

In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing on-time delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NP-hard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadth-first tree search algorithm that gives evidence of the quality of the solutions.