Transcript Finding Global Minimum/Maximum: Genetic Algorithm vs. Simulated

The Genetic Algorithm vs. Simulated Annealing
Hirophysics.com
Charles Barnes
PHY 327
Finding the min/max of a function
The genetic algorithm and simulated annealing processes are used for
determining the global minimum and maximum of a selected range for any
given function.
Global minimum
The function E(x) is equivalent to the internal energy of the system.
Hirophysics.com
Genetic Algorithm
The genetic algorithm is a computer-performed optimization method that
mimics the process of natural evolution.
•An initial population is generated [A(0):=(A 1(0), A2(0), … An(0)]
•Each individual in a population is assigned a fitness function.
There are three types of operators for genetic algorithm:
1.Reproduction (Selection)
2.Crossover
3.Mutation
Hirophysics.com
Reproduction
Hirophysics.com
Crossover
• The crossover operator randomly recombines pairs through mating.
Parents
P1
P2
1001 | 0111 | 0111
1110 | 0100 | 1111
Parents
P1,2
1110 | 0111 | 1111
P3
1010 | 1101 | 0001
Child
1110 | 0111 | 1111
Child
1010 | 0111 | 0001
etc.
This is a genetic operator and evolutionary algorithm known as crossover.
Hirophysics.com
Mutation
• The mutation operator is a sudden change of chromosome.
001100101001011101
001100101101011101
001100101101001101
A number is randomly switched in the code.
Hirophysics.com
Genetic Algorithm - Parameters
There are three main parameters that can be changed in the function of the
genetic algorithm:
•M: the population of a specific farm
•N: the length of an individual’s binary string
•k: the temperature interval
In addition to these, the function can also itself be changed.
The research done on the genetic algorithm was to find which parameters, if
any, influenced the production of accurate results.
Hirophysics.com
Functions Used in Genetic Algorithm




Hirophysics.com
Results – Genetic Algorithm
• The genetic algorithm proved quite accurate on each experiment,
producing exceptional results entirely independent of the function.
• When the variables M, N, and k were changed, little to no effect on the
global min/max was observed.
• The genetic algorithm had no problem finding the minimum and
maximum on any type of function.
Hirophysics.com
Simulated Annealing
Hirophysics.com
The Simulated Annealing Process
Hirophysics.com
Results – Finding the Global Max
Finding the global maximum of a function typically produced a graph as
follows:
The graph displays how the solutions converge.
Hirophysics.com
Results – Finding the Global Min
Finding the global minimum of a function typically produced a graph as
follows:
The graph displays how the solutions converge.
Hirophysics.com
Results – Changing Parameters
The algorithm used for finding the maximum function was generally more
accurate than the minimum algorithm, producing similar graphs with similar
maximums each time.
e.g.
100 Calculations
10,000 Calculations
It is interesting to note that the more calculations done by the algorithm, the faster the
convergence is to the solution.
Hirophysics.com
Results – Accuracy
Graph 1 –(x-2)2+3
Results of the Algorithms:
Max1=3 at x=2

Hirophysics.com
Graph 2 (x-2)2+3
Max1 = Min2
Min2=5.04 at x=0.57

Findings – Simulated Annealing
• Accurate results for both the maximum and minimum simulated
annealing algorithms were dependent on functions, as more complicated
functions (typically those with powers or exponentials) had trouble
producing accurate results
• In general, the more iterations the algorithm would undergo, the more
accurate the final data would be for simpler functions.
• Finding the maximum via simulated annealing is much more accurate
than finding the minimum, though not usually typically accurate.
Hirophysics.com
Conclusion
• As observed, the genetic algorithm seems to be the most accurate
method of the two to find both the maximum and minimum of any
function.
• The simulated annealing process seems to have trouble finding the
maximum and minimum of more complicated functions.
Hirophysics.com
Future Research
To understand why the simulated annealing algorithm was not accurate,
especially at finding the global minimum of a function
Hirophysics.com