选择算子

2024-05-28

选择算子（精选4篇）

选择算子篇1

1、引言

遗传算法是模拟生物进化过程, 借鉴生物界自然选择和自然遗传机制发展起来的随机化搜索算法[1]。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算, 是对自然选择的一种模拟, 也是遗传算法中一个重要的算子。经验数据表明, 传统的遗传算法存在早熟收敛和后期收敛速度慢的缺点[2], 许多学者对选择算子做了不同的改进。本文在总结相关文献资料的基础上, 从不同方面对选择算子的改进进行了讨论, 并展望其研究方向, 为遗传选择算子的选取提供相关的策略。

2、经典的选择算子

遗传算法中的选择算子根据个体适应度对种群中的个体进行优胜劣汰操作, 使得适应度较高的个体有较大的概率被遗传到下一代群体中;适应度较低的个体有较小的概率被遗传到下一代群体中。经典又成熟的选择算子是用遗传算法求解相应问题的首选, 常用的有比例选择, 无回放随机选择, 排序选择等。

(1) 比例选择方法是一种回放式随机采样的方法[1], 也就是我们通常称作的轮盘赌选择方法。个体被选中的概率与其适应度成正比。

(2) 无回放随机选择方法是根据每个个体在下一代中的生存期望值来进行随机选择运算。

(3) 排序选择方法是基于个体按适应度大小排序来分配各个个体被选中的概率。

通过选择, 交叉, 变异等遗传操作, 虽然种群在不断地进化, 产生更多的优良个体, 但毕竟这些操作都带有一定的随机性。也就是说最优的个体不一定会被选中, 新种群的最优个体也不一定是迄今为止的最优个体, 所以, 配合相应的遗传操作还要有最优保存策略。即当前群体中最好的个体和迄今为止最好的个体进行比较, 用最好的个体替换掉当前群体中最差的个体。

3、改进的选择算子

已有的选择算子比较成熟, 但遗传算法在求解问题中的性能有待提高, 许多研究者从选择算子的角度提高算法性能, 主要体现在理论和提高算法收敛性能两个方面。

3.1 选择算子在理论上的研究

选择算子在理论方面的深入研究并不多, 文献[3]利用3种权威测试函数对4种改进的选择算子进行了收敛速度、收敛可靠性和运算成本3方面的测试比较, 并对测试结果作了详细的分析。文献[4]指出了遗传算法的选择方式与其全局收敛性和收敛速度的关系。常用的选择算子不能保证算法的全局收敛性, 在引入改进选择策略后轮盘赌选择方式能保证算法的全局收敛性, 但收敛速度较慢。同时给出了遗传算法选择操作的若干策略。

3.2 选择算子在提高算法收敛速性上的改进

选择算子确保优秀的个体能够在新一代中得以保留, 但会使种群的多样性降低, 在实际应用中算法常收敛于局部最优解和后期收敛速度过慢等现象, 基于此有许多文献对选择算子进行了改进, 提高算法的收敛性能, 下面对此做个总结。

文献[5]在传统轮盘赌选择算子的基础上加入多轮盘和排序提出了一种基于排序的多轮轮盘赌选择算子, 并将此算子与最佳个体保存法的思想相结合, 进一步提出了无放回的基于排序的多轮轮盘赌选择算子, 能有效地提高算法的收敛性。文献[6]对选择交叉两个算子进行改进, 有效解决遗传算法中收敛速度与局部最优解的矛盾。文献[7借鉴生物中亲缘选择的思想, 提出基于亲缘选择的遗传算法。该算法构造新选择算子, 通过按亲缘关系放弃一个解而获得另一个解来保证算法在最优解的领域内的有效搜索。文献[8]提出基于三角函数的选择算子, 分析基于三角函数选择算子的可行性, 并通过实验比较基于三角函数的选择算子与其他选择算子的性能。文献[9]提出了一种高级选择模型, 它允许自适应控制“选择压力”。文献[10]在选择算子中引入裂变选择的思想, 避免种群中超级个体的出现, 维持了种群的多样性。文献[11]于基于正弦函数的选择算子克服了轮盘赌对适应值非负的要求, 非常适用于求解水库优化调度, 且能够很好地保持种群多样性。文献[12]把相似个体分在同一组中, 以组为单位进行选择, 并通过该组个体的特点进行高斯搜索生成新的群体。这样使得遗传算法在搜索过程中不仅可以很好地保持个体的多样性, 并且可以提高解的精确度。文献[13]在传统轮盘赌的基础上提出了一种基于排序的多轮轮盘赌选择算子, 在提高了算子选优能力的同时也减少了随机性所产生的误差。文献[14]提出了交替选择算子配合传统的盘赌选择算子, 以增加种群多样性。文献[15]选用轮盘选择和锦标赛选择相结合自适应选择算子的遗传算法, 并优化TSP问题求解, 则可以调整收敛速度, 避免被动式搜索。

4、展望选择算子的研究方向

选择算子的改进有助于遗传算法性能的提高, 在总结相关文献的基础上, 对选择算子的研究有以下几点展望:

(1) 加强遗传算法基础理论的研究

选择算子的改进还是缺少理论的指导, 需要加强遗传算法理论方面的研究。在对遗传算法的研究中, 理论的发展一直是个薄弱环节。虽然通过许多的实例验证了选择算子的改进对算法性能的改善, 但缺少理论上的分析。

(2) 借鉴多种思想改进选择算子

在解决实际问题中有选择策略的思想都可以考虑和基本的选择算子进行结合, 或可以根据相应的选择思想提出全新的选择算子, 同时也需要多种思想的综合考虑。

(3) 求解问题的多元化

改进的选择算子的性能主要是通过测试函数来进行验证, 但对其他问题是否适用, 需要进一步讨论。

5、结束语

遗传算法中的种群在进行更新时, 第一步要进行选择操作, 不同的选择算子对算法性能有不同的影响。本文对遗传算法中选择算子及其改进进行了介绍, 从不同方面给出选用选择算子的策略, 为遗传选择算子的选取提供了更好的途径。

选择算子篇2

由于具有有利于减少资源占用与管理成本、有利于控制工程造价、有利于提升全面履约能力等优点,工程总承包模式已经成为国内外建设活动中多有使用的承发包方式。在总承包模式下,分包商在很大程度上影响项目的实施进度、成本、质量,进而影响到总承包商企业的经营效率。这就要求总承包企业在选择分包商时全面分析评价分包商的实施能力。

目前国内常用AHP、模糊综合评价等方法来评价与选择分包商,亦有采用改进的并行混沌优化算法来进行决策。这些方法或者需要将定性指标定量化,或者要求决策者具有相应较高的决策理论基础,不利于在工程实践中推广。语言评度集结评价方法可以在评价者对各指标语言评价的基础上,予以直接的综合集结,评价方法计算简单,评价结果明确。因此,语言评度集结评价方法应是适合于对分包商评价与选择的一种综合评价方法。

1 分包商系统分析

分包是相对于总承包而言的,是指总包商将工程中的一项或者若干项具体工作的实施交给其他公司,通过一个分包合同约束对方在自己的管理下有其他公司来实施。实施分包工作的承包商称为“分包商”。系统论的结构功能原则表明,系统的结构是受环境的影响而改变的,这就要求在系统结构分析的同时兼顾系统环境的具体分析。

按照上述分包商系统分析思想,分包商系统是由管理、财务、组织、资源、技术等组成部分构成,不断进行着信息、物质、能量相互交流的有机整体。社会环境系统(包括政治环境、经济环境、科技环境、法律环境、社会文化环境等)、市场环境系统(包括市场容量、市场结构、市场规则、竞争对手、供应商、购买者等)自然环境系统(包括资源环境、生态环境等)[2]等与分包商相关联的因素共同构成分包商系统的外部环境[1]。分包商系统结构如图1[1,2]所示。

2 构建综合评价指标体系

2.1 筛选评价指标的原则

构建一套完整全面反映分包企业承包实力的指标体系是合理选择分包商的基础。在对分包商系统的目标、功能、环境以及各管理要素进行系统分析的前提下,建立有机统一的评价指标系统体系。评价指标体系的建立应遵循的以下三个原则:

2.1.1 科学性原则

评价指标体系的设计应严格从分包企业分包能力的定义出发,首先要能够真实反映分包商的分包能力,其次要能够客观阐明决定分包商分包能力的内部因素和影响其分包综合能力的外部环境因素。

2.1.2 系统性的原则

全面整体的分析问题是系统分析的基本思想,在全面整体评价的要求下应兼顾考虑局部评价的重要性。因此在指标体系构建和具体评价指标选取上,应以构建科学完整的评价系统为出发点,考虑各评价指标在评价指标体系中的合理构成,以及各具体评价指标间的逻辑关联关系,以此保持评价指标的相对均衡统一,实现评价指标系统的最优化。

2.1.3 可评价性和可操作性相结合的原则

指标体系的应用性决定整个评价体系的可操作性,评价指标应具有普遍可统计性,定义要明确,界限要分明,易于测得和比较。

2.2 综合评价指标体系

在管理系统工程中,系统综合评价就是全面评定系统的价值。而价值通常被理解为评价主体根据其效用观点对于评价对象满足某种需求的认识。对于由图1建立起的待选择分包商系统,在各待选分包商满足法律规定的诸如资质水平、注册资金等强制性指标的前提下,根据上述指标筛选原则可以构建出目的明确、层次清晰的评价指标系统,如图2。

评价指标系统主要由以下指标则构成:

(1)报价水平,分包商的对分包工程的报价高低。

(2)技术装备水平,分包商项目团队的技术人员以及大型器械的配备水平。

(3)财务能力,分包商的完成的分包工程的经济财务实力。

(4)项目管理能力,分包商对于工程项目实施的管理能力,包括工程项目实施过程中的工期、成本、质量、安全管理等。

(5)沟通协调能力,在项目实施的工作中分包商与总包方、其他分包商、业主方、设计方、监理方的协调沟通能力。

(6)类似工程的经验,近年来分包商承揽类似工程的经验。

(7)信誉水平,分包商企业的业内诚信水平和业主对其提供承包服务的满意程度。

3 语言信息集结算子评价决策方法[3]

鉴于专家对于分包商的评价都是语言值,如“好”、“很好”等;而且每个评价指标的权重也是语言值,如“稍重要”、“重要”等;因此语言加权取大算子(LWM算子)和混合语言加权平均算子(HLWA算子)便是评价和选择分包商的最佳选择。

利用LWM和HLWA算子评价决策的过程如下:

步骤1,对于以多属性群决策问题,设X,U和D分别为方案集、属性集和决策者集,且设ω=(ω1,ω2,…,ωn)为属性的权重向量,λ=(λ1,λ2,…,λt)为决策者的权重向量,且ωi,λkS(i∈M,k=1,2,…,t)。设决策者dkD给出方案xiX在属性uj下的语言数据评估值(属性值)rij(k),并得到决策矩阵Rk=(rij(k)),且rij(k)∈S。

步骤2:利用LWM算子对决策矩阵Rk中第i行的属性值进行集结,得到决策者dk所给出的决策方案xi综合属性值

步骤3:利用HLWA算子对t位决策者给出的方案xi的综合属性值zi(k)(ω)(k=1,2,…,t)进行集结,得到决策方案xi的群体综合属性值zi(λ,μ)=HLWAλ,μ(zi(1)(ω),zi(2)(ω),…,zi(t)(ω))=maxjmin{μk,bi(k)}(i∈N),其中μ=(μ1,μ2,…,μt)是HLWA算子的相关联加权向量。且μk∈S(k=1,2,…,t),bi(k)是一组加权语言数据(ηi(1),ηi(2),…,ηi(t))中第k大的语言数据,其中ηi(t)=min{λl,zi(l)(ω)},l=1,2,…,t。

步骤4:利用Zi(λ,μ)(i∈N)对方案进行排序和择优。

4 分包商选择的语言信息集结算子评价案例

某总承包商欲将其承包的大型房屋建筑的幕墙工程对外分包,现委托三位专家d1、d2、d3利用文章上述的语言信息及结算子评价方法从3个待选择分包商x1、x2、x3选出最优分包商。语言评度集S={s-4,s-3,s-2,s-1,s0,s1,s2,s3,s4}={极差,很差,差,稍差,一般,稍好,好,很好,极好}或={极不重要,很不重要,不重要,稍不重要,一般,稍重要,重要,很重要,极重要}。

4.1三位专家根据图2所示的指标给出三个分包商的语言评度值如评价矩阵R1、R2、R3。

已知指标属性值权重向量ω=(ω1,ω2,…,ω7)=(s3,s1,s1,s3,s2,s2,s0),决策者权重向量λ=(λ1,λ2,λ3)=(s3,s0,s1)。HLWA的加权向量μ=(s3,s0,s2)。

4.2利用LWM算子对决策矩阵Rk中的行属性值进行集结,得到各决策者对于每个方案的决策综合属性值:Z1(1)(ω)=s3,Z2(1)(ω)=s2,Z3(1)(ω)=s2;Z1(2)(ω)=s2,Z2(2)(ω)=s2,Z3(2)(ω)=s2;Z1(3)(ω)=s3,Z2(3)(ω)=s2,Z3(3)(ω)=s2。

4.3利用HLWA算子集结决策者集的评价数据,得到各分包商分包能力综合语言评度值:Z1(λ,μ)=s3;Z2(λ,μ)=s2;Z3(λ,μ)=s2。

4.4由Z1(λ,μ)>Z2(λ,μ)=Z3(λ,μ)知分包商x1的分包综合能力优于x2、x3,建议总包方选分包商x1作为分包合作伙伴。

5 结语

文章立足于总承包商企业角度,从系统理论出发,构建了选择分包商的综合评价指标体系,提出了基于LWM算子和HLWA算子的综合评价方法。评价指标体系全面反映了关乎分包商分包综合能力的各重要因素。LWM算子和HLWA算子,使评价人员和决策者的主观经验得到了充分体现。这种方法不用评价语言值数值化,对评价者、决策者的决策理论知识要求不高,是一种科学合理、可操作性强的分包商评价与选择方法。

摘要：从建筑总承包企业的角度出发,分析了影响分包商选择的各项因素,以此为基础构建了分包商承包能力评价的多层次指标体系,提出利用语言信息算子(LWM算子和HLWA算子)对分包商进行评价和排序,算例证明这是一种科学合理、可操作性强的分包商评价与选择方法。

关键词：分包商,综合评价,LWM算子,HLWA算子

参考文献

[1]赵锡斌.企业环境研究的几个基本理论问题[J].武汉大学学报(哲学社会科学版),200401,57(1).12-17.

[2]康承业,汪波.建筑企业承包商选择的综合评价方法研究[J].天津大学学报(社会科学版),201005.12(3).215-218.

选择算子篇3

遗传算法(Genetic Algorithm,GA)是由Holland在借鉴生物界自然选择原理和自然遗传进化机制的基础上于1975年提出的全局自适应搜索算法[1]。它从代表问题的可能潜在解集的一个种群开始,通过选择、交叉、变异等操作,使种群得到不断的进化,直至满足遗传终止条件为止。通常把这种基于单种群的遗传算法称为简单遗传算法或标准遗传算法(Simple GA,SGA)。遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对所求解问题的种类具有很强的鲁棒性。但传统遗传算法存在的寻优能力差、易出现早熟的缺点[2],文献[3,4,5]对传统遗传算法的编码方式进行了改进,在一定程度上提高了遗传算法的收敛性。另外还有一些学者将动态规划[6]、逐次优化[7]、免疫算法[8]、模拟退火[9]、蚁群算法[10]分别与遗传算法相融合。其对遗传算法的研究仅体现在编码方法和多算法融合两方面,而对遗传算法的操作算子并未进行多少改进。本文对遗传算法的选择算子进行了改进,并在交叉变异之后引入了最优保存策略,将改进后遗传算法用于水库短期优化调度中,结果令人满意。

1 水库短期优化调度模型

以发电量最大为目标建立水库短期优化调度数学模型。模型目标函数及约束条件如下:

目标函数:

$Μ a x f = \sum_{i = 1}^{n} Κ q_{i} Η_{i} Δ t (1)$

约束条件:

最小下泄流量和最大下泄能力约束:

$Q_{\min} \leq Q_{i} \leq Q_{\max} (2)$

允许最高水位和最低水位约束:

$Ζ_{\min} \leq Ζ_{i} \leq Ζ_{\max} (3)$

保证出力和装机容量约束:

$Ν_{\min} \leq Ν_{i} \leq Ν_{\max} (4)$

水量平衡约束:

$V_{i + 1} = V_{i} + R_{i} - Ο_{i} (5)$

式中:f为总发电量,kWh;K为出力系数;qi为i时段发电流量,m3/s;Hi为i时段平均发电水头,m;Δt为时段长度,h;n为时段数;Qi为i时段下泄流量,m3/s;Qmin为最小下泄流量,m3/s;Qmax为最大下泄能力,m3/s;Zi为i时段初水库蓄水位;Zmax为允许最高水位,m;Zmin为最低水位,m;Ni为i时段的出力;Nmin为保证出力,万kW;Nmax为装机容量,万kW;Vi+1为i+1时段初库容,亿m3;Vi为i时段初库容,亿m3;Ri为i时段来水量,亿m3;Oi为i时段下泄水量,亿m3。

2 遗传算法的设计

在水库水位允许变化的范围内,随机产生pop个代表水库运行过程中水位的序列(Z11,Z12,Z13,…,Z1n),(Z21,Z22,Z23,…,Z2n),…,(Zpop1,Zpop2,Zpop3,…,Zpopn)作为初始种群,按预定的目标函数进行评价,计算种群中每个个体的适应度,根据适应度对个体进行选择、交叉、变异等遗传操作,再经过反复迭代直至满足迭代终止条件为止。

2.1 个体编码

编码是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法。在水库优化调度中常使用实数编码方式。其具体编码步骤:根据求解精度的要求,把水位变化区间[Zmin,Zmax]分成m等份,并按从小到大的次序用整数1,2,3,…,m+1来表示。个体的基因型相应地用这些实数来表示,如在1至m+1之间的某一实数j所表示的实际水位为:

$Ζ_{i} = Ζ_{\min} + \frac{Ζ_{\max} - Ζ_{\min}}{m} \cdot (j - 1) (6)$

2.2 初始种群的产生

研究发现,初始种群的分布性质严重影响整个算法的收敛性,因此尽量使初始种群中更多的个体落在可行解空间内是提高算法收敛性的前提条件。本文采用有约束生成方式来生成含有pop个个体的初始种群。

2.3 适应度评价

适应度是反映种群中个体优劣程度的指标。适应度函数的表达式:

$F = f - \sum_{i = 1}^{k} Μ (7)$

式中:F表示适应度;f为目标函数值;M惩罚值;k为个体中违约的基因数。

2.4 选择算子的改进

选择算子是指以一定的方法从种群中选择出优良个体进入下一代种群中。针对标准遗传算法的轮盘赌选择初期容易引起种群多样性的降低与后期收敛速度慢的问题,本文对选择算子进行改进,提出一种比例复制方法,即先从原种群中找出适应度最高的个体,把该个体复制Ps×pop份,再依选择比例Ps从原种群中选出Ps×pop个个体,把这些选出的个体用种群中适应度最高的个体代替。这样可以使遗传算法在进化的初期一定程度上保持种群的多样性并且在进化的末了阶段仍然具有对优秀个体的选择能力,提高了遗传算法的全局收敛性。

2.5 交叉算子

交叉是指对两个相互配对的染色体按某种方式相互交换其部分基因,它是通过基因重组产生新个体的主要手段,决定了GA的全局搜索能力。其基本方法是先对种群中的个体进行两两配对,以交叉概率Pc指定要进行交叉运算的配对个体,对配对个体以随机生成的[1,n-1]之间的整数所代表的位置为起始交叉点,交换该点之后的遗传基因。例如,相互配对的个体的基因编码分别为:

$\begin{array}{l} A_{1} = (2 7 10 13 14 | 17 20 18 16 14 11) \\ A_{2} = (3 8 9 11 19 | 22 17 16 15 12 6) \end{array}$

若随机生成的交叉点的位置是5,则这两个个体就从第6个基因开始交换编码。交换后的新个体为:

$\begin{array}{l} A_{1}^{´} = (2 7 10 13 14 | 22 17 16 15 12 6) \\ A_{2}^{´} = (3 8 9 11 19 | 17 20 18 16 14 11) \end{array}$

2.6 变异算子

变异算子是通过基因突变产生新个体的辅助手段,它决定GA的局部搜索能力。非均匀变异是指对原有的基因值做随机扰动,以扰动后的结果作为变异后的新基因值,它可使遗传算法在初始阶段以较大的概率进行全局搜索,在后期运行阶段进行重点区域的局部搜索,从而加快收敛速度。本文采用非均匀变异方法,其操作过程为,对于个体的每一个基因座,依变异概率Pm指定其为变异点,然后对该变异点进行变异。例如,若个体Z(Z1,Z2,…,Zk,…,Zn)中的基因Zk被指定为变异点,则对该基因在其对应的定义区间[Zmin,Zmax]内进行变异,变异公式为:

$\begin{array}{l} Ζ_{k}^{´} = {\begin{cases} Ζ_{k} + Δ (t, Ζ_{k, \max} - Ζ_{k}), r a n d (2) = 1 \\ Ζ_{k} - Δ (t, Ζ_{k} - Ζ_{k, \min}), r a n d (2) = 2 \end{cases} (8) \\ Δ (t, y) = y [1 - r^{(1 - t / Τ) b}] (9) \end{array}$

Rand(2)是指随机产生的[1,2]之间的整数。函数Δ(t,y)的值域为[1,y]。其中r为产生的[0,1]之间的随机数,t为当前进化的代数,T为总的进化代数,b为决定非一致程度的参数。

2.7 最优保存策略

在遗传算法的运行过程中,通过对个体的交叉、变异等遗传操作而不断地产生出新的个体。虽然随着群体的进化过程会产生越来越多的优良个体,但由于选择、交叉、变异等遗传操作的随机性,它也可能破坏当前群体中适应度较好的个体,从而对遗传算法的运行效率和收敛性产生不利的影响。,因此本文将最优保存策略引入到遗传操作当中从而将适应度最好的个体要尽可能地保留到下一代群体中。其具体操作过程是:

(1)找出当前群体中适应度最高的个体;

(2)若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高,则以当前群体中的作为新的迄今为止的最好个体;

(3)若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度低,则用迄今为止的最好个体替换掉当前群体中的最佳个体。

已有文献证明,使用保存最优个体的遗传算法收敛于最优解的概率为1[1]。

2.8 终止策略

遗传算法迭代的终止条件一般采用如下准则:

(1)是否到了预定算法的最大代数;

(2)是否找到了某个较优的染色体;

(3)连续几次迭代后得到的最优解是否变化等;

在水库优化调度中通常以满足最大迭代次数为遗传终止条件。

3 实例应用

以葛洲坝水电站为例,使用改进遗传算法对其进行优化调度,并把得到的调度结果与标准遗传算法相对比。已知该水电站装机容量271.5万kW,保证出力76.8万kW,库容15.8亿m3,设计正常蓄水位为66.5 m,最低水位65.5 m,最小下泄流量3 200 m3/s,调度期初和调度期末的水位都是66 m,调度期为1 d。取设计条件下5次入库径流系列对两种遗传算法分别以进化代数50代、100代、150代、200代和250代各模拟5次,其结果见表1。由表1可知,随着进化代数的增加,两种方法所得到的平均出力呈增加趋势,而改进遗传算法的出力明显高于标准遗传算法。

为更详细地比较两种方法的特点,作者对两种方法在流量过程1下的模拟结果进行分析,见图1。从图1可以看出,标准遗传算法的全局搜索能力较弱,随着进化代数的增加,易陷入局部最优解,而改进遗传算法收敛速度较快,在后期其局部搜索能力也更强。

为了评价两种遗传算法趋近全局最优解的能力,本文又把该结果与在同一求解精度下动态规划所求的总出力相比较,见表2。由表2可知,在进化250代的情况下,AGA所得到的平均出力占最优值的比例在0.998～0.999之间,而SGA的结果仅占最优值的0.987～0.991,说明AGA趋近于全局最优解的能力更强。

4 结论

(1)针对标准遗传算法收敛性差,易陷入局部最优解的缺点,本文对其选择算子进行了改进,在选择算子中提出了对优秀个体进行比例复制的方法,并在交叉变异之后引入最优保存策略。建立了水库短期优化调度模型,并用改进遗传算法进行求解,结果表明,此改进算法的收敛性比标准遗传算法收敛性更快,更易趋近于全局最优解。

(2)由于GA是随机搜索算法,进化相同的代数所得到的最优值也可能不一样,因此在水库优化调度中,为了得到更好的效果,应该对其进行多次演算。

参考文献

[1]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[2]罗志军.遗传算法的全局收敛性的齐次有限马尔柯夫链分析[J].系统工程与电子技术,2000,22(1):73-76.

[3]王大刚,程春田,李敏.基于遗传算法的水电站优化调度研究[J].华北水利水电学院学报,2001,22(1):5-10.

[4]陈立华,梅亚东,董雅洁,等.改进遗传算法及其在水库群优化调度中的应用[J].水利学报,2008,39(5):550-556.

[5]胡明罡,练继建.基于改进遗传算法的水电站日优化调度方法研究[J].水力发电学报,2004,23(2)17-21.

[6]刘攀,郭生练,雒征,等.求解水库优化调度问题的动态规划-遗传算法[J].武汉大学学报(工学版),2007,4(5):1-6.

[7]许银山,梅亚东,魏婧,等.梯级水库群长期优化调度的逐次优化-遗传算法[J].中国农村水利水电,2008,(9):25-27.

[8]叶碎高,温进化,王士武.多目标免疫遗传算法在梯级水库优化调度中的应用研究[J].南水北调与水利科技,2011,9(1):65-67.

[9]涂启玉,梅亚东.基于改进遗传算法的溪洛渡水库优化调度研究[J].水电能源科学,2008,26(3):39-42.

选择算子篇4

遗传算法(Genetic Algorithm-GA)的产生最早归功于美国Michigan大学的Holland在20世纪60年代末、70年代初开创性工作[1],是模拟生物遗传和自然淘汰的生物进化过程的一种模型。与传统的优化算法有较大的不同,遗传算法有其自身的优点,主要表现在以下几方面[2](1) GA在每个时刻都可以对多个子空间进行搜索,对初始值不做要求。(2) 在GA中仅靠适应度来评价个体优劣,基本上不用搜索空间的知识或辅助信息。(3) GA具有很强的鲁棒性。虽然GA具有诸多的优点,但作为全局搜索算法,仍然存在无法全局收敛的情况,发生这种情况较为典型的是“早熟”现象。遗传算法“早熟”是指群体多样性遭到破坏,算法搜索停滞不前,最终收敛到一个局部最优解,而无法收敛到全局最优解。“早熟”现象的本质特征是因为群体多样性受到破坏。

在选择算子的作用下,优秀模式会大量增加,低劣模式会迅速减少,整个群体向好的方向进化,但是在选择算子的作用下,群体丧失了多样性,群体进化中后期就可能产生“早熟”现象。针对传统遗传算法“早熟”现象,许多的研究人员对其进行了改进,如文献[3]作者通过改进传统的选择算子,从而对传统GA进行了改进,文献[4]采用种群多样性算子产生较好的初始种群分布,并以该算子作为判断种群是否早熟收敛的依据。本文分析研究了“早熟”现象产生的原因,通过改进传统杂交算子和引入二元变异算子来替换传统变异算子对遗传算法进行了改进,实验结果证明,改进后的算法有效的抑制了“早熟”现象的出现。

1 简单遗传算法(Simple Genetic Algorithm)

标准遗传算法的运行过程为一个典型的迭代过程,其必须完成的功能工作内容及主要步骤如下:

1)选择合适的编码策略,把实际问题的参数集合X和域转化为位串结构空间S;

2)定义一个合适的适应度函数f(X);

3)确定所需要的遗传策略,其中包括选择群体大小N,选择交叉及变异方法,以及确定交叉概率pc、变异概率pm等相关的遗传参数;

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

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

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

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

2 算法改进

2.1 交叉算子的改进

在传统的遗传算法中,经常会出现“近亲繁殖”现象。所谓“近亲繁殖”现象即:一对父母A,B经过遗传操作后产生的一对子代为ab1、a1b、ab1、a1b随即被放入子代中。然而在进化到下一代或者下几代的时候,ab1、ab1很有可能作为新的父母进行遗传操作,此时即发生了“近亲繁殖”。这也是造成群体单一性的主要原因之一。