Heuristic Approximation of Optimal Paths in Spatial Databases by using Fuzzy Motivation Functions

A. Vancha-Am, A. Morris, and G. Vert (USA)


GIS, spatial databases, fuzzy logic, fuzzy databases, genetic algorithms


: It is not apparent if current Spatial Database Management Systems (SDBMS) can efficiently support network computations which traverse line segments in a spatial network based on connectivity rather than geographic proximity. Most of the algorithms used in spatial network analysis are based on geographical knowledge of physical proximity of the network elements. The objective of this project is to experiment in managing spatial network analysis as a virtual search space problem by taking the least amount of physical properties of the network elements into the knowledge of the analysis program. The data analysis problem is to approximate the optimal path between two given starting and ending nodes. Genetic Algorithms are used as the heuristic to discover optimal paths. Hypotheses of these optimal paths are represented by a bit-string of series of genes. A Fuzzy Motivation function is used as the performance measurement for the learning program. The training experience is the valid paths within the network, given the starting and ending node. Three selection functions have been developed and measured the performances. Those selection functions are 1) FMA Rank Selection, 2) FMA based Probabilistically Selection function and 3) FMA based Probabilistically Selection function with Hypothesis pruning.

Important Links:

Go Back