Centroid particle swarm optimisation for high-dimensional data classification

ABSTRACT

This paper proposes a new variant of Particle Swarm Optimization (PSO), dubbed CentroidPSO, to tackle data classification problem in high dimensional domains. It is inspired by the center-based sampling theory, which states that the center region of a search space contains points with higher probability to be closer to the optimal solution. The experimental results show striking performance of the CentroidPSO as compared to the standard PSO, four closely related PSO variants, and three recent evolutionary computation approaches. Moreover, a comparison with three machine learning approaches indicate that the CentroidPSO is a very competitive and promising classifier.     

Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimisation with negative knowledge

Particle swarm optimisation (PSO) is an evolutionary metaheuristic inspired by the swarming behaviour observed in flocks of birds. The applications of PSO to solve multi-objective discrete optimisation problems are not widespread. This paper presents a PSO algorithm with negative knowledge (PSONK) to solve multi-objective two-sided mixed-model assembly line balancing problems. Instead of modelling the positions of particles in an absolute manner as in traditional PSO, PSONK employs the knowledge of the relative positions of different particles in generating new solutions. The knowledge of the poor solutions is also utilised to avoid the pairs of adjacent tasks appearing in the poor solutions from being selected as part of new solution strings in the next generation. Much of the effective concept of Pareto optimality is exercised to allow the conflicting objectives to be optimised simultaneously. Experimental results clearly show that PSONK is a competitive and promising algorithm. In addition, when a local search scheme (2-Opt) is embedded into PSONK (called M-PSONK), improved Pareto frontiers (compared to those of PSONK) are attained, but longer computation times are required.     

Multi-scale 2D tracking of articulated objects using hierarchical spring systems

This paper presents a flexible framework to build a target-specific, part-based representation for arbitrary articulated or rigid objects. The aim is to successfully track the target object in 2D, through multiple scales and occlusions. This is realized by employing a hierarchical, iterative optimization process on the proposed representation of structure and appearance. Therefore, each rigid part of an object is described by a hierarchical spring system represented by an attributed graph pyramid. Hierarchical spring systems encode the spatial relationships of the features (attributes of the graph pyramid) describing the parts and enforce them by spring-like behavior during tracking. Articulation points connecting the parts of the object allow to transfer position information from reliable to ambiguous parts. Tracking is done in an iterative process by combining the hypotheses of simple trackers with the hypotheses extracted from the hierarchical spring systems.     

Hierarchical classification of protein function with ensembles of rules and particle swarm optimisation

This paper focuses on hierarchical classification problems where the classes to be predicted are organized in the form of a tree. The standard top-down divide and conquer approach for hierarchical classification consists of building a hierarchy of classifiers where a classifier is built for each internal (non-leaf) node in the class tree. Each classifier discriminates only between its child classes. After the tree of classifiers is built, the system uses them to classify test examples one class level at a time, so that when the example is assigned a class at a given level, only the child classes need to be considered at the next level. This approach has the drawback that, if a test example is misclassified at a certain class level, it will be misclassified at deeper levels too. In this paper we propose hierarchical classification methods to mitigate this drawback. More precisely, we propose a method called hierarchical ensemble of hierarchical rule sets (HEHRS), where different ensembles are built at different levels in the class tree and each ensemble consists of different rule sets built from training examples at different levels of the class tree. We also use a particle swarm optimisation (PSO) algorithm to optimise the rule weights used by HEHRS to combine the predictions of different rules into a class to be assigned to a given test example. In addition, we propose a variant of a method to mitigate the aforementioned drawback of top-down classification. These three types of methods are compared against the standard top-down hierarchical classification method in six challenging bioinformatics datasets, involving the prediction of protein function. Overall HEHRS with the rule weights optimised by the PSO algorithm obtains the best predictive accuracy out of the four types of hierarchical classification method.     

Train service timetabling in railway open markets by particle swarm optimisation

Railway timetabling is an important process in train service provision as it matches the transportation demand with the infrastructure capacity while customer satisfaction is also considered. It is a multi-objective optimisation problem, in which a feasible solution, rather than the optimal one, is usually taken in practice because of the time constraint. The quality of services may suffer as a result. In a railway open market, timetabling usually involves rounds of negotiations amongst a number of self-interested and independent stakeholders and hence additional objectives and constraints are imposed on the timetabling problem. While the requirements of all stakeholders are taken into consideration simultaneously, the computation demand is inevitably immense. Intelligent solution-searching techniques provide a possible solution. This paper attempts to employ a particle swarm optimisation (PSO) approach to devise a railway timetable in an open market. The suitability and performance of PSO are studied on a multi-agent-based railway open-market negotiation simulation platform.     

Reprint of: Multi-scale 2D tracking of articulated objects using hierarchical spring systems

This paper presents a flexible framework to build a target-specific, part-based representation for arbitrary articulated or rigid objects. The aim is to successfully track the target object in 2D, through multiple scales and occlusions. This is realized by employing a hierarchical, iterative optimization process on the proposed representation of structure and appearance. Therefore, each rigid part of an object is described by a hierarchical spring system represented by an attributed graph pyramid. Hierarchical spring systems encode the spatial relationships of the features (attributes of the graph pyramid) describing the parts and enforce them by spring-like behavior during tracking. Articulation points connecting the parts of the object allow to transfer position information from reliable to ambiguous parts. Tracking is done in an iterative process by combining the hypotheses of simple trackers with the hypotheses extracted from the hierarchical spring systems.     

Profit optimisation of the multiple-vacation machine repair problem using particle swarm optimisation

This paper investigates a multiple-vacation M/M/1 warm-standby machine repair problem with an unreliable repairman. We first apply a matrix-analytic method to obtain the steady-state probabilities. Next, we construct the total expected profit per unit time and formulate an optimisation problem to find the maximum profit. The particle swarm optimisation (PSO) algorithm is implemented to determine the optimal number of warm standbys S* and the service rate μ* as well as vacation rate ν* simultaneously at the optimal maximum profit. We compare the searching results of the PSO algorithm with those of exhaustive search method to ensure the searching quality of the PSO algorithm. Sensitivity analysis with numerical illustrations is also provided.     

Parameter selection in particle swarm optimisation: a survey

Nowadays, particle swarm optimisation (PSO) is one of the most commonly used optimisation techniques. However, PSO parameters significantly affect its computational behaviour. That is, while it exposes desirable computational behaviour with some settings, it does not behave so by some other settings, so the way for setting them is of high importance. This paper explains and discusses thoroughly about various existent strategies for setting PSO parameters, provides some hints for its parameter setting and presents some proposals for future research on this area. There exists no other paper in literature that discusses the setting process for all PSO parameters. Using the guidelines of this paper can be strongly useful for researchers in optimisation-related fields.     

Cultural-based particle swarm for dynamic optimisation problems

Many practical optimisation problems are with the existence of uncertainties, among which a significant number belong to the dynamic optimisation problem (DOP) category in which the fitness function changes through time. In this study, we propose the cultural-based particle swarm optimisation (PSO) to solve DOP problems. A cultural framework is adopted incorporating the required information from the PSO into five sections of the belief space, namely situational, temporal, domain, normative and spatial knowledge. The stored information will be adopted to detect the changes in the environment and assists response to the change through a diversity-based repulsion among particles and migration among swarms in the population space, and also helps in selecting the leading particles in three different levels, personal, swarm and global levels. Comparison of the proposed heuristics over several difficult dynamic benchmark problems demonstrates the better or equal performance with respect to most of other selected state-of-the-art dynamic PSO heuristics.     

Novel algorithms of particle swarm optimisation with decision criteria

The particle swarm optimisation (PSO) is a stochastic, optimisation technique based on the movement and intelligence of swarms. In this paper, three new effective optimisation algorithms BPSO, HPSO and WPSO, by incorporating some decision criteria into PSO, have been proposed and analysed both in terms of their efficiency, resistance to the problem of premature convergence and the ability to avoid local optima. In the new algorithms, for each particle except position, two sets of velocities are generated and the profit matrix is constructed. Using the decision criteria the best strategy is selected. Simulations for benchmark test nonlinear function show that the algorithms in which the decision criteria have been applied, are beneficial over classical PSO in terms of their performance and efficiency.     

Identifying stage of Alzheimer disease using multiclass particle swarm optimisation technique

ABSTRACT

Detecting brain structural changes from magnetic resonance (MR) images can facilitate early diagnosis and treatment of neurological and psychiatric diseases. Alzheimer Disease (AD) is a progressive neurodegenerative disorder that causes structural changes in patient’s brain. As such, it is essential to develop an algorithm for identifying the biomarkers of this disease stage. We developed a novel volumetric analysis of anatomical components of brain with multiclass particle swam optimisation technique (MPSO) approach to detect the stages of AD as potential biomarkers. To avoid image distortion bias correction is applied. We have used anatomical structures i.e. tissue and ventricle volume are used as criteria to categorise image features into four classes such as Alzheimer Mild cognitive decline, Alzheimer Moderate Cognitive decline and Alzheimer Severe Cognitive decline and healthy subject. This work was experimented with 30 AD and 10 normal cases. We observed that grey matter content was reduced from 4 to 20% of normal brain and volume of ventricle is increasing gradually from mild to severe cognitive decline. The statistical performance measures are calculated for proposed and existing work. The value shows that our empirical evaluation has superior diagnosis performance. We found that AD patient’s brain has reduced volume in grey matter and subsequently shrunk the volume of brain. The size of ventricle is also the major concern to predict the severity of AD disease. Therefore, the volumes of grey matter and ventricle size more discriminately classify the AD patient with severity from normal subject.     

Dynamical information fusion of heterogeneous sensors for 3D tracking using particle swarm optimization

This paper presents a new method for three dimensional object tracking by fusing information from stereo vision and stereo audio. From the audio data, directional information about an object is extracted by the Generalized Cross Correlation (GCC) and the object’s position in the video data is detected using the Continuously Adaptive Mean shift (CAMshift) method. The obtained localization estimates combined with confidence measurements are then fused to track an object utilizing Particle Swarm Optimization (PSO). In our approach the particles move in the 3D space and iteratively evaluate their current position with regard to the localization estimates of the audio and video module and their confidences, which facilitates the direct determination of the object’s three dimensional position. This technique has low computational complexity and its tracking performance is independent of any kind of model, statistics, or assumptions, contrary to classical methods. The introduction of confidence measurements further increases the robustness and reliability of the entire tracking system and allows an adaptive and dynamical information fusion of heterogenous sensor information.     

A memetic particle swarm optimisation algorithm for dynamic multi-modal optimisation problems

Many real-world optimisation problems are both dynamic and multi-modal, which require an optimisation algorithm not only to find as many optima under a specific environment as possible, but also to track their moving trajectory over dynamic environments. To address this requirement, this article investigates a memetic computing approach based on particle swarm optimisation for dynamic multi-modal optimisation problems (DMMOPs). Within the framework of the proposed algorithm, a new speciation method is employed to locate and track multiple peaks and an adaptive local search method is also hybridised to accelerate the exploitation of species generated by the speciation method. In addition, a memory-based re-initialisation scheme is introduced into the proposed algorithm in order to further enhance its performance in dynamic multi-modal environments. Based on the moving peaks benchmark problems, experiments are carried out to investigate the performance of the proposed algorithm in comparison with several state-of-the-art algorithms taken from the literature. The experimental results show the efficiency of the proposed algorithm for DMMOPs.     

Applications of particle swarm optimisation in integrated process planning and scheduling

Integration of process planning and scheduling (IPPS) is an important research issue to achieve manufacturing planning optimisation. In both process planning and scheduling, vast search spaces and complex technical constraints are significant barriers to the effectiveness of the processes. In this paper, the IPPS problem has been developed as a combinatorial optimisation model, and a modern evolutionary algorithm, i.e., the particle swarm optimisation (PSO) algorithm, has been modified and applied to solve it effectively. Initial solutions are formed and encoded into particles of the PSO algorithm. The particles “fly” intelligently in the search space to achieve the best sequence according to the optimisation strategies of the PSO algorithm. Meanwhile, to explore the search space comprehensively and to avoid being trapped into local optima, several new operators have been developed to improve the particles’ movements to form a modified PSO algorithm. Case studies have been conducted to verify the performance and efficiency of the modified PSO algorithm. A comparison has been made between the result of the modified PSO algorithm and the previous results generated by the genetic algorithm (GA) and the simulated annealing (SA) algorithm, respectively, and the different characteristics of the three algorithms are indicated. Case studies show that the developed PSO can generate satisfactory results in both applications.     

A meta optimisation analysis of particle swarm optimisation velocity update equations for watershed management learning

Particle swarm optimisation (PSO) is a general purpose optimisation algorithm used to address hard optimisation problems. The algorithm operates as a result of a number of particles converging on what is hoped to be the best solution. How the particles move through the problem space is therefore critical to the success of the algorithm. This study utilises meta optimisation to compare a number of velocity update equations to determine which features of each are of benefit to the algorithm. A number of hybrid velocity update equations are proposed based on other high performing velocity update equations. This research also presents a novel application of PSO to train a neural network function approximator to address the watershed management problem. It is found that the standard PSO with a linearly changing inertia, the proposed hybrid Attractive Repulsive PSO with avoidance of worst locations (AR PSOAWL) and Adaptive Velocity PSO (AV PSO) provide the best performance overall. The results presented in this paper also reveal that commonly used PSO parameters do not provide the best performance. Increasing and negative inertia values were found to perform better.     

An improved particle swarm optimiser based on swarm success rate for global optimisation problems

Inertia weight is one of the control parameters that influences the performance of particle swarm optimisation (PSO) in the course of solving global optimisation problems, by striking a balance between exploration and exploitation. Among many inertia weight strategies that have been proposed in literature are chaotic descending inertia weight (CDIW) and chaotic random inertia weight (CRIW). These two strategies have been claimed to perform better than linear descending inertia weight (LDIW) and random inertia weight (RIW). Despite these successes, a closer look at their results reveals that the common problem of premature convergence associated with PSO algorithm still lingers. Motivated by the better performances of CDIW and CRIW, this paper proposed two new inertia weight strategies namely: swarm success rate descending inertia weight (SSRDIW) and swarm success rate random inertia weight (SSRRIW). These two strategies use swarm success rates as a feedback parameter. Efforts were made using the proposed inertia weight strategies with PSO to further improve the effectiveness of the algorithm in terms of convergence speed, global search ability and improved solution accuracy. The proposed PSO variants, SSRDIW_PSO and SSRRIW_PSO were validated using several benchmark unconstrained global optimisation test problems and their performances compared with LDIW-PSO, CDIW-PSO, RIW-PSO, CRIW-PSO and some other existing PSO variants. Empirical results showed that the proposed variants are more efficient.     

Non-linear system control using a recurrent fuzzy neural network based on improved particle swarm optimisation

This article introduces a recurrent fuzzy neural network based on improved particle swarm optimisation (IPSO) for non-linear system control. An IPSO method which consists of the modified evolutionary direction operator (MEDO) and the Particle Swarm Optimisation (PSO) is proposed in this article. A MEDO combining the evolutionary direction operator and the migration operation is also proposed. The MEDO will improve the global search solution. Experimental results have shown that the proposed IPSO method controls the magnetic levitation system and the planetary train type inverted pendulum system better than the traditional PSO and the genetic algorithm methods.     

Particle swarm optimisation for feature selection in classification: Novel initialisation and updating mechanisms

In classification, feature selection is an important data pre-processing technique, but it is a difficult problem due mainly to the large search space. Particle swarm optimisation (PSO) is an efficient evolutionary computation technique. However, the traditional personal best and global best updating mechanism in PSO limits its performance for feature selection and the potential of PSO for feature selection has not been fully investigated. This paper proposes three new initialisation strategies and three new personal best and global best updating mechanisms in PSO to develop novel feature selection approaches with the goals of maximising the classification performance, minimising the number of features and reducing the computational time. The proposed initialisation strategies and updating mechanisms are compared with the traditional initialisation and the traditional updating mechanism. Meanwhile, the most promising initialisation strategy and updating mechanism are combined to form a new approach (PSO(4-2)) to address feature selection problems and it is compared with two traditional feature selection methods and two PSO based methods. Experiments on twenty benchmark datasets show that PSO with the new initialisation strategies and/or the new updating mechanisms can automatically evolve a feature subset with a smaller number of features and higher classification performance than using all features. PSO(4-2) outperforms the two traditional methods and two PSO based algorithm in terms of the computational time, the number of features and the classification performance. The superior performance of this algorithm is due mainly to both the proposed initialisation strategy, which aims to take the advantages of both the forward selection and backward selection to decrease the number of features and the computational time, and the new updating mechanism, which can overcome the limitations of traditional updating mechanisms by taking the number of features into account, which reduces the number of features and the computational time.     

Design of water distribution networks using accelerated momentum particle swarm optimisation technique

Optimisation of looped water distribution networks (WDNs) has been recognised as an NP-hard combinatorial problem which cannot be easily solved using traditional mathematical optimisation techniques. This article proposes the use of a new version of heuristic particle swarm optimisation (PSO) for solving this problem. In order to increase the convergence speed of the original PSO algorithm, some accelerated parameters are introduced to the velocity update equation. Furthermore, momentum parts are added to the PSO position updating formula to get away from trapping in local optimums. The new version of the PSO algorithm is called accelerated momentum particle swarm optimisation (AMPSO). The proposed AMPSO is then applied to solve WDN design problems. Some illustrative and comparative illustrative examples are presented to show the efficiency of the introduced AMPSO compared with some other heuristic algorithms.     

自适应粒子滤波在人体跟踪过程中的应用

人体运动跟踪技术近年来在图像处理与计算机视觉领域引起很多关注,在当前一些重要研究和应用领域有着广泛的需求。在以往跟踪方法的基础上提出了基于决策规则的自适应粒子滤波的无标记运动目标跟踪方法。利用一个带外观模板的人体关节模型,通过学习得到运动模型及基于关节模型的相似性计算,巧妙地利用自适应粒子滤波对运动目标进行实时跟踪,使得在粒子滤波过程中,可以根据实际滤波情况在线调节粒子数。实验表明,提出的算法鲁棒性好,跟踪速度比基于传统粒子滤波的快。