Particle swarm optimization: Hybridization perspectives and experimental illustrations

Metaheuristic optimization algorithms have become popular choice for solving complex and intricate problems which are otherwise difficult to solve by traditional methods. In the present study an attempt is made to review the hybrid optimization techniques in which one main algorithm is a well known metaheuristic; particle swarm optimization or PSO. Hybridization is a method of combining two (or more) techniques in a judicious manner such that the resulting algorithm contains the positive features of both (or all) the algorithms. Depending on the algorithm/s used we made three classifications as (i) Hybridization of PSO and genetic algorithms (ii) Hybridization of PSO with differential evolution and (iii) Hybridization of PSO with other techniques. Where, other techniques include various local and global search methods. Besides giving the review we also show a comparison of three hybrid PSO algorithms; hybrid differential evolution particle swarm optimization (DE-PSO), adaptive mutation particle swarm optimization (AMPSO) and hybrid genetic algorithm particle swarm optimization (GA-PSO) on a test suite of nine conventional benchmark problems.     

Image data analysis and classification in marketing

Nowadays, the diffusion of smartphones, tablet computers, and other multipurpose equipment with high-speed Internet access makes new data types available for data analysis and classification in marketing. So, e.g., it is now possible to collect images/snaps, music, or videos instead of ratings. With appropriate algorithms and software at hand, a marketing researcher could simply group or classify respondents according to the content of uploaded images/snaps, music, or videos. However, appropriate algorithms and software are sparsely known in marketing research up to now. The paper tries to close this gap. Algorithms and software from computer science are presented, adapted and applied to data analysis and classification in marketing. The new SPSS-like software package IMADAC is introduced.     

Enhancing performance of particle swarm optimization through an algorithmic link with genetic algorithms

Evolutionary Algorithms (EAs) are emerging as competitive and reliable techniques for several optimization tasks. Juxtapositioning their higher-level and implicit correspondence; it is provocative to query if one optimization algorithm can benefit from another by studying underlying similarities and dissimilarities. This paper establishes a clear and fundamental algorithmic linking between particle swarm optimization (PSO) algorithm and genetic algorithms (GAs). Specifically, we select the task of solving unimodal optimization problems, and demonstrate that key algorithmic features of an effective Generalized Generation Gap based Genetic Algorithm can be introduced into the PSO by leveraging this algorithmic linking while significantly enhance the PSO’s performance. However, the goal of this paper is not to solve unimodal problems, neither is to demonstrate that the modified PSO algorithm resembles a GA, but to highlight the concept of algorithmic linking in an attempt towards designing efficient optimization algorithms. We intend to emphasize that the evolutionary and other optimization researchers should direct more efforts in establishing equivalence between different genetic, evolutionary and other nature-inspired or non-traditional algorithms. In addition to achieving performance gains, such an exercise shall deepen the understanding and scope of various operators from different paradigms in Evolutionary Computation (EC) and other optimization methods.     

Theoretical analysis of steady state genetic algorithms

Evolutionary Algorithms, also known as Genetic Algorithms in a former terminology, are probabilistic algorithms for optimization, which mimic operators from natural selection and genetics. The paper analyses the convergence of the heuristic associated to a special type of Genetic Algorithm, namely the Steady State Genetic Algorithm (SSGA), considered as a discrete-time dynamical system non-generational model. Inspired by the Markov chain results in finite Evolutionary Algorithms, conditions are given under which the SSGA heuristic converges to the population consisting of copies of the best chromosome.     

Optimization based DC programming and DCA for hierarchical clustering

One of the most promising approaches for clustering is based on methods of mathematical programming. In this paper we propose new optimization methods based on DC (Difference of Convex functions) programming for hierarchical clustering. A bilevel hierarchical clustering model is considered with different optimization formulations. They are all nonconvex, nonsmooth optimization problems for which we investigate attractive DC optimization Algorithms called DCA. Numerical results on some artificial and real-world databases are reported. The results demonstrate that the proposed algorithms are more efficient than related existing methods.     

Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems

Point-to-Multipoint systems are a kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to a combinatorial optimization problem, the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard and it is known that, for these problems, there exist no polynomial time algorithms with a fixed approximation ratio. Algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities. J. L. Marenco: This work supported by UBACYT Grant X036, CONICET Grant 644/98 and ANPCYT Grant 11-09112. A. K. Wagler: This work supported by the Deutsche Forschungsgemeinschaft (Gr 883/9–1).     

Advanced Genetic Programming Based Machine Learning

A Genetic Programming based approach for solving classification problems is presented in this paper. Classification is understood as the act of placing an object into a set of categories, based on the object’s properties; classification algorithms are designed to learn a function which maps a vector of object features into one of several classes. This is done by analyzing a set of input-output examples (“training samples”) of the function. Here we present a method based on the theory of Genetic Algorithms and Genetic Programming that interprets classification problems as optimization problems: Each presented instance of the classification problem is interpreted as an instance of an optimization problem, and a solution is found by a heuristic optimization algorithm. The major new aspects presented in this paper are advanced algorithmic concepts as well as suitable genetic operators for this problem class (mainly the creation of new hypotheses by merging already existing ones and their detailed evaluation). The experimental part of the paper documents the results produced using new hybrid variants of Genetic Algorithms as well as investigated parameter settings. Graphical analysis is done using a novel multiclass classifier analysis concept based on the theory of Receiver Operating Characteristic curves. The work described in this paper was done within the Translational Research Project L282 “GP-Based Techniques for the Design of Virtual Sensors” sponsored by the Austrian Science Fund (FWF).     

TRANSFORM-ANN for online optimization of complex industrial processes: Casting process as case study

Artificial Neural Networks (ANNs) are well known for their credible ability to capture non-linear trends in scientific data. However, the heuristic nature of estimation of parameters associated with ANNs has prevented their evolution into efficient surrogate models. Further, the dearth of optimal training size estimation algorithms for the data greedy ANNs resulted in their overfitting. Therefore, through this work, we aim to contribute a novel ANN building algorithm called TRANSFORM aimed at simultaneous and optimal estimation of ANN architecture, training size and transfer function. TRANSFORM is integrated with three standalone Sobol sampling based training size determination algorithms which incorporate the concepts of hypercube sampling and optimal space filling. TRANSFORM was used to construct ANN surrogates for a highly non-linear industrially validated continuous casting model from steel plant. Multiobjective optimization of casting model to ensure maximum productivity, maximum energy saving and minimum operational cost was performed by ANN assisted Non-dominated Sorting Genetic Algorithms (NSGA-II). The surrogate assisted optimization was found to be 13 times faster than conventional optimization, leading to its online implementation. Simple operator's rules were deciphered from the optimal solutions using Pareto front characterization and K-means clustering for optimal functioning of casting plant. Comprehensive studies on (a) computational time comparisons between proposed training size estimation algorithms and (b) predictability comparisons between constructed ANNs and state of art statistical models, Kriging Interpolators adds to the other highlights of this work. TRANSFORM takes physics based model as the only input and provides parsimonious ANNs as outputs, making it generic across all scientific domains.     

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.     

Bayesian approach to global optimization and application to multiobjective and constrained problems

In this paper, the Bayesian methods of global optimization are considered. They provide the minimal expected deviation from the global minimum. It is shown that, using the Bayesian methods, the asymptotic density of calculations of the objective function is much greater around the point of global minimum. The relation of this density to the parameters of the method and to the function is defined.Algorithms are described which apply the Bayesian methods to problems with linear and nonlinear constraints. The Bayesian approach to global multiobjective optimization is defined. Interactive procedures and reduction of multidimensional data in the case of global optimization are discussed.     

A tabu search algorithm for the training of neural networks

The most widely used training algorithm of neural networks (NNs) is back propagation (BP), a gradient-based technique that requires significant computational effort. Metaheuristic search techniques such as genetic algorithms, tabu search (TS) and simulated annealing have been recently used to cope with major shortcomings of BP such as the tendency to converge to a local optimal and a slow convergence rate. In this paper, an efficient TS algorithm employing different strategies to provide a balance between intensification and diversification is proposed for the training of NNs. The proposed algorithm is compared with other metaheuristic techniques found in literature using published test problems, and found to outperform them in the majority of the test cases.     

Positional robust inversion in nonlinear dynamical systems

The article studies robust inversion of nonlinear dynamical systems using a known phase vector. Inversion algorithms are proposed for the case when the system dynamics is exactly known. These algorithms solve the inversion problem with any prespecified accuracy. Algorithms solving the inversion problem with perturbed system dynamics are also considered. Accuracy bounds are obtained for the various algorithms. __________ Translated from Nelineinaya Dinamika i Upravlenie, No. 3, pp. 5–18, 2003.     

A metaheuristic methodology based on the limitation of the memory of interval branch and bound algorithms

Branch and Bound Algorithms based on Interval Arithmetic permit to solve exactly continuous (as well as mixed) non-linear and non-convex global optimization problems. However, their intrinsic exponential time-complexities do not make it possible to solve some quite large problems. The idea proposed in this paper is to limit the memory available during the computations of such a global optimization code in order to find some efficient feasible solutions. By this way, we introduce a metaheuristic frame to develop some new heuristic global optimization algorithms based on an exact code. We show in this paper, with a small assumption about the sorting by breadth first of elements in the data structure, that the time-complexity of such metaheuristic algorithms becomes polynomial instead of exponential for the exact code. In order to validate our metaheuristic approach, some numerical experiments about constrained global optimization problems coming from the COCONUT library were solved using a heuristic which certifies an enclosure of the global minimum value. The objective is not to solve completely the problem or find a better solution, but it is to know what is the highest precision which can be guaranteed reliably with the available memory.     

DNA序列的分类

本文对 A题中给出的 DNA序列分类问题进行了讨论 .从“不同序列中碱基含量不同”入手建立了欧氏距离判别模型 ,马氏距离判别模型以及 Fisher准则判定模型 ;又从“不同序列中碱基位置不同”入手建立了利用序列相关知识的相关度分类判别算法 ,并进一步研究了带反馈的相关度分类判别算法 .对于题中所给的待分类的人工序列和自然序列 ,本文都一一作了分类 .接着 ,本文又对其它各种常见的分类算法进行了讨论 ,并着重从分类算法的稳定性上对几种方法作了比较 .     

A Taxonomy of Evolutionary Algorithms in Combinatorial Optimization

This paper shows how evolutionary algorithms can be described in a concise, yet comprehensive and accurate way. A classification scheme is introduced and presented in a tabular form called TEA (Table of Evolutionary Algorithms). It distinguishes between different classes of evolutionary algorithms (e.g., genetic algorithms, ant systems) by enumerating the fundamental ingredients of each of these algorithms. At the end, possible uses of the TEA are illustrated on classical evolutionary algorithms.     

A multicriteria approach for rating the credit risk of financial institutions

Within the new bank regulatory context, the assessment of the credit risk of financial institutions is an important issue for supervising authorities and investors. This study explores the possibility of a developing risk assessment model for financial institutions using a multicriteria classification method. The analysis is based on publicly available financial data for UK firms. The results indicate that the proposed multicriteria methodology provides promising results compared to well known statistical methods.     

A subgradient proximal method for solving a class of monotone multivalued variational inequality problems

Numerical Algorithms - It is well known that the algorithms with using a proximal operator can be not convergent for monotone variational inequality problems in the general case. Malitsky (Optim....     

The continuous differential ant-stigmergy algorithm for numerical optimization

Many promising optimization algorithms for solving numerical optimization problems come from population-based metaheuristics. A few of them are based on Swarm-Intelligence Algorithms, which are inspired by the collective behavior of social organisms. One of the most successful of such algorithms is the Differential Ant-Stigmergy Algorithm (DASA), which uses stigmergy, a method of communication in emergent systems where the individual parts (artificial ants) of the system communicate with one another by modifying their local environment (pheromone intensity). The main characteristic of the DASA is its underlying structure (pheromone graph) that uses discrete steps to move through a continuous search space. As a consequence of this the search-space movement is in some way limited and the algorithm’s time/space complexity is increased. In order to overcome the problem an improved algorithm called the Continuous Differential Ant-Stigmergy Algorithm (CDASA) is proposed and then benchmarked on standard benchmark functions. This benchmarking showed that the CDASA performs better than the DASA, especially at lower dimensions, that its time/space complexity is decreased, and that the algorithm code is simplified. As such, the CDASA is more suitable for parallel implementations on General-Purpose Graphic Processing Units. Compared to the Swarm-Intelligence Algorithms presented in this paper, the CDASA is the best-performing algorithm and competitive to the state-of-the-art algorithms belonging to different metaheuristic approaches.     

Boosting for Correlated Binary Classification

Boosting is a successful method for dealing with problems of high-dimensional classification of independent data. However, existing variants do not address the correlations in the context of longitudinal or cluster study-designs with measurements collected across two or more time points or in clusters. This article presents two new variants of boosting with a focus on high-dimensional classification problems with matched-pair binary responses or, more generally, any correlated binary responses. The first method is based on the generic functional gradient descent algorithm and the second method is based on a direct likelihood optimization approach. The performance and the computational requirements of the algorithms were evaluated using simulations. Whereas the performance of the two methods is similar, the computational efficiency of the generic-functional-gradient-descent-based algorithm far exceeds that of the direct-likelihood-optimization-based algorithm. The former method is illustrated using data on gene expression changes in de novo and relapsed childhood acute lymphoblastic leukemia. Computer code implementing the algorithms and the relevant dataset are available online as supplemental materials.     

Methods to compare expensive stochastic optimization algorithms with random restarts

We consider the challenge of numerically comparing optimization algorithms that employ random-restarts under the assumption that only limited test data is available. We develop a bootstrapping technique to estimate the incumbent solution of the optimization problem over time as a stochastic process. The asymptotic properties of the estimator are examined and the approach is validated by an out-of-sample test. Finally, three methods for comparing the performance of different algorithms based on the estimator are proposed and demonstrated with data from a real-world optimization problem.