Optimization Algorithms


Many practical optimization problems have no analytical solutions. The more constraints and parameters there are, the more the the complexity of such problems increases. In addition in many cases non linear functions are needed. In similar situations, without specific analytical solutions, iterative optimization algorithms are useful: they calculate the approximation xk+1 from the actual approximation xk of the solution. A particular kind of iterative algorithms is represented by the heuristic ones: they are algorithms that find solutions among all possible ones but they don’t guarantee that the best solution will be found. Heuristic algorithms usually find a solution close to the optimal one with reasonable computational times but there is no proof that this will always be the same.Also heuristic algorithms are typically used in problems without a known method to find an optimal solution under the given constraints.

The EML2 group has detailed knowledge of heuristic and metaheuristic algorithms. They are used as optimization methods for complex EM problems. This is the case of genetic algorithms and tabu search technique, that we use in wireless network optimum planning problems. In such problems, optimal solutions are represented by the configurations of positioning and electrical parameters for the antennas of the wireless system the guarantee high quality of service and low EM emission. Optimization algorithms are also used in research activities and projects such as: “SeGriPlaNet” and “Genetic Agents”.

GENETIC ALGORITHMS

 They have been developed by John Holland during the ‘70s and they are based on the analogy with genetic processes and natural selection mechanisms.  In these heuristic algorithms, a population of abstract representations (the chromosomes), usually represented in binary strings, evolves towards better or optimal solutions.

The chromosomes codify the parameters of the problem that have to be optimized (genetic representation of the problem).

The “goodness” of each chromosome is evaluated thanks to a fitness function: it is a particular objective function that quantifies the optimality of a solution of the optimization problem.

The evolution of such a population, as shown in figure, starts from individuals randomly generated and evolves in generations. In each generation the fitness of every chromosome is evaluated and genetic operators are applied: mutation alters one or more characters in a string; crossover combines sections coming from different chromosomes (the so-called parents) in order to form new individuals (the children).

A generic genetic algorithm is performed through these steps:

1) initialization of the population

2) selection of chromosomes for genetic operators

4) reproduction: creation of a new generation of chromosomes from those individuals that have been previously selected

5) termination: the previous steps are repeated until a specific termination condition has been reached

A typical genetic optimization in a wireless network planning problem tries to optimize the positioning and the electrical parameters of the antennas

1) the examined geographic area is discretized in a grid of test points

2) fitness function determination

3) E field evaluation for each test point given by each antenna

4) fitness function evaluation for each test point

GeneticAlg

 TABU SEARCH

 Tabu Search is generally attributed to Fred Glover, it is a metaheuristic belonging to the class of local search techniques. The performances of these techniques are enhanced in Tabu Search by using memory structures.

Tabu Search uses a neighbourhood search procedure to iteratively move from a solution x to a solution x’, in the neighbourhood of x, until some stopping criterion has been satisfied.

To explore regions of the search space that would be left unexplored by the local search procedure and to escape local optimality, tabu search modifies neighbourhood structure of each solution as the search progesses (i.e. from N(x) a N*(x) is derived).  The solutions admitted to the new neighbourhood N*(x) are determined through the use of special memory structures such as tabu list (the one that gives its name to tabu search technique). In its simplest form, a tabu list contains the solutions that have been visited in the recent past. Solutions belonging to the tabu list are excluded from N*(x).