A Survey on Applications and Optimizations of Genetic Algorithm

A Survey on Applications and Optimizations of Genetic Algorithm

Abhishek Shetye Student SKNCOE

Pune, India

Rushabh Tike Student SKNCOE

Pune, India

Varun K. V. Student SKNCOE

Pune, India

Manish Wadkar Student SKNCOE

Pune, India

Abstract Optimization problem is a problem that is often encountered in everyday life. It is inseparable from human nature that wants to get maximum profit and minimum losses. Genetic Algorithm is a meta heuristic search technique based on the mechanism of natural selection, genetics and evolution. Genetic Algorithms (GA) is an optimization technique for searching very large spaces that models the role of genetic material in living organisms. A small population of individual exemplars can effectively search a large space because they contain schemata, useful substructures that can be potentially combined to make fitter individuals. Formal study of competing schemata shows that the best policy for replicating them is to increase them exponentially according to their relative fitness. This turns out to be policy used by genetic algorithms. Fitness is determined by examining a large number of individual fitness cases. This process can be very efficient if the fitness cases also evolve by their own GAs. Network Models such as multi-layered perceptions, make local changes and so find local minima. To find a global minima genetic algorithms are used. Genetic Algorithm is merely a stochastic, discrete event and a non-linear process. The obtained optima is an end product containing the best product containing the best elements of previous generations where the attributes of a stronger individual tend to be carried forward into the following generation. The rule states, Survival of fittest will win.

Keywords Genetic algorithm, travelling salesman problem, artificial intelligence, ant algorithm, local search algorithm, stochastic hill climbing, crossover, mutation

1. INTRODUCTION

   CONSIDER THE PROBLEM OF PLAYING CHESS. TO

   build a program that could play chess, we have to specify the starting position of the chess board, the rules that dsefine legal moves. And the board position that represent a win. The goal of the winning the game, if possible, must be made explicit. But the issue with such problems is that solving it cannot be always sequentialized and needs some degree of heuristics to solve it in an optimal fashion. Such problems are categorized under np-Complete and solution of these problems come under the scope of GA [6]. Some of the problems that fall within the scope of AI and the kinds of techniques will be useful to solve these problems: Chess Hill climbing, Water Jug Best First Search, Branch and Bound, 8

   Puzzle A* Search. Depth First Search, Traveling Salesman Heuristic Search, Missionaries and Cannibals Best First Search with backtracking, Tower of Hanoi Best First Search, Monkey and Bananas Breadth First Search, Best First Search, Cryptarithmetic Depth First Search, Bridge Depth First Search

   This project can be used by logistics institutions and transportation companies for calculating optimal solutions and routes [5]. The Purpose of choosing this topic is to provide optimal solution for problem needing any degree of heuristics for solution. Most of the time we realize that hard coding a single algorithm to problems with multiple solutions is not very pragmatic. That is why we try to provide an escape route via our application so that users can calculate optimal solutions with increasing accuracy. And another reason for using Artificial intelligence is to get increased accuracy every time the system is being used as it keeps learning and improving is ability to discern between inputs.

2. LITERATURE REVIEW

   In this section, some of the recent studies and techniques of the usage of genetic algorithm will be covered.

   The paper written by K. F. Man, K. S. Tang and S. Kwong introduces Genetic Algorithms as a complete new concept. It also explains when and why Genetic Algorithm should be used.

   GA is based on the mechanism of natural selection, which is a biological process in which the strongest individuals are most likely to survive. Simply said, solution to a problem solved by genetic algorithms is evolved.

   The algorithm starts with a set of solutions (represented by chromosomes) called as population. Solutions from one population and are used to form a new population which will be better than the previous population. Solutions which are selected to form new solutions (offspring) are selected according to their fitness value.

   Outline of simple GA

   Genetic Algorithm ()

   {

   //initialize with population P init P

   //evaluate fitness of all individuals evaluate f(x)

   //generation of new population

   //select best parents P=selectparents P(x);

   //crossover to form new children crossover P(x);

   //mutation of new offspring mutate P(x);

   //replace old population by new population P=new.P;

   //loop

   If(condition not satisfied)

   goto evaluate f(x);

   end ()

   }

   Selection

   Chromosomes are selected from the population to be parents to crossover. We have to select the best chromosomes to crossover. Hence selection is used. In this paper the authors have used roulette wheel selection

   Parents are selected according to their fitness. The better the chromosomes are, the more chances to be selected they have. Imagine a roulette wheel where all chromosomes are placed in the population, every chromosome has its place according to its fitness function.

   Encoding

   The chromosome should in some way contain information about solution which it represents. The most commonly used method is binary string. Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution.

   Crossover

   Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point is copied from a first parent and then everything after a crossover point is copied from the second parent. Crossover rate generally should be high, about 80%-95%

   Mutation

   Mutation takes place after crossover. This is prevent the falling of all solutions in a population into a local optimum solution. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation rate should be very low. Best rates reported are about 0.5%-1%. [1]

   Richki Hardi has presented a system which is an application of genetic algorithm in TSP for distribution of mineral water.

   This paper describes the use of simple genetic algorithm in solving TSP.

   The genetic algorithm used in this application has four functions.

   Encoding

   In the encoding process, the gene can be represented by a string of bits, a tree, a list of rules, etc. The author has used Permutation Encoding in this system. So if one chromosome form is: P = (X1, X2, X3, , Xn).

   Specification: Salesman moves from town X1 to X2 and so on up to Xn.

   Selection

   Selection is a process for determining which individuals will be selected and how the descendants will be formed from the recombination of the selected individuals.

   There are several selection processes [7] available including: Roulette wheel selection, rank based selection, local selection, tournament selection, etc. Higher fitness values represents better solution to the problem.

   The fitness function used by the author is: P[i] =fitness[i]/nuber of fitness

   Where,

   P[i] =probability of fitness [i]

   I= index of chromosomes (1, 2, 3,, n)

   Crosses

   Crosses is crossover or recombination. Order crossover is the technique used in this system.

   Mutation

   Mutation is the process of adding a very small random value which has a low probability of variable offspring. Opportunities mutation is used in this system. Opportunities mutation is a percentage of the total number of genes in the mutated population.

   The opportunity to control the new gene mutations is evaluated in this method. If the there is a chance of a small mutation, then those genes may be useful, but if there is a chance of a big mutation then the child will lose the semblance of its parent and the algorithm will also lose its ability to learn from its history.

   Result Analysis and Conclusion

   In this system the crossover function is implemented with order crossover scheme. A part of chromosome is exchanged while maintaining the order of the city that is not part of the chromosome. A random number R is generated which represents the number of population. Chromosome k is selected as the parent if R[k] <pc where pc is the probability of crossover parameters.

   Mutations are done by using a mutation scheme. In this system swapping mutation is used as the mutation scheme. The number of chromosomes that have mutations in a population is determined by the parameters of mutation rate (pm). Mutation process is done by swapping genes with genes randomly selected afterwards.

   The entire system is searched by the results of the GA to obtain the distribution of the shortest route in the 20 districts.

   GA gives the result in only one generation due to the near optimal solution set. This system can also analyse the data so that inputs can be faster and decision making can be more effective and efficient. [2]

   When we use simple GA for solving tsp the generated optimal solution is over stochastic and does not consider the neighbourhood information in whole process. Hence the authors, Lai Nian and Zheng Jinhua propose to use a hybrid GA which will reduce the randomness. This paper focuses on solving tsp by using a hybrid genetic algorithm. Hybrid genetic algorithm has two parts: Ant algorithm [9] and local optimization search.

   Ant algorithm

   The ant algorithm is based on behaviour of ants searching for food. It is used for finding optimal paths.

   Initially, the ants walk randomly. When an ant finds a food source, it returns to the colony leaving behind a trail of pheromones that shows the path to the food source. If other ants come across the pheromones they are likely to follow the path. When they do, they too leave a trail of pheromones. As more ants follow the path, the stronger it gets. Because the ants drop pheromones every time they bring food, shorter paths are more likely to be stronger hence optimizing the solution.

   Local optimization search

   Local search is a heuristic method for solving computationally hard optimization problems.

   In this method the authors use local search algorithm to minimize the total distance by using an exchange operation.

   Hybrid Genetic Algorithm

   The proposed algorithm is based on simple genetic algorithm, local search algorithm and ant algorithm.

   Local search algorithm is used to speed up the convergence of the algorithm. The ant algorithm is used to guide the algorithm to the optimal solution. Randomness of the algorithm is reduced by using the heuristic data from the previous generations which also improve the efficiency of the algorithm.

   Result analysis

   In order to verify the effectiveness of the algorithm various tsp data sets such as Berlin52, Eil76, lin105, KroA150, KroA200 were used. Simple genetic algorithm was also compared with hybrid genetic algorithm to verify the efficiency of hybrid genetic algorithm.

   The experiments showed that the solution given by hybrid genetic algorithm was closer to the optimal solution than the solution given by simple genetic algorithm.

   Disadvantages

   • According to the constraint in TSP, ants can only access the nodes which have not been to before traveling to complete

   • When compared with other good algorithms, the number of test city is insufficient and some test cases dont find the optimal solution.

   • This algorithm is time-consuming due to the addition of local search operations. [3]

     The paper written by authors, K. Katayama, H, Sakamoto, H. Narihisa proposes an efficient genetic algorithm for solving TSP.

     They have proposed a hybrid mutation genetic algorithm which uses a complete subtour exchange crossover. This GA also applies a stochastic hill climbing procedure in its mutation process.

     An ordinary hybrid GA consists of a GA and a local search algorithm. The GA and the local search algorithm are completely separate during the hybrid search process. The HMGA proposed by the authors has a new crossover operation in addition to the local search.

     The authors also apply a complete subtour exchange crossover as the crossover operator and stochastic hill climbing as the mutation operator.

     Outline of the algorithm is as follows:

     1. Coding for the solution.

     2. Generating an initial population.

     3. Evaluating fitness value.

     4. Selection.

     5. Crossover with complete subtour exchange.

     6. Mutation with stochastic hill climbing (SHC).

     7. Termination condition.

   • In step 1, the city name is coded as a gene and the symbol string is coded as a chromosome. Chromosome length is the number of cities.

   • In step 2, a finite set of individuals are generated which are called as population.

   • In step 3, the fitness value which is the sum of the Euclidean distance between each of the cities is evaluated.

   • In step 4, the initial population is chosen.

   • In step 5, crossover is carried out with complete subtour exchange which help to avoid the construction of unsuitable offspring.

   • In step 6, we apply the stochastic hill climbing approach. It allows an occasional bad move with some probability P which enables the algorithm avoid entrapment in the local optima.

   • In step 7, a termination condition is checked and if it is not satisfied jump to step 3.

     Results

     Experiments were done on the kroAI00 (100 city problem) problem.

     Various algorithms such as HMGA with SHC, OM: ordinary mutation, WOM: without mutation were used to compare efficiency. The parameter values were common for the three different algorithms. From the results it was clear that HMGA, which applied SHC was no match for both the OM and WOM, It also showed very fast convergence for a few generations. Experimental results also showed that the GA leads good convergence as high as 99 percent even for 500 cities TSP.

     Advantages and Disadvantages

   • In the proposed GA, selection is implemented with the elite preservation [1, 6] strategy, which ensures that the best member of the population survives into the next generation.

   • Good subtours also help to avoid the construction of unsuitable offspring.

   • In this study, only SHC was used as the mutation process. However, if simulated annealing approach is used a more efficient genetic algorithm could be achieved [4].

3. STSTEM DESIGN

   The system is based on Genetic algorithm. Genetic algorithms are inspired by Darwins theory about evolution. Solution to a problem solved by genetic algorithms is evolved. Algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope, that the new population will be better than the old one. Solutions which are selected to form new solutions (offspring) are selected according to their fitness – the more suitale they are the more chances they have to reproduce. This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied.

   Operations of GA Encoding of a Chromosome The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. Crossover After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point copy from a first parent and then everything after a crossover point copy from the second parent. Mutation After a crossover is performed, mutation takes place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1.

4. CONCLUSIONS AND FUTURE WORK

This paper bases on a simple genetic algorithm. SGA heavily relies on random value functions and this is why the output is mostly localized and inconsistent. This algorithm is time-

consuming due to added local search operations. For these reasons, it is necessary to design some faster optimal operations for time-consuming problem. Maybe we can use density information between cities for TSP problem, and these will be our next research. We can also use hybrid mutated genetic algorithm to improve the results obtained by simple genetic algorithm applied in graph coloring [8].

Future Work

• To nd optimized path for Travelling Salesman Problem

  i.e. global minima over provided generations.

• Self-learning game where agent learns how to survive by avoiding obstacles and danger.

• Self-taught motion for unmanned vehicles in unknown terrain.

• Creation of knowledge base for regression based analytics in financial sector.

REFERENCES

1. Genetic Algorithms: Concepts and Applications, K. F. Man, Member, IEEE, K. S. Tang, and S. Kwong, Member, IEEE.

2. Genetic Algorithm in Solving the TSP on These Mineral Water by Richki Hardi Huimin Pan, Jingchu Liu, Sheng Zhou, and Zhisheng Niu, A Block Regression Model for Short-Term Mobile Trafc Forecasting, 2015 IEEE.

3. Hybrid Genetic Algorithm for TSP by Lai Nian and Zheng Jinhua Jinyoung Ahn, Eunjeong Ko, Eun Yi Kim, Highway Traffic Flow Prediction using Support Vector Regression and Bayesian Classifier, International Conference on Big Data and Smart Computing (Big Comp), 2016.

4. The Efficiency of Hybrid Mutation Genetic Algorithm for the Travelling Salesman Problem, K. Katayama, H. Sakamoto, H. Narihisa.

5. Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem by H. C. W. Lau, T. M. Chan, W. T. Tsui, and W. K. Pang.

6. Adaptation in natural and artificial systems, J. Holland, University of Michigan press, Ann Arbor, 1975.

7. A genetic algorithm performance with different selection strategies, Noraini Mohd Razali, John Geraghty, Proceedings of the World Congress on Engineering Vol II, 2011.

8. Genetic Algorithm Applied to the Graph Colouring Problem, Musa M. Hindi and Roman V. Yampolskiy.

9. Ant Colony Optimization and its Application to Adaptive Routing in Telecommunication Networks, Gianni Di Caro, Université libre de Bruxelles.