Extension Of Particle Swarm Algorithm For Constrained Layout Optimization

This dissertation supported by two NSFC projects makes an extensive research on Parti-cle Swarm Optimization Algorithm (PSO) against the background of performance constrained layout optimization problems (CLOP). The constrained layout problems are widely seen in the industrial fields, such as nesting problems with cutter-path constraint, loading problems with stability constraint, and packing problems with equilibrium constraint against the satellite mod-ule layout optimization. Constrained layout optimization problems are known as a complex combinatorial optimization. Theoretical research and practical application have shown it is im-portant challenges for us because of both the combinatorial explosion in mathematics and the complexity in engineering system. To solve these challenges, it is required to not only provide effective solution algorithms aimed at CLOP, but also make full use of the human intelligence and knowledge-based method in order to make full use of their respective advantages from al-gorithms and knowledge (including human wisdom).This dissertation firstly deeply analyzes search mechanism and convergence of PSO that would be helpful for constructing extended PSO algorithms. Then we introduce the algorithm for rough set reduction and multi-knowledge extraction to obtain layout knowledge. Last, we integrate the layout knowledge into the scatter search algorithm form a Knowledge-based Scat-ter Search (KbSS) for layout optimization problem. The main contributions are described as follows:Swarm Intelligence is an innovative distributed intelligent paradigm whereby the collective behaviors of unsophisticated individuals interacting locally with their environment cause coher-ent functional global patterns to emerge. Although the swarm algorithms have exhibited good performance across a wide range of application problems, it is difficult to analyze the conver-gence. In this thesis, we discuss the dynamic trajectory and convergence of the swarm intelligent model namely the particle swarm algorithm. We explore the tradeoff between exploration and exploitation using differential analysis and Laplace transform. The trajectories are parsed into first-order inertial element and second-order oscillation element. Their transfer functions are derived, and the trajectories are described in explicit time functions. The first-order inertial element is helpful to maintain the trajectory's stability and algorithm convergence, while the second-order oscillation element trends to explore some new search spaces for the better solu-tions. The convergence regions of the swarm system are analyzed using the spectral radius and Lyapunov second theorem on stability.Finding reducts is one of the key problems in the increasing applications of rough set theory, which is also one of the bottlenecks of the rough set methodology. The population-based reduc-tion approaches are attractive to find multiple reducts in the decision systems, which could be applied to generate multi-knowledge and to improve decision accuracy. In this thesis, we design a particle swarm optimization algorithm (PSO) for rough set reduction and multi-knowledge ex-traction. It is a swarm-based search approach, in which different individual trends to be encoded to different reduct. The approach discovers the best feature combinations in an efficient way to observe the change of positive region as the particles proceed throughout the search space. The performance of our approach is evaluated and compared with Genetic Algorithms (GA). Empirical results illustrate that the approach can be applied for multiple reduct problems and multi-knowledge extraction effectively.For solving the equilibrium-constrained circles packing problem with the background of layout design, this thesis presents a knowledge-based scatter search algorithm (KbSS). In the algorithm, the swarm-based multi-knowledge is extracted through rough set theory, and scatter search is applied as an open framework for the knowledge fusion. Experiment results show the approach is feasible and effective. Scatter search-based knowledge extraction has good perfor-mance, since the knowledge extraction provides a combination of high-quality solutions and diversity of solutions in the search process. It is more effective to avoid falling into premature or jump out of local traps, which could improve the stability of the algorithm. So the algorithm can maintain more balance for its local and global search capabilities, which is helpful for the search process to jump from the local minima of the neighborhood to the global optimal solution with high accuracy.