SOLVING THE SHORTEST PATH PROBLEM WITH IMPRECISE ARC LENGTHS USING A TWO-STAGE TWO-POPULATION GENETIC ALGORITHM

CCUR > College of Natural Science and Engineering > College of Science > Department of Applied Mathematics > journal articles > Item 987654321/22911

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/22911

Title:	SOLVING THE SHORTEST PATH PROBLEM WITH IMPRECISE ARC LENGTHS USING A TWO-STAGE TWO-POPULATION GENETIC ALGORITHM
Authors:	Lin, Feng-Tse Shih, Teng-San
Contributors:	應用數學系
Keywords:	CONSTRAINTS FUZZY NETWORK
Date:	2011-12
Issue Date:	2012-09-04 09:38:33 (UTC+8)
Abstract:	This study investigates how to solve the shortest path problem with imprecise arc lengths using a two-stage two-population genetic algorithm (CA). This approach can conveniently represent imprecise numerical quantities, and therefore, it is able to handle imprecise arc lengths. In its first stage, the proposed GA simulates a fuzzy number by partitioning an imprecise arc length into a finite number of subintervals. Each subinterval represents a partition point. A random real number in [0, 1] is first assigned to each partition point. The GA then evolves the values in each partition point, with the final values in each partition point representing the membership grades of that, fuzzy number. Thus, it is possible to obtain estimated values for the originally imprecise arc lengths, and the fuzzy problem becomes a defuzzified instance. The second stage of the GA is to search for the best solution to the defuzzified instance using a scheme in which two candidate populations evolve simultaneously. The first population comprises a set of feasible candidate solutions, and the second population consists of infeasible candidate solutions. The two solution populations are separately maintained and evolved, but their offspring may flow from one population into the other. Experimental results show that the proposed two-stage two-population GA approach obtains better results than other fuzzy shortest path approaches.
Relation:	INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL Volume: 7 Issue: 12 Pages: 6889-6904
Appears in Collections:	[Department of Applied Mathematics] journal articles

Files in This Item:

There are no files associated with this item.

View Licence

Loading...