基于多目標(biāo)優(yōu)化的染色算法

　　圖的鄰點(diǎn)可區(qū)別均勻V-全染色（AVDEVTC）是指在滿足鄰點(diǎn)可區(qū)別V-全染色的基礎(chǔ)上，還要保證每種顏色的使用次數(shù)相差不超過1，把完成AVDEVTC所用的最少顏色稱為圖的鄰點(diǎn)可區(qū)別均勻V-全色數(shù)（AVDEVTCN）。針對圖的AVDEVTC問題，提出了一種基于多目標(biāo)優(yōu)化的染色算法。設(shè)計(jì)了一個(gè)總目標(biāo)函數(shù)和四個(gè)子目標(biāo)函數(shù)，在染色矩陣上通過每個(gè)點(diǎn)的顏色集合的迭代交換操作，使得每個(gè)子目標(biāo)函數(shù)都達(dá)到最優(yōu)，進(jìn)而滿足總目標(biāo)函數(shù)的要求，完成染色。經(jīng)過理論分析和實(shí)驗(yàn)對比表明，8個(gè)頂點(diǎn)以內(nèi)的所有簡單連通圖都存在AVDEVTC，且圖的AVDEVTCN介于最大度加1與最大度加2之間。實(shí)驗(yàn)結(jié)果表明，該染色算法能夠在較短的時(shí)間內(nèi)正確地計(jì)算出1 000個(gè)頂點(diǎn)以內(nèi)的圖的AVDEVTCN。
?