Genetic Algorithms (GAs) are adaptive heuristic search algorithm premised on the evolutionary ideas of natural selection and genetic. The basic concept of GAs is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Charles Darwin of survival of the fittest. As such they represent an intelligent exploitation of a random search within a defined search space to solve a problem.
First pioneered by John Holland in the 60s, Genetic Algorithms has been widely studied, experimented and applied in many fields in engineering worlds. Not only does GAs provide an alternative methods to solving problem, it consistently outperforms other traditional methods in most of the problems link. Many of the real world problems involved finding optimal parameters, which might prove difficult for traditional methods but ideal for GAs. However, because of its outstanding performance in optimisation, GAs have been wrongly regarded as a function optimiser. In fact, there are many ways to view genetic algorithms. Perhaps most users come to GAs looking for a problem solver, but this is a restrictive view [ De Jong ,1993 ] .
Herein, we will examine GAs as a number of different things:
However, due to various constraints, we would only be looking at GAs as pro blem solvers and competent machine learning here. We would also examine how GAs is applied to completely different fields.
Many scientists have tried to create living programs. These programs do not merely simulate life but try to exhibit the behaviours and characteristics of a real organisms in an attempt to exist as a form of life. Suggestions have been made that alife would eventually evolve into real life. Such suggestion may sound absurd at the moment but certainly not implausible if technology continues to progress at present rates. Therefore it is worth, in our opinion, taking a paragraph out to discuss how Alife is connected with GAs and see if such a prediction is far fetched and groundless.
GAs were introduced as a computational analogy of adaptive systems. They are modelled loosely on the principles of the evolution via natural selection, employing a population of individuals that undergo selection in the presence of variation-inducing operators such as mutation and recombination (crossover). A fitness function is used to evaluate individuals, and reproductive success varies with fitness.
The paradigm of GAs descibed above is usually the one applied to solving most of the problems presented to GAs. Though it might not find the best solution. more often than not, it would come up with a partially optimal solution.
Nearly everyone can gain benefits from Genetic Algorithms, once he can encode solutions of a given problem to chromosomes in GA, and compare the relative performance (fitness) of solutions. An effective GA representation and meaningful fitness evaluation are the keys of the success in GA applications. The appeal of GAs comes from their simplicity and elegance as robust search algorithms as well as from their power to discover good solutions rapidly for difficult high-dimensional problems. GAs are useful and efficient when
The advantage of the GA approach is the ease with which it can handle arbitrary kinds of constraints and objectives; all such things can be handled as weighted components of the fitness function, making it easy to adapt the GA scheduler to the particular requirements of a very wide range of possible overall objectives.
GAs have been used for problem-solving and for modelling. GAs are applied to many scientific, engineering problems, in business and entertainment, including:
The TSP is interesting not only from a theoretical point of view, many practical applications can be modelled as a travelling salesman problem or as variants of it, for example, pen movement of a plotter, drilling of printed circuit boards (PCB), real-world routing of school buses, airlines, delivery trucks and postal carriers. Researchers have tracked TSPs to study biomolecular pathways, to route a computer networks' parallel processing, to advance cryptography, to determine the order of thousands of exposures needed in X-ray crystallography and to determine routes searching for forest fires (which is a multiple-salesman problem partitioned into single TSPs). Therefore, there is a tremendous need for algorithms.
In the last two decades an enormous progress has been made with respect to solving travelling salesman problems to optimality which, of course, is the ultimate goal of every researcher. One of landmarks in the search for optimal solutions is a 3038-city problem. This progress is only party due to the increasing hardware power of computers. Above all, it was made possible by the development of mathematical theory and of efficient algorithms. Here, the GA approach is discussed.
There are strong relations between the constraints of the problem, the representation adopted and the genetic operators that can be used with it. The goal of traveling Salesman Problem is to devise a travel plan (a tour) which minimises the total distance travelled. TSP is NP-hard (NP stands for non-deterministic polynomial time) - it is generally believed cannot be solved (exactly) in time polynomial. The TSP is constrained:
When GAs applied to very large problems, they fail in two aspects:
To use a standard GA, the following problems have to be solved:
Thus, permutation matrices are used. Two tours including the same cities in the same order but with different starting points or different directions are represented by different matrices and hence by different chromosomes, for example:
tour (23541) = tour (12354)
However, the ordinary genetic operators generate too many invalid solutions, leading to poor results. Alternative solutions to TSP require new representations ( Position Dependent Representations) and new genetic operators.
This approach, EDAC [Valenzuela 1995], has potential for any search problem in which knowledge of good solutions for subproblems can be exploited to improve the solution of the problem itself. The idea is to use the Genetic Algorithm to explore the space of problem subdivisions rather than the space of solutions themselves, and thus capitalise on the near linear scaling qualities generally inherent in the divide and conquer approach.
The basic mechanisms for dissecting a TSP into subproblems, solving the subproblems and then patching the subtours together to form a global tour, have been obtained from the cellular dissection algorithms of Richard Karp. Although solution quality tends to be rather poor, Karp`s algorithms possess an attractively simple geometrical approach to dissection, and offer reasonable guarantees of performance. Moreover, EDAC approach is intrinsically parallel.
The EDAC approach has lifted the application of GAs to TSP an order or magnitude larger in terms of problem sizes than permutation representations. Experimental results demonstrate the successful properties for EDAC on uniform random points and PCB problems in the range 500 - 5000 cities.
Genetic Algorithms have been used to solve many different types of business problems in functional areas such as finance, marketing, information systems, and production/ operations. Within these functional areas, GAs have performed a variety of applications such as tactical asset allocation, job scheduling, machine-part grouping, and computer network design.
Models for tactical asset allocation and international equity strategies have been improved with the use of GAs. They report an 82% improvement in cumulative portfolio value over a passive benchmark model and a 48% improvement over a non-GA model designed to improve over the passive benchmark.
Genetic algorithms are particularly well-suited for financial modelling applications for three reasons:
Distributed computer network topologies are designed by a GA, using three different objective functions to optimise network reliability parameters, namely diameter, average distance, and computer network reliability. The GA has successfully designed networks with 100 order of nodes.
GA has also been used to determine file allocation for a distributed system. The objective is to maximise the programs' abilities to reference the file s located on remote nodes. The problem is solved with the following three different constraint sets:
Genetic Algorithm has been used to schedule jobs in a sequence dependent setup environment for a minimal total tardiness. All jobs are scheduled on a single machine; each job has a processing time and a due date. The setup time of each job is dependent upon the job which immediately precedes it. The GA is able to find good, but not necessarily optimal schedules, fairly quickly.
GA is also used to schedule jobs in non-sequence dependent setup environment. The jobs are scheduled on one machine with the objective of minimising the total generally weighted penalty for earliness or tardiness from the jobs' due dates. However, this does not guarantee that it will generate optimal solutions for all schedules.
GA is developed for solving the machine-component grouping problem required for cellular manufacturing systems. GA provides a collection of satisfactory solutions for a two objective environment (minimising cell load variation and minimising volume of inter cell movement), allowing the decision maker to then select the best alternative.
Applying the well established decision processing phase model of Simon (1960), Genetic Algorithms appear to be very well suited for supporting the design and choice phases of decision making.
GAs can be of great assistance for examining alternatives since they are designed to evaluate existing potential solutions as well to generate new (and better) solutions for evaluation. Thus GAs can improve the quality of decision making.
The approach to learning behaviours, which lead the robot to its goal, described here reflects a particular methodology for learning via simulation model. The motivation is that making mistakes on real system can be costly and dangerous. In addition, time constraints may limit the extent of learning in real world. Since learning requirs experimenting with behaviours that might occassionally produce undesriable results if applied to real world. Therefore, as shown in the diagram, the current best behaviour can be place in the real, on-line system, while learning continues in the off-line system.
Previous studies have shown that knowledge learned under simulation is robust and might be applicable to the real world if the simulation is more general ( add more noise and distortion) . If this is not possible, the differences between the real world and the simulation have to be identified.
Genetic Alogrithms are adaptive search techniques that can learn high performance knowledge structures. The genetic algorithms' strength come from the implicitly parrallel search of the solution space that it performs via a population of candidate solutions and this population is manipulated in the simulation. The candidate solutions represent every possible behaviour of the robot and based on the overall performance of the candidates, each could be assigned a fitness value. Genetic operators could then be applied to improve the performance of the population of behaviours. One cycle of testing all of the competimg behaviour is defined as a generation, and is repeated until a good behaviours is evolved. The good behaviour is then applied to the real world. Also because of the nature of GA, the initial knowledge does not have to be very good.
The system described has been used to learn behaviours for controlling simulate autonomous underwater vehicles, missile evasion, and other simulated tasks. Future work will continue examining the process of building robotic system through evolution. We want to know how multiple behaviours that will be required for a higher level task interact, and how multiple behaviours can be evolved simultaneously. We are also examining additional ways to bias the learning both with initial rule sets, and by modifying the rule sets during evolution through human interaction. Other open problems include how to evolve hierachies of skills and how to enable the robot to evolve new fitness functions as the need for new skill arises.
In order to provide machines with the ability to interact in complex, real-world environments, sensory data must be presented to the machine. One such module dealing with sensory input is the visual data processing module, also known as the computer vision module. A central task of this computer vision module is to recognise objects from images of the environment.
There are two different parts to computer vision modules, namely segmentation and recognition. Segmentation is the process of finding interested objects while recognition works to see if the located object matches the predefined attributes. Since images cannot be recognised until they have been located and separated from the background, it is of paramount importance that this vision module is able to locate different objects of interest for different systems with great efficiency.
It has been shown that the genetic algorithm perform better in finding areas of interest even in a complex, real-world scene. Genetic Algorithms are adaptive to their environments, and as such this type of method is appealing to the vision community who must often work in a changing environment. However, several improvements must be made in order that GAs could be more generally applicable. Grey coding the field would greatly improve the mutation operation while combing segmentation with recognition so that the interested object could be evaluated at once. Finally, timing improvement could be done by utilising the implicit parallelization of multiple independent generations evolving at the same time.
Genetic algorithms are currently the most prominent and widely used computational models of evolution in artificial-life systems. This decentralised models provide a basis for understanding many other systems and phenomena in the world. Researches on GAs in alife give illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems.
In the rapidly converging telecommunications industry, technology never stops changing. To assist telecom managers in adapting and prospering during this turbulent period, a business-simulation program, TeleSim, is developed, using artificial life approach. This training tool is designed to provide thought leadership and training for managers facing the challenges of a rapidly changing marketplace.
A TeleSim player acts as a manager in a telecommunications company and pilots the company through a simulated marketplace testing various scenarios and the impact on operations, competitor response and customer behaviour. The player confronts with internal staff communications, regulatory penalties, natural disasters, and financial/ technological trade-offs similar to those that managers face in the real world.
In this virtual telecommunications marketplace, the TeleSim player faces seven competitors, which are modelled using adaptive agent technology. The competitive agents interact, adapt to each other, and to the decisions of the player. The competitors learn to execute the best strategic moves as they adapt to the ever changing environment. This emerging and evolving world involves convergence in technology as well as changes in the market and regulations, demonstrating some self-organising behaviours.
Simulations let people experience and think through the complexity of the business situation and make experiments that they could not possibly do in the real world. People learn to make decisions and gain a better understanding of what present management has been doing. TeleSim allows for a more interactive computer-based approach to scenario development and strategic planning. TeleSim simulates telecommunications businesses, designed as a tool for business planning and management training. In TeleSim, the player learns to develop strategic plans to assess market opportunities and determine an organisation's capability for pursuing the dynamics of its strategic direction.
Artificial-life programmer claim that, with the help of the increasingly advanced technology, they will soon go beyond merely modelling or simulating living organisms and actually create life. The claim is not simply that one could design an artificial life with the help of a computer, and then build it out of organic molecules. They claim that one could creat living organism simply by programming a computer in a right way. If today's virus is not alive, tommorrow's will be. Computer equivalent of worm, frog would soon be rampaging in the networks. This claim is known as "strong A-life", as opposed to " weak A-life". Obviously there are two schools of thought regarding to this claim.
Foes of strong-A-life argue that no matter how advance computer technology would become, life cannot be created simply by programming a computer. They put forward the arguments:
A computer generated life is not a material object. When one talks about living organism, it is a kind of material object: something that takes up space and has a mass, a chemical composition, and other physical properties. Material objects are something that satisfy most proposed definitions of life: they take in matter, utilize its energy, and expel its remains in a less ordered form; they have well-defined boundaries; they can reproduce themselves with great accuracy; and so on. On the contrary computer generated life forms do not satisfy these definitions of life.
It can not move about. The only movements one could detect from computer generated organism are contraction and expansion.
It is not capable of dying. Computer generated life forms can not really die. Real organism is made up of molecules arranged in an extremely complex and delicate way. When an organism dies, the arrangement is destroyed. However, the life of artificial life ceases to exit when the machine on which it is running stops. But the program hardly dies since when the machine is turned back on, computer generated life "resurrects".
Same individual but have different life span on different machines. When a program, regarded as the artificial life, is run on two machine, the two instances of the program are supposed to have identical attribute and thus can be assumed to be the same individual. However, clearly two instances could have different life span if one of the machine stops running before the other. This is absolutely nonsense in the context of real life. It literally means that one individual could die more than once.
Supporters of strong a-life obviously think otherwise. One of the more prominent supporter, Christopher Langton , writes that the artificial life created do not live in the medium as we know. It is in a virtual medium where they reside. He further argues that models built could be so real that they would cease to be models of life and become examples of life themselves. He claims that any definition or list of criteria broad enough to include all known biological life will also include certain classes of computer processs and therefore will have to be considered as "actually alive".
If the conception of a computer algorithms being based on the evolutionary of organism is surprising, the extensiveness with which this algorithms is applied in so many areas is no less than astounishing. These applications, be they commercial, educational and scientific, are increasingly dependent on this algorithms, the Genetic Algorithms. Its usefulness and gracefulness of solving problems has made it the a more favourite choice among the traditional methods, namely gradient search, random search and others. GAs are very helpful when the developer does not have precise domain expertise, because GAs possess the ability to explore and learn from their domain.
In this report, we have placed more emphasis in explaining the use of GAs in many areas of engineering and commerce. We believe that, through working out these interesting examples, one could grasp the idea of GAs with greater ease. We have also discuss the uncertainties about whether computer generated life could exist as real life form. The discussion is far from conclusive and ,whether artificial life will become real life, will remain to be seen.
In future, we would witness some developments of variants of GAs to tailor for some very specific tasks. This might defy the very principle of GAs that it is ignorant of the problem domain when used to solve problem. But we would realize that this practice could make GAs even more powerful.
Back to my Homepage