【作者】 张长胜；

【导师】 欧阳丹彤；

【作者基本信息】 吉林大学 ， 计算机软件与理论， 2009， 博士

【摘要】 近来,人们发现专注于单独使用一种算法具有非常大的局限性,如果将元启发式算法与其他优化技术或元启发式算法之间有效结合,即混合元启发式算法,能够更加有效、更加灵活的处理实际问题。本文将粒子群算法与其他技术相结合提出了几种求解规划、聚类和调度问题的混合粒子群算法,并将这些算法与已知的算法进行了比较分析。针对单目标规划问题,将粒子群算法与微分进化算法相结合,提出了一种求解单目标非线性规划问题混合算法DE-PSO;针对多目标规划问题,将传统求解多目标规划问题的分解技术结合到粒子群算中,提出了MCPSO算法。针对聚类问题,将经典的K均值算法引入到粒子群算法中,提出了求解分割聚类问题PKPSO算法和求解动态聚类问题的DKPSO算法。针对流水车间作业调度问题,通过将局部搜索策略、遗传操作及退火策略结合到粒子群算法中,提出了求解单目标流水车间调度问题的SADPSO算法、HPGA算法、AHPSO算法及ATPPSO算法;针对多目标流水车间作业调度问题,将传统求解多目标规划问题的分解技术结合到粒子群算中,提出了MDPSO算法。混合元启发式算法是一个非常新的研究领域,目前对此领域的研究还尚处于初级阶段,本文的研究工作能够对该领域的研究起到促进作用。此外,还为求解这些实际问题提供了几种新的手段。因此,具有一定理论意义和实际价值。更多还原

【Abstract】 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.更多还原