A Memetic Genetic Program for Knowledge Discovery
Gert Nel. 2005.

Download this paper.

Abstract:

Local search algorithms have been proved to be effective in refining solutions that have been found by other algorithms. Evolutionary algorithms, in particular global search algorithms, have shown to be successful in producing approximate solutions for optimisation and classification problems in acceptable computation times. A relatively new method, memetic algorithms, uses local search to refine the approximate solutions produced by global search algorithms. This thesis develops such a memetic algorithm. The global search algorithm used as part of the new memetic algorithm is a genetic program that implements the building block hypothesis by building simplistic decision trees representing valid solutions, and gradually increases the complexity of the trees. The specific building block hypothesis implementation is known as the building block approach to genetic programming, BGP. The effectiveness and efficiency of the new memetic algorithm, which combines the BGP algorithm with a local search algorithm, is demonstrated.

Back to top

A Serendipitous Software Framework for Facilitating Collaboration in Computational Intelligence
Edwin Peer. 2005.

Download this paper.

Abstract:

A major flaw in the academic system, particularly pertaining to computer science, is that it rewards specialisation. The highly comp etitive quest for new scientific developments, or rather the quest for a better reputation and more funding, forces researchers to sp ecialise in their own fields, leaving them little time to properly explore what others are doing, sometimes even within their own field of interest. Even the peer review process, which should provide the necessary balance, fails to achieve much diversity, since reviews are typically performed by persons who are again specialists in the particular field of the work. Further, software implementations are rarely reviewed, having as a consequence the publishing of untenable results. Unfortunately, these factors contribute to an environment which is not conducive to collaboration, a cornerstone of academia building on the work of others. This work takes a step back and examines the general landscape of computational intelligence from a broad perspective, drawing on multiple disciplines to formulate a collaborative software platform, which is flexible enough to support the needs of this diverse research community. Interestingly, this project did not set out with these goals in mind, rather it evolved, over time, from something more specialised into the general framework described in this dissertation. Design patterns are studied as a means to manage the complexity of the computational intelligence paradigm in a flexible software implementation. Further, this dissertation demonstrates that releasing research software under an open source license eliminates some of the deficiencies of the academic process, while preserving, and even improving, the ability to build a reputation and pursue funding. Two software packages have been produced as products of this research: i) CILib, an open source library of computational intelligence algorithms; and ii) CiClops, which is a virtual laboratory for performing experiments that scale over multiple workstations. Together, these software packages are intended to improve the quality of research output and facilitate collaboration by sharing a rep ository of simulation data, statistical analysis tools and a single software implementation.

Back to top

ACODV: Ant Colony Optimisation Distance Vector Routing in Ad Hoc Networks
Johan du Plessis. 2005.

Download this paper.

Abstract:

A mobile ad hoc network is a collection of wireless mobile devices which dynamically form a temporary network, without using any existing network infrastructure or centralised administration. Each node in the network effectively becomes a router, and forwards packets towards the packet's destination node. Ad hoc networks are characterized by frequently changing network topology, multi-hop wireless connections and the need for dynamic, efficient routing protocols.
This work considers the routing problem in a network of uniquely addressable sensors. These networks are encountered in many industrial applications, where the aim is to relay information from a collection of data gathering devices deployed over an area to central points. The routing problem in such networks are characterised by:
The overarching requirement for low power consumption, as battery powered sensors may be required to operate for years without battery replacement; An emphasis on reliable communication as opposed to real-time communication, it is more important for packets to arrive reliably than to arrive quickly; and Very scarce processing and memory resources, as these sensors are often implemented on small low-power microprocessors. This work provides overviews of routing protocols in ad hoc networks, swarm intelligence, and swarm intelligence applied to ad hoc routing. Various mechanisms that are commonly encountered in ad hoc routing are experimentally evaluated under situations as close to real-life as possible. Where possible, enhancements to the mechanisms are suggested and evaluated. Finally, a routing protocol suitable for such low-power sensor networks is defined and benchmarked in various scenarios against the Ad hoc On-Demand Distance Vector (AODV) algorithm.

Back to top

Image Clustering using Particle Swarm Optimization
Mohammed Omran. 2005.

Download this paper.

Abstract:

Because of its simplicity and efficieny in navigating large search spaces for optimal solutions, particle swarm optimizers (PSOs) are used in this research to develop efficient, robust and flexible unsupervised image clustering algorithms. Both hard (crisp) and fuzzy clustering are being studied and comparison with the well known image clustering techniques is being conducted. Furthermore, a PSO algorithm which dynamically determine the number of clusters in the image set (i.e., fully unsupervised image clustering) will be developed. The influence of the number of particles, number of iterations, and other PSO parameters on the performance of the PSO will be explored.

Back to top

PSO-Based Coevolutionary Game Learning
Nelis Franken. 2004.

Download this paper.

Abstract:

Games have been investigated as computationally complex problems since the inception of artificial intelligence in the 1950's. Originally, search-based techniques were applied to create a competent (and sometimes even expert) game player. The search-based techniques, such as game trees, made use of human-defined knowledge to evaluate the current game state and recommend the best move to make next. Recent research has shown that neural networks can be evolved as game state evaluators, thereby removing the human intelligence factor completely. This study builds on the initial research that made use of evolutionary programming to evolve neural networks in the game learning domain. Particle Swarm Optimisation (PSO) is applied inside a coevolutionary training environment to evolve the weights of the neural network. The training technique is applied to both the zero sum and non-zero sum game domains, with specific application to Tic-Tac-Toe, Checkers and the Iterated Prisoner's Dilemma (IPD). The influence of the various PSO parameters on playing performance are experimentally examined, and the overall performance of three different neighbourhood information sharing structures compared. A new coevolutionary scoring scheme and particle dispersement operator are defined, inspired by Formula One Grand Prix racing. Finally, the PSO is applied in three novel ways to evolve strategies for the IPD -- the first application of its kind in the PSO field. The PSO-based coevolutionary learning technique described and examined in this study shows promise in evolving intelligent evaluators for the aforementioned games, and further study will be conducted to analyse its scalability to larger search spaces and games of varying complexity.

Back to top

Mining continuous classes using evolutionary computing.
Gavin Potgieter. 2003.

Download this paper.

Abstract:

Data mining is the term given to knowledge discovery paradigms that attempt to infer knowledge, in the form of rules, from structured data using machine learning algorithms. Specifically, data mining attempts to infer rules that are accurate, crisp, comprehensible and interesting. There are not many data mining algorithms for mining continuous classes. This thesis develops a new approach for mining continuous classes. The approach is based on a genetic program, which utilises an efficient genetic algorithm approach to evolve the non-linear regressions described by the leaf nodes of individuals in the genetic program's population. The approach also optimises the learning process by using an efficient, fast data clustering algorithm to reduce the training pattern search space. Experimental results from both algorithms are compared with results obtained from a neural network. The experimental results of the genetic program is also compared against a commercial data mining package (Cubist). These results indicate that the genetic algorithm technique is substantially faster than the neural network, and produces comparable accuracy. The genetic program produces substantially less complex rules than that of both the neural network and Cubist.

Back to top

Niching Particle Swarm Optimizers
Riaan Brits. 2003.

Download this paper.

Abstract:

This research extends the inherent unimodal nature of particle swarm optimizers to efficiently locate multiple optimal solutions in multimodal problems. New algorithms, based on topological neighborhoods and subswarms, inspired by genetic algorithm research in niching and speciation, are used to form multiple, stable niches.

Back to top

The Artificial Immune System with Evolved Lymphocytes
Attie Graaff. 2003.

Download this paper.

Abstract:

The natural immune system can be modeled into an artificial immune system that can be used to detect any unwanted patterns in a non-biological environment. One of the main tasks of an immune system is to learn the structure of these unwanted patterns for a faster response to future foreign patterns with the same or similar structure. The artificial immune system (AIS) can therefor be seen as a pattern recognition system. The AIS contains artificial lymphocytes (ALC) that classify any pattern either as part of a predetermined set of patterns or not. It is possible for an ALC to classify more than one pattern and even classify a pattern better than other ALCs. The ALCs that never classify any pattern need to be replaced by newly created or evolved ALCs. It is therefore important to know what ALCs need to be replaced so that ALCs with a better classification are kept. In the natural immune system the lymphocytes have different states: Immature, Mature, Memory or Annihilated. Lymphocytes in the annihilated state needs to be replaced by newly created or evolved lymphocytes. The thesis presents an AIS for detection of unwanted patterns and proposes a threshold function to determine the state of an ALC.

Back to top

Training Support Vector Machines with Particle Swarms
Ulrich Paquet. 2003.

Download this paper.

Abstract:

I am doing research on Particle Swarm Optimisation for optimising functions f(x) with linear equality constraints Ax = b, and linear inequality constraints. This is used to train Support Vector Machines. Training a SVM requires solving a quadratic programming program with dimension equal to the number of training examples. I am currently working on methods of decomposing the problem and optimising the smaller subproblems using the PSO developed for constrained optimisation.

Back to top

An Analysis of Particle Swarm Optimizers
Frans van den Bergh. 2001.

Download this paper.

Abstract:

Many scientific, engineering and economic problems involve the optimization of a set of parameters. These problems include examples like minimising the losses in a power grid by finding the optimal configuration of the components, or training a neural network to recognise images of people's faces. Numerous optimisation algorithms have been proposed to solve these problems, with varying degrees of success. The Particle Swarm Optimizer (PSO) is a relatively new technique that has been empirically shown to perform well on many of these optimisation problems. This research develops a theoretical model that can be used to describe the long-term behaviour of the algorithm. An enhanced version of the PSO is constructed and shown to have guaranteed convergence on local minima. This algorithm is extended further, resulting in an algorithm with guaranteed convergence on global minima. A model for constructing cooperative PSO algorithms is also developed, resulting in the introduction of two new PSO-based algorithms. The new PSO models are applied to function optimization tasks and training of product unit neural networks.

Back to top

Training and Optimization of Product Unit Neural Networks
Adiel Ismail. 2001.

Download this paper.

Abstract:

Product units in the hidden layer of multilayer neural networks provide a pwerful mechanism for neural networks to efficiently learn higher-order combinations of inputs. Training product unit neural networks using local optimization algorithms is difficult due to an increased number of local minima and increased chances of network paralysis. This research investigates the problems using local optimization, especially gradient descent, to train product unit neural networks, and shows that particle swarm optimization, genetic algorithms and leapfrog are efficient alternatives to successfully train product unit neural networks. Architecture selection, i.e. pruning, of product unit neural networks is also studied and a pruning algorithm developed.

Back to top