Evolutionary segmentation of texture image using genetic algorithms towards automatic decision of optimum number of segmentation areas

Segmentation of an image composed of different kinds of texture fields has difficulty in an exact discrimination of the texture fields and a decision of the optimum number of segmentation areas in an image when the image contains similar and/or unstationary texture fields. In this paper we formulate the segmentation problem upon such images as an optimization problem and adopt evolutionary strategy of genetic algorithms for the clustering of small regions in a feature space. The purpose of this paper is to demonstrate the efficiency of genetic algorithms to the texture segmentation and to develop the automatic texture segmentation method.     

Pattern-based time-series subsequence clustering using radial distribution functions

Clustering of time series subsequence data commonly produces results that are unspecific to the data set. This paper introduces a clustering algorithm, that creates clusters exclusively from those subsequences that occur more frequently in a data set than would be expected by random chance. As such, it partially adopts a pattern mining perspective into clustering. When subsequences are being labeled based on such clusters, they may remain without label. In fact, if the clustering was done on an unrelated time series it is expected that the subsequences should not receive a label. We show that pattern-based clusters are indeed specific to the data set for 7 out of 10 real-world sets we tested, and for window-lengths up to 128 time points. While kernel-density-based clustering can be used to find clusters with similar properties for window sizes of 8–16 time points, its performance degrades fast for increasing window sizes.

Order acceptance using genetic algorithms

This paper uses a genetic algorithm to solve the order-acceptance problem with tardiness penalties. We compare the performance of a myopic heuristic and a genetic algorithm, both of which do job acceptance and sequencing, using an upper bound based on an assignment relaxation. We conduct a pilot study, in which we determine the best settings for diversity operators (clone removal, mutation, immigration, population size) in connection with different types of local search. Using a probabilistic local search provides results that are almost as good as exhaustive local search, with much shorter processing times. Our main computational study shows that the genetic algorithm always dominates the myopic heuristic in terms of objective function, at the cost of increased processing time. We expect that our results will provide insights for the future application of genetic algorithms to scheduling problems.     

Parallel processing, neural networks and genetic algorithms

In an earlier paper[1] some recent developments in computational technology to structural engineering were described. The developments included: parallel and distributed computing; neural networks; and genetic algorithms. In this paper, the authors concentrate on parallel implementations of neural networks and genetic algorithms. In the final section of the paper the authors show how a parallel finite element analysis may be undertaken in an efficient manner by preprocessing of the finite element model using a genetic algorithm utilizing a neural network predictor. This preprocessing is the partitioning of the finite element mesh into sub-domains to ensure load balancing and minimum interprocessor communication during the parallel finite element analysis on a MIMD distributed memory computer. © 1998 Published by Elsevier Science Limited. All rights reserved.     

Machine-component grouping using genetic algorithms

One major problem in cellular manufacturing is the grouping of component parts with similar processing requirements into part families, and machines into manufacturing cells to facilitate the manufacturing of specific part families assigned to them. The objective is to minimize the total inter-cell and intra-cell movements of parts during the manufacturing process. In this paper, a mathematical model is presented to describe the characteristics of such a problem. An approach based on the concept of genetic algorithms is developed to determine the optimal machine-component groupings. Illustrative examples are used to demonstrate the efficiency of the proposed approach. Indeed, the results obtained show that the proposed genetic approach is a simple and efficient means for solving the machine-component grouping problem.     

Comparing networks with differing neural-node functions using transputer-based genetic algorithms

Different neural net node computational functions are compared using feedforward backpropagation networks. Three node types are examined: the standard model, ellipsoidal nodes and quadratic nodes. After preliminary experiments on simple small problems, in which quadratic nodes performed very well, networks of differing nodes types are applied to the speech recognition 104 speaker E-task using a fixed architecture. Ellipsoidal nodes were found to work well, but not as well as the standard model. Quadratic nodes did not perform well on the larger task. To facilitate an architecture independent comparison a transputer-based genetic algorithm is then used to compare ellipsoidal and mixed ellipsoidal and standard networks with the standard model. These experiments confirmed the earlier conclusion that ellipsoidal networks could not compare favourably with the standard model on the 104 speaker E-task. In an evolutionary search in which layer node types were free to adjust ellipsoidal nodes had a tendency to become extinct or barely survive. If the presence of ellipsoidal nodes was enforced then the resulting networks again performed poorly when compared with the standard model.     

Design and comparison of adaptive power system stabilizers based on neural fuzzy networks and genetic algorithms

This paper presents two different power system stabilizers (PSSs) which are designed making use of neural fuzzy network and genetic algorithms (GAs). In both cases, GAs tune a conventional PSS on different operating conditions and then, the relationship between these points and the PSS parameters is learned by the ANFIS. ANFIS will select the PSS parameters based on machine loading conditions. The first stabilizer is adjusted minimizing an objective function based on ITAE index, while second stabilizer is adjusted minimizing an objective function based on pole-placement technique. The proposed stabilizers have been tested by performing simulations of the overall nonlinear system. Preliminary experimental results are shown.     

Efficient solutions for Mastermind using genetic algorithms

We present a new genetic algorithm for playing the game of Mastermind. The algorithm requires low run-times and results in a low expected number of guesses. Its performance is comparable to that of other meta-heuristics for the standard setting with four positions and six colors, while it outperforms the existing algorithms when more colors and positions are examined. The central idea underlying the algorithm is the creation of a large set of eligible guesses collected throughout the different generations of the genetic algorithm, the quality of each of which is subsequently determined based on a comparison with a selection of elements of the set.     

Leveraging saving-based algorithms by master-slave genetic algorithms

Saving-based algorithms are commonly used as inner mechanisms of efficient heuristic construction procedures. We present a general mechanism for enhancing the effectiveness of such heuristics based on a two-level genetic algorithm. The higher-level algorithm searches in the space of possible merge lists which are then used by the lower-level saving-based algorithm to build the solution. We describe the general framework and we illustrate its application to three hard combinatorial problems. Experimental results on three hard combinatorial optimization problems show that the approach is very effective and it enables considerable enhancement of the performance of saving-based algorithms.     

Sub-pixel mapping and sub-pixel sharpening using neural network predicted wavelet coefficients

Sub-pixel mapping and sub-pixel sharpening are techniques for increasing the spatial resolution of sub-pixel image classifications. The proposed method makes use of wavelets and artificial neural networks. Wavelet multiresolution analysis facilitates the link between different resolution levels. In this work a higher resolution image is constructed after estimation of the detail wavelet coefficients with neural networks. Detail wavelet coefficients are used to synthesize the high-resolution approximation. The applied technique allows for both sub-pixel sharpening and sub-pixel mapping. An algorithm was developed on artificial imagery and tested on artificial as well as real synthetic imagery. The proposed method resulted in images with higher spatial resolution showing more spatial detail than the source imagery. Evaluation of the algorithm was performed both visually and quantitatively using established classification accuracy indices.     

Decision trees and genetic algorithms for condition monitoring forecasting of aircraft air conditioning

Unscheduled maintenance of aircraft can cause significant costs. The machine needs to be repaired before it can operate again. Thus it is desirable to have concepts and methods to prevent unscheduled maintenance. This paper proposes a method for forecasting the condition of aircraft air conditioning system based on observed past data. Forecasting is done in a point by point way, by iterating the algorithm. The proposed method uses decision trees to find and learn patterns in past data and use these patterns to select the best forecasting method to forecast future data points. Forecasting a data point is based on selecting the best applicable approximation method. The selection is done by calculating different features/attributes of the time series and then evaluating the decision tree. A genetic algorithm is used to find the best feature set for the given problem to increase the forecasting performance. The experiments show a good forecasting ability even when the function is disturbed by noise.     

Motion fairing using genetic algorithms

In this paper, we solve the motion smoothing problem using genetic algorithms. Smooth motion generation is essential in the computer animation and virtual reality area. The motion of a rigid body in general consists of translation and orientation. The former is described by a space curve in three-dimensional Euclidean space while the latter is represented by a curve in the unit quaternion space. By adopting the geometric approach, the smoothness of both translation data and orientation data is measured from the strain energy perspective and a nonlinear optimization problem is formulated that aims to minimize the weighted sum of the strain-energy and the sum of the squared errors. A hybrid algorithm that combines genetic algorithms and local search schemes is deployed to solve this optimization problem and the experiments show that both smoothness and shape preservation of the resulting motion can be achieved by the proposed algorithm.     

Dynamic vehicle routing using genetic algorithms

Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic Vehicle Routing Problem (DVRP), new customer orders appear over time, and new routes must be reconfigured while executing the current solution. Montemanni et al. [1] considered a DVRP as an extension to the standard vehicle routing problem (VRP) by decomposing a DVRP as a sequence of static VRPs, and then solving them with an ant colony system (ACS) algorithm. This paper presents a genetic algorithm (GA) methodology for providing solutions for the DVRP model employed in [1]. The effectiveness of the proposed GA is evaluated using a set of benchmarks found in the literature. Compared with a tabu search approach implemented herein and the aforementioned ACS, the proposed GA methodology performs better in minimizing travel costs. Franklin T. Hanshar is currently a M.Sc. student in the Department of Computing and Information Science at the University of Guelph, Ontario, Canada. He received a B.Sc. degree in Computer Science from Brock University in 2005. His research interests include uncertain reasoning, optimization and evolutionary computation. Beatrice Ombuki-Berman is currently an Associate Professor in the Department of Computer Science at Brock University, Ontario, Canada. She obtained a PhD and ME in Information Engineering from University of The Ryukyus, Okinawa, Japan in 2001 and 1998, respectively. She received a B.Sc. in Mathematics and Computer Science from Jomo Kenyatta University, Nairobi, Kenya. Her primary research interest is evolutionary computation and applied optimization. Other research interests include neural networks, machine learning and ant colony optimization.     

Evolving dynamic Bayesian networks with Multi-objective genetic algorithms

A dynamic Bayesian network (DBN) is a probabilistic network that models interdependent entities that change over time. Given example sequences of multivariate data, we use a genetic algorithm to synthesize a network structure that models the causal relationships that explain the sequence. We use a multi-objective evaluation strategy with a genetic algorithm. The multi-objective criteria are a network's probabilistic score and structural complexity score. Our use of Pareto ranking is ideal for this application, because it naturally balances the effect of the likelihood and structural simplicity terms used in the BIC network evaluation heuristic. We use a basic structural scoring formula, which tries to keep the number of links in the network approximately equivalent to the number of variables. We also use a simple representation that favors sparsely connected networks similar in structure to those modeling biological phenomenon. Our experiments show promising results when evolving networks ranging from 10 to 30 variables, using a maximal connectivity of between 3 and 4 parents per node. The results from the multi-objective GA were superior to those obtained with a single objective GA. Brian J. Ross is a professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his M.Sc. at the University of British Columbia, Canada, in 1988, and his Ph.D. at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, language induction, concurrency, and logic programming. He is also interested in computer applications in the fine arts. Eduardo Zuviria received a BS degree in Computer Science from Brock University in 2004 and a MS degree in Computer Science from Queen's University in 2006 where he held jobs as teacher and research assistant. Currently, he is attending a Ph.D. program at the University of Montreal. He holds a diploma in electronics from a technical college and has worked for eight years in the computer industry as a software developer and systems administrator. He has received several scholarships including the Ontario Graduate Scholarship, Queen's Graduate Scholarship and a NSERC- USRA scholarship.     

Rules extraction from constructively trained neural networks based on genetic algorithms

The application of neural networks in the data mining has become wider. Although neural networks may have complex structure, long training time, and the representation of results is not comprehensible, neural networks have high acceptance ability for noisy data, high accuracy and are preferable in data mining. On the other hand, It is an open question as to what is the best way to train and extract symbolic rules from trained neural networks in domains like classification. In this paper, we train the neural networks by constructive learning and present the analysis of the convergence rate of the error in a neural network with and without threshold which have been learnt by a constructive method to obtain the simple structure of the network.The response of ANN is acquired but its result is not in understandable form or in a black box form. It is frequently desirable to use the model backwards and identify sets of input variable which results in a desired output value. The large numbers of variables and nonlinear nature of many materials models that can help finding an optimal set of difficult input variables. We will use a genetic algorithm to solve this problem. The method is evaluated on different public-domain data sets with the aim of testing the predictive ability of the method and compared with standard classifiers, results showed comparatively high accuracy.     

Feature selection by genetic algorithms in object-based classification of IKONOS imagery for forest mapping in Flanders, Belgium

Obtaining detailed information about the amount of forest cover is an important issue for governmental policy and forest management. This paper presents a new approach to update the Flemish Forest Map using IKONOS imagery. The proposed method is a three-step object-oriented classification routine that involves the integration of 1) image segmentation, 2) feature selection by Genetic Algorithms (GAs) and 3) joint Neural Network (NN) based object-classification. The added value of feature selection and neural network combination is investigated. Results show that, with GA-feature selection, the mean classification accuracy (in terms of Kappa Index of Agreement) is significantly higher (p < 0.01) than without feature selection. On average, the summed output of 50 networks provided a significantly higher (p < 0.01) classification accuracy than the mean output of 50 individual networks. Finally, the proposed classification routine yields a significantly higher (p < 0.01) classification accuracy as compared with a strategy without feature selection and joint network output. In addition, the proposed method showed its potential when few training data were available.     

Time series prediction using evolving radial basis function networks with new encoding scheme

This paper presents a new encoding scheme for training radial basis function (RBF) networks by genetic algorithms (GAs). In general, it is very difficult to select the proper input variables and the exact number of nodes before training an RBF network. In the proposed encoding scheme, both the architecture (numbers and selections of nodes and inputs) and the parameters (centres and widths) of the RBF networks are represented in one chromosome and evolved simultaneously by GAs so that the selection of nodes and inputs can be achieved automatically. The performance and effectiveness of the presented approach are evaluated using two benchmark time series prediction examples and one practical application example, and are then compared with other existing methods. It is shown by the simulation tests that the developed evolving RBF networks are able to predict the time series accurately with the automatically selected nodes and inputs.     

Adaptive reconfiguration of data networks using genetic algorithms

Genetic algorithms are applied to an important, but little investigated, network design problem, that of reconfiguring the topology and link capacities of an operational network to adapt to changes in its operating conditions. These conditions include: which nodes and links are unavailable; the traffic patterns; and the quality of service (QoS) requirements and priorities of different users and applications. Dynamic reconfiguration is possible in networks that contain links whose endpoints can be easily changed, such as satellite channels, terrestrial wireless connections, and certain types of optical connections. We report preliminary results that demonstrate the feasibility of performing genetic search quickly enough for online adaptation.     

Tissue segmentation in ultrasound images by using genetic algorithms

This paper presents a genetic based incremental neural network (GINeN) for the segmentation of tissues in ultrasound images. Performances of the GINeN and the Kohonen network are investigated for tissue segmentation in ultrasound images. Feature extraction is carried out by using continuous wavelet transform. Pixel intensities at the same spatial location on 12 wavelet planes and on the original image are considered as features, leading to 13-dimensional feature vectors. The same training set is used for the training of the Kohonen network and the GINeN.

This paper proposes the use of wavelet transform and genetic based incremental neural network together in order to increase the segmentation performance. It is observed that genetic based incremental neural network gives satisfactory segmentation performance for ultrasound images.     

Extraction and reuse of design patterns from genetic algorithms using case-based reasoning

In this paper, we propose a case-based reasoning scheme in which we extract domain knowledge (in the form of design patterns) from a genetic algorithm used to optimize combinational logic circuits at the gate level. Such information is used in two ways: first, we show how the selection pressure of the genetic algorithm is biased by Boolean simplification rules that are normally adopted by human designers, including some which are not completely straightforward. Secondly, we reuse some of these design patterns extracted from the evolutionary process to reduce convergence times of a genetic algorithm using previously found solutions as cases to solve similar problems.The second author acknowledges support from CONACyT through project No. 32999-A. The third author acknowledges partial support for this work through CONACyT Project No. I-39324-A.