基于自适应遗传算法的一类非线性规划问题的新算法

基于自适应遗传算法的一类非线性规划问题的新算法（通用7篇）

篇1：基于自适应遗传算法的一类非线性规划问题的新算法

基于自适应遗传算法的一类非线性规划问题的新算法

传统的`方法解答非线性规划问题存在着有进入局部最优、效率低、甚至根本得不出结果的局限性,而遗传算法中用不变的pc和pm来控制进化,很容易导致早熟,降低算法搜索效率.根据适应度自动对交叉概率pc和变异概率pm进行调整,提出一种新的遗传算法.通过对6个测试函数的仿真实验,结果表明本算法是非常有效的.

作 者：高娟 徐裕生 卫龙飞 GAO Juan XU Yu-sheng WEI Long-fei 作者单位：高娟,徐裕生,GAO Juan,XU Yu-sheng(西安建筑科技大学理学院,陕西西安,710055)

卫龙飞,WEI Long-fei(中国第一飞机设计研究院,陕西西安,710089)

刊 名：河北工业科技 ISTIC英文刊名：HEBEI JOURNAL OF INDUSTRIAL SCIENCE & TECHNOLOGY年，卷(期)：26(6)分类号：O221.2关键词：遗传算法 交叉概率 变异概率 适应度函数

篇2：基于自适应遗传算法的一类非线性规划问题的新算法

将自适应收缩可行域的遗传算法与视纵向电导微分成像法相结合,反演瞬变电磁测深中的导电薄层,计算结果证明:该算法通过对可行域的.自适应收缩,加快了计算速度、提高了计算精度;并在一定程度上克服了瞬变电磁测深的等值性,缩小了等值范围.通过对导电薄层模型的模拟计算和实例分析,并与常规反演曲线进行对比,使用本法反演成像的结果,明显地显示出导电薄层的存在.

作 者：李貅 薛国强 宋建平郭文波 武军杰 沈梅芳 Li Xiu Xue Guoqiang Song Jianping Guo Wenbo Wu Junjie Shen Meifang  作者单位：李貅,Li Xiu(西安通大学电子与信息工程学院,陕西,西安,710049;长安大学地质工程与测绘工程学院,陕西西安,710054)

薛国强,宋建平,郭文波,Xue Guoqiang,Song Jianping,Guo Wenbo(西安通大学电子与信息工程学院,陕西,西安,710049)

篇3：基于自适应遗传算法的一类非线性规划问题的新算法

关键词：非线性规划,遗传算法,分层遗传算法

0 引言

非线性规划 (Nonlinear Programming, NP) 是20世纪50年代才开始形成的一门新兴学科, 是运筹学中的重要分支之一, 广泛应用于最优设计、管理科学及系统控制等领域。[1]求解非线性规划解法往往比较复杂且效率较低、或只能搜索到局部最优解, 甚至会找不到最优解。遗传算法 (genetic algorithm, GA) 是在20世纪70年代中期, 由美国Michigan大学J.Holland在他的著作《Adaptation in Natura and Artificial Systems》中提出新兴的智能算法。[2]遗传算法良好的鲁棒性, 在实际应用中被广泛使用, 并有诸多改进形式。本文就基本遗传算法的一种改进形式———分层遗传算法来求解一类非线性规划问题, 实例表明, 该算法具有良好的求解效果。

1 非线性规划问题

现实中诸多问题建立模型都是非线性规划问题, 简单来说例如, 如何在有限的人力、物力、财力条件下合理安排产品生产, 从而达到最高的利润;如何组织货源, 既能满足顾客需要, 又能使得资金周转最快等。这些问题最终都可归结为求解一个带有约束条件的函数极值问题。非线性规划问题通常可描述为如下的模型:

其中f (x) 为目标函数, x为决策变量, gi (x) , hj (x) 分布为x不等式约束和等式约束。求解非线性规划传统的解法有牛顿法、共轭梯度法、制约函数法、可行方向法等, 但这些方法都有效率较低, 容易达到局部最优, 甚至有时找不到解的局限性, 随着智能优化算法的发展, 如遗传算法、蚁群算法、模拟退火等智能优化算法的出现, 这些局限性得到不同程度的改善。

本文考虑一类非线性规划问题:

其中x= (x1, x2, …, xn) T, li和ui为xi的下界和上界。

2 分层遗传算法

遗传算法是基于自然选择原理和模拟生物遗传机制的全局收敛优化算法, 其基本思想是从一个代表最优化问题解的一组初始值开始进行搜索, 这组解称作一个种群, 种群有一定的数量, 通过基因编码的个体组成, 其中每一个个体称为染色体, 不同的个体通过染色体的选择、交叉、变异又生成新的个体, 依照适者生存的规则, 个体经过若干代的进化, 最终得到条件最优的个体。

2.1 简单遗传算法

简单遗传算法 (simple genetic algorithm, 简称SGA) 的运行过程为一个典型的迭代过程, 其必须完成的工作内容和基本步骤如下:

1) 选择编码策略, 把参数集合X和域转换为位串结构空间S;

2) 定义适应值函数f (X) ;

3) 确定遗传策略, 包括选择种群大小n, 选择、交叉、变异方法, 以及根据遗传策略确定交叉概率pc、变异概率pm等遗传参数;

4) 随机初始化生成群体P;

5) 计算群体中个体位串解码后的适应值f (X) ;

6) 按照遗传策略, 运用选择、交叉和变异算子作用于群体, 形成下一代群体;

7) 判断群体性能是否满足某一指标, 或者已完成预定迭代次数, 不满足则返回步骤6) , 或者修改遗传策略再返回步骤6) 。

SGA作为最基本的遗传算法, 在处理不同问题时理论还不是很成熟, 常常会有早熟、不稳定和收敛速度慢等问题出现。本文就是在简单遗传算法的基础上通过分层计算, 改进遗传算法, 使得可以更好地求解非线性规划[3]。

2.2 分层遗传算法

分层遗传算法 (Hierarchic Genetic Algorithm, HGA) , 就是对于同一问题, 首先随机地生成N×n个样本 (N叟2, n叟2) , 然后将它们分成N个子种群, 每个子种群包含n个样本, 对每个子种群独立运行各自的遗传算法, 记作为GAi (i=1, 2, …, N) 。这N个遗传算法最好在设置特性上有较大的差异, 这样就可以为将来的高层遗传算法产生更多种类的优良模式[4]。

在每一个子种群的遗传算法运行到一定代数后, 将N个遗传算法的结果种群记录到二维数组R[1…N, 1…n中, 则R[i, j] (i=1…N, j=1…n) 表示GAi的结果种群的第个体。同时, 将N个结果种群的平均适应度值记录到数组A[1…N]中, A[i]表示GAi的结果种群平均适应度值。高层遗传算法与普通遗传算法的操作相类似, 也可分成如下三个步骤:

(1) 选择。基于数组A[1…N], 即N个遗传算法的平均适应度值, 对数组R代表的结果种群进行选择操作, 一下结果种群由于它们的平均适应度值高而被复制, 甚至复制多次;另一些结果种群由于它们的适应度值而被淘汰。

(2) 交叉。如果R[i, 1…n]和R[j, 1…n]被随机地匹配到一起, 而且从位置x进行交叉 (1燮i, j燮N;1燮x燮n-1) , 则R[i x+1, …n]和R[j, x+1, …n]相互交换相应部分。这一步骤相当于交换GAi和GAj中结果种群的n-x个个体。

(3) 变异。以很小的概率将少量的随机生成的新个体替换R[1…N, 1…n]中随机抽取的个体。至此, 高层遗传算法的第一轮运行结束。N个遗传算法GAi (i=1, 2, …, N) 可以从相应于新的R[1…N, 1…n]种群继续各自的操作。

在N个GAi再次各自运行到一定代数后, 再次更新数组R[1…N, 1…n]和A[1…N], 并开始高层遗传算法的第二轮运行。如果继续循环操作, 直至得到满意的结果。

分层遗传算法的具体流程框架图如图1。

3 数值实验

为了评估所提出的算法性能, 本文选取了以下3个测试函数[5]:

(1) Shubert Function

算法均采取实数编码, 遗传操作算子采取轮盘赌选择, 算术交叉和高斯变异。具体参数选取如下:交叉概率pc=0.4;变异概率pm=0.02;终止迭代次数T=50;优化精度为0.02, 对比SGA和HGA求解结果如表1。

由表1可以看出, HGA求解一类非线性规划问题明显比SGA更接近最优值, 且搜索效率更快。因为传统遗传算法的种群搜索集中于个体适应值差别不大的局部领域, 造成在搜索过程后期, 收敛速度缓慢。

4 结语

为更好更快的求解非线性规划问题, 突破传统遗传算法的缺陷, 尝试使用分层遗传算法求解非线性规划, 利用遗传算法本身的并行性, 低层和高层独立计算, 使得求解问题脱离了易陷于局部最优的情况, 提高进化效率, 且发现非线性规划问题越复杂, 这种分层遗传算法的全局搜索寻优能力越强。

参考文献

[1]应玖茜, 魏权龄.非线性规划及其理论[M].北京:中国人民大学出版社, 1944.

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

[3]邢文训, 谢金星.现代优化计算方法[M].北京:清华大学出版社, 2005.

[4]王小平, 曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社, 2002.

[5]JIN Xi-dong.Solving constrained optimization problems using cultural algorithms and regional schemata[D].Wayne State University, 2001.

[6]XIE Jin-xing.A brief review on evolutionary computation[J].Control and Decision, 1997, 12 (1) .

[7]曹先彬, 许凯, 章洁等.基于生命期引导的生态进化模型[J].软件学报, 2000, 11 (6) ;823-828.

篇4：基于自适应遗传算法的一类非线性规划问题的新算法

[关键词]配送中心：选址；遗传算法；规划；算法设计

中图分类号：1775文献标识码：A文章编号：1009－283(2009)04-0124-01

1配送中心选址规划及算法设计的遗传算法选择

配送中心的选址，是指在一个具有若干供应点及若干需求点的经济区域内，选一个地址设置配送中心的规划过程。较佳的配送中心选址方案是使商品通过配送中心的汇集、中转、分发，直至输送到需求点的全过程的效益最好。

在配送中心选址的定量方法中，主要有重心法及鲍摩一瓦尔夫模型的应用，但他们在求解时都存在缺点，如重心法中，因自由度过多，迭代计算非常复杂，最佳地点实际上很难找到；鲍摩一瓦尔夫模型因采用逐次逼近法，不能保证必然会得到最优解，并且在求出的解中，可能出现配送中心数目较多的情况，而且配送中心的固定费用没在所得的解中反映出来。

遗传算法(Genetic Algorithm)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的基本思想是建立在自然选择和群体遗传学机理基础上的随机、迭代、进化。具有广泛适用性的概率搜索方法，通过模拟生物进化中“优胜劣汰、适者生存”的规律，进行编码与进化寻优。

实践表明，遗传算法在求解配送中心地址模型时可以取得较好的效果，因此，本文采用遗传算法的思想对配送中心选址规划进行描述及算法设计，为使用遗传算法求解配送中心地址模型提供一些参考。

2遗传算法下配送中心选址规划的一般描述

为了能够将遗传算法应用于配送中心选址问题，必须对其进行数学的抽象。可以将通常情况下的配送中心选址规划问题抽象为以下几个方面：

规划区域表示

将具体的规划区域抽象为一个矩形，根据实际需要的规划精度将矩形区域分割成为mxn的矩形单元格，每一个矩形单元格代表一个与实际物流情况近似的地理区域。用s(i，j)表示规划区域中的第i行、第j列的一个矩形单元格，配送中心可以设置在任一个矩形单元格内。

物流需求经济效益

用B(i，j)表示单元格s(i，j)在满足其物流需求的基础上所产生的经济效益，它是指单元格对物流活动结果进行生产消费和生活消费后产生的社会经济效益。配送中心的修建成本

修建配送中心的成本与当地的地理情况和经济情况有很强的相关性，在不同区域修建配送中心代价是不相同的。在模型中用c(i，j)表示s(i，j)区域修建—个标准配送中心所需的费用

单元格物流需求量

在模型中，用Q(i，j)表示—个单元格s(i，j)的物流需求量。表示该区域在一定时期内对物流服务的需求量。单元格的物流需求量由该区域的人口密度、经济状况、产业结构等因素所决定。

单位物流成本

在模型中，用F(s(i，j)。s(k，1))表示从区域s(i，j)到区域s(k，1)的单位物流成本，并且只定义相邻区域之间的运输成本，非相邻区域的单位物流成本通过多个相邻区域的单位物流成本的叠加累计得出，在规划配送中心时应该使运输成本最小。

配送中心的配送范围

从经济角度和实际运输工具的运送范围来考虑，配送中心的覆盖范围不可能无限大。在时间情况中，考虑到配送中心之间的分工合作，每个配送中心都会有一定的覆盖范围。用A(i，j)表示设置在区域s(i，j)的配送中心的配送区域，其配送范围可以表示为：从点(i－k，j－k)到点(i+k，i+k)(k为自然数)的一个长方形区域，每个候选点的配送范围可以相同也可以不同，如果i－k<0或j－k<0，则说明其遇到了边界，无意义。

配送中心选址模型的规划目标

在规划区域内选取几个单元格作为配送中心的设置点，使规划区域内的物流需求经济效益减去物流成本达到最大。

3配送中心选址模型的遗传算法设计

对配送中心选址模型的求解进行遗传算法设计是寻找出最优解的重要保证，遗传算法作为一种通过模拟自然进化过程搜索最优解的方法，在求解配送中心地址模型时可以取得较好的效果，本文对算法设计如下：

①前提假设

配送中心能够满足任意数量的物流服务需求；

在规划区域中处于相同划分区域的物流属性相同；

配送中心到物流需求点的配送时间可以忽略不计；

模型中不考虑库存。即在“零库存”的情况下进行的，并且物流需求产生时能够立即送货。

②配送中心规划方案的解表达方式

用一组长度为m×n的二进制数串来表示一种布局方案，第k个数表示s((k／n)+1，modle(k／n))的单元格为候选的配送中心。在模型中，用P(i，j)=l表示s(i，j)被设置为候选配送中心点，P(i，j)=0表示s(i，j)没被设置为候选配送中心点。

例如：{1，0，0，1，1……0，1，1}表示P(1，1)=l，P(1，2)=0，P(1，3)=0……

③依据配送目标确定配送中心规划方案的评价函数

④选择算子，采用比例选择算子，即每个个体以与适应度大小成正比的概率被选中遗传到下一代。

⑤交叉算子，采用单点交叉算子，即在个体编码字符串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。

⑥变异算子，采用编码字符串范围内的均匀随机变异，即分别用符合某一范围内均匀的随机数，以某一较小的概率来替换个体编码字符串中各个基因座上的原有基因值。

篇5：基于自适应遗传算法的一类非线性规划问题的新算法

OFDMA (正交频分多址接入) 是在O F D M (正交频分复用) 基础上发展起来的一种无线接入方式, 它的资源分配机制可根据用户业务量的大小动态分配子信道的数量, 己成为无线通信系统的关键技术[1]。OFDMA系统中的资源分配问题一直是人们的研究热点, 其中大都是基于物理层的资源分配算法, 而这类算法没有考虑决定用户服务质量 (Quality of Service, 以下简称Qo S) 的MAC层 (介质访问控制层) 。为了更好地满足用户的Q o S要求, 基于P H Y (物理层) 与M A C层相结合的跨层资源分配算法相继出现[2,3,4], 但这些算法仍存在计算量大, 公平性差的缺点。为此, 有学者提出了基于遗传算法的跨层资源分配算法[5], 该算法在降低计算复杂度的同时, 有效地提高了系统的性能并兼顾了用户间的公平性。但由于遗传算法本身固有易陷入局部最优的缺点, 使得它不能每一次都获得较好的资源分配方案。

自适应遗传算法是在遗传算法基础上提出的一种改进算法。该算法全局搜索能力强, 具有自适应性, 且与遗传算法相比, 不易陷入局部最优。为此, 借鉴基于遗传算法的跨层资源分配算法, 本文提出了基于自适应遗传算法的跨层资源分配算法, 利用该算法良好的寻优能力解决O F D M A系统跨层资源分配问题。

2 OFDMA系统PHY层与MAC层联合优化的系统模型

本文研究O F D M A系统下行链路的跨层资源分配问题, 其系统模型如图1所示。设系统有K个用户, 系统带宽被划分成N个子载波, 每帧由S个符号组成, 在发送每一数据帧前, 建立用户队列状态信息, 调度算法根据分组调度准则决定用户k的缓存中待发送的比特信息Qk (bit) , 且每个用户待发送的数据存储在相应的列队中, 并始终保持先进先出原则, 设每个数据包的最大等待时延为T。发送端通过列队状态信息及每个用户在所有子载波上的瞬时信道衰落信息为每个用户分配相应的子载波, 功率及比特。

定义Rk为用户k在第S个符号内发送的比特, ck, n表示第k个用户分配到第n个子载波上的比特数量, 其取值范围为ck, n∈{0, 1, 2, ..., U}, U为每个子载波上每个O F D M符号内允许传输的最大比特数, 并引入一个在[0, 1]内取值的变量ρk, n, 表示第k个用户占用第n个子载波的概率, 令Rk, n=ρk, n⋅ck, n。hk, n表示第k个用户在第n个子载波上的信道增益, pk, n为每个子载波上所分配到的发射功率, pe为用户的误码率, 由于自适应功率分配对系统整体性能的提高很有限, 因此各个子载波上的功率平均分配[6]。假设每个子载波采用Q A M (正交幅度调制) 调制方式, 根据Q A M误比特率调制方式, 每个子载波在第S个符号上所能承载的比特数可表示为[7]:

其中, σ2为信道噪声方差, σ2=N 0B/N, N0为噪声功率谱密度。在某一帧内, 用户k在第n个子载波上承载的总比特数可表示为[5]:

本文通过物理层与M A C层联合优化, 将分组调度算法和子载波分配算法有效的结合, 尽可能提高系统吞吐量, 以满足通信系统实时性的要求, 故本文采用的效用函数为所有用户发送的比特信息之和, 其数学表达示为:

由用户k在缓存中等待发送的比特信息Qk及该用户的传输速率Rk, 可得用户k的平均等待时延Tk为:

其中, Tk是保证用户Qo S的一个重要指标。从表达示⑷可以看出, 当Qk一定时, Rk越大, 用户k的平均等待时延Tk就越小, 且整个系统的效用函数值, 即表达式⑶就越大。而Rk正是由每个用户的列队信息Qk及每个用户在每个子载波上的信道状态hk, n所决定的。因此, 想要求得效用函数的最大值和每个用户平均等待时延的最小值, 需要应用寻优的数学方法寻找一组最优的子载波分配方案。本文利用寻优能力较强的自适应遗传算法解决此问题。

3 自适应遗传算法的基本原理

自适应遗传算法是任子武等人[8]在2006年提出的一种改进的遗传算法。该算法在遗传算法的基础上, 通过每个染色体适应度的大小自适应的调整交叉概率和变异概率来改善遗传算法易陷入局部最优的缺陷。

在自适应遗传算法中, 最关键的交叉和变异概率调整为[8]:

其中, pc1, pc2为交叉概率, pm1, pm2为变异概率。一般情况下, pc1=0.9, pc2=0.6, pm1=0.1, pm2=0.01。favg为种群的平均适应度, fmax为种群的最大适应度, f’是要进行交叉操作的两个染色体中较大的适应度值, f是要进行变异操作染色体的适应度值。

从公式⑸和公式⑹中可以看出, 自适应遗传算法随着染色体的适应度值相应的改变交叉概率和变异概率, 当染色体适应度较小时, 其交叉和变异概率较大, 使之向着更好的方向发展;反之, 若染色体适应度较大, 其交叉和变异概率相对较小, 以保持个体的优良特性, 且种群中最大适应度个体的交叉概率和变异概率不为零, 这就相应地提高了种群中表现优良个体的交叉概率和变异概率, 使得它们不会处于一种停滞不前的状态, 从而使算法跳出局部最优解。自适应遗传算法流程图如图2所示。

4 基于自适应遗传算法的跨层资源分配算法的实现

O F D M A系统中的资源分配问题属于复杂的优化问题, 本文引入自适应遗传算法, 根据每个用户在每个子载波上hk, n的大小找到一组子载波分配方案, 使得整个系统的效用函数值最大, 既得到了合理的跨层资源分配, 又有效避免了陷入局部最优, 其算法的具体实现过程如下:

⑴初始化:设定算法终止条件, 初始群体规模M, 每个染色体含有的基因数为子载波个数N, 交叉概率pc1, pc2, 变异概率pm1, pm2。

⑵编码:由于随机产生的初始群体会使最优资源分配方案的质量下降, 且搜索到最优解的可能性较小, 因此, 本文通过如下方式获得初始种群:

其中Lk为用户k的平均业务量。

从前面的理论分析可知, 当每个子载波所分配的发射功率一定时, hk, n越大, 子载波上所能发射的比特信息就越多, kQ与kL之比相当于用户k的平均等待时延。因此, 该种群的产生方式更好的满足了用户间的公平性, 且平均等待时延较大的用户可分配到信道条件好的子载波以发送比特信息。

设系统有K个用户, 系统带宽被分为N个子载波, 则每个染色体由N个基因组成, 且每个基因为1~K之间的某个数, 表示第n个子载波分配给第k个用户, 则某一染色体可表示为如下形式:

其中, 该染色体表示第一个子载波分配给用户1, 第二个子载波分配给用户3, 第三个子载波分配给用户4, 依次类推。

通过该方案得到的染色体M1虽是优秀的但却是唯一的。为保证群体多样性, 且使群体向着更好的方向收敛, 则对于其它染色体的每一个基因, 以概率p0保留染色体M1相对应的基因, 以概率1-p0随机产生一个1~K之间的一个整数, 以代替原基因。为使整个群体具有多样性, 引入继承概率p0, 通常情况下, p0∈[0.1, 0.3]。

⑶计算适应度函数:将效应函数作为适应度函数, 根据每个用户分配到的子载波集合, 按公式⑴计算每个用户在每个子波上所发送的信息量, 并根据公式⑶计算适应度函数, 即在一帧中, 所有用户在所有子载波上发送的信息总和。并计算出群体的平均适应度, 找出群体中适应度的最大值和最小值。

⑷选择操作:按照“适者生存、优胜劣汰”机制, 将适应度最小的染色体替换成适应度最大的染色本。

⑸交叉操作:从染色体中随机选出相邻的两个染色体进行交叉配对, 在1~N之间, 随机选取一个交叉点, 并根据交叉概率⑸对选取的一对染色体进行交叉操作, 配对个体在交叉位置处相互交叉各自的内容, 从而形成一对新的染色体。

⑹变异操作:从群体中随机选出要进行变异操作的染色体, 随机对其某个基因按变异概率⑹对其进行基因变异操作, 并以随机产生1~K的值作为新的基因。

⑺由选择, 交叉, 变异操作后得到了一个新的群体。

⑻重复步骤⑶-⑺, 直到满足终止条件, 算法结束。

5 实验仿真与结果分析

为了验证本文提出的算法的性能, 这里进行了仿真实验, 并与目前解决资源分配问题效果最好的基于遗传算法的资源分配算法[5]进行了比较。仿真实验环境是在CPU为AMD公司生产的Sempron2600+, 其主频为1.6GHz, 计算机内存为768MB的计算机上运行的。程序采用MATLAB R2008b版本编写。

OFDMA系统仿真实验条件:Rayleigh衰落信道, 噪声功率谱密度N0=1, 子信道增益Eα2k, n=1, OFDMA系统中子载波个数N为128, pe=10-6, 系统总的传输带宽为0.78125MHz, 每20个OFDM符号组成一帧, 系统采用自适应Q A M调制方式, 每个子载波上每个O F D M符号内允许传输的最大比特数U为6。且系统中有K=4个用户, 每个用户M A C层数据包到达服从Possion分布, 每个数据包长度Q为2 0 0比特, 数据包的最大等待时延T设为40ms。假设每个用户的SNR (平均信噪比) 都一样, M A C层每个用户的平均业务量分别为1.3Mbps, 1.4Mbps, 1.5Mbps, 1.6Mbps。

本文采用的自适应遗传算法的终止条件为达到最大迭代次数500, 种群规模M=100, 种群中所含的基因数设定为子载波的个数N=128, 继承概率p0=0.1, 交叉概率pc1=0.9, pc2=0.6, 变异概率pm1=0.1, pm2=0.01。

本实验从最大效用函数和平均等待时延两个方面来验证基于自适应遗传算法的资源分配算法效果。图3为O F D M A系统存在4个用户, 每个用户的S N R均为29d B时, 基于遗传算法的资源分配算法和本文提出的改进算法的收敛曲线。从图中可以看出, 在迭代次数相同的情况下, 本文提出的改进算法能获得更大的效用函数值, 即在发射功率一定的条件下, 可发射更多的比特信息, 且从图中可以看出, 当达到一定的迭代次数时, 基于遗传算法的资源分配算法的效用函数值没有显著的提升, 而本文提出的改进算法随着迭代次数的不断增加, 效用函数值有明显提高, 最终收敛于全局最优解, 即用户发送的总信息量。本文提出的改进算法的搜索能力较基于遗传算法的资源分配算法强, 有效的提高了系统的频谱利用率及吞吐量。

图4为基于遗传算法的资源分配算法和本文提出的改进算法在不同S N R下的用户数据包平均等待时延曲线。

从图中可以看出, 在相同SNR下本文提出改进算法的用户数据包平均等待时延小于基于遗传算法的资源分配算法, 这主要是由于本文提出的改进算法在相同的时间内可发送更多的比特信息, 即传输速率较快, 所以用户所需的平均等待时延较小。由此从两个方面可以看出本文提出的改进算法其性能要高于基于遗传算法的资源分配算法。

6 结束语

本文提出一种基于自适应遗传算法的跨层资源分配算法, 利用该算法全局搜索能力强来获得O F D M A系统中最优的资源分配方案。实验结果表明, 本文提出的改进算法与基于遗传算法的资源分配算法相比, 在满足用户间公平性的前提下, 可以进一步提高系统的频谱利用率及吞吐量, 且减小了用户的平均等待时延, 是一种行之有效的资源分配算法, 在无线通信系统中具有一定的实际应用价值。

参考文献

[1]胡成, 邱玲.多小区OFDMA系统一种跨层资源分配方法[J].计算机仿真报, 2008, 25 (5) :93-96.

[2]G SONG, Y LI LJCIMINI JR andH ZHENG.Joint channel-aware and queue-aware data scheduling in mul-tiple shared wireless channels[C].IEEE Wireless Commu-nications and Net-working Conference, 2004, pp1939-1944.

[3]WEI CHEN, PINGYI FAN, ZHIGANG CAO.Waterfilling in cellar:the optimal power allocation policy with channel and buffer state information[J].IEEE International Conference on Communications, 2005, (1) :537-541.

[4]ANDREWS M, KUMARAN K, and RAMANAN K, et al..Providing quality of service over a shared wirelesslink[J].IEEE Communications Magazine, 2001, 39 (2) :150-154.

[5]郁宇.OFDMA系统中基于遗传算法的联合优化设计[D].合肥:中国科学技术大学, 2007.

[6]W.RHEE, J.M.Cioffi.Increasing in capacity ofmulti-user OFDM system using dynamic sub-channelallocation[J].IEEE Vehicular Technology Conference Proceedings, 2000, (2) :1085-1089.

[7]MOHAMMAD TORABI, M.REZA SOLEYMANI.Adaptive Bit Allocation for Space-time Block Coded OFDM System[J].IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003, (4) :409-412.

篇6：基于梯度的自适应量子遗传算法

以量子算法为代表的量子计算由于具有指数级存储容量、高度的并行性和对经典启发式算法的指数加速作用, 因而在计算复杂度、收敛速度等方面明显超过常规算法。将量子计算机制引入现有进化算法可以在很大程度上提升算法的各项优化性能。目前, 量子计算与进化算法的融合研究主要集中于进化策略的构造和编码方式。在量子进化算法中, 个体采用量子位概率幅编码, 用量子非门代替个体变异以实现群体的多样性, 用基于量子门的量子比特相位旋转实现个体进化。

本文根据量子计算原理, 对量子旋转门转角的确定方法做了改进研究, 提出了一种考虑目标函数梯度的自适应计算方法, 并对基于该方案的改进量子遗传算法进行了数值模拟。

1基本量子遗传算法

2000年, K.H.Han等人将量子的态矢量表达引入到遗传算法的编码中, 利用量子旋转门实现染色体基因的变换, 提出了第一种量子遗传算法 (Quantum Genetic Algorithm, QGA) , 并通过一类组合优化问题验证了算法的有效性。

QGA是基于量子叠加态和量子位的概念提出的。量子比特或量子位是量子计算中的最小信息单位。一个量子位可以处于|0〉态、|1〉态以及|0〉态和|1〉态之间的任意叠加态。一个量子位的状态可以描述为:

其中α, β为复数, 称为量子位对应态的概率幅。|α|2表示量子态被观测为|0〉态的概率, |β|2表示量子态被观测为|1〉态的概率, 且满足归一化条件:

如果一个系统有个量子位, 则该系统可同时描述2m个状态, 然而在观测时, 该系统将坍缩为一个确定的状态。

传统进化计算的染色体编码通常有3种方式:二进制、十进制、符号编码。在QGA中采用基于量子位的编码方式, 一个量子位可由其概率幅定义为undefined, 同理, m个量子位可定义为:

其中, |αi|2+|βi|2=1, i=1, 2, …, m。 这种描述的优点在于可以表达任意量子叠加态。

量子遗传算法的伪代码如下:

与GA相似, QGA也是一种全局性概率搜索算法, 它包括一个群休Q (t) ={qundefined, qundefined, …, qundefined}。其中, t表示进化代数, n是群体规模, qundefined为所谓量子染色体, 其定义为:

其中, m为量子位数, 即染色体的长度, j=1, 2, …, n。

2基于梯度的改进量子遗传算法

量子遗传算法中的关键技术之一是如何计算量子旋转角的方向和大小。迄今为止, 大多数已有的量子遗传算法均采用基于查询量子旋转角表的方法。这种算法要进行多路条件判断, 所以算法的效率不高。有些学者提出了一种基于自适应的确定转角的方法, 使迭代步长随着进化代数的增加而逐渐减小。不过, 此方法没有充分考虑各个染色体个体间的差别, 而对全部个体一视同仁。

本文提出了一种考虑目标函数梯度的量子旋转门转角的自适应计算方法, 并据此给出了一种改进的量子遗传算法GQGA。

2.1编码方案

在GQGA中, 根据量子位上对应的概率幅来编码。考虑到初始群体编码的随机性及量子态对应的概率幅要遵循的约束条件, 可采用双链编码方案:

其中, n为量子位数, m为群体规模, tij=2π×rand, rand为介于0和1之间的随机数。在GQGA中, 把每个量子位上的概率幅视为两个上下并列的基因, 每条染色体都包含并列的两条基因链, 而每条基因链即表示一个最优解。从而, 每条染色体便可以同时搜索寻解空间中的两个最优解:

其中, i=1, 2, …, m, Pis称为“正弦”解, Pic称为“余弦”解。这种处理方法的好处在于既避免了十进制与二进制的相互转换过程, 也避免了因测量而导致的随机误差。由于在每次的迭代过程中正弦和余弦解同时更新, 所以在群体规模保持不变的条件下, 可以增强对于解空间的搜索遍历性, 提高优化速度。同时, 还可以增加全局最优解的数量, 提高全局收敛性的概率。

2.2量子旋转门转角的确定

GQGA用于更新量子比特相位的量子旋转门为:

更新过程为:

undefined

确定量子旋转门转角大小的方法是:将目标函数在某个染色体处的变化趋势信息适当添加到转角步长的计算函数中。当目标函数在搜索点处变化率较小时, 适当增加转角步长, 否则适当减小转角步长。这样既保证了收敛速度, 又兼顾了全局收敛性。根据上述思想, 可构造转角步长函数如下:

undefined

其中, Δθ0为迭代初值, ∇f (Xundefined) 为目标函数f (X) 在点Xundefined处的梯度, A、∇fjmax和∇fjmin分别定义为:

undefined

α0和β0是迄今搜索到的全局最优解中的某个量子位的概率幅, α1和β1是当前最优解中对应量子位的概率幅。

2.3算法描述

实现上述梯度量子遗传算法的伪代码如下:

步骤1:初始化种群。根据 (5) 式生成由m条染色体构成的初始种群, 设初始转角步长为θ0, 变异概率为pm。

步骤2:变换解空间。把每个染色体表示的近似解, 从单位空间In=[-1, 1]n映射到解空间Ω, 算出每个染色体的适应度。记当前最优解为X0, 相应染色体为P0, 当代最优解为X0, 相应的染色体为P0。若fit (X0) >fit (X0) , 则P0=P0。

步骤3:对群体中的所有染色体上的每个量子位, 用P0中对应的量子位为目标, 根据“2.2”中的方法计算转角大小及方向, 采用量子旋转门确定新的量子位。

步骤4:对群体中的每个染色体, 根据变异概率用量子非门进行变异。

步骤5:转至步骤2, 直至达到最大进化代数或满足收敛条件为止。

3数值实验

下面选取两个常用的标准测试函数进行数值模拟计算, 并将计算结果与基本量子遗传算法CQGA和一般遗传算法CGA进行对比分析, 以检验上述算法的有效性。

(1) Shaffer’s F5函数。

其中, xi∈ (-65.536, 65.536)

undefined

该函数有多个局部极大值点, 最大值点为 (-32, -32) , 最大值为1.002。若目标函数值大于1.000, 则理解为算法收敛。Shaffer’s F5函数的图像如图1所示。

(2) Shaffer’s F6函数。

该函数有无穷多个局部极大值点, 但其中只有 (0, 0) 为全局最大值点, 最大值为1。自变量的定义域均为 (-100, 100) 。当优化结果大于0.995时认为算法收敛。该函数的图像如图2所示。

算法参数:种群规模m=50, 量子位数n=2, 交叉概率pc=0.8, 变异概率pm=0.1, 转角步长初值θ0=0.01π, Shaffer’s F5限定代数Lmax=200, Shaffer’s F6限定代数Lmax=500。在CQGA中, 编码长度取为20, 即每个染色体包含40个量子位, 适应度函数即取为目标函数。

对于上述两个测试函数, 分别用GQGA、CQGA、CGA进行10次计算, 优化结果见表1、图3和图4。

从表1、图3和图4中可以很清楚地看出, 基于梯度的改进量子遗传算法GQGA在优化精度、计算速度、收敛性等方面均明显优于普通量子遗传算法CQGA和普通遗传算法CGA, 这主要得益于考虑了目标函数的梯度以及确定量子旋转门转角的自适应机制。

摘要：根据量子计算原理, 提出了一种量子旋转门转角的自适应确定方案。该方案的基本思想是在设计量子旋转门转角大小时, 充分考虑目标函数的梯度, 当目标函数变化率较小时, 适当增加转角步长, 反之适当缩小转角步长。数值计算结果表明, 基于该方案的改进量子遗传算法比基本量子遗传算法有更佳的全局收敛性和更快的收敛速度。

关键词：量子遗传算法,目标函数梯度,量子旋转门转角

参考文献

[1]SHOR P W.Algorithms for quantum computation[C].DiscreteLogarithms and Factoring.Proc.of the 35th Annual Symp, 1994.

[2]GROVER L K.A fast quantum mechanical algorithm for databasesearch[C].Proc.of the 28th Annual ACM Symp, 1996.

[3]NARAYANAN A, MOORE M.Quantum-inspired genetic algo-rithms[C].Proceedings of IEEE International Conference on Evo-lutionary Computation, 1996.

[4]HAN K H, KIM J H.Genetic quantum algorithm and its applica-tion to combinational optimization problem[C].Proceedings of theInternational Congress on Evolutionary Computation, 2000.

[5]TALBI H, DRAA A, BATOUCHE M.A new quantum-inspiredgenetic algorithm for solving the traveling salesman problem[C].Proceedings of the International Conference on Industrial Technol-ogy, 2004.

[6]KHORSAND A R, AKBARZADEH M R.Quantum gate optimi-zation in a meta-level genetic quantum algorithm[C].2005IEEEInternational Conference on Systems, Man and Cybernetics, 2005.

[7]MOORE P, VENAYAGAMOORTHY G K.Evolving combina-tional logic circuits using a hybrid quantum evolution and particleswarm inspired algorithm[C].Proceedings of the 2005NASA/DoDConference on Evolvable Hardware, 2005.

[8]DREO J, SIARRY P.An ant colony algorithm aimed at dynamiccontinuous optimization[J].Applied Mathematics and Computa-tion, 2006 (1) .

[9]ZHANG G X, LI N, JIN W D.A novel quantum genetic algorithmand its application[J].ACTA Electronica Sinica, 2004 (3) .

篇7：基于自适应遗传算法的一类非线性规划问题的新算法

入侵检测(Intrusion detection)是通过对系统数据的收集与分析,发现未经授权的攻击行为和网络访问,从而为网络安全提供有力的保障[1]。目前入侵检测智能性研究成为热点,这主要是因为智能优化算法、神经网络、模式识别等技术的引入[2]。例如刘永忠等[3]提出了一种基于模糊粗糙集的特征加权聚类算法(FRS-FCM),该方法能有效提高入侵检测的检测准确率,降低误检率,并较大地提高低频攻击的检测率。朱红萍等[4]提出一种基于遗传算法的入侵检测特征选择算法。该算法在保证特征分类精度和确保入侵检测漏检率、误检率尽量小的前提下明显提高了入侵检测的效率。胡明霞等[5]通过遗传算法找到BP神经网络的最适合权值,解决直接使用BP学习造成的训练样本数量过大而难以收敛的问题,与传统网络入侵检测算法相比,该算法的训练样本时间更短,具有较好的识别率和检测率。

智能算法、神经网络、模式识别等技术具有自适应(Self-adaptation)、自学习(self-learning)的能力,可以通过自适应、自学习从中提取正常的系统或用户活动特征模式,并检测出异常活动的攻击模式[6,7,8]。这些特性使得上述方法在入侵检测系统中得到了很好的应用[9,10]。遗传算法(Genetic Algorithm,GA)是一种全局启发式搜索 ,属于人工智能的进化计算分支[11]。现基于此提出一种基于遗传算法的入侵检测方法,该方法用自适应的适应度函数、交叉概率及变异概率取代固定的适应度函数、交叉概率及变异概率来改进遗传算法。

1 遗传算法简介

按照达尔文(Darwin)的进化论,地球上的任何一种生物从诞生开始就进入漫长的进化阶段。期间必存在生存斗争,生存能力强的个体存活下来比较容易,并有较大的机会产生后代;具有较弱生存能力的个体则较容易被淘汰,或者有较低的概率产生后代,直至渐渐消亡。

遗传算法主要就是根据达尔文的进化论以及孟德尔和摩根的遗传学理论而提出的一种基于生物进化机制的全局性概率搜索算法。可用于解决很多应用领域的问题。遗传算法用编码空间代替问题的参数空间,以适应度函数作为一个评价依据,依据一定的概率p重组编码位串,从而生成新一代的编码,群体中的个体不断得到优化,逐渐接近最优解,从而最终达到求解问题的目的。习惯上把Holland于1975年提出的遗传算法称为传统的遗传算法。其主要步骤如下[12]:

1) 给定群体规模N,交配概率Pc和变异概率Pm;

2) 随机生成一个N个初始解组成的初始群体;

3) 计算当前初始群体各染色体x的适应度函数值F(x);

4) 如果满足停止准则,则转10);

5) 对群体中的每一个染色体x计算概率p(x);

6) 依据概率值从群体中随机选择N个染色体,得到种群;

7) 依交配概率Pc按交叉算子进行交配,其子代进入新的群体,未进行交配的染色体直接复制到新群体中;

8) 依变异概率Pm从种群中选择染色体按变异算子进行变异操作,用变异后的染色体代替新群体中的原染色体;

9) 用新群体代替旧群体,代数加一,转3)

10) 进化过程中适应值最大的染色体,经解码后作为最优解输出;

11) 结束。

计算过程用流程图表示如图1。

2 自适应遗传算法设计与应用于入侵检测

2.1 基于GA的入侵检测模型

基于GA的入侵检测模型如图2所示。

2.2 自适应遗传算法

2.2.1 适应度函数

适应度函数在遗传算法中表示个体接近最优解的程度,因而要求设计的适应度函数保证适应度非负。在进化的初期,可能出现个别适应度很高的个体(接近或是局部最优解),而大多数个体适应度还很低,因此这样的个体被选择的概率远高于其它个体,可能充斥下一代群体,使得进化难以继续,出现早熟现象;而在进化的后期,群体中个体的适应度相近,较好的个体和较差的个体被选择的概率差不多,会使得进化缓慢,从而降低收敛速度。为解决这个问题,本算法采用适应度的差值衡量适应度的差异大小,具体定义为

$\begin{array}{l}\beta =\Delta f/\Delta F(1)\\ \Delta f=f{}_{\max }-f{}_{\min }(2)\\ \Delta F=F{}_{\max }-F{}_{\min }(3)\end{array}$

其中,ΔF为适应度的理论最大差值,Δf为本代群体适应度的差值,fmax为本代群体适应度的最大值, fmin为本代群体适应度的最小值, Fmin为适应度的理论最小值,Fmax为适应度的理论最大值,可知β的取值范围为[0,1]。 如果采用适应度和平均适应度的差值的绝对值的平均值、差值的平方的平均值(即方差)等衡量,虽然更准确,但计算更繁琐,将影响运算速度,且最大平均值不好计算,以致与平均值的比值的取值范围(后面将要用到)难以确定。根据β对适应度进行变换

$f^{\prime }(x)=f(x)+k(\beta -0.5)(4)$

式(4)中,k是常数,f(x)为变换前的适应度,f′(x)为变换后的适应度,根据具体情况设置, 越大则变换力度越大,但要尽量保证个体的适应度非负。

当群体中个体的适应度差异较大时 (β>0.5),个体的适应度都增大 k(β-0.5),但适应度 小的个体增长的比例大,被选择的概率增大,有利于保持群体的多样性,以向更广的解空间搜索,避免陷入局部最优;当群体中的个体适应度差异较小时 (β<0.5),个体的适应度都减小k(0.5-β)(这时个体的适应度普遍较大,减少后应仍非负,如果有个别个体适应度太小,减少后为负,可补充定义为 0(意味着将其淘汰)或某个较小值(以增强群体的多样性)),但适应度大的个体减少的比例较小,被选择的概率增大,增加了搜索的导向性,避免盲目搜索。

2.2.2 变异概率

传统GA的变异概率是固定的,现采取动态的方式灵活调整,具体方法如下:当染色体个体差异较小时,应使得变异概率增大,这样能保持群体的多样性,以便向更广的解空间进行搜索,避免陷入局部最优。当个体差异较大时,应使得变异概率减少,达到减少计算量并保证群体的多样性。因此定义变异概率

${\rm P}{}_{\text{m}}=0.2(1-\beta )(5)$

因为变异运算也会破坏好的个体,变异概率一般取值较小(在生物进化中也较小),所以乘以0.2。可知Pm的取值范围为[0, 0.2]。

2.2.3 交叉概率

标准遗传算法的交叉概率是固定的,并不能很好体现变异的作用。在进化的初期,应增大交叉概率,这是因为初期个体差异较大,交叉产生更好个体的概率也较大;在进化的后期,个体差异较小 (相 当于“近亲结婚”),交叉产生更好个体的可能性也较小,应减小交叉概率,减少计算量。因此定义交叉概率如下:

${\rm P}{}_{\text{c}}=\beta (6)$

可知 Pc的取值范围为[0,1]。

3 对比实验与分析

在对比实验中,采用经典的KDD’1999数据集,该数据集包含DOS、PROBE、R2R、U2R等攻击类型数据[13]。

图3为遗传算法的误差平方和曲线和适应度曲线,图4为本文自适应遗传算法误差平方和曲线和适应度曲线,从图4可以看出大约经过了400迭代的搜索后染色体的平均适应度趋于稳定,收敛时间为11.413 seconds,误差为0.039。从图3可以看出在标准的GA中,大约经过500次迭代搜索后染色体的平均适应度将逐渐趋于稳定,收敛时间为13.987 seconds,误差为0.089。从表1中可以看出,本文提出的方法和遗传算法相比较,在检测时间方面,本文提出的方法则是表现最好的,入侵检测准确率明显高于上述算法,并且区别很明显。对不同类型的攻击检测具有良好的均衡性,并且能保证较高检测率。

4 结束语

提出一种基于改进的遗传算法-自适应遗传算法的入侵检测方法,算法显著提高了收敛性能,并且具有很强的自适应能力,并在保证较高检测率的基础上,对不同类型的攻击检测具有良好的均衡性。