利用熱退火啟發式連續非拘束最佳化演算法解決組合問題

Abstract

組合最佳化問題有許多工業應用，例如IC佈局、工業排程調度、異構體分析等，然而，組合最佳化是在一個有限的解集合中尋找最佳解的問題，其時間複雜度會呈階乘性成長，這類型的問題屬於NP-hard或NP-complete，隨著維度增加窮舉法便是不可行的，其中最知名的組合最佳化問題便是旅行商人問題(Travelling Salesman Problem; TSP)。 模擬退火演算法提供了能夠使用隨機搜索方向來脫離局部最小值的組合求解器，我們提出了一種不同於以往的熱退火啟發式演算法，是基於非線性規劃將組合問題建構成一個函數最佳化問題，再利用梯度下降(gradient descent)的求解器，可以將收斂速度大大提高到與梯度下降搜索相同的水平，當中還包含一個新的熱退火啟發正則化約束函數，用於通過逐漸增加函數凸性來放大全局最小值來逃避局部最小值。 我們試著將熱退火啟發式連續非拘束最佳化演算法(Annealing-inspired Continuous Unconstrained Optimization; ACUO)應用於不同城市數的旅行商人問題 (TSP)，在實驗結果中表明，演算法的運算為多項式時間複雜度，相較於窮舉求解法階乘時間複雜度，大幅加速了收斂時間，且對於高維旅行商人問題能夠有效解決，在50個城市的旅行商人問題中僅有5%的相對誤差。

Combinatorial optimization problem has various industrial applications, such as IC layout, industrial scheduling, isomer analysis, etc. However, the combinatorial optimization problem is to find the best solution in a limited solution set, and its time complexity grows exponentially. This type of problem is NP-hard or NP-complete. As the dimensions increase, the exhaustive method is not feasible. One of the most well-known combinatorial optimization problems is the Traveling Salesman Problem (TSP). Simulated Annealing Algorithm provides a combinatorial solver capable of escaping local minima using random search directions. We propose a novel annealing-inspired heuristic algorithm that approaches the combinatorial problem as a function optimization problem based on nonlinear programming. We use a gradient-descent(GD) based solver to greatly improve the convergence rate to the same level as GD search. Also included a new annealing-inspired regularization constraint function for escaping local minima by gradually increased convexity to zoom in on the global minima. We attempted to apply the Annealing-inspired Continuous Unconstrained Optimization (ACUO) to the Traveling Salesman Problem (TSP) with different numbers of cities. The experiment results show that the algorithm operates in polynomial time complexity, which is a great improvement compared to the factorial time complexity of exhaustive method. It especially accelerates the convergence time and effectively solves high-dimensional TSP instances. For a TSP with 50 cities, the relative error is only 5%.