Keywords

1 Introduction

Cancer incidence and prevalence is continuously growing. The majority of the cancer patients is nowadays treated with radiation therapy (RT), either to kill the cancer cells or to palliate the symptoms. A technologically advanced type of RT is intensity-modulated radiation therapy (IMRT). A multileaf collimator is used in IMRT to transform the radiation beam into a number of discrete small sub-beams called beamlets. The optimal intensities of these beamlets are calculated independently, in a large-scale optimization problem called fluence map optimization (FMO) problem, leading to non-uniform radiation maps. Typically, a predefined number of non-uniform radiation maps intersects the tumor from different irradiation directions. Although non-uniform radiation maps allow, by themselves, an enhanced sparing of the neighboring healthy organs while properly irradiating the tumor with the prescribed dose, selection of appropriate irradiation directions play a decisive role on these conflicting tasks: deliver dose to the tumor while preventing (too much) dose to be deposited in the surrounding tissues. The optimal selection of beam irradiation directions, known as beam angle optimization (BAO) problem, is a very difficult optimization problem.

Two completely different mathematical formulations of the BAO problem can be found in the literature. A combinatorial formulation, widely used, considers a discrete sample of all continuous beam angle directions. This formulation leads to a NP-hard optimization problem [3]. A large number of different algorithms have been used to speed up the searches, including gradient search [7], neighborhood search [1], simulated annealing [9], response surface approaches [2], branch-and-prune [11] or hybrid approaches [4]. Iterative BAO is a successful combinatorial strategy used in practice that adds one beam at a time, sequentially, to a treatment plan, reducing the total number of possible combinations significantly [3]. Alternatively, a continuous formulation has been proposed by the authors, considering all continuous beam angle directions. This formulation leads to a highly non-convex optimization problem with many local minima on a continuous search space. Figure 1 illustrates the non-convex nature of a two-dimension BAO problem for a nasopharyngeal tumor case. Due to the curse of dimensionality, the number of local minima will increase exponentially for larger dimensions. The continuous search space of the BAO problem has been explored using derivative-free optimization frameworks [13,14,15,16].

This paper compares two of the most successful strategies used to address the continuous and the combinatorial BAO formulations: a parallel multistart derivative-free framework that explores thoroughly the BAO problem continuous search space is compared to an iterative BAO framework that would obtain a theoretical upper limit of the treatment plan quality [18]. A set of ten clinical cases of nasopharyngeal (intra-cranial) tumors treated at the Portuguese Institute of Oncology of Coimbra (IPOC) is used to test and discuss the benefits of our continuous approach against the benchmark combinatorial approach. The paper is organized as follows. In the next section we present a continuous and a combinatorial formulation of the BAO problem. In section three we describe a parallel multistart derivative-free framework for the BAO problem. Computational tests are presented in section four. In the last section we have the conclusions.

Fig. 1.
figure 1

BAO surface for a nasopharyngeal tumor case considering only two coplanar beam irradiation directions.

Full size image

2 Mathematical Formulation of the BAO Problem

The aim of BAO is to determine the best ensemble of beam angle directions to irradiate the patient. Here, coplanar beams are considered, i.e. beam directions lay on the plane of rotation of the linear accelerator around the patient that lays in a fix positioned couch. It is assumed that the treatment planner defines, a priori, the number of beam irradiation directions to be n. In order to assess the quality of an n-beam angle ensemble, \(\theta _1, \ldots , \theta _n\), the optimal value of the FMO problem obtained for that beam angle ensemble, \(f(\theta _1, \ldots , \theta _n)\), is used. A mathematical formulation for the BAO problem can then consider that the best ensemble of beam directions is obtained for the (FMO) function’s minimum:

$$\begin{aligned} \begin{array}{lll} \min &{} f(\theta _1, \ldots , \theta _n) &{} \\ &{}&{}\\ s.t. &{} \theta _1, \ldots , \theta _n \in \varTheta , &{} \text {where} \; \varTheta \; \text {is the set of all possible beam angles.} \end{array} \end{aligned}$$
(1)

For a combinatorial BAO formulation, the interval of possible gantry angles, \([0^\circ ,360^\circ [\), is discretized into evenly spaced angles. For example, for an angle increment of one degree, the set of all candidate beam angles \(\varTheta \) of Eq. (1) corresponds to the set of 360 beam angles \(\{ 0, 1, \ldots , 359 \}\). For a continuous BAO formulation, the interval of possible gantry angles \([0^\circ ,360^\circ [\) is considered. Note that the beam angle directions \(-10^\circ \) and \(350^\circ \) are the same as well as beam angle directions \(370^\circ \) and \(10^\circ \). Thus, we can consider \(\varTheta =\mathbb {R}^n\) and avoid a bounded formulation.

Regardless of using a combinatorial or a continuous BAO formulation, the quality of each beam ensemble is assessed through the FMO optimal value. The resolution of the FMO problem requires the accurate assessment of the radiation dose distribution, measured in Gray (Gy), for each irradiated structure of the patient. The volume of each structure is discretized into small volume elements called voxels. The dose is calculated for each individual voxel using the principle of superposition, i.e., adding the dose from all beamlets that reach each individual voxel. Using the superposition principle, i.e., considering the contribution of each beamlet, the dose is computed for each voxel. Typically, for a nasopharyngeal treatment plan the number of beamlets (\(N_b\)) reaches the hundreds while the number of voxels (\(N_v\)) reaches the tens of thousands. For optimization purposes, a dose matrix D is constructed considering the beamlet intensities and by indexing each column to a given beamlet and each row to a given voxel. Thus, the dose deposited in voxel i by beamlet j is stored in row i and column j of matrix D. The total dose received by voxel i is the sum of the doses of all beamlets that reach voxel i, i.e., \(\sum _{j=1}^{N_b} D_{ij} w_j\), where \(w_j\) is the intensity (or weight) of beamlet j. The main difficulty in solving the FMO problem is the dimension of the dose matrix that originates large-scale optimization problems.

Many different mathematical models and optimization procedures have been presented for the FMO problem, including linear models [17], nonlinear models [6], a priori multicriteria models [5], a posteriori multicriteria models [12], particle swarm optimization models [19] and fuzzy inference systems models [10]. Here, we use the following convex penalty function voxel-based nonlinear model [1]:

$$\begin{aligned} \begin{array}{ll} \min _w &{} \sum \limits _{i=1}^{N_v} \left[ \underline{\lambda }_i \left( T_i - \sum \limits _{j=1}^{N_b} D_{ij} w_j\right) _+^2 +\right. \left. \overline{\lambda }_i \left( \sum \limits _{j=1}^{N_b} D_{ij} w_j - T_i\right) _+^2 \right] \\ &{}\\ s.t. &{} w_j \ge 0, \; j = 1, \ldots , N_b, \end{array} \end{aligned}$$

where \(\overline{\lambda }_i\) and \(\underline{\lambda }_i\) are weights that penalize overdose and underdose of voxel i, \(T_i\) is the tolerance/prescribed dose for voxel i and \((\cdot )_+ = \max \{0,\cdot \}\). This model penalizes the square difference between the tolerance/prescribed dose and the received dose by each voxel, implying that small differences from the tolerance/prescribed dose (overdose or underdose) may be clinically tolerated while larger differences from the tolerance/prescribed dose are decreasingly accepted.

The discussion of the most appropriate FMO problem formulation/resolution to be embedded in a BAO framework is out of the scope of this study. Furthermore, the FMO model is used as a black-box function. Thus, the conclusions drawn regarding continuous or combinatorial BAO formulations/resolutions are valid regardless of the FMO formulation/resolution considered.

3 Parallel Multistart Derivative-Free Optimization Framework

The multistart strategy designed to address the continuous BAO formulation takes advantage of the peculiarities of this particular space. As the order of the irradiation directions of a beam ensemble is not important, the continuous BAO search space has symmetry features, which allows a large reduction of the space to be explored by simply keeping the beam directions sorted for each beam ensemble [16]. In order to sample this reduced search space in an appropriate manner, all possible combinations of sorted beam ensembles divided by the 4 quadrants will be considered as starting beam ensembles (iterates or points). E.g., for a continuous three-dimensional BAO search space, all possible three-beam directions distribution by the four quadrants are illustrated in Fig. 2(a). Each of these three-beam ensemble corresponds to a starting point placed in the different painted cubes illustrated in Fig. 2(b). For continuous tree-dimension BAO search space only \(\frac{1}{4}\) of the entire search space \([0,360]^3\) is explored. For n-beam angle ensembles, the total number of (hyper)cubes of the entire search space is \(4^n\) while the number of (hyper)cubes of the reduced search space, which corresponds to the number of possible distributions of n sorted beam angles by the 4 quadrants is the combination with repetition of . For continuous n-dimension BAO search space only \(\frac{1}{2^n}\) of the entire search space \([0,360]^n\) is explored.

Fig. 2.
figure 2

Three beam directions distribution by the four quadrants – (a) and the corresponding cubes in the search space \([0,360]^3\) – (b).

Full size image

After setting the starting points, \(\mathbf{x}^0_i \in [0,360]^n, i=1, \ldots , N\), one for each hypercube of the reduced search space, the objective function value is evaluated at each of these initial beam ensembles. The best solutions and corresponding objective function values found so far for each region (hypercube) are assigned to these initial points and corresponding function values: \(\mathbf{x}^*_i =\mathbf{x}^0_i, i=1, \ldots , N\); \(f^*_i =f(\mathbf{x}^0_i), i=1, \ldots , N\). A local procedure is then used to locally improve that value. Two important aspects of a parallel multistart procedure in a multi-modal search space must be cautioned. First, as different search procedures coexist in time, the same region may end up being explored by different local search procedures wasting precious computational time. In order to avoid that, each hypercube can only be explored by a single local search procedure at a time. When the outcome of different local search procedures lay in the same hypercube, only the local search yielding the iterate with lowest function value remain active. Information of the regions that have active local searches is stored using a boolean vector, \(\mathbf{Active}_{N \times 1}\), that is updated at the end of each iteration. Second, due to the highly non-convex nature of the search space, derivative-free local search algorithms are advisable. Pattern search methods (PSM) were previously selected for the resolution of the continuous BAO problem as they have the ability to avoid local entrapment and need a reduced number of function (FMO) evaluations to converge [13,14,15]. Pattern search methods as described in Rocha et al. [13,14,15] are used as local search procedure. Algorithm 1 displays the parallel multistart PSM algorithm.

figure b

4 Computational Results

A set of ten clinical examples of nasopharyngeal tumor cases already treated at IPOC were used to test the different approaches. For the nasopharyngeal tumor cases in study, two different planning target volumes (PTVs) were considered, \(PTV_{70}\) and \(PTV_{59.4}\), corresponding to two different levels of prescribed radiation doses. The organs at risk (OARs) considered were the brainstem, the spinal cord, the oral cavity and the parotid glands. OAR tolerance doses and prescribed doses for the PTVs are depicted at Table 1. The tolerance dose considered for the brainstem and the spinal cord is the maximum dose as these are serial type organs, i.e., organs whose function is jeopardized even if only a small portion is injured. The tolerance dose for the parotid glands, the larger salivary gland, and the oral cavity, that contains the remaining salivary glands, is the mean dose because the salivary glands are parallel type organs, i.e., organs whose function is not jeopardized if only a small portion is injured.

Table 1. Prescribed doses and tolerance doses for tumor volumes and OARs.
Full size table

Our tests were performed on a 2.2 Ghz Intel Xeon 8-core computer workstation with 25 GB RAM. The nonlinear convex FMO formulation (Eq. (1)) was addressed using a trust-region-reflective algorithm (fmincon) from Optimization Toolbox of MATLAB (R2016a). CERR [8] was used to import the patients’ computed tomography (CT) sets with the considered structures delineated. This freeware research software allows the computation of the necessary dosimetric data for treatment planning optimization as well as convenient visualization and analysis of the treatment plans obtained. QIB, the pencil beam algorithm of CERR, was used for dose calculations. An automated dose calculation procedure for each beam ensemble was developed instead of using the menu bar of CERR.

Typically, nasopharyngeal tumors are treated with five to nine equispaced coplanar beam ensembles. Since the importance of appropriate selection of beam directions increases for lower number of beam angles, we consider treatment plans with five coplanar beams. Thus, using the multistart PSM framework, five-beam treatment plans were obtained and denoted MultistartBAO. The initial step-size considered was \(\alpha ^0=2^5=32\) and the minimal value allowed was one, defining the stopping criteria. By choosing a power of two for initial step-size, as step-size remains the same at successful iterations and is halved at unsuccessful ones, the beam directions remain integer until the stopping criteria when the step-size becomes a rational number. Despite only integer irradiation directions are tested, it is worth to highlight that the continuous BAO space is explored which is fundamentally different from a combinatorial approach.

Iterative BAO is a successful strategy used in practice [5]. Furthermore, this strategy would obtain a theoretical upper limit of the treatment plan quality [18]. Treatment plans obtained by Wild et al. [18], called \(4\pi \) and corresponding to a theoretical upper limit of a plan’s quality, were obtained using iterative BAO considering noncoplanar beam orientations for a 5\(^\circ \) angular spacing. In this study, MultistartBAO plans were compared with five-beam treatment plans obtained using iterative BAO and denoted IterativeBAO. A discrete set of 360 beam directions, \(\{0,1,2, \ldots ,359\}\), was used by considering a one degree angular spacing. In iterative BAO, beams are added sequentially one at a time to a treatment plan. The first beam is determined by computing the optimal FMO value of all one-beam ensembles for each possible beam direction. The one-beam ensemble leading to the lowest optimal FMO value is selected. Given a beam ensemble with \(n-1\) beam irradiation directions, the next beam direction, nth, is determined by computing the optimal FMO value of all n-beam ensembles obtained by adding each of the remaining beam directions to the \(n-1\)-beam ensemble. The n-beam ensemble selected corresponds to the one yielding the lowest FMO value. Thus, obtaining a five-beam ensemble requires the computation of 360 + 359 + 358 + 357 + 356 = 1790 FMO optimal values. Nevertheless, this greedy strategy reduces the number of FMO problem resolutions compared to other combinatorial BAO approaches.

Table 2. Results of the beam angle optimization processes.
Full size table

Treatment plans obtained using optimized beam ensembles were also compared with five-beam coplanar equispaced treatment plans, denoted Equi. The objective of these comparisons is to benchmark the treatment plans with optimal beam angle ensembles with treatment plans commonly used in clinical practice. Table 2 displays the results of the BAO processes in terms of final FMO value, the measure considered for quality assessment of a beam ensemble. Compared to the FMO value of the Equi treatment plans, MultistartBAO obtained an average reduction of the FMO value of 13,4%, clearly outperforming IterativeBAO that obtained an average redution of 7,0%. Furthermore, MultistartBAO required an average of 438 function evaluations which is about four times less than the number required by IterativeBAO. Average computational time required by MultistartBAO was three hours while IterativeBAO spent an average of nine hours (also computed in parallel).

Table 3. Target coverage obtained by treatment plans.
Full size table
Table 4. OARs sparing obtained by treatment plans.
Full size table

Despite the good results in terms of optimal FMO value improvement, treatment plan’s quality can be acknowledged by different dose metrics. One of the most important target metrics is the tumor coverage, i.e. the percent of the tumor volume that receives at least 95% of the prescribed dose. Existence of coldspots, i.e. percentage of the tumor volume receiving less than 93% of the prescribed dose, and occurrence of hotspots, i.e. percentage of the tumor volume receiving more than 110% of the prescribed dose, are also metrics of interest. These three target metrics, displayed in Table 3, show that MultistartBAO outperforms both IterativeBAO and Equi treatment plans concerning tumor coverage metrics.

Metrics usually screened for OARs are mean and/or maximum doses, depending if the organ has a parallel or serial architecture, respectively. Table 4 depicts organ sparing results. For the brainstem and the spinal cord, serial organs, the maximum dose is displayed. It can be verified that treatment plans with optimized beam directions always comply with the prescribed maximum doses while Equi treatment plans fail to do so in some cases. For oral cavity and parotids, parallel organs, the mean dose is displayed. Improved sparing of oral cavity and parotids is clearly obtained by treatment plans with optimal five-beam ensembles. Compared to the Equi treatment plans, in average, MultistartBAO treatment plans achieve a mean dose irradiation reduction on the right parotid, left parotid and oral cavity of 2.1 Gy, 2.9 Gy and 2.2 Gy, respectively. Furthermore, MultistartBAO treatment plans double the mean dose irradiation reduction numbers of IterativeBAO treatment plans. Over-irradiation of salivary glands can lead to xerostomia, a common RT complication of nasopharyngeal cancer cases leading to swallow difficulties. Thus, the enhanced salivary glands sparing is of the utmost interest.

In clinical practice, results are typically judged by their dose-volume histogram (DVH). DVH are cumulative histograms that ideally would have 100% dose for the whole tumor volume dropping immediately to zero, while the curves for the remaining structures would be always zero meaning that no radiation was delivered to the healthy tissues. For illustration, DVH results for the fourth patient, a patient that obtained an average FMO value reduction, are displayed in Fig. 3. The DVH curves show enhanced tumor coverage and sparing by MultistartBAO treatment plans.

Fig. 3.
figure 3

Cumulative dose volume histogram comparing the results obtained by MultistartBAO, IterativeBAO and Equi for the fourth case.

Full size image

5 Conclusions

The BAO problem is a challenging highly non-convex optimization problem yet to be solved satisfactorily. Apart from iterative BAO, there is little or none commercial offer for beam direction selection. A parallel multistart PSM framework was presented and compared with iterative BAO using a set of clinical nasopharyngeal tumor cases. This multistart framework proved to be a competitive strategy to address the continuous BAO problem formulation. A global search scheme with a tailored sampling of the search space is combined with a procedure that locally improves the sampled ensembles. Despite the importance of the global strategy sketched, particularly for a search space with a peculiar shape due to symmetry properties, the choice of PSM, a derivative-free method, for locally improving the solutions is important to avoid local entrapment.

For the nasopharyngeal clinical cases retrospectively tested, the use of optimized directions obtained by the parallel multistart approach enhanced the quality of the treatment plans obtained. The high quality treatment plans obtained considering optimal beam ensembles were compared favorably with typical equispaced treatment plans. Furthermore, the presented multistart derivative-free framework for a continuous BAO formulation clearly outperforms an iterative approach for a combinatorial BAO formulation. Although iterative BAO reduces the number of comparisons required to achieve an improved solution compared to other combinatorial BAO approaches, it is a greedy strategy for the combinatorial BAO that truncates the search space at each iteration possibly disregarding the best ensembles with n-beam directions.

Several strategies for minimizing the number of function evaluations, and consequently decrease the computational time, were embedded in this multistart strategy including parallelization, searching in a reduced space and construction of hypercubes. In future work, further effort must be made to speed up even more this procedure maintaining the high quality results here detailed. One obvious strategy is to accelerate FMO computation as most of the BAO computational time is consumed for obtaining the optimal FMO values. Nevertheless, the computational burden of BAO will always decrease as future computer workstations will certainly become faster.