[發明專利]基于離散化與啟發式進化算法的空間布局優化方法

有效

• 申請號: 201710561501.0
• 申請日: 2017-07-11
• 公開（公告）號: CN107330214B
• 公開（公告）日: 2021-06-01
• 發明（設計）人: 張永健;楊舟
• 申請（專利權）人: 哈爾濱工業大學（威海）
• 主分類號: G06F30/15
• 分類號: G06F30/15;G06F30/27;G06N3/12;G06F111/04
• 代理公司: 威海科星專利事務所 37202
• 代理人: 初姣姣

本發明涉及船舶建造過程中空間資源優化布局方法技術領域，具體的說是一種基于離散化與啟發式進化算法的空間布局優化方法，針對船舶建造過程中空間資源受限制約生產效率的問題，在對二維空間及不規則布局件幾何信息離散化的基礎上，建立了空間布局優化問題的數學模型，將啟發式的移動策略與遺傳進化算法相結合設計了問題的求解算法，采用無出界初始種群生成策略提高初始解的質量，引入重疊出界懲罰因子實現了問題的無約束轉化，通過仿真實驗對算法進行了驗證，結果表明算法在收斂速度和求解質量方面具有優勢。

技術領域：

本發明涉及船舶建造過程中空間資源優化布局方法技術領域，具體的說是一種基于離散化與啟發式進化算法的空間布局優化方法。

背景技術：

空間資源作為當前造船模式下制約生產效率的瓶頸資源，其優化利用問題存在于船舶制造的各個環節，受到船舶企業的廣泛關注。因此研究空間布局(spatial layout)問題的解決方法對于提高企業生產效率具有重大意義。

船舶制造的空間布局問題與排樣問題(nesting problem)一樣，均是尋求平面最優布局的優化問題。從布局件形狀來看，對于幾何特征簡單的矩形件，可直接通過數學規劃法(如：線性規劃、動態規劃、混合整數規劃等)求解。但此類方法并不適用于輪廓復雜的不規則件。因此有學者提出了將不規則件轉化為矩形來處理的矩形包絡法，但該方法造成的空間浪費較大。利用臨界多邊形(NFP)可以準確定位不規則多邊形的靠接位置，但其計算方法較為復雜，且不能處理帶弧線的圖形。基于像素的表示方法可以處理任意不規則圖形，但矢量圖轉化為像素圖會帶來額外的運算開銷。因此有學者提出了離散化的幾何形狀表示方法，可通過矩陣來表示空間資源的占用以降低問題的復雜度，但布局精度取決于其離散化程度。

不規則圖形排樣問題求解算法主要有基于規則(如：最低水平線，NFP最低中心等)的啟發式算法，以及智能優化算法(遺傳算法、模擬退火等)。啟發式算法實現簡單，求解效率較高，但所得結果通常為問題的近似最優解，且根據經驗和特定條件提出的啟發式規則不具備一般性。智能優化算法收斂速度較慢，但理論上能得到問題的最優解。

鑒于船舶建造過程中的布局件尺寸較大，其布局精度要求低于一般的零件、皮料排樣。

發明內容：

本發明針對現有技術中存在的缺點和不足，提出了一種選擇離散化的方式處理空間資源和布局件，在此基礎上建立了任意不規則件的空間布局模型，同時考慮到遺傳算法收斂速度慢等缺點，將之與啟發式策略相結合的基于離散化與啟發式進化算法的空間布局優化方法。

本發明可以通過以下措施達到：

一種基于離散化與啟發式進化算法的空間布局優化方法，其特征在于包括以下步驟：步驟1：建立空間布局優化模型，具體包括：

步驟1-1：幾何信息離散化處理：首先定義空間布局問題相關概念：其中定義1場地：指可供加工、堆放利用的空間資源，如分段堆場，組立加工平臺；基于場地特征，對其作以下假定：①場地為二維矩形；②場地空間內部不存在不可占用區域，且能夠被任意劃分；一個長為L，寬為W的矩形場地，根據實際精度需求，用m×m大小的網格將場地離散化后，其初始空間資源占用信息可用的零矩陣SP來表示；

定義2布局件：指根據船舶建造模式、生產工藝以及船體特征分解所生成的中間產品，如船舶分段，對其假定如下：①其平面投影為任意二維圖形，不僅限于凹凸多邊形，也包括含弧線的不規則圖形；②其投影包含加工、轉移所需安全距離的部分空間；③由高度產生的約束不予考慮；④布局件能夠以不同的角度放置到場地空間，為減少計算量，選取了4個具有代表性的角度：0°、90°、180°、270°。0°為其初始狀態角度，其余角度在初始狀態基礎上旋轉得到，在實際工程應用中，可根據情況增加或減少旋轉角度；