矩形布局優化問題的局部搜索蜂群算法

摘 要：帶平衡約束的矩形布局問題屬于組合優化問題，當問題規模增大時求解困難。為提高求解效率，設計了一個蜂群算法，通過分析解的分布，提供了基于貪心策略的群體初始化方案，選擇了有效的變異算子，將蜂群算法的搜索空間聚焦于最優解可能的區域。另外設計了一個二次局部搜索算法，對解的質量進行進一步提升。在10個公開的案例上與目前性能最好的算法進行了對照，提出的蜂群算法在其中9個較大規模的案例上超過了現有算法。理論分析和實驗結果表明，相對于現有算法，所提蜂群算法能明顯提高求解效率。

關鍵詞：布局優化問題； 蜂群算法； 局部搜索

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-3695（2023）07-012-1998-05

doi：10.19734/j.issn.1001-3695.2022.12.0779

Artificial bee colony algorithm with local search for rectangle layout optimization

Xu Yichun^1，2， Zhang Yinghui^1，2， Wan Shuzhen²， Dong Fangmin^2?

（1.Hubei Province Engineering Technology Research Center for Construction Quality Testing Equipments， Yichang Hubei 443002， China; 2.College of Computer amp; Information， China Three Gorges University， Yichang Hubei 443002， China）

Abstract：The rectangular layout problem with balance constraints is a combinatorial optimization problem， which is difficult to solve when the problem scale increases. To improve the performance，this paper designed a bee colony algorithm. By analyzing the distribution of solutions， it provided a greedy initialization scheme for the population， selected an effective mutation operator， and limited the search space around the optimal solution. In addition， it designed a local search module to further improve the quality of the solution. On 10 open test cases， the algorithm was compared with the best known existing algorithms， and the performance of the proposed algorithm exceeded the existing algorithms on 9 large-scale cases. The theoretical analysis and experimental results show that the proposed algorithm can significantly improve the efficiency of solution.

Key words：layout optimization problem; artificial bee colony; local search

帶平衡約束的布局優化問題背景是在一個返回式衛星艙內，要求將一些給定的儀器、設備等部件進行合理的布置，使得各部件之間、部件與艙壁之間不存在干涉量，且衛星艙在運行中易維持平衡^［1～3］。該問題作為一個優化問題，不僅在算法理論上具有重要意義，同時在工業制造上也極具價值。目前該問題的求解算法研究主要采用一些群體智能方法^［4～8］、模擬退火算法^［9］，以及擬人擬物算法^{［10， 11］}等。最近研究人員提出了深度神經網絡的方法^［2］，雖然效果良好，但需要大量的訓練，而且性能稍低于業界最好的算法^［11］。總體上看，這些方法在中小規模的問題上能有效解決，但隨著布局物增多，算法性能下降嚴重。

經過分析，本文認為現有的這些算法設計，其主要缺點在于問題本身的信息沒有充分利用，在建立了目標函數之后，直接應用通用的優化工具。而遺傳算法、粒子群算法或者蟻群算法這些通用的優化算法，雖然具有局部搜索和全局搜索的能力，但如果沒有問題信息的引導，實際上還是盲搜索。

此外，傳統方法給出的解基于某一個定位順序，整個解空間由不同的定位順序構成，而這實際上對解進行了一定程度的限制，忽略了對解進一步改進的可能。

針對上述兩個缺陷，本文在文獻［3］的基礎上設計了局部搜索蜂群算法。人工蜂群算法是元啟發式算法的一種，近期在工程中應用廣泛^{［12， 13］}。本文通過分析布局優化問題解的分布特征，對人工蜂群算法進行改進，使得其將搜索計算聚焦于更多優秀可行解的子空間，從而提高了搜索效率。而且，對于人工蜂群算法輸出的解，設計了一個二次局部搜索步驟，進一步提高解的精度。

本文通過理論分析和實驗的方式驗證了算法設計的合理性，并且在一個公開的數據集上，本文與目前性能最好的算法進行了比較。

1 相關工作

1.1 無正交約束優化算法

早期的矩形布局優化問題中沒有正交約束，即每個布局物i有矩形位置坐標和旋轉角度三個實變量（x_i， y_i， θ_i）， i=1，2，…，n，因此優化算法需要在R³ⁿ的高維空間中進行搜索，難度較大。這一類算法包括直接遺傳算法^［4］、粒子群算法^［6］、模擬退火算法^［9］以及Wang-Landau抽樣算法^［14］。因為解空間隨著布局物增多迅速增加，算法在少數布局物時效果較好，但布局物數量上升時，難以得到滿意的布局，算法并不適用。

1.2 基于正交約束的定位優化算法

徐義春等人^［5］提出增加矩形的正交約束，規定矩形布局物之間的邊必須平行或者垂直，即θ_i只有90°或者0°兩個選項，從而將變量空間縮小到2ⁿUR²ⁿ。在此約束下，文獻［5］設計了一種直接定位方法，輸入一個布局物排序，即可以得到一個質量較好的布局。然后應用遺傳算法對定位排序進行尋優。該方法給出的結果相對第一類方法，在同等時間內，布局質量有較大提高。黃振東、季美等人分別設計了不同的定位方法，并應用粒子群算法^［7］、蟻群算法^［8］等對定位順序進行優化。

1.3 基于正交約束的擬人擬物算法

劉景發等人^{［10， 11］}也研究了帶正交約束的布局優化問題，設計了一個2階的大部分光滑的目標函數，從而采用梯度下降法（擬物）來進行優化，并采用一些擬人機制來處置局部最優問題。這類方法達到了目前業界的最好水平， 超出了前述基于定位的優化算法。但是由于問題的局部最優點太多，隨著問題規模的增加，其求解也相當困難。

1.4 深度神經網絡的方法

最近在基于定位方法的基礎上，研究人員提出通過指針網絡來建立輸入的矩形布局物參數與優良布局順序的關系^［2］。由于布局結果未知，指針網絡不能通過有監督方式學習，所以采用強化學習的方法來進行訓練。但是強化學習的訓練時間較長，而且學習質量也跟訓練數據有關系。實驗結果表明，網絡能以極快的速度得出一個較好的解，其性能超過多數傳統的搜索算法，但是解的質量并沒有超過文獻［11］。

1.5 人工蜂群優化算法

本文的目標是利用人工蜂群算法結合定位算法，使性能進一步提升，反超擬人擬物算法。人工蜂群算法是20世紀末提出的一種基于蜂群覓食機制的群體優化算法，由于其優化機制簡單，有較好的全局搜索和局部搜索能力，目前在工程優化領域得到廣泛的應用^［12］。本文采用人工蜂群的一個整數版本^［13］。

算法1 人工蜂群算法

輸入：個體數目n;循環代數G;重初始化代數t;變異算子m和適應度函數f。

輸出：目標最優解。

初始化第1代個體，s₁，s₂，…，s_n

for g=1 to G

for i=1 to n

//階段1

s^′_i=m（s_i）

if f（s^′_i）＜f（s′_i） then s_i=s^′_i

for i=1 to n

//階段2

用輪盤賭方式選擇一個s_i

s^′_i=m（s_i）

if f（s^′_i）＜f（s^′_i） then" s_i=s^′_i

記錄最優個體s^*

for i=1 to n

//階段3

if s_i在t次機會內沒有更新 then s_i重新初始化

輸出最優的個體s^*

從算法1可以看出， 蜂群算法在全局優化和局部優化中得到很好的平衡，第1階段中，每個個體都有變異的機會，具有較強的全局優化能力；第2階段中，優秀的個體給予更多的機會，加強了局部搜索能力；第3階段中，長期處于局部最優的個體將被重新初始化，著重解決長期陷入局部最優的問題。

2 問題定義

用序列E=［（l₁，w₁，m₁），（l₂，w₂，m₂），…，（l_n，w_n，m_n）］表示給定n個矩形的參數，其中第i個矩形的長、寬、質量分別為l_i，w_i，m_i。假定每個矩形的質心處于矩形的幾何中心。另有一圓形容器，以容器的圓心為坐標原點O=（0， 0）。現將每個矩形以水平或垂直方向布置于圓形容器內，矩形i的中心坐標和方向為x_i，y_i，θ_i。用序列X=［（x₁，y₁，θ₁），（x₂，y₂，θ₂），…，（x_n，y_n，θ_n）］表示n個矩形的布局變量，圖1標志了各種記號的含義。

矩形布局問題優化問題定義如下：

a）正交約束。規定每個矩形有一條邊平行于坐標軸，因此θ_i只有兩個值，本文中θ_i=0表示矩形i的l_i邊平行于x軸，θ_i=1表示l_i邊垂直于x軸。

b）干涉約束。規定任意兩個矩形不存在干涉量，幾何上必須滿足式（1）（2），即對任意的i，j：

其中：l^′_i和w^′_i分別是長邊和寬邊在考慮矩形是否旋轉后的結果，即

c）平衡約束。矩形集合的質心需靠近容器中心， 以保證系統的靜不平衡量較小。給定一個小的正常數δ，矩形系統的質心坐標（x_w，y_w）滿足

其中：

d）目標函數。布局問題的目標是確定所有矩形的位置和方向，在滿足上述約束的情況下，這些矩形都必須包含在容器內。當容器半徑較小時，尋找可行的矩形配置是一個較難的問題。本文給出一個等價的優化目標函數，即求所有矩形的包絡半徑達到最小：

3 蜂群算法

本文在文獻［5］的定位算法基礎上，應用人工蜂群算法進行定位順序尋優。通過問題本身的屬性，分析可行解的分布特點，然后根據其特點設計針對性的人工蜂群算法。由于算法利用了問題本身的信息，效果比直接應用優化工具進行盲搜素有較大的提高。

3.1 定位算法

定位算法的主要思想是按照一個定位順序（排列）依次確定矩形的位置。布置下一個矩形j時，需要緊貼前面已經布置的某個矩形i，并不可與其他已布置的矩形產生干涉。如圖2（b）所示，矩形i提供了8個角部區域，在每個角部區域矩形j可以有兩個方向布置（圖2（b）），故一共有16個位置，因此j最多有16×（j-1）個位置可供選擇。對每個可行位置計算一個以已布置矩形質心為圓心的包絡半徑R_w（本文中稱為質心包絡半徑），選擇R_w最小的位置作為j的位置。算法2表示了定位算法的主要步驟， 由于計算質心的時間復雜度是O（n）， 故Deploy_One的時間復雜度為O（n²），整個算法的時間復雜度是O（n³）。

算法2 定位算法

1）deploy_all（s，E） //完整定位算法

輸入：s是一個排列；E是n個矩形的參數集合。

輸出：布局結果X及其最小質心包絡半徑R_best。

根據s對E重排， 令X［1］∶=（0，0，0）

for j=2 to n //調用子函數定位每個矩形

R_best，X=deploy_one（j，E，X）

return R_best，X

2）deploy_one（j，E，X） //定位第j個矩形

輸入：j是當前定位的矩形;E是n個矩形的長、寬、質量參數；X是n個矩形的位置，其中前j-1個矩形位置已確定。

輸出：X是n個矩形的位置，其中前j個矩形位置已確定。

R_best是前j個矩形的質心包絡半徑。

R_best∶=∞

for i =1 to j-1

計算i提供的16個位置PS

for p in PS

if p是可行位置 then

計算R_w

if R_w＜R_best then

p_best∶=p;R_best∶=R_w

X［j］∶=p_best

return R_best，X

3.2 定位算法解的分布分析

算法2根據一個定位順序可以輸出一個質量較好的（即包絡半徑較小）布局可行解，而不同的定位順序得到的解質量并不一樣。現有算法通過各種尋優工具來搜索好的定位順序。但是，通過分析大量的布局結果發現，質量較好的布局存在一些共性，即在定位順序中，質量較大或者形狀較大的矩形往往應優先布局。本文先用一個具體的例子來分析逆序數與布局質量的關系，然后通過統計驗證的方法來對此特性進行進一步分析。

定義1 排序因子。每個矩形i的排序因子與其尺寸和質量相關，定義為

a_i=1m_il_iw_i（7）

定義2 正序和逆序。在一個矩形序列中，如果存在兩個矩形的位置i＜j， 滿足a_i≤a_j，則稱i和j之間是正序關系，否則是逆序關系。

定義3 逆序數。一個矩形序列中逆序關系的總數，稱為該序列的逆序數。

斷言1 n個矩形序列的逆序數最小為0，最大為[n（n-1）]/2。

例1 假設有5個布局物，其中4個小的布局物的長寬質量分別為（1，1，1）， 1個大的布局物為（1，4，4），則一共有5種實質不同的定位順序，布局結果分別列于圖3中。

圖中按定位的次序給布局物進行標號。從上到下（同一行從左到右）逆序數分別為（0，1，2，3，4）， 包絡半徑分別為（2.24，2.24，2.24，2.40，2.80），可見逆序數較小的定位順序會帶來更優良的布局。從原理上分析，當優先布置較小的布局物時， 由于定位算法保持局部緊湊，這些小的布局物將聚合成團，后面遇到較大布局物則空間無法避讓，從而布局質量較差；而大型布局物先布局，后面布置的小型布局物容易在大型布局物的周圍找到合適的空間。

為了分析一個定位序列的逆序數與包絡半徑的關系，本文隨機生成一個10個不同的矩形的布局案例（更大規模的案例具有相似的表現），應用定位算法2計算出各種排列的包絡半徑，并統計每一種逆序數下的最小包絡半徑，如圖4（a）所示。結果表明，整體上逆序數較小的輸入給出了較小的包絡半徑， 而最小的包絡半徑出現在逆序數小于10的序列中。這個結果提示人們應該在較小的逆序數序列中去尋優，而不是在整個排列空間。其次，根據數論理論^［15］，統計出不同逆序數下的矩形序列的個數，如圖4（b）所示，逆序數小于10的序列，實際上在整個排列空間中占比非常小，約為0.8%。

這個案例說明：優良的布局逆序數一般較小，而較小的逆序數數量也較少，所以搜索時如果聚焦于小逆序數空間，則可用較小計算耗費，就能得到很好的布局結果。

3.3 基于逆序數的蜂群算法設計

根據3.2節的分析，并參考1.5節的蜂群算法，本文設計了一個基于逆序數的蜂群算法，利用定位算法，將搜索重點聚焦于逆序數較小的序列中。

a）個體和適應度函數的設計。將矩形的一個排列s定義為個體，應用定位算法2輸出其包絡半徑r（s），規定r（s）越小，個體適應度越大，故定義適應度函數。

b）初始群體的貪心設計。蜂群初始化對算法性能有較大影響。根據3.2節的分析，優良的布局分布在逆序數較小的序列空間，因此設計的蜂群算法初始群體包含n個個體，第一個個體是逆序數為0的矩形序列，即將n個矩形按排序因子進行從小到大排序。 隨后依次交換第1個個體的（1，2），（2，3），…，（n-1，n）元素的位置，得到余下的n-1個個體。顯然這n-1個個體的逆序數為1。本設計使初始群體聚集于小的逆序數空間。

c）變異算子的設計。蜂群算法的前兩個階段，都要對個體進行變異。本文研究了遺傳算法^［16］中的三個變異算子，包括SWAP、INSERT和INVERSION。在序列中隨機選取長度為k的一個子段，SWAP算子交換首尾元素，INSERT算子將尾部元素插入到首部之前，而INVERSION算子將子段的元素順序逆轉，如圖5所示。這些算子會改變個體的逆序數。

d）選擇概率的設計。在蜂群算法的第2階段，每個個體根據其適應度獲得一個概率，給予一個更新的機會。選擇概率為

由于蜂群算法設置了n個個體，運行G代，每代有兩個階段需要進行適應度計算，故蜂群算法的時間復雜性為O（2Gn⁴）。

4 二次局部搜索

蜂群算法最后輸出的是一個定位順序對應的布局，而定位順序的總數是n！ ， 因此最優結果超不出這個排列空間。本文提出一個時間復雜度為O（n³）的二次局部搜索算法，在適當的時間耗費下，進一步改進蜂群算法輸出的結果。由于蜂群算法的時間復雜度是O（2Gn⁴）， 故加上這個局部搜索之后，并不會影響整體的算法性能。

二次局部搜索基于這樣的思路：在定位算法的核心處理deploy_one中，每個矩形采取了貪心策略，選擇了一個當時能帶來最優包絡半徑的位置，但實際上這個位置對最終結果并不一定是最優。因此在輸出最終結果后，可以再次調整每個矩形的位置，以獲得改進，算法如下：

算法3 局部搜索算法LocalSearch（E，X，R_best）

輸入：n個矩形的參數集合E；當前的布局結果X;布局X的包絡半徑R_best。

輸出： 改進后的布局X和包絡半徑R_best。

for j =1 to n

交換恢復矩形j和n的E，X數據

R，X=deploy_one（n，E，X）

if R＞R_best then

恢復矩形j和n的E，X數據

return X，R_best

本文應用二次局部搜索算法對例1的結果進行改進。其中前三個布局已達最優，后兩個質量較差的布局按照原來的布局次序，依次為每個布局物尋找新的位置，結果如圖6所示，位置調整后達到了最優。

5 實驗與討論

本文的測試計算在一臺3.1 GHz主頻CPU、16 GB內存的機器上進行，使用C++語言編程。實驗中蜂群算法個體數目設置為矩形個數，循環代數G為100， 初始化間隔t設置為20。

本文采用質心包絡半徑和計算時間作為算法比較的性能指標。由于本文算法將布局解的質心作為布局中心，可以使靜不平衡量的理論值為0，所以實驗中不平衡量不再作為性能指標。

5.1 實驗1 三種變異算子的性能比較

為了評價SWAP、INSERT、 INVERSION三種變異算子，本文生成了30個布局案例的數據集，每個案例包括20個隨機生成的矩形，其中l_i和w_i取值為［1，100］，m_i接近l_i×w_i。變異算子設置子段的長度k為［2，9］。圖7展示了算法給出的在不同的k設置下，三種變異算子給出的布局包絡半徑的平均值。從圖中可見，三種算子的性能沒有明顯的差異，但是還是可以看出：a）k的設置不能太大也不能太小，太大的k使得蜂群算的搜索超出了低逆序數空間，而太小的k則又過分限制了搜索范圍；b）INSERT算子在k設置為5時具有最好的性能。

本文分析INSERT算子效果較好的原因在于相對其他兩種算子，INSERT算子帶來的逆序數變化最小，因此更容易控制住逆序數的變化程度。例如假設k=5的子段原來的逆序數為0，則SWAP算子增加了7個逆序，INVERSION算子增加了10個逆序，而INSERT算子只增加了4個逆序。這種小步長的變化，使得搜索在低逆序數空間有更多的機會。在后續實驗中，選擇了k=5的INSERT算子作為蜂群算法的變異算子。

5.2 實驗2 蜂群個體初始化的方案比較

本文的蜂群算法提出了初始群體的貪心化設置，即n個個體的逆序數小于等于1。 而常見的群體搜索算法一般都是隨機初始化以保證算法的全局搜索能力。本文使用實驗1同一個數據集，比較了貪心初始化方案和隨機初始化方案的不同性能，如圖8所示。結果表明貪心初始化的結果遠遠好于隨機初始化，經過100代的進化后，隨機初始化的結果還不如貪心初始化第1代的結果。

5.3 實驗3 算法的局部和全局搜索性能

在蜂群算法的階段3中，群體如果監測到個體在t次機會中都沒有更新，則說明該個體陷入局部極小，進行重新初始化，從而增強了算法全局搜索能力。算法的全局搜索性能用群體的平均半徑來表示，當平均半徑一直變小時，說明算法的局部搜索能力較強，但同時可能會減弱全局搜索能力；反之，則全局搜索能力增強，但局部搜索能力減弱。

為了說明蜂群算法的搜索性能，本文以實驗1中一個案例的迭代數據來說明。圖9中給出了4個t設置下的平均半徑和最小半徑在100次迭代下的曲線。可以看出，當t=10時，群體的平均半徑在較短時間內上下變化，直到第22代才獲得一個較好的優化結果，說明算法過于偏重全局搜索能力，而局部搜索能力較弱；當t=40時，群體的平均半徑在較長周期內保持下降，說明算法偏重于局部搜索，但是全局搜索能力受到影響，最后的優化結果也不太好。因此，蜂群算法通過三個階段保持局部搜索和全局搜索方面的平衡，而通過參數t，算法能在平衡性方面進行一定的調整。

5.4 實驗4 二次局部搜索的改進效果

為了驗證局部搜索產生的效果，本文記錄蜂群算法直接輸出的結果以及增加二次局部搜索模塊的結果。包絡半徑在二次局部搜索下尺寸減小的相關數據如表1所示。

表中結果顯示，局部搜索算法在約2/3的樣例有改進，雖然改進的量并不大，但是在實際應用中，可能會帶來關鍵性能的提升。另外其計算耗費非常少，因此局部搜索模塊是算法的一個重要組成部分。

5.5 實驗5 與IBF算法的對比

文獻［10］公布了10個公開的布局案例，布局物數目為10～100個。其中在100個布局物的情形下，需要大量的計算，對算法性能有較嚴格的要求。在此數據集上，目前性能表現最好的是IBF算法^［10］，在全部10個案例上都達到已報告的最好結果，因此本文將提出的蜂群算法與該算法進行性能比較。為了使性能比較公平，本文給每個案例指定一個優化包絡半徑作為目標，然后比較每個算法搜索到解的時間耗費。由于蜂群算法性能優勢明顯，本文在每個案例上運行5次進行結果統計。

結果表明蜂群算法在每個案例上都以更短的時間搜索到目標布局，而且時間最少提高了3倍，平均提高了20倍，蜂群算法表現出明顯的優勢。結果如表2所示，其中蜂群算法用ABC（artificial bee colony）表示。

為了進一步測試兩個算法的性能，本文對更小的包絡半徑進行實驗。為了避免算法長期不收斂，規定超過一個小時未搜索到可行布局為失敗。表3中記錄了每個案例上5次運行的結果，并給出了成功找到目標解時的平均時間。可以看出，IBF算法僅在兩個小規模案例上能找到結果，其他8個案例5次運行全部失敗。而蜂群算法在9個案例上都超過了IBF算法， 僅在案例1上失敗。案例1上失敗的原因是由于蜂群算法定位規則的限制，使得解空間變小，在小規模問題上有可能錯過最優解。但是在中大規模問題上，蜂群算法優勢明顯。

5.6 實驗6 與深度神經網絡算法DAR的對比

文獻［2］提出的深度神經網絡算法DAR經過訓練后，能夠輸出質量較佳的定位順序。由于神經網絡的計算不是一個迭代搜索的過程，所以速度很快，其時間復雜度為O（n³）。為了公平對比，本文的蜂群算法只輸出第一代的最佳布局，在實驗5使用的數據集上，與神經網絡算法進行包絡半徑比較，結果如表4所示。

表中的結果表明，在所有10個樣例上，DAR算法輸出的布局，都劣于蜂群算法，說明在復雜的布局優化問題中，學習算法確實學到了一定的布局知識，但跟人類利用問題信息和經驗設計的啟發式算法相比，還有一定的差距。

最后以R3為例，展示DAR、IBF和蜂群算法所獲得的布局圖，其半徑分別為63.03，56.44，56.02。從圖10可以看出，三種算法雖然基于不同的原理，但可以看到的規律是較大的布局物都靠近中心位置，這也是本文蜂群算法設計的基礎。

6 結束語

針對帶平衡約束的矩形布局優化問題，本文通過分析解空間的分布特點，提出了一個局部搜索的蜂群算法。算法在定位算法的基礎上，通過群體的貪心初始化，以及專門選擇的變異算子，將搜索空間聚焦到局部，從而在整體上提高了搜索算法的性能。另外設計了二次局部搜索模塊，能在較短的時間內對蜂群算法的結果實現進一步改進。實驗結果表明，蜂群算法性能相對現有算法有較大提高。工程中布局物有更復雜的形狀，而且在三維情形下有多層次布局需求。下一步的工作可將本文的思路和方法擴展到這些應用中。

參考文獻：

［1］馮恩民， 王錫祿， 王秀梅， 等. 帶性能約束布局問題的全局優化算法［J］. 高校應用數學學報： A輯中文版， 1999，14（1）： 98-104. （Feng Enming， Wang Xilu， Wang Xiumei， et al. A global optimization algorithm for layout problems with behavior constraints［J］. Applied Mathematics： A Journal of Chinese Universities， 1999，14（1）： 98-104.）

［2］徐義春， 萬書振， 董方敏. 帶平衡約束矩形布局優化問題的深度強化學習算法［J］ . 計算機應用研究， 2022，39（1）：146-150. （Xu Yichun， Wan Shuzhen， Dong Fangmin. Deep reinforcement learning algorithm for the rectangle layout optimization with equilibrium constraint［J］. Application Research of Computers， 2022，39（1）：146-150.）

［3］Xu Yichun， Wan Shuzhen， Dong Fanmin. Problem-specific knowledge based artificial bee colony algorithm for the rectangle layout optimization problem in satellite design［C］//Proc of the 34th International Conference on Software Engineering amp; Knowledge Engineering. 2022.

［4］翟金剛， 馮恩民， 李振民， 等. 帶性能約束布局問題的不干涉遺傳算法［J］. 大連理工大學學報， 1999，39（3）： 352-357. （Zhai Jingang， Feng Enming， Li Zhenming， et al. Non-overlapped genetic algorithm for layout problem with behavior constraints［J］. Journal of Dalian University of Technology， 1999，39（3）： 352-357.）

［5］徐義春， 董方敏， 劉勇， 等. 帶平衡約束矩形布局優化問題的遺傳算法［J］. 模式識別與人工智能. 2010，23（6）：794-801. （Xu Yichun， Dong Fangmin， Liu Yong， et al. Genetic algorithm for rectangle layout optimization with equilibrium constraints［J］. Pattern Recognition and Artificial Intelligence， 2010，23（6）：794-801.）

［6］Xu Yichun， Xiao Renbin， Amos M. Particle swarm algorithm for weighted rectangle placement［C］//Proc of the 3rd International Conference on Natural Computation. Piscataway， NJ： IEEE Press， 2007：728-732.

［7］黃振東， 肖人彬. 求解帶平衡約束矩形布局問題的混合算法［J］. 華中科技大學學報： 自然科學版， 2011，39（3）： 96-99. （Huang Zhendong， Xiao Renbin. Hybrid algorithm for the rectangular packing problem with constraints of equilibrium［J］. Journal of Huazhong University of Science and Technology： Natural Science Edition， 2011，9（3）： 96-99.）

［8］季美， 肖人彬. 基于蟻群算法的帶平衡約束矩形布局問題的啟發式求解［J］. 計算機應用， 2010，30（11）： 2898-2901. （Ji Mei， Xiao Renbin. Ant colony optimization and heuristic algorithms for rectangle layout optimization problem with equilibrium constraints［J］. Journal of Computer Applications， 2010，30（11）： 2898-2901.）

［9］Xu Yichun， Xiao Renbin， Amos M. Simulated annealing for weighted polygon packing［EB/OL］. （2008-09-29）. https：//arxiv.org/abs/0809.5005.

［10］劉景發， 張振， 薛羽， 等. 帶靜不平衡約束的正交矩形布局問題的啟發式模擬退火算法［J］. 模式識別與人工智能， 2015，28（7）： 626-632. （Liu Jingfa， Zhang Zhen， Xue Yu， et al. Heuristic simulated annealing algorithm for orthogonal rectangle packing problem with static non-equilibrium constraints［J］. Pattern Recognition and Artificial Intelligence， 2015，28（7）： 626-632.）

［11］Liu Jingfa， Li Jian， Lu Zhipeng， et al. A quasi-human strategy-based improved basin filling algorithm for the orthogonal rectangular packing problem with mass balance constraint［J］. Computers amp; Industrial Engineering， 2017，107： 196-210.

［12］Akay B， Karaboga D， Gorkemli B， et al. A survey on the artificial bee colony algorithm variants for binary， integer and mixed integer programming problems［J］. Applied Soft Computing， 2021，106：107351.

［13］zcan U， Aydogˇan E K， Himmetogˇlu S， et al. Parallel assembly lines worker assignment and balancing problem： a mathematical model and an artificial bee colony algorithm［J］. Applied Soft Computing， 2022，130：109727.

［14］劉景發， 劉思妤. 帶靜不平衡約束的矩形裝填問題的啟發式算法［J］. 軟件學報， 2018，29（2）： 283-298. （Liu Jingfa， Liu Siyu. Heuristic algorithm for the rectangular packing problem with static non-equilibrium constraint［J］. Journal of Software， 2018，29（2）： 283-298.）

［15］Bona M. Combinatorics of permutations［M］. 3rd ed. Boca Raton， FL： Chapman and Hall/CRC Press， 2022.

［16］陳加俊， 譚代倫. 求解旅行商問題的探索—開發—跳躍策略單親遺傳算法［J］. 計算機應用研究，2023，40（5）：1375-1380. （Chen Jiajun，Tan Dailun. Partheno-genetic algorithm based on explore-develop-jump strategy for solving traveling salesman problem［J］. Application amp; Research of Computers， 2023，40（5）：1375-1380.）