软件项目调度中改进遗传算法应用研究

薛云勇

摘  要：在信息化程度越来越高的现代社会，计算机技术应用越来越普遍。在计算机科学技术中，软件公司是衔接用户需求和程序人员对软件具体细节编程的关键环节。为了紧跟时代步伐，本文对现代软件项目中的遗传算法进行了分析研究，遗传算法是模拟自然选择和生物进化过程的一类优化算法，即进化算法（Evolutionary Algorithms，EAs）中的一种，改进遗传算法是软件项目调度的研究重点和发展方向。

关键词：遗传算法;软件工程;调度研究;项目管理

中图分类号：TP301.6;TP311.5      文献标识码：A 文章编号：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  軟件项目调度中遗传算法的产生和发展

遗传算法（Genetic Algorithms，GA）是用数字化变化来表示生物进化过程的一种计算机算法。遗传算法将自然界中的演进规律运用到计算机信息科学与工程学科中的演进算数方法。遗传算法出现、形成于20世纪50年代后期到70年代初期，在最早期是一些进行生物遗传系统模拟研究的生物学家所采用的电子计算方法，随着此方法的不断推广，人们逐渐对类似算法进行总结、更新、补充，在此过程中就有人将自然界的生物进化过程应用到计算机编码的算术设计之中，由于受当时科技发展条件的限制，人们利用自然界规律来编排算法也只形成了单独的小单元程序块，且只能进行变异操控。随着后期的发展改进和计算机科学技术的不断进步，小单元程序块之间的联系逐渐加强，并逐渐形成一个体系完备的逻辑体，最后就形成了现在计算机所使用的成熟的遗传算法。遗传算法这一计算机项目工程新名词最先是由John H. Holland提出，他的著作的出版是遗传算法发展的里程碑，其对遗传算法的发展和改进具有历史性意义，John H. Holland常被视为遗传算法问世的标志。De Jong对遗传算法（Genetic Algorithms，GA）进行了全面、系统的介绍和整理，从而使遗传算法（Genetic Algorithms，GA）在计算机信息科学中得到了认可和应用，并且使其在使用的过程中不断得到修改和完善。在上个世纪90年代之后，遗传算法（Genetic Algorithms，GA）进入高速发展阶段，我国对遗传算法的研究也是从20世纪90年代开始的[1]。在上个世纪80年代中期之前，遗传算法在计算机科学领域之中并没有得到实际性的应用，在那个时期人们对遗传算法的学习只限于算法的理论知识认知。随着计算机科学技术的成熟以及人们对遗传算法认识的深入，遗传算法在计算机程序设计中不断得到应用，其价值也得到了此领域专家的肯定。

遗传算法（Genetic Algorithms，GA）在具有操作简便、算数思想逻辑清晰优势的同时，还能有效求解NP类型的多目标的函数优化问题，因此得到诸多学科和不同研究领域专家的高度重视和广泛认可。遗传算法对于复杂问题的解决高效而迅速，所以其在软件工程项目调度问题和优化软件工程项目求解方面优势显著。

2  软件发展的背景和遗传算法在软件工程调度中的重要作用

进行软件项目调度时，求解成功率有高低之分，求解质量有好坏之分。影响软件项目调度模型工程效益的因素包括从事本项目的程序员的编码学习能力、工作人员的工作能力和经验、工作人员的加班上限、工程任务和技能匹配、技能等级难度等诸多方面[2]。软件项目调度以提高求解命中率为前提，规范处理软件工程进度和程序，通过改进、修补遗传算法模型进行优化求解。通过实验结论来证明通过优化后的遗传算法加以改进的调度模型具有更好的工程项目优化性能，使项目在工程约定期内，低成本、高质量地达到项目规划要求。遗传算法（Genetic Algorithms，GA）是进化算法的一种，同时，进化算法还包括：进化编程、进化策略、遗传编程等。遗传算法具有广泛适用性和自适应性等特点，因此算法的组合性改良、函数性改良、模式化检验、机器语言学习、智能化操控、生产的调度分配等方面得到了广泛的推广和应用，这是软件项目调度对改进遗传算法的研究热度越来越高的原因之一。

相较于传统的优化算法，遗传算法（Genetic Algori-thms，GA）优势明显：一是在算法变量上的区分，计算机中传统的优化算法不是对程序之中变量的直接改变和操作，而遗传算法的运算对象是整个编码个体，遗传算法（Genetic Algorithms，GA）此操作处理方法可以直接对结构对象整个结构进行操作，十分方便地利用遗传操作算子来模仿生物在自然界中的遗传和进化，在处理一些无数值概念问题方面具有明显的优越性，如集合、序列、矩阵问题等。

3  软件项目调度中遗传算法的性能改进

遗传算法以对生物的进化机制进行模拟为基本思想，由达尔文的物竞天择，适者生存的自然生物进化论演变来的遗传算法的基本步骤，包括编码、选择、交叉、变异、初始数据群体的生成以及适应性评估的检测。常用的选择算法有比例选择、最佳选择、竞赛选择，遗传算法最重要、最常用的操作是交叉操作，交叉操作又分为单个交叉，对点交叉，多个交叉。单个交叉是指对编码串中随机的一个交叉点进行交换，对点交叉是指交换编码串中随机选择的两个编码串，而多个交叉是指对随机选择的多个交叉点进行编码串交换。通过交叉操作会产生新的运算方式，新的运算方式继承了交叉操作前算法的优秀特性。遗传算法中的变异是指对进行变异的个体随机选择变异位进行变异，遗传算法中变异发生的概率极低。变异分为实值变异、二进制变异。

20世紀70年代中期，美国提出软件工程的软件项目管理，当时美国国防部专门研究的软件不能按时提交，通过对此项目进行调查发现，不能按时完成的项目中，70%是因为管理不善引起的，而非技术原因引起的软件开发预算超支和软件开发质量达不到用户要求[3]。于是软件开发者开始重视软件开发各项工作的管理。20世纪90年代中期，软件研发项目管理不善导致了诸多问题，如软件工程在约定时间内无法完成，软件开发的预算不能把控以及开发出的软件达不到用户预期要求，软件工程的后期无法维护等。这些问题的存在造成了极大的经济损失，美国国防部对因软件工程失误造成的损失进行了统计，结果显示，美国在软件工程项目中的损失高达810亿美元。在实际的软件工程项目中，软件危机对世界各国造成的损失远远超出810亿美元。因此，软件危机的解决方法研究得到了世界各国的高度关注，北大西洋公约组织于德国召开的以软件危机为主题的国际会议，针对如何降低软件危机带来的损失进行了一次学术探讨，此次会议第一次提出了解决软件危机的工程方案名称：软件工程。从此以后，软件工程成为了一门新的计算机科学学科。

和其他项目管理相比，软件项目管理具有特殊性。如计算机硬件的生产是在生产流程和生产技术指导下进行，软件工程的开发基于算术逻辑思维，因此，在软件开发的过程中，软件开发的开发情况和发展方向难以估量。对于生产的软件的评价标准为相对性评价，软件开发工作具有较高的延展性和创造性，这就容易导致软件开发过程难以把控。例如，由数千个程序员对Windows操作系统进行修改、编写，如果没有完善的管理系统，则庞大复杂系统的正常运行以及所生产的软件质量难以保障。

4  软件项目调度中遗传算法的存在优势及模块的调度

遗传算法的作用对象是结构而非传统算法的具体变量，因此遗传算法具有简便、快速以及错误率低的特点。遗传算直接操作的对象包括集合、序列、矩阵、数列、链表等结构。在不同于传统检索的肯定搜索规则，遗传算法检索时使用的是以概率变化为依据的检索方式。因此，其对联通性，凹凸性等没有特别的要求，遗传算法的辅助信息也较为简单，它的适用范围相对于其它算法而言更广[4]。遗传算法在检索过程中采用并行处理方式，这就避免了算法陷入局部最优解的困境当中，算法的运行效率也大大提高。

随着社会的发展，软件工程存在的问题也发生了变化。软件工程调度中的任务调度问题，是任务调度模型在软件项目调度中急需解决的问题。一般用TPG来描述软件工程任务调度模型中模块与模块任务之间的存在的内在与外在关系。项目中模块的操作执行需要技能集合，完成模块任务需要相当的工作量，任务之间有前驱后继关系，在满足以上要求的前提之下，还要考虑到降低成本和缩短员工的工作时间。

5  结  论

随着我国信息行业的快速发展，在利用遗传算法解决软件项目调度问题时，要严格遵循遗传算法的使用步骤和规则，了解软件项目设计流程，并选择适合的遗传算法来解决问题，降低软件工程项目开发过程成本和缩短时间。

参考文献：

[1] 高世刚.基于云遗传算法的软件项目资源调度研究 [D].武汉：武汉科技大学，2010.

[2] 范增辉，方伟.改进遗传算法在软件项目调度中的研究 [J].计算机应用与软件，2016，33（12）：34-39+48.

[3] 孔令飞.遗传算法在软件项目调度中的应用 [D].长春：吉林大学，2008.

[4] 张搴林，曾诚.基于改进遗传算法的软件项目人力资源调度研究 [J].中国新通信，2013，15（2）：87.