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

鄒文俊

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

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

中圖分類號(hào)：G4 文獻(xiàn)標(biāo)識(shí)碼：Adoi：10.19311/j.cnki.1672-3198.2018.08.072

0 引言

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

1 差分進(jìn)化算法概述

1.1 概念

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

1.2 優(yōu)點(diǎn)

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

2 差分進(jìn)化算法的原理

2.1 差分進(jìn)化算法

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

2.2 差分進(jìn)化算法步驟

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

（1）染色體編碼。

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

（2）初始化種群。

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

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

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

（4）變異。

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

（5）交叉。

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

（6）選擇。

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

（7）終止條件。

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

3 差分進(jìn)化算法分析

3.1 背景介紹

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

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

3.2 算法設(shè)計(jì)

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

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

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

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

R1=2 5 6 7 8 3 1 4

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

（2）初始化種群。

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

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

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

（4）變異。

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

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

④離散算法后的驗(yàn)證。

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

差分進(jìn)化算法變異的第二種方式是差分向量加減運(yùn)算法：

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

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

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

（5）交叉運(yùn)算。

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

為了將變異體的基因有效的傳遞下去，所以試驗(yàn)體的一個(gè)基因必須先從變異體中隨機(jī)選取。

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

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

（6）選擇。

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

4 結(jié)束語

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

參考文獻(xiàn)

[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ìn)化算法研究進(jìn)展[J].控制與決策，2007，22（7）：721-722.

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

[5]張果果.物流配送路徑優(yōu)化標(biāo)準(zhǔn)的實(shí)證研究[J].北京交通大學(xué)學(xué)報(bào)（社會(huì)科學(xué)版），2016，（03）.

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

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

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