Meta-heuristic Optimization Algorithms

In many fields of science and engineering, we face with a problem which needs to optimize a mathematical function. It means we need our function to be maximum or minimum of its values. If our problem is maximization, desired function is called “utility function” or “profit function” and if the problem is minimization, the function is called “cost function” or “loss function”, but in general we could call the function as “objective function”.

In Calculus, for finding extremums of function (minimums or maximums), we set the derivative of the function equal to zero and then solve the equation to find the answer points. These points are called “stationary points” and the value of function is “extremum” at these points.

But consider a function like below which its derivative is so complicated to solve to find the stationary points.

  f(x,y) = x^{\frac{2}{3}} + 4 \times sin^2(xy^3+7 \times y^2) + sinh(x^{0.2}+8 \times y^4) - e^{sinc(x^2-log(x))} + ….

Obliviously finding the answers for this equation:  $f'(x,y) = 0$ , is kind of impossible. So, how could we find extremums for such functions??!!

One dummy solution which comes to mind is to evaluate the value of function for a wide range of X and Y and then choose the maximum values or minimum values. For example if we just want to find the extremum of above mentioned function, only in range of  {x\in (-100,+100)} and  {y\in (-100,+100)} , we need to span the X and Y to mentioned range with step size of 0.01 for example. In this situation we have for example 2000 values for X and 2000 values for Y and in total, we have 4,000,000 pair of (x,y) which function should be evaluated at.

Consider each evaluation of f(x,y) for each pair of (x,y), takes many mathematical calculation for above mentioned function and we should do this 4,000,000 times and then we need a sort algorithm to find the minimum and maximum. Back to our assumption, this evaluation is only for the range of (-100,+100) and extremum could happen outside of this range. So, this seems not to be a good solution to our problem.

For solving these kind of problems, heuristic optimization algorithms evolved which most famous one of them is almost “Genetic Algorithm”. There are many other meta-heuristic optimization algorithms which inspired from our nature or our environment, like: “Particle Swarm Optimization”, “Ant Colony Optimization”, “Tabu Search”, “Imperialist Competitive Algorithm”, ” Invasive Weed Optimization” and etc.

For example, in Genetic Algorithm, inspiring from humans and animals’ way of birth and their DNA, at first, we choose a good amount of points in a wide range of variables, randomly, that are our parents to make a new generation. But not all parents are good enough to make new generation. Considering this, to have a good generation of points, we choose those parents which are more fit, that means their fitness function is minimum or maximum (according to our optimization objective). Then we match these parents and make generation around them by some algorithms. Then we calculate again fitness value for current generation and choose the best ones as parents for next generation and so on, till we converge to an acceptable solution.

Roughly saying, almost all of meta-heuristic optimization algorithms work like above, but any of them has its own way of selecting the desired points for function evaluation and any of them, as their name suggest, inspired from an biological or natural or cultural or etc, phenomenon.

Leave a Reply

Your email address will not be published. Required fields are marked *


Enjoy this blog? Please spread the word :)

Follow by Email