United States Department of Transportation - Federal Highway Administration FHWA Home Feedback

2019 VERSION: Volume III: Guidelines for Applying Traffic Microsimulation Modeling Software 2019 Update to the 2004 Version

2004 Version - Appendix D: Simple Search Algorithms for Calibration

Since simulation models are complex, it is not typically possible to formulate the models as a closed-form equation for which traditional calculus techniques can be applied to find a minimum value solution. It is necessary to use some sort of search algorithm that relies on multiple operations of the simulation model, plotting of the output results as points, and searching between these points for the optimal solution. Search algorithms are required to find the optimal solution to the calibration problem. The calibration problem is a nonlinear least-squares optimization problem.

There are many software programs available for identifying the optimal combination of calibration parameters for minimizing the squared error between the field observations and the simulation model. The Argonne National Laboratory (www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Categories/nonlinleastsq.html) lists several software programs for nonlinear least-squares parameter estimation.

The sections below illustrate some simple approaches available for single-parameter estimation and dual-parameter estimation when working with a stand-alone simulation model. Estimation of three or more parameters, however, would require the use of a software program.

D.1 Single-Parameter Search Algorithm (Golden Section)68

Several methods are available for finding the value of a single parameter that minimizes the squared error between the model and the observations. These methods include Newton's Method, Secant Method, Quadratic Approximation Methods, and the Golden Section Method. The Golden Section Method is illustrated in the example below.

D.1.1 Example of Golden Section Method

Objective: Find the global value of the mean headway between vehicles that minimizes the squared error between the field counts of traffic volumes and the model estimates.

Approach: Use the Golden Section Method to identify the optimal mean headway.

Step 1: Identify the maximum and minimum acceptable values for the parameter to be optimized.

This step brackets the possible range of the parameter in which the optimal solution is presumed to lie. The user can select the appropriate range. For this example, we will set the minimum acceptable value for the mean headway at 0.5 s and the maximum at 2.0 s. The larger the range, the more robust the search. However, it will take longer to find the optimum value. The smaller the range of acceptable values, the greater the likelihood that the best solution lies outside of the range.

Step 2: Compute the squared error for maximum and minimum values.

The simulation model is run to determine the volumes predicted when the maximum acceptable mean headway is input and again for the minimum acceptable headway. Either randomization should be turned off or the model should be run several times with each mean headway and the results averaged. The squared error produced by the model for each mean headway is computed.

Step 3: Identify two interior parameter values for testing.

The two interior points (x1 and x2) are selected according to specific ratios of the total range that preserve these ratios as the search range is narrowed in subsequent iterations. The formulas for selecting the two interior mean delays for testing are the following:

Equation 14. The lower interior point value for the mean delay to be tested, X subscript 1, equals the lower end of the search range for the mean delay, min, plus 0.382 times the sum of the upper end of the search range for the mean delay, max, minus min.  (Equation 14)

Equation 15. The upper interior point value for the mean delay to be tested, X subscript 2, equals min plus 0.618 times the sum of max minus min.  (Equation 15)

where:

x1 = lower interior point value for the mean delay to be tested

x2 = upper interior point value for the mean delay to be tested

min = lower end of the search range for the mean delay

max = upper end of the search range for the mean delay

The minimum and maximum ends of the search range are initially set by the user (based on the acceptable range set in step 1); however, the search range is then gradually narrowed as each iteration is completed.

Step 4: Compute squared error for two interior parameter values.

The simulation model is run for the new values of mean delay (x1 and x2) and the squared errors are computed.

Step 5: Identify the three parameter values that appear to bracket the optimum.

This step narrows the search range. The parameter value (x1 or x2) that produces the lowest squared error is identified. (If either the minimum or the maximum parameter values produce the least-squared error, the search range should be reconsidered.) The parameter values to the left (lower) and right (higher) of that point become the new minimum and maximum values for the search range. For instance, in Figure 16, parameter value x2 produces the lowest squared error.

Figure 16. Golden Section Method. Graph. This graph charts Parameter on the horizontal axis and Squared Error on the vertical axis. The minimum and maximum acceptable values for the parameter to be optimized are identified at points along the horizontal axis, as are two interior points, X subscript 1 and X subscript 2. The search range is the area between the minimum and maximum values. Squared error is highest at the minimum parameter value, drops slightly at X subscript 1, is at its lowest at X subscript 2, and rises back up at the maximum parameter value.

Figure 16. Golden Section Method.

Step 6: Return to step 3 and repeat until the uncertainty in the location of the optimal parameter value is satisfactory.

The Golden Section search is repeated until the range of values in which the optimum parameter value lies is small enough to satisfy the user's requirements. After about 10 iterations, the uncertainty in the optimal value of the parameter is reduced by a factor of 100. Therefore, if an initial range of 0.5 to 2.5 s is specified for the mean headway (a range of 2.0 s), this range will be reduced to 0.2 s after 10 iterations of the Golden Section Method. The user should obtain the optimal value of the mean headway to within ± 0.1 s.

D.2 Simple Two-Parameter Search Algorithm

In the case where two model parameters are to be optimized, a contour plot approach to identifying the optimal values of the parameters can be used. One first identifies the acceptable ranges of the two parameters and then exercises the model for pairs of values of the parameters. The squared error is computed for each pair of parameter values and is plotted in a contour plot to identify the value pairs that result in the lowest squared error. An example of this approach is shown in Figure 17 for optimizing the mean headway and mean reaction time parameters. The search starts with the default values, blankets the region with a series of tests of different values, and then focuses in more detail on the solution area.

Figure 17. Example contour plot of the squared error. Graph. This graph charts Mean Reaction Time on the horizontal axis and Mean Headway on the vertical axis. Two default lines extend from the centers of each axis and intersect, forming four quadrants within the graph. An Optimal Headway line extends from the vertical axis, beginning just below the default line, and an Optimal Reaction Time line extends from the horizontal axis, beginning about halfway between the default line and the end of the graph. These two lines intersect in the lower right quadrant, at a coordinate labeled 0.5, representing the lowest value of squared error. Three increasingly larger elliptical circles extend out from this coordinate. There is a note on the bottom of the graph that reads Contours equal Squared Error times 10 to the fifth power.

Figure 17. Example contour plot of the squared error.

D.3 Dual-Objective, Two-Parameter Search Algorithm69

This section addresses the case where the analyst wishes to consider two model calibration objectives separately, rather than as the weighted sum of the squared errors (single objective) discussed above. The analyst in this case can use a variation of the two-dimensional search algorithm identified above with up to two parameters. Instead of plotting a single set of contour lines for the squared error, the analyst plots two sets of contour lines (one set for each objective) for each pair of parameters. The analyst then visually identifies the acceptable solution range where both objectives are satisfied to the extent feasible. The following example illustrates this algorithm.

The analyst has identified the following two objectives for the model calibration:

Figure 18 shows how changing the mean headway and the mean reaction time changes the values of these two objectives (speed and capacity). The solution region shows the pairs of values of mean headway and mean reaction time that meet both objectives.

Figure 18. Dual-objective, dual-parameter search. This figure shows the case where two model calibration objectives are considered separately. Instead of plotting a single set of contour lines for the squared error, two sets of contour lines (one set for each objective) are plotted for each pair of parameters. The example in this figure shows how changing the mean headway and the mean reaction time changes the values of these two objectives (speed and capacity).

Note: vphl = vehicles per hour per lane

Metric conversion: 1 mi/h = 1.61 km/h

Figure 18. Dual-objective, dual-parameter search.

Table of Contents | List of Tables | List of Figures | Top of Section | Previous Section | Next Section | HOME

FHWA Home
FHWA
Federal Highway Administration - United States Department of Transportation