差分進化算法的算法設(shè)計研究

鄒文俊

摘 要：優(yōu)化技術(shù)是一種以數(shù)學(xué)為基礎(chǔ)，用于求解各種工程問題優(yōu)化解的應(yīng)用技術(shù)。而作為一種優(yōu)化算法，差分進化算法因其有效性，在現(xiàn)代優(yōu)化技術(shù)和工程實踐應(yīng)用中的作用越來越凸顯。闡述了差分進化算法的基本概念，對差分簡化算法的原理進行了介紹，對算法步驟進行了論述，并結(jié)合一物流配送路徑優(yōu)化例子，重點圍繞該算法的設(shè)計進行分析，為差分進化算法的應(yīng)用提供了思路。

關(guān)鍵詞：差分進化算法；算法設(shè)計；應(yīng)用

中圖分類號：G4 文獻標識碼：Adoi：10.19311/j.cnki.1672-3198.2018.08.072

0 引言

差分進化算法 （Differential Evolution ，DE）是一種新興的進化計算技術(shù)。它是由 R.Storn 和K.Price于1995 年提出的，最初的設(shè)想是用于解決切比雪夫多項式問題，后來發(fā)現(xiàn) DE 也是解決復(fù)雜優(yōu)化問題的有效技術(shù)。DE 特有的記憶能力使其可以動態(tài)跟蹤當前的搜索情況，以調(diào)整其搜索策略，具有較強的全局收斂能力和魯棒性，且不需要借助問題的特征信息，適于求解一些利用常規(guī)的數(shù)學(xué)規(guī)劃方法所無法求解的復(fù)雜環(huán)境中的優(yōu)化問題。近年來，DE 已經(jīng)在許多領(lǐng)域得到了應(yīng)用，譬如人工神經(jīng)元網(wǎng)絡(luò)、化工、電力、機械設(shè)計、信號處理、路徑優(yōu)化等。

1 差分進化算法概述

1.1 概念

差分進化算法是一種強調(diào)在全局中尋找最優(yōu)解的技術(shù)，即通過種群內(nèi)個體間的合作與競爭來實現(xiàn)對優(yōu)化問題的求解，其本質(zhì)是一種基于實數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法，是一種以“適者生存”的理念來進行“優(yōu)勝劣汰”的智能型算法，同時，差分進化算法在對問題的求解過程中采用了并行搜索的實現(xiàn)方式，通過該方式，大大減少了對問題求解過程中所需要的時間。差分進化算法通過非常簡單的算法結(jié)構(gòu)，趨于智能化的適應(yīng)條件判斷來進行新一代種群的生成，并最終通過適應(yīng)條件判斷來選出全局的最優(yōu)方案。

1.2 優(yōu)點

差分進化計算是一種具有魯棒性的方法，能適應(yīng)不同的環(huán)境不同的問題，而且在大多數(shù)情況下都能得到比較滿意的有效解。它對問題的整個參數(shù)空間給出一種編碼方案，而不是直接對問題的具體參數(shù)進行處理，不是從某個單一的初始點開始搜索，而是從一組初始點搜索。搜索中用到的是目標函數(shù)值的信息，可以不必用到目標函數(shù)的導(dǎo)數(shù)信息或與具體問題有關(guān)的特殊知識。因而進化算法具有廣泛的應(yīng)用性，高度的非線性，易修改性和可并行性。

2 差分進化算法的原理

2.1 差分進化算法

差分進化算法具備適應(yīng)性較高的特征，在求解過程中尋找最優(yōu)解的問題上，即使進化機制存在一定的不規(guī)則性、適應(yīng)度不合適的問題，但進化的本身是對全局進行搜索來實現(xiàn)的，容易實現(xiàn)全局上的最優(yōu)解。同時，差分進化算法在求解最優(yōu)解的過程中運用了并行的搜索方式，大大提高問題的求解速度。其中，初始種群中的每一個染色體則看作是一個解。在每一代的染色體間進行變異、交叉、選擇實現(xiàn)生成下一代染色體，并保證染色體種群的整體質(zhì)與量。通過不斷的迭代，通過適應(yīng)值的評估選擇最優(yōu)的解來作為問題最終的答案。

2.2 差分進化算法步驟

遺傳算法的主要步驟可分為以下幾個步驟：

（1）染色體編碼。

在利用差分進化算法解決相關(guān)問題的最優(yōu)解之前，需要把實際應(yīng)用問題中的相關(guān)數(shù)據(jù)轉(zhuǎn)換為差分進化算法中的染色體數(shù)據(jù)。染色體編碼就是將實際所求解的問題向基因編碼的映射。染色體是數(shù)據(jù)的外在表現(xiàn)形式，良好的編碼能夠直接影響到對問題求解的過程。

（2）初始化種群。

在差分進化算法中，初始化種群是由一定數(shù)量的染色體構(gòu)成的。通過將基因進行編碼，形成染色體，隨機生成一定數(shù)量的染色體，使其構(gòu)成一個一定數(shù)量的種群。

（3）適應(yīng)值函數(shù)。

差分進化算法中的適應(yīng)值函數(shù)是算法中至關(guān)重要的一個參數(shù)，是評判種群中個體好壞的最基本也是最重要的條件，更是評判差分進化算法是否繼續(xù)進行下去的一個標識，只有適應(yīng)值高的個體才能夠進入下一代算法操作，利用適應(yīng)值來淘汰不適應(yīng)的個體，使得最優(yōu)解的獲取更迅速，也更容易。

（4）變異。

差分進化算法中的變異操作是最為重要的一個步驟，實現(xiàn)過程為在種群中隨機選擇三個染色體，將兩個適應(yīng)值較低的2個染色體進行計算，再將結(jié)果與適應(yīng)值最高的染色體進行計算，獲取的結(jié)果作為“變異體”供下一步驟使用。

（5）交叉。

差分進化算中的交叉操作是對產(chǎn)生下一代染色體的一個重要的操作步驟，實現(xiàn)過程為將參與變異操作步驟中的“優(yōu)秀染色體”與變異操作過程后產(chǎn)生的“變異體”進行交叉產(chǎn)生“試驗體”，為了保證變異體的延續(xù)性，將“變異體”中的隨機一個基因位上的基因作為固定的交叉基因。

（6）選擇。

差分進化算法中的選擇操作決定了下一代染色體種群中的個體，實現(xiàn)過程為將參與交叉操作的“優(yōu)秀染色體”與交叉操作后的“試驗體”通過適應(yīng)值評估，選擇適應(yīng)值最優(yōu)秀的那一個，即是說，下一代染色體的新的個體可能為上一代染色體的個體直接保留下來。

（7）終止條件。

差分進化算法中的終止條件是判斷循環(huán)迭代次數(shù)結(jié)束的一個標識，在優(yōu)化問題的求解過程中，是判斷最優(yōu)解誕生的一個重要依據(jù)。如果滿足設(shè)定的循環(huán)迭代終止條件，則代表了最優(yōu)解的誕生，如果未產(chǎn)生最優(yōu)解則繼續(xù)返回步驟（3），進入新一輪的計算。

3 差分進化算法分析

3.1 背景介紹

車輛路徑的問題是一種NP-hard的問題，在NP-hard的問題中，車輛路徑問題屬于最經(jīng)典也是相對較難的問題。由于車輛路徑問題存在的模糊因素以及不定因素較多，因此解決該問題大多采用的是啟發(fā)式的算法。本文所闡述的差分進化算法就屬于啟發(fā)式的算法中的一種，在解決復(fù)雜的全局優(yōu)化問題方面， 差分進化算法的性能更加優(yōu)秀，過程也更為簡單，受控參數(shù)少，可有效用以解決車輛路徑的問題。

現(xiàn)某物流有限公司的服務(wù)項目以產(chǎn)品配送為主，秉承以客戶需求為導(dǎo)向，為客戶提供優(yōu)質(zhì)的物流配送服務(wù)。現(xiàn)配送中心需完成8家客戶的配送任務(wù)。如何選擇最優(yōu)路徑，從而降低配送成本，提升配送效率，是企業(yè)需要解決的問題。

3.2 算法設(shè)計

差分進化算法的算法設(shè)計主要包括編碼設(shè)計，初始化種群，確定適應(yīng)值函數(shù)，變異，交叉運算和選擇這幾個步驟。

（1）編碼設(shè)計。

在利用差分進化算法解決物流配送車輛路徑優(yōu)化問題的最優(yōu)解之前，需要把配送過程中的相關(guān)數(shù)據(jù)轉(zhuǎn)換為染色體數(shù)據(jù)。

染色體編碼表示需要配送的客戶信息，每個自然數(shù)代表一個待配送客戶。設(shè)定染色體表示為：R1=（i1，i2，...，in），（n為自然數(shù)）例如：經(jīng)過計算染色體的編碼為：

R1=2 5 6 7 8 3 1 4

那么，這條染色體表示為8個終端客戶進行物流配送，自然數(shù)的排序表示這8個客戶的配送路徑。

（2）初始化種群。

差分進化算法的隨機搜尋起始于隨機構(gòu)成的初代種群，通過不斷的一次一次的迭代操作，最終產(chǎn)生最優(yōu)的結(jié)果。初始化種群的數(shù)量為X，則每一個染色體對應(yīng)著3.1中隨機產(chǎn)生的結(jié)果。此例中的初始化種群，由一定數(shù)量的配送路徑構(gòu)成。

（3）確定適應(yīng)值函數(shù)。

差分進化算法中的適應(yīng)值函數(shù)是算法中至關(guān)重要的一個參數(shù)，是評判種群中個體好壞的最基本也是最重要的條件，更是評判差分進化算法是否繼續(xù)進行下去的一個標識。本文中，用車輛配送成本作為適應(yīng)值函數(shù)，用以判斷配送路徑是否最合理。

（4）變異。

差分進化算法中，變異是必定會進行的一個過程。利用從種群中隨機選取的兩個個體的差向量作為第三個個體的隨機變化源，將差向量加權(quán)后按照一定的規(guī)則與第三個個體求和而產(chǎn)生“變異體”。差分進化算法中，變異有兩種方式，第一種是差分離散運算算法：

通過公式V = R1 | F×（R2 & R3）計算得出變異體V。其中，設(shè)定D=R2&R3，即V = R1 | F×D。

④離散算法后的驗證。

在得出最終結(jié)果后，需要進行一次驗證，因為在進行計算后，可能得出的路徑中會出現(xiàn)超出取值范圍的數(shù)值。比如只有8條路徑，但最終得出的結(jié)果為1 12 2 3 4 5 6 8。其中出現(xiàn)了12的數(shù)值，則該條變異路徑為廢解，需要剔除。

差分進化算法變異的第二種方式是差分向量加減運算法：

通過公式V=R1+F×（R2-R3），計算得出變異體V。

由于客戶是由一個個自然數(shù)表示，所以對計算結(jié)果中的小數(shù)點需要進行修正。因為與8位客戶，所以將結(jié)果中最大值和最小值改為8和1，將帶有小數(shù)的數(shù)字按照排序大小優(yōu)先變?yōu)榇髷?shù)值，形成新的路徑，如下：

從離散差分算法和加減差分算法的算法設(shè)計中來看，雖然離散差分算法的復(fù)雜度較高，但是它更接容易進行計算機編碼。其中變異步驟使用離散算法可以省略將小數(shù)數(shù)字轉(zhuǎn)換成整數(shù)的步驟，減少不必要的操作和誤差。

（5）交叉運算。

變異個體與某個預(yù)先決定的目標個體進行參數(shù)混合，生成試驗個體，這一過程稱之為交叉。從之前變異運算的3個父染色體中取得一個適應(yīng)值最高的出來作為“優(yōu)選體”。將優(yōu)選體與變異體進行交叉，交叉完成后的染色體成為“試驗體”。

為了將變異體的基因有效的傳遞下去，所以試驗體的一個基因必須先從變異體中隨機選取。

從上可以看到，變異體中的隨機選取位是7，所以“試驗體”的同位素也為7。之后其它位置的基因可以隨機從“優(yōu)選體”和“試驗體”中進行選擇，形成了一個完整的試驗體17675218。

可以發(fā)現(xiàn)交叉后的試驗體是有重復(fù)的數(shù)值的，是一條不合格的染色體，所以需要進行一次修正。修正的手法采用逐個基因驗證，由上至下進行隨機選取，當產(chǎn)生重復(fù)數(shù)值則往前查找是否某個基因位可以進行替換。比如基因位來源于“變異體”，則嘗試替換為“優(yōu)選體”的基因。再繼續(xù)往下進行，直至“試驗體”的每一個基因位都不重復(fù)。

（6）選擇。

在交叉運算完成后，會產(chǎn)生一個優(yōu)選體，一個試驗體。此時需要進行一個適應(yīng)值的評估，使得適應(yīng)值高的那一個染色體得意被保留，成為下一代種群中的一員。所以下一代種群中的一員可能是優(yōu)選體，也可能是試驗。

4 結(jié)束語

智能優(yōu)化是將人工智能技術(shù)與運籌學(xué)、控制理論、大系統(tǒng)理論中靜態(tài)優(yōu)化、動態(tài)優(yōu)化、多級優(yōu)化等方法相結(jié)合，尋求解決傳統(tǒng)優(yōu)化方法難以解決的多目標、局部解、不確定、未確知、維數(shù)災(zāi)難等問題的新途徑。差分進化算法作為一種新穎的智能優(yōu)化算法，容易理解，實現(xiàn)簡單，具有良好的優(yōu)化性能，已廣泛應(yīng)用于各種優(yōu)化問題中。但差分進化算法跟其它進化算法一樣存在早熟悉收斂等問題，因此對差分進化算法進行改進，提高其全局搜索能力和收斂速率，使之適應(yīng)于各種工程實際問題中，是一個值得深入研究的方向。本文以物流配送路徑優(yōu)化為切入點，分析了差分進化算法的基本概念和算法步驟。但是對算法設(shè)計的分析還比較淺顯，尚未涉及算法在具體案例中應(yīng)用，將在今后的學(xué)習(xí)研究中加以完善。

參考文獻

[1]Storn R，Price K. Differential evolution — A simple andefficient adaptive scheme for global optimization overcontinuous spaces [R]. Berkeley： University ofCalifornia，2006.

[2]Lampinen J. A bibliography of differential evolutionalgorithm[EB/ OL]. （2002-10-14） . http ：/ / www. lut.fi/ ～ jlampine/ debiblio. htm.

[3]劉波.差分進化算法研究進展[J].控制與決策，2007，22（7）：721-722.

[4]周謙.差分進化算法的應(yīng)用研究[D].鄭州：中原工學(xué)院， 2016.

[5]張果果.物流配送路徑優(yōu)化標準的實證研究[J].北京交通大學(xué)學(xué)報（社會科學(xué)版），2016，（03）.

[6]王東健.水產(chǎn)品冷鏈物流配送中心選址及配送路徑優(yōu)化研究[D].吉林：吉林大學(xué)，2015.

[7]袁菁穗.差分演化算法研究綜述[J].科技信息， 2010 （26） ：130-131.

[8]楊丹婷.冷鏈物流配送路徑優(yōu)化研究[D].大連：大連海事大學(xué)，2014.