检索结果-内蒙古大学图书馆

12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)

作者： Hu, Xiao-Bing Zhang, Ming-Kong Liao, Jian-Qin Zhang, Hai-Lin Beijing Normal Univ Acad Disaster Reduct & Emergence Management Beijing Peoples R China MiidShare Technol Ltd Chengdu Peoples R China Minist Transport Res Inst Highway Beijing Peoples R China

ISBN: (纸本)9781509040933

This paper is concerned with finding the k shortest routes or paths in a network where each node has some specific time windows only within which is the node accessible. Because of such time windows at nodes, classical methods for the k shortest paths problem (k-SPP) is not applicable to the k shortest paths problem in a time-window network (k-SPPTW). Taking inspiration from the natural ripple-spreading phenomenon, we propose a novel ripple-spreading algorithm (RSA) for the k-SPPTW. By conducting a purpose-designed ripple relay race in a time-window network, the reported RSA can resolve not only one-to-one k-SPPTW, but also one-to-all k-SPPTW, where all the k shortest paths from a given source node to every other node in the network need to be found. The computational complexity of RSA is just O(kxN(ATU)xN(L)), where N-L is the number of links in the network, and N-ATU is the average simulated time units for a ripple to travel through a link. Experimental results demonstrate the effectiveness and efficiency of the proposed RSA for the k-SPPTW.

关键词： k Shortest Paths Problem ripple-spreading algorithm Time-Window Network

来源：评论

学校读者我要写书评

暂无评论

A ripple-spreading algorithm for Network Performance Assessment

A Ripple-Spreading Algorithm for Network Performance Assessm...

引用

IEEE Symposium Series on Computational Intelligence

作者： Xiao-Bing Hu Ming-Kong Zhang Jian-Qin Liao Academy of Disaster Reduction and Emergence Management Beijing Normal University China Chengdu MiidShare Technology Ltd China

ISBN: (纸本)9781509042418

To assess the performance of a network system against disturbances, existing methods are usually concerned with two different extreme situations: (i) how likely the system will degrade into some separated sub-graphs because of disturbances;(ii) how likely the I~(st)best paths will be cut off by disturbances. However, a more general situation, i.e., how likely those paths whose lengths are within a given range will be affected by disturbances, is barely discussed Basically, to address this general situation, all (not just a proportion) of those paths whose lengths are within the given range must be found out between all pairs of origin and destination (OD) of interest. Unfortunately, no effective method has ever been reported to accomplish this task, although there are many methods capable of calculating all the 1~(st)best paths between all OD pair of interest. This paper, for the first time, attempts to address the above general situation of network performance assessment. To this end, a novel ripple-spreading algorithm (RSA) is proposed to carry out a ripple relay race on the network, in order to identify all of those paths whose lengths are within the given range. Surprisingly, the proposed RSA can find all such paths between all OD pairs of interest by just a single run of ripple relay race. This work makes progress towards the general performance assessment of a network system against disturbances.

关键词： ripple-spreading algorithm network system performance assessment path optimization disturbances

来源：评论

学校读者我要写书评

暂无评论

Finding the k shortest paths by ripple-spreading algorithms

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2020年 87卷 103229-000页

作者： Hu, Xiao-Bing Zhang, Chi Zhang, Gong-Peng Zhang, Ming-Kong Li, Hang Leeson, Mark S. Liao, Jian-Qin Civil Aviat Univ China Coll Elect Informat & Automat CAUC ENAC Joint Res Ctr Appl Math Air Traff Manag Tianjin Key Lab Adv Signal Proc Tianjin 300300 Peoples R China Beijing Union Univ Collaborat Innovat Ctr eTourism Beijing 100101 Peoples R China Beijing Normal Univ Acad Disaster Reduct & Emergence Management Fac Geog Sci Beijing 100875 Peoples R China Civil Aviat Univ China Coll Elect Informat & Automat CAUC ENAC Joint Res Ctr Appl Math Air Traff Manag Tianjin 300300 Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL W Midlands England Chengdu MiidShare Technol Ltd Chengdu 610000 Peoples R China

The k shortest paths problem (k-SPP) is fundamentally important to both theoretical and application researches on computational intelligence. Inspired by the natural ripple-spreading phenomenon that occurs on a water surface, this paper proposes a novel ripple-spreading algorithm (RSA). RSA differs from many existing methods which need to reconstruct route networks or to sweep the network for k times, and it can identify the k shortest paths by a single run of ripple relay race in the original route network. Besides the k-SPP in normal route networks, the RSA can also be extended, without losing optimality and effectiveness, to some time-window networks (where various waiting behaviors at nodes are introduced) and dynamical networks (where the network topology and link costs may change over time due to factors such as moving obstacles and spreading disasters). For one-to-all k-SPP, which aims to find all the k shortest paths from a given source to every other node in a network (no matter with or without time windows at nodes, and no matter whether the network topology and link costs can change over time or not), the RSA can still find out all required solutions using only a single run, while the computational complexity is exactly the same as that for the one-to-one k-SPP, i.e., O(k x N-L x N-ATU), where N-L is the number of links in the network, and N-ATU is the average simulated time units for a ripple to travel through a link. The comparative experimental results illustrate the effectiveness and efficiency of the proposed RSA.

关键词： k shortest paths problem ripple-spreading algorithm Time window Time-varying route network

来源：评论

学校读者我要写书评

暂无评论

A distributed design of ripple-spreading algorithms for path optimisation problems

引用

INTERNATIONAL JOURNAL OF COMPUTER APPLICATIONS IN TECHNOLOGY 2021年第3期65卷 209-221页

作者： Wang, Tian-Qi Zhang, Gong-Peng Hu, Xiao-Bing Yang, Hongji Civil Aviat Univ China CAUC ENAC Joint Res Ctr Appl Math Air Traff Manag Tianjin Peoples R China Civil Aviat Univ China Sino European Inst Aviat Engn Tianjin Peoples R China Beijing Union Univ Collaborat Innovat Ctr eTourism Beijing Peoples R China Univ Warwick Sch Engn Coventry W Midlands England Univ Leicester Sch Informat Leicester Leics England

As a relatively new nature-inspired algorithm, ripple-spreading algorithm (RSA) exhibits some advantageous features when resolving various Path Optimisation Problems (POPs) against both traditional deterministic algorithms and evolutionary approaches, e.g., RSA is a multi-agent, bottom-up, simulation model full of flexibility for modifications (like many evolutionary approaches), and it can guarantee optimality (like many deterministic algorithms). Towards real applications to large-scale POPs, RSA still needs to improve its computational efficiency. We used it to take some measures in order to achieve a trade-off between computational efficiency and optimality. This paper, for the first time without sacrificing optimality, proposes a way to significantly improve the computational efficiency of RSA. This is done by taking advantage of the multi-agent nature of RSA, i.e., a multi-agent model is naturally friendly to distributed design and parallel computing. Therefore, this paper reports a distributed design of RSA for POPs. Preliminary experimental results clearly demonstrate the effectiveness and efficiency of the new design of RSA.

关键词： ripple-spreading algorithm distributed design parallel computation paths optimisation computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Deterministic Agent-Based Path Optimization by Mimicking the spreading of ripples

引用

EVOLUTIONARY COMPUTATION 2016年第2期24卷 319-346页

作者： Hu, Xiao-Bing Wang, Ming Leeson, Mark S. Di Paolo, Ezequiel A. Liu, Hao Beijing Normal Univ State Key Lab Earth Surface Proc & Resource Ecol Beijing 100875 Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL W Midlands England Univ Basque Country Ikerbasque Basque Sci Fdn Ctr Res Life Mind & Soc San Sebastian 20080 Spain Beijing Metropolitan Traff Informat Ctr Beijing 100161 Peoples R China

Inspirations from nature have contributed fundamentally to the development of evolutionary computation. Learning from the natural ripple-spreading phenomenon, this article proposes a novel ripple-spreading algorithm (RSA) for the path optimization problem (POP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source is the first to be reached. This very simple principle forms the foundation of the proposed RSA. In contrast to most deterministic top-down centralized path optimization methods, such as Dijkstra's algorithm, the RSA is a bottom-up decentralized agent-based simulation model. Moreover, it is distinguished from other agent-based algorithms, such as genetic algorithms and ant colony optimization, by being a deterministic method that can always guarantee the global optimal solution with very good scalability. Here, the RSA is specifically applied to four different POPs. The comparative simulation results illustrate the advantages of the RSA in terms of effectiveness and efficiency. Thanks to the agent-based and deterministic features, the RSA opens new opportunities to attack some problems, such as calculating the exact complete Pareto front in multiobjective optimization and determining the kth shortest project time in project management, which are very difficult, if not impossible, for existing methods to resolve. The ripple-spreading optimization principle and the new distinguishing features and capacities of the RSA enrich the theoretical foundations of evolutionary computation.

关键词： Agent-based model deterministic algorithms ripple-spreading algorithm path optimization

来源：评论

学校读者我要写书评

暂无评论

A New Method for Resource Allocation Optimization in Disaster Reduction and Risk Governance

引用

International Journal of Disaster Risk Science 2016年第2期7卷 138-150页

作者： Xiao-Bing Hu Ming Wang Tao Ye Peijun Shi State Key Laboratory of Earth Surface Processes and Resource Ecology Beijing Normal University Academy of Disaster Reduction and Emergence Management Beijing Normal University

How to allocate and use resources play a crucial role in disaster reduction and risk governance(DRRG).The challenge comes largely from two aspects: the resources available for allocation are usually limited in quantity; and the multiple stakeholders involved in DRRG often have conflicting interests in the allocation of these limited resources. Therefore resource allocation in DRRG can be formulated as a constrained multiobjective optimization problem(MOOP). The Pareto front is a key concept in resolving a MOOP, and it is associated with the complete set of optimal solutions. However, most existing methods for solving a MOOPs only calculate a part or an approximation of the Pareto front, and thus can hardly provide the most effective or accurate support to decisionmakers in DRRG. This article introduces a new method whose goal is to find the complete Pareto front that resolves the resource allocation optimization problem in *** theoretical conditions needed to guarantee finding a complete Pareto front are given and a practicable, ripplespreading algorithm is developed to calculate the complete Pareto front. A resource allocation problem of risk governance in agriculture is then used as a case study to test the applicability and reliability of the proposed method. The results demonstrate the advantages of the proposed method in terms of both solution quality and computational efficiency when compared with traditional methods.

关键词： Disaster reduction Multiobjective optimization Pareto front Resource allocation Risk governance ripple-spreading algorithm

来源：评论

学校读者我要写书评

暂无评论

A deterministic and nature-inspired algorithm for the fuzzy multi-objective path optimization problem

引用

COMPLEX & INTELLIGENT SYSTEMS 2023年第1期9卷 753-765页

作者： Ma, Yi-Ming Hu, Xiao-Bing Zhou, Hang Civil Aviat Univ China Sino European Inst Aviat Engn Tianjin 300300 Peoples R China Civil Aviat Univ China Coll Safety Sci & Engn Lab Complex Syst Safety & Intelligent Decis Tianjin 300300 Peoples R China Beijing Union Univ Collaborat Innovat Ctr eTourism Beijing 100101 Peoples R China Univ Warwick Sch Engn Coventry CV4 7AL W Midlands England

Increasing evaluation indexes have been involved in the network modeling, and some parameters cannot be described precisely. Fuzzy set theory becomes a promising mathematical method to characterize such uncertain parameters. This study investigates the fuzzy multi-objective path optimization problem (FMOPOP), in which each arc has multiple crisp and fuzzy weights simultaneously. Fuzzy weights are characterized by triangular fuzzy numbers or trapezoidal fuzzy numbers. We adopt two fuzzy number ranking methods based on their fuzzy graded mean values and distances from the fuzzy minimum number. Motivated by the ripple spreading patterns on the natural water surface, we propose a novel ripple-spreading algorithm (RSA) to solve the FMOPOP. Theoretical analyses prove that the RSA can find all Pareto optimal paths from the source node to all other nodes within a single run. Numerical examples and comparative experiments demonstrate the efficiency and robustness of the newly proposed RSA. Moreover, in the first numerical example, the processes of the RSA are illustrated using metaphor-based language and ripple spreading phenomena to be more comprehensible. To the best of our knowledge, the RSA is the first algorithm for the FMOPOP that can adopt various fuzzy numbers and ranking methods while maintaining optimality.

关键词： Fuzzy graph Multi-objective optimization Path optimization Pareto optimal path ripple-spreading algorithm

来源：评论

学校读者我要写书评

暂无评论

A New Path Optimization Method in Dynamic Adverse Weathers 12

A New Path Optimization Method in Dynamic Adverse Weathers

引用

12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)

作者： Zhang, Ming-Kong Hu, Xiao-Bing Liao, Jian-Qin Beijing Normal Univ Acad Disaster Reduct & Emergence Management Beijing Peoples R China MiidShare Technol Ltd Chengdu Peoples R China

ISBN: (纸本)9781509040933

Travelling in adverse weathers is a dynamical path optimization problem (DPO), as weather conditions usually keep changing during the traveling period. A common practice of DPO is to conduct real-time online path optimization based on the current weather conditions. However, this can hardly lead to optimal actual travelling trajectory under a given weather dynamics, because the online optimization based on the current weather conditions is rarely optimal for future weather conditions. This paper is concerned with, given a weather dynamics, how to achieve optimal actual travelling trajectory by just a single offline optimization. To this end, the concept of co-evolutionary path optimization (CEPO) is introduced, where weather conditions are not static, but keep changing during a single run of offline optimization. Existing DPO methods can hardly address CEPO, because in a single run of online optimization, existing DPO methods treat weather conditions as static, i.e., existing DPO methods do not consider/allow weather conditions to change in a single run of online optimization. To address the CEPO in dynamical adverse weathers, this paper proposed a ripple-spreading algorithm (RSA), which can achieve optimal actual travelling trajectory by a single offline calculation. The reported CEPO and RSA are then tested on a typhoon scenario in Hainan Province of China, and the advantages against traditional DPO are clearly demonstrated.

关键词： Co-Evolutionary Path Optimization Adverse Weathers ripple-spreading algorithm Typhoon

来源：评论

学校读者我要写书评

暂无评论

An Effective Method to Find the k Shortest Paths in a Generalized Time-Window Network

An Effective Method to Find the <i>k</i> Shortest Paths in a...

引用

IEEE Congress on Evolutionary Computation (CEC) held as part of IEEE World Congress on Computational Intelligence (IEEE WCCI)

作者： Hu, Xiao-Bing Zhang, Ming-Kong Liao, Jian-Qin Zhang, Hai-Lin Beijing Normal Univ Acad Disaster Reduct & Emergence Management Beijing Peoples R China Chengdu MiidShare Technol Ltd Chengdu Peoples R China Res Inst Highway Minist Transport Beijing Peoples R China

ISBN: (纸本)9781509006229

It is a challenging task to find the k shortest paths in a time-window network, where a node may have some specific time windows only within which is the node accessible. Existing research assumes that a traveller can pass through an accessible node immediately or wait to pass at start times of future time windows at the node. This paper targets at a more general case where a traveller, once arriving at a node, may choose to pass through the node at any discrete time in the time windows of the node. In such a generalized time-window network, the degree of complexity increases significantly, as the size of solution space soars up exponentially. By mimicking the natural ripple-spreading phenomenon on a liquid surface, we propose an effective ripple-spreading algorithm (RSA) for the k shortest paths problem in a generalized time-window network (k-SPPGTW). Besides one-to-one k-SPPGTW, the RSA is also extended to one-to-all k-SPPGTW, where all the k shortest paths from a given source to every other node in the network need to be found. The new method has a theoretical guarantee of optimality. The computational complexity of the reported RSA is just O(kxN(ATU)xN(L)), where N-L is the number of links in the network, and N-ATU is the average simulated time units for a ripple to travel through a link. The effectiveness and efficiency of the reported RSA for the k-SPPGTW are demonstrated by some preliminary experimental results.

关键词： k Shortest Paths Problem Generalized Time-Window Network ripple-spreading algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient Nature-Inspired Method to Solve the Shortest Path Tour Problem

An Efficient Nature-Inspired Method to Solve the Shortest Pa...

引用

IEEE Symposium Series on Computational Intelligence (IEEE SSCI)

作者： Ma, Yi-Ming Zhou, Hang Hu, Xiao-Bing Civil Aviat Univ China Sino European Inst Aviat Engn Tianjin Peoples R China Civil Aviat Univ China Coll Safety Sci & Engn Tianjin Peoples R China

ISBN: (纸本)9781728190488

The shortest path tour problem (SPTP) is the abstract model of many practical applications, such as network function virtualization (NFV) and warehouse management. The aim of SPTP is to find the shortest path that passes multiple disjoint node subsets in a given order. The challenging part is the computational redundancy of existing decomposition-based algorithms, which is caused by determining the shortest paths from all pairs of sources and destinations in each subproblem. Inspired by the ripple spreading motions on water surface, a ripple-spreading algorithm (RSA) is proposed to solve SPTP in this paper. RSA outperforms other algorithms by forming connections among subproblems, and each subproblem can be solved in a single run to determine the shortest paths to every destination node. The time complexity is irrelevant to node quantities, so RSA is more efficient on large scale networks with sparse connections theoretically. Comparative experiments were conducted on fully random networks, and RSA was validated to be the most powerful algorithm by promoting the efficiency several times. Additionally, layered graphs were designed to simulate the topology of NFV. The computational efficiency of RSA also surpassed other algorithms on layered graphs with various parameters. This brand new algorithm should help to endow the SPTP-related problems with excellent solving efficiency and scalability.

关键词： Shortest Path Tour Problem ripple-spreading algorithm Optimization Decomposition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：