軟件項(xiàng)目調(diào)度中改進(jìn)遺傳算法應(yīng)用研究

薛云勇

摘? 要：在信息化程度越來(lái)越高的現(xiàn)代社會(huì)，計(jì)算機(jī)技術(shù)應(yīng)用越來(lái)越普遍。在計(jì)算機(jī)科學(xué)技術(shù)中，軟件公司是銜接用戶需求和程序人員對(duì)軟件具體細(xì)節(jié)編程的關(guān)鍵環(huán)節(jié)。為了緊跟時(shí)代步伐，本文對(duì)現(xiàn)代軟件項(xiàng)目中的遺傳算法進(jìn)行了分析研究，遺傳算法是模擬自然選擇和生物進(jìn)化過(guò)程的一類優(yōu)化算法，即進(jìn)化算法（Evolutionary Algorithms，EAs）中的一種，改進(jìn)遺傳算法是軟件項(xiàng)目調(diào)度的研究重點(diǎn)和發(fā)展方向。

關(guān)鍵詞：遺傳算法;軟件工程;調(diào)度研究;項(xiàng)目管理

中圖分類號(hào)：TP301.6;TP311.5? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）01-0095-02

Research on Improved Genetic Algorithms in Software Project Scheduling

XUE Yunyong

（Nanjing University of Information Science and Technology，Nanjing? 210044，China）

Abstract：The application of computer technology is becoming more and more popular in the modern society with higher degree of informatization. Software company is the key link to connect user needs and programmers to program specific details of software in computer science and technology. In order to keep pace with the times，the genetic algorithm in modern software projects is analyzed and studied in this paper. The genetic algorithm is one of the evolutionary algorithms（EAs）which simulates natural selection and biological evolution process. The improved genetic algorithm is the research focus and development direction of software project scheduling.

Keywords：genetic algorithm;software engineering;scheduling research;project management

1? 軟件項(xiàng)目調(diào)度中遺傳算法的產(chǎn)生和發(fā)展

遺傳算法（Genetic Algorithms，GA）是用數(shù)字化變化來(lái)表示生物進(jìn)化過(guò)程的一種計(jì)算機(jī)算法。遺傳算法將自然界中的演進(jìn)規(guī)律運(yùn)用到計(jì)算機(jī)信息科學(xué)與工程學(xué)科中的演進(jìn)算數(shù)方法。遺傳算法出現(xiàn)、形成于20世紀(jì)50年代后期到70年代初期，在最早期是一些進(jìn)行生物遺傳系統(tǒng)模擬研究的生物學(xué)家所采用的電子計(jì)算方法，隨著此方法的不斷推廣，人們逐漸對(duì)類似算法進(jìn)行總結(jié)、更新、補(bǔ)充，在此過(guò)程中就有人將自然界的生物進(jìn)化過(guò)程應(yīng)用到計(jì)算機(jī)編碼的算術(shù)設(shè)計(jì)之中，由于受當(dāng)時(shí)科技發(fā)展條件的限制，人們利用自然界規(guī)律來(lái)編排算法也只形成了單獨(dú)的小單元程序塊，且只能進(jìn)行變異操控。隨著后期的發(fā)展改進(jìn)和計(jì)算機(jī)科學(xué)技術(shù)的不斷進(jìn)步，小單元程序塊之間的聯(lián)系逐漸加強(qiáng)，并逐漸形成一個(gè)體系完備的邏輯體，最后就形成了現(xiàn)在計(jì)算機(jī)所使用的成熟的遺傳算法。遺傳算法這一計(jì)算機(jī)項(xiàng)目工程新名詞最先是由John H. Holland提出，他的著作的出版是遺傳算法發(fā)展的里程碑，其對(duì)遺傳算法的發(fā)展和改進(jìn)具有歷史性意義，John H. Holland常被視為遺傳算法問(wèn)世的標(biāo)志。De Jong對(duì)遺傳算法（Genetic Algorithms，GA）進(jìn)行了全面、系統(tǒng)的介紹和整理，從而使遺傳算法（Genetic Algorithms，GA）在計(jì)算機(jī)信息科學(xué)中得到了認(rèn)可和應(yīng)用，并且使其在使用的過(guò)程中不斷得到修改和完善。在上個(gè)世紀(jì)90年代之后，遺傳算法（Genetic Algorithms，GA）進(jìn)入高速發(fā)展階段，我國(guó)對(duì)遺傳算法的研究也是從20世紀(jì)90年代開(kāi)始的[1]。在上個(gè)世紀(jì)80年代中期之前，遺傳算法在計(jì)算機(jī)科學(xué)領(lǐng)域之中并沒(méi)有得到實(shí)際性的應(yīng)用，在那個(gè)時(shí)期人們對(duì)遺傳算法的學(xué)習(xí)只限于算法的理論知識(shí)認(rèn)知。隨著計(jì)算機(jī)科學(xué)技術(shù)的成熟以及人們對(duì)遺傳算法認(rèn)識(shí)的深入，遺傳算法在計(jì)算機(jī)程序設(shè)計(jì)中不斷得到應(yīng)用，其價(jià)值也得到了此領(lǐng)域?qū)＜业目隙ā?/p>

遺傳算法（Genetic Algorithms，GA）在具有操作簡(jiǎn)便、算數(shù)思想邏輯清晰優(yōu)勢(shì)的同時(shí)，還能有效求解NP類型的多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，因此得到諸多學(xué)科和不同研究領(lǐng)域?qū)＜业母叨戎匾暫蛷V泛認(rèn)可。遺傳算法對(duì)于復(fù)雜問(wèn)題的解決高效而迅速，所以其在軟件工程項(xiàng)目調(diào)度問(wèn)題和優(yōu)化軟件工程項(xiàng)目求解方面優(yōu)勢(shì)顯著。

2? 軟件發(fā)展的背景和遺傳算法在軟件工程調(diào)度中的重要作用

進(jìn)行軟件項(xiàng)目調(diào)度時(shí)，求解成功率有高低之分，求解質(zhì)量有好壞之分。影響軟件項(xiàng)目調(diào)度模型工程效益的因素包括從事本項(xiàng)目的程序員的編碼學(xué)習(xí)能力、工作人員的工作能力和經(jīng)驗(yàn)、工作人員的加班上限、工程任務(wù)和技能匹配、技能等級(jí)難度等諸多方面[2]。軟件項(xiàng)目調(diào)度以提高求解命中率為前提，規(guī)范處理軟件工程進(jìn)度和程序，通過(guò)改進(jìn)、修補(bǔ)遺傳算法模型進(jìn)行優(yōu)化求解。通過(guò)實(shí)驗(yàn)結(jié)論來(lái)證明通過(guò)優(yōu)化后的遺傳算法加以改進(jìn)的調(diào)度模型具有更好的工程項(xiàng)目?jī)?yōu)化性能，使項(xiàng)目在工程約定期內(nèi)，低成本、高質(zhì)量地達(dá)到項(xiàng)目規(guī)劃要求。遺傳算法（Genetic Algorithms，GA）是進(jìn)化算法的一種，同時(shí)，進(jìn)化算法還包括：進(jìn)化編程、進(jìn)化策略、遺傳編程等。遺傳算法具有廣泛適用性和自適應(yīng)性等特點(diǎn)，因此算法的組合性改良、函數(shù)性改良、模式化檢驗(yàn)、機(jī)器語(yǔ)言學(xué)習(xí)、智能化操控、生產(chǎn)的調(diào)度分配等方面得到了廣泛的推廣和應(yīng)用，這是軟件項(xiàng)目調(diào)度對(duì)改進(jìn)遺傳算法的研究熱度越來(lái)越高的原因之一。

相較于傳統(tǒng)的優(yōu)化算法，遺傳算法（Genetic Algori-thms，GA）優(yōu)勢(shì)明顯：一是在算法變量上的區(qū)分，計(jì)算機(jī)中傳統(tǒng)的優(yōu)化算法不是對(duì)程序之中變量的直接改變和操作，而遺傳算法的運(yùn)算對(duì)象是整個(gè)編碼個(gè)體，遺傳算法（Genetic Algorithms，GA）此操作處理方法可以直接對(duì)結(jié)構(gòu)對(duì)象整個(gè)結(jié)構(gòu)進(jìn)行操作，十分方便地利用遺傳操作算子來(lái)模仿生物在自然界中的遺傳和進(jìn)化，在處理一些無(wú)數(shù)值概念問(wèn)題方面具有明顯的優(yōu)越性，如集合、序列、矩陣問(wèn)題等。

3? 軟件項(xiàng)目調(diào)度中遺傳算法的性能改進(jìn)

遺傳算法以對(duì)生物的進(jìn)化機(jī)制進(jìn)行模擬為基本思想，由達(dá)爾文的物競(jìng)天擇，適者生存的自然生物進(jìn)化論演變來(lái)的遺傳算法的基本步驟，包括編碼、選擇、交叉、變異、初始數(shù)據(jù)群體的生成以及適應(yīng)性評(píng)估的檢測(cè)。常用的選擇算法有比例選擇、最佳選擇、競(jìng)賽選擇，遺傳算法最重要、最常用的操作是交叉操作，交叉操作又分為單個(gè)交叉，對(duì)點(diǎn)交叉，多個(gè)交叉。單個(gè)交叉是指對(duì)編碼串中隨機(jī)的一個(gè)交叉點(diǎn)進(jìn)行交換，對(duì)點(diǎn)交叉是指交換編碼串中隨機(jī)選擇的兩個(gè)編碼串，而多個(gè)交叉是指對(duì)隨機(jī)選擇的多個(gè)交叉點(diǎn)進(jìn)行編碼串交換。通過(guò)交叉操作會(huì)產(chǎn)生新的運(yùn)算方式，新的運(yùn)算方式繼承了交叉操作前算法的優(yōu)秀特性。遺傳算法中的變異是指對(duì)進(jìn)行變異的個(gè)體隨機(jī)選擇變異位進(jìn)行變異，遺傳算法中變異發(fā)生的概率極低。變異分為實(shí)值變異、二進(jìn)制變異。

20世紀(jì)70年代中期，美國(guó)提出軟件工程的軟件項(xiàng)目管理，當(dāng)時(shí)美國(guó)國(guó)防部專門(mén)研究的軟件不能按時(shí)提交，通過(guò)對(duì)此項(xiàng)目進(jìn)行調(diào)查發(fā)現(xiàn)，不能按時(shí)完成的項(xiàng)目中，70%是因?yàn)楣芾聿簧埔鸬模羌夹g(shù)原因引起的軟件開(kāi)發(fā)預(yù)算超支和軟件開(kāi)發(fā)質(zhì)量達(dá)不到用戶要求[3]。于是軟件開(kāi)發(fā)者開(kāi)始重視軟件開(kāi)發(fā)各項(xiàng)工作的管理。20世紀(jì)90年代中期，軟件研發(fā)項(xiàng)目管理不善導(dǎo)致了諸多問(wèn)題，如軟件工程在約定時(shí)間內(nèi)無(wú)法完成，軟件開(kāi)發(fā)的預(yù)算不能把控以及開(kāi)發(fā)出的軟件達(dá)不到用戶預(yù)期要求，軟件工程的后期無(wú)法維護(hù)等。這些問(wèn)題的存在造成了極大的經(jīng)濟(jì)損失，美國(guó)國(guó)防部對(duì)因軟件工程失誤造成的損失進(jìn)行了統(tǒng)計(jì)，結(jié)果顯示，美國(guó)在軟件工程項(xiàng)目中的損失高達(dá)810億美元。在實(shí)際的軟件工程項(xiàng)目中，軟件危機(jī)對(duì)世界各國(guó)造成的損失遠(yuǎn)遠(yuǎn)超出810億美元。因此，軟件危機(jī)的解決方法研究得到了世界各國(guó)的高度關(guān)注，北大西洋公約組織于德國(guó)召開(kāi)的以軟件危機(jī)為主題的國(guó)際會(huì)議，針對(duì)如何降低軟件危機(jī)帶來(lái)的損失進(jìn)行了一次學(xué)術(shù)探討，此次會(huì)議第一次提出了解決軟件危機(jī)的工程方案名稱：軟件工程。從此以后，軟件工程成為了一門(mén)新的計(jì)算機(jī)科學(xué)學(xué)科。

和其他項(xiàng)目管理相比，軟件項(xiàng)目管理具有特殊性。如計(jì)算機(jī)硬件的生產(chǎn)是在生產(chǎn)流程和生產(chǎn)技術(shù)指導(dǎo)下進(jìn)行，軟件工程的開(kāi)發(fā)基于算術(shù)邏輯思維，因此，在軟件開(kāi)發(fā)的過(guò)程中，軟件開(kāi)發(fā)的開(kāi)發(fā)情況和發(fā)展方向難以估量。對(duì)于生產(chǎn)的軟件的評(píng)價(jià)標(biāo)準(zhǔn)為相對(duì)性評(píng)價(jià)，軟件開(kāi)發(fā)工作具有較高的延展性和創(chuàng)造性，這就容易導(dǎo)致軟件開(kāi)發(fā)過(guò)程難以把控。例如，由數(shù)千個(gè)程序員對(duì)Windows操作系統(tǒng)進(jìn)行修改、編寫(xiě)，如果沒(méi)有完善的管理系統(tǒng)，則龐大復(fù)雜系統(tǒng)的正常運(yùn)行以及所生產(chǎn)的軟件質(zhì)量難以保障。

4? 軟件項(xiàng)目調(diào)度中遺傳算法的存在優(yōu)勢(shì)及模塊的調(diào)度

遺傳算法的作用對(duì)象是結(jié)構(gòu)而非傳統(tǒng)算法的具體變量，因此遺傳算法具有簡(jiǎn)便、快速以及錯(cuò)誤率低的特點(diǎn)。遺傳算直接操作的對(duì)象包括集合、序列、矩陣、數(shù)列、鏈表等結(jié)構(gòu)。在不同于傳統(tǒng)檢索的肯定搜索規(guī)則，遺傳算法檢索時(shí)使用的是以概率變化為依據(jù)的檢索方式。因此，其對(duì)聯(lián)通性，凹凸性等沒(méi)有特別的要求，遺傳算法的輔助信息也較為簡(jiǎn)單，它的適用范圍相對(duì)于其它算法而言更廣[4]。遺傳算法在檢索過(guò)程中采用并行處理方式，這就避免了算法陷入局部最優(yōu)解的困境當(dāng)中，算法的運(yùn)行效率也大大提高。

隨著社會(huì)的發(fā)展，軟件工程存在的問(wèn)題也發(fā)生了變化。軟件工程調(diào)度中的任務(wù)調(diào)度問(wèn)題，是任務(wù)調(diào)度模型在軟件項(xiàng)目調(diào)度中急需解決的問(wèn)題。一般用TPG來(lái)描述軟件工程任務(wù)調(diào)度模型中模塊與模塊任務(wù)之間的存在的內(nèi)在與外在關(guān)系。項(xiàng)目中模塊的操作執(zhí)行需要技能集合，完成模塊任務(wù)需要相當(dāng)?shù)墓ぷ髁?，任?wù)之間有前驅(qū)后繼關(guān)系，在滿足以上要求的前提之下，還要考慮到降低成本和縮短員工的工作時(shí)間。

5? 結(jié)? 論

隨著我國(guó)信息行業(yè)的快速發(fā)展，在利用遺傳算法解決軟件項(xiàng)目調(diào)度問(wèn)題時(shí)，要嚴(yán)格遵循遺傳算法的使用步驟和規(guī)則，了解軟件項(xiàng)目設(shè)計(jì)流程，并選擇適合的遺傳算法來(lái)解決問(wèn)題，降低軟件工程項(xiàng)目開(kāi)發(fā)過(guò)程成本和縮短時(shí)間。

參考文獻(xiàn)：

[1] 高世剛.基于云遺傳算法的軟件項(xiàng)目資源調(diào)度研究 [D].武漢：武漢科技大學(xué)，2010.

[2] 范增輝，方偉.改進(jìn)遺傳算法在軟件項(xiàng)目調(diào)度中的研究 [J].計(jì)算機(jī)應(yīng)用與軟件，2016，33（12）：34-39+48.

[3] 孔令飛.遺傳算法在軟件項(xiàng)目調(diào)度中的應(yīng)用 [D].長(zhǎng)春：吉林大學(xué)，2008.

[4] 張搴林，曾誠(chéng).基于改進(jìn)遺傳算法的軟件項(xiàng)目人力資源調(diào)度研究 [J].中國(guó)新通信，2013，15（2）：87.