遗传优化搜索算法

2024-05-20

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

遗传优化搜索算法篇1

关键词：多目标组合优化,适应度赋值,局部搜索

0 引言

现实世界的很多问题常常要考虑多个相互冲突的目标。多目标问题的最优解通常不是单个解,而是一组Pareto最优解。20世纪80年代中期作为关键智能计算技术之一的进化算法开始应用到了多目标优化领域,并逐渐形成了众多的多目标进化算法。其中,遗传算法和局部搜索的混合,常常表现出胜过“纯”遗传算法的较快的收敛速度和较高的全局搜索能力[1,2,3,4,5]。Ishibuchi和Murata在文献[1]中建立了基于随机加权和的多目标遗传局部搜索算法IM-MOGLS(multi-objective genetic local search algorithms),其主要思想是每代随机地产生一组权重,用于进化过程中双亲的选择和局部搜索过程中搜索方向的确定,局部搜索作用于当前群体的每一个个体上。Jaszkiewicz在文献[3]也建立了一种多目标遗传局部搜索算法J-MOGLS,主要做法是根据随机权重确定的标量化函数,从当前群体中选择一定数目的不同个体,构成临时群体,从中选择两个个体交叉,得到的新个体进行局部搜索。本文对Deb等人提出的著名的NSGA-Ⅱ算法[6]加以改进,并与局部搜索相结合,提出了一种不同的多目标遗传局部搜索算法MOGLS。该算法采用基于分散度的精英选择策略和二元赌轮选择操作,并采取非劣解并行局部搜索策略,在改善算法收敛性的同时,保持了群体的多样性。通过对一组多目标flow shop问题的求解,与IM-MOGLS[1]、J-MOGLS[3]、NSGA-Ⅱ[6]算法进行比较,验证了本算法的有效性。

1 问题描述

一般地,多目标组合优化问题可描述如下[7]:

Minimize z=f(x)=(f1(x)=z1,…,fr(x)=zr)

Subject to x∈Ω

其中,f(x)为具有r个分量的目标向量,x是离散的决策向量,Ω是可行解的集合,点z=f(x)是解x∈Ω在目标空间中的像。

如果对任意的j∈{1,2,…,r},有zj≤zj′,并且至少存在一个j,有zj < zj′,则称点z=(z1,…,zr)支配点z′ = (z1 ′,…,zr′)。

如果解x的像支配解x′的像,则称解x支配解x′。

如果不存在x∈Ω使得z=f(x)支配z*=f(x*),则称解x*∈Ω是Pareto最优解(或非劣解)。

Pareto最优解组成的集合称为Pareto最优集。Pareto最优集在目标空间的像称为Pareto前沿(或非劣前沿)。

2 多目标遗传局部搜索算法(MOGLS)

2.1 精英选择策略

本文MOGLS算法使用两个群体:进化群体和外部群体。外部群体用来保存进化过程中产生的所有非劣解。在每次迭代中,从外部群体NDt中随机选择Nelite个精英解,组成精英解集Et,加入到当前群体MPt中,形成联合群体MPt∪Et。让目前所发现的所有非劣解都有机会参与局部搜索,以提高算法的收敛性。

从外部群体NDt中选择Nelite个精英解的过程如下:首先计算外部群体中每个个体与其他个体在目标空间中的欧几里德距离,将其中的最小值作为该个体的分散度。然后选择Nelite个分散度最大的个体,当外部群体中的个体数不足Nelite时,不足的部分再从外部群体中依据分散度由大到小的顺序依次选择。这种策略不但操作简单,而且能够选择密度较小的外部群体中的个体,有利于维持群体多样性。

2.2 个体的适应度赋值和选择

多目标进化算法中,适应度赋值是关键技术之一。本文在NSGA-Ⅱ非劣分级及拥挤距离评估的基础上,提出如下适应度赋值方法:

(1) 采用NSGA-Ⅱ的快速非劣分级技术将当前群体Pt划分为k个子群体,F1,F2,…,Fk;非劣等级分别为1,2,…,k;等级为1的个体为当前群体的非劣解。

(2) 然后使用NSGA-Ⅱ的拥挤距离评估方法对每一等级的非劣前沿上的点E∈f(Fi),i=1,2,…,k,计算拥挤距离dist(E)。

(3) 令等级k+1的最大适应度为0,即maxfitnessk+1=0。

(4) 对等级为j的个体x∈Fj,计算其适应度fitness(x)。

fitness(x)=maxfitnessj+1+dist(f(x))

(5) 计算等级j的最大适应度maxfitnessj。

maxfitnessj=max{fitness(y):y∈Fj}

(6) 如果j≤1则停止,否则j=j-1,返回步骤(4)。

上述适应度赋值过程,是从第k级开始,逐级计算每一等级个体的适应度值,直到第1级的,等级为j的个体的适应度等于其本身拥挤距离与等级为j+1的所有个体的适应度最大值之和。

在基于个体适应度的赌轮选择中,当某个体的适应度过大时,往往使得此个体多次被选择,造成在交配池中过多。为此,本文采用文献[8]的二元赌轮选择方式,即在连续两次的随机采样中指针不复位,从当前群体中选择两个不同个体,进一步保持群体多样性。

2.3 多目标局部搜索

IM-MOGLS和J-MOGLS对进化产生的每一个个体进行局部搜索,但是当个体质量较差时,搜索效率并不高。此外,IM-MOGLS和J-MOGLS对个体进行局部搜索时,只在新个体和目标个体这两个个体间比较后就决定是否接受新个体,这种方式有时会丢弃一些支配其它个体的Pareto最优解。为避免上述问题,本文采取非劣解并行搜索策略,主要做法是:对非劣解集S中的每一个解x,产生一个邻域N(x),对该邻域内的解y,只要y不被S中的解支配,则接受y作为新解,放入集合S′中,S′为搜索过程中产生的不被S支配的邻域解的集合。用S′修正S,即将S′的解添加到S中,同时删除S中被支配的解,这样会得到改善的非劣解集S。再将S作为初始集合,重复上述搜索过程。这种从S出发,并行地勘探解空间的几个区域,能够加强不同区域的搜索,提高搜索效率。具体步骤如下:

(1) 初始化局部搜索的非劣解集合S,并将S加入到NDI中,令迭代次数t=1。

(2) 构建邻域解的集合S′,方法如下:

置S′为空集。对S中每一个解xk,产生xk的邻域N(xk),对y∈N(xk),判断y是否处于受集合NDI支配的区域。若y不被NDI中的任何解支配,且y∉NDI,则将y加入到S′中。

(3) 用S′修正NDI,即将S′的解添加到NDI中,剔除其中受支配的解。

(4) 如果t小于最大迭代数,则S=NDI,t=t+1,返回步骤(2)。

2.4 MOGLS的实现步骤

(1) 算法参数设定

群体规模Npop,交叉概率Pc,变异概率Pm,最大精英数Nelite,局部搜索的最大迭代数Niter。

(2) 初始化

随机产生规模为Npop的初始群体,计算每个个体的r个目标值。初始化外部群体ND1=ϕ,初始化精英解集E1=ϕ。

(3) 群体分级

据Pareto支配关系在目标空间对群体Pt进行非劣分级,确定每个个体的非劣等级。

(4) 修正外部群体NDt

将等级序数为1的个体加入到NDt中,再从NDt中删去被支配的个体

(5) 适应度赋值

对每一等级中个体进行拥挤距离评估,然后按2.2节的方法计算所有个体的适应度。

(6) 选择、交叉和变异

将Pt中的个体按适应度由大到小排序,选择前Npop个个体进入交配池,按二元赌轮选择操作从交配池中选择两个不同的个体,进行交叉和变异,共产生Npop个个体,形成中间群体MPt。

(7) 精英机制

从集合NDt中选出Nelite个个体,存放于集合Et中。

(8) 评价

对联合群体MPt∪Et中的中的Npop+Nelite个个体,计算r个目标值。

(9) 局部搜索

应用2.3节的方法对MPt∪Et的非劣解集S进行局部搜索,得到改善的非劣解集NDI。用NDI修正MPt∪Et,得到下一代群体Pt+1。

(10) 停止准则

若停止条件满足,则输出外部群体,否则Pt=Pt+1,返回步骤(3)。

3 算法测试

3.1 测试问题

Flow shop问题是一种典型的组合优化问题,置换flow shop调度可以描述为n个工件按同一加工顺序在m个机器上进行加工,要求确定使预定目标函数最小的工件加工顺序。此问题是NP难问题,其搜索空间的规模是n!。本文产生8个测试问题[2],包括机器数m为20,工件数n分别为20、40、60、和80,目标数N为2和3,每一问题表示成N×n。对于N=2,优化目标是使制造周期(make span)和最大拖期(maximum tardiness)达到最小,对于N=3,还要使目标总流程时间(total flow time)达到最小。

3.2 性能指标

本文采用Knowles 和Corne[9]提出的基于与参考集(Pareto最优集或近似Pareto最优集)的距离指标D1R来评价解的质量。D1R可同时考察解集的收敛性和多样性。设S*是参考解集,Sj是评价的解集,则D1R定义如下:

$D_{1 R} (S_{j}) = \frac{1}{| S^{*} |} \sum_{y \in S^{*}} \min {d_{x y} | x \in S_{j}}$

其中dxy是解x和参考解y在N维标准化目标空间的距离:

$d_{x y} = \sqrt{\sum_{i = 1}^{Ν} (f_{i}^{*} (y) - f_{i}^{*} (x))^{2}}$

其中f $_{i}^{*}$ (·)是使用参考集进行标准化的第i个目标值。

D1R不但能评价解集Sj的分布,而且能评价Sj到参考集S*的近似程度。D1R(Sj)越小,解集Sj的质量越好。

3.3 计算结果和比较

本文采用IM-MOGLS、J-MOGLS以及NSGA-Ⅱ作为参考算法,检验本文MOGLS算法的优化性能。所有算法均使用基于工件加工顺序的自然数编码,统一设定参数:群体规模Npop=100,交叉概率Pc=0.9,变异概率Pm=0.3,精英解的数目Nelite=20。对于J-MOGLS,群体的最大规模为Nmax =200,对于MOGLS,局部搜索的最大迭代数Niter=3。所有算法使用相同的进化和局部搜索操作:两点交叉、插入变异、对换邻域且搜索步长为2。计算终止条件均设定为评价100000个解。每种算法在相同的初始条件下独立运行15次,合并各次非劣解集并剔除其中的劣解后,获得各问题的最终非劣解集,作为参考集(非劣前沿)。表1是每种算法产生的非劣解数量以及评价指标D1R的计算结果。从中可以看到,在相同的算法终止条件下,本文的算法能够获得较多的非劣解。还可看到,除问题2×20外,本文算法的D1R指标均好于其他三种算法,反映出本文算法能产生更接近Pareto前沿的近似集。

注:表中斜线“/”前面数字表示非劣解数量,斜线后面的数字表示指标D1R的计算值

4 结束语

本文提出了一种新的多目标遗传局部搜索算法MOGLS。MOGLS基于Pareto支配关系对非劣解进行并行局部搜索,增强不同区域的搜索,采用基于分散度的精英选择策略和二元赌轮选择操作,保持群体的多样性。此外,在群体进化的选择过程中淘汰掉个别最差个体,以加快解的收敛速度。与其它多目标算法比较,结果表明,MOGLS算法能有效地产生数量较多分布较广的近似Pareto最优解。

参考文献

[1]Ishibuchi H,Murata T.A multi-objective genetic local search algorithmand its application to flowshop scheduling[J].IEEE Transactions onSystems Man and Cybernetics,1998,28(3):392 403.

[2]Ishibuchi H,Yoshida T,Murata T.Balance between genetic search andlocal search in memetic algorithms for multiobjective permutation flow-shop scheduling[J].IEEE Transactions on Evolutionary Computation,2003,7(2):204 223.

[3]Jaszkiewicz A.Genetic local search for multi-objective combinatorialoptimization[J].European Journal of Operational Research,2002,137(1):50 71.

[4]Knowles J,Corne D.A memetic algorithm for multiobjective optimiza-tion[C]//Proceedings of the Congress on Evolutionary Computation,Piscataway,NJ,USA:IEEE,2000,325 332.

[5]Jaszkiewicz A.On the Performance of multiple-objective genetic localsearch on the 0/1 knapsack problem:a comparative experiment[J].IEEETransactions on Evolutionary Computation,2002,6(4):402 412.

[6]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective ge-netic algorithm:NSGA-Ⅱ[J].IEEE Transactions on EvolutionaryComputation,2002,6(2):182 197.

[7]Arroyo J E C,Armentano V A.genetic local search for multi-objectiveflowshop scheduling problems[J].European Journal of Operational Re-search,2005,167:717 738.

[8]Elaoud S,Loukil T,TeghemJ.The Pareto fitness gengtic algorithm:Testfunction study[J].European Journal of Operational Research,2007,177(3):1703 1719.

基于遗传算法的飞机气动优化设计篇2

基于遗传算法的飞机气动优化设计

建立了一种以实数编码技术为基础的遗传算法模型,并把它与通过工程估算的气动分析方法相结合,进行飞机气动外形的单点和多点优化设计.优化设计中,设计变量取为机翼、机身和尾翼的外形及三者之间的相对位置,优化目标是使飞机在跨音速和超音速飞行状态下获得配平状态下最大的升阻比.设计结果表明该优化设计方法是十分有效的.,可以用来对具有正常布局形式的飞机进行气动外形的优化设计.

作者：王晓鹏作者单位：西北工业大学,飞机系,西安,710072;上海航天技术研究院,上海,33刊名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS年，卷(期)：200219(2)分类号：V211.3关键词：遗传算法气动外形优化设计

基于遗传算法的配水系统优化浅析篇3

关键词：遗传算法优化配水系统非线性规划

中图分类号：O224 文献标识码：A 文章编号：1674-098X（2015）02（c）-0232-01

遗传算法是基于随机性质的计算技术。这些算法的主要优点是其广泛的适用性、灵活性和找到最优或接近最优的解决方案且相对容易的计算需求能力。由荷兰首创的遗传算法，已被证明在各种探索工程、科学和商业中的优化问题非常有用。

1 基于遗传算法的管网优化

遗传算法通常要求问题的系统状态被表示为称为染色体串。例如：如果八种不同管道尺寸可供利用，那么3位的二进制串可用来表示选项。当评估管网系统成本时，这个过程要求将二进制编码转化为离散管道直径。然而，在该文中描述的遗传基础的方法它被认为是不必要的代表解决方案作为一个染色体，以避免二进制编码转化为离散的管道尺寸。在本研究开发的技术包括用于WDS的最低成本设计/增强以下步骤。

（1）读取网络数据、成本数据、所需的最小剩余水头，变异概率，解决方案的人口规模（范围50～350），代数的最大值（MG，范围10～30），惩罚因子（范圍0.9～1.0万元），公差（范围5～10 m），每单位长度（HL）平均水头损失，迭代直径调整最大值，管道最低要求速度。

（2）通过随机数据发生器生成初始解决方案的人口。该网络是分层分为上、中、下管径系列，网络这种分层是根据设计工程师的判断。例如：位于距离源头最远的节点处的管道被分成低维的尺寸。下部直径集可包括50、80、100、125和150 mm，这样有助于修剪搜索空间，促进更快的收敛到最优值。

（3）计数器1=1。

（4）人口的所有解决方案进行如下：

①计数器2=1。

②设计一个新的网络转到步骤③。

在现有的管网系统增强的情况下结合现有的直径与新的平行线设置，获得等效的管道直径。

③调用水力分析子程序ANALIS来计算流量，流速和剩余压头。

④如果每单位长度的水头损耗>HL，可以增加管道直径至下一个商业直径大小。如果流速

⑤重复步骤②和③。如果解决方案为第一，不可行但恢复早期解决方案可行然后进行到步骤5；第二，可行然后存储解决方案。

⑥递增计数器2。

⑦如果计数器2

（5）存储新组群的解决方案，对于此解决方案节点处剩余水头要高于所需的剩余水头公差。此步骤有助于减少所需的液压分析次数。

（6）在新的种群评估解决方案的成本和存储具有最小成本的可行的解决方案。

（7）递增计数器1。

（8）如果计数器1超过MG转到步骤（15）。

（9）如果解决方案不能满足最小剩余压头约束，将惩罚成本视为惩罚因子的产物以及关键节点处的水头。在该研究中的惩罚因子已经采取每米压头介于0.9～1.0万元。

（10）计算总成本包括管网成本和惩罚成本之和。

（11）计算每一种解决方案的适应性f=1/总成本

（12）在一个时间如前所述产生两个后代根据他们的适应值进行采取了两种新的人口方案的交叉。

（13）以突变率为基础使每代发生变异。

（14）后代构成了新的种群。请转到步骤（4）。

（15）写下每一代的存储解决方案集以及写下最佳解决方案的管网细节情况。

2 GA和NLP-IPF技术的对比

GA和基于自然语言处理技术是已被有效地应用到配水系统优化问题的强有力的工具。对融合技术的有效性依赖于固有特征的适应性以及问题公式化表达中的配水系统的性能。这两个技术都需要通过试错来调整参数，以获得最佳的解决方案。适应度函数是任何遗传算法的最重要的方面。其它重要的参数包括解决方案的人口数量，其它重要的参数包括在多于一组的直径，公差等级的策略的解空间的分层，还有突变率和惩罚因子。在NLP的IPF的情况下，控制收敛速度的参数包括惩罚参数的无约束目标函数和它的后续值，并在有限差分法的步长。在本研究中，GA和NLP-IPF的优缺点如下观察所示。

2.1 GA和NLP-IPF技术的优点

GA可处理分布在整个解决空间的人口解决方案。它可在搜索过程中同事并行攀登多峰，这样可使获得局部最小值的概率大大减少。就NLP技术而言，解决方案高度依赖出事解决方案而且它总是收敛基于初始解决方案的局部最小值。

GA算法针对每一个解决方案集中的一代采用离散管径，然而NLP技术中，直径生成需要进一步四舍五入到商业规模的实数。对大型规模的管网来说，这个过程甚至常常利用专业的判断四舍五入后转换解决方案。GA采用了更合理的适应度函数选择下一代的成员，而NLP依赖于无约束目标函数的导数。

2.2 NLP技术相比于GA技术的优势所在

相比于GA，NLP的收敛速度更快特别是对于中型和大型网络。在NLP技术中，可包括附加的技术，例如：对于链路中的两个部分与下一个下部和上部市售的直径尺寸，使得它们的组合水力特性是相同的，该非商业直径的示例分割。

3 结论

该文介绍了遗传算法在配水系统的设计的适用性。（1）该算法已经与具有IPF方法的NLP技术进行了比较，相比于迄今为止在文学上所呈现的技术，该方法被认为是最有效的。（2）从GA和NLP技术的几个中等规模的管网系统中获得的解决方案集显示，相比于从NLP技术中所获得的，GA一般可提供更好的解决方案。（3）在成本上的差异则是边缘化的，这显示了两种技术都是有效的。

参考文献

[1]沈军，刘勇健.水资源优化配置模型参数识别的遗传算法，武汉大学学报：工学版，2002，35（3）：13-16.

遗传优化搜索算法篇4

目前对于主题爬虫搜索策略的方法集中于基于内容评价的搜索策略, 基于链接结构评价的搜索策略, 基于未来回报价值评价的搜索策略及基于自动分类的搜索算法和启发式搜索算法。

基于内容评价的主题爬虫, 其中最具有代表性的是Best First Search, FishSearch, SharkSearch三种算法, 都是根据语义相似度的高低决定链接的访问顺序。这类方法起源于文本检索中对文本相似度的评价, 优点是计算简单。但是却忽略了web网页是一种半结构化文档, 包含了许多结构信息, 页面之间也不是单独存在的, 页面中的链接指示了他们之间的相互关系。

基于链接结构评价的搜索策略, 代表有Page Rank和Hits算法, 考虑了链接的结构和页面之间的引用关系, 但忽略了页面与主题的相关性, 容易出现“主题漂移”问题。

基于未来回报价值评价的搜索策略, 它是通过训练获得用于预测未来回报的经验信息, 使网络爬虫的搜索具有一定的“倾向性”。代表有基于巩固学习的方法和基于“语境图”的方法。由于需要对已有的信息进行训练或者借助搜索引擎构建语境图, 而这些初期的操作都是建立在已有的信息结构上的 (例如搜索引擎) , 而其本身就具有局限性, 影响算法的效果。基于自动分类的搜索算法。此算法是把网络爬虫看成Agent, 使其具有一定的自主性, 可以学习互联网上的知识并具备一定的经验信息, 然后可以计算网页是否属于所需要的主题类型, 从而得到正确的下载方向。

启发式搜索算法, 用在线获得的知识评价待访问链接的价值, 按照一定的原则选择价值最大的链接进行下一步的搜索, 找出到达目标节点的最佳路径, 删除不好的, 保留好的节点。但它是一种局部最优搜索算法, 搜索过程中会丢失掉许多相关的网页, 因此需根据实际的应用进行改进从而跳出局部最优点。鉴于此本文提出了下文的算法。

1 基于模拟退火遗传算法的主题搜索策略

1.1 遗传算法

遗传算法 (Genetic Algorithms, GA) 是一种模拟生物进化的智能优化算法, 根据生物优胜劣汰适者生存的原则, 借助交叉、变异、选择等操作, 使所要解决的问题在竞争中得以进化, 从而求得问题的最优解。遗传算法的特点是一种高效的全局搜索算法。

遗传算法的特性决定了其在网络爬虫搜索策略中应用的可能性。由通用搜索引擎产生一定数目的初始种群;选择由交叉概率所求个数的链接作为交叉的结果;通过变异操作, 引入一些目录型网页, 扩大搜索范围;然后通过选择操作, 从第一轮结果中选出相关度高的个体作为新一代的种子进入新一轮的遗传。具体实现如下:

1) 初始种群:在google或者百度进行主题和主题的一个同义词进行检索获得相关的URL, 然后各选取前n个作为初始化种子集S。对所选的2n个URL进行权威值 (Authority) 排名A, 再结合Alexa中文官方网查询这些URL对应网站的访问排名L, 得到他们的综合排名AL。AL=Am+Ln (其中m=0.8, n=0.2) , 选择排名靠前的80%的网页构成集合S11作为第一代遗传种群。

用HITS算法来计算Authority, 计算公式如下:

其中ap为网页p的Authority值, hp为p的Hub值。

2) 交叉:提取初始种群S11中的所有链接对应的网页中包含的链接URL, 用VSM算法计算锚文本及其上下文与主题的相关度, 提取相关度高的一部分作为交叉结果。

3) 变异:将初始化种群中的集合S中的2n个URL按照Hub和Alexa综合排名值从大到小排列 (仿照权威页和Alexa综合排名计算方法) , 组合成集合H, 然后通过变异操作根据设定的变异概率引入Hub网页, 适当地增加URL。设变异概率为Pm, 则从集合H中选取前H*Pm个URL作为变异结果, 记为集合S13。

至此, 交叉、变异操作都已完成所得到的S1=S11∪S12∪S13, 即为第一代遗传所得的种子群体。虽然此时爬虫已经抓取了许多与主题相关的网页但是由于互联网上的网页的错综复杂性, 也只是抓了一少部分而已。故, 还需要爬虫继续不断的循环地对互联网上的信息进行抓取工作。

4) 选择:在进入遗传算法第二代交叉变异之前, 还得对第一代遗传产生的种子群体S1进行选择操作, 以选出相关度高的, 适应性强的URL还产生新一代种子群体。

1.2 模拟退火算法 (SA)

模拟退火算法起源于统计物理学中对固体退火过程的模拟。它采用随机接受准则接收新解, 用一个称为冷却系数的参数控制算法进程, 这使得算法可能跳出局部最优解。SA一般采用Metropolis准则来确定由i'来替换i的概率:

在这里f (i) 为适应度值, 即主题相关度值。根据Metropolis准则, 当新解更忧时接受新解作为当前解, 否则以概率P接受其作为当前解。

该方式能够使得SA收敛于全局最优解, 具有良好的局部寻优能力, 可以很好的避免陷入局部最优解, 但SA收敛速度相当慢, 全局搜索能力不强, 影响网络爬虫的效率。

1.3 模拟退火遗传算法的搜索策略

GA全局搜索能力强, 而局部搜索能力较差;SA局部搜索能力强, 却对整个搜索空间的状况了解不多, 搜索效率不高。SA-GA将SA嵌入到自适应GA的循环体中, 互相取长补短, 形成一种新的优化算法。

将SA-GA算法应用于主题爬虫的搜索策略, 具体的实现步骤如下:

1) 设置初始参数, 主要包括遗传算法种群规模大小 (S1) 、最大进化代数 (Tmax) 、模拟退火算法的初始温度 (T0) 、温度下降系数0≤k≤1、最大内循环次数 (tmax) 。

2) 采用1.1 (1) 所述方法产生初始种群S1。

3) 对种群中各个个体适应度值即URL所对应的主题相关度进行计算, 并按照高低顺序排列。按照1.1 (1) 所述方式进行交叉, 变异操作产生新的个体, 即第一代遗传结果。

4) 根据选择操作, 产生新一代遗传种群S2。

5) 为了避免遗传算法的过早收敛, 用模拟退火机制对新一代种群中的个体即链接进行选择:设置内循环次数t初值为0, 从D中随机抽出一个链接i', 再从新一代种群S2中任选出一个链接i, 根据M etropolis准则来确定是否用i'来代替i。如果f (i') ≥f (i) , 则用i'来代替i;如果f (i') n (n为一随机数) , 则亦用i'来代替i。重复抽取直至t>tmax为止。

6) 如果当前进化代数T

2 结语

GA全局搜索能力强局部搜索能力差, SA局部搜索能力强但在后期收敛速度慢。将两种方法结合, 可以融合两者的优势克服单一算法的不足, 从而使主题爬虫搜索信息在内容和速度上都高于传统的方法及单个方法的应用。由于网络的复杂性及所用排名网站的局限性都会对结果产生影响, 所以GASA算法也存在一定的局限性, 需要作出进一步的努力和改进。

摘要：以何种策略访问网络, 提高搜索效率, 是近年来主题搜索引擎研究的主要问题之一。本文对主题爬虫常用搜索策略进行了简单分析, 提出了实用性较强的基于SAGA的主题爬虫搜索策略。

关键词：主题搜索策略,遗传算法,模拟退火算法,基于模拟退火遗传算法的搜索策略

参考文献

[1]Sutton R S, Barto A G.R einforcement Learning:an introduction[M].MA:MIT Press, 1998.

[2]Diligenti M, Coetzee F M, Lawrence S et al.Focused crawling using context graphs[C].In:Proc of the International Conference on Very Large Database (VLDB'00) , 2000.

[3]梁云静.基于遗传算法的主题爬虫搜索策略的研究[D].湖北工业大学, 2010.

[4]王海鹰, 魏颖.基于蚁群算法的多目标网页综合评价策略[J].计算机工程与应用, 2011.

[5]贺晟, 程家兴, 蔡欣宝.基于模拟退火算法的主题爬虫[J].计算机技术与发展, 2009.

遗传优化搜索算法篇5

基于遗传算法的航空发动机模糊优化控制

为适应航空发动机非线性的控制要求,采用基于多个修正因子的模糊控制方法对航空发动机的控制器进行设计,利用改进的遗传算法对模糊控制器的多个修正因子进行参数优化,并对航空发动机数学模型进行仿真试验.从仿真的结果看,改进遗传算法的收敛性比较强,收敛速度快;仿真优化后的修正因子取值在满足一定范围时,控制系统能达到比较好的`控制效果.基于遗传算法参数优化的模糊控制器表现出比较好的控制性能.

作者：张世英胡宇朱杰堂作者单位：第二炮兵工程学院,西安,710025刊名：弹箭与制导学报 PKU英文刊名：JOURNAL OF PROJECTILES, ROCKETS, MISSILES AND GUIDANCE年，卷(期)：201030(2)分类号：V233.7关键词：遗传算法模糊控制修正因子航空发动机参数优化隶属度函数 genetic algorithm fuzzy control correction factor aeroengine parameter optimization membership function

遗传优化搜索算法篇6

关键词：无功优化；遗传算法；改进；实数编码

中图分类号： TM714 文献标识码： A 文章编号： 1673-1069（2016）11-135-2

0 引言

传统优化算法在电力系统无功优化应用上，有明确的数学意义，逻辑思维严谨，要求目标函数具有连续可导的性质。然而，无功优化本质是一个多变量、多约束，连续性与离散性相结合的非线性规划问题，经典优化算法在处理非线性变量和离散变量上显得力不从心，经典优化算法在无功优化上未能收敛到令人满意的结果。遗传算法则是一种群体型操作，是以群体中的个体为操作对象，对目标函数没有连续可导的要求，适用于处理无功优化的非线性和离散变量问题。因此，遗传算法是一种较为理想的无功优化算法，已在实践上取得良好的效果[2][3]。

1 二进制遗传算法

遗传算法是一种概率搜索算法，它使用0和1作为编码，对染色体实行二进制编码。对数据的处理首先就要进行编码，将变量编成一串由0和1组成的基因，然后对这些基因进行交叉、变异和适应度评估。这些二进制串结构数据的长度会影响运算时间和计算精度。二进制编码方式有诸多好处，比如使编码和解码操作简单、使串结构的交叉和变异等运算也较易实现、符合生物进化思想。相反，二进制编码也存在不足，例如，连续函数在进行离散化运算时存在较大误差；变量的编码串较长时，计算精度会高，但搜索的空间扩大，使得收敛速度慢；如果变量的编码串较短，则无法达到计算精度要求；二进制编码无法反映出无功优化的本质，其求解过程物理意义不清晰[4][5]。

2 改进后的实数编码遗传算法

针对二进制编码方式的缺陷，本文将其改进为实数编码法。对变量施以实数编码，带来许多好处。比如，不必进行编码解码的运算；进行交叉变异遗传运算时物理意义清晰；运算速度提高，不会因为系统节点多而出现维数灾；计算精度能达到要求。电力系统无功优化模型中的控制变量，具有连续性质的发电机端电压施以直接实数编码；具有离散性质的可调变压器位置和无功补偿容易则施以间接实数编码，使离散变量映射为具有连续性质的整数变量[6]。

映射方程为：

Ti=Ti0+DTi×STi（2.1）

Qi=QQi×SQi（2.2）

式中：Ti为有载可调变压器的变化；

Ti0为有载可调变压器变比的最小值，设为正实数；

DTi为有载可调变压器变比的档位数，设为正整数；

STi 为有载可调变压器离散变比的档位步长，设为正整数；

Qi为无功补偿装置的无功功率投切量；

QQi为无功补偿装置投切组数。当无功补偿装置为容性时为正整数。当无功补偿装置为感性时为负整数；

SQi为无功补偿装置离散投切量的步长，设为正实数。

根据以上方法将控制变量的染色体进行映射。表示全部控制变量染色体可表示为：

X=UQT（2.3）

式中：U为发电机端电压；

Q为无功补偿装置无功功率的投切量；

T为有载可调变压器变比。

对离散变量映射后得到的染色体为

U，

U...

D，

D...

D，

D... （2.4）

由上式知，具有连续性的发电机端电压编码是一个实数，具有离散性的补偿装置的无功功率和变压器的变比的编码是调节档位范围的一个整数[7]。

3 IEEE-14节点系统无功优化仿真

分别用二进制编码遗传算法和实数编码遗传算法，对IEEE-14节点进行无功优化，对比它们的优化结果。IEEE-14节点系统包含5台发电机，分别在节点 1 、节点 2、节点3、节点6和节点8上，；3 台有载可调变压器分别接在支路 4-7、支路4-9 和支路 5-6上； 1个无功补偿点连接在节点9。IEEE-14系统的数据见文献[1]。

本文以IEEE-14节点系统的有功网损最小作为目标函数：

limp=G

-U

-2U

Ucos（δ

-δ

（3.1）

式中：p为IEEE-14节点系统有功网损，n为网络总支路数；

G为支路i，j的电导；

U，U分别为节点i，j的电压；

δ，δ分别为节点i，j的相角。

根据式（2.1）—（2.4）对控制变量X 进行实数编码得：

U，

B，

T，

T（3.2）

设IEEE-14节点系统中可调变压器变比范围是（0.90—1.10），其调节的步长为2.5%，共有8个分接头；节点电压范围是（0.95—1.10）；无功补偿电纳调节范围是（0—0.50）。IEEE-14系统初始有功网损为0.142。系统中以基准功率为100MVA。种群规模是100，最大进化代数200，交叉率为0.5，变异率为0.05。

两种编码方式的仿真结果如表1所示。

表1 两种编码方式仿真结果

[编码方式＼&最小网损＼&运算时间＼&进化代数＼&二进制编码

实数编码＼&0.1360

0.1325＼&33.4

27.3＼&130

90＼&]

4 结论

用两种编码方式的遗传算法分别对IEEE-14节点进行优化后，从仿真结果可知：用实数编码的遗传算法对系统进行优化，无论在最小网损，还是运算速度都优于二进制编码的遗传算法。因此，本文提出的实数编码遗传算法对电力系统进行无功优化是切实可行的。

参考文献

[1] 张粒子，舒隽，林宪枢，等.基于遗传算法的无功规则优化[J].中国电机工程学报，2000，20（6）：5-8.

[2] 范宏，韦化.改进遗传算法在无功优化中的应用[J].电力系统及其自动化学报，2005，17（1）：6-9

[3] 雷英杰，张善文.遗传算法工具箱及应用（第二版）[M].西安：西安电子科技大学出版社，2013.

[4] 毕鹏翔，苗竹梅，刘健.浮点数编码的无功优化遗传算法[J].电力自动化设备，2003，23（9）：42-45.

[5] Walters，GA.andD.K.Smith，EvolutionarydesignalgorithmforoPtimallayoutoftreenetworks，EngineeringOPtimiZation，vol.24，261-281，1995.

[6] 向为，黄纯，谢雁鹰，蒋晏如.具有改进变异的遗传算法在无功优化中的应用[J].继电器，2005，32（9）：31-34.

遗传优化搜索算法篇7

物流配送是现代物流管理中的一个重要环节,特别是对于有大量服务对象的实体,例如拥有上千个客户的公司。物流配送业务中的优化决策问题的核心是如何对车辆进行调度。合理分配各车负责的售货点,选择配送路径,从而达到加快配送速度,提高配送质量,降低成本,提高经济效益的目的。

在此需要解决如下问题:

有m个送货车S1,S2,…,Sm,各自具有自已的装载量和行驶距离限制,可载着某种物资从各自当前的位置出发对n个售货点:T1,T2,…,Tn进行送货并返回原出发地,各售货点具有各自的需求量,要求每个售货点只能由一个送货车来送货,并且单位货物的卸货时间相同,即卸货时间与货物量成正比。现要找到一种最佳的送货策略,对这些送货车的送货地点和送货路线进行统筹分配和规划,使得所有货车都送完货返回出发地所用时间最短。

2 遗传算法与禁忌搜索

近年来发展起来的遗传算法(GA)引起了各学科人员的普遍兴趣,用来解决NP难度问题效果尤为显著。

“物竞天择,适者生存”,是进化论的基本思想。遗传算法就是模拟自然界想做的事,它以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法,遗传算法以其简单通用、健壮性强、适于并行处理以及高效、实用等显著特点,在各个领域得到广泛应用,取得良好效果,并逐渐成为重要的智能算法之一。

但是,由于遗传算法只需调整种群的几个参数而不是单个的解,并且遗传算法存在早熟收敛和盲目搜索问题,因此在寻找最优调度的过程中,可通过把禁忌搜索算法独有的记忆思想引入到遗传算法的搜索过程中,构造新的重组算子,并把禁忌搜索算法作为遗传算法的变异算子来实现。

禁忌搜索的思想最早由Glover提出,它是对局部领域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。禁忌搜索算法的特点是采用了禁忌技术,所谓禁忌就是禁止重复前面的工作。为了回避局部领域搜索陷入局部最优的不足,禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点。在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点。禁忌搜索机制是通过设置近期操作的存储结构(禁忌表),以当前解邻域中未在禁忌表中出现或满足藐视准则的最佳状态来替换当前状态,而并不在乎其性能是否优于当前解,按此原则产生一定的突跳性以避免局部极小,同时也避免迂回搜索的出现。

在此,提出GATS算法来求解具有时间和距离限制的多车物流配送问题,利用GA提供并行搜索主框架,结合遗传种群进化和TS较强的具有避免迂回搜索能力的邻域搜索,实现快速全局优化。既保持了GA具有多个解的优点,又提高了GA的爬山能力。

3 算法设计

3.1 基因编码

每条基因用所有送货车和售货点的一个排列表示,代表各辆售货点的分配方案和游历顺序。各送货车号用A,B,…字母表示,各售货点序号用1,2,…整数表示。

根据各送货车和售货点的初始化顺序,分别给送货车排号A,B,…用三维数组存储其编号、装载量、最大行驶距离;给各售货点排号:1,2,…用二维数组存储各售货点序号和需求量。具体结构如表1所示。

3.2 初始化种群

若送货车数目为M,售货点数目为N,将所有售货点标识组成一组任意排列,生成N个售货点标识的一个序列,并将第一辆送货车标识A插入首位,在2到(N-1)自然数中随机产生(M-1)个数,按从小到大的顺序排序,按一定策略将送货车标识顺次插入序列的相应位置,组成一个排列,并保证排列中不能有两个连续送货车标识位,基因的第一个染色体为第一辆车的标识,即每条基因第一个染色体均为第一辆送货车标识A,同时确保各辆送货车不超过其最大装载量和最大距离限制。

3.3 计算基因适应值

计算各送货车的送货游历时间加上送货中途卸货时间(TTA,TTB,TTC,TTD),取最后完成送货任务的送货车的送货加卸货时间,即求取最大值:Max(TTA,TTB,TTC,TTD)。用一个较大的固定值WMAX来减去该最大值,作为该基因的适应值f。

表示为:f(基因适应值)=WMAX-Max(TTA,TTB, TTC, TTD)

3.4 基因有效性检验

基因有效性检验是用于判定某基因是否满足问题的限制条件,各售货点需求是否均得到满足,各送货车是否超出行驶距离限制或时间限制,或送的总货物是否超出装载量。

3.5 基因的杂交和变异

循环进行杂交和变异操作求取最终解决方案步骤简述为将每代种群中淘汰操作后剩下的基因直接复制,进入下一代,设基规模为SUBPOP生成1到SUBPOP之间的随机数Y,Z则将种群中第Y,Z两个染色体作为交叉的父代,然后对该对双亲进行交叉操作,产生两个子代。进行有效性判断,有效则用禁忌搜索来进行变异,产生新的局部较优的有效的基因,如此循环增加子代种群个数组成新一代既定规模的种群。如此循环,直至达到最大的遗传代数,终止循环,找到适应值最大的基因,进行最合理化整理最终得到的染色体序列即为问题的最优解。

3.5.1 杂交

种群由上一代遗传到下一代需要淘汰掉一些基因,同时产生一些新的基因补充进来以维持种群规模。在此介绍的方法是:将父代染色体按适应值大小排序,根据种群规模和淘汰率计算出需要淘汰的基因个数,将适应值小的基因淘汰掉,然后通过随机选择父代进行杂交产生有效的子代,然后进入下一步的变异操作。

3.5.2 变异

在通过杂交产生基因后,再通过禁搜索进行变异,搜索到邻域内的局部最优解加入子代种群中。在此介绍的禁搜索中,将禁忌长度设为t,使t*t=N。藐视准则设定为基于搜索方向的准则。若禁忌对象上次被禁时使得适配值有所改善,并且目前该禁忌对象对应的候选解的适应值优于当前解,则对该禁忌对象解禁。禁忌频率设定为记录由基因中某个染色体出发后回到该染色体的迭代次数。终止条件设定为最大迭代步数。

4 结语

本文介绍的多车物流配送问题的求解方法简要概述为:首先产生初始种群,按照适应值排序,根据淘汰率淘汰掉适应值小的基因,剩下的利用禁忌搜索算法经过变异操作进行优化后加入子代种群中,在当前规模的子代种群中随机选取一对父代进行遗传,再用禁忌搜索算法进行变异,然后将新个体加入子代。重复操作产生子代个体,直到满足种群规模。然后再对子代按适应值进行排序,根据淘汰率淘汰掉适应值小的基因,再进行杂交和变异产生子代,如此循环操作,直到遗传代数达到其代数限制后,终止循环,找出适应值最大的基因,进行最合理化整理即为目前最优送货方案。

参考文献

[1]王凌.智能优化算法及其应用.清华大学出版社.

[2]蔡临宁.物流系统规划----建模及实例分析.机械工业出版社.

基于遗传算法的QoS路由优化算法篇8

在分析目前已有算法局限性的基础上, 本文提出了一种新的基于遗传算法的多约束优化QoS路由算法。通过仿真证明, 该算法性能良好, 实现简单, 具有研究的前景, 在满足时延和费用的约束条件下, 使得消耗的网络资源尽可能少。

1QoS路由问题算法

1.1遗传算法

遗传算法是基于个体和自然的相互作用模拟遗传选择和自然淘汰的生物进化的计算模型, 是一种新的全局优化搜索算法。该算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图1所示。遗传算法是一种群体型操作, 该操作以群体中所有个体为对象, 以选择、交叉和变异3个主要操作算子构成遗传操作。这些个体有解决问题的基因。该算法利用遗传算子产生一系列的代。在种群只有最合适的个体可以生存下来并且产生后代, 将它们的生物特性传送给后代。

1.2GLBR和ARGA算法

在GLBR算法中, 将基因按照顺序节点的形式放在一个大小不一的染色体中。当遗传操作进行随机性选择时, 种群的下一代可能会出现不适合的个体。这样在两个相邻节点的通信路径可能不存在, 需要进行一些复杂的遗传操作以便找到一条新的通信路径。并且由于种群个体大小不一, 交叉运算较为复杂。

为简化GLBR算法的遗传操作, 在ARGA算法中将网络表示成树结构, 基因作为树的结点。用这种编码方法, 每个染色体的长度相同并且在树结点完成遗传操作, 于是搜索的路径总能存在。因此GLBR算法中没有必要去检查搜索路径的有效性。

图2所示的8个节点的网络描述了上述过程。其中节点A和H分别是源节点和目的节点。所有的路径采用树结构表示, 如图3。阴影部分是从节点C到H的相同路径。为减少染色体基因数目, 图3的网络树结构简化为图4所示的树结构。在简化后的树结构中, 每一个树结点作为一种基因, 路径代表了染色体, 并缩减了表示节点C到H的路径的两棵树。

1.3ARGAQ算法

在ARGAQ算法中采用了延时和传输成功率两个QoS参数。延时表示一个节点到另一个节点传输数据包所用的时间。传输成功率表示正确传输数据包没有出现丢包的概率。

图5所示的网络中节点A是源节点, 节点B是目的节点。节点A向B发送10个数据包, 图5 (a) 和 (b) 的传输成功率是分别由公式1和公式2计算得到。

10×0.9×0.9×0.9×0.9=6.561 (1)

10×1.0×1.0×0.6×1.0=6.000 (2)

对比可得图5 (a) 的数据传输成功率较高, 此时为最优路径。

图6所示的网络模型中, 有延时和传输成功率两个参数, 由公式3可以得到比值T。其中n表示路径中链接节点的数量。

undefined (3)

当节点A与节点D通信时, 可以走两条路径:“A-B-D”或“A-C-D”。按照公式3可以得到以下两个式子。

undefined (4)

undefined (5)

尽管路径“A-B-D”的延时比“A-C-D”要短, 但路径“A-C-D”的丢包率要要低一些, 因此“A-C-D”为最优路径。这样需要参考两个QoS路由参数来寻找最优路径。

2基于遗传算法的优化算法

2.1多目标优化

该改进算法为多目标优化采用了多分组模型。当存在多个目标时, 一个解在某个目标上是最好的, 在另一个目标上可能是最差的。所以将全局领域划分成几个不同空间领域并且每个个体在各自空间中进化, 若找到某个体满足最终条件标准, 该个体就是最佳路径。若没有找到最优路径, 就在各空间领域之间交换其中的最优个体, 直到完成遗传次代。如图7所示, 图中有4个不同目标函数独立并存于各自的空间领域中。

如图8所示, 竖坐标表示了时延, 横坐标表示通信费用。图中的点表示个体 (或路径) 。左上方的个体费用最低, 右下方的个体时延最小。阴影部分的个体时延和费用达到最优值, 被称为Pareto解。 Pareto解附近的个体是通过不同领域互相交换解得到的。

2.2QoS路由搜索引擎

路由搜索引擎 (RSE) 包括两个搜索引擎, 即缓存搜索引擎 (CSE) 和树搜索引擎 (TSE) 。它们都是独立操作但共同合作来更新路由信息。当路由搜索引擎收到一个从客户发来的QoS路由请求, 它将请求并行转发给缓存搜索引擎和树搜索引擎。缓存搜索引擎和树搜索引擎分别并发去搜索满足QoS要求的路径。缓存搜索引擎在缓存数据库中搜索路径 (在缓存数据库中, 目的节点和路由信息保存为数据项) 。当缓存搜索引擎找到一条路径满足QoS的要求, 这条路由信息被传送给路由搜索引擎, 如果该路径不满足要求就作为新个体放入基因库中。当缓存搜索引擎搜索不到满足要求的路径时, 就由树搜索引擎搜索路径再转发给路由搜索引擎。

2.3搜索引擎和数据库更新

由于网络状态随时发生动态变化, 数据库信息也需要及时更新。当树搜索引擎寻找到一条QoS路径, 它就将该路径信息存放到缓存数据库中。对使用频繁的路由信息赋予更高的优先级, 这样该路径就可以很快被缓存搜索引擎搜寻到。当缓存搜索引擎找到的路径不满足客户的QoS要求, 该路径信息就当成一个新个体放入到树搜索引擎的基因库中并在遗传算法的选择操作中使用, 如图9所示。

2.4树搜索引擎操作

当树搜索引擎收到路由搜索引擎发来的寻找QoS路径的消息后, 它将树根结点作为源节点。在有相同路线时对树网络模型进行简化。在简化后的树网络中, 基因用树的结点表示。染色体的基因里有相邻节点的信息。使用这种树模型, 能够避免路由循环, 这样算法不会在路由循环时浪费搜索时间。另外染色体比较短, 遗传操作起来更简单。

基因编码后, 就选择初始种群。使用等第选择模型选择两个个体来进行遗传操作。等第选择模型将个体按适应度进行排名。个体适应度取决于时延和费用, 时延短、费用低的个体适应度高。由于需要得到快速回应, 交叉操作采用简单的单点交叉。在变异操作中, 基因在0到变异概率p这个范围内随机选择, 其中undefined为染色体的长度。在交叉变异后, 使用精英模型将种群中适应度高的个体完整的遗传给下一代。这样可以保留最优值并且路由算法可以快速收敛到时延和费用的期望值。

3仿真实验

使用如图10的20个网络节点模型进行仿真。路由搜索引擎发出QoS要求和目的节点信息后, 缓存搜索引擎和树搜索引擎并行去寻找路径。

在仿真实验中, 假定客户要求QoS的时延低于60ms, 费用低于100, 图11为利用遗传算法搜索网络时延、费用随遗传代数变化的曲线图。从图中可以看出, 该算法能够很快从局部解中摆脱, 使用该改进遗传算法能快速有效地完成全局优化解。

表1显示了使用树搜索引擎的仿真结果。若种群中个体比较少时, 寻找路径所需的代数量会变大。当个体数目很多时, 代数量就会比较小。当个体数目是12或者16

时, 区别不大。由于各领域间的个体会交换, 在交换区间很短时可以很快的找到解。这说明了通过交换个体, 该算法可以很快接近Pareto解。

4结束语

在本文中, 基于遗传算法提出了一种多目标最优化算法, 主要涉及时延和费用等参数。仿真结果表明, 该算法收敛速度快, 可靠性高, 能够满足多媒体对实时性的要求。

目前进行了两个QoS指标的仿真。在今后的研究中, 将要使用更多的QoS路由参数。总之, QoS路由算法的深入研究将会对Internet、无线网络及高性能网络路由系统的科技进步起到积极的促进作用, 在多媒体等领域具有广泛的应用前景。

摘要：由于一些像远程视频会议之类的新服务要求更好的服务质量, 多媒体通信路由算法需要使用多个QoS的参数。然而解决QoS路由问题、搜索两个无关参数的可行路径是一个NP完全问题。提出了一种基于遗传算法的QoS路由算法。仿真实验结果表明, 该算法具有很好的性能并且为多约束QoS路由问题的求解提供了一种有效的途径。

关键词：QoS (服务质量) ,遗传算法,多约束,路由算法

参考文献

[1]孙宝林, 李腊元.一种基于遗传算法的多约束QoS多播路由优化算法[J].计算机工程与应用, 2003 (30) .

[2]C BARANSEL, W DOBOSIEWICZ, P GBURZYNSKI.Routing inmultihop packet pwitching networks:Gb/s challenge[J].IEEENetwork, 1995 (3) .

[3]M MUNETOMO, Y TAKAI, Y SATO.An adaptive routing algo-rithm with load balancing by a genetic algorithm[J].IPSJ, 1998 (2) .

[4]L BAROLLI, A KOYAMA, T YAMADA, et al.An intelligent poli-cing routing mechanism based on fuzzy logic and genetic algorithmsand its performance evaluation[J].IPSJ, 2000 (11) .

[5]BIN WANG, JENNIFER C HOU.Multicast routing and its QoSextension:Problems, algorithms, and protocols[J].IEEE Network, 2000 (10) .

[6]L.BAROLLI, A.KOYAMA, T.SUGANUMA, N.SHIRATORI.Agenetic algorithm based GoS routing method for multimedia com-munications over high-speed networks[J].IPSJ, 2003 (2) .

基于单亲遗传算法的管网优化篇9

在管网的自动化管理中,空间分析是体现系统智能化程度的一个很重要的功能,而对管网进行连通性分析是管网空间分析的核心,即在某些代价最小的情况下,使管网中所有管点相连通的方案。任何一种管网连接形式都可以抽象为由一些节点和边组成的图[1]。因此,以管网连接图为基础,寻找出一个或多个连通所有管点,且使某些代价最小的管网连通分析,可以抽象为求图的最小生成树问题。

近年来,主要采用图论中的传统算法,如Kruskal算法[2]、Prim算法[3]、Dijkstra算法、Sollin算法求图的最小生成树,这些算法可以根据给定的边的代价,获取代价和最小的生成树,但是这些算法只能得到唯一的最小生成树,并且只能针对一种代价[4]。但是通常情况下图的最小生成树形式不唯一,例如,在管网规划中,往往要针对管网长度最短和投资最小两个条件综合选取最小树的方案,有时针对一种权值的次优解,也可能是管网中某些问题的一个较好的设计方案,如果任选其中一个,可能会丢弃或忽略更优方案。因此,在实际应用中希望能够同时获取若干个权值最小或次小的生成树作为待选方案,然后综合考虑所有因素后,选出最佳的连通方案。已知过n个顶点的树的数目为nn-2,因此求管网的最小生成树问题是典型的组合优化问题,考虑到遗传算法对组合优化问题的求解非常有效,能够在较短时间内,以较高概率获得一批最优或接近最优的方案,因此本文采用遗传算法,并且结合管网中求最小树的特点,对传统遗传算法进行改进,采用单亲遗传算法进行求解。

1 单亲遗传算法的求解

使用遗传算法求解问题,首先要找出一种适合的编码方式,结合管网的实际情况,采用边编码方式:设某一无向图G中共有n个顶点、m条边,分别对图中的节点和边进行编号,以图中的所有边作为编码变量,用一个长度为m且按边的编号顺序排列的二进制字符串表示图的所有子图。各个编码变量的取值为0或1,当字符串中某位上的字符值为1时,表示它所对应的一条边是构成子图的边;当字符值为0时,表示它所对应的边不是构成子图的边[5]。如图1(a)所示的无向图,连线上的数字表示各边的编号。图1(b)为无向图(a)的一颗生成树,用边编码表示该生成树,可表示为{0001101001}。

采用这种边编码方式表示最小生成树比较简单直观。然而,由生成树的性质可知,对于一个有n个顶点的图来说,一颗生成树必须是一个具有n-1条边的连通无回路的子图,但采用上述的边编码方式不能直接表达生成树的性质。若二进制串中含有非n-1条边,则对应的子图一定不是一棵树。即使正好含有n-1条边的子图,也有可能因为含有圈而不是一棵树。对于一般的最小生成树问题,在基本遗传算法的进化过程中,子代个体的产生主要通过随机地从亲代群体中选择两个个体,随机交换两个亲代个体的部分基因,生成两个新的子代个体。这种交叉算子非常容易破坏子体构成生成树的基本特性,产生有效个体的概率非常低。针对这种问题,文中放弃了传统的双亲交叉遗传算子,采用单亲遗传算法SPGA(Single Parent Genetic Algorithms)的进化策略来弥补这种编码的问题[6]。

(1) 单亲换位算子

单亲换位算子对所选择的个体基因链上的任意一对基因进行交换,且所执行的基因交换次数以及被交换的基因位都是随机产生的。例如:个体A为0001101001,对下划线部分进行交换,可得到新的个体A′为0101100001。

(2) 单亲逆转算子

单亲逆转算子是将所选择的个体基因链上的任意一段基因进行逆转,一次性地完成从一个母体突变为一个新个体。例如:个体A为0001101001,对下划线部分进行变异,可得到新的个体A′为0010011001。

同时,对于产生的每个新个体,首先判断该个体是否满足成为树的必要条件,即是否有n-1个字符为1,对于满足条件的个体采用深度优先搜索算法[7],对个体进行连通性判断,确定该个体可以构成一个生成树的情况下,计算个体的适应度值。对于不满足树的条件的个体不做任何操作,直接删除,重新选择个体进行交叉或变异,产生新的个体。

2 适应度函数

以树状管网的规划为例,主要针对两项指标:管网长度和管网总投资,因此在求最小树时,可以先以管网总长度最短为优化目标,使用遗传算法求出符合条件的一组生成树方案,然后再对每个方案进行管网投资估算,从管网投资大小的角度进一步比较各种方案的优劣[8]。另一种方法是直接以管网投资最小为优化目标,通过遗传优化搜索选出投资最小的一组方案,然后再根据管网长度作进一步选择。

(1) 以管网总长度最短为优化目标的适应度函数

其中,F——个体的适应度;

F0——一个较大的正常数,保证个体的适应度值F总为非负;

NP——管网初步连接图中边的数目;

ND——管网初步连接图中顶点的数目;

Li——第i条边的长度,单位为米;

Zi——个体编码中第i位上的字符值(对应于图中的第i条边),为0或1。

如果生成树的总长度短,则采用上面的适应度函数,该个体具有较大的适应度,即具有较强的生存能力。对于一个不能构成生成树的个体,其适应度值为0。因此,按照上述所定义的适应度函数计算个体的生存能力,可以保证通过遗传算法的进化搜索过程,能寻找到一批最小或次最小的生成树,达到求解最小树问题的目的。

(2) 以管网总投资最小为优化目标的适应度函数

其中,F——个体的适应度;

F0——一个较大的正常数,保证个体的适应度值F总为非负;

a,b——管道造价经验公式系数;

Dmax——以速度Vmin通过管网总流量Q时的最大管径,单位为米,

qi——第i条管段的流量;

Di——以Vmin通过流量qi时的管径,单位为米,

从上面两个适应度函数的计算方法可以看出,管网长度的计算方法比较简单,而管网投资的计算量比较大,为了加快适应度的计算速度,减少计算量,文中采用管网总长度最短的函数作为遗传算法的适应度函数,在每代进化时将管网造价函数值作为选择的参考因素,对于产生的最后结果种群,计算种群中每个个体的造价函数值,从中选出最优个体。这样既保证在进化过程中综合考虑管网长度和总造价,又减少了运算量,从而加快算法的执行速度。

3 选择策略

已经证明当某种选择方式能保证上一代群体中的所有适应度大于零的个体都有机会被选择到下一代时,单亲遗传算法在使用了精英选择后是全局收敛的[9]。因此,该文在每次选择时,采用遗传算法传统的选择方法和精英选择相结合的方法,同时对上述策略进行进一步改进,既保证适应度高的个体可以进化到下一代,同时也保证群体的多样性,具体的选择策略为:首先,采用基于按比例适应度分配的轮盘赌选择法,对选择的个体进行交叉、变异,形成一定数量(小于群体规模)的新个体,组成新一代种群,计算个体的适应度,并获取适应度的最大值。然后采用精英选择的方法,将父代种群中适应度大于当前最大适应度的个体,直接放入新一代种群中。若此时新种群个体数小于指定的群体规模,则采用基于排序的适应度分配法,将父代个体按管网造价函数值由大到小排序,依次判断每个个体是否可以进入新一代种群,判断标准为:若个体已经在新种群中出现,则不再选择,否则将个体直接保存到新种群中,重复上述过程,直到个体数达到群体规模,这样既可以保证适应度高的个体进入到下一代,同时又保证了个体的多样性,即不允许群体中有相同个体出现。若种群中个体数大于群体规模,则将最后几个管网造价函数值大且长度相对长的个体淘汰。

4 交叉概率Pc和变异概率Pm的选择

遗传算法的参数中交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键,直接影响算法的收敛性,因此该文采用Srinvivas等提出的自适应遗传算法AGA(Adaptive GA)[10],使Pc和Pm能够随适应度自动改变:当种群中个体适应度趋于一致或者趋于局部最优时,使Pc和Pm增加,而当群体适应度比较分散时,使Pc和Pm减少。同时,对于适应度高于群体平均适应度的个体,采用较低的Pc和Pm;而对低于平均适应值的个体,采用较高的Pc和Pm。但是这样做会使得进化初期群体中较优的个体几乎处于一种不发生变化的状态,而此时的优良个体不一定是全局最优解,这就会增加进化走向局部最优解的可能性。为此,采用公式(3)、(4)改进Pc、Pm的计算公式[9],该公式相应地提高了群体中表现优良个体的交叉率和变异率,使得它们不会处于一种近似停滞不前的状态,同时由于采用了前面介绍的选择方法,也保证了真正的优良个体不会被破坏。

其中,根据大量的实验结果,取Pc1=0.9,Pc2=0.6,Pm1=0.1,Pm2=0.001。fmax为群体中最大的适应度;favg为每代群体的平均适应度;f ′为要交叉个体的适应度;f为要变异个体的适应度。

5 实例研究

分别使用单亲遗传算法、Kruskal算法和Dijkstra算法,求如图2所示管网连接图的最小生成树。单亲遗传算法中根据以往经验和针对不同参数收敛性的大量实验,选择群体规模为20,最大遗传代数设为200,图中共有51条连接管线,26个需水节点,其中25处为高位蓄水池,节点26处为泵站。已知管网中各点的需水量和各管段的长度以及流速等参数,遗传算法的部分结果和另两种方法的结果如表1所示。

表中给出了使用该文的改进单亲遗传算法产生的20个个体中的三个,通过大量实验,可以看出200次迭代后,可以产生全部的进化最优解(管网长度最短),同时还可以得到多个管网长度次短的方案。由表1可以看出Kruskal算法可以产生管网长度最短的连通方案,但是并不是造价最低的连通方案,单亲遗传算法2的管网总造价最小、管网长度次短,是问题的最优解。由此可以看出,使用传统算法得到的总长度最短的连通方案,并不是管网造价最少的方案,而使用文中给出的单亲遗传算法,可以同时考虑多种因素,得到真正符合管网需求的连通分析最优解。同时,通过改变相关的计算参数,还可以综合考虑更多的因素。

6 结论

遗传算法思想简单、易于实现、鲁棒性强并具有隐含并行性,是启发式全局概率搜索算法。本文结合管网中求最小生成树的特点,对传统遗传算法进行改进,采用单亲遗传算法的进化策略,结合精英选择以及自适应的交叉、变异概率求解图的最小生成树,由理论分析和实验数据可以看出,采用遗传算法求最小生成树可以得到一组满足条件的解,从而可以综合考虑管网长度和管网总造价。因此,与传统算法相比,应用遗传算法求解最小生成树问题及其扩展问题能得到比较满意的结果,为组合优化问题的研究提供了新途径和新经验。

参考文献

[1]乔淑娟,骆力明,王华.基于MapX技术的城市地下管网地理信息系统的研究.微计算机信息,2006,3.

[2]Kruskal J.On the shortest spanning subtree of graph and the traveling sales-man problem,Prco ACM,1956,7(1):48-50.

[3]Prim R.Shortest connection networks and some generalizations.Journal of Bell Systems Technology,1957,36:1389-1401.

[4]Graham R,Hell P.On the history of the minimum spanning tree prob-lem.Annals of the History of Computing,1985,7:43-57.

[5]Piggott P,Suraweera F.Encoding graphs for genetic algorithms:an in-vestigation using the minimum spanning tree problem.In Yao[463]:305-314.

[6]云庆夏,等.遗传算法与遗传规划——一种搜索寻优技术.北京:冶金工业出版社,1997.

[7]卢开澄,卢华明,等.图论及其应用.第二版.北京:清华大学出版社,1995.

[8]周荣敏,林性粹.用单亲遗传算法进行树状管网优化布置.水利学报,2001(6):14-18.

[9]李茂军,童调生.单亲遗传算法及其全局收敛性分析[J].自动化学报,1999,25(1):76-80.

基于遗传算法的多峰函数优化篇10

目前,对于求解整体优化问题已经进行了大量理论研究,并提出了许多基于导数的解析方法[1]和其他非解析的数值优化技术[2]。但是,在实际领域中存在着各种高度复杂的优化问题,其目标函数可能表现为非连续或非处处可微、非凸、多峰和带噪声等各种形式。这类复杂优化问题不适合于采用解析方法,同时用传统上的搜索技术求解也会遇到许多困难。而遗传算法由于具有很强的鲁棒性,即能适应不同领域的优化问题求解,并在大多数情况下都能得到满意的解。

1 遗传算法

遗传算法(Genetic Algorithms,GA)是一种来自生物进化理论中“自然选择,适者生存”原则的搜索(寻优)算法,它基于生物学的自然选择原理和自然遗传机制模拟生命的进化。遗传算法用于优化问题时,其最主要特征就是:它不在单点上寻优,而是从整个种群中选择生命力强的个体产生新的种群;它使用随机转换原理而不是确定性规则来工作[3]。遗传算法以编码空间代替问题的参数空间,以适应度函数为评价依据,以编码群体为进化基础,以对群体中个体位串的遗传操作实现选择和遗传机制,建立起一个迭代过程。在这一过程中,通过随机重组编码位串中重要的基因,使新一代的位串集合优于老一代的位串集合,群体的个体不断进化,逐渐接近最优解,最终达到求解问题的目的。

2 整体优化问题的严格定义[4]

定义1:给定非空集合S作为搜索空间,f:S→R为目标函数,整体优化问题作为任务:

$\max_{x \in S} f (x) (1)$

给出,亦即在搜索空间S中找到至少一个使目标函数最大化的点。

函数值f*=f(x*)<+∞称为一个整体极大值,当且仅当:

$\forall x \in S \Rightarrow f (x) \leq f (x^{*}) (2)$

成立时,x*∈S被称为一个整体极大值点(整体极大解)。将所有整体极大值点的集合记为argf*。显然,argf*非空时优化问题(1)适定的最基本要求。有时也把S中的点称为可能解或候选解。

3 函数优化问题的遗传算法设计

遗传算法应用于优化问题求解,也是一个启发式随机搜索过程。在该搜索过程中,GA不仅需要探索解空间上的全局性最优解,而且应当充分利用已获得的解空间信息逼近当前局部最优解。GA通过群体和遗传算子(选择、交叉、变异)可以实现扬弃性的探索,克服局部极值陷阱和模式欺骗,实现整个解空间范围内的搜索,提高全局寻优能力。通过继承性的开发,维持群体的可进化型,同时克服早熟问题,实现邻域搜索,提高逼近搜索能力。以多峰函数f(x)=10sin(5x)+7cos(4x)为例介绍此算法的实现过程。

3.1 编码

由于遗传算法不能直接处理问题空间的参数,因此,必须通过编码将要求的问题表示成遗传空间的染色体或者个体,它们由基因按一定结构组成。由于遗传算法的鲁棒性,对编码的要求不苛刻。在这里采用二进制编码。长度大小取决于变量的二进制编码长度,本文取L=10。

3.2 适应度函数

遗传算法遵循自然界优胜劣汰的原则,在进化搜索中基本上不用外部信息,而是用适应度表示个体的优劣,作为遗传操作的依据。个体的适应度高,则被选择的概率就高,反之就低。适应度函数(Fitness Function) 是用来区分群体中的个体好坏的标准,是算法演化过程的驱动力,是进行自然选择的惟一依据。该问题适应度函数定义为:

$f (x) = {\begin{matrix} g (x) - C_{\min}, & 若 g (x) - C_{\min} > 0 \\ 0 ‚ & 否则 \end{matrix}$

式中:Cmin既可以是特定的输入值,也可以是当前所有代或最近K代中g(x)的最小值,本问题中取为0。

3.3 选择算子

本文采用赌轮盘法赌选择算子,即将所有染色体的适应值之和看作一个轮盘,每个染色体根据其适应值的大小划分在轮盘中所占据的范围。然后旋转轮盘,当轮盘停下时,指针所对应的染色体即被选中,完成一次选择。重复上述过程,直到达到所需要的染色体个数为止。设群体规模大小为N,个体i的适应度值为fi,则这个个体被选择的概率为: $Ρ_{i} = \sum_{i = 1}^{Ν} f_{i}$ 。

3.4 交叉算子

交叉是遗传算法中一个最为重要的操作,也是遗传算法区别于其他传统优化方法的主要特点之一。群体中的每个个体之间都以一定的概率PC交叉,即两个个体从各自字符串的某一位置(一般是随机确定)开始互相交叉,这类似生物进化过程中的分裂与重组。利用交叉有可能由父代个体在子代组合成具有更适合度的个体。该实验中PC=0.6。

3.5 变异算子

基因的突变普遍存在于生物的进化过程中。变异是指父代中的每个个体的每一位都以概率PM翻转,即由“1”变为“0”,或由“0”变为“1”。遗传算法的变异特性可以使求解过程随机地搜索到解可能存在的整个空间,因此可以在一定程度上求得全局最优解。本实验中PM=0.001。

4 实验结果及分析

本文采用Matlab语言编程调试经过30次遗传迭代后,寻优结果如图1所示,图中“*” 表示经过迭代后的最优结果,此时最优解x*=7.859 2,f(x*)=16.995 0。

迭代过程中迭代次数与函数值的变化如表1 所示。可以看出,遗传算法迭代10次以后函数值基本趋于稳定,从图1也可以看出,表1中得到的值基本与图一的峰值相吻合。此算法对其他的多峰函数同样能快速搜索到最优解,可见遗传算法能快速搜索到多峰函数的最优解。

5 结语

通过该实验可以发现,采用GA求解多峰函数优化问题,形式直观,操作简单,GA表现出了强大的搜索能力。在工程技术、经济、科学和社会等许多领域中存在的大量的连续性的整体优化问题,均可以采用上述方式,并且可以很直接地运行于并行计算环境,克服了传统启发式搜索算法存在的多方面的局限性。

摘要：目前,对于整体优化问题已经进行了大量理论研究,并提出了许多基于导数的解析方法和其他非解析的数值优化技术。但是,在实际领域中存在着各种高度复杂的优化问题,其目标函数可能表现为非连续或非处处可微、非凸、多峰和带噪声等各种形式,这类复杂优化问题不适合于采用解析方法,同时用传统上的搜索技术求解也会遇到许多困难。针对上述问题,提出利用遗传算法求解多峰函数的优化方法,新方法利用遗传算法的鲁棒性,对多峰函数进行优化,并用Matlab进行仿真,实验结果表明,遗传算法可以快速稳定地搜索到多峰函数的最优解。

关键词：遗传算法,多峰函数,优化方法,鲁棒性

参考文献

[1]HARIK G.finding multimodal solutions using restrictedtournament selection[J].Proceedings of the sixth interna-tional conference on Genetic Alogorithms,1995:24-31.

[2]TORN A,ZILINSKAS A.Global optimization[M].Ber-lin:Springer-Verlag,1989.

[3]刘妍,苏喜友.遗传程序设计理论与应用[J].微计算机信息,2010,26(27):115-117.

[4]马玉新,解建仓,罗军刚.方向自学习遗传算法[J].计算机工程,2009,35(17):14-18.

[5]朱灿,梁昔明.一种多精英保存策略的遗传算法[J].计算机应用,2008,28(4):939-941.

[6]李军化,黎明,袁丽华.一种改进的双种群遗传算法[J].小型微型计算机系统,2008,29(11):2099-2102.

[7]席红雷,行小帅,张清泉.基于梯度优化的自适应小生境遗传算法[J].计算机工程,2008,34(11):186-188.

[8]GASPAR A,COLLARD P.From GAs to artificial immunesystem:improving adaptation in time dependent optimiza-tion[C].[S.l.]:Proceedings of the Congress on Evolu-tionary Computation,1999.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【遗传优化搜索算法】相关文章：

基于遗传算法的优化设计论文04-28

应用遗传算法的齿轮传动优化设计09-11

遗传节约综合算法在配送路线优化中的应用05-10

遗传禁忌搜索算法06-03

遗传算法优化分段进水生物脱氮工艺的流量分配05-22

基于TSP问题的物流配送路径优化的遗传算法实现09-12

基于遗传算法和空间推进方法的高超声速进气道优化设计研究04-17

加速遗传算法05-19

遗传算法开题报告05-27

遗传算法论文范文05-09