1. Introduction
Engineers are devoted to solving real-life problems. The solutions to these problems require the minimization (or maximization) of a function (usually called an objective function or cost function). The problem might have some constraints, turning the problem solving to a challenging task. The current set of chapters deals with different applications: supersonic flutter, motion estimation, chemical and environmental processes, complex nonlinear systems, cutting and packing, topology optimization, curve interpolation, etc. Despite the different domains for each application, they have some essential features in common. They have some parameters representing the solution, the parameters are the inputs to the objective function. The objective function must be minimized through the optimization process to eventually maximize the reliability and efficiency of the resulting solution [1].
Two major categories of methods can be used to determine the set of parameters which supplies the minimal (or maximal) value for an objective. The first category relies on deterministic methods [2]. They require a seed solution (also called initial solution) and iteratively determine a solution. Once the initial solution is given, the deterministic method will end up always the same final solution. However, it might be not the global optimum. The second category relies on probabilistic methods (also called metaheuristics) [3]. They do not rely on the initial solution and each execution can reach a different solution.
In the sequence, it explains the deterministic and probabilistic methods. It will be shown that the different methods have different properties. Surely, each problem has the most appropriate method. However, this association might not be an easy task.
2. Deterministic methods
Among the deterministic methods, the Gauss-Newton method is one of the most commonly used methods and it can be formulated as
where some initial solution
where
The definition of the step size is not trivial, some approaches, like the Armijo rule, using nonmonotone line search were proposed [4]. A very well-known approach uses the Levenberg-Marquardt modification. It can be used even if
This set of chapters has several deterministic methods, in the following they are briefly presented. The chapter “Verification and validation of supersonic flutter of the rudder model for experiment” uses a deterministic approach combined with a gradient evaluation to determine the next solution. The parameters are exclusively continuous. The problem has some constraints related to the first and second frequencies of the rudder.
The chapter “An optimization procedure of the model’s base construction in multimodel representation of complex nonlinear systems” uses a deterministic method. Artificial Neural Networks must be trained before usage. During the training phase, their parameters are determined using some cost function and gradient information. After trained, the artificial neural network will provide the same output for a given input.
The chapter “Approximation algorithm for scheduling a chain of tasks for motion estimation on heterogeneous systems MPSoC” uses a deterministic approach. This research is focused on processing speed. As explained by the authors, motion estimation is a key feature in a video codec. Temporal redundancy can be estimated and used in interframe video compression. The authors explored a parallel approach suitable for embedded platforms.
The chapter “Analytical solutions of some strong oscillators” presents an analytical solution for cubic and quintic Diffing’s oscillators. The authors consider arbitrary initial solutions. The authors point out that the Duffing equation has a large area of application: mechanical engineering, electrical engineering, plasma physics, etc.
The chapter “Optimal heat distribution using asymptotic analysis techniques” uses a deterministic method. The next solution is determined using the concept of topological derivative. The topological derivative defines a vector that iteratively defines the path to the final solution (optimal heat distribution).
3. Metaheuristics
Metaheuristics are a wide range of methods, usually inspired from nature. Every metaheuristic has a random component and this is why they are also known as probabilistic methods. The chapter “Optimization multicriteria scheduling criteria through analytical hierarchy process and lexicography goal programming modeling” is the first example that uses a probabilistic method. Multicriteria decision analysis is a research area where multiple possibilities are considered to determine the best choices. It creates an aleatory matrix of judgments which will determine the coherence among the criteria. The authors present an example about electric cable cut. The following criteria were considered: qualification of workers, safety knowledge, equipment performance, scheduling equipment, production technology, and cost of upgrading waste.
Some metaheuristics used in this set of chapters are briefly introduced: simulated annealing, tabu search, and genetic algorithms.
3.1 Simulated annealing
Simulated annealing is based on metal annealing [8]. It was originally proposed to solve combinatorial problems. However, several proposals to incorporate continuous parameters soon appeared [9, 10, 11]. Simulated annealing has clearly two different phases: exploratory and refinement [12]. Initially, at higher temperature, the domain is explored. At lower temperatures, the solution is refined and convergence happens. The simulated annealing has only one current solution.
The simulated annealing with crystallization factor described in the chapter “Versatility of simulated annealing with crystallization heuristic: its application to a great assortment of problems” is an example of how continuous parameters can be approached. The crystallization factor supplies a sensitivity to the algorithm. It was successfully applied to irregular packing problems with fixed containers, in this situation, the cost function is discrete and some parameters are continuous [13, 14, 15]. This chapter shows different applications, the curve interpolation application has integer and continuous parameters [16, 17, 18, 19, 20].
The objective function of some problems might be costly computationally. For example, when it is required to solve a finite element problem. The simulated annealing can be modified to incorporate a partial evaluation of the objective function. The objective function returns an interval which surely contains the function’s precise value. This approach was successfully applied to the electrical impedance tomography problem where 32 finite element problems were solved every time to evaluate the objective function [21, 22, 23, 24, 25, 26, 27, 28].
Several books have been published about simulated annealing [29, 30]. Simulated annealing has also solved multi-objective problems [31]. A well known simulated annealing for multi-objective is AMOSA [32, 33]. The simulated annealing with crystallization factor has also solved multi-objective problems [34, 35, 36].
The simulated annealing with crystallization heuristic has shown to be very versatile, regarding the type of parameters (integer, continuous, combinatorial) and the type of objective function (continuous, discrete, intervalar, and multiple).
3.2 Tabu search
Tabu search was originally proposed to solve combinatorial problems (like simulated annealing). Tabu search can be viewed as a special case of simulated annealing. However, not with all possibilities available to the simulated annealing. Tabu search uses a local search and it has a structure storing visited solutions. One already visited solution is avoided. The word Tabu means that something cannot be touched, in the sense that already visited solutions must not be visited again. Three types of memories are commonly used to store the visited solutions: short-term, intermediate-term, and long-term [37]. The tabu search, like the simulated annealing, has only one current solution.
The chapter “A methaheuristic tabu search optimization algorithm: applications to chemical and environmental process” shows that tabu search can be used in a wide spectrum of engineering problems.
3.3 Genetic algorithms
Genetic algorithms are based on natural selection and they create a population of solutions. Based on this population of solutions, a new population is created using some operators: cross-over and mutation [38]. Genetic algorithm has a strong exploratory feature. Currently, it can be used with integer and continuous parameters. However, it does not have any convergence criteria. After a certain number of iterations, the best so far solution is defined as the
The chapter “Mixed-discrete nonlinear programming engineering problems” combines genetic algorithms with sequential quadratic programming. The sequential quadratic programming is a well-known gradient-based search algorithm.
4. Conclusions
As described, there are many types of engineering problems and this is the reason for the great number of methods developed to solve them. In this set of chapters, we intend to enumerate a few of them, showing their pros and cons and discuss the types of their parameters, type of the objective functions, computational cost, implementation facility, etc.
Acknowledgments
M. S. G. Tsuzuki is partially supported by CNPq (process 311.195/2019-9). A. K. Sato is supported by FUSP/Petrobras.
References
- 1.
Peyvandi H. Computational Optimization in Engineering—Paradigms and Applications. London, UK: IntechOpen; 2017. p. 4 - 2.
Auroux D, Caillau J-B, Duvigneau R, Habbal A, Pantz O, Pronzato L, et al. Survey of sequential convex programming and generalized Gauss-Newton methods. ESAIM: Proceedings and Surveys. 2021; 71 :64-88 - 3.
Boussa I, Lepagnot J, Siarry P. A survey on optimization metaheuristics. Information Sciences. 2013; 237 (7):82-117 - 4.
Grippo L, Lampariello F, Lucidi S. Nonmonotone line search technique for Newton’s method. SIAM Journal on Numerical Analysis. 1986; 23 :707-716 - 5.
Ichikawa M, Gotoh T, Kagei S, Iwasawa T, Tsuzuki MSG. Pulmonary blood flow analysis based on two input model with aorta and pulmonary artery contribution using contrast-enhanced MRI. In: Proceeding of the 11th IEEE ISBI; Beijing, China. 2014. pp. 882-885 - 6.
Saka T, Ichikawa M, Kagei S, Gotoh T, Iwasawa T, Tsuzuki MSG. Perfusion analysis for lung MR images considering non-monotonic response of Gd-contrast agent. IFAC-PapersOnLine. 2014; 47 (3):3587-3592 - 7.
Burer S, Letchford AN. Non-convex mixed-integer nonlinear programming: A survey. Surveys in Operations Research and Management Science. 2012; 17 (7):97-106 - 8.
Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science. 1983; 220 (4598):671-680 - 9.
Corana A, Marchesi M, Martini C, Ridella S. Minimizing multimodal functions of continuous variables with the simulated annealing algorithm. ACM Transactions on Mathematical Software. 1987; 13 :262-280 - 10.
Ingber L. Very fast simulated re-annealing. Mathematical and Computer Modelling. 1989; 12 (8):967-973 - 11.
Duran GC, Sato AK, Ueda EK, Takimoto RY, Bahabadi HG, Barari A, et al. Using feedback strategies in simulated annealing with crystallization heuristic and applications. Applied Sciences. 2021; 11 :11814 - 12.
Tavares RS, Martins TC, Tsuzuki MSG. Simulated annealing with adaptive neighborhood: A case study in off-line robot path planning. Expert Systems with Applications. 2011; 38 (4):2951-2965 - 13.
Martins TC, Tsuzuki MSG. Simulated annealing applied to the rotational polygon packing. IFAC Proceedings Volumes. 2006; 39 (3):475-480 - 14.
Martins TC, Tsuzuki MSG. Rotational placement of irregular polygons over containers with fixed dimensions using simulated annealing and no-fit polygons. Journal of the Brazilian Society of Mechanical Sciences. 2008; 30 (3):205-212 - 15.
Sato AK, Martins TC, Tsuzuki MSG. Rotational placement using simulated annealing and collision free region. IFAC Proceedings Volumes. 2010; 43 :234-239 - 16.
Ueda EF, Martins TC,Tsuzuki MSG. Planar curve fitting by simulated annealing with feature points determination, IFAC-PapersOnLine. Jan 2018; 51 :290-295 - 17.
Ueda EK, Tsuzuki MS, Barari A. Piecewise Bézier curve fitting of a point cloud boundary by simulated annealing, in INDUSCON 2018, Jan 2019. pp. 1335-1340 - 18.
Ueda EK, Barari A, Sato AK, Tsuzuki MSG. Detection of defected zone using 3D scanning data to repair worn turbine blades. IFAC-PapersOnLine. 2020; 53 :10531-10535 - 19.
Ueda EK, Barari A, Tsuzuki MSG. Determination of open boundaries in point clouds with symmetry. In: Advances in Intelligent Systems and Computing. Proceeding of the ICGG 2020. Vol. 1296. 2021. pp. 332-342 - 20.
Ueda EK, Sato AK, Martins TC, Takimoto RY, Rosso RSU Jr, Tsuzuki MSG. Curve approximation by adaptive neighborhood simulated annealing and piecewise Bézier curves. Soft Computing. 2020; 24 :18821-18839 - 21.
Martins TC, Camargo EDLB, Lima RG, Amato MBP, Tsuzuki MSG. Electrical impedance tomography reconstruction through simulated annealing with incomplete evaluation of the objective function. In: 33rd IEEE EMBC; Boston, USA. 2011. pp. 7033-7036 - 22.
Martins TC, Tsuzuki MSG. Simulated annealing with partial evaluation of objective function applied to electrical impedance tomography. IFAC Proceedings Volumes. 2011; 44 :4989-4994 - 23.
Tavares RS, Martins TC, Tsuzuki MSG. Electrical impedance tomography reconstruction through simulated annealing using a new outside-in heuristic and GPU parallelization. Journal of Physics: Conference Series. Dec 2012; 407 :012015 - 24.
Martins TC, Tsuzuki MSG. Electrical impedance tomography reconstruction through simulated annealing with total least square error as objective function. In: 34th IEEE EMBC; San Diego, USA. 2012. pp. 1518-1521 - 25.
Martins TC, Tsuzuki MSG. Electrical impedance tomography reconstruction through simulated annealing with multi-stage partially evaluated objective functions. In: 35th IEEE EMBC; Osaka, Japan. 2013. pp. 6425-6428 - 26.
Martins TC, Tsuzuki MSG, Camargo EDLBD, Lima RG, Moura FSD, Amato MBP. Interval simulated annealing applied to electrical impedance tomography image reconstruction with fast objective function evaluation. Computers & Mathematcs with Applications. 2016; 72 (5):1230-1243 - 27.
Martins TC, Tsuzuki MSG. Investigating anisotropic EIT with simulated annealing. IFAC-PapersOnLine. 2017; 50 :9961-9966 - 28.
Tavares RS, Sato AK, Martins TC, Lima RG, Tsuzuki MSG. GPU acceleration of absolute EIT image reconstruction using simulated annealing. Biomedical Signal Processing and Control. 2019; 52 :445-455 - 29.
Tan CM. Simulated Annealing. London, UK: IntechOpen; 2008 - 30.
Tsuzuki MSG. Simulated Annealing—Advances, Applications and Hybridizations. London, UK: IntechOpen; 2012 - 31.
Tsuzuki MSG. Simulated Annealing—Single and Multiple Objective Problems. London, UK: IntechOpen; 2012 - 32.
Bandyopadhyay S, Saha S, Maulik U, Deb K. A simulated annealing-based multiobjective optimization algorithm: AMOSA. IEEE Transactions on Evolutionary Computation. 2008; 12 :269-283 - 33.
Martins TC, Fernandes AV, Tsuzuki MSG. Image reconstruction by electrical impedance tomography using multi-objective simulated annealing. In: IEEE ISBI 2014; Beijing, China. July 2014. pp. 185-188 - 34.
Martins TC, Tsuzuki MSG. EIT image regularization by a new multi-objective simulated annealing algorithm. In: Proceeding of the 37th IEEE EMBC; Milan, Italy. 2015. pp. 4069-4072 - 35.
Ueda EK, Tsuzuki MSG, Takimoto RY, Sato AK, Martins TC, Miyagi PE, et al. Piecewise Bézier curve fitting by multiobjective simulated annealing. IFAC-PapersOnLine. 2016; 49 :49-54 - 36.
Najafabadi HR, Goto TG, Martins TC, Barari A, Tsuzuki MSG. Multi-objective topology optimization using simulated annealing method. In: Advances in Intelligent Systems and Computing, Proceeding of the ICGG 2020. Vol. 1296. 2021. pp. 343-353 - 37.
Jaziri W. Tabu Search. Vienna, Austria: I-Tech Education and Publishing; 2008 - 38.
Popa R. Genetic Algorithms in Applications. London, UK: IntechOpen; 2012