Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Recenzirano
  • Hybrid-biased genetic algor...
    Luo, Qiang; Rao, Yunqing; Yang, Piaoruo; Zhao, Xusheng

    Computers & operations research, September 2024, 2024-09-00, Letnik: 169
    Journal Article

    •Solve the problem of packing unequal rectangles into a circular fixed size container.•Propose a biased genetic algorithm hybridized with a local search algorithm.•Improve the decoding procedure and analyze its time complexity.•Three new initial layouts and a new set of position evaluation rules are proposed.•Produce over half of new best solutions out of 108 benchmark instances. This study addresses the two-dimensional circular knapsack packing problem, which packs unequal rectangles into a circular container to maximize the number or the area of items packed. A biased genetic algorithm hybridized with a local search algorithm is proposed to solve the problem. The algorithm has a powerful global searching ability and is responsible for exploration, and a local search is applied for exploitation. Therefore, the proposed approach has an excellent search ability that can balance intensification and diversification well. A decoding procedure is proposed to transform the chromosome into a packing layout. The procedure first produces several initial layouts that contain a few rectangles, forms a complete layout for each initial layout, and selects the best one as the final packing layout. Three new types of initial layouts are considered. A new set of evaluation rules for the placement position and a random selection method are proposed. Computational experiments using two benchmark datasets showed that the evolutionary algorithm could provide better solutions than state-of-the-art algorithms from the literature, with 64 new best solutions out of 108 benchmark instances.