Original Title: A Hybrid Genetic Algorithms and Tabu Search for Solving an Irregular Shape Strip Packing Problem
Source: li01.tci-thaijo.org
Disclaimer: Summary generated by AI based on the provided document. Please refer to the original paper for full scientific accuracy.

ក្បួនដោះស្រាយហ្សេនេទិក និងការស្វែងរក Tabu បែបកូនកាត់សម្រាប់ដោះស្រាយបញ្ហានៃការវេចខ្ចប់បន្ទះដែលមានរូបរាងមិនទៀងទាត់

ចំណងជើងដើម៖ A Hybrid Genetic Algorithms and Tabu Search for Solving an Irregular Shape Strip Packing Problem

អ្នកនិពន្ធ៖ Kittipong Ekkachai (Department of Electronic, National Electronics and Computer Technology Center, Thailand), Pradondet Nilagupta (Department of Computer Engineering, Kasetsart University, Thailand)

ឆ្នាំបោះពុម្ព៖ 2003 Kasetsart J. (Nat. Sci.)

វិស័យសិក្សា៖ Computer Science

១. សេចក្តីសង្ខេបប្រតិបត្តិ (Executive Summary)

បញ្ហា (The Problem)៖ ឯកសារនេះដោះស្រាយបញ្ហានៃការវេចខ្ចប់បន្ទះដែលមានរូបរាងមិនទៀងទាត់ (Irregular shape strip packing problem) ដើម្បីស្វែងរកការរៀបចំដ៏ល្អបំផុតដែលកាត់បន្ថយប្រវែងធុងឱ្យនៅខ្លីបំផុត ដែលជាបញ្ហាជួបប្រទះញឹកញាប់ក្នុងឧស្សាហកម្មវាយនភ័ណ្ឌ និងការកាត់លោហៈ។

វិធីសាស្ត្រ (The Methodology)៖ ការស្រាវជ្រាវនេះបានស្នើឡើងនូវវិធីសាស្ត្រកូនកាត់ដែលរួមបញ្ចូលគ្នានូវក្បួនដោះស្រាយហ្សេនេទិក (Genetic Algorithms) និងការស្វែងរក Tabu (Tabu Search) ដោយប្រើប្រាស់គំរូពហុកោណដែលមិនស៊ីគ្នា (No-fit polygon) ដើម្បីស្វែងរកទីតាំងរៀបចំដ៏ប្រសើរបំផុត។

ក្បួនដោះស្រាយហ្សេនេទិក (Genetic Algorithms)
ការស្វែងរកតាមបែប Tabu (Tabu Search)
ពហុកោណដែលមិនស៊ីគ្នា (No-fit polygon)
លក្ខណៈវិនិច្ឆ័យនៃការដាក់ជាពហុដំណាក់កាល (Multi-phase placement criteria)

លទ្ធផលសំខាន់ៗ (The Verdict)៖

វិធីសាស្ត្រកូនកាត់មានដំណើរការដូចក្បួនដោះស្រាយហ្សេនេទិកនៅដំណាក់កាលដំបូងសម្រាប់ការស្វែងរកបែបពង្រីក បន្ទាប់មកវាសម្របខ្លួនបន្តិចម្តងៗរហូតដល់មានដំណើរការដូចការស្វែងរក Tabu នៅដំណាក់កាលចុងក្រោយ។
តាមរយៈការធ្វើតេស្តលើទិន្នន័យពហុកោណប៉ោងចំនួន ១៣ វិធីសាស្ត្រកូនកាត់ផ្តល់លទ្ធផលល្អជាងក្បួនដោះស្រាយហ្សេនេទិកពី ២,៥៦% ទៅ ៤,៦៩%។
វិធីសាស្ត្រកូនកាត់នេះក៏ទទួលបានលទ្ធផលនៃការវេចខ្ចប់ល្អប្រសើរជាងការប្រើប្រាស់តែការស្វែងរក Tabu ទូទៅពី ០,២៦% ទៅ ២,៧៨% ផងដែរ។

២. ការវិភាគលើប្រសិទ្ធភាព និងដែនកំណត់ (Performance & Constraints)

វិធីសាស្ត្រ (Method)	គុណសម្បត្តិ (Pros)	គុណវិបត្តិ (Cons)	លទ្ធផលគន្លឹះ (Key Result)
Genetic Algorithms (GA) ក្បួនដោះស្រាយហ្សេនេទិក	មានសមត្ថភាពធ្វើឱ្យដំណោះស្រាយប្រសើរឡើងយ៉ាងឆាប់រហ័សនៅដំណាក់កាលដំបូងនៃការស្វែងរក។	មិនសូវមានប្រសិទ្ធភាពសម្រាប់ពហុកោណដែលស្មុគស្មាញ ហើយការធ្វើឱ្យប្រសើរឡើងមានសភាពយឺតនៅដំណាក់កាលក្រោយ។	ផ្តល់ការប្រើប្រាស់សម្ភារៈបានប្រហែល 73.67% ទៅ 77.62% និងមានប្រវែងធុងវែងជាងគេ (លទ្ធផលខ្សោយជាងគេក្នុងចំណោមវិធីទាំង៣)។
Tabu Search (TS) ការស្វែងរក Tabu	មានល្បឿនលឿន និងស្វែងរកដំណោះស្រាយថ្មីពីតំបន់ជុំវិញនៃដំណោះស្រាយបច្ចុប្បន្នបានល្អជាង GA នៅដំណាក់កាលចុងក្រោយ។	គុណភាពនៃដំណោះស្រាយពឹងផ្អែកខ្លាំងទៅលើចំណុចចាប់ផ្តើមដែលត្រូវបានជ្រើសរើសដោយចៃដន្យ (Random start)។	ផ្តល់លទ្ធផលល្អជាង GA តែនៅចាញ់ក្បួនដោះស្រាយកូនកាត់ ដោយអត្រាប្រើប្រាស់សម្ភារៈស្ថិតចន្លោះ 75.92% ទៅ 79.33%។
Hybrid GA/TS ក្បួនដោះស្រាយកូនកាត់ GA/TS	រួមបញ្ចូលចំណុចខ្លាំងរបស់ GA និង TS ដោយពង្រីកការស្វែងរកនៅដំណាក់កាលដំបូង និងផ្តោតលើការកែលម្អលម្អិតនៅដំណាក់កាលចុងក្រោយ (Self-adapting)។	ត្រូវការពេលក្នុងការរចនាកូដស្មុគស្មាញ និងទាមទារការកំណត់ប៉ារ៉ាម៉ែត្រត្រឹមត្រូវ (Parameter tuning) ដើម្បីទទួលបានប្រសិទ្ធភាពខ្ពស់។	ផ្តល់លទ្ធផលល្អបំផុត ដោយយកឈ្នះ GA (2.56%-4.69%) និង TS (0.26%-2.78%) ជាមួយនឹងការប្រើប្រាស់សម្ភារៈរហូតដល់ 76.89% - 80.07%។

ការចំណាយលើធនធាន (Resource Cost)៖ ការស្រាវជ្រាវនេះមិនទាមទារធនធានកុំព្យូទ័រធំដុំនោះទេ ដោយសារការសាកល្បងត្រូវបានធ្វើឡើងនៅលើកុំព្យូទ័រជំនាន់ចាស់ ដែលអាចដំណើរការបានយ៉ាងងាយស្រួលនៅលើកុំព្យូទ័របច្ចុប្បន្ន។

Hardware: កុំព្យូទ័រ PC ដែលមាន CPU Intel Celeron 2.0 GHz និង RAM 256 MB (កុំព្យូទ័រយួរដៃធម្មតានៅពេលបច្ចុប្បន្នអាចដំណើរការបានយ៉ាងរលូន និងលឿនជាងមុនឆ្ងាយ)។
Software: ប្រព័ន្ធប្រតិបត្តិការ Windows 2000 (ឬជំនាន់ថ្មីជាង) និងកម្មវិធីសរសេរកូដសម្រាប់អនុវត្តក្បួនដោះស្រាយ (ឧទាហរណ៍ C++ ឬ Python សម្រាប់ Computation Geometry)។
Dataset: សំណុំទិន្នន័យគំរូរបស់ Kendall ដែលមានបំណែកពហុកោណប៉ោង (Convex polygon) ចំនួន 13, 26, 39, និង 52 ដុំ។
Expertise: ចំណេះដឹងស៊ីជម្រៅផ្នែកក្បួនដោះស្រាយម៉ាស៊ីន (Meta-heuristics) ធរណីមាត្រកុំព្យូទ័រ (Computational Geometry) និងការគណនា No-fit polygon (NFP)។

៣. ការពិនិត្យសម្រាប់បរិបទកម្ពុជា/អាស៊ីអាគ្នេយ៍

ភាពលំអៀងនៃទិន្នន័យ (Data Bias)៖

ការសិក្សានេះពឹងផ្អែកជាចម្បងទៅលើសំណុំទិន្នន័យគំរូស្តង់ដារ (Benchmark datasets) ដូចជា Kendall ដែលមានរូបរាងពហុកោណទ្រឹស្តីច្រើនជាងទិន្នន័យជាក់ស្តែងពីឧស្សាហកម្ម។ សម្រាប់ប្រទេសកម្ពុជា ការខ្វះខាតទិន្នន័យជាក់ស្តែងពីរោងចក្រក្នុងស្រុក (ដូចជារូបរាងពុម្ពខោអាវ ឬដែក) អាចធ្វើឱ្យលទ្ធផលពេលយកមកអនុវត្តជាក់ស្តែងមានការប្រែប្រួល។ ទោះយ៉ាងណា ក្បួនដោះស្រាយនេះជាមូលដ្ឋានគ្រឹះដ៏ល្អដែលអាចបត់បែនបាន។

លទ្ធភាពនៃការអនុវត្ត (Applicability)៖

វិធីសាស្ត្រនេះមានសក្តានុពលខ្ពស់ខ្លាំងក្នុងការជួយកាត់បន្ថយការខ្ជះខ្ជាយវត្ថុធាតុដើមនៅក្នុងវិស័យឧស្សាហកម្មសំខាន់ៗមួយចំនួននៅកម្ពុជា។

វិស័យកាត់ដេរសម្លៀកបំពាក់ និងស្បែកជើង (Garment and Footwear Industry): កម្ពុជាមានរោងចក្រកាត់ដេររាប់រយ។ ការយកក្បួនដោះស្រាយនេះ (Nesting Algorithm) មកប្រើក្នុងការរៀបចំប្លង់កាត់ក្រណាត់ នឹងជួយកាត់បន្ថយក្រណាត់សំណល់ សន្សំសំចៃថវិកាបានរាប់លានដុល្លារ និងបង្កើនល្បឿននៃការងារកាត់។
ឧស្សាហកម្មកាត់លោហៈ និងកញ្ចក់ (Metal and Glass Cutting): នៅតាមរោងជាង និងរោងចក្រផលិតសម្ភារៈសំណង់ ការរៀបចំប្លង់កាត់បន្ទះដែក ឬកញ្ចក់ឱ្យមានប្រសិទ្ធភាពជួយកាត់បន្ថយការខាតបង់សម្ភារៈដែលនៅសល់ (Scrap generation) ព្រោះវត្ថុធាតុដើមទាំងនេះមានតម្លៃថ្លៃ។
រោងចក្រផលិតគ្រឿងសង្ហារិម (Furniture Manufacturing): ការកាត់បន្ទះឈើក្តារបន្ទះ (Plywood) ដើម្បីបង្កើតជារូបរាងផ្សេងៗសម្រាប់គ្រឿងសង្ហារិម អាចប្រើប្រាស់ក្បួននេះដើម្បីទាញយកប្រយោជន៍អតិបរមាពីឈើមួយសន្លឹក និងកាត់បន្ថយការកាប់បំផ្លាញព្រៃឈើតាមរយៈការប្រើប្រាស់ឈើឱ្យអស់លទ្ធភាព។

សរុបមក ការធ្វើសមាហរណកម្មក្បួនដោះស្រាយ Optimization ទាំងនេះទៅក្នុងប្រព័ន្ធកុំព្យូទ័ររបស់រោងចក្រ នឹងជួយជំរុញឱ្យវិស័យកម្មន្តសាលនៅកម្ពុជាមានការប្រកួតប្រជែងខ្ពស់ និងចំណាយថ្លៃដើមទាប។

៤. ផែនការសកម្មភាពសម្រាប់និស្សិត (Actionable Roadmap)

ដើម្បីអនុវត្តតាមការសិក្សានេះ និស្សិតគួរអនុវត្តតាមជំហានខាងក្រោម៖

សិក្សាមូលដ្ឋានគ្រឹះនៃទិន្នន័យធរណីមាត្រ (Computational Geometry): និស្សិតគួរស្វែងយល់ពីរបៀបតំណាងរូបរាងពហុកោណ (Polygons) ជាទិន្នន័យឌីជីថល និងរៀនសរសេរកូដដើម្បីគណនា No-fit polygon (NFP) ឬ Minkowski's difference។ អាចប្រើប្រាស់បណ្ណាល័យ Shapely នៅក្នុង Python ដើម្បីចាប់ផ្តើមអនុវត្តការគណនាទាំងនេះ។
ស្ថាបនាក្បួនដោះស្រាយហ្សេនេទិកជាមូលដ្ឋាន (Basic Genetic Algorithms): សរសេរកូដបង្កើត Genetic Algorithm ផ្ទាល់ខ្លួនទូទៅសម្រាប់ការរៀបចំបំណែក (Packing)។ គួរចាប់ផ្តើមសាកល្បងជាមួយរូបរាងងាយៗដូចជាចតុកោណកែងសិន មុននឹងឈានទៅដោះស្រាយបញ្ហារូបរាងមិនទៀងទាត់ (Irregular shapes) ដោយប្រើប្រាស់ Bottom-Left (BL) heuristic ជាលក្ខណៈវិនិច្ឆ័យក្នុងការដាក់។
បញ្ចូលក្បួនស្វែងរក Tabu និងបង្កើតជាប្រព័ន្ធកូនកាត់ (Hybridization): នៅពេល GA ដំណើរការបានល្អហើយ ត្រូវសរសេរមុខងារ Tabu Search បន្ថែមជាលក្ខណៈ Mutation Module។ កំណត់បញ្ជី Tabu List សម្រាប់ចងចាំជម្រើសដែលបានសាកល្បងរួច ដើម្បីបង្ខំឱ្យក្បួនដោះស្រាយផ្លាស់ប្តូរវិធីរៀបចំនៅពេលដែល GA មិនអាចរកឃើញលទ្ធផលថ្មីប្រសើរជាងមុន (Self-adapting mechanism)។
ប្រមូលទិន្នន័យរោងចក្រពិត និងធ្វើតេស្តជាក់ស្តែង (Real-world Testing): សហការជាមួយរោងចក្រកាត់ដេរ ឬរោងជាងដែកក្នុងស្រុកដើម្បីទទួលបានគំរូទិន្នន័យឯកសារ CAD files (DXF/SVG) នៃរូបរាងពុម្ពដែលត្រូវកាត់។ បញ្ចូលទិន្នន័យទាំងនេះទៅក្នុងក្បួនដោះស្រាយ ហើយប្រៀបធៀបប្រសិទ្ធភាព (% នៃការសន្សំសម្ភារៈ) ជាមួយនឹងការរៀបចំដោយដៃរបស់កម្មករជំនាញ។
អភិវឌ្ឍចំណុចប្រទាក់អ្នកប្រើប្រាស់ (User Interface Development): បង្កើតកម្មវិធីដែលមាន UI ងាយស្រួលប្រើដោយប្រើប្រាស់ PyQt5, Tkinter ឬបង្កើតជា Web App (ប្រើ Streamlit)។ នេះអនុញ្ញាតឱ្យបុគ្គលិករោងចក្រដែលមិនចេះសរសេរកូដ អាចបញ្ចូលរូបភាពពុម្ព និងទាញយកប្លង់កាត់ Optimal Layout បានភ្លាមៗសម្រាប់យកទៅប្រើជាមួយម៉ាស៊ីនកាត់ CNC។

៥. វាក្យសព្ទបច្ចេកទេស (Technical Glossary)

ពាក្យបច្ចេកទេស	ការពន្យល់ជាខេមរភាសា (Khmer Explanation)	និយមន័យសាមញ្ញ (Simple Definition)
Genetic Algorithms (ក្បួនដោះស្រាយហ្សេនេទិក)	វិធីសាស្ត្រស្វែងរកដំណោះស្រាយដោយត្រាប់តាមដំណើរការវិវត្តន៍តាមបែបធម្មជាតិ ដូចជាការបង្កាត់ពូជ (Crossover) និងការបំប្លែងហ្សែន (Mutation) ដើម្បីបង្កើតដំណោះស្រាយថ្មីដែលកាន់តែប្រសើរពីមួយជំនាន់ទៅមួយជំនាន់។	ដូចជាការជ្រើសរើសសត្វឬរុក្ខជាតិដែលល្អបំផុតមកបង្កាត់ពូជ ដើម្បីបានកូនជំនាន់ក្រោយដែលកាន់តែមានភាពធន់និងផ្តល់ទិន្នផលខ្ពស់។
Tabu Search (ការស្វែងរកតាមបែប Tabu)	ក្បួនដោះស្រាយការស្វែងរកក្នុងតំបន់ដែលប្រើប្រាស់បញ្ជីចងចាំ (Tabu list) ដើម្បីកត់ត្រាជម្រើសដែលធ្លាប់បានសាកល្បងរួច ការពារកុំឱ្យប្រព័ន្ធវិលត្រឡប់ទៅរកជម្រើសដដែលៗ និងជួយឱ្យវាអាចរំដោះខ្លួនចេញពីដំណោះស្រាយដែលជាប់គាំងនៅមួយកន្លែង (Local optima)។	ដូចជាការដើរក្នុងរង្វង់វង្វេង (Maze) ដែលយើងគូសសញ្ញាសម្គាល់ផ្លូវដែលទាល់ ដើម្បីកុំឱ្យដើរចូលផ្លូវនោះម្តងទៀត។
No-fit Polygon (ពហុកោណមិនស៊ីគ្នា)	វិធីសាស្ត្រធរណីមាត្រកុំព្យូទ័រសម្រាប់កំណត់ទីតាំងដែលអាចដាក់ពហុកោណពីរនៅក្បែរគ្នាដោយមិនមានការត្រួតស៊ីគ្នា ដោយបង្កើតបានជាព្រំដែនសិប្បនិម្មិតមួយដែលបង្ហាញពីទីតាំងអនុញ្ញាត។	ដូចជាការរាវរកទីតាំងគែមនៃបំណែករូបផ្គុំ Jigsaw ថាតើអាចរុញវាចូលគ្នាតាមជ្រុងណាបានខ្លះដោយមិនឱ្យជាន់លើគ្នា។
Strip Packing Problem (បញ្ហានៃការវេចខ្ចប់បន្ទះ)	បញ្ហានៃការរៀបចំវត្ថុផ្សេងៗចូលទៅក្នុងផ្ទៃមានកំណត់ដែលមានទទឹងថេរ ប៉ុន្តែប្រវែងមិនកំណត់ (ដូចជាសន្លឹកក្រណាត់ ឬបន្ទះដែក) ដោយធ្វើយ៉ាងណាឱ្យប្រវែងសរុបដែលប្រើប្រាស់មានទំហំខ្លីបំផុត។	ដូចជាការរៀបចំឥវ៉ាន់ចូលក្នុងប្រអប់រថយន្ត ឬទូកកុងតឺន័រ ដោយព្យាយាមរៀបយ៉ាងណាឱ្យស៊ីកន្លែងតិចបំផុត។
Minkowski's difference (ផលសង Minkowski)	ប្រមាណវិធីគណិតវិទ្យាលើសំណុំនៃចំណុចសម្រាប់គណនា No-fit polygon រវាងរូបរាងពហុកោណប៉ោងពីរ ដើម្បីកំណត់គម្លាតនិងទីតាំងប៉ះគ្នា។	ដូចជាការដកស្រមោលរបស់វត្ថុមួយចេញពីវត្ថុមួយទៀត ដើម្បីមើលទំហំខុសគ្នាពិតប្រាកដ និងរកមើលថាតើពួកវាអាចផ្គុំចូលគ្នាបានយ៉ាងដូចម្តេច។
Meta-heuristics (ក្បួនដោះស្រាយម៉ាស៊ីន ឬ មេតាអឺរីស្ទិក)	ក្របខណ្ឌក្បួនដោះស្រាយកម្រិតខ្ពស់ដែលត្រូវបានរចនាឡើងដើម្បីស្វែងរកដំណោះស្រាយល្អបំផុត ឬជិតល្អបំផុត សម្រាប់បញ្ហាស្មុគស្មាញដែលពិបាកដោះស្រាយតាមរបៀបគណិតវិទ្យាធម្មតាក្នុងរយៈពេលដ៏ខ្លី។	ដូចជាយុទ្ធសាស្ត្រមេបញ្ជាការដែលបញ្ជាទ័ពឱ្យស្វែងរកវត្ថុមានតម្លៃក្នុងព្រៃធំ ដោយប្រើទាំងការរាវរកជុំវិញកន្លែងសង្ស័យ និងការបែងចែកកម្លាំងទៅទីតាំងថ្មីៗ។

៦. ប្រធានបទពាក់ព័ន្ធ (Further Reading)

អត្ថបទដែលបានបោះពុម្ពនៅលើ KhmerResearch ដែលទាក់ទងនឹងប្រធានបទនេះ៖

ប្រធានបទ និងសំណួរស្រាវជ្រាវដែលទាក់ទងនឹងឯកសារនេះ ដែលអ្នកអាចស្វែងរកបន្ថែម៖