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

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

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

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

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

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