A mean field annealing approach to robust corner detection

This paper is an extension of our previous paper to improve the capability of detecting corners. We proposed a method of boundary smoothing for curvature estimation using a constrained regularization technique in the previous paper. We propose another approach to boundary smoothing for curvature estimation in this paper to improve the capability of detecting corners. The method is based on a minimization strategy known as mean field annealing which is a deterministic approximation to simulated annealing. It removes the noise while preserving corners very well. Thus, we can detect corners easier and better in this approach than in the constrained regularization approach. Finally, some matching results based on the corners detected by corner sharpness in the mean field annealing approach are presented as a demonstration of the power of the proposed algorithm.     

Smooth curve extraction by mean field annealing

In this paper, we attack the figure — ground discrimination problem from a combinatorial optimization perspective. In general, the solutions proposed in the past solved this problem only partially: either the mathematical model encoding the figure — ground problem was too simple or the optimization methods that were used were not efficient enough or they could not guarantee to find the global minimum of the cost function describing the figure — ground model. The method that we devised and which is described in this paper is tailored around the following contributions. First, we suggest a mathematical model encoding the figure — ground discrimination problem that makes explicit a definition of shape (or figure) based on cocircularity, smoothness, proximity, and contrast. This model consists of building a cost function on the basis of image element interactions. Moreover, this cost function fits the constraints of aninteracting spin system, which in turn is a well suited physical model to solve hard combinatorial optimization problems. Second, we suggest a combinatorial optimization method for solving the figure — ground problem, namely mean field annealing which combines the mean field approximation and annealing. Mean field annealing may well be viewed as a deterministic approximation of stochastic methods such as simulated annealing. We describe in detail the theoretical bases of this method, derive a computational model, and provide a practical algorithm. Finally, some experimental results are shown for both synthetic and real images.This research has been sponsored in part by Commissariat à l'Energie Atomique, and in part by the ORASIS project (PRC Communications Homme/Machine).     

A mean field annealing approach to accurate free form shape matching

The SoftAssign algorithm is an elegant free form shape matching algorithm. While its objective function can be interpreted as consisting of three desired terms: minimising a weighted sum of matching errors of combinations of all the points in the two free form shapes to be matched, equalising their weights (probabilities) of being real ones and also maximising the overlapping area between the free form shapes to be matched, the last term has no effect on the optimisation of the parameters of interest due to normalisation. In this paper, we reformulate the last two terms using the inequality about the geometric and algebraic averages and the sum of the powers of these probabilities. For the sake of computational efficiency, instead of considering combinations of all the points in the overlapping free form shapes to be matched, we employ the traditional closest point criterion to establish possible correspondences between the two overlapping free form shapes to be matched. The saddle point solution of the resulting objective function no longer yields a closed form solution to the parameters of interest. For easy computation, we then adopt a pseudo-linearisation method to linearise the first order derivative of the objective function, leading the parameters of interest to be tracked and estimated with a closed form solution. The parameters of interest are finally optimised using the efficient deterministic annealing scheme with the camera motion parameters estimated using the quaternion method in the weighted least squares sense. A comparative study based on both synthetic data and real images with partial overlap has shown that the proposed algorithm is promising for the automatic matching of overlapping 3D free form shapes subject to a large range of motions.     

A new method to optimize the satellite broadcasting schedules usingthe mean field annealing of a Hopfield neural network

Reports a new method for optimizing satellite broadcasting schedules based on the Hopfield neural model in combination with the mean field annealing theory. A clamping technique is used with an associative matrix, thus reducing the dimensions of the solution space. A formula for estimating the critical temperature for the mean field annealing procedure is derived, hence enabling the updating of the mean field theory equations to be more economical. Several factors on the numerical implementation of the mean field equations using a straightforward iteration method that may cause divergence are discussed; methods to avoid this kind of divergence are also proposed. Excellent results are consistently found for problems of various sizes.     

A new pruning heuristic based on variance analysis of sensitivityinformation

Architecture selection is a very important aspect in the design of neural networks (NNs) to optimally tune performance and computational complexity. Sensitivity analysis has been used successfully to prune irrelevant parameters from feedforward NNs. This paper presents a new pruning algorithm that uses the sensitivity analysis to quantify the relevance of input and hidden units. A new statistical pruning heuristic is proposed, based on the variance analysis, to decide which units to prune. The basic idea is that a parameter with a variance in sensitivity not significantly different from zero, is irrelevant and can be removed. Experimental results show that the new pruning algorithm correctly prunes irrelevant input and hidden units. The new pruning algorithm is also compared with standard pruning algorithms.     

HC_AB: A new heuristic clustering algorithm based on Approximate Backbone

Clustering is an important research area with numerous applications in pattern recognition, machine learning, and data mining. Since the clustering problem on numeric data sets can be formulated as a typical combinatorial optimization problem, many researches have addressed the design of heuristic algorithms for finding sub-optimal solutions in a reasonable period of time. However, most of the heuristic clustering algorithms suffer from the problem of being sensitive to the initialization and do not guarantee the high quality results. Recently, Approximate Backbone (AB), i.e., the commonly shared intersection of several sub-optimal solutions, has been proposed to address the sensitivity problem of initialization. In this paper, we aim to introduce the AB into heuristic clustering to overcome the initialization sensitivity of conventional heuristic clustering algorithms. The main advantage of the proposed method is the capability of restricting the initial search space around the optimal result by defining the AB, and in turn, reducing the impact of initialization on clustering, eventually improving the performance of heuristic clustering. Experiments on synthetic and real world data sets are performed to validate the effectiveness of the proposed approach in comparison to three conventional heuristic clustering algorithms and three other algorithms with improvement on initialization.     

Solving the truck and trailer routing problem based on a simulated annealing heuristic

In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (that is, a truck pulling a trailer) or a single truck, while others can only be serviced by a single truck for various reasons. SA has seen widespread applications to various combinatorial optimization problems, including the VRP. However, to our best knowledge, it has not been applied to the TTRP. So far, all the best known results for benchmark TTRP instances were obtained using tabu search (TS). We applied SA to the TTRP and obtained 17 best solutions to the 21 benchmark TTRP benchmark problems, including 11 new best solutions. Moreover, the computational time required by the proposed SA heuristic is less than those reported in prior studies. The results suggest that SA is competitive with TS on solving the TTRP.     

A simulated annealing heuristic for the open location-routing problem

This paper introduces the open location-routing problem (OLRP) that is a variant of the capacitated location-routing problem (CLRP). OLRP is motivated from the rise in contracting with third-party logistic (TPL) companies and is different from CLRP in that vehicles do not return to the distribution center after servicing all customers. The goal of OLRP is to minimize the total cost, consisting of facility operation costs, vehicle fixed costs, and traveling costs. We propose a simulated annealing (SA)-based heuristic for solving OLRP, which is tested on OLRP instances that have been adopted from three sets of well-known CLRP benchmark instances with up to 318 customers and 4 potential depots. The computational results indicate that the proposed heuristic efficiently solves OLRP.     

基于自适应模拟退火的NoC映射算法

在片上网络(Network on Chip,NoC)系统中,如何完成应用特征图到结构特征图的映射是影响系统实际性能的关键步骤之一。针对NoC系统越发庞大,映射算法耗时也随之增加的问题,提出了自适应模拟退火(Self-Adaptive Simulated Annealing,SASA)的NoC映射算法。采用相对平滑方式实现温度下降过程,针对模拟退火算法易陷于局部最优的缺点,采用自适应方法改变新解生成方式,提高了算法收敛于全局最优的概率。实验结果表明,该算法与常见NoC映射算法(如基于遗传的映射算法)相比,平均性能提升了5.3%,耗时缩短了11.1%。     

A new causal discovery heuristic

Probabilistic methods for causal discovery are based on the detection of patterns of correlation between variables. They are based on statistical theory and have revolutionised the study of causality. However, when correlation itself is unreliable, so are probabilistic methods: unusual data can lead to spurious causal links, while nonmonotonic functional relationships between variables can prevent the detection of causal links. We describe a new heuristic method for inferring causality between two continuous variables, based on randomness and unimodality tests and making few assumptions about the data. We evaluate the method against probabilistic and additive noise algorithms on real and artificial datasets, and show that it performs competitively.     

A simulated annealing heuristic for the capacitated location routing problem

The location routing problem (LRP) is a relatively new research direction within location analysis that takes into account vehicle routing aspects. The goal of LRP is to solve a facility location problem and a vehicle routing problem simultaneously. We propose a simulated annealing (SA) based heuristic for solving the LRP. The proposed SALRP heuristic is tested on three sets of well-known benchmark instances and the results are compared with other heuristics in the literature. The computational study indicates that the proposed SALRP heuristic is competitive with other well-known algorithms.     

A GRASP algorithm based new heuristic for the capacitated location routing problem

Abstract

In this paper, the capacitated location-routing problem (CLRP) is studied. CLRP is composed of two hard optimisation problems: the facility location problem and the vehicle routing problem. The objective of CLRP is to determine the best location of multiple depots with their vehicle routes such that the total cost of the solution is minimal. To solve this problem, we propose a greedy randomised adaptive search procedure. The proposed method is based on a new heuristic to construct a feasible CLRP solution, and then a local search-based simulated annealing is used as improvement phase. We have used a new technique to construct the clusters around the depots. To prove the effectiveness of our algorithm, several LRP instances are used. The results found are very encouraging.     

Searching for optimal frame patterns in an integrated TDMAcommunication system using mean field annealing

In an integrated time-division multiple access (TDMA) communication system, voice and data are multiplexed in time to share a common transmission link in a frame format in which time is divided into slots. A certain number of time slots in a frame are allocated to voice and the rest are used to transmit data. Maximum data throughput can be achieved by searching for the optimal configuration(s) of relative positions of voice and data transmissions in a frame (frame pattern). When the problem size becomes large, the computational complexity in searching for the optimal patterns becomes intractable. In the paper, mean field annealing (MFA), which provides near-optimal solutions with reasonable complexity, is proposed to solve this problem. The determination of the related parameters are addressed. Comparison with the random search and simulated annealing algorithm is made in terms of solution optimality and computational complexity. Simulation results show that the MFA approach exhibits a good tradeoff between performance and computational complexity.     

A new rotating machinery fault diagnosis method based on improved local mean decomposition

A demodulation technique based on improved local mean decomposition (LMD) is investigated in this paper. LMD heavily depends on the local mean and envelope estimate functions in the sifting process. It is well known that the moving average (MA) approach exists in many problems (such as step size selection, inaccurate results and time-consuming). Aiming at the drawbacks of MA in the smoothing process, this paper proposes a new self-adaptive analysis algorithm called optimized LMD (OLMD). In OLMD method, an alternative approach called rational Hermite interpolation is proposed to calculate local mean and envelope estimate functions using the upper and lower envelopes of a signal. Meanwhile, a reasonable bandwidth criterion is introduced to select the optimum product function (OPF) from pre-OPFs derived from rational Hermite interpolation with different shape controlling parameters in each rank. Subsequently, the orthogonality criterion (OC) is taken as the product function (PF) iterative stopping condition. The effectiveness of OLMD method is validated by the numerical simulations and applications to gearbox and roller bearing fault diagnosis. Results demonstrate that OLMD method has better fault identification capacity, which is effective in rotating machinery fault diagnosis.     

基于改进势场蚁群算法的机器人路径规划

提出一种全局静态环境下移动机器人路径规划的改进势场蚁群算法.该算法采用人工势场法求得的初始路径和机器人与下一个节点之间的距离综合构造启发信息,并引入启发信息递减系数,避免了传统蚁群算法由于启发信息误导所致的局部最优问题;依据零点定理, 提出初始信息素不均衡分配原则,不同的栅格位置赋予不同的初始信息素,降低蚁群搜索的盲目性,提高算法的搜索效率;设定迭代阈值,自适应调节信息素挥发系数,使得该算法具有较高的全局搜索能力,避免出现停滞现象.仿真结果验证了所提出算法的可行性和有效性.     

A simulated annealing heuristic for the dynamic layout problem with budget constraint

Facility layout problem has been extensively studied in the literature because the total material handling cost can be a significant portion in the operational costs for a company and in the manufacturing cost of a product. Today’s severe global competition, rapid changes in technology and shortening life cycle of products force companies to evaluate and modify their facility layout in a periodic fashion. This type of layout problems is categorized as the dynamic facility layout problem (DFLP). As a realistic dimension of the problem, one has to consider also the limited budget to cover the cost of changing the layout. In this study, we propose a simulated annealing heuristic for the DFLP with budget constraint, and show the effectiveness of this heuristic on a set of numerical experiments.     

A global simulated annealing heuristic for the three-parameter lognormal maximum likelihood estimation

It is well known that the inclusion of the threshold parameter in a lognormal distribution creates serious complications for parameter estimation; several parameterized schemes and global optimization procedures have been proposed to solve the problem in the maximum likelihood framework. A global Simulated Annealing optimization heuristic is proposed to solve the problem of maximum likelihood estimation in any parameterization scheme for the three-parameter lognormal distribution, as well as for the extended lognormal distribution. Positively and negatively skewed lognormal distributions are considered by introducing a one-parameter conditional estimation procedure in the classical parameterization for the three-parameter lognormal distribution, and a dual reparameterization is introduced for parameters estimation in the extended lognormal distribution. Simulated and real data are analyzed to test the efficiency of the proposed algorithm.     

A new CAN-like field network based on a star topology

Because of the particular medium access technique they adopt, Controller Area Networks (CAN) suffer from an intrinsic drawback which severely limits the maximum bus length allowed at high bit rates.In this paper, a new proposal is presented, which is based on a star topology and enables to enlarge the CAN network extension more than 10 times or, equivalently, to increase the bit rate of the same factor. In the proposed scheme, a star coupler takes part actively in the arbitration phase by disabling on-the-fly all the nodes which lose the contention, so that the increased propagation delays can be dealt with properly.The new mechanism shows a behaviour that is very similar to CAN, thus a reasonable degree of compatibility with the original protocol and the technology of the existing devices can be preserved.     

A new cutting-stock heuristic for scheduling production

This study interprets a scheduling problem in the woven fiberglass industry as an example of the cutting-stock problem; where wasted production capacity rather than wasted material is to be controlled. The solution is complicated due to the need to consider setup costs, so a heuristic is developed and tested. Comparison to one company's a historical production decisions indicates that both wasted capacity and setup Costs can be substantially reduced through application of the heuristic.