Describe a situation in which one should consider the use of a genetic algorithm.

 

The Genetic Algorithm can solve problems that do not have a precisely-defined solving method, or if they do, when following the exact solving method would take far too much time. They are suitable for problems with a large solution space and many local max or min. They are useful when you do not need a precise answer, merely one that is “good enough”. You do not have to make any statements about differentiability and continuity. Continuously differentiable problems with few local optimum are usually solved most efficiently with traditional methods.

 

  Summarize the genetic algorithm approach to solving a problem

 

Genetic algorithms are non-deterministic heuristic search strategies that are based on iteratively evolving a population of individuals, each of which encodes one of the solutions to a given optimization problem, towards more promising zones of the space of solutions of the optimization problem. Each iteration of a GA consists in modifying some selected individuals of the current population by means of some random operators (crossover and mutation) in order to create new individuals and, consequently, a new population. At each iteration, the solutions are tested against a fitness function.

 

  List two disadvantages of GAs.

 

       They do not typically give precise answers.

 

       They are strongly dependent on a set of parameters (population size, number of generations, probabilities for applying the random operators, rate of generational reproduction, etc) that have to be experimentally tuned for the optimization problem at hand.

 

  Crossover

 

       Describe this operator

 

Crossover operates on selected genes from parent chromosomes and creates new offspring.

 

       Describe single point crossover.

 

One crossover point is selected, the binary string from the beginning of the chromosome to the crossover point is copied from parent A to the offspring, the rest is copied from parent B to the offspring.

 

  Describe mutation and explain why it is used

 

Mutation is intended to prevent falling of all solutions in the population into a local optimum of the solved problem. Mutation operation randomly changes the offspring resulted from crossover. In case of binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1.

 

  Define the fitness function and explain how it is used in the genetic algorithm approach.

                       

The function you are trying to maximize or minimize. To decide which offspring survive to the next generation.

 

  Systems of linear algebraic equations

 

Given the system of equations

 

A₀₀X₀ + A₀₁X₁ + A₀₂X₂ + A₀₃X₃ = B₀

A₁₀X₀ + A₁₁X₁ + A₁₂X₂ + A₁₃X₃ = B₁

A₂₀X₀ + A₂₁X₁ + A₂₂X₂ + A₂₃X₃ = B₂

A₃₀X₀ + A₃₁X₁ + A₃₂X₂ + A₃₃X₃ = B₃

 

These equations can be expressed as a matrix equation AX = B

 

       Write the matrix A

 

A₀₀       A₀₁       A₀₂       A₀₃

A₁₀       A₁₁       A₁₂       A₁₃

A₂₀       A₂₁       A₂₂       A₂₃

A₃₀       A₃₁       A₃₂       A₃₃

 

       Write the matrix X

 

X₀

X₁

X₂

X₃

 

       Write the matrix B

 

B₀

B₁

B₂

B₃

 

 

       There can fail to be a solution if the set of equations is singular. Define singular.

 

If one or more of the M equations is a linear combination of the others (row degeneracy) or if all equations ocntain certain variables only in exactly the same linear combination (column degeneracy)

 

  Matrix classifications

 

The classification of a matrix can be used to identify a solution techinque. Define the following concerning the classification of matrices.

 

       Lower triangular

 

Has elements only on the diagonal and below, rest are 0.

 

       Diagonal

 

Has elements only on the diagonal, rest are 0.

 

  LU Decomposition

 

Given the matrix equation Ax = b and given that LxU = A where L is lower triangular and U is upper triangular. Summarize the solution using LU decomposition.

 

Ax = b  can be rewritten as  LUx = b or L(Ux) = b

Solve for y such that Ly = b

Then solve for Ux = y

 

  Define the identify matrix I

 

A matrix whose elements are all 1 on the diagonal and 0 elsewhere.

 

  Given the matrix A, what is meant by the inverse A or A^-1?

 

A matrix such that AA^-1 = I where I is the identify matrix.

 

 

  What is the difference between interpolation and extrapolation.

 

Interpolation is concerned with estimating values between known data points. Extrapolation is concerned with estimating values outside the range of known dat points.

 

  How is Lagrange’s formula used in polynomial interpolation and extrapolation.

 

It gives the interpolating polynomial of degree N-1 through N points.

 

 

 

 

 

 

 

 

 

 

 

 

  What is a cublic spline?