鄭朝鑫, 董 晨, 葉 尹

(1.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108； 2.福建省人大常委會(huì)，福建 福州 350001； 3.網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 福州 350108)

0 引言

目前比較流行的3D建模方式是三維激光掃描點(diǎn)云建模方式，文獻(xiàn)[1-2]展示了這種方式建模可以達(dá)到極高的模型精度.微軟公司也推出Kinect，文獻(xiàn)[3-4]介紹Kinect技術(shù)以及利用Kinect進(jìn)行3D建模的實(shí)現(xiàn)方法.另外一種比較特殊的3D建模方式是從2D圖片中進(jìn)行摳圖建模，文獻(xiàn)[5]詳細(xì)地介紹這種建模方法的具體實(shí)現(xiàn)以及技術(shù)細(xì)節(jié).遺傳算法(genetic algorithm，GA)是將生物界中的自然選擇和種群遺傳學(xué)原理引入到算法的搜索過(guò)程中，具有強(qiáng)大的魯棒性以及搜索性能.文獻(xiàn)[6]展示如何直接利用經(jīng)典遺傳算法來(lái)解決智能事件辨識(shí)問(wèn)題、傳感器數(shù)量配置優(yōu)化問(wèn)題.文獻(xiàn)[7-9]研究遺傳算法的改進(jìn)方法以及具體的實(shí)現(xiàn)步驟，并用大量的仿真實(shí)驗(yàn)數(shù)據(jù)證明改進(jìn)后的混合遺傳算法具備更加強(qiáng)大的搜索性能.文獻(xiàn)[10]提出一種基于遺傳算法的入侵檢測(cè)特征選擇方法，提高系統(tǒng)的檢測(cè)效率.文獻(xiàn)[11]通過(guò)遺傳算法中編碼技術(shù)和基因技術(shù)分析，在社交網(wǎng)站數(shù)據(jù)分析過(guò)程中發(fā)現(xiàn)不良信息和違法信息.

1 3D建模

動(dòng)態(tài)3D建模技術(shù)在家居裝修中，將需要求解房間的長(zhǎng)、寬、高, 以及用戶身高作為多維空間中的一組可能解.利用遺傳算法進(jìn)行搜索計(jì)算最優(yōu)可能解，最后得到8組標(biāo)定向量誤差最小的解.在本文中，需要利用陀螺儀傳感器輸出數(shù)據(jù)，實(shí)現(xiàn)測(cè)量立方體房間中心點(diǎn)與墻角連線的單位向量數(shù)值.這個(gè)過(guò)程中存在著設(shè)備誤差以及人工站在房間中心點(diǎn)對(duì)準(zhǔn)墻角位置進(jìn)行輔助標(biāo)定的人為操作誤差，如圖1.歸納可得本文中的優(yōu)化問(wèn)題是利用遺傳算法對(duì)陀螺儀測(cè)量數(shù)據(jù)的各種誤差進(jìn)行有效性的優(yōu)化，最后計(jì)算得到現(xiàn)場(chǎng)房間單位比例的長(zhǎng)寬高尺寸.3D模型本身尺寸單位是點(diǎn)或者說(shuō)像素，與現(xiàn)實(shí)物體尺寸只是比例映射關(guān)系，所以陀螺儀簡(jiǎn)易測(cè)量可通過(guò)遺傳算法得到房間最佳的長(zhǎng)寬高比例信息，即可實(shí)現(xiàn)3D建模目的.

圖1 不同用戶測(cè)量同一房間產(chǎn)生的坐標(biāo)系原點(diǎn)偏差示意圖Fig.1 Different users measure the frame origin deviation of the same room

2 遺傳算法

2.1 編碼方式

基因編碼選擇實(shí)數(shù)編碼方式.系統(tǒng)需要求解的目標(biāo)有4個(gè)實(shí)數(shù)值，分別對(duì)應(yīng)房間長(zhǎng)度、寬度、高度、用戶身高，通過(guò)遺傳算法將4個(gè)參數(shù)優(yōu)化后，就可以通過(guò)3D引擎創(chuàng)建一個(gè)3D房間模型并設(shè)置正確的攝像頭位置視野與實(shí)際房間尺寸及用戶視野一一映射，如圖2.

圖2 各視野與實(shí)際房間尺寸一一映射Fig.2 Each view is mapped to the actual room size

算法種群第i個(gè)個(gè)體的編碼定義為：Xi={w,l,h,b}，其中w為房間長(zhǎng)度，l為房間寬度，h為房間高度，b為用戶身高.在系統(tǒng)中用戶操作進(jìn)行標(biāo)定的向量是8個(gè)，8個(gè)標(biāo)定向量與個(gè)體信息間的關(guān)系如下式.

(1)

這樣經(jīng)過(guò)式(1)對(duì)解進(jìn)行轉(zhuǎn)換后，得到的8個(gè)向量就是遺傳算法能處理的搜索空間，遺傳算法可對(duì)這8個(gè)向量進(jìn)行交叉、變異等操作，并與標(biāo)定向量進(jìn)行適應(yīng)值匹配，如圖3.

圖3 房間墻角人工標(biāo)定步驟示意圖Fig.3 Schematic diagrams of manual calibration step in room corner

2.2 交叉操作

遺傳算法的交叉方式描述如下： 第i個(gè)子代染色體的交叉概率Pc，如果滿足執(zhí)行交叉運(yùn)算的條件，則雙親中的父親就選擇第i個(gè)子代染色體自身，數(shù)學(xué)表達(dá)為Xi={wi,li,hi,bi}，母親染色體則通過(guò)隨機(jī)選擇方法獲得，其數(shù)學(xué)表達(dá)式為Xj={wj,lj,hj,bj}，根據(jù)式(1)將父母的基因轉(zhuǎn)換成兩組8個(gè)向量的基因數(shù)據(jù)，在這個(gè)基礎(chǔ)上進(jìn)行交叉操作.

交叉操作具體步驟為： 1) 隨機(jī)產(chǎn)生Pi∈U(0, 1), 當(dāng)Pi>Pc，則這個(gè)染色體不滿足交叉概率，不進(jìn)行交叉運(yùn)算，跳轉(zhuǎn)到步驟8)，結(jié)束交叉操作; 2) 隨機(jī)生成1～8的隨機(jī)數(shù)，決定本次交叉的基因總數(shù)Ct; 3) 選擇父親染色體Xi，并根據(jù)式(1)計(jì)算得到父親基因數(shù)據(jù)8個(gè)向量，隨機(jī)生成1～8的隨機(jī)數(shù)i，則選擇第i個(gè)向量Vi作準(zhǔn)備; 4) 隨機(jī)選擇母親染色體Xj，并根據(jù)式(1)計(jì)算得到母親基因數(shù)據(jù)8個(gè)向量，隨機(jī)生成1～8的隨機(jī)數(shù)j，則選擇第j個(gè)向量Vj; 5) 隨機(jī)生成步驟3)的隨機(jī)數(shù)k，選擇Vi的第k維分量浮點(diǎn)數(shù)，隨機(jī)生成步驟3)的隨機(jī)數(shù)m，選擇Vj的第m維分量浮點(diǎn)數(shù)，將Vi的k與Vj的m進(jìn)行交叉賦值實(shí)現(xiàn)向量Vi和Vj的交叉操作; 6) 交叉后的基因數(shù)據(jù)映射還原成新的染色體Xi和Xj替換原來(lái)的染色體數(shù)據(jù)，局部交叉成功; 7) 將Ct數(shù)值減1，判斷Ct是否大于1，如果大于1，代表整體交叉操作尚未結(jié)束，跳轉(zhuǎn)至步驟2)重復(fù)進(jìn)行; 8)Ct為0，結(jié)束交叉操作.

2.3 變異操作

變異運(yùn)算，采用染色體中的一個(gè)隨機(jī)基因，用新的隨機(jī)數(shù)賦值實(shí)現(xiàn)基因變異的目的.遺傳算法變異方式描述如下： 子代第i個(gè)染色體Xi={wi,li,hi,bi}的變異概率Pm滿足變異條件，則將染色體根據(jù)式(1)解碼成基因信息得到8個(gè)向量數(shù)據(jù)，然后進(jìn)行變異操作.

變異操作具體步驟為： 1) 隨機(jī)產(chǎn)生Pi∈U(0, 1), 當(dāng)Pi>Pm，則此染色體不滿足變異條件，不進(jìn)行變異操作運(yùn)算，跳轉(zhuǎn)至步驟6)，結(jié)束變異操作; 2) 選擇變異染色體Xi，并根據(jù)式(1)計(jì)算得到8個(gè)向量的基因數(shù)據(jù); 3) 隨機(jī)產(chǎn)生ζk∈U(0, 1)，令j=(Int(ζk×8)+1) ，則j∈[1, 8]，這里Int表示取整運(yùn)算.選擇第j個(gè)向量Vj; 4) 隨機(jī)生成一個(gè)符合向量取值范圍內(nèi)的浮點(diǎn)數(shù)更新替換向量Vj; 5) 變異后的基因數(shù)據(jù)映射還原成新的染色體Xi，更新染色體數(shù)據(jù)，完成第i個(gè)染色體的變異操作; 6) 結(jié)束變異操作.

2.4 選擇策略

遺傳算法通過(guò)選擇操作模擬實(shí)現(xiàn)種群的繁衍過(guò)程.選擇即是擇優(yōu)，因此選擇操作是基于適應(yīng)值計(jì)算結(jié)果的過(guò)濾方法，每個(gè)個(gè)體被選擇的概率Pi計(jì)算公式如下：

(2)

種群進(jìn)行選擇操作具體步驟為： 1) 根據(jù)種群規(guī)模NP參數(shù)大小，設(shè)置擇優(yōu)操作的次數(shù)St=NP，初始化ids=0; 2) 準(zhǔn)備對(duì)種群第ids個(gè)新染色體個(gè)體進(jìn)行擇優(yōu)操作; 3) 隨機(jī)生成一個(gè)0～1之間的隨機(jī)數(shù)P; 4) 初始化i=0，從第i個(gè)個(gè)體Xi開(kāi)始，根據(jù)式(2)計(jì)算Xi的選擇概率Pi，令P=P-Pi.判斷P是否大于0，如果P小于0，則跳轉(zhuǎn)到步驟6); 5)i=i+1，跳轉(zhuǎn)到步驟4)，繼續(xù)進(jìn)行輪盤旋轉(zhuǎn)選擇; 6) 得到種群中的第i個(gè)染色體，即選中染色體Xi.將Xi賦值給新一代種群中的第ids個(gè)空值染色體; 7) ids=ids+1，判斷ids是否小于St，如果小于St，則跳轉(zhuǎn)到步驟2); 8) 選擇操作完成，新一代種群染色體賦值全部完成，結(jié)束操作.

2.5 解決房間尺寸計(jì)算問(wèn)題

遺傳算法首先設(shè)置一定數(shù)量的種群，種群中的每個(gè)個(gè)體對(duì)應(yīng)問(wèn)題的一個(gè)可能解.需要求解的參數(shù)數(shù)量N即為解的維度，算法具體實(shí)現(xiàn)過(guò)程描述為： 存在一個(gè)N維空間，其中有M個(gè)個(gè)體組成的種群.個(gè)體i的表達(dá)方式為Xi={X1,X2, …,XN}，采用隨機(jī)賦值方式初始化種群，而后經(jīng)過(guò)選擇遺傳、交叉、變異操作，迭代得到新一代的規(guī)模為M的種群.

將標(biāo)定的8個(gè)向量Vi和可能解的8個(gè)向量Vxi都單位化之后，就具備在相同尺度下進(jìn)行比較的條件，下一步驟為計(jì)算8對(duì)向量的向量差，并求向量差的長(zhǎng)度值，最后求出適應(yīng)值，計(jì)算公式如下：

(3)

(4)

式(4)是計(jì)算適應(yīng)值的函數(shù)，其中DO的物理意義是可能解代表的房間墻角單位向量與實(shí)際房間墻角單位向量的偏差值.式(4)的前半段代表對(duì)8個(gè)DO偏差值進(jìn)行累計(jì)，作為綜合的偏差，偏差越大，數(shù)值就越小.偏差越小，數(shù)值就越接近1，即100%.后半段中，DO越小，代表兩個(gè)單位向量偏差越小，可能解代表的墻角的空間位置與實(shí)際房間墻角位置越靠近，1-DO的值也就越接近1, DO越大，1-DO的值就越小.式(5)的計(jì)算結(jié)果代表可能解與現(xiàn)實(shí)房間相似度，理論最大值為1，代表可能解100%與現(xiàn)實(shí)房間匹配.

遺傳算法實(shí)現(xiàn)具體步驟描述為： 1) 根據(jù)設(shè)計(jì)好的初始種群數(shù)量和遺傳代數(shù)設(shè)定參數(shù)，并對(duì)種群中每個(gè)染色體數(shù)據(jù)結(jié)構(gòu)用隨機(jī)數(shù)進(jìn)行初始化賦值，產(chǎn)生初始種群; 2) 執(zhí)行循環(huán)體操作，對(duì)種群每個(gè)染色體Xi={wi,li,hi,bi}，根據(jù)式(1)計(jì)算得到8個(gè)向量，然后以8個(gè)向量為參數(shù)進(jìn)行適值函數(shù)運(yùn)算，適應(yīng)值函數(shù)按照式(3)和式(4)計(jì)算可得.依此求得每個(gè)個(gè)體生存適應(yīng)值fitness，并且保存記錄具有最佳適應(yīng)值的個(gè)體染色體信息; 3) 根據(jù)每個(gè)染色體個(gè)體的生存適應(yīng)值執(zhí)行選擇策略，適應(yīng)值越大則染色體被選擇的概率Pi根據(jù)式(2)計(jì)算得到的數(shù)值越大，能獲得的遺傳生存幾率越大，以此選擇出下一代種群; 4) 對(duì)新一代的種群執(zhí)行交叉運(yùn)算操作; 5) 對(duì)新一代的種群執(zhí)行變異運(yùn)算操作.讓種群的個(gè)體在選擇、交叉及變異算子作用下不斷向更好的適應(yīng)能力方向進(jìn)化; 6) 判定算法停止條件，如果循環(huán)次數(shù)達(dá)到預(yù)定的遺傳代數(shù)NG，則退出循環(huán)操作，跳轉(zhuǎn)至步驟7).如果不滿足算法停止條件，則跳轉(zhuǎn)至步驟2); 7) 所記錄下來(lái)的最佳適應(yīng)值就是最優(yōu)解組合，可通過(guò)最佳染色體信息解算出房間的8個(gè)墻角頂點(diǎn)空間位置，結(jié)束算法.

3 改進(jìn)遺傳算法

由于遺傳算法每次發(fā)生種群迭代時(shí)，主要的操作是擇優(yōu)，以保證新一代的種群比上一代更優(yōu)，這是遺傳算法的優(yōu)勢(shì)，同樣也導(dǎo)致容易陷入局部最優(yōu).遺傳算法設(shè)置跳出局部最優(yōu)的操作是交叉和變異.在本文中，一種有目的性的嘗試突破當(dāng)前最優(yōu)適應(yīng)值的改進(jìn)的擇優(yōu)操作方式被提出.有意識(shí)的突破最優(yōu)的擇優(yōu)方式可參考粒子群算法的優(yōu)化過(guò)程，當(dāng)粒子群中有最優(yōu)個(gè)體時(shí)，其他個(gè)體的迭代更新方式是有目的的優(yōu)化.當(dāng)遺傳算法的種群擇優(yōu)就能提高種群的最佳適應(yīng)值時(shí)，擇優(yōu)操作相比經(jīng)典遺傳算法得到改進(jìn).

3.1 實(shí)現(xiàn)步驟

改進(jìn)遺傳算法種群進(jìn)行遺傳時(shí)，大部分的步驟及其描述都是相同的，其中遺傳操作的核心思想做了修改，從普通的擇優(yōu)遺傳操作改進(jìn)為有意識(shí)的突破最優(yōu)的擇優(yōu)方式.具體步驟為： 1) 根據(jù)種群規(guī)模NP參數(shù)大小，設(shè)置擇優(yōu)操作的次數(shù)St=NP，初始化ids=0; 2) 準(zhǔn)備對(duì)種群第ids個(gè)新染色體個(gè)體進(jìn)行擇優(yōu)操作; 3) 隨機(jī)生成一個(gè)0～1之間的隨機(jī)數(shù)P; 4) 初始化i=0，從第i個(gè)個(gè)體Xi開(kāi)始，根據(jù)式(2)計(jì)算Xi的選擇概率Pi，令P=P-Pi.判斷P是否大于0，如果P小于0，則跳轉(zhuǎn)到步驟6); 5)i=i+1，跳轉(zhuǎn)到步驟4)，繼續(xù)進(jìn)行輪盤選擇; 6) 得到種群中的第i個(gè)染色體，即選中染色體Xi.利用粒子群算法中的公式對(duì)染色體的四維參數(shù)的所有方向進(jìn)行預(yù)處理，計(jì)算所有方向的最佳適應(yīng)值，有目的地留取最佳適應(yīng)值數(shù)值最大的方向作為新染色體Xk, 令Xi=Xk; 7) 將有意識(shí)的嘗試突破最優(yōu)適應(yīng)值的方式得到的新染色體賦值給新一代種群的第ids個(gè)空值染色體; 8) ids=ids+1，判斷ids是否小于St，如果小于St，則跳轉(zhuǎn)到步驟2); 9) 改進(jìn)的擇優(yōu)操作完成，新一代種群染色體賦值全部完成，結(jié)束操作.

3.2 性能分析

對(duì)改進(jìn)遺傳算法和經(jīng)典遺傳算法的搜索結(jié)果進(jìn)行橫向?qū)Ρ?測(cè)試平臺(tái)分別運(yùn)行兩種算法，令種群規(guī)模NP=800，交叉概率Pc=0.7，變異概率Pm=0.02，遺傳代數(shù)NG=500.兩種算法采用的參數(shù)完全相同，初始化時(shí)的目標(biāo)解也標(biāo)定為相同目標(biāo)解，測(cè)試結(jié)果如表1所示.

表1 遺傳算法及其改進(jìn)算法性能實(shí)驗(yàn)

測(cè)試結(jié)果： 經(jīng)典遺傳算法得到的最佳適應(yīng)值，不如改進(jìn)的遺傳算法.改進(jìn)算法搜索得到的最優(yōu)解比遺傳算法更加逼近目標(biāo)解.結(jié)果表明改進(jìn)算法確實(shí)表現(xiàn)出更優(yōu)的搜索性能.

從改進(jìn)遺傳算法的某個(gè)染色體角度比較.令種群規(guī)模NP=800，交叉概率Pc=0.7，變異概率Pm=0.02，遺傳代數(shù)NG=500，目標(biāo)解為{0.559 718, 0.204 419, 0.803 074, 0.209 286}，測(cè)試結(jié)果如表2所示.

表2 改進(jìn)遺傳算法隨機(jī)染色體個(gè)體迭代過(guò)程

從第一次和第二次迭代數(shù)據(jù)看出，改進(jìn)遺傳算法有強(qiáng)大的全局搜索能力，兩次迭代后，個(gè)體快速向目標(biāo)解靠近.第三次迭代中的第一維數(shù)據(jù)出現(xiàn)嚴(yán)重偏移目標(biāo)解的現(xiàn)象，表明改進(jìn)遺傳算法的交叉或者變異機(jī)制觸發(fā)了操作，這種操作也保證種群多樣性.第四次迭代時(shí)，染色體更新信息來(lái)自適應(yīng)值更高的上一代染色體.第67次迭代中的第四維信息、第239次迭代出現(xiàn)在第一維的信息，都是屬于變異操作的影響.

4 實(shí)驗(yàn)結(jié)果與分析

使用遺傳算法對(duì)6組不同長(zhǎng)度、寬度、高度的房間以及不同身高的用戶做動(dòng)態(tài)3D建模優(yōu)化實(shí)驗(yàn)，如表3所示.表中的偏差率代表計(jì)算出來(lái)的房間尺寸與現(xiàn)實(shí)房間尺寸的偏差大小，偏差率大小與算法計(jì)算出來(lái)的身高成正比.當(dāng)算法隨機(jī)產(chǎn)生的可能解中的身高越接近用戶的真實(shí)身高時(shí)，算法計(jì)算得到的房間尺寸就無(wú)限接近真實(shí)房間尺寸.偏差率的大小不影響裝修預(yù)覽效果，預(yù)覽匹配數(shù)值代表3D模型中對(duì)應(yīng)的墻角空間位置與現(xiàn)實(shí)房間的墻角空間位置的匹配百分比.從實(shí)驗(yàn)數(shù)據(jù)知，預(yù)覽匹配率平均在99%左右，說(shuō)明該3D動(dòng)態(tài)實(shí)時(shí)建模方法具有不錯(cuò)的精確匹配率.

表3 不同房間的遺傳算法優(yōu)化結(jié)果比較

5 結(jié)語(yǔ)

未來(lái)還可以研究提高改進(jìn)遺傳算法的運(yùn)行效率方法，縮短算法運(yùn)行消耗時(shí)間.可研究更好的適應(yīng)值表達(dá)函數(shù)，使得適應(yīng)值能更精確地表達(dá)虛擬房間與現(xiàn)實(shí)房間的相似度.目前只是針對(duì)立方體的房間進(jìn)行測(cè)量并建模，在這個(gè)基礎(chǔ)上以后還能對(duì)測(cè)量方法進(jìn)行擴(kuò)展，可增加支持不規(guī)則房間的形狀及尺寸的測(cè)量建模，對(duì)室內(nèi)窗口、門口、墻垛、梁等信息采集和處理，具有比較好的現(xiàn)實(shí)適應(yīng)性，能在更多場(chǎng)合中使用，經(jīng)過(guò)擴(kuò)展的應(yīng)用將有更好的發(fā)展前景.