一种求解双层过道布置问题的离散花授粉算法

A Discrete Flower Pollination Algorithm for Solving Double-Layer Corridor Allocation Problem

结合布局活动中设施布置在多层空间的实际情况,对过道布置问题在双层空间中的布置优化进行研究,构建了一种新的混合整数非线性规划模型.基于可行解的离散性和问题求解的复杂性,提出一种花授粉算法离散方法.通过重新定义授粉过程,将以问题规模为搜索深度的随机搜索过程作为全局搜索,而在局部寻优阶段,个体以交换对的形式跟随最优解更新自身.为进一步提高算法性能,在全局搜索阶段引入临界值,通过变异陷入局部最优的个体实现变邻域搜索,并设置阈值以提高求解效率.通过对比改进前后两算法求解38个测试算例的运算结果,验证了算法改进的有效性.最后,应用改进离散花授粉算法求解原过道布置问题,并与不同算法的实验结果进行对比,发现所提算法在求解质量和效率方面更具优势.

Considering the situation that facilities are distributed into multi-layers space,a double layer corridor allocation problem was proposed,and the mixed-integer nonlinear programming model was built for this problem.Based on the discrepancy of feasible solutions and complexity of the issue,a discrete flower pollination algorithm was proposed.By redefining the pollination process,the random search process that sets the problem size as the search depth was taken as the global search.In the local optimization stage,the individual updated itself via the exchange pair by following the optimal solution.In order to improve the performance of the algorithm,the thresholds were set in the global search stage to actualize variable neighborhood search by mutating the individual that was in the local optimum,and another threshold was set to improve the efficiency of the solution.The effectiveness of the algorithm was validated by comparing the results that are gotten from two algorithms via solving the 38 benchmark instances.Finally,the improved flower pollination algorithm was applied to solve the corridor allocation problem,and the contrast experiments illustrate that the proposed algorithm possesses more advantages both in quality and efficiency.