遗传算法的改进与应用

第５Ｏ卷第２期　２０１０年２月　电讯技术　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｏ１．５０　Ｎｏ．２　Ｆｅｂ．２０ｌ０　

文章编号：１００１—８９３Ｘ（２０１０）０２—００６３—０６　

改进型遗传算法及其在代数码书搜索中的应用　

宋铁成，张德民，张天骐，宋　吉吉　

（重庆邮电大学信号与信息处理重庆市重点实验室，重庆４０００６５）　

摘要：针对基本遗传算法（ＳＧＡ）易于早熟收敛、全局优化速度缓慢、局部搜索能力弱等缺点，提出　

一种改进型遗传算法（ＩＧＡ），并将其应用于ＡＣＥＬＰ语音编码器的代数码书搜索中。改进型算法使　

用了经验式随机方法初始化种群，设计了与进化代数相关的自适应交叉和变异概率，采取了移民策　

略维持群体多样性，最后引入了局部爬山搜索机制。将ＩＧＡ应用于ＩＴＵ—Ｔ　Ｇ．７２９Ａ语音编码器，仿　

真结果表明了该算法的可行性和有效性，从而为代数码书搜索方法的研究提供了新思路。　

关键词：语音编码；遗传算法；代数码书；搜索算法　

中图分类号：ＴＮ９１２．３　文献标识码：Ａ　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—８９３ｘ．２０１０．０２．０１３　

Ｉｍｐｒｏｖｅｄ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎ　

ｉｎ　Ａｌｇｅｂｒａｉｃ　Ｃｏｄｅｂｏｏｋ　Ｓｅａｒｃｈ　

ＳＯＮＧ　Ｔｉｅ—ｃｈｅｎｇ，ＺＨＡＮＧ　Ｄｅ—ｍｉｎ，ＺＨＡＮＧ　Ｔｉａｎ—ｑｉ，ＳＯＮＧ　Ｚｈｅ　

（Ｃｈｏｎｇｑｉｎｇ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｓｉｇｎａｌ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ，Ｃｈｏｎｇｑｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｐｏｓｔｓ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｃｈｏｎｇｑｉｎｇ　４０００６５，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｃｏｎｃｅｒｎｉｎｇ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｓｉｍｐｌｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ（ＳＧＡ），ｓｕｃｈ　ａｓ　ｐｒｅｍａｔｕｒｅ　ｃｏｎｖｅｒｇｅｎｃｅ，　

遗传算法理论及其应用发展

摘 要: 首先介绍了遗传算法的基本工作原理和主要特点; 然后讨论了近年来从遗传算子、控制参数等方面对遗传算法的发展,并对遗传算法在国内外的研究进展和新的应用领域进行了讨论; 最后评述了遗传算法未来的研究方向和主要研究内容。

关键词: 遗传算法; 遗传算子; 控制参数; 组合优化

遗传算法[1] (Genetic Algorithms，简称GA )是由美国Michigan 大学的Holland教授于1975年首先提出的。它源于达尔文的进化论、孟德尔的群体遗传学说和魏茨曼的物种选择学说; 其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。从公开发表的论文看, 我国首先开始研究应用遗传算法的有赵改善和华中理工大学的师汉民等人。遗传算法最早应用于一维地震波形反演中, 其特点是处理的对象是参数的编码集而不是问题参数本身, 搜索过程既不受优化函数联系性的约束, 也不要求优化函数可导, 具有较好的全局搜索能力; 算法的基本思想简单, 运行方式和实现步骤规范, 具有全局并行搜索、简单通用、鲁棒性强等优点, 但其局部搜索能力差, 容易出现早熟现象。自1985年起, 国际遗传算法会议每两年召开一次, 在欧洲, 从1990年开始每隔一年也举办一次类似的会议。1993年, 国际上第一本以遗传算法和进化计算为核心内容的学术期刊5 Evolutionary Com putation6 (进化计算) 在MIT 创刊; 1994年, 在美国奥兰多召开的IEEE World Congress on Computation Intelligence ( IEEE全球计算智能大会)上, 进化计算与模糊逻辑、神经网络一起统称为计算智能; 1997年, 5 IEEE

Transaction son Evolutionary Computation6创刊。这些刊物及时全面地报道了近年来遗传算法的最新研究成果。目前, 与遗传算法有关的学术会议包括ICGA、PPSN、ICEC、ANN&GA、EP、FOGA、COGANN、EC、GP、SEAL等。作为一种自适应的全局优化算法，遗传算法以概率搜索为根本导向。它的特点如下。

改进的遗传算法在智能组卷中的应用研究

摘 要：该文提出分段二进制编码，对遗传算法的选择过程进行改进，并采用独立题型题库存放的方法来求解组卷问题。实验结果表明，新方法的组卷成功率和收敛速度都得到明显提高，较好的克服了早熟收敛现象，组卷质量明显提高。

关键词：改进遗传算法 智能组卷 数学模型

中图分类号：tp18 文献标识码：a 文章编号：1674-098x（2013）03（c）-00-02

随着我国信息技术的飞速发展，计算机在教学领域有了广泛应用，用计算机进行网上考试已经成为一种趋势，因此怎么才能快速从试题库中选出一份满足用户各项要求的试卷成为一个问题。目前常用的组卷方法有随机选题法、回溯试探法、遗传算法三种，而传统的遗传算法主要通过交叉算子繁衍后代，容易造成早熟收敛现象。因此目前已经有很多人为提高组卷效率，将遗传算法的算子改进后再应用到智能组卷系统中。该文为加快算法的收敛速度，将遗传算法的算子进行了改进，并应用于智能组卷系统中。

1 智能组卷的数学模型

将智能组卷问题视为从一定题量的数据库中抽取满足组卷要求的一组试题组合，就能够将组卷问题转化为一个多重约束目标问题。求解一份由m道试题且每道试题有n个属性的试卷，相即构建一个m×n的目标矩阵s。

s= 试题常有如下属性：⑴难度系数a1、⑵分数a2、⑶能力层次a3、⑷预计答题时间a4、⑸题型a5、⑹已出题次数a6。目标矩阵应满足以下约束条件：

⑴试卷难度系数=1-/总分（由用户给定）；

⑵试卷总分=（一般为100分）；

⑶答题总时间=（由用户给定）；

⑷（为第p能力层次题分），能力层次类型和所占分数由用户给定，即能力层次约束，其中

⑸题型题分=，第j题型题分，其中：c={，j为题型要求约束。题型分别为：判断、单选、填空、多选等，具体组卷题型类别和每题分值由用户给定。

组卷过程中，试题要根据数学模型中给出的各项指标来决定，即表示第i道试题中的第j项指标，其中i=1，2，…，m；j=1，2，…，n。

Ｅｘａｍｐｌｅ　ｏｆ　Ａｐｐｌｉｃａｔｉｏｎ　

改进遗传算法在网格任务调度中的应用　

卜艳萍　

（上海交通大学技术学院，上海２０１　１０１）　

摘要：为了提高遗传算法的搜索性能，同时满足网格资源的优化分配，提出了一种带过滤机制　

的遗传算法，使其适用于网格任务调度问题的优化处理。仿真研究表明该算法更符合网格调度的复　

杂环境，能得到较短的任务执行时间和较好的负载均衡性。　

关键词：遗传算法；网格；任务调度；完成时间　

中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１６７４—７７２０（２０１０）１８－００９５－０４　

Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｇｒｉｄ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　

ＢＵ　Ｙａｎ　Ｐｉｎｇ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｇｈａｉ　Ｊｉａｏｔｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０１　１０１，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｅａｒｃｈｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ　ｆｏｒ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｏｐｔｉｍｉｚｅ　ｔｈｅ　ｇａｄ　ｒｅｓｏｕｒｃｅｓ　ａｌｌｏｃａｔｉｏｎ，ａｎ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｆｉｌｔｒａｔｉｎｇ　ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｔｏ　ｔｈｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｇａｄ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍｓ．Ｂｙ　ｕｔｉｌｉｚｉｎｇ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ，ｓｈｏｒｔｅｒ　

ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ａｎｄ　ｂｅｔｔｅｒ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｌｏａｄ　ｂａｌａｎｃｉｎｇ　ｃａｎ　ｂｅ　ｇａｉｎｅｄ　ｖｉａ　ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｓｔｕｄｉｅｓ，ｅｓｐｅｃｉａｌｌｙ　ｉｎ　ｇａｄ　ｓｃｈｅｄｕｌｉｎｇ　ｅｎｖｉ－　

ｒｏｎｍｅｎｔｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｇａｄ；ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ；ｍａｋｅｓｐａｎ