遗传优化搜索算法

遗传优化搜索算法（精选12篇）

遗传优化搜索算法 第1篇

1 基本算法简介

1.1 遗传算法

遗传算法的思想是:首先将代表问题的解用染色体编码, 形成种群, 再通过适应度函数计算每个个体的适应性, 按照适者生存、优胜劣汰的原理, 在每一代选择性能优异的个体, 对其使用交叉、变异算子, 产生新种群。交叉操作交换两个染色体的一部分, 变异操作改变染色体上某个随机位置的基因值。经过多次重复迭代, 适应性较弱的个体被淘汰, 适应性强的则统治种群, 最终生成符合优化目标的染色体, 获得问题的近似最优解。

多种群可拓宽搜索空间, 增加群体多样性。多样性是遗传算法必不可少的本质属性, 这是因为它能使遗传算法搜索一个比较大的解的空间区域。采用最优个体保留策略, 每一次的演化过程中, 子代总是保留了父代种最好的个体, 以在“高适应度模式为祖先的家族方向”搜索出更好的样本, 从而保证最终可以搜索到全局最优解。

1.2 模式搜索法

模式搜索法 (Pattern Search, PS) 是一类求解优化问题的方法, 无需事先知道关于待优化函数的梯度信息。PS可以找到一个点序列x0, x1, x2, ..., 它们逐渐逼近理想点, 利用发现的函数变化规律沿着有利方向寻找更好的点, 即模式本身自适应调整[6]。算法流程为如下:

(1) PS算法根据问题的变量, 确定模式向量集{V}i。

(2) 根据模式向量集生成网格 (mesh) 。网格, 即PS算法搜索的一组点, 以寻找使目标函数得到改善的点。该算法形成网格的方法是:给模式向量乘以网格尺寸Δm;把结果向量与当前点xm相加, 生成新的备选点集为xm+Δm×{V}i, 当前点是指在前一步找到的具有最佳目标函数值的点。

(3) 对网格点进行选举。对当前点xm与新生成的点集xm+Δm×{V}i, 寻找最小的点, 作为下一次迭代的基点xm+1。一般有两种选举方法, 全局模式搜索和局部模式搜索, 前者寻优结果较稳定, 耗时长;后者减少搜索时间, 但可能陷入局部最优。

(4) 网格的扩展和搜索。若对网格选举找到一个优于当前点的新点, 则称“成功选举”, 扩展网格尺寸, Δm+1=Áe×Δm, 扩展因子Áe>1, 否则, Δm+1=Áu×Δm, 缩减因子Áu<1。

2 多种群遗传-模式搜索算法

2.1 算法框架

多种群遗传-模式搜索算法 (MGPS) 可分为两步:首先是多种群遗传算法 (MGA) 找到最优解所在的区域, 然后利用模式搜索 (PS) 快速找到最优解。如图1所示。

2.2 粗搜索

在粗搜索阶段, 多个种群运用标准遗传算法 (SGA) 进行搜索, 每步迭代时将多个种群的结果汇总, 互相更新最优个体。优点是能够较好地跳出局部最优点, 快速逼近全局最优点的临近区域。算法步骤如图2所示。

各种群采用不同的控制参数[7], 大多数学者建议选择较大的pc (0.7~0.9) 和较小的pm (0.01~0.05) 。但是pc和pm的取值方式还是有无数种, 对于不同的选择, 优化结果差异很大。MGA弥补了简单遗传算法的这一不足, 通过多个设有不同控制参数的种群协同进化, 同时兼顾了算法的全局搜索和局部搜索。各种群之间通过移民算子进行联系, 实现多种群的协同进化;最优解的获取是多个种群协同进化的综合结果。加入人工选择算子保存各种群每个进化代中的最优个体, 并作为判断算法收敛的依据。精华种群和其他种群有很大不同。精华种群不进行选择、交叉、变异等遗传操作, 保证进化过程中各种群产生的最优个体不被破坏和丢失。同时, 精华种群也是判断算法终止的依据, 这里采用最优个体最少保持代数作为终止判据。这种判据充分利用了遗传算法在进化过程中的知识积累, 较最大遗传代数判据更为合理。

3 仿真测试

复杂二元函数求最值:

该非线性函数在给定范围内分布着许多局部极值, 通常的寻优算法极易陷入局部极值或在各局部极值间振荡, 比较适用于验证多种群遗传-模式搜索算法的性能。标准遗传算法运行3次得到的结果如表1所示, 其进化过程如图3所示。

从表1和图3可知, 3次得到的优化结果均不相同, 标准遗传算法很不稳定, 而且接近500代仍未稳定, 最优解还有上升的可能。对于这种复杂的函数优化, 标准遗传算法很难找到最优解。多种群遗传算法运行3次的结果如表2所示, 其进化过程如图4所示。

由表2和图4可知, 多种群遗传算法运行3次的结果完全一致, 其稳定性较好, 而且进化代数较小。所以, 多种群遗传算法的收敛速度快, 适合复杂问题的优化。然而, 多种群遗传算法也难免会陷入局部最优, 如图5所示, 其最优解是38.750 3, 对应自变量:x=11.625 5, y=5.625 04。

为解决该问题, 使用本文提出的多种群遗传-模式搜索算法, 将多种群遗传算法得到的最优解作为模式搜索的初始值, 继续优化, 如图6所示, 经过近5次迭代就找到了最优解, 使多种群遗传算法快速跳出局部最优。网格尺寸不断缩小直至稳定在一个值。

4 结语

本文提出的优化算法MGPS融合了MGA强大的全局搜索能力PS搜索算法的局部寻优精度高优势。算法首先使用MGA实现粗搜索, 可迅速逼近全局最优解的临近区域;然后利用PS实现细搜索, 可准确定位全局最优解。实验表明MGPS算法优于单独执行的SGA和MGA算法。MGPS提高了算法的成功率, 并减少了陷入局部最优的可能, 且收敛速度较快, 是一种有效的优化算法。在后期的工作中将MGPS算法运用于其他领域, 如无人机航迹规划[8], 图像处理[9], 目标识别等[10]。

参考文献

[1]ELANSARY A M, ELDAMATTY A A, NASSEF A O.A cou pled finite element genetic algorithm technique for optimum de sign of steel conical tanks[J].Thin-Walled Structures, 2010, 48 (3) :260-273.

[2]VIDOSSICH G.An addition and a correction to my paper“Diffe-rential inequalities for evolution equations”[J].Nonlinear Anal ysis:Theory, Methods&Applications, 2010, 72 (2) :618-623.

[3]王凌.智能优化算法及其应用[M].北京:清华大学出版社, 2001.

[4]周文彬, 蔡永铭, 陈华艳.实值多种群遗传算法求解动态规划问题[J].控制工程, 2007 (z1) :103-104.

[5]NICOSIA G, STRACQUADANIO G.Generalized pattern search algorithm for peptide structure prediction[J].Biophysi cal Journal, 2008, 95 (10) :4988-4999.

[6]WETTER M, POLAK E.Building design optimization using a convergent pattern search algorithm with adaptive precision sim ulations[J].Energy and Buildings, 2005, 37 (6) :603-612.

[7]聂冲, 王维平, 赵雯.基于学习算子的自学习遗传算法设[J].计算机仿真, 2006 (9) :168-171.

[8]郑锐, 冯振明, 陆明泉.基于遗传算法的无人机航路规划优化研究[J].计算机仿真, 2011 (6) 88-91.

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

遗传优化搜索算法 第2篇

车辆路径优化研究是一个既有理论和实践意义又富有挑战性的课题.针对该NP难问题,提出了一种改进遗传算法.该算法采用了一种新的编码方式,使得染色体中的`每一个基因能代表三层含义;采用了一种与爬山法相结合的混合进化策略.通过性能比较可以看出,在同等计算量情况下,改进遗传算法的优势明显.

作 者：孔志周 官东 作者单位：孔志周(湖南大学,统计学院,长沙,410079;中南大学,信息科学与工程学院,长沙,410083)

官东(中南大学,信息科学与工程学院,长沙,410083)

遗传优化搜索算法 第3篇

摘 要：电力系统的无功优化是降低网损、保障电压质量的有效手段，遗传算法是解决这种多约束非线性组合优化问题的很好方法。简单遗传算法（SGA）中的交叉率和变异率分别是一个过大或者过小的固定值，造成了高适应度基因遭到破坏和算法陷入迟钝，本文中改进遗传算法（IGA）使用变化的交叉率和变异率避免了此类现象。文献中以IEEE33节点系统为例，分别用两种算法进行了无功优化的计算，通过比较得到结论，IGA具有最优解更加准确、收敛速度更加迅速的优点。

关键词：无功优化；改进遗传算法；交叉率；变异率

1 概述

近年来，越来越多的专家将目光投向电力系统的无功功率上来，希望通过调节无功功率的潮流分布，从而减小系统有功网损，使电力系统更加经济、高效。

电力系统的无功优化是指电力系统在满足安全稳定运行的所有约束条件下使有功网损、电压质量和无功补偿等预期目的总体最佳的多约束非线性组合优化问题。为了解决此问题，产生了多种无功优化方法[1]，其中包括：非线性规划法[2]、线性规划法[3]、混合整数规划法[4]、动态规划法[5]、人工智能法等，其中人工智能法又包括人工神经网络、专家系统、模糊算法、Tabu搜索法、模拟退火法、遗传算法等一系列算法。本文的改进遗传算法是在传统的简单遗传算法的基础上对交叉和变异环节进行了改进，使运算过程更加迅速、运算结果更加准确。

2 无功优化的数学模型

电力系统无功优化是指在满足系统各种运行约束的条件下，通过优化计算确定发电机的机端电压、有载调压变压器的分接头档位和无功补偿设备投入量等，以达到系统有功网损最小的目的[6]。

①本文以系统有功网损最小为优化目标：

minF=PS

PS表示系统的有功网损。

②功率平衡的约束在潮流计算中是绝对满足的，如下：

PGi-PLi=UiUj（Gijcosδij+Bijsinδij）

QGi+QCi-QLi-QRi=UiUj（Gijcosδij-Bijsinδij）

式中，n代表电网节点总数；Ui、Uj代表节点i、j的电压；PGi、PLi代表节点i发电机有功功率和有功负荷；QGi、QCi、QLi、QRi代表节点i发电机无功功率、容性无功补偿容量、无功负荷和感性无功补偿容量；代表电网中节点i和j之间的电导、电纳和节点电压相角差。

③网络中，不等式的约束条件为：

Uimin?Ui?Uimaz （节点电压约束）

Qmin?Qi?Qimaz （节点无功约束）

Timin?Ti?Timaz （变压器分接头约束）

3 改进遗传算法

基本遗传算法（简单遗传算法，Simple Genetic Algorithm，简称SGA）是一种仿造生物遗传和进化机制得到的适合于复杂系统优化的自适应概率优化技术。

简单遗传算法中，交叉率（pc）为一恒定值，这种运算虽然简单，但存在很严重的缺陷，如果PC为一适中大小的固定值，那么对于迭代初期来说交叉率相对较低，会引起迭代迟钝，影响遗传算法的整体过程；对于迭代后期而言交叉率相对较高，会导致新的搜索区域被开辟，造成迭代趋向随机化的严重后果。

针对上述缺陷，本文献采用了一种变化交叉率的改进方法，为了满足迭代前期对较大交叉率的要求，我们设初始交叉率pc为一个较大值，同时为了满足迭代后期对较小交叉率的需要，我们让pc在每次迭代过程中逐渐减小，直到减小到某一固定值为止恒定。

同理，变异率（pm）也为一恒定值，同样存在缺陷，如果pm为一适中大小的固定值，那么对于迭代初期来说变异率相对较高，在迭代初期会导致原本就极少的具有高适应度的个体基因被变异破坏，大大阻碍了遗传基因的进一步优化；对于迭代后期而言变异率相对较低，会导致迭代后期没有新的具有活力的基因注入，从而使整个遗传算法陷入局部最优解。

针对上述缺陷，本文献同样采用了变化变异率的改进方法，为了满足迭代前期对较小遗传率的要求，我们设初始遗传率pm为一个较小值，同时为了满足迭代后期对较大遗传率的需要，我们让pm在每次迭代过程中逐渐增大，直到增大到某一固定值为止恒定。

我们把上面对交叉率和遗传率的改进植入简单遗传算法中，从而得到改进遗传算法（Improved genetic algorithm，简称IGA）。

4 算例分析比较

下面以IEEE33节点系统为例，此系统中有支路32条、联络开关支路5条。本算例中，33节点系统为一配网系统且无变压器，不可通过调节变压器分接头档位来进行优化。0号节点为平衡节点，其余32个节点为PQ节点，可以通过向17号节点添加无功补偿装置的方法对系统节点电压进行调节，以达到减小有功损耗的目的。

两种遗传算法的种群规模均为popsiza=40、最大迭代次数为T=30、二进制编码方式、赌轮盘选择。简单遗传算法（SGA）的交叉率为固定值pc=0.8，变异率为固定值pm=0.1；而改进遗传算法（IGA）的交叉率为初始值pcmax=0.8，以0.02为步长递减到pcmin=0.2的变化值，最后pc恒定在0.2，交叉率为初始值pmmin=0.1，以0.005为步长递增到pmmax=0.2的变化值，最后pm恒定在0.2。

图2和图3分别为两种遗传算法运算的结果曲线图。

通过图2、3的结果对比可以看出，改进遗传算法进行无功优化得到的最优适应度更好。

对17号节点的无功补偿后，网络的节点电压得到优化，数据如表1。

从上述表1对比结果可知，与简单遗传算法相比，改进遗传算法进一步降低了无功优化的网损，提高了降损率，并且有着更短的运行时间，更好的运行效率。

5 结论

本文对简单遗传算法进行无功优化所存在的高适应度基因易造成破坏和运算易陷入迟钝状态的现象进行了分析，从而增加了递减交叉率和递增变异率的运算环节，分别用两种遗传算法进行了无功优化的仿真运算。算例结果表明，改进遗传算法具有求解更准确、收敛速度更迅速的优点。

参考文献：

[1]陈燕萍.基于改进遗传算法的电力系统无功优化[J].南京师范大学，2008，5.

[2]李林川，王建勇，陈礼义.电力系统无功优化规划[J].中国电机工程学报，1999，19（2）：66-69.

[3]赵尤新，徐国禹.灵敏度法分析计算电力系统无功和电压最优控制问题[J].重庆大学学报，1985，8（2）：1-11.

[4]Rama Iyer S，Ramachandran K，Hariharan S. Optimal Reactive Power Allocation for Improved System Perfor-mance[J].IEEETransactions Power and System，1984，PAS-103（6）.

[5]李文沉.电力系统安全经济運行——模型与方法[M].重庆大学出版社，1989.

[6]张利生.电网无功控制与无功补偿[M].中国电力出版社，2012.

作者简介：

搜索最危险滑面的遗传算法 第4篇

边坡稳定性分析是岩土工程中最老的问题之一,也是在研究和实践中最活跃的问题之一,多年以来,大量的学者曾经提出了很多土坡稳定性分析方法,己有很多土坡稳定性安全系数的计算方法和临界滑动面的搜索方法,并且几个大型软件分析已经得到应用,但是仍然存在不少的问题。遗传算法(Genetic Algorithm,简称GA)受自然演化过程的启发,模拟生物的进化过程,这是一种自适应全局搜索算法。与我们经典优化算法(如梯度法、黄金分割法、单纯形法等)相比,遗传算法具有这样些特点:①具有很好的可操作性,简单明了;②遗传算法隐含并行性,具有较高的搜索效率;③遗传算法不受某些限制性假设的约束,如不必要求连续性,导数存在等,这就使得该方法适用范围更广,具有很强的通用性;④遗传算法利用概率转移规则,而非确定性转移规则。这样使得遗传算法具有良好的全局优化性和鲁棒性。

正因为遗传算法的这些特点和优点,它在岩土工程中得到了广泛的应用[1]。

1遗传算法

物种之间和物种内部相互竞争,只有适应环境的才能生存下来,这就是达尔文进化论的核心思想。孟德尔提出的遗传学说(又称基因学说)就是染色体遗传学说。生命很容易被毁灭,看来极其脆弱,但有时能在极其恶劣的环境中生存,显示出非常顽强的生命力。远古时代产生的单细胞,在经历无数的恶劣环境下,从简单的生命形式,由低级到高级、从简单到复杂,不断地进化延续,产生了人这种有语言、有智力的高级生命体,就是自然演化的过程。

这个自然演化过程,就是使得生命体逐步达到适应环境的最佳结构与效果,从本质上看,就是一个学习与优化的过程。它一方面通过模拟达尔文“优胜劣汰、适者生存”的机制来激励更能适应环境的更好的结构;另外一方面又通过模拟孟德尔遗传变异原理,在迭代过程中保持已有的结构,同时寻找更好的结构[2,3,4]。

遗传算法受自然演化过程的启发,模拟生物的进化过程,这是一种自适应全局搜索算法。借鉴了遗传学的术语,遗传算法中个体称作染色体(chromosome),个体的分量称为基因(gene),分量的取值称为等位基因(allele)。一般,遗传算法有复制、交叉、变异三种基本的遗传操作,图1表示了基本遗传算法的过程。

2编码方法和遗传算子

在研究遗传算法中,针对不同的问题,学者们设计了很多各具特色的编码方法和遗传算子[5,6]。遗传算法一般先对原问题进行编码,实现由问题空间到搜索空间(可行解域)的映射。简单遗传算法一般采用二进制编码方案,存在不足之处(如搜索空间不连续),对于一些多维或高精度要求的连续函数优化问题不合适等。采用实数编码可以克服这一缺陷[7]。对于求目标函数最小值的问题,其适应度函数一般可定义为:

undefined

式中,Cmax为一相对大的数,ξ为参变量集。

对于求目标函数最大值的问题,其适应度函数可以定义为:

undefined

式中,Cmin为一个相对小的常数。

大量计算说明,仅仅使用式(1)或式(2)来计算个体的适应度,对某些问题收敛快、效果好,但是对某些问题则收敛慢。实践中证实,在进化过程中,动态的对适应度函数进行调整可以很好的缓解早熟现象。适应度的增加和降低又称为适应度尺度变化,线性尺度变化方法、幂函数变换法、指数变换方法[7]是常用的适应度尺度变化方法。

为了模拟自然界的生物进化过程,遗传算法采用了三种基本的遗传算子,包括选择算子、交叉算子,变异算子。遗传算子的选择对遗传算法的计算效率和收敛性有很大的影响。选择算子就是从当前代群体中按某规则选择比较优良的个体复制到下一代。常用的选择算子有比例选择算子(也叫做赌轮选择)、排序选择算子、锦标赛选择算子[8]、杰出者选择(elitist selection)等。

交叉算子就是将两个准备配对的染色体(可行解)按某种方式交换其部分基因,形成新的个体。这样,重新组合种群中现有的基因型以产生新的基因型。遗传算法常见的交叉算子有单点交叉算子、两点交叉算子、多点交叉算子、均匀交叉算子、算术交叉算子[9]。

变异算子就是将染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因代替,从而形成一个新个体。这样可使现有的基因型发生突变,以使种群呈现多样性。遗传算法一般采用基本位变异算子、均匀变异算子、非均匀变异、自适应变异[10]。

遗传算法的运行一般需要一些运行参数,包括种群规模Np,交叉概率Pc,变异概率Pm,终止代数Nt等运行参数,这些参数对遗传算法的效率有较大的影响。这些参数的选取一般情况下是根据经验选取得的。种群规模Np就是种群中所含个体(可行解)的数量。当取值较小时遗传算法的运算速度快,但却种群的多样性缺乏,容易引起早熟;当取值较大时遗传算法的运行时间长,一般选取小于200。终止代数Nt,也就是遗传算法所迭代的最大次数。交叉概率Pc,即在种群中按某种规则选两个个体进行交叉的概率,一般选取范围是0.4～0.99[11]。变异概率Pm就是对种群中个体进行变异操作的概率,取值较小,一般选取范围是0.0001～0.1 [11]。一般遗传算法中的交叉概率和变异概率是一个常数,不能动态调整,Strivivas[12]提出了交叉概率和变异概率的自适应选取方法,Pc和Pm的选取方法如下:

undefined

式中,k1,k2,k3,k4∈(0,1),fmax表示种群中个体的最大适应度,favg是种群的平均适应度,f′表示待交叉的两个个体中较大的适应度值,f是待变异个体的适应度值。从式(3)和式(4)可以看出,采用自适应选取方法,对于大适应度的个体,赋予较小的交叉和变异概率;对于小适应度的个体,则用大的交叉和变异概率。

遗传算法计算过程一般可以用如下步骤来构造:

第一步:确定出个体的表现型X和问题的解空间。

第二步:确定目标函数及其数学描述形式或量化方法。

第三步:确定出个体的基因型X及遗传算法的搜索空间,也就是确定表示可行解的染色体编码方法。

第四步:确定出由个体基因型X到个体表现型X的对应关系或转换方法,也就是确定解码方法。

第五步:确定出由目标函数值f(X)到个体适应度Fitness(X)的转换规则。也就是确定个体适应度的量化评价方法。

第六步:确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。也就是设计遗传算子。

第七步:确定种群规模Np、交叉概率Pc、变异概率Pm、进化代数Nt等参数。即确定遗传算法的有关运行参数。

3遗传算法搜索简单土坡最危险滑面

在前面,我们已经介绍了如何具体应用遗传算法。在这里我们将用一个简单土坡最危险滑面搜索问题来验证。以说明遗传算法的有效性。从文献[13]选取一个实例,某坝基20 m以下存在着低强度软粘土,而其上是高50 m,坡比为1∶3的均质土坡。每个土层的参数见表1。

这里用Bishop圆弧法搜索最危险滑面。参考张天宝的研究结果,当固定出滑点时(坡底)将有两个极值区。选定出滑点xA=0(坡底),选定搜索区域如表2所示。采用二分法搜索,结果为最小安全系数Fs为1.171,所对应的滑弧圆心位置在(72.700,68.741),半径为100.053购员m。若搜索区域为表3.3所示,采用二分法得到最小安全系数Fs为1.299,所对应的滑弧圆心位置在(43.164,143.633),半径为149.978 m。

这里采用遗传算法,运行参数采用表4所示,选定搜索区域如表2所示。迭代到107代得到最优个体,最小安全系数Fs为1.171,所对应的滑弧圆心位置在(72.730,68.746),半径为100.055 m。若搜索区域为表3.3所示,则迭代到131代得到最优个体,最小安全系数Fs为1.171,所对应的滑弧圆心位置在(72.713,68.751),半径为100.068 m。

4结束语

遗传算法的选择是一种正确的方法,由于其是一种全局搜索方法,避免了其它方法引起的陷入僵局的局部极值的缺陷。采用遗传算法进行求解,可以得出全局意义上的最小安全系数,其收敛比较容易,速度也较快,更重要的是能够处理复杂土质情况的边坡问题,所以,选择遗传算法分析边坡稳定问题在理论和实践上是具有可行性和有效性的。二分法是传统的优化方法,在本例中,可以看出二分法在第一次能搜索到全局最优值,但在第二次得到的只是局部最优值,不同搜索范围得到不同搜索结果。可见对于多极值问题,二分法搜索到全局最优值是有困难的。而遗传算法在不同搜索范围内能均能搜索到全局最优值,可见对边坡最危险滑面的搜索是有效的。

摘要：本文介绍遗传算法,并阐述具体应用在搜索土坡的最危险滑面。用一个简单土坡最危险滑面搜索问题来验证,证明了遗传算法对搜索最危险滑面的有效性。

遗传优化搜索算法 第5篇

一种基于遗传算法的设备备件配置优化方法

针对备件费用与备件保障度的平衡问题,提出一种设备备件配置优化模型.采用遗传算法进行求解,在求解过程中,运用自适应的交叉、变异策略,提高算法的精确度,并通过举例验证算法的`有效性.

作 者：王家鹏 高崎 王宏焰 徐志伟 WANG Jia-peng GAO Qi WANG Hong-yan XU Zhi-wei 作者单位：军械工程学院,装备指挥与管理系,河北,石家庄,050003刊 名：兵工自动化 ISTIC英文刊名：ORDNANCE INDUSTRY AUTOMATION年，卷(期)：28(10)分类号：O232 TP301.6关键词：备件 优化 遗传算法

遗传优化搜索算法 第6篇

摘要：为了获得满足潮流能水轮机设计要求的专用翼型，基于遗传算法建立了水轮机翼型优化设计模型，该模型综合考虑了升力系数、阻力系数、升阻比和压力系数等因素，采用XFOIL评估翼型的水动力性能，对几种典型设计要求情况下的水轮机翼型进行了优化设计。数值结果表明，该模型能够根据不同的设计要求获得相对应的水轮机翼型，不仅可以改善翼型的水动力系数，还能够避免翼型空化现象的产生。在最小化压力系数情况下，最大厚度位置更靠近翼型后缘，而最大化升力系数情况下则更靠近翼型前缘。为了达到指定的设计目标，需要考虑多个攻角下的升力系数或压力系数。

关键词：潮流能；水轮机；翼型；水动性能；空化

中图分类号：TK73文献标识码：A

随着世界经济的发展，能源消耗越来越多。由于化石能源危机以及传统能源所带来的环境污染和碳排放等问题，使得清洁的可再生能源日益重要。潮流能是一种非常重要的新能源，具有可靠、周期性、分布广泛、且可持续等优点。越来越多的国家已经开展了相关的研究，潮流能将在未来的能源中扮演重要角色。为了利用潮流能，采用水轮机作为主要的能量捕获装置，叶片作为直接承受水动力并将其转化为机械能的部件，对潮流能转化效率有重要影响。因此，叶片是潮流能水轮机设计中的关键部件。

在水平轴潮流能叶片设计中，翼型选择、翼展、以及沿展向分布的弦长、厚度和扭转角度分布均为重要影响参数。此外，翼型前缘粗糙度、平台的升降运动和表面重力波等均会对水动性能产生重要影响＼[1-2＼]。为了提高水轮机效率，国内外学者已经开展了相关的研究工作。Wu等人＼[3＼]引入Schmitz理论对桨叶进行设计，并充分考虑了空泡问题，能够提高水轮机效率。Battena等人＼[4＼]采用试验对动量方法进行了研究，表明该方法具有足够的精度，并采用该方法对叶片进行设计。Reza等人＼[5＼]采用响应面方法，以最大化输出功率为目标函数对海洋水平轴水轮机叶片沿展向的厚度和扭转角等进行优化设计。翼型设计是水轮机设计中的关键问题，只有选择合理的翼型，才能最大限度地提高水轮机效率。尽管已经开展了相关的研究，但是大都采用风力机和航空专用翼型，使水轮机无法达到最佳效率。因此，有必要研究适用于水轮机的最佳翼型。

目前，国外的翼型研究与设计主要集中在飞行器和风力机领域，国内学者对风力机翼型也开展了相关研究＼[6-8＼]。通过相关学者的研究，已经获得了重要的翼型数据，如专为风力机设计的翼型有SERI翼型、为了减小前缘粗糙敏感度的DU翼型和CASW1风力机翼型等，它们的共同特点是基于空气动力学原理，大都不是水轮机叶片的理想翼型。以应用最为广泛的NACA翼型为例，该系列翼型具有较差的失速特性，并且对于前缘粗糙度较为敏感。虽然水轮机和风力机以及飞行器机翼有很多相似之处，但是水轮机叶片的载荷环境有较大的不同。水的密度是空气密度的800多倍，因此水轮机所承受的载荷要大。此外，水轮机在水中运行过程中存在的空化现象可能会对叶片产生较大的破坏。因此相对于风力机叶片，不但需要尽可能避免空化的产生，还要求翼型具有更大的厚度来满足强度要求。目前，仍然缺乏对潮流能水轮机的专用翼型及其分析方法的研究，急需开展相关的研究工作。

目前，在风力机和航空航天领域，已有学者开展了翼型优化设计的研究，Lighthill＼[9＼]采用了反设计技术。反设计方法的基本思想是由假定分布在翼型表面的压力系数来构造翼型曲线，通过迭代办法不断修正压力分布来达到指定的设计要求。尽管该方法已被广泛采用，但是在设计过程中无法同时考虑多个设计要求。由于水轮机翼型有多方面的设计要求，必须采用多目标设计方法。Grasso[10]采用基于梯度方法对水轮机翼型在7°攻角下的水动性能进行了优化设计。为了使潮流能水轮机在1～3 m/s流速下达到较好的性能，Goundar等人＼[11＼]对翼型的高升力、高升阻比、较高的强度以及空泡的出现等问题开展研究。Molland等人＼[12＼]采用XFOIL对二维水翼的空泡问题开展研究。尽管在潮流能水轮机优化设计方面已有了一些研究成果，但是在翼型设计方面仍然处于起步阶段，并且国内的相关研究工作基本处于空白，因此急需开展相关研究。

本文以潮流能水轮机叶片翼型为研究对象，建立了翼型优化设计模型，该模型同时考虑了升力系数、阻力系数、升阻比和表面压力系数等因素。为了获得全局最优解，采用遗传算法进行求解，水动性能和压力系数通过XFOIL数值仿真软件获得，最后采用该方法获得了不同设计目标情况下的翼型，通过对比分析得到了各种翼型的特点，为进一步开展水轮机设计提供依据。

1水轮机翼型设计要求与优化算法

1。1水轮机翼型设计要求

由于处于不同的流体介质中，故风力机和水轮机叶片的设计要求有较大的不同。风向和风力具有较大的随机性，风力机叶片的气动弹性等问题较为显著，在风力机设计中，选择较高的设计升力系数能够降低阵风和疲劳载荷，改善风力机的使用寿命。与风力机不同，水轮机的流体环境中的湍流较低，流速较小并且比较稳定，因此疲劳并不是水轮机的显著问题。由于阵风的影响，风力机叶片可能处于失速区域，当攻角到达失速点后，气动效率可能急剧下降。因此，翼型分离点设计显得尤为重要。对于潮流能水轮机，在设计中更希望水动性能不要随着攻角的变化过于剧烈，尤其是在失速区域＼[13＼]。在具体的翼型设计中要求分离点随着攻角的增加而缓慢向后缘移动。一般情况下，风力机叶片较为细长，可能产生较大的扭转力矩，所以风力机的力矩系数是一个非常重要的设计参数。而水轮机叶片的展弦比较小，叶片足够刚硬，所以力矩系数在水轮机叶片设计过程中并不是主要因素。

空化现象是水轮机与风力机的最大区别。空泡产生的条件如图1所示，图1中横坐标为弦线位置。由图1可知，当某一流体区域的压力绝对值大于临界空化压力值时就会形成气泡＼[12＼]。一般而言，气泡分为惯性（瞬态）空泡或者非惯性空泡。惯性空泡是由一个空气泡在水中迅速破裂，产生了一个冲击波，该类型空泡通常发生在抽水机、螺旋桨和叶轮等机械结构中。非惯性空泡则是由诸如声场等外在某种型式的能量输入迫使流体产生振荡导致的。由惯性空泡的破裂所产生的冲击波可能会对水轮机结构造成破坏，因此，在水轮机叶片翼型设计中应考虑空泡的影响。空泡参数定义如式（1）所示。

σc=p0-pvq=pAT+ρgh-pv0。5ρV2 。（1）

式中：pv为空泡压力，主要依赖于水的温度；p0为局部压力；q为动压。

压力系数定义为：

Cp=pL-p00。5ρV2。 （2）

根据翼型表面的压力分布可以判断是否产生空泡，当pL与pv相等或者最小的负压系数Cp与空泡系数相等时就会产生空泡现象。

图1空泡产生的条件

Fig。1Condition for cavitation

水轮机沿展向由不同的翼型组成，靠近桨叶外侧部位，要求翼型具有较大的升力系数和升阻比以及较小的阻力系数，使得采用较小的弦长就可以达到指定的水动力载荷。从水动力学设计的角度，翼尖区域的升阻比是最为重要的参数，由于水轮机所受到的载荷较大，为了满足结构设计的要求，一般采用较厚的翼型。由于靠近翼根部位承受了极大的载荷，为了结构布置的需要，对翼型厚度有特别要求，但此时又会牺牲较大的水动性能。在不同设计要求的情况下，翼型会出现较大的不同，如何根据水轮机的要求来设计特定的翼型成为了需要深入研究的问题。

1。2遗传算法

优化算法可以分为基于梯度和非梯度两类方法，基于梯度的优化方法难以得到全局最优解，并且对翼型设计可能会存在收敛速度慢等问题；诸如遗传算法的非梯度方法具有全局寻优性能，因此，本文采用遗传算法作为优化算法。

遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的高效全局寻优搜索算法。该算法由一组初始解（初始种群）组成，每一个解采用二进制编码如式（3）所示，所有n个设计变量编码成一个二进制数并顺序排列，选择一个适应度函数，并对每一个解的适应度进行评估，淘汰适应度差的解，通过对编码后的二进制数进行变异、杂交等操作获得新解。从而形成了新的种群，重复上述过程，经过若干代的求解能够接近甚至获得全局最优解。

P=[01…11111…012…01…10n]。 （3）

相对于传统优化方法，遗传算法具有可行解表示广泛性、群体搜索性、随机搜索性和全局性等优点，在各类优化方法中被广泛采用＼[14-15＼]。

2翼型优化模型

2。1翼型参数化方法

设计变量的选择对优化结果非常重要，为了能够准确描述翼型，又不过多牺牲几何信息，拟合曲线的选取至关重要，多项式样条曲线能够显著减少设计变量的个数＼[16＼]。本文采用了三次样条曲线，为了尽可能扩大搜索空间，在翼型曲线上选择若干个点，采用每一个点的横坐标和纵坐标作为设计变量，通过翼型曲线上的点（xi，yi）i=1，…，k以及前缘和后缘的切线斜率（t0，t1）来拟合翼型曲线。最终翼型设计变量X如式（4）所示。

X=（t0，x1，y1，x2，y2，…，xk，yk，t1）。 （4）

2。2翼型评估方法

一般而言，翼型水动性能和压力分布可由计算流体力学（CFD）软件得到。对于流速较低的水动力学问题计算精度较高，但是由于翼型优化需要大量评估目标函数，计算量极大，因此该方法并不适合。XFOIL是一款由Drela开发的能够准确评估翼型气动力的数值软件，该软件基于面元法和粘性边界层等模型，与CFD计算结果接近，能够快速准确地评估翼型，是进行翼型优化设计的理想方法＼[17＼]。

2。3优化模型

潮流能水轮机翼型优化以升力系数、阻力系数、升阻比和压力系数的函数作为目标函数，XFOIL作为评估工具，将翼型参数化之后，建立如下所示的翼型优化模型。

目标函数为：

f（X）=f（CL，CL/CD，CD，Cpmax）。 （5）

约束条件为：

hj（X）≤0，j=1，…，m； （6）

XLi≤Xi≤XUi，i=1，…，l。 （7）

式中：CL，CL/CD，CD和Cpmax分别为升力系数，升阻比，阻力系数和压力系数最大值；Xi，XUi和XLi分别为第i个设计变量及其上下界，此处的设计变量为翼型上节点坐标等。目标函数f（X）可以是水动性能和压力系数的任意组合形式，在实际翼型设计中可以根据需要灵活选择。

依赖于翼型变量的目标函数，同时满足等式和不等式约束条件，通过求解优化模型可以得到满足设计要求的翼型。

3水轮机叶片翼型优化设计

对于潮流能水轮机，叶片沿展向的不同位置有不同的设计要求，靠近翼尖位置，具有较高升阻比的薄翼型是较优的选择，在一个较宽的攻角范围内，必须具有较高的升力系数和升阻比，阻力系数应当尽可能小。由于根部承受较大的载荷，为了保证桨叶具有足够的结构刚度和强度，要求根部翼型具有较大的厚度。此外，为了避免空化现象，可能需要选择较厚的翼型。为了验证本文方法，并探讨翼型特性，采用Reynold数为106，目标函数是攻角为3°情况的升力系数、阻力系数、升阻比和压力系数，获得不同设计要求下的翼型，并对比各个翼型的水动性能和压力分布特性。

基于本文所提出的优化模型和求解方法，对几种不同设计要求进行求解，最终得到每种情况下的翼型曲线如图2所示。由图2可知，当最小化阻力系数和最大化升力系数时，翼型曲线较为接近；当最大化升阻比时，最大厚度位于距翼型前缘35%处，最大厚度为弦长的8。8%；在最小化阻力系数情况下，最大厚度距前缘35%，最大厚度为弦长的8。3%。对于水轮机而言，由于较大的升力部分转化为垂直于水轮机平面的推力，而转化为水轮机轴向力的部分较小。不同于升力系数，阻力系数的降低能够显著提高水动性能。区别于前两种翼型，最大化升力系数和最小化最小压力系数所获得的翼型有较大的不同，在最大化升力系数情况下，翼型前部较厚，到后缘处翼型厚度减小，最大厚度位于距翼型前缘39%处，最大厚度为弦长的11。4%；而对于最小化最小负压系数，最大厚度位于距翼型前缘52%处，最大厚度为弦长的8。8%。

图2不同目标函数情况下的翼型对比

Fig。2 Hydrofoil for different objective function

不同设计目标函数情况下的升力系数、阻力系数和升阻比如图3-图5所示。与翼型数据结果类

攻角/（°）

图3不同翼型的升力系数随攻角的变化

Fig。3Lift coefficient vs。 attact angles

for different hydrofoil

攻角/（°）

图4不同翼型的阻力系数随攻角的变化

Fig。4Drag coefficient vs。 attact angles

for different hydrofoil

似，最小化阻力系数和最大化升阻比所得到的两种翼型具有非常接近的水动性能。以负压系数作为目标函数情况下，升力系数大大小于其他3种情况，阻力系数则与最小化阻力系数情况接近。尽管最大化升力系数具有较大的升力系数，但是阻力系数明显大于其他翼型的阻力系数，并且该翼型虽然在3°攻角情况下具有最大的升力系数，但是随着攻角的增加，最大化升阻比和最小化阻力系数时的翼型具有更大升力系数。因此在进行翼型设计时，不能只考虑一种攻角下的水动性能，而要进行综合考虑。

攻角/（°）

图5不同翼型的升阻比随攻角的变化

Fig。5Liftdrag ratio vs。 attact angles

for different hydrofoil

4种不同翼型在3°攻角情况下的表面压力系数如图6所示。由图6可知，最小化压力系数时的压力分布最为均匀，最小值为-0。5，可见最小化压力系数可以大大改善翼型表面的压力分布，进而避免空化现象的产生。最小化阻力系数和最大化升阻比情况下的翼型，最小压力系数为-1。1，两者较为接近。最大化升力系数情况下的最小压力系数峰值最小，达到了-1。5，也越容易产生空化现象。

弦线位置

图6不同翼型的3°攻角下的压力分布

Fig。6Pressure distributions of 3°attact angle

不同攻角下的翼型表面压力系数对比如图7-图10所示。由图可知，不同攻角下的同一翼型压力系数分布规律较为一致。随着攻角的增加，最小压力系数也随着减小，而且压力分布会更加不均匀。尽管最小化压力系数情况下，翼型在3°攻角时具有最佳的压力分布特性，但是随着攻角的增加，最小压力系数急剧增加，显然对避免空化现象不利，因此，需要综合考虑多个攻角下的压力分布系数。

弦线位置

图7最大升力系数翼型时不同攻角的压力分布

Fig。7Pressure distributions for maximum lift coefficient

弦线位置

图8最大升阻比翼型时不同攻角的压力分布

Fig。8 Pressure distributions for maximum liftdrag ratio

弦线位置

图9最小化阻力系数翼型时不同攻角的压力分布

Fig。9Pressure distributions for minimized drag coefficient

弦线位置

图10最小化压力系数翼型时

不同攻角的压力分布

Fig。10Pressure distributions for minimized

pressure coefficient

4结论

本文针对潮流能水轮机叶片翼型，提出了一种优化设计方法。该方法采用了具有全局寻优特性的遗传算法，选取的曲线拟合方法能够准确地描述翼型曲线，通过该模型获得的翼型不仅能够提高水动力性能，还能改善翼型的空化问题。在最大化升力系数情况下，翼型具有较小的阻力系数，以压力系数为目标函数能够显著改善压力系数分布特性。为了改善水轮机性能，需要考虑多个攻角进行综合设计。通过该方法能够显著改善潮流能水轮机翼型的水动性能和压力分布特性。

参考文献

[1]ZHANG L， WANG S Q， SHENG Q H。 The effects of surge motion of the floating platform on hydrodynamics performance of horizontalaxis tidal current turbine＼[J＼]。 Renewable Energy， 2015， 74：796-802。

[2]LUST E E， LUZNIK L， FLACK K A， et al。 The influence of surface gravity waves on marine current turbine performance＼[J＼]。 International Journal of Marine Energy， 2013， 3/4： 27-40。

[3]WU B G， ZHANG X M， CHEN J M， et al。 Design of highefficient and universally applicable blades of tidal stream turbine＼[J＼]。 Energy，2013， 60：187-194。

[4]BATTENA W M J， BAHAJ A S， MOLLAND A F， et al。 Experimentally validated numerical method for the hydrodynamic design of horizontal axis tidal turbines＼[J＼]。 Ocean Engineering，2007， 34：1013-1020。

[5]REZA C， MARTIN O， RALF B。 Blades optimization for an ocean current horizontal axis turbine using response surface methodology＼[C＼]//OCEANS。 Spain：IEEE，2011。

[6]白井艳， 杨科， 黄宸武， 等。 风力机专用翼型的反设计＼[J＼]。 工程热物理学报， 2012， 33（11）：1884-1888。

BAI Jingyan，YANG Ke， HUANG Chenwu， et al。 The inverse design of wind turbine airfoil＼[J＼]。 Journal of Engineering Thermophysics，2012， 33（11）：1884-1888。（In Chinese）

[7]王林， 刘雄伟。 风力发电机叶片翼型气动性能分析与数值模拟＼[J＼]。 太阳能学报， 2012， 33（5）： 711-716。

WANG Lin， LIU Xiongwei。 Numerical simulation and analysis on aerodynamic performance of wind turbine blade＼[J＼]。 Acta Energiae Solaris Sinca， 2012， 33（5）： 711-716。 （In Chinese）

[8]王龙， 宋文萍， 许建华。 基于 Pareto 遗传算法的风力机翼型多点优化设计＼[J＼]。 太阳能学报， 2013，34（10）：1685-1689。

WANG Long，SONG Wenping， XU Jianhua。 Multipoint optimization wind turbine airfoils based on Pareto genetic algorithm＼[J＼]。 Acta Energiae Solaris Sinca， 2013，34（10）：1685-1689。 （In Chinese）

[9]LIGHTHILL M J。 A new method of twodimensional aerodynamic design＼[R＼]。 London：Aeronautical Research Council，Reports and Memoranda， 1945。

[10]GRASSO F。 Design and optimization of tidal turbine airfoil＼[J＼]。 Journal of Aircraft， 2012， 49（2）：636-643。

[11]GOUNDAR J N，AHMED M R。 Design of a horizontal axis tidal current turbine＼[J＼]。 Applied Energy， 2013，111：161-174。

[12]MOLLAND A F， BAHAJ A S， CHAPLIN J R， et al。 Measurements and predictions of forces， pressures and cavitation on 2D sections suitable for marine current turbines＼[J＼]。 Journal of Engineering for the Maritime Environment， 2004， 218（2）：127-138。

[13]AHMED M R。 Blade sections for wind turbine and tidal cureent turbine applications-current status and future challenges＼[J＼]。 International Journal of Energy Research，2012，36：829-844。

[14]官凤娇，韩旭，周长江，等。 基于微型多目标遗传算法的布料机臂架结构优化＼[J＼]。湖南大学学报：自然科学版，2008， 35（11）：26-31。

GUAN Fengjiao，HAN Xu，ZHOU Changjiang，et al。Design optimization of the telescopic boom of concrete distribution machine based on micro multiobjective genetic algorithm＼[J＼]。 Journal of Hunan University：Natural Sciences， 2008， 35（11）：26-31。 （In Chinese）

[15]邓乾旺， 高礼坤， 罗正平， 等。 基于多目标遗传算法的起重机吊装路径规划＼[J＼]。湖南大学学报：自然科学版， 2014， 41（1）：63-69。

DENG Qianwang，GAO Likun，LUO Zhengping，et al。 Lifting path planning of crane based on multiobjective genetic algorithm＼[J＼]。Journal of Hunan University：Natural Sciences，2014， 41（1）：63-69。 （In Chinese）

[16]SAMAREH J A。Survey of shape parameterization techniques for highfidelity multidisciplinary shape optimization＼[J＼]。 AIAA Journal， 2001， 39（5）： 877-884。

基于遗传算法的主题信息搜索研究 第7篇

随着Web上多元化信息的增长, 通用搜索引擎已经不能满足人们日益增长的对于个性化信息检索服务的需要, 为了适应特定人群的需要, 主题搜索引擎便应运而生。

主题搜索引擎服务于特定人群, 其检索的页面内容仅限于特定主题或专门领域, 在搜索过程中无须对整个Web进行遍历, 只需选择与主题相关的网页进行访问。那么爬虫以何种搜索策略可以提高搜索效率便成了近年来主题搜索引擎研究中的热点问题之一。目前, 常用的主题搜索引擎搜索策略主要有两类:基于内容评价的搜索策略, 基于链接结构评价的搜索策略。

基于内容评价的搜索策略以向量空间模型算法为理论基础, 根据网页与主题的相似度来评价链接价值的高低, 从而决定其搜索策略。其中以VSM和Best-First算法为代表, 其优点是具有较好的理论基础且计算简单, 但忽略了Web页面之间的链接关系, 不能很好地发挥网页链接的作用。

基于链接结构评价的搜索策略是以Web页面之间的链接关系为基础, 通过分析Web结构来确定网页的重要性, 从而决定搜索策略, 通常认为有较多入链或出链的页面具有较高的价值。其中以HITS算法为代表, 其优点是考虑了网页间的链接结构, 但忽略了页面本身与主题的相关性, 易出现“主题漂移”问题。

1 基于遗传算法的主题爬虫的设计思想

基于上述分析, 我们决定利用遗传算法高效、并行、全局寻优的特点, 在爬虫搜索策略中引入遗传算法, 来提高爬虫的搜索效率。

遗传算法是一种模拟生物进化的智能优化算法。它根据进化论优胜劣汰、自然选择、适者生存和物种遗传的原则, 借助选择、交叉、变异等操作, 使所要解决的问题在竞争中得以进化, 从而求得问题的满意解或最优解。

具体的算法设计如下:利用通用搜索引擎获取待搜索的网页URL, 根据网页间的链接关系获取初始种子群体;通过交叉操作, 对父代个体进行变换, 产生出大量新的个体, 再从中选取主题相关度高的个体;通过变异操作, 引入新种子集合, 扩大搜索范围;通过选择操作, 选出适应度高的个体 (URL) 作为下一代的种子进入新一轮的遗传, 缩小了新种子数量, 可以加快网页抓取速度。

2 基于遗传算法的主题爬虫的关键技术

2.1 网页的Authority和Hub值

根据网络拓扑结构的“蝴蝶结”理论, 网页大概分为目录型网页和权威型网页。

目录型网页 (也称之为Hub网页) 是提供指向权威网页链接集合的Web网页, 它本身可能并不重要, 或者说没有几个网页指向它, 但是Hub网页提供了指向就某个主题而言最为重要的站点的链接集合。权威型网页 (也称之为Authority网页) 是有许多好的网页指向的Web网页, 这种网页的反向链接数很多, 而正向链接数相对较少, 通常认为Authority网页的内容具有较强的主题相关度。结构如图1、图2所示。

网页的Authority和Hub值计算方式如下:

将网页p的Authority值记为ap, Hub值记为hp, 为所有待搜索网页赋初值:ap (0) ←1, hp (0) ←1;再通过以下迭代公式对ap和hp进行反复修正, 直至结果收敛:

2.2 正向最大匹配分词

正向最大匹配分词是基于分词词典的分词系统, 分词词典中有大量的词, 一般词典中词的数量在十几万到几十万不等。然后将待分词的句子按照从左到右的扫描规则与词典中的词进行匹配。若匹配上, 则将这个词分出来。所谓最大匹配, 就是要求每一句分词的结果中词汇的总量要最少。

本文选用的分词词典是中科院中文分词器I C T C L A S2009版。

2.3 向量空间模型算法

把文档di看成是由一组词条 (T1, T2, …, Tn) 构成的, 对于每一个词条Ti, 都可以根据它在文档中的重要程度赋予一定的权值wi。若将T1, T2, …, Tn看作一个n维坐标系, wi为对应的Ti的坐标值, 则每一篇文档di都可看作向量空间中由一组词条矢量构成的一个点, 如图3所示。

设D是一个包含m篇文档的集合, D={d1…di, …, dm}, i=1, 2, …, m。集合D中的每篇文档di都被表示成向量di= (wi1, …, wij, …, win) , i=1, 2, …, m;j=1, 2, …, n。其中, wij表示第j个特征项Tj在文档di中的权值。

判断网页与主题是否相关就需要计算网页与主题的相似度, 向量空间模型算法的基本思想就是计算图3中两个向量之间的夹角余弦值。

其中, di为待分类的文本特征向量, dj为第j类的中心向量, M为特征向量的维数, wi, k和wj, k分别为向量的第k维在文本di和dj中对应的权值, wi, j采用如下公式计算:

其中, tfi为词条Tj在文档中出现的次数;dfi表示整个文档集D中包含词条Tj的文档数, 称为文档频率;N表示统计语料中的文档总数。

3 基于遗传算法的主题爬虫的实现

3.1 构造初始群

主题搜索是面向特定主题的, 则初始种子集应该来自该主题领域, 否则爬虫无法展开爬行工作。具体做法是将待检索的问题提交给通用搜索引擎, 对其返回的结果集进行处理, 选择一定数目的URL组成初始群体。

本文选用搜索引擎www.google.cn, 将其返回的结果集的前n个结果页面对应的URL组成集合S1, 再对S1进行如下扩展:

(1) 根据集合S1中网页的入链进行扩展。将集合S1中网页的所有入链对应的URL组成集合S2。

(2) 根据集合S2中网页的出链进行扩展。将集合S2中网页包含的所有出链对应的URL组成集合S3。

(3) 集合S=S1+S2+S3, 同时对集合S进行URL去重。根据公式 (1) 和 (2) , 计算集合S中网页的Authority和Hub值。对集合S中所有网站的月访问量排名进行统计, 本文有关网页访问量的排名是通过网站http://www.123cha.com/alexa/查询得来, Alexa排名是目前常引用的用来评价某一网站访问量的一个指标, 它是根据对用户下载并安装了Alexa Tools Bar嵌入到IE等浏览器, 从而监控其访问的网站数据进行统计的。

将集合S中所有网页按照Authority值的大小进行排名, 则S的Authority排名记为{a1, a2, …ai, …ak}, 集合S的Alexa排名记为{l1, l2, …li, …lk}。则集合{a1m+l1n, a2m+l2n, …aim+lin, …akm+lkn} (其中m=0.8, n=0.2) 记为S的综合排名值。

将集合S的节点根据综合排名从大到小排列, 选取前α (α为预先设定的, 本文α取值80%) 个节点组成初始群S11。同理, 综合集合S的Hub排名和Alexa排名将S的节点从大到小排列, 组成集合H。

3.2 交叉

下载初始群S11中所有URL对应的网页, 提取每个网页包含的超链及关于超链的描述信息, 描述信息通常以文本和图片的形式出现。下面是一个超链的实例:

中关村在线。其中, “中关村在线”是超链“http://www.zol.com.cn”的描述, 也称之为一个“锚文本 (anchor text) ”。

将所有超链的锚文本进行解析, 提取关键词, 再与所搜索的主题的关键词集合进行比对, 从而剔除掉与主题无关的链接, 如广告, 娱乐等。然后利用向量空间模型算法计算剩余超链的描述信息与主题的相关度r, 从而预测超链与主题的相关性。将所有超链的URL按照主题相关度r的大小进行降序排列, 得到的URL集合记为M, 设交叉概率为P1, 则选取前M*P1个URL作为交叉结果, 记为集合S12。

3.3 变异

目录性网页是各种网页链接的集合, 它所链接的网页大多与目录网页本身不相关, 即这部分页面被不相关的网页所链接, 为了增加这部分页面被搜索的机会, 从而扩大网页的搜索范围, 可通过变异操作根据设定的变异概率引入Hub网页。设变异概率为P2, 则从Hub网页集合H中选取前H*P2个URL作为变异结果, 记为集合S13。其中P1+P2=1。

记S14=S11∪S12∪S13, 则S14为第一代遗传的结果, 即主题爬虫进行第一轮搜索得到的URL集合。

3.4 选择

选择操作是将种子集合中适应度 (相似度) 高的个体进行一定的处理, 然后按照预先设定的概率α遗传给下一代, 再开始新一轮的交叉、变异, 直至得到最优解。

下载集合S13中URL对应的页面, 并进行如下处理:

(1) 将页面包含的所有超链进行去重;

(2) 去除已经被搜索到的超链;

(3) 根据超链的描述信息, 提取关键词, 利用向量空间模型算法预测超链对应的URL与主题的相关性。将所有超链按照相关度r的大小进行降序排列, 得到集合N, 选取前N*α (本文设定为80%) 个URL组成集合S21, 并将集合S21作为下一代的种子进入新一轮的遗传。

判断爬虫是否终止种子搜索, 是则终止进化操作, 否则继续进行交叉、变异操作。

3.5 终止搜索

判断爬虫是否终止搜索的方式有以下三种:

(1) 已下载的页面数是否超过用户设定的最大值。

(2) 遗传进化代数是否超出用户设定的最大进化代数。

(3) 是否有新种子出现。

是则终止进化操作;否则跳转到交叉步骤, 继续进化过程。

4 性能评价

4.1 实验设计

本文采用三种算法分别对给定主题进行搜索, 将搜索到的网页根据向量空间模型算法计算其与主题的相似度, 相似度超过给定值的网页被认为是相关网页, 反之为不相关网页。然后分别统计三种算法搜索到的相关的网页数。

(1) Best-First算法:首先利用通用搜索引擎获取初始URL, 再计算URL对应的网页与主题之间的相似度, 选择相似度高的URL进行搜索, 相似度的计算通常采用余弦进行计算。

(2) HITS算法:首先利用一个如Google或Ba--idu的搜索引擎获取与主题相关的网页集合, 再计算集合中所有网页的Authority和Hub值, 优先搜集Authority值大的网页。

(3) GA算法:首先利用Google获取初始种子, 通过选择、交叉、变异等操作, 得到最优解。

4.2 实验结果分析

本文以“搜索引擎”为搜索主题, 从《中国分类主题词表》中得到主题特征集, 并根据资料统计出主题词的权重。相似度计算采用向量空间模型算法。分词采用正向最大匹配算法。

首先利用www.google.cn搜索与主题相关的页面, 获得大约31, 800, 000条查询结果, 选取前100个结果组成集合S1, 然后进行扩展, 再进行交叉、变异等操作。

设定遗传算法的交叉概率为80%, 变异概率为20%。

实验结果分析如图4所示。

此图表明:爬虫搜索初期, 本文提出的遗传算法搜索效率低于BF算法。随着下载的页面数的增加, 搜索到的相关页面数与下载的页面数的比例也随之增加, GA算法的搜索效率也高于BF和HITS算法, 由此可见本文提出的算法具有一定的优势。

5 结束语

本文提出的基于遗传算法的主题信息搜索方案, 是利用遗传算法的全局寻优特点, 同时, 根据网页间的链接结构, 借助超链的描述信息预测链接对应的页面的主题相关度, 一定程度上提高了爬虫搜索效率。

本文在锚文本的提取和分析上还存在一些不足, 下一步的研究重点是从半结构化网页中抽取出有价值的能够代表网页的属性, 例如锚文本、标题和正文等。将这些属性结合起来作为网页的对象, 从而可以更好地预测网页与主题的相关性。

参考文献

[1]Salton.G, Yang.C.A Vector Space Model for Automatic Indexing[J].Communications of ACM.1975.

[2]Cho.J.Garcia-Molina.H, Page.L.Efficient crawling through URL ordering:the Seventh International World-Wide Web Conference[C].1998.Australia.

[3]Kleinberg.J.M.Authoritative sources in a hyperlinked environment:the Ninth Annual ACM-SIAM Symposium on Dis-crete Algorithms[C].1998.USA.

[4]Matthew.P.D.Richardson.The intelligent surfer:Probabilistic combination of link and content information in PageRank.Neural Information Processing Systems[J].2002.

[5]曾春, 邢春晓.基于内容过滤的个性化搜索算法[J].软件学报.2003.

[6]王晓宇, 周傲英.万维网的链接结构分析及其应用综述[J].软件学报.2003.

[7]林海霞, 原福永, 陈金森等.一种改进的主题网络蜘蛛搜索算法[J].计算机工程与应用.2007.

[8]刘国靖, 康丽, 罗长寿.基于遗传算法的主题爬虫策略[J].计算机应用.2007.

遗传优化搜索算法 第8篇

配电网规划的目标是找到最优的电力网络建设方案, 涉及到变电站位置的选择, 馈线段的铺设, 同时又要满足变电站容量、电压降、辐射网络结构等众多约束条件。电网规划问题是一个大型非线性的组合优化问题。目前电网规划问题的研究方法主要有数学优化方法和启发式优化方法。

数学优化方法 (如线性规划、整数规划等) 具有理论完备、计算简单等特点。但在处理此类大型非线性、多约束的优化问题上其简化的数学模型往往会有较大的误差。目前启发式优化方法得到了广泛的应用。诸如:遗传算法、蚁群算法、模拟退火、禁忌搜索等现代启发算法在此类问题上有良好的表现, 而多种启发算法的混合应用, 有利于发挥特定算法的优势, 克服单一算法的不足。 文献[2]应用遗传算法处理配电网优化问题, 在规模的配电网规划上有良好的结果, 但缺乏对算法的收敛和全局最优问题的讨论。文献[3], [4]采用了混合算法解决此类问题, 但由于是在计算的两个阶段分先后应用某种算法。故存在算法之间的数据依赖。研究表明, 单独应用某个启发算法存在一些不足, 而多种启发式算法的混合应用方式也是值得研究的课题。

遗传算法是一种并行的群体搜索算法, 它结果不依赖于初始值的选取, 适合于求解类似复杂非线性优化问题。但是它存在容易发生“早熟”或收敛速度慢, 计算效率低等问题, 算法最终不能给出令人满意的解。文献[6]在传统遗传算法的基础上, 提出了一种快速环路分解遗传算法, 有效提高配电网络的重构计算收敛速度。禁忌搜索的特点是采用了禁忌技术, 禁止重复以前的工作, 需要的迭代次数少, 搜索效率高, 适于解决配电网规划等纯整数规划问题。 但它是从一点出发沿一条线路搜索, 最终解的质量和收敛速度与初始解的优劣有很大的关系。本文提出的遗传-禁忌混合算法将两者的优化行为结合起来, 既可以削弱参数选择的苛刻性, 又可以优化搜索性能。有别于常规的混合算法, 本文利用禁忌搜索思想改造遗传算子, 使传统的遗传算法具备一定的“爬山能力”, 实验表明其全局搜索性能与局部优化能力均强于单个的启发算法。

1 配电网规划优化模型

在变电站供电范围已知的情况下, 配电网规划寻优的数学模型可以表示为:

undefined

满足:

undefined

式中:ῶ为年等值系数;k 为线路的编号;Nk为可能构成的辐射网的线路编号的集合;Xk表示线路k为新修线路时取 1, 已有线路时为0-1间的小数;I (lk ) 为线路lk的电流;Imax (lk) 为线路lk 最大允许电流;S为符合点个数;s为节点编号;Vmin为节点电压下限;Vmax为节点电压上限;Kmax为优化后的线路条数。求解目标是满足约束条件的线路编号集合。对于此类规划问题, 显然用数学优化方法求解是十分困难的。

2 TS-GA混合算法

2.1 编 码

本文采用直观的二进制编码。这里需要对线路的取舍、线径的选择进行编码。对于本文算例中的33条线路中的每条线路有以下规划选择方案:

线路: ①已有;②铺设;③不铺设。

线径:A.185 mm2;B.240 mm2;C. 300 mm2。

假定这里仅考虑单回线路, 我们可以这样定义该线路对应的基因组合:0110。前两位代表3种可能的线路方案中的一种, 后两位代表三种线径中的一种。将规划中的所有线路按顺序串联起来, 构成一个染色体。如图1是一个染色体片断。

二进制编码简单直观, 解码方便, 缺点是如果节点过多, 染色体长度会较长。

2.2 适应度函数

本算法将优化方案中的染色体解码后计算其目标函数的值。利用该值的大小来反映规划方案的优劣。计算方法如下:

(1) 染色体解码, 得到一个优化方案。

(2) 检查规划方案是否符合配电网的连通性和辐射性。

(3) 潮流计算得到网损和线路的电压降。

(4) 满足约束条件的解代入目标函数 (公式 1) , 计算其适应度值。

2.3 改进的遗传-禁忌算子

2.3.1 期望值选择

遗传算法中的选择操作是指从父代群体中选择优良个体并淘汰劣值个体的操作。这里用染色体的适应度函数作为评估的标准。如果采用轮赌方法决定个体的选中的概率。设群体规模为N, 个体i的适应度值为 fi, 其被选中的概率为:

undefined

在原始种群规模不大的情况下, 由于统计的误差, 依据产生的随机数进行路由选择有可能淘汰适应度较高的个体。本算法采用期望值模式来选择下一代个体, 算法如下:

(1) 计算群体中个体在下一代中的生存期望值:

undefined

(2) 对期望新定标处理:对适应度大的个体其期望值减去0.5, 对适应度小的个体, 其期望值减去1。

(3) 期望值为0的个体不被选择。实验表明, 基于期望值的选择方法比赌轮法能更好的选择出优良的个体参与杂交运算。

2.3.2 禁忌杂交算子

传统的遗传杂交算子的目的在于扩大解的空间, 避免陷入局部最优。但交叉算子使群体中的染色体具有局部相似性, 从而使搜索停滞不前。本文在交叉算子中引入禁忌表, 表结构如表1所示。

染色体采用先进先出方式 (FIFO) , 表的数据行数称为禁忌表的长度, 它表示表中染色体的停留步数。染色体从表的底部向表上部移动, 表中第一行数据将移出禁忌表。禁忌表的长度将直接影响到搜索的进程和行为。表1中禁忌表的长度为4。

禁忌杂交算法如下:

(1) 初始化禁忌表为空。在父代群体中选取两个染色体进行杂交运算。

(2) 计算子代染色体的适应值, 如果该值大于父代群体适应值的平均值。将其移入下一代群体, 并移入禁忌表。反之, 作如下操作。

(3) 如果子代染色体不在禁忌表, 即使其适应度值比禁忌表中的“目前最好值”差, 也将其接受为下一代群体成员。并移入禁忌表。

(4) 如果子代染色体在禁忌表中, 其适应度值比禁忌表中的“目前最好值”差, 则丢弃该染色体。

(5) 如果子代染色体在禁忌表中, 其适应度值比禁忌表中的“目前最好值”好, 则按照“藐视规则”将其接受为下一代群体成员。并移入禁忌表。其适应度值设为目前最好值。

在禁忌杂交算法中, 具有高适应值的子代进入到下一代的机会是很大的, 但是并不是所有的高适应值的子代一定都进入到下一代。因为禁忌杂交算法使用了禁忌表, 它可以限制适应值相同的子代出现的次数, 因此可使群体中尽可能保持染色体结构的多样性, 从而避免算法早熟。

2.3.3 禁忌变异算子

遗传算法中的变异操作的目的是为了产生更为优良的种群。从父代P的基因中随机选择变异基因进行基因变异操作。 (0-1 和1-0) 变异概率Pm一般设为 0.001。 避免算法退化为随机搜索。为了防止算法陷入局优, 同样引入变异禁忌表, 如表2 。

杂交算子禁忌表中增加了一个变异基因位栏目。用于记录发生变异的基因位的序号。染色体同样采用先进先出方式 (FIFO) 。

禁忌变异算法如下:

(1) 初始化禁忌表为空。在父代群体中选取染色体进行变异运算。

(2) 每次发生变异时, 都将变异基因位的序号与禁忌表中的序号进行比较, 若不在表中, 则可进入下一代, 并移入禁忌表。

(3) 若变异后的个体的适应值大于目前最好值, 则“破禁”, 可进入下一代, 并移入禁忌表。

(4) 若变异后的个体的适应值小于目前最好值, 则放弃该变异操作结果。

3 算 例

图2是某配电网改造工程中的一张社区平面图。该区域共有33条规划线路, 20个负荷点。粗线表示已有线路, 细线表示规划中的线路。节点15为变电站的位置。表3、表4给出了各负荷点的负荷需求和可用线径。

图3给出了基于 GA-TS混合算法的最优规划方案, 表4给出了方案中的各段馈线的线径选择。从实验结果分析中, 我们发现无论单独应用遗传算法, 或禁忌搜索算法, 其解的质量均比本混合算法差, 本文算法结果更贴近实际需求。具有较高的实际应用价值。

4 结 语

从上面的分析和算例研究表明, 在配电网优化问题上, 遗传算法费时长, 易于陷入局部最优, 禁忌搜索具有搜索时间短, 可以接受劣值解, “爬山”能力强等特点, 但它依赖于良好的初始解, 本文利用禁忌搜索思想改造遗传算子, 使得禁忌杂交算子、禁忌变异算子可以引导算法较快地找到全局最优解。遗传-禁忌搜索混合算法可以应用到同类的非线型整数规划问题上。

参考文献

[1]Ramirez-Rosado l J, Bernal-Agustin J L.Genetic algorithms ap-plied to the design of large power distribution system[J].IEEETrans on Power System, 1998, 13 (2) :696-703.

[2]谢敏, 敬东.遗传算法在配电网规划中的应用[J].电站系统工程, 2002, (1) .

[3]陈根军, 唐国庆.基于禁忌搜索与蚁群最优结合算法的配电网规划[J].电网技术, 2005, (1) .

[4]顾浩.混合遗传-模拟退火算法在电网规划中的应用[J].上海交通大学学报, 1999, (4) .

[5]陈国良, 王熙法, 庄镇泉, 等.遗传算法及其应用[M].北京:人民邮电出版社, 2001.

遗传优化搜索算法 第9篇

修理级别分析(Level of Repair Analysis,LORA)用来评估综合后勤保障中系统全寿命成本的影响要素, 以实现最低全寿命维修成本的系统设计。LORA是一个确定失效部件应报废还是修理,以及在修理网络中什么位置执行这些活动的过程。

现有文献中讨论了不同的多层、多级的LORA模型［１－９］,这些模型无不涉及大量的决策变量,因此,通过传统优化方法如整数规划和分支定界等很难对LORA问题进行优化求解,而遗传算法及其混合策略在求解非常耗时的大规模组合问题时显示出了极高的效力。鉴于此,本文提出一种遗传禁忌搜索混合算法, 将其应用于LORA问题求解,并利用算例的比较分析,表明该算法能在可接受计算时间内求得最优解。

1 LORA问题模型的建立

1.1航空装备维修级别和层次划分

LORA分析是以维修级别与装备修理的约定层次的划分为基础的。维修级别根据装备的范围和深度区分任务,并按维修时所处场所划分等级。航空装备维修级别分为三级,即基层级(O)、中继级(I)和基地级(D)。装备修理约定层次一般划分为外场可更换件(LRU)、车间可更换件(SRU)、车间可更换件子部件(SSRU)三个层次。对于一个给定的设计,修理级别分析师必须决定哪些部件要修理、哪些部件要报废、在修理网络中何处执行这些活动,从而确定部件进行修理或报废的位置,并以最低成本满足维修要求。

1.2建立数学模型

本文研究中,设i为所研究系统的部件,i=1,2,…,n,n为部件总数;r为修理选项,包括修理、报废、移动; e为维修级别。本文参考文献[1,3,4]所描述的模型, 对LORA问题进行建模,通过最小化维修成本获得最优修理决策。

建立的数学模型如下:

其中:ＶCｒ，ｅ，ｉ为部件i在维修级别e上执行修理选项r的可变成本;λｉ为部件i全寿命周期内所需维修任务的总次数;ＦCｒ，ｅ，ｉ为部件i在维修级别e上执行修理选项r的固定成本;Xｒ，ｅ，ｉ为决策变量,Xｒ，ｅ，ｉ=1,表示部件i在维修级别e上选择了修理选项r,否则Xｒ，ｅ，ｉ=0。

式(1)是目标函数,对执行修理和报废活动的固定和可变成本求和,并使其最小。约束条件如下:

式(2)确保在基层级(e=1)选择一个修理选项。 式(3)表示如果在e级上采取移动决策,在e+1级上应只采取修理决策,否则,在e+1级上不选择任何修理选项。式(4)表示子部件与父部件在各维修级别上采取相同的报废或者移动决策;j表示部件i的子部件。式(5)表示在最高级维修级别上(e=3)仅有两种修理决策(修理或报废)可供选择。

2求解算法设计

2.1算法思路

遗传算法和禁忌搜索(Tabu Search,TS)都是求解组合优化问题的常用算法［１０］。遗传算法及其混合策略在求解非常耗时的大规模组合问题时显示出了极高的效力,缺点是当种群规模较大时求解速度较慢,而禁忌搜索又较依赖于初始解。因此,提出两者混合算法即GATS算法,克服两种算法的缺点并保留各自的优势,对NP-hard和组合优化的LORA问题进行求解。

本文的GATS算法首先生成N个初始可能解; 然后利用禁忌搜索的迭代过程进行邻域搜索,对这些解进行更新;之后,流程返回遗传算法,再进行一个迭代过程;通过遗传算子产生新的后代,并根据新的后代的适应值对最佳解的禁忌表进行更新。GATS算法的终止准则是达到了预定义的连续迭代次数,迭代过程获得的最佳解相同。

GATS算法流程如图1所示。

GATS算法的具体步骤如下:

(1)随机产生一个解集(20个解),验证式(2)、式(3)、式(4)、式(5)。

(2)通过邻域搜索改进解的适应度值。邻域解仅通过修改解的值为1或0获得。另外,直到验证了式(2)~式(5),才接受邻域解。然后,更新禁忌表,其中包含所有已探索过的解的适应度值。接着,仅当适应度值不出现于禁忌表中时,探索一个新的邻域。

(3)重复步骤(2),直到最佳适应度值没有改进

(4)用最佳邻域替换该解。

(5)基于遗传算法的选择算子和交叉算子,选择两个解来产生新的染色体。当验证了式(2)~ 式(5) 时,接受这些新的解。

(6)利用变异算子,生成新的染色体。

(7)更新最佳染色体的禁忌表。

(8)重复以上步骤,直到最佳染色体没有改进。

2.2 GATS算法设计

2.2.1编码方式

用遗传算法求解特定问题时,首先要确定编码方式。本文采用的编码方式是一个二进制矩阵(n×d), 其中n为所有部件(即项目)的数量,d为所有修理决策的数量。该编码方式中,xｉｊ=1意味着部件i和级别j选择了修理、报废或者移动决策。图2是染色体或解的二进制编码方式,其中“项目”表示待分析产品, 可以是部件或子部件。

另外,任何技术系统都可视为装配的集合,这些装配又可视为一些子装配的集合。出于建模的考虑,系统分解结构用一个矩阵来表示,称为共性矩阵,如图3所示。其中列代表父部件,行表示子部件,子部件4、 5、6属于父部件3,或者说父部件3包含了子部件4、 5、6。根据式(4),无论何时父部件3采取报废或移动决策,子部件4、5、6都将采取同样的决策。

2.2.2适应度函数

本文的目标函数是求解最小值问题,算法的选择过程采用轮盘选择法,因此本文采用的适应度函数为:

其中:Cmax为f(x)的最大值,

2.2.3遗传算法算子

GATS算法使用适应度值比例选择的轮盘赌抽样作为交叉算子。每一代采用最优保存策略,用满足式(1)的最好的解替换最差的。选择一对父代进行交叉运算产生两个新的子代。交叉算子通过交换信息作用于这两个父染色体。由于每一对父代染色体的基因密码有着相同的结构,因此随机选择交叉点进行单点交叉,接着根据式(4)调整子代修理决策。

变异运算是遗传算法的另一重要特点,是产生新个体的辅助方法,变异运算的目的是维持群体的多样性,防止解陷入局部最优。本文中变异算子从最优解列表中随机选出一个染色体,并用一个同样是随机产生的新的染色体替换;另外,选择一个最优解,并随机为部件产生一个修理决策;然后再根据式(4)调整修理决策。

2.2.4邻域结构

TS的框架由产生自初始解的一些邻域解组成,通过目标函数对这些解进行评估并分类。禁忌表通过最优解的适应度进行更新,然后确定一个新的解并从中产生额外的邻域搜索。当一系列迭代之后最佳解保持不变时,便求得了最优解。本文采用互换的方法产生邻域结构。

2.2.5禁忌对象和禁忌表的确定

本文将禁忌对象设定为状态本身,将每次迭代最终接受的解作为禁忌对象放入禁忌表中。禁忌表是禁忌对象的集合。

3实例分析

本节将根据数值实验的结果测试GATS算法的有效性。为了比较起见,对文献[3]执行过的案例进行研究。文献[3]中给出了航空发动机的三层结构和两级修理网络,以及所有项目在不同级别上不同修理选项的固定成本和可变成本。另外,图4给出共性矩阵, 显示父部件(项目1到项目10)与子部件(项目11到项目32)之间的关系。用MATLAB语言对GATS算法进行编译,并在电脑上实施该算法。表1为本文GATS算法获得的最优解,与文献[3]的修理决策相同。另外,文献[7]中也对文献[3]执行过的案例进行了研究,其中所使用的免疫粒子群算法(IA-PSO)和本文GATS算法得出相应的总维修成本分别是4 277.27美元和4 216.27美元,计算时间分别为32s和21s,如表2所示。

4结论

(1)在现有LORA研究的基础上,对LORA问题进行了建模,以最小化维修成本为目标,获得最佳修理级别决策。

(2)利用遗传-禁忌搜索混合算法,对LORA问题进行了优化求解,并给出了算法的求解步骤。利用文献[3]中的数据,通过算例的比较分析,对三级修理网络和多级系统结构的修理决策进行了优化,结果表明在合理的时间内可获得LORA问题的最优解,证明该算法是切实可行的。与免疫粒子群算法的比较结果表明了本文算法的有效性。

遗传优化搜索算法 第10篇

针对遗传算法局部搜索能力差的缺陷, 一些学者提出了将遗传算法与局部搜索算法相结合的方法用于解决函数优化[1,2]和多段供应链[3]等优化问题。本文也提出了一种遗传算法与局部搜索算法相结合的方法, 这种方法与上述方法最大的区别在于局部搜索过程中引入了混沌, 同时, 混沌局部搜索是否进行受自适应策略控制, 这种方法以下简称为ACLSGA。

2 自适应混沌局部搜索策略的遗传算法 (ACLSGA)

2.1 混沌局部搜索

混沌是自然界广泛存在的一种非线性现象, 具有随机性、遍历性和对初始条件的极度敏感性等特点, 在一定范围内能够按其自身的规律不重复地遍历所有状态。本文采用的混沌系统为[4]:

式中, k为迭代次数, k=1, …, K, K为最大的迭代次数。α、β为控制参数, α∈ (0, 1) , 当β>=2时, 方程式 (1) 是一个混沌系统。

混沌局部搜索描述为:

begin

设置混沌系统参数和混沌搜索次数M;

根据混沌系统得到一个长度为M的混沌序列;

选择当前种群中的最佳个体vc;

混沌搜索初始计数器t=0;

while (t<M)

叠加混沌序列中某一项到vc中任一维上形成新个体vn;

计算新个的适应度值;

2.2 自适应策略

遗传算法在初始进化阶段具有较好的多样性, 而到了后期个体之间的多样性不断减少, 进化过程缓慢或停滞。为了充分发挥遗传算法自身的特点, 混沌局部搜索并不是在一开始就执行, 而要等到遗传算法进化到一定的程度才执行。进化程度的度量标准引入文献[1]中的一种自适应策略, 这种自适应策略定义为:

如果FVR (t) >1, 则执行混沌局部搜索, 否则不执行混沌局部搜索。

2.3 自适应混沌局部搜索策略的遗传算法的描述

本文研究的问题为连续变量的全局最小最优问题, 这类问题可以描述为:f:S→R为n维实值函数。函数f在S域上全局最小化就是寻求点Xmin∈S, 使得f (Xmin) 在S域上全局最小, 即坌X∈S:f (Xmin) <f (X) 。

用遗传算法解决上述问题通常采用实数编码的具有精英保留选择机制的遗传算法[5]。本文遗传算法的交叉方式、选择方式和变异方式分别采用均匀算术交叉、锦标赛选择和高斯变异, 这种遗传算法以下简称为RGA。根据上面的情况, ACLSGA的步骤为:

步骤1:初始化参数:种群规模NP, 种群最大进化代数Gmax, 问题的维数D, 输入变量的上界H和下界L。

步骤2:初始化种群:

其中, rand为 (0, 1) 的均匀分布的一个随机数。

步骤3:置进化代数G=1。

步骤4:执行一次RGA, 找出适应度值最佳的个体Xbest, 记Xbest的适应度值为Fbest。

步骤5:计算连续两代平均的适应度比值, 若, 则转步骤7, 否则继续。

步骤6:执行2.1中的混沌局部搜索。

步骤7:, 如果G<Gmax, 转步骤4;否则继续。

步骤8:输出Xbest和Fbest。

3 仿真实验

为检验ACLSGA的有效性, 从文献[6]中选择2个基准的全局最小化函数来进行评价, 两个测试函数如下:

3.1 Sphere函数

3.2 Griewank函数

上述函数中, f1为单峰独立函数, f2为多峰独立函数, 2个函数的全局最小值都为0。

下面, 对ACLSGA和RGA进行比较。实验环境为Matlab中, 种群规模NP=50, 种群最大进化代数Gmax=1500, 混沌控制参数α=0.9、β=2.0, 混沌搜索次数M=25。以20次实验的最大最优值、最小最优值、平均值、标准差作为比较的评价标准, 得到的寻优结果如表1所示。

从表2中可以看出, 2个函数对应性能指标ACLSGA都比RGA要好。

为了更好地比较两种算法总的寻优结果, 20次实验每代平均的收敛结果如图1和图2所示。图中, 纵坐标为误差函数|f (x) -f (x) |的对数值 (误差函数中, f (x) 为全局最优值, f (x) 为算法找到的最优值) , 横坐标为进化代数, 蓝色实线、红色实线分别表示RGA、ACLSGA的收敛曲线。从收敛曲线图上可以看出, ACLSGA的收敛速度比RGA都要快。

4 结束语

本文提出了一种自适应混沌局部搜索策略的遗传算法 (ACLSGA) , 通过2个测试函数优化结果比较证明:ACLSGA比RGA的寻优效果好, 收敛速度快。

参考文献

[1]Yun, YS.Hybrid genetic algorithm with adaptive local search scheme[J].Computers&Industrial Engineering, 2006, 51 (1) :128-141.

[2]Yun, YSu, Moon C, Kim D.Hybrid genetic algorithm with adaptive local search scheme for solving multistage-based supply chain problems[J].Computers&Industrial Engineering, 2009, 56 (3) :821-838.

[3]Coskun Hamzacebi.Improving genetic algo-rithms'performance by local search[J].Applied Mathematics and Computation, 2008, 196 (1) :309-317.

[4]YANG LI-JIANG, CHEN TIAN-LUN.Appli-cation of Chaos in Genetic Algorithms[J].理论物理通讯 (英文版) , 2002, 38 (2) :168-172.

[5]田小梅, 龚静.实数编码遗传算法的评述[J].湖南环境生物职业技术学院学报, 2005, 11 (1) :25-31.

遗传优化搜索算法 第11篇

关键词：遗传算法网架结构配电网优化

1 问题的提出

配电系统中的网架结构优化问题主要有两个特点：非线性和整数性，这也正是解决问题的困难所在。用非线性规划方法解题常常会遇到搜索方向错误，迭代不收敛，逼近速度慢等问题。当变量和约束条件数目较多时，这些问题更加突出。另外，线路都是按整回和确定的电压等级来架设的，若变量取线路的某电气量，则变量应是整数值或某种离散值。对于这样的非线性整数规划问题，目前还没有理想的优化算法。若试图严格地解决这种问题，将会遇到一个典型的组合数目以指数形式增长，即所谓“组合爆炸”问题。综观以前的各种传统优化方法，各有优势，要么容易偏离最优解陷入局部最优，要么受到维数的限制而难以达到实用的目的。为了解决这两个方面的问题，下面把遗传算法引入城市电力网网架结构的优化中来，以欺得到一个较满意的解决问题的办法。

2 遗传算法介绍

遗传算法是一种搜索算法，是通过模拟自然进化过程来搜索最优解的方法。其目的是解释自然界的自适应过程而设计的一个体现自然界进化机理的软件系统。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择决定了群体中哪些个体能够存活并繁殖，即适者生存，不适者淘汰；有性生殖保证了后代基因中的混合与重组，加快了进化过程。由于该方法隐含并行性和全局信息的有效利用能力，尤其适合于处理传统搜索方法解决不了的复杂问题，近十多年來在各领域得到广泛应用。

遗传算子：一个简单的遗传算法由复制、杂交和变异三个遗传算子组成。其中复制算子是把当前群体中的个体按与适应值成正比的概率复制到新群体中去。这样，低适应值的个体趋向于被淘汰，高适应值的个体趋向于被复制，复制算子的作用效果提高了群体的平均适应值，也充分体现了“优胜劣汰”这种自然进化机制；杂交算子是模拟生物界的有性繁殖，可以产生新的个体，使其比它的两个父代有更高的适应值。杂交算子是遗传算法的重要组成部分；变异算子是用一个很小的概率随机地改变染色体串上的位置，其效果是增加群体的多样性，扩大搜索空间。

主要特点：遗传算法与传统的优化算法相比，主要体现在它不是直接作用参变量集上，而是利用参变量集的某种编码；不是从单个点，而是从一个点的群体开始搜索，因而能够快速全局收敛；它还利用了概率转移规则，而非确定性规则，因而能够搜索离散的有噪声的多峰值复杂空间；以及利用适应值信息，无须导数或辅助信息，具有广泛的适应性；在解空间内进行充分的搜索，但并不是盲目地穷举或瞎碰，因此在其搜索时间和效率上往往优于其他优化方法。首先，它在搜索过程中不容易陷入局部最优，即使在所定义的适应函数是不连续的、非规则的或有噪声情况下，它也能以很大的概率找到整体最优解。为了寻找最优解，传统方法是用启发式策略，在单个猜测解的领域寻找，即使算法中允许偶尔地跳到解空间中更远的部分，这些启发式算法也往往趋于局部最优。理论上遗传算法像撒网一样，通过保持在参变量的解空间区域中的多个点的搜索可以以很大的概率找到全局最优解。其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。由于遗传算法的操作主要是在单个位串上，至多是一对位串之间的杂交，所以可让每个处理机负责处理单个位串，从而可以并行处理整个群体。

计算步骤：在进行个体遗传算法之前，需要作好如下准备工作。首先是选择编码；一般编码选择由多个二进制串（0，1）构成，其中“0”、“1”分别表示支路不连通和连通。应注意的是编码不局限于二进制，根据对象不同也可选其他的数来编码。其次是确定适应值函数；相当于确定数学规划中的目标函数。然后在选择控制算法的参数；最后确定停止运行的准则。

3 网架结构优化的遗传算法

网络结构优化的目标函数：网络结构优化问题是基于现有网架结构，在已知水平年电源及负荷需求下，并假定变电站的扩建或新建的时间、地点和容量都已确定，决定在规划期内何时何地架设多少回输电线路，以使得线路年费用最小。这里采用考虑了贴现的线路建设投资费用和运行费用的最小年费用法，即。其中Z为方案总的线路建设投资费用，为方案第年的运行费用。

编码的选择：遗传算法是一个搜索特征串空间的过程，其目的是找到具有相对高适应值的串。在应用遗传算法求解特殊问题之前，第一步就要确定用类似于染色体的串来表示问题的办法，即染色体的编码形式。这里采用二进制编码形式，直接对待选线路进行编码，反映其是否架设，以及选用多大截面等。这种编码形式非常直观，便于规划方案和染色体之间的编码和解码。若只考虑线路架设与否，则可将各待选线路排序，然后按此顺序将每条待选线路作为染色体串中的一个基因，每个基因是一个一位的二进制数。当基因值为1时，表示其对应的待选线路被选中加入系统，当基因值为0时，则相反。但考虑到对方案进行评估时需对方案所表示的网络进行潮流分析，这样的染色体解码成规划方案时应能得到线路参数，所以需在基因中加入线路截面的信息。

城网优化遗传算法的计算过程：首先输入原始数据；其中包括网络拓扑，即节点数、已有和待架线路数、各线路的首末节点号和线路的有关参数。节点的发电出力及负荷，遗传算数本身所需参数，即群体大小、基因位数、最大遗传代数、变异率和计算适应函数时用到的有关参数等。然后形成初始方案，接着计算适应值，进行遗传操作，最后输出计算结果。

适应函数的建立：在编码方案选定以后，接着就是要确定适应函数以检测由特定位串所表示的规划方案的好坏程度，从而指引遗传操作的正常进行。适应函数应该反映电网规划的目的和要求，即要使规划方案在满足正常运行要求和安全运行要求的情况下，使电网的建设和运行费用最小。建设费用和运行费用最小的目标函数，在考虑约束条件后的增广函数数学模型为。其中为方案的年费用，为惩罚因子，为方案的约束条件。电网规划的目的是希望电网的建设和运行费用最小，为符合遗传算法最大值的特点，适应函数可表示为。其中的选取以保证为非负数为准。由的表达式可知适应函数是一个非线性的、不连续和非凸的，这对于严格的数学规划方法是难以求解的，而遗传算法则是在解码得到一个解之后才对适应函数进行计算评估的，因此对适应函数形式无任何限制，这充分显示了遗传算法的优越性。

参考文献：

[1]孙杰.基于单亲遗传算法的配电网络优化规划[D].华北电力大学（河北）.2005年.

[2]闫大威.基于遗传算法的城市中压配电网规划自动布线[D].天津大学；2005年.

遗传优化搜索算法 第12篇

1 问题分析

最优路径规划, 通常是指在一个赋权图的两个指定节点 (起始点和目标节点) 之间找出一条具有最小权的路径。在实际复杂地形中的最优路径规划与正常环境下的最优路径之间存在明显的差异, 前者虽然本质上属于图论中最短路线问题的范畴, 但由于多个决策目标的存在, 不能直接运用最短路线模型求解[1]。

遗传算法具有全局寻优和潜在并行的特点, 对求解最优路径具有一定优势[2]。但传统遗传算法操作时会产生大量无效路径, 因此为了提高求解最优路径问题的效率, 采用改进的遗传算法求解, 并有效的避免了传统遗传算法的“早熟”现象。

2 算法设计

2.1 遗传算法介绍

遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。遗传算法是解决搜索问题的一种通用算法, 对于各种通用问题都可以使用。遗传搜索算法的特征为:首先组成一组候选解;依据某些适应性条件测算这些候选解的适应度;根据适应度保留某些候选解, 放弃其他候选解;对保留的候选解进行某些操作, 生成新的候选解。

2.2 遗传算法改进

基于以上, 我们选择遗传算法作为解决此问题的基本算法。但遗传算法也有它本身固有的缺陷, 例如种群早熟、陷入局部最优、多次进化后种群向纯种发展等。因此我们在传统的遗传算法上又做了如下的改进:

1) 初始种群时按照一定的概率选择距离出发点最近的点作为到达点。基于行走路线不能交叉的原则, 出发点与到达点之间大部分都应该是距离最近的且未走过的点。因此初始化数据时系统自动以一定的概率选择最近的点作为下一个到达点。

2) 遗传算法求得最优解易陷入局部最优, 因此在时间允许的范围内多次调用遗传算法求得最优解。调用中可以把上次求得的最优解作为下一次初始种群的一部分参与进化。求解最优解后为了防止个别点的交叉, 对于最优解又进行了优化处理以进一步求得最优解。

3) 遗传算法中要对种群进行排序, 保留最优个体群, 删除最差个体群。但删除最差个体群时, 必然会破坏种群多样性, 导致种群向纯种方向进化。因此我们在使用最优个体覆盖最差个体时, 将最优个体反向覆盖最差个体, 这样, 即保留了个体的多样性, 又保证了迭代进化的方向。

2.3 数据结构设计

2.3.1 图与基因的描述

根据题目描述, 采用完全图的方式描述图, 采用邻接矩阵的方式存储图。若是实际中的地图, 只要把其中两点间的距离定义为足够大, 程序也能求解 (在本文中不讨论) 。

1) 记录距离的图描述

public double[, ]Cost_table;

2) 记录速度的图描述

public double[, ]Speed_table;//随机生成个点之间的速度值

3) 基因信息的描述

2.3.2 遗传算法的全局参数

根据大量的实际测试, 最终确定了遗传算法的参数如下:

2.4 遗传算法的实现

1) 初始化种群。完成对种群的初始化, 并记录当前的最优基因。初始化时按一定的概率选择未走的最近点作为下一点。

2) 基因个体交叉。两两交叉, 随机产生交叉点。为防止出现个别点的重复出现, 只复制一半, 另外一半程序自动搜索剩余的未被走到的点。

3) 基因变异。进化后期, 为防止种群早熟, 会提高变异率。变异时, 自动生成两个路径点, 然后逆置两点间的路径。

4) 种群进化。种群按照指定的迭代次数进化, 进化中记录当前的最优解, 并将最优解作为下一代的优秀基因保存并参与进化。

5) 最优解优化。对于最优解进行局部最优的判断, 若出现个别局部不优秀的解, 给予适当的微调整。

3 结果分析

3.1 实际运行结果

图1、图2依次为客户数等于50、100时的运行结果。

从大量的结果来分析, 在客户数少于等于30时, 系统能找到最优解, 当客户数大于30小于等于100时, 系统能找到近似最优解。我们大胆预测, 该近似最优解与实际最优解之间的误差小于3%。实际上我们也可以减少遗传算法的执行次数, 这样得到的最优解误差会大一些, 大该在8%左右。但实际运行时间会缩短, 我们测试100个客户时, 大约的运行时间为3分钟 (取决于硬件配置) 。

4 结束语

遗传算法的执行效果很大程度上取决于变异概率、种群大小、迭代次数、交叉算子等参数。因此对于某个问题, 需要大量的时间去摸索配置参数, 我们经过大量的测试最终选择了现在的参数设置。但当客户数的数量变大时, 这样的参数是否还是最优的有待继续的测试。我们总结以下几个改进方向:1) 交叉可以考虑多个个体参与交叉。2) 优化时不一定按照当前最优优化, 而应该在一定概率上接收当前的非最优结果。3) 变异要以更多的方式进行, 而不是现在仅有的一种方式。

参考文献

[1]汪祖柱, 程家兴, 方宏兵, 等.车辆路径问题的混合优化算法[J].运筹与管理, 2004 (6) :482-521.

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