The use of Genetic Algorithms to optimise strategies for the detection in lymph nodes of metastatic spread

Pradhan M 1 and Farshid G 2

1 Health Informatics, Faculty of Health Sciences, University of Adelaide , South Australia 5000

2 Dept. of Pathology, University of Adelaide , South Australia 5000 and IMVS, South Australia

Breast cancer is one of the most common tumours in women. In these patients, the spread of the disease to the axillary lymph nodes is a predictor of patient outcome and an important factor in treatment selection. To determine if breast cancer has spread to the axillary lymph, the nodes are removed surgically and undergo pathological examination. Clearance of the axillary lymph nodes in breast cancer patients is associated with significant complications. A promising new alternative to axillary surgery is sentinel node biopsy that uses the microscopic examination of one special axillary node, called the sentinel node, to predict the likelihood of presence of cancer in the remaining nodes. The importance of metastasis detection in the sentinel node has motivated consideration of pathology examination methods to improve the detection rate over current practice. We have developed a mathematical model of metastatic spread in the sentinel lymph node that we use to calculate the probability of tumour detection and the cost of pathology examination. This model allows us to compare different pathology examination policies. To find the best policies we have integrated the mathematical model with Genetic Algorithms (GAs). GAs use stochastic sampling to test a wide range of possible examination options. We demonstrate the use of GAs for policy optimisation and discuss the results of the optimisation process in for pathological examination of sentinel nodes.

Finding the best policy for sentinel lymph node examination

Healthcare policy is a balancing act between the allocation of scarce resources and maximising patient benefit. The particular balancing act that we are concerned with is the question of how to maximise the detection during pathology examination of breast cancer metastasis in axillary lymph nodes. In this work we use a mathematical model of metastatic spread in a lymph node and Genetic Algorithms (GAs) to find the most cost-effective policy for pathology examination.

Breast cancer is a major cause of premature death in women. The status of the axillary lymph nodes is one of the most powerful predictors of outcome for these patients and the number of involved nodes also influences further treatment choices including chemotherapy and radiation therapy to the axilla [1, 2] . In addition to breast surgery for local control, axillary surgery is central to the treatment of this disease. Unfortunately, axillary surgery has significant long-term complications including chronic lymphedema, long term pain, shoulder stiffness and the risk of development of angiosarcoma [3] . The most promising new alternative to axillary surgery is sentinel node biopsy that uses the microscopic examination of one special axillary node, called the sentinel node, to predict the likelihood of presence of cancer in the remaining nodes [4, 5] . Thus patients whose sentinel nodes are uninvolved may avoid axillary surgery and its unpleasant side effects.

The implementation of sentinel node biopsy is hindered currently by the imprecision of methods used to examine the sentinel node [4, 6, 7] . In regular axillary chain dissection, each lymph node is examined histologically by a single cut through the node. In the era of sentinel node biopsy, the state of the whole axillary basin is determined by the examination of a single node. Obviously, a single cut through the node has less chance of detecting the presence of tumour than a more thorough examination ( Figure 1 ).

If pathology laboratories increase the number of sections taken in lymph node examinations they face increased costs through materials, technician time, and pathologist time. Until now there has not been a way to evaluate formally the potential benefit of competing sectioning strategies for sentinel nodes. We have developed a mathematical model of metastatic spread in a sentinel node that we use to assess cost-benefit of pathology examination strategies [8] . For a given pathology examination strategy the model calculates the probability of tumour detection and the cost of the strategy. The model uses data from a database of 120 sentinel nodes in breast cancer patients [9] .

Figure 1 . The effect of sampling strategy on the likelihood of detecting nodal micrometastases.

In (A), a SN is bisected and one slice is processed. Only one section is examined histologically; the metastasis has a high chance of being missed. In (B), the node is first sliced fine, all the slices are submitted for processing and multiple sections are examined histologically. The probability of identifying the micrometastasis improves, but the cost of processing and examination increases. (Adapted from Friedman, S. et al . Acta Oncol 27, 483-487 1988).

While our mathematical model allows us to determine a cost and probability of tumour detection for a specific pathological examination strategy, we wanted to explore a large number of potential strategies to assess which was the best to implement. In this paper we describe the use of GAs to search for optimal tumour detection strategies. We describe how constraints on cost are modelled in GAs, and how we may use techniques from another heuristic search method, that of simulated annealing, to improve strategy selection in GAs. This work is not a theoretical treatment of GAs or of optimisation. Rather, we introduce these areas of research, and demonstrate empirical results based on the optimisation task we wish to solve.

Genetic algorithms for policy optimisation

The task of selecting the 'best' pathological examination strategy for sentinel node biopsy is made difficult because of the large number of potential options we have. The process of pathology examination begins when a pathologist cuts, or grosses , a lymph node. The lymph node is then fixed and multiple levels, or sections , are taken. Sections may be taken 'through the block' at regular intervals, or a set number of sections can be cut at specified intervals. Table 1 describes the variety of options that we must investigate. Note that the parameters we have to set for a strategy include categorical variables (bisection or uniform) and continuous variables (the section interval).

Table 1 . Options for strategy selection in the pathology examination of sentinel nodes.

The field of optimisation is concerned with techniques that attempt to find the optimal-or near optimal-solution for problems in which exhaustive examination of all options is infeasible. The range of all possible combinations of the parameters in a problem is often called the hypothesis state or state space . In many real-world problems the state space grows exponentially with the number of parameters. We can frame optimisation as a search through the state space for the optimal solution. In our case, we seek a pathological examination strategy that maximised the ratio of probability of tumour detection to cost of examination. Because we cannot hope to examine every possible potential strategy we are limited to finding a range of good strategies, and if we are lucky we will find the 'best' strategy, but we have not guarantee of doing so. (Please refer to the Appendix for a brief tutorial introduction to optimisation.)

Central to optimisation methods is an objective function such that , where is a vector of input parameters. The objective function evaluates the quality of a potential solution. In the case of sentinel node examination strategies, the objective function is the mathematical model of metastatic spread in lymph nodes. The task of the optimisation algorithm is to find the combination of parameters listed in Table 1 that maximise the probability/cost ratio.

T raditional numerical optimisation techniques require that problems be represented under certain regularity conditions, such as continuous, differentiable parameters [10] . Because the sentinel node model includes both continuous and categorical variables we are not able to use numerical optimisation methods. GAs belong to a class of optimisation techniques called 'stochastic sampling methods'. Unlike gradient methods, stochastic methods do not make assumptions about the nature of the objective function (e.g. that it is differentiable). Stochastic sampling methods select potential configurations at random, and then attempt to improve upon configurations that are most likely to yield an optimal solution. The development of GAs was motivated by biological evolution [11, 12] , in particular, GAs utilise a 'survival of the fittest' analogy to promote potentially good strategies. A general GA is as follows:

• A GA begins by creating a population of candidate solutions.
• Each member of the population is evaluated by an objective function to assess its 'fitness'.
• A new generation of the population is created using 3 operators:
• Selection . A certain number of individuals are selected to the new generation. The probability that an individual is selected depends on its fitness.
• Crossover . Pairs of individuals are selected, based on their fitness, to produce two offspring by applying the crossover operator. Both offspring are in the new generation.
• Mutation . Individuals are chosen at random to undergo mutation, which changes bits in the gene representation.
• The new generation is evaluated using the objective (fitness) function, and a new generation is generated as described in step 3.

The process stops when the best solution (fittest individual) does not improve, or the algorithm reaches a predetermined number of generations. There are innumerable variations to the basic algorithm described above.

Method

We have implemented the sentinel node mathematical model as approximately 200 lines of Matlab code [13] . We used GAOT, a well-tested implementation of GAs in Matlab [14] . To incorporate our model into GAOT we created a representation of a pathological examination strategy as a 'genetic string'. GAs use the genetic operators on the string representation to generate and test new examination strategies. We coded each parameter in Table 1 as a 'gene' in the string. An objective function was created that took as input a string, decoded the parameters and evaluated the strategy using the sentinel node mathematical model. The mathematical model returns two parameters: (1) the probability of detecting a tumour of a set size ( T ) in a lymph node of specified dimensions ( N ); and (2) the cost of the strategy which takes into account the best orientation to take gross levels, the number of cassettes required to fix the levels, and the time required to process and examine the lymph node specimens. For a strategy i the objective function returns a fitness score, , of the ratio

.

We normalised the raw ratio by this theoretical maximum so the fitness score lies between 0 and 1, . We created at random an initial population of 100 members and ran the GAs for 200 generations.

Parameters of the experiment

The average size of sentinel nodes in the database was 8.47 mm x 5.14 mm. To find an optimal strategy that was effective across a wide variety of node sizes, we modified the objective function to return the average for a range of node sizes from 4 mm in length to 10 mm in length in 2 mm intervals. Thus, the mathematical model was evaluated four times for every strategy under consideration.

The size of the tumour to be detected was set at 50 microns. Even at this small size there is evidence that the presence of micrometastases in the axillary lymph nodes is an indicator of poor survival in women with breast cancer [15] . The probability of tumour detection assumes that the examining pathologist will detect the tumour if it appears on the slide.

We ran the experiments in two separate trials. The first trial used GAOT's default parameters for crossover and mutation rates. In the second set of runs we increased the rate of crossover and mutation to create a more diverse population.

Representing constraints

So our results would be useful in reality, we wanted to model the constraints on reimbursement for histology examination. We required that the cost for any strategy should be under some maximum dollar limit. In GAs there are several ways to model constraints:

•  The genetic operators can be modified to create new members of the population that do not fall outside of our constraints.

•  Choose a string representation that forces the constraint.

•  Assign a low fitness score to any member that falls outside of the constraints.

For the purposes of this experiment we chose method (3) because this did not require us to make modifications to GAOT. The disadvantage of this approach is that a certain percentage of the population are 'wasted' because they do not fit into the constraints.

Genetic annealing

In an attempt to extend local search around potential candidates we borrowed from simulated annealing (SA) the concept of an annealing schedule. As the number of generations increased we reduced the rate of random mutation and the removal of high scoring candidates. (Please refer to the Appendix for an introduction to simulated annealing)

Results

In both trials initial populations were generated at random and evolved using GAOT. In trial 1 we used GAOT's default default parameters for mutation and crossover for 200 generations. In trial 2 we increased the mutation and crossover rates and ran the GAs for 100 generations. The tumour size was kept constant at 50 microns.

Table 2 shows the difference in the 'best' strategies discovered in the two trials (here applied to an 'average' sentinel node).

Table 2 . Results of GA runs for policies under $100.

The probability of detection and cost of the strategies assume an 'average' sized sentinel node 8.47 mm x 5.17 mm.

In trial 1 we noticed that the population converged very quickly and the population became homogenous. This is one of the documented problems with the GA technique: the genes from a high scoring member of the population can quickly spread to limit the variation, and hence search, of the population gene pool. In trial 2 we still noticed rapid convergence of the best solution ( Figure 2 ), however this time we found that a number of different options were considered and there was less homogeneity in the populations. Figure 3 shows the spread of fitness scores before and after running the GAs.

Figure 2 . Convergence of the GAs.

It is worth considering the differences between the two strategies isolated as 'best' solutions in the trials (Table 2). The uniform strategy found in trial 1 has a normalised fitness score of 0.69, and the bisection strategy has a score of 0.74. Thus, the uniform strategy is a local maxima in the state space. The bisection strategy will work well with smaller nodes but will drop off in detection rate with larger nodes as more of the lymph node is left unexamined.

Figure 3 . Histograms of fitness scores for the initial and final populations.

Figure 4 demonstrates the trade-off between the uniform and bisection/serial strategies. The bisection/serial strategy sets the maximum number of levels and therefore has a constant cost. Using the uniform strategy the number of levels, and therefore the cost, will vary but the detection rate remains constant. This result implies that different examination strategies will be useful depending on the size of the sentinel lymph node. The GA runs excluded numerous uniform strategies because they tipped over $100 on the node sizes of 10mm despite promising results at sizes between 7 mm and 10 mm. It is interesting to note that the GAs found a uniform strategy that managed to sneak under the constraint at a cost of $99.17 for a 10mm node.

Figure 4 . The trade-offs between in probability and cost of bisection and uniform strategies for different node sizes.

We implemented genetic annealing by reducing the rates of mutation and crossover, and also the variance of mutation operators, with progressive generations. This experiment did not improve the search strategy of the GAs. We feel this strategy may not have had a significant effect on the search process because of the early convergence. In a gene pool with greater variation (a larger number of closely competing solutions) an annealing approach may result in focusing search around the potential solutions.

Discussion and conclusions

The results of the GAs were encouraging. We were able to use our sentinel node model as an objective function in a GA technique, we were able to represent constraints in the search operation, and we found successfully strategies that optimised the objective function. Although our current experiments are limited in the range of parameters we explored, they lay the ground for a more complete set of experiments.

While the GA framework provides us with a sophisticated and easy to use search strategy, finding the best combination of GA parameters to work well for our problem was difficult. For example, we can set both the rate and type of mutation, selection, and crossover to name a few. Because the semantics of the search operations are in the domain of GAs rather than in explicit terms of the state space, it is difficult to estimate the effects of changing these, and other, GA parameters. The GA literature is rich with variations to the basic or canonical GA (for example see www.aic.nvl.navy.mil/galist/) which can be daunting at first. Ultimately, the effective use of GAs, or any other search strategy, will rely on a good understanding of the problem domain, and a good understanding of the optimisation technique.

It is important to put this work in context. First, this work does not attempt to provide a definitive recommendation on the type of pathological examination strategy for sentinel nodes. The experiments used in this work are to demonstrate the use of GAs for policy optimisation and more work needs to be done in refining the parameters of the model. We also plan to use an improved representation of the lymph node shape in a future version of our sentinel node mathematical model. While this will improve the accuracy of tumour detection, it will also increase the time it takes to evaluate. Since the model is called many times during the GA cycle, this may dramatically increase the time it takes to run the GAs.

References

[1] C. Carter, C. Allen, and D. Henson, "Relation of tumour size, lymph nodes status and survival in 24,740 breast cancer cases.," Cancer , vol. 63, pp. 181-187, 1989.

[2] E. Fisher and e. al, "Pathologic Findings from the National Surgical Adjuvant Breast Project Protocol B-06," Cancer , vol. 71, pp. 2507-2514., 1993.

[3] J. J. Albertini, G. H. Lyman, C. Cox, T. Yeatman, L. Balducci, N. Ku, S. Shivers, C. Berman, K. Wells, D. Rapaport, A. Shons, J. Horton, H. Greenberg, S. Nicosia, R. Clark, A. Cantor, and D. S. Reintgen, "Lymphatic mapping and sentinel node biopsy in the patient with breast cancer," Jama , vol. 276, pp. 1818-22 Issn: 0098-7484, 1996.

[4] A. E. Giuliano, "Lymphatic mapping and sentinel node biopsy in breast cancer," Jama , vol. 277, pp. 791-2 Issn: 0098-7484, 1997.

[5] U. Veronesi, G. Paganelli, V. Galimberti, G. Viale, S. Zurrida, M. Bedoni, A. Costa, C. de Cicco, J. G. Geraghty, A. Luini, V. Sacchini, and P. Veronesi, "Sentinel-node biopsy to avoid axillary dissection in breast cancer with clinically negative lymph-nodes," Lancet , vol. 349, pp. 1864-7 Issn: 0140-6736, 1997.

[6] D. Folscher, G. Langman, E. Panieri, D. Theunissen, and D. Dent, "Sentinel axillary lymph node biopsy: helpful in axillary management in patients with breast cancer?," Br J Surg , vol. 84, pp. 1586 (Abstract), 1997.

[7] M. Flett, P. Stanton, and C. TG, "Lymphatic mapping and sentinel node biopsy in breast cancer.," Br J Surg , vol. 85, pp. 991-3, 1998.

[8] G. Farshid and M. Pradhan, "In Press.," , 1999.

[9] J. Kollias, P. Gill, B. Cahtterton, V. Hall, B. Coventry, and G. Farshid, "The accuracy of sentinel node biopsy in breast cancer," Medical Journal of Australia , vol. Submitted, 1999.

[10] W. Press, S. Teukolsky, W. Vetterling, and B. Flannery, Numerical Recipes . Cambridge, UK: Cambridge Press, 1992.

[11] J. H. Holland, Adaption in natural and artificial systems . Cambridge, MA: MIT Press, 1975.

[12] D. Goldberg, Genetic Algorithms in Search, Optimisation, and Machine Learning . Reading, MA: Addison-Wesley Publishers, 1989.

[13] Mathworks Inc., Matlab technical manual . New Jersey: Prentice-Hall Inc., 1997.

[14] C. Houck, J. Joines, and M. Kay, "A Genetic Algorithm for Function Optimization: A Matlab Implementation," NCSU-IE, North Carolina TR 95-09, 1995.

[15] P. P. Rosen, P. E. Saigo, D. W. Braun, Jr., E. Weathers, F. AA, and D. W. Kinne, "Axillary micro and macrometastases in breast cancer. Prognostic significance of tumour size.," Ann Surg , vol. 194, pp. 585-591, 1981.

[16] G. Rudolph, "Convergence analysis of canonical genetic algorithms," University of Dortmund, Dortmund, Germany 1994.

[17] S. Kirkpatrick, C. D. Gelatt, and M. D. Vecchi, "Optimisation by simulated annealing," Science , vol. 220, pp. 671-680, 1983.

Home > Research > Virtual Sentinel Node

© 2004 The University of Adelaide Last Modified Wednesday, 28-Jun-2006 11:32:05 CST  Health Informatics	Copyright | Privacy | Disclaimer