1. 概述

自然界一直是許多元啟發(fā)式算法的靈感來源。 它設(shè)法在沒有提示的情況下，基于個體經(jīng)驗找到問題的解決方案。 自然選擇和適者生存是創(chuàng)建早期元啟發(fā)式算法的主要動機。 在自然界中，動物以多種方式相互交流。 螢火蟲則是利用眨眼的能力進行交流。 大約有 2000 種螢火蟲，都擁有自己特殊的閃爍圖案。 它們通常會產(chǎn)生具有特定圖案的短閃爍。 光亮及其強度成為稱為生物發(fā)光的生化過程的成果。 據(jù)信，這種閃爍的主要功能是求偶和吸引潛在的受害者。 一些熱帶螢火蟲可以同步它們的閃爍，從而展示了生物自組織的一個例子。 光亮的強度作為與其光源距離的函數(shù)，遵循平方反比定律，因此來自螢火蟲的閃爍光線會導致它周圍的螢火蟲在閃爍的視線范圍內(nèi)做出反應(yīng)。

受螢火蟲行為啟發(fā)的種群優(yōu)化算法有兩種變體：螢火蟲算法，和螢火蟲群優(yōu)化（GSO）算法。 螢火蟲（firefly）和發(fā)光甲蟲（glowworms）的主要區(qū)別在于后者是無翅的。 在本文中，我們將研究前一種類的優(yōu)化算法。

2. 算法說明

螢火蟲算法（F-算法）由 X-Sh. Yang 于 2007 年在英國劍橋大學提出，并立即引起了優(yōu)化研究人員的注意。 螢火蟲算法是群體智能算法家族的一部分，最近在解決優(yōu)化問題方面取得了令人印象深刻的成果。 特別是，螢火蟲算法在求解連續(xù)和離散優(yōu)化問題的能力。 螢火蟲算法基于真實螢火蟲的閃爍特性，有三條規(guī)則。 規(guī)則如下：

1. 所有螢火蟲都會朝著更有吸引力和更明亮的對應(yīng)物移動。

2. 螢火蟲的吸引力程度與其亮度成正比，由于空氣吸收光線的事實，隨著與另一只螢火蟲的距離增加，亮度會降低。 故此，在任何兩只閃爍的螢火蟲之間，不太亮的螢火蟲會向較亮的螢火蟲移動。 如果沒有更亮或更具吸引力的對應(yīng)物，則螢火蟲將隨機移動。

3. 螢火蟲的亮度或光線強度由問題的目標函數(shù)的值決定。

最初，在算法開始時，所有螢火蟲都隨機分散在整個搜索空間當中。 然后，該算法根據(jù)兩個階段判定最佳分區(qū)：

1. 光線強度的變化 — 螢火蟲在其當前位置的亮度反映在其適應(yīng)性值中，朝著有吸引力的螢火蟲移動。

2. 螢火蟲通過觀察鄰近螢火蟲的光線強度來改變其位置。

現(xiàn)在，我們可以更詳盡地深入了解螢火蟲優(yōu)化的復(fù)雜性。 該算法本質(zhì)上如圖例 1 所示。

編輯切換為居中

圖例 1. 搜索空間中的螢火蟲。 能見度隨著距離的增加而降低

搜索原理背后的主要思路是隨著螢火蟲之間距離的增加，能見度呈非線性降低。 如果沒有這種非線性關(guān)系，每只螢火蟲都會確定性地向更明亮的光源移動。 然而，正如我們在圖例 1 中看到的，螢火蟲不會選擇其最亮的近鄰，因為由于環(huán)境對光線的吸收，它發(fā)出的光線很難被注意到。 取而代之，它選擇了一個不太明亮的對應(yīng)物（盡管是其環(huán)境中最亮的）。 此特征解釋了算法劃分為較小群落的良好能力。 由于遠距離光吸收的非線性函數(shù)，這現(xiàn)象會很自然地發(fā)生。 在下面的圖例 2 中，我們可以看到具有不同 gamma 介質(zhì)吸收系數(shù)值的算法的可見性與距離的函數(shù)，這是算法參數(shù)之一。

編輯切換為居中

圖例 2. 介質(zhì)透明度與距離f(x) 的函數(shù)，其中 gamma 透明度系數(shù)分別等于 1.0、0.2、0.05、0.01。

當 gamma 趨于無窮大時，環(huán)境變得不透明；當 gamma 為零時，環(huán)境是完全透明的；每只螢火蟲在搜索空間中的任何距離都能看到對方。 如果 gamma = 0.0 會發(fā)生什么？ 所有的螢火蟲都會飛到最明亮的相對位置，匯聚到某個非最佳點。 如此，算法不會收斂停留在某個局部極值。 如果環(huán)境完全不透明，會發(fā)生什么情況？ 螢火蟲不會看到比自己更有吸引力的同類。 根據(jù)算法作者提出的概念，看不到比自己更好的同類，那么螢火蟲就會隨機移動。 該算法將退化為隨機搜索。 在我們的算法分類評級表格中，隨機搜索算法排在最后。 ?

我們來深入分析算法，并考慮描述螢火蟲運動的方程。 能見度與距離的函數(shù)是計算所謂吸引力指數(shù)的基礎(chǔ)：

attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

其中: attractiveness - 吸引力，不言自明 gamma - 環(huán)境不透明度系數(shù) distance - 螢火蟲之間的歐氏距離 fireflies [k].f - 第 k 只螢火蟲的光線強度

該方程清楚地表明，吸引力函數(shù)直接取決于問題的維度和距離值的限制，因此該算法的作者建議為特定的優(yōu)化問題選擇透明度系數(shù)。 我認為，在事先不知算法將如何表現(xiàn)的情況下就這樣做，既不方便又耗時；因此我認為有必要對 0 到 20 范圍內(nèi)的距離值進行規(guī)范化。 為達此目的，應(yīng)用我們在其它算法中反復(fù)使用的 Scale() 函數(shù)。 在計算吸引力之前，“distance” 的轉(zhuǎn)換如下所示：

distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);

其中:

maxDist — 在一對螢火蟲之間的最大歐幾里得距離

在這種情況下，螢火蟲的吸引力將不取決于問題的維度，也無需為特定的優(yōu)化問題選擇 gamma 系數(shù)。 吸引力函數(shù)判定每只螢火蟲將做出什么樣的配偶選擇。 這個選擇是有嚴格判定的。 螢火蟲相互吸引力的影響決定了 beta 系數(shù)（算法的第二個參數(shù)）。 如果在每次迭代中螢火蟲已經(jīng)提前確定了相應(yīng)的選擇，如何確保算法的搜索能力？ 為此，引入了隨機向量分量，和第三個算法參數(shù)（alpha）。 螢火蟲的復(fù)雜行為關(guān)系如下所示：

fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];

其中: fireflies [i].c [c] - 第 i 個螢火蟲的第 c 個坐標 beta - 螢火蟲吸引力影響系數(shù) alpha - 當螢火蟲移動時影響隨機分量的系數(shù)，給出與移動目標的偏差 r - 范圍 [-1.0;1.0] 內(nèi)的隨機數(shù) v[c] - 向量分量，通過第 c 個坐標表征搜索范圍極點之間的距離 Хj - 螢火蟲對中的對應(yīng)坐標，其將有運動 Xi - 計算運動的螢火蟲的對應(yīng)坐標

現(xiàn)在是時候講述算法代碼了。 它相對簡單。 我們來研究細節(jié)。

螢火蟲將用一個簡單的結(jié)構(gòu)來描述 S_Firefly，該結(jié)構(gòu)具有兩個組成部分，即 c[] - 坐標，f - 螢火蟲的亮度（適應(yīng)度函數(shù)）。 鑒于對于每只螢火蟲，在相應(yīng)的迭代中只有單一個體，它移動后會形成新的配對，因此在計算下一次移動時，我們不會冒覆蓋坐標的風險。 為此目的，我將引入下面研究的特殊結(jié)構(gòu)。

//—————————————————————————————————————————————————————————————————————————————— struct S_Firefly { ?double c ?[]; //coordinates ?double f; ? ? //the value of the fitness function }; //——————————————————————————————————————————————————————————————————————————————

S_Attractiveness 結(jié)構(gòu)的用意是存儲成對的吸引力值和相應(yīng)螢火蟲的數(shù)量。 每只螢火蟲不會朝向最吸引人的螢火蟲的坐標移動，而是朝向其伙伴已經(jīng)移動的坐標。 這與作者描述的算法版本存在一些差異，但這就是它能更好地工作的方式。

//—————————————————————————————————————————————————————————————————————————————— struct S_Attractiveness { ?double a; //attractiveness ?int ? ?i; //index of the most attractive firefly }; //——————————————————————————————————————————————————————————————————————————————

螢火蟲算法由 C_AO_FA 類進行定義。 這里有三個公開方法，其中一個是用于初始初始化的 Init()，兩個需要在每次迭代時調(diào)用的公開方法 — Flight() 和 Luminosity()，私密幫助方法，和存儲參數(shù)常量的成員。

//—————————————————————————————————————————————————————————————————————————————— class C_AO_FA { ?//---------------------------------------------------------------------------- ?public: S_Firefly fireflies []; //fireflies ?public: double ? ?rangeMax ?[]; //maximum search range ?public: double ? ?rangeMin ?[]; //minimum search range ?public: double ? ?rangeStep []; //step search ?public: double ? ?cB ? ? ? ?[]; //best coordinates ?public: double ? ?fB; ? ? ? ? ? //FF of the best coordinates ?public: void Init (const int ? ?paramsP, ?//number of opt. parameters ? ? ? ? ? ? ? ? ? ? const int ? ?sizeP, ? ?//swarm size ? ? ? ? ? ? ? ? ? ? const double alphaP, ? //alpha, randomness in motion ? ? ? ? ? ? ? ? ? ? const double betaP, ? ?//beta, effect of attractiveness ? ? ? ? ? ? ? ? ? ? const double gammaP); ?//gamma, transparency of the environment ?public: void Flight (); ?public: void Luminosity (); ?//---------------------------------------------------------------------------- ?private: S_Attractiveness att []; ?private: int ? ?swarmSize; ?private: int ? ?params; ?private: double maxDist; ?private: double v []; ?private: double alpha; ? ? ?//randomness in motion ?private: double beta; ? ? ? //effect of attractiveness ?private: double gamma; ? ? ?//transparency of the environment ?private: bool ? luminosity; ?private: double SeInDiSp ?(double In, double inMin, double inMax, double step); ?private: double RNDfromCI (double min, double max); ?protected: double Scale ? (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, ?bool revers); }; //——————————————————————————————————————————————————————————————————————————————

Init() 公開方法用于初始化，應(yīng)在每次優(yōu)化開始之前調(diào)用。 其參數(shù)是算法的補充參數(shù)。 該方法將為數(shù)組分配內(nèi)存，并重置全局和每個單獨螢火蟲的光線亮度值。