Heuristic particle filter: applying abstraction techniques to the design of visual tracking algorithms

Abstract: Many real‐world visual tracking applications have a high dimensionality, i.e. the system state is defined by a large number of variables. This kind of problem can be modelled as a dynamic optimization problem, which involves dynamic variables whose values change in time. Most applied research on optimization methods have focused on static optimization problems but these static methods often lack explicit adaptive methodologies. Heuristics are specific methods for solving problems in the absence of an algorithm for formal proof. Metaheuristics are approximate optimization methods which have been applied to more general problems with significant success. However, particle filters are Monte Carlo algorithms which solve the sequential estimation problem by approximating the theoretical distributions in the state space by simulated random measures called particles. However, particle filters lack efficient search strategies. In this paper, we propose a general framework to hybridize heuristics/metaheuristics with particle filters properly. The aim of this framework is to devise effective hybrid visual tracking algorithms naturally, guided by the use of abstraction techniques. Resulting algorithms exploit the benefits of both complementary approaches. As a particular example, a memetic algorithm particle filter is derived from the proposed hybridization framework. Finally, we show the performance of the memetic algorithm particle filter when it is applied to a multiple object tracking problem.     

Multi-objective discrete urban road network design

This paper addresses the problem of designing urban road networks in a multi-objective decision making framework. Given a base network with only two-way links, and the candidate lane addition and link construction projects, the problem is to find the optimal combination of one-way and two-way links, the optimal selection of network capacity expansion projects, and the optimal lane allocations on two-way links to optimize the reserve capacity of the network, and two new travel time related performance measures. The problem is considered in two variations; in the first scenario, two-way links may have different numbers of lanes in each direction and in the second scenario, two-way links must have equal number of lanes in each direction. The proposed variations are formulated as mixed-integer programming problems with equilibrium constraints. A hybrid genetic algorithm, an evolutionary simulated annealing, and a hybrid artificial bee colony algorithm are proposed to solve these two new problems. A new measure is also proposed to evaluate the effectiveness of the three algorithms. Computational results for both problems are presented.     

Parallel Ant Colony Optimization on Graphics Processing Units

The purpose of this paper is to propose effective parallelization strategies for the Ant Colony Optimization (ACO) metaheuristic on Graphics Processing Units (GPUs). The Max–Min Ant System (MMAS) algorithm augmented with 3-opt local search is used as a framework for the implementation of the parallel ants and multiple ant colonies general parallelization approaches. The four resulting GPU algorithms are extensively evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi GPU architecture. A rigorous effort is made to keep parallel algorithms true to the original MMAS applied to the Traveling Salesman Problem. We report speedups of up to 23.60 with solution quality similar to the original sequential implementation. With the intent of providing a parallelization framework for ACO on GPUs, a comparative experimental study highlights the performance impact of ACO parameters, GPU technical configuration, memory structures and parallelization granularity.     

Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization

The particle swarm optimization (PSO) is a relatively new generation of combinatorial metaheuristic algorithms which is based on a metaphor of social interaction, namely bird flocking or fish schooling. Although the algorithm has shown some important advances by providing high speed of convergence in specific problems it has also been reported that the algorithm has a tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. The present paper proposes a new variation of PSO model where we propose a new method of introducing nonlinear variation of inertia weight along with a particle's old velocity to improve the speed of convergence as well as fine tune the search in the multidimensional space. The paper also presents a new method of determining and setting a complete set of free parameters for any given problem, saving the user from a tedious trial and error based approach to determine them for each specific problem. The performance of the proposed PSO model, along with the fixed set of free parameters, is amply demonstrated by applying it for several benchmark problems and comparing it with several competing popular PSO and non-PSO combinatorial metaheuristic algorithms.     

解决多目标优化问题的差分进化算法研究进展

差分进化(differential evolution,DE)是一种简单但功能强大的进化优化算法.由于其优秀的性能,其诞生之日起就吸引了各国研究人员的关注.作为一种基于群体的全局性启发式搜索算法,差分进化算法在科学和工程中有许多成功的应用.本文对解决多目标优化问题的差分进化算法研究进行了综述,对差分进化的基本概念进行了详细的描述,给出了几种解决多目标优化问题的差分进化算法变体,并且给出了差分进化算法解决多目标优化问题的理论分析,最后,给出了差分进化算法解决多目标优化问题的工程应用,并指出了未来具有挑战性的研究领域.     

Convergence speed in multi‐objective metaheuristics: Efficiency criteria and empirical study

Solving optimization problems using a reduced number of objective function evaluations is an open issue in the design of multi‐objective optimization metaheuristics. The usual approach to analyze the behavior of such techniques is to choose a benchmark of known problems, to perform a predetermined number of function evaluations, and then, apply a set of performance indicators in order to assess the quality of the solutions obtained. However, this sort of methodology does not provide any insights of the efficiency of each algorithm. Here, efficiency is defined as the effort required by a multi‐objective metaheuristic to obtain a set of non‐dominated solutions that is satisfactory to the user, according to some pre‐defined criterion. Indeed, the type of solutions of interest to the user may vary depending on the specific characteristics of the problem being solved. In this paper, the convergence speed of seven state‐of‐the‐art multi‐objective metaheuristics is analyzed, according to three pre‐defined efficiency criteria. Our empirical study shows that SMPSO (based on a particle swarm optimizer) is found to be the best overall algorithm on the test problems adopted when considering the three efficiency criteria. Copyright © 2010 John Wiley & Sons, Ltd.     

A multi‐start threshold accepting algorithm for multiple objective continuous optimization problems

A multi‐start threshold accepting algorithm with an adaptive memory (MS‐TA) is proposed to solve multiple objective continuous optimization problems. The aim of this paper is to find efficiently multiple Pareto‐optimal solutions. Comparisons are carried out with multiple objective taboo search algorithm and genetic algorithm. Experiments on literature problems show that the proposed algorithm is more effective. The presented multi‐start adaptive algorithm improves the best‐known results by a significant margin. Copyright © 2010 John Wiley & Sons, Ltd.     

Selected variants of a Memetic Algorithm for JSP – a comparative study

The article aims to address a research gap concerning the adequate configuration of a Memetic Algorithm adapted to solve the Job-Shop Scheduling Problem. The goal was accomplished by means of conducting a comparative study of 16 variants of a Memetic Algorithm, characterised with different places of hybridisation and local search methods applied. The study involved the solution of eleven instances of JSP and the comparison of the results with the results achieved with an Evolutionary Algorithm lacking the mechanism of hybridisation and selected local search methods. The utilitarian significance of the problem also involved the use of assessment measures intended for both practical applications and research purposes.     

Improving the push–pull strategy in a serial supply chain by a hybrid push–pull control with multiple pulling points

Because of its benefits – from lowered inventory costs to greater flexibility in adapting to shifting market forces – the push–pull strategy is being widely used in today's competitive supply-chain designs. The push–pull strategy also brings potential supply-chain risks related to order fulfilment capability and robustness against external variability. More specifically, the use of this strategy often results in an inability to minimise the impact of lead-time variability. We present a new, hybrid push–pull strategy that incorporates additional stock points after the push–pull boundary as the pulling points in a serial supply chain, which can mitigate the risks and improve the robustness of the push–pull strategy without sacrificing its benefits in inventory cost reduction. For the evaluation and comparison of different supply-chain strategies, a nonlinear, mixed-integer programming model with a cost-minimisation objective function is developed and implemented in the numerical experimentation, with simulated annealing as the search algorithm. Results from the experiments demonstrate the potential improvement by our proposed strategy in terms of the robustness and cost-effectiveness against external variability. The results also verify the risks and limitations of the conventional push–pull strategy and provide some managerial implications regarding the use of push–pull supply chains.