怎麼寫演算法改進的小論文

① 詳談改進的遺傳演算法求解柔性作業車間調度問題論文

詳談改進的遺傳演算法求解柔性作業車間調度問題論文

0 引言

作業車間調度問題(Job-shop scheling problem，JSP)是研究生產線調度問題最常用的模型之一，也是實現先進製造和提高生產效率的基礎和關鍵. 柔性作業車間調度問題( Flexible jobshopscheling problem，FJSP)是傳統作業車間調度問題的擴展，在傳統的作業車間調度問題中，每個工件的加工工序是確定的，每一道工序的加工機器和加工時間也是確定的，而在柔性作業車間調度問題中，每個工件的每一道工序可以在多個可選擇的加工機器上進行加工，並且不同的加工機器所需要的加工時間是不同的，增加了調度的靈活性，比較符合生產的實際情況.

柔性作業車間調度問題已經被證明是更復雜的NP-Hard 問題，因而難以取得最優解. 目前，求解FJSP 的常用方法有禁忌搜索( TS)，模擬退火(SA)和遺傳演算法(GA)等. 其中遺傳演算法以其操作簡單、魯棒性強、搜索全局最優解速度快等特點，在生產調度領域得到了廣泛的應用.

遺傳演算法是由美國J. Holland 教授於1975 年提出的，是一種模擬自然進化過程的一種優化演算法. 由於傳統的遺傳演算法存在著較大的缺陷，國內外學者已從不同角度對其進行了改進，本文對傳統遺傳演算法的初始種群進行橡兆局了改進，以提高初始解的質量.

1 柔性作業車間調度模型設有n 個待加工工件J(J1，J2，…，Jn)，在m台設備上加工M(M1，M2，…，Mm)，每個工件Ji有Pi(Pi1，Pi2，…，Pin) 道工序，每道工序可在一台或多台設備上加工，同一道工序在不同設備上加工的時間可能不等，工序Pik的可選機器集為Mik(Mik 罬)，每台設備的加工時間從0 開始，加工完所有工件的完成時間為ETMi . 本文以最小化最大完工時間為性能指標，其目標函數為梁讓:f(x) = min(max(ETMi))，1 ≤ i ≤ m模型需滿足如下約束條件:(1)同一工件的工序加工順序確定;(2)每道工序必須在它的上一道工序加工完成後才能開始加工;(3)每道工序只能選擇一台設備進行操作;(4)每台設備在同一時間只能加工一個工件的一道工序;(5)每道工序在設備上操作時都不允許被中斷;(6) 不同工件工序之間沒有先後約束條件.一個包含3 個工件、5 台機器的FJSP 的問題.

2 演算法的設計

(1) 基因編碼

常用的遺傳演算法編碼方案有二進制編碼、格雷碼編碼、矩陣編碼、自然數編碼等，本文採用自然數編碼，每條染色體表示一個可行解，同時採用雙層編碼，第一層編碼為基於工件的工序編碼，編碼長度為所有工件工序之和，基因值代表工件號，基因值出現的次數代表該工件的工序總數，第二層編碼為對應於第一層工件工序的機器編碼，所以編碼長度也為所有工件工序之和.染色體表示的工序順序為(O31，O11，O12，O21，O22，O32，O13，O33)，染色體表示的機器序列為(M2，M4，M2，M1，M4，M5，M3，M4).

(2)產生初始種群

初始種群的優良對生物進化會產生很大的影響，本文對初始種群的機器選擇進行了改進，首先隨機生成初始猜灶種群的工序編碼，工序編碼生成後就要對應生成機器編碼，每個工件工序在對應可選機器集中選擇機器時，是以不同的概率的來選擇不同的機器，機器加工時間短的以大概率被選擇，相比之下，機器加工時間長的以小概率被選擇，這樣既保證了機器選擇的隨機性，也優化了初始種群.

(3)適應度函數的確定

本文以最小化最大完工時間為目標函數，故選擇全部工件完工時間作為評價種群優劣的標准，設n 個待加工工件在m(M1，M2，…，Mm) 台設備上加工，所有加工工件工序在設備上的最後完工時間為ETMi(i = 1，2，…，m)，T = max(ETMi)，則適應度函數fi = 1 /T，T 越小，則適應度越大，即個體越優.

(4)選擇

選擇操作的目的是為了保留優良個體，使他們可以遺傳到下一代. 本文採用精英保留策略和輪盤賭法相結合的方法，對父代個體和子代個體進行選擇時直接將最優個體和次優個體遺傳到下一代，然後對剩餘的個體採用輪盤賭法進行選擇，選擇出p - 2 個個體到下一代進行遺傳操作. 若種群規模為p，個體i 的適應度為fi，則個體i 被選擇的概率pi為pi = fi /Σpk = 1fk即適應度越高的個體被選擇的概率就越大.

(5)交叉

交叉操作是產生新個體的主要方法，提高全局搜索能力. 本文採用單點交叉方式，即隨機產生一個交叉點，交換交叉點後的基因. 從種群中隨機選擇兩個個體，交換兩個個體工序編碼的交叉點後面的基因，將交叉後工件多餘的工序替換為其他工件缺失的工序;機器部分則按交叉前工件工序所選擇的機器進行相應調整以保證其子代染色體的`合法性.

(6)變異

變異操作的目的是改變演算法的局部搜索能力，有助於維持進化群體的多樣性，防止過早陷入局部最優. 本文採用互換方式，即隨機產生兩個變異點，交換兩點的基因值. 從種群中隨機選擇一個個體，對該個體的工序編碼部分隨機產生兩個變異點，交換兩點的基因值，同時將交換的基因位所對應的機器號也進行交換.

3 模擬實例分析

6 × 6(6 個工件，6 台機器) FJSP的加工工序，機器選擇和加工時間矩陣表. 分別用標准遺傳演算法和本文提出的改進遺傳演算法對工件最小化最大完工時間進行優化計算，並分析優化計算結果.

遺傳演算法採用以下參數:種群規模為100，進化代數為100，交叉概率Pc = 0. 8，變異概率Pm =0. 1. 演算法運行10 次，標准遺傳演算法的最大完工時間為20，收斂代數為75 代左右;改進遺傳演算法的最大完工時間為16，收斂代數為35 代左右. 改進遺傳演算法既縮短了工件完工時間，也加快了收斂代數. 從而驗證了改進遺傳演算法的可行性

4 結論

傳統遺傳演算法在進行種群初始化時採用的大多是隨機選擇方式，而本文提出了一種新的種群初始化方法，提高了種群初始解的質量. 最後對改進遺傳演算法進行了模擬實驗，並將結果與標准遺傳演算法進行比較，結果表明了本演算法的優越性和可行性.

② PID計算機控制的演算法和實現 這個論文怎麼寫

畢業論文格式
1、論文題目：要求准確、簡練、醒目、新穎。
2、目錄：目錄是論文中主要段落的簡表。（短篇論文不必列目錄）
3、提要：是文章主要內容的摘錄，要求短、精、完整。字數少可幾十字，多不超過三百字為宜。
4、關鍵詞或主題詞：關鍵詞是從論文的題名、提要和正文中選取出來的，是對表述論文的中心內容有實質意義的詞彙。關鍵詞是用作機系統標引論文內容特徵的詞語，便於信息系統匯集，以供讀者檢索。每篇論文一般選取3-8個詞彙作為關鍵詞，另起一行，排在「提要」的左下方。
主題詞是經過規范化的詞，在確定主題詞時，要對論文進行主題，依照標引和組配規則轉換成主題詞表中的規范詞語。
5、論文正文：
（1）引言：引言又稱前言、序言和導言，用在論文的開頭。引言一般要概括地寫出作者意圖，說明選題的目的和意義, 並指出論文寫作的范圍。引言要短小精悍、緊扣主題。
〈2）論文正文：正文是論文的主體，正文應包括論點、論據、論證過程和結論。主體部分包括以下內容：
a.提出-論點；
b.分析問題-論據和論證；
c.解決問題-論證與步驟；
d.結論。
6、一篇論文的參考文獻是將論文在和寫作中可參考或引證的主要文獻資料，列於論文的末尾。參考文獻應另起一頁，標注方式按《GB7714-87文後參考文獻著錄規則》進行。
中文：標題--作者--出版物信息（版地、版者、版期）：作者--標題--出版物信息所列參考文獻的要求是：
（1）所列參考文獻應是正式出版物，以便讀者考證。
（2）所列舉的參考文獻要標明序號、著作或文章的標題、作者、出版物信息。

③ 在FPGA上快速實現MD5演算法的新方法論文

在FPGA上快速實現MD5演算法的新方法論文

摘 要 文章介紹了一種在FPGA上快速實現MD5演算法的新方法，給出了優化設計的原理、實現的具體方法及其重要模塊的設計實現方案。

關鍵詞 MD5；FPGA；Verilog語言；集成電路；關鍵路徑

1 引言

隨著電子商務和網路通信的發展，網路信息安全的重要性越來越顯著，信息加密、數字簽名、數據的完整性認證、身份驗證等成為信息安全領域的重要內容。MD5演算法本身是為數字簽名應用而設計的，隨後也應用在信息驗證技術當中。作為應用最廣泛的安全散列演算法，MD5演算法的高效實現就成為研究的需要，MD5演算法本身可以採用軟體實現，但其性能受到處理器件性能的制約不能滿足網路通信帶寬日益增長的要求，因而通過硬體實現高速MD5 運算就成為需要。

2 MD5演算法介紹

MD5 演算法可以對任何長度不超過 264二進制位的消息產生128 位的單向散列消息摘要輸出， RFC1321 標准中的MD5 演算法主要步驟如下：

在一些初始化處理後，MD5以512位分組來處理輸入文本，每一分組又劃分為16個32位子分組。演算法的輸出由四個32位分組組成，將它們級聯形成一個128位散列值。

（1）附加填充比特：填充消息使其長度恰好為一個比512位的倍數僅小64位的數。即對報文進行填充使報文的長度(比特數)與448模512同餘。填充方法是附一個1在消息後面接所要求的多個比特0。

（2）附加長度值：在其後附上64位的消息長度（填充前）。如果消息長度大於 264，僅使用該長度的低64比特。這樣，該域包含的長度值為初始長度模264 的值。

這兩步的作用是使消息長度恰好是512位的整數倍（演算法的其餘部分要求如此），同時確保不同的消息在填充後不相同。

（3）初始化寄存器：四個32位初始化變數為：

它們也被稱為鏈接變數（chaining variable）

（4）進行演算法的主循環：這一步是演算法的核心，它是一個包含四個大循環的64步函數，四個大循環結構相同，但每次使用的邏輯函數不同，每一個大循環由對512比特的16步操作組成，即每16步為一輪大循環。

每次操作如下(設 Ai+1、Bi+1 、Ci+1 、Di+1 為第 +1個時鍾周期時打入寄存器的值)：

以一下是每輪中用到的四個非線性函數（每輪一個）。

常數ti可以如下選擇：在第i步中，ti是4294967296*abs(sin(i))的整數部分，i的單位是弧度。Wi是512位消息分組中的一個，Si是每次循環移位的次數。對每次而言也是固定的常數。

（5）結果輸出：所有64步完成之後，將第64步的輸出加到四個初始化變數上作為新的初始化變數，進行下一個512比特分組的運算，直到所有分組處理完畢，單次操作圖如下：

圖1. MD5演算法單步操作圖

3 演算法優化

由上圖可以看到，硬體實現時，MD5演算法每一步操作中的關鍵路徑在於B的求取（其他三個變數都是直接傳遞），這個關鍵路徑包括了四個模 232加法運算、三輸入變數的邏輯運算、"兩個查找表運算及一個循環左移運算，而在FPGA設計中，加法運算最為耗時，四個加法運算至少需要三個加法器級聯完成，加法運算嚴重製約了整個操作的速度，可見要加快演算法運行速度就必須在簡化這一關鍵路徑上下工夫，經過觀察我們發現，在

中 對每個周期都是已知的常數，是輸入的512比特的一個32位分組，這樣，在512比特輸入初始化完成後，也可看作固定常數，

Ai是第i時鍾周期里寄存器D 的值，而 Di的值又是第i-1周期里的Ci-1 ，即Ai 的`值是第i-1周期里Ci-1的值。

若在第i周期設中間寄存器變數 ，並令

那麼在第i+1周期，

就可以表示為

操作就可以用下面幾個式子代替：

其中， Ai+1沒有參與任何運算，因此上式可以接著化簡為

這樣一來，原來一個周期內需要完成三級加法和相應的組合邏輯，現在只需要完成兩級加法和部分組合邏輯就行了，大大提高了演算法速度，只要在運算開始時加－個周期的初始化即可，簡化後的系統框圖如下：

圖2. 改進後的單步操作圖

4 結果比較

由上文中的演算法分析部分不難看出，傳統的實現方式關鍵路徑是3級32比特加法器延遲和組合邏輯的延遲，而改進的實現方式減少了一級加法器的延遲，並把組合邏輯的延遲分散到不同路徑上，因此，採用改進的實現方式大約可以將速度提高到原來的1.5倍左右。同時，為了實現數據的初始化，需要提前一個周期計算出寄存器A的值，因此整個演算法的實現需要65個周期。我們採用 VerilogHDL 描述，選擇Altera Stratix II EP2S15F672C5 FBGA晶元，在QuartusII6.0上驗證通過。由於在FPGA中，連線延時也很關鍵，而這部分延時不能像加法延時那樣通過預先計算並存儲在寄存器中來消除一部分，所以實際的MD5改進演算法與傳統型相比較，速度的提高約為1.3，資源方面由於只是增加了一個時鍾節拍，寄存器數量和組合邏輯並沒有增加，所以改進型在資源方面和傳統型相當。下表為演算法改進前後在資源、頻率、流量上的比較。

表1. 改進前後資源比較

5 結束語

由表1可見，改進型MD5演算法實現，使用的資源並沒有明顯增加，但速度的改善十分明顯，基本實現了用較少的資源得到較高速率的目標，證明了結構的正確性和合理性。實驗結果也說明，這種利用寄存器來減少加法器級聯從而減少關鍵路徑的實現方法也可用於一般的FPGA硬體設計中。

參考文獻

[1] R.Rivest. The MD5 Message-Digest Algorithm，RFC1321 1992。

[2] Jarvinen K， Tommiska M，Skytta J.Hardware implementation analysis of the MD5 hash algorithm.System Sciences，2005.HICSS』05.Proceedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:298

[3] Bruce Schneier. 應用密碼學.北京：機械工業出版社，2000：188～194

[4] William Stallings. 密碼編碼學與網路安全：原理與實踐.北京：電子工業出版社，2001: 216～222。

[5] 夏宇聞.Verilog 數字系統設計教程.航空航天大學出版社，2005