2.1. Design representation

It is assumed that the designs are to be represented parametrically. This is a common encoding method where the relevant design variables are the parameters of the design representation model. A design instance is then described by the associated (typically numerical) values taken by these parameters (Eastman et al., 1991; Green, 1997; Malmqvist & Schachinger, 1997). This does have the drawback of restricting the domain into a single representation; however, it is possible to allow sufficient flexibility by careful abstraction of the domain. For example, the bicycle example could detail all the possible saddle configurations; however, these are unlikely to have a major impact on the remainder of the domain, and hence, it is acceptable to assume that these can be represented simply by the saddle connection point only. In addition to the design parameters (e.g., geometry, material, etc.), this representation must also contain all the objective design criteria (e.g., weight, cost) and the subjective criteria that have been measured previously (e.g., suitable for city riding). The set of design parameters, objective, and subjective criteria²

2.2. Engineering design knowledge needs

The knowledge needs of designers changes as they gain experience. Popovic (2004) classifies the designer expertise level in part according to how many design rules and constraints a designer can mentally manage at any one time. Hence, to improve the capacity of novice designers, it is beneficial to present design rules and constraints in an intuitive manner, that is, one that requires less mental effort to process. Although this will impact the complexity of design rules and constraints, the benefit is that designers are able to process more rapidly a larger scope of the total design model.

In addition to the cognitive aspects of the knowledge presentation, it is also necessary to consider the type of knowledge that designers require. Ahmed and Wallace (2004) report on empirical evidence quantifying the relative volumes of novice queries for specific types of design information. Of these queries, the two largest categories were related to company and design process. Clearly, these are considered important by the novice designers but as they are process related, these will not contain significant product knowledge. The next most significant set of queries relate more closely to product, and are classified under “how does it work,” “what are the trade-offs,” “what is a typical value,” and “what issues to consider.” This product type knowledge can be represented by the relationships between product design parameters and objectives.

2.3. Knowledge engineering management methods

Knowledge engineering methods are concerned with eliciting domain knowledge from experts for future use. This has two aspects: the acquiring specific knowledge, and the storage and structuring of this knowledge.

Eliciting specific knowledge is primarily concerned with the rationale and rules that generate designs (Blessing, 1994; Arciszewski, 1997; Smith & Morrow, 1999). Although these rules can provide more explicit guidance during design, a major challenge is to identify the appropriate rule at any given point in the design process. Examples of this are rule-based design systems, for example, Siddall (1986), Arafat et al. (1993), Thornton (1996), and Arciszewski (1997). Critically, a large investment is needed to elicit these rules. This typically involves interviewing design experts, and then encoding and structuring the rules so that they can be readily accessed (Modesitt, 1992). This approach tends to be expensive to implement (Ahmed, 2001).

The storage aspects extend beyond the physical nature and media that is used to record design knowledge. Assuming that some archival media is being used, there is the issue of structuring and retrieving the information. This must address the granularity of the design data to be stored and how this is to be structured. These issues are researched by product and project data management groups. Such databases can be used to populate a case-based reasoning design tool (Leake et al., 1999; Reich & Barai, 1999; Rosenman, 2000). This approach allows designers to identify the most similar previous designs. These designs are then used as starting points for new designs, provided the designer understands the effects of any modifications made. Such an approach provides no rationale about how such previous designs were reached, unless this is explicitly included. Hence, there is a need to link the storage with rationale used to create the design in the first instance.

The method introduced in this paper aims to exploit design databases that lack rationale. Through the analysis of such databases, explicit design knowledge is to be extracted, providing rationale for these designs. By providing explicit understanding of the relationships in the domain, it will also be possible to create new designs more rapidly. Further, there is the potential of discovering new domain rules that were overlooked by domain experts.

2.4. Induction methods

Induction methods are data driven as opposed to expert driven, which is the case with the knowledge engineering approaches. This provides an advantage in cases where expert availability is limited, but sufficient prior data is available to build a model of the product family. There are a number of induction methods, ranging widely in the transparency of the models they generate (Andrews et al., 1995; Heckerman, 1999; Maire, 1999; Hong et al., 2000; Hwang & Yang, 2002). A brief overview of a sample of these is provided, starting with neural networks, one of the least transparent approaches.

Neural networks have been shown to be able to learn complex mappings well (Lawrence et al., 1996). The benefits of using neural networks lies in the wide range of domains they can be applied to, and the speed at which they perform at once trained. These benefits are underpinned by a strong theoretical understanding of how they learn and the performance and accuracy that can be expected of neural networks. However, the internal structure of the trained network remains opaque. This is a problem, as it difficult to understand how the input and output variables are related. Without this understanding, all that can be done is to use the neural network in a trial and error mode, which is an inefficient search strategy. There has been work on extracting simple and intelligible rules from these networks (Corbett-Clark, 1998; Huang & Xing, 2002; Matthews, 2002). This is a posttraining process, which provides explicit rules that can then be validated by an expert, and potentially edited if necessary. This provides a combined strategy to gain insights into the domain. However, this is a more complex process than acquiring the rules directly from the data.

Data mining methods are a large collection of methods that, in general, generate association rules from large databases. In contrast to neural networks, these are explicit rules. However, the rules are difficult to interpret, and are most often used as part of some other algorithm, for example, credit card fraud detection (Michalski & Kaufman, 1997). Data mining is primarily used to classify accurately and efficiently new cases into previously determined categories. As these methods are commonly used for computer identification of, for example, fraud detection, importance is given to the statistical significance of data mining results. The understanding of the limits of data mining methods represents one of the major benefits of this approach. However, the rules generated by the data mining methods are rarely used to provide greater insight into the original problem domain.

Automated science discovery methods provide insights into a domain where only empirical evidence is available. These methods iteratively build and test rules on a given set of observations, guided by a set of functional operators (Żytkow, 1999, 2000). Several empirical applications are cited, including physics, chemistry, and astronomy. Langley et al. (1987) introduced an algorithm for building mathematical equations from a given set of observation variables. This algorithm searches for equations that result in constant values for given subsets of observations, and it uses these to build further equations until some equation remains constant for all observations. This final equation represents a law for the given domain. The science discovery methods represent an implementation of the scientific method, and therefore, inherit the rigor that this thorough approach provides. Unfortunately, these discovery methods tend to be exhaustive, and hence, computationally expensive. In addition, for the science discovery methods, it is assumed that all the necessary observations are included.

For further reference on machine learning techniques and methods, Michalski and Tecuci (1994) and Mitchell (1997) provide thorough overviews of the domain, and Arciszewski and Ziarko (1992) discuss a selection of methods from an engineering perspective.

2.5. Summary: Criteria for an HEM

Engineering design knowledge presents an interesting set of requirements: a designer must have an understanding of how the various design variables are interrelated, but at the same time seeks new areas that are likely to challenge this understanding. Therefore, to support a designer, it will be necessary to provide these relationships in a nonconstraining manner. A large single unifying model is likely to constrain. For this reason, this approach proposes to offer a set of small (micro) models representing certain aspects of the domain. These loosely related micromodels represent a set of heuristics to be used by a designer searching for a good concept that can then be further analyzed by more expensive tools. The micromodels will be simple enough that the engineering principles can be seen without compromising accuracy, providing domain understanding, and hence, the ability to search the design space intelligently.

3.1. GP

GP is an evolutionary search algorithm (Koza, 1992; Koza et al., 1999). With GP, a more flexible solution representation is adopted. Instead of a fixed vectorlike structure, a tree structure is used. This allows the representation of functional forms (see Fig. 3). Functions are built up from primitive functional elements (e.g., addition and multiplication in algebra, or LISP functions). These functions form the nodes of a tree. The arguments of these functions are then subtrees, the terminal nodes being the function variables or constants. GP uses the same sexual recombination approach to generate the new solution space, but the operators are modified to apply to tree structures. This search results in identifying tree structures that provide good solutions, as evaluated by the provided fitness function. An example would be identifying an algebraic expression that curve fits the given dataset well. Unless there is some evolutionary pressure to keep these tree structures small, they are able to grow arbitrarily large if this improves their fitness score.

The creation of functional trees, using functional nodes for addition, squaring, and square root and terminal nodes a and b.

3.2. Island approach

As there is no great need in evolutionary computing searches for new candidate solutions to be generated synchronously, a number of evolutionary algorithms were developed for distributed computing environments. One of the earlier versions of this was applied to optimization of Walsh polynomials, distributing the solution populations to different independent GAs (Tanese, 1989). Two methods were compared, one where the GAs were left running independently of each other, and one where a small portion of the population was allowed to “migrate” between the otherwise independent GAs. Cohoon et al. (1987) defined a set of basic migration policies. These determine how members of different “islands” can migrate between islands: a mesh structure restricts migration between neighbors, a star allows migration through a central point, linear/circular is a one-dimensional mesh, and random removes any restriction to the inter-island migration. This island approach provided nearly linear acceleration when the processing was distributed between independent processors. Further studies demonstrated that this could be improved to superlinear acceleration by controlling the migration more carefully (Belding, 1995; Andre & Koza, 1996).

More practical applications of the island approach appear later. Potter et al. (1995) use the island approach to evolve a robot controller that has two competing strategies. The two strategies are evolved independently (one on each island); however, this application was sensitive to the initial seeding. Further work developed the island approach to string matching and neural networks (Potter, 1997; Potter & De Jong, 2000). This provided a better understanding of the behaviors of niches in the overall population, and how these niches can cooperate to provide some emergent behavior.

Wiegand et al. (2001) formalized the above approaches, and provided a general framework for cooperative coevolutionary algorithms. This work investigated more general questions about evaluating the collaborative nature between the islands and how many islands should be used.

3.3. Combining the EC elements

We have just described the core computational ideas that are to be adopted in the search for simple useful design relationships. As the aim is to search for arbitrary algebraic structures, the GP approach is the most suitable for this task. This will allow for the flexibility that can be achieved using algebraic structures that would not naturally occur if adopting the GA encoding method. As noted, the algebraic relationships can become arbitrarily large unless pressure is applied to keep them small. However, it is important to identify potential complex relationships. This will be achieved by using the island approach: individual solutions will be kept simple, and similar solutions will be developed on their own island. The interaction of these islands will represent the more complex behavior. Hence, it will be possible to report these complex behaviors by reporting the linkage between a pair of these islands that each represent a simple behavior. This linkage is identified through “collaborative” behavior between islands. The next section expands on these ideas.

4.1. Problem domain

The GP-HEM developed in this paper is based around real-valued design variables. This, in turn, provides a restriction on the type of design domain that can be analyzed fruitfully. The approach identifies simple algebraic relationships between subsets of design variables. Hence, it is necessary for the problem domain to be described using such components. In addition, the nature of the relationships being extracted is mostly continuous.³

As the design domain must be specified to this parametric granularity, this appears to be most applicable to the embodiment design phase. However, these algebraic rules can be interpreted as design guidelines, which provide a greater understanding of the design family. This understanding can then be applied at the earlier conceptual design stage, leading to better quality design concepts.

Because of the constraints on design representation, this approach appears to be most suited to mechanically oriented design domains. Similar approaches exist, for example, Ishino and Jin (2002) apply GP to understand designers' intent in a mechanical gear design domain. Such domains are more likely to be continuous in the design parameters, and hence, more suitable to this approach. There is evidence that a similar approach has also provided interesting results in chemical process engineering (Lakshminarayanan et al., 2000). It should be possible to apply this approach to other design domains, provided a sufficiently continuous problem area is being analyzed. Both these methods apply a GP to identify the mapping between the design parameters and a single design objective. Where designs have multiple objectives, this process is repeated independently for each objective.

Highly discontinuous domains are not expected to be successfully modeled by this approach, for example, in software design where very small design changes can result in large performance changes. In addition, the modeling of software design in a conceptual manner is a nontrivial task.

4.2. Assumptions

A number of assumptions are made on the nature of the design domain, the available data, and type of models that are to be extracted. First, it is assumed that the design domain is continuous (or no less than piecewise continuous) in the design variables. This assumption permits the search for algebraic models, rather than classification type models. It also allows simpler approximation functions to be created. This leads to the second assumption: the data is real valued and all present (no missing values). Thus, algebraic expressions constructed from the design variables can be directly evaluated as a real number. The third and final assumption is that micromodels provide a meaningful representation of the design domain. It is assumed that by combining micromodels, and thus in particular enabling direct relationships between subsets of design objectives, meaningful and interesting domain relationships will be identified with the GP-HEM.

4.3. Island creation

The islands GP approaches described in Section 3.2 simply distributed the solution population between processors arbitrarily. For the GP-HEM, each island represents a meaningful subset of design variables, and therefore there is a need for more careful distribution of the population between the islands. However, it is not known beforehand which design variables belong together. The approach adopted for the GP-HEM is to cluster the population of candidate solutions, and to treat each cluster independently as if it were a real island. This requires a metric to determine how the objects are to be clustered. This poses a challenge, because there are no inexpensive metrics for the functional space being searched by the GP. The following sections describe how this clustering can be achieved.

4.4. The fitness function

The fitness function provides the bias that directs the GP search. This function must reflect the desired properties of the better solutions, and it is typically computed by a function independent of the solution set. The aim is for the GP-HEM to discover pairs of functions that contain different terminal nodes, but have a high covariance coefficient. This is because the method is based on a cooperating coevolutionary approach, where “halves” of the micromodels are generated by the GP. Such pairs describe interesting phenomena that are being observed within the dataset. However, this is based strictly on the current population as opposed to some external measurement. As a result, it is no longer possible to compare fitness values across generations.

The candidate solutions are clustered into different islands based on the symbols they contained, and within each island it is expected that candidates have a high covariance. The algorithm therefore does not compare the covariance of a candidate solution with that of other members of that solution's island. In a further runtime optimization measure, the candidate is only measured against the medoids of the other islands. This is because the medoid is the representative of the island, and it will have a high covariance between itself and its fellow island members.

The aim is to keep the functions simple. To achieve this, a penalty is given to longer functions. Hence, the desired properties of the fitness function for a given solution member (f) can be summarized as follows:

1. the average covariance f has with the other islands' medoids must be high, because this suggests that f is a meaningful design expression when compared to the other medoids; and
2. the number of terms used in f should be kept low, but not so low that trivial expressions are overly promoted, because this suggests that f is likely to be comprehensible.

Based on this, the fitness function is expressed as follows:

where M is the set of medoids; S_fg is the covariance between functions f and g; and len(f) is the length of function f, which is counted by the number of terminal nodes.

4.5. Termination and final report

Evolutionary computing algorithms are typically terminated when the maximum fitness score achieves a preset level. This requires the fitness scores to be comparable between generations, which is not the case with the GP-HEM. Hence, the termination criteria in this case are crudely set to terminate the GP search algorithm after a preset number of iterations.

On termination of the evolutionary search algorithm, the results are compiled into a final report. This report is effectively the user interface of the method, and hence, it is important to ensure this report is meaningful to designers. This is achieved by reporting the functions in the simplest version possible. The report identifies pairs of functions that are both highly correlated and quite different with respect to the terminal nodes they contain.

The first step of the reporting function is to take a final measurement of the fitness of all the candidate solutions. This is performed in the same manner as previously and thus requires the population to be clustered into islands one last time. The next step is to identify “high-quality” pairs of candidate solutions from the population. This quality is measured by the pairs that have high covariance; are short; and come from different islands. This is computed for the function pair (f, g), where f and g are from different islands, as follows:

Function pairs are then reported, starting with the associated pair that scored the highest quality measure. The report displays the two functional form, in standard algebraic format, and the quality score for that pair.

5.1. Design space definition

The design space of the panel was represented by four design parameters and four objective criteria, forming an eight dimensional space. The design parameters were: width (x), height (y), depth (d), and material (ρ), all of which were randomly sampled from a uniform distribution. The objective criteria were weight, cost, life expectancy, and sales volume. These were related as follows:

where ε_N and ε_U represent noise and are randomly sampled values from a normal and uniform distribution, respectively. Note that the number of units sold was modeled only by a random value. This represents the subjective nature of the customer population. A key aim of this case study was to find out an explicit relationship for this objective based on the remaining parameters. In addition, all objectives had a small amount of Gaussian noise added. This was supposed to represent the noise occurring in real-world domains due to other factors that this simple model did not include.

Finally, a database of 200 examples was created from this model. This represented the “past designs” that would form the basis of the analysis. The size of this database was set similar to other product databases that would be analyzed.

5.2. Domain analysis

In addition to supplying a database of previous examples, the GP-HEM has three running parameters that need to be supplied. These determine how the analysis will be performed:

1. population size: how many relationships to hold for consideration during each iteration;
2. number of clusters: how many islands to create; and
3. number of iterations: number of generations to allow the search process to run.

For this case study, the parameters were as follows: the population size was set to 100, this population was to be split into 10 clusters, and the GP was allowed to run for 10 generations. After the run, the top 10 relationships (pairings) were reported as follows:

Although most of these relationships do not fully extract components of the original model, a number of useful design heuristics are reported. Further, this report illustrates how the quality function [Eq. (2)] scores the pairings.

The following paragraphs analyze the report with respect to each of the design objectives.

5.3. Method parameter sensitivity

The GP-HEM has four principal parameters: number of clusters to use, population size, crossover policy, and number of generations to run for before terminating. A series of independent experiments were run to investigate the sensitivity of the GP-HEM to each of these parameters. A common datum point is used throughout all the experiments as a reference point.

As discussed in Section 4.5, one drawback with the GP-HEM is the difficulty in measuring fitness independently of a given generation and cluster configuration. The development of the quality function [Eq. (2)] provides some independent measure of the final report, allowing different runs of the GP-HEM to be compared. In addition to this, an additional manual evaluation for the final report was used. Function pairs were classified into one of five different categories:

Independent GP-HEM runs can be compared by the categorization profile of each run. Although it might appear to be ideal to extract perfect relationships, a designer is likely to prefer to identify trends in the design domain. As such, a desirable profile is one with a high number of good and average relationships and a low number of misleading and wrong relationships.

5.3.1. Number of islands

The number of islands, or clusters, determines how many different types of “half” relationships can be classified. Clearly, it is essential to set the number of clusters no lower than the number of half relationships that exist in the design domain. However, it is unlikely that this number is known a priori. Therefore, it is good practice to set the number of islands slightly higher than would be expected for the design domain.

The GP-HEM was executed using the flat screen display data set with a series of different clustering settings. The results are presented in Table 1 using the profiles and quality measures. From here, it is can be seen that k = 3 produces the “best” results, in terms of the total number of good and average relationships. An alternative view would be to consider that k = 10, the datum setting, is best in terms of minimizing wasted effort due to wrong or misleading relationships. It is worth noting that the quality range (min/max Q) is nearly constant for all k settings.

Classification profiles and quality ranges for cluster number experiments

5.3.2. GP policy

At the core of any GP algorithm lies the crossover policy. This defines what proportion of the next generation arises from sexual reproduction (crossover), mutation, elite retention, and random injection. The sum of these four must add up to 100% of the new population, and so there were 3 degrees of freedom for this set of experiments. The experiments explicitly changed the crossover, mutation, and elitism proportions allowing the random injection level to be determined by the remaining available population. Each parameter was tested at a low, medium, and high setting, the datum being all three parameters set at medium. Due to the time required to manually inspect each set of results, a subset of the total possible 27 experiments was drawn up. This experiment schedule is listed in Table 2, and the profile results are listed Table 3.

Experiment schedule for the GP cross-over policy

Profile results from the GP cross-over policy assessment

For more detailed analysis, the raw result table is reordered for each policy parameter. For each parameter, the table is presented in order of ascending value of that parameter. Trends for each policy parameter were identified in term of how the profile changed as each individual parameter was increased. From Table 4, we can note the following: a high elitism policy is better; a high crossover policy is better; and a low mutate policy is worst. In respect to the mutate policy, the better policy depends on if the object is to maximize the good and average relationships (in which case use high mutate), or minimize misleading and wrong (in which case use medium mutate).

Profile trends for GP policy parameters

5.3.3. Population

The population represents the number of relationships under consideration in the GP-HEM algorithm. As the relationships are algebraic, there are infinitely many distinct forms that can be created using the given design variables. However, as the aim is to identify simple relationships, this reduces the number of potential candidates. In the flat screen design domain, it would be feasible to enumerate and test all relationships consisting of up to five symbols. However, this approach would not scale to more complex domains. The population size was varied between 50 and 200, each time evaluating the final relationships.

Table 5 contains the results of these runs. From this table it can be seen that there is an optimal population at about n = 50. This is interesting, as it clearly demonstrates that large populations are detrimental to the quality of the final result. However, it is important to bear in mind that the number of clusters will also have an effect on the final outcome: for the smaller populations each cluster will hold few members and for the large population each cluster will hold many members that potentially should not be in the same cluster.

Varying the population size used by GP-HEM

5.3.4. Number of design variables

The GP-HEM uses the design variables as the building blocks for the algebraic relationships. Increasing the number of variables represents an increase in the domain complexity. For this experiment, redundant variables were added. These variables took on random values that had no relationship either to the rest of the design or to each other. Therefore, it was not expected that these variables should appear in meaningful design relationships. However, it must be noted that although the number of variables was increased, there was no similar increase in the number of islands. As a result, each island “contained” more variables on average.

Table 6 contains the results of this these runs. The results show that the GP-HEM is relatively robust to a small increase in the number of (redundant) variables. When the increase becomes large (v = 12 and 16), numerous completely wrong relationships are being reported. However, this will be partly biased due to the number of islands remaining fixed.

Applying the GP-HEM to the design domain with redundant design variables added

5.3.5. Sensitivity to data sample size

An important aspect of any machine learning approach is the volume of data required to obtain “good” results. This set of runs illustrates how the GP-HEM performs with varying amounts of data from which to learn the relationships. The data sample size was varied between 50 and 600 data points.

Table 7 contains the results for these runs. Overall, there is relatively little change in the profile of the results and the range of quality scores. However, with fewer points, there will be a more significant change in the confidence in the relationships. In addition, this set of runs also illustrates how the computational time increases with the increased sample size.

Varying the sample size used by the GP-HEM

5.3.6. Sensitivity to noise

In addition to the sensitivity to sample size, it is important to consider how well a machine learning algorithm handles noisy data sets. In this set of runs, a controlled amount of noise was added to the sample generated from the domain model, ranging from σ = 0 to 1.0.

Table 8 contains the results for these runs. Interestingly, there is very little difference in the profile of the relationships extracted. The main difference in the results between the various noise levels is given by the reduced quality measurements. This is to be expected, as the quality score is based on the covariance between the relationships that will be reduced as a result of adding noise to the original data.

Varying the added noise level to the data

5.3.7. Convergence and termination criteria

The GP-HEM adopted the simple termination criteria of halting after a predetermined number of generations. A set of experiments was run to identify the trends in the performance of GP-HEM with varying the run length from 1 generation through to 20 generations.

Table 9 contains the relationship profiles for all the runs of varying lengths. The primary interest is in the relationships that are classified under good and average. The results show that this stabilizes at nine relationships in total from five generations onward. The poorest two relationship classes, misleading and wrong, remain stable throughout. The perfect relationships reduce rapidly from a relatively high count early in the run through to a stable count of two in later generations.

Relationship profiles after varying number of generations

5.4. Discussion

The analysis of this design case study has illustrated the nature of the relationships that can be extracted, along with some of the weaknesses of the implementation. A significant number of design heuristics were extracted that provide an understanding of how the design variables are related through trade-offs. These were not only based on design parameters, but they also could provide an understanding of how the design characteristics were related.

The principal weakness is evident in the scoring functions, both fitness [Eq. (1)] and quality [Eq. (2)]. It is not possible to compare fitness function score directly between population generations. This is important to enable measuring of how well the population is improving overall between generations and to provide a more intelligent stop criteria. The quality scoring function has two drawbacks: first, it penalizes important long expression too heavily, and second it scores tautological relationships too highly (e.g., relationship 3). The first issue should be able to be rectified by modifying the nature of the length penalty. The second issue will require an extra penalty component to the quality function reflecting on the amount of overlap in design variables between the two halves of the relationship.

A.1. Illustration

This example is taken from Kaufman and Rousseeuw (1990). Table A.1 contains the coordinates of 10 objects, which have been plotted in Figure A.1. From this data, the euclidean distances are computed between all pairs of points. If k = 2 clusters are to be identified, then the algorithms starts be arbitrarily choosing two medoid candidates, say points 1 and 5. A new table can be drawn up, for each point computing the distance to point 1 and point 5. Table A.2 contains this information and also identifies the clusters for this case. Clearly, this is not a very good clustering. At the final iteration, the medoids are points 4 and 8. Table A.3 is the distance table for this case. Figure A.2 illustrates these two clustering configurations.

Raw data set for PAM illustration

A two-dimensional data plot of 10 objects.

Distance and clusters for first iteration

Table A.3: Distance and clusters for last iteration

The clustering of the first and last iteration.