A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem

Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.

New Methods to Solve Fuzzy Shortest Path Problems

This paper discusses the problem of finding a shortest path from a fixed origin s to a specified node t in a network with arcs represented as typical triangular fuzzy numbers (TFN). Because of the characteristic of TFNs, the length of any path p from s to t , which equals the extended sum of all arcs belonging to p , is also TFN. Therefore, the fuzzy shortest path problem (FSPP) becomes to select the smallest among all those TFNs corresponding to different paths from s to t (specifically, the smallest TFN represents the shortest path). Based on Adamo's method for ranking fuzzy number, the pessimistic method and its extensions - optimistic method and λ combination method, are presented, and the FSPP is finally converted into the crisp shortest path problems.

A Novel Approach for Finding a Shortest Path in a Mixed Fuzzy Network

We present a novel approach for computing a shortest path in a mixed fuzzy network, network having various fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using -cuts. Then, we present a dynamic programming method for finding a shortest path in the network. For this, we apply a recently proposed distance function for comparison of fuzzy numbers. Four examples are worked out to illustrate the applicability of the proposed approach as compared to two other methods in the literature as well as demonstrate the novel feature offered by our algorithm to find a fuzzy shortest path in mixed fuzzy networks with various settings for the fuzzy arc lengths.

Extracting multi-objective multigraph features for the shortest path cost prediction:Statistics-based or learning-based?

Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.

Study of Multi-objective Fuzzy Optimization for Path Planning

During path planning, it is necessary to satisfy the requirements of multiple objectives. Multi-objective synthesis is based on the need of flight mission and subjectivity inclination of decision-maker. The decision-maker, however, has illegibility for under- standing the requirements of multiple objectives and the subjectivity inclination. It is important to develop a reasonable cost performance index for describing the illegibility of the decision-maker in multi-objective path planning. Based on Voronoi dia- gram method for the path planning, this paper studies the synthesis method of the multi-objective cost performance index. Ac- cording to the application of the cost performance index to the path planning based on Voronoi diagram method, this paper ana- lyzes the cost performance index which has been referred to at present. The analysis shows the insufficiency of the cost per- formance index at present, i.e., it is difficult to synthesize sub-objective flmctions because of the great disparity of the sub-objective fimctions. Thus, a new approach is developed to optimize the cost performance index with the multi-objective fuzzy optimization strategy, and an improved performance index is established, which could coordinate the weight conflict of the sub-objective functions. Finally, the experimental result shows the effectiveness of the proposed approach.

Floyd-Warshall Algorithm Based on Picture Fuzzy Information

The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.

基于图论的快速FCM图像分割算法

研究基于图论的最短路径算法与加权直方图方法,结合快速模糊聚类思想,提出一种改进的快速模糊C-均值(FCM)图像分割算法。利用最短路径算法对图像进行初始化处理,使处理后的灰度值准确反映邻域像素对原像素的影响。通过加权直方图改变灰度变化剧烈区域像元在图像分割中的影响程度,并自适应寻找初始聚类中心。实验结果表明,该算法能快速准确地分割图像,具有较强的抗噪性。

基于模糊聚类和最短路径的关键输电断面确定新方法

针对因支路故障或过载被切除之后的潮流转移关键输电断面如何正确快速确定问题,提出了基于模糊聚类和最短路径的潮流转移关键输电断面快速搜索新方法。该方法首先采用具有自适应选择最佳分类数的随机聚类方法,对所有线路功率构成进行分类,获得故障或过载支路的并行支路集构成初始输电断面,以避免由于人为给定分类数的不恰当所产生的多选及漏选问题;然后对初始输电断面中的每一支路,依次从故障或过载支路的一端开始搜索包括相应支路的到故障或过载支路另一端的最短路径,在该路径上所有与故障或过载支路潮流方向相同的支路,均为关键输电断面中的候选支路,以补充单纯由聚类方法确定的候选支路可能的漏选;候选支路再经简单的分布因子校核即可确定是否为关键输电断面中的支路。该方法实现了基于支路功率聚类关键输电断面选择方法和最短路径关键输电断面选择方法的有机融合和优势互补,提高了辨识精度。多个算例证实了文中方法的有效性。

基于模糊旅行时间的动态交通分配模型

提出了一种新的模糊动态交通分配(FDTA)模型,采用模糊集合理论描述动态旅行时间,应用模糊h截集的最短路径方法找出模糊最短路径集合,计算各条路径的隶属函数,并采用C-LOGIT模型实现网络加载,最后比较了FDTA模型和经典的随机动态交通分配(SDTA)模型.仿真结果显示:在正常交通状况下FDTA模型能够获得与SDTA模型非常接近的分配结果,并更加符合实际的交通状况;当有交通拥堵、事故、施工/管制等动态交通状况发生时,FDTA模型能够解决动态交通状况的建模问题;当交通网络结构复杂时,通过改变h值可以有效减少模糊最短路径的数量,提高计算效率.

基于多目标模糊决策的最佳路径分析

在进行最佳路径选取时,如何综合考虑多种模糊因素的影响和确定每个因素影响的大小是一个关键问题。该文建立了用于最佳路径分析的道路层次模型,给出了多目标模糊决策的数学模型,确定了各种影响因素的模糊隶属度函数,应用层次分析方法确定了各个影响因素的权重。在Dijkstra最短路径算法的基础上,提出了应用多目标模糊决策的方法来实现在多种模糊因素影响下的最佳路径选择,并通过实例分析和仿真实验验证了该方法的正确性。

基于模糊控制的认知无线电路由选择策略

一般无线网络的路由选择算法由于固定的信道分配不适合直接应用于认知无线电网络,需要针对认知无线电网络特有的信道动态性特点提出合适的路由选择策略。结合按需路由的基本流程,引入模糊控制技术,在充分考虑信道利用率和信道感知度这两种度量标准的影响下,提出一个可行的具有较小路由选择代价和最短路径双重优点的路由选择策略。仿真结果表明,基于模糊控制的路由选择策略较一般无线网络的按需路由协议具有更好的数据包投递率性能和吞吐量性能。

战术导弹发射车最优路径规划算法研究

介绍了战时情况下,能使战术导弹发射车顺利、安全、高效进入发射阵地的最优路径算法,并提出了两种新的算法:基于图论的多重运算法、首轮淘汰法,基于模糊理论的算法。运用这两种算法可以有效地解决导弹发射车道路寻优问题。

不确定信息下模糊网络最短路径关键边问题

由于道路中断时常发生,车辆在行驶的过程中并不了解这些不确定的道路中断信息,同时交通网络边的权重也存在不确定性,可以模糊数表达,因此有必要研究在不确定环境下的模糊交通网络最短路径关键边问题。基于OERI积分值的概念,定义了模糊网络的最短路径和不确定环境下的模糊最短路径关键边,给出了模糊网络最短路径的标号算法,同时给出了不确定信息环境下的模糊最短路径关键边的有效算法,最后进行了实例分析,表明了算法的有效性。

带均匀分布权值的最短路问题

最短路问题是网络设计中的一个基本问题,当前研究工作都基于边的权值是确定的这一假设。论文研究边的权值是一区间数时的最短路问题,利用优化理论,建立了目标函数系数在区间上均匀分布的模糊线性整数规划模型。通过引入正、负理想点概念,将模型转化为具有确定系数的单目标优化问题,给出了求解算法,并证明了算法的时间复杂性是多项式时间的。仿真实例说明了模型和算法的有效性。

多方案经营过程模型选择策略

经营过程建模的目的是为了经营过程的分析及重构。在经营过程中 ,由于存在约束、不确定性和不可精确估量等因素 ,其评价值常常是模糊的 ,评价目标不单一。因而存在一个对各种方案过程模型选择的问题 ,这个问题可以转化为多目标模糊最短路径问题。讨论了多目标模糊最短路径的算法与Pareto解空间问题 ,提出了基于模糊推理引擎选择多个Pareto解的策略。提出了经营过程设计框架 ,从而解决了企业内。

模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n2)。

模糊权值网络最短路问题的数学模型及算法

模糊权值网络的最短路问题是一类重要的网络优化问题.针对边权值为三角模糊数的模糊权值网络的最短路问题,基于模糊数的结构元加权序,将其模糊线性规划模型等价转化为经典的线性规划模型,并提出一种改进的权矩阵算法来求解该问题,算法证明和应用实例表明新算法的正确性和有效性.此外对于边权值为其他形式模糊数的模糊权值网络的最短路问题,文中模型和算法同样有效.

带有模糊约束最短路问题的数学模型及算法

针对带有模糊约束的最短路问题,在其模糊线性规划模型的基础上,利用容差法和罚函数法对该模型进行转化,得到了与原模型具有相同最优解与最优值的转化模型,并提出一种修正的萤火虫算法求解转化模型.数值算例结果表明,该模型与算法对求解带有模糊约束的最短路问题有效.

带模糊权值的最短路问题及启发式算法

研究网络链路权值是三角型模糊数时的最短路问题,建立模糊线性整数优化模型。通过引入目标函数的正、负理想点和隶属度概念,将模糊优化问题转化为确定系数的单目标优化问题,并给出求解算法。该算法通过调整反映决策者意图的目标函数权系数,得到决策者的满意解。对14个节点的实例网络进行仿真,经过6步就能得到令决策者满意的解,表明了模型和算法的有效性。