Global optimization methods for engineering applications: A review

A review of the methods for global optimization reveals that most methods have been developed for unconstrained problems. They need to be extended to general constrained problems because most of the engineering applications have constraints. Some of the methods can be easily extended while others need further work. It is also possible to transform a constrained problem to an unconstrained one by using penalty or augmented Lagrangian methods and solve the problem that way. Some of the global optimization methods find all the local minimum points while others find only a few of them. In any case, all the methods require a very large number of calculations. Therefore, the computational effort to obtain a global solution is generally substantial. The methods for global optimization can be divided into two broad categories: deterministic and stochastic. Some deterministic methods are based on certain assumptions on the cost function that are not easy to check. These methods are not very useful since they are not applicable to general problems. Other deterministic methods are based on certain heuristics which may not lead to the true global solution. Several stochastic methods have been developed as some variation of the pure random search. Some methods are useful for only discrete optimization problems while others can be used for both discrete and continuous problems. Main characteristics of each method are identified and discussed. The selection of a method for a particular application depends on several attributes, such as types of design variables, whether or not all local minima are desired, and availability of gradients of all the functions.Notation Number of equality constraints - () ^T A transpose of a vector - A A hypercubic cell in clustering methods - Distance between two adjacent mesh points - Probability that a uniform sample of sizeN contains at least one point in a subsetA ofS - A(v, x) Aspiration level function - A The set of points with cost function values less thanf(x _G ^* ) +. Same asA _f () - A _f () A set of points at which the cost function value is within off(x _G ^* ) - A () A set of points x with[f(x)] smaller than - A _N The set ofN random points - A _q The set of sample points with the cost function value f _q - _Q The contraction coefficient; –1 _Q 0 - _R The expansion coefficient; _E > 1 - _R The reflection coefficient; 0 < _R 1 - A _x () A set of points that are within the distance from x _G ^* - D Diagonal form of the Hessian matrix - det() Determinant of a matrix - d _j A monotonic function of the number of failed local minimizations - d _t Infinitesimal change in time - d _x Infinitesimal change in design - A small positive constant - (t) A real function called the noise coefficient - ₀ Initial value for(t) - exp() The exponential function - f ^(c) The record; smallest cost function value over X^(C) - [f(x)] Functional for calculating the volume fraction of a subset - Second-order approximation tof(x) - f(x) The cost function - An estimate of the upper bound of global minimum - f ^E The cost function value at x^E - f ^L The cost function value at x^L - f _opt The current best minimum function value - f ^P The cost function value at x ^P - f ^Q The cost function value at x ^Q - f _q A function value used to reduce the random sample - f ^R The cost function value at x ^R - f ^S The cost function value at x^S - f _{T F min} A common minimum cost function value for several trajectories - f _{TF opt} The best current minimum value found so far forf _{TF min} - f ^W The cost function value at x ^W - G Minimum number of points in a cell (A) to be considered full - The gamma function - A factor used to scale the global optimum cost in the zooming method - Minimum distance assumed to exist between two local minimum points - gi(x) Constraints of the optimization problem - H The size of the tabu list - H(x^*) The Hessian matrix of the cost function at x^* - h _j Half side length of a hypercube - h _m Minimum half side lengths of hypercubes in one row - I The unity matrix - ILIM A limit on the number of trials before the temperature is reduced - J The set of active constraints - K Estimate of total number of local minima - k Iteration counter - The number of times a clustering algorithm is executed - L Lipschitz constant, defined in Section 2 - L The number of local searches performed - _i The corresponding pole strengths - log () The natural logarithm - LS Local search procedure - M Number of local minimum points found inL searches - m Total number of constraints - m(t) Mass of a particle as a function of time - m() TheLebesgue measure of thea set - Average cost value for a number of random sample of points inS - N The number of sample points taken from a uniform random distribution - n Number of design variables - n(t) Nonconservative resistance forces - n _c Number of cells;S is divided inton _c cells - NT Number of trajectories - Pi (3.1415926) - P _i ^(j) Hypersphere approximating thej-th cluster at stagei - p(x ⁽ⁱ⁾⁾ Boltzmann-Gibbs distribution; the probability of finding the system in a particular configuration - pg A parameter corresponding to each reduced sample point, defined in (36) - Q An orthogonal matrix used to diagonalize the Hessian matrix - _i (i = 1, K) The relative size of thei-th region of attraction - r _i ^(j) Radius of thej-th hypersp here at stagei - R _x ^* Region of attraction of a local minimum x^* - r _j Radius of a hypersphere - r A critical distance; determines whether a point is linked to a cluster - R ⁿ A set ofn tuples of real numbers - A hyper rectangle set used to approximateS - S The constraint set - A user supplied parameter used to determiner - s The number of failed local minimizations - T The tabu list - t Time - T(x) The tunneling function - T _c (x) The constrained tunneling function - T _i The temperature of a system at a configurationi - TLIMIT A lower limit for the temperature - TR A factor between 0 and 1 used to reduce the temperature - u(x) A unimodal function - V(x) The set of all feasible moves at the current design - v(x) An oscillating small perturbation. - V(y⁽ⁱ⁾) Voronoi cell of the code point y⁽ⁱ⁾ - v^–1 An inverse move - v _k A move; the change from previous to current designs - w(t) Ann-dimensional standard. Wiener process - x Design variable vector of dimensionn - x^# A movable pole used in the tunneling method - x⁽⁰⁾ A starting point for a local search procedure - X^(c) A sequence of feasible points {x⁽¹⁾, x⁽²⁾,,x^(c)} - x(t) Design vector as a function of time - X^* The set of all local minimum points - x^* A local minimum point forf(x) - x^*(i) Poles used in the tunneling method - x _G ^* A global minimum point forf(x) - Transformed design space - The velocity vector of the particle as a function of time - Acceleration vector of the particle as a function of time - x ^C Centroid of the simplex excluding x ^L - x ^c A pole point used in the tunneling method - x ^E An expansion point of x ^R along the direction x ^C x ^R - x ^L The best point of a simplex - x ^P A new trial point - x ^Q A contraction point - x ^R A reflection point; reflection of x ^W on x ^C - x ^S The second worst point of a simplex - x ^W The worst point of a simplex - The reduced sample point with the smallest function value of a full cell - Y The set of code points - y ⁽ⁱ⁾ A code point; a point that represents all the points of thei-th cell - z A random number uniformly distributed in (0,1) - Z ^(c) The set of points x where [f ^(c) – ] is smaller thanf(x) - []₊ Max (0,) - | | Absolute value - The Euclidean norm - f[x(t)] The gradient of the cost function     

Automated sampling decision scheme for the AVM system

Reducing the sampling rate to as low as possible is a high priority for many factories to reduce production cost. Automatic virtual metrology based intelligent sampling decision (ISD) scheme had been previously developed for reducing the sampling rate and sustaining the virtual metrology (VM) accuracy. However, the desired sampling rate of the ISD scheme is fixed and set manually. Hence, whenever the VM accuracy gets worse, it cannot adaptively increase the default sampling rate in the ISD scheme. As a consequence, it would take more time to collect enough samples for improving the VM accuracy. Moreover, when the VM accuracy performs well all the time, it cannot automatically decrease the default sampling rate in ISD, which may result in unnecessary waste. Accordingly, this paper proposes an automated sampling decision (ASD) scheme to adaptively and automatically modify the sampling rate online and in real time for continuous improvement. The ASD scheme can monitor the VM accuracy online as well as update the VM models in real time for maintaining the VM accuracy when the VM accuracy becomes poor. Also, the ASD scheme can automatically reduce the sampling rate while the VM accuracy performs well.     

Polarization-Dependent Periodic Pulse Oscillation in a Diode-Laser-Pumped and Intracavity Frequency-Doubled Nd:YVO 4 Laser

We demonstrate that two cross-polarized longitudinal modes can have 50% higher conversion efficiency than two parallel-polarized longitudinal modes in a diode-laser-pumped and intracavity frequency-doubled Nd:YVO(4) laser when operated under periodic pulse oscillation. Through simulations of the rate equations for primary frequency intensities and gains, we also verify that this effect can be attributed to gain competition and complementary conversion coefficient between second-harmonic and sum-frequency generations.     

Inexpensive high availability solutions for the SIP-based VoIP service

In the era of IP-based service, people expect a simple, cheap, and competent Voice over IP (VoIP) service as an alternative of the traditional voice over PSTN. The introduction of the SIP protocol realizes the expectation. Following the cost saving spirit of VoIP, we focus on studying inexpensive high availability solutions for the SIP-based VoIP Service. In this paper, Peer-to-Peer (P2P) based and DN-LB based schemes are mainly compared in the paper. A P2P-based scheme enables an inexpensive high availability solution to the VoIP service by the shared computation resources form P2P nodes. Such a P2P-based solution may be appropriate for an individual VoIP user. However, a caller may take a large volume of messages to find out a callee via the proxy nodes in the P2P network. This inherent property of a P2P network may induce the message overhead and long call setup delay. Based on above, another inexpensive scheme, which is a probing-based name resolution solution, is proposed to achieve high availability and load balancing for the VoIP service. We tag the probing mechanism onto the open source project Domain Name Relay Daemon (DNRD) to become a domain name resolution based load balancer (DN-LB). With DN-LB, all request messages from clients can be fairly distributed to all failure-proof proxy servers in the server farm without using any additional costly intermediate network device and changing the standard SIP architecture. Such a DN-LB based solution may be a good choice for a VoIP service provider.     

Scalable continuous object detection and tracking in sensor networks

With the advancement of MEMS technologies, sensor networks have opened up broad application prospects. An important issue in wireless sensor networks is object detection and tracking, which typically involves two basic components, collaborative data processing and object location reporting. The former aims to have sensors collaborating in determining a concise digest of object location information, while the latter aims to transport a concise digest to sink in a timely manner. This issue has been intensively studied in individual objects, such as intruders. However, the characteristic of continuous objects has posed new challenges to this issue. Continuous objects can diffuse, increase in size, or split into multiple continuous objects, such as a noxious gas. In this paper, a scalable, topology-control-based approach for continuous object detection and tracking is proposed. Extensive simulations are conducted, which show a significant improvement over existing solutions.     

Extending 3D Lucas–Kanade tracking with adaptive templates for head pose estimation

The Lucas–Kanade tracker (LKT) is a commonly used method to track target objects over 2D images. The key principle behind the object tracking of an LKT is to warp the object appearance so as to minimize the difference between the warped object’s appearance and a pre-stored template. Accordingly, the 2D pose of the tracked object in terms of translation, rotation, and scaling can be recovered from the warping. To extend the LKT for 3D pose estimation, a model-based 3D LKT assumes a 3D geometric model for the target object in the 3D space and tries to infer the 3D object motion by minimizing the difference between the projected 2D image of the 3D object and the pre-stored 2D image template. In this paper, we propose an extended model-based 3D LKT for estimating 3D head poses by tracking human heads on video sequences. In contrast to the original model-based 3D LKT, which uses a template with each pixel represented by a single intensity value, the proposed model-based 3D LKT exploits an adaptive template with each template pixel modeled by a continuously updated Gaussian distribution during head tracking. This probabilistic template modeling improves the tracker’s ability to handle temporal fluctuation of pixels caused by continuous environmental changes such as varying illumination and dynamic backgrounds. Due to the new probabilistic template modeling, we reformulate the head pose estimation as a maximum likelihood estimation problem, rather than the original difference minimization procedure. Based on the new formulation, an algorithm to estimate the best head pose is derived. The experimental results show that the proposed extended model-based 3D LKT achieves higher accuracy and reliability than the conventional one does. Particularly, the proposed LKT is very effective in handling varying illumination, which cannot be well handled in the original LKT.     

Application of a remote image surveillance system in a robotic weapon

As one of the major steps toward a fully intelligent autonomous robotic weapon, we have made progress in three major areas, (1) design of the surveillance system by an AVR microcontroller, (2) implementation of the design mechanism, and (3) performance of the human- machine interface surveillance system via the LabVIEW graphical programming environment, so that the supervisor can control the vehicle with a keyboard or a specially adapted mouse. In order to accomplish all these achievements, there have been major additions and overhauls in both system software codes and system circuit board developments. All these developments, including a new algorithm and hardware implementation, are described in this article. The experimental results have shown the practicality of the AVR microcontroller, the LabVIEW graphical programming environment, and ZigBee wireless technology applied to a robotic weapon.     

Social evaluations of embodied agents and avatars

The purpose of this study was to examine social evaluations (i.e., perceptions of empathy and positivity) following peoples’ interactions with digital human representations. Female research participants engaged in a 3-min interaction while immersed in a 3-D immersive virtual environment with a “peer counselor.” Participants were led to believe that the peer counselor was either an embodied agent (i.e., computer algorithm) or an avatar (i.e., another person). During the interaction, the peer counselor either smiled or not. As predicted, a digitally-rendered smile was found to affect participants’ social evaluations. However, these effects were moderated by participants’ beliefs about their interaction partner. Specifically, smiles enhanced social evaluations of embodied agents but degraded them for avatars. Although these results are consistent with other findings concerning the communicative realism of embodied agents and avatars they uniquely demonstrate that people’s beliefs alone, rather than actual differences in virtual representations, can impact social evaluations.     

A multi-strategy knowledge interoperability framework for heterogeneous learning objects

This paper presents a knowledge exchange framework that can leverage the interoperability among semantically heterogeneous learning objects. With the release of various e-Learning standards, learning contents and digital courses are easy to achieve cross-platform sharing, exchanging, and even reorganizing. However, knowledge sharing in semantic level is still a challenge due to that the learning materials can be presented in any form, such as audios, videos, web pages, and even flash files. The proposed knowledge exchange framework allows users to share their learning materials (also called “learning objects”) in semantic level automatically. This framework contains two methodologies: the first is a semantic mapping between knowledge bases (i.e. ontologies) which have essentially similar concepts, and the second is an ontology-based classification algorithm for sharable learning objects. The proposed algorithm adopts the IMS DRI standard and classifies the sharable learning objects from heterogeneous repositories into a local knowledge base by their inner meaning instead of keyword matching. Significance of this research lies in the semantic inferring rules for ontology mapping and learning objects classification as well as the full automatic processing and self-optimizing capability. Focused on digital learning materials and contrasted to other traditional technologies, the proposed approach has experimentally demonstrated significantly improvement in performance.     

Hybrid feature selection by combining filters and wrappers

Feature selection aims at finding the most relevant features of a problem domain. It is very helpful in improving computational speed and prediction accuracy. However, identification of useful features from hundreds or even thousands of related features is a nontrivial task. In this paper, we introduce a hybrid feature selection method which combines two feature selection methods – the filters and the wrappers. Candidate features are first selected from the original feature set via computationally-efficient filters. The candidate feature set is further refined by more accurate wrappers. This hybrid mechanism takes advantage of both the filters and the wrappers. The mechanism is examined by two bioinformatics problems, namely, protein disordered region prediction and gene selection in microarray cancer data. Experimental results show that equal or better prediction accuracy can be achieved with a smaller feature set. These feature subsets can be obtained in a reasonable time period.