Research On Hybrid Particle Swarm Algorithms For Programming, Clulstering And Scheduling Problems

The programming, clustering and scheduling problems are a kind of important optimization problems in our real life which are all NP-hard and difficult to find a satisfying solution within a limited time. How to get the best or a satisfying solution quickly has great significance for improving productivity and the development of soceity. The traditional optimization algorithms have many advantages such as good computing efficiency, strong soundness and mature property, but they all have insurmountable limitation that it is difficult or impossible to find the exactly or even approximately best solution for a complex system. The presentation of evolutionary algorithm gives a new idea for solving complex optimization problems. It has been adopted by many research fields because of its intelligence, universality, stability, essential parallelism and global search ability. Many researchers in our country have put forward lots of optimization algorithms in which the particle swarm optimization algorithm is newer and preferable. It has been applied to many project practice problems and can get very good optimization effects. For many years the main focus of research was on the application of single metaheuristics to given problems. In recent years, it has become evident that the concentration on a sole metaheuristic is rather restrictive. A skilled combination of concepts of different metaheuristics, a so called hybrid metaheuristic, can provide a more efficient behavior and a higher flexibility when dealing with real-world and large-scale problems.In this work, we mainly research the hybrid metaheuristic algorithms based on particle swarm optimization algorithm for the programming, clustering and scheduling problems. That is solvting these problems by combining particle swarm optimization algorithm with other techniques.For the programming problems, a novel hybrid algorithm DE-PSO is proposed which combines the particle swarm optimization (PSO) algorithm with differential evolution (DE) operators to solve the programming problems with single objective. It incorporates concepts from DE and PSO, updating particle not only by DE operators but also by mechanisms of PSO. A random moving strategy is proposed to enhance the algorithm's exploration ability and modified DE operators are used to enhance each particle's local turning ability. These can not only maintain the algorithm's exploratory feature and at the same time can expedite its convergence. The proposed DE-PSO algorithm is tested on several benchmark functions from the usual literature. Numerical comparisons with different hybrid meta-heuristics demonstrate the effectiveness and efficiencies of the proposed DE-PSO method. In order to find multiple Pareto-optimal solutions, the traditional decomposition methods, stochastic population based algorithms and normal constraint methods for multiobjective programming problems need to run at least one time for each subproblem and each running processing is completely independent, which causes the problem of unable to share information and consuming more time. The obtained solution may also not be comparable. Furthermore, in many real-life applications of multiobjective optimization, may have many or even infinite Pareto optimal vectors. It is very time-consuming, if not impossible, to obtain the complete PF. On the other hand, the decision maker may not be interested in having an unduly large number of Pareto optimal vectors to deal with due to overflow of information. Therefore, many multiobjective optimization algorithms are to find a manageable number of Pareto optimal vectors which are evenly distributed along the PF, and thus good representatives of the entire PF. In this work, we combined the particle swarm optimization algorithm with decomposition methods effectively, and developed the MCPSO algorithm to solve the multiobjective programming problems. In this algorithm, a decomostion method is used to decompose the multiobjective programming problem into a number of scalar optimization subproblems and the particle swarm optimization algorithm is used to optimize them simultaneously. Each subproblem is presented only by one particle and optimized by only using information from its several neighboring subproblems which can not make the candidates share information effectively, but make the algorithm have lower computational complexity. The performance of the algorithm is compared with two multi-objective genetic search algorithms proposed in the literature. Computational results show that the proposed algorithm yields a reasonable approximation of the Pareto optimal set and outperforms NSGA and SPEA significantly for the applied benchmark programming instances.For the clustering problems, we converted them into optimization problems and integrated the particle swarm optimization algorithm with K-means to solve them. For the partitional clustering problem, an algorithm called PKPSO was proposed, in which the PSO and K-means algorithm are combined together through a new way. By analyzing the algorithm, how to adjust the control parameters is proposed. In order to further improve its performance, the inertia weight is made to change dynamically with the iterations. The comparisons are made between the PKPSO, PSO and K-means algorithm. Through theory analysis and experiments, the PKPSO property of global convergence is proved. It can not only overcome the shortcoming of K-means's trapping local minimum, but also the solutions precision and the algorithm stability are better than the other two algorithms. However, in partitional clustering algorithms, not only the number of clusters must be specified first but the clustering results are influenced greatly by the initial conditions. A dynamic clustering algorithm called DKPSO is then proposed and the cluster number can be determined automatically during running. In order to relieve the impact of initial conditions, the data set is partitioned into large number clusters, and then the discrete PSO is used to further optimize the cluster number and use the K-means algorithm to optimize the cluster center. Finally, the algorithm validity is testified through experimentation.For the flowshop scheduling problems, we combined the local search strategies, generic operations and annealing strategies with the particle swarm optimization algorithm and proposed the SADPSO, HPGA, AHPSO and ATPPSO algorithm for the flowshop scheduling problem with single objective. Based on the analysis for each algorithm, their effectivenesses are validated by the comparisons with other existing algorithms on benchmarks with different scale and difficulties. Moreover, an algorithm called MDPSO is developed to solve the multiobjective flowshop scheduling problem, which integrated the particle swarm optimization algorithm with the traditional decomposing methods for multiobjective programming problems. In this way, the multiobjective optimization problem is decomposed into a number of scalar optimization subproblems which can be optimized simultaneously through particle swarm optimization algorithm. Each subproblem is optimized by only using information from its several neighboring subproblems which can not make the candidates share information effectively, but make the algorithm have lower computational complexity. The performance of the algorithm is compared with two multi-objective genetic local search algorithms proposed in the literature. Computational results show that the proposed algorithm yields a reasonable approximation of the Pareto optimal set and outperforms NSGA-II and SPEA-II significantly for the applied benchmark flowshop scheduling instances.Hybrid metaheuristics is a new research area and currently enjoys an increasing interest in the optimization community since the special issue"Hybrid Metaheuristics"of International Journal of Mathematical Modelling and Algorithms was published in 2005. The design and implementation of hybrid metaheuristics rise problems going beyond questions about the design of a single metaheuristic. Choice and tuning of parameters is for example enlarged by the problem of how to achieve a proper interaction of different algorithm components. Interaction can take place at low-level, using functions from different metaheuristics, but also at high-level, e.g., using a portfolio of metaheuristics for automated hybridization. However, the field of hybrid metaheuristics is still in its early days. Many approaches are pre-mature and a substantial amount of further research is necessary in order to develop clearly structured hybrid metaheuristics that can be generally used for optimization. So, this paper's work will enrich and push forward the studies of the related areas in both theoretical and technological aspects.