Agent-Based Models and Optimal Control in Biology: A Discrete Approach - Mathematical Concepts and Methods in Modern Biology - page 160

Exercise 5.17. What other methods besides those mentioned in this section could
be used to improve the run time of this model (i.e., to make it more computationally
efficient)?
5.7 A HEURISTIC APPROACH
In previous sections we have discussed optimal control as it relates to agent-based
models, and techniques for improving the run time of such models. In theory, the pro-
cess of finding the optimal solution requires only that we evaluate the entire solution
space and choose the solution that minimizes the cost function. In practice, however,
this remains unfeasible. For one thing, it is quite possible that the solution space is
infinite; and even if it is finite, it is often the case that there are far too many solutions
to possibly implement them all (in terms of realistic run times), even in models that
have been subjected to scaling and aggregation techniques.
For example, a discrete model of the immune system might involve many millions
of cells. Each will have its own rules describing its interaction with other cells, and
may also have many variables attributed to it. Analytic methods fail in these cases, and
exhaustive enumeration by computer is unfeasible due to the limitations of computer
processing speeds. In fact, as the processing power of computers grows, so too does
the possibility for creating models that increase in complexity, so that it is impossible
to be certain that computers will ever be able to “catch up” to the complexity of the
models.
For this reason, most of the optimization and optimal control methods currently
used in discrete modeling (and with agent-based models in particular) are in the form
of heuristic algorithms . An algorithm is a formal set of rules used in order to obtain
a solution to a problem. A heuristic algorithm is a specific type of algorithm that
conducts a “smart” search of the solution space. It may make use of certain aspects of
the problem to avoid having to search through every possible solution, or it may update
its search method based on the input it receives from previously found solutions.
These algorithms begin with a choice of control input values (i.e., full or partial
solutions) and use various methods to refine the values so as to decrease the value of
the associated cost function until no better solution can be found. While these methods
do not guarantee an optimal solution, they do provide an opportunity for analysis. In
particular, if constructed and executed correctly, they are a vast improvement upon
random searches of the solution space. One advantage to the heuristic approach is
that it can be used with virtually any model. Since heuristic algorithms rely on results
from simulation, it is not necessary to transform the model in any way in order
to implement them. They provide a “brute force” technique that, while not always
optimal, can always be used when other methods may fail. In particular, heuristic
algorithms provide a baseline for results obtained via other, more rigorous methods.
While a mathematician may be concerned with developing an algorithmic theory for
explicitly finding a true optimal solution, in practice scientists and other researchers