基于改进粒子群算法的船舶排样问题研究

提出了一种改进的粒子群算法来解决船舶排样问题。该算法将混合蛙跳算法的分组思想引入简化粒子群算法中,粒子能够利用更丰富的信息进行更快地收敛。船舶排样零件形状虽多为不规则图形,但它可以转化为矩形件后再进行排样。剩余矩形排样法是解决矩形件排样问题的一种较好的启发式算法,它既满足BL条件又符合BLF算法的思想,这样就能够对排样过程中产生的空白间隙进行填充,保证了较高的板材利用率,有利于找到较优解。用此算法结合剩余矩形法对2组矩形件进行排样,达到了90%以上的利用率,均优于对比文献,表明了本文算法的有效性。

Research on ship layout problem based on improved particle swarm algorithm

An improved particle swarm optimization algorithm is proposed to solve the ship layout problem,which belongs to discrete problems. Combined SimplifiedParticle Swarm Optimization ( SPSO) and grouping idea of Shuffled Frog Leaping Optimization ( SFLA) ,the particles can converge faster with more infor-mation. Although most of ship layout parts' shapes are irregular graphics,they can be transformed into rectangular parts before layout. Surplus rectanglemethod is a better method in solving the packing problem of rectangles compared with other methods. It satisfies Bottom Left ( BL) condition and the thoughtof Bottom Left Fill ( BLF) algorithm and rectangles can fill out the blank space,thus it can ensure to get high ratio and can find a optimal solution easily.The utilizations of two groups of rectangular pieces layout tested by SFLA - SPSO combined with surplus rectangle method are above 90% ( better than refer-ences') ,which shows that the proposed algorithm is effective.