Evolutionary computation applied to the reconstruction of 3-D surface topography in the SEM

A genetic algorithm has been applied to the line profile reconstruction from the signals of the standard secondary electron (SE) and/or backscattered electron detectors in a scanning electron microscope. This method solves the topographical surface reconstruction problem as one of combinatorial optimization. To extend this optimization approach for three-dimensional (3-D) surface topography, this paper considers the use of a string coding where a 3-D surface topography is represented by a set of coordinates of vertices. We introduce the Delaunay triangulation, which attains the minimum roughness for any set of height data to capture the fundamental features of the surface being probed by an electron beam. With this coding, the strings are processed with a class of hybrid optimization algorithms that combine genetic algorithms and simulated annealing algorithms. Experimental results on SE images are presented.     

Application of simulated annealing to the biclustering of gene expression data.

In a gene expression data matrix, a bicluster is a submatrix of genes and conditions that exhibits a high correlation of expression activity across both rows and columns. The problem of locating the most significant bicluster has been shown to be NP-complete. Heuristic approaches such as Cheng and Church's greedy node deletion algorithm have been previously employed. It is to be expected that stochastic search techniques such as evolutionary algorithms or simulated annealing might improve upon such greedy techniques. In this paper we show that an approach based on simulated annealing is well suited to this problem, and we present a comparative evaluation of simulated annealing and node deletion on a variety of datasets. We show that simulated annealing discovers more significant biclusters in many cases. Furthermore, we also test the ability of our technique to locate biologically verifiable biclusters within an annotated set of genes.     

Simulated annealing, acceleration techniques, and image restoration

Typically, the linear image restoration problem is an ill-conditioned, underdetermined inverse problem. Here, stabilization is achieved via the introduction of a first-order smoothness constraint which allows the preservation of edges and leads to the minimization of a nonconvex functional. In order to carry through this optimization task, we use stochastic relaxation with annealing. We prefer the Metropolis dynamics to the popular, but computationally much more expensive, Gibbs sampler. Still, Metropolis-type annealing algorithms are also widely reported to exhibit a low convergence rate. Their finite-time behavior is outlined and we investigate some inexpensive acceleration techniques that do not alter their theoretical convergence properties; namely, restriction of the state space to a locally bounded image space and increasing concave transform of the cost functional. Successful experiments about space-variant restoration of simulated synthetic aperture imaging data illustrate the performance of the resulting class of algorithms and show significant benefits in terms of convergence speed.     

Telecommunication access network design with reliability constraints

In this paper, we study the problem of the design of telecommunication access networks with reliability constraints. These networks form an important part of the telecommunications infrastructure of large organizations, such as banks. Using data patterned after an actual bank network in the U.S., we formulate an optimization model for this problem which specifically takes into account the various cost, and discount structures offered by telecommunication carriers. We then develop dedicated solution procedures for obtaining solutions. Starting from a cluster solution, we then use perturbation techniques which we developed specifically for this problem within an overall simulated annealing solution algorithm. We show how to make the solution procedure more efficient by implicitly determining the values for many variables. We then report the results of our computational testing for a variety of problems. We compare our solution to a lower bound obtained using a linear programming relaxation. We show that substantial cost savings can be realized with our model, and solution procedure. Finally, we discuss which types of annealing steps in the simulated annealing algorithm are important.     

Stochastic nonlinear image restoration using the wavelet transform

The dominant methodology for image restoration is to stabilize the problem by including a roughness penalty in addition to faithfulness to the data. Among various choices, concave stabilizers stand out for their boundary detection capabilities, but the resulting cost function to be minimized is generally multimodal. Although simulated annealing is theoretically optimal to take up this challenge, standard stochastic algorithms suffer from two drawbacks: i) practical convergence difficulties are encountered with second-order prior models and ii) it remains computationally demanding to favor the formation of smooth contour lines by taking the discontinuity field explicitly into account. This work shows that both weaknesses can be overcome in a multiresolution framework by means of the 2-D discrete wavelet transform (DWT). We first propose to improve convergence toward global minima by single-site updating on the wavelet domain. For this purpose, a new restricted DWT space is introduced and a theoretically sound updating mechanism is constructed on this subspace. Next, we suggest to incorporate the smoothness of the discontinuity field via an additional penalty term defined on the high frequency subbands. The resulting increase in complexity is small and the approach requires the specification of a unique extra parameter for which an explicit selection formula is derived.     

Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks

The problem of finding an optimum conflict-free transmission schedule for a broadcast packet radio network (PRNET) is NP-complete. In addition to a host of heuristic algorithms, recently, neural network and simulated annealing approaches to solve this problem were reported. We show that the standard genetic algorithm, though able to solve small problems, performed poorly for large networks. This is because classical crossover and mutation operations create invalid members, which flood the whole population, hindering the progress of the search for valid solutions. In this paper, special crossover and mutation operations are defined, such that the members of the population always remain valid solutions of the problem. Excellent results were obtained in a few generations, even for very large networks with 400 nodes. The results were compared with recently reported neural network and mean field annealing approaches.     

A tabu search algorithm for routing optimization in mobile ad-hoc networks

In this paper, we propose a routing optimization algorithm to efficiently determine an optimal path from a source to a destination in mobile ad-hoc networks. To determine an optimal path for the nodes is important for transmitting data between nodes in densely deployed networks. In order to efficiently transmit data to its destination, the appropriate routing algorithms must be implemented in mobile ad-hoc networks. The proposed algorithm is designed by using a tabu search mechanism that is a representative meta-heuristic algorithm. The proposed tabu search algorithm carries out two neighborhood generating operations in order to determine an optimal path and minimize algorithm execution time. We compare the proposed tabu search algorithm with other meta-heuristic algorithms, which are the genetic algorithm and the simulated annealing, in terms of the routing cost and algorithm execution time. The comparison results show that the proposed tabu search algorithm outperforms the other algorithms and that it is suitable for adapting the routing optimization problem.     

Channel assignment in cellular radio networks

The authors investigate algorithms based on simulated annealing to solve the channel assignment problem for cellular radio networks. The blocking probability of a network is chosen as the optimization criterion. In order to check the quality of the solutions obtained by simulated annealing, they examine some special types of networks which allow an effective calculation of optimal solutions by tailored algorithms. Their investigations show that simulated annealing is a very powerful tool for solving channel assignment problems     

Meta‐heuristic algorithms for channel scheduling problem in wireless sensor networks

The channel scheduling problem is to decide how to commit channels for transmitting data between nodes in wireless networks. This problem is one of the most important problems in wireless sensor networks. In this problem, we aim to obtain a near‐optimal solution with the minimal energy consumption within a reasonable time. As the number of nodes increases in the network, however, the amount of calculation for finding the solution would be too high. It can be difficult to obtain an optimal solution in a reasonable execution time because this problem is NP‐hard. Therefore, most of the recent studies for such problems seem to focus on heuristic algorithms. In this paper, we propose efficient channel scheduling algorithms to obtain a near‐optimal solution on the basis of three meta‐heuristic algorithms; the genetic algorithm, the Tabu search, and the simulated annealing. In order to make a search more efficient, we propose some neighborhood generating methods for the proposed algorithms. We evaluate the performance of the proposed algorithms through some experiments in terms of energy consumption and algorithm execution time. The experimental results show that the proposed algorithms are efficient for solving the channel scheduling problem in wireless sensor networks. Copyright © 2011 John Wiley & Sons, Ltd.     

Symbolic Vector Dynamics Approach to Initial Condition and Control Parameters Estimation of Coupled Map Lattices

In this paper, we extend symbolic dynamics, a standard analytical method for 1-D chaotic map, and initiate a solution to the problem of estimation in coupled map lattices (CMLs) by introducing the symbolic vector dynamics. We develop a novel technique for estimating initial conditions. We also expand the applicable scope of a word-lifting technique for parameter estimation from a 1-D chaotic map to CMLs. Both theoretical and experimental results show that those algorithms can construct one-to-one correspondence between the set of global orbits and the set of admissible codes. Therefore, we provide novel analytical techniques for understanding turbulences in CMLs.     

A channel allocation for cellular mobile radio systems using simulated annealing

We consider the channel allocation problem, which is one of the most interesting problems in mobile radio systems. This problem is known to be NP‐complete and a couple of heuristic algorithms have been developed. In this paper, we convert the problem into a simpler form through the concept of pattern, a set of cochannel cells. We suggest another algorithm based on simulated annealing for this simplified problem. The algorithm is applied into different benchmark problems that have appeared in the literature. The presented examples illustrate that our method works very well. Computational results using our formulation and simulated annealing algorithm are reported. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the use of simulated annealing to automatically assign decorrelated components in second-order blind source separation

In this paper, an automatic assignment tool, called BSS-AutoAssign,for artifact-related decorrelated components within a second-order blind source separation (BSS) is presented. The latter is based on the recently proposed algorithm dAMUSE, which provides an elegant solution to both the BSS and the denoising problem simultaneously. BSS-AutoAssign uses a local principal component analysis (PCA)to approximate the artifact signal and defines a suitable cost function which is optimized using simulated annealing. The algorithms dAMUSE plus BSS-AutoAssign are illustrated by applying them to the separation of water artifacts from two-dimensional nuclear overhauser enhancement (2-D NOESY)spectroscopy signals of proteins dissolved in water.     

Hierarchical 3-D Floorplanning Algorithm for Wirelength Optimization

Three-dimensional (3-D) IC physical design problems are usually of higher complexity, with a greatly enlarged solution space due to multiple device structure. In this paper, a new 3-D floorplanning algorithm is proposed for wirelength optimization. Our main contributions and results can be summarized as follows. First, a new hierarchical flow of 3-D floorplanning with a new inter-layer partitioning method. The blocks are partitioned into different layers before floorplanning. A simulated annealing (SA) engine is used to partition blocks with the objective of minimizing the statistical wirelength estimation results. The solution quality is not degraded by the hierarchical flow. Second, floorplans of all the layers are generated in a SA process. Original 3-D floorplanning problem is transformed into solving several 2-D floorplanning problems simultaneously. The solution space is scaled down to maintain a low design complexity. Finally, Experimental results show that our algorithm improves wirelength by 14%-51% compared with previous 3-D floorplanning algorithms. The hierarchical approach is proven to be very efficient and offers a potential way for high-performance 3-D design     

On the feasibility of impulse reflection response data for thetwo-dimensional inverse scattering problem

Layer stripping algorithms for inverse scattering problems are very fast but have the reputation of being numerically unstable, especially when applied to noisy data. The goal of this paper is to provide an explicitly discrete framework for layer stripping algorithms for the two-dimensional (2-D) Schrodinger equation inverse scattering problem. We determine when 2-D layer stripping algorithms are numerically stable, explain why they are stable, and specify exactly the (discrete) problem they solve when they are stable. We reformulate the 2-D Schrodinger equation as a multichannel two-component wave system by Fourier transforming the Schrodinger equation in the lateral spatial variable. Discretization results in new 2-D layer stripping algorithms which incorporate multichannel transmission effects; this leads to an important new feasibility condition on impulse reflection response data for stability of these algorithms. A 2-D discrete Schrodinger equation is defined, and analogous results are obtained. Numerical examples illustrate the new results, especially how rendering noisy data feasible stabilizes layer stripping algorithms     

Exact rebinning methods for three-dimensional PET

The high computational cost of data processing in volume PET imaging is still hindering the routine application of this successful technique, especially in the case of dynamic studies. This paper describes two new algorithms based on an exact rebinning equation, which can be applied to accelerate the processing of three-dimensional (3-D) PET data. The first algorithm, FOREPROJ, is a fast-forward projection algorithm that allows calculation of the 3-D attenuation correction factors (ACF's) directly from a two-dimensional (2-D) transmission scan, without first reconstructing the attenuation map and then performing a 3-D forward projection. The use of FOREPROJ speeds up the estimation of the 3-D ACF's by more than a factor five. The second algorithm, FOREX, is a rebinning algorithm that is also more than five times faster, compared to the standard reprojection algorithm (3DRP) and does not suffer from the image distortions generated by the even faster approximate Fourier rebinning (FORE) method at large axial apertures. However, FOREX is probably not required by most existing scanners, as the axial apertures are not large enough to show improvements over FORE with clinical data. Both algorithms have been implemented and applied to data simulated for a scanner with a large axial aperture (30 degrees), and also to data acquired with the ECAT HR and the ECAT HR+ scanners. Results demonstrate the excellent accuracy achieved by these algorithms and the important speedup when the sinogram sizes are powers of two.     

A new strategy for the application of genetic algorithms to thechannel-assignment problem

The channel-assignment problem in cellular radio networks is known to belong to the class of NP-complete optimization problems. So far, this problem has been solved by heuristic assignment strategies or by the application of combinatorial optimization tools like simulated annealing or neural networks. We propose a new powerful approach to the channel-assignment problem by combining the two mentioned groups of solution techniques. The results obtained by the application to a well-known benchmark problem reveal that this absolutely new strategy clearly outperforms the already existing algorithms     

Interior-point methodology for 3-D PET reconstruction

Interior-point methods have been successfully applied to a wide variety of linear and nonlinear programming applications. This paper presents a class of algorithms, based on path-following interior-point methodology, for performing regularized maximum-likelihood (ML) reconstructions on three-dimensional (3-D) emission tomography data. The algorithms solve a sequence of subproblems that converge to the regularized maximum likelihood solution from the interior of the feasible region (the nonnegative orthant). We propose two methods, a primal method which updates only the primal image variables and a primal-dual method which simultaneously updates the primal variables and the Lagrange multipliers. A parallel implementation permits the interior-point methods to scale to very large reconstruction problems. Termination is based on well-defined convergence measures, namely, the Karush-Kuhn-Tucker first-order necessary conditions for optimality. We demonstrate the rapid convergence of the path-following interior-point methods using both data from a small animal scanner and Monte Carlo simulated data. The proposed methods can readily be applied to solve the regularized, weighted least squares reconstruction problem.     

Underwater imaging with a moving acoustic lens

The acoustic lens is a high-resolution, forward-looking sonar for three dimensional (3-D) underwater imaging. We discuss processing the lens data for recreating and visualizing the scene. Acoustical imaging, compared to optical imaging, is sparse and low resolution. To achieve higher resolution, we obtain a denser sample by mounting the lens on a moving platform and passing over the scene. This introduces the problem of data fusion from multiple overlapping views for scene formation, which we discuss. We also discuss the improvements in object reconstruction by combining data from several passes over an object. We present algorithms for pass registration and show that this process can be done with enough accuracy to improve the image and provide greater detail about the object. The results of in-water experiments show the degree to which size and shape can be obtained under (nearly) ideal conditions.     

Simulated Annealing Mechanic Based Noncoherent Signal Detection for Ultra-wideband Sensor Networks

Ultra-wideband (UWB) sensors have extensive commercial and military applications. Unfortunately, coherent signal detection in the presence of intensive multipath propagations may generally become impractical due to complicated realization algorithms and hardware requirements. In this article, we deal with noncoherent UWB signal detection within a promising biological framework, which can also be generalized to the binary-hypothesis target-detection problem, i.e. identification of the presence or absence of a target. Through the developed characteristic representations, signal detection is firstly formulated as a two-group pattern (or target) classification problem in a 2-D feature plane, in which an optimal decision bound can be numerically derived given the supervised training instances. This optimization problem is addressed by using the nature-inspired simulated annealing algorithm (SA), which essentially emulates the physical annealing process of forming the freeze state with the minimum energy. In sharp contrast to traditional optimization techniques, by probabilistically permitting search movement towards worse solutions, SA algorithm can converge to the global optimal with an asymptotical probability of 1. The numerically derived detection performance demonstrated that our present technique is much superior to the existing noncoherent schemes, which provides the appealing signal/target detection architecture for the emerging UWB sensor networks.     

遗传模拟退火算法在玻璃和晶体色散方程参量反演中的应用

根据已测K9玻璃和晶体(ZnS,MgF2,Calcite)的实验数据,将遗传模拟退火算法应用于修正的Sellimeier方程的参数反演中,建立了上述材料的色散方程。同时比较了遗传模拟退火算法和遗传算法(包括标准遗传算法和多种群遗传算法)在迭代搜索性能方面的差异。结果表明:遗传模拟退火算法的优化效果最优并且性能最稳定。同时,将通过遗传模拟退火算法所得K9玻璃和晶体在某一光谱区域的色散方程应用于其他光谱区域中,发现色散方程的拟合值与实验值符合较好,这表明通过该方法所得色散方程具有较好的外推性。因此,通过遗传模拟退火算法进行色散方程的参量反演方法可以用于其他材料色散方程的拟合。