Using cultural algorithms to re-engineer semantic networks

Evolutionary computation has been successfully applied in a variety of problem domains and applications. In this paper we discuss the use of a specific form of evolutionary computation known, as Cultural Algorithms to improve the efficiency of the subsumption algorithm in semantic networks Subsumption is the process that determines if one node in the network is a child of another node. As such, it is utilized as part of the node classification algorithm within semantic network-based applications. We identify two complementary methods of using Cultural Algorithms to solve the semantic network re-engineering problem: top-down and bottom-up.; The top-down re-engineering approach improves subsumption efficiency by reducing the number of attributes that need to be compared for every node without impacting the results. We demonstrate that a Cultural Algorithm approach can be used to identify these defining attributes that are most significant for node retrieval. These results are then utilized within an existing vehicle assembly process planning application that utilizes a semantic network based knowledge base to improve the performance and reduce complexity of the network. It is shown that the results obtained by Cultural Algorithms are at least as good, and in most cases better, than those obtained by the human developers. The advantage of Cultural Algorithms is especially pronounced for those classes in the network that are more complex.; The second part of our thesis approaches the semantic network re-engineering problem from a different perspective. The re-engineered semantic network will contain all of the concepts and attributes described previously, but the structure will be created using bottom-up learning heuristics and the Cultural Algorithm learning process. The goal of Cultural Algorithms in this application is to classify the input concepts into clusters that are most efficient for subsumption and classification. A set of concepts with all of their properties is used as the input and a semantic network is generated as an output. This approach allows us to create a new semantic network without relying on any of the previous design information. We also show how Cultural Algorithms are used to discover emergent knowledge by incrementally combining building block; from each level of the network to the next in this application. The results obtained by using Cultural Algorithms are then favorably compared with both a decision tree algorithm and with the results obtained manually by the human developers.; Our thesis concludes with a comparison of the top-down and bottom-up approaches in term of reducing the complexity of subsumption and suggests further research topics that should be addressed.