基于多目標優(yōu)化的圖的強可區(qū)別染色算法研究.pdf

1、圖論中的一個經(jīng)典難題——圖染色問題，屬于圖論的一個分支，也是科學計算與工程設計中的基本問題。現(xiàn)實世界中有很多問題都可以轉化為圖的問題來解決，例如比賽安排問題、網(wǎng)絡通信問題、排課表問題、物資存儲問題、無線通訊頻道分配，印刷電路板設計及變址寄存器數(shù)目分配等等，這些問題的解決都涉及到圖的染色理論，所以染色問題是圖論中極具研究意義的領域之一。隨著現(xiàn)實世界中交通運輸、計算機網(wǎng)絡通信、軍事、生產(chǎn)管理等實際問題需求的發(fā)展，以及經(jīng)典智能優(yōu)化算法所存在的

2、不足以及局限性的演變，我們對快速而準確地實現(xiàn)染色結果并將其應用于實際的需求也逐步增大。
　　圖的強可區(qū)別染色問題是一種多條件約束染色，是在可區(qū)別全染色的基礎之上再增加約束條件，使得色集合的包含元素更多，共包括兩種染色概念:鄰點強可區(qū)別全染色、點強可區(qū)別全染色。目前在已公開發(fā)表的文獻中對強可區(qū)別全染色的研究僅局限于圈圖、輪圖、完全圖、樹等特殊圖，而對于一般隨機圖的強可區(qū)別染色研究尚無可行的解決方法。本文結合多目標優(yōu)化的研究思想，設計

3、了基于多目標優(yōu)化的強可區(qū)別染色算法，算法通過設定多個子目標函數(shù)逐步尋優(yōu)，使其最終的目標函數(shù)得到Pareto最優(yōu)解，實現(xiàn)局部最優(yōu)化到整體最優(yōu)化的過程。同時文中還設計實現(xiàn)了有限點以內(nèi)所有生成樹算法以及所有簡單連通圖生成算法，為各類染色算法的研究及結果集測試奠定基礎。本文的主要工作如下:
　　(1)介紹了圖論以及圖染色理論的基本概念、多目標優(yōu)化問題的相關概念、遺傳算法的基本思想以及應用于解決正常邊染色的算法執(zhí)行過程，同時對其優(yōu)缺點進行分

4、析總結。
　　(2)給出了兩類隨機圖生成算法，第一類是輸入頂點數(shù)目依照規(guī)則隨機連邊生成隨機簡單連通圖算法;第二類是基于生成樹生成有限點數(shù)內(nèi)所有偽非同構圖算法，因此第二類算法又包含了生成樹算法;兩種隨機圖生成算法為后續(xù)一系列染色算法的結果集測試、統(tǒng)計以及相關引理、猜想的證明提供基礎研究數(shù)據(jù)，為各種染色算法的研究奠定良好的基礎。
　　(3)設計并實現(xiàn)了基于多目標優(yōu)化的圖的鄰點強可區(qū)別全染色算法、基于多目標優(yōu)化的圖的點強可區(qū)別全染

5、色算法，同時設計了兩類正常邊染色算法、頂點染色算法、色集合調(diào)整算法等一系列子算法。強可區(qū)別全染色算法的最終目的是要確保頂點的色集合不同，色集合除了頂點顏色，頂點與其關聯(lián)邊顏色之外還加入了相鄰頂點的顏色，所以色集合調(diào)整的難度變得更大。所以本文設計了更詳細的的強色集調(diào)整規(guī)則，以及相應的過程評估函數(shù)來及時生成新的預染色組，從而更快速地搜索到最優(yōu)解，在不提高算法時間復雜度的情況下，提高算法的運行效率。
　　(4)測試結果集為7個點以內(nèi)所有