Data association approaches in bearings-only multi-target tracking

According to requirements of time computation complexity and correctness of data association of the multi-target tracking, two algorithms are suggested in this paper. The proposed Algorithm 1 is developed from the modified version of dual Simplex method, and it has the advantage of direct and explicit form of the optimal solution. The Algorithm 2 is based on the idea of Algorithm 1 and rotational sort method, it combines not only advantages of Algorithm 1, but also reduces the computational burden, whose complexity is only 1/N times that of Algorithm 1. Finally, numerical analyses are carried out to evaluate the performance of the two data association algorithms.     

Ant colony optimization for continuous domains

In this paper we present an extension of ant colony optimization (ACO) to continuous domains. We show how ACO, which was initially developed to be a metaheuristic for combinatorial optimization, can be adapted to continuous optimization without any major conceptual change to its structure. We present the general idea, implementation, and results obtained. We compare the results with those reported in the literature for other continuous optimization methods: other ant-related approaches and other metaheuristics initially developed for combinatorial optimization and later adapted to handle the continuous case. We discuss how our extended ACO compares to those algorithms, and we present some analysis of its efficiency and robustness.     

A study of ACO capabilities for solving the maximum clique problem

This paper investigates the capabilities of the Ant Colony Optimization (ACO) meta-heuristic for solving the maximum clique problem, the goal of which is to find a largest set of pairwise adjacent vertices in a graph. We propose and compare two different instantiations of a generic ACO algorithm for this problem. Basically, the generic ACO algorithm successively generates maximal cliques through the repeated addition of vertices into partial cliques, and uses “pheromone trails” as a greedy heuristic to choose, at each step, the next vertex to enter the clique. The two instantiations differ in the way pheromone trails are laid and exploited, i.e., on edges or on vertices of the graph. We illustrate the behavior of the two ACO instantiations on a representative benchmark instance and we study the impact of pheromone on the solution process. We consider two measures—the re-sampling and the dispersion ratio—for providing an insight into the performance at run time. We also study the benefit of integrating a local search procedure within the proposed ACO algorithm, and we show that this improves the solution process. Finally, we compare ACO performance with that of three other representative heuristic approaches, showing that the former obtains competitive results.     

A heuristic approach to find the global optimum of function

This paper presents the modified ant colony optimization (MACO) based algorithm to find global optimum. Algorithm is based on that solution space of problem is restricted by the best solution of the previous iteration. Furthermore, the proposed algorithm is that variables of problem are optimized concurrently. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and observed to be better.     

A hybrid optimization approach for multi-level capacitated lot-sizing problems

Solving multi-level capacitated lot-sizing problems is still a challenging task, in spite of increasing computational power and faster algorithms. In this paper a new approach combining an ant-based algorithm with an exact solver for (mixed-integer) linear programs is presented. A MAX–MIN ant system is developed to determine the principal production decisions, a LP/MIP solver is used to calculate the corresponding production quantities and inventory levels. Two different local search methods and an improvement strategy based on reduced mixed-integer problems are developed and integrated into the ant algorithm. This hybrid approach provides superior results for small and medium-sized problems in comparison to the existing approaches in the literature. For large-scale problems the performance of this method is among the best.     

A likelihood-based method for haplotype association studies of case-control data with genotyping uncertainty

This paper discusses the associations between traits and haplotypes based on Fl (fluorescent intensity) data sets. We consider a clustering algorithm based on mixtures of t distributions to obtain all possible genotypes of each individual (i.e. "GenoSpec-trum"). We then propose a likelihood-based approach that incorporates the genotyping uncertainty to assessing the associations between traits and haplotypes through a haplotype-based logistic regression model. Simulation studies show that our likelihood-based method can reduce the impact induced by genotyping errors.     

A new solution algorithm for improving performance of ant colony optimization

This study proposes an improved solution algorithm using ant colony optimization (ACO) for finding global optimum for any given test functions. The procedure of the ACO algorithms simulates the decision-making processes of ant colonies as they forage for food and is similar to other artificial intelligent techniques such as Tabu search, Simulated Annealing and Genetic Algorithms. ACO algorithms can be used as a tool for optimizing continuous and discrete mathematical functions. The proposed algorithm is based on each ant searches only around the best solution of the previous iteration with β. The proposed algorithm is called as ACORSES, an abbreviation of ACO Reduced SEarch Space. β is proposed for improving ACO’s solution performance to reach global optimum fairly quickly. The ACORSES is tested on fourteen mathematical test functions taken from literature and encouraging results were obtained. The performance of ACORSES is compared with other optimization methods. The results showed that the ACORSES performs better than other optimization algorithms, available in literature in terms of minimum values of objective functions and number of iterations.     

A multi-space data association algorithm for target tracking systems

In this paper, a multi-space data association algorithm based on the wavelet transform is proposed. In addition to carrying out the traditional hard logic data association in measurement space, the new algorithm updates the state of the target in the pattern space. Such a function significantly reduces the complicated environment misassociation effects on the data association. Simulation results show that the performance of the multi-spaced data association is much better than the existing data association algorithms in complicated clutter environments, such as the nearest-neighbor standard filter (NNSF), the probabilistic data association (PDA) and the joint probabilistic data association (JPDA). The computation of the multiple-space data association is much less than the aforementioned other existing data associations, and this new data association does not need any priori information of the environment. In complicated clutter environments, compared with the other data association, the new data association proposed in this paper is very robust, reliable and stable.     

A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP

The difficulty to solve multiple objective combinatorial optimization problems with traditional techniques has urged researchers to look for alternative, better performing approaches for them. Recently, several algorithms have been proposed which are based on the ant colony optimization metaheuristic. In this contribution, the existing algorithms of this kind are reviewed and a proposal of a taxonomy for them is presented. In addition, an empirical analysis is developed by analyzing their performance on several instances of the bi-criteria traveling salesman problem in comparison with two well-known multi-objective genetic algorithms.     

Finding Edge-disjoint Paths in Networks: An Ant Colony Optimization Algorithm

One of the basic operations in communication networks consists in establishing routes for connection requests between physically separated network nodes. In many situations, either due to technical constraints or to quality-of-service and survivability requirements, it is required that no two routes interfere with each other. These requirements apply in particular to routing and admission control in large-scale, high-speed and optical networks. The same requirements also arise in a multitude of other applications such as real-time communications, vlsi design, scheduling, bin packing, and load balancing. This problem can be modeled as a combinatorial optimization problem as follows. Given a graph G representing a network topology, and a collection T={(s ₁,t ₁)...(s _k ,t _k )} of pairs of vertices in G representing connection request, the maximum edge-disjoint paths problem is an NP-hard problem that consists in determining the maximum number of pairs in T that can be routed in G by mutually edge-disjoint s _i −t _i paths. We propose an ant colony optimization (aco) algorithm to solve this problem. aco algorithms are approximate algorithms that are inspired by the foraging behavior of real ants. The decentralized nature of these algorithms makes them suitable for the application to problems arising in large-scale environments. First, we propose a basic version of our algorithm in order to outline its main features. In a subsequent step we propose several extensions of the basic algorithm and we conduct an extensive parameter tuning in order to show the usefulness of those extensions. In comparison to a multi-start greedy approach, our algorithm generates in general solutions of higher quality in a shorter amount of time. In particular the run-time behaviour of our algorithm is one of its important advantages.

---

Work partially supported by the fet Integrated Project 15964 (aeolus), and by the Spanish cicyt projects tin2005-09198-c02-02 (asce), tin2005-08818-c04-02 (oplink) and tin2005-25859-e. C. Blum also acknowledges support by the ramón y cajal postdoctoral program of the Spanish Ministry of Science and Technology. Preliminary versions of this work were presented at the 1st European Workshop on Evolutionary Computation in Communications, Networks, and Connected Systems, lncs 3005:160–169, Springer 2004, and in the 9th Intl. Workshop on Nature Inspired Distributed Computing, p. 239, ieee 2006.     

Ant colony optimization with a specialized pheromone trail for the car-sequencing problem

This paper studies the learning process in an ant colony optimization algorithm designed to solve the problem of ordering cars on an assembly line (car-sequencing problem). This problem has been shown to be NP-hard and evokes a great deal of interest among practitioners. Learning in an ant algorithm is achieved by using an artificial pheromone trail, which is a central element of this metaheuristic. Many versions of the algorithm are found in literature, the main distinction among them being the management of the pheromone trail. Nevertheless, few of them seek to perfect learning by modifying the internal structure of the trail. In this paper, a new pheromone trail structure is proposed that is specifically adapted to the type of constraints in the car-sequencing problem. The quality of the results obtained when solving three sets of benchmark problems is superior to that of the best solutions found in literature and shows the efficiency of the specialized trail.     

Fuzzy criteria for feature selection

The presence of less relevant or highly correlated features often decrease classification accuracy. Feature selection in which most informative variables are selected for model generation is an important step in data-driven modeling. In feature selection, one often tries to satisfy multiple criteria such as feature discriminating power, model performance or subset cardinality. Therefore, a multi-objective formulation of the feature selection problem is more appropriate. In this paper, we propose to use fuzzy criteria in feature selection by using a fuzzy decision making framework. This formulation allows for a more flexible definition of the goals in feature selection, and avoids the problem of weighting different goals is classical multi-objective optimization. The optimization problem is solved using an ant colony optimization algorithm proposed in our previous work. We illustrate the added value of the approach by applying our proposed fuzzy feature selection algorithm to eight benchmark problems.     

Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking

The ever-increasing demand in surveillance is to produce highly accurate target and track identification and estimation in real-time, even for dense target scenarios and in regions of high track contention. The use of multiple sensors, through more varied information, has the potential to greatly enhance target identification and state estimation. For multitarget tracking, the processing of multiple scans all at once yields high track identification. However, to achieve this accurate state estimation and track identification, one must solve an NP-hard data association problem of partitioning observations into tracks and false alarms in real-time. The primary objective in this work is to formulate a general class of these data association problems as multidimensional assignment problems to which new, fast, near-optimal, Lagrangian relaxation based algorithms are applicable. The dimension of the formulated assignment problem corresponds to the number of data sets being partitioned with the constraints defining such a partition. The linear objective function is developed from Bayesian estimation and is the negative log posterior or likelihood function, so that the optimal solution yields the maximum a posteriori estimate. After formulating this general class of problems, the equivalence between solving data association problems by these multidimensional assignment problems and by the currently most popular method of multiple hypothesis tracking is established. Track initiation and track maintenance using anN-scan sliding window are then used as illustrations. Since multiple hypothesis tracking also permeates multisensor data fusion, two example classes of problems are formulated as multidimensional assignment problems.This work was partially supported by the Air Force Office of Scientific Research through AFOSR Grant Numbers AFOSR-91-0138 and F49620-93-1-0133 and by the Federal Systems Company of the IBM Corporation in Boulder, CO and Owego, NY.     

经过改进的求解TSP问题的蚁群算法

介绍了一种求解TSP问题的算法—改进的蚁群算法,算法通过模拟蚁群搜索食物的过程,可用于求解TSP问题,算法的主要特点是:正反馈、分布式计算、与某种启发式算法相结合.通过对传统蚁群算法的改进可以得到较好的结果.计算机仿真结果表明了该算法的有效性.     

An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)

The multi-objective resource allocation problem (MORAP) addresses the important issue which seeks to find the expected objectives by allocating the limited amount of resource to various activates. Resources may be manpower, assets, raw material or anything else in limited supply which can be used to accomplish the goals. The goals may be objectives (i.e., minimizing costs, or maximizing efficiency) usually driven by specific future needs. In this paper, in order to obtain a set of Pareto solution efficiently, we proposed a modified version of ant colony optimization (ACO), in this algorithm we try to increase the efficiency of algorithm by increasing the learning of ants. Effectiveness and efficiency of proposed algorithm was validated by comparing the result of ACO with hybrid genetic algorithm (hGA) which was applied to MORAP later.     

Ant colony optimization for solving an industrial layout problem

This paper presents ACO_GLS, a hybrid ant colony optimization approach coupled with a guided local search, applied to a layout problem. ACO_GLS is applied to an industrial case, in a train maintenance facility of the French railway system (SNCF). Results show that an improvement of near 20% is achieved with respect to the actual layout. Since the problem is modeled as a quadratic assignment problem (QAP), we compared our approach with some of the best heuristics available for this problem. Experimental results show that ACO_GLS performs better for small instances, while its performance is still satisfactory for large instances.     

Soft computing optimization methods applied to logistic processes

This paper discusses the methodologies that can be used to optimize a logistic process of a supply chain described as a scheduling problem. First, a model of the system based on a real-world example is presented. Then, a new objective function called Global Expected Lateness is proposed, in order to describe multiple optimization criteria. Finally, three different optimization methodologies are proposed: a classical dispatching rule, and two soft computing techniques, Genetic Algorithms (GA) and Ant Colony Optimization (ACO). These methodologies are compared to the dispatching policy in the real-world example. The results show that dispatching heuristics are outperformed by the GA and ACO meta-heuristics. Further, it is shown that GA and ACO provide statistically identical scheduling solutions and from the optimization performance point of view, it is equivalent to use any of the meta-heuristics.     

Identification of constitutive parameters for fractional viscoelasticity

This paper develops a numerical model to identify constitutive parameters in the fractional viscoelastic field. An explicit semi-analytical numerical model and a finite difference (FD) method based numerical model are derived for solving the direct homogenous and regionally inhomogeneous fractional viscoelastic problems, respectively. A continuous ant colony optimization (ACO) algorithm is employed to solve the inverse problem of identification. The feasibility of the proposed approach is illustrated via the numerical verification of a two-dimensional identification problem formulated by the fractional Kelvin–Voigt model, and the noisy data and regional inhomogeneity etc. are taken into account.