熊思穎，董黎君

?

標(biāo)記平面立體線圖的自適應(yīng)遺傳算法

熊思穎，董黎君

(太原理工大學(xué)機(jī)械工程學(xué)院，山西 太原 030024)

針對由理查德·邁爾斯提出的標(biāo)記線圖的遺傳算法進(jìn)行改進(jìn)：采取自適應(yīng)參數(shù)調(diào)整法，同一代中適應(yīng)度高于平均的個體雜交和變異率動態(tài)變化，適應(yīng)度低于平均的個體雜交和變異率設(shè)為定值；在創(chuàng)建初始種群時加入了約束條件，旨在改善初始種群覆蓋空間的不確定性和個體分布的相對不合理性；修正了遺傳算法的適應(yīng)度函數(shù)，使得以個體適應(yīng)度為指標(biāo)的選擇算子能正確引導(dǎo)算法搜索解空間。用遺傳算法標(biāo)記6幅不同的線圖，變量為雜交率、變異率公式中的參數(shù)和，分析算法標(biāo)記成功率曲線的變化趨勢，探討算子參數(shù)設(shè)置對遺傳算法性能的影響，結(jié)果表明屬于區(qū)間[0，0.05]，屬于區(qū)間[0.8，1.0]且為標(biāo)記線圖的遺傳算法的最優(yōu)參數(shù)設(shè)置。

線圖標(biāo)記；遺傳算法；二進(jìn)制編碼；適應(yīng)度

線圖解釋一直是計(jì)算機(jī)輔助設(shè)計(jì)和機(jī)器視覺研究的一個活躍領(lǐng)域，被廣泛應(yīng)用于建筑草圖的處理和二維工程圖的三維重建等方面。一致性標(biāo)記問題由HARALICK和SHAPIRO[1]在20世紀(jì)70年代提出，起到排除線圖的二義性和確定線圖平面結(jié)構(gòu)的作用，是三維流形物體重構(gòu)的重要預(yù)備步驟。MYERS和HANCOCK[2]致力于研究多面體場景的線圖的一致性標(biāo)記，在此基礎(chǔ)上，STANFILL和WALTA[3]提出了離散弛豫算法，表明使用一致性節(jié)點(diǎn)標(biāo)記庫便于在多面體對象的一致解釋中指明搜索方向，通過分析三維場景及其二維投影之間的幾何約束關(guān)系構(gòu)造一致性節(jié)點(diǎn)標(biāo)記庫。文獻(xiàn)[2]使用遺傳算法確定線圖棱線的最佳一致性標(biāo)記，提出一種通過標(biāo)記給出消失點(diǎn)的線圖重建三維場景的方法，介紹了遺傳算法是解決模糊線圖標(biāo)記問題的有效手段，證明基于種群和初始種群創(chuàng)建具有隨機(jī)性特點(diǎn)的優(yōu)化方法可以為線圖標(biāo)記問題提供優(yōu)良的解。HANCOCK和KITTLER[4]將Faugeras和Hummel提出的貝葉斯框架應(yīng)用于多面線框圖的標(biāo)記，BONNICI和CAMILLERI[5]將藝術(shù)線索如陰影和譜線與遺傳算法結(jié)合的方法標(biāo)記手繪圖，文獻(xiàn)[2]利用遺傳算法的概率搜索和優(yōu)化功能分配和評估線圖的標(biāo)記組合。

本文從雜交率和變異率、初始種群、適應(yīng)度函數(shù)等方面著手改善由理查德·邁爾斯提出的標(biāo)記線圖的遺傳算法易陷入局部最優(yōu)和成功率低的缺點(diǎn)，驗(yàn)證改進(jìn)后遺傳算法的優(yōu)越性，探討標(biāo)記線圖的遺傳算法的最優(yōu)參數(shù)設(shè)置。

1 遺傳算法設(shè)計(jì)

遺傳算法的進(jìn)化主要靠選擇算子和雜交算子來推進(jìn)，變異算子在算法的全局意義上只是起到修復(fù)和補(bǔ)充的作用[6]。傳統(tǒng)遺傳算法的雜交、變異率設(shè)為定值，在進(jìn)化初期，固定的雜交、變異率能快速淘汰種群中性能低的個體，但是在進(jìn)化后期，固定的雜交、變異率反而會破壞種群中的優(yōu)質(zhì)個體，放緩算法的收斂速度[7]。因此，在標(biāo)記線圖的遺傳算法中引入自適應(yīng)機(jī)制。

1.1 適應(yīng)度函數(shù)

圖1 24種合法的節(jié)點(diǎn)標(biāo)記

式(2)的待定參數(shù)是無記憶標(biāo)記錯誤過程發(fā)生的概率。為了使?jié)h明距離的指數(shù)作用更明確，可將式(2)改寫為

在多次運(yùn)行遺傳算法后發(fā)現(xiàn)，由理查德·邁爾斯提供的染色體適應(yīng)度式(5)計(jì)算得出的染色體適應(yīng)度過小，在選擇操作中，某個個體的累計(jì)概率相對其之前個體突然變大，通常大于0.9，且其后個體的適應(yīng)度變化非常緩慢，導(dǎo)致通過輪盤賭選出的個體適應(yīng)度差異過小，甚至?xí)霈F(xiàn)種群中個體適應(yīng)度相等的情況，導(dǎo)致優(yōu)化無法進(jìn)行，最終獲得某個局部最優(yōu)解。解決方案：引入與算法迭代次數(shù)相關(guān)的縮放參數(shù)，將其與式(5)中的價值函數(shù)C()相乘，新的適應(yīng)度函數(shù)由式(6)~(8)表示，即

其中，C()為第個染色體的價值函數(shù)；()max為價值函數(shù)的最大值；為算法最大迭代次數(shù)；為算法的當(dāng)前迭代次數(shù)；為一個隨算法迭代次數(shù)非線性變化的正數(shù)。

1.2 染色體編碼

線圖標(biāo)記算法將線圖的棱邊描述為凸棱(共有凸棱的兩個面對于視點(diǎn)而言均為可見面，且位于棱線右側(cè)的面逆時針轉(zhuǎn)過一個大于90°、小于180°的角與位于棱線左側(cè)的面重合，由記號“+”表示)、凹棱(共有凹棱的兩個面對于視點(diǎn)而言均為可見面，且位于棱線右側(cè)的面逆時針轉(zhuǎn)過一個大于180°、小于270°的角與位于棱線左側(cè)的面重合，由記號“–”表示)或遮擋棱(共有遮擋棱的兩個面中只有一個面可見，由記號“→”或“←”表示，順著箭頭的方向走，被遮擋平面在左手邊)。為標(biāo)記一幅線圖，需將線圖表示為節(jié)點(diǎn)的集合，從預(yù)定義的節(jié)點(diǎn)庫中為構(gòu)成節(jié)點(diǎn)的每條棱線分配一個記號，節(jié)點(diǎn)庫由該節(jié)點(diǎn)所屬的某型節(jié)點(diǎn)的所有合法記號匯編而成。對于每一個節(jié)點(diǎn)，其節(jié)點(diǎn)庫中包含多種記號樣式，線圖標(biāo)記算法的任務(wù)是找出使得線圖中所有節(jié)點(diǎn)被正確標(biāo)記的棱線記號集合。

1.3 創(chuàng)建初始種群

本文采取文獻(xiàn)[2]中建議的種群規(guī)模popusize=100。經(jīng)典遺傳算法的初始種群是隨機(jī)產(chǎn)生的，初始種群在搜索空間的覆蓋范圍是不確定的，若初始種群空間不涉及全局最優(yōu)解所在區(qū)域，而算子又不能在有限的進(jìn)化代數(shù)內(nèi)使種群個體分布覆蓋到最優(yōu)解區(qū)域，就不可避免地發(fā)生算法陷入局部最優(yōu)解的問題，因此初始種群個體分布的相對合理性對于改善算法的全局收斂性至關(guān)重要。

代表一幅線圖的染色體是由數(shù)個代表一個節(jié)點(diǎn)的基因片段拼接而成，結(jié)合24個合法的節(jié)點(diǎn)標(biāo)記和在1.2節(jié)中敘述的染色體編碼方法可以知道，每個棱線標(biāo)記對應(yīng)的字符的二進(jìn)制表示中“1”的數(shù)目恒為3，每一條基因片段上的24個基因中“1”的個數(shù)恒為9個，因此可以在創(chuàng)建初始種群時約束染色體上“1”的數(shù)目，使得種群能夠科學(xué)地表征解空間并且節(jié)約算法運(yùn)行時間。

1.4 選擇算子

選擇算子的作用是利用某種策略在當(dāng)前種群中選出優(yōu)質(zhì)的個體，增大其進(jìn)入交配池的幾率，以提高算法的全局收斂性，使算法具有良好的效率。

累計(jì)概率為

1.5 雜交和變異算子

破壞性雜交算子可以更好地探索搜索空間，因此本文采取均勻交叉。首先生成一個在0到1之間的隨機(jī)數(shù)，如果雜交率P≥，則將隨機(jī)配對的2條染色體上的基因互換，互換方式有別于點(diǎn)式雜交：隨機(jī)生成一條與父代染色體長度相同的二進(jìn)制位串，其中“0”表示不交換父代染色體對應(yīng)位置上的基因，“1”則表示交換，稱這條二進(jìn)制位串為雜交掩碼[10]。變異操作是按概率對染色體上隨機(jī)選取的基因位取反，該操作對恢復(fù)種群的多樣性有一定作用。首先產(chǎn)生一個在0到1之間的隨機(jī)數(shù)，如果變異率P≥，則將變異算子作用于父代染色體，隨機(jī)選取染色體上的變異位，變異位上的二進(jìn)制代碼是0則變?yōu)?，1則變?yōu)?。

其中，a、b、c、d為小于等于1的常數(shù)。父代染色體經(jīng)雜交變異操作獲得子代染色體，比較父代染色體和子代染色體的適應(yīng)度并將適應(yīng)度低的一方淘汰，適應(yīng)度高的一方進(jìn)入交配池。首先應(yīng)從適應(yīng)度優(yōu)于平均值的子種群popu1中每次隨機(jī)取出2個要參與雜交的個體，重復(fù)populsize/2次，并將待雜交個體順序放入雜交交配池中。

1.6 遺傳算法流程圖

遺傳算法的基本流程如圖2所示。終止條件：算法最大迭代次數(shù)=200。

圖2 遺傳算法流程圖

1.7 判斷算法標(biāo)記成功的方法

根據(jù)編碼規(guī)則，利用逆向思維對遺傳算法最終迭代結(jié)果進(jìn)行解碼操作，碼串中每長度為25的1個串經(jīng)解碼后可翻譯為1個節(jié)點(diǎn)標(biāo)記。每個節(jié)點(diǎn)由3條邊組成，而每條邊又可以作為另一個節(jié)點(diǎn)的1條邊，也就是說每個節(jié)點(diǎn)都與3個面鄰接，即將節(jié)點(diǎn)標(biāo)記根據(jù)節(jié)點(diǎn)標(biāo)記傳播理論“粘”起來可以形成一個封閉的“標(biāo)記環(huán)”，且每個節(jié)點(diǎn)屬于3個“標(biāo)記環(huán)”。將上述“標(biāo)記環(huán)”與所標(biāo)記的線圖進(jìn)行匹配，匹配成功則表示算法標(biāo)記成功，反之，則失敗。

1.8 改進(jìn)后的遺傳算法的優(yōu)越性

選取圖3所示的線圖作為實(shí)驗(yàn)對象比較改進(jìn)后遺傳算法(improved genetic algorithm，IGA)和理查德提出的標(biāo)記線圖的遺傳算法(genetic algorithm proposed by Richard，RGA)的收斂速度和穩(wěn)定性。RGA算法隨機(jī)生成初始種群，種群大小取100，選擇操作為一般輪盤賭法，采用多點(diǎn)交叉和基本位變異，雜交率取0.9，變異率取0.03；IGA算法中a取1，b取0.6，c取0.1，d取0.05。不限制算法的迭代次數(shù)，兩種算法各執(zhí)行50次，記錄算法成功率、獲得正確標(biāo)記所需的平均迭代次數(shù)，結(jié)果見表1。

圖3 實(shí)驗(yàn)線圖

表1 兩種算法實(shí)驗(yàn)結(jié)果比較

從表1的數(shù)據(jù)可以看出，RGA算法的成功率在30%左右，且收斂的代數(shù)偏大。IGA算法的成功率在58%左右，收斂代數(shù)明顯降低，改進(jìn)后遺傳算法的穩(wěn)定性和收斂速度相較于標(biāo)準(zhǔn)遺傳算法均有較大提升。

2 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)用的測試線圖如圖3所示，標(biāo)記后的線圖如圖4所示。遺傳算法用MATLAB R2012b編寫。統(tǒng)計(jì)遺傳算法成功標(biāo)記線圖的次數(shù)并計(jì)算其占總實(shí)驗(yàn)次數(shù)的比例(平均值)，繪制成折線圖，分析折線走勢探討遺傳算法的最佳參數(shù)設(shè)置，討論雜交率和變異率的選取對算法性能的影響。常數(shù)b和d是針對適應(yīng)度小于平均值的個體設(shè)置的雜交率和變異率，沿用RGA算法b取0.6，d取0.05。如果將實(shí)驗(yàn)變量、的取值編碼為－、－，上述希臘字母分別代表參數(shù)、的具體數(shù)值(表2)。設(shè)定參數(shù)為定值時研究參數(shù)取不同值時的成功率，表3的9個橫行代表代號為i~ix的9組實(shí)驗(yàn)，每組實(shí)驗(yàn)有9個不同的參數(shù)設(shè)置，每個參數(shù)設(shè)置對應(yīng)的遺傳算法均運(yùn)行50次，每次迭代200代，根據(jù)運(yùn)行結(jié)果計(jì)算每個參數(shù)設(shè)置對應(yīng)的算法成功標(biāo)記線圖的概率，計(jì)算出每組實(shí)驗(yàn)的平均成功率，反映在圖5折線的縱坐標(biāo)上；設(shè)定參數(shù)為定值時研究參數(shù)取不同值時算法標(biāo)記成功的概率，表3的9個縱列代表代號為I~IX的9組實(shí)驗(yàn)，按照上述方法繪制圖6。

圖4 標(biāo)記后的線圖

表2 參數(shù)a、c的取值

表3 18組實(shí)驗(yàn)參數(shù)設(shè)置

圖5 參數(shù)c對算法成功率的影響

圖6 參數(shù)a對算法成功率的影響

3 實(shí)驗(yàn)結(jié)果

由圖5可知，參數(shù)的變化對算法成功率的影響頗為顯著。當(dāng)大于0.2時，6幅線圖標(biāo)記成功的概率除了線圖(4)有小幅上升外均大幅下降，且當(dāng)大于0.35時，成功率基本上不足50%；當(dāng)位于區(qū)間[0，0.05]時，算法成功標(biāo)記線圖的概率較高，對于線圖(1)、(2)、(5)，算法成功率在取0.05時達(dá)到峰值，雖然在此區(qū)間內(nèi)線圖(3)、(4)和(6)標(biāo)記成功的概率呈下降趨勢，但就整體變化而言，下降趨勢相對較緩，且概率下降小于10%；當(dāng)位于區(qū)間[0.05，0.20]時，線圖(1)、(2)、(4)的成功率曲線均呈現(xiàn)不同程度的直線下降趨勢，線圖(3)、(4)、(6)的成功率曲線有所波動，但相比于區(qū)間[0，0.05]成功率是有所下降的。參數(shù)的選取直接影響種群中適應(yīng)度相對較高個體的變異率，且與變異率是正比關(guān)系，因此在選取參數(shù)時，最好不要在大于0.1的區(qū)間內(nèi)選取。實(shí)際上，小但非零變異率是種群進(jìn)化的重要手段，但不是算法最終收斂的關(guān)鍵因素。

分析圖6，隨著參數(shù)的變化，線圖成功率曲線波動較大，當(dāng)在某些小區(qū)間上增大時，成功率上升到某個上限便會有所下降，在區(qū)間[0.8，1.0]時曲線變化相對緩和且此時算法的成功率較高。參數(shù)的取值對應(yīng)種群中較優(yōu)秀個體的雜交率，且二者是正比關(guān)系。

綜上所述，參數(shù)屬于區(qū)間[0，0.05]且參數(shù)屬于區(qū)間[0.8，1.0]時為標(biāo)記線圖的遺傳算法的最優(yōu)參數(shù)設(shè)置。

4 結(jié)束語

遺傳算法雖然是一種廣泛應(yīng)用的全局搜索算法，但仍然存在許多不足，比如容易發(fā)生過早收斂、收斂速度慢、陷入局部最優(yōu)等問題。通?？梢詫⑦z傳算法與具有較強(qiáng)局部搜索能力的啟發(fā)式算法如爬山法、梯度法等結(jié)合起來，在一定程度上改進(jìn)遺傳算法的性能。

二進(jìn)制編碼的長度與線圖的節(jié)點(diǎn)數(shù)成正比。用遺傳算法標(biāo)記復(fù)雜線圖時，由于這類線圖包含數(shù)量可觀的節(jié)點(diǎn)，普遍存在編碼串過長的問題，算法的計(jì)算精度雖有提高，但由于算法的搜索空間急劇擴(kuò)大，計(jì)算量增加，導(dǎo)致算法的效率變差，同時會削弱變異算子對染色體的作用。可以嘗試從以下兩個方面改進(jìn)上述缺點(diǎn)：直接方法是換一種編碼策略，可以采取浮點(diǎn)數(shù)編碼，用在算法搜索空間較大的情形，便于將遺傳算法和經(jīng)典的優(yōu)化算法結(jié)合使用；間接方法就是從線圖著手，先將復(fù)雜線圖劃分為若干簡單線圖，對簡單線圖進(jìn)行標(biāo)記后再將其依據(jù)標(biāo)記的一致性或標(biāo)記的傳播理論“粘合”起來。

上述只探討了平面立體完整線圖的標(biāo)記情況，對于不完整的線圖，可以將線圖補(bǔ)全后再用改進(jìn)后的遺傳算法標(biāo)記。亦可以將上述方法根據(jù)曲面的標(biāo)記特點(diǎn)運(yùn)用于曲面立體線圖的標(biāo)記。

[1] HARALICK R M, SHAPIRO L G. The consistent labeling problem: Part I [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 173-184.

[2] MYERS R, HANCOCK E R. Genetic algorithms for ambiguous labeling problem [J]. Pattern Recognition, 2000, 33(4): 685-704.

[3] STANFILL C, WALTA D. Toward memory-based reasoning [J]. Communications of the ACM, 1986, 29(12): 1213-1228.

[4] HANCOCK E R, KITTLER J. Edge-labeling using dictionary-based relaxation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(2): 165-181.

[5] BONNICI A, CAMILLERI K P. A constrained genetic algorithm for line labeling of line drawings with shadows and table-lines [J]. Computers & Graphics, 2013, 37(5): 302-315.

[6] 李雅, 黃少濱, 李艷梅, 等. 基于遺傳算法的反例理解[J]. 哈爾濱工程大學(xué)學(xué)報, 2016, 37(10): 1394-1399.

[7] 曲志堅(jiān), 張先偉, 曹雁鋒, 等. 基于自適應(yīng)機(jī)制的遺傳算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(11): 3222-3225.

[8] GAO M T, CAI X P. Labeling line drawings with hidden-part-drawn of planar object with trihedral vertices [J]. Computer Aided Drafting, Design and Manufacturing, 2015, 25(2): 1-13.

[9] BURKS A R, PUNCH W F. An analysis of the genetic marker diversity algorithm for genetic programming [J]. Genetic Programming and Evolvable Machines, 2017, 18(2): 213-245.

[10] LATIF A H M M, BRUNNER E. A genetic algorithm for designing microarray experiments [J]. Computational Statistics, 2016, 31(2): 409-424.

[11] LI H Y, ZUO H F, LIANG K, et al. Optimizing combination of aircraft maintenance tasks by adaptive genetic algorithm based on cluster search [J]. Journal of Systems Engineering and Electronics, 2016, 27(1): 140-156.

A Self-Adaptive Genetic Algorithm for Labeling Line Drawings of Planar Objects

XIONG Siying, DONG Lijun

(College of Mechanical Engineering, Taiyuan University of Technology, Taiyuan Shanxi 030024, China)

This paper improves the genetic algorithm for labeling line drawings presented by Richard Myers in the following areas: self-adaption parameter adjustment method was used, the hybridization rate and mutation rate of individuals with high fitness in the same generation were dynamically changed, and the rate of hybridization and mutation of individuals with lower fitness was set as a fixed value; the constraints were established when the initial population was created, with the aim of improving the uncertainty of the initial population coverage space and the relative irrationality of the individual distribution; the fitness function of the genetic algorithm was modified so that the selection operator with the individual fitness as the index could correctly guide the algorithm to search the solution space. The genetic algorithm was employed to mark six different line drawings, the parameterandin the formula of hybridization rate and mutation rate were used as experimental variables, the change tendency of the algorithm’s mark success rate curve was analyzed, and the influence of operator parameter setting on the performance of genetic algorithm was discussed. The results show thatbelongs to interval [0, 0.05] andbelongs to interval [0.8, 1.0] andis the optimal parameter setting of the genetic algorithm for labeling line drawings.

line drawing label; genetic algorithm; binary coding; fitness

TP391.41

10.11996/JG.j.2095-302X.2018061105

A

2095-302X(2018)06-1105-07

2018-03-15；

2018-03-28

熊思穎(1993-)，女，江西九江人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：1140980289@qq.com

董黎君(1962-)，女，山西運(yùn)城人，教授，博士，碩士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、圖學(xué)理論及應(yīng)用。E-mail：dlj_lmq@163.com