求解GCP問題的啟發(fā)式算法研究.pdf

1、圖著色問題(GCP，Graph Coloring Problem)是經(jīng)典的組合優(yōu)化問題之一。它也是科學(xué)計算和工程設(shè)計中一個重要和基本的問題。事實上，許多現(xiàn)實生活中的問題例如考試時間表問題和任務(wù)分配問題等都可以被模擬成圖的著色問題。由于對任意一個圖著色實例而言，沒有一種算法可以在多項式的時間內(nèi)找到它的全局最優(yōu)解，因此圖的著色問題是一個NP難的問題。 長期以來，人們一直在尋求快速、高效的啟發(fā)式算法，以便在合理的計算時間內(nèi)解決大規(guī)模問

2、題。由于對規(guī)模較大的問題，目前的啟發(fā)式算法尚不能在較短的時間內(nèi)給出高質(zhì)量的解，因此本文提出了一種基于全局最優(yōu)解和局部最優(yōu)解關(guān)系的ILS算法(ILSBR)和多級歸約算法。它們的基本原理是通過對.GCP問題的局部最優(yōu)解和全局最優(yōu)解之間關(guān)系的分析，發(fā)現(xiàn)對局部最優(yōu)解的簡單的相交操作能以很高的概率得到全局最優(yōu)解的部分解。ILSBR算法利用這些部分解構(gòu)造一種新的擾動策略(RLG重著色)，并將其應(yīng)用到傳統(tǒng)的ILS算法中。而多級歸約算法利用這些部分解逐