Genetic Algorithm

Genetic Algorithm in Health Economic Modelling

A genetic algorithm searches for good inputs or decisions by breeding many candidate answers, scoring each one with the model, and letting the better ones pass their features on to the next round. Health economists use it where a model can score a candidate but offers no formula or gradient that leads to the best one, as when unobservable natural history parameters are fitted to registry data or service capacities are tuned inside a simulation. The name refers to the biological metaphor and has nothing to do with the economics of genetic testing. It is one branch of numerical optimisation and returns the best candidate found in the time allowed, which may not be the true optimum.

A population that improves by selection and recombination

Whitley notes that only two parts of most genetic algorithms depend on the problem, the encoding and the evaluation function. The encoding turns a candidate into a string, often called a chromosome, such as a vector of 28 natural history parameters or the number of rehabilitation places in each service. The evaluation function is usually the health economic model itself, returning a goodness-of-fit score, a wait time or a net monetary benefit.

A run starts with a population of candidates, usually generated at random, and each one is evaluated. Selection then copies candidates into an intermediate population, with better candidates more likely to be copied. Crossover pairs the copies and, with probability $p_c$, swaps segments between partners to make offspring. Mutation finally alters each element of each string with a small probability $p_m$, which Whitley reports is typically below 1%. One pass through these steps is a generation, and the new population is evaluated in turn.

In the canonical algorithm the chance of being copied is proportional to fitness.

$$p_i = \frac{f_i}{\sum_{j=1}^{N} f_j}$$

where $p_i$ is the probability that candidate $i$ is chosen on each draw, $f_i$ is its evaluation score, which must not be negative, and $N$ is the population size. The expected number of copies of candidate $i$ is $N p_i$, which equals $f_i / \bar{f}$, its evaluation divided by the population mean, which Whitley calls its fitness.

Calibration minimises a lack-of-fit score, so the score has to be turned round before it can act as a fitness. In the Lung Cancer Policy Model, Kong and colleagues made the probability of reproduction proportional to the difference between a parameter set's goodness-of-fit value and the largest value among all sets tested, so the worst-fitting set could not reproduce.

$$p_i = \frac{G_{\max} - G_i}{\sum_{j=1}^{N} \left( G_{\max} - G_j \right)}$$

where $G_i$ is the goodness of fit score of parameter set $i$, lower being better, and $G_{\max}$ is the largest score among the sets tested. The same shift makes negative net monetary benefits usable as fitness values, as the worked example shows.

Diversity, selection pressure and convergence

A genetic algorithm must keep exploring while concentrating on the best areas found so far. Whitley explains that selection can drive every string to the same value at some position, and if this happens before a satisfactory solution is reached the algorithm has prematurely converged, a particular risk with small populations. Mutation is the source of renewed variation. As the population improves, the spread of fitness shrinks and selection weakens, which fitness scaling or selection by rank can partly correct.

Rudolph proved by Markov chain analysis that the canonical algorithm with mutation, crossover and proportional reproduction never converges to the global optimum, whatever the starting population, crossover operator or objective function. Variants that always keep the best solution in the population do converge to it. The result concerns the limit as generations grow without bound, so it gives no assurance about a finite run. Keeping the best candidate, known as elitism, also stops the best score from getting worse between generations.

Calibrating disease models with a genetic algorithm

Disease model calibration is one established use. Kong and colleagues calibrated 28 natural history parameters of the Lung Cancer Policy Model, a microsimulation built to evaluate screening, against 11 targets combined into a weighted sum. Their genetic algorithm used populations of 40 parameter sets, one-point crossover and mutations that drew new values within 10% of a parent's values. It stopped after 1,000 parameter sets (25 generations) or once a set fell below a preset score.

Each run simulated 500,000 people and took 24 minutes, so 1,000 runs took about 400 hours of processor time. Over 10 repeated searches, simulated annealing reached a mean best score of 86.5 against 91.3 for the genetic algorithm, a significant difference. To reach a score below 95, simulated annealing needed 202 iterations on average and the genetic algorithm 294, a difference that was not significant. With two parameters, both performed equally well. The authors judged simulated annealing the better choice for automated calibration, while noting that both were faster than a grid search, whose computing time grows exponentially with the number of parameters.

Reiker and colleagues later calibrated 23 parameters of OpenMalaria, an individual-based malaria model, to 11 epidemiological objectives. The best fit previously achieved with a genetic algorithm had a weighted loss of 63.7. Bayesian optimisation with a Gaussian process emulator reached 58.3, and the authors note that purely sampling-based methods such as genetic algorithms usually draw sparse samples near existing ones instead of predicting fit across the whole parameter space.

Searching for the best service configuration

The second use treats a simulation model as the evaluation function for a planning decision. Yan and colleagues in Alberta combined a genetic algorithm with a discrete event simulation of stroke rehabilitation. The decision variables were the capacities of inpatient rehabilitation, early supported discharge and outpatient rehabilitation, and the objective was to minimise waits for all three. Conventional search was judged not feasible, because each service's wait depends on the other two capacities and the stochastic simulation is slow.

The model predicted that waits would be close to zero if early supported discharge capacity rose to 113 patients per day (75 at the time) and outpatient capacity to 143 (101 at the time). Compared with the status quo, the configuration served more survivors and was estimated to give net savings of CAD 25.45 million a year (2019 dollars) through shorter waits in acute beds. No budget constraint was imposed, so the search answers a capacity question. Sharing out a fixed budget is a problem of constrained optimisation.

Worked example with four screening strategies

All numbers in this example are illustrative. A programme chooses a screening start age and interval, coded as a four-bit string. The first two bits give the start age (00 for 40, 01 for 45, 10 for 50, 11 for 55) and the last two give the interval (00 for one year, 01 for two, 10 for three, 11 for four). Fitness is the incremental net monetary benefit per person against no screening.

$$NMB = \lambda \, \Delta E - \Delta C$$

where $NMB$ is the incremental net monetary benefit in GBP, $\lambda$ is the value placed on a QALY, $\Delta E$ is the QALY gain per person and $\Delta C$ is the extra cost per person. The example sets $\lambda$ at GBP 25,000, the lower end of the GBP 25,000 to GBP 35,000 per QALY range in section 6.3.7 of the NICE manual (PMG36).

1. Evaluate the first generation. The four candidates give the following results.

For string 1001, 25,000 × 0.012 gives GBP 300 of health value, and subtracting the GBP 180 cost leaves an NMB of GBP 120. Annual screening from 40 has an ICER of 520 / 0.016 = GBP 32,500 per QALY against no screening, above $\lambda$, so its NMB is negative.

2. Turn NMB into fitness. Subtracting the lowest NMB (minus 120) from each gives fitness values of 220, 240, 0 and 160, which sum to 620.

3. Select. The selection probabilities are 220 / 620 = 0.355, 240 / 620 = 0.387, 0 and 160 / 620 = 0.258. With $N = 4$, the expected copies are 1.42, 1.55, 0 and 1.03, so annual screening from 40 drops out.

4. Cross over. Strings 1001 and 0110 are cut after the second bit and their tails swapped, giving 1010 (age 50, every 3 years) and 0101 (age 45, every 2 years).

5. Evaluate the offspring. String 1010 gains 0.011 QALYs (GBP 275) for GBP 130, an NMB of GBP 145. String 0101 gains 0.013 QALYs (GBP 325) for GBP 230, an NMB of GBP 95.

6. Mutate. Flipping the last bit of 1010 gives 1011 (age 50, every 4 years), with 0.008 QALYs (GBP 200) for GBP 90, an NMB of GBP 110.

7. Interpret. The best NMB in the population rose to GBP 145, against GBP 120 before, because crossover joined the start age of one good strategy to the interval of another. With only 16 possible strings every strategy could simply be evaluated, so the method earns its place only when combinations are far too many to enumerate.

Choices that change the result

Settings fixed before the search can change what it finds. Population size, $p_c$, $p_m$, the selection scheme and the stopping rule all trade breadth of search against computing time. The encoding fixes the resolution, and Whitley gives the example that 10 bits per parameter allow 1,024 discrete values. Bit patterns that decode to no legal parameter value need a rule, and one option Whitley describes is to give them a default worst-possible evaluation.

Whitley notes that if one evaluation takes an hour, 10,000 evaluations take over a year, about 50 generations of 200 strings. Microsimulation outputs also carry Monte Carlo error, so repeat runs of one candidate give different scores, and Kong and colleagues note that search results are stochastic and need statistical tests to compare.

Reading the result in an economic evaluation

A genetic algorithm returns one best candidate with no measure of its uncertainty. A single best-fitting parameter set treats calibrated values as known and leaves their parameter uncertainty out of any later probabilistic sensitivity analysis, unless several good sets are carried forward. A strategy picked from a noisy simulation can also look best by chance, so leading candidates merit rerunning with more replications.

The ISPOR Optimization Methods Emerging Good Practices Task Force describes heuristics, including genetic algorithms, as giving approximate solutions where an exact approach is unavailable or computationally expensive. Its second report asks that the optimisation methods and tools be reported and justified. For a genetic algorithm that includes the settings above and the spread of results over repeated runs.

Genetic algorithms beside other search methods

Whitley calls genetic algorithms a weak method because they assume little about the problem, and adds that where a good specialised method exists the genetic algorithm may not be the best tool. Linear and integer allocation problems have exact methods under linear programming and integer programming. Simulated annealing moves a single candidate and accepts some worse moves, and particle swarm optimisation moves a population without crossover. Wolpert and Macready's no free lunch theorems show that any gain an algorithm makes on one class of problems is offset by worse performance on another, so no search method is best for every model.

Limitations and common misreadings

A frequent misreading treats the answer as the optimum. A genetic algorithm can stall at a local optimum. Repeated runs from different random starts show how stable the answer is, as in Kong's 10 genetic algorithm searches, whose best scores ranged between 85.2 and 94.1.

Every candidate in every generation needs a full model run, which makes the method expensive. Its biological vocabulary of chromosomes, fitness and offspring adds no evidence to the model, and the result is only as good as the evaluation function and the data behind it.

Sources

• Crown W, Buyukkaramikli N, Thokala P, et al. Constrained optimization methods in health services research: an introduction. Report 1 of the ISPOR Optimization Methods Emerging Good Practices Task Force. Value in Health. 2017;20(3):310-319. https://doi.org/10.1016/j.jval.2017.01.013
• Crown W, Buyukkaramikli N, Sir MY, et al. Application of constrained optimization methods in health services research: report 2 of the ISPOR Optimization Methods Emerging Good Practices Task Force. Value in Health. 2018;21(9):1019-1028. https://doi.org/10.1016/j.jval.2018.05.003
• Kong CY, McMahon PM, Gazelle GS. Calibration of disease simulation model using an engineering approach. Value in Health. 2009;12(4):521-529. https://doi.org/10.1111/j.1524-4733.2008.00484.x
• National Institute for Health and Care Excellence. NICE technology appraisal and highly specialised technologies guidance: the manual (PMG36). Published 31 January 2022, last updated 13 October 2026. Section 6.3.7. https://www.nice.org.uk/process/pmg36
• Reiker T, Golumbeanu M, Shattock A, et al. Emulator-based Bayesian optimization for efficient multi-objective calibration of an individual-based model of malaria. Nature Communications. 2021;12:7212. https://doi.org/10.1038/s41467-021-27486-z
• Rudolph G. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks. 1994;5(1):96-101. https://doi.org/10.1109/72.265964
• Whitley D. A genetic algorithm tutorial. Statistics and Computing. 1994;4(2):65-85. https://doi.org/10.1007/BF00175354
• Wolpert DH, Macready WG. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation. 1997;1(1):67-82. https://doi.org/10.1109/4235.585893
• Yan C, McClure N, Dukelow SP, et al. Optimal planning of health services through genetic algorithm and discrete event simulation: a proposed model and its application to stroke rehabilitation care. MDM Policy and Practice. 2022;7(2):23814683221134098. https://doi.org/10.1177/23814683221134098