资源描述：
《以基因演算法求解单原片方形物件排列问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、科學與工程技術期刊第二卷第三期民國九十五年75JournalofScienceandEngineeringTechnology,Vol.2,No.3,pp.75-83(2006)以基因演算法求解單原片方形物件排列問題123吳泰熙吳奕樺張欽智1逢甲大學工業工程與系統管理系台中市西屯區文華路100號2美國奧本大學工業與系統工程系Auburn,Alabama36849,USA3仁德醫護管理專科學校資訊管理科苗栗縣後龍鎮溪洲里7鄰砂崙湖79-9號摘要工業界莫不亟思要如何精減人力以提昇效率、全面降低生產成本。然而尚有部分產業仍利用人工方
2、式來處理原物料切割∕排列等相關作業。此類複雜之「物件切割」問題需要有合適之演算法來迅速求得原物料切割計畫。過去文獻中，不乏因為使用遺傳基因演算法（geneticalgorithm,GA）而獲致不錯演算績效之研究，因此本研究採用GA之演算架構，但繼續加強在上述文獻中尚未被著墨之「菁英策略」，並使用不同之「編碼」設計，以期超越文獻之GA演算結果。在例題測試階段，我們首先以部分例題對所提出之GA演算法之參數進行實驗，以獲取參數組合建議。接著經由建議之參數組合，對38題國際文獻演算例題進行測試，再與國際文獻演算結果進行比較。結果顯示本
3、研究所提出之GA演算法，在中、小題型之單原片方形物件排列問題中幾乎皆優於國際文獻最佳結果，某些例題甚至超越文獻結果將近10%之使用率，演算績效可謂非常傑出。關鍵詞：方形物件排列問題，基因演算法SolvingTwo-DimensionalPackingProblemsbyUsingaGeneticAlgorithm123TAI-HSIWU,YI-HUAWUandCHIN-JUCHANG1DepartmentofIndustrialEngineeringandSystemsManagement,FengChiaUniversity
4、100WenhwaRd.,Seatwen,Taichung,Taiwan2DepartmentofIndustrialandSystemEngineering,AuburnUniversityAuburn,Alabama36849,USA3DepartmentofInformationManagement,Jen-TeJuniorCollegeofMedicine,NursingandManagement79-9,ShijouLi,Houlong,Miaoli,TaiwanABSTRACTInthisstudy,ageneti
5、c-basedalgorithm(GA)isproposedfornestingtwo-dimensionalrectangularpartsinamaterialplate.IntheliteratureGAhasbeenadoptedforsolvingthesame76科學與工程技術期刊第二卷第三期民國九十五年problem,fairlygoodresultshavingbeenobtained.Anewmethodfordesigningthecodingofthechromosomes,accompaniedbyap
6、roposalforanelitismstrategy,ispresentedinthisresearch,aimingatfurtherextendingtheproblem-solvingcapabilityofthetraditionalGA.Promisingcomputationalresultsareobtainedandreportedbyrunningexamplesfromtheliterature.KeyWords:two-dimensionalpackingproblem,geneticalgorithm
7、,elitismstrategy一、緒論構，但繼續加強在上述文獻中尚未被著墨之「菁英策略」（elitismstrategy），並使用不同之「編碼」設計，希望透過隨著時代進步、工業快速發展，如何降低生產成本來獲此二項機制之導入，設計出更好表現之GA演算法，以期最得較高之利潤是各企業極力追求的目標之一。然而觀察時下後能有效地產生最佳或近似最佳之方形物件排列計畫。的產業，仍有不少廠家依舊利用傳統人工方法來處理切割、在本研究所探討之方形物件排列問題中，就所提供的方排列等相關作業，但此舉卻恐造成不必要之物料及成本浪形物料原片之數目而言，
8、可分為單一原片及多張原片問題。費。因此業者莫不絞盡腦汁，發展出快速的解決之道。「物若物件數量過多，無法排入單一原片時，自然需要用到多張件切割」問題乃在預先給定的物料原片（materialplate）上，原片。多張原片問題的處理方法大多是以數學規劃方式或啟剪裁出所需要數量及尺寸
