Natural algorithms. The implementation of the algorithm of the behavior of a swarm of bees
In my previous article , the algorithm described the behavior of a swarm of bees and its use for solving optimization and synthesis problems. Armed with C ++ and OpenGL, I wrote a program that implements this algorithm in two-dimensional space and displays the swarming of "bees."
The following function was chosen as the test function:
')
The objective function has a clearly defined minimum, where a good half of the bees are already flying in the third step.
A little video of the process itself for various settings:
attraction to PNP (personal best position) - 0.5. Attraction to GNP (global best position) - 0.5. Inertia weight - 0.5. Bees in a swarm - 60. For clarity, I set a delay of 500ms before each step.
The attraction to the PNP is 0.1. Attraction to GNP - 0.7. Inertia weight - 0.3. Bees in a swarm - 60.
Now the task is more difficult.
The function oscillates strongly.
The attraction to PNP is 0.3. Attraction to GNP - 0.3. Inertia weight - 0.3. Bees in a swarm - 60.
And even more difficult task.
Borders extended.
The attraction to PNP is 0.3. Attraction to GNP - 0.3. Inertia weight - 0.3. Bees in a swarm - 60.
The stopping criterion is more explicit if compared with the genetic algorithm, but there are also pitfalls here. For example, in the case of the second function, which has many local minima, which are quite close in meaning to the global one. At 7 seconds it can be seen that the GNP was not in the global minimum and goes into it only at 12 seconds.
A special point here is the construction of the objective function. We must correctly assess the quality of the object optimization according to specified criteria. You can create works of art, if you set a law that evaluates beauty.
Instead of calculating the objective function, experience is also possible. For example. We need to set the Wi-Fi point in the room so that the signal on the sofa and the kitchen is maximum. We set the boundaries of the room. After that, the algorithm tells us which points to put and check the signal. We measure the signal in the kitchen and on the sofa and on the basis of this data we assign the value of the objective function to each position. There you can also include the distance from the walls (you can't hang it under the chandelier), and also the distance from the switch and the socket, feng shui ... And after a couple of hours of running around with a laptop and a point we will know where to mount it, and where not necessary.
An example, of course, wild, but applies to real life. I emphasize that the optimization method does not affect the choice of the objective function.
PS Method performance will be reviewed next time, and next time.
MCI will be compared with the gradient descent method. And if there are people willing to help, then please, put your candidates on the table and we will check which algorithm is better and in which case.
PPS Program code without comments can be found here .
The following function was chosen as the test function:
')
The objective function has a clearly defined minimum, where a good half of the bees are already flying in the third step.
A little video of the process itself for various settings:
attraction to PNP (personal best position) - 0.5. Attraction to GNP (global best position) - 0.5. Inertia weight - 0.5. Bees in a swarm - 60. For clarity, I set a delay of 500ms before each step.
The attraction to the PNP is 0.1. Attraction to GNP - 0.7. Inertia weight - 0.3. Bees in a swarm - 60.
Now the task is more difficult.
The function oscillates strongly.
The attraction to PNP is 0.3. Attraction to GNP - 0.3. Inertia weight - 0.3. Bees in a swarm - 60.
And even more difficult task.
Borders extended.
The attraction to PNP is 0.3. Attraction to GNP - 0.3. Inertia weight - 0.3. Bees in a swarm - 60.
Stop criterion
The stopping criterion is more explicit if compared with the genetic algorithm, but there are also pitfalls here. For example, in the case of the second function, which has many local minima, which are quite close in meaning to the global one. At 7 seconds it can be seen that the GNP was not in the global minimum and goes into it only at 12 seconds.
And in conclusion about the optimization problem
A special point here is the construction of the objective function. We must correctly assess the quality of the object optimization according to specified criteria. You can create works of art, if you set a law that evaluates beauty.
Instead of calculating the objective function, experience is also possible. For example. We need to set the Wi-Fi point in the room so that the signal on the sofa and the kitchen is maximum. We set the boundaries of the room. After that, the algorithm tells us which points to put and check the signal. We measure the signal in the kitchen and on the sofa and on the basis of this data we assign the value of the objective function to each position. There you can also include the distance from the walls (you can't hang it under the chandelier), and also the distance from the switch and the socket, feng shui ... And after a couple of hours of running around with a laptop and a point we will know where to mount it, and where not necessary.
An example, of course, wild, but applies to real life. I emphasize that the optimization method does not affect the choice of the objective function.
PS Method performance will be reviewed next time, and next time.
MCI will be compared with the gradient descent method. And if there are people willing to help, then please, put your candidates on the table and we will check which algorithm is better and in which case.
PPS Program code without comments can be found here .
Source: https://habr.com/ru/post/104208/
All Articles