Aprendizagem e busca local em algoritmos meméticos para projetoassistido por computador

Abstract

The computer aided design (CAD) process is an automated system characterized by the association of a mathematical and computational model of the device being designed and an adequate automatic search technique, an optimization method, for finding the optimal values for the design variables. However, this automated CAD process often requires many calls to the analysis software until the optimized prototype satisfies the specifications and requirements defined by the designer. Since the analysis software usually employs a computationally intensive numerical method, it is desirable that the optimization method finds an acceptable solution while minimizing the number of calls to this software. Evolutionary algorithms, a special class of global-search methods, have been recognized as powerful tools for the solution of CAD problems for quite some time, but in recent years, memetic algorithms or hybrid algorithms have received growing attention due to their potential to improve typical evolutionary algorithms in many different contexts. Memetic algorithms in general benefit from the association of local search operators with the usual reproductive operators of evolutionary algorithms. However, in the context of optimization with continuous variables within CAD problems, the computational cost of local search operators is not affordable. This cost can be greatly reduced with the employment of approximation techniques within these operators, making the use of memetic algorithms for CAD problems more practical. The main objectives of this thesis are to investigate, implement and test the use of local approximations within a memetic optimization framework for the solution of CAD problems, particularly the design of electromagnetic devices. This thesis aims to further advance the development and investigation of memetic algorithms, with particular attention to problems whose function evaluations involve complex and intensive calculations.In this context, the additional complexity in the algorithm would be justifiable. This thesis organizes, develops and implements a framework for evolutionary optimization applied to CAD problems. This framework accomodates various evolutionary algorithms for both mono and multi-objective optimization, including memetic algorithms. These algorithms are unified in the framework thanks to the identification ofa common structure for modeling them. Any evolutionary algorithm in this framework can employ the approximation-based local search proposed in this thesis. This operator utilizes the multiquadric interpolation technique for building a local approximation for each one of the nonlinear objective and constraint functions, and the sequential quadratic programming method to solve a local version of the global problem. For the multi-objective operator an additional step is taken to transform the multi-objective problem into a mono-objective problem with additional constraints via the goal attainment formulation. This thesis also presents a formal analysis of memetic algorithms. This analysis is divided in two main parts. The first part investigates the effect of the local search operator on the global convergence properties of standard evolutionary algorithms via Markov chain theory. The second part studies the computational cost of memetic algorithms. In this second part, the computational complexity of the local search operators is derived and expressions for the overhead of the local search are developed. This analysis leads to the following important results about the proposed local search methodology: (i) The memetic algorithm preserves the global convergence properties of standard evolutionary algorithms. When the memetic algorithm employs Lamarckian local search and an irreducible mutation operator, it will be globally convergent if the number o individuals selected for local search is smaller than the population size, i.e., if < . (ii) The memetic algorithm preserves the polynomial complexity of standard evolutionary algorithms. The complexity of the local search is dominated by a term that is quadratic with NL, the maximum number of points in the local data set. (iii) The overhead of the local search can be reduced by not using the local search at every generation, which allows one to employ higher values for and nTR, the number of trust region updates. That is the balance between frequency and intensity of the local search. In total six problems are discussed. Three analytical test functions without constraints; one unconstrained magnetostatic problem, the design of the pole shape of a magnetizer device; and two versions of a constrained magnetostatic problem, the well known benchmark problem 22. The three analytical test functions are used to illustrate the increase in convergence speed due to the multiquadric-based local search. The magnetizer problem shows the negligible overhead of the approximation-based local search when dealing with computationally intensive functions. The analytical functions are fast to evaluate, hence the memetic algorithm takes more time than the genetic algorithm, but this situation clearly inverts when the time to evaluate increases. The mono-objective version of the problem 22 is used here as a representative instance of CAD problems in electromagnetic design. Twelve different evolutionary algorithms fromthe framework are hybridized with the MQ-based local search. The experiment shows that all tested evolutionary algorithms benefit from the use of the local search operator. This is an empirical evidence that, for the class of problems delimited in this thesis, evolutionary algorithms in general can be greatly improved by their association with approximation-based local search operators. The bi-objective version of problem 22 is used to illustrate the multi-objective multiquadric-based local search operator. The results also show that all three multi-objective memetic algorithms perform better than their basic genetic counterparts. The local search not only improves the convergence speed measured by the S-metric, but also improves the quality of the outcome sets, regarding the metrics NDCSR and S-metric.