Genetic Algortihms

Question 1

What are genetic algorithms?

Answer 1

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection.Genetic algorithms are one of the tools we can use to apply machine learning to finding best or optimal solution to problems that have billions of potential solutions. Basically, a genetic algorithm is a set of simple rules to solve certain types of otherwise difficult problems. However to solve the problems by genetic algorithms should have the following criteria.

1. The problem involves a lot of variables to some extent. the more variable there are , the better this technique applies
2. Each variable can take on potential values to generate different solution sets.
3. we can substitue a value for each of the variables and the particular combination of individual values can be a solution set.
4. The problem can be quantified in some manner therefore any two solution sets can easily compared to judge the better one out of it.

Question 2

How to solve problems with genetic algorithms?

Answer 2

When solving a problem with genetic algorithm instead of asking for a specific solution. We provide characteristics that the solution must have or rules its solution must pass to be accepted.

Question 3

What is the fundamental aspect or goal of solving a problem by Genetic algorithm?

Answer 3

A fundamental aspect of solving problems using a genetic algorithm is that they must provide the feedback that helps the engine select better of two guesses. That feedback is called fitness, for how closely the guess fits the desired result.

Ex: In a number range of 1 to 1000 guessing one number 1 in 1000 chances by asking wrong or right takes more guesses than asking feedback of higher or lower.

Ex 2: Try to find a set of values in range 1-1000. All in range 1 to 1000, we only receive back a fitness value indicating how closely that set of number matches the desired set. Here the goal would maximize or minimize that fitness.

Question 4

What is the process of genetic algorithm problem-solving?

Answer 4

Genetic algorithms and genetic programming are very good at finding solutions to very large problems. They do it by taking millions of samples from the search space, making small changes, possibly recombining parts of the best solutions, comparing the resultant fitness against that of the current best solution, and keeping the better of the two. This process repeats until one of the following occurs: The known solution found, A solution meeting all requirements is found, a certain number of generations has passed, a specific amount of time has passed.

Question 5

How Mutation and crossover process helps in the genetic algorithm?

Answer 5

Ex: In a number range of 1 to 1000 guessing one number 1 in 1000 chances by asking wrong or right takes more guesses than asking feedback of higher or lower.

As per above example, the genetic algorithm does not know what is lower. It has no intelligence. It does not learn. It will make the same mistake every time. Hence it will use the random exploration of problem space combined with the evolutionary processes like mutation and crossover to improve the guesses.

Question 6

List of fields are currently using genetic algorithms ?

Answer 6

• Plan airplane routes.
• Develop equity market bidding strategies
• point antenna on military vehicles
• optimize an iterative prisioner’s dilemma strategy
• Work toward developing artificial intelligence.

Question 8

Advantages of GA

Answer 8

1. Does not require any derivative information
2. Is faster and more efficient as compared to the traditional methods.
3. Provides a list of “good” solutions and not just a single solution.
4. Always gets an answer to the problem, which gets better over the time.
5. Useful when the search space is very large and there are a large number of parameters involved.

Question 9

Limitations of GAs

Answer 9

GAs are not suited for all problems, especially problems which are simple and for which derivative information is available.

Fitness value is calculated repeatedly which might be computationally expensive for some problems.

Being stochastic, there are no guarantees on the optimality or the quality of the solution.

If not implemented properly, the GA may not converge to the optimal solution.

Question 10

Population

Answer 10

It is a subset of all the possible (encoded) solutions to the given problem. The population for a GA is analogous to the population for human beings except that instead of human beings, we have Candidate Solutions representing human beings.

Question 11

Chromosomes

Answer 11

A chromosome is one such solution to the given problem.

Question 12

Gene

Answer 12

A gene is one element position of a chromosome.

Question 13

Allele

Answer 13

It is the value a gene takes for a particular chromosome.

Question 14

Genotype

Answer 14

Genotype is the population in the computation space. In the computation space, the solutions are represented in a way which can be easily understood and manipulated using a computing system.

Question 15

Phenotype

Answer 15

Phenotype is the population in the actual real world solution space in which solutions are represented in a way they are represented in real world situations.

Question 16

Decoding and Encoding

Answer 16

For simple problems, the phenotype and genotype spaces are the same. However, in most of the cases, the phenotype and genotype spaces are different. Decoding is a process of transforming a solution from the genotype to the phenotype space, while encoding is a process of transforming from the phenotype to genotype space. Decoding should be fast as it is carried out repeatedly in a GA during the fitness value calculation.

Question 17

Fitness Function

Answer 17

A fitness function simply defined is a function which takes the solution as input and produces the suitability of the solution as the output. In some cases, the fitness function and the objective function may be the same, while in others it might be different based on the problem.

Question 18

Genetic Operators

Answer 18

These alter the genetic composition of the offspring. These include crossover, mutation, selection, etc.

Question 19

Basic structure of GA

Answer 19

Question 20

Application areas

Question 21

Application areas

Answer 21

Optimization − Genetic Algorithms are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints. The approach to solve Optimization problems has been highlighted throughout the tutorial.

Economics − GAs are also used to characterize various economic models like the cobweb model, game theory equilibrium resolution, asset pricing, etc.

Neural Networks − GAs are also used to train neural networks, particularly recurrent neural networks.

Parallelization − GAs also have very good parallel capabilities, and prove to be very effective means in solving certain problems, and also provide a good area for research.

Image Processing − GAs are used for various digital image processing (DIP) tasks as well like dense pixel matching.

Vehicle routing problems − With multiple soft time windows, multiple depots and a heterogeneous fleet.

Scheduling applications − GAs are used to solve various scheduling problems as well, particularly the time tabling problem.

Machine Learning − as already discussed, genetics based machine learning (GBML) is a niche area in machine learning.

Robot Trajectory Generation − GAs have been used to plan the path which a robot arm takes by moving from one point to another.

Parametric Design of Aircraft − GAs have been used to design aircrafts by varying the parameters and evolving better solutions.

DNA Analysis − GAs have been used to determine the structure of DNA using spectrometric data about the sample.

Multimodal Optimization − GAs are obviously very good approaches for multimodal optimization in which we have to find multiple optimum solutions.

Traveling salesman problem and its applications − GAs have been used to solve the TSP, which is a well-known combinatorial problem using novel crossover and packing strategies.