14295071
Sample Complexity of Real-Coded Evolutionary Algorithms
Researchers studying Evolutionary Algorithms and their applications have always been confronted with the sample complexity problem. The relationship between population size and global convergence is not clearly understood. Population size is usually chosen depending on researcher’s experience. In this paper, we study the population size using Probably Approximately Correct (PAC) learning theory. A ruggedness measure for fitness functions is defined. A sampling theorem that theoretically determines an appropriate population size towards effective convergence is proposed. Preliminary experiments show that the initial population of the proposed size provides good starting point(s) for searching the solution space and thus leads to finding global optima.
1221771
Multi-scale feature identification using evolution strategies
An image usually contains a number of different features and regions. Many image-related applications, such as content-based image retrieval and MRI-based diagnosis, often require the ability to identify and mark features within the image. For images containing a specific sort of feature (e.g. convective storm) or region (e.g. earthquake debris), that feature or region is always located adjacent to other features and regions on the image. A generic framework for automatically identifying features in images based on evolutionary computation is proposed here. The significant characteristic of the method is that it does not require segmentation. We use evolution strategies as the optimization algorithm to identify features. The system is based on a conjecture that certain filters will give prominent responses to certain features. The identified features are represented as regions enclosed within the chosen search structure-the ellipse. By defining filter response criteria as the fitness function, evolution strategies succeeds in finding the feature in a much more efficient way than, say, segmentation.
16151894
Low Level Fusion of Imagery Based on Dempster-Shafer Theory
An approach to fuse multiple images based on Dempster-Shafer evidential reasoning is proposed in this article. Dempster-Shafer theory provides a complete framework for combining weak evidences from multiple sources. Such situations typically arise in the image fusion problems, where a ‘real scene’ image has to be estimated from incomplete and unreliable observations. By converting images from their spatial domain into the evidential representations, decisions are made to aggregate evidences such that a fused image is generated. The proposed fusion approach is evaluated on a broad set of images and promising results are given.
38619191
Function Granularity Estimation for Multimodal Optimization
In this article, we study the subspace function granularity and present a method to estimate the sharing distance and the optimal population size. To achieve multimodal function optimization, niching techniques diversify the population of Evolutionary Algorithms (EA) and encourage heterogeneous convergence to multiple optima. The key to a successful diversification is effective resource sharing. Without knowing the fitness landscape, resource sharing is usually determined by uninformative assumptions on the number of peaks. Using the Probably Approximately Correct (PAC) learning theory and the ∊-cover concept, a PAC neighborhood for a set of samples is derived. Within this neighborhood, we sample the fitness landscape and compute the subspace Fitness Distance Correlation (FDC) coefficients. Using the estimated granularity feature of the fitness landscape, the sharing distance and the population size are determined. Experiments demonstrate that by using the estimated population size and sharing distance an Evolutionary Algorithm successfully identifies multiple optima.
27055322
A Fast Evolution Strategies Based Approach To Image Registration
An image registration approach based on Evolution Strategies is proposed. In image registration, an invariant reference needs to be established within each source image, which is unavailable in many cases. To solve this problem, feature configuration (which is defined as the cluster of feature vectors on an image representing homogeneous feature distribution,) is employed to describe the object inside the scene. Instead of finding the correspondence of the entire image, the spatial relationships of the feature configuration in every source image are discovered with Evolution Strategies (ES). While one approach, even this one, may not be suitable for every image domain, the ES approach has many advantages. Compared to some methods, it is computationally effective; compared to other, it is capable of discovering transformations of larger scope (e.g., greater rotation angles or translation distances etc.) The search structure we use is an ellipsoid. The results from various images prove it to be an efficient and effective method.
223678
Automatic classification of digestive organs in wireless capsule endoscopy videos
Wireless Capsule Endoscopy (WCE) allows a physician to examine the entire small intestine without any surgical operation. With the miniaturization of wireless and camera technologies the ability comes to view the entire gestational track with little effort. Although WCE is a technical break-through that allows us to access the entire intestine without surgery, it is reported that a medical clinician spends one or two hours to assess a WCE video, It limits the number of examinations possible, and incur considerable amount of costs. To reduce the assessment time, it is critical to develop a technique to automatically discriminate digestive organs such as esophagus, stomach, small intestinal (i.e., duodenum, jejunum, and ileum) and colon. In this paper, we propose a novel technique to segment a WCE video into these anatomic parts based on color change pattern analysis. The basic idea is that the each digestive organ has different patterns of intestinal contractions that are quantified as the features. We present the experimental results that demonstrate the effectiveness of the proposed method.
14857157
An MPI prototype for compiled communication on Ethernet switched clusters
Compiled communication has recently been proposed to improve communication performance for clusters of workstations. The idea of compiled communication is to apply more aggressive optimizations to communications whose information is known at compile time. Existing MPI libraries do not support compiled communication. In this paper, we present an MPI prototype, CC-MPI, that supports compiled communication on Ethernet switched clusters. The unique feature of CC-MPI is that it allows the user to manage network resources such as multicast groups directly and to optimize communications based on the availability of the communication information. CC-MPI optimizes one-to-all, one-to-many, all-to-all, and many-to-many collective communication routines using the compiled communication technique. We describe the techniques used in CC-MPI and report its performance.The results show that communication performance of Ethernet switched clusters can be significantly improved through compiled communication.
18808395
Stippling and silhouettes rendering in geometry-image space
We present a novel non-photorealistic rendering method that performs all operations in a geometry-image domain. We first apply global conformal parameterization to the input geometry model and generate corresponding geometry images. Strokes and silhouettes are then computed in the geometry-image domain. The geometry-image space provides combined benefits of the existing image space and object space approaches. It allows us to take advantage of the regularity of 2D images and yet still have full access to the object geometry information. A wide range of image processing tools can be leveraged to assist various operations involved in achieving non-photorealistic rendering with coherence.
3570050
Algorithms for Supporting Compiled Communication
We investigate the compiler algorithms to support compiled communication in multiprocessor environments and study the benefits of compiled communication, assuming that the underlying network is an all-optical time-division-multiplexing (TDM) network. We present an experimental compiler, E-SUIF, that supports compiled communication for High Performance Fortran (HPF) like programs on all-optical TDM networks, and describe and evaluate the compiler algorithms used in E-SUIF. We further demonstrate the effectiveness of compiled communication on all-optical TDM networks by comparing the performance of compiled communication with that of a traditional communication method using a number of application programs.
18020602
Automatic validation of code-improving transformations on low-level program representations
This paper presents a general approach for automatically validating code-improving transformations on low-level program representations. The approach ensures the correctness of compiler and hand-specified optimizations at the machine instruction level. The method verifies the semantic equivalence of the program representation before and after a transformation to determine the validity of the transformation. To verify that the transformation is semantics preserving, the method derives semantic effects from the instructions that span the execution paths affected by the transformation. The semantics are preserved if the normalized semantic effects are unchanged. A validating compilation system was implemented that is able to validate traditional compiler transformations and more powerful transformations that modify the branch structure of a program.
33631313
Particle Swarm Optimization with Multiscale Searching Method
This paper presents a new method for effectively searching all global minima of a multimodal function. The method is based on particle swarm optimizer, particles are dynamically divided into serval subgroups of different size in order to explore variable space using various step size simultaneously. In each subgroup, a new scheme is proposed to update the the positions of particles, this scheme takes into consideration the effect of all subgroup seeds. Experimental results for one dimensional, two dimensional and thirty dimensional test suites demonstrated that this method can get overall promising performance over a wide range problems.