Random Search Optimization
Many problems for which computers were initially created are of optimization nature. And one of the important ways to solve optimization tasks is a Random Search. It has two main advantages over other methods:
Popular Genetic Algorithm is just one of the Random Search family.
Here is our task of optimization - look at the demo above: we want to transport some box (depicted as a violet
100 metres by straight line.
We have a kind of transportation machine or prime mover, depicted by green dot. It has infinitely small size and so can share coordinates with the box.
The box and the mover are tied with an elastic spring (yellow line) so when mover goes away from the box, spring tension starts move the box.
When the mover reaches
100m mark, it stops, but the box may overshot the position and then it would be pulled back
by spring. It could really oscillate for some time until friction would stop it.
The mover is unmanned so we can control it in a slightly restricted way: we can tell it change the speed after
20m - so the whole path is divided into
5 regions and inside each of them mover goes with a
constant speed. At region boundaries the speed is switched instantly. However speed could not change by more than
3 m/s - for the fear of burning electric drives of the mover.
To model the process of transportation use the following pseudocode:
x = 0 // initial coordinate of the box v = 0 // initial speed of the box xd = 0 // initial coordinate of the mover (or driver) t = 0 // initial time dt = 0.2 // time step of simulation m = 5 // mass of the box k = 0.5 // coefficient of elasticity of the spring (as in Hooke's Law) b = -0.5 // coefficient of friction for the box (viscous friction, proportional to speed) while not_stopped: force_spring = k * (xd - x) force_friction = b * v force_total = force_spring + force_friction acceleration = force_total / m x = x + v * dt v = v + acceleration * dt t = t + dt xd = xd + speed_of_prime_mover(xd) * dt end while;
The process of transportation is stopped when three conditions are met:
0.1by absolute value.
The speed of prime mover is determined by
5 values (i.e. for part of way between
20 metres, then between
40 and so on to the last between
100 - after which the mover is stopped).
We choose some initial list of speeds, like
1 2 3 2 1 and calculate transportation time by simulation.
Then we perform about
100 steps of the Random Search to improve this time.
At each step we randomly choose one of
5 values and increase or decrease it by random value. Then we run simulation
again and if the result is better, we remember it as the "current best".
We also need to check whether the new list of speeds satisfy the restrictions:
So at each step we check two things: whether new list of speed is valid (according to restrictions) and whether it improves the overall time. If so, we remember the newly achieved time as a record.
Input data contains the number
N of random search attempts at the first line.
The second line contains initial list of speeds -
5 integer values, like
1 1 2 2 1.
N lines will contain description of a single optimization attempt each in form of two values - the index of
the speed list element which we try to improve and the amount by which it is changed.
Answer should contain resulting list of speeds and then the best overall time achieved (with these speeds). Values should provide
1e-7 precision or better.
input data: 16 3 3 3 3 1 3 +1.7 // not valid 4 -1.3 // not valid 3 +0.5 // ok 1 +1.1 // ok 4 -1.3 // not valid 3 +0.1 // ok 4 -0.9 // not valid 1 +1.5 // ok 2 +0.5 // ok 4 -1.5 // not valid 1 -0.8 // no improve 1 +0.7 // not valid 1 -0.3 // no improve 1 +0.9 // not valid 2 -0.7 // no improve 1 -1.9 // no improve answer: 3 5.6 3.5 3.6 1 102.2
Here we try with the first attempt to increase the
3rd speed in a list (
0-based indexing) by
1.7 - this gives
it a value of
4.7 but since the next speed is
1 their difference violates restrictions.
Next attempt is to decrease the
4th speed by
1.3 which makes it negative (
-0.3) it is also invalid.
To help understanding these rules the comments are added to each of the attempts on the right.