Advanced Techniques of Genetic Algorithm & Application

INTRODUCTION

The genetic algorithm (GA) is finding wide acceptance in many disciplines. This paper introduces the elements of GAs and their application to environmental science problems. The genetic algorithm is an optimization tool that mimics natural selection and genetics. The parameters to be optimized are the genes, which are strung together in an array called a chromosome. A population of chromosomes is created and evaluated by the cost function, with the ―most fit‖ chromosomes being kept in the population while the ―least fit‖ ones are discarded. The chromosomes are then paired so they can mate, involving combining portions of each chromosome to produce new chromosomes. Random mutations are imposed. The new chromosomes are evaluated by the cost function and the process iterates. Thus the parameter space is explored by a combination of combining parts of the best solutions as well as extending the search through mutations. The trade-offs involved in selecting population size, mutation rate, and mate selection are briefly discussed below. The key to using GAs in environmental sciences is to pose the problem as one in optimization. Many problems are quite naturally optimization problems, such as the many uses of inverse models in environmental science. Other problems can be manipulated into optimization form by careful definition of the cost function, so that even nonlinear differential equations can be approached using GAs. Examples of both the natural type as well as those contrived into an optimization form are presented. GAs are well suited to many optimization problems where more traditional methods fail. Some of the advantages they have over conventional numerical optimization algorithms are that they: • Optimize with continuous or discrete parameters, • Don‘t require derivative information, • Simultaneously search from a wide • sampling of the objective function surface, • Deal with a large number of parameters, • Are well suited for parallel computers, • Optimize parameters with extremely complex objective function surfaces, • Provide a list of semi-optimum parameters, not just a single solution, • May encode the parameters so that the optimization is done with the encoded parameters, and • Works with numerically generated data, experimental data, or analytical functions.

In the following sections we give a short overview of how the GA works, briefly review some of the ways that GAs have been used in environmental science, and present an example application that demonstrates the strength of the GA on an inverse problem.

When the initial generation is generated, the GA evolves the generation using the operators, discussed as follows.

In this kind of operator, the individuals have a preference with better fitness score and enable them to pass their gene to the successive generation of the individual.

This reflects a generation of breeding among persons. Randomly choose two individuals using selection operators and crossover operators. After chosen, genes are at the crossover sites exchanged, so building a completely new offspring or individual. Figure 2 shows the crossover operator.

To use this tool, introduce random genes into offspring to retain the genetic heterogeneity to prevent excessive divergences. Figure 3 shows the mutation process.

John Holland is often referred to as the ―father of genetic algorithms.‖ He developed this brand of genetic programming during the 1960‘s and 1970‘s gaspipeline transmission for his dissertation (see Goldberg 1989). Since that time, they have been applied to a wide variety of problems, including those described above. The following explanation follows the flow chart in Figure 1. The first step is defining an objective function with inputs and outputs. A binary GA encodes the value of each input parameter (e.g. a, b, c, d) as a binary number. The parameter values are then placed side by-side in an array known as a chromosome.

A population is a matrix with each row representing a chromosome. The algorithm begins with a population consisting of random ones and zeros (see Figure 2).

These random binary digits translate into guesses of values of the input parameters. Next, the binary chromosomes are converted to continuous values which are evaluated by the objective function. Mating takes place between selected chromosomes. Mates are randomly selected with a probability of selection greater for those chromosomes yielding desirable output from the objective function (tournament or roulette wheel selection). Offspring (new chromosomes) result by keeping the binary strings to the left of the crossover point for each parent and swapping the binary strings to the right of the crossover point, as shown in Figure 3. Crossover mimics the process of meiosis in biology. Mutations randomly convert some of the bits in the population from ―1‖ to ―0‖ or visa versa. The objective function outputs associated with the new population are calculated and the process repeated. The algorithm stops after finding an acceptable solution or after completing a set number of iterations.

Selecting the best population size, mating scheme, and mutation rate is still an area of controversy. Haupt and Haupt (1998, 2000) address some of these issues. Since the GA is a random search, a certain population size and mutation rate can give considerably different answers for different independent runs. A GA run will give a good answer found from a wide exploration of the search space but not necessarily the best answer. Most real world optimization problems have multiple objectives. Multiple objectives can be handled by weighting and adding the fitness from each objective. Multi-objective optimization does not have a single optimum solution relative to all objectives. Instead, there are a set of optimal solutions, known as Pareto-optimal or non-inferior solutions. A Pareto GA attempts to find as many Pareto optimal solutions as possible, since all these solutions have the same cost.

The GA is used in genetics-based machine learning that is an emerging area. The GAs are essential to machine learning for three factors. Firstly, it operates in discrete spaces where gradient-based techniques could not be applied. This could be used to check for rulesets, neural network structures, cellular automation machines, and many more. In this way, this could be used while stochastic high scaling and optimization algorithms could also be regarded. Secondly, these are reinforced learning techniques. A specific variable, fitness, is used to assess the efficiency of the learning technique. Eventually, GA requires a population, and often whatever one needs is not a single individual, however, a community.

The GA can be used for different digital imaging activities and the equivalent heavy pixel's algorithms. Segmentation of images is one of the key problems in the area of image processing. A lot of efficient methods are available to solve this issue. Its purpose of such a method is to divide the digital image into multiple segments based on genetic or conceptual similarities. Its purpose is to investigate the implementation of GA in the segmentation of images.

Multiple soft time frames, multiple depots, and heterogeneous fleet problems are also solved through the GA. Vehicle routing problems are consisting of a variety of consumers, every needing the same amount of the products to be transported. The vehicle is delivered from a single warehouse will supply the products needed and returns to the warehouse. That vehicle could bring a specific weight and could also be reduced to the distance traveled it can carry. Every consumer is permitted to visit just one vehicle. An issue is the alternative range of distribution routes that meet these criteria and have low overall costs. Throughout fact, it is also seen as analogous to reducing the total distance covered, or reducing the number of vehicles utilized, and instead of decreasing the total distance for this number of units.

The GA has been most widely used in optimized challenges where we have to maximize or reduce a given objective function value through a given set of conditions. Such a strategy will solve a problem related to optimization. The optimization raises issues of minimizing or optimizing variables with several factors that are typically subject to fairness and inequalities restrictions. This plays a pivotal role in research, marketing, and manufacturing operations. Several challenges of industrial engineering architecture are very complex and hard to overcome using traditional optimization algorithms. Within past years, GA has attracted significant attention to its capacity as an innovative optimization methodology. Depending on their usability, ease of activity, minimum specifications, and simultaneous and international viewpoint, GA has been commonly applied to a variety of issues .

The GA becomes very strong multimodal computation methods through that we need to find solutions to several optimal problems. For technical challenges due to the physical and expense limitations, even better results achieved by a

execution could be easily moved to another approach without much disruption in the design stage. It introduces a swarm multimodal optimization algorithm called cooperative human behavior.

The GA can also be used to describe various financial systems such as the cobweb system, the resolution of game theory optimization, asset pricing, etc. Several economists have started to use GAs to fix common shortcomings of conventional economic models while retaining a convenient mathematical structure. The optimization of GA happens in a way that can mimic the complexities of real decision-making issues. Also, it eliminates the need for a fixed structure to the policy problem and therefore can determine between alternate optimizations.

GA also serves to practice machine learning, particularly recursive neural networks. GA is a meta-heuristic method influenced by the natural selection mechanism which belongs to the larger network of evolution optimizations. The GA is widely used to produce high-quality alternatives for computation and problem finding by focusing on bio-inspired operations like selection, mutation, and crossover. This algorithm is a reliable approach to evolutionary optimization based on biological concepts. The population of strings describing potential solutions to problems is developed .

The GA seems to have very good simultaneous functionality and proves to be a very successful way to solve such problems, as well as providing a good study area. This approach is a populations-based computational optimizations technique that have been utilized to effectively train neural network systems. But, if many people making up the population, the runtime of the algorithm is always very large. Parallelism computing is a methodology that can theoretically be used to tackle this problem. Through the study explores the implementation of a parallel GA for the search for optimal specifications of artificial neural networks system. The Palatalization is accomplished using the Inter processes communication Framework, wherein sub-populations are shared among processors during selection, mutation, and crossover.

A schedule at scheduling issues typically includes contradictory priorities based on the cost of the individual and the cost of the operator. Consumers tend to spend less time waiting, changing, and of vehicles. So far as the quality of service is involved, consumers are engaged in lower crowing whereas providers are involved with increasing income and therefore have high lead levels. Waiting time performs a significant role in scheduling planning issues. Customers are interested in integrating services with reasonable waiting times, while operators tend to provide fewer services. The GA is used to solve various scheduling problems such as timetables and so on.

The GA can be used to design the route taken by a robotic arm from each stage to another. Various GA implementations in the area of robotic trajectory modelling have been conducted out over the last few generations. This algorithm, which is versatile public-purpose optimization algorithms, was used to produce collision-free paths for a robot with defined begin and target mutual specifications. A code system and fitness analysis are the main features of the design of the algorithm. Fitness evaluation included a measured total of the distance, time, and collisions consequences for each route.

The GA is used to design aircraft by changing variables and creating better approaches in the field of motion. A cheaper aircraft could never be the strongest, and the most effective would not be the most convenient. Under other terms, the final aircraft is still, in some context, a collaboration. Different measurements are included in the feature referred to as a quality or quantitative statistic, like value, control surfaces, mechanisms, production, fuel consumption, disturbance, and aviation dynamics, the relative weight of which depends on the expected aircraft usage.

GA has been used to evaluate the DNA structure using specimen spectrometric information. In recent years, the field of bioinformatics has progressed exponentially. Advancements in genomic engineering have contributed to an increase in the generation of genetic information. Such a role is challenged by the lack of awareness of genetic characteristics, as quality-altering hypotheses can quickly be implemented during algorithm construction, and the technique can easily become redundant. The GAs is an evolution-inspired category of machine learning algorithms that are very promising to solve such challenges. Image Segmentation. 2. To study the genetic algorithm works begins by creating a random initial population.

Image segmentation is important problem and there available numerous image segmentation methods. Most of these methods were developed to be used on a certain class of images and therefore aren‘t general image segmentation methods. Bhanu and Lee divide the image segmentation algorithms into three major categories:

Edge detection includes the detection of boundaries between different regions of the image. Due to these boundaries discontinuities occurs between the pixels of the chosen feature such as color, texture and intensity.

Region splitting is an image segmentation method in which pixels are classified into regions. Each region has a range of feature values, with thresholds being delimiters. It is very important to choose these thresholds, as it greatly affects the quality of the segmentation. This tends to excessively split regions, resulting in over segmentation.

Clustering separates the image into various classes without any prior information. In this the data which belong to same class should be as similar as possible and the data which belongs to different class should be as different as possible.

Image Segmentation has many applications which are: 1. Face recognition 2. Fingerprint recognition 3. Medical imaging such as: • Locate tumors and other pathologies • Measure tissue volumes • Computer-guided surgery • Diagnosis 4. Locate objects in satellite images (roads, forests, etc.) 5. Iris recognition 6. Traffic control systems 7. Brake light detection 8. Machine vision 9. Agricultural imaging – crop disease detection etc.

There are many algorithms for image segmentation. But due to different constraint it is difficult to find the optimal solution. In, it classifies the belonging of the pixels and then use region growing to get the object. Linking the area information and color histogram for building video databases based on objects was proposed in . In a genetic algorithm based segmentation process to change the image characteristics caused by variable environmental condition was proposed. In a twos tep approach to image segmentation is reported. The authors in proposed a graph-based method.

The space for all possible feasible solutions is called search space. Each solution can be marked by its value of the fitness of the problem. Looking for the solution means looking for extrema (either maximum or minimum) in search space. The search space can be known by the time of solving a problem and we generate other points as the process of finding the solution continues. (Shown in fig. 1)

chromosomes, which encode candidate solutions to an optimization problem, evolves toward better solutions. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (crossover and mutation) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached

Genetic Algorithm consists of the following steps: Step1: Choose the initial population of individuals Step2: Evaluate the fitness of each individual in that population Step3: Repeat on this generation until termination (time limit, sufficient fitness achieved etc.): • Select the best-fit individuals for reproduction. • Breed new individuals through crossover and mutation operations to give birth to offspring • Evaluate the individual fitness of new individuals • Replace least-fit population with new individuals

For Image Segmentation Farmer and Shugars divide the genetic algorithms used for image segmentation into two major classes: Parameter selection, where genetic algorithms are used to modify the parameters of an existing image segmentation method to improve its output. 1. Pixel-level segmentation, where genetic algorithms are used to perform region labeling.

The GA is a probabilistic solution to optimize the problems that are modeled on a ge-netic evaluation process in biologically and are focused as an effective algorithm to find a global optimum solution for many types of problems. The GA is used in different artificial intelligence applications like object-oriented systems, robotics, and futuristic emerging technologies. Genetic Algorithm has many advantages in obtaining the optimized solution. It was proved to be the most powerful optimization technique in a large space. Genetic algorithm allows performing robust search for finding the global optimum. Genetic algorithm allows performing robust search for finding the global optimum. The result of the optimization depends on the chromosome encoding scheme and involvement of genetic operators as well as on the fitness function. However, the quality of image segmentation can be improved by selecting the parameters in an optimized way.

[1] Aly, A.H. and R.C. Peralta (1999a). Comparison of a genetic algorithm and mathematical programming to the design of groundwater cleanup systems, Water Resources Research, 35(8), pp. 2415-2425. [2] Aly, A.H. and R.C. Peralta (1999b). Optimal design of aquifer clean up systems under uncertainty using a neural network and a genetic algorithm, Water Resources Research, 35(8), pp. 2523-2532. [3] Barth, H. (1992). Oceanographic Experiment Design II: Genetic Algorithms, Journal of Oceanic and Atmospheric Technology, 9, pp. 434-443. [4] Boschetti, F., Dentith, M.C. and List, R. D. (1995). A staged genetic algorithm for tomographic inversion of seismic refraction data. Exploration Geophysics 26, pp. 331-335. [5] Boschetti, F., Dentith, M.C. and List, R. D. (1996). Inversion of seismic refraction data using genetic algorithms. Geophysics 61, pp. 1715-1727. [6] Cartwright, H.M. and S.P. Harris (1993). Analysis of the Distribution of Airborne Pollution using Genetic Algorithms, [7] Fayad, H. (2001). Application of neural networks and genetic algorithms for solving conjunctive water use problems, Ph.D. Dissertation, Utah State University, 152 pp. [8] Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, New York: Addison-Wesley. [9] Hart, J., I. Hunt, V. Shankararaman (1998). Environmental management systems – a role for AI?, ECAI 98 W7 Binding Environmental Sciences and AI. [10] Jervis, M., M.K. Sen, and P.L. Stoffa (1996). Prestack Migration Velocity Estimation using Nonlinear Methods, Geophysics, 60, pp. 138- 150. [11] Kim, S., H. Lee, J. Kim, C. Kim, J. Ko, H. Woo, and S. Kim (2002). Genetic algorithms for the application of Activated Sludge Model No. 1, Water Science and Technology, 45 (4-5), pp. 405-411. [12] Mulligan, A.E. and L.C. Brown (1998). Genetic algorithms for calibrating water quality models, J. of Environmental Engineering, pp. 202-211. [13] Porsani, M. J., P. L. Stoffa, M. K. Sen, and R. K. Chunduru (2000). Fitness functions, genetic algorithms and hybrid optimization in seismic waveform inversion, J. Seismic Explor., 9, pp. 143-164. [14] Ritzel, B.J., J.W. Eheart, and S. Rajithan (1994). Using geteic algorithms to solve a multiple objective groundwater pollution containment problem, Water Resources Research, 30(5), pp. 1589-1603. [15] Rogers, L.L. and F.U. Dowla (1994). Optimization of groundwater remediation using artificial neural networks with parallel solute transport modeling, Water Resources Research, 30(2), pp. 457-481. [16] Sen, M.K. and P.L. Stoffa (1992). Rapid Sampling of Model Space using Genetic Algorithms: Examples from Seismic Waveform Inversion, Geophys. J. Int., 108, pp. 281-292.

Madhyanchal Professional University, Bhopal