Genetic algorithm with additional parameter for 2-dimensional irregular shape cutting problem

• Autorzy: Żak S.

Warianty tytułu

PL

Algorytm genetyczny z dodatkowym parametrem do wykroju elementów o nieregularnych kształtach z powierzchni dwuwymiarowych

• Języki publikacji: EN

Abstrakty

EN

The optimum cutting problems occur very frequently in various area of industry and technology. A number of algorithms were proposed, targeting solving particular variants of the aforementioned problems (guillotine cut, non-guillotine cut, etc.). In the article, we proposed and examined a genetic algorithm implementation with an additional parameter, allowing for optimization of the placement of individual elements with irregular shape profile on dimensional surface. The simulation results were presented, examining the impact of the combination of generic operators and the proposed additional parameter on the quality of the obtained results. An example of practical implementation of the examined algorithm in engineering applications is presented, thanks to the integration with the AutoDesk software package - AutoCAD 2007.

PL

Problemy optymalnego rozkroju bardzo często występują w różnych dziedzinach techniki. Opracowano liczne algorytmy pozwalające na rozwiązywanie szczegółowych wariantów tych problemów (rozkrój gilotynowy, niegilotynowy itp.). W artykule zaproponowano i przebadano algorytm genetyczny z dodatkowym parametrem pozwalający na optymalizację wykroju elementów o nieregularnych kształtach z powierzchni dwuwymiarowych. Przedstawiono wyniki symulacji, w trakcie których zbadano wpływ doboru standardowych operatorów genetycznych, jak i zaproponowanego dodatkowego parametru, który ma wpływ na jakość uzyskiwanych wyników. Przedstawiono również możliwość praktycznego użycia algorytmu w zastosowaniach inżynierskich dzięki integracji z programem AutoCAD 2007.

Słowa kluczowe

EN

2d irregular-shape; cutting; modified genetic algorithm; work automation; AutoCAD 2007

PL

automatyzacja pracy; AutoCAD 2007; rozkrój nieregularny; algorytm genetyczny; algorytm zmodyfikowany

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Mechanika
• Rocznik: 2008
• Tom: R. 105, z. 3-M
• Strony: 217--224
• Opis fizyczny: Bibliogr. 10 poz.,Tab., rys.,

Twórcy

autor

Żak S.

Bibliografia

• [1] Brooks R., Smith C.A.B., Stone A.H., Tutte W.T., The Dissection of Rectangles into Squares, Duke Math. Journal, Vol. 7, 1940.
• [2] Błażewicz J., Hawryluk P., Walkowiak R., Using a Tabu Search Approach for Solving the Two-Dimensional Irregular Cutting Problem, Annals of Operations Research, Vol. 41, 1993, 312-327.
• [3] Burke E., Hellier R., Graham K., Whitwell G., A New Bottom-Left-Fill Heuristics Algorithm for Two Dimensional Irregular Packing Problem, Operations Research, Vol. 54, No. 3, May–June 2006, 581-601.
• [4] Budzyńska L., Kominek P., Influence of Given Representation on Performance of an Evolutionary Algorithm for 2d Irregular-Shape Cutting Problem, Symposium on Methods of Artificial Intelligence, Gliwice, November 5–7 2003.
• [5] Budzyńska L., Kominek P., The Application of GLS Algorithm to 2 Dimensional Irregular-Shape Cutting Problem, Lecture Notes in Computer Science, Vol. 3038, Springer, Berlin 2004, 1241-1248.
• [6] Davis L., Applying Adaptive Algorithms to Epistatic Domains, Proceedings of the International Joint Conference on Artificial Intelligence, 1985.
• [7] Falkenauer E., Bouffouix , Genetic Algorithm for Job Shop, Proceedings of 1991 IEEE International Conference on Robotics and Automation, 1991.
• [8] Syswerda G., Schedule optimization Using Genetic Algorithms, Handbook of Genetic Algorithms, New York 1991.
• [9] Goldberg D.E., Lingle R., Alleles, Loci, and Travelling Salesman Problem, Proceedings of the First International Conference on Genetic Algorithms, Hillsdale, New York 1985.
• [10] Olivier L., Smith D., Holland J., A Study of Permutation Crossover on the Traveling Salesman Problem, Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, New York 1987.