Set-based particle swarm optimization applied to the multidimensional knapsack problem

Particle swarm optimization algorithms have been successfully applied to discrete/valued optimization problems. However, in many cases the algorithms have been tailored specifically for the problem at hand. This paper proposes a generic set-based particle swarm optimization algorithm for use in discrete-valued optimization problems that can be formulated as set-based problems. A detailed sensitivity analysis of the parameters of the algorithm is conducted. The performance of the proposed algorithm is then compared against three other discrete particle swarm optimization algorithms from literature using the multidimensional knapsack problem and is shown to statistically outperform the existing algorithms.     

Particle swarm optimizer for weighting factor selection in intensity-modulated radiation therapy optimization algorithms

In inverse treatment planning of intensity-modulated radiation therapy (IMRT), the objective function is typically the sum of the weighted sub-scores, where the weights indicate the importance of the sub-scores. To obtain a high-quality treatment plan, the planner manually adjusts the objective weights using a trial-and-error procedure until an acceptable plan is reached. In this work, a new particle swarm optimization (PSO) method which can adjust the weighting factors automatically was investigated to overcome the requirement of manual adjustment, thereby reducing the workload of the human planner and contributing to the development of a fully automated planning process. The proposed optimization method consists of three steps. (i) First, a swarm of weighting factors (i.e., particles) is initialized randomly in the search space, where each particle corresponds to a global objective function. (ii) Then, a plan optimization solver is employed to obtain the optimal solution for each particle, and the values of the evaluation functions used to determine the particle’s location and the population global location for the PSO are calculated based on these results. (iii) Next, the weighting factors are updated based on the particle’s location and the population global location. Step (ii) is performed alternately with step (iii) until the termination condition is reached. In this method, the evaluation function is a combination of several key points on the dose volume histograms. Furthermore, a perturbation strategy – the crossover and mutation operator hybrid approach – is employed to enhance the population diversity, and two arguments are applied to the evaluation function to improve the flexibility of the algorithm. In this study, the proposed method was used to develop IMRT treatment plans involving five unequally spaced 6 MV photon beams for 10 prostate cancer cases. The proposed optimization algorithm yielded high-quality plans for all of the cases, without human planner intervention. A comparison of the results with the optimized solution obtained using a similar optimization model but with human planner intervention revealed that the proposed algorithm produced optimized plans superior to that developed using the manual plan. The proposed algorithm can generate admissible solutions within reasonable computational times and can be used to develop fully automated IMRT treatment planning methods, thus reducing human planners’ workloads during iterative processes.     

Performance evaluation of TRIBES, an adaptive particle swarm optimization algorithm

This paper presents a study of the performance of TRIBES, an adaptive particle swarm optimization algorithm. Particle Swarm Optimization (PSO) is a biologically-inspired optimization method. Recently, researchers have used it effectively in solving various optimization problems. However, like most optimization heuristics, PSO suffers from the drawback of being greatly influenced by the selection of its parameter values. Thus, the common belief is that the performance of a PSO algorithm is directly related to the tuning of such parameters. Usually, such tuning is a lengthy, time consuming and delicate process. A new adaptive PSO algorithm called TRIBES avoids manual tuning by defining adaptation rules which aim at automatically changing the particles’ behaviors as well as the topology of the swarm. In TRIBES, the topology is changed according to the swarm behavior and the strategies of displacement are chosen according to the performances of the particles. A comparative study carried out on a large set of benchmark functions shows that the performance of TRIBES is quite competitive compared to most other similar PSO algorithms that need manual tuning of parameters. The performance evaluation of TRIBES follows the testing procedure introduced during the 2005 IEEE Conference on Evolutionary Computation. The main objective of the present paper is to perform a global study of the behavior of TRIBES under several conditions, in order to determine strengths and drawbacks of this adaptive algorithm.     

A new particle swarm optimization algorithm for noisy optimization problems

We propose a new particle swarm optimization algorithm for problems where objective functions are subject to zero-mean, independent, and identically distributed stochastic noise. While particle swarm optimization has been successfully applied to solve many complex deterministic nonlinear optimization problems, straightforward applications of particle swarm optimization to noisy optimization problems are subject to failure because the noise in objective function values can lead the algorithm to incorrectly identify positions as the global/personal best positions. Instead of having the entire swarm follow a global best position based on the sample average of objective function values, the proposed new algorithm works with a set of statistically global best positions that include one or more positions with objective function values that are statistically equivalent, which is achieved using a combination of statistical subset selection and clustering analysis. The new PSO algorithm can be seamlessly integrated with adaptive resampling procedures to enhance the capability of PSO to cope with noisy objective functions. Numerical experiments demonstrate that the new algorithm is able to consistently find better solutions than the canonical particle swarm optimization algorithm in the presence of stochastic noise in objective function values with different resampling procedures.     

Optimization of β-Cyclodextrin-Assisted Extraction of Apigenin and Luteolin from Chrysanthemum indicum L. Using Response Surface Methodology Combined with Different Optimization Algorithms and Evaluation of Its Antioxidant Capacity

Cyclodextrins and their derivatives have shown successful applications in extracting active compounds from medicinal plants. However, the use of β-cyclodextrin derivatives for extracting apigenin and luteolin from Chrysanthemum indicum L. remains unexplored. Additionally, the application of nature-inspired optimization algorithms in optimizing extraction conditions has been limited. Therefore, this study was performed with the aims of optimizing the extraction of apigenin and luteolin from C. indicum with the assistance of 2-hydroxypropyl-β-cyclodextrin (HP-β-CD) using response surface methodology combined with various optimization algorithms, including desirability function approach, genetic algorithm, particle swarm optimization, and firefly algorithm. The results showed that the optimal conditions obtained by the four algorithms were consistent, with an extraction time of 60 min, HP-β-CD concentration of 30 mg/mL, and a solvent-to-solid ratio of 24 mg/mL. At these conditions, the apigenin and luteolin contents were 1.362±0.008 and 8.724±0.117 mg/g, respectively. The results also showed that HP-β-CD-assisted extraction exhibited significantly higher apigenin and luteolin contents compared to conventional solvent. Comparable results were also yielded from the antioxidant assay. Our study suggested that the nature-inspired optimization algorithms might be potential options in enhancing the effectiveness of the traditional response surface methodology for the optimization of extraction of natural products.     

Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.     

Deep Learning-Based Metaheuristic Weighted K-Nearest Neighbor Algorithm for the Severity Classification of Breast Cancer

ObjectiveThe most widespread and intrusive cancer type among women is breast cancer. Globally, this type of cancer causes more mortality among women, next to lung cancer. This made the researchers to focus more on developing effective Computer-Aided Detection (CAD) methodologies for the classification of such deadly cancer types. In order to improve the rate of survival and earlier diagnosis, an optimistic research methodology is required in the classification of breast cancer. Consequently, an improved methodology that integrates the principle of deep learning with metaheuristic and classification algorithms is proposed for the severity classification of breast cancer. Hence to enhance the recent findings, an improved CAD methodology is proposed for redressing the healthcare problem.Material and MethodsThe work intends to cast a light-of-research towards classifying the severities present in digital mammogram images. For evaluating the work, the publicly available MIAS, INbreast, and WDBC databases are utilized. The proposed work employs transfer learning for extricating the features. The novelty of the work lies in improving the classification performance of the weighted k-nearest neighbor (wKNN) algorithm using particle swarm optimization (PSO), dragon-fly optimization algorithm (DFOA), and crow-search optimization algorithm (CSOA) as a transformation technique i.e., transforming non-linear input features into minimal linear separable feature vectors.ResultsThe results obtained for the proposed work are compared then with the Gaussian Naïve Bayes and linear Support Vector Machine algorithms, where the highest accuracy for classification is attained for the proposed work (CSOA-wKNN) with 84.35% for MIAS, 83.19% for INbreast, and 97.36% for WDBC datasets respectively.ConclusionThe obtained results reveal that the proposed Computer-Aided-Diagnosis (CAD) tool is robust for the severity classification of breast cancer.     

Two New PRP Conjugate Gradient Algorithms for Minimization Optimization Models

Two new PRP conjugate Algorithms are proposed in this paper based on two modified PRP conjugate gradient methods: the first algorithm is proposed for solving unconstrained optimization problems, and the second algorithm is proposed for solving nonlinear equations. The first method contains two aspects of information: function value and gradient value. The two methods both possess some good properties, as follows: 1)β _k ≥ 0 2) the search direction has the trust region property without the use of any line search method 3) the search direction has sufficient descent property without the use of any line search method. Under some suitable conditions, we establish the global convergence of the two algorithms. We conduct numerical experiments to evaluate our algorithms. The numerical results indicate that the first algorithm is effective and competitive for solving unconstrained optimization problems and that the second algorithm is effective for solving large-scale nonlinear equations.     

A modified particle swarm optimization algorithm for parameter estimation of a biological system

Background

Mathematical modeling has achieved a broad interest in the field of biology. These models represent the associations among the metabolism of the biological phenomenon with some mathematical equations such that the observed time course profile of the biological data fits the model. However, the estimation of the unknown parameters of the model is a challenging task. Many algorithms have been developed for parameter estimation, but none of them is entirely capable of finding the best solution. The purpose of this paper is to develop a method for precise estimation of parameters of a biological model.

Methods

In this paper, a novel particle swarm optimization algorithm based on a decomposition technique is developed. Then, its root mean square error is compared with simple particle swarm optimization, Iterative Unscented Kalman Filter and Simulated Annealing algorithms for two different simulation scenarios and a real data set related to the metabolism of CAD system.

Results

Our proposed algorithm results in 54.39% and 26.72% average reduction in root mean square error when applied to the simulation and experimental data, respectively.

Conclusion

The results show that the metaheuristic approaches such as the proposed method are very wise choices for finding the solution of nonlinear problems with many unknown parameters.

     

A novel numerical optimization algorithm inspired from weed colonization

This paper introduces a novel numerical stochastic optimization algorithm inspired from colonizing weeds. Weeds are plants whose vigorous, invasive habits of growth pose a serious threat to desirable, cultivated plants making them a threat for agriculture. Weeds have shown to be very robust and adaptive to change in environment. Thus, capturing their properties would lead to a powerful optimization algorithm. It is tried to mimic robustness, adaptation and randomness of colonizing weeds in a simple but effective optimizing algorithm designated as Invasive Weed Optimization (IWO). The feasibility, the efficiency and the effectiveness of IWO are tested in details through a set of benchmark multi-dimensional functions, of which global and local minima are known. The reported results are compared with other recent evolutionary-based algorithms: genetic algorithms, memetic algorithms, particle swarm optimization, and shuffled frog leaping. The results are also compared with different versions of simulated annealing — a generic probabilistic meta-algorithm for the global optimization problem — which are simplex simulated annealing, and direct search simulated annealing. Additionally, IWO is employed for finding a solution for an engineering problem, which is optimization and tuning of a robust controller. The experimental results suggest that results from IWO are better than results from other methods. In conclusion, the performance of IWO has a reasonable performance for all the test functions.     

Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions

This paper presents glowworm swarm optimization (GSO), a novel algorithm for the simultaneous computation of multiple optima of multimodal functions. The algorithm shares a few features with some better known swarm intelligence based optimization algorithms, such as ant colony optimization and particle swarm optimization, but with several significant differences. The agents in GSO are thought of as glowworms that carry a luminescence quantity called luciferin along with them. The glowworms encode the fitness of their current locations, evaluated using the objective function, into a luciferin value that they broadcast to their neighbors. The glowworm identifies its neighbors and computes its movements by exploiting an adaptive neighborhood, which is bounded above by its sensor range. Each glowworm selects, using a probabilistic mechanism, a neighbor that has a luciferin value higher than its own and moves toward it. These movements—based only on local information and selective neighbor interactions—enable the swarm of glowworms to partition into disjoint subgroups that converge on multiple optima of a given multimodal function. We provide some theoretical results related to the luciferin update mechanism in order to prove the bounded nature and convergence of luciferin levels of the glowworms. Experimental results demonstrate the efficacy of the proposed glowworm based algorithm in capturing multiple optima of a series of standard multimodal test functions and more complex ones, such as stair-case and multiple-plateau functions. We also report the results of tests in higher dimensional spaces with a large number of peaks. We address the parameter selection problem by conducting experiments to show that only two parameters need to be selected by the user. Finally, we provide some comparisons of GSO with PSO and an experimental comparison with Niche-PSO, a PSO variant that is designed for the simultaneous computation of multiple optima. This work is partially supported by a project grant from the Ministry of Human Resources Development, India and by DRDO-IISc Mathematical Engineering Program.     

Optimization of the hydrolysis of lignocellulosic residues by using radial basis functions modeling and particle swarm optimization

The concentrations of glucose and total reducing sugars obtained by chemical hydrolysis of three different lignocellulosic feedstocks were maximized. Two response surface methodologies were applied to model the amount of sugars produced: (1) classical quadratic least-squares fit (QLS), and (2) artificial neural networks based on radial basis functions (RBF). The results obtained by applying RBF were more reliable and better statistical parameters were obtained. Depending on the type of biomass, different results were obtained. Improvements in fit between 35% and 55% were obtained when comparing the coefficients of determination (R²) computed for both QLS and RBF methods. Coupling the obtained RBF models with particle swarm optimization to calculate the global desirability function, allowed to perform multiple response optimization. The predicted optimal conditions were confirmed by carrying out independent experiments.     

肿瘤亚型识别研究中智能算法的应用

目的:为解决肿瘤亚型识别过程中易出现的维数灾难和过拟合问题,提出了一种改进的粒子群BP神经网络集成算法。方法:算法采用欧式距离和互信息来初步过滤冗余基因,之后用Relief算法进一步处理,得到候选特征基因集合。采用BP神经网络作为基分类器,将特征基因提取与分类器训练相结合,改进的粒子群对其权值和阈值进行全局搜索优化。结果:当隐含层神经元个数为5时,候选特征基因个数为110时,QPSO/BP算法全局优化和搜索,此时的分类准确率最高。结论:该算法不但提高了肿瘤分型识别的准确率,而且降低了学习的复杂度。     

A Bayesian Interpretation of the Particle Swarm Optimization and Its Kernel Extension

Particle swarm optimization is a popular method for solving difficult optimization problems. There have been attempts to formulate the method in formal probabilistic or stochastic terms (e.g. bare bones particle swarm) with the aim to achieve more generality and explain the practical behavior of the method. Here we present a Bayesian interpretation of the particle swarm optimization. This interpretation provides a formal framework for incorporation of prior knowledge about the problem that is being solved. Furthermore, it also allows to extend the particle optimization method through the use of kernel functions that represent the intermediary transformation of the data into a different space where the optimization problem is expected to be easier to be resolved–such transformation can be seen as a form of prior knowledge about the nature of the optimization problem. We derive from the general Bayesian formulation the commonly used particle swarm methods as particular cases.     

Searching for structural bias in particle swarm optimization and differential evolution algorithms

During the last two decades, a large number of metaheuristics have been proposed, leading to various studies that call for a deeper insight into the behaviour, efficiency and effectiveness of such methods. Among numerous concerns that are briefly reviewed in this paper, the presence of a structural bias (i.e. the tendency, not justified by the fitness landscape, to visit some regions of the search space more frequently than other regions) has recently been detected in simple versions of the genetic algorithm and particle swarm optimization. As of today, it remains unclear how frequently such a behaviour occurs in population-based swarm intelligence and evolutionary computation methods, and to what extent structural bias affects their performance. The present study focuses on the search for structural bias in various variants of particle swarm optimization and differential evolution algorithms, as well as in the traditional direct search methods proposed by Nelder–Mead and Rosenbrock half a century ago. We found that these historical direct search methods are structurally unbiased. However, most tested new metaheuristics are structurally biased, and at least some presence of structural bias can be observed in almost all their variants. The presence of structural bias seems to be stronger in particle swarm optimization algorithms than in differential evolution algorithms. The relationships between the strength of the structural bias and the dimensionality of the search space, the number of allowed function calls and the population size are complex and hard to generalize. For 14 algorithms tested on the CEC2011 real-world problems and the CEC2014 artificial benchmarks, no clear relationship between the strength of the structural bias and the performance of the algorithm was found. However, at least for artificial benchmarks, such old and structurally unbiased methods like Nelder–Mead algorithm performed relatively well. This is a warning that the presence of structural bias in novel metaheuristics may hamper their search abilities.     

Determining residual reduction algorithm kinematic tracking weights for a sidestep cut via numerical optimization

Musculoskeletal modeling allows for the determination of various parameters during dynamic maneuvers by using in vivo kinematic and ground reaction force (GRF) data as inputs. Differences between experimental and model marker data and inconsistencies in the GRFs applied to these musculoskeletal models may not produce accurate simulations. Therefore, residual forces and moments are applied to these models in order to reduce these differences. Numerical optimization techniques can be used to determine optimal tracking weights of each degree of freedom of a musculoskeletal model in order to reduce differences between the experimental and model marker data as well as residual forces and moments. In this study, the particle swarm optimization (PSO) and simplex simulated annealing (SIMPSA) algorithms were used to determine optimal tracking weights for the simulation of a sidestep cut. The PSO and SIMPSA algorithms were able to produce model kinematics that were within 1.4° of experimental kinematics with residual forces and moments of less than 10 N and 18 Nm, respectively. The PSO algorithm was able to replicate the experimental kinematic data more closely and produce more dynamically consistent kinematic data for a sidestep cut compared to the SIMPSA algorithm. Future studies should use external optimization routines to determine dynamically consistent kinematic data and report the differences between experimental and model data for these musculoskeletal simulations.     

Parameter Identification of Robot Manipulators: A Heuristic Particle Swarm Search Approach

Parameter identification of robot manipulators is an indispensable pivotal process of achieving accurate dynamic robot models. Since these kinetic models are highly nonlinear, it is not easy to tackle the matter of identifying their parameters. To solve the difficulty effectively, we herewith present an intelligent approach, namely, a heuristic particle swarm optimization (PSO) algorithm, which we call the elitist learning strategy (ELS) and proportional integral derivative (PID) controller hybridized PSO approach (ELPIDSO). A specified PID controller is designed to improve particles’ local and global positions information together with ELS. Parameter identification of robot manipulators is conducted for performance evaluation of our proposed approach. Experimental results clearly indicate the following findings: Compared with standard PSO (SPSO) algorithm, ELPIDSO has improved a lot. It not only enhances the diversity of the swarm, but also features better search effectiveness and efficiency in solving practical optimization problems. Accordingly, ELPIDSO is superior to least squares (LS) method, genetic algorithm (GA), and SPSO algorithm in estimating the parameters of the kinetic models of robot manipulators.     

Evaluation of a particle swarm algorithm for biomechanical optimization

Optimization is frequently employed in biomechanics research to solve system identification problems, predict human movement, or estimate muscle or other internal forces that cannot be measured directly. Unfortunately, biomechanical optimization problems often possess multiple local minima, making it difficult to find the best solution. Furthermore, convergence in gradient-based algorithms can be affected by scaling to account for design variables with different length scales or units. In this study we evaluate a recently-developed version of the particle swarm optimization (PSO) algorithm to address these problems. The algorithm's global search capabilities were investigated using a suite of difficult analytical test problems, while its scale-independent nature was proven mathematically and verified using a biomechanical test problem. For comparison, all test problems were also solved with three off-the-shelf optimization algorithms--a global genetic algorithm (GA) and multistart gradient-based sequential quadratic programming (SQP) and quasi-Newton (BFGS) algorithms. For the analytical test problems, only the PSO algorithm was successful on the majority of the problems. When compared to previously published results for the same problems, PSO was more robust than a global simulated annealing algorithm but less robust than a different, more complex genetic algorithm. For the biomechanical test problem, only the PSO algorithm was insensitive to design variable scaling, with the GA algorithm being mildly sensitive and the SQP and BFGS algorithms being highly sensitive. The proposed PSO algorithm provides a new off-the-shelf global optimization option for difficult biomechanical problems, especially those utilizing design variables with different length scales or units.     

A competitive clustering particle swarm optimizer for dynamic optimization problems

Optimization in dynamic optimization problems (DOPs) requires the optimization algorithms not only to locate, but also to continuously track the moving optima. Particle swarm optimization (PSO) is a population-based optimization algorithm, originally developed for static problems. Recently, several researchers have proposed variants of PSO for optimization in DOPs. This paper presents a novel multi-swarm PSO algorithm, namely competitive clustering PSO (CCPSO), designed specially for DOPs. Employing a multi-stage clustering procedure, CCPSO splits the particles of the main swarm over a number of sub-swarms based on the particles positions and on their objective function values. The algorithm automatically adjusts the number of sub-swarms and the corresponding region of each sub-swarm. In addition to the sub-swarms, there is also a group of free particles that explore the environment to locate new emerging optima or exploit the current optima which are not followed by any sub-swarm. The adaptive search strategy adopted by the sub-swarms improves both the exploitation and tracking characteristics of CCPSO. A set of experiments is conducted to study the behavior of the proposed algorithm in different DOPs and to provide guidelines for setting the algorithm’s parameters in different problems. The results of CCPSO on a variety of moving peaks benchmark (MPB) functions are compared with those of several state-of-the-art PSO algorithms, indicating the efficiency of the proposed model.     

A locally convergent rotationally invariant particle swarm optimization algorithm

Several well-studied issues in the particle swarm optimization algorithm are outlined and some earlier methods that address these issues are investigated from the theoretical and experimental points of view. These issues are the: stagnation of particles in some points in the search space, inability to change the value of one or more decision variables, poor performance when the swarm size is small, lack of guarantee to converge even to a local optimum (local optimizer), poor performance when the number of dimensions grows, and sensitivity of the algorithm to the rotation of the search space. The significance of each of these issues is discussed and it is argued that none of the particle swarm optimizers we are aware of can address all of these issues at the same time. To address all of these issues at the same time, a new general form of velocity update rule for the particle swarm optimization algorithm that contains a user-definable function \(f\) is proposed. It is proven that the proposed velocity update rule guarantees to address all of these issues if the function \(f\) satisfies the following two conditions: (i) the function \(f\) is designed in such a way that for any input vector \(\vec {y}\) in the search space, there exists a region \(A\) which contains \(\vec {y}\) and \( f\!\left( {\vec {y}} \right) \) can be located anywhere in \(A\) , and (ii) \(f\) is invariant under any affine transformation. An example of function \(f\) is provided that satisfies these conditions and its performance is examined through some experiments. The experiments confirm that the proposed algorithm (with an appropriate function \(f)\) can effectively address all of these issues at the same time. Also, comparisons with earlier methods show that the overall ability of the proposed method for solving benchmark functions is significantly better.