优化临淮岗工程资源的遗传算法优化方案

1.问题分析

针对临淮岗洪水控制工程,在工程建设时为了能获得质量优良、资源消耗少、工程成本低的效果,就必须对资源进行较好的分配和安排,力求每天所需资源量接近平均值,避免出现资源需求量大起大落的现象。均衡施工可以大大减少资源需求量的强度、机械设备和运输工具需要量以及施工现场的各种临时设施,降低施工管理费,避免不必要的损失,从而降低工程造价,工期固定,资源均衡是优化目标。

主坝施工现场图

姜唐湖进洪闸施工现场图

“工期固定、资源均衡”就是在不延长总工期的前提下,调整非关键分项工程的作业起讫时间达到资源尽可能均衡的目的。根据资源分布函数的均方差、极差和资源的需要量变化的频繁程度等指标,来衡量资源是否均衡。上述指标愈小,说明资源愈均衡。在实际工程中,很难使上述指标都达到最小,因此往往根据所需均衡的资源选一种最合适的指标作为衡量标准。

2.模型的建立与描述

在给定初始网络计划的条件下,设每个分项工程所需资源量是事先确定的,网络计划的时间参数也可通过计算事先得到,那么多维资源均衡优化的目标和一维资源均衡优化的目标是一样的,就是使单位时间资源消耗的方差为最小,数学模型描述如下:

式中 T——工程的总工期;

R(t)——在工程的t时刻所有资源的加权资源量;

Rm——在工程的整个工期内所有资源的加权平均值;

m——工程中用到的所有资源种类;

i—— 分项工程;

n——分项工程数;

Ritk——t时刻第i个分项工程第k 种资源的需要量;

ω(ikt)——分项工程i的第k 种资源在t时刻的权重;

Rkt(i)——分项工程i的第k 种资源在t时刻的资源量,一般为常量;

Ts——分项工程的实际开工时间;

T(i)——分项工程i的工期;

Ts(k)——分项工程i的紧前分项工程的实际开工时间;

T(k)——分项工程i的紧前分项工程的工期;

TL(i)——分项工程i的最晚开工时间;

TE(i)——分项工程i的最早开工时间;(www.xing528.com)

Ts(i)——分项工程i的实际开工时间;

S(i)——分项工程i的自由时差。

3. “工期固定——多种资源均衡” 优化的遗传算法设计

(1)染色体设计。

以每个分项工程的实际开工时间作为变量,并占用一个单元,按照分项工程的编号顺序将所有分项工程排列成一行,形成染色体串,如图3-9所示。

图3-9　染色体结构图

(2)编码设计。

染色体中的每一段代表一个分项工程的开工时间,它的取值范围为Ts(i)∈[TE(i),TL(i)],令TE(i)=Ts(i)-TE(i)表示开工时间的相对值,则:0＜Ts(i)＜S(i),将Ts(i)的二进制编码放入染色体段中,则它唯一确定了(i)分项工程的开工时间,它的编码长度由松弛时间S(i)决定。

(3)产生祖先。

随机产生一组初始解(n个)(下面将一组解称为一个种群,Population)。这几个初始解所构成的解集为原始群体。母体数N 是每一代个体的固定总数,也即初始解的个数。根据调试经验,N 取60左右应该是合适的。

(4)选择方法。

计算每个染色体的适应值,从中选出适应值较大的n 个串,称这n 个染色体的集合为一个匹配集 (Mating Pool),这个过程叫选择(Selection)。选择的方法有多种,在此采用了转轮法(Roulette Wheel Method)。

(5)交叉。

交叉是GA 的核心操作,是产生新的优秀个体最主要的手段。交叉可以把两个染色体中优良的性能传递到下一代的某一个染色体中,使该染色体具有优于其父辈的性能,如果交叉后得到的后代性能不佳,则可以在此后的选择过程中将其摒弃,匹配集中只保留性能比较好的染色体。交叉率的大小将直接影响优化结果。

计所选择的一对父本为A1和A2,其适应度值分别为f1和f2,传统的GA 对A1和A2的交换操作是首先产生一随机数i (1＜i＜k),然后交换其位置i左边的部分,产生一对子染色体A1和A2,改进后的操作实际上并不对A1和A2的基因进行交换,而是按序由A1和A2中选取等位基因组成一个子染色体,选取的原则是适应度高的父本被选取的概率大,其过程为先计算选取等位基因的概率。

然后从i=1,2,…,k按照P1,P2从A1或A2中选取等位基因。

(6)变异。

变异操作是模拟生物在自然环境中由于各种偶然因素引起的基因突变过程,表现为码串中字符的翻转,即0变1或1变0。变异率Pm分布在0～1之间,一般取0～1%之间的一个数。变异率Pm较小时新个体出现得少,但由于个体较稳定,故收敛性好。随着变异率增大,新个体变多,优秀个体出现几率大,故结果更优,收敛性也较好。但再增大,由于个体的稳定性差,可能使好的个体未保留下来就被破坏了,致使结果和收敛性都变坏了。

(7)译码及约束条件的处理。

在优化问题中对约束条件的处理,用遗传算法进行搜索时通常有两种策略:一是不允许搜索进入不合法区域,让群体中的所有个体均满足给定的约束,并要求产生的子代也满足给定约束;二是允许在一定程度上偏离合法区域,群体中的个体可以在一定程度上违反给定的约束,但必须在个体的适应度计算上体现违反的程度,一般通过惩罚项来实现。

(8)算法实现过程。

该优化工程的实现过程可以用如图3-10所示。