Multi-agent Evolutionary Algorithm For Floorplanning And Three-dimensinoal Bin Packing Problem

In every aspect of human activities, we often encounter the Bin Packing Problem(BPP), such as transport loading problems, manufacturing cutting issues, placement problems and so on. The BPP is a combinatorial optimization problem and its reasonable solution can largely save resources and reduce losses. The BPP belongs to NP-Hard problems and traditional precise algorithms will lead to the combinatorial explosion of calculation. Therefore, the heuristic method is preferred to theoretical research and practical application.The BPP in our life varies because of the difference in load constraints and optimization objectives. Placement scheme, the decoding algorithm, is the core part of the BPP. At present, the BPP in research includes two main aspects: Two-dimensional Bin Packing Problem(2D-BPP) and Three-dimensional Bin Packing Problem(3D-BPP). Scholars have conducted lots of researches on the 2D-BPP and proposed some effective heuristic algorithms. Many decoding algorithms of the 3D-BPP are extended from the decoding algorithms of the 2D-BPP. So, in order to study the 3D-BPP, we must understand the decoding method 2D-BPP. Floorplanning in Very Large Scale Integration(VLSI) is a special case of the 2D-BPP. Therefore, this paper designs a VLSI floorplanning algorithm firstly. Then it extends the algorithm to the 3D-BPP. Optimization algorithms used in this paper include the Multi-agent Particle Swarm Optimization(MAPSO) and the Multi-agent Genetic Algorithm(MAGA). Here is the main work of this paper:1. The Moving Block Sequence(MBS) is used to be a new decoding algorithm for floorplanning in VLSI. The MBS is a non-slicing representation of layout. Owning to its search convex space, the MBS provides a platform for the design of cross-operator. It needs smaller storage compared to the existing methods and ensures left-bottom tight layout. Traditional PSO has advantages of its universal、robust and parallel computing. Inoder to make the best use of every individual’s features, this paper combines the MBS and the MAPSO to compose an algorithm, called Multi-agent Genetic Algorithm based on Multi-agent Particle Swarm Optimization(MAPSO-MBS). The MAPSO-MBS is tested by MCNC and GSRC and it gets a good result.2. The MBS which is applicable to the 2D-BPP is improved to an algorithm named Three-dimensional Moving Block Sequence(3DMBS). The paper extends the 3DMBS to the unconstrained the 3D-BPP, using the 3DMBS as the decoding algorithm of the 3D-BPP. The 3DMBS needs small storage compared, and it provides a convenient for the optimization algorithm. The algorithm can achieve optimal results.3. For the 3D-BPP, due to the actual need, to seek a reasonable and effecitive placement strategy remains an important research. In the process of solving optimization problems, MAGA has great potential. By the combination of the 3DMBS and the MAGA, this paper forms a new algorithm named Multi-agent Genetic Algorithm based on Three-dimensional Moving Block Sequence(MAGA-3DMBS). The MAGA-3DMBS is tested by randomly generated data and it gets a good result.