基于人工鱼群算法的一维下料问题的研究
|
摘要
一维下料问题是一个经典的组合优化问题,属于NP-hard问题。怎样找到一种较好的下料方案,成为节约原材料,降低成本,从而提高企业的经济效益的重要问题之一。常用的求解一维下料问题的方法有分支定界法、动态规划法和整数规划法等方法。对于大规模的一维下料问题,许多专家尝试用遗传算法来求解,并取得了较为满意的结果。人工鱼群算法是一种新型的智能随机优化算法,它具有对目标函数、初始值和参数设定要求不高等特点。
本文就如何改进人工鱼群算法的性能及把该算法应用于一维下料问题中进行了研究。本文的主要工作和创新点可归纳如下:
1)针对人工鱼群算法的不足提出了三点改进方法。首先在算法进行的过程中,使人工鱼的视野由大逐渐变小,这样既能使算法跳出局部最优解又能提高收敛速度。其次通过对算法中觅食行为和聚群行为的改进来提高算法性能。通过两个测试函数的仿真试验表明了改进算法的有效性。
2)用人工鱼群算法来解决一维下料问题,对算法做了如下几方面的重新定义及调整:给出了解决一维下料问题的编码方法和初始化方法;重新定义了人工鱼群算法距离、邻域及中心的概念;对算法中觅食行为、聚群行为及追尾行为进行了适当的调整。通过两个数值试验证明采用人工鱼群算法解决下料问题是可行的,并且取得了较好的寻优效果。
The one-dimensional cutting problem belongs to the combination and optimization problem and NP-hard. Looking for an optimum cutting solution can not only save raw materials and decrease produce cost, but also is an efficient method to improve the utilization of materials and to increase the benefit of enterprises. The one-dimensional cutting problems are usually solved using branch-and-bound, dynamic programming or integer linear programming. When dealing with the cutting stock problems with both mass material and parts, experts try to using the artificial intelligence algorithms like genetic algorithm and achieved better results. The artificial fish swarm (AFSA) is a new stochastic optimization algorithm based on group intelligent, essentially is a complex intelligent system. It has no special requirement for object functions, being insensitive to the initial values, tolerating wide range of values of parameters.
The paper focuses on the improvement of AFSA algorithm and solving the one-dimensional cutting problem with the AFSA. The main achievements include:
1) After analyzing the disadvantage of AFSA, an improved artificial fish swarm algorithm is presented. Firstly, it dynamically adjusts the vision of artificial fish. The way improves the global searching ability and increases the searching speed of the algorithm. Secondly, the preying behavior and the swarming behavior are improved in the algorithm. The simulation results show that this method is an efficient algorithm for solving optimization problems of function.
2) In the paper, for solving the one-dimensional cutting problem with the AFSA, some parts of the AFSA are adjusted and redefined: the method of coding and initialization are introduced; the concepts of distance and center are redefined; the preying behavior, the swarming behavior and the following behavior are adjusted. Finally, the AFSA is applied to solve the one-dimensional cutting problem. The results demonstrate that the method is feasible and has the feature of high rate of convergence and high optimizing precision.
本文就如何改进人工鱼群算法的性能及把该算法应用于一维下料问题中进行了研究。本文的主要工作和创新点可归纳如下:
1)针对人工鱼群算法的不足提出了三点改进方法。首先在算法进行的过程中,使人工鱼的视野由大逐渐变小,这样既能使算法跳出局部最优解又能提高收敛速度。其次通过对算法中觅食行为和聚群行为的改进来提高算法性能。通过两个测试函数的仿真试验表明了改进算法的有效性。
2)用人工鱼群算法来解决一维下料问题,对算法做了如下几方面的重新定义及调整:给出了解决一维下料问题的编码方法和初始化方法;重新定义了人工鱼群算法距离、邻域及中心的概念;对算法中觅食行为、聚群行为及追尾行为进行了适当的调整。通过两个数值试验证明采用人工鱼群算法解决下料问题是可行的,并且取得了较好的寻优效果。
The one-dimensional cutting problem belongs to the combination and optimization problem and NP-hard. Looking for an optimum cutting solution can not only save raw materials and decrease produce cost, but also is an efficient method to improve the utilization of materials and to increase the benefit of enterprises. The one-dimensional cutting problems are usually solved using branch-and-bound, dynamic programming or integer linear programming. When dealing with the cutting stock problems with both mass material and parts, experts try to using the artificial intelligence algorithms like genetic algorithm and achieved better results. The artificial fish swarm (AFSA) is a new stochastic optimization algorithm based on group intelligent, essentially is a complex intelligent system. It has no special requirement for object functions, being insensitive to the initial values, tolerating wide range of values of parameters.
The paper focuses on the improvement of AFSA algorithm and solving the one-dimensional cutting problem with the AFSA. The main achievements include:
1) After analyzing the disadvantage of AFSA, an improved artificial fish swarm algorithm is presented. Firstly, it dynamically adjusts the vision of artificial fish. The way improves the global searching ability and increases the searching speed of the algorithm. Secondly, the preying behavior and the swarming behavior are improved in the algorithm. The simulation results show that this method is an efficient algorithm for solving optimization problems of function.
2) In the paper, for solving the one-dimensional cutting problem with the AFSA, some parts of the AFSA are adjusted and redefined: the method of coding and initialization are introduced; the concepts of distance and center are redefined; the preying behavior, the swarming behavior and the following behavior are adjusted. Finally, the AFSA is applied to solve the one-dimensional cutting problem. The results demonstrate that the method is feasible and has the feature of high rate of convergence and high optimizing precision.
引文
[1]Sweeney P. E., Partemoster E. R. Cutting and Packing Problems: a categorized application-orientated research[J]. Journal of Operational Research Society, 1992, 43(7): 691-706
[2]Haessler R. W., Sweeney P. E. Cutting Stock Problem and Solution Procedures[J]. European Journal of Operation of Research, 1991, 54: 141-150
[3]Chen Chuan-lung S., Hart Stephen M., Tham Wai Mui. A Simulated Annealing Heuristic for the One Dimensional Cutting Stock Problem[J]. European Journal of Operation Research 1996, 93: 522-535
[4]Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem[J]. Operations Research, 1961, 9: 849-859
[5]Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem[J]. Operations Research, 1963, 1: 863-888
[6]Gilmore P. C., Gomory R. E. Multistage cutting stock problems of two and more dimensions [J]. Operations Research, 1965, 13: 94-120
[7]Waesher G. An LP-based approach to cutting stock problems with multiple objectives[J]. European Journal of Operational Research, 1990, 44: 175-184
[8]Chauny F., Loulou R. LP-based method for the multi-sheet cutting stock problem[J]. INFOR, 1994, 32(4): 253-264
[9]Vance P. H., Barnhart C., Johnson E. L. Solving binary cutting stock problems by column generation and branch-and-bound[J]. Computational Optimization and Applications, 1994, 3(2): 111-130
[10]Carvalho J. M. V., Rodrigues A. J. G. An LP-based approach to a two-stage cutting stock problem[J]. European Journal of Operational Research, 1995, 84: 580-589
[11]Francois V. Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem[J]. Operations Research, INFORMS, 2000, 48(6): 915-926
[12]Zak E. J. Row and column generation technique for a multistage cutting stock problem[J]. Computers& Operations Research, 2002, 29(9): 1143-1156
[13]Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stockproblem with multiple stock lengths[J]. European Journal of Operational Research, Special Issue on Cutting and Packing, 2002, 14(12): 274-294
[14]Beasley J. E. An exact two-dimensional non-guillotine cutting tree search procedure[J]. Operations Research, 1985, 33(1): 49-64
[15]Chu C. B., Antonio J. Approximation algorithms to solve real-life multicriteria cutting stock problems[J]. Operations Research, 1999, 47(4): 495-508
[16]Chen C. L. S., Hart S. M., Tham W. M. Simulated annealing heuristic for the one-dimensional cutting stock problem[J]. European Journal of Operational Research, 1996, 93(3): 522-535
[17]Scholl A., Klein R. A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[J]. Computers& Operations Research, 1997, 347: 627-645
[18]Leung T. W., Yang C. H., Trout M. D. Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem[J]. Computers and Industrial Engineering, 2001, 40(3): 201-214
[19]曹炬,胡修彪.大规模矩形件优化排样的遗传算法[J].锻压机械, 1999, 4: 217-221
[20]聂义勇等.考虑库存余材利用的杆材下料方案[J].小型微型计算机系统. 2001, 22(7),830-832
[21]高尚,杨静宇.群智能算法及其应用[M].中国水利水电出版社. 2006
[22]王冬梅.群集智能优化算法的研究[D].湖北:武汉科技大学硕士学位论文, 2004
[23]Holland J. H. Adapation in natural and artificial systems[D]. Ann Arbor: University of Michigan Press, 1975
[24]Dorigo M., Maniezzo V., Colorni A. Ant System: Optimization by a colony of cooperating agents[J]. IEEE Trans on System, Man and Cybernetics-Part B, 1996, 26(1): 1-13
[25]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践, 2002, 22(11): 32-38
[26]李晓磊.一种新型的智能优化算法—人工鱼群算法[D].浙江:浙江大学, 2003
[27]罗方芳,陈国龙,郭文忠.基于改进的Fish-search算法的信息检索研究[J].福州大学学报(自然科学版), 2006, 34(2): 184-188
[28]张梅凤,邵诚,甘勇等.基于变异算子与模拟退火混合的人工鱼群优化算法[J].电子学报, 2006, 34(8): 1381-1385
[29]李亮,迟世春,林皋.禁忌鱼群算法及其在边坡稳定分析中的应用[J].工程力学, 2006, 23(3): 6-10
[30]Shan X. J., Jiang M. Y., Li J. P. The Routing Optimization Based on Improved Artificial Fish Swarm Algorithm[A]. Proceedings of the 6th World Congress on Intelligent Control and Automation[C], 2006: 3658-3662
[31]Zhang M. F., Shao C., Li M. J. Mining Classification Rule with Artificial Fish Swarm[A]. Proceedings of the World Congress on Intelligent Control and Automation[C], 2006: 5877-5881
[32]Li C., Wang S. L. Next-Day Power Market Clearing Price Forecasting Using Artificial Fish-Swarm Based Neural Network[A]. Third International Symposium on Neural Networks, ISNN 2006, Proceedings-Part II[C], 2006: 1290-1295
[33]Wang X. W., Gao N., Huang M. An Artificial Fish Swarm Algorithm Based and ABC Supported Qos Unicast Routing Scheme in NGI[A]. ISPA2006[C], LNCS4331: 205-214
[34]Wang D. D., Zhou Y. Q., Cao D. Q. Artificial fish-school algorithm for solving nonlinear equations[J]. Journal of Information and Computational Science, March, 2007: 281-289
[35]周石林.一维下料问题的研究[D].江苏:南京航空航天大学, 2000
[36]Haessler R. W. A note on computational modification to the Gilmore-Gomory cutting stock algorithm[J]. Operations Research, 1980, 28(4): 1001-1005
[37]Valerio D. E., Carvalho J. M. Exact solution of cutting stock problems using column generation and branch and bound[J]. Int. Trans. Opl Res, 1998, 5(1): 35-44
[38]Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems[J]. Math. Program, 1999(86): 565-594
[39]Haessler R. W. Controlling Cutting Pattern Changes in One-Dimensional rim Problem[J], Operations Research, 1975, 23(3): 483-493
[40]Vahrenkamp R. Random search in the one-dimensional cutting stock problem[J], European Journal of Operational Research, 1996(95): 191-200
[41]Wagner, B. J. A genetic algorithm solution for one-dimensional bundled stock cutting[J]. European Journal of Operational Research, 1999: 368-381
[42]Gelenbe E., Schmajuk N., Staddon J., et al. Autonomous search by robots and animals: A survey[J], Robotics and Autonomous Systems, 1997(22): 23-34
[43]Reynolds C. W. Flocks, herds, schools: a distributed behavioral model[A]. Proceeding of SIGGRAPH’87[C]. Anaheim, California. Computer Graphics 1987, 21(4): 25-34
[44]Yu Y., Tian Y. F., Yin Z. F. Multiuser Detector Based on Adaptive Artificial Fish School Algorithm. Proc[J], IEEE Int. Symp. on Communications and Information Technology, 2005: 1480-1484
[45]黄华娟,周永权.改进型人工鱼群算法及复杂函数全局优化方法[J].广西师范大学学报(自然科学版), 2008,26(1): 194-197
[46]范玉军,王冬冬,孙明明.改进的人工鱼群算法[J].重庆师范大学学报(自然科学版), 2007, 24(3): 23-26
[47]张梅凤,邵诚.多峰函数优化的生境人工鱼群算法[J].控制理论与应用, 2008, 25(4): 773-776
[48]Ahuja R. K., Ergun O, et al. A survey of very large-scale neighborhood search techniques[J]. Discrete Applied Mathematics, 2002(123): 75-102
[49]Ahuja R. K., Orlin J. B., Sharma D. Very large-scale neighborhood search[J], International Transactions in Operational Research, 2000(7): 301-317
[2]Haessler R. W., Sweeney P. E. Cutting Stock Problem and Solution Procedures[J]. European Journal of Operation of Research, 1991, 54: 141-150
[3]Chen Chuan-lung S., Hart Stephen M., Tham Wai Mui. A Simulated Annealing Heuristic for the One Dimensional Cutting Stock Problem[J]. European Journal of Operation Research 1996, 93: 522-535
[4]Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem[J]. Operations Research, 1961, 9: 849-859
[5]Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem[J]. Operations Research, 1963, 1: 863-888
[6]Gilmore P. C., Gomory R. E. Multistage cutting stock problems of two and more dimensions [J]. Operations Research, 1965, 13: 94-120
[7]Waesher G. An LP-based approach to cutting stock problems with multiple objectives[J]. European Journal of Operational Research, 1990, 44: 175-184
[8]Chauny F., Loulou R. LP-based method for the multi-sheet cutting stock problem[J]. INFOR, 1994, 32(4): 253-264
[9]Vance P. H., Barnhart C., Johnson E. L. Solving binary cutting stock problems by column generation and branch-and-bound[J]. Computational Optimization and Applications, 1994, 3(2): 111-130
[10]Carvalho J. M. V., Rodrigues A. J. G. An LP-based approach to a two-stage cutting stock problem[J]. European Journal of Operational Research, 1995, 84: 580-589
[11]Francois V. Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem[J]. Operations Research, INFORMS, 2000, 48(6): 915-926
[12]Zak E. J. Row and column generation technique for a multistage cutting stock problem[J]. Computers& Operations Research, 2002, 29(9): 1143-1156
[13]Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stockproblem with multiple stock lengths[J]. European Journal of Operational Research, Special Issue on Cutting and Packing, 2002, 14(12): 274-294
[14]Beasley J. E. An exact two-dimensional non-guillotine cutting tree search procedure[J]. Operations Research, 1985, 33(1): 49-64
[15]Chu C. B., Antonio J. Approximation algorithms to solve real-life multicriteria cutting stock problems[J]. Operations Research, 1999, 47(4): 495-508
[16]Chen C. L. S., Hart S. M., Tham W. M. Simulated annealing heuristic for the one-dimensional cutting stock problem[J]. European Journal of Operational Research, 1996, 93(3): 522-535
[17]Scholl A., Klein R. A fast hybrid procedure for exactly solving the one-dimensional bin packing problem[J]. Computers& Operations Research, 1997, 347: 627-645
[18]Leung T. W., Yang C. H., Trout M. D. Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem[J]. Computers and Industrial Engineering, 2001, 40(3): 201-214
[19]曹炬,胡修彪.大规模矩形件优化排样的遗传算法[J].锻压机械, 1999, 4: 217-221
[20]聂义勇等.考虑库存余材利用的杆材下料方案[J].小型微型计算机系统. 2001, 22(7),830-832
[21]高尚,杨静宇.群智能算法及其应用[M].中国水利水电出版社. 2006
[22]王冬梅.群集智能优化算法的研究[D].湖北:武汉科技大学硕士学位论文, 2004
[23]Holland J. H. Adapation in natural and artificial systems[D]. Ann Arbor: University of Michigan Press, 1975
[24]Dorigo M., Maniezzo V., Colorni A. Ant System: Optimization by a colony of cooperating agents[J]. IEEE Trans on System, Man and Cybernetics-Part B, 1996, 26(1): 1-13
[25]李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践, 2002, 22(11): 32-38
[26]李晓磊.一种新型的智能优化算法—人工鱼群算法[D].浙江:浙江大学, 2003
[27]罗方芳,陈国龙,郭文忠.基于改进的Fish-search算法的信息检索研究[J].福州大学学报(自然科学版), 2006, 34(2): 184-188
[28]张梅凤,邵诚,甘勇等.基于变异算子与模拟退火混合的人工鱼群优化算法[J].电子学报, 2006, 34(8): 1381-1385
[29]李亮,迟世春,林皋.禁忌鱼群算法及其在边坡稳定分析中的应用[J].工程力学, 2006, 23(3): 6-10
[30]Shan X. J., Jiang M. Y., Li J. P. The Routing Optimization Based on Improved Artificial Fish Swarm Algorithm[A]. Proceedings of the 6th World Congress on Intelligent Control and Automation[C], 2006: 3658-3662
[31]Zhang M. F., Shao C., Li M. J. Mining Classification Rule with Artificial Fish Swarm[A]. Proceedings of the World Congress on Intelligent Control and Automation[C], 2006: 5877-5881
[32]Li C., Wang S. L. Next-Day Power Market Clearing Price Forecasting Using Artificial Fish-Swarm Based Neural Network[A]. Third International Symposium on Neural Networks, ISNN 2006, Proceedings-Part II[C], 2006: 1290-1295
[33]Wang X. W., Gao N., Huang M. An Artificial Fish Swarm Algorithm Based and ABC Supported Qos Unicast Routing Scheme in NGI[A]. ISPA2006[C], LNCS4331: 205-214
[34]Wang D. D., Zhou Y. Q., Cao D. Q. Artificial fish-school algorithm for solving nonlinear equations[J]. Journal of Information and Computational Science, March, 2007: 281-289
[35]周石林.一维下料问题的研究[D].江苏:南京航空航天大学, 2000
[36]Haessler R. W. A note on computational modification to the Gilmore-Gomory cutting stock algorithm[J]. Operations Research, 1980, 28(4): 1001-1005
[37]Valerio D. E., Carvalho J. M. Exact solution of cutting stock problems using column generation and branch and bound[J]. Int. Trans. Opl Res, 1998, 5(1): 35-44
[38]Vanderbeck F. Computational study of a column generation algorithm for bin packing and cutting stock problems[J]. Math. Program, 1999(86): 565-594
[39]Haessler R. W. Controlling Cutting Pattern Changes in One-Dimensional rim Problem[J], Operations Research, 1975, 23(3): 483-493
[40]Vahrenkamp R. Random search in the one-dimensional cutting stock problem[J], European Journal of Operational Research, 1996(95): 191-200
[41]Wagner, B. J. A genetic algorithm solution for one-dimensional bundled stock cutting[J]. European Journal of Operational Research, 1999: 368-381
[42]Gelenbe E., Schmajuk N., Staddon J., et al. Autonomous search by robots and animals: A survey[J], Robotics and Autonomous Systems, 1997(22): 23-34
[43]Reynolds C. W. Flocks, herds, schools: a distributed behavioral model[A]. Proceeding of SIGGRAPH’87[C]. Anaheim, California. Computer Graphics 1987, 21(4): 25-34
[44]Yu Y., Tian Y. F., Yin Z. F. Multiuser Detector Based on Adaptive Artificial Fish School Algorithm. Proc[J], IEEE Int. Symp. on Communications and Information Technology, 2005: 1480-1484
[45]黄华娟,周永权.改进型人工鱼群算法及复杂函数全局优化方法[J].广西师范大学学报(自然科学版), 2008,26(1): 194-197
[46]范玉军,王冬冬,孙明明.改进的人工鱼群算法[J].重庆师范大学学报(自然科学版), 2007, 24(3): 23-26
[47]张梅凤,邵诚.多峰函数优化的生境人工鱼群算法[J].控制理论与应用, 2008, 25(4): 773-776
[48]Ahuja R. K., Ergun O, et al. A survey of very large-scale neighborhood search techniques[J]. Discrete Applied Mathematics, 2002(123): 75-102
[49]Ahuja R. K., Orlin J. B., Sharma D. Very large-scale neighborhood search[J], International Transactions in Operational Research, 2000(7): 301-317