怎么写算法改进的小论文

① 详谈改进的遗传算法求解柔性作业车间调度问题论文

详谈改进的遗传算法求解柔性作业车间调度问题论文

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