自适应交叉adaptive crossover.doc

自适应交叉adaptive crossover 自适应变异adaptive mutation 等位基因allele 算术交叉arithmetic crossover 人工生命artificial life 装箱问题Bin Packing 二进制编码基因binary genes 边界变异boundary mutation 基因块假设,积木块假设building block hypothesis 细胞cell 符号编码基因character genes 染色体chromosome 分类器系统classifier system,CS 粗粒度并行遗传算法coarse-grained PGA 个体编码coding 交叉crossover 交叉算子crossover operator 交叉概率crossover rate 排挤crowding 文化算法Cultural Algorithms 切断算子cut operator 循环交叉Cycle Crossover,CX 解码decode 分解型并行算法decomposition parallel approach 脱氧核糖核酸deoxyribonucleic acid,DNA 确定式采样选择deterministic sampling 双倍体diploid 显性基因dominance 动态参数编码dynamic parameter encoding,DPE 边重组交叉Edge Recombination Crossover,EX 枚举搜索算法enumerative search 遗传隐匿epistasis 评价函数evaluation function 进化evolution 进化策略Evolution Strategy,ES 进化算法Evolution Algorithms,EA 进化计算Evolution Computation 进化规划Evolution Programming,EP 期望值选择模型expected value model 细粒度并行遗传算法fine-grained PGA 适应度fitness 适应度函数fitness function 适应度景象fitness landscape 适应度尺度变换fitness scaling 浮点数编码基因floating-point genes 变异频率frequency of mutation 函数最优化function optimization 遗传算法欺骗问题GA deceptive problem 高斯变异 Gaussian mutation 基因gene 代沟generation gap 遗传算法genetic algorithms,GAs 遗传算子genetic operators 遗传编程genetic programming,GP 遗传学genetics 基因组genome 基因型genotype 全局搜索global searching 格雷码Gray codes 贪婪算法greedy algorithm 海明距离Hammig distance 单倍体haploid 遗传heredity 杂合子heterozygous 启发式算法heuristic method 爬山搜索算法hill-climbing search 纯合子homozygous 混合遗传算法hybrid genetic algorithm,HGA 超立方体hypercube 隐含并行性implicit parallelism 个体individual 初始群体initial population 倒位算子inverse operator 岛屿模型island model 背包问题Knapsack problem 致死基因lethal gene 线性尺度变换linear scaling 局部搜索local searching 基因座locus 机器学习machine learning 马尔可夫链Markov chain 巨并行遗传算法massively PGA 配对mating 配对规则mating rule 凌乱遗传算法messy GA,MGA 元遗传算法meta genetic algorithm Michigan 方法Michigan approach 移民migration 多指令流多数据流MIMD 最小欺骗问题minimal deceptive problem,MDP 多模态最优化multi-modal optimization 多目标最优化multi-object optimization 多模态函数multimodal function 多参数编码multiparameter encoding 多峰值函数multiple hump function 多点交叉multiple point crossover 变异mutation 变异算子mutation operator 变异概率mutation rate 邻居模型neighbourhood model 人工神经网络artificial neural network,ANN 小生境niche 非均匀变异non-uniform mutation NP-完全Nondeterministic Polynomial Completeness 目标函数object function 离线性能off-line performance 子代群体offspring o在线性能n-line performance 单点交叉one-point crossover 最优化optimization 顺序交叉Order Crossover,OX 描述过剩overspecification 并行遗传算法parallel genetic algorithm,PGA 并行性parallelism 部分映射交叉Partially Mapped Crossover,PMX 部分匹配交叉Partially Matched Crossover,PMX 罚函数penalty function 排列permutation 表现型phenotype Pitt 方法Pitt approach 植物授粉模型plant pollination model 多倍体polyploid 群体population 群体平均适应度population average fitness 群体多样性population diversity 群体大小population size 乘幂尺度变换power law scaling 早熟现象,早期收敛premature convergence 预选择preselection 概率算法probabilistic algorithms 概率算子probabilistic operator 交叉概率probability of crossover 倒位概率probability of inversion 变异概率probability of mutation 比例选择模型proportional model 随机算法random algorithms 随机搜索算法random searching,RS 随机游走random walks 排序选择模型rank-based model 浮点数编码基因read-coded genes 隐性基因recessive 无回放余数随机选择remainder stochastic sampling with replacement 重排序算子reordering operator 复制reproduction 核糖核酸ribonucleic acid,RNA 稳健性robustness 赌盘选择roulette wheel selection O截断尺度变换scaling with sigma truncation 模式schema 模式定义长度schema defining length 模式阶schema order 模式定理Scheme Theorem 选择selection 选择算子selection operator 共享函数sharing function 单指令流多数据流SIMD 基本遗传算法simple genetic algorithm,SGA 基本变异simple mutation 模拟退火算法simulated annealing,SA 单峰值函数single hump function 拼接算子splice operator 标准型并行方法standard parallel approach 踏脚石模型stepping-stone model 无回放随机选择stochastic sampling with replacement 随机联赛选择模型stochastic tournament model 终止条件termination conditions 测试函数test function 旅行商问题Traveling Salesman Problem,TSP 双点交叉two-point crossover 描述不足underspecification 均匀交叉uniform crossover 均匀变异uniform mutation X 染色体X chromosome Y 染色体Y chromosome基于混合遗传算法的多约束集装箱装载问题研究胡 瑞1，丁香乾2，张 峰2 时间:2008年06月24日字 体: 大 中 小关键词:遗传算法集装箱装载启发式算法定序第一个摘要： 在考虑集装箱装载货物底置等级、侧放方式、堆码层数等一些实际应用的约束条件下，根据同类型货物一次性装载的思想，提出了一种新的基于空间划分的启发式算法，并以此为基础构造了一种混合遗传算法。关键词： 集装箱装载 启发式 混合遗传算法 多约束在运输中如何进行货物的有效装载，即怎样将一批矩形货物布入一个或多个集装箱中，使集装箱的空间利用率达到最高，这属于NP完全问题。集装箱装载问题根据集装箱数量的有限和无限划分成两类：一是集装箱数量无限，盒子必须全部装完，要使所用的集装箱数量最少；二是集装箱数量有限，盒子数量超过了集装箱的装载能力，要求被装载盒子的总体积达到最大，使空间利用率最高。在实际中第二类问题更为常见，所以在此只分析第二类问题。目前常用的布局优化方法多为不带约束的简化布局问题，而现实生活中存在着大量的约束条件。针对具有货物底置位置、允许侧放方式、最大堆码层数等多约束条件下的集装箱装载问题和目前集装箱容积有效利用率普遍较低的情况，本文将这些约束考虑到启发式规则中，根据装载中单种货物数量一般较多的实际情况，提出了一种新的基于空间划分的启发式算法，并将其与遗传算法结合，进一步提出了混合遗传算法求解多约束装箱问题。该算法已用于企业的实际装箱中，结果表明，本文提出的方法可行且有效。1 多约束集装箱装载的启发式策略实际装载中单种货物数量一般较多，采用现有针对单个物品的基于三维空间的启发式算法存在装载效率和空间利用率低的问题。因此，本文采用同类型货物一次性装载的思想，提出了一种新的基于空间划分的启发式策略。该策略根据待布局空间块中货物装载方式的不同将剩余空间最多划分为五种空间块。实际应用中，对算法中的约束条件处理方法是引入不同变量分别表示货物的侧放方式、货物的堆码层数、底置等级等属性。1.1 基于空间划分的启发式算法流程算法流程的步骤如下：(1)初始化空间块序列为集装箱箱体。(2)依次按底置等级递增、体积递减对货物类型排序。(3)从货物类型序列中按顺序取某类型货物，从空间块列表中取第一个可用空间块。(4)将所取类型的货物一次性装载到所取空间块中。根据货物可取侧放方式、最大堆码层数的不同，计算空间块的最大装载数量(本文称为标准装车)，同时产生标准装车的摆放方式。当货物数量小于标准装车时(称为非标准装车)，根据货物数量、允许侧放方式、最大堆码层数产生非标准装车的摆放方式。(5)分割空间块，将其添加到空间块序列，按体积对空间块重新排序。(6)如(4)为标准装车，求所取类型货物的剩余数量，从空间块列表中取第一个可用空间块，转(4)；否则转(3)。1.2 定序规则定序规则用来确定物体布入的先后顺序，对最终布局结果的优劣有重要影响。由于货物底置等级越低，要求放置的位置越低，所以采用依次按底置等级递增、体积递减的定序规则对货物类型排序。1.3 定位规则1.3.1 标准装车装车规则：对箱体的某种侧放方式，X-Y平面的摆放次序为先横后纵。如图1所示，Nxhorz，Nyhorz，Nyvert，Nxbert分别表示整的横箱、纵箱在X轴和Y轴的数目；Nrem_x，Nrem_y表示零头在X轴和Y轴方向的数目；wid表示待布局立方体的宽。确定Nyhorz和Nyvert满足：minwid-Nyhorzboxwid-Nyvertboxlen(1)零头应置于最外侧。零头的摆放应考虑空间完整程度, 再决定横放还是纵放。如果程度一致，则横放。在Z轴方向，根据货物可取侧放方式、最大堆码层数遍历得到最优的箱子层数lay_num和各层的侧放方式。最优判定准则是可装的箱子数目最多。1.3.2 非标准装车装车规则：当装载不满时：(1)应避免中间突出的情况，以免使空间过于破碎。如有中间突出的情况，应把突出的摆放换到边上，这样可以利用最外边的一段空间。(2)如有小于最小尺寸的边，应尽量把此类情况转换为其他方式。(3)在宽度方向上求最优，是为了维护空间完整度。非标准装车有以下几种情况，如图2所示。设待布局箱子数目为num_all，如空间块的标准装车方式所确定的各层侧放方式不同，则首先根据标准装车摆放各层，对不满的一层，令lay_num=1，刷新num_all，转(1)。如标准装车方式所确定的各层侧放方式相同，则：(1)由标准装车确定的各参数计算箱体在所布空间块的理论长度La，其中：La=Va/(Nyhorzboxwid+Nyvertboxlen)(2)Va=boxwidboxlennum_all/lay_num(3)(2)计算纵放排数：Nxvert1=La/boxwid(4)横放排数：Nxhorz1=La/boxlen(5)(3)计算余箱数num_r=num_all-Nxvert1Nyvert-Nxhorz1Nyhorz(6)(4)余箱放置的种类有以下几种：V0表示竖放；H0表示横放；V1表示竖放1列或几列，其余按横放；H1表示横放1列或几列，其余按竖放。这4种方式对应的共同约束为：所有情况的最长行不能超过长度界限；优先级应考虑空间的完整性和较短的总长度。具体流程如图3所示。图3中各公式如下：Lv=trunc(La/boxwid)Lh=trunc(La/boxlen)Nh=num_r/NyhorzNh1=(Lv+boxwid-Lh)/boxlenNv=num_r/NyvertNv1=(Lh+boxlen-Lv)/boxwid同1.4 空间划分空间块的划分如图4(a)、(b)所示。根据零头所在位置的不同，空间块可最多分割为A-B-C1-D-E-F或A-B-C2-D-E-F五种，各空间块可视化时的遮挡顺序为D-E-C-F-B-A。2 约束集装箱装载问题的混合遗传算法采用以上基于空间划分的启发式算法的效率较高，但仍然难以保证获得全局最优解或次优解。遗传算法4作为一种模拟自然进化过程的随机性全局优化概率搜索算法，在求解优化问题中显示了优越的性能。因此本文将启发式算法与遗传算法结合，进一步提出了求解多约束装箱问题的混合遗传算法。2.1 染色体的编码方法编码是GA应用成功与否的关键。本文采用Grefen-stette等针对TSP提出的基于顺序表示的遗传基因编码方式4，把待装物品的类型编号按排放顺序排的串作为一个解的编码，即p=p1，p2pn。其中n表示装物品的类型；p1为整数，其值代表物品类型的编号。2.2 目标函数和适应度在集装箱装载过程中不仅要求容器空间利用率达到最高，同时要考虑多种约束。由于在启发式装载过程中引入了不同变量(暂不考虑重心约束)，因此适应度函数为：其中BVi表示布入的第i个箱子体积，CV为集装箱体积，m为布入箱子总个数。2.3 选择和交叉操作采用类似于轮盘赌选择法和跨世代精英选择策略。对于本文这种类似于TSP问题的以符号编码的基因串p，采用Goldberg等针对TSP提出的部分匹配交叉操作(Partially Matched Crossover)5策略。这种交叉操作的主要思想是：随机选取二个交叉点，以便确定一个匹配段，根据二个父个体中二个交叉点之间的中间段给出的映射关系生成二个子个体。2.4 变异操作变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。对于变异操作，采用逆位遗传算子，在父个体的底置等级相同的染色体段内随机