遗传算法的综述

2025-01-24

遗传算法的综述（共9篇）

遗传算法的综述篇1

0 引言

遗传算法 (Genetic Algorithm, 简称GA) 起源于对生物系统所进行的计算机模拟研究。是由美国Michi遗传算法n大学的John Holland教授创建的, 并于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and artificial Systems》。它提出的基础是达尔文的进化论、魏慈曼的物种选择学说和孟德尔的群体遗传学说:其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。遗传算法以其具有并行搜索、简单通用、鲁棒性强等优点, 受到国内外学者的关注。自1985年以来, 国际上已召开了多次遗传算法学术会议和研讨会, 并组织了国际遗传算法学会。

1 遗传算法的基本原理

在自然界中, 由于同一个生物群体中各个体之间也存在差异, 且对所处环境有的适应和生存能力也参差不齐, 遵照进化论所提出的自然界生物进化的基本原则:适者生存、优胜劣汰, 自然界将淘汰那些适应能力较差的个体。但是通过交配继承了父本优秀的染色体和遗传基因的, 或者通过染色体核基因的重新组合产生的生物的生命力往往会更强, 适应能力也更强。在自然界中, 基因会发生突变, 染色体核基因的重组是无法控制的, 但这种无法控制的, 小概率的变异, 也可能产生新基因和生命力更强的新个体。在此基础上, 遗传算法真实的模拟自然界生物进化机制进行对问题的最优化搜索。遗传算法是建立在自然选择和种群遗传学基础上的随机迭代和进化, 具有广泛适用性的搜索方法, 同时具有很强的全局优化搜索能力。对于某个给定的优化问题, 目标函数为:

要求 (X0, Y0, Z0) 使得H为极大值和极小值, 以适应优化的需要。此外, Ω是 (X, Y, Z……) 的定义域, H为实数, f为解空间 (X, Y, Z……) ∈Ω到实数域H∈R的一种映射。遗传算法要根据目标函数H设定一个适应性函数f, 用以判断某个样本的优劣程度。遗传算法的基本步骤如下:

(1) 编码:定义问题的解空间到染色体编码空间的映射, 一般是用二进制将解空间编码成由0和1组成的有限长度字符串。一般一个候选解 (个体) 用一串符号表示。

(2) 初始化种群:在一定的限制条件下初始化种群, 该种群的解空间的一个子空间。算法将从初始化种群开始模拟优胜劣汰的选择过程, 最后选择出优秀的群体和个体。

(3) 设计适应度函数:将种群中的每一个染色体解码成适于计算机适应度函数的形式, 并计算其数值。设计适应度函数的主要方法是将问题的目标函数转换成合适的适应度函数。

(4) 选择:根据适应度大小选择优秀个体繁殖下一代, 适应度越高, 则被选中的概率也越大。选择是遗传算法的关键, 它体现了自然界中适者生存的思想。

(5) 交叉:随机选择两个用于繁殖下一代的个体的相同位置, 在选中的位置进行交换。

(6) 变异:对某个串中的某一位进行取反操作。变异模拟了自然界中偶然基因突变现象。

从步骤四开始重复进行, 知道满足某一性能指标或者规定的遗传代数。

步骤1、2和3是实际应用中关键, 步骤4、5和6进行三种基本基因操作。对新生成一代群体进行重复评价、选择、交叉和变异, 如此循环往复, 使得群体中最优个体的适应度和群体的平均适应度不断提高, 直到最优个体的适应度达到某个界限或者最优个体的适应度和平均适应度不能再提高。

2 遗传算法的特点

遗传算法继承了进化计算的特征之外, 也有其自身的特点:

(1) 遗传算法不是直接作用在参数变量集上, 而是在求解问题的决定因素和控制参数的编码 (即染色体的0、1编码) 上进行操作, 从中找到适应值较高的子串。而且遗传算法不受约束条件的限制。

(2) 遗传算法并不是从单个点出发执行算法, 而是从一个点的群体开始, 这样就可以提高算法的效率和程序的运行速率, 也大大减少了陷入局部最优解的可能性。

(3) 遗传算法利用了适应值的信息, 适应值是根据不同问题设计所得, 针对的是这个问题, 从而减少了其他辅助信息的导入, 即只需要对象函数和编码串。因此, 遗传算法几乎可以处理任何问题。

(4) 遗传算法利用概率转移规则, 而不是确定性的规定。遗传算法采用的概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动。

(5) 遗传算法在搜索过程中不容易陷入局部最优, 即使在所定义的适应度函数是不连续的非规则的或有噪声的情况下, 也能以很大的概率找到全局最优解。

(6) 遗传算法采用自然进化机制来表现现实复杂的现象, 能够快速可靠地解决非常困难的问题。

(7) 遗传算法具有固有的并行性, 具有并行计算的能力。

(8) 遗传算法具有可扩展性, 易于同别的技术混合、结合使用。

3 遗传算法的应用

遗传算法是多学科结合与渗透的产物, 已经发展成为一种自组织、自适应的综合技术。其提供了一种解决复杂系统优化问题的通用框架, 但不是没用固定的方法, 它不依赖于问题的具体领域, 所以广泛应用于很多学科。

3.1 函数优化

函数优化是遗传算法的一个经典应用领域, 也是对遗传算法进行性能评价的常用算例。很多学者构造出了各种各样的复杂形式的测试函数, 有连续函数也有离散函数, 有凸函数也有凹函数, 有确定函数也有随机函数, 有单峰值函数也有多峰值函数等。用这些几何性质各具特色的函数来评价遗传算法的性能, 更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题, 用其他优化方法较难求解, 而遗传算法却可以方便地得到较好的结果。

3.2 组合优化

随着问题规模的增大, 组合优化问题的搜索空间也急剧扩大。有时在现有的的计机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题, 学者们已意识到应把主要精力放在寻求其满意解上, 二不是一定要寻找精确的最优解, 而遗传算法是寻求这种满意解的最佳工具之一。有实践证明, 遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形有划分问题等各种具有NP难度的问题上得到成功应用。

3.3 生产调度问题

在许多情况下所建立起来的数学模型难以精确求解, 即使经过了一些简化之后可以进行求解, 也会因为简化太多而使得求解结果与实际相差甚远。因此, 目前在解决生产中的调度问题时还是主要依靠一些经验。1985年Davis首次将遗传算法引入到调度问题。从此在调度问题的解决过程中, 遗传算法使得调度的总流程时间, 平均流程时间等大大降低, 提高了生产的效率。

3.4 图像处理

图像处理是计算机视觉中的一个重要的研究领域, 其前景十分乐观。但在图像处理的扫描、特征提取、图像分割等过程中不可避免的会产生误差。而遗传算法则可以很好的解决这些问题。在图像分割的时候可以利用遗传算法来发现最优解从而帮助确定分割阈值;利用遗传算法在图像增强过程中寻找控制参数的最优解或者是近似最优解;利用遗传算法对图像进行特征提取再对所提取的特征进行优化, 从而提高图像的识别率等。

3.5 自动化控制

随着现代技术和科学技术的不断发展, 人工成本的不断提高, 机器的自动化要求越来越高, 工程师所要考虑的是选择合适的控制结构, 然后对其参数进行一定的优化使得满足特定的实际性能要求。遗传算法具有鲁棒性和广泛适用性的全局优化方法, 能更好的为其控制器降价, 更好的控制机器人手臂, 优化机器人手臂的运动轨迹。遗传算法的优化功能在越来越多的机器自动化领域得到关注。

4 遗传算法存在的问题

随着学科技术的迅速发展, 遗传算法也应用到更多的领域。由于遗传算法来源于进化论和群体遗传学, 缺乏严格的数学基础, 收敛性证明比较困难, 虽然可以利用马尔科夫链的性质证明在保留最优值情况下, 遗传算法可以收敛到全局最优解, 但是对其收敛速率估计是当前需要深入研究和讨论的问题。因为它能从理论上对遗传算法的任何修正形式提供评判标准, 指明改进算法性能的正确方向。另外, 利用马尔科夫链分析对遗传算法的具体应用和参数设计所提供的指导信息非常少。如何选择遗传算法的参数, 才能得到最优结果, 到目前还没有理论指导。以上这两个方面还需要需找更有效的分析手段和严格的数学证明。

5 结束语

遗传算法不是一种单纯的优化算法, 而是一种以进化思想为基础的全新的一般方法论, 是一种解决问题的方法。经过多年的研究和发展, 遗传算法在越来越多的领域展现出它的优势, 不论是基础理论研究、算法设计还是实际应用。应用研究是遗传算法的主要方向, 开发遗传算法的商业软件、开拓更广泛的遗传算法应用领域是今后应用研究的主要任务。

摘要：遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术, 已广泛应用与计算机科学、人工智能、信息技术及工程实践。本文介绍遗传算法的基本工作原理和特点, 讨论存在问题, 分析遗传算法的研究现状。

关键词：遗传算法,优化算法,收敛性

参考文献

[1]Holland J.H.Adaptation in Natural and Artificial Systems[M].Ann Arbor:University of Michigan Press, 1975.

[2]边霞, 米良.遗传算法理论及其应用研究进展[J].计算机应用研究, 2010, 27 (7) .

[3]王东生.遗传算法及其应用[M].人民邮电出版社, 1996.

[4]周国华.遗传算法及其在生产调度中的应用[J].西南交通大学学报:社会科学版, 2000, 1 (2) .

[5]田莹, 苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报, 2007, 12 (3) .

[6]马岚, 张燕东.多目标遗传算法及其在自动控制系统设计中的应用[J].系统工程与电子技术, 1997.

遗传算法的综述篇2

遗传算法中的哲学思想

遗传算法不仅仅是一种算法,它本身包含着一种创新思维,体现出学科之间交互所发生的一些突破,它不但在计算机理论上具有极大的.理论创新,而且在哲学上也具有丰富的思想.

作者：游贵荣魏仁兴作者单位：福建商业高等专科学校计算机系、马列部,福建,福州,350012刊名：福建商业高等专科学校学报英文刊名：JOURNAL OF FUJIAN COMMERCIAL COLLEGE年，卷(期)：“”(1)分类号：B815关键词：遗传算法相互作用突变

遗传算法的综述篇3

1 遗传算法在自动控制领域中的应用

在自动控制领域中, 遗传算法可以分为离线设计分析以及在线自适应调节两大类。其中离线设计分析又可以分为两类, 即直接设计与间接设计法。遗传算法在直接设计法当中可以作为一个搜索与优化引擎, 而在间接设计法当中, 遗传算法可以为其提供一个比较优化的参数如加权函数矩阵。遗传算法在线应用情况一般分为被用来当作学习机制辨识未知的特征参数和直接优化控制器的参数这两种情况, 这个时候可以运用传统的辨识方式去对系统的状态进行估计, 以此构成遗传算法作为自适应优化机制的自适应控制器。

1.1 系统辨识

在自动控制领域中, 系统辨识是设计的基础。传统的辨识方式通常都是先把模型结构给确定好, 再把模型的参数给确定好, 在确定这些系统结构的时候往往要具备许多先验知识, 如果结构出现不理想状态, 就必须要对结构重新进行确定, 然后对参数进行辨识, 这就使得系统辨识比较复杂。而遗传算法的运用就改变了这一复杂化程度, 它可以是连续的, 能够对参数空间的不同区域进行搜索, 并把这些搜索的方向指向更加优解的区域。遗传算法可以对空间中的多个点进行同时处理和搜索, 增加了全局优解的效果。同时, 遗传算法在模型的线性化与降价处理中应用的也比较广泛, 它可以对全局最优的名义模型和加性或乘性不确定性误差界函数进行同时辨识, 对那些连续以及离散系统进行处理, 在控制基因中引入遗传算法并作为结构开关, 可以对模型的阶次以及参数进行同时优化, 既适用于时域问题又适用于频域模型。

1.2 非线性系统

在自动控制领域设计中, 很多控制问题可以包含在优化的框架之内。一般情况下, 这种优化任务要在一个多维空间当中对若干个参数进行同时确定, 受限于实际问题, 这些参数通常带有比较严格的约束以及非线性, 而且指标函数不仅不能够连续而且也不可微, 不一样的参数组合有可能得到一个相同的控制作用。这时运用传统优化的方式很容易对初始值的选取感到敏感, 从而陷入附近的局部极值。遗传算法就给非线性系统的有效控制找到了良好途径, 因为遗传算法不需要指标函数的微分, 在设计自动化方法时, 可以对实际系统的多个性能要求进行考虑, 并且可以为非线性对象的线性控制器进行直接设计, 而不用将对象线性化, 很多实践都能够证明遗传算法在自动控制系统设计中有一个非常有效且合理的方法。

1.3 神经网络

近几年来, 遗传算法在神经网络优化中使用的越来越广泛, 这也是当前非常重要的应用方向。神经网络有着强大的棒性与容错性、大规模的行性与能学习性、比较复杂的非线性等优势, 使其在自动控制领域中引起了广泛关注, 对其应用的研究也非常活跃。在自动控制领域中, 神经网络运用最多的就是层前馈神经网络模型, 这种模型有着非常广的输入以及输出映射能力, 然而因为这种模型是运用的反向传播算法, 这种算法要在很长时间才能接受, 并且会遇到一些局部极小的问题。当前, 用遗传算法对神经网络进行优化可以分为三个方面, 即对网络结构进行优化、对权系数进行优化以及对结构和参数进行同时优化。用遗传算法进行模糊神经网络权值的优化, 这在许多文献资料中都有研究, 依照仿真结构来进行表明, 运用遗传算法对神经网络控制器进行学习, 可以让神经网络的映射能力更加广泛以及遗传算法更加快速收敛。

2 对遗传算法在自动控制领域应用的展望

随着科学技术的不断提升, 遗传算法得到了迅速发展, 并广泛应用于各个领域当中。但是遗传算法还有许多有待解决的问题, 这些问题有:算法存在早熟;收敛速度比较低, 尤其是对用用到一些高维且复杂程度的问题中这种情况表现的更加明显;遗传算法本身的参数选取存在着许多困难。当前, 遗传算法在自动控制领域中的应用大多数还处在仿真研究的阶段当中, 实际的应用相对比较少, 怎样依照自动控制系统的特点来对适用于自动控制系统分析与设计的遗传算法进行选择是以后要重点研究的内容, 这就要求广大设计者要充分理解、熟悉和掌握实际工程中的问题和控制理论;要有效合理地进行编码以组成染色体以及有效解决多目标优化问题。

摘要：当前, 许多控制领域问题, 当考虑到系统优化、自适应、自学习以及自组织等方面的要求时, 多存在很多常规方法难以奏效的困难。而遗传算法在自动控制领域中的应用已经得到了良好效果。如遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器以及运用遗传算法进行人工神经网络的结构优化设计和权值学习等都显示出了遗传算法在自动控制领域中应用的可能性。本文就对遗传算法在自动控制领域中的应用做一些探讨。

关键词：遗传算法,自动控制,应用综述

参考文献

[1]王博岩, 卢肖, 陈洁, 张燕平.基于精英遗传算法的GSM网络频点优化设计[J].计算机技术与发展, 2013 (02) .

[2]梁雨生, 李向波.基于遗传算法的装配线平衡问题研究[J].价值工程, 2013 (05) .

[3]解庆, 赵小强.遗传算法编码策略研究[J].甘肃科技, 2013 (02) .

气动优化设计中的遗传算法研究篇4

气动优化设计中的遗传算法研究

建立了以实数编码技术为基础的多种遗传算法模型。利用这些模型来研究复制、重组和变异三种基本的遗传操作对气动优化设计的优化质量和效率产生的影响，在此基础上研究群体规模、最大进化代数和遗传概率等遗传控制参数对优化质量和优化效率的影响，期望对应用遗传算法的`气动优化设计提供一些有益的参考。

作者：王晓鹏 WANG Xiao-peng 作者单位：西北工业大学,刊名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA年，卷(期)：19(2)分类号：V211.3关键词：遗传算法气动优化设计实数编码技术

遗传算法的综述篇5

多目标最优化是一门迅速发展起来的学科,是最优化的一个重要分支,它主要研究在某种意义下多个数值目标的同时最优化问题[1],吸引了不少学者的关注。在现实生活中,人类改造自然的方案规划与设计过程在总体上都反映了“最大化效益,最小化成本”这一基本优化原则,在合作对策问题中如何求解最优策略以获得共赢目标,在非合作对策问题中如何使自己的利益实现最大化,使对方的受益最小化,以及控制工程中的稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问题等,实际上都是多目标的优化问题,因此多目标优化问题在现实世界中随处可见。

多目标优化是最优化领域的一个重要的研究方向,因为科学研究和工程实践中许多优化问题都可归结为一个多目标优化问题。多目标优化问题起源于许多实际复杂系统的设计、建模和规划。这些系统所在的领域包括工业制造、城市运输、资本预算、水库管理、能量分配、后勤补给、网络通信等等,可以说多目标优化问题无处不有、无处不在。

2 多目标优化模型

多目标优化问题(Muliti-objective Optimization Problem,MOP),又称多准则优化问题(Multicriteria Optimization Problem),多性能优化问题(Multi-performance Optimization Problem)或向量优化问题(Vector Optimization Problem)。

一般的多目标优化问题(MOP)由一组目标函数和相关的一些约束组成,可作如下数学描述:

其中X=(X1,X2,…,Xn)T是Rn空间的n维向量,称X所在的空间D为问题的决策空间,fi(X)(i=1,2,…,m)为问题子目标函数,它们之间是相互冲突的,即不埚X∈Ω使(f1(X),f2(X),…,fm(X))在X处同时取最小值,m维向量(f1(X),f2(X),…,fm(X))所在的空间称为问题的目标空间,gi(X)≤0(i=1,2,…,p)为约束函数。

多目标优化问题的本质是在很多情况下,各个子目标可能是相互冲突的,一个子目标的改善有可能引起另一个子目标性能的降低,也就是说,要使多个子目标同时达到最优是不可能的,而且只能在他们中间进行协调和折中处理,使各个子目标函数尽可能达到最优。法国经济学家V.Pareto(1848-1923)最早研究了经济学领域内的多目标优化问题,提出了Pareto解集。多目标优化问题的Pareto最优解仅仅是一个可以接受的“不坏”的解,并且通常一个多目标问题大多会具有很多个Pareto最优解。在实际应用问题中,必须根据对问题的了解程度和决策人员的个人偏好,从Pareto最优解集合中挑选一个或一些解作为多目标优化问题的最优解。所以,求解多目标优化问题的首要步骤和关键问题就是求解多目标优化问题的所有最优解。

3 传统的优化方法

绝大多数传统的多目标优化方法是将多个目标通过某种技术转换为一个目标的优化问题,然后再借助数学规划工具来求解。常见的传统优化方法有:

(1)加权求和法(Weighted Sum Method)

这种方法由Zadeh首先提出,该方法就是将多目标优化中的各个目标函数加权(即乘以一个用户自定义的权值)然后求和,将其转换为单目标优化问题进行求解。

利用加权求和可以将多目标优化转化为以下形式:

通过选取不同的权重组合,可以获得不同的Pareto最优解。这也是最为简单有效的一种求解多目标优化问题的经典方法,而且对与Pareto最优前端为凸的多目标优化问题,这种方法可以保证获得Pareto最优解。但其缺点也很明显,权重的选取与各个目标的相对重要程度有很大关系。此外,在搜索空间非凸时,很难在Pareto最优前端的非凸部分上求得解。

(2)ε-约束法(ε-Constraint Method)

ε-约束法是由Marglin[2]和Haimes[3]等人于1971年提出的,其原理是将某个目标函数作为优化目标,而约束其他目标函数的方法来求解多目标优化问题,模型如下:

εi作为上界可在优化过程中取不同的值,以便搜索到多个Pareto最优解,记Xf为可行解集合。通过这种方式将多目标优化问题转换为单目标优化问题,然后通过一般的数学规划方法或者模拟退火等方法进行求解。

(3)最小-最大法(Min-Max Approach)

最小最大法起源于博弈论法,是为求解有冲突的目标函数而设计的。这种方法的线性模型由Jutler和Solich提出[4],后由Osyczka和Rao进一步发展[5],是通过最小化各个目标函数值与预设目标值之间的最大偏移量来寻求问题的最优解。

4 多目标遗传算法

遗传算法GA(Genetic Algorithm)是受生物学进化学说和遗传学理论的启发而发展起来的,是一类模拟自然生物进化过程与机制求解问题的自组织与自适应的人工智能技术,是一种借鉴生物界自然选择和自然遗传机制的随机的搜索算法,由Holland教授于1975年提出[6]。Goldberg总结了一种统一的最基本的遗传算法,称为基本遗传算法(Simple Genetic Algorithms,SGA)。只使用基本的遗传算子:选择算子、交叉算子和变异算子。其遗传进化过程简单,容易理解,是其他遗传算法的雏形和基础。

常用的几种多目标遗传算法:

(1)并列选择法

Schaffer提出的“向量评估多目标遗传算法”是一种非Pareto方法。此方法先将种群中全部个体按子目标函数的数目均等分成若干个子种群,对各子群体分配一个子目标函数,各子目标函数在其相应的子群体中独立进行选择操作后,再组成一新的子种群,将所有生成的子种群合并成完整群体再进行交叉和变异操作,如此循环,最终求得问题的Pareto最优解。

(2)非劣分层遗传算法(NSGA)

Srinivas和Deb于1994年提出的非劣分层遗传算法(Non-dominated Sorting Genetic Algorithm)也是一种基于Pareto最优概念的多目标演化算法。首先,找出当代种群中的非劣解并分配最高序号(如零级),赋给该层非劣解集与当前种群规模成比例的总体适应值。为了保持解的多样性,所有该层非劣解基于决策向量空间距离共享此总体适应值。此后,该层非劣解集将不予考虑。然后,开始下一层非劣解集的搜索,在该层得到的非劣解集称为第二层,分配排列序号(如一级),并赋给与该层种群规模(除去以上各层已被赋予适应度的非劣解)成比例的总体适应值,同样,必须在该层非劣解集中实行适应值共享。如此重复直到当前种群中最后一个个体被赋予适应度值。

在前面的研究基础上,Deb等人于2002年又提出了一种非劣分层选择法2(NSGA-II)[7],这种方法的主要思想是对种群中的个体按Pareto进行排序,按照序值从小到大选择个体,若某些个体具有相同的序值,则偏好于那些位于目标空间中稀疏区域的个体。

(3)基于目标加权法的遗传算法

其基本思想是给问题中的每一个目标向量一个权重,将多有目标分量乘上各自相应的权重系数后再加和,合起来构成一个新的目标函数,将其转化成一个单目标优化方法求解。

若以这个线性加权和作为多目标优化问题的评价函数,则多目标优化问题可以转化为单目标优化问题。权重系数变化方法是在这个评价函数的基础上,对每个个体去不同的权重系数,就可以利用通常的遗传算法来求解多目标优化问题的多个pareto最优解。

(4)多目标粒子群算法(MOPSO)

粒子群优化算法(Particle Swarm Optimization,PSO)是一种进化计算技术,由美国学者Eberhart和kennedy于1995年提出,但直到2002年它才被逐渐应用到多目标优化问题中。PSO初始化为一随机粒子种群,然后随着迭代演化逐步找到最优解。在每次迭代中,粒子通过跟踪两个“极值”来更新自己,一个是粒子本身所找到的个体极值p Best,另一个是该粒子所属邻居范围内所有粒子找出的全局极值q Best。MOPSO与求解单目标的PSO相比,唯一的区别就是不能直接确定全局极值q Best,按照pareto支配关系从该粒子的当前位置和历史最优位置中选取较优者作为当前个体极值,若无支配关系,则从两者中随机选取一个。

(5)微遗传算法(Micro-Genetic Algorithm,Micro-GA)

Micro-GA是由Coello和Toscano Pulido于2001年提出的,是一种包含小的种群和重新初始化过程的遗传算法GA,其过程如下:首先,产生随机的种群,并注入种群内存,种群内存分为可替代和不可替代两部分。不可替代部分在整个运行过程中保持不变,提供算法所需要的多样性;可替代部分则随算法的运行而变化。在每一轮运行开始,Micro-GA的种群从种群内存的两部分选择个体,包含随机生成的个体(不可替代部分)和进化个体(可替代部分);Micro-GA使用传统的遗传操作;其后,从最终的种群选择两个非劣向量,与外部种群中的向量比较,若与外部种群的向量比较,任何一个都保持非劣,则将其注入外部种群,并从外部种群中删除所有被它支配的个体。

5 传统方法和遗传算法比较

尽管遗传算法的理论基础还不尽完善,但遗传算法已经很广泛的应用于多目标问题的求解上,并且取得了不错的效果。相比其他算法,遗传算法具有适应性和通用性、隐并行性、扩展性这三个独特的特点。但是它还是不能很好的解释遗传算法的早熟问题和欺骗问题,缺少完整的收敛性证明等。理论研究比较滞后,参数设置比较困难,解决约束优化问题还缺乏有效的手段,易早熟,而且计算量相对于传统方法要大的多,即使是使用遗传算法解决多目标优化问题,目前的多目标进化算法能有效的求解的目标数一般不超过4个。

与遗传算法相比较，传统算法在处理多目标优化问题上，也具有其特有的优势。相对遗传算法来说，传统算法的计算量小、计算速度快、设计简单、容易理解，方便建立数学模型，并且传统方法有充分的理论支持。因此虽然遗传算法在解决多目标优化问题上取得了很多成效，但这并不意味着传统方法不及遗传算法有效，会被多目标遗传算法取代。相反，传统算法在解决一些问题上仍然具有很大的优势，比如计算速度快，易实现。所以我们在求解多目标问题中，如果能结合遗传算法和传统方法间的优点，效果将会越来越好。

6 结束语

在工程实践中和科学领域中存在着很多复杂的多目标优化问题。在单目标优化问题中,最优解就是一个且已经具有了明确的概念,但对于多目标优化问题,不同于单目标优化,多目标优化处理的是一些相互冲突、相互制约的目标,其解集也不是单一的一个解,而是一组最优解的集合。传统的数学规划原理在多目标优化的实际应用中虽然不太适用,但其也有自己的优点,而且就对于现在的多目标遗传算法也并不是很完善的,需要解决的问题也很多。因此,有必要进一步研究求解多目标优化问题的更多高效算法,结合两者的优点,使处理多目标问题的效果越来越好。

摘要：多目标优化是最优化领域的一个重要的研究方向。论述了多目标优化模型,同时介绍了常用的几种传统优化方法和常用的几种多目标遗传算法,对改进后的遗传算法与传统优化方法求解效果进行了比较,认为要进一步研究求解多目标优化问题的更多高效算法,若能结合两者的优点,处理多目标问题的效果将越来越好。

关键词：多目标优化,传统优化方法,遗传算法

参考文献

[1]林锉云,董家礼.多目标优化的方法与理论[M].吉林:吉林教育出版社,1992.

[2]Marglin S.Public Investment Criteria.MIT Press,Cambridge[M].Massachusetts:1967.

[3]Y.Haimes.Integrated system identification and optimization[J].control and Dynamic System:Advances in Theory andApplication,1973,10:435-518.

[4]Osyczka A.Multicriterion optimization in engineering withFORTRAN programs[J].Ellis Horwood LIMITED.1984.

[5]Tseng C H and Lu T W.Mini-max multi-objectiveoptimization in structural design[J].International Journal forNumerical Methods in Engineering.1990,30:1213-1228.

[6]Holland J H.Adaptation in naturation in naturalandartificial systems[J].The Uniuversityof Michigan Press,1975(1):21-24.

遗传算法中遗传操作的改进策略篇6

遗传算法[1,2]是本世纪六七十年代由美国J.H.Holland教授提出的一种模拟生物进化过程中的自然选择机制的优化方法。同其他优化方法相比, 遗传算法具有全局、并行搜索的特点, 不易陷入局部最优, 同时搜索不依赖于问题的梯度信息, 尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 在许多领域[3,4,5]获得了成功应用。

但是, 遗传算法也存在着一些不足之处, 如局部搜索能力差、寻优精度不高、存在早熟收敛等。通过对二进制编码的分析, 发现对编码串不同基因位的改变导致优化变量的变化程度不等。针对这个特点, 本文提出了一种改进的交叉和变异策略, 使得群体在进化初期可以搜索到更大的解空间, 提高算法在全局范围的搜索能力;在进化后期减少较优模式被破坏的机率, 同时维持一定的种群多样性, 加强算法在局部范围的搜索能力。仿真实例优化结果表明, 改进遗传操作提高了算法的寻优能力和收敛性能。

1 改进遗传操作

1.1 二进制编码特性分析

在标准遗传算法中, 对交叉点和变异点的选择均采取了等概率随机选择的方式。显然, 这些操作忽视了二进制编码的一个重要特性:个体中不同基因位改变时, 引发的解空间变化幅度不相等[6,7], 换句话说, 就是各个基因位的重要性不相等。以交叉操作为例, 假设 $\underset{6}{1} \underset{5}{1} \underset{4}{1} \underset{3}{0} \underset{2}{0} \underset{1}{1}$ 和 $\underset{6}{0} \underset{5}{0} \underset{4}{1} \underset{3}{1} \underset{2}{0} \underset{1}{0}$ 是两个交叉父代, 它们解码后分别为57和12。当选择第5个基因位作为交叉点时, 生成的新个体101100和011001解码后对应的十进制数为44和25;而选择第1个基因位作为交叉点时生成的个体对应的十进制数为56和13。显然, 选择高位基因 (第5个基因位) 作为交叉点时, 生成的子体与父代间的差异较大, 因而可以搜索到更大的解空间;当选择低位基因 (第1个基因位) 作为交叉点时, 子代与父代的差异相对较小, 这样只能实现对父代邻域的局部搜索。

同样的例子表明, 对于变异操作存在着类似的现象:高位基因变异后生成的子代与父代间的差异较大, 因而可以搜索到父代没有到达的解空间, 同时, 有利于在全局范围内维持种群的多样性;而低位基因的变异只能实现对父代邻域的局部搜索。

1.2 改进交叉操作

改进交叉操作与标准交叉操作的区别主要体现在交叉点的选取方式上, 标准交叉操作是在基因串中等概率随机选择一位作为交叉点, 而改进交叉操作充分考虑了二进制编码的特性, 赋予各个基因位不同的交叉点选择概率 (所谓交叉点选择概率, 是指该基因位被选作交叉点的概率) , 并使之随着进化呈现不同的变化趋势。交叉点选择的基本原则是:在进化初期, 优先选择高位基因作为交叉点, 这样可以搜索到更大的解空间, 同时可以维持种群的多样性;当进化到后期时, 由于父代已经接近最优解, 为防止子代偏离父代太远, 应该选择低位基因作为交叉点。

1.2.1 交叉点选择概率公式

通过常数k∈ (0, 1) 将长度为l的编码串分为两部分:将1～round (kl) 之间的基因位作为低位基因部分, round (kl) + 1～l之间的基因作为高位基因部分, 使处于同一部分的基因位具有相同的交叉点选择概率, 而不同部分的交叉点选择概率则完全不同:

$p_{c p g} = a + \frac{b}{1 + \exp (α (g - g_{0}))} (1)$

pcpd=1-pcpg (2)

round (x) 为取整函数, pcpg表示高位基因部分的交叉点选择概率, pcpd为低位基因部分的交叉点选择概率, g为进化代数, a、b、α、g0为事前设定的常数。

图1是一组pcpg, pcpd随进化的变化曲线, 其中各参数分别为:a=0.3, b=0.4, α=0.04, g0=180。可以看出, 图中高位基因交叉点选择概率pcpg和低位基因交叉点选择概率pcpd的变化曲线完全符合上述的交叉点选择基本原则, 充分利用了各个基因位的信息, 加强了种群在全局的搜索能力, 同时保证进化后期不会远离最优解。

1.2.2 参数分析

观察式 (1) , 可以看出公式的第二项是一个Sigmoid函数, 根据Sigmoid函数的性质, 成立式:

${\begin{cases} a + b \approx p_{c p g 0} \\ a \approx p_{c p g Τ} \end{cases} (3)$

其中, pcpgo、pcpgT分别为高位基因的初始和最终交叉点选择概率。由于0<pcpgT<1, 那么有0<a<1成立, 又因为0<pcpgT<pcpg0<1, 可得0<b<1。

交叉点选择概率公式中其他参数对pcpg、pcpd的影响为:参数α控制着pcpg、pcpd随进化变化的快慢程度, 即图1中斜线部分的倾斜程度, α越大, 图中斜线部分也越倾斜。建议α在0.02～0.05之间取值。参数g0的取值并不能改变曲线的形状, 只能影响到图中斜线部分的相对位置, g0增大, 则斜线部分向右移动, 反之, 斜线部分向左移动, 即, g0决定了pcpg、pcpd发生较大变化的起始代数。建议g0在0.4gmax至0.6gmax之间取值, 其中, gmax为最大进化代数。

1.2.3 实施过程

1) 随机选择两个个体作为交叉父代;

2) 确定常数k, 将每个变量分为高位基因和低位基因两部分;

3) 根据公式 (1) 和 (2) , 计算各个部分的交叉点选择概率;

4) 随机产生1个0～1之间的随机数, 根据赌轮选择原则, 将产生的随机数与pcpg比较, 如果pcpg大于随机数, 则表明交叉点应在高位基因部分进行选取, 那么在round (kl) + 1～l之间随机选取一点作为交叉点;否则在1～round (kl) 之间随机选择一点作为交叉点;

5) 交换两个父代交叉点后的部分, 形成新的个体。

1.3 改进变异操作

文献[7]中曾针对二进制编码的特性提出了一种自适应变异算法, 其理论依据是不同基因位的改变造成个体适应度的改变程度不等, 因此可以根据变异后适应度值的变化程度反过来调整各个基因位的变异。但是这种变异策略的理论基础有很大的局限性。以图2所示的优化问题y=f (x) 为例, 假设x*为全局最优解, x1为变异父代, 对x1不同基因位变异后得到的个体分别为x2和x3。显然, 由x1到x2, 个体的变化程度远大于从x1到x3, 但是适应度值的改变规律却完全相反。此时, 如果仍然根据适应度值的变化幅度来调整变异率, 将会得到错误的结果, 进而影响算法的性能。由于多极值目标函数在遗传算法寻优中很普遍, 因而上述现象出现的几率很大, 对算法带来的负面影响也就无法忽视。

不同于文献[7]中的自适应变异算法, 本文提出的改进变异策略直接对编码的各个基因位赋予不同的变异率, 基本原则是:在进化初期, 赋予高位基因较高的变异率, 这样可以搜索到更大的解空间, 提高算法的全局搜索能力;在进化后期已逼近最优解时, 适当降低高位基因的变异率, 减少较优个体结构被破坏的概率, 同时增大低位基因的变异率, 提高算法在局部范围的搜索能力。

同交叉策略一样, 变异操作通过常数k将基因串分为高位基因部分和低位基因部分, 使处于同一部分的基因位具有相同的变异率, 而不同部分的基因位的变异率完全不同:

$p_{m g} = a_{1} + \frac{b_{1}}{1 + \exp (α_{1} (g - g_{0}'))} (4)$

$p_{m d} = a_{2} + \frac{b_{2}}{1 + \exp (- α_{1} (g - g_{0}'))} (5)$

其中, pmg表示高位基因的变异率, pmd为低位基因的变异率, g为进化代数, a1、b1、a2、b2、α1、g0′均为事前设定的常数。由于pmg、pmd随进化的变化曲线与pcpg、pcpd的基本相同, 对此将不再详细说明。公式中各个参数的含义参见1.2.2节的分析。

改进变异操作的实施过程如下:

1) 确定常数k, 将每个变量分为高位基因部分和低位基因部分;

2) 根据公式 (4) 和 (5) , 计算各个基因位的变异率;

3) 随机产生l个0～1之间的随机数, 将各个基因位的变异率与相应的随机数比较, 若变异率大于随机数, 则该基因位发生变异, 否则, 该基因位不作操作。

值得注意的是, 上述的交叉和变异操作是针对优化目标只有一个变量的情况。当优化目标具有多个变量时, 只要分别对每个变量相应的基因串执行上述操作即可。

2 仿真算例

为了能够验证两种改进遗传操作的有效性, 分别将只采用了改进交叉操作的遗传算法 (简称MC-GA) 和只采用了改进变异操作的遗传算法 (简称MM-GA) 用于优化5个典型的测试函数, 并将结果和标准遗传算法 (SGA) 进行了比较。

2.1 测试函数

本文选择的测试函数[8]分别为De Jong函数F5, Bohachevsky函数#1, Bohachevsky函数#2, Bohachevsky函数#3, Schaffer函数F7。这五个标准测试函数均为多峰函数, 具有多个局部极值。表1中给出了各个函数的最优解, 相应的目标函数值, 以及二进制编码的长度。

2.2 控制参数

文中的控制参数设置如下:群体规模为100, 最大运行代数为500, 三种算法均采用比例选择, MM-GA和SGA采用多点交叉, 交叉率为0.8, MC-GA和SGA采用点式变异, 变异率为0.03。此外, 基因分段比例k=0.6, 公式 (1) 中的控制参数分别为:a=0.3, b=0.4, α=0.04, g0=240, 公式 (4) , (5) 中的各参数设置为:a1=0.01, b1=0.01, a2=0.01, b2=0.05, α1=0.03, g0′=300。

2.3 计算结果分析

表2～4为三种算法对五个测试函数运行30次后的平均结果, 表中分别给出了变量x1, x2的平均值和均方根植, 目标函数的平均值及均方根植, 以及在多次运行中算法收敛的次数。通过比较可以看出, 同SGA相比, 绝大多数情况下, 改进算法的结果更接近于函数的最优解, 这表明改进算法提高了寻优的精度;从算法的稳定性方面讲, 改进算法的均方差值要低于标准算法的结果, 这说明, 改进算法的解更加集中, 稳定性更好。另外, 改进算法虽然不能避免早熟收敛, 但与标准算法相比, 其收敛性已得到显著提高。

图3为三种算法对De Jong F5函数的目标函数值进化曲线, 从图3中可以看出, MM-GA与MC-GA出现收敛的代数基本相同, 而SGA的收敛代数明显落后于两种改进算法, 这说明改进算法的收敛速度更快。

表2和表3的比较结果表明, MM-GA找到的解的质量略优于MC-GA, 出现这种现象的原因是:MC-GA没有考虑到交叉点前基因的取值对于交叉子代的影响, 以致出现了许多无效交叉操作。用一个简单的例子对此进行说明。假设两个交叉父代为10001和00011, 如果选择第4位作为交叉点, 由于两个父代在第5基因位上的取值相同, 交叉后子代与父代完全相同, 交叉操作失效。进一步分析可以得出, 选择第i位作为交叉点时, 交叉点前父代基因取值相同的概率为0.5l-i, 这说明交叉子代与父代相同的概率与交叉点的选择有着密切的关系, 交叉点基因位选择越高, 无效交叉出现的概率也越大。由于MC-GA忽视了这一点, 导致在进化初期出现许多无效的交叉操作, 引起搜索能力的降低, 这是MC-GA需要考虑改进的地方。

3 结论

通过对二进制编码特性的分析, 提出了一种改进的交叉和变异策略, 对二进制编码串中的各基因位赋予不同的交叉点选择概率和变异率, 并使之随进化呈现不同的变化趋势。最后通过5组标准测试函数证明了改进遗传算法的寻优能力。本文的主要结论有:

(1) 对二进制编码特性的分析结果表明, 不同基因位的改变所引起的个体在解空间的变化幅度是不等的, 也即各个基因位的重要性是不相等的。

(2) 基于二进制编码特性的改进遗传操作使得个体在进化初期可以搜索到更大的解空间, 加强了算法在全局的搜索能力;在进化后期减少了较优模式被破坏的机率, 同时能够维持一定的种群多样性。

(3) 对5个测试函数仿真实验的结果表明, 与SGA相比, 改进算法具有寻优精度高, 解的稳定性好等优点。同时, 与标准算法相比, 改进算法的收敛性得到显著提高。

(4) 进一步的比较发现MM-GA的优化能力比MC-GA略强一些, 这是由于MC-GA没有考虑到交叉点前基因的取值对于交叉子代的影响, 以致产生许多无效的交叉操作。我们对此将进行进一步的研究分析。

摘要：通过分析发现, 二进制编码中不同基因位改变时, 所引起优化变量的变化程度不相等。基于此, 提出一种改进的交叉和变异策略, 对编码串中各个基因位赋予不同的交叉点选择概率和变异率, 并随进化调整各位的交叉点选择概率和变异率。仿真结果表明, 同标准遗传算法相比, 采用改进策略的遗传算法具有寻优精度高、稳定性好、收敛性强等优点;此外, 同改进交叉操作相比, 改进变异操作能更有效地提高算法的寻优能力。

关键词：遗传算法,二进制编码,交叉,变异

参考文献

[1]陈国良, 王煦法, 等.遗传算法及其应用[M].北京:人民邮电出版社, 1999.

[2]潘正君, 康立山, 陈毓屏.演化算法[M].北京:清华大学出版社, 2000.

[3]Raton B.Genetic algorithms for pattern recognition[M].CRC Press, 1996.

[4]Shaunna M, Tom L, Adbulla H.A genetic algorithm environment for starpattern recognition[J].Journal of Intelligent and Fuzzy Systems, 1998, 6:3-16.

[5]Gen M, Cheng R.Genetic algorithms and engineering optimization[M].New York:Wiley-Interscience, 2000.

[6]李海民, 吴成柯.自适应变异遗传算法及其性能分析[J].电子学报, 1999, 27 (5) :90-92.

[7]汪民乐, 高晓光, 汪德武.遗传算法控制参数优化策略研究[J].计算机工程, 2003, 29 (5) :51-52.

基于遗传算法的粒子滤波跟踪算法篇7

粒子滤波跟踪算法由于处理非线性、非高斯问题的突出能力,在目标跟踪领域越来越受到大家的青睐。但它自身却有一个无法回避的问题:粒子样本多样性退化。丧失粒子多样性的粒子滤波器极容易使目标跟踪的状态收敛到个别状态点上去,经过数次递推后由于估计状态减少就会造成目标跟踪丢失。因此,许多学者都提出了粒子重采样的方法,如:多项式重采样算法[1]、累积分布重采样。然而重采样过程中采取复制保留权值较高的粒子,删除权值较低的粒子的结果,导致粒子多样性的减弱,特别是在样本受限条件下甚至导致滤波发散[2]。遗传算法[3](Genetic Algorithm)是科学家借鉴生物界的遗传进化规律而得到的随机的优化与搜索方法。文献[4]进一步从蒙特卡罗仿真的观点建立了粒子滤波器和遗传算法之间的关系。文献[5-7]将遗传算法引入粒子重采样中,有效增加粒子多样性;但优选方法单一,粒子多样性小,新生粒子精度低还造成了计算量急剧增加的问题。文献[8]把遗传算法也应用到了粒子重采样中,但其在父代的选择时仅使用了单一阈值选择,对交叉算子与变异算子产生的后代做了限制,同样影响到粒子的多样性。文献[9]利用粒子群优化算法改进粒子滤波,该方法使粒子分布朝后验概率密度分布取值较大的区域运动在一定程度上能克服粒子贫乏问题但粒子群优化算法计算量较大,采样粒子分布带宽存在发散现象,粒子分布方差分布变化较大。

本文利用遗传算法来解决粒子滤波跟踪算法中的粒子多样性退化的问题。在传统遗传算法中,一般采样使用阈值限制法加赌轮法的选择方案,而本文采用多项式重采样进行部分优选复制,每次采样后去除已被选过的样本粒子,同时进行阈值调整。交叉和变异算子对子代进行选择时,都不对子代粒子相似系数做限定。在变异算子中采用了马尔可夫链蒙特卡罗移动(MCMC)[10]加高斯白噪声的变异方法并采用快速MH(Metropolis-Hastings)抽样[11]。

1 粒子滤波算法

粒子滤波技术是基于Bayesian理论和Monte Carlo方法的一种求解后验概率的实用性方法。它通过预测和更新求得后验概率密度。

预测:假设在(k-1)时刻,p(xk-1|z1:k-1)是已知的,对于一阶马尔科夫过程,由Chapman-Kolmogorov方程,有

更新:即由系统的观测模型,在获得k时刻的观测值zk后,实现先验概率p(xk|z1:k-1)至后验概率p(xk|z1:k)的推导

其中:p(zk|xk)称为似然性,表示系统状态由xk-1转移到kx后和观测值的相似程度。p(xk|z1:k-1)为先验概率,p(zk,z1:k-1)是一个归一化常数在上式有先验概率密度到后验概率密度的积分是很难实现,不可能进行精确的分析,所以采用序列重要性采样实质上是利用蒙特卡罗仿真来模拟递归贝叶斯估计。

如果系统的整个递归过程符合马尔科夫假设,那么k时刻,系统状态的后验概率密度函数用一组带有权值的粒子{xk(i),wk(i)}Ni=1表示为

其中:wki为粒子对应的权值,且;δ(*)为狄拉克函数。当粒子数足够大时,这种对后验概率密度的离散加权估计可以很大程度上逼近状态的真实分布,从而接近贝叶斯估计的最优解。

一个已知的、容易采样的参考分布q(x0:k|z1:k)作为重要性函数,权值的迭代公式为

2 基于遗传算法粒子重采样

2.1 有效采样尺寸

为了减少算法的计算量,提高跟踪算法的实时性,设定一个表示粒子退化程度的参数——有效采样尺寸,定义为

其中wki为观测后粒子权值。由于上式难以精确计算,实际利用它的一种近似估计,定义为

其中wk*(i)为归一化后得到的标准化权值。

通过试验,我们发现当时开始启动重采样算法是比较合理的。

2.2 遗传算法

遗传算法作为一种快捷、简便、容错性强的算法,其步骤一般为编码、产生初始群体、计算相似度、复制、交换和变异六个步骤。其中复制概率Ps、交换概率Pc、变异概率Pm在本文中用特定区间的随机数表示:复制概率Ps∈[.0,607.],交换概率Pc∈[.0,2.025],变异概率Pm=1-Ps-Pc。下面给出遗传算法的具体步骤:

步骤1:样本编码及相似度计算。

对新采样的粒子编号为i=,1,2,3,…，N,作为父代样本:{xki,i=,1,2,3,…，N},利于目标的颜色特征通过Bhattacharyya系数计算模板与采样点相似度。由于在每次观测后得到每个采样点的相似度为ρi,i=1,2,3…N。对相似系数进行归一化为

步骤2:优选复制。

利用传统多项式重采样方法对归一化的相似系数进行采样,相似系数大的样本获得较大的概率被选择复制子代,而相似系数小的样本获得较小的概率被选中复制为子代。每次选后,把被选中的样本移出父代,剩余样本相似系数重新进行归一化处理,继续选择,直到产生的子代个数达到Ps×N,Ps为随机0.6到0.7之间的随机数。多项式重采样在粒子滤波算法中有较好的实时性,但重采样粒子样本退化严重,而传统的遗传算法中使用阈值限制法加赌轮法进行优选复制法,实时性不时很强而且相似度较大的以均等概率复制为子代,优选性不突出,利用多项式重采样进行优选复制的方法可以保证跟踪算法有较好的实时性,通过随机数限定样本个数给样本的多样性留出了空间,减小了粒子退化程度。

步骤3:交叉繁殖。

在优选复制以后的剩余(N-Ps×N)个样本中随机抽取两个样本进行杂交。设被抽取样本为ia、ib,其中ia、ib为优选复制后剩余的样本,利用一个随机数α∈[0.3,0.4]作为交换率,交叉繁殖公式为

将新生的作为子代,如此循环,直到抽到的杂交子代个数达到Pc×N。由随机数作交换率进行样本交叉繁殖的方法可以较好地提高样本的多样性,与传统的采用固定系数交换率的遗传算法相比,随机数作交换率进行样本交叉繁殖的方法在即使采样到相同样本时候通过不同的交换率也会有新的样本产生,更好地增加了粒子的多样性。

步骤4:变异繁殖。

变异繁殖是为了给样本集带来新样本,变异繁殖的方法很多,本文变异繁殖采用马尔可夫链蒙特卡罗移动加高斯白噪声实现并采用MH(Metropolis-Hastings)算法对样本进行选择,很大程度的提高了变异样本的多样性。仍然在剩余的(N-Ps×N)个样本中随机抽取(N-Ps×N-Pc×N)个样本做变异繁殖。变异后的样本为

其中:Ak|k-1为一阶马尔可夫链转移矩阵,δ~N(,0)1。

对样本进行快速MH抽样:

1)按照均匀概率分布从区间[0,l]中抽样得到门限值u,u~U(,0)1;

2)对新变异样本和原样本进行似然估计分别为;

3)设,若u<θ,保留作为变异后的样本;

当变异样本数达到(N-Ps×N-Pc×N),变异繁殖结束。

在传统的遗传算法中,样本变异一般采样固定的变异概率产生新样本,对解决粒子退化问题的作用有限。本文通过马尔可夫链蒙特卡罗移动加高斯白噪声来提高变异样本的多样性,而且使用快速MH抽样保证了粒子的拥有较大的相似度。

图1为在跟踪视频的50帧时采用遗传算法的优选、交叉和变异三步骤对粒子分布进行处理后的粒子分布情况图。

从图1中可以看出,原来样本点经过遗传算法后被舍弃同时出现了一些更能反映目标位置的新的样本点。通过以上遗传进化得到了新的子代样本。将新生的子代样本用Bhattacharyya系数计算采样点与模板相似度:

将新生样本的相似系数转化为新生样本的权值系数

对新生样本系数归一化为

3 实验结果与分析

为了证明本文所改进的算法的优越性通过编程在计算机上进行了仿真实验。电脑配置为P4 2.8,512M内存,WINDOWS XP操作系统和VC++6.0的开发平台,借助Open CV函数库设计了跟踪算法。程序流程如下:

1)在第一帧中手动选择跟踪窗口,计算目标模板颜色直方图,初始化粒子滤波器,生成均匀分布粒子群;

2)读入下一帧图像,启动粒子滤波,进行粒子转移,对转移后的新生样本根据式(10),计算各个样本点相似性系数,以及归一化新生样本系数;

3)计算有效采样尺寸,当执行步骤4),执行步骤5);

4)遗传重采样算法:

a.样本编码及相似度计算,b.优选复制,c.交叉繁殖,d.变异繁殖;

5)以为加权系数新生样本点坐标求和得到目标运动位置坐标,输出坐标;

6)视频是否结束,未结束则跳转到步骤2),若视频结束则停止整个程序。

试验视频分别为近红外与可见光拍摄的320×240 avi格式视频。在所有的跟踪过程中,目标模板都是通过手动选取视频图像中的目标建立的,蓝色框所框住的为跟踪目标,跟踪过程中粒子数N=100,图2与图3为可见光视频的跟踪效果对比的图,图4为目标运动轨迹,图5为粒子分布带宽与方差对比图,图6为多项式重采样、粒子群重采样和遗传重采样三种算法运算时间比较图。

通过两种跟踪算法的跟踪效果图对比可以发现基于颜色特征的粒子滤波跟踪算法基本上都能跟踪上目标,但由于粒子数较少的情况下加之粒子滤波重采样时粒子样本的退化,跟踪目标不是很稳定,时常偏离目标的真实位置如图2的48帧和60帧。而这种跟踪不稳定的现象在跟踪目标发生遮挡的时候表现更加明显如图2的53帧。通过图4目标运动轨迹图也可以得到同样结果,基于多项式重采样的算法跟踪目标位置与目标真实位置偏差较大,有明显的上下漂移情况,基于遗传算法的跟踪算法却能较为平稳的跟踪目标,鲁棒性较强(见图3、图4)。虽然增加粒子数在一定程度是能增加采样的多样性,但这直接影响到了程序的运行效率,很难实现实时跟踪,对解决粒子退化问题帮助不大。图5分别为多项式重采样、粒子群优化重采样和遗传重采样三种情况下的粒子分布情况,多项式重采样方法粒子带宽分布比较平稳,但粒子分布带宽较窄,粒子方差变化很大,粒子分布带宽窄,方差大主要就使由于粒子在重采样中粒子多样性丢失,样本只集中到个别几个粒子上,因此跟踪目标很不稳定,跟踪框很容易偏离跟踪目标(见图2、图4);粒子群优化重采样粒子带宽分布也较窄,后期带宽有发散现象,粒子分布方差较多项式重采样有一定的改善,但较遗传重采样而言粒子分布方差还是比较大;遗传重采样方法粒子分布的带宽较大,而粒子分布方差比较平稳,采样点分布比较均匀,样本丰富,是一种比较理想的样本采样结果(见图5)。

图6为三种重采样算法运行每帧图像处理时间比较,多项式重采样,遗传重采样和粒子群优化重采样算法每帧平均用时间分别为:47.66 ms,48.60ms和60.63 ms遗传算法相对粒子群优化算法运算速度提高了24.75%,而遗传算法相对多项式重采样运算速度只降低了1.97%,但从图3、图4和图5可知,遗传算法的跟踪精度比多项式重采样有较大的提高。由此可知改进后的遗传算法有较高的运算效率,目标跟踪上有较好的实时性。通过以上对比可以发现改进后的遗传重采样粒子滤波跟踪算法既保持了粒子的多样性,拥有较高的实时性,同时应用了较好的模板更新策略,即使在复杂背景下或者遮挡发生时候跟踪框都能较好准确的找的真实的跟踪目标。

4 结论

本文应用改进的遗传算法解决粒子滤波跟踪算法中粒子样本退化的问题。在改进的遗传算法中,利用了多项式采样法进行了优选繁殖,利用特定区间的随机数做交换率进行样本交叉繁殖,最后在变异繁殖中使用了马尔可夫链蒙特卡罗移动加高斯白噪声做样本变异以及MH抽样算法选取样本,以上改进很好的解决了粒子退化问题,保证了样本的多样性。在模板更新中,使用了多模板融合更新技术。通过试验表明改进后的粒子滤波跟踪算法的目标跟踪效果更加稳定,跟踪精度更高。

摘要：针对粒子滤波跟踪算法中粒子多样性退化问题,将改进的遗传算法应用到粒子重采样中,改善了样本的多样性。在改进的遗传算法中,使用了多项式重采样进行优选复制;以特定区间的随机数做交换率进行样本交叉繁殖;使用了马尔可夫链蒙特卡罗移动加高斯白噪声做样本变异繁殖并使用快速MH抽样算法选取样本。改进后的粒子滤波跟踪算法不但保持了较高的运算效率,而且还较好地提高了跟踪的稳定性。试验表明,改进后的粒子滤波跟踪算法目标跟踪更加稳定,目标定位更加准确。

关键词：遗传算法,粒子滤波,快速MH抽样,多模板融合,目标跟踪

参考文献

[1]Gordon N J,Salmond D J,Smith A F M.Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimation[J].IEE Proceedings on Radar and Signal Processing(S0143-7070),1993,140(2):107-113.

[2]徐林忠.基于粒子滤波和卡尔曼滤波的复杂场景下视频跟踪[D].杭州:浙江大学,2008:51-56.XU Lin-zhong.Visual Tracking Based on Particle Filter and Kalman Filter under Complex Environments[D].Hangzhou:Zhejiang University,2008:51-56.

[3]张文修,梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社,2000.ZHANG Wen-xiu,LIANG Yi.Mathematics Base of Genetic Algorithm[M].Xi’an:Xi’an Jiaotong University Press,2000.

[4]Higuchi T.Monte Carlo filter using the genetic algorithm operators[J].Journal of Statistics Computer Simulation(S0094-9655),1997,59(1):l-23.

[5]Ronghua L,Bingrong H.Coevolution based adaptive Monte Carlo localization[J].International Journal of Advanced Robotic Systems(S1729-8806),2004,1(3):183-190.

[6]Park S,Hwang J,Rou K,et al.A new particle filter inspired by biological evolution:genetic filter[J].International Journal of Applied Science Engineering and Technology(S1307-4318),2007,4(1):459-463.

[7]叶龙,王京玲,张勤.遗传重采样粒子滤波器[J].自动化学报,2007,33(8):885-887.YE Long,WANG Jing-ling,ZHANG Qin.Genetic resampling Particle filter[J].Acta Automatica Sinica,2007,33(8):885-887.

[8]席涛,张胜修,原魁,等.基于遗传进化策略的粒子滤波视频目标跟踪[J].光电工程,2009,36(3):28-32.XU Tao,ZHANG Sheng-xiu,YUAN Kui,et al.Video Object Tracking Based on Particle Filter with Genetic Evolution Strategy[J].Opto-Electronic Engineering,2009,36(3):28-32.

[9]方正,佟国峰,徐心和.基于粒子群优化的粒子滤波定位方法[J].控制理论与应用,2008,25(3):533-537.FANG Zheng,TONG Guo-feng,XU Xin-he.A Localization method for particle-filter based on the optimization of particle swarm[J].Control Theory&Application,2008,25(3):533-537.

[10]Gilks W R,Berzuini C.Following a moving target monte carlo inference for dynamic Bayesian models[J].Journal of the Royal Statistical Society B(S1369-7412),2001,36(1):127-146.

遗传算法的综述篇8

堆石坝的本构模型参数一般是通过室内试验测定或根据以往工程经验确定的,而这种方法由于受室内试验方法、试验设备、施工工艺、施工方法和施工质量等方面的影响,会使堆石坝真实的材料参数与计算时所采用的材料参数不一致,这样,如果利用设计时给出的本构模型参数进行面板堆石坝安全评价及预测,势必会造成较大的误差[1]。目前,众多学者在解决这一问题时,大多都致力于基于实测信息的参数反演分析的研究。在堆石坝工程中的反演方法常采用直接法,即将堆石料的参数反演问题转换成优化问题[2,3,4],以有限元计算位移值与实测位移值的最小误差函数作为目标函数,通过反复迭代,寻找使计算位移值和实测值之间误差最小的模型参数。本文鉴于面板堆石坝工程有限元计算过程的复杂性,利用遗传算法优化BP神经网络权值和阈值建立遗传神经网络,模拟堆石的有限元计算,通过正交设计方法构造遗传神经网络训练样本,完成遗传神经网络的学习、训练及测试过程,建立能模拟堆石坝有限元计算的遗传神经网络模型,然后结合再结合遗传算法的优化过程,将两者应用于面板堆石坝体力学参数反演中,反演得到计算位移与实际位移拟合较好的堆石料参数。结果表明,利用遗传算法和遗传神经网络算法相结合的方法,在解决堆石坝反演分析问题中具有明显的优越性。

1 BP神经网络

BP(Back propagation)神经网络是目前最有代表意义和广泛用途的神经网络模型。它是由一个输入层、一个输出层和一个或多个隐含层组成的,其特点是:各层神经元仅与相邻层神经元之间有连接;各层内神经元之间无任何连接;各层神经元之间无反馈连接。理论已经证明,当隐层神经元数目足够多时,BP神经网络可以以任意精度逼近任何一个具有有限间断点的非线性函数。因此,能够适应于求解高度非线性等复杂岩土工程问题。

但是BP网络也并不是一个十分完善的网络,主要存在学习收敛速度太慢、不能保证收敛到全局最小点等缺陷,而且BP神经网络结构的确定尚无理论指导,往往根据经验确定,其权值则通常由梯度法来确定,通常经过多次反复试验却又很难找到最优的网络结构和权值[5,6],大量研究表明,遗传算法可以为神经网络的设计和训练提供新的途径。

2 遗传算法

遗传算法(Genetic Algorithm,GA)是由美国密执根(Michigan)大学的J.Holland教授于1975年首先提出的,它是一种新兴的模拟自然界生物进化机制的搜索寻优技术。其核心思想源于人们对生物进化过程的认识,模拟了自然选择和自然遗传过程中发生的繁殖、交换、变异现象,它根据适者生存、优胜劣汰的自然法则利用遗传算子:选择、交叉、变异逐代产生、优选个体,最终搜索到较优个体的算法[7]。

遗传算法在优化过程中,处理的对象并不是参数本身,而是对参数集进行编码的个体,它采用同时处理群体中多个个体的方法,同时对搜索空间中的多个解进行评估,实现其全局搜索能力及易于并行化的特点。鉴于遗传算法使用简单,鲁棒性强,易于并行化,搜索不依赖于梯度信息,被广泛地应用于各种领域[7],如函数优化、组合优化、生产调度问题、自动控制、机器人学、图像处理、遗传编码、机器学习、数据挖掘、信息战等。

3 遗传神经网络算法

遗传算法是一种通用的问题求解方法,它对求解问题的本身一无所知,不受其搜索空间限制性条件的约束、不需要目标函数具有连续性等辅助信息,而且它的搜索能力具有全局性,可以很容易找到全局最优解。因此,利用遗传算法优化BP神经网络弥补神经网络自身的缺陷[8],能够更好的解决传统方法中的靠经验来设计网络结构、收敛速度慢和不容易找到全局最优解等方面的问题,同时可以充分发挥遗传算法的全局搜索能力和BP神经网络的局部搜索能力,进而提高网络精度及性能。

4 水布垭面板堆石坝的参数反演分析

4.1 工程概况

水布垭面板堆石坝是目前世界上已建成的最高面板坝,最大坝高233 m,坝顶高程409 m,坝轴线长660 m,坝顶宽度12 m,大坝上游坝坡1∶1.4,下游平均坝坡1∶1.4,总填筑工程量1 570万m3,其中坝体堆石填筑量约为1 563.74万m3。主要分为7个填筑区:ⅠA区(黏土铺盖区)、ⅠB区(盖重区)、ⅡA区(垫层料区)、ⅢA区(过渡区)、ⅢB区(主堆石区)、ⅢC区(次堆石区)、ⅢD区(下游堆石区)。大坝典型断面及坝料分区见图1。

为了监测坝体在填筑过程中的变形,在0+212剖面235、265、300、340、370 m高程处共计布置了35个测点;在0+132剖面和0+356剖面300、340、370 m高程处分别布置了11条水平、垂直位移测线,共73个测点。随着坝体的填筑完成,目前已取得了丰富的变形监测成果[9]。

4.2 待反演参数及取值范围的确定

本文结合各本构模型的优缺点,最终选取邓肯E-B模型进行堆石坝的有限元计算,邓肯E-B模型的主要参数有φ、c、Rf、k、n、kb、m、kur、nur。如果将上述所有参数均作为待反演的参数,计算过程很难保证反演结果收敛到精确值,而且根据以往的经验可知参数φ、c、Rf、kur、nur的试验值与实际值差别不大,可直接取试验值;而参数k、n、kb、m由于受试验条件与现场条件的差异,其试验值与实际值差别较大,因此本文选取k、n、kb、m作为待反演参数。由于垫层区及过渡区等相对于坝体堆石区厚度较小,材料变化对坝体的变形影响甚小,故本文主要对主、次堆石区的两组材料参数进行反演计算。根据以往工程经验及水布垭初始设计参数,设定参数的取值范围见表1所示。

4.3 测点选取

本文根据以往工程经验,选取0+212断面的8个测点,即SV01-1-6、SV01-1-9、SV01-1-17、SV01-1-20、SV01-1-26、SV01-1-29、SV01-1-32、SV01-1-34。8个测点分布于坝体不同高程、不同材料分区内,且测点变形的实测值应正常稳定,变形监测数据的完整性、可靠性较好。测点具体位置及高程见图2。

4.4 遗传神经网络的模拟计算

在堆石坝材料参数反分析中,面板堆石坝工程有限元计算过程相当费时费力,如果有限元计算程序直接被优化程序调用进行反演计算,难度相当大,效率也非常低[9]。因此,本文利用遗传神经网络来建立堆石料参数和位移量之间的映射关系,代替直接反分析法中的有限元计算以提高计算效率。在构造遗传神经网络训练样本过程中,本文通过均匀设计试验法形成参数组,根据水布垭工程施工样图,建立了有限元分析模型,利用ANSYS的APDL语言,结合邓肯E-B模型的非线性计算原理以及堆石坝的非线性静力分析一般方法,编制了堆石坝施工模拟的计算程序,实现了堆石坝的有限元分析计算。

然后将参数组和相应的有限元计算得到的测点位移值作为遗传神经网络的输入和输出,训练遗传神经网络,同时观察遗传神经网络训练样本的输出误差,网络精度满足计算要求,则表示网络训练完成,否则需要进行重新训练。当网络训练完成后,还需要随机构造测试样本参数,利用训练好的遗传神经网络进行模拟计算,同时进行有限元计算,对比神经网络模拟计算结果和有限元计算值之间的误差,如果误差小于容许误差则表明训练好的遗传神经网络是可以模拟有限元计算的,否则的话表明训练好的遗传神经网络不成功,需重新训练。满足上述条件的遗传神经网络即建立了输入和输出之间潜在的映射关系,即给遗传神经网络输入一组参数,即可得出对应的测点位移,达到代替有限元计算、节省时间、提高效率的目的。本文在利用遗传算法优化BP神经网络权值及阈值时,选取种群规模N为50,遗传代数为100,交叉概率Pc=0.6,变异概率Pm=0.2。图3为遗传算法训练神经网络的连接权重的过程,从图中可以看出当进化到40代的时候已经趋于稳定,此时误差平方和、适应度值的理论与实际值基本上已吻合,说明BP神经网络的取值与阈值优化完成,满足精度要求。

4.5 目标函数的确定

在优化理论中,一般通过建立目标函数来寻找使遗传神经网络模拟值和实测值之间误差最小的模型参数,其实质就是寻找一组待反演的参数使与其相应的位移值与实测位移值逼近的方法。本文在优化反演计算中,把测点的实测值和遗传神经网络模拟有限元计算值的误差平方和作为目标函数,即:

$F (X) = \sum_{i = 1}^{m} [S_{i} (X) - S_{i}^{*} (X)]^{2} \to \min$

式中:X为本构模型参数;m为反演输出测点数;Si为第i个测点的遗传神经网络模拟输出值;S*i为第i个测点实测沉降值[10]。

4.6 遗传算法优化搜索

在堆石体参数的反演分析中,利用训练好的遗传神经网络代替实际的有限元计算,极大地缩短了反演分析时间,为遗传算法进行堆石体参数的优化搜索提供了便利条件。

遗传算法利用训练好的遗传神经网络模拟有限元计算生成控制测点的沉降值,再与控制测点的实测沉降值比较,不断进化搜索得到最符合堆石体实际变形的参数[11],过程如图4所示。

本文利用遗传算法-遗传神经网络算法对参数进行反演,反演时,遗传算法在给定的初值参数范围内进行随机取值,结果都收敛到相近的数值。图5为遗传算法寻优过程,从图中可以看出,当迭代次数达到70步左右时,遗传算法全局最优值趋于稳定,参数优化完成,具体的反演结果见表2。

4.7 反演参数的验证

为了验证反参数的可靠性,本文利用表2中反演得到的参数进行有限元计算,将坝体0+212断面235 m、265 m、300 m高程处测点实测沉降值与反演参数计算值进行了对比,结果见图6-8。

从图6-8可以看出,通过反演材料参数计算得到的有限元计算结果,跟实测资料的规律大致相同,实测位移值与计算位移值符合较好,满足反分析的计算要求,对于个别点出现误差较大的,可能是由于施工的不均匀性或人为、监测误差等方面的原因所致。

5 总结

本文以水布垭面板堆石坝为工程背景,采用遗传神经网络模拟堆石坝的有限元正分析计算,结合遗传算法建立了面板坝堆石体坝力学参数的位移反演分析模型,并利用反演得到的模型参数进行堆石坝有限计算。结果表明,计算所得的沉降值与实测值吻合较好,误差较小,满足反分析的精度要求,而且利用遗传算法和遗传神经网络算法相结合的方法应用于位移反分析中,既发挥了遗传神经网络的非线性映射、网络推理和预测功能,又利用了遗传算法精度高、收敛快等诸多优点,在解决复杂堆石坝工程位移反分析中具有较好的实际应用价值。

参考文献

[1]苏安安.水布垭面板堆石坝土体参数的位移反演分析[D].北京:清华大学水利水电工程系,2007.

[2]张丙印,袁会娜,李全明.基于神经网络和演化算法的土石坝位移反演分析[J].岩土力学,2005,26(4):547-552.

[3]田明俊,周晶.基于蚁群算法的土石坝土体参数反演[J].岩石力学与工程学报,2005,24(8):1 411-1 416.

[4]张社荣,何辉.改进的遗传算法在堆石体参数反演中的应用[J].岩土力学,2005,26(2):182-186.

[5]闻新,周露,王丹力,等.MATLAB神经网络应用设计[M].北京:科学出版社,2000.

[6]顾永明,张国华.面板堆石坝演化人工神经网络反演分析模型研究[J].西北水电,2007,(2).

[7]陈国良,王煦法.遗传算法及其应用[M].北京:人民邮电出版社,1996.

[8]吴涛.用遗传算法优化神经网络权值[J].广东湛江:湛江师范学院学报,2007,28(2):120-122.

[9]清江水电开发公司.水布垭技术总结[R].武汉:长江勘探设计院.

[10]徐宝松,苗艳东.基于粒子群算法的大坝力学参数反演[J].水力发电,2009,(3):102-104.

遗传算法的综述篇9

教学中的最后一个环节, 也是最能体现学生学习情况、教师授课效果的环节就是考试。但面对各高校每年大量扩招的现状, 考试命题、阅卷等工作越来越繁重, 这无疑使得命题效率、试卷质量、阅卷差错率受到或多或少的影响。同时, 传统命题方式, 可能产生不同教师命题, 内容侧重点、难点有所差异, 无法更客观、公正地反映学生的学习效果及教师的教学质量, 无法对教师的教学改革提供更积极有益的理论指导。因此, 推行无纸化考试, 采用高效智能算法自动生成试题成为对学生考核手段变革的必然。

组卷问题是一个全局寻优的问题, 在寻优过程中需要综合考虑章节 (ch) 、题型 (ty) 、知识点 (Kn) 、难度系数 (Di) 、区分度 (De) 、答题时间 (Ti) 、分数 (Sc) 等各种约束条件。则每道题目可用一个形如: (Ch, Ty, Kn, Di, De, Ti, Sc) 的7维向量描述。设题库中题目数量为n, 则n道题目可用式 (1) 所示的7×n阶矩阵描述。

式 (1) 中:七种参数既可由用户手工输入, 也可利用之前的模板自动产生。试卷生成算法可转化为如何在已有n道题目的题库中选择m道题目, 使这m道题目在章节、知识点、难度系数、区分度等方面满足或最接近用户的需求, 即在该7×n阶矩阵中选则最优的7×m阶子矩阵。

1 传统试卷生成算法

经过20多年的发展, 目前主要采用的试卷生产算法有以下三种:

1.1 随机选取法

根据用户输入的考试要求, 随机从试题库中选取满足条件的试题组成试卷, 直到整份试卷组成或已搜索到题库末尾。该方法具有很大的随机性和不确定性, 无法从整体上把握教学的要求, 不具有智能性[1], 且组卷效率低下。

1.2 回溯试探法

即将随机选取法产生的每一个状态类型记录下来, 当搜索失败时释放上次的状态类型, 再按照一定的变换规律重新选取, 直到满足要求的整份试卷自动生成[2]。

1.3 传统遗传算法

遗传算法 (Genetic Algorithm) 是模拟达尔文进化论的自然选择和遗传学机理的生物进化过程的计算模型, 是一种通过模拟自然进化过程搜索最优解的方法。遗传算法从代表问题可能潜在的解集的一个种群 (Population) 开始, 而一个种群则由经过基因 (Gene) 编码的一定数目的个体 (Individual) 组成。每个个体实际上是染色体 (Chromosome) 带有特征的实体。应用于组卷中, 种群即初始交配池中试卷的集合, 个体即每一套试卷而染色体即组成该试卷的每道试题。传统遗传算法生成试卷的思路如图1所示。

首先按特定方法对试题进行编码, 然后从原始题库中抽取出一定数量的试题生成n份初始试卷, 作为遗传算法的交配池。计算其中每份试题的适应度值, 并按照预先设置好的复制、交叉、变异原则进行相应运算, 衡量适应度值是否满足要求。如果满足则解码生成试卷, 否则继续进行交叉变异等各项运算, 直至适应度值满足要求或达到预先设定好的代数要求为止。

2 基于改进遗传算法的试卷生成算法设计

遗传算法具有内在的并行性, 全局寻优和收敛速度快的特点, 这些都易于处理试题库自动组卷问题[3]。但基于传统的遗传算法的组卷方法易发生早熟、收敛速度慢等问题, 针对这些问题, 魏平等[4]采用稳态策略的单亲遗传算法求解组卷问题, 通过突变算子的引入, 使整个种群保持在最有可能获得成功的状态, 加快算法向全局最优值的逼近速度。王淑佩等[5]提出了一种自适应调整种群适应值分布的基于小生境技术的遗传算法并将之应用于求解组卷问题。

本文采用一种新的基于改进遗传算法的试卷生成算法, 具体设计如下:

2.1 编码设计及初始种群的生成

试题编码采用分组自然数编码方式。按照题型将其分为不同组, 组内采用自然数按照题目录入的先后顺序编码。在系统生成试卷前, 首先需要用户提供期望的难度、章节、及命题蓝图。如:用户期望的试卷难度为0.8, 命题范围为1～6章, 并选用1号命题蓝图, 即:整份试卷满分100, 其中选择题20×2分、填空题10×1分、判断题10×1分、简答题4×5分、程序设计题2×10分。运用石中盘[6]的理论, 根据用户输入的期望难度值自动生成各种难度试题占整份试卷的百分比, 再在遵从章节分配和命题蓝图等约束条件的前提下, 随机生成初始种群。表现形式如表1, 表2所示。

2.2 适应度函数

适应度函数用于衡量个体性能的优略程度, 他的设计对遗传算子有很大影响, 是优化个体的依据[7]。本文采用实际属性值和用户期望值之差作为适应度函数, 差值越小说明个体适应度越高, 越符合用户的期望, 反之, 适应性越低。

试卷难度:Di (x) =Dih-g (x) 。式中:Dih为用户期望的难度系数; $g (x) = (\sum_{i = 1}^{n} a_{i}) / n$ 为当前试卷难度;ai为每道试题的难度。