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.
關聯:
INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL Volume: 7 Issue: 12 Pages: 6889-6904
