基于并列選擇遺傳算法的太陽影子定位方法

于 鵬， 劉澤鋒， 郭改慧， 陸金巧， 呂 楊

(1.陜西科技大學(xué) 文理學(xué)院， 陜西 西安 710021； 2.陜西科技大學(xué) 機(jī)電工程學(xué)院， 陜西 西安 710021)

基于并列選擇遺傳算法的太陽影子定位方法

于 鵬1， 劉澤鋒2， 郭改慧1， 陸金巧1， 呂 楊1

(1.陜西科技大學(xué) 文理學(xué)院， 陜西 西安 710021； 2.陜西科技大學(xué) 機(jī)電工程學(xué)院， 陜西 西安 710021)

根據(jù)“立竿見影”和竿影日照?qǐng)D的原理，提出了一種太陽影子定位方法.首先結(jié)合太陽高度角、太陽赤緯角，以理論影長(zhǎng)和實(shí)際影長(zhǎng)的相關(guān)系數(shù)最大和其誤差平方和最小為目標(biāo)函數(shù)建立了求太陽影子定位的多目標(biāo)優(yōu)化模型，并以測(cè)量地的經(jīng)緯度作為設(shè)計(jì)變量，運(yùn)用并行選擇的遺傳算法進(jìn)行求解，實(shí)現(xiàn)了對(duì)測(cè)量地的精準(zhǔn)定位.最后通過實(shí)例分析，指出與傳統(tǒng)的枚舉算法相比，本文采用的遺傳算法的求解結(jié)果無論在精度還是在收斂速度上都優(yōu)于傳統(tǒng)的枚舉算法.

太陽影子定位； 多目標(biāo)優(yōu)化； 并行選擇； 遺傳算法

0 引言

“立竿見影”現(xiàn)象揭示了在某地一根直立的桿，一天之內(nèi)其影子的長(zhǎng)度隨太陽位置的變化而變化的自然規(guī)律，在這種自然現(xiàn)象中，影長(zhǎng)的變化與桿所在的位置有著密切的聯(lián)系.通過觀察一個(gè)直桿的影長(zhǎng)隨時(shí)間的變化情況，確定直桿所在的位置，具有積極的科學(xué)意義與應(yīng)用價(jià)值.例如在建筑物的采光設(shè)計(jì)[1]中，可以用竿影日照?qǐng)D的原理來求某地的建筑物投射的影長(zhǎng)，進(jìn)而來確定建筑物的采光條件.再比如在光伏陣列的設(shè)計(jì)[2]中，可以通過建立地理經(jīng)緯度與影長(zhǎng)的數(shù)學(xué)模型來求得光伏陣列所在地的遮擋物的影長(zhǎng)變化，進(jìn)而合理設(shè)計(jì)陣列的排布間距.因此，設(shè)計(jì)一種簡(jiǎn)潔實(shí)用的算法，來實(shí)現(xiàn)太陽影子的定位就顯得尤為重要.

遺傳算法是20世紀(jì)70年代興起的一種全新的仿生優(yōu)化算法，它是在模擬達(dá)爾文生物進(jìn)化論和孟德爾遺傳學(xué)理論基礎(chǔ)上發(fā)展起來的一種概率優(yōu)化搜索算法.遺傳算法一經(jīng)提出，便引起了廣泛的關(guān)注[3-8]，眾多作者根據(jù)不同的目的，提出了一系列改進(jìn)的算法.例如，以解決單目標(biāo)問題為目的的順序選擇、大變異、自適應(yīng)等遺傳算法，以及以解決多目標(biāo)問題為目的的權(quán)重法、并列選擇法、共享函數(shù)法等遺傳算法[9].如何運(yùn)用遺傳算法來解決太陽影子定位問題，是本文要解決的一個(gè)核心問題.在本文中，作者采用逆推的思想，結(jié)合太陽高度角、太陽赤緯角，建立了求太陽影子定位的多目標(biāo)優(yōu)化模型，并運(yùn)用并行選擇的遺傳算法進(jìn)行求解，實(shí)現(xiàn)了對(duì)測(cè)量地的精準(zhǔn)定位.

1 太陽影子定位問題

1.1 設(shè)計(jì)變量確定

求解太陽影子定位問題的最終目的，是希望通過觀察未知地點(diǎn)某一天內(nèi)太陽影子的實(shí)際長(zhǎng)度，從而確定該地的經(jīng)、緯度，所以可以選取測(cè)量地的經(jīng)、緯度作為設(shè)計(jì)變量.由于東西半球晝夜相反，而本文是以東半球?yàn)檠芯繉?duì)象，所以設(shè)計(jì)變量的取值范圍為：

-90 ° ≤φ≤90 °

(1)

0 °<θ≤180 °

(2)

1.2 目標(biāo)函數(shù)的確定

實(shí)際影長(zhǎng)已知，而通過給定經(jīng)緯度的數(shù)值，可得到對(duì)應(yīng)的理論影長(zhǎng)，當(dāng)理論影長(zhǎng)接近或等于實(shí)際影長(zhǎng)時(shí)，此時(shí)的經(jīng)緯度值即為測(cè)量地點(diǎn).為此，以理論影長(zhǎng)和實(shí)際影長(zhǎng)的接近程度作為優(yōu)化的目標(biāo)函數(shù).由于一天內(nèi)的影長(zhǎng)變化為一個(gè)向量，而比較向量的接近程度可以從其方向(即變化規(guī)律)和數(shù)值大小兩方面比較.衡量變化規(guī)律的相似性用相關(guān)系數(shù)，相關(guān)系數(shù)越接近1，則說明兩個(gè)向量的變化規(guī)律越相似，衡量數(shù)值大小選用誤差平方和，誤差平方和越小說明兩個(gè)向量的偏離程度越小.經(jīng)過上述分析，建立以下兩個(gè)目標(biāo)函數(shù)：

(3)

(4)

1.3 約束條件

1.3.1 理論影長(zhǎng)的計(jì)算

假設(shè)某天某時(shí)刻太陽的位置如圖1所示，立于地面上的桿高為H，太陽光線通過桿頂P點(diǎn)，在地面上形成一個(gè)影子點(diǎn)P′，影子長(zhǎng)度OP為S′，太陽光線與地面的夾角為α.則其滿足的數(shù)學(xué)表達(dá)為

(5)

圖1 影子形成圖

1.3.2 太陽高度角的計(jì)算

太陽高度角是指某地太陽光線與該地作垂直于地心的地表切線的夾角，它隨地方時(shí)和太陽赤緯角的變化而變化.其計(jì)算公式[10]為：

sinβ=sinφsinσ+cosφcosσcost

(6)

式(6)中：β為太陽高度角，φ為當(dāng)?shù)氐木暥龋覟樘柍嗑暯?，t為地方時(shí)角，其位置如圖2所示.

圖2 太陽高度角示意圖

由于太陽光射到地球表面上時(shí)，會(huì)經(jīng)過大氣層，使太陽光發(fā)生折射，折射后的太陽高度角α的計(jì)算公式為：

(7)

由于影響大氣層的折射率的因素[11]較多，為了方便計(jì)算，取空氣折射率來近似代替，n=1.000 273.

1.3.3 地方時(shí)角的計(jì)算

本文以東半球?yàn)檠芯繉?duì)象，則對(duì)應(yīng)的地方時(shí)角的推導(dǎo)公式為：

(8)

式(8)中：T為北京時(shí)間，θ為當(dāng)?shù)亟?jīng)度.

1.3.4 太陽赤緯角的計(jì)算

太陽赤緯角[12]是地球赤道平面與太陽和地球中心的連線之間的夾角，赤緯角以一年為周期，在南北回歸線的范圍內(nèi)移動(dòng)，這成為季節(jié)的標(biāo)志，其近似的計(jì)算公式為：

sinσ=0.397 95cos[0.985 63/(N-173)]

(9)

式(9)中：N為日數(shù)，從1月1日算起，取值范圍為0≤N≤365.

1.3.5 優(yōu)化模型

根據(jù)上述的目標(biāo)函數(shù)和約束條件，建立太陽影子定位的優(yōu)化模型為：

2 遺傳算法求解太陽影子定位問題

2.1 并行選擇的遺傳算法

并行選擇[9]的基本思想是先將群體中的全部個(gè)體按子目標(biāo)函數(shù)的數(shù)目均等地劃分為一些子群體，對(duì)每個(gè)子群體分配一個(gè)子目標(biāo)函數(shù)，各個(gè)子目標(biāo)函數(shù)在相應(yīng)的子群體中獨(dú)立地進(jìn)行選擇運(yùn)算，各自選擇出適應(yīng)度高的個(gè)體組成一個(gè)新的子群體，然后再將所有這些新生成的子群體合并成一個(gè)完整的群體，在這個(gè)群體中進(jìn)行交叉和變異運(yùn)算，從而生成下一代的完整群體，如此不斷地進(jìn)行“分割-并列選擇-合并”操作，最終可求出多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解.

圖3為并列選擇的遺傳算法示意圖.

圖3 并列選擇遺傳算法的示意圖

2.2 算法步驟

(1)對(duì)設(shè)計(jì)變量經(jīng)度、緯度，用格雷碼進(jìn)行編碼，根據(jù)每個(gè)變量的精度和變化范圍確定其對(duì)應(yīng)的編碼個(gè)數(shù)為21.其對(duì)應(yīng)的編碼公式[9]為：

2mj<(bj-aj)×10n≤2mj-1

(10)

式(10)中：[aj,bj]為變量的取值范圍，mj為二進(jìn)制編碼的個(gè)數(shù)，n為變量精度.

(2)采用隨機(jī)的方法產(chǎn)生個(gè)體數(shù)為100的初代種群，且設(shè)置最大遺傳代數(shù)為50，使用遺傳代溝為0.9；

(11)

式(11)中：Ni為種群的大小，P為根據(jù)目標(biāo)函數(shù)的大小所確定的個(gè)體在種群的位置，sp為選擇壓力，一般取1.7.

(4)對(duì)上一步生成的種群，采用單點(diǎn)交叉[9]的方式，如圖4所示，生成新的種群，交叉概率取0.7；

圖4 單點(diǎn)交叉運(yùn)算的示意圖

(5)為了避免問題過早收斂，對(duì)新種群的個(gè)體進(jìn)行變異操作，變異概率取0.01；

(6)由于遺傳代溝的存在，為了保證每一代的種群個(gè)數(shù)不變，對(duì)種群進(jìn)行重插入.采用的策略為基于適應(yīng)度插入方法，用子代代替適應(yīng)度小的父代.

(7)判斷種群是否達(dá)到最大遺傳代數(shù)，如果未達(dá)到則轉(zhuǎn)向步驟3，否則此時(shí)種群中適應(yīng)度最大的個(gè)體所對(duì)應(yīng)的目標(biāo)函數(shù)值，即為全局最優(yōu)解.

遺傳算法的具體工作流程如圖5所示.

圖5 遺傳算法的流程圖

3 實(shí)例運(yùn)算與結(jié)果分析

3.1 實(shí)例問題

通過測(cè)量得到某地在4月18日中從14∶42到15∶42的長(zhǎng)度為2 m的直桿在水平地面上的太陽影子頂點(diǎn)坐標(biāo)數(shù)據(jù)如表1所示，其中直桿垂直于地面，以桿的底端為坐標(biāo)原點(diǎn)，水平面為xy平面.給出可能的地點(diǎn).(以上數(shù)據(jù)來源于2015年全國(guó)大學(xué)生數(shù)學(xué)建模大賽)

表1 某地4月18日桿的影子坐標(biāo)數(shù)據(jù)表

3.2 運(yùn)算結(jié)果

本問題在2015年全國(guó)大學(xué)生數(shù)學(xué)建模大賽中采用了枚舉法進(jìn)行求解，在給定經(jīng)緯度搜索的步長(zhǎng)為1度的情形下，最終得到的最優(yōu)解為：

z1=1.15×10-6,z2=0.100 5

對(duì)應(yīng)的經(jīng)緯度為(108 °E,17 °N)，搜索用時(shí)4 min.

運(yùn)用上述的并列選擇的遺傳算法，并使用Mat lab編程，對(duì)模型進(jìn)行求解，由于遺傳算法在求解中具有隨機(jī)性，我們多次運(yùn)行程序，計(jì)算結(jié)果如表2所示.

表2 遺傳算法求解結(jié)果匯總表

對(duì)計(jì)算結(jié)果進(jìn)行分析，最終得到最優(yōu)解

z1=2.61×10-8,z2=4.41×10-4

對(duì)應(yīng)的經(jīng)緯度為(109.02 °E,18.76 °N)遺傳算法收斂的時(shí)間為8 s.

3.3 結(jié)果分析

比較2015年全國(guó)大學(xué)生數(shù)學(xué)建模大賽所給的準(zhǔn)確地點(diǎn)(109.5 °E,18.3 °N)，本文給出的結(jié)果是比較理想的.當(dāng)然本文所給結(jié)果仍有一定誤差，這主要是由折射率數(shù)值的選取和搜索誤差造成的.不過就求解的過程而言，本文所用的方法與枚舉算法相比，求解結(jié)果的精度更高，收斂的時(shí)間更短.

4 結(jié)論

本文針對(duì)太陽影子定位問題，建立了多目標(biāo)優(yōu)化模型，并運(yùn)用并行選擇的遺傳算法進(jìn)行求解，最終通過實(shí)例分析，指出應(yīng)用并行選擇遺傳算法進(jìn)行太陽影子定位問題的求解，不僅收斂速度快，而且能夠避免陷入局部最優(yōu)化，因此該方法是一種值得推廣的好方法.

[1] 鄭鵬飛,林大均,劉小羊,等.基于影子軌跡線反求采光效果的技術(shù)研究[J].華東理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2010，36(3):458-463.

[2] 張文華,司德亮,徐淑通,等.太陽影子倍率的計(jì)算方法及其對(duì)光伏陣列布局的影響[J].太陽能,2011(9):28-31.

[3] Tang Kezong,Sun Tingkai,Yang Jingyu.An improved genetic algorithm based on a novel selection strategy for nonlinear program-mingproblems[J].Computers and Chemical Engineering，2011，35(4):615-621．

[4] 劉淳安，王宇平.基于新模型的多目標(biāo)遺傳算法[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2005，32(2):260-267．

[5] 于志剛,宋申民,段廣仁.遺傳算法的機(jī)理與收斂性研究[J].控制與決策，2005，20(9):971-980．

[6] Ding Wanfu,Guo Ruifeng,Qin Chenggang,et al.A fault-tolerant scheduling algorithm with software fault tolerance in hard real-time systems[J].Journal of Computer Research and Development,2011,48(4):691-698.

[7] 馬永杰,云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2012,29(4):1 201-1 206.

[8] 林基明,班文嬌,王俊義,等.基于并行遺傳-最大最小蟻群算法的分布式數(shù)據(jù)庫(kù)查詢優(yōu)化[J].計(jì)算機(jī)應(yīng)用 ,2016,36(3):675-680.

[9] 雷英杰,張善文,李續(xù)武,等.MATLAB遺傳算法工具箱及其應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2005.

[10] 王昌名.可照時(shí)數(shù)和太陽高度角計(jì)算公式的簡(jiǎn)化證明[J].山東氣象,1989(2):46-48.

[11] 金群鋒.大氣折射率影響因素的研究[D].杭州:浙江大學(xué),2006:4-5.

[12] 陳曉勇,鄭科科.對(duì)建筑日照計(jì)算中太陽赤緯角公式的探討[J].浙江建筑,2011,28(9):6-8.

[13] 梁昔明，朱燦，顏東煌.基于物種選擇的遺傳算法求解約束非線性規(guī)劃問題[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，40(1):185-189.

【責(zé)任編輯：蔣亞儒】

Positioning method by the shadow of the sun based on parallel selected genetic lgorithm

YU Peng1, LIU Ze-feng2, GUO Gai-hui1, LU Jin-qiao1, LV Yang1

(1.School of Arts and Sciences， Shaanxi University of Science & Technology, Xi′an 710021, China； 2.College of Mechanical and Electrical Engineering, Shaanxi University of Science & Technology, Xi′an 710021, China)

According to the natural phenomenon that produces a shadow of objects under direct sunlight and the formation principle of stick sunlight shadow chart,the positioning method by the shadow of the sun is offered.Combined with relevant knowledge such as solar altitude and declination of sun.The multiple object optimization model,whose objective fun-ction is the maximum of correlation coefficient and the minimum of error sum of squares about practical and theoretical shadow′s length,is built.Regarding longitude and latitude of measure area as design variables,the measure area is confirmedwith parallelism selection genetic algorithm.In the analysis of case, compared with enumeration method,there is the truth that,the result by genetic algorithm is more accurate and the solution speed is faster than enumeration method.

positioning by the shadow of the sun; multiple object optimization; parallelism selection; genetic algorithm

2016-07-21

國(guó)家自然科學(xué)基金項(xiàng)目(11401356)

于 鵬(1981-)，男，寧夏永寧人，講師，碩士，研究方向：不確定推理

1000-5811(2017)01-0193-05

TP391

A