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

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

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