Maximum likelihood estimation of Gaussian mixture models using stochastic search

Gaussian mixture models (GMM), commonly used in pattern recognition and machine learning, provide a flexible probabilistic model for the data. The conventional expectation–maximization (EM) algorithm for the maximum likelihood estimation of the parameters of GMMs is very sensitive to initialization and easily gets trapped in local maxima. Stochastic search algorithms have been popular alternatives for global optimization but their uses for GMM estimation have been limited to constrained models using identity or diagonal covariance matrices. Our major contributions in this paper are twofold. First, we present a novel parametrization for arbitrary covariance matrices that allow independent updating of individual parameters while retaining validity of the resultant matrices. Second, we propose an effective parameter matching technique to mitigate the issues related with the existence of multiple candidate solutions that are equivalent under permutations of the GMM components. Experiments on synthetic and real data sets show that the proposed framework has a robust performance and achieves significantly higher likelihood values than the EM algorithm.     

Improved algorithm based on mutual information for learning Bayesian network structures in the space of equivalence classes

As is well known, greedy algorithm is usually used as local optimization method in many heuristic algorithms such as ant colony optimization, taboo search, and genetic algorithms, and it is significant to increase the convergence speed and learning accuracy of greedy search in the space of equivalence classes of Bayesian network structures. An improved algorithm, I-GREEDY-E is presented based on mutual information and conditional independence tests to firstly make a draft about the real network, and then greedily explore the optimal structure in the space of equivalence classes starting from the draft. Numerical experiments show that both the BIC score and structure error have some improvement, and the number of iterations and running time are greatly reduced. Therefore the structure with highest degree of data matching can be relatively faster determined by the improved algorithm.     

Enhancing the food locations in an artificial bee colony algorithm

Artificial bee colony or ABC is one of the newest additions to the class of population based Nature Inspired Algorithms. In the present study we suggest some modifications in the structure of basic ABC to further improve its performance. The corresponding algorithms proposed in the present study are named Intermediate ABC (I-ABC) and I-ABC greedy. In I-ABC, the potential food sources are generated by using the intermediate positions between the uniformly generated random numbers and random numbers generated by opposition based learning (OBL). I-ABC greedy is a variation of I-ABC, where the search is always forced to move towards the solution vector having the best fitness value in the population. While the use of OBL provides a priori information about the search space, the component of greediness improves the convergence rate. The performance of proposed I-ABC and I-ABC greedy are investigated on a comprehensive set of 13 classical benchmark functions, 25 composite functions included in the special session of CEC 2005 and eleven shifted functions proposed in the special session of CEC 2008, ISDA 2009, CEC 2010 and SOCO 2010. Also, the efficiency of the proposed algorithms is validated on two real life problems; frequency modulation sound parameter estimation and to estimate the software cost model parameters. Numerical results and statistical analysis demonstrates that the proposed algorithms are quite competent in dealing with different types of problems.     

基于触发序列集合的过程模型行为相似性算法

过程模型的相似性计算是业务过程管理中不可缺少的任务,广泛应用于组织合并、用户需求变更、模型仓库管理等多个场景.对基于主变迁序列的相似性度量方法 PTS进行研究,并提出了改进方案.通过定义完整触发序列表示模型行为,基于A*算法结合剪枝策略实现触发序列集合间的映射,进而完成模型相似性计算.实验结果表明:该方法较主流的基于模型行为相似性算法,计算合理性有很大提升.     

Probabilistic joint models incorporating logic and learning via structured variational approximation for information extraction

Traditional information extraction systems for compound tasks adopt pipeline architectures, which are highly ineffective and suffer from several problems such as cascading accumulation of errors. In this paper, we propose a joint discriminative probabilistic framework to optimize all relevant subtasks simultaneously. This framework offers a great flexibility to incorporate the advantage of both uncertainty for sequence modeling and first-order logic for domain knowledge. The first-order logic model provides a more expressive formalism tackling the issue of limited expressiveness of traditional attribute-value representation. Our framework defines a joint probability distribution for both segmentations in sequence data and possible worlds of relations between segments in the form of an exponential family. Since exact parameter estimation and inference are prohibitively intractable in this model, a structured variational inference algorithm is developed to perform parameter estimation approximately. For inference, we propose a highly coupled, bi-directional Metropolis-Hastings (MH) algorithm to find the maximum a posteriori (MAP) assignments for both segmentations and relations. Extensive experiments on two real-world information extraction tasks, entity identification and relation extraction from Wikipedia, and citation matching show that (1) the proposed model achieves significant improvement on both tasks compared to state-of-the-art pipeline models and other joint models; (2) the bi-directional MH inference algorithm obtains boosted performance compared to the greedy, N-best list, and uni-directional MH sampling algorithms.     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.     

Pruning by dominance in best-first search for the job shop Scheduling problem with total flow time

Best-First search is a problem solving paradigm that allows to design exact or admissible algorithms. In this paper, we confront the Job Shop Scheduling problem with total flow time minimization by means of the A ^* algorithm. We devised a heuristic from a problem relaxation that relies on computing Jackson’s preemptive schedules. In order to reduce the effective search space, we formalized a method for pruning nodes based on dominance relations and established a rule to apply this method efficiently during the search. By means of experimental study, we show that the proposed method is more efficient than a genetic algorithm in solving instances with 10 jobs and 5 machines and that pruning by dominance allows A ^* to reach optimal schedules, while these instances are not solved by A ^* otherwise. These experiments have also made it clear that the Job Shop Scheduling problem with total flow time minimization is harder to solve than the same problem with makespan minimization.     

融合简化稀疏A*算法与模拟退火算法的无人机航迹规划

针对无人机航迹规划问题,提出了一种融合简化稀疏A^*算法与模拟退火算法（Fusion of Simplified Sparse A^* Algorithm and Simulated Annealing algorithm,简称FSSA-SA）的航迹规划方法.首先,在对威胁环境进行建模之后,将模拟退火思想与具体航迹规划问题求解相结合,给出了模拟退火算法求解航迹规划问题的具体设计与实现方法.其次,利用简化的稀疏A^*算法在规划起止点之间进行一次往返搜索,并将所得结果中较优的一条航迹作为模拟退火算法的初始解,实现了两种算法的融合.然后,当退火进行至低温区时,通过对位置存在冗余的航迹节点的剔除,进一步改善了算法的求解质量.最后为了验证算法的优越性,将本文算法与稀疏A^*算法、模拟退火算法进行了仿真对比试验.试验结果表明,本文提出的FSSA-SA算法相比于上述两种算法,具有较少的规划耗时;相比于稀疏A^*算法,在所得航迹的综合代价相差不大的情况下,内存占用量少了两个量级;相比与模拟退火算法,在相同的退火条件下,其规划所得航迹的综合代价平均减少了35%左右.     

Competitive Hopfield Network Combined With Estimation of Distribution for Maximum Diversity Problems

This paper presents a discrete competitive Hopfield neural network (HNN) (DCHNN) based on the estimation of distribution algorithm (EDA) for the maximum diversity problem. In order to overcome the local minimum problem of DCHNN, the idea of EDA is combined with DCHNN. Once the network is trapped in local minima, the perturbation based on EDA can generate a new starting point for DCHNN for further search. It is expected that the further search is guided to a promising area by the probability model. Thus, the proposed algorithm can escape from local minima and further search better results. The proposed algorithm is tested on 120 benchmark problems with the size ranging from 100 to 5000. Simulation results show that the proposed algorithm is better than the other improved DCHNN such as multistart DCHNN and DCHNN with random flips and is better than or competitive with metaheuristic algorithms such as tabu-search-based algorithms and greedy randomized adaptive search procedure algorithms.      

Parameter estimation for crop growth model using evolutionary and bio-inspired algorithms

All dynamic crop models for growth and development have several parameters whose values are usually determined by using measurements coming from the real system. The parameter estimation problem is raised as an optimization problem and optimization algorithms are used to solve it. However, because the model generally is nonlinear the optimization problem likely is multimodal and therefore classical local search methods fail in locating the global minimum and as a consequence the model parameters could be inaccurate estimated. This paper presents a comparison of several evolutionary (EAs) and bio-inspired (BIAs) algorithms, considered as global optimization methods, such as Differential Evolution (DE), Covariance Matrix Adaptation Evolution Strategy (CMA-ES), Particle Swarm Optimization (PSO) and Artificial Bee Colony (ABC) on parameter estimation of crop growth SUCROS (a Simple and Universal CROp Growth Simulator) model. Subsequently, the SUCROS model for potential growth was applied to a husk tomato crop (Physalis ixocarpa Brot. ex Horm.) using data coming from an experiment carried out in Chapingo, Mexico. The objective was to determine which algorithm generates parameter values that give the best prediction of the model. An analysis of variance (ANOVA) was carried out to statistically evaluate the efficiency and effectiveness of the studied algorithms. Algorithm's efficiency was evaluated by counting the number of times the objective function was required to approximate an optimum. On the other hand, the effectiveness was evaluated by counting the number of times that the algorithm converged to an optimum. Simulation results showed that standard DE/rand/1/bin got the best result.     

Directed explicit-state model checking in the validation of communication protocols

The success of model checking is largely based on its ability to efficiently locate errors in software designs. If an error is found, a model checker produces a trail that shows how the error state can be reached, which greatly facilitates debugging. However, while current model checkers find error states efficiently, the counterexamples are often unnecessarily lengthy, which hampers error explanation. This is due to the use of naive search algorithms in the state space exploration.In this paper we present approaches to the use of heuristic search algorithms in explicit-state model checking. We present the class of A^* directed search algorithms and propose heuristics together with bitstate compression techniques for the search of safety property violations. We achieve great reductions in the length of the error trails, and in some instances render problems analyzable by exploring a much smaller number of states than standard depth-first search. We then suggest an improvement of the nested depth-first search algorithm and show how it can be used together with A^* to improve the search for liveness property violations. Our approach to directed explicit-state model checking has been implemented in a tool set called HSF-SPIN. We provide experimental results from the protocol validation domain using HSF-SPIN.     

基于一致性度量的数字孪生模型实时自修正

数字孪生技术解决了信息物理世界的融合难题,在工业互联网领域里获得了十分广泛的应用。为解决数字孪生与物理实体的动态修正问题,本文提出一种基于一致性度量的数字孪生模型实时自修正方法。利用数据变化快慢将模型分为渐变模型和快速模型2个部分,构建参数快速搜索方法,结合拉丁超立方全局搜索和贪婪局部搜索,并引入迭代更新机制,实现物理实体和数字孪生体的一致性度量。实验结果表明,数字孪生模型通过优化模型可调参数的选取过程,改善可调参数选取随机性的问题,实现模型与物理实体高度一致性,达到了模型实时自修正要求。     

A Greedy EM Algorithm for Gaussian Mixture Learning

Learning a Gaussian mixture with a local algorithm like EM can be difficult because (i) the true number of mixing components is usually unknown, (ii) there is no generally accepted method for parameter initialization, and (iii) the algorithm can get trapped in one of the many local maxima of the likelihood function. In this paper we propose a greedy algorithm for learning a Gaussian mixture which tries to overcome these limitations. In particular, starting with a single component and adding components sequentially until a maximum number k, the algorithm is capable of achieving solutions superior to EM with k components in terms of the likelihood of a test set. The algorithm is based on recent theoretical results on incremental mixture density estimation, and uses a combination of global and local search each time a new component is added to the mixture. This revised version was published online in August 2006 with corrections to the Cover Date.     

一种基于A*算法的虚拟力场避障导航算法

针对传统A＊算法在实际应用中需要所有的节点信息,算法忽略车身实际宽度的问题,提出了基于A＊算法同时结合使用虚拟力场法的避障导航算法。该改进算法解决了 A＊算法在实际应用中存在的问题,也避免了单独使用虚拟力场法存在的容易陷入局部极小点、在目标点附近有障碍物时无法到达以及摆动剧烈的问题。仿真实验验证了新算法的有效性,实验结果表明该算法拓宽了原有算法的使用范围并且提高了无人车实时路径导航的能力。     

Multi‐core scalable and efficient pathfinding with Parallel Ripple Search

Game developers are often faced with very demanding requirements on huge numbers of agents moving naturally through increasingly large and detailed virtual worlds. With the advent of multi‐core architectures, new approaches to accelerate expensive pathfinding operations are worth being investigated. Traditional single‐processor pathfinding strategies, such as A^* and its derivatives, have been long praised for their flexibility. We implemented several parallel versions of such algorithms to analyze their intrinsic behavior, concluding that they have a large overhead, yield far from optimal paths, do not scale up to many cores or are cache unfriendly. In this article, we propose Parallel Ripple Search, a novel parallel pathfinding algorithm that largely solves these limitations. It utilizes a high‐level graph to assign local search areas to CPU cores at “equidistant” intervals. These cores then use A^* flooding behavior to expand towards each other, yielding good “guesstimate points” at border touch on. The process does not rely on expensive parallel programming synchronization locks but instead relies on the opportunistic use of node collisions among cooperating cores, exploiting the multi‐core's shared memory architecture. As a result, all cores effectively run at full speed until enough way‐points are found. We show that this approach is a fast, practical and scalable solution and that it flexibly handles dynamic obstacles in a natural way. Copyright © 2012 John Wiley & Sons, Ltd.     

Hybrid shortest path algorithm for vehicle navigation

Vehicle navigation is one of the important applications of the single-source single-target shortest path algorithm. This application frequently involves large scale networks with limited computing power and memory space. In this study, several heuristic concepts, including hierarchical, bidirectional, and A^*, are combined and used to develop hybrid algorithms that reduce searching space, improve searching speed, and provide the shortest path that closely resembles the behavior of most road users. The proposed algorithms are demonstrated on a real network consisting 374,520 nodes and 502,485 links. The network is preprocessed and separated into two connected subnetworks. The upper layer of network is constructed with high mobility links, while the lower layer comprises high accessibility links. The proposed hybrid algorithms are implemented on both PC and hand-held platforms. Experiments show a significant acceleration compared to the Dijkstra and A^* algorithm. Memory consumption of the hybrid algorithm is also considerably less than traditional algorithms. Results of this study showed the hybrid algorithms have an advantage over the traditional algorithm for vehicle navigation systems.     

基于遗传算法的UAV自适应航迹规划

根据遗传算法与动态的稀疏A*搜索(Dynamic Sparse A*Search,DASA)算法各自的特点,提出一种组合优化算法来实现在不确定战场环境中自适应航迹规划.在无人机(UAV,Unmanned Aerial Vehicles)飞行前,采用全局搜索能力强的遗传算法进行全局搜索,对从起始点到目标点的飞行航线进行规划,生成全局最优或次优的可行参考飞行航线;在无人机任务执行阶段,以参考飞行航线为基准,采用DASA算法进行在线实时航迹再规划.仿真结果表明,与遗传算法相比,该组合算法不但能生成近似最优解,而且能够满足在线实时应用的要求.     

A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flow shops

Obtaining an optimal solution for a permutation flowshop scheduling problem with the total flowtime criterion in a reasonable computational timeframe using traditional approaches and optimization tools has been a challenge. This paper presents a discrete artificial bee colony algorithm hybridized with a variant of iterated greedy algorithms to find the permutation that gives the smallest total flowtime. Iterated greedy algorithms are comprised of local search procedures based on insertion and swap neighborhood structures. In the same context, we also consider a discrete differential evolution algorithm from our previous work. The performance of the proposed algorithms is tested on the well-known benchmark suite of Taillard. The highly effective performance of the discrete artificial bee colony and hybrid differential evolution algorithms is compared against the best performing algorithms from the existing literature in terms of both solution quality and CPU times. Ultimately, 44 out of the 90 best known solutions provided very recently by the best performing estimation of distribution and genetic local search algorithms are further improved by the proposed algorithms with short-term searches. The solutions known to be the best to date are reported for the benchmark suite of Taillard with long-term searches, as well.     

Evolutionary decision-makings for the dynamic weapon-target assignment problem

The dynamic weapon-target assignment (DWTA) problem is an important issue in the field of military command and control. An asset-based DWTA optimization model was proposed with four kinds of constraints considered, including capability constraints, strategy constraints, resource constraints and engagement feasibility constraints. A general “virtual” representation of decisions was presented to facilitate the generation of feasible decisions. The representation is in essence the permutation of all assignment pairs. A construction procedure converts the permutations into real feasible decisions. In order to solve this problem, three evolutionary decision-making algorithms, including a genetic algorithm and two memetic algorithms, were developed. Experimental results show that the memetic algorithm based on greedy local search can generate obviously better DWTA decisions, especially for large-scale problems, than the genetic algorithm and the memetic algorithm based on steepest local search.