遗传算法,最优化问题P-400-NetworkDesign

典型问题网络设计问题网络设计问题(NetworkDesignProblem)东北大学系统工程研究所2010.09网络设计问题网络设计问题属于一类重要的工程优化问题任何具有网状拓扑结构的问题均可归结为网任何具有网状拓扑结构的问题，均可归结为网络设计问题，涵盖的内容非常广泛。很多实际问题可以构造为网络设计问题。近年来些从事遗传算法研究的学者对网近年来，一些从事遗传算法研究的学者，对网络设计的优化问题倾注了极大的关注。络设计的优化问题倾注了极大的关注2典型优化问题的模型与算法-R03各类网络设计问题基本网络设计问题最短路径问题(ShortestPathProblem(SPP))最大流问题(i())最大流问题(MaximumFlow(MXF)Problem)最小费用流(MinimumCostFlow(MCF)Problem)双准则网络设计问题(BicriteriaNetworkDesignProblem(BNP))双准则网络设计问题(cteaNetwoesgobe(N))多准则网络设计问题(Multi-criteriaNetworkDesignProblem)最小生成树问题约束最小生成树问题约束最小生成树问题二次最小生成树问题度约束最小生成树问题度约束最小生成树问题双目标最小生成树问题多目标最小生成树问题(MulticriteriaMinimumSpanningTree(MST))(mc-MST))叶约束最小生成树问题(Leaf-constrainedMinimumSpanningTree))3典型优化问题的模型与算法-R03各类网络设计问题物流网络设计问题(LogisticNetworkDesign)基本运输问题(TransportationProblem)扩运输问题扩展运输问题(ExtensionofTransportationProblem)双阶段运输问题(Two-stageTransportationProblem)多阶段物流链网络(MultistageLogisticChainNetwork)多阶段物流链网络(Multi-stageLogisticChainNetwork)供应链网络设计(SupplyChainNetworkDesign)多仓储VRP问题(Multi-depotVRP)多仓储问题(p)通信网络和局域网设计问题有适应能力的网络路由(AdaptiveNetworkRouting)集中式络集中式网络设计(CentralizedNetworkDesign)计算机网络扩展(ComputerNetworkExpansionProblem)主干网设计(BackboneNetworkDesign)主干网设计(BackboneNetworkDesign)双准则局域网拓扑设计(BicriteriaLANTopologicalDesign)4典型优化问题的模型与算法-R03典型问题最短路径问题最短路径问题(ShortestPathProblem)5典型优化问题的模型与算法-R03最短路径问题最短路径问题也许是所有网络设计中最简单的问题。问题描述：问题描述：假设每条边(i,j)∈A有一个相关的费用（或距离）cij，目标就是要寻找一条从指定的起点s到指定的终点t目标就是要寻找条从指定的起点s到指定的终点t的一条路径，使总费用（或距离）最小。248361816203224248361816203224248361816203224157102713121611122015st11157102713121611122015st157102713121611122015st11ijcij3692712231238133692712231238133692712231238136典型优化问题的模型与算法-R03网络模型网络模型可描述为：有向图：G=(V,A)，其中V是节点的集合，A是连接有向图：G(V,A)，其中V是节点的集合，A是连接的集合cij是和每个连接(ij)相关的费用cij是和每个连接(i,j)相关的费用起点:节点1终点:节点m终点:节点m指示变量:otherwisepaththeinincludedislinkif0,)(1jixij,,24836181611203224st24836181611203224st24836181611203224stcij1571027131211121513st111571027131211121513st1571027131211121513st11ijij3692338133692338133692338137典型优化问题的模型与算法-R03模型描述用数学公式可描述为：xczmmmin147st25)1(111ixczijijij　min由点i出去的边之和14367)(1)1,,3,2(0)(11mimixxmkkimjij　　s.t.where),,2,1,(1or0)(1mjixmiij　　　　进入点i的边之和where,xij:从点i到点j的连接；cij:和每个连接(i,j)相关的费用；约束条件的含义是：节点1只有一条出去的边；由节点i出去的边和进入节点i的边是相等的由节点i出去的边和进入节点i的边是相等的；进入节点m的边只有一条。8典型优化问题的模型与算法-R03特点一类特殊的0-1线性规划问题NP难题NP-难题9典型优化问题的模型与算法-R03应用与交通路网有关的求“距离”最短的问题飞机最优航线确定问题大型船只的航线确定问题2584060大型船只的航线确定问题GPS导航移动机器人路径规划IP路由选择问题60258st60302030605030503040IP路由选择问题管道铺设大型停车场的车位诱导医院向导系统136911st6060302030505050304030医院向导系统高速公路收费系统旅游线路设计问题47104040中文自然语言处理中的“中文分词”问题多阶段决策问题设备更新问题原料选用投资预算…典型优化问题的模型与算法-R0310中文分词问题对中文字符串通过原子切分、找出原子之间所有可能的组词方案后形成一个特殊的有向图例如：对汉字串“他说的确实在理”进行有向图构造123456他07说的确实在理的确实在对汉字串“教学科研”进行有向图构造确实在理对汉字串教学科研进行有向图构造01234教学科研教学科研求最短路实上就找句话中最少的分01234学科求最短路实际上就是找一句话中最少的分词。典型优化问题的模型与算法-R0311设备更新问题年初购买新设备及使用不同年限的设备维修费用：年限第1年第2年第3年第4年第5年购买单价（万元）1111121313使用年限0~11~22~33~44~5维修费用（万元）56811185916184116171822123456164118161718图中假设：点i，表示第i年年初，同时也表示第i-1年的年末。例如…由ij的边表示由第i年年初购买设备并使用到第j年年初例如41由i~j的边，表示由第i年年初购买设备，并使用到第j年年初。例如..边上的权重表示设备购买和维修费用之和，不同的边费用不同。例如..典型优化问题的模型与算法-R0312一般的求解方法穷举法动态规划法分阶段逐步求出各节点到终点的最短路。E.W.Dijkstra最短路算法从起点逐步求出到每一个节点的最短路从起点逐步求出到每个节点的最短路。Floyd-WarshallAlgorithmFloyd-Warshallalgorithmisanalgorithmtosolvetheallpairsyggpshortestpathprobleminaweighted,directedgraphbymultiplyinganadjacency-matrixrepresentationofthegraphmultipletimesmultipletimes.Bellman-Ford算法也称为反向搜索算法或距离向量算法，它是从目的点出发反向向索算离向算从点向计算的。它是找到一个给定的源顶点出发的最短路径，限制条件是径上最多只有一条链路；然后再找到一些最短路径，限制条件是路径上最多只有2条链路其余类似条件是路径上最多只有2条链路，其余类似。14典型优化问题的模型与算法-R03GA求解如何对网络中的路径进行编码，是设计GA的关键难点在于：由起点到终点的一个路径包含可变个节点边的随机序列通常不能对应一条路径24836181620322424836181620322424836181620322415710361316112015st1115710361316112015st15710361316112015st11369271223123813369271223123813369271223123813路径1：1→2→4→8→10目标函数：z=110路径2：1→2→4→7→8→10目标函数：z=109路径2：1→2→4→7→8→10目标函数：z=109路径3：1→3→5→4→7→8→10目标函数：z=11015典型优化问题的模型与算法-R03GA求解编码要解决的关键问题：染色体的合法性染色体是否描述了给定问题的一个解染色体是否描述了给定问题的一个解通常采用修复技术将非法染色体转换为合法染色体染色体的可行性由染色体解码得到的解是否在问题的可行域内由染色体解码得到的解是否在问题的可行域内有四种处理约束的技术映射的唯一性染色体到解的映射通常存在三种形式1111染色体到解的映射通常存在三种形式：1:1,m:1,1:n1:1映射是最好的1:n映射是最不期望的1映射会减少种群的多样性m:1映射会减少种群的多样性编码方法：基于优先级的编码可变长编码定长编码定长编码16典型优化问题的模型与算法-R03GA求解基于优先级的编码这种编码方式最早由Cheng&Gen,1997年提出，用于求解资受项度问题解资源受限项目调度问题。并非直接对解编码（不存在直接的映射关系），而是采用一种间接的方法通过对路径的导向性信息进行编码构一种间接的方法：通过对路径的导向性信息进行编码，构建染色体中的路径而不是路径本身。在基于优先级的编码方法中：在基于优先级的编码方法中基因的位置代表节点编号，有多少节点就有多少个基因；基因的值代表节点的优先权，不同节点的优先权各不相同。染色体对应的路径由一系列始于节点1，终于节点m的相继节点构染色体对应的路径由系列始于节点1，终于节点m的相继节点构成；解码时，从节点1开始依次选择路径，在可选的节点中只有优先权最高的节点加入路径中最高的节点加入路径中。nodeID:1234567priority:216453717典型优化问题的模型与算法-R03GA求解基于优先级的编码实例实例假设要寻找一条节点1到7的路径。编码如图所示。首先，寻找与节点1相邻的节点。节点2，3和4在此都是首先，寻找与节点1相邻的节点。节点2，3和4在此都是适合的，但节点3具有更高的优先权，因此，被纳入路径。然后，寻找与节点3相邻的节点(4,6)，并将具有最高优先权(,)的节点纳入路径(节点4)。重复这些步骤，直至得到一条完整的路径(1,3,4,7)。25nodeID:1234567147st2511priority:2164537361437path:18典型优化问题的模型与算法-R03GA求解基于优先级的编码优点：优点任何顺序的编码对应着一条路径(合法性)，因此，绝大多数已有的遗传操作可以轻易地在这种编码上运用。同样，任何一条路径拥有相应的编码(完备性)，因此，遗传搜索能到达解空间中的任意一点。缺点缺点：编码与路径之间的映射是m:1的，这意味着不同的染色体可能对应着同一