莊鶴林,楊火根,夏小云,廖偉志

(1.江西理工大學(xué)理學(xué)院，江西 贛州 341000;2.嘉興學(xué)院信息科學(xué)與工程學(xué)院，浙江 嘉興 314001)

1 引言

矩陣乘法是數(shù)值計(jì)算中的一個(gè)基本運(yùn)算，在科學(xué)研究和工程分析中有著廣泛的運(yùn)用。矩陣乘法的計(jì)算時(shí)間直接影響了應(yīng)用領(lǐng)域的時(shí)間復(fù)雜度。

1969年，德國數(shù)學(xué)家Strassen[1]提出了一個(gè)新的分治矩陣乘法算法，將矩陣乘法的時(shí)間復(fù)雜度從O(n3)降低至O(n2.81)，大大提高了矩陣乘法的效率。

Strassen算法提出之后，眾多數(shù)學(xué)家嘗試尋找更好的算法。當(dāng)前最好的矩陣乘法算法時(shí)間復(fù)雜度為O(n2.376)[2]。已經(jīng)證明了當(dāng)使用(n/2)×(n/2)矩陣的線性組合時(shí)，不可能使(n/2)×(n/2)矩陣乘法僅用6次乘法完成[3]。對于(n/3)×(n/3)矩陣，當(dāng)前最好的算法需要至少23次乘法[4]。

快速矩陣乘法算法能夠通過窮舉所有可能的情況獲得，然而計(jì)算量過于巨大，難以實(shí)現(xiàn)。近年來，研究人員提出使用計(jì)算機(jī)算法求解快速矩陣乘法，他們使用遺傳算法找到了與Strassen算法等同時(shí)間復(fù)雜度的矩陣乘法算法。2001年由Kolen等人[5]提出使用進(jìn)化算法推導(dǎo)Strassen算法，但其增加了過多的約束條件，效率非常低，并且只能找到與Strassen完全相同的算法。2010年,Oh等人[6]對遺傳算法進(jìn)行了改進(jìn)，使用雜交和局部搜索方法，并使用高斯消除法和線性無關(guān)等計(jì)算適應(yīng)度，效果有了明顯改進(jìn)，找到了大量不同于Strassen算法卻與其有相同時(shí)間復(fù)雜度的算法，并對各個(gè)算法進(jìn)行了分類比較和分析。但是，這些算法的求解效率仍不讓人滿意，平均計(jì)算時(shí)間需要幾個(gè)小時(shí)。此外，Zhou等人[7]使用蟻群算法也重現(xiàn)了Strassen算法，找到了與Strassen算法同等時(shí)間復(fù)雜度的10種不同類型的解，求解時(shí)間相比遺傳算法從數(shù)小時(shí)下降到數(shù)秒鐘。最近，Heule等人[8]基于SAT的局部搜索算法，找到了僅使用23次乘法的(n/3)×(n/3)矩陣乘法的新模式。

群體智能優(yōu)化算法源于對自然界的生物進(jìn)化過程或覓食行為的模擬[9 -11]，它將搜索和優(yōu)化過程模擬成個(gè)體的進(jìn)化或覓食過程，用搜索空間中的點(diǎn)模擬自然界中的個(gè)體，將求解問題的目標(biāo)函數(shù)度量成個(gè)體對環(huán)境的適應(yīng)能力，將個(gè)體的優(yōu)勝劣汰過程或覓食過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程，是一種求解極值問題的自適應(yīng)人工智能技術(shù)。

人工蜂群算法是一種模擬蜜蜂行為的優(yōu)化算法[12 -14]，該算法參數(shù)相對較少、易于實(shí)現(xiàn)，具有較快的收斂速度，且融入了反饋思想，跳出局部能力強(qiáng)，獲得了眾多學(xué)者的關(guān)注，其在TSP問題[15]、函數(shù)優(yōu)化[16]和流水線調(diào)度[17]等優(yōu)化問題中獲得了廣泛的應(yīng)用。

本文將基于2×2快速矩陣乘法問題轉(zhuǎn)換為一個(gè)組合優(yōu)化問題，提出使用人工蜂群智能算法來求解該問題，結(jié)合問題本身特點(diǎn)對人工蜂群算法進(jìn)行改進(jìn)并用于矩陣乘法問題搜索求解。本文所提算法充分利用群體智能算法的固有并行性、魯棒性和全局優(yōu)化等特點(diǎn)，針對優(yōu)化問題自身特點(diǎn)設(shè)計(jì)適應(yīng)度函數(shù)，優(yōu)化搜索空間，能進(jìn)行有效的快速矩陣乘法算法搜索。

2 快速矩陣乘法問題描述

2.1 快速矩陣乘法問題

對于如式(1)所示的n×n矩陣乘法，

AB=C

(1)

需要構(gòu)造一組Pi(i=1,2,…,m)，可描述為如下形式：

aij,bij∈{-1,0,1}

(2)

當(dāng)Cj(j=1,2,3,…,n2)都可由Pi(i=1,2,…,m)線性組合來表示以及m

2.2 2×2快速矩陣乘法問題

目前已經(jīng)證明2×2矩陣乘法至少需要7次乘法，即m最小取7。需要構(gòu)造一組Pi(i=1,2,…,7)，描述為如下形式：

aij,bij∈{-1,0,1}

(3)

當(dāng)Cj(j=1,2,3,4)都可由Pi(i=1,2,…,7)線性組合來表示時(shí)，即找到2×2矩陣乘法的一個(gè)快速算法。

分析可得，每個(gè)Pi有8個(gè)變量，總共有7×8=56個(gè)變量。對于每個(gè)Pi,所有變量全0是無意義的，并且對于任意一組Pi，將任意一個(gè)或多個(gè)Pi的所有變量取相反數(shù)后邏輯上與原來的Pi組相同，即變化后的Pi組能線性表示的Cj，原Pi組也能線性表示。故對于任意Pi的(ai1ai2ai3ai4)和(bi1bi2bi3bi4)在賦值時(shí)能夠按照排除全0、首個(gè)非0系數(shù)必須為1(或-1)的原則去掉無意義或邏輯重復(fù)的選擇，剩余2×2快速矩陣乘法的系數(shù)選擇共40個(gè)，記作choicei(1≤i≤40)。每個(gè)Pi有40×40=1600種賦值方法。這1 600種賦值方法記作combi(1≤i≤1600)，即comb40(i-1)+j=(choicei,choicej)。

將問題用矩陣的形式描述，Pi(i=1,2,…,7)的全部系數(shù)記錄在一個(gè)矩陣?yán)?，記作XS7×8，如下所示：

XS7×8唯一決定一個(gè)Pi組對應(yīng)的矩陣P16×7,P16×7的每一列(Pi)唯一對應(yīng)一個(gè)Pi。P16×7如下：

其中，XS7×8的第i行對應(yīng)P16×7的第i列，轉(zhuǎn)換公式如式(4)所示：

Pij=XSj,(i-1)mod 4+1×XSj,(i-1)mod 4 + 5

(4)

C1=A1B1+A2B3,

C2=A1B2+A2B4,

C3=A3B1+A4B3,

C4=A3B2+A4B4

(5)

給出Q16×4如下：

Q16×4的第i列(Qi)與Ci唯一對應(yīng)。

2×2矩陣乘法問題轉(zhuǎn)化為尋找一個(gè)XS7×8，其對應(yīng)的P16×7，存在一個(gè)矩陣H7×4，使P16×7H7×4=Q16×4成立。

2.3 可行解結(jié)果轉(zhuǎn)換

在結(jié)果用矩陣表示的情況下，可用一個(gè)XS唯一表示一個(gè)解。下面給出將矩陣形式的結(jié)果轉(zhuǎn)化為普通結(jié)果的公式。

(6)

對于成立的PH=Q，Ci的表達(dá)式如式(7)所示：

(7)

其中，H需要通過廣義逆計(jì)算，計(jì)算公式如式(8)所示：

H=PQ

(8)

其中，為廣義逆中的左除運(yùn)算。

2.4 描述與定義補(bǔ)充

描述1矩陣按列連接:對于2個(gè)行數(shù)相同的矩陣A和B，記A|B為A和B按列連接而成的增廣矩陣。

描述2遍歷操作：將XS第i行的賦值依次替換為comb1，comb2，…，comb[(3n2-1)/2]2，對每一個(gè)替換結(jié)果都訪問一次的過程稱為對XS第i行的遍歷。對XS的遍歷即為對XS的每一行都遍歷一遍。對XS的第i行遍歷在邏輯上等價(jià)于對P的第i列遍歷和對Pi遍歷。

描述3遍歷位置(i，a，b):comb的每一行可由2個(gè)系數(shù)決定，記作a和b。a即該行中的(ai1ai2ai3…ain2)在choice中的序號，b即該行中的(bi1bi2bi3…bin2)在choice中的序號。當(dāng)對某一XS的第i行進(jìn)行遍歷操作時(shí)，其遍歷位置可由(i，a，b)唯一確定。

定義1(不同解) 對于2個(gè)XS,其中一個(gè)XS中存在一行向量在另一個(gè)XS無相同行向量，這2個(gè)XS即為不同解。

一組Pi即為一個(gè)解，而一個(gè)XS唯一決定一組Pi，因此用XS記錄一個(gè)解。為在記錄時(shí)避免邏輯上的重復(fù)記錄，定義不同解，因?yàn)榉遣煌?相同解)在邏輯上是相同的。

定義2(相鄰解) 對某一XS進(jìn)行遍歷操作時(shí)，找到的與原本XS適應(yīng)度相同的所有XS都稱為其相鄰解。

定義3(鄰位更優(yōu)解) 對某一XS進(jìn)行遍歷操作時(shí)，找到的比原本XS適應(yīng)度高的所有XS都稱為其鄰位更優(yōu)解。

定義4(劣質(zhì)解) 對某一解,若自身及其所有相鄰解在遍歷過程中都找不到鄰位更優(yōu)解，稱該解為劣質(zhì)解。

此外，本文中用到的矩陣的秩即為極大線性無關(guān)組所含向量的個(gè)數(shù)。

3 基于人工蜂群算法的2×2快速矩陣乘法算法

3.1 人工蜂群算法(ABC)

人工蜂群算法ABC(Artificial Bee Colony algorithm)是一個(gè)由蜂群行為啟發(fā)的算法，于2005年由Karaboga[12]為優(yōu)化函數(shù)問題而提出。

蜜蜂是一種群居昆蟲，雖然單個(gè)昆蟲的行為極其簡單，但是由多個(gè)簡單的個(gè)體所組成的群體卻表現(xiàn)出極其復(fù)雜的行為。真實(shí)的蜜蜂種群能夠在各種環(huán)境下，以極高的效率從食物源中采集花蜜。

人工蜂群算法的主要組成部分包括食物源、雇傭蜂和非雇傭蜂。人工蜂群算法的2種最基本的行為模式為蜜源招募蜜蜂和放棄某個(gè)蜜源。食物源的好壞對應(yīng)于算法中的適應(yīng)度。雇傭蜂對應(yīng)一個(gè)食物源，并與其它蜜蜂分享此食物源信息，食物源越好招募到其它蜜蜂的概率越大。非雇傭蜂分為偵查蜂和跟隨蜂,跟隨蜂在食物源附近搜索新的潛在食物源,偵查蜂搜索新的食物源。

在初始化后，該算法的每次迭代主要分以下3個(gè)階段。

(1)雇傭蜂階段：一個(gè)雇傭蜂與一個(gè)食物源對應(yīng)。雇傭蜂在鄰域搜索并依據(jù)貪心算法更新。

(2)跟隨蜂階段：跟隨蜂依概率選擇雇傭蜂帶回的食物源信息對應(yīng)的食物源搜索鄰域并依據(jù)貪心算法更新。

(3)偵查蜂階段：當(dāng)某個(gè)可能解迭代limit次仍沒有改進(jìn)時(shí)，就認(rèn)為此食物源不好，此時(shí)對應(yīng)雇傭蜂轉(zhuǎn)化為偵查蜂，放棄該食物源，同時(shí)隨機(jī)生成一個(gè)新的食物源。

3.2 ABC算法優(yōu)化

雇傭蜂和跟隨蜂在搜索鄰域時(shí)，選擇鄰域的一個(gè)小區(qū)域遍歷。多個(gè)跟隨蜂選擇同一蜜源搜索鄰域時(shí)，極可能會出現(xiàn)重復(fù)搜索的情況。為避免此情況，本文基于基本ABC進(jìn)行優(yōu)化，對于一個(gè)蜜源，對其7個(gè)Pi遍歷采用繞圈的方式搜索鄰域，如圖1所示。

Figure 1 Circle traversal圖1 繞圈遍歷

每個(gè)Pi初始起點(diǎn)分別為comb中隨機(jī)的一個(gè)位置。無論是雇傭蜂還是跟隨蜂，選中一個(gè)Pi遍歷時(shí)，都從當(dāng)前起點(diǎn)開始，順序搜索一定范圍的鄰域，并用最后的位置更新起點(diǎn)。如果適應(yīng)度改進(jìn)，則再次隨機(jī)初始化所有Pi的起點(diǎn)。這樣，使隨機(jī)性體現(xiàn)在Pi的選擇和初始起點(diǎn)上。

一個(gè)花蜜由7個(gè)Pi組成，對其中某個(gè)Pi遍歷時(shí)，在其它6個(gè)Pi不發(fā)生改變時(shí)，再對已遍歷部分搜索是沒有意義的。繞圈遍歷的作用在于，當(dāng)某一蜜源中的某一Pi被重復(fù)選中時(shí)，搜索會從新的起點(diǎn)開始，除非再繞了一圈，否則已搜索部分不會被重復(fù)搜索。

某解自身與其相鄰解，若不進(jìn)行完整遍歷，不確定該解是否為劣質(zhì)解。若非劣質(zhì)解，也不確定哪一個(gè)或哪幾個(gè)相鄰解存在鄰位更優(yōu)解。各個(gè)Pi都在隨機(jī)到來的繞圈中變化著。繞圈遍歷作為鄰域搜索策略，其目的在于保證解的適應(yīng)度不降低，并且等待鄰位更優(yōu)解的出現(xiàn)。

3.3 適應(yīng)度設(shè)置與計(jì)算方法

向量組A可線性表示向量組B的充要條件為R(A)=R(A|B)，其中R(A)為矩陣A的秩。一個(gè)矩陣即為一個(gè)向量組，根據(jù)該充要條件，向量組能否線性表示另一向量組可轉(zhuǎn)化為對矩陣秩的判斷。

判斷是否所有Ci可由Pi組線性表示，即判斷Pi組是否為可行解，只要判斷P與P|C的秩是否相等即可。這在使用窮舉法時(shí)是可行的，然而對于群體智能算法而言不能僅做此簡單的判斷。群體智能算法是一類在迭代過程中逐漸趨優(yōu)的算法，對于解的好壞要有更準(zhǔn)確的描述。

判斷Ci是否可由Pi組線性表示，只要判斷P與P|Ci的秩是否相等即可。當(dāng)Pi組能夠線性表示的Ci越多，認(rèn)為其適應(yīng)度越好。故判斷適應(yīng)度的好壞，需計(jì)算所有P|Ci中與P的秩相等的個(gè)數(shù)，再利用此數(shù)對適應(yīng)度進(jìn)行映射。適應(yīng)度按照升序或降序的原則設(shè)置。

為更好地描述某一解的收斂情況，稱可線性表示t個(gè)Ci的解收斂至第t級。特別地，當(dāng)t=n2時(shí)，表示該解收斂至可行解。

3.4 2×2快速矩陣乘法的ABC算法

本節(jié)給出用于2×2快速矩陣乘法的人工蜂群算法。作為隨機(jī)啟發(fā)式搜索算法，適應(yīng)度的計(jì)算在算法搜索過程中起到關(guān)鍵的作用[18]。對于本文中的矩陣乘法問題而言，適應(yīng)度的意義僅為區(qū)分解可線性表示的Ci的個(gè)數(shù)，故采用如式(9)所示的適應(yīng)度計(jì)算公式：

S=ne+1

(9)

其中，ne為該解對應(yīng)的Pi組可線性表示的Ci的個(gè)數(shù)，最后一項(xiàng)加1是為了避免賭盤選擇時(shí)總適應(yīng)度為0導(dǎo)致計(jì)算時(shí)存在分母為0的情況。算法中使用的鄰域搜索策略為從起點(diǎn)開始遍歷，直到找到一個(gè)鄰位更優(yōu)解或向后400個(gè)comb。具體算法步驟如算法1所示：

算法1快速矩陣乘法的ABC算法

輸入：無。

輸出：可行解。

步驟1隨機(jī)初始化蜜源Xi(i=1,2,…,SN)。

步驟2進(jìn)入循環(huán)。

步驟3每個(gè)雇傭蜂對對應(yīng)蜜源隨機(jī)選擇一個(gè)Pi按照繞圈遍歷鄰域搜索策略搜索鄰域，用此鄰域中適應(yīng)度最高的解更新蜜源，若有多個(gè)，采用賭盤算法選擇其中一個(gè)。若適應(yīng)度改進(jìn)，則再次初始化這個(gè)蜜源的所有起點(diǎn)，并再次初始化其limit。

步驟4每個(gè)偵查蜂按照賭盤算法選擇一個(gè)蜜源，隨機(jī)選擇一個(gè)按照繞圈遍歷鄰域搜索策略搜索鄰域。用此鄰域中適應(yīng)度最高的解更新蜜源，若有多個(gè)，采用賭盤算法選擇其中一個(gè)。若適應(yīng)度改進(jìn)，則再次初始化這個(gè)蜜源的所有起點(diǎn)，并再次初始化其limit。

步驟5偵查蜂使每個(gè)蜜源limit減1，并丟棄所有l(wèi)imit為0的蜜源。隨機(jī)生成蜜源至蜜源數(shù)為SN。

步驟6若找到可行解或運(yùn)行時(shí)間達(dá)到上限，循環(huán)結(jié)束。

雇傭蜂階段和跟隨蜂階段的操作基本一致，但二者的作用有所區(qū)別。每只雇傭蜂固定搜索自己對應(yīng)的蜜源的鄰域，以保證每輪迭代中每個(gè)蜜源有至少一次的鄰域搜索。而跟隨蜂則是讓適應(yīng)度更好的蜜源有更多鄰域搜索的機(jī)會，以形成正反饋。

3.5 算法有效性分析

在2×2矩陣乘法中，一個(gè)解能夠線性表示3個(gè)Ci，看似距離線性表示全部4個(gè)Ci僅一步之遙，而在實(shí)際算法運(yùn)行中，收斂至第3級一般只需要幾秒鐘，而在此基礎(chǔ)上收斂至第4級通常需要數(shù)分鐘。

2.4節(jié)中給出了劣質(zhì)解的概念，實(shí)驗(yàn)中發(fā)現(xiàn)，劣質(zhì)解大量存在，是從第3級收斂至第4級困難的主要原因之一。

如果不采取有效的策略，那么程序就會在劣質(zhì)解的鄰域搜索上浪費(fèi)大量的時(shí)間，降低了算法效率。然而事實(shí)上，許多算法的策略僅僅是設(shè)置一個(gè)迭代上限，若達(dá)到迭代上限則重新初始化，這并不能有效地減少程序在劣質(zhì)解的鄰域搜索。

人工蜂群算法融入了正反饋與負(fù)反饋的思想，這是它性能優(yōu)秀的關(guān)鍵因素，這個(gè)特性非常適合于快速矩陣乘法問題求解。適應(yīng)度高的蜜源會招來更多的偵查蜂搜索其鄰域，而適應(yīng)度低的蜜源一旦被判斷不好，就會被丟棄。實(shí)驗(yàn)時(shí)將limit設(shè)置為30，當(dāng)某一蜜源連續(xù)30代適應(yīng)度都未提升時(shí)，拋棄該蜜源。對于某一解，其自身無法收斂至下一級，但是卻無法確定其相鄰解是否能收斂至下一級。當(dāng)然，它可能是個(gè)劣質(zhì)解，其所有相鄰解都無法收斂至下一級，設(shè)定limit為30，能夠避免浪費(fèi)過多時(shí)間在劣質(zhì)解的鄰域搜索上，并且又不會太快地拋棄一個(gè)可能優(yōu)質(zhì)的解。

4 實(shí)驗(yàn)分析

4.1 優(yōu)化ABC的時(shí)間開銷與參數(shù)的關(guān)系

為探討本文所提算法的性能，首先對其時(shí)間開銷進(jìn)行分析。算法大部分時(shí)間用于雇傭蜂階段和偵查蜂階段的鄰域搜索，偵查蜂階段相比之下可忽略不計(jì)。理論上其每一次迭代所用的平均時(shí)間與種群大小(SN)成正比。為驗(yàn)證此分析，在不同種群大小下分別進(jìn)行5次重復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境為同一計(jì)算機(jī)的相同運(yùn)行環(huán)境，結(jié)果如表1所示。

Table 1 Running time of the 1 000 iterations for different population sizes 表1 不同種群大小SN下迭代1 000代所需的時(shí)間 s

分別在種群大小為7,10,15下進(jìn)行采樣，得到的平均時(shí)間與種群大小呈現(xiàn)一致比例。

此外，由于影響算法性能的參數(shù)較多，研究時(shí)僅憑經(jīng)驗(yàn)將limit設(shè)置為30，將每次鄰域搜索的最大范圍設(shè)置為400個(gè)comb，使雇傭蜂和跟隨蜂的數(shù)量相等，其數(shù)值就是種群大小。剩余影響算法效率的參數(shù)就是種群大小。

上面已經(jīng)分析了每一代所需的時(shí)間可近似與種群大小成正比，那么僅需對不同種群大小下得到一個(gè)可行解所需的迭代次數(shù)進(jìn)行實(shí)驗(yàn)便可分析其性能。對不同種群大小下找到一個(gè)可行解所需的迭代次數(shù)分別進(jìn)行了30次獨(dú)立實(shí)驗(yàn)，結(jié)果如圖2所示。

Figure 2 Relationship between population size and iteration圖2 種群大小與迭代次數(shù)關(guān)系圖

種群大小為10和15時(shí)的迭代次數(shù)波動情況相近，而種群大小為7時(shí)的迭代次數(shù)波動范圍大，且總體數(shù)值要高于總?cè)捍笮?0和15時(shí)的。

每一代所需的時(shí)間可近似與種群大小成正比，那么將搜索到一個(gè)可行解所需的平均迭代次數(shù)G與種群大小乘積的倒數(shù)定義為效率E。分別取30次獨(dú)立實(shí)驗(yàn)的迭代次數(shù)的中位數(shù)和平均數(shù)計(jì)算不同種群大小下的中位效率(Em)和平均效率(Ea)。計(jì)算結(jié)果如表2所示。

Table 2 Search efficiency for different population sizes表2 不同種群大小下的搜索效率

由于計(jì)算結(jié)果偏小，將結(jié)果做了乘以10 000的處理?？梢钥吹剑瑹o論是從中位數(shù)還是平均數(shù)來看，種群大小并非越小越好，也非越大越好，事實(shí)上經(jīng)測量，種群大小在小于7時(shí)，效率會急劇下降；在高于15時(shí)也會一直下降。實(shí)測得到在limit為30以及鄰域搜索范圍最大值為400comb時(shí)，種群大小設(shè)定為10左右效率是最高的。

4.2 優(yōu)化ABC與其他算法的性能比較

為定量分析本文所述改進(jìn)ABC—IABC (Improved Artificial Bee Colony algorithm)的性能，將其與基本ABC—BABC (Basic Artificial Bee Colony algorithm)、一種基于擁擠度概念的改進(jìn)ABC—CABC (Artificial Bee Colony Algorithm based on Congestion concept)[19,20]以及其它一些算法進(jìn)行對比實(shí)驗(yàn)。

目前已有許多算法用于搜索2×2快速矩陣乘法，本文選用這些算法中同為群體智能算法的遺傳算法GA(Genetic Algorithm)[6]與非群體智能算法的隨機(jī)搜索算法RS(Random Search)[21]作為代表進(jìn)行對比實(shí)驗(yàn)。另外，粒子群優(yōu)化算法與煙花算法在大量的研究中被證實(shí)具有較高的性能，本文選取它們的中值粒子群優(yōu)化算法MPSO(Median-oriented Particle Swarm Optimization)[22]和自適應(yīng)煙花算法AFWA(Adaptive FireWorks Algorithm)[23]進(jìn)行對比實(shí)驗(yàn)。

7種算法的實(shí)現(xiàn)均在同一編程環(huán)境，除各自算法策略，其它部分使用相同的數(shù)據(jù)結(jié)構(gòu)。在相同條件下，進(jìn)行3次重復(fù)實(shí)驗(yàn)。每次重復(fù)實(shí)驗(yàn)運(yùn)行11個(gè)單位時(shí)間，每隔1個(gè)單位時(shí)間采樣記錄一次當(dāng)前搜索到的不同解的個(gè)數(shù)。取3次實(shí)驗(yàn)的平均值,結(jié)果如圖3所示。

Figure 3 Solution numbers found by BABC,CABC,IABC,GA,RS,MPSO and AFWA in different running time圖3 7種算法搜索不同解數(shù)量隨時(shí)間變化圖

從圖3可以看出，3種ABC的性能都明顯優(yōu)于GA和RS的，2種優(yōu)化ABC較BABC性能都有所提升；AFWA的性能接近BABC的，而MPSO的性能僅比RS的略高。

由于矩陣乘法問題解空間的復(fù)雜性，特別是劣質(zhì)解的存在，使得GA的交叉操作和PSO的極值跟蹤操作難以使解收斂，而ABC和AFWA基于反饋的鄰域搜索機(jī)制能夠有效地使解收斂。

對于一種搜索算法，評價(jià)其性能指標(biāo)的重要因素包括搜索不同解的能力。如果在已搜索到的解的基礎(chǔ)上難以再搜索到新解，即搜索到的都是重復(fù)的解，也是不合格的。從圖3中可以看到，在已搜索到150個(gè)以上不同解的基礎(chǔ)上，IABC搜索到的新解總數(shù)仍保持較高的增長速度，而CABC的搜索速度已明顯下降，這也證實(shí)了IABC在搜索新解方面的優(yōu)秀性能。

5 結(jié)束語

本文采用人工蜂群算法重現(xiàn)了Strassen快速矩陣乘法算法。由于快速矩陣乘法問題的自身特性，尤其是劣質(zhì)解的存在，使得融入反饋思想的ABC相較其它經(jīng)典算法有極大的優(yōu)越性。本文在基本ABC的基礎(chǔ)上，采用了繞圈遍歷方法改進(jìn)，避免了鄰域的重復(fù)搜索。實(shí)驗(yàn)結(jié)果證實(shí)了人工蜂群算法的優(yōu)越性，以及在此基礎(chǔ)上繞圈遍歷策略帶來的性能提升。

關(guān)于快速矩陣乘法算法，當(dāng)前對其解的適應(yīng)度描述分為5個(gè)等級，即一個(gè)解可線性表示0,1,2,3,4個(gè)Ci映射的5個(gè)等級。算法中適應(yīng)度的設(shè)置對算法的性能影響較大，尤其是對于大的搜索空間而言，僅用5個(gè)適應(yīng)度劃分等級是明顯不夠的。因此，尋求更優(yōu)的適應(yīng)度函數(shù)對于矩陣乘法問題尤為重要。

此外，3×3快速矩陣乘法算法[24]搜索空間相對于2×2快速矩陣乘法要大得多[4]。如何尋找更加高效的智能搜索算法進(jìn)行快速矩陣乘法求解仍然是一個(gè)巨大的挑戰(zhàn)。