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

施嘉偉， 陳觀林,， 徐 煌

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

0 引 言

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

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

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

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

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

(1)

約束條件如下

2 多目標(biāo)遺傳算法的實(shí)現(xiàn)

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

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

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

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

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

2.2 快速非支配排序和擁擠度計(jì)算

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

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

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

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

密度代價(jià)主要由各停放點(diǎn)的車輛密度組成，使用均方差進(jìn)行計(jì)算。引入密度代價(jià)使管理更加方便。

2.4 選擇和交叉算子

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

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

2.5 精英策略

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

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

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

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

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

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

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

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

線性回歸模型如下

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

(2)

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

(3)

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

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

(4)

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

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

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

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

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

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

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

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

4 結(jié) 論

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