帆船VMG預測遺傳算法優(yōu)化

潘明杰， 任久春， 汪建波， 朱 謙

(復旦大學 信息科學與工程學院，上海 200433)

帆船VMG預測遺傳算法優(yōu)化

潘明杰， 任久春， 汪建波， 朱 謙

(復旦大學 信息科學與工程學院，上海 200433)

VMG(Velocity Made Good)泛指帆船在迎風階段船速于迎風方向上的分量，反映了帆船運動員利用風的能力。在前期研究中通過設計BP神經網絡模型對帆船VMG進行預測。為提高BP神經網絡預測的準確性，提出了采用遺傳算法對原網絡模型的權值及閾值進行優(yōu)化，并對網絡重新進行學習訓練。對比結果表明，使用遺傳算法優(yōu)化后的BP模型在多項指標上都有了明顯提高。

VMG; 時間序列預測; 遺傳算法; BP算法; 神經網絡

0 引言

帆船運動中，運動員對海風的利用效率將直接影響到最終的比賽成績[1]。VMG(Velocity Made Good)，是現在國際上通用的描述運動員利用海風水平的重要指標之一，其意為帆船船速在迎風方向上的分量，也是運動員選擇航線的重要依據。對運動員而言，若能在行駛過程中，了解到其下一時刻、甚至下一時段的VMG變化情況，則可根據此預測情況實時調整路線、修改戰(zhàn)術，從而爭取更有利的行駛策略。因此，若能實現對VMG的預測，則無疑將為運動員科學、合理地選擇行進路線提供重要依據。

考慮到帆船在運動過程中，會受到環(huán)境與人為操作的雙重影響，采用傳統(tǒng)力學的分析方法較難對運動規(guī)律進行準確描述[2]。神經網絡由于無需事先了解事物的內部關系，通過對樣本的學習訓練來對事物關系進行近似擬合，在該方面則具有較好的應用前景。結合前期研究，我們發(fā)現可以通過使用BP神經網絡模型對帆船VMG進行一定的預測[3]。

但由于BP模型易陷入局部極小值及收斂速度慢[4]，因此，會導致學習效率較低且會存在一定誤差，而如何提高對VMG的預測性能即是本文的研究重點。我們加入遺傳算法對原有模型進行優(yōu)化。遺傳算法的本質在于，通過遺傳算子模擬遺傳過程中出現的復制、交叉和變異等現象對種群個體逐代擇優(yōu)，從而獲得最優(yōu)個體。因此，我們可以通過前期學習訓練，對BP網絡模型的權值及閾值進行調整，將遺傳算法中所獲得最優(yōu)個體對BP網絡模型的初始權值及閾值進行賦值，以加快網絡的學習速度及收斂速度。對比結果表明，使用遺傳算法優(yōu)化的BP模型相較于原有模型在多項指標上有了明顯改善。

1 VMG定義

在運動員駕駛帆船時，如何確定帆船行駛策略主要參考兩個標準：

(1) 在自然風向上，是否使船速在最短路徑上的分速度到達最大；

(2) 在航標連線方向上，是否更接近目標。

在帆船行駛過程中，往往以VMG作為最主要的參考標準。所謂VMG，是Velocity Made Good的縮寫，譯為有效航速。由于受到風的影響，在迎風階段運動員一般采用“之”字形航線駛向航標，因此，需要一個用于評價帆船向目標點行駛能力的參數，即VMG[5]。最初，其是指船速在目標方向上的分量，其與目標方向同相，該值越大，則表明行船效果越佳，也可理解為是狹義上VMG,如圖1所示。

圖1 狹義VMG定義

之后，隨著人們在此領域地深入研究，發(fā)現也可利用船速在真風方向上的分量對此進行表示。其所反映出運動員對風的駕馭能力更為明顯、直觀，因此也被理解為廣義上的VMG，本文所進行的研究都基于廣義VMG的概念基礎,如圖2所示。

圖2 廣義VMG定義

通過對VMG進行下一時刻、甚至下一時段的預測，對運動員而言具有以下作用：

(1) 若VMG持續(xù)減小，則可能意味著船向與風向間夾角過大，需要調整航向以減小此夾角；

(2) 若VMG保持穩(wěn)定或增大，則一般不需要對航向進行較大調整；

(3) VMG產生突變(如突然減小)，則表明此時風向可能有較大變化，需要調整航線，以改變船體受風模式(受風模式將在第5節(jié)進行詳細說明)。

在本系統(tǒng)中，各參數所組成的速度三角形模型,如圖3所示。

圖3 系統(tǒng)VMG示意圖

其中，VB表示帆船的實際速度，α表示帆船航向與實際風向間的夾角，所以，VMG的計算，如式(1)。

VMG=VB*cos(α)

(1)

2 遺傳算法

所謂遺傳算法，是一種參考生物界的進化規(guī)律演化而來的隨機化搜索方法。其由J.Holland教授于1975年提出，主要思想是利用變異、雜交、繁殖等手段，根據達爾文的適者生存、優(yōu)勝劣汰的理論選擇最優(yōu)點進行變異和雜交，從而產生新的后代。

對遺傳算法而言，其主要優(yōu)缺點有[6]：

(1) 搜索過程不直接作用于變量上，而是對參數集進行了編碼的個體上；

(2) 搜索過程是從一組解迭代到另一組解，以避免了陷入局部最優(yōu)解的可能性；

(3) 采用概率的變遷規(guī)則指導搜索方向；

(4) 對搜索空間無任何特殊要求，適應范圍廣；

(5) 編碼不規(guī)范及編碼存在表示的不確定性；

(6) 對算法的精度、計算復雜性等方面，尚未有有效的定量分析方法。

綜合以上特點，遺傳算法一般被用于[7]：

(1) 函數優(yōu)化問題

這是遺傳算法的經典應用領域。對一些非線性、多模型、多目標的函數優(yōu)化問題，相比其他優(yōu)化方法，遺傳算法在簡便性和效率上都有明顯優(yōu)勢。

(2) 車間調度問題

由于現實生產中，往往依靠經驗進行生產調度，而用常規(guī)數學模型無法有效對此進行精確求解。而依靠遺傳算法，則恰能對應此問題。目前遺傳算法在流水線生產車間調度、生產規(guī)劃、任務分配等方面都得到了有效應用。

(3) 機器學習問題

主要被用于學習模糊控制規(guī)則，可更好地改進模糊系統(tǒng)性能。

除此以外，遺傳算法還被使用在數據挖掘、自動控制、圖像識別等多個方面。

3 模型設計及優(yōu)化

為了減少訓練時間，原有的BP模型采用三層結構，即輸入層、隱含層及輸出層。各層的設定如下：

輸入層：根據式(1)及圖3可知，VMG是通過船速及帆船船向與海風的夾角所得。在船速方面，由于慣性的存在，當前時刻的船速既延續(xù)了上一時刻的船速狀態(tài)，又會受到當前時刻海風參數的影響；在夾角方面，因為需要通過當前風向與當前船向獲得，而當前時刻的船向同船速一樣，也是上一時刻帆船運動情況與當前時刻的海風共同作用結果。因此，綜合這兩方面原因，我們將前一時刻的船速、船向及當前時刻的風速、風向作為輸入變量。

隱含層：此處參考式(2)[8]。其中，M、N分別為輸入層和輸出層結點數，a為1～10中任意的數，所以結點數在3至12之間。通過使用原有模型進行多次實驗，我們取結點數為8，如式(2)。

(2)

輸出層：即當前時刻的VMG。

此外，輸入層與隱含層間、隱含層與輸出層間的傳遞函數分別選用tansig函數及purelin函數。由此，原BP模型,如圖4所示。

圖4 BP網絡初始模型

對于原有BP模型而言，存在易陷入局部最小值及收斂速度慢的情況，而依靠遺傳算法則恰恰可以解決以上兩個問題，提高網絡性能，從而實現我們最初的預期。對于原有模型的遺傳算法優(yōu)化過程如下[9]，如圖5所示。

圖5 GA-BP網絡流程圖

(1)種群初始化

首先，對個體編碼采用浮點數編碼，個體編碼長度等于其決策變量的位數，而網絡的全部權值及閾值都被個體所包含。

(2)計算適應度

根據得到的BP神經網絡的初始權值及閾值，利用訓練數據對網絡進行訓練，并將網絡預測后的輸出與期望輸出根據式3進行處理，作為適應度函數，如式(3)。

(3)

(3)選擇操作

采用適應度比例法，首先采用輪盤賭選擇方法進行選擇操作，之后將當前群體中適應度最高的個體結構完整復制到下一代群體中。

(4)交叉操作

由于使用浮點數編碼，因此選用算數交叉法，即通過兩個體的線性組合產生兩個新的個體。

(5)變異操作

采用非一致變異法，對原有的基因值做一隨機擾動，將擾動后的結果作為變異后的新基因值。

4 仿真實驗及結果對比

實驗數據方面，考慮到帆船在迎風時，由于依靠伯努力效應的作用，大多采用折線形航線，無法沿航標間的連線行駛，所以迎風階段，帆船會出現左舷受風與右舷受風兩種模式,如圖6所示。

很明顯，即使對于同一個運動員，在這兩種模式下的駕駛習慣也幾乎不可能相同。因此，在確定訓練數據之前，需要依據其所受風的模式進行分類。

為將問題簡化，有以下假設：

(1)在同一天的訓練過程中，海風風向沒有較大變化；

(2)運動員在不同受風模式下的操作習慣不同，但在相同受風模式下習慣相同；

(3)行駛方向相同的航段受風模式相同。

基于以上假設，并利用自行研發(fā)的帆船多參數軌跡回放軟件對多條帆船軌跡進行查看后，我們發(fā)現：同一圈內，可將帆船多段折線形的行駛軌跡等效為三角形軌跡，即將同方向航段合并，從而將運動數據進行聚合分類，對問題進行簡化，如圖7所示。

之后，我們根據設定好的模型以前一秒船速、前一秒船向、當前真實海風速度、當前真實海風風向作為網絡輸入，以當前VMG作為網絡輸出。訓練數據選用2013年7月2日某個運動員某一圈訓練時采集到左舷受風模式下的數據，共450條。數據矩陣每一行的各項指標依次為前一秒船速，前一秒船向，當前真實海風速度，當前真實海風風向，當前VMG。而同一天另一圈左舷受風模式下的30條數據則作為驗證數據。

此外，實驗使用Matlab神經網絡工具箱作為主要建模工具，各參數設定如表1[10]所示。

表1 遺傳算法參數設定

在確定網絡模型及訓練數據后，即對網絡進行學習訓練，之后，利用訓練后的模型對驗證數據進行預測，并與實際結果進行對比。訓練結果及預測對比如圖8至圖10所示。

同時，我們對該網絡進行了多次實驗，實驗結果，如表2所示。

圖8 GA-BP訓練結果

圖9 GA-BP網絡學習曲線

圖10 GA-BP網絡預測結果對比

訓練方法lm激勵函數tansig結點數8mse(10-2)1．511．521．421．511．55相對誤差(%)76．087．038．589．1

通過圖8至圖10及表2的結果，我們可以發(fā)現，在學習速率方面，優(yōu)化后的模型學習速率較快，在前100次內的訓練過程中，學習曲線下降明顯，之后下降趨勢逐漸減小，直至600次之后下降梯度小于系統(tǒng)設定值，因此訓練停止；而在mse及相對誤差方面，始終分別約在1.5%及8%左右，且結合圖9，系統(tǒng)預測結果無論在趨勢及區(qū)間上都與實際數據相符，也說明使用遺傳算法優(yōu)化的BP模型同樣可對帆船VMG進行有效預測。

之后，我們對優(yōu)化前后的網絡模型進行相應對比?？梢钥吹剑诰W絡模型結構相同的情況下，優(yōu)化后的網絡在mse方面有明顯提高，約為原模型的1/5；相對誤差也下降了約25%,如表3所示。

表3 優(yōu)化前后的網絡模型訓練結果對比

此外，在學習次數方面，優(yōu)化后的網絡明顯下降，學習過程在要求時間內即告完成。由此，可以說明，通過使用遺傳算法對網絡間的權值及閾值進行調整優(yōu)化，可有效地提高BP網絡性能，使學習速率及預測精度得到改善。

5 總結

本文基于之前的研究結果，針對BP神經網絡易陷入局部極小值及收斂速度慢的不足，為提高原有的BP(Back Propagation)神經網絡模型的網絡性能，使用遺傳算法進行優(yōu)化，通過對網絡各層間的權值及閾值進行調整，使原有模型在各項指標上(如mse，相對誤差等方面)均得到了一定的改善。同時，改善后的網絡在學習速率上得到明顯提高，學習曲線下降情況良好。結果表明，使用遺傳算法進行優(yōu)化可大大提高模型的收斂速度，優(yōu)化后的模型在帆船VMG預測問題上具有更好的預測能力。

[1] Detomi D, Parolini N, Quarteroni A. Mathematics in the Wind[J]. Monografias de la Real Academia de Ciencias de Zaragoza, 2009,31:35-56.

[2] 邢惠麗,魏振鋼,胡西厚,葛艷,雷國華. 賽場環(huán)境實時變化的帆船比賽最優(yōu)路徑規(guī)劃[J]. 計算機工程與應用, 2008,44(17):234-237.

[3] Titlow J D. A dynamic model for downwind sailing[J]. Ancient Interface. AIAA Symposium on the Aero/Hydronautics of sailing, AIAA,1977.

[4] 高慧,潘明杰,周翔等,帆船VMG時間序列模糊邊界研究[J].微型電腦應用, 2014, 30(7):30-34.

[5] 周政.BP神經網絡的發(fā)展現狀綜述[J].山西電子技術，2008(2):90-92.

[6] Ocean Sail. Velocity Made Good-Trading off course against speed[EB/OL]. ：http://www.oceansail.co.uk/Articles/VMGArticle.php.

[7] 馬永,賈俊芳,遺傳算法研究綜述[J].山西大同大學學報(自然科學版),2007,23(7):11-13.

[8] 葛繼科,邱玉輝,吳春明,蒲國林,遺傳算法研究綜述[J].計算機應用研究,2008,25(10):2911-2916.

[9] 畢小龍,袁勇,基于BP神經網絡的人口預測方法研究[J].武漢理工大學學報交通科學與工程版, 2007, 31( 6) : 556-558.

VMG Forecasting of Sailboat by Optimizing BP Neural Network Based on Genetic Algorithm

Pan Mingjie,Ren Jiuchun,Wang Jianbo,Zhu Qian

(School of Information Science and Technology,Fudan University,Shanghai 200433,China)

VMG(Velocity Made Good) means the projection of sailboat speed in the direction of true wind, and its value shows athletes’ ability in sailing against wind as well as ability in making use of wind. We have designed a back propagation model to predict VMG to predict the VMG. In order to increase the accuracy of the prediction, we take genetic algorithm to optimize the weights and threshold of the BP network. The result shows that the genetic algorithm can make significant improvement in many aspects of the BP network.

Velocity made good(VMG); Time series prediction; Genetic algorithm; Back propagation algorithm; Neural network

上海市科研計劃項目(14231202102)

潘明杰(1990-)，男，上海，復旦大學通信系，碩士研究生。研究方向：機器學習，無線傳感網絡 任久春(1974-)，男，上海，復旦大學通信系，講師，研究方向：通信網絡，機器學習，無線傳感網絡 汪建波(1986-)，男，江西，上海市水上運動中心科研成員，研究方向：帆船項目運動技術監(jiān)控與分析，比賽場地分析 朱 謙(1960-)，男，上海，復旦大學通信系，副教授，研究方向：無線傳感網絡

1007-757X(2017)03-0012-04

TP311

A

2016.03.30)