《基于分解理论carp问题》由会员分享，可在线阅读，更多相关《基于分解理论carp问题（21页珍藏版）》请在金锄头文库上搜索。
1、基于分解理论的基因算法在多目标CARP问题上的应用 目录 1 Introduction 2 Background 3 D MAENS 4 Conclusion 1 Introduction 容量约束弧路径问题 CARP 是一种组合的最优化问题 它应用在城市垃圾收集和车队管理等问题上 很多人一直在尝试用启发式和元启发式算法解决CARP问题 其中包括进化算法 但是几乎所有算法都把它当做单目标问题 考虑到它的实际应用 CARP问题通常不止一个目标 文中作者提出了一种基于分解理论用扩展邻域搜索方法的基因算法 D MAENS 这种新的算法其实是把适用于单目标CARP问题的邻域搜索算法 MAENS 和多目
2、标进化优化结合起来产生的 这种新的算法在多目标组合优化问题中更具竞争力 2 Background 2 1CARP问题给定一个图的一些边和弧线 这些路线要求被车辆服务 也称作任务 一些容量有限的车辆停在起点 CARP问题就是为这些车辆寻找一条最优的路径 其中约束条件如下 1 每辆车都开始和结束于相同的一点 称作车库 2 每个路线只能被一辆车服务 3 每辆车服务的总任务不能超过它的车容量 到目前为止 由于CARP问题只是考虑使车队的总服务费用最少 所以它一直被当做单目标问题 然而规划和现实之间还是有很大的差距 所以Lacomme等又增加了一个目标函数 同时考虑其中一辆行驶最长路径的车的服务费用最小
3、 2 Background Lacomme等所提出来的NSGA II算法正是通过把适用于单目标CARP问题的一种方法和一种常用的多目标进化算法 MOEA 结合起来所形成的一种混合算法 Lacomme所提出的两个目标彼此之间互相冲突 因此没有单一的全局最优解存在 给定一个图G V E A 其中V E A分别代表点 边和弧的集合 对于每个边 E和每一个弧 A都有三个非负特性参数 交通费服务费 和需求 每条边和弧的需求都要求车辆以服务费为代价来服务 所有边的总任务集合为 弧的总任务 总的任务集为 m辆车位于起点容积为Q 2 Background 对一条边服务的话从两个方向中任意一个方向都可以 而对于
4、一个弧只能有一个服务方向 为了定义方便每一条边任务分配两个ID 比如说t1和t2 每一个弧任务分配一个ID 对于所有的任务t都有以下六个特点 尾顶点tv t 头顶点hv t 交通费 服务费 需求 相反IDinv t 对于每一条边任务来说 1 hv t1 tv t2 tv t1 hv t2 2 3 4 5 inv t1 t2 inv t2 t1 2 Background 对于每一个弧任务和它的任务IDt来说 1 hv t tv t 2 3 4 5 inv t 1因为所有的ID都是正的 inv t 1表示与t相反的ID不存在 除此之外定义起点的回路ID为0 1 tv 0 hv 0 2 3 inv
5、0 0 2 Background 例子中边的集合为ER v1 v5 v2 v6 v3 v7 v4 v8 起点为v0 图中没有弧线 IDs1 2 3 4分别对应着边 v1 v5 v2 v6 v3 v7 v4 v8 IDs5 6 7 8是它们的相反方向 虚线代表着中间路径 2 Background 基于以上符号表示 CARP问题可以表示为一系列路径的集合S R1 R2 Rm 每个路径有一系列ID构成Rk 为了保证每个路径都是从起点出发并回到同一点 使 这样对于路径Rk来说总的费用和需求如下 其中dist v1 v2 表示顶点v1到v2的直线最短距离 2 Background 所以CARP问题可以表
6、示如下 2 Background 2 2EMOIssuesInMO CARPMO CARP问题是一种组合问题 它需要在一系列约束条件下在离散并且有限的解空间中寻找Pareto最优可行解集 把局部搜索策略和进化算法结合起来形成的基因算法对于组合问题非常有效 但是这样有一个新的问题产生了 那就是怎样在邻域内识别另一个解来替换当前解 因此我们必须考虑下面四个问题 1 fitnessassignment2 diversitypreservation3 elitism4 identifyingthebestneighboringsolutionduiringlocalsearch 2 Backgroun
7、d 1 FitnessAssignmentinMO CARP目前在EMO中fitnessassignment存在三种策略 1 thecriterion based2 domination based3 decomposition based 先前对数值测试函数的研究表明criterion based会忽略Pareto前端的中间部分 而domination based不会 所以更适合MO CARP 另一方面decomposition based基于假设 每一个Pareto最优解都被当做一个标量优化子问题的最优解 然而在MO CARP问题中它不适用 实际上MO CARP中通常存在一些对于任何加权和
8、目标都不是最优的解 此外由于Pareto前端的离散性 一个Pareto最优解可能是多个被分解了的子问题的全局最优解 因此计算资源可能都浪费在寻找相同的Pareto最优解 这种策略也不是很好 2 Background 2 DiversityPreservationinMO CARP多样性表示方面有三种策略 nichingtechnique Cell basedmethods和crowdingdistancemethod 其中niching和cell based的性能主要是基于参数 sharingparameter和cellsize 而crowding的性能由一个小的方差表示 3 Elitismi
9、nMO CARP精英策略可以通过把非支配解集存储起来来实现 或者从父代和子代的合集中选择 根据这些存储起来的非支配解对搜索过程影响与否又可以分成两类 2 Background 4 EvaluatingSolutionsDuringLocalSearchinMO CARP寻找邻域中的最优解其实跟对每一个解分配适应度然后选择出来适应度最好的本质上一样 因此我们从适应度分配这个角度检验邻域中最优解这个问题 Criterion based和domination based都是把解集分成不同的前端 每个前端包含的解有相同的适应度 这样很难说明每个前端中哪个解最好 当采用decomposition bas
10、ed时 解决每一个子问题时通过局部搜索很容易找到最优解 除此之外把多个目标函数合成单一的目标函数也是常用的方法 但是性能通常由权重向量决定 通过以上讨论 现存MOEAs能对前三个问题很好解决 MOEA D是唯一一种能对MO CARP中最后一个问题很好解决的算法 正是由于它采用了独特的基于分解的模型提供一种很自然的方法来应用局部搜索 作者提出的D MAENS算法采用的基于分解的模型正是借用MOEA D 3 D MAENS D MAENS能很好的解决上面四个问题 为了使算法简单 它是所有可行算法中使用参数最少的一类 特别的是它采用了NSGA II中快速非支配排序来分配适应度 采用拥挤度来表示多样性
11、 采用MOEA D中现存的两种对elitism和thedecompositionstrategy策略来寻找邻域中最优解 D MAENS把MO CARP问题用一系列均匀分布的权重向量集分成多个标量子问题 种群规模 解的个数 等于子问题的个数 种群中每个个体对应一个单独的子问题 当处理某个子问题时 进化算法和局部搜索应用于当前子问题的邻域中的子问题的个体们 3 D MAENS 3 1分解理论模型目标函数F x f1 x fn x 权重向量子问题的目标函数表示为如果有N个权重向量 多目标CARP因此分解为N个单目标CARP 通过优化过程形成一个种群X x1 xn 在每一代种群都要按照下面步骤进化 首
12、先 每个子问题分配一个独特的解 第i个子问题的种群由T个其他子问题的独特解组合起来得到 这T个子问题的权重向量与第i个子问题的权重向量是临近的 就欧氏距离而言 如果临近那么第i个子问题的最优解与第j个子问题的最优解相近 3 D MAENS 其次 每个子问题再生成新的解 对于第i个子问题 先从种群中选出两个父代 然后采用交叉和局部搜索产生子代yi 对于每个子问题进行一次得到子代种群Y y1 yN 最后把X和Y中的解放在一起 采用快速非支配排序法和拥挤度法 最好的N个解保存在X中作为下一代 Step1 Initializationa 设置 一系列非支配解集作为输出 b 用N个均匀分布的权值向量把M
13、O CARP分成N个子问题 P1 P2 PN c 随机初始化种群X x1 xN d 计算每对权重向量之间的欧式距离 3 D MAENS Step2 Searchfornewsolutionsa 给每个子问题分配一个独特解b 对每个子问题都构造出对应的子种群c 设置i 1d 随机从Xi中选择两个解e 应用交叉算法和局部搜索产生yif 剔除中所有受F yi 支配的解 把F yi 插入如果中没有向量支配F yi g 设置i i 1 Ifi N 返回到Step2d h 用非支配排序和拥挤度方法整理中的解 选出N个最优的放到X中 Step3 Termination如果满足停机准则就停机否则返回Step2 3 D MAENS 3 2函数标准化f1 S 和f2 S 不能直接等于目标函数 i e 因为规模不同 直接应用会导致MAENS更偏向 因此要求标准化 3 D MAENS 下式中分别表示所有路径总费用的最小和最大值 分别表示最长路径的费用最小值和最大值 实际上我们不可能穷举出所有的可能解然后获得上述值 因此我们可以用近似值代替它们 在这里我们用到目前为止已经找到的所有可行解的总费用 最长路径 的最大值 最小值 来代替上面的 具体的首先设置其中a是一个相当大的数 然后在搜寻过程中逐渐更新 4 conclusion
