基于鯨魚(yú)優(yōu)化算法的類(lèi)圖重構(gòu)研究

胡志剛　楊娜　劉偉

摘? ?要：為了提高軟件質(zhì)量，組合使用重構(gòu)技術(shù)、軟件度量和元啟發(fā)式搜索可以有效改進(jìn)軟件的結(jié)構(gòu)而不影響其功能. 本文提出一種基于鯨魚(yú)優(yōu)化算法的類(lèi)圖重構(gòu)方法，并結(jié)合耦合、繼承、抽象3個(gè)指標(biāo)所構(gòu)建的質(zhì)量模型來(lái)指導(dǎo)類(lèi)圖重構(gòu)序列尋優(yōu). 在6個(gè)不同的開(kāi)源程序上使用鯨魚(yú)優(yōu)化方法對(duì)類(lèi)圖進(jìn)行重構(gòu)，研究結(jié)果表明：基于鯨魚(yú)優(yōu)化算法的類(lèi)圖重構(gòu)在質(zhì)量增益上優(yōu)于模擬退火算法和爬山算法，可有效提高重構(gòu)質(zhì)量.

關(guān)鍵詞：軟件質(zhì)量;軟件重構(gòu);鯨魚(yú)優(yōu)化;質(zhì)量度量;類(lèi)圖

中圖分類(lèi)號(hào)：TP311? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：A

Research on Class Diagram Refactoring Based

on Whale Optimization Algorithm

HU Zhigang YANG Na LIU Wei

（1. School of Computer Science and Engineering，Central South University，Changsha 410083，China;

2. College of Computer Science and Electronic Engineering，Hunan University of Chinese Medicine，Changsha 410208，China）

Abstract：In order to improve software quality，the combination of refactoring techniques，software metrics，and meta-heuristic search can effectively improve the structure of software without affecting its function. In this paper，a class diagram refactoring method based on Whale Optimization Algorithm is proposed，and the quality model constructed by index coupling，inheritance and abstraction is empolyed to guide the search for the optimal refactoring sequence. Cetacean optimization method is used to refactor the class diagram in six different open source programs. The results show that the class diagram refactor the based on cetacean optimization algorithm is superior to Simulated Annealing Algorithm and Hill Climbing Algorithm in terms of quality gain，and can effectively improve the quality refactoring.

Key words：software quality;software refactoring;whale optimization algorithm;quality measures;class diagram

軟件產(chǎn)品經(jīng)常隨著需求的變更演變?yōu)橥瓿刹煌墓δ埽@些演變可能使軟件設(shè)計(jì)變得更加復(fù)雜，致使軟件質(zhì)量降低. 重構(gòu)被定義為優(yōu)化現(xiàn)有系統(tǒng)的內(nèi)部結(jié)構(gòu)而不改變其功能，主要通過(guò)改進(jìn)抽象、耦合、繼承等質(zhì)量屬性來(lái)提高軟件質(zhì)量. 重構(gòu)最初是在面向?qū)ο筌浖沫h(huán)境中提出的[1]，軟件重構(gòu)已經(jīng)被應(yīng)用于面向方面的軟件、軟件產(chǎn)品線等不同的環(huán)境，以及應(yīng)用在代碼、模型、文檔等不同的層次中.

軟件重構(gòu)階段可以分為代碼層重構(gòu)和模型層重構(gòu)，模型層的類(lèi)圖重構(gòu)通過(guò)找到最佳重構(gòu)序列來(lái)提高軟件質(zhì)量，而尋找最佳重構(gòu)是一個(gè)優(yōu)化問(wèn)題，可通過(guò)進(jìn)化算法來(lái)實(shí)現(xiàn)，進(jìn)化算法包括爬山算法[2]、模擬退火算法、群體智能算法和生物地理算法等. 群體智能算法主要是模擬動(dòng)物的群體行為，依靠相互合作來(lái)捕獲食物，通過(guò)自身學(xué)習(xí)及向他人學(xué)習(xí)來(lái)不斷改變自身的搜索方向來(lái)提高捕食的效率. 群體智能優(yōu)化算法的優(yōu)勢(shì)在于利用群體能力進(jìn)行協(xié)同搜索，從而在解空間內(nèi)找到最優(yōu)解. 其中鯨魚(yú)優(yōu)化算法是根據(jù)鯨魚(yú)圍捕獵物的行為而提出的算法.

很多人都對(duì)軟件重構(gòu)進(jìn)行了相關(guān)研究. Kebir等人[3]提出了一種基于遺傳算法的軟件構(gòu)件自動(dòng)重構(gòu)方法，首先檢測(cè)出代碼壞味道，然后從基于組件的源代碼中構(gòu)建源代碼模型，最后用遺傳算法搜索重構(gòu)的最佳序列來(lái)減少源代碼模型中存在的代碼壞味道. Mohan等人[4]介紹了許多優(yōu)化算法用于自動(dòng)化重構(gòu)，實(shí)現(xiàn)了一個(gè)Java重構(gòu)工具M(jìn)ultiRefactor，該工具著眼于軟件質(zhì)量、代碼優(yōu)先級(jí)及重構(gòu)覆蓋率. Khatchadourian等人[5]提出了一種自動(dòng)重構(gòu)方法，并設(shè)計(jì)了一個(gè)Eclipse IDE的插件，幫助開(kāi)發(fā)人員以一種保持語(yǔ)義的方式編寫(xiě)高效的流代碼. 該方法基于一種新的數(shù)據(jù)排序和類(lèi)型狀態(tài)分析，由前置條件和轉(zhuǎn)換組成，用于自動(dòng)確定將順序流轉(zhuǎn)換為并行流、將已經(jīng)并行的流進(jìn)行無(wú)序或去并行化. 與這些針對(duì)局部代碼的重構(gòu)相比，本文側(cè)重于全局的類(lèi)圖重構(gòu)及模型優(yōu)化.

軟件質(zhì)量模型被廣泛應(yīng)用于軟件重構(gòu)以識(shí)別重構(gòu)對(duì)象、引導(dǎo)重構(gòu)策略的選擇以及評(píng)估重構(gòu)后軟件質(zhì)量的變化. 本研究重點(diǎn)考慮抽象、耦合和繼承屬性，它們?cè)谲浖|(zhì)量中占很大因素，對(duì)于單個(gè)質(zhì)量指標(biāo)可以表示軟件度量的不同方面. 繼承可以指導(dǎo)類(lèi)是否是正確關(guān)聯(lián)和擴(kuò)展的[6]，以及類(lèi)的層級(jí)結(jié)構(gòu)，該度量結(jié)合了實(shí)現(xiàn)接口和抽象類(lèi)的使用. 耦合可用來(lái)指導(dǎo)軟件系統(tǒng)中對(duì)象之間相互依賴(lài)的程度[7]，期望盡可能的低耦合. 抽象是指導(dǎo)系統(tǒng)的穩(wěn)定，系統(tǒng)的變化是體現(xiàn)在具體類(lèi)上的，使用抽象可以提升設(shè)計(jì)的簡(jiǎn)單性，改善軟件開(kāi)發(fā)的質(zhì)量[8]. 因此我們采用繼承、耦合和抽象來(lái)構(gòu)建質(zhì)量模型.

鯨魚(yú)優(yōu)化算法搜索能力強(qiáng)、結(jié)構(gòu)簡(jiǎn)單、參數(shù)少并且易于實(shí)現(xiàn) [9]，所以選擇鯨魚(yú)優(yōu)化算法尋找最優(yōu)的類(lèi)圖重構(gòu)序列來(lái)進(jìn)行類(lèi)圖重構(gòu)，最后通過(guò)構(gòu)建質(zhì)量模型來(lái)評(píng)價(jià)類(lèi)圖重構(gòu)的質(zhì)量.

1? ?質(zhì)量模型構(gòu)建

為了簡(jiǎn)化UML類(lèi)圖在RAM中的表示，以便用鯨魚(yú)優(yōu)化算法處理類(lèi)圖，用抽象數(shù)據(jù)結(jié)構(gòu)UML映射復(fù)雜度更低一些. 考慮15種常規(guī)的類(lèi)圖重構(gòu)重命名類(lèi)、用委托關(guān)系代替繼承關(guān)系、用繼承關(guān)系代替委托關(guān)系、提取到子類(lèi)、提取到父類(lèi)、折疊繼承關(guān)系、內(nèi)聯(lián)類(lèi)、提取類(lèi)、函數(shù)下移、方法提到基類(lèi)中、方法重命名、字段下移、字段上移、字段重命名、封裝字段. 通過(guò)一系列的轉(zhuǎn)化來(lái)找到最優(yōu)的重構(gòu)序列，然而在一些場(chǎng)景中，如果多個(gè)類(lèi)都繼承自某一父類(lèi)或者父接口，會(huì)具有接口上的一致性. 但是如果將其中的某些類(lèi)單獨(dú)提取出來(lái)，可能會(huì)破壞這種一致性. 因此，為了提高類(lèi)圖的整體質(zhì)量，有時(shí)候需要綜合考慮多個(gè)因素，而不僅僅只是考慮接口的一致性，進(jìn)而獲得更好的解決方案.

2? ?基于鯨魚(yú)優(yōu)化算法的類(lèi)圖重構(gòu)

鯨魚(yú)優(yōu)化算法是一種元啟發(fā)式優(yōu)化算法，該算法模擬了座頭鯨的捕獵行為，座頭鯨喜歡捕食一群靠近水面的小魚(yú)和小蝦，遇到獵物后會(huì)先向下俯沖大約12 m，然后開(kāi)始在獵物周?chē)圃炻菪螝馀荩詈笥蜗蛩娌妒倡C物[10]. 這個(gè)過(guò)程提取出三個(gè)數(shù)學(xué)模型即圍捕獵物、螺旋氣泡網(wǎng)捕食和尋找獵物. 用鯨魚(yú)算法解決類(lèi)圖優(yōu)化的基本思想如圖1所示.

根據(jù)類(lèi)圖可能的重構(gòu)序列及質(zhì)量模型作為優(yōu)化的參數(shù)，鯨魚(yú)群中的每一個(gè)個(gè)體的位置均包含一組重構(gòu)序列. 利用鯨魚(yú)尋找獵物的方式不斷更新類(lèi)圖的重構(gòu)序列，直到找到最好的位置，即找到最佳重構(gòu)序列. 針對(duì)質(zhì)量度量，首先采用耦合、繼承和抽象這三個(gè)適應(yīng)度函數(shù)來(lái)進(jìn)行指導(dǎo)，并獲得鯨魚(yú)優(yōu)化算法針對(duì)單個(gè)度量的改進(jìn)程度.

2.1? ?提取重構(gòu)序列

2.2? ?螺旋氣泡網(wǎng)尋找

2.2.1? ?收縮包圍機(jī)制

2.2.2? ?螺旋更新位置

2.3? ?搜索最優(yōu)重構(gòu)序列

3? ?實(shí)驗(yàn)環(huán)境與結(jié)果分析

3.1? ?數(shù)據(jù)來(lái)源

將鯨魚(yú)優(yōu)化算法用于類(lèi)圖的優(yōu)化，將抽象、耦合和繼承這三個(gè)適應(yīng)度函數(shù)來(lái)進(jìn)行衡量?jī)?yōu)化的結(jié)果. 實(shí)驗(yàn)的輸入程序包括6個(gè)開(kāi)源Java項(xiàng)目：JSON，一個(gè)用于數(shù)據(jù)交換格式的Java庫(kù);詞法分析器生成器JFlex;基于xml的遠(yuǎn)程過(guò)程調(diào)用庫(kù)Apache-XmlRpc;Mango及解析器生成器和基于GUI框架開(kāi)發(fā)的圖形編輯器JHotDraw. 上述6個(gè)開(kāi)源項(xiàng)目針對(duì)不同的軟件結(jié)構(gòu)，有關(guān)實(shí)驗(yàn)的Java項(xiàng)目的詳細(xì)信息見(jiàn)表4. 實(shí)驗(yàn)的總運(yùn)行次數(shù)為10*3（搜索）*3（函數(shù)）*6（基準(zhǔn)），總共運(yùn)行540次. 實(shí)驗(yàn)在一臺(tái)3.40GHz Intel Core i7-3770處理器和8gb RAM的PC上進(jìn)行.

3.2? ?實(shí)驗(yàn)結(jié)果分析

圖3展示了運(yùn)用鯨魚(yú)優(yōu)化算法的結(jié)果，顯示了6個(gè)基準(zhǔn)程序中每個(gè)適應(yīng)度函數(shù)的平均質(zhì)量增益（通過(guò)最終的總體度量分?jǐn)?shù)減去初始分?jǐn)?shù)，10次運(yùn)行的平均值）.

在三個(gè)適應(yīng)度函數(shù)中，耦合是唯一一個(gè)顯示出顯著改善的因子. 抽象的改進(jìn)很小，繼承完全沒(méi)有變化. 事實(shí)上，繼承函數(shù)唯一有變化的情況是在模擬退火中. 對(duì)于耦合函數(shù)在改進(jìn)方面更有效，在抽象和繼承函數(shù)中改進(jìn)很小表明用于組合這些函數(shù)的度量缺乏波動(dòng)性. 在Mango項(xiàng)目中耦合函數(shù)的增益明顯高于其他，這說(shuō)明Mango項(xiàng)目耦合程度較高，易于改進(jìn). XmlRpc在耦合方面改進(jìn)很小，可能是因?yàn)樗?lèi)之間的耦合很小.

結(jié)果表明鯨魚(yú)優(yōu)化算法相對(duì)質(zhì)量提升更優(yōu)，但也表明，模擬退火算法優(yōu)于爬山算法，這是因?yàn)榕郎剿惴ǜ菀紫萑刖植孔顑?yōu)，提前找到的最優(yōu)重構(gòu)序列并不是全局最優(yōu)，鯨魚(yú)優(yōu)化算法相比較而言不容易陷入局部最優(yōu). 同樣的抽象和繼承缺乏應(yīng)用的重構(gòu)操作，這些函數(shù)的質(zhì)量增益差的原因是由于缺少可用的操作，而其他指標(biāo)更不穩(wěn)定，并且有更多的重構(gòu)操作可用來(lái)改進(jìn)他們.

為了進(jìn)一步驗(yàn)證鯨魚(yú)優(yōu)化算法的求解性能，將鯨魚(yú)優(yōu)化算法與爬山算法和模擬退火算法這三種不同的優(yōu)化算法進(jìn)行了60次求解. 圖5表明了鯨魚(yú)優(yōu)化算法用于類(lèi)圖重構(gòu)的收斂性更好，因?yàn)榕郎剿惴ㄊ沁x擇鄰近點(diǎn)，容易陷入局部最優(yōu)，達(dá)到快速收斂，模擬退火算法的特點(diǎn)是隨機(jī)選擇，相比較而言沒(méi)那么容易陷入局部最優(yōu)，收斂速度相對(duì)慢一些，而鯨魚(yú)優(yōu)化收斂是取決于a，固定住a，來(lái)弱化算法，從而減弱其收斂性，實(shí)驗(yàn)結(jié)果表明，鯨魚(yú)優(yōu)化算法的全局優(yōu)化能力最強(qiáng)，且算法相對(duì)穩(wěn)定，而模擬退火算法優(yōu)化能力和穩(wěn)定性居中，且優(yōu)于爬山算法，所以鯨魚(yú)優(yōu)化算法在收斂性和搜索空間上都要更優(yōu)一些. 對(duì)函數(shù)的初始和最終度量分?jǐn)?shù)進(jìn)行統(tǒng)計(jì)分析，使用具有95%置信水平的Wilcoxon符號(hào)秩檢驗(yàn)，所獲得的結(jié)果在比較函數(shù)的每次運(yùn)行時(shí)具有統(tǒng)計(jì)學(xué)意義.

4? ?總? ?結(jié)

近年來(lái)，有很多關(guān)于軟件重構(gòu)的研究，但現(xiàn)有的重構(gòu)研究多側(cè)重于在代碼編寫(xiě)階段為開(kāi)發(fā)人員提供局部代碼的重構(gòu)及代碼推薦，很少考慮在分析設(shè)計(jì)階段為開(kāi)發(fā)設(shè)計(jì)人員提供全局性的重構(gòu). 本文采用鯨魚(yú)優(yōu)化算法來(lái)調(diào)整類(lèi)成員與類(lèi)之間的映射關(guān)系，得到一組最優(yōu)重構(gòu)序列. 同時(shí)，實(shí)驗(yàn)對(duì)比證明了本文提出的鯨魚(yú)優(yōu)化算法可以有效應(yīng)用于軟件重構(gòu)進(jìn)而提高軟件質(zhì)量. 后續(xù)工作將對(duì)穩(wěn)定性、可靠性等屬性做進(jìn)一步研究.

參考文獻(xiàn)

[1]? ? BAQAIS A A B，ALSHAYEB M. Automatic software refactoring：a systematic literature review[J]. Software Quality Journal，2020，28（2）：459—502.

[2]? ? 張英杰，郭會(huì)芳，付海濱，等. 面向多模態(tài)函數(shù)的自適應(yīng)混沌爬山微粒群算法[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，40（2）：77—81.ZHANG Y J，GUO H F，F(xiàn)U H B，et al. An adaptive chaotic hill-climbing particle swarm optimization algorithm for multimodal functions[J]. Journal of Hunan University （Natural Sciences），2013，40（2）：77—81. （In Chinese）

[3]? ? KEBIR S，BORNE I，MESLATI D. A genetic algorithm-based approach for automated refactoring of component-based software[J]. Information and Software Technology，2017，88：17—36.

[4]? ? MOHAN M，GREER D. Using a many-objective approach to investigate automated refactoring[J]. Information and Software Technology，2019，112：83—101.

[5]? ? KHATCHADOURIAN R，TANG Y M，BAGHERZADEH M，et al.Safe automated refactoring for intelligent parallelization of Java 8 streams[C]//2019 IEEE/ACM 41st International Conference on Software Engineering （ICSE）. Montreal，QC，Canada.IEEE：2019：619—630.

[6]? ? SAVIC M，IVANOVIC M，RADOVANOVIC M. Analysis of high structural class coupling in object-oriented software systems[J]. Computing，2017，99（11）：1055—1079.

[7]? ? BASHIR R S，LEE S P，KHAN S U R，et al. UML models consistency management：Guidelines for software quality manager[J]. International Journal of Information Management，2016，36（6）：883—899.

[8]? ? GHANNEM A，KESSENTINI M，HAMDI M S，et al. Model refactoring by example：A multi-objective search based software engineering approach[J]. Journal of Software：Evolution and Process，2018，30（4）：e1916.

[9]? ? CHAKRABORTY A，KAR A K.Swarm intelligence：A review of algorithms[M]//Nature-Inspired Computing and Optimization.Cham：Springer International Publishing，2017：475—494.

[10]? NASIRI J，KHIYABANI F M. A whale optimization algorithm （WOA） approach for clustering[J]. Cogent Mathematics & Statistics，2018，5（1）：1483565.