1. 概述

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

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

2. 算法說明

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

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

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

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

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

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

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

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

編輯切換為居中

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

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

編輯切換為居中

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

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

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

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

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

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

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

其中:

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

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

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

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

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

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

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

來研究每次迭代時(shí)調(diào)用的第一個(gè)公開方法 — Flight()。 算法的主要邏輯集中在該方法當(dāng)中，因此有必要詳盡地研究它。 'luminosity' 變量當(dāng)作一個(gè)標(biāo)志，允許我們判定算法是處于第一次迭代，還是在后續(xù)迭代中運(yùn)行。 如果標(biāo)志尚未設(shè)置，則需要按照均勻分布將螢火蟲隨機(jī)分布到坐標(biāo)空間之中。 在執(zhí)行此操作的同時(shí)，我們?yōu)槊總€(gè)坐標(biāo)設(shè)置位移向量，并立即計(jì)算螢火蟲之間可以達(dá)到的最大可能歐氏距離（如前所述，這對(duì)于規(guī)范化螢火蟲之間的距離是必要的，以避免環(huán)境透明度系數(shù)對(duì)問題維度的依賴性）。 完成這些操作后，啟用 “l(fā)uminosity” 標(biāo)志。

if (!luminosity) { ?fB = -DBL_MAX; ?//-------------------------------------------------------------------------- ?double summCoordinates = 0.0; ?for (int c = 0; c < params; c++) ?{ ? ?v [c] = rangeMax [c] - rangeMin [c]; ? ?summCoordinates += pow (v [c], 2.0); ?} ?maxDist = pow (summCoordinates, 0.5); ?//-------------------------------------------------------------------------- ?for (int s = 0; s < swarmSize; s++) ?{ ? ?for (int k = 0; k < params; k++) ? ?{ ? ? ?fireflies [s].c ?[k] = RNDfromCI (rangeMin [k], rangeMax [k]); ? ? ?fireflies [s].c ?[k] = SeInDiSp (fireflies [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); ? ?} ?} ?luminosity = true; }

從第二次及蘇隨后的迭代中，在第一次迭代中隨機(jī)發(fā)送出去的螢火蟲開始發(fā)光（適應(yīng)度函數(shù)開始針對(duì)它們進(jìn)行計(jì)算）之后，可以計(jì)算出每只螢火蟲的吸引力程度。 為此，我們需要針對(duì)所有可能的螢火蟲配對(duì)，計(jì)算它們之間的歐幾里得距離。 為此，只需將坐標(biāo)差的平方相加，然后取它們總和的平方根。 計(jì)算出的距離會(huì)應(yīng)用到吸引力計(jì)算方程。 這就是我們?yōu)楹蚊恐晃灮鹣x僅取可能的配對(duì)。 判定所有螢火蟲的最大亮度。 這是判定最亮螢火蟲所需的做法，因?yàn)椴豢赡苷业揭粚?duì)螢火蟲，且獨(dú)自在空間中徘徊。 好吧，也許，在下一次迭代中會(huì)更幸運(yùn)。

//measure the distance between all------------------------------------------ for (int i = 0; i < swarmSize; i++) { ?att [i].a = -DBL_MAX; ?for (int k = 0; k < swarmSize; k++) ?{ ? ?if (i == k) continue; ? ?summCoordinates = 0.0; ? ?for (int c = 0; c < params; c++) summCoordinates += pow (fireflies [i].c [c] - fireflies [k].c [c], 2.0); ? ?distance = pow (summCoordinates, 0.5); ? ?distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false); ? ?attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance); ? ?if (attractiveness > att [i].a) ? ?{ ? ? ?att [i].a = attractiveness; ? ? ?att [i].i = k; ? ?} ? ?if (fireflies [i].f > maxF) maxF = fireflies [i].f; ?} }

Flight() 方法的這一部分代碼負(fù)責(zé)螢火蟲的飛行。 對(duì)于那些不幸的螢火蟲，其亮度大于所有其它螢火蟲，計(jì)算方式略有不同。 我們添加了一個(gè)移動(dòng)向量到其當(dāng)前位置，即 alpha 系數(shù)乘以隨機(jī)數(shù) [-1.0;1.0]。 理論上，在算法中，這一行動(dòng)是對(duì)最佳解的附加研究，期望它能更好，但是，正如我們稍后將看到的，這種技術(shù)將被證明無甚大用。 在此階段，我們研究算法的經(jīng)典版本。

對(duì)于所有其它螢火蟲，若已經(jīng)找到配對(duì)螢火蟲，計(jì)算運(yùn)動(dòng)時(shí)將包括朝向相應(yīng)配對(duì)的螢火蟲移動(dòng)（通過添加的隨機(jī)分量，我之前提到過）。