Dr. Dobb's Journal February 1999
While recently working on a streaming video decoder, I ran into a tough problem. I wanted both high frame rates and high resolution -- but couldn't get both. How should I balance resolution and frame rate to get the best overall output, especially on systems where the available CPU power might fluctuate wildly?
This type of decision-making is common in many kinds of software. My video decoder problem was similar to that encountered by search-engine designers ("Should I show more matches or only more-relevant matches?"). File-system designers must balance robustness ("Will I lose files in a crash?") and speed.
The technique Andrew discusses this month could let users, rather than programmers, make decisions such as these. That is, rather than designers dictating what they see as priorities, end users can specify their priorities, and have the software dynamically adjust.
-- Tim Kientzle
Suppose you are the president of a major airline. Your fleet of commuter jets is showing its age and you have a mandate from the board to purchase 20 new aircraft. Some of the factors you may take into account are reliability, fuel consumption, maintenance costs, price of spare parts, and pilot preference. In turn, each of these factors may require weighing a large number of individual data points.
The total number of factors can easily run into the hundreds or thousands (especially where acquisition of military equipment is concerned, or where taxpayer money is concerned). Naturally, some factors are more important than others, but it's by no means clear how to combine them all together to give an answer. To add to this difficulty, some inputs may be unquantifiable, or only specified in vague terms.
In this article, I present the analytic hierarchy process (AHP), a decision-making tool for exactly this type of problem. Devised by Thomas Saaty of the Wharton Business School (see Mathematical Methods of Operational Research, by T.L. Saaty, Dover, 1988), it's a simple but intriguing analytical technique for reducing complex decisions to a series of comparisons and rankings. The results are then combined to give a single, unequivocal result.
I'll illustrate how the process works by using the AHP to select one of several compilers for use in an introductory C++ course. The aim is to select the compiler that has the best match to student needs, based on an assessment of the relative importance of the features available in a C++ package, and the competing strengths of three rival products.
The first step in using the AHP is to make a list of the factors to be considered in the decision. For a student compiler, factors such as cost, quality of the documentation, and whether or not the compiler supports exception handling are important. The ability to produce fast run times or handle legacy code is less of a priority. The AHP then requires you to construct a hierarchy of factors that will lead up to your decision.
A hierarchy lets you move from general questions and preferences (How important is the quality of development environment?) to the more specific (How important are run-time sizes?) to the particular (How good is the loop unrolling algorithm?). Grouping documentation preferences or C++ specifics is natural. This lets you state broad preferences, such as "cost is more important than a slick environment," or "cost is only slightly more important than standard C++ constructs."
Figure 1 shows the hierarchy tree I've designed for this problem. The form of the tree is fairly straightforward to formulate in this case, but may require considerable thought for more complex cases. This is a point at which it may be useful to brainstorm with colleagues.
The next step is to decide on the relative importance of each factor at each level. For instance, Table 1 assigns purely subjective numbers to the level-1 features. With these numbers, you can construct a matrix of pairwise comparisons, showing the relative importance of one criterion over another (Table 2).
Next, you form a set of weightings for the four features, so that:
To derive a set of weights from this matrix that you can use for subsequent decision making, you need a little mathematics. A proof demonstrated by Saaty shows that the optimal set of scores is the principal eigenvector of this matrix. The proof requires knowledge of the kernels of linear transformations. Although the general eigenvector problem can be complex, there are several algorithms to calculate principal eigenvectors in a simple iterative manner, one of which I have implemented in Listing One. For this matrix, the eigenvector is {0.3, 0.2, 0.4, 0.1}, which forms the set of weights showing the relative importance of each feature.
Once you have a set of weights for these four features, it's a straightforward matter to rank the competing products. For each compiler, simply multiply the weight of each feature by a score showing how well the compiler implements that given feature. The sum of these scaled scores is the compiler's overall score. The compiler with the highest score is the winner.
You may be wondering why you don't simply add up the relative preferences and normalize to 1. After all, this would be much simpler and gives the same answer. The reason is that the way users feel about product (or feature) A, compared to product (or feature) B, may not precisely reflect how they feel about B compared to A. Neither score is wrong; it's just that an imprecise value judgment is being made.
In this case, the pairwise comparison matrix may not be consistent, so that off-diagonal elements may not be the reciprocal of their transpose entries. This could be a problem if you were restricted to normalizing vectors, since you would then be unable to produce the weights by simple normalization. However, the eigenvector formulation handles such cases with ease. The resulting vector simply reflects a composite view of the two conflicting judgments. This is a major strength of the AHP, in that it combines imprecise, vaguely specified, and even contradictory preferences into a single, unequivocal result.
Suppose you can't easily supply a numerical score for a set of attributes. Saaty suggests that you construct a matrix where each off-diagonal element is acquired by comparing the two factors in importance using a scale like that in Table 3. For instance, if A is strongly more important than B, then A is 5 times as important as B, while B is 1/5 as important as A.
You can use this scale if it's just too difficult to numerically rank a group of features. Suppose you were called on to rank famous composers -- who would be rash enough to say, "Mozart is 2.334 times better than Puccini." And would this mean that Puccini is 0.4285 as good as Mozart? Rather than making silly numerical pronouncements of this form, you would be better advised to use a verbal scale of the aforementioned form. The power of the AHP in this type of case is that it will still give useful answers, even with the inevitable inconsistencies that will creep in due to the lower precision.
But what happens when you want to actually compare different products against each other to provide scores for each product? The answer is that you can use exactly the same approach. Instead of comparing the importance of features, we rank how well the product implements that feature. For instance, on Cost, the three compilers are ranked as (80 percent, 50 percent, 20 percent) showing that the first compiler had the highest score, presumably because it was cheapest. This means that the relative scores for the three products are (0.533,0.333,0.133). The contribution from Cost to the first compiler's final score is therefore 0.533 (the first compiler's score for Cost) times 0.3 (the importance that Cost has in the final reckoning).
As mentioned, it may happen that you can't agree on absolute scores for the products. In this case, you can carry out a pairwise comparison of the appropriate features, comparing one against the other. For instance, "ease of use of IDE" is going to be particularly hard to judge numerically, and it makes more sense here to compare each of the rival products with each other.
Since the algorithm is recursive, you can build hierarchies of features. I've illustrated this by making the decision on "C++ features" dependent on two subfeatures: whether the compiler supplies the Standard Template Library (STL), and whether it supports exception handling.
After deciding that having the STL available is twice as important as supporting exception handling, the weights for these two features are therefore (0.667, 0.333). Applying a score of 9 if the compiler supports the given feature and 1 if it doesn't, we come up with the scores (0.052, 0.474, 0.474) for STL support and (0.474, 0.474, 0.052) for exception handling. The overall compiler scores for C++ features are therefore (0.192, 0.474, 0.333), and these scores are fed back to the higher levels for the final decision.
Listing One implements the AHP in C. The hierarchy for the problem is set up as an n-ary null-terminated tree. Levels in the hierarchy are set up as elements in a statically declared array, where each element contains the following:
I've assigned the scores in Table 4 to each of the three fictional compiler's features. Matrices of pairwise comparisons have been written into the static array at the head of the program.
The matrix for the top-level decision has deliberately been made inconsistent. The importance of cost compared to documentation has been given as 3/2 above the diagonal, and as 2/1 below the diagonal. The matrix values are found in Table 5.
Since the calculation of principal eigenvectors is so quick, I have made no effort to distinguish between cases where we can calculate a priority vector from simple normalization, and cases where we actually need the eigenvector machinery.
When the program is run, eigenvectors are calculated for each element in the hierarchy and each case is evaluated recursively to give a final score. The winning compiler in this case was the ByteMangler with a score of 0.439. Although not the first choice on cost, it had a better development environment and documentation than the competition. The Nanosoft and Outprise compilers came in second and third with scores of 0.288 and 0.272, respectively.
A natural extension to this idea would be "what-if" sampling. Assuming you start with top-level weights and work downward in level of detail, there may occur cases where varying the values of some low-level attributes makes no difference at all to the final answer. The values of these unimportant inputs would then be ignored and no further effort would be expended in working on them. Knowledge of such inputs (which could be found using sensitivity analysis or Monte Carlo techniques) could result in saving substantial time and resources.
References to commercial tools that implement the AHP can be found at http:// expertchoice.com/, which has more information, and downloads of commercial demos. There is a dazzling array of ingenious uses of the technique, ranging from selecting mutual funds and choosing boat hulls for the U.S. Coast Guard, to predicting (correctly, as it turned out) Saddam Hussein's moves in the Gulf War.
DDJ
/* FILE: ahp.c** AUTHOR: Andrew Colin
** DATE: 29th October 1998
** DISCLAIMER: No liability is assumed by the author for any use made
** of this program.
** DISTRIBUTION: Any use may be made of this program, as long as the
** clear acknowledgment is made to the author in code and runtime
** executables. The author retains copyright.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#define MAX_ATTRIBUTES 10
#define N_CASES 3
#define MAX_ITERATIONS 100
#define randomize() srand((unsigned)time(NULL))
typedef struct element {
int n_factors; /* Number of attributes/items */
char attributes[MAX_ATTRIBUTES][0xFF]; /* Not used */
double preferences[MAX_ATTRIBUTES][MAX_ATTRIBUTES]; /* rankings */
struct element *branch[MAX_ATTRIBUTES]; /* Address of sub-attribute */
double eigenvector[MAX_ATTRIBUTES]; /* computed rankings */
double ranking[N_CASES]; /* Final, relative worth of each choice */
} ELEMENT;
ELEMENT array[] = {
{ 4, {"Top-level", "b", "c", "d"},
{{1,1.5,0.75,3},{0.667,1,0.5,2},{1.333,2,1,4},{0.333,0.5,0.25,1}},
{&array[1], &array[2], &array[3], &array[4]} },
{ 3,{"Documentation"},{{1,0.25,0.333},{4,1,1.333},{3,0.75,1}}, {NULL}},
{ 3, {"Cost"}, {{1,1.6,4},{0.625,1,2.5},{0.25,0.4,1}}, { NULL } },
{ 3, {"IDE"}, {{1,0.714,1.25},{1.4,1,1.75},{0.8,0.571,1}}, { NULL } },
{ 2, {"C++ features"}, {{1,2},{0.5,1}}, { &array[5], &array[6] } },
{ 3, {"STL library"}, {{1,0.111,0.111},{9,1,1},{9,1,1}}, { NULL } },
{ 3, {"Exception handling"}, {{1,1,9},{1,1,9},{0.111,0.111,1}},{NULL}},
};
/*---------------------------------------------------------------------------*/
/* Multiplies a matrix m and a vector v; returns the result in vector
* r. Note the syntax for passing a statically declared multidimensional array
* to a function (see K&R, p112, second edition)
*/
void mmult( int size, double m[][MAX_ATTRIBUTES], double v[], double r[] ) {
int i, j;
for (i=0; i<size; i++) {
r[i] = 0.0;
for (j=0; j<size; j++)
r[i] += m[i][j] * v[j];
}
}
/*---------------------------------------------------------------------------*/
/* Given a matrix m, this routine returns the normalized principal
* eigenvector e using the power method (see Burden and Faires,
* Numerical Analysis, Prindle, Weber & Schmidt, 1985, pp 452-456)
*/
void np_eigenvalue( int size, double m[MAX_ATTRIBUTES][MAX_ATTRIBUTES],
double e[MAX_ATTRIBUTES] ) {
double v[MAX_ATTRIBUTES];
double largest, s, sum;
int i, iteration;
/* Initial random guess for eigenvector */
for (i=0; i<size; i++)
v[i] = (double)rand() / RAND_MAX;
iteration = 0;
while (iteration < MAX_ITERATIONS) {
/* Construct new approximation to eigenvector */
mmult( size, m, v, e );
/* Find largest element in new eigenvector */
largest = 0.0;
for (i=0; i<size; i++) {
s = fabs(e[i]);
if (s > largest)
largest = s;
}
/* Normalise by dividing by element of largest absolute magnitude */
for (i=0; i<size; i++)
e[i] /= largest;
/* Copy new approximation to old approximation */
for (i=0; i<size; i++)
v[i] = e[i];
++iteration;
}
/* Normalise eigenvector so that sum of elements = 1 */
sum = 0.0;
for (i=0; i<size; i++)
sum += e[i];
for (i=0; i<size; i++)
e[i] /= sum;
}
/*---------------------------------------------------------------------------*/
/* Evaluates the priority vector for each node in the decision
* tree. This routine calculates the principal eigenvector of the
* array 'preferences' and writes it to the array 'eigenvector'.
*/
void get_eigenvector (ELEMENT *e) {
np_eigenvalue( e->n_factors, e->preferences, e->eigenvector );
}
/*---------------------------------------------------------------------------*/
/* Recursive routine to evaluate the ranking vector for an element of
* a hierarchy, where the priorities (or principal eigenvectors) have
* already been calculated.
*/
void evaluate_hierarchy( ELEMENT *e ) {
int i, j;
if (e->branch[0] == NULL) { /* At bottom level of hierarchy */
assert (e->n_factors == N_CASES);
for (i=0; i<N_CASES; i++)
e->ranking[i] = e->eigenvector[i];
}
else {
for (i=0; i<e->n_factors; i++) /* At intermediate level */
evaluate_hierarchy( e->branch[i] );
for (j=0; j<N_CASES; j++) {
e->ranking[j] = 0.0;
for (i=0; i<e->n_factors; i++)
e->ranking[j] += e->eigenvector[i]
* e->branch[i]->ranking[j];
}
}
#ifdef _DEBUG
for (i=0; i<N_CASES; i++)
printf("Ranking for item %i is %f\n", i, e->ranking[i]);
#endif
}
/*---------------------------------------------------------------------------*/
main() {
int i;
randomize();
printf("\nWelcome to the Analytic Hierarchy Process!");
printf("\nLast compiled on %s, %s\n", __TIME__, __DATE__);
/* Evaluate priority arrays for each element in 'array' */
for (i=0; i<sizeof(array) / sizeof(array[0]); i++)
get_eigenvector (&array[i]);
/* Evaluate the tree. The result is returned in array[0].ranking */
evaluate_hierarchy (&array[0]);
/* Display rankings for each case. The highest score is the winner. */
for (i=0; i<N_CASES; i++)
printf("Case %i has ranking %f\n", i, array[0].ranking[i]);
return 0;
}