Surrogate models are commonly employed to reduce computational expenses when dealing with expensive objective optimization problems. This paper introduces a hybrid approach that combines the global exploration capabilities of the Covariance Matrix Adaption Evolution Strategy (CMA-ES) algorithm with the localized search strategy of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method, incorporating a new non-parametric surrogate model derived from the computational geometry structure of a convex hull in multiple dimensions. After running CMA-ES for some time, the populations of the two most recent iterations are collected to construct the convex approximation of the actual problem landscape. Since the population tends to converge in a landscape basin, the local landscape can be simulated using the constructed convex surrogate model. The accuracy of the convex surrogate model is subsequently validated by the historical solutions and used to determine the probability of switching to a local search. Given BFGS's superior performance in handling unimodal optimization problems, this hybrid approach demonstrates its potential to accelerate the convergence process in finding the global optimum. The experiment is conducted on test functions of the BBOB benchmark with a small evaluation budget, and the results after applying Mann-Whitney U tests confirm the superiority of this method compared to CMA-ES and another global-local framework APrMF.

Restart strategy helps the covariance matrix adaptation evolution strategy (CMA-ES) to increase the probability of finding the global optimum in optimization, while a single run CMA-ES is easy to be trapped in local optima. In this paper, the continuous non-revisiting genetic algorithm (cNrGA) is used to help CMA-ES to achieve multiple restarts from different sub-regions of the search space. The CMA-ES with on-line search history-assisted restart strategy (HR-CMA-ES) is proposed. The entire on-line search history of cNrGA is stored in a binary space partitioning (BSP) tree, which is effective for performing local search. The frequently sampled sub-region is reflected by a deep position in the BSP tree. When leaf nodes are located deeper than a threshold, the corresponding sub-region is considered a region of interest (ROI). In HR-CMA-ES, cNrGA is responsible for global exploration and suggesting ROI for CMA-ES to perform an exploitation within or around the ROI. CMA-ES restarts independently in each suggested ROI. The non-revisiting mechanism of cNrGA avoids to suggest the same ROI for a second time. Experimental results on the CEC 2013 and 2017 benchmark suites show that HR-CMA-ES performs better than both CMA-ES and cNrGA. A positive synergy is observed by the memetic cooperation of the two algorithms.

To solve economic load dispatch problems, this paper designs a combination of artificial bee colony (ABC) and covariance matrix adaptation evolution strategy (CMA-ES). In this method, multiple variables are updated at the employed bee stage. The onlooker bee stage of the ABC method is replaced by the CMA-ES method. To begin with a good position, the CMA-ES method is initialized based on the state of employed bees of the ABC method. The proposed method is used to solve economic load dispatch problem with different sizes, and compared with three other methods. Simulation results show that the method attains better performance by combining ABC and CMA-ES. Moreover, the sensitivity of parameter settings is also discussed, and a default setting is obtained for such problems.

The continuous Non-revisiting Genetic Algorithm (cNrGA) uses the entire search history and parameter-less adaptive mutation to significantly enhance search performance. Experimental results show that it has better performance than Covariance Matrix Adaptation Evolution Strategy (CMA-ES), a state of the art evolutionary algorithm. Storing the search history is natural and costs little when fitness evaluations are expensive. However, if the number of evaluations required is substantial, some memory management is desirable. In this paper, we propose two pruning mechanisms to keep the memory used constant. They are Random pruning and Least Recently Used pruning. The idea is to prune a node when a memory threshold is reached and a new node is required to be inserted, thus keeping the overall memory used constant. Experimental results show that both strategies can maintain the performance of cNrGA, up to the limit when 90% of the nodes are not recorded. This suggests that cNrGA can be extended to use in situations when the number of fitness evaluations are much larger than before with no significant effect on statistical performance, which widens the applicability of cNrGA to include more practical problems that require larger number of fitness evaluations before converging to the global optimum.

Evolutionary algorithms are typically run several times in design optimization problems and the best solution taken. We propose a novel online algorithm selection framework that learns to use the best algorithm based on previous runs, hence in effect using different and better algorithms as the search progresses. First, a set of algorithms are run on a benchmark problem suite. Given a new problem, a default algorithm is run and its convergence characteristics are recorded. This is used to map to the problem database to find the most similar problem. In turn, the database returns the best algorithm for this problem and this algorithm is run in the second iteration and so on, aiming to home onto the most suitable algorithm for the problem. The resulting algorithm, named Sequential Learnable Evolutionary algorithm (SLEA), outperforms Covariance Matrix Adaptation Evolution Strategy (CMA-ES) with multi-restarts. SLEA is also applied to a new problem, a real world application, and learns its characteristics. Experimental results show that it can correctly select the best algorithm for the problem. Finally, this paper proposes a new research program which learns the algorithm-problem mapping through solving real world problems accessed through the web and worldwide cooperation through Wikipedia.

Dynamic objective problem (DOP) raises two challenging issues to evolutionary algorithm: comparing two individuals evaluated at different time instances and tracing the jumping global optimum. This paper presents a dynamic objective evolutionary algorithm (DOEA) that handles these issues through search history. The presented algorithm, namely dynamic objective history driven evolutionary algorithm (DyHdEA), stores the entire search history including the position, the fitness and the evaluated time of the solutions in a dynamic fitness tree. In the experiment section, DyHdEA is examined on a 10-dimensional DOP that is composed of five basis problems ranging from uni-modal to multi-modal, and from separable to non-separable. Meanwhile, the performance of DyHdEA is compared with five benchmark DOEAs including artificial immune algorithm, differential evolution, evolutionary programming, and particle swarm optimization. Seen from the result, DyHdEA effectively traces the dynamic global optimum with jumping transitions.

The concept of algorithm portfolio has a long history. Recently this concept draws increasing attention from researchers, though most of the researches have concentrated on single objective optimization problems. This paper is intended to solve multiobjective optimization problems by proposing a multiple evolutionary algorithm portfolio. Differing from previous approaches, each component algorithm in our portfolio method has an independent population and the component algorithms do not communicate in any way with each other. Another difference is that our algorithm introduces no control parameters. This parameter-less characteristic is desirable as each additional parameter requires independent parameter tuning or control. A novel score calculation method, based on predicted performance, is used to assess the contributions of component algorithms during the optimization process. Such information is used by an algorithm selector which decides, for each generation, which algorithm to use. Experimental results show that our portfolio method outperforms individual algorithms in the portfolio. Moreover, it outperforms the AMALGAM method.

Many good evolutionary algorithms have been proposed in the past. However, frequently, the question arises that given a problem, one is at a loss of which algorithm to choose. In this paper, we propose a novel algorithm portfolio approach to address the above problem. A portfolio of evolutionary algorithms is first formed. Artificial Bee Colony (ABC), Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES), Composite DE (CoDE), Particle Swarm Optimization (PSO2011) and Self adaptive Differential Evolution (SaDE) are chosen as component algorithms. Each algorithm runs independently with no information exchange. At any point in time, the algorithm with the best predicted performance is run for one generation, after which the performance is predicted again. The best algorithm runs for the next generation, and the process goes on. In this way, algorithms switch automatically as a function of the computational budget. This novel algorithm is named Multiple Evolutionary Algorithm (MultiEA). Experimental results on the full set of 25 CEC2005 benchmark functions show that MultiEA outperforms i) Multialgorithm Genetically Adaptive Method for Single Objective Optimization (AMALGAM-SO); ii) Population-based Algorithm Portfolio (PAP); and iii) a multiple algorithm approach which chooses an algorithm randomly (RandEA). The properties of the prediction measures are also studied. The portfolio approach proposed is generic. It can be applied to portfolios composed of non-evolutionary algorithms as well.

In continuous non-revisiting genetic algorithm (cNrGA), search space is partitioned into sub-regions according to the distribution of evaluated solutions. The partitioned subregion serves as mutation range such that the corresponding mutation is adaptive and parameter-less. As pointed out by Chow and Yuen, the boundary condition of the mutation in cNrGA is too restricted that the exploitative power of cNrGA is reduced. In this paper, we tackle this structural problem of cNrGA by a new formulation of mutation range. When sub-region is formulated as which certain overlap exists between adjacent sub-regions, this creates a soft boundary and it allows individual move from a sub-region to another with better fitness. This modified cNrGA is named cNrGA with overlapped search sub-region (cNrGA/OL/OGF). By comparing with another work on this problem, Continuous non-revisiting genetic algorithm with randomly re-partitioned BSP tree (cNrGA/RP/OGF), it has an advantage on processing speed. The proposed algorithm is examined on 34 benchmark functions at dimensions ranging from 2 to 40. The results show that the proposed algorithm is superior to the original cNrGA, cNrGA/RP/OGF and covariance matrix adaptation evolutionary strategy (CMA-ES).

Multiobjective evolutionary algorithms (MOEAs) often have several control parameters, and their performance is highly related to the parameters. A proper set of parameter values is useful for MOEAs in a particular application. This paper addresses the parameter control problem. Inspired by the observations in differential evolution (DE), we proposed a parameter control system using opposition-based learning (OBL). The proposed method contains three conditions which characterize the state of parameters at different evolutionary stages. It keeps good parameters for the current search stage. In case the parameters are bad, it uses OBL to accelerate the finding of good ones. The method is applied to a newly proposed multiobjective DE algorithm (MODEA) which does not control parameters. The resulting algorithm is tested on CEC 2009 test suite comparing with two other recently proposed MOEAs, namely GDE3 and MOEA/D. Experimental results show that the proposed method can significantly improve the performance of MODEA. Moreover, the resulting algorithm significantly outperforms GDE3 and MOEA/D.

Differential evolution (DE) is a simple and efficient evolutionary algorithm. It contains three parameters which need to be predefined by users. These parameters are sensitive to specific problems and difficult to set. Opposition-based computing (OBC) is a new scheme for computational intelligence. OBC is helpful to existing techniques by making better decisions through simultaneous consideration of entities and opposite entities. The opposition phenomenon exists in the literature concerning parameter control of DE. In this paper, OBC is employed to assist with the solving of parameter control problem in DE. Employing OBC to parameter control problem in DE has not been reported previously to our knowledge. The proposed approach is called opposition-based adaptive DE (OADE). It uses two pools to respectively store parameters and opposite parameters. The parameters and their opposites are used at the same time to generate trial vectors in DE. During the evolutionary process, fitness improvement at a generation serves as a filter to detect proper parameters for optimization problems. The detected proper parameters and their opposites are stored in pools, whereas the improper parameters and their opposites are replaced by new randomly generated ones. The utilization of parameters and their opposites can balance the exploration and exploitation behavior of DE in one generation. The performance of OADE is compared with three other DE algorithms. The experimental results show that OADE significantly outperforms the benchmark algorithms. Moreover, OADE is not sensitive to the pool size.

Most existing multiobjective evolutionary algorithms (MOEAs) assume the existence of Pareto-optimal solutions/Pareto-optimal objective vectors in a neighborhood of an obtained Pareto-optimal set (PS)/Pareto-optimal front (PF). Obviously, this assumption does not work well on the multiobjective problem (MOP) whose true PF and true PS are in the form of multiple segments-truly disconnected MOP (TYD-MOP). Moreover, these MOEAs commonly involve more than three control parameters; and some of them even involve nine control parameters. The stabilities of their performance against parameter settings are generally unknown. In this paper, we propose a MOEA, namely multiobjective density driven evolutionary algorithm (MODdEA), which can handle TYD-MOP. MODdEA stores all evaluated solutions by a binary space partitioning (BSP) tree. Benefiting from the BSP scheme, a fast solution density estimation by the archive is naturally obtained. MODdEA uses this estimated density together with the nondominated rank to probabilistically select mating individuals, which relaxes the neighborhood assumption on PF in a parameter-less manner. Moreover, two genetic operators, extended arithmetic crossover and diversified mutation, are proposed to enhance the explorative search ability of the algorithm. MODdEA is examined on two test problem sets. The first test set consists of six TYD-MOPs; the second test set consists of 17 benchmark MOPs which are commonly examined by the existing MOEAs. Comparing to 14 test MOEAs, MODdEA has superior performance on TYD-MOP and is competitive on MOP whose true PF and PS are one single connected segment.

This paper considers the scenario of the (1+1) evolutionary algorithm (EA) and randomized local search (RLS) with memory. Previously explored solutions are stored in memory until an improvement in fitness is obtained; then the stored information is discarded. This results in two new algorithms: (1+1) EA-m (with a raw list and hash table option) and RLS-m+ (and RLS-m if the function is a priori known to be unimodal). These two algorithms can be regarded as very simple forms of tabu search. Rigorous theoretical analysis of the expected time to find the globally optimal solutions for these algorithms is conducted for both unimodal and multimodal functions. A unified mathematical framework, involving the new concept of spatially invariant neighborhood, is proposed. Under this framework, both (1+1) EA with standard uniform mutation and RLS can be considered as particular instances and in the most general cases, all functions can be considered to be unimodal. Under this framework, it is found that for unimodal functions, the improvement by memory assistance is always positive but at most by one half. For multimodal functions, the improvement is significant; for functions with gaps and another hard function, the order of growth is reduced; for at least one example function, the order can change from exponential to polynomial. Empirical results, with a reasonable fitness evaluation time assumption, verify that (1+1) EA-m and RLS-m+ are superior to their conventional counterparts. Both new algorithms are promising for use in a memetic algorithm. In particular, RLS-m+ makes the previously impractical RLS practical, and surprisingly, does not require any extra memory in actual implementation.

In this paper, we report a novel evolutionary algorithm that enhances its performance by utilizing the entire previous search history. The proposed algorithm, namely history driven evolutionary algorithm (HdEA), employs a binary space partitioning tree structure to memorize the positions and the fitness values of the evaluated solutions. Benefiting from the space partitioning scheme, a fast fitness function approximation using the archive is obtained. The approximation is used to improve the mutation strategy in HdEA. The resultant mutation operator is parameter-less, anisotropic, and adaptive. Moreover, the mutation operator naturally avoids the generation of out-of-bound solutions. The performance of HdEA is tested on 34 benchmark functions with dimensions ranging from 2 to 40. We also provide a performance comparison of HdEA with eight benchmark evolutionary algorithms, including a real coded genetic algorithm, differential evolution, two improved differential evolution, covariance matrix adaptation evolution strategy, two improved particle swarm optimization, and an estimation of distribution algorithm. Seen from the experimental results, HdEA outperforms the other algorithms for multimodal function optimization.

In continuous non-revisiting genetic algorithm (cNrGA), the solution set with different order leads to different density estimation and hence different mutation step size. As a result, the performance of cNrGA depends on the order of the evaluated solutions. In this paper, we propose to remove this dependence by a search space re-partitioning strategy. At each iteration, the strategy re-shuffles the solutions into random order. The re-ordered sequence is then used to construct a new density tree, which leads to a new space partition sets. Afterwards, instead of randomly picking a mutant within a partition, a new adaptive one-gene-flip mutation is applied. Motivated from the fact that the proposed adaptive mutation concerns only small amount of partitions, we propose a new density tree construction algorithm. This algorithm refuses to partition the sub-regions which do not contain any individual to be mutated, which simplifies the tree topology as well as speeds up the construction time. The new cNrGA integrated with the proposed re-partitioning strategy (cNrGA/RP/OGF) is examined on 19 benchmark functions at dimensions ranging from 2 to 40. The simulation results show that cNrGA/RP/OGF is significantly superior to the original cNrGA at most of the test functions. Its average performance is also better than those of six benchmark EAs.

History-driven Evolutionary Algorithm (HdEA) is an EA that uses the entire search history to improve searching performance. By building the approximated fitness landscape and estimating the gradient using the entire history, HdEA performs a parameter-less adaptive mutation. In order to decrease the number of parameters that makes the HdEA more robust, this paper proposes a novel adaptive parameter control system. This system is as an add-on component to HdEA, which uses the whole search history in HdEA to control the parameters in an automatic manner. The performance of the proposed system is examined on 34 benchmark functions. The results shows that the parameter control system gives similar or better performance in 24 functions and has the benefit that two parameters of the HdEA are eliminated; they are set and varied automatically by the system.

The non-revisiting genetic algorithm (NrGA) is extended to handle continuous search space. The extended NrGA model, Continuous NrGA (cNrGA), employs the same tree-structure archive of NrGA to memorize the evaluated solutions, in which the search space is divided into non-overlapped partitions according to the distribution of the solutions. cNrGA is a bi-modulus evolutionary algorithm consisting of the genetic algorithm module (GAM) and the adaptive mutation module (AMM). When GAM generates an offspring, the offspring is sent to AMM and is mutated according to the density of the solutions stored in the memory archive. For a point in the search space with high solution-density, it infers a high probability that the point is close to the optimum and hence a near search is suggested. Alternatively, a far search is recommended for a point with low solution-density. Benefitting from the space partitioning scheme, a fast solution-density approximation is obtained. Also, the adaptive mutation scheme naturally avoid the generation of out-of-bound solutions. The performance of cNrGA is tested on 14 benchmark functions on dimensions ranging from 2 to 40. It is compared with real coded GA, differential evolution, covariance matrix adaptation evolution strategy and two improved particle swarm optimization. The simulation results show that cNrGA outperforms the other algorithms for multi-modal function optimization.

We study empirically the effects of operator and parameter choices on the performance of the non-revisiting genetic algorithm (NrGA). For a suite of 14 benchmark functions that include both uni-modal and multi-modal functions, it is found that NrGA is insensitive to the axis resolution of the problem, which is a good feature. From the empirical experiments, for operators, it is found that crossover is an essential operator for NrGA, and the best crossover operator is uniform crossover, while the best selection operator is elitist selection. For parameters, a small population, with a population size strictly larger than 1, should be used; the performance is monotonically increasing with crossover rate and the optimal crossover rate is 0.5. The results of this paper provide empirical guidelines for operator designs and parameter settings of NrGA.

Conventional genetic programming (GP) does not guarantee no revisits, i.e., a program may be generated for fitness evaluations more than one time. This is clearly wasteful in applications that involve expensive and/or time consuming fitness evaluations. This paper proposes a new GP - non-revisiting genetic programming NrGP - that guarantees that all programs generated is original. The basic idea is to use memory to store all programs generated. To increase efficiency in indexing and storage, the memory is organized as an S-expression trie. Since the number of solutions generated is modest for applications involving expensive and/or time consuming fitness evaluations, the extra memory needed is manageable. GP and NrGP are compared using two GP bench mark problems, namely, the symbolic regression and the even N-parity problem. It is found that NrGP outperforms GP, significantly reducing the computational effort (CE) required. This clearly shows the power of the idea of ensuring no revisits. It is anticipated that the same non-revisiting idea can be applied to other types of GP to enhance their efficiency. A new CE measurement is also reported that removes some statistical biases associated with the conventional CE.

A novel genetic algorithm is reported that is non-revisiting: It remembers every position that it has searched before. An archive is used to store all the solutions that have been explored before. Different from other memory schemes in the literature, a novel binary space partitioning tree archive design is advocated. Not only is the design an efficient method to check for revisits, if any, it in itself constitutes a novel adaptive mutation operator that has no parameter. To demonstrate the power of the method, the algorithm is evaluated using 19 famous benchmark functions. The results are as follows. (1) Though it only uses finite resolution grids, when compared with a canonical genetic algorithm, a generic real-coded genetic algorithm, a canonical genetic algorithm with simple diversity mechanism, and three particle swarm optimization algorithms, it shows a significant improvement. (2) The new algorithm also shows superior performance compared to covariance matrix adaptation evolution strategy (CMA-ES), a state-of-the-art method for adaptive mutation. (3) It can work with problems that have large search spaces with dimensions as high as 40. (4) The corresponding CPU overhead of the binary space partitioning tree design is insignificant for applications with expensive or time-consuming fitness evaluations, and for such applications, the memory usage due to the archive is acceptable. (5) Though the adaptive mutation is parameter-less, it shows and maintains a stable good performance. However, for other algorithms we compare, the performance is highly dependent on suitable parameter settings.

In this article, a non-revisiting particle swarm optimization (NrPSO) is proposed NrPSO is an integration of the non-revisiting scheme and a standard particle swarm optimization (PSO). It guarantees that all updated positions are not evaluated before. This property leads to two advantages: 1) it undisputedly reduces the computation cost on evaluating a time consuming and expensive objective function and 2) It helps prevent premature convergence. The non-revisiting scheme acts as a self-adaptive mutation. Particles genericly switch between local search and global search. In addition, since the adaptive mutation scheme of NrPSO involves no parameter, comparing with other variants of PSO which involve at least two performance sensitive parameters, the performance of NrPSO is more reliable. The simulation results show that NrPSO outperforms four variants of PSOs on optimizing both uni-modal and multi-modal functions with dimensions up to 40. We also illustrate that the overhead and archive size of NrPSO are insignificant. Thus NrPSO is practical for real world applications. In addition, it is shown that the performance of NrPSO is insensitive to the specific chosen values of parameters.

Given any randomized search algorithm, we can avoid re-evaluating the fitness of previously visited points by storing the information in memory. This idea is applied to the (1+1) Evolutionary Algorithm with standard mutation and the Randomized Local Search (RLS) algorithm. Our analysis shows that a large reduction in running time can be obtained if we store recently visited points and execute those algorithms on some pseudo-boolean functions. Besides, the stored information can also be used to affect the generation of new search points. We illustrate this idea by designing an algorithm called Progressive Randomized Local Search. In contrary to RLS, it is capable of escaping from local maxima.

In this article, a non-revisiting simulated annealing algorithm (NrSA) is proposed. NrSA is an integration of the non-revisiting scheme and standard simulated annealing (SA). It guarantees that every generated neighbor must not be visited before. This property leads to reduction on the computation cost on evaluating time consuming and expensive objective functions such as surface registration, optimized design and energy management of heating, ventilating and air conditioning systems. Meanwhile, the prevention on function re-evaluation also speeds up the convergence. Furthermore, due to the nature of the non-revisiting scheme, the returned non-revisited solutions from the scheme can be treated as self-adaptive solutions, such that no parametric neighbor picking scheme is involved in NrSA. Thus NrSA can be identified as a parameter-less SA. The simulation results show that NrSA is superior to adaptive SA (ASA) on both uni-modal and multi-modal functions with dimension up to 40. We also illustrate that the overhead and archive size of NrSA are insignificant, so it is practical for real world applications.

In [1], we propose non-revisiting genetic algorithm (NrGA) and apply it to a set of bench mark real valued test functions. NrGA has the advantage that it is non-revisiting, i.e. a visited point will not be visited again. This provides an automatic mechanism for diversity maintenance which does not suffer from premature convergence. Another advantage is that it supports a parameter-less adaptive mutation mechanism In this paper, we show how NrGA can be adapted to a real world combinatorial optimization problem - the famous traveling salesman problem (TSP). Comparison with genetic algorithm (GA) (with revisits and standard mutation) is made. It is shown that NrGA gives superior performance compared to GA. Moreover, it gives the same stable performance using different types of mutation operators. Moreover, turning off GA’s mutation operator but only use the NrGA inherent parameter-less adaptive mutation gives the best performance.

Genetic Algorithm (GA) is a revisiting stochastic algorithm. In other words, a solution that has been visited before may be revisited. The fitness of the solution has to be evaluated each time. Since fitness evaluation is the most computationally intensive process in the execution of the GA, revisits should be minimized or eliminated. In this paper, a novel dynamic binary partitioning tree archive is proposed to eliminate all revisits. It works as follows: When the GA generates a solution, the tree is accessed. A leaf node is appended to the tree if the solution has not been visited before and so has no record in the tree. Otherwise, a search is initiated from the leaf node that is the duplicate to the solution to find the nearest neighbor solution in the search space that is not visited. During this process, whole sub-trees may be pruned if all the leaf nodes it contains are visited. The search naturally implements a self adaptive mutation mechanism. Hence the GA requires no other mutation parameter or mutation scheme. Experimental results reveal that this new GA is superior in performance compared with the standard GA with revisits, and the tree archive is not memory intensive.

In augmented reality (AR), the lighting direction plays an important role to the quality of the augmented scene. The corresponding lighting direction estimation is a challenging problem as it depends on an extra unknown variable -reflectance of the material. In this article, we propose to estimate the lighting direction by a neural network (NN) which is trained by a sample set. Since the empirical reflectance of a captured scene is in form of scattered points, we unify the representation of reflectance as a two dimensional polynomials. Moreover, a novel neural network model is presented to construct the mapping from reflectance to lighting direction. Contrary to the existing NNs, the proposed model accepts surface input pattern in which the drawbacks of feature vector are overcome. Experimental results of 2000 lighting estimations with unknown reflectances are presented to demonstrate the performance of the proposed algorithm.

This article points out the limitations of vectoral input pattern on density estimation and Bayesian classification. A continuous Bayesian classifier is proposed to tackle these limitations. The classifier accepts signal as input pattern; thus the problem of optimal description length selection is avoided. The algorithm is evaluated on signal clustering and distribution classification.

The self organizing map (SOM) has been applied to wide ranges of fields including computer vision and image processing. Despite of its simple training algorithm, the vectorial input pattern of SOMs induced a sequence of drawbacks which should not be overlooked. These drawbacks include optimal description length selection problem and inaccurate clustering of scattered point patterns. In this article, an extension of SOM to continuous domain, namely signal SOM (SSOM), is proposed to tackle the drawbacks caused by the vectorial input pattern SOMs. Remarkably, it provides an analytical model expression and involves no model selection problem. The SSOM is evaluated by a simulation about clustering of three signal groups. By comparing with the conventional SOM, a more structural map in term of signal group distribution is obtained by the SSOM. Thus, it indicate the contribution of this article on extending the ability of SOM.

Genetic algorithms have proven to be reasonably good optimization algorithms. Despite many successful applications, there is a lack of theoretical insight into why they work so well. In this paper, Vose-Liepins' so called "infinite population model" is used to derive a lower and upper bound for the expected probability of the global optimal solution under proportional selection and uniform crossover. Elitist selection is not assumed. The approach is to aggregate the Markov chain (MC) into subsets of decreasing Hamming distances. The aggregation is based on a proof of equally likelihood in probability of elements in these subsets. The aggregation model is then extended to Nix-Vose's fully realistic "finite population model." This leads to a lower and upper bound expression based on the first passage theory of the MC for the probability of success of the algorithm. The proof of equally likelihood is extended correspondingly to permutations of populations. Numerical simulations reveal that the bounds are useful for small perturbations of the fitness function for all problem sizes in the infinite population model. Due to the computational burden, however, the aggregated finite population model is still restricted to relatively small problem sizes. Finally, an approximate aggregated finite population model that does not require computation of the full mixing matrix is found to give excellent performance.

The object location problem has been solved using the repeated genetic algorithm by determining the number of independent runs to guarantee a given probability of success. However, this number is still too large for the detection of some noisy images with acceptable certainty. Through an in depth analysis of all the genetic operations and their interrelationships, we design an improved crossover and a dynamic search scheme that integrate the crossover, mutation and selection operations so that the probability of success of correct location in a single run for some test objects is enhanced significantly. As a consequence, only a few repeated runs are required to guarantee a high probability of success in solving this type of real problem.

A Hough-like technique for circular object detection is reported. The proposed technique is simple in implementation, efficient in computation and robust to noise. In general, to evaluate circle parameters for all possible point triplets in an edge image containing n points, /sub n/C3 enumerations of the points have to be examined. However, if specific relations of the circle points are sought, the required number of enumerations can be reduced. In this paper, we propose one such technique with point triplets possessing right angle property and the required enumerations can be reduced to /sub n/C2. In addition, a novel hypothesis processing strategy known as hypothesis filtering is introduced. This includes two novel constraints: consistency checking with gradient angles and neighbouring points validation, which are used to filter non-circular feature point sets possessing right angle property. It is found that the use of hypothesis filtering as a preprocessing step improves significantly the speed of detection. Experimental results demonstrate the effectiveness of the method to detect circles in both synthetic drawings and real images.

A novel parametrization method for the Hough transform is reported. Instead of the conventional non-parametric form, the parametric form is used and copies of the transformed shape are plotted on two dimensional slices of the Hough space. It is shown that the corresponding parametrization has uniform precision with respect to translation, and cancels out the quantization uncertainty due to image digitization. A problem of the Hough transform is discovered which is due to non-uniform discretized voting. It is shown that the above class of parametrizations avoids the problem. Finally, a particular solution of the parametrization scheme is described which is called the Fourier parametrization. It is shown that the parametrization has uniform precision with respect to the affine transformation.