CHAPTER EIGHT

Hybrid Approaches

8.1 INTRODUCTION

As mentioned previously, the fields of industrial, civil, and military engineering continuously need new and efficient diagnostic methods. The same holds in the areas of geophysical applications, buried-object detection, cultural heritage, demining, and medical diagnostics. However, although several excellent results have been obtained by applying the imaging procedures developed in the previous chapters, the need for new application-oriented methods based on hybrid strategies is widely recognized. The idea is to combine different imaging modalities in order to derive profit from the specific features of the different methods and improve the effectiveness of the inspection.

Hybrid methods could include, for example, two-step procedures in which fast qualitative algorithms (Chapter 5) are combined with quantitative methods (Chapters 6 and 7) in order to first derive the supports of the unknown scatterers and successively retrieve the distributions of their dielectric parameters. Other approaches can combine different quantitative procedures (e.g., deterministic and stochastic algorithms can be combined in order to speed up the convergence of slow and computationally expensive stochastic methods near the global solution). Since efficient “general purpose” imaging techniques cannot be developed, these new combined strategies must be closely related to specific applications and should essentially lead to the implementation of model-driven approaches. This chapter discusses some examples of possible hybrid approaches. Although the definition of a hybrid method is again quite an arbitrary task, some examples are reported in this chapter, with reference to proposals appearing in the scientific literature. The first example concerns a case in which iterative methods (Chapter 6) for quantitative imaging of strong scatterers require an initial estimate of the distribution of dielectric parameters. As mentioned previously, this initial distribution can be obtained by using a fast qualitative method, such as diffraction tomography (Section 5.11). Quantitative deterministic methods for strong scatterers adopt these strategies almost always if a priori information about the configuration is not available. For example, in the study by Abubakar et al. (2006) the initial solution is obtained by using a linear backpropagation. Another useful approach concerns the use of a qualitative method to determine the shape of the object under test and then, successively, the distribution of its relevant dielectric parameters. An efficient method for deriving the shape of an object is the linear sampling method (Section 5.8), which can be combined with both deterministic and stochastic methods.

The direct application of stochastic optimization algorithms to solve inverse problems in electromagnetics, although highly desirable (as discussed in Chapter 7, these methods are potentially capable of finding the global minimum of a given functional, relatively independently of the properties of the functional itself, e.g., convexity, differentiability), is problematic because of the high computational load required by these methods. In fact, a direct application is possible only for limited parameterizations (see the examples given in Chapter 7). However, the favorable properties of these methods can be kept if they are combined with other faster methods. Hybrid strategies can be devised by using local search methods during the optimization process.

Owing to the versatility of stochastic optimization methods, discussed above, there are evidently several various possibilities of integrating stochastic and deterministic approaches. The simplest way is to start the local search when the stochastic method has reached a reasonable basin of attraction, that is, a region of the space solution where the global minimum is likely included. In the first iterations of the stochastic method, the solution space can be explored (starting from arbitrary trial solutions, not necessarily located near the right solution) and, possibly, during the minimization process, the trial solutions can escape from local minima. Then, the deterministic procedure starts and the solution is quickly reached. The main difficulty is in devising a criterion for switching from the stochastic method to the determinist one. This approach has been followed in the study by Park and Jeong (1999), where a standard genetic algorithm is combined with a Levenberg-Marquardt algorithm. A similar method has been used in the study by Caorsi et al. (2000), where the genetic algorithm is cascaded with a standard conjugate-gradient method. Another critical point is represented by the modality to be adopted in order to restart the stochastic process if the final solution is not acceptable, that is, if the global minimum is not reached.

Another example of hybridization of a stochastic algorithm with a deterministic one can be found in the paper by Xiao and Yabe (1998), However, the integration of stochastic and deterministic methods can be made stronger. The so-called memetic algorithm represents a significant example.

8.2 THE MEMETIC ALGORITHM

The memetic algorithm is an iterative population-based method (Moscato 1989, Moscato and Norman 1992, Merz and Freisleben 2000). During the iterative evolution, only local minima of the cost function are considered. They are obtained by applying a local minimization method to any element of the population.

Let us consider the classical structure of the genetic algorithm (Section 7.3). After an initialization phase (k = 0), in which a population ⁰ is constructed (the same considerations made concerning the genetic algorithm still hold true here), before the application of the genetic operators, the chromosomes Ψ^k_p, p = 1,...,P⁰ are subjected to a local optimization, which provides a set of local optima , p = 1,...,P⁰. Since the same minimum can be reached more than once, the set of different local minima includes Q⁰ ≤ P⁰ elements. This set is used for application of the genetic operators (with the same modalities discussed in Section 7.3 for the genetic algorithm). If a reduced parameterization of the scattering problem can be used, since the algorithm's population is composed of local optima only, the number of individuals involved in the evolution can be chosen very small, even equal to the number of unknowns.

In this way, the memetic algorithm combines, at each iteration, a local search and a stochastic minimization. The use of a local search is aimed at increasing the convergence velocity, whereas the genetic operators are applied to escape from local minima. Consequently, the method combines the advantages of both stochastic and deterministic procedures.

It should be mentioned that when it was introduced, the memetic algorithm was aimed at “emulating the process of exchange of ideas among people” by considering the concept of meme, which is a unit of information that can be transmitted when people exchange ideas (Merz and Freisleben 2000). Moreover, people process any idea to obtain a personal optimum before propagating it. Accordingly, in the memetic algorithm, each “idea” is an individual and the combined procedure that performs the local/global optimization is inspired by the abovementioned considerations.

Different local search methods can, of course, be considered. Caorsi et al. (2003a) used a standard conjugate gradient together with a real-coded implementation of the genetic operators. Some illustrative examples are presented below. In the first example, the same problem geometry considered by Michalski (2001) is applied. In particular, a borehole configuration is assumed and the target is the reconstruction of an infinite dielectric cylinder under transverse magnetic (TM) illumination conditions. However, Michalski's (2001) approach requires a numerical computation of forward scattering solution needed to calculate the cost function at any iteration. On the contrary, in the study by Caorsi et al. (2003a) the scatterer cross section has been approximated by a multilayer elliptic cylinders, so that the scattered values are computed by using the recursive procedure based on series expansions in Mathieu functions discussed in Section 3.5, according to the assumption of neglecting the effect of the interface (Michalski 2001).

An example is given as follows. The imaging configuration is the one reported in Figure 4.9. The object to be inspected is a void (ε_r = 1) in the soil of cylindrical shape with an elliptic cross section. The center of the cross section is placed at point r_t = −0.173λ− 0.865λ,ŷ, whereas the semimajor axis of the ellipse is a = 0.26λ and the semifocal distance is d = 0.245λ. The background medium is lossless and characterized by ε_b = 12ε₀ and μ_b = μ₀. The source (S = 1) is a line current located at point x₁ = −0.865λ (position of the transmitting hole) and y¹ = −1.041λ (depth of the source), whereas the scattered field is collected at M = 13 measurement points such that x₂ = 0.865λ (position of the receiving hole) and y^m = −(m − 1)·0.173λ, m = 1,..., M.

The cost function is constituted by the square norm of the residual of the discrete data equation, although amplitude-only data are considered as input data (see Section 11.3 for a brief discussion of this point). Moreover, the memetic algorithm has been applied by using the following parameters (Caorsi et al. 2003b): probability of crossover, p_c = 0.9; probability of mutation, p_m = 0.3; maximum number of iterations for the conjugate gradient (local search), 20; maximum number of iterations for the genetic operators (global search), 30; threshold for the stopping the local search, F (cost function) ≤ 10⁻⁵; threshold for stopping the application of the genetic operators, F ≤ 10⁻³. Moreover, some a priori information is introduced by setting some bounds on the unknowns to be retrieved (some of them are directly related to the geometry of the problem). In particular, the center of the elliptic cross section is searched in the range −0.865λ≤x≤0.865λ and −2.1λ≤y≤0, whereas the relative dielectric permittivity of the homogeneous cylinder is assumed in the range 1 ≤ ε_r ≤ 120.

Figure 8.1a shows the behavior of the cost function for three elements of the population. In the figure, CG_kp denotes the value of the functional for the pth element of the population at the kth iteration, where k = 0 is the initialization phase (the starting solutions are randomly chosen in the abovementioned ranges), whereas MA and the rhombus indicate the values for the best element of the population (i.e., the best value of the kth iteration of the memetic algorithm). Between two iterations of the memetic algorithm (or, as in the present case, between the initialization and the first iteration), the plots in Figure 8.1a concern the local search. As can be seen, just after the first iteration of the memetic algorithm, the convergence threshold is reached. It is worth noting that the local search is trapped in local minima, since the trial solutions in the initialization phase are very far from the actual solution. However, the algorithm, due to the application of the genetic operators, is able to escape from the local minima and explore a different region of the solution space, allowing the convergence of the process. It should be noted that, for the best individual, the starting value of the estimated dielectric permittivity was ε_r ≈ 40, whereas in the final solution, the actual value of ε_r = 1.0 has been approximated with an error less than 5%.

FIGURE 8.1 Reconstruction of a homogenous dielectric cylinder in a borehole configuration using the memetic algorithm: (a) the functional to be minimized for three elements of the population; (b) trajectories of the individuals of the population of the memetic algorithm in the [x,y] plane (coordinates of the center of the reconstructed cross section). [Reproduced from S. Caorsi, A. Massa, M. Pastorino, and A. Randazzo, “Electromagnetic detection of dielectric scatterers using phaseless synthetic and real data and the memetic algorithm,” IEEE Trans. Geosci. Remote Sens. 41(12), 2745–2753 (Dec. 2003), © 2003 IEEE.]

Very interesting is Figure 8.1b, which shows the trajectories of the coordinates of center of the elliptic cross section during application of the memetic algorithm. In the figure, the continuous and dashed lines refer to movements during initialization and the first iteration, respectively. Furthermore, black and white triangles denote the starting and arrival points during application of the local search, respectively. As in Figure 8.1a, the rhomb denotes the optimum element at each phase. As can be seen, at the beginning of the initialization phase, the trial solutions are quite distant from the true solution (point r_t = −0.173λ−0.865λŷ). At the end of this phase, the best solution is represented by the rhomb in the upper left part of the figure. However, all the solutions are not near the true solution. After application of the genetic operators, new solutions are generated (white triangles). One of them is located near the true solution and, starting from this solution, at iteration k = 1, the local search is able to rapidly obtain the final optimum solution. On the contrary, the other elements of the population move toward other points in the search space. In particular, the movement of the solution in the lowest right part of the figure terminates in a final point coincident with a final point for the initialization phase; that is, the same local minimum is reached.

Another example concerns the reconstruction of a two-layer elliptic dielectric cylinder, which is bounded by two ellipses whose semimajor axes are a₁ = 0.26λ and a₂ = 0.295λ. The relative dielectric permittivities of the two layers are ε_r1 = 1.0 (inner layer) and ε_r2 = 5.0 (outer layer). The scatterer corresponds essentially to a pipe or a hollowed buried cylinder. The center of the cross section, the semifocal distance, and all the other parameters of the imaging configuration and of the memetic algorithm are the same as in the previous example. Figure 8.2a shows the contours of the reconstructed cross sections at the various iterations corresponding to the best elements of the population. In this case, the final solution is reached after five iterations of the memetic algorithm. The behavior of the cost function during the minimization process is shown in Figure 8.2b, again referred to as the “best element of the population.”

In this case, too, at iterations k = 1 and k = 2, the same contours are retrieved, which correspond to the same local minimum of the cost function. However, at the end of the local search of iteration k = 5 a very good solution is reached. The abilities of the memetic algorithm to escape from local minima are clearly shown in Figure 8.2b.

The memetic algorithm has also been used to inspect PEC cylinders. Figure 8.3 provides the results of the reconstruction of a circular cylinder performed by inverting real scattering data that have been measured by a prototype of the microwave imaging system based on the modulated scattering technique and working at 3 GHz (Caorsi et al. 2002). The apparatus is described in Section 9.4.

Finally, it should be mentioned that the memetic algorithm has been also considered a good candidate in other inverse problems in the field of applied electromagnetics. For example, Pisa et al. (2005) used it to compute the specific absorption rate inside a human head when subjected to radiation from a cellular phone.

FIGURE 8.2 Reconstruction of a two-layer elliptic cylinder using the memetic algorithm: (a) cross section of the cylinder at various iterations (best elements of the population); (b) behavior of the functional to be minimized (best element of the population). [Reproduced from S. Caorsi, A. Massa, M. Pastorino, and A. Randazzo, “Electromagnetic detection of dielectric scatterers using phaseless synthetic and real data and the memetic algorithm,” IEEE Trans. Geosci. Remote Sens. 41 (12), 2745–2753 (Dec. 2003), © 2003 IEEE.]

FIGURE 8.3 Errors on the reconstruction on the parameters of a PEC circular cylinder by using real data, memetic algorithm: (a) semimajor axis; (b) x coordinate of the center; (c) radius. In each figure, a, b, c, and d refer to the populations at the beginning of the initial phase, at the end of the initial phase, after the application of the genetic operators, and at the end of the first iteration, respectively. [Reproduced from S. Caorsi, A. Massa, M. Pastorino, and A. Randazzo, “Detection of PEC elliptic cylinders by a memetic algorithm using real data,” Microwave Opt. Technol. Lett. 43 (4), 271–273 (Nov. 20, 2004), © 2004 Wiley.]

8.3 LINEAR SAMPLING METHOD AND ANT COLONY OPTIMIZATION

As mentioned in Section 8.1, several different hybrid techniques can be devised by combining different approaches. In this section, we consider, for illustration purposes, the combination of a qualitative method, namely, the linear sampling method (Section 5.8), and a quantitative stochastic method, ant colony optimization (Section 7.6). Integration of the two approaches in a single code is straightforward. In fact, the imaging process consists of two stages: (1) starting from the measured values of the scattered electric field in the observation domain, the shapes and positions of the unknown scatterers are determined very rapidly by application of the linear sampling method; and (2) when the support of the scatterer is available, the ant colony optimization method can be applied to retrieve the dielectric properties of the target. In this case, taking into account the a priori information concerning the shape of the target, a relatively small parameterization can be used for the stochastic approach.

This approach has been followed (Brignone et al. 2008a) for two-dimensional configurations and extended to three-dimensional configurations (Brignone et al. 2008b). The hybrid approach combines the robustness and generality of the linear sampling method, which is able to retrieve the contours of a wide class of scatterers (e.g., dielectric and conducting objects, constituting either weak or strong scatterers) with the capability of escaping from local minima of the ant colony optimization algorithm, which has been found to converge within a reasonably small number of iterations.

A reconstruction example is shown in Figure 8.4 (Brignone et al. 2008a). It concerns the inspection of two separated cylinders. The original configuration is shown in Figure 8.4a. The circular and rectangular cylinders are characterized by ε_r = 4 and ε_r = 2, respectively.

The cross sections of the cylinders are located in a square investigation domain of side 0.26m and discretized into 31 × 31 square subdomains. The number of incidence and observation angles, uniformly spaced for sake of simplicity, is S = M = 12, and the operating frequency is f = 1 GHz. Each measurement sample is corrupted by a zero mean additive Gaussian noise with variance equal to 7% of its value (Brignone et al. 2008a).

The following parameters have been used the ant colony optimization application (see Section 7.6): N = 114, P = 120, q = 0.1, Q = 5, and ξ = 0.65. Figure 8.4b gives the profiles detected by the linear sampling methods, whereas Figure 8.4c provides the dielectric permittivity distribution retrieved using the ant colony optimization method (at iteration k = 300). As can be seen, the optimization procedure successfully exploits the a priori information on the shape provided by the qualitative approach. It is worth noting that despite discretization of the investigation domain into 961 subdomains, the number of unknowns in the stochastic optimization procedure is reduced to only 114 unknowns, due to the useful information provided by the linear sampling method. Finally, some other results obtained using this hybrid technique are discussed in Section 8.3.

FIGURE 8.4 Imaging of two separated cylinders with circular and rectangular cross sections using the hybrid method of linear sampling and ant colony optimization: (a) actual scatterers; (b) supports provided by the linear sampling method; (c) reconstructed distribution of relative dielectric permittivity using the ant colony optimization algorithm. The gray lines in (b) and (c) represent the true profiles. (Reproduced from M. Brignone, G. Bozza, A. Randazzo, R. Aramini, M. Piana, and M. Pastorino, “Hybrid approach to the inverse scattering problem by using ant colony optimization and no-sampling linear sampling,” Proc. 2008 IEEE Antennas and Propagation Society Int. Symp., San Diego, CA, July 5–12, 2008, © 2008 IEEE.)

Clearly, following this philosophy, the stochastic method can be replaced in a straightforward way with a quantitative deterministic method. This approach has been followed, for example, in the study by Catapano et al. (2007), where the linear sampling method has been used in a two-step procedure together with a solving technique based on the extended Born approximation (Section 4.7) and a gradient procedure (Section 6.8).

REFERENCES

Abubakar, A., P. M. van den Berg, and T. M. Habashy, “An integral equation approach for 2.5-dimensional forward and inverse electromagnetic scattering,” Geophys. J. Int. 165, 744–762 (2006).

Brignone, M., G. Bozza, A. Randazzo, R. Aramini, M. Piana, and M. Pastorino, “Hybrid approach to the inverse scattering problem by using ant colony optimization and no-sampling linear sampling,” Proc. 2008 IEEE Antennas Propagation Society Int. Symp., San Diego, CA, July 5–12, (2008a).

Brignone, M., G. Bozza, A. Randazzo, R. Aramini, M. Piana, and M. Pastorino, “A hybrid approach to 3D microwave imaging by using linear sampling and ant colony optimization,” IEEE Trans. Anten. Propag. 56, 3224–3232 (2008b).

Caorsi, S., M. Donelli, and M. Pastorino, “A passive antenna system for data acquisition in scattering applications,” IEEE Anten. Wireless Propag. Lett. 1, 203–206 (2002).

Caorsi, S., A. Massa, and M. Pastorino, “A computational technique based on a real-coded genetic algorithm for microwave imaging purposes,” IEEE Trans. Geosci. Remote Sens. 38, 1697–1708 (2000).

Caorsi, S., M. Pastorino, M. Raffetto, and A. Randazzo, “Detection of buried inhomogeneous elliptic cylinders by a memetic algorithm,” IEEE Trans. Anten. Propag. 51, 2878–2884 (2003a).

Caorsi, S., A. Massa, M. Pastorino, and A. Randazzo, “Electromagnetic detection of dielectric scatterers using phaseless synthetic and real data and the memetic algorithm,” IEEE Trans. Geosci. Remote Sens. 41, 2745–2753 (2003b).

Catapano, I., L. Crocco, M. D'Urso, and T. Isernia, “On the effect of support estimation and of a new model in 2-D inverse scattering problems,” IEEE Trans. Anten. Propag. 55, 1895–1899 (2007).

Merz, P. and B. Freisleben, “Fitness landscape analysis and memetic algorithms for the quadratic assignment problem,” IEEE Trans. Evolut. Comput. 4, 337–352 (2000).

Michalski, K. A., “Electromagnetic imaging of elliptical-cylindrical conductors and tunnels using a differential evolution algorithm,” Microwave Opt. Technol. Lett. 28, 164–169 (2001).

Moscato, P., On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts toward Memetic Algorithms, Calif. Institute of Technology, Pasadena, Caltech Concurrent Computation Program Technical Report 826, 1989.

Moscato, P. and M. G. Norman, “A ‘memetic’ approach for the traveling salesman problem. Implementation of a computational ecology for combinatorial optimization on message-passing systems,” in Parallel Computing and Transputer Applications, M. Valero et al., eds., Institute of Physics, Amsterdam, 1992.

Park, C.-S. and B.-S. Jeong, “Reconstruction of a high contrast and large object by using the hybrid algorithm combining a Levenberg-Marquart algorithm and a genetic algorithm,” IEEE Trans. Magn. 35, 1582–1585 (1999).

Pisa, S., M. Cavagnaro, V. Lopresto, and E. Piuzzi, “A procedure to develop realistic numerical models of cellular phones for an accurate evaluation of SAR distribution in the human head,” IEEE Trans. Microwave Theory Tech. 53, 1256–1265 (2005).

Xiao, F. and H. Yabe, “Microwave imaging of perfectly conducting cylinders from real data by micro genetic algorithm couple with deterministic method,” IEICE Trans. Electron. E81-C, 1784–1792 (1998).