Skip to main content
main-content

Über dieses Buch

Artificial neural networks and genetic algorithms both are areas of research which have their origins in mathematical models constructed in order to gain understanding of important natural processes. By focussing on the process models rather than the processes themselves, significant new computational techniques have evolved which have found application in a large number of diverse fields. This diversity is reflected in the topics which are subjects of the contributions to this volume. There are contributions reporting successful applications of the technology to the solution of industrial/commercial problems. This may well reflect the maturity of the technology, notably in the sense that 'real' users of modelling/prediction techniques are prepared to accept neural networks as a valid paradigm. Theoretical issues also receive attention, notably in connection with the radial basis function neural network. Contributions in the field of genetic algorithms reflect the wide range of current applications, including, for example, portfolio selection, filter design, frequency assignment, tuning of nonlinear PID controllers. These techniques are also used extensively for combinatorial optimisation problems.

Inhaltsverzeichnis

Frontmatter

Workshop Summary

Workshop Summary

EMA-EERIE, Nîmes, France, April 18, 1995

The conference was preceded by a one day workshop. The morning was devoted to neural networks and the afternoon to genetic algorithms. General introductions, theoretical and implementational issues and specific applications were presented to the participants. We include here a brief summary of each workshop.

David W. Pearson, Nigel C. Steele, Rudolf F. Albrecht

Invited Talk

Kohonen Neural Networks for Machine and Process Condition Monitoring

Kohonen feature map neural networks have been used for a variety of successful applications since their introduction in the late eighties. They have one major advantage over their more common peers in that they are capable of unsupervised learning. This property makes them ideal for machine health monitoring situations.Unsupervised learning allows the network to represent single or multiple classes according to distribution and density. Novelty detection is then possible on-line or classes can be labelled to give diagnosis. This presentation explains the special nature of machine monitoring applications in data availability and desired diagnosis information and provides examples of such systems working in different environments.

Tom Harris

Plenary Session

Process Modelling and Control with Neural Networks: Present Status and Future Directions

Even though there exist numerous traditional approaches for solving nonlinear control tasks their realization in practice often proves to be difficult, mainly because of i) insufficient analytical knowledge of the system to be controlled, and ii) because of incomplete knowledge of the physical parameters of the system.Neural networks can cope with these problems because of their capability to realize multivariate, nonlinear transformations and to learn these merely by empirical information, i.e. by representative training examples (data driven modeling).In this contribution we discuss neural methods for modeling and control and illustrate their use in real world applications. In order to improve the corresponding conventional solutions, it is crucial to i) incorporate prior knowledge (analytical and/or rule based) into the neural network and ii) to optimize its architecture by refined learning methods. We point out the future need for neural control of the complete process rather than controlling its parts independently.Further, we discuss the necessity to combine neural methods with the modern techniques of Nonlinear Dynamics for the modeling and control of processes with highly nonlinear dynamic behavior.

Bernd Schürmann

Classification

A Genetic Algorithm for Multicriteria Inventory Classification

One of application areas of the genetic algorithms is parameter optimization. This paper addresses the problem of optimizing a set of parameters that represent the weights of criteria, where the sum of all weights is 1. A chromosome represents the values of the weights, possibly along with some cut-off points. A new crossover operation, called continuous uniform crossover, is proposed, such that it produces valid chromosomes given that the parent chromosomes are valid. The new crossover technique is applied to the problem of multicriteria inventory classification. The results are compared with the classical inventory classification technique using Analytical Hierarchy Process.

H. Altay Güvenir

Optimizing Classifiers for Handwritten Digits by Genetic Algorithms

We present the first large real-world application for the neural network optimizing genetic algorithm Enzo. Nets had several thousands links and the training data up to over 200,000 patterns. We evolved nets for a classification task that have an order of magnitude free parameters less than commonly used polynomial classifiers while maintaining the same performance.To achieve this we implemented some significant enhancements and minor improvements of the original algorithm.It is also shown how to use Enzo as an efficient tool to create nets satisfying task-specific constraints.

J. Schäfer, H. Braun

DCS: A Promising Classifier System

A classifier system is a machine learning system that learns syntactically simple string rules called classifiers. Such systems combine learning and evolution processes. The Bucket Brigade algorithm implements the first one, while the second one often use a genetic algorithm. Unfortunately, this kind of genetics-based machine learning systems suffers from a lot of problems yielding system instability, often resulting in poor performance. The main difficulty consists in maintaining good classifiers in the population during the evolution process.

Philippe Collard, Cathy Escazut

Application of neural networks for classification of temperature distribution patterns

Classification of spatially distributed measurements in industrial processes is an important but difficult task. Interpretation of the signals from horizontal probes in blast furnaces is a typical example. A neural network-based classification of such temperature measurements is described in this paper. Using temperature profiles first classified by the team, training and test sets were formed, and feedforward neural networks of different size were trained and evaluated on the material. The network size was found to clearly affect the quality of the classifications. By a judicious choice of the number of hidden nodes, a reliable neural classifier was obtained, which was incorporated in a supervision and control system for a Finnish blast furnace.

Henrik Saxén, Abhay Bulsari, Leif Karilainen, Kalevi Raipala

Genetic Algorithms and Combinatorial Optimisation

Combination of Genetic Algorithms and CLP in the Vehicle-Fleet Scheduling Problem

Constraint Logic Programming (CLP) is a technique which presents several advantages in dealing with combinatorial optimization problems as it combines the declarative aspects of Logic Programming with the efficiency of Constraint Techniques. However, the attempts to solve the Vehicle Scheduling Problem (VSP) through the application of CLP[1] has not been successful, due to the huge complexity of the problem and the scarcity of constraints able to drive the solution.This paper presents a new approach to the problem which attempts to combine the advantages of CLP with the benefits of Genetic Algorithms in order to obtain satisfactory results with respect to execution time and solution quality.

E. Stefanitsis, N. Christodoulou, J. Psarras

Minimum Cost Topology Optimisation of the Cost 239 European Optical Network

A genetic algorithm is presented for the minimum-cost topology optimisation of the COST 239 European Optical Network (EON). The algorithm makes use of real traffic data where possible, and produces a network amongst twenty given nodes with two-shortest-node-disjoint routing between node pairs. Both routes are fully resourced, guaranteeing the network will survive a single component failure. The results are compared with the earlier ‘hand-crafted’ EON topology.

M. C. Sinclair

Timetabling Using Genetic Algorithms

This paper is concerned with the automated construction of timetables for a university. Timetabling essentially involves the assignment of course modules to periods and lecture rooms. It is a class of scheduling problems which is highly constrained. Several approaches including graph-theoretic and heuristic methods have been applied to it in the past. The timetabling system presented in this paper is based on Genetic Algorithms techniques. Hence it aims not only at finding a feasible solution to the problem; a timetable produced should also be of good quality, i.e. satisfy as many secondary constraints as possible. A corresponding objective function, and a Genetic Algorithm using problem-specific chromosome representations and operators have been developed and implemented in C and PROLOG. Testing was begun in a real-life environment with promising results.

Wilhelm Erben

Resolution of Cartographic Layout Problem by Means of Improved Genetic Algorithms

In this paper, a system for spatial layout and its application to cartographic domain is proposed. Genetic algorithms have been used as a way to deal with several kinds of constraints (fuzzy and Boolean), by means of the fitness function.When a representation other than bit strings is used, it is often necessary to redefine the genetic operators. This led us to consider specific mutation and crossover operators. Specific probabilities are also needed in order to realise the combined goals of maintaining diversity in the population and sustaining the convergence capacity of the resolution process. Mutation process needs probabilistic model and is performed by means of the Gibbs-Boltzman probability. In this way, our system profits by the simulated annealing efficiency. This mixed method permits to examine solutions space without falling into a local minimum. The search process decreases a fitness function. This function describes the sum of costs inherent to different constraints. In order to explore entirely the solutions space, crossover process has been set up using adaptive probability. This probability varies during the resolution process. This variation is defined in order to process all regions of the cartographic map considering that, mutation operator is more dedicated to a given region of the map.

Yassine Djouadi

Using Genetic Algorithms to Solve the Radio Link Frequency Assignment Problem

The Radio Link Frequency Assignment Problem (RLFAP) is that of assigning frequencies to a number of radio links in such a manner as to simultaneously satisfy a large number of constraints and use as few distinct frequencies as possible. This problem is known to be NP-complete. We describe the application of a genetic algorithm to the solution of the RLFAP. The standard crossover operators were found to be of limited use due to the highly epistatic nature of the problem and a range of new (crossover and mutation) operators are described. Dynamically modifying the weights used in the fitness function has also proved to be effective in improving the performance of the standard genetic algorithm. This work is being undertaken as part of the EUCLID CALMA Project - RTP 6.4, Combinatorial Algorithms for Military Applications.

A. Kapsalis, V. J. Rayward-Smith, G. D. Smith

Learning and Training

A Transformation for Implementing Efficient Dynamic Backpropagation Neural Networks

Most Artificial Neural Networks (ANNs) have a fixed topology during learning, and often suffer from a number of short-comings as a result. Variations of ANNs that use dynamic topologies have shown ability to overcome many of these problems. This paper introduces Location-Independent Transformations (LITs) as a general strategy for implementing distributed feedforward networks that use dynamic topologies (dynamic ANNs) efficiently in parallel hardware. A LIT creates a set of location-independent nodes, where each node computes its part of the network output independent of other nodes, using local information. This type of transformation allows efficient support for adding and deleting nodes dynamically during learning. In particular, this paper presents an LIT for standard Backpropagation with two layers of weights, and shows how dynamic extensions to Backpropagation can be supported.

George L. Rudolph, Tony R. Martinez

AA1*: A Dynamic Incremental Network that Learns by Discrimination

An incremental learning algorithm for a special class of self-organising, dynamic networks is presented. Learning is effected by adapting both the function performed by the nodes and the overall network topology, so that the network grows (or shrinks) over time to fit the problem. Convergence is guaranteed on any arbitrary Boolean dataset and empirical generalisation results demonstrate promise.

Christophe Giraud-Carrier, Tony Martinez

Non-Supervised Sensory-Motor Agents Learning

This text discusses a proposal for creation and destruction of neurons based on the sensory-motor activity. This model, called sensory-motor schema, is used to define a sensory-motor agent as a collection of activity schemata. The activity schema permits a useful distribulion of neurons in a conceptual space, creating concepts based on action and sensation. Such approach is inspired in the theory of the Swiss psychologist and epistemologist Jean Piaget, and intends to make explicit the account of the processes of continuous interaction between sensory-motor agents and their environments when agents are producing cognitive structures.

Raul Sidnei Wazlawick, Antonio Carlos da Rocha Costa

Functional Equivalence and Genetic Learning of RBF Networks

In this paper a functional equivalence property of feedforward networks is introduced and studied for the case of radial basis function networks with Gaussian activation function and metrics induced by an inner product. The description of functional equivalent parameterizations is used for proposition of new genetic learning rules that operate only on a small part of the whole weight space.

Roman Neruda

Teaching Relaxation Labeling Processes Using Genetic Algorithms

In a recent work, a learning procedure for relaxation labeling algorithms has been introduced which involves minimizing a certain cost function with classical gradient methods. The gradient-based learning algorithm suffers from some inherent drawbacks that could prevent its application to real-world problems of practical interest. Essentially, these include the inability to escape from local minima and its computational complexity. In this paper, we propose using genetic algorithms to solve the relaxation labeling learning problem to overcome the difficulties with the gradient algorithm. Experiments are presented which demonstrate the superiority of the proposed approach both in terms of quality of solutions and robustness.

Marcello Pelillo, Fabio Abbattista, Angelo Maffione

VLSI Optimal Neural Network Learning Algorithm

In this paper we consider binary neurons having a threshold nonlinear transfer function and detail a novel direct design algorithm as an alternative to the classical learning algorithms which determines the number of layers, the number of neurons in each layer and the synaptic weights of a particular neural network. While the feedforward neural network is described by m examples of n bits each, the optimisation criteria are changed. Beside the classical size-and-depth we also use the A and the AT2 complexity measures of VLSI circuits (A being the area of the chip, and T the delay for propagating the inputs to the outputs). We considering the maximum fan-in of one neuron as a parameter and proceed to show its influence on the area, obtaining a full class of solutions. Results are compared with another constructive algorithm. Further directions for research are pointed out in the conclusions, together with some open questions.

Valeriu Beiu, John G. Taylor

Applications in Biology and Biotechnology

Using of Neural-Network and Expert System for Imissions Prediction

The result of our analysis is oriented to the formation of a warning system by the prediction of the concentration of suphure dioxide (SO2) on the basis of a hydrometeorological forecast. The analysis carried out in this study is based on the application of neural nets (NN) and expert system (ES) methodology The prediction is made by putting to use both NN and ES in the form of an integrated system.

E. Theocharidou, Z. Burianec

The Costing of Process Vessels Using Neural Networks

A set of commercial data relating physical dimensions and materials to the purchase cost of simple process vessels has been analysed using multilinear regression and artificial neural networks. The ability of each of these approaches to estimate purchase cost is compared with a third method which combines elements of the first two.

M. Leck, P. Bromley, D. Peel, A. M. Gerrard

Neural Network Modelling of Fermentation Taking into Account Culture Memory

In the present paper the problem of chemostat modelling using the neural networks is considered. Two kinds of neural network models taking into account the culture memory are proposed. The first one is a feedforward neural network with time delayed feedback connections from and to the output neurons. The second one is a feedforward neural network with time delayed feedback connections from the input neurons describing only the specific growth rate. The obtained neural network model is adopted in the classical nonlinear model. Simulation investigations and comparison of the both models are carried out. The interpretation of the parameters according to their biological means is made.

P. Koprinkova, M. Petrova, T. Patarinska

Brain Electrographic State Detection Using Combined Unsupervised and Supervised Neural Networks

This work describes the development of a new approach to NN processing of sleep-related brain electrographic signals, using two sequentially combined unsupervised (Kohonen layer, KNN) and supervised (Widrow-Hoff layer, WHNN) algorithms. Twelve parameters extracted from physiological data (EEG, EMG and EOG, obtained from unrestrained rats through several sleep-waking periods), were first processed by a KNN, that detected different signal patterns. These patterns were further examined by an EEG expert, who identified them as belonging to one of the known sleep-waking stages, or to transitional and/or unknown signal combinations. Selected outputs of the KNN, classified in this way, formed the input vectors to a WHNN, that allowed fast and reliable tracking of changes in these states (both known and newly detected) during prolonged periods of time. Such an approach can represent an important aid for simultaneous exploration, detection and also temporal following of electrographic events along the sleep-waking cycle.

A. J. F. Coimbra, J. Marino-Neto, F. M. de Azevedo, C. G. Freitas, J. M. Barreto

Genetic and Neural Theory Combined

From the Chromosome to the Neural Network

A proposal for a model of morphogenesis process taking inspiration from biology is presented in this paper. This process uses a chromosome as a production system to create an artificial neural network. It starts with a single cell containing the chromosome. Cells can divide and establish connections among them. Both structure and weights of the neural network are defined by the morphogenesis process. An application to a neural network driving an autonomous mobile robot is presented which exhibits encouraging first results.

Olivier Michel, Joëlle Biondi

CAM-Brain

The Evolutionary Engineering of a Billion Neuron Artificial Brain by 2001 which Grows/Evolves at Electronic Speeds inside a Cellular Automata Machine (CAM)

A “Darwin Machine” is defined to be a piece of hardware that evolves its own architecture at electronic speeds. A Darwin Machine is an example of “Evolutionary Engineering”, which in turn is defined to be the building of complex structures and dynamics using evolutionary methods. The author believes that evolutionary techniques will dominate 21st century engineering, especially molecular scale (nanotech) engineering, with its gargantuan number of components and complexities. This paper reports on the second year of an ambitious 8 year research project which aims to implement a type of Darwin Machine in the form of a cellular automata based artificial brain with a billion neurons by 2001, which grows/evolves at (nano-)electronic speeds inside a Cellular Automata Machine — ATR’s so-called “CAM-Brain Project”. The basic idea is to use cellular automata based neural networks which grow under evolutionary control at (nano-)electronic speeds. The states of the cellular automata (CA) cells and the CA state transition rules can be stored cheaply in gigabytes of RAM. By using state of the art cellular automata machines, e.g. MIT’s “CAM8” machine ($40,000), which can update 200 million CA cells a second, it may be technically feasible within a year or so to evolve artificial nervous systems containing a thousand neurons, and within 5 years, a million neurons. By the end of the current research project, i.e. 2001, it should be possible using nano-scale electronics to grow/evolve artificial brains containing a billion neurons and upwards. This is our aim.

Hugo de Garis

A Perfect Integration of Neural Networks and Evolutionary Algorithms

Evolutionary computation techniques need to interact with a fitness function or an objective function for the selection to be made properly. In cases objective functions are not well defined, evolutionary algorithms may not be able to perform properly. In this paper, we propose to use a well-trained neural network model to provide estimates of objective values at points that we have not experienced to support the selection process of the evolutionary algorithm. An example of gasoline blending task is used to demonstrate that such an integrated system functions as a powerful tool for product design.

Percy P. C. Yip, Yoh-Han Pao

g-lvq, a combination of genetic algorithms and lvq

One of the ultimate goal in neural network research is the complete optimization of a neural network: topology, learning algorithm, initial weights and number of neurons. Up to now, only partial solutions have been found. This optimization should look at two conditions if the task assigned to the NN is going to be classification: accuracy, and obtention of a good representation of the sample. lvq neural nets are a supervised classification algorithms created by Kohonen. In this work, lvq NNs will be optimized using a GA according to three criteria: accuracy, net size and distortion. These three criteria are considered a vector fitness with three components that must be optimized separately. In order to carry this out, variable-length genomes are used to represent the neural network; each neuron is codified together with its label. Results in synthetic and real-world problems show that g-lvq is able to find an optimal size of the network, as well as combinations of weights that maximize classification accuracy.

J. J. Merelo, A. Prieto

Evolving Neural Network Structures: An Evaluation of Encoding Techniques

Feed-forward neural network structures, trained with back-propagation, are adapted by the use of the genetic algorithm (GA). Through this search technique problem specific topologies are found. The method used to represent network structure, in a form suitable for the GA, is investigated. Comparisons are made between three such encoding methods. Details are given of how these representational schemes can influence the performance of both the genetic algorithm and the resultant neural networks found by the GA.

Stephen G. Roberts, Mike Turega

Failure Detection and Identification

Application of Radial Basis Function Networks to Fault Diagnosis for a Hydraulic System

Faults in a hydraulic test rig are detected and isolated by using two radial basis function networks (RBF). One RBF is used to model the test rig according to its nonlinear structure. The output prediction error, generated from the real responses and the model responses, is used as a residual to indicate the occurence of any fault. A second RBF is used to enhance the effect of an individual fault while reducing the effects of the other faults, in such a way that the fault is isolated. Simulation using real data collected from the rig demonstrates the effectiveness of this method.

Dingli Yu, D. N. Shields, S. Daley

Optimally Robust Fault Diagnosis Using Genetic Algorithms

A new fault isolation method is proposed using state space parity equations and genetic algorithms and is deemed superior to a previous method proposed by the authors. Faults are isolated by making a residual vector zero for a particular individual fault and significantly non-zero for other faults. This method uses genetic algorithms to minimise the effect of a particular fault on the residuals in the presence of the unknown inputs and to maximise the effect for other faults. A real data simulation on a hydraulic test rig is performed to demonstrate the effectiveness of the method.

Dingli Yu, D. N. Shields

Development of a Neural-based Diagnostic System to Control the Ropes of Mining Shifts

Although the application of neural networks in quality control and maintenance is growing quickly from last years, they are just an incipient technology in the Mining Industry. At the same time, maintenance of the shift is probably the most important matter in Mining, considering that the shift could be the only way out for people and material in a colliery.The Area of Project Engineering of the University of Oviedo has designed a system to control the state of the wire ropes for extraction in coal shifts, based on the information supplied by three groups of electromagnetic sensors (Inductive and Hall-Effect) placed in a head around the rope when inspection is carried out.The system involves the use of three parallel neural subnetworks which output is introduced in common final layers to be definitely classified. This system allows to detect internal broken wires and to prevent more serious defects before they occur, in such a way that the rope can be maintained in service during a longer period of time, with the necessary equilibrium between security, reliability and economy. If this system is placed permanently on the shift, the risk of unexpected failure of the wire rope should be decreased to the minimum.

F Ortega, J. B Ordieres, C Menéndez, C. González Nicieza

Lime Kiln Fault Detection and Diagnosis by Neural Networks

Artificial neural networks have recently been used successfully for fault detection and diagnosis in chemical processes. In this paper, we present a study on fault detection and diagnosis of an industrial lime kiln which is a complex highly nonlinear process within the pulp and paper industry. We show the capability of neural networks to learn faults which can occur during steady state kiln operation, their adaptation to different input distributions involving nonlinear mappings and their capability to spontaneously generalize. We compare the performance of two architectures, nameley BPNN (Back Propagation Neural Network) and RBFNN (Radial Basis Function Neural Network), and investigate several topologies. Through this study, it can be concluded that the RBFNN arquitecture learns faster, with less error and performs better at classifying kiln malfunctions.

B Ribeiro, E Costa, A Dourado

Investigations into the Use of Wavelet Transformations as Input into Neural Networks for Condition Monitoring

Condition monitoring has become widely accepted in industry, with vibration providing the most useful condition parameter. Analysis of these vibration signals usually involves Fourier transforms and, occasionally, neural networks. However, a problem when using Fourier transforms as input into a neural network is the size of the input data set. Wavelet transforms provide an alternative which allows for a dramatic reduction in the size of the data set. This paper will explore the feasibility of using wavelet transforms as input into neural networks for condition monitoring.

J MacIntyre, J C O’Brien

Image, Motion and Recognition

Genetic Algorithm for Neurocomputer Image Recognition

Genetic algorithms for optimization of feature set and internal structure of neural networks are considered. Results of experimental investigation of genetic algorithms are given. Experiments show that performance of neural networks after such optimization substantially increases.

Ernst M. Kussul, Tatyana N. Baidyk

Feature Map Architectures for Pattern Recognition: Techniques for Automatic Region Selection

In the present paper we address several issues about data processing with Kohonen maps. First, this neural system and multidimensional scaling are compared. Next, several unsupervised techniques for delimiting domains on a Kohonen map are described. The different procedures are illustrated by using real-world data.

B. Martín-del-Brío, N. Medrano-Marqués, J. Blasco-Alberto

Adaptive Genetic Algorithms for Multi-Point Path Finding in Artificial Potential Fields

We present research work in progress into the use of adaptive genetic algorithms (AGAs) to search for collision-free paths in an artificial potential field (APF) representation of a cluttered robotic work-cell. We argue that the AGA approach promises to avoid the drawback of other APF approaches which are vulnerable to entrapment by local minima.

R. M. Rylatt, C. A. Czarnecki, T. W. Routen

Spatio-Temporal Mask Learning: Application to Speech Recognition

In this paper, we describe the “spatio-temporal” map which is an original algorithm to learn and recognize dynamic patterns represented by sequences. This work is slanted toward an internal and explicit representation of time which seems to be neuro-biologically relevant. The map involves units with different kinds of links: feed-forward connections, intra-map connections and inter-map connections. This architecture is able to learn sequences robust to noise from an input stream. The learning process is self-organized for the feed-forward links and “pseudo” self-organized for the intra-map links. An application to French spoken digits recognition is presented.

Stéphane Durand, Frédéric Alexandre

Artificial Neural Networks for Motion Estimation

This paper deals with the using of Artificial Neural Networks (ANN) for motion estimation. By means of simple neural structures it is possible to improve the reliability and accuracy of block matching algorithms (BMA) by a postprocessing of the similarity criterion. The ANN dimensions the appropriate structures. The fundamental idea and some first results will be described. The performance capability of the proposed method is shown for selected synthetic one- and real world two-dimensional measuring situations which are not solvable by means of conventional BMA.

Olaf Schnelting, Bernd Michaelis, Rüdiger Mecke

Advanced Neural Networks Methods for Recognition of Handwritten Characters

In this paper, we present the efficient voting classifier for the recognition of handwritten characters. This system consists of three voting nonlinear classifiers: two of them base on the multilayer perceptron, and one uses the moments method. The combination of these kinds of systems showed superiority of neural techniques applied with classical against exclusive traditional approach and resulted in high percentage of correctly recognized characters. Also, we present a comparison of the recognition results.

Sławomir Skoneczny, Jarosław Szostakowski

Genetic Algorithms Theory

The Use of a Variable Length Chromosome for Permutation Manipulation in Genetic Algorithms

Permutations are difficult to represent and manipulate as chromosomes in genetic algorithms. Simple crossover often yields illegal solutions, and repair mechanisms appear to be very disruptive. A new chromosome structure, the Variable Length Sequence (VLS), and associated operators have been developed. The rationale is that the crossover should guarantee that the resulting solution is legal, and that the effect of disruption should be reduced by the retention of genetic memory within the chromosome. VLS is applied to the travelling salesman problem (TSP), and the results compared with those obtained using the PMX and C1 operators. VLS out-performs the other operators over a wide range of parameters.

Phil Robbins

Theoretical Bounds for Genetic Algorithms

We investigate various properties of Genetic Algorithms. We present 1) a result which highlights the potential existence of long-run crossover and mutation bias in a GA, together with a partial avoidance strategy based on mutation operators, 2) an analysis of GA premature convergence, which indicates the advantage of larger populations, 3) an application of the theory of metric spaces which describes an intrinsic smoothness property of GA populations and highlights the safety in numbers principle and 4) a lower bound on the convergence rate of a mutation-crossover GA. The models presented are generally independent of solution encoding and are thus applicable to a wide range of Genetic Algorithms.

David Reynolds, Jagannathan Gomatam

An Argument Against the Principle of Minimal Alphabet

For many years the field of Genetic Algorithms (GAs) has been dominated by bit-string based GAs. The argument as to why bit-strings are the best method of encoding parameters in GA strings is known as the principle of minimal alphabet.

Gary M. Gibson

Heterogeneous Co-evolving Parasites

This paper investigates a development of Hillis’ co-evolving parasites scheme and looks at how it might be used for job-shop scheduling problems. It suggests that a problem defined by orthogonal constraints may be solved using multiple types of co-evolving parasite.Areas of specialisation permit the development of solutions specialised for certain constraints; overlaps of these areas create hybrids which combat multiple kinds of parasite and therefore provide solutions.The main advantage of such a technique is that it permits the use of an evolutionary approach without requiring the specification of a fitness function, which is problematic for many real-world problems.

J. Holmes, T. W. Routen, C. A. Czarnecki

Typology of Boolean Functions Using Walsh Analysis

Much previous works deal with the functions that cause a genetic algorithm (GA) to diverge from the global optimum. It is now a fact: Walsh analysis allows the identification of GA-hard problems. But what about genetics-based machine learning? Do we know what makes a problem hard for a classifier system (CS)? In order to try to answer these questions, we describe the relation between CS performance and the structure of a given boolean function when it is expressed as a Walsh polynomial. The analysis of the relative magnitude of Walsh coefficients allows us to set up a typology of boolean functions according to their hardness for a CS. Thus, each function can be placed in a specific class of difficulty. Using the converse process, we can start from well chosen Walsh coefficients in order to build boolean functions hard for a CS to learn.

Cathy Escazut, Philippe Collard

Neural Networks Theory

Artificial Neural Networks for Nonlinear Projection and Exploratory Data Analysis

Mapping scheme consists in projecting data samples represented as points in high-dimensional data space onto a subspace of few dimensions, generally two dimensions. Mapping methods are used in order to eliminate statistical redundancies in the original data set and to facilitate the visual inspection of the data by the analyst which discover clusters between the data samples. A feedforward neural network trained by means of an unsupervised backpropagation algorithm is used for the nonlinear mapping. The Sammon’s stress is used as an error function for the learning algorithm. The number of hidden units is related to the complexity of the nonlinear functions that can be generated by the network and is selected by means of an informational criterion. To provide some insight into the behavior of the interactive system, and to presents its main facilities, some results are reported.

Denis Hamad, Mohamed Betrouni

Generic Back-Propagation in Arbitrary FeedForward Neural Networks

In this paper, we describe a general mathematical model for feedforward neural networks. The final form of the network is a vectorial function f of two variables, x (the input of the network) and w (the weight vector). We show that the differential of f can be computed with an extended back-propagation algorithm or with a direct method. By evaluating the time needed to compute the differential with the help of both methods, we show how to chose the best one. We introduce also input sharing and output function which allow us to implement efficiently a multilayer perceptron with our model.

Cédric Gégout, Bernard Girau, Fabrice Rossi

From Prime Implicants to Modular Feedforward Networks

The paper utilises prime implicants and minimal polynomials in order to reduce the size of the training set of a neural feedforward network. We propose a heuristic in order to compute reduced polynomials which are often able to reduce the training set since the computation of minimal polynomials is intractable. Further abstractions lead to modular feedforward sub-architectures of neural networks for special training patterns. Finally, we introduce overlapping modular sub-architectures for distinct training patterns.

Uwe Hartmann

Hierarchical Backward Search Method: A New Classification Tree Using Preprocessing by Multilayer Neural Network

This paper proposes a novel pattern recognition algorithm. The new algorithm consists of two stages: the pyramid making stage and the classification making stage. The classification tree generated by the algorithm is called “PACT” (Pyramid Architecture Classification Tree), which is just a kind of classification tree but has a great ability to deal with huge dimensional real scale problem.PACT does not only shows good performance but also induces a new idea: a fractal characteristic which a category set shows in huge dimensional feature space. The new idea accounts for how awkward conventional algorithms, including neural networks and classification trees, are when applied to huge dimensional pattern classification problems. The new idea gives a new positive reason for hierarchical pattern processing.

Hiroto Yoshii

Adaptation Algorithms for 2-D Feedforward Neural Networks

The generalized weight adaptation algorithms presented in [6, 11] are extended for 2-D madaline and 2-D two-layer FNN’s.

Tadeusz Kaczorek

Selecting the Best Significant Fragment to the Incremental Heteroassociative Neural Network (RHI)

The generality of the artificial neural networks models infers the requests based in the totality of the characteristics of the patterns. The RHI model infers just with a limited set of this characteristics, the significant fragment. This reason make RHI really appropriated by resolution of control and active vision problem. Although RHI model present high sensibility to distortion. In this paper it is developed the formalism to obtain the significant fragment in such a way it improve the noise tolerance.

J. M. García Chamizo, R. Satorre Cuerda, F. Ibarra Picó, S. Cuenca Asensi

Image, Motion and Recognition

An Orthogonal Neural Network with Guaranted Recall by Iterative Filters and Its Application to Texture Discrimination

It is presented an orthogonal neural network which uses parallel iterative filters in its hidden layer. Orthogonality gives a high storage capacity of the network and its iterative filters get an accurate response. Also, this filters are implemented by a parallel process for getting a quick convergence time. As a simple example of application, we use it to learn several natural textures and its classification.

F. Ibarra-Picó, J. M. García-Chamizo, Rosana Satorre-Cuerda

Automatic Radar Target Identification Using Neural Networks

Automatic radar target identification is a very difficult task because data are very noisy and very few is known to decide which part of the signal is important. Identification techniques could help to build more efficient radars but also to better understand how this signal could be interpreted. We present here some connectionist techniques that have been tested on this task. They offer rather good identification rate but do not yet permit to understand the hidden structure of the signal.

Jean-François Remm, Frédéric Alexandre, Laurent Savy

Keystroke Dynamics Based User Authentication Using Neural Networks

We present a possible use of neural networks in the area of computer security. The back-propagation neural network is used to implement a prototype user authentication procedure using, capable to determine whether the user typing on the keyboard is valid. The obtained results are presented.

Roman Roštár, Jaroslav Olejár

Application of Learning to Learn to Real-World Pattern Recognition

Pattern recognition has for decades played an important role in the development of intelligent systems and numerous algorithms have been proposed to deal with this important task. Though much interest and research has been invested into the construction of advanced pattern recognition systems, almost all of these algorithms are incapable of meta-learning. These one-shot learning systems do not address the problem of automatic adaptation of learning bias and hence lack one of the most fundamental requirements inherent to any truly autonomous pattern recognition system: the ability to learn to learn. The purpose of this paper is to report the findings of an extensive empirical study (i.e., including 26 real-world data sets) involving a system capable of meta-learning. Statistically significant reductions in both network units and training time are observed when utilizing a multi-shot learning environment.

Steve G. Romaniuk

Quarry Aggregates: A Flexible Inspection Method Utilising Artificial Neural Networks

Close monitoring of particle size and shape is essential if today’s demanding material requirements for crushed rock aggregates are to be met.An intelligent mechatronic inspection system is described here. On-line product sampling directs aggregate through an inspection chamber where a novel imaging system digitises the particle geometry. Data processing algorithms extract dimensional data and image features, allowing an artificial neural network classifier to assign qualitative shape descriptors to each particle, thus providing each sampled batch with a breakdown of constituent particle size and shape distributions.

D W Calkin, R M Parkin

Genetic Algorithms Theory

An Evolution Model for Integration Problems

In this paper a general evolution model for integration problems is introduced and applied to the solution of the Rendering Equation which is a multidimensional integral equation modelling radiant light transfer. Often it is not possible to solve integral equations in a closed analytical form. Then an estimate for the integral has to be determined by numerical or stochastic approximation. Unfortunately stochastic integration techniques are extremely slow to converge. Numerical techniques are usually faster in convergence but their success strongly depends on function requirements. The evolution model presented here overcomes the disadvantages of these methods, i.e. loss of direction and missing innovation. It is far more flexible and produces reliable estimates even in the presence of multimodal integrands. Furthermore it provides a general framework for the description of a wide variety of adaptive sampling techniques.

Brigitta Lange

Convergence of Algorithm and the Schema Theorem in Genetic Algorithms

In this article two aspects of GA are commented from a mathematical point of view. One is concerned with the convergence of GA, and the other is a probabilistic interpretation of the schema theorem. GA produces a stochastic process (that is, Markov chain) of populations. A week sufficient condition which guarantees the convergence to a unique stable distribution will be given which is satisfied by a wide range of current GA. On the other hand, the inequality appeared in the Schema Theorem is not possible to be interpreted from a probabilistic point of view without replacing those random variables by their expectations since the theorem includes random variables. This replacement unfortunately prevents the theorem from being true, and hence it is forced to be revised. Two types of the correct versions of the schema theorem will be given after a rigorous derivation based on a probability theory.

Yoshinori Uesaka

Incorporating Neighbourhood Search Operators Into Genetic Algorithms

In this paper an abstract genetic algorithm (GA) is proposed which effectively merges local hill-climbing with recombination and population based selection in a general manner. This extension is possible because the traditional crossover can be resolved into two functions: one function is as a particular class of operator, which is actually distinct from the other which is the recombination itself. Thus traditional GAs can be classified as a special case of a more general approach in which recombination is applied along with other operators. In the work reported here, using the framework of an abstract GA, the performance of several operators as well as the effects of recombination are studied in the context of the graph bipartitioning problem.

Christian Höhn, Colin Reeves

Automatic Change of Representation in Genetic Algorithms

In the areas of Genetic Algorithms, Artificial Life and Animats, genetic material is often represented as a fixed size sequence of genes with alleles of 0 and 1. This is in accord with the ‘principle of meaningful building blocks’. The principle suggests that epistatically related genes should be positioned very close to one another. However, in situations in which gene dependency information cannot be determined a priori, a Genetic Algorithm that uses a static, list chromosome structure will often not work. The problem of determining gene dependencies is itself a search problem, and seems well suited for the application of a Genetic Algorithm. In this paper, we propose a self-organizing Genetic Algorithm, and, after describing four different chromosome representations, show that the best one for a Genetic Algorithm to use to coevolve the organization and contents (gene dependencies and values) of a chromosome is a hierarchy.

Franz Oppacher, Dwight Deugo

Dominant Takeover Regimes for Genetic Algorithms

The genetic algorithm (GA) is a machine-based optimization routine which connects evolutionary learning to natural genetic laws [1–2]. The present work addresses the problem of obtaining the dominant takeover regimes in the GA dynamics. Estimated GA run times are computed for slow and fast convergence in the limits of high and low fitness ratios. Using Euler’s device for obtaining partial sums in closed forms, the result relaxes the previously held requirements for long time limits. Analytical solutions reveal that appropriately accelerated regimes can mark the ascendancy of the most fit solution. In virtually all cases, the weak (logarithmic) dependence of convergence time on problem size demonstrates the potential for the GA to solve large N-P complete problems.

David Noever, Subbiah Baskaran

Interactve Evolutionary Algorithms in Design

Interactive Evolutionary Algortihms use the judgment of a human user as the fitness or objective function in a genetic search. Most approaches to interactive evolution take advantage of the human capability to instantly grasp the value, usefulness or beauty of images. The human fantasy and creativity is supported by the genetic operators of recombination and mutation. Artificial evolution can thus serve as a useful tool for achieving flexibility and complexity in constructive synthesis applications, with a moderate amount of user-input and detailed knowledge. In this paper we investigate the novel idea of using operators related to warping and morphing techniques as evolutionary operators in an image search space. We also present the IDEA system, an interactive X-window tool, a tool for interactive evolution of bitmap images. Our main interest is in the evolution of design pictures, which we examplify with, the design of cars and houses.

Jeanine Graf

Neural Networks Theory

Decrypting Neural Network Data: A Gis Case Study

The problem of data encoding for training back-propagation neural networks is well known. The basic principle is to avoid encrypting the underlying structure of the data. This is not easy in the real world, where we often receive data which has been processed by at least one previous user. The data may contain too many instances of some class, and too few instances of other classes. Then topology, and parameters settings designed. Finally, the network produces some results which need to be explained, or decrypted.We present our experience and results on some satellite data augmented by a terrain model. The task was to predict the forest supra-type based on the available information. In this process we were forced to invent some methods to deal with very large amounts of erratically reliable data, and to produce meaningful predictions at the end.

R. A. Bustos, T. D. Gedeon

A Framework for Creating Societies of Agents

The ADN project constitutes a generic tool for the analysis and development of distributed intelligent agents. The introduction presents the impetus driving ADN as well as a brief history of the project. Next, the parallel between cognitive psychology and the knowledge modeling architecture are laid open. A brief description of ADN’s functionalities is also presented.

Jean-François Arcand, Sophie-Julie Pelletier

Adaptive Scaling of Codebook Vectors

In this paper we introduce a vector quantization algorithm in which the codebook vectors are extended with a scale parameter to let them represent Gaussian functions. The means of these functions are determined by a standard vector quantization algorithm; and for their scales we have derived a learning rule. Our algorithm estimates probability densities efficiently. The main application is pattern classification.

S. Haring, J. N. Kok

Bias Estimation for Neural Network Predictions

This paper looks at the problem of performance assessment in the use of neural networks for classification tasks. It is well-known that the prediction obtained from a trained neural network is subject to errors, both in terms of bias and variance in the estimated error rate.In order to estimate these measures, it is customary to reserve some data as a test set. This is reasonable if data are plentiful, but when the data set is small in size, this is likely to reduce the accuracy of the network estimates, simply because there are not enough data left for adequate training. An alternative approach will allows the use of all the data, is to employ the bootstrap method.Here we give a brief introduction to the bootstrap, and then report on some computational experiments on artificial data sets in order to investigate the potential of this approach for the estimation of error bias.

Colin R Reeves

ANN Realizations of Local Approximations Schemes

Some schemes of the local approximation (LA) of functions defined on multidimensional space are described. For the simplest variants, namely, for the space filtration scheme and Nadraja-Watson scheme, the approximation precision is estimated. It is shown that ANN based on LA can solve the approximation problem with a good precision if the space dimension is moderate and some special elements are used.

A. A. Pervozvanskii

Changing Network Weights by Lie Groups

In this paper we investigate how stability properties of a continuous recursive neural network within neighbourhoods of certain equilibrium points can be changed whilst keeping the equilibrium points fixed. This can be achieved, under certain conditions, by the use of Lie group transformations operating on the synaptic weight matrix.

David W. Pearson

TIme Series, Sequences and Filters

Unsupervised Learning of Temporal Sequences by Neural Networks

We propose to define a new model of formal neural network. This model extends existing Hopfield networks to process temporal data and achieve a non-supervised learning of them. We propose a learning law to adress in this context the sensitivity to input changes. A spatial representation of network’s temporal activity is given by which learnt sequences can be identified. An example of such a network is given and the results of the simulation are presented.

B. Gas, R. Natowicz

Multivariate Time Series Modelling of Financial Markets with Artificial Neural Networks

This work presents an integrated approach for modelling the behaviour of financial markets with Artificial Neural Networks (ANNs). The model allows to forecast financial time series. Its originality lies in the fact that it is based on statistics and macroeconomics principles and it integrates fundamental economic knowledge in a multivariate nonlinear time series ANN model. The model is applied to real-life case studies and the results are discussed.

Thomas Ankenbrand, Marco Tomassini

Neural Network Approach to Pisarenko’s Frequency Estimation

This paper proposes a neural network approach for computing in real-time the required eigenvector in Pisarenko’s frequency estimation method. We will show both analytically and by simulations that this neural network approach has some advantages over the available neural network methods and is more suitable for real-time applications of Pisarenko’s frequency estimation method.

Fa-Long Luo, Rolf Unbehauen

Rounding FIR Filter Coefficients Using Genetic Algorithms

The quantisation process of filter coefficients required due to the finite length of the register provided to store the coefficients is an important step in the realization of a given filter. This process must be optimally carried out to minimise the error in the filter response caused by the quantisation of coefficients. Genetic algorithm is a heuristic optimisation procedure which is able to optimise both discrete and continuos functions efficiently. This paper explains how to use a genetic algorithm to round the coefficients of an FIR (finite-impulse-response) filter represented using fixed-point numbers and presents the simulation results.

D. H. Horrocks, N. Karaboğa, M. Alçi

Evolutionary Adaptive Filtering

Evolutionary algorithms have seen an ever increasing use in a variety of applications owing to their robustness and ease of implementation. This paper considers the performance of these algorithms when applied to adaptive filtering, with particular emphasis on the direct system modelling problem. The proposed approach also introduces a two — layer genetic algorithm that performs a coarse grain search at the word level followed by a fine grain optimisation of the filter weights at the bit level.

D. Ait-Boudaoud, R. Cemes, S. Holloway

Genetic Algorithms and Combinatorial Optimisation

A Genetic Algorithm for Some Discrete-Continuous Scheduling Problems

In this paper a Genetic Algorithm (GA) for solving some discrete-continuous scheduling problems is proposed. In this algorithm, each genotype represents a solution which is derived directly from the idea of a feasible sequence rather than being coded as a binary string. Applying suitable genetic operators allows to conduct the searching process in a feasible region only.

Joanna Józefowska, Rafal Różycki, Jan Węglarz

Hybridizing Genetic Algorithms with Branch and Bound Techniques for the Resolution of the TSP

In this paper some mixed techniques are outlined in order to combine the advantages of two very different methods for the resolution of combinatorial optimization problems (Genetic Algorithms and Branch and Bound Techniques), simultaneously avoiding their drawbacks. Due to the disparity between the basic techniques it is not suitable that they work at the same level so two models have been developed in which each technique assumes the role of being a tool of the other one. Parallelism is an important issue in these techniques.

C. Cotta, J. F. Aldana, A. J. Nebro, J. M. Troya

Performance of Genetic Algorithm Used for Analysis of Call and Service Processing in Telecommunications

A genetic algorithm applied for finishing time determination in the simulation method used for analysis of call and service processing in telecommunications has been described. The evaluation of a performance of the genetic algorithm including influences of the initial string population size on the convergence, differences coming from crossover and mutation probabilities variation, relations between the number of processors and the convergence as well as termination criterion have been discussed.

Vjekoslav Sinković, Ignac Lovrek

Evolutionary Heuristics for the Bin Packing Problem

In this paper we investigate the use of two evolutionary based heuristic to the bin packing problem. The intractability of this problem is a motivation for the pursuit of heuristics that produce approximate solutions. Unlike other evolutionary based heuristics used with optimization problems, ours do not use domain-specific knowledge and has no specialized genetic operators. It uses a straightforward fitness function to which a graded penalty term is added to penalize infeasible strings. The encoding of the problem makes use of strings that are of integer value. Strings do not represent permutations of the objects as is the case in most approaches to this problem. We use a different representation and give justifications for our choice. Several problem instances are used with a greedy heuristic and the evolutionary based algorithms. We compare the results and conclude with some observations, and suggestions on the use of evolutionary heuristics for combinatorial optimization problems.

Sami Khuri, Martin Schütz, Jörg Heitkötter

A Clausal Genetic Representation and its Evolutionary Procedures for Satisfiability Problems

This paper presents a clausal genetic representation for the satisfiability problem (SAT). This representation, CR for short, aims to conserve the intrinsic relations between variables for a given SAT instance. Based on CR, a set of evolutionary algorithms (EAs) are defined. In particular, a class of hybrid EAs integrating local search into evolutionary operators are detailed. Various fitness functions for measuring clausal individuals are identified and their relative merits analyzed. Some preliminary results are reported.

Jin-Kao Hao

Parallelism and Neural Networks

Massively Parallel Training of Multi Layer Perceptrons With Irregular Topologies

In this paper we present an approach to the training of feed forward neural networks on massively parallel SIMD-architectures. In order to cover a wide field of applications we focus our attention on the flexibility of the load balancing routines. Our approach is characterized by three important properties: 1. All four types of parallelism inherent in the training phase are used. 2. In a preprocessing step neural networks are transformed into equivalent topologies, more suited for parallel computation. 3. Each learning task can be parallelized in a number of different ways, the best of which is chosen according to estimations of the computing efficiency.Following these concepts we developed PINK2, a massively parallel simulator kernel for the MasPar MP1216. In contrast to most known approaches, efficient only for special topologies, it achieves good computing performance on a broad range of differing benchmark problems.

D. Koll, M. Riedmiller, H. Braun

Parallel Boltzmann Machine Topologies for Simulated Annealing Realisation of Combinatorial Problems

In this paper we investigate the convergence of parallel Boltzmann Machine topologies for solving the maximum matching problem. The simulations of the Boltzmann Machine topologies are done in Occam on transputers. The results of tests carried out by varying some implementation parameters are presented. A description is given of a Boltzmann Machine in terms of an asynchronous iterative algorithm allowing a new approach to the proof of theoretical convergence.

I. Ashman, T. Vladimirova, C. Jesshope, R. Peel

Radial Basis Function Networks

Radial Basis Function Neural Networks in Credit Application Vetting Systems

This paper describes an investigation carried out at Coventry into the suitability of Radial Basis Function(RBF) Neural Networks for use in credit vetting systems. The RBF used is an All Classes in One configuration with unweighted Euclidean distance measure. The paper examines the performance of the RBF network in classifying good and bad loan cases over a data set supplied by a substantial finance organisation. The effects of changing the number of centres and the training regime are examined. The network prediction performance is compared over the same data set with both a manually configured, and a genetic algorithm designed Back Propagation Trained Multi-Layer-Perceptron.The performance of the RBF network in classifying cases is found to be comparable with these two solutions, providing similar prediction rates. The relative simplicity of the RBF solution gives greatly reduced computing time for comparable performance, and potentially easier routes to providing information about the decisions reached. Ideas for enhancing the future performance of the system are discussed.

A. G. Williamson, P. Munson

A Dynamical Architecture for a Radial Basis Function Network

We present a dynamical architecture for a Radial Basis Function Network. The scheme is based on the Simulated Annealing procedure for learning. Increase of performances with respect to classical methods and opportunity to vary the size of the network are reported.

Bernard Lemarié, Anne-Gaelle Debroise

Centre Selection for Radial Basis Function Networks

This paper is concerned with radial basis function neural networks. A new method is described by which means radial basis function centres can be selected. The method is based on a mean tracking clustering algorithm and it is shown how the approach provides a good procedure for radial basis function centre selection. Results are given which indicate how the method realises a network with excellent approximation properties.

K. Warwick, J. D. Mason, E. L. Sutanto

Multimedia, CAD and Software Tools

Flexible User-Guidance in Multimedia CBT-Applications Using Artificial Neural Networks

The paper decribes a system architecture for CBT-applications that includes artificial neural networks (ANNs) for dynamically creating user-specific paths through a database of multimedia objects. The organisation of these objects is based on principles of hypersystems. Additionally a semantic data model is involved to describe the objects’ characteristics. The ANNs represent experiences and decisions of former users, based on the object’s characteristics. During a CBT-session, the ANNs are used by a run-time controller in order to retrieve objects, which are appropriate candidates for continuing the lesson, from the semantic data model.

Klaus Langer, Freimut Bodendorf

Use of Genetic and Neural Technologies in Oil Equipment Computer-Aided Design

Oil pumping equipment designers have to solve different types of optimization problems. Use of strong mathematical means is frequently very difficult, or, even impossible because of complexity of those problems. This paper suggests using genetic algorithms as an alternate facility to find optimal parameters of pumping unit under given particular conditions. Neural networks are employed to approximate the best solution using statistics on already found solutions for a set of conditions. Experimental results are discussed.

R. M. Vahidov, M. A. Vahidov, Z. E. Eyvazova

GENESIS: An Object-Oriented Framework for Simulation of Neural Network Models

In this paper we present GENESIS as a highly flexible and graphical environment for simulating ANN based on the object-oriented paradigm. This includes a hierarchy of classes that models ANNs being characterized by a high degree of modularity. The use of object-oriented techniques provides the data abstraction facilities necessary to support modification and extension of the simulation system at a high level of abstraction, from a graphic user interface.. Furthermore, ANN specification is suitable for joining networks in a neural macro-structure.

L. Fuentes, J. F. Aldana, J. M. Troya

NNDT — A Neural Network Development Tool

A tool for analysis, modelling, simulation and prediction with feedforward and recurrent neural networks is presented. The Neural Network Development Tool (NNDT) is implemented in Visual Basic and C and runs under MS Windows on personal computers. Network training is carried out by the Levenberg-Marquardt method and the user interface facilitates interactive analysis and modification of parameters as well as illustration of results. The features offered by the tool are especially useful in the difficult process of training recurrent networks, but are also of value, e.g., in scanning the performance of feedforward networks for analysing if and when overfitting occurs.

Björn Saxén, Henrik Saxén

Genetic and Neural Theory Combined

Genetic Synthesis of Task-Oriented Neural Networks

A stochastic search technique based on genetic algorithms for design of task-oriented neural networks is described in the paper. Although the theory of the algorithms is clear, its implementation in the design of neural structures is not yet well investigated. With the help of two case studies, we want to outline the new design approach.

Andrej Dobnikar

Evolving Neural Networks Using the “Baldwin Effect”

This paper describes how through simple means a genetic search towards optimal neural network architectures can be improved, both in the convergence speed as in the quality of the final result. This result can be theoretically explained with the Baldwin effect, which is implemented here not just by the learning process of the network alone, but also by changing the network architecture as part of the learning procedure. This can be seen as a combination of two different techniques, both helping and improving on simple genetic search.

Egbert J. W. Boers, Marko V. Borst, Ida G. Sprinkhuizen-Kuyper

Genetic Algorithms Theory

Modification of Holland’s Reproductive Plan for Diploid Populations

A modification of Genetic Algorithm capable of dealing with a diploid population is described. Each individual of such a population should be represented as a double bitstring chromosome. Both a procedure of creation of the initial population using genomic mutation and a version of gene dominancy evolution are suggested. Results of numerical experiments proving high search ability of the algorithm are presented.

V. B. Klepikov, K. V. Mahotilo, S. A. Sergeev

Optimisation

Simulated Annealing Artificial Neural Networks for the Satisfiability (SAT) Problem

A simulated annealing artificial neural network, which is based on the principles of Harmony Theory [1], is proposed for the solution of the satisfiability (SAT) problem of propositional calculus. The structure of the employed network is such that not only is a valid solution to any given SAT problem automatically provided, but — furthermore — this solution contains the values of the variables which render true the greatest possible number of clauses.The number of clauses which are satisfied is automatically revealed by the quantitative measure of harmony [1] once the simulated annealing settling procedure has been completed. Additionally, both the identity of the satisfied clauses and the actual values of all variables are determined by the settled-upon activation values of the network nodes.

T. Tambouratzis

Policy Optimization by Neural Network and Its Application to Queueing Allocation Problem

The problem of allocating an arriving customer to one of parallel servers has been actively studied in queueing theory for load balancing in computer networks or in multi-processor systems. To theoretically derive the optimal allocation policy, the assumption of identical servers is usually required. However this assumption is unrealistic in many applications. This paper considers the queueing allocation problem with non-identical servers and multi-class customers. The goal is to optimize the allocation policy with respect to the mean delay of an arbitrary customer. To this end, we represent the allocation policy by a neural network; namely, we allocate an arriving customer according to the output of the neural network, where the inputs to the neural-net are the numbers of queueing customers at each server and the class of the arrival. By using the simulated annealing method, we search the optimal allocation policy in the weight space. Numerical results show that the present procedure significantly reduces the mean delay in comparison to an empirical policy.

Hisashi Sato, Yutaka Matsumoto, Norio Okino

Comparison of Genetic and Other Unconstrained Optimization Methods

This paper presents and compares genetic and non-genetic, algorithms for unconstrained optimization of differentiable functions f : Rn ↦ R with many local optima. The topics discussed here are: population size, the role of crossover, including gradient line search into GA and memorizing the calculated gradients.One thousand 10 dimensional test functions with 10–20 randomly located optima have been minimized by the tested algorithms. The population sizes of the algorithms were bigger than the number of the local optima.A rank comparison test, the Friedman test, have been used to find the statistically significant differences between the convergence of the algorithms.

Antti Autere

Neural Networks for Dynamical Crop Growth Model Reduction and Optimization

A dynamic crop growth model of undeterminate tomato variety (TOMGRO) consists of a large number (69) of difference equations that describe age classes of different organs. In order to find a fast working and low-dimensional equivalent with dynamic Neural Networks (NN), several model reduction approaches has been tried, including aggregation, PCA transformation, and bottleneck NN compression. Reduced data were used to train dynamic NN. Simulations with the NN model produced trajectories which agreed well with the original trajectories of TOMGRO.

Ilya Ioslovich, Ido Seginer

Self-Organizing Maps and Auto-Associative Memory

Modified Kohonen’s Learning Laws for RBF Network

A hybrid training method for the radial basis function (RBF) network is presented. The method applies the Kohonen’s self-organizing map (SOM) and a modified learning vector quantization (LVQ) algorithms. Learning algorithms are derived for two alternative RBF network structures exploiting local Gaussian basis functions. The potential of the proposed methods is demonstrated by a function approximation example.

Tommi Ojala, Petri Vuorimaa

Kohonen’s Maps for Contour and “Region-Like” Segmentation of Gray Level and Color Images

One propounds two methods of image contour segmentation based on the tonotopy property of Kohonen’s self-organizing maps (SOM). The first method consists in quantizing the set of gray levels of the image by making use of a one dimensional SOM, then detecting the spatial discontinuities of the involved mapping of quantized gray levels onto map’s cells. The same method brings color image segmentation when quantizing the color values of the image by making use of a three dimensional SOM. This first method is multiresolution acording to gray level or color accuracy. Examples of gray level and color image segmentations illustrate its outcome.The second method presented consists in quantizing the set of spatial and gray level pixel coordinates by a three dimensional SOM. This quantization brings a “region-like” pixel clustering out of which one computes contour segmentation of the image. This method is monoresolution and yelds contour segmentations less noisy than the one obtained by the first method. This second method is illultrated by an example of gray level image segmentation.

René Natowicz, Lothar Bergen, Bruno Gas

Using Genetic Algorithm in Self-Organizing Map Design

A new method for self-organizing map design is proposed. The method is based on a genetic algorithm. Some simulations are also reported.

Ari Hämäläinen

Modular Labeling RAAM

The Labeling RAAM model is a neural network able to encode labeled graphs in fixed size representations. In order to speed up the training procedure and for reducing in size the developed compressed representations, we propose a modular Labeling RAAM. In order to develop the modular system, we face two main problems: the mapping problem, i.e., how to map components of the structures into modules; and the membership problem, i.e., discovering which module must be used for decoding a compressed representation. The mapping between components and modules can be decided on the basis of the strongly connected components of the structures. The membership problem is solved by resorting to the BAMs derived from each LRAAM module. Preliminary results on the modular system are encouraging.

Alessandro Sperduti, Antonina Starita

Self-Organizing Maps for Supervision in Robot Pick-And-Place Operations

A scheme for supervised learning based on multiple self-organizing maps (SOMs) is presented, and its application to robotic tasks, namely pick-and-place operations, is outlined. The advantage of this multiple organization is that the learning method is simplified because the problem is divided into several SOMs, which are trained in the standard unsupervised way. The resulting network preserves the SOM properties like dimensionality reduction and cluster formation, and its classification performance is comparable to other supervised methods like backpropagation networks.

Enrique Cervera, Angel P. del Pobil

Parallelism and Genetic Algorithms

Q-Learning and Parallelism in Evolutionary Rule Based Systems

We present PANIC (Parallelism And Neural networks In Classifier systems), a parallel learning system which uses a genetic algorithm to evolve behavioral strategies codified by sets of rules. The fitness of an individual is evaluated through a learning mechanism, QCA (Q-Credit Assignment), to assign credit to rules. QCA evaluates a rule depending on the context where it is applied. This new mechanism, based on Q-learning and implemented through a multi-layer feed-forward neural network, has been devised to solve the rule sharing problem posed by traditional credit assignment methods. To overcome the heavy computational cost of this approach, we propose a decentralized and asynchronous parallel model of the genetic algorithm.

Antonella Giani, Fabrizio Baiardi, Antonina Starita

Comparing Parallel Tabu Search and Parallel Genetic Algorithms on the Task Allocation Problem

There exist many sequential heuristic combinatorial techniques to efficiently solve a wide set of problems. Researchers are proposing new parallel versions for them so as to take advantage of the power offered by parallel computers. In this paper new locally-linked parallel versions for two such techniques, Tabu Search and Genetic Algorithms, are proposed and tested on different-sized items of the Task Allocation Problem, one of the most challenging optimisation problems.

I. De Falco, R. Del Balio, E. Tarantino

Distributed Genetic Algorithms with an Application to Portfolio Selection Problems

This paper presents a PVM-based coarse-grained distributed genetic algorithm implemented on workstation clusters. After successfully evaluating the algorithm with standard test functions, we apply it to a hard real-world portfolio selection problem. The distributed version easily outperforms sequential genetic algorithms and shows promise for difficult management applications.

A. Loraschi, Marco Tomassini, A. Tettamanzi, Paolo Verda

Optimisation

Interval arithmetic and genetic algorithms in global optimization

In this work we have combined two promising global optimization methods, interval arithmetic methods and genetic algorithms, into a set of hybrid algorithms that share the good properties of both methods while avoiding some drawbacks of the constituent methods. Interval aritmetic gives us some simple arithmetic methods to estimate the range of rational functions to be optimized, while genetic algorithms are able to adaptively guide the search.

Jarmo T. Alander

A Genetic Algorithm for Minimization of Fixed Polarity Reed-Muller Expressions

A Genetic Algorithm (GA) is developed to find small or minimal Fixed Polarity Reed-Muller expressions (FPRMs) for large functions. We combine the GA with greedy heuristics, i.e. we use Hybrid GAs (HGAs). We show by experiments that results superior to all other approaches for large functions can be obtained using GAs.

Rolf Drechsler, Bernd Becker, Nicole Göckel

Control Theory Applications

Identification and Adaptive Control of Nonlinear Processes Using Combined Neural Networks and Genetic Algorithms

This paper presents a new combined neural-genetic method for identifying processes comprising static nonlinearities and linear dynamics, and for adapting the model to linear and nonlinear parameter changes. The approach is based on multilayer and recurrent neural networks. It is shown that the powerful properties of genetic algorithms may be used to advantage in a learning neural network. We solve a number of problems and compare the results and the method with those previously reported by Narendra & Parthasarathy.

A. H. Abu-Alola, N. E. Gough

Elevator group control using distributed genetic algorithm

In this work we have studied the applicability of genetic algorithms to the optimization of elevator group control parameters. The goal was to minimize the average passenger waiting time in a simulated office building. The elevator group control consists of a set of elevators and controllers. At the highest level of the system hierarchy the elevator group controller decides which elevator serves which call. The decision is based on the actual calls, state of the elevators (location, direction, load) and on the estimation of the traffic situation like: incoming, interfloor, outgoing, which gives some idea how the calls will be distributed within a few minutes time period. Especially in office buildings the traffic type depends on the time of the day. This allocation problem, which seems to be quite simple, turns out to be a very difficult control problem in practise and is one of the features how elevator companies can competed with one another.

Jarmo T. Alander, Jari Ylinen, Tapio Tyni

Neural Control of Nonlinear Non-Minimum Phase Dynamical Systems

This paper argues that the ‘optimization along trajectories formulation of the distal learning approach [1] doesn’t work on non-minimum phase dynamical plants [2] and the ‘local optimization’ one doesn’t work on plants with variable or badly-estimated time-delay. It then proposes a modification of the procedure and illustrates improvements on the control of a simulated irrigation canal.

Abdelmoumène Toudeft

Industrial Kiln Multivariable Control: MNN and RBFNN Approaches

Artificial neural networks have been recognized as a valuable framework for nonlinear identification and control. In this paper we discuss and compare the use of two types of neural network arquitectures (1) MNN (Multilayer Neural Network) and (2) RBFNN (Radial Basis Function Neural Network) for modelling a second order nonlinear chemical process — a lime kiln in the pulp and paper industry. The simulation results showed that MNN performs better in this practical case. Therefore, it was used in an IMC (Internal Model Control) strategy. The neurocontroller was analysed with regards to performance and robustness against disturbances.

B Ribeiro, A Dourado, E Costa

Genetic Tuning of Neural Non-Linear PID Controllers

The techniques of genetic algorithms are proposed as a means of tuning neural non-linear PID control systems. It is shown that the use of genetic algorithms for this purpose results in highly effective genetic neural non-linear PID control systems. These results are illustrated by designing a genetic neural non-linear PID control systems and contrasting the results with an optimally tuned linear PID controllers.

A H Jones

Applications in Biology and Biotechnology

Connectionnist Algorithm for a 3D Dense Image Building from Stereoscopy

In this paper, we present a neuron-like network able to build 3D dense maps from stereoscopic image pair. The process of stereopsis is encoded by an energy function, which controls the evolving of the network. This one has the same structure than original images, and evolutes on a simple gradient steep. Thus, the system is fully parallel and could be hardware implemented for a real time use.

Marc-Noël Fauvel, Pascal Aubry

A Unified Neural Network Model for the Self-organization of Topographic Receptive Fields and Lateral Interaction

A self-organizing neural network model for the simultaneous development of topographic receptive fields and lateral interactions in cortical maps is presented. Both afferent and lateral connections adapt by the same Hebbian mechanism in a purely local and unsupervised learning process. Afferent input weights of each neuron self-organize into hill-shaped profiles, receptive fields organize topographically across the network, and unique lateral interaction profiles develop for each neuron. The resulting self-organized structure remains in a dynamic and continuously-adapting equilibrium with the input. The model can be seen as a generalization of previous self-organizing models of the visual cortex, and provides a general computational framework for experiments on receptive field development and cortical plasticity. The model also serves to point out general limits on activity-dependent self-organization: when multiple inputs are presented simultaneously, the receptive field centers need to be initially ordered for stable self-organization to occur.

Joseph Sirosh, Risto Miikkulainen

A Neural Network Implementation for a Electronic Nose

A new implementation of a multi-layer perceptron neural network is presented where activation levels within the network are encoded using Sigma-Delta modulation. Large, hardware networks can be constructed, which can be trained using the standard back-propagation algorithm. The network has been used to form a stand-alone electronic nose system capable of distinguishing between four odours.

Philip B James-Roxby

Genetic Algorithms (GAs) in the Role of Intelligent Regional Adaptation Agents for Agricultural Decision Support Systems

An AI adaptation methodology designed to assist in transporting agricultural models between regions is presented. A methodology to perform model adaptation (viz. localization) is frequently necessary when models are transported because models developed in one region often do not produce valid results when used in a different region. In this methodology, a GA plays the role of the adaptation agent. By linking a GA to an agricultural model, the model become more robust because it is able to adapt to the region in which the model is being used. This methodology has been implemented within a decision support system (DSS) developed within an EC project called SYBIL. The DSS helps farmers predict when diseases and funguses will attack their plants, so they can make intelligent decisions on preventing these attacks. Preliminary testing within this environment indicates this adaptation methodology has the ability to allow agricultural models developed in one area to be effectively utilized in other regions.

Gianni Jacucci, Mark Foy, Carl Uhrik

Genetic Algorithm Applied to Radiotherapy Treatment Planning

Conformal therapy attempts to produce accurate medical treatment that will produce a uniform dose over cancerous regions whilst at the same time sparing healthy tissues, especially the organs at risk. The constrained optimisation problem, that consists of working back from a given dose specification to elemental beam weight intensities is referred as the so called inverse problem. Due to the nature of the problem and in particular to its conflicting objectives, it is believed that heuristic techniques may have advantages over direct methods to solve for the beam intensities.

O. C. L. Haas, K. J. Burnham, M. H. Fisher, J. A. Mills

Learning and Training

An Experience Based Competitive Learning Neural Model for Data Compression

This paper presents a novel design of a multi-layer neural model which implements an experience based learning algorithm to train the neural network and achieve comparable data compression. This design takes 16 bits each cycle as the input to the network. A competitive learning based operation is then applied to the input to find the winner which exactly matches the 16 bits. Another hidden layer is further designed to produce various outputs corresponding to the different outcomes of the competitive learning. The output then controls the coder to complete the encoding. Finally, an experience based learning algorithm is developed to train the network to make the best use of the statistical information from input to achieve the highest possible compression.

Jianmin Jiang

Using Neural Networks for Generic Strategic Planning

This paper argues the scarcity of strategic planning software is due to Western philosophical traditions which see strategy hypothesising as a mysterious, intuitive process that resists analysis and computerisation. But progress is possible if one extracts, from the tactical planning literature, eight key, generic, strategy-evaluation criteria. An experiment then tests whether scores on such criteria can be used to power machine learning of overall strategy desirabilies, and whether such learning is better achieved using multiple regression analysis or a simulated neural network. Both methods were successful, but the neural network was clearly the most accurate. It therefore constitutes a promising basis for self-improving, strategic planning software.

Ray Wyatt

Neural Network Training Compared for BACKPROP QUICKPROP and CASCOR in Energy Control Problems

Gradient-based neural network learning algorithms, specifically the backpropagation (BACKPROP), quickpropagation (QUICKPROP), and cascade correlation (CASCOR), have been re-implemented, tested, and compared for making predictions of time series for daily energy (gas) consumption. Daily records of energy consumption form a time series with information that can predict energy demand for a few days. Initially, the basic prediction is made from the past series without taking external influences into consideration. Later, other independent predictive data series can be included to improve prediction. Repeated presentation of hundreds of sample patterns systematically trains a network which converges upon connection configurations that predict expected demand. It has been demonstrated that the learning algorithms can consistently train networks to predict, one-day-ahead over the succeeding year, with the average error reduced to below 20%.

Alexei N. Skurikhin, Alvin J. Surkan

Mixed Applications

Application of Neural Network for Home Security System

In this study, the application of Artificial Neural Network (ANN) for home security system (HSS) is investigated. The HSS consists of a neural network with input, hidden and output layers. The HSS detects the presence of unidentified person in the house and initiates an alarm. It has its own fault-diagnostic algorithm. In case any system component fails, it gives an alarm which is different from the other, to indicate the system failure. The minimum number of nodes, the optimum number of hidden layers, the speed, the accuracy and learning time for back propagation (BP) algorithm [1] are investigated in the present paper.

Turgay Ibrikci, V. Krishnamurthi

Application of Genetic Algorithms in Sliding Mode Control Design

A Genetic Algorithm (GA) is a stochastic adaptive algorithm whose search method is based on simulation of natural genetic inheritance and Darwinian striving for survival. The GA has been adapted to study the problem of designing a stable sliding mode which yields robust performance in variable structure control systems. For various cases, we show that GA is viable and has great potential in the design of sliding mode control systems.

N. H. Moin, A. S. I. Zinober, P. J. Harley

Application of Temporal Neural Networks to Source Localisation

In this paper, we present several neural networks approaches to deal with the problem of source localisation in signal processing. To locate a far field source, we have to retrieve the propagation delays between sensors. They are the only relevant temporal information we can handle on the signal.As we have to process temporal data, we study different time representations in neural networks. First, time may be represented explicitly and externally with multilayer perceptrons. Then, we use a time-delay neural network that appears to be more suitable to represent explicitly the temporal nature of the signal. Last, we study recurrent neural networks that represent time in their internal organisation.

Brigitte Colnet, Stéphane Durand

Using Genetic Algorithms for Optimal Design of Axially Loaded Non-Prismatic Columns

This paper presents a method for optimizing the design of axially loaded non-prismatic columns using genetic algorithms (GAs). The design problem was formulated as an optimization problem in which the objective function is to minimize the volume of a column under a given load by changing its shape, subject to both buckling and strength constraints. Both floating point representation and binary representation (with and without Gray coding) were used and compared against a mathematical programming method based on the generalized reduced gradient method. Our results show that the floating point representation scheme provides the best solutions, both in terms of precision and in terms of computing time. This problem is of great interest in engineering, since considerable savings can be achieved due to the effective use of material through the optimal shape of a column, mainly for mass production.

Carlos A. Coello, Alan D. Christiansen

Behaviour Learning by a Reward-Penalty Algorithm : From Gait Learning to Obstacle Avoidance by Neural Networks

Designing a mobile robot capable to evolve on various floors is a hard, and not yet solved task. Among the numerous ways, the biological inspired researches are attractive. Taking inspiration from such devices, a study on walk learning and obstacle avoiding by neural networks is presented. After a general presentation of the learning method, and its adaptation to neural networks, results on gait learning are described and first simulations on obstacle avoidance are also presented. Finally, a global network performing the two tasks with success is given.

Isabelle Sarda, Anne Johannet

Training Data Selection

Using Evolutionary Computation to Generate Training Set Data for Neural Networks

Most neural networks require a set of training examples in order to attempt to approximate a problem function. For many real-world problems, however, such a set of examples is unavailable. Such a problem involving feedback optimization of a computer network routing system has motivated a general method of generating artificial training sets using evolutionary computation. This paper describes the method and demonstrates its utility by presenting promising results from applying it to an artificial problem similar to a real-world network routing optimization problem.

Dan Ventura, Tim Andersen, Tony R. Martinez

Optimal Training Pattern Selection Using a Cluster-Generating Artificial Neural Network

In this piece of research, the problem of optimal pattern selection for artificial neural network training is investigated. Given an initial set of training patterns, the objective is to extract the minimal subset which accurately represents the initial set.The training pattern selection strategy which is presented here is based on the clustering capability of the Harmony Theory simulated-annealing harmony-maximisation artificial neural network [1]. Correction and reduction of the training set is achieved by rectifying the repetition and misclassification errors as well as by organising and unifying the training patterns in terms of their similarities.

T. Tambouratzis, D. G. Tambouratzis

Training Set Selection in Neural Network Applications

In some applications of ANNs to classification problems, training can be inefficient simply because of the high volume of data available for training purposes. The question arises whether it is necessary to use all the data in order adequately to approximate the decision boundaries.It is intuitively obvious that points near to the boundaries are likely to have more influence over the network weights than those which are far away. Of course, as the boundaries are initially unknown, the status of any particular data point is also unknown. Here we describe an approach which uses an initial crude estimate of the decision boundaries to select appropriate training data in the case of the Multi-Layer Perceptron, followed by a phased addition of points to the training set. We compare this approach with the standard method on both artificial and real data sets, and report results which demonstrates the potential for improved performance in terms of both efficiency and reliability.

Colin R Reeves

Parallelism and Genetic Algorithms

A Genetic Algorithm for Load Balancing in Parallel Query Evaluation for Deductive Relational Data Bases

Datalog is a query language for deductive databases. This language allows to evaluate a query incrementally on a network of processes. The tuples flow among them in parallel in order to compute the solution to the query. A major issue in this evaluation is the problem of assigning the processes to processors in a multiprocessors system. Not only load balancing is wanted but lowering the communication costs among the processors is crucial. We have tackled this problem by using a GA that works on a specific fitness function that allows to meet these goals. The techniques and results are presented here.

E. Alba, J. F. Aldana, J. M. Troya

Combining Distributed Populations and Periodic Centralized Selections in Coarse-Grain Parallel Genetic Algorithms

In this paper we demonstrate that parallel genetic algorithms can profit from performing periodic centralized selections of distributed populations. With this combination, implementations can benefit from the variety of environments provided by distributed approaches, while periodically being able to consider the population as a whole and disregard very unfit individuals. We study four different parallel genetic algorithm implementation strategies; each of them striking a different balance between centralization and distribution. These strategies are applied to several well-known benchmark problems. Our results show that the implementations using periodic centralized selections exhibit remarkable robustness in terms of their search quality, while keeping running time overheads under control. Our main conclusion is that performing centralized selections represents an improvement to the traditional population distribution approaches, which are susceptible to somewhat inefficient search.

R. Bianchini, C. M. Brown, M. Cierniak, W. Meira

Modified Genetic Algorithms by Efficient Unification with Simulated Annealing

Genetic algorithms (GA) are stochastic search techniques based on the mechanics of natural selection and natural genetics. By using genetic operators and cumulative information, genetic algorithms prune the search space and generate a set of plausible solutions. This paper describes a Modified Genetic Algorithm (MGA) that is developed by making a marriage between the Simple Genetic Algorithm (SGA) and the Simulated Annealing (SA). In this proposed algorithm, all the conventional genetic operators, such as, selection, reproduction, crossover, mutation, have been used, but they have been modified by a set of new functions such as, a evaluation function, a selection function, a mutation function, etc., which utilizes the concept of successive descent as seen in simulated annealing. In this way, MGA can be implemented to solve combinatorial optimization problems more accurately and quickly.

S. Ghoshray, K. K. Yen, J. Andrian

VLSI Standard Cell Placement by Parallel Hybrid Simulated-Annealing and Genetic Algorithm

Placement of standard cells is a part of physical VLSI chip design. In order to achieve high performance, area of the chip and lengths of wires connecting cells have to be minimized. In the placement step, the goal is to place cells in such a way that total wire-length is as short as possible. Since this problem is NP-hard, heuristic techniques have to be applied. Modern approaches include simulated annealing and genetic algorithms. In this paper, we discuss those methods and show that they can be improved by combination. A heuristic technique called parallel recombinative simulated annealing (PRSA) is described. It integrates features of both simulated annealing and genetic algorithms. Behavior of PRSA is studied with respect to different parameter settings.

Karl Kurbel, Bernd Schneider, Kirti Singh

Genetic Algorithms and Combinatorial Optimisation

Performance of Genetic Algorithms in the Solution of Permutation Flowshop Problem

Scope of this paper is to investigate the applicability of Genetic Algorithms to the solution of Static Permutation Flowshop problem and to compare their performance with those obtained with Taboo Search Algorithms. Since in order to obtain good results with Genetic Algorithms (Gas) it is necessary to tune a set of parameters, then a second purpose of the study is to devise a methodology to perform this tuning. The methodology used is the “Response Surface Methodology”.

Nicoletta Sangalli, Quirico Semeraro, Tullio Tolio

A Genetic Algorithm for the Maximal Clique Problem

The maximal clique problem (MaxClique) is known to be difficult (in terms of complexity) both in its exact and in the approximate form. Therefore, probabilistic algorithms for this problem are worthwhile to study. In this paper, we present an evolutionary (genetic) approach to solving the maximal clique problem (we are not directly concerned here with complexity). As opposed to previous work, our solution is inspired by a theoretical result [1] which improves the genetic algorithm. Experimental results for graphs with various properties are given; the convergence towards a good solution (in almost all of the runs, the global optimum) turns out to be quick.

Cristina Bazgan, Henri Luchian

Fuzzy Logic and Uncertainty

Minimal Error Rate Classification in a Non-stationary Environment via a Modified Fuzzy ARTMAP Network

This paper investigates the feasibility of the fuzzy ARTMAP neural network for statistical classification and learning tasks in an on-line setting. The inability of fuzzy ARTMAP in implementing a one-to-many mapping is explained. Thus, we propose a modification and a frequency measure scheme which tend to minimise the misclassification rates. The performance of the modified network is assessed with noisy pattern sets in both stationary and non-stationary environments. Simulation results demonstrate that modified fuzzy ARTMAP is capable of learning in a changing environment and, at the same time, of producing classification results which asymptotically approach the Bayes optimal limits. The implications of taking time averages, rather than ensemble averages, when calculating performance statistics are also studied.

Chee Peng Lim, Robert F. Harrison

Decision Making in Uncertain Environment with GA

In this work, we develop a particular approach based on Genetic Algorithms (GA) for solving the decisionmaking problem in an uncertain environment, expressed as a graph-search problem. We show how Genetic Algorithms can be used as a new kind of heuristic search technique. The algorithm is illustrated in a particular decision-making application, namely an expert system which performs the automatic target recognition of armoured vehicules from short-range infra-red images. To illustrate the flexibility of the Genetic Algorithms approach for decision making, two implementations (single and multi-stage GA) are build and compared.

Christiaan Perneel, Marc Acheroy

The Use of Fuzzy ARTMAP to Identify Low Risk Coronary Care Patients

The performance of fuzzy ARTMAP and modified fuzzy ARTMAP is compared using real-world data from a medical domain, the task being to predict the death or survival of patients admitted to a coronary care ward. Modified fuzzy ARTMAP is shown to perform consistently more accurately than fuzzy ARTMAP and is also much less prone to variations in performance with different orderings of training data. However, modified fuzzy ARTMAP does not show as large an improvement in performance as fuzzy ARTMAP when employed in the voting strategy. When unanimous voting decisions alone are considered, fuzzy ARTMAP is able to increase significantly accuracy in identifying survivors at the cost of decreased coverage of cases. This allows the identification of a subset of patients who have a low-risk of death from their condition and are thus potentially suitable for early discharge from hospital.

J. Downs, R. F. Harrison, R. L. Kennedy, K. Woods

NeuroGraph - A Simulation Environment for Neural Networks, Genetic Algorithms and Fuzzy Logic

NeuroGraph is a simulation environment for neural networks. It provides an easy to use graphical user interface to design, construct and execute neural networks. The most important design goals were easy extensibility, good performance and the ability to solve real world problems. Extensibility is ensured by an extremely flexible, hierarchical internal representation (data structure), which can be easily manipulated by graphical tools. Current available extensions to the neural network simulator are components for genetic algorithms and fuzzy logic. As examples the automated generation of a neural network by a genetic algorithm and a fuzzy controller are shown. This data structure can be interpreted for debugging purposes or can be executed directly for high performance computing. In the later case C or C++ code is generated from the internal representation of the neural, gentic or fuzzy functions, compiled and stored in an executable process (library). NeuroGraph has a file or process interface to interconnect which other processes. It is also possible to generate C or C++ code representing the neural network, genetic algorithm or fuzzy component which can be incorporated in other applications.

P. Wilke, J. Rehder, G. Billing, C. Mansfeld, J. Nilson

Time Series, Sequences and Filters

Comparison of Identification Techniques for Nonlinear Systems

The problem of identifying a dynamic process from experimentally derived data has received much attention in the technical literature. Classically, a least squares based method is used, having first established a suitable structure, to estimate the parameters of a linear discrete time model. Whilst recognising that such linear models are not suitable for all applications, they have gained widespread acceptance, since, in the main they are used with controller design algorithms which require models of that form.

I. G. French, S. Ho, A. Adgar
Weitere Informationen