A knowledge-based environment for the validation of simulation models.

Abstract

A new approach to the validation of simulation models is developed in this thesis. The underlying goal of the approach is to utilize both domain specific knowledge about expected behaviour of the system (typically acquired from a domain expert), and where available, data gathered from an observable system. The approach is knowledge, rather than statistically, based. Behavioural knowledge about the simulation model is formulated in terms of an external specification which is comprised of three disjoint sets of relationships; namely, formal specifications, qualitative specifications and observational specifications. These sets of relationships are developed in a formal context and together they form a knowledge base of validation reference information. A key element in the implementation of a software environment for simulation model validation is the development of an effective means for utilizing the validation reference information. This, in effect, becomes an experiment design problem. Its solution is undertaken in a constraint set framework that evolves from a transformation on the validation reference information. The experiment design problem is thus transformed into a "constraint covering" problem which we refer to as the $C\sp3$ problem (Consistent Constraint Covering). The complexity of the $C\sp3$ problem is analyzed using graph-theoretic concepts. This analysis is based on a new concept that is associated with a set of constraints; namely, a constraint set graph. We explore the relationships between a maximum independent set of a constraint set graph and a simplified version of the $C\sp3$ problem and show its relationship to both the edge cover problem and a set-covering problem. A relationship between the $C\sp3$ problem and the clique cover problem, which is known to be NP-complete, is also shown. An effective approximation algorithm to solve the $C\sp3$ problem is then developed and some of its key properties are explicitly demonstrated. The performance of the algorithm on a set of example problems is included. The thesis establishes a formal general framework for studying the validation problem for simulation models. The $C\sp3$ problem is shown to be a key aspect of the validation problem and the solution to the $C\sp3$ problem which is developed therefore contributes significantly to the solution of the simulation model validation problem.