An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis

Clustering is a popular data analysis and data mining technique. A popular technique for clustering is based on k-means such that the data is partitioned into K clusters. However, the k-means algorithm highly depends on the initial state and converges to local optimum solution. This paper presents a new hybrid evolutionary algorithm to solve nonlinear partitional clustering problem. The proposed hybrid evolutionary algorithm is the combination of FAPSO (fuzzy adaptive particle swarm optimization), ACO (ant colony optimization) and k-means algorithms, called FAPSO-ACO–K, which can find better cluster partition. The performance of the proposed algorithm is evaluated through several benchmark data sets. The simulation results show that the performance of the proposed algorithm is better than other algorithms such as PSO, ACO, simulated annealing (SA), combination of PSO and SA (PSO–SA), combination of ACO and SA (ACO–SA), combination of PSO and ACO (PSO–ACO), genetic algorithm (GA), Tabu search (TS), honey bee mating optimization (HBMO) and k-means for partitional clustering problem.     

Genetic particle swarm optimization for polygonal approximation of digital curves

Polygonal approximation is an important technique in image representation which directly impacts on the accuracy and efficacy of the subsequent image analysis tasks. This paper presents a new polygonal approximation approach based on particle swarm optimization (PSO). The original PSO is customized to continuous function value optimization. To facilitate the applicability of PSO to combinatorial optimization involving the problem in question, genetic reproduction mechanisms, namely crossover and mutation, are incorporated into PSO. We also propose a hybrid strategy embedding a segment-adjusting-and-merging optimizer into the genetic PSO evolutionary iterations to enhance its performance. The experimental results show that the proposed genetic PSO significantly improves the search efficacy of PSO for the polygonal approximation problem, and the hybrid strategy can accelerate the convergence speed but still with good-quality results. The performance of the proposed method is compared to existing approaches on both synthesized and real image curves. It is shown that the proposed hybrid genetic PSO outperforms the polygonal approximation approaches based on genetic algorithms and ant colony algorithms. The text was submitted by the author in English. Peng-Yeng Yin was born in 1966 and received his B.S., M.S. and Ph.D. degrees in Computer Science from National Chiao Tung University, Hsinchu, Taiwan, in 1989, 1991 and 1994, respectively. From 1993 to 1994, he was a visiting scholar at the Department of Electrical Engineering, University of Maryland, and the Department of Radiology, Georgetown University. In 2000, he was a visiting Associate Professor in the Visualization and Intelligent Systems Lab (VISLab) at the Department of Electrical Engineering, University of California, Riverside (UCR). He is currently a Professor at the Department of Information Management, National Chi Nan University, Nantou, Taiwan. His current research interests include image processing, pattern recognition, machine learning, computational biology, and evolutionary computation. He has published more than 70 articles in refereed journals and conferences. Dr. Yin received the Overseas Research Fellowship from the Ministry of Education in 1993 and Overseas Research Fellowship from the National Science Council in 2000. He is a member of the Phi Tau Phi Scholastic Honor Society and listed in Who’s Who in the World.     

Pattern synthesize of a cylindrical conformal array antenna by PSO algorithm

Pattern synthesize of conformal array antennas is often a challenging problem. Various optimization algorithms such as genetic, particle swarm optimization (PSO), and invasive weed optimization have already been used for pattern synthesizing of conformal arrays. In this paper, a focused beam is synthesized for a quarter cylindrical conformal array antenna using the PSO algorithm with small computations. The desired pattern is a focused beam at θ = 90° and ? = 45° with 10° beamwidth in elevation and 15° beamwidth in azimuth with ?20 dB side‐lobe level. This method can be used in general for synthesizing arbitrary desired patterns and array geometries.     

旅行商问题研究及混合粒子群算法求解

定性地分析了基本粒子群算法,结合遗传算法思想,构造了3种杂交和4种变异运算法则,从而得到了12种混合粒子群算法,并采用14城市算例对其检验和分析。为进一步验证混合算法的性能,根据分析结果挑选了几种较优的混合算法用以解决中国34城市（CTSP）问题和kroC100问题,其中CTSP问题很快达到最优解,对kroC100问题该文提供的算法获得了一个比现有已知结果更好的结果。     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

Markowitz-based portfolio selection with cardinality constraints using improved particle swarm optimization

This work presents particle swarm optimization (PSO), a collaborative population-based meta-heuristic algorithm for solving the Cardinality Constraints Markowitz Portfolio Optimization problem (CCMPO problem). To our knowledge, an efficient algorithmic solution for this nonlinear mixed quadratic programming problem has not been proposed until now. Using heuristic algorithms in this case is imperative. To solve the CCMPO problem, the proposed improved PSO increases exploration in the initial search steps and improves convergence speed in the final search steps. Numerical solutions are obtained for five analyses of weekly price data for the following indices for the period March, 1992 to September, 1997: Hang Seng 31 in Hong Kong, DAX 100 in Germany, FTSE 100 in UK, S&P 100 in USA and Nikkei 225 in Japan. The test results indicate that the proposed PSO is much more robust and effective than existing PSO algorithms, especially for low-risk investment portfolios. In most cases, the PSO outperformed genetic algorithm (GA), simulated annealing (SA), and tabu search (TS).     

A charging-scheme decision model for electric vehicle battery swapping station using varied population evolutionary algorithms

This paper proposes a new battery swapping station (BSS) model to determine the optimized charging scheme for each incoming Electric Vehicle (EV) battery. The objective is to maximize the BSS’s battery stock level and minimize the average charging damage with the use of different types of chargers. An integrated objective function is defined for the multi-objective optimization problem. The genetic algorithm (GA), differential evolution (DE) algorithm and three versions of particle swarm optimization (PSO) algorithms have been implemented to solve the problem, and the results show that GA and DE perform better than the PSO algorithms, but the computational time of GA and DE are longer than using PSO. Hence, the varied population genetic algorithm (VPGA) and varied population differential evolution (VPDE) algorithm are proposed to determine the optimal solution and reduce the computational time of typical evolutionary algorithms. The simulation results show that the performances of the proposed algorithms are comparable with the typical GA and DE, but the computational times of the VPGA and VPDE are significantly shorter. A 24-h simulation study is carried out to examine the feasibility of the model.     

An exploratory research of elitist probability schema and its applications in evolutionary algorithms

An important problem in the study of evolutionary algorithms is how to continuously predict promising solutions while simultaneously escaping from local optima. In this paper, we propose an elitist probability schema (EPS) for the first time, to the best of our knowledge. Our schema is an index of binary strings that expresses the similarity of an elitist population at every string position. EPS expresses the accumulative effect of fitness selection with respect to the coding similarity of the population. For each generation, EPS can quantify the coding similarity of the population objectively and quickly. One of our key innovations is that EPS can continuously predict promising solutions while simultaneously escaping from local optima in most cases. To demonstrate the abilities of the EPS, we designed an elitist probability schema genetic algorithm and an elitist probability schema compact genetic algorithm. These algorithms are estimations of distribution algorithms (EDAs). We provided a fair comparison with the persistent elitist compact genetic algorithm (PeCGA), quantum-inspired evolutionary algorithm (QEA), and particle swarm optimization (PSO) for the 0–1 knapsack problem. The proposed algorithms converged quicker than PeCGA, QEA, and PSO, especially for the large knapsack problem. Furthermore, the computation time of the proposed algorithms was less than some EDAs that are based on building explicit probability models, and was approximately the same as QEA and PSO. This is acceptable for evolutionary algorithms, and satisfactory for EDAs. The proposed algorithms are successful with respect to convergence performance and computation time, which implies that EPS is satisfactory.     

An improved hybrid particle swarm optimization algorithm for fuzzy p-hub center problem

The p-hub center problem is useful for the delivery of perishable and time-sensitive system such as express mail service and emergency service. In this paper, we propose a new fuzzy p-hub center problem, in which the travel times are uncertain and characterized by normal fuzzy vectors. The objective of our model is to maximize the credibility of fuzzy travel times not exceeding a predetermined acceptable efficient time point along all paths on a network. Since the proposed hub location problem is too complex to apply conventional optimization algorithms, we adapt an approximation approach (AA) to discretize fuzzy travel times and reformulate the original problem as a mixed-integer programming problem subject to logic constraints. After that, we take advantage of the structural characteristics to develop a parametric decomposition method to divide the approximate p-hub center problem into two mixed-integer programming subproblems. Finally, we design an improved hybrid particle swarm optimization (PSO) algorithm by combining PSO with genetic operators and local search (LS) to update and improve particles for the subproblems. We also evaluate the improved hybrid PSO algorithm against other two solution methods, genetic algorithm (GA) and PSO without LS components. Using a simulated data set of 10 nodes, the computational results show that the improved hybrid PSO algorithm achieves the better performance than GA and PSO without LS in terms of runtime and solution quality.     

IPSO算法用于确定型单机场地面等待问题

针对单机场地面等待问题,已有人采用遗传算法进行了求解,但其搜索最优解的能力差,且搜索效率低。粒子群优化（PSO）算法对该问题解空间及粒子编码设计难度较大,因而还未曾用于解决地面等待问题。针对确定型单机场地面等待数学模型,分别采用基本PSO、线性递减惯性权重加收缩因子PSO、随机惯性权重加收缩因子PSO、模拟退火PSO算法四种方法对该模型进行优化求解,并和采用遗传算法的结果进行了对比,仿真实验表明这四种方法在寻优能力和寻优效率方面显著提高,其中模拟退火PSO方法最好。     

Nonlinear continuous multi-response problems: a novel two-phase hybrid genetic based metaheuristic

Generally the most real world production systems are tackling several different responses and the problem is optimizing these responses concurrently. This study strives to present a new two-phase hybrid genetic based metaheuristic for optimizing nonlinear continuous multi-response problems. Premature convergence and getting stuck in local optima, which makes the algorithm time consuming, are common problems dealing with genetic algorithms (GAs). So we hybridize GA with a clustering approach and particle swarm optimization algorithm (PSO) to make a balanced relationship between time consuming and premature termination. The proposed algorithm also tries to find Ideal Points (IPs) for response functions. IPs are considered as improvement measures that determine when PSO should start. PSO based local search exploit Pareto archive solutions to enhance performance of the algorithm by expanding the search space. Since there is no standard benchmark in this field, we use two case studies from distinguished paper in multi-response optimization and compare the results with some of the mentioned algorithms in the literature. Results show the outperformance of the proposed algorithm than all of them.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

On the improved performances of the particle swarm optimization algorithms with adaptive parameters,cross-over operators and root mean square (RMS) variants for computing optimal control of a class of hybrid systems

This paper deals with the concept of including the popular genetic algorithm operator, cross-over and root mean square (RMS) variants into particle swarm optimization (PSO) algorithm to make the convergence faster. Two different PSO algorithms are considered in this paper: the first one is the conventional PSO (cPSO) and the second is the global-local best values based PSO (GLbest-PSO). The GLbest-PSO includes global-local best inertia weight (GLbestIW) with global-local best acceleration coefficient (GLbestAC), whereas the cPSO has a time varying inertia weight (TVIW) and either time varying acceleration coefficient (TVAC) or fixed AC (FAC). The effectiveness of the cross-over operator with both PSO algorithms is tested through a constrained optimal control problem of a class of hybrid systems. The experimental results illustrate the advantage of PSO with cross-over operator, which sharpens the convergence and tunes to the best solution. In order to compare and verify the validity and effectiveness of the new approaches for PSO, several statistical analyses are carried out. The results clearly demonstrate that the GLbest-PSO with the cross-over operator is a very promising optimization technique. Similar conclusions can be made for the GLbest-PSO with RMS variants also.     

Wind Farm Layout Design Using Cuckoo Search Algorithms

Wind energy has emerged as a strong alternative to fossil fuels for power generation. To generate this energy, wind turbines are placed in a wind farm. The extraction of maximum energy from these wind farms requires optimal placement of wind turbines. Due to complex nature of micrositing of wind turbines, the wind farm layout design problem is considered a complex optimization problem. In the recent past, various techniques and algorithms have been developed for optimization of energy output from wind farms. The present study proposes an optimization approach based on the cuckoo search (CS) algorithm, which is relatively a recent technique. A variant of CS is also proposed that incorporates a heuristic-based seed solution for a better performance. The proposed CS algorithms are compared with genetic and particle swarm optimization (PSO) algorithms, which have been extensively applied to wind farm layout design. Empirical results indicate that the proposed CS algorithms outperformed the genetic and PSO algorithms for the given test scenarios in terms of yearly power output and efficiency.     

A novel and effective particle swarm optimization like algorithm with extrapolation technique

A novel competitive approach to particle swarm optimization (PSO) algorithms is proposed in this paper. The proposed method uses extrapolation technique with PSO (ePSO) for solving optimization problems. By considering the basics of the PSO algorithm, the current particle position is updated by extrapolating the global best particle position and the current particle positions in the search space. The position equation is formulated with the global best (gbest) position, local best position (pbest) and the current position of the particle. The proposed method is tested with a set of 13 standard optimization benchmark problems and the results are compared with those obtained through two existing PSO algorithms, the canonical PSO (cPSO), the Global-Local best PSO (GLBest PSO). The cPSO includes a time-varying inertia weight (TVIW) and time-varying acceleration co-efficients (TVAC) while the GLBest PSO consists of Global-Local best inertia weight (GLBest IW) with Global-Local best acceleration co-efficient (GLBestAC). The simulation results clearly elucidate that the proposed method produces the near global optimal solution. It is also observed from the comparison of the proposed method with cPSO and GLBest PSO, the ePSO is capable of producing a quality of optimal solution with faster convergence rate. To strengthen the comparison and prove the efficacy of the proposed method a real time application of steel annealing processing (SAP) is also considered. The optimal control objectives of SAP are computed through the above said three PSO algorithms and also through two versions of genetic algorithms (GA), namely, real coded genetic algorithm (RCGA) and hybrid real coded genetic algorithm (HRCGA) and the results are analyzed with the proposed method. From the results obtained through benchmark problems and the real time application of SAP, it is clearly seen that the proposed ePSO method is competitive to the existing PSO algorithms and also to GAs.     

Application of metaheuristics-based clustering algorithm to item assignment in a synchronized zone order picking system

Warehousing management policy is a crucial issue in logistic management. It must be managed effectively and efficiently to reduce the production cost as well as the customer satisfaction. Synchronized zoning system is a warehousing management policy which aims to increase the warehouse utilization and customer satisfaction by reducing the customer waiting time. This policy divides a warehouse into several zones where each zone has its own picker who can work simultaneously. Herein, item assignment plays an important role since it influences the order processing performance. This study proposes an application of metaheuristic algorithms, namely particle swarm optimization (PSO) and genetic algorithm (GA), for item assignment in synchronized zoning system. The original PSO and GA algorithms are modified so that it is suitable for solving item assignment problem. The datasets with different sizes are used for method validation. Results obtained by PSO and GA are then compared with the result of an existing algorithm. The experimental results showed that PSO and GA can perform better than the existing algorithm. These results also show that PSO has better performance than GA, especially for bigger problems. It proves that item assignment policy obtained by PSO and GA has higher utilization rates than the existing algorithm.     

具有适应性突变和惯性权重的粒子群优化(PSO)算法及其在动态系统参数估计中的应用

An important problem in engineering is the unknown parameters estimation in nonlinear systems. In this paper, a novel adaptive particle swarm optimization (APSO) method is proposed to solve this problem. This work considers two new aspects, namely an adaptive mutation mechanism and a dynamic inertia weight into the conventional particle swarm optimization (PSO) method. These mechanisms are employed to enhance global search ability and to increase accuracy. First, three well-known benchmark functions namely Griewank, Rosenbrock and Rastrigrin are utilized to test the ability of a search algorithm for identifying the global optimum. The performance of the proposed APSO is compared with advanced algorithms such as a nonlinearly decreasing weight PSO (NDWPSO) and a real-coded genetic algorithm (GA), in terms of parameter accuracy and convergence speed. It is confirmed that the proposed APSO is more successful than other aforementioned algorithms. Finally, the feasibility of this algorithm is demonstrated through estimating the parameters of two kinds of highly nonlinear systems as the case studies.     

粒子群优化算法的改进研究

本文针对粒子群优化算法(PSO)存在早熟收敛的问题,提出了一系列改进措施,分别将混沌理论、遗传算法和免疫算法应用到PSO算法中。计算机仿真实验表明:改进算法基本保持了PSO算法简单、易实现的特点,且能够有效避免算法的早熟收敛问题,具有很强的全局搜索能力。     

A particle swarm optimization algorithm for optimal car-call allocation in elevator group control systems

High-rise buildings require the installation of complex elevator group control systems (EGCSs). In vertical transportation, when a passenger makes a hall call by pressing a landing call button installed at the floor and located near the cars of the elevator group, the EGCS must allocate one of the cars of the group to the hall call. We develop a particle swarm optimization (PSO) algorithm to deal with this car-call allocation problem. The PSO algorithm is compared to other soft computing techniques such as genetic algorithm and tabu search approaches that have been proved as efficient algorithms for this problem. The proposed PSO algorithm was tested in high-rise buildings from 10 to 24 floors, and several car configurations from 2 to 6 cars. Results from trials show that the proposed PSO algorithm results in better average journey times and computational times compared to genetic and tabu search approaches.     

QoS multicast routing using a quantum-behaved particle swarm optimization algorithm

QoS multicast routing in networks is a very important research issue in networks and distributed systems. It is also a challenging and hard problem for high-performance networks of the next generation. Due to its NP-completeness, many heuristic methods have been employed to solve the problem. This paper proposes the modified quantum-behaved particle swarm optimization (QPSO) method for QoS multicast routing. In the proposed method, QoS multicast routing is converted into an integer programming problem with QoS constraints and is solved by the QPSO algorithm combined with loop deletion operation. The QPSO-based routing method, along with the routing algorithms based on particle swarm optimization (PSO) and genetic algorithm (GA), is tested on randomly generated network topologies for the purpose of performance evaluation. The simulation results show the efficiency of the proposed method on QoS the routing problem and its superiority to the methods based on PSO and GA.