基于蚁群算法的玻璃切割控制系统
|
摘要
人工蚁群算法是对生物(蚂蚁)群体行为的模拟抽象，它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁穴至食物间最短路径这种集体寻优特征，该算法具有分布计算、信息正反馈和启发式搜索等特点。
玻璃由于其透明、透光、反射、多彩等特性，已经作为一种重要的建筑装饰材料被广泛应用到各个领域，而玻璃切割作为玻璃深加工的前道工序，其自动化程度的高低以及原料利用率的大小影响整个玻璃成品的成本。
玻璃排版的目标是通过计算机优化排样，减少排样工作量，简化切割工艺，加快排样速度，有效提高材料的利用率，降低产品成本。优化排样算法的研究不仅有充分的理论意义，也有很高的实用价值。
本文完成了玻璃切割系统的设计，通过计算机控制软件，优化玻璃自动排版，根据工艺控制流程对切割机进行控制，将玻璃原片加工成所需的一系列玻璃产品。
本文在简要介绍玻璃切割控制系统的基础上，重点研究了基于蚁群算法的玻璃优化排版设计和具体实现。主要内容包括：玻璃切割计算机控制系统软件的设计实现，包括工作界面的设置，以及各种加工数据的数据库设计及访问等；对于玻璃原材料的优化排版，主要讨论了基于蚁群算法的矩形玻璃件的排放，以及切割路径(旅行商)问题的自动优化排版系统的设计；采用图形预处理-排样-人机交互的方法，在较短的时间内对矩形件排样问题给出满意的解决方案。
Ant Colony System is the abstract simulation of biological (ants) group behaviors, such as transmitting simple information between the biological individual, and searching the shortest path between the food and the nest. ACS has advantages of distribution of computing, information feedback and the heuristic search feature.
Glass decorative material products have been great demand in daily life. The glass cutting is the pre- procedure of glass deep processing, and its degree of automation and utilization of raw materials glass is very important for the cost.
The purpose of glass typesetting is to optimize automatic typesetting, reduce load of work, simplify the cutting processes, speed up the pace of typesetting, improve the material utilization, and reduce the cost of products. The research is not only meaningful in theory, but also valuable in practice.
We accomplish the system of glass cutting, and with the control software, we can optimize glass automatic typesetting, control cutting machine, and process the original piece of glass into a range of glass products as required.
On the basis of the brief introduction about glass cutting control system, we focused on how to realize the optimized glass typesetting on the foundation of ACS. We have mainly done such jobs: the software design of glass cutting computer control system(including the work interface, and various database design and data processing visit), optimization typesetting of raw materials(mainly discussed the layout of rectangle glass pieces using ACS and cutting trails (TSP)offer a good result in short time).
玻璃由于其透明、透光、反射、多彩等特性，已经作为一种重要的建筑装饰材料被广泛应用到各个领域，而玻璃切割作为玻璃深加工的前道工序，其自动化程度的高低以及原料利用率的大小影响整个玻璃成品的成本。
玻璃排版的目标是通过计算机优化排样，减少排样工作量，简化切割工艺，加快排样速度，有效提高材料的利用率，降低产品成本。优化排样算法的研究不仅有充分的理论意义，也有很高的实用价值。
本文完成了玻璃切割系统的设计，通过计算机控制软件，优化玻璃自动排版，根据工艺控制流程对切割机进行控制，将玻璃原片加工成所需的一系列玻璃产品。
本文在简要介绍玻璃切割控制系统的基础上，重点研究了基于蚁群算法的玻璃优化排版设计和具体实现。主要内容包括：玻璃切割计算机控制系统软件的设计实现，包括工作界面的设置，以及各种加工数据的数据库设计及访问等；对于玻璃原材料的优化排版，主要讨论了基于蚁群算法的矩形玻璃件的排放，以及切割路径(旅行商)问题的自动优化排版系统的设计；采用图形预处理-排样-人机交互的方法，在较短的时间内对矩形件排样问题给出满意的解决方案。
Ant Colony System is the abstract simulation of biological (ants) group behaviors, such as transmitting simple information between the biological individual, and searching the shortest path between the food and the nest. ACS has advantages of distribution of computing, information feedback and the heuristic search feature.
Glass decorative material products have been great demand in daily life. The glass cutting is the pre- procedure of glass deep processing, and its degree of automation and utilization of raw materials glass is very important for the cost.
The purpose of glass typesetting is to optimize automatic typesetting, reduce load of work, simplify the cutting processes, speed up the pace of typesetting, improve the material utilization, and reduce the cost of products. The research is not only meaningful in theory, but also valuable in practice.
We accomplish the system of glass cutting, and with the control software, we can optimize glass automatic typesetting, control cutting machine, and process the original piece of glass into a range of glass products as required.
On the basis of the brief introduction about glass cutting control system, we focused on how to realize the optimized glass typesetting on the foundation of ACS. We have mainly done such jobs: the software design of glass cutting computer control system(including the work interface, and various database design and data processing visit), optimization typesetting of raw materials(mainly discussed the layout of rectangle glass pieces using ACS and cutting trails (TSP)offer a good result in short time).
引文
1 DORIGO. M , CAROG.D, GAMBARDELLA. Ant algorithms for discrete optimization.Artificial Life, 1999, 5(3) .137- 172.
2 COLORN IA, DOR IGO M , et al. Ant system for job- shop scheduling . Belgian Journal of Operations Research, Statis2tics and Computer Science (JORBEL ) .1994, 34. 39- 53.
3 M.Dorigo, V. Maniezzo ,Colomi. Ant system Optimization by a colony of cooperating agents. IEEE Trans on SMC,1996,26(1).28-41
4 Hwang, C. J, Kao. A knowledge-based approach to class scheduling problems with a developed system ACS. 1989,22(3).555 - 561
5 Twardowski, K.E.; Implementation of a genetic algorithm based associative classifier system (ACS) 1990,6(11) .48-54
6 Dorigo, M,Gambardella, L.M. Ant colony system, a cooperative learning approach to the traveling salesman problem. Evolutionary Computation, Volume 1, Issue 1, April 1997 .53-66
7 R Durbin,D Willshaw. An Analogue Approach to the Traveling Salesman Problem Using an Elastic Net Method.Nature,1987(326).689～691
8 J-L Deneubourg et al. The Self-Organizing Exploratory Pattern of the Argentine Ant.Insect Behavior, 1990(3). 159-168
9 M Resnick.Turtles,Termites,Taffic James. Combridge.MA.MIT press, 1994
10 N R Franks et al. The Blind Leading the Blind in Amy Ant Raid Patterns. Testing A Model of Self-Organization (Hymenoptera. Formicidae).Insect Behav,1991(4).583～607
11 W J Gutahr. A Generalized Convergence Result for the Graph-Based Ant System Metaheuristic. Probability in the Engineering and Informational Science, 2003(17).545～569
12 Christofides N , Whitlock C. An algorithm for two2dimensional cutting problems. Operations Research,1977,25.30-44.
13 Wang P Y. Two algorithms for const rained two2dimensional cutting stock problems. Operations Research, 1983,31 .573 - 586.
14 Dorigo M , Gambardella L M. Ant colony system. A cooperative learning approach to the t raveling salesman problem. IEEE Trans Evolut Comput ,1997 ,1 (1) .53 - 66.
15 Dorigo M , Maniezzo V , Colorni A. Ant system, optimization by a colony of cooperating agent s[J ]. IEEE Trans Systems, Man ,and Cybernetics2 Part B. Cybernetics , 1996 ,26 (1) .29 - 41.
16 Dorigo M, Gambardella L M. Ant colony system. A cooperative learning approach to the t raveling salesman problem [J]. IEEE Trans on Evolutionary Computations, 1997, 1 (1). 53～66.
17 M Dorigo and G Di Caro. The ant colony optimization met heuristic ,in .D. Corner ,M. Dorigo, F. Glover ,eds. New Ideas in Optimization. McGraw2Hill, London ,UK,1999.
18 M Dorigo ,Eric Bonabeau and Guy Therafluz. Ant Algorithm and Stimergy. Future Generation Computer Systems ,2000,16.851～871。
19 StutzleThomas,HoosHolger. H. Max-Min ant system Future Generation Computer System, 2000, 16(8).889-914
20 Wei Zhou,Meinel.C,Raja, V. H. A framework for supporting distributed access control policies, Computers and Communications, 2005.27(6)442-447
21 Dorigo, M. Gambardella, L. M. Ant colony system a cooperative learning approach to the traveling salesman problem Evolutionary Computation, 1997, 4(1) .53-66
22 Gomez, J. F. Khodr, H. M. De Oliveira, P. M. Ant colony system algorithm for the planning of primary distribution circuits, Power Systems.2004,19(5).996-1004
23 Jun Ouyang,Gui-Rong Yan. A multi-group ant colony system algorithm for TSP, Machine Learning and Cybernetics, Volume 1, 26-29 Aug. 2004.117-121
24 Cheng-Fa Tsai,Chun-Wei Tsai,Ching-Chang Tseng. A new approach for solving large traveling salesman problem, Evolutionary Computation. Volume 2, 12-17,May 2002.1636-1641
25 唐立山等．非数值并行算法(第一部)--模拟退火算法．北京：科学出版社，2000．
26 王爱虎．一种基于二叉树结构表达的矩形物体排样的启发式方法．软件学报．1996，4．252-257
27 李士勇．蚁群优化算法及其应用研究发展．计算机测量与控制，2003，11(12)．911～913，917
28 鄢烈祥．用列队竞争算法解旅行商问题．运筹与管理，1999，8(3)．24～30
29 丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合．计算机研究与发展，2003，40(9)．1531～1536
30 马良 旅行推销员问题的算法综合．教学的实践与认识，2000，30(2)：156～165
31 马良，王龙德．背包问题的蚂蚁优化算法．计算机应用，2001，21(8)．4～5
32 刘瑞杰，须文波．求解矩形件优化排料蚁群算法，江南大学学报，2005，4(1)，23～26
33 刘德全．矩形件排样问题的遗传算法求解．小型微型计算机系统，1998，19(12)：20～25．
34 龚志辉．基于遗传算法的矩形件优化排样系统研究．长沙：湖南大学，2003．21．
35 王宏达，尚久浩，樊养余．智能排样算法分析与展望．机电工程技术．2004，33(10)：9-12
36 陈义保，钟毅芳，张磊．基于蚁群系统的方案组合优化设计方法．机械设计与研究，2004，20(1)．13～16
37 陈崚，沈洁，秦玲．蚁群算法进行连续参数优化的新途径．系统工程理论与实践．2003，23(3)．48-53．
38 袁立，胡劲松，多线程蚁群算法及其在最短路问题上的应用研究．物流技术．2005，2．57～59
39 范辉，华臻，李晋江，点覆盖问题的蚂蚁算法求解．计算机工程与应用，2004．23．71～73
40 陈庆平．组合优化问题和神经网络组合优化计算方法探讨及应用．福州师专学报(自然科学版)，2001，21(2)．1～5．
41 胡小兵，袁锐，黄席樾，易继军，蚁群算法原理的仿真研究．计算机仿真，2004，21(8)：125～128
42 孟正大，郝立．开放式玻璃自动切割机计算机控制系统设计测控技术．2002．21(12)．26～30
2 COLORN IA, DOR IGO M , et al. Ant system for job- shop scheduling . Belgian Journal of Operations Research, Statis2tics and Computer Science (JORBEL ) .1994, 34. 39- 53.
3 M.Dorigo, V. Maniezzo ,Colomi. Ant system Optimization by a colony of cooperating agents. IEEE Trans on SMC,1996,26(1).28-41
4 Hwang, C. J, Kao. A knowledge-based approach to class scheduling problems with a developed system ACS. 1989,22(3).555 - 561
5 Twardowski, K.E.; Implementation of a genetic algorithm based associative classifier system (ACS) 1990,6(11) .48-54
6 Dorigo, M,Gambardella, L.M. Ant colony system, a cooperative learning approach to the traveling salesman problem. Evolutionary Computation, Volume 1, Issue 1, April 1997 .53-66
7 R Durbin,D Willshaw. An Analogue Approach to the Traveling Salesman Problem Using an Elastic Net Method.Nature,1987(326).689～691
8 J-L Deneubourg et al. The Self-Organizing Exploratory Pattern of the Argentine Ant.Insect Behavior, 1990(3). 159-168
9 M Resnick.Turtles,Termites,Taffic James. Combridge.MA.MIT press, 1994
10 N R Franks et al. The Blind Leading the Blind in Amy Ant Raid Patterns. Testing A Model of Self-Organization (Hymenoptera. Formicidae).Insect Behav,1991(4).583～607
11 W J Gutahr. A Generalized Convergence Result for the Graph-Based Ant System Metaheuristic. Probability in the Engineering and Informational Science, 2003(17).545～569
12 Christofides N , Whitlock C. An algorithm for two2dimensional cutting problems. Operations Research,1977,25.30-44.
13 Wang P Y. Two algorithms for const rained two2dimensional cutting stock problems. Operations Research, 1983,31 .573 - 586.
14 Dorigo M , Gambardella L M. Ant colony system. A cooperative learning approach to the t raveling salesman problem. IEEE Trans Evolut Comput ,1997 ,1 (1) .53 - 66.
15 Dorigo M , Maniezzo V , Colorni A. Ant system, optimization by a colony of cooperating agent s[J ]. IEEE Trans Systems, Man ,and Cybernetics2 Part B. Cybernetics , 1996 ,26 (1) .29 - 41.
16 Dorigo M, Gambardella L M. Ant colony system. A cooperative learning approach to the t raveling salesman problem [J]. IEEE Trans on Evolutionary Computations, 1997, 1 (1). 53～66.
17 M Dorigo and G Di Caro. The ant colony optimization met heuristic ,in .D. Corner ,M. Dorigo, F. Glover ,eds. New Ideas in Optimization. McGraw2Hill, London ,UK,1999.
18 M Dorigo ,Eric Bonabeau and Guy Therafluz. Ant Algorithm and Stimergy. Future Generation Computer Systems ,2000,16.851～871。
19 StutzleThomas,HoosHolger. H. Max-Min ant system Future Generation Computer System, 2000, 16(8).889-914
20 Wei Zhou,Meinel.C,Raja, V. H. A framework for supporting distributed access control policies, Computers and Communications, 2005.27(6)442-447
21 Dorigo, M. Gambardella, L. M. Ant colony system a cooperative learning approach to the traveling salesman problem Evolutionary Computation, 1997, 4(1) .53-66
22 Gomez, J. F. Khodr, H. M. De Oliveira, P. M. Ant colony system algorithm for the planning of primary distribution circuits, Power Systems.2004,19(5).996-1004
23 Jun Ouyang,Gui-Rong Yan. A multi-group ant colony system algorithm for TSP, Machine Learning and Cybernetics, Volume 1, 26-29 Aug. 2004.117-121
24 Cheng-Fa Tsai,Chun-Wei Tsai,Ching-Chang Tseng. A new approach for solving large traveling salesman problem, Evolutionary Computation. Volume 2, 12-17,May 2002.1636-1641
25 唐立山等．非数值并行算法(第一部)--模拟退火算法．北京：科学出版社，2000．
26 王爱虎．一种基于二叉树结构表达的矩形物体排样的启发式方法．软件学报．1996，4．252-257
27 李士勇．蚁群优化算法及其应用研究发展．计算机测量与控制，2003，11(12)．911～913，917
28 鄢烈祥．用列队竞争算法解旅行商问题．运筹与管理，1999，8(3)．24～30
29 丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合．计算机研究与发展，2003，40(9)．1531～1536
30 马良 旅行推销员问题的算法综合．教学的实践与认识，2000，30(2)：156～165
31 马良，王龙德．背包问题的蚂蚁优化算法．计算机应用，2001，21(8)．4～5
32 刘瑞杰，须文波．求解矩形件优化排料蚁群算法，江南大学学报，2005，4(1)，23～26
33 刘德全．矩形件排样问题的遗传算法求解．小型微型计算机系统，1998，19(12)：20～25．
34 龚志辉．基于遗传算法的矩形件优化排样系统研究．长沙：湖南大学，2003．21．
35 王宏达，尚久浩，樊养余．智能排样算法分析与展望．机电工程技术．2004，33(10)：9-12
36 陈义保，钟毅芳，张磊．基于蚁群系统的方案组合优化设计方法．机械设计与研究，2004，20(1)．13～16
37 陈崚，沈洁，秦玲．蚁群算法进行连续参数优化的新途径．系统工程理论与实践．2003，23(3)．48-53．
38 袁立，胡劲松，多线程蚁群算法及其在最短路问题上的应用研究．物流技术．2005，2．57～59
39 范辉，华臻，李晋江，点覆盖问题的蚂蚁算法求解．计算机工程与应用，2004．23．71～73
40 陈庆平．组合优化问题和神经网络组合优化计算方法探讨及应用．福州师专学报(自然科学版)，2001，21(2)．1～5．
41 胡小兵，袁锐，黄席樾，易继军，蚁群算法原理的仿真研究．计算机仿真，2004，21(8)：125～128
42 孟正大，郝立．开放式玻璃自动切割机计算机控制系统设计测控技术．2002．21(12)．26～30