Regular PapersNo Access

USING CULTURAL ALGORITHMS TO RE-ENGINEER LARGE-SCALE SEMANTIC NETWORKS

NESTOR RYCHTYCKYJ

Ford Motor Company, Manufacturing Engineering Systems, Rouge Office Building, Dearborn, MI 48121, USA

Search for more papers by this author

and

ROBERT G. REYNOLDS

Department of Computer Science, Wayne State University, Detroit, MI 48202, USA

Search for more papers by this author

https://doi.org/10.1142/S0218194005002506Cited by:7 (Source: Crossref)

Abstract

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. We identify two complementary methods of using Cultural Algorithms to solve the problem of re-engineering large-scale dynamic semantic networks in order to optimize the efficiency of subsumption: 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 goal of bottom-up approach is to classify the input concepts into new clusters that are most efficient for subsumption and classification. While the resultant subsumption efficiency for the bottom-up approach exceeds that for the top-down approach, it does so by removing structural relationships that made the network understandable to human observers. Like a Rete network in expert systems, it is a compilation of only those relationships that impact subsumption. A direct comparison of the two approaches shows that bottom-up semantic network re-engineering creates a semantic network that is approximately 5 times more efficient than the top-down approach in terms of the cost of subsumption. In conclusion, we will discuss these results and show that some knowledge that is useful to the system users is lost during the bottom-up re-engineering process and that the best approach for re-engineering a semantic network requires a combination of both of these approaches.

Keywords:

References

R. Brachman and J. Schmolze, Cognitive Science 9(2), 171 (1985). Crossref, Web of Science, Google Scholar
R. Brachmanet al., Principles of Semantic Networks (Morgan Kaufmann, 1991) pp. 401–456. Crossref, Google Scholar
G. Piatetsky-Shapiro and W. Frawley (eds.) , Knowledge Discovery in Databases ( AAAI Press , 1991 ) . Google Scholar
V. Rajlich, Proc. 1997 IEEE Int. Conf. on Software Maintenance (IEEE Press, 1997) pp. 84–91. Crossref, Google Scholar
M. Sternberg and R. Reynolds, IEEE Trans. on Evolutionary Computation 1(4), 225 (1997). Crossref, Google Scholar
H. Al-Shehri, Evolution-Based Decision Tree Optimization Using Cultural Algorithms, Ph.D. Dissertation, Wayne State University, 1997 . Google Scholar
N. Rychtyckyj, DLMS: Ten years of AI for vehicle assembly process planning, AAAI-99/IAAI-99 Proceedings, Orlando, FL, July 18–22, 1999, pp. 821–828 . Google Scholar
N. Rychtyckyj and R. Reynolds, Using cultural algorithms to improve performance in semantic networks, in Proc. 1999 Congress of Evolutionary Computation, Washington D.C, July 6–9, vol. 3, 1997, pp. 1651–1656 . Google Scholar
N. Rychtyckyj and R. Reynolds, Assessing the performance of cultural algorithms for semantic network re-engineering, in Proc. 2000 Congress on Evolutionary Computation, July 16–19, La Jolla, CA, 2000, pp. 1482–1491 . Google Scholar
N. Rychtyckyj and R. Reynolds, Long-term maintenance of deployed knowledge representation systems, in Proc. Seventh Int. Conf. on the Principles of Knowledge Representation and Reasoning, April 12–17, Breckenridge, CO, 2000, pp. 494–504 . Google Scholar
J. Debenham, Knowledge base maintenance through knowledge representation, in Proc. 12th Int. Conf. on Database and Expert Systems Applications, Munich, Germany, September 3–5, 2001 . Google Scholar
Spangler, Scott and Kreulen, Jeffrey, Knowledge base maintenance using knowledge gap analysis, in Proc. 7th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, San Francisco, CA, 2000, pp. 462–466 . Google Scholar
L. Zhanget al., Journal of the American Medical Informatics Association 11(3), 195 (2004). Crossref, Web of Science, Google Scholar
M. Quillian, Semantic Memory in Semantic Information Processing (MIT Press, 1975) pp. 216–270. Google Scholar
J. Schmolze and T. Lipkis, Proc. Eight Int. Joint Conf. on Artificial Intelligence (Morgan Kaufmann, 1983) pp. 330–332. Google Scholar
W. A. Woods, Principles of Semantic Networks (Morgan Kaufmann, 1991) pp. 45–94. Crossref, Google Scholar
M. Schmidt-Strauss, Proc. First Int. Conf. on Knowledge Representation and Reasoning (Morgan Kaufmann, 1989) pp. 421–431. Google Scholar
N. Rychtyckyj, Proc. Sixth Int. Conf. on Tools with Artificial Intelligence (IEEE Computer Science Press, 1994) pp. 339–345. Crossref, Google Scholar
R. G. Reynolds and C. Chung , Proc. 1996 IEEE Int. Conf. on Evolutionary Computing ( IEEE Press , 1996 ) . Google Scholar
R. G. Reynolds and C. Chung, Proc. Seventh Int. Conf. on Genetic Algorithms (Morgan Kaufmann, 1997) pp. 401–408. Google Scholar
R. G. Reynolds, An introduction to cultural algorithms, in Proc. 3rd Annual Conf. on Evolutionary Programming, eds. A. Sebald and L. Fogel, 1994, pp. 131–139 . Google Scholar
L. Booker, Classifier systems, endogeneous fitness, and delayed rewards: A preliminary investigation, in Proc. 2001 Genetic and Evolutionary Computation Conference, San Francisco, CA, July 7–11, 2001, pp. 921–934 . Google Scholar
P. Angeline, Tracking extrema in dynamic environments, in the 6th Int. Conf. in Evolutionary Programming VI, Indianapolis, Indiana, USA, April 1997, pp. 335–345 . Google Scholar
C. Chan-Jin, Knowledge-Based Approaches to Self-Adaptation in Cultural Algorithms, Ph.D. thesis, Wayne State University, Detroit, MI, 1997 . Google Scholar
G. Miller, Psychological Review 63, 81 (1956). Crossref, Web of Science, Google Scholar
R. G. Reynolds, New Ideas in Optimization (McGraw Hill, 1999) pp. 367–377. Google Scholar
N. Rychtyckyj, Proc. Fifth Int. Conf. on the Principles of Knowledge Representation and Reasoning (Morgan Kaufmann, 1996) pp. 588–596. Google Scholar
N. Rychtyckyj and R. Reynolds, Evolutionary Programming VII (Springer-Verlag, 1998) pp. 181–190. Google Scholar