This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Many artificial Intelligent (A.I) techniques are applied in image processing. We still try to get better result in order to perform the best application for professional used. This paper proposed to analyze the strength and weaknesses of the several evolutionary algorithms. The algorithms are Genetic Algorithm, Memetic Algorithm and Selfish Gene Algorithm. It is also reviews the applications of Evolutionary Computation Algorithm techniques within the fields of image processing.
Methodology for this project includes data collection and data analysis. For data collection, the data are gathered from books, journals or articles. It is the importance part in doing a research. Literature review is come out from that data which is review the aspect of the problem already studied by other researchers. While in data analysis, spider diagram is used to show how this review is going on. Spider diagrams introduced as a visual technique intended to be used in conjunction with the Unified Modeling Language (UML) for object oriented modeling and it is emerged from work on constraint diagrams, (Howse. J. et al, 2005)
Figure 1. Spiders diagram that shown the branch of Evolutionary Algorithm in the Image processing Field.
Evolutionary Computation Algorithm
Evolutionary algorithms (EAs) are computer programs that attempt to solve complex problems by mimicking the processes of Darwinian evolution. In an EA a number of artificial creatures search over the space of the problem. They compete continually with each other to discover optimal areas of the search space. It is hoped that over time the most successful of these creatures will evolve to discover the optimal solution (Jones G., 2004).
2.1 Evolutionary Algorithms (EAs)
As the history of the field suggests there are many different variants of Evolutionary Algorithms (EAs). The common underlying idea behind all these techniques is the same: given a population of individuals the environmental pressure causes natural selection (survival of the fittest) and this causes a rise in the fitness of the population. Given a quality function to be maximized we can randomly create a set of candidate solutions.
Another research by Sbalzarini I.F et al (2000) stated that EAs such as evolution strategies (ES) and genetic algorithms (GA) have become the method of choice for optimization problems that are too complex to be solved using deterministic techniques such as linear programming or gradient method. EAs require little knowledge about the problem being solved, and they are easy to implement, robust, and inherently parallel. To solve a certain optimization problem, it is enough to require that one is able to evaluate the objective (cost) function for a given set of input parameters. Because of their universality, ease of implementation, and fitness for parallel computing, EAs often take less time to find the optimal solution than gradient methods.
There are three main independent implementation instances of EAs: Genetic Algorithms (GAs) that developed by Holland, evolution strategies (ES) developed in Germany by Rechenberg and Schwefel and evolutionary programming (EP), originally developed by L.J.Fogel et al (J. Gareth, 2004).
2.1.1 Genetic Algorithms (GA)
Evolution is drive out by a process dependent on mutation and natural selection. Research by Talbi H. et al(2007), Genetic algorithms (GAs) are adaptive heuristic search algorithm that derives from the evolution theory. It is consists of three main operations: selection, crossover, and mutation. In the population, the selection evaluates each individual and keeps only the fittest ones. For those fittest individuals, it could be selected according to its probability. The others which are not fit will be removed from the current population. The crossover is when two individuals recombine to have new ones which might be better. While the mutation is a genetic operator that alters one ore more gene values in a chromosome from its initial state. It's used to tend the population diversified enough during the optimization process.
According to Pignalberi et al (2003), Genetic Algorithm (GA) is a well-known spread technique for exploring in parallel a solution space by encoding the concept of evolution in the algorithmic search: from a population of individuals representing possible problem solutions, evolution is carried out by means of selection and reproduction of new solutions.
Research by Huang C. F. and Rocha L M. (2004) illustrates that genetic algorithm operates on an evolving population of artificial organisms, or agents. Each agent is comprised of a genotype and a phenotype. Evolution occurs by iterated stochastic variation of genotype, and selection of the best phenotypes in an environment according to a fitness function. In machine learning, the phenotype is a candidate solution to some optimization problem, while the genotype is an encoding or description, of that solution by means of a domain independent representation, namely binary symbol strings (or chromosomes).
Genetic algorithms (GAs) derive from the evolution theory. They were introduced in 1975 by John Holland and his team as a highly parallel search algorithm. Later, they have been mainly used as an optimization device. According to the evolution theory, within a population only the individuals well adapted to their environment can survive and transmit some of their characters to their descendants. In genetic algorithms, this principle is traduced into the problem of finding the best individuals represented by chromosomes. So, each chromosome encodes a possible solution for the given problem and, starting from a population of chromosomes, the evolution process performs a parallel search through the solutions' space. The fitness is measured for each individual by a function related to the objective function of the problem to be solved.
2.1.2 Evolution Strategies (ES)
In computer science, evolution strategy (ES) is an optimization technique based on ideas of adaptation and evolution. Evolution strategies use natural problem-dependent representations, and primarily mutation and selection as search operators.
Yuan X et al (2008) stated that Evolution Strategies (ES) is an evolutionary computation algorithm that designed for real number function optimization and has been applied successfully too different application areas.
2.1.3 Genetic Programming (GP)
GP is a domain-independent method for enabling a computer to solve the problem automatically made from high-level statement. Using ideas from natural evolution, GP starting from single-stream random computer programs, and progressively sort them through processes of mutation and sexual recombination, until solutions emerge. All this without users know or which could ensure form or solution structure in advance. GP has given generation of ideas to researcher to be doing competitive decision and applications, including novel scientific discoveries and inventions patentable. (Poli R et al, 2008)
2.1.4 Selfish Gene Algorithm (SGA)
The Selfish Gene algorithm (SG) is a new evolutionary optimization algorithm based on the illumination of the Darwinian Theory given by English biologist Richard Dawkins. In the selfish gene theory, population is the number of individuals and can be seen as a pool of genes. Therefore, by representing and evolving some statistical parameters, the SG can helps to a statistical characterization of the population (Corno F., 2000). Research by Vasiliauskas A. (2008) showed the concept of selfish gene algorithm (SGA). Chromosome is also called genotype and all living organisms have DNA molecules. Genes is part of DNA molecule and gene location in DNA is called locus. Usually for the same locus there can be different versions of gene and it is called alleles. To determine the fittest chromosome or genotype, allele's frequencies or probabilities in population are calculated. Generally evolution means, that organism which succeeds will increases its allele's frequency in population at the expense of children. And organism which fails will decreases its allele's frequency in population.
Here are the main features of SGA.
There is no explicit population in algorithm. Individuals are created and destroyed
only temporary for comparison of their genomes.
Unfitted individual are not going to be destroyed permanently but are stored in a virtual population. This means that there is no recombination operator at all. Instead a new solution is generated according to their genes frequency in population.
Mutation operator is encoded as random gene selection not accordingly to frequencies.
Value of fitness are not going to be assign to generated solution but only need to compare two generated solution between each other.
Lastly, the better solution will return back to the algorithm.
2.1.5 Memetic Algorithm
Research by Garg P., 2009 stated that the memetic algorithms can be viewed as a hybrid between a population-based global technique and a local search made by each of the individuals. It is an extension of the traditional genetic algorithms with a local hill climbing as local search. The local search is used to improve its fitness. Same genetic algorithms, memetic algorithms are a population-based approach. From the present research, memetic algorithms have shown that their orders of magnitude faster than traditional genetic Algorithms for some problem domains.
In a memetic algorithm the population is initialized at random or using a heuristic. Then, every respectively individuals make local search to increase the fitness in order to form a new population. With the search result, higher quality individuals are selected to form next generation. Selection phase also similar and used deep in the classical genetic algorithm selection phase.
Once two parents have been selected, their chromosomes will be consolidated and the classical operators of crossover used to generate new individuals. Then, it is enhanced use local search technique. Local search objective in memetic algorithms is to detect local optimum more efficiently then genetic algorithm.
3.0 Results and discussion
Here is a table that compares steps in the Genetic Algorithm, Selfish Gene Algorithm, Memetic Algorithm (MA), Evolution Strategies (ES) and Genetic Programming (GP).
Table 1. Features of Genetic Algorithm, Selfish Algorithm, Memetic Algorithm, Evolution Strategies and Genetic Programming.
Chromosome contains the information about the solution that it's represent. The good results are found with the good representation of the chromosome. In genetic algorithm, there are various types of techniques in representing the chromosome or genotype. The types are binary encoding, permutation encoding and value encoding. This encoding can be use in all other algorithms. Representation of chromosome between Evolution Strategies, Genetic Algorithm and Genetic Programming are different. The major difference is that ES gene evolves in the real number domain, which avoids information loss due to the binary coding representation of GA. Where Genetic programming are using limited symbolic alphabet and represent as a tree structure.
The pressure part is in the parent selection, where the stochastic technique of roulette wheel is used to pick parents for the new population. For all algorithms, we also can use other selection techniques such as random selection and tournament selection. But differ than Memetic Algorithm where it is use heuristic search to pick its individuals for it population.
Population size is very important in not only to a genetic algorithm but all variant evolutionary algorithms. But due to its limited population size, a genetic algorithm may also give bad representatives of good search regions and good representatives of bad regions. In addition, genetic algorithm will produce solutions in low quality (El-Mihoub T.A et al, 2006). For a new population, there is a bit different between the selfish gene algorithm and other algorithm where it is use virtual population. In the selfish gene theory, individuals are not so important, and the population is seen as just a store of genetic material. So, the selfish gene algorithm does not consider any explicit population, and does not enumerate the individuals belonging to it. Therefore it uses an abstract model which is called virtual population where it is a not real population because after we use the population, the individual that are not use are going to be keeping in other store.
When we come to recombination, there must have a crossover operation such as single point, two point, uniform and arithmetic crossovers. In this review, there are no crossover in the selfish gene algorithm and genetic programming. But for mutation, all algorithms are used it as reproduction operator.
Fitness function is important step in evolutionary algorithms. It is a heuristic function that indicates to the algorithm whether and individual fits or not the environment. Define a fitness function in measuring the performance of an individual chromosome or genotype in the problem domain. The fitness function establishes the basis for selecting chromosomes that will be mated during the reproduction.
Next generation is used to looping the process until it get the optimum value that more accurate. It will repeat the crossover and mutation process until reached at a certain objective. For the selfish gene algorithm, we don't have to use the next generation step.
As common with evolutionary algorithms, the operators are applied in a loop. An iteration of the loop is called a generation. The sequence of generations is continued until a termination criterion is met.
Most algorithms have difficulties to converge close to the minimum of such functions, because the probability of making progress decreases rapidly as the minimum is approached. For those reason above, that why some of the algorithms have to be hybrid with other techniques to improve their performance.
In the past, many researchers have gone to enhance the conventional genetic algorithms. Based on Garg P., (2009)'s paper, Genetic algorithms are a population-based Meta heuristics. They have been successfully applied to many optimization problems. However, premature convergence is an inherent characteristic of such classical genetic algorithms that makes them incapable of searching numerous solutions of the problem domain. A memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the premature convergence.
Other technique that can be hybrid with one of the EAs is a particle swarm optimization (PSO). Based on the research by Premalatha K. and Natarajan A.M (2009), they proposed a hybrid method between PSO and GA for Global Maximization. They found that PSO have many limitations where the swarm may prematurely converge. For the global best PSO, particles converge to a single point, which is on the line between the global best and the personal best positions. This point is not guaranteed for a local. Another limitation is the fast rate of information flow between particles, resulting in the creation of similar particles with a loss in diversity that increases the possibility of being trapped in local optima. To overcome the limitation, hybrid algorithms with GA are proposed. Research by_____ proposed a hybrid GA and Ant Colony Optimization (ACO) where ACO as a local search.
In the image processing field, most of the algorithms have been applied in image segmentation, image enhancement, image restoration, image analysis, feature extraction, feature selection and face detection. However, based for the literature, there is no selfish gene algorithm being applied in image processing fields. It is very interesting algorithm that can be explored.