The global optimization of mixed integer non-linear problems (MINLP), constitutes a major area of research in many engineering applications. In this work, a comparison is made between an algorithm based on Simulated Annealing (M-SIMPSA) and two Evolutionary Algorithms: Genetic Algorithms (GAs) and Evolution Strategies (ESs). Results concerning the handling of constraints, through penalty functions, with and without penalty parameter setting, are also reported. Evolutionary Algorithms seem a valid approach to the optimization of non-linear problems. Evolution Strategies emerge as the best algorithm in most of the problems studied.
Real world problems can, in general, be formulated as mixed integer non-linear programming problems (MINLP). These problems, due to their combinatorial nature, are considered difficult problems. Gradient optimization techniques have only been able to tackle special formulations, where continuity or convexity had to be imposed, or by exploiting special mathematical structures. Approaches based on stochastic algorithms have been used. These approaches, also know as adaptive random search, have successfully tackle MINLP, mostly in the area of chemical engineering (Reklaitis, Ravindran, and Ragsdell, 1983, Salcedo, 1992 and Banga and Seider, 1996). In recent years, a vast amount of work has been published on applications of evolutionary algorithms (Genetic Algorithms, Evolution Strategies, Simulated Annealing, etc.) to the solution of MINLP in many engineering applications. These algorithms are distinct from conventional algorithms since, in general, only the information regarding the objective function is required. Moreover, they start from a pool of points that evolves over time, possibly in the direction of the optimum. It should be stressed that the objective of this on going research is not to find the ‘best’ algorithm for all problem instances, but to compare different algorithms, in order to find out classes of problems which may be more suitable for certain algorithms than others.
The general formulation of the problem is as follows:
equation(1)
g(x)≤0
where
h∈Rm,g∈Rp.
In this work, 7 test problems, proposed by independent authors, are studied using Genetic Algorithms (GAs) and Evolution Strategies (ESs). These problems arise from the area of chemical engineering, and represent difficult non-convex optimization problems, with continuous and discrete variables. Comparisons are made with an M-SIMPSA algorithm (Cardoso, Salcedo and Feyo de Azevedo, 1996a, Cardoso, Salcedo and Feyo de Azevedo, 1996b, Cardoso, Salcedo, Feyo de Azevedo and Barbosa, 1997 and Cardoso, 1998) based on the combination of the non-linear simplex method of Nelder and Mead and Simulated Annealing.
It is well known that one of the main disadvantages of Evolutionary Algorithms lies in the required computational time. On the other hand, requiring only the objective function values to execute the search, based on a pool of points, allows Evolutionary Algorithms to deal with non-convex problems with reduced chances of being trapped on a local optimum. This work compared Genetic Algorithms, Evolution Strategies with previous published results of M-SIMPSA (Cardoso et al. 1997), a Simulated Annealing based algorithm.
The results clearly show the difficulty in dealing with equality constraints (Problem 2 and Problem 4); however, when reformulated without these constraints, the algorithms exhibited a high rate of convergence.
The method proposed by Deb (1998) to deal with the constraints is clearly superior to the usual penalty scheme, since it does not require the setting of a penalty parameter. The proposal of Cardoso et al. (1997) for the M-SIMPSA algorithm can generate infeasible points with fitness values superior to feasible points. Evolutionary strategies exclude all non-feasible points, which corresponds to an infinite penalty. All algorithms presented have great difficulties with Problem 7 which is not surprising since the problem is highly constrained; the global optimum corresponds to a point where a very small variation in any of the continuous variables produces infeasibility. Thus, it seems of utmost importance the development of appropriate methods to deal with constraints in the context of Evolutionary Algorithms.
Evolutionary Strategies exhibit difficulties in highly constrained problems but, in general, they are the most efficient in terms of function evaluations. In summary, the solution of MINLP problems with Evolutionary Algorithms is a valid approach in non-convex problems where computational time is not of primary importance. Future work will address the comparison of evolutionary algorithms with adaptive random search algorithms, as well as the treatment of equality constraints.
