基于遗传算法与强化学习的机位分配问题研究，许永磊，曾伟，机场停机位分配是机场运行调度的一项非常重要的工作。为提高机场运行效益和服务质量，针对机场机位复杂的调度问题，本文提出了新
山国武技论文在线 目标优化函数 最大离港靠桥次数 ∑∑ 离港机位是近机位的航班数量。 最少空闲时间 ∑∑ 所有机位的相邻航班离港时刻间隔时间的总和。 最少拖拽次数 ∑∑ 离港杋位与进港机位不是同一机位的航班数量。 约束条件 飞札唯一性约束 机位唯约束: 航班必狐停靠满足该机型的机位: 航班类型约束: 国际航线、特殊专访航班必须停在特定指定机位。 航班功能需求约束: 时间约束: 相同离港枳位,紧邻两个航班至少间隔九十分钟。 遗传算法步骤与结果 编码表示 染色体二进制编码虽然具有更广的搜索空间,但是不能很好的表示机位分配问题,所以 夲文利用整数编码。夲文提出新的染色体编码策略即利用两个基因表示一个航班,第一个基 因表示飞机进港机位,第二个基因表示飞机离港机位。所以整个染色体长度是飞机数量 的两倍,即 考虑到奇数位基因代表飞札进港札位,必须具有唯一性,偶薮位基因代表离港札位,具 有可重复性,借鉴文献编码方法,木文提出改进的编码策略,即令奇数位基因数字代表 剩余机位集合下标索引号,偶数位基因数宇代衣实际离港机位号,如图所示。这样产生的 山国武技论文在线 染色体,可以保证交叉和突变运算的后代染色体具有不冗余性。 第n个飞 机走港机‖机离港机‖机进港机|机离港机 机讲洪机‖机离港机 位下标号 位下标号 位号 位下标号 位 图染色体信息 若机位集合 则染色体 表小第一架飞机进港机位 、离港杋位,第二架飞杋进港机位、离港杋位,第三架飞机进港机位、离港机 位。这样,一个合法的染色体具有如卜特征;)奇数位基因可以不同,也可以相同,) 偶数位具有相同基因的飞机满足吋间约束 初始种群的生成 根据航班信息表和业务规则,把所冇航班分配到航站楼或机库,另外,航班数量可能比 机场杋位数量多,因此需要考虑离港时刻杋库到航站楼或航站楼到航站楼间调度的情况,即 如果航站楼存在安全时刻的空闲近机位,可以把航站楼未分配到离港近机位的航班 调度到,或把机库中未分配到离港机位的航班调度到,同理,可把航站楼未分配 到离港近机位的航班调度到,或把机库中未分配到离港机位的航班调度到或,这 样可以保证所有机位尽可能被利用。各个航站楼基因按顺序组合起来即可得到一个待评估 解,重复上述步骤得到初始化种群。 算法流程如下 )根据航班信息和业务烑则把肮班分配到肮站楼或机库, ()各个航站楼按照进港时刻从晚到早排序, ()根据航线类型、功能需求、飞机机型分配进港机位, ()优先分配近机位进港, ()近机位已满后,分配可调远机位和固定远机位进港, ()进港分配完成后,进行离港机位分配, ()近机位飞机直接近机位离港, ()可调远机位先随机找一个近机位,判断该机位相邻航班时间约束是否满足,如果 满足,逑行卜—个可调远机位离港分配,否则再随机选择其他近札位,如果木航站楼近机位 都无法满足,执行步骤,否则执行步骤 )査看紧邻航站楼是否有安全时间段空闲近机位,若有,就调度过去,否则就等明 天调度, 可调远机位都已分配离港机位。固定远机位不可靠桥,直接在进港机位离港 若机库有飞机,按业务规则将机库航班调度到 航站楼中存在安全时间 段的空闲机位进行离港 得到一个初始解,由 所有约束条件组成的检验函数检验,若合法,执行步 骤(),否则执行步骤(), 如果和群数量小丁规定大小,执行步骤(),否则结束。 交叉、变异、适应度函数的设计 山国武技论文在线 交叉 釆用经典的轮盘赌策略选择两个父代进行单点交叉。改进的染色体编码策略,交叉以 后得到两个子代,基因具有不冗余性,如图所示 交叉点 图交叉 以机位集合 为例,若父代染色体分别为、 ,交叉点为,其中 是近机位, 是可调远机位, 是固定远机位 则父代对应实际机位编号 父代对应实际机位编号 子代对应实际机位编号 ,子代对应实际机位 编号 中奇数位基因虽有相同,但是对应实际机位编号却不同,显然, 子代都具有编码合法性,在交叉时候是不会存在同一架飞机对应不同进港机位的问题,并且 机位与航班机型兀配ε但这里需要注意一个问题,交叉作用以后,离港约束条件可能无法满 足,为了防止这些无意义的后代通过高的适应度值被保留下来,这里对所有后代进行 检验,然后淘汰不合法的后代 变异 为了提高种群的多样性,避免算法陷入局部最优,需要对染色体进行变异处理。另外为 了提高算法的效率,采用基因对变异策略,即无论变异氐是奇数位还是偶数位,该点对应航 班的两个基因都要一起变异。从符合机型要求的剩余空闲机位集合中随机选一个下标号作为 奇数位突变后基因,从符合札型要求的剩余空闪机位集合中随机选一个作为偶数位突变后基 因,这样可以避免由于近机位、可调远札位的走港、离港规则约束而产生不合法的突变子代。 如图所示岩变异点是第五个,满足该点对应机型的机位集合 ,则父代 对应实际机位编号 ,子代对应实际机位编号 。显然变 异后子代染色体具有缤码合法性,保证进港机位不冗余且机位与机型匹配,但离港约束条件 可能无法满足,所以要采用对所有后代进行筛选。 突变基因对 图突变 山国武技论文在线 适应度函数 目标优化函数作为适应度函数,即出港靠桥次数、空闲时间、拖拽次数。考虑到多个目标兰 位和景响幅度的不同,采用归一化方法进行处理,利用权重系数法来解决多目标优化的问题 如公式所示 其中: 为出港靠桥次数, 为空闲时间, 为拖拽次数, 为适应度函数,α’β,γ是常数,,并且采用精英策略,总是侏留父代和子代中适 应度最好的一批作为新父代且新父代的数量等于种群大小。 实验与结果 遗传算法中参数配置 般交叉概率 ,变异概率 初始种群大小,最大迭代次数 本 文参数配置如表 表参数配置 交叉 突 最大 初始航班a(权B(权(权 概率 交概率 迭代代数 化总群大小 数量 系数)重系重系 数) 算法结果 在处理器、内存的朕想笔记木电脑上利用 进行仿真,仿真结果在卜图中 所示。图代表种群最大适应度与平均适应度,图代表最大适应度个体靠桥次数与种群平 均靠桥次数,图代表最大适应度个体拖拽次数与种群平均拖拽次数,图代表最大适应度 个体空闲时间与种群平均空闲时间。 0.2 最人适应度 0.2 平均适应度 0.18 0.17 0.16 15 0.14 0.13 20 代数 山国武技论文在线 图种群最大适应度与平均适应度 最大适应度个体靠桥次数 62.8 种群平均靠桥次数 8 代数 图最大适应度个体靠桥次数与种群平均靠桥次数 27.1 26.9-4最人适应度个体拖搜次数 26.8 6.7 种群平均拖拽次数 26.6 26.5 26.1 26.3 26.2 40 200 代数 冬最大适应度个体拖拽次数与和群平均拖拽次数 4300 4250 4200 套1150x种群平均空闲时间 4050 x最大适应度个体空闲时间 1000 40 100 代数 图最大适应度个体空闲时间与和群平均空闲时间 山国武技论文在线 由上图可以看岀,第代以后算法收敛,种群中最优个体适应度为 靠桥次数 次,空闲时问 ,拖拽次数次。并且该算法运算时间为 遗传算法与强化学习结合的机位分配算法 算法步骤 遗传算法需要初始解集,这对于本身不知道初始解的大规模组合问题的求解是·和缺 陷。而强化学习采用试错评估模式,只需要清楚条件规则,通过奖励或惩罚的信号引导, 就可以在有限迭代下收敛,得到问题的解,于是针对以上问题,本文提出遗传算法与强化学 习结合来进行机位分配,即把遗传算法的染色体求解转换为多阶段决策问题,构造广义的马 尔科夫过稈,将适应度函数作为立即回报值,通过强化学习实现机位的分配。已有学者对于 遗传算法和强化学习的结合进行了研究,其中干本年、高阳等人提出了一种基于强化学习的 遗传算法,并证明其收敛。因此这两个方法的融合是有意义的。 杓建勹尔科夫过程:染色体中奇偶位基因都代表机位编号,且相邻两个基因代表一个航 班。因此把染色体分割成段,为航班数量。段基因组所有可能合法的组合构成状 态空间,在该状态空间中状态的选择构成了动作空间。每段基因,按照值表,根据状态 动作选择策略,选择动作。染色休对应的适应度作为每段所选动作的立即回报值 为了尽量减少搜索空间,把染色体求解转换为多阶段决策,即依次求、 航站 楼对应的子染色体,每个航站楼拥有自身的表,其中,对于每个航站楼,表示第 个航班的第个动作,表示一个航班的两个基因所有合法的组合。前文问题描述中已知 航站楼近机位、可调远机位、固定远机位的数量与机库机位数量,现求出各个航 站楼中每个航班的动作空间大小 (C+D)+E 其中表示第个航站楼每个肮班的动作空间大小,代表第个航站楼近机位数量, 代表杋场近杋位数量,代表第个航站楼可调远札位数量,代表札库机位数量,代 表第个航站楼固定远札位数量。 (5922)*(65)7 (5922)*(155)6735 + 染色体的适应度值作为立即回报值,各个航站楼更新自身表,迭代有限次后即可找 到最优染色体。若不采用多阶段决策,机场每个航班的动作空间人小为 十十十+十*十++ 很显然,多阶段决策可以吏好的减少搜索空间。 算法步骤 ()状态动作衣的构建:利用二维表存储值,代表第行第个动作,也代表第 个航班的第个基因组合,其中由式 可得 的表的列数,通过 业务规则可以得到每个航站楼所属飞杋数量,也即各个航站楼表的行数如表所示 山国武技论文在线 表状态动作表 ()初始化状态动作表:为了指引强化学习的探索步伐,加快学习效率,可以根据业务 柷则在初始化时候进行引导赋值。本文中表第行代表第个飞机,满足该飞机机型约束 的基因组合赋予正数,不满足约束的基因组合赋予负数 ()动作基因映射表:文中一个航班对应两个基因,二维表没小法直接展示动作与 基因的关系,仅可以表示第个航班对应的最好动作的值,为了使动作与基因能够相互转 化,必须定义一个映射表,为了说明问题,仅显示部分数据,如表所示 表动作基因的决射 动作值 基因对 )状态动作选择:对于每个航站楼每个航班,利用ε贪婪搜索算法,以-ε概率选择最 大的对应的动作、以ε概率随机选择第个动作,并记录该动作,用于自身衣更新 ()表更新:和和组成的染色体利用 检验是否符合条件约束要求,如 果符合,=适应度值,否则 是立即回报值,采用 算法史新、 各自的表,算法如公式所示。 其中:α是学习率,λ是折扣系数,是航班在时刻的基因组合,是航班在时刻 的动作,是航班在时刻转移后的实际基因缉合,是航班在时刻转移后的实际动作。 算法结果 强化学习中参数的配置 选用相同的航班,共架,幕数等于种群大小与迭代代数的乘积,即 另外,为 了解决强化学习前期与后期关于探索和利用的矛盾,采用变化ε策喀,即 主要参数配賀如表。 表参数醉置 a(学习率)(折扣系数) C(贪婪慨率) 航班量 山国武技论文在线 实验结果 在处理器、内存的联想笔记本电脑上利用 仿真,图代表实际选择染色 体与最人值对应染色体是否合法,是不合法,是合法。通过多次的试错探索 最大值对应染色体廾始合法,并且实际选择染色体的合法频率越来越高。图代表实际 选择染色体与最大值对应染色体的适应度,实际选择染色体的适应度在附近波动,且 大约幕后波动幅度越来越小。图代表最大值对应染色体的空闲时间。图最大 值对应染色体的靠桥次数。图代表最大值对应染色体的拖拽次数 0.9 -实际选择染色体 0.8 最大Q值对应染色体 0. 0.6 0.5 0. 0.1 0 epoxide(幕 图实际选择柒色体与最人值对应染色体的合法性 实际选择基犬型 最大Q值对应基因型 0.15 .1 1000 2000 3000 4000 6000 7000 de(幕) 图实际选择染色伓与最大值对应染色体的适应度 1000 3500 3000 国炉 1000 20U 3000 4000 7000 幕