Developer | Contacts |
---|---|
Chellick | diggerpotato173@gmail.com |
Visit codes section to choose the algorythm.
Use valid Dtypes for all input
statements.
Watch out!
You may also change optimised func, simply to retype something:
def function(self=None, x, y, args=None):
return x**2 + y**2
My hypothesis is that: a population adapts better over generations than under the influence of social factors.
Analysis of the efficiency of global optimization algorithms on test functions and development of their modifications in order to increase efficiency. During the development of the project roadmap, the following tasks were set:
- Implementation of a standard genetic algorithm in Python.
- Adapting the genetic algorithm to solve the problem of calculating the global extrema of a function.
- Obtaining a solution and values.
- Implementation of the swarm method in Python.
- The study of various modifications of both algorithms in order to improve the efficiency of solving this problem.
- Comparison of the operation of two global optimization algorithms.
Genetic Algorithm, known as GA or GA, is a search technique used to solve global optimization problems. It is based on mechanisms similar to natural selection in nature and is a kind of evolutionary computation. This method uses evolutionary selection methods such as inheritance, mutation, selection, and crossing over to achieve better optimization. To solve the problem of finding local extrema of a function, an algorithm based on the classical genetic algorithm of John Holland is used. The work of the algorithm can be divided into several stages:
- first generation generation
- selection of parents
- crossing
- mutations
- creating a new generation
Items 2-5 are performed until the specified number of generations has passed. In the FGEF problem (finding the global extremum of a function), a binary string with a given length is taken as an individual. The characteristic of comparison, in turn, is the number of units in a given individual. The population is an array with N-specified number of elements.
The birth of individuals of the next generation occurs as follows: several random individuals in the population are taken, strings are compared, the best (those with more units in the binary string are considered) representatives are selected as parents for crossing. Then the method of dividing both parents into parts is used (one part from the first parent, the second - the remainder from the second parent).
Thus, a new generation is assembled, the same size as the previous one, and replaces it. In most cases, the highest quality individuals pass on their genes from generation to generation, due to which the quality of individuals from generation to generation improves each time.
The number of individuals in one generation, the number of generations, the chance of mutation, and the limitations of the function are the adjustable parameters of the genetic algorithm. In the fitness function in GA, the x and y coordinates are given by the following formula:
In the process of finalizing the genetic algorithm, it was decided to think over some possible modifications that can improve its quality. To begin with, it was decided to conduct an experiment with one of the main parameters of GA - the probability of mutation. The initial idea, which consisted in the usual decrease in probability with iterations, proved to be incapable, after which it was decided to add some dependence to the formula for recalculating the probability of mutation, which can be described by the following formula:
-
$\frac{\sum x}{n}$ is the arithmetic mean -
$P_{const}$ – set probability value
The following line of reasoning was taken as a basis: “Evolutionary methods of adaptation work worse as long as the population does not go beyond fitness.” The value of 0.05 is a constant that was derived as a result of the experiments.
The t-test or Wil-Coxon test is a statistical test used to test for differences between two sets of paired or independent measurements in terms of the level of some quantitative trait. Its algorithm is:
-
Formation of arrays from two samples;
-
Sorting arrays in ascending order;
-
Designation of ranks of elements;
-
Calculating the value of statistics;
-
Significance level assertions;
-
Calculation of critical boundaries of statistics.
In my opinion, it is much more appropriate to start a detailed description of the criterion from the fourth point.
Having carried out all the necessary procedures with the data set, the statistics value was obtained equal to 36, after which it was necessary to choose the significance level Q, within the interval of boundaries of which the statistics value is included. In my case, this turned out to be the value
Next, it is necessary to calculate the critical boundaries
Where
-
$\psi\left(1-0.5Q\right)$ – value of the inverse normal distribution function with parameters (0, 1); -
$n, m$ are the lengths of the vectors of the two samples.
In my case, respectively equal:
And if the value of the function is not within the given vector, we can conclude: at a significance level
Modification | Classic algorythm |
---|---|
-0.0022425534980673057 | -0.0006717369065685338. |
-9.52306394407384e-05 | -0.0006830993887316342 |
-8.126037448610686e-05 | -0.00024145274596588202 |
-4.083974121737291e-05 | -0.002483959676483339 |
-0.00012317116935000151 | -0.0003371956284549569 |
Particle swarm method (MPS, PSO, or PSO) is a numerical optimization method that does not require knowing the exact gradient of the function being optimized. The idea of the algorithm was partially borrowed and adapted by the psychologists Kennedy and Eberhard, who were studying the behavior of animal aggregations. The model was slightly simplified and elements of the behavior of a crowd of people were added, therefore, individuals (GA) or elements were called particles. He solves the problem by having a population of possible solutions - particles, moving them in the search space in accordance with a simple mathematical formula regarding the position and speed of the particle. The operation of the algorithm can be divided into the following stages: Swarm creation. Finding the best solution for each particle. Finding the best among all particles. Correction of the speed of each particle. Particle movement. Result output. Steps 2-5 are executed until the specified number of iterations has passed or the termination condition of the algorithm is met. One of the main features of PSO (particle swarm optimization) is the vector velocity equation. What is given by the formula,
Where
-
$C_1$ – coefficient of personal velocity vector; -
$C_2$ is the coefficient of the public velocity vector; -
$r_1, r_2$ are random coefficients in the interval$[0, 1]$ ; -
$\omega$ – coefficient of inertia; -
$V_i^t$ – previous speed value; -
$p_{best\left(i\right)}^t$ is the best value of an individual; -
$P_{bestglobal}^t$ is the best swarm value; -
$P_i^t$ - value$t$ of a point in$i$ iteration.
In my implementation of the particle swarm method, there is a modification based on changing the personal, global and inertial coefficients in the vector velocity equation
These coefficients are changed according to the following formulas:
A similar modification is used in order to expand the search area with a large coefficient
Mod PSO | Classic PSO |
---|---|
197.964940448349 | 187.00941142755548 |
197.30952377944215 | 192.67747220008312 |
199.12183640000237 | 194.02478678041484 |
197.18410821114276 | 156.84365767141742 |
198.32082127639313 | 192.1959597676409 |
Comparison of optimization algorithms As a function that needs to be optimized, we will take the following formula:
Initial parameters of GA (mod.):
- Number of individuals - 100;
- Length of individuals - 32;
- Number of iterations - 100;
- Mutation probability - 0.2;
- Lim1 - -3;
- Lim2 - 13;
- max.
Initial PSO parameters (mod.):
- Number of individuals - 100;
- Number of iterations - 100;
- Lim1 - -3;
- Lim2 - 13;
- max.