改進遺傳算法在共享單車停放點分配中的應(yīng)用*

施嘉偉， 陳觀林,， 徐 煌

(1.安徽理工大學(xué) 計算機科學(xué)與工程學(xué)院，安徽 淮南 232000；2.浙江大學(xué)城市學(xué)院 計算機與計算科學(xué)學(xué)院，浙江 杭州 310015)

0 引 言

共享單車停車服務(wù)請求過多時存在著競爭關(guān)系，加上車輛與停放點之間的數(shù)量制約，處理請求的順序不同使得分配效果會有所差異，造成總距離代價不同。在停放點分配問題中的優(yōu)化目標不止一個，需要使用多目標優(yōu)化算法[1]。而遺傳算法本身屬于隨機搜索類算法，在實際應(yīng)用中很容易陷入局部最優(yōu)的情況，因此需要對其進行改進。

文獻[4]提出了一種自適應(yīng)量子旋轉(zhuǎn)門更新方式改變了種群進化的方向，從而提高算法的全局搜索能力。文獻[5]提出了一種融合貪心算法的遺傳算法在倉儲車輛調(diào)度優(yōu)化中的應(yīng)用，讓交叉、變異用起來更加靈活，有效的提升了算法的調(diào)度效率。文獻[6]在傳統(tǒng)的滑膜控制方法加入了神經(jīng)網(wǎng)絡(luò)，利用Lyapunov函數(shù)推導(dǎo)了神經(jīng)網(wǎng)絡(luò)權(quán)值的自適應(yīng)律，提高了原方法一定的精度。文獻[7]提出了一種新的智能停車系統(tǒng)原型，采用遺傳算法解決了停車場車輛調(diào)度問題。文獻[8]目標是使加權(quán)流量和庫存成本之和最小化，為了有效地求解該模型，開發(fā)出基于遺傳算法的啟發(fā)式算法。

線性回歸是機器學(xué)習(xí)中經(jīng)典的回歸算法，是現(xiàn)在主要的統(tǒng)計預(yù)測技術(shù)[9]。融合了線性回歸的遺傳算法可以找出停車順序中的內(nèi)在聯(lián)系，將遺傳算法生成的新個體用作線性回歸的訓(xùn)練集，對訓(xùn)練后的回歸系數(shù)排序，預(yù)測出停車的優(yōu)先級，能夠改善遺傳算法局部搜索能力較差的缺點。因此，使用線性回歸對遺傳算法產(chǎn)生的個體進行訓(xùn)練，能夠得出一個有效的停放點分配方案。

1 數(shù)學(xué)模型

本文主要解決共享單車停放點分配問題。共享單車亂停亂放一直是行業(yè)詬病，現(xiàn)如今逐漸建立起了智能停放點和電子欄桿等約束停車的方案。停車誘導(dǎo)系統(tǒng)的研究是該行業(yè)未來發(fā)展的方向，因此停放點分配問題需要制定良好的模型。本文采用雙目標遺傳算法建模，設(shè)f(x)為待停的單車到停放點的距離代價總和，g(x)為所有停放點之間的停車密度代價總和。數(shù)學(xué)模型可表示為

(1)

約束條件如下

2 多目標遺傳算法的實現(xiàn)

優(yōu)化問題通常有多個優(yōu)化目標，各個目標之間又是矛盾的，因此要使所有子目標同時達到性能最優(yōu)是不可能的。通常多目標優(yōu)化問題的解是由一組Pareto最優(yōu)解集構(gòu)成的，其中每一個元素都成為非支配解。

2.1 染色體編碼與初始化種群

本文采用自然數(shù)對每輛車進行編碼，自然數(shù)編碼因帶有實際意義而有著廣泛的應(yīng)用。停車的順序會對最終求得的距離代價產(chǎn)生影響，按處理停車的時間先后順序組成多目標遺傳算法中的染色體。

初始化種群操作為隨機生成染色體中每個基因的排列，將基因排列隨機打亂如下

式中x為染色體,x1,x2,…,xn為車輛的編號隨機排序。例如，染色體[4,2,1,3]為4#車先停，2#車其次，以此類推。

2.2 快速非支配排序和擁擠度計算

多目標遺傳算法無法實現(xiàn)多個子目標同時達到最優(yōu)，因此要使用快速非支配排序和擁擠度對種群進行篩選，作為衡量種群優(yōu)劣的指標。

快速非支配排序：首先找出種群中的非支配解，記為第一梯度并標記為1，然后從種群中剔除這一梯度的解；繼續(xù)找出剩下個體中的非支配解，記為第二梯度并標記為2，以此類推，對種群中所有個體標記，同一層的個體擁有相同的標記值。

2.3 適應(yīng)度函數(shù)與解碼

在停放點分配問題中，距離代價主要由停車的順序和可用停放點決定，由于引入了可用停放點的條件，后停的車輛在不同的染色體中會被分配到不同的停放點。距離代價的解碼過程用貪心算法進行求解，統(tǒng)計待停車輛到可用停放點的總距離。

密度代價主要由各停放點的車輛密度組成，使用均方差進行計算。引入密度代價使管理更加方便。

2.4 選擇和交叉算子

本文選擇錦標賽選擇算法。由于該算法執(zhí)行的效率高以及實現(xiàn)簡單的特點，錦標賽選擇算法是很流行的選擇策略。在當(dāng)前子代種群中抽取若干對染色體，選擇快速非支配排序和擁擠度較優(yōu)的個體作為精英保留到下一代。操作如下：1)確定每次選擇的個體數(shù)量(本文選擇2個)；2)在種群里隨機選擇個體，兩兩構(gòu)成一組，根據(jù)快速非支配排序和擁擠度，選擇適應(yīng)度最好的個體作為競爭勝利者；3)重復(fù)上一步驟，得到足夠的個體構(gòu)成新一代種群。

染色體中車輛的序號唯一，造成染色體中不能出現(xiàn)重復(fù)的序號，隨機選擇自身某段的基因進行自交。

2.5 精英策略

在多目標遺傳算法中加入精英策略可以保證基因良好的個體遺傳到下一代，保持種群的多樣性，同時也讓種群的大小維持在一個固定的數(shù)量。

2.6 實驗結(jié)果分析

Pareto最優(yōu)解集如圖1(a)所示。遺傳算法的終止條件有多種，本文選擇距離代價達到特定收斂閾值作為結(jié)束條件。經(jīng)過實驗可以發(fā)現(xiàn)，多目標遺傳算法在經(jīng)過一定的代數(shù)之后可以得到一個Pareto最優(yōu)解集。在解集中用人工干預(yù)選擇出適合當(dāng)前問題的解。

從圖1(b)可以看出，距離代價在子代個數(shù)達到5 000之后陷入了局部最優(yōu)的情況。理論上距離代價會隨著代數(shù)的增長而收斂，但需要花費的時間成本可能會隨著決策變量的增加而大量增加，因此需要對其進一步優(yōu)化。由于距離代價是優(yōu)化的主要目標，接下來對這個單目標進行算法的改進。

圖1 實驗結(jié)果

3 融合了線性回歸的改進遺傳算法的實現(xiàn)

融合線性回歸的遺傳算法在基礎(chǔ)的遺傳算法框架上，融入了線性回歸算法，將每輛車是否停到最優(yōu)停放點作為輸入，距離代價作為輸出，訓(xùn)練出一種有向的染色體基因組成，改善了遺傳算法的局部搜索能力。改進遺傳算法流程圖如圖2所示。

圖2 融合了線性回歸的遺傳算法流程

線性回歸模型如下

Y=wx+b,x∈{0,1}

(2)

式中xi為車輛是否停到最近的停放點，取值為1或0。wi為線性回歸系數(shù)，Y為停車的距離代價。編碼如下

(3)

例如，上述第一行[1,0,0,1]，為1#車與4#車停到了最優(yōu)停放點，2#車與3#車競爭資源失敗，停到了次優(yōu)停放點。

線性回歸是一種普通的回歸算法，但應(yīng)用廣泛。損失函數(shù)如下

(4)

對于這個損失函數(shù)，有兩種求解最小值的方法，分別是梯度下降法和最小二乘法。因損失函數(shù)為平方損失函數(shù)，在此情況下，回歸問題可以用最小二乘法解決。利用最小二乘法可以解出回歸系數(shù)w=(XTX)-1XTY。訓(xùn)練結(jié)束后，將回歸系數(shù)進行排序。訓(xùn)練之后的回歸系數(shù)w=[w1,w2,…,wn]。

假設(shè)將回歸系數(shù)升序排序后得到以下序列[w3,w2,w1,w4]。則最終預(yù)測出的停車優(yōu)先級為[3,2,1,4]，該順序表示當(dāng)前訓(xùn)練結(jié)束后該車輛停到最優(yōu)停放點對總距離代價的影響程度，影響較大的先停。

每產(chǎn)生一個新的子代，便將其加入線性回歸的訓(xùn)練集，使遺傳算法和線性回歸同步進行。每次更新訓(xùn)練集后重新訓(xùn)練，將訓(xùn)練后得出的回歸系數(shù)進行排序，獲得新的染色體基因構(gòu)成。單純使用線性回歸在此模型中并不具有穩(wěn)定性，因此,將線性回歸融入遺傳算法穩(wěn)定的結(jié)構(gòu)中能更快地找到最優(yōu)解。

實驗結(jié)果會受到供需比的影響。每個停放點數(shù)量上限不同會導(dǎo)致停車的方案和適應(yīng)度產(chǎn)生較大的差異，供需比在0.5以下會導(dǎo)致算法在短時間內(nèi)快速收斂，此時并不需要加入線性回歸來加快收斂，可以直接用貪心算法來解碼。只有在供需比大于0.5時，算法在本文環(huán)境下才有實際的作用。供需比大于0.8的情況較少且單靠遺傳算法的運算時間急速激增，最終決定把供需比調(diào)節(jié)在0.65～0.75之間。圖4是供需比在0.75時的效果圖。

圖3 算法收斂代數(shù)比較

車輛與停放點間的供需比影響算法的收斂代數(shù)。不同供需比下算法比較如表1所示。

表1 算法收斂代數(shù)對比

經(jīng)過上述實驗可知，融合了線性回歸的遺傳算法和基礎(chǔ)的遺傳算法都能得到最優(yōu)解，但本文使用的算法可以節(jié)約一定的時間成本，并改善了遺傳算法局部搜索能力。在供需比達到0.75時，遺傳算法收斂的代數(shù)明顯增加，而融合了線性回歸的遺傳算法的收斂速度遠遠優(yōu)于原算法。

4 結(jié) 論

本文把距離代價作為單一決策變量，在遺傳算法的解碼過程中融入了線性回歸進行優(yōu)化，新算法能夠在更短的時間內(nèi)找出最優(yōu)解，改善了遺傳算法的搜索能力。實驗結(jié)果證明方法有效。