利用關係分解和熵感知採樣改善邊直方圖採樣演算法

Abstract

排列問題嵌入了各種語義，其中一些重視基因的相對順序，一些重視基因之間的鄰近關係，還有一些重視基因的絕對位置關係。由於這些不同的語義，排列分佈估計演算法可能會在一種語義的某些問題中找到接近最優的解，但在另一種語義中則不然。為了解決語義問題，本文對邊直方圖採樣演算法提出了三個改進。首先，本論文文引入關係矩陣和熵感知採樣來增強邊直方圖採樣演算法表示不同語義的能力。其次，本論文結合了自適應機制，在演化過程中動態調整採樣基因的數量。最後，本論文提出了一種過濾機制，在採樣過程中動態排除確定性較低的關係。實驗結果顯示，與其他六種排列分佈估計演算法相比，改進的邊直方圖採樣演算法在線性排序問題上找到了最接近最佳解的解，並且在二次分配問題上找到了與點直方圖採樣演算法相比更接近最佳解的解。此外，改進的邊直方圖採樣演算法在流程式生產排程問題上找到的解和最佳解的距離是原始的邊直方圖採樣演算法找到的解和最佳解的距離的三分之一。雖然與原始的邊直方圖採樣演算法相比，改進的邊直方圖採樣演算法需要更多的函數評估次數才能在某些旅行銷售員問題實例中找到最佳解，但其他排列分佈估計演算法卻無法找到最佳解。總體而言，與其他排列分佈估計演算法相比，改進的邊直方圖採樣演算法在旅行銷售員問題、二次分配問題、流程式生產排程問題和線性排序問題上找到了平均最接近最佳解的解。

Permutation problems embed with various semantics, some of which give importance to the relative order of genes, some to the adjacency relation between genes, and some to the absolute position of genes. Due to these different semantics, permutation estimation of distribution algorithms (EDAs) may find solutions close to the optimal in some problems of one semantic but not in another. To address the semantic issue, the thesis presents three improvements to the edge histogram-based sampling algorithm (EHBSA). Firstly, the thesis introduces relational matrices and entropy-aware sampling to augment EHBSA's capability to represent diverse semantics. Secondly, the thesis incorporates an adaptive mechanism to dynamically adjust the number of sampled genes during evolution. Lastly, the thesis proposes a filtering mechanism to dynamically eliminate relations with lower certainty during the sampling process. The experiments show that the improved EHBSA finds the solutions closest to the optimal compared to the other six permutation EDAs on the linear ordering problem (LOP) and finds solutions closer to the optimal on the quadratic assignment problem (QAP) compared to the node histogram-based sampling algorithm. Furthermore, the improved EHBSA obtains solutions three times closer to the optimal solution compared to the original EHBSA on the permutation flow shop problem (PFSP). Although the improved EHBSA requires more function evaluations to find the optimal solutions in some traveling salesman problem (TSP) instances compared to the original EHBSA, other permutation EDAs fail to find the optimal solutions. Overall, the improved EHBSA finds the solutions closest to the optimal on average across TSP, QAP, PFSP, and LOP compared to other permutation EDAs.