Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem

Abstract

The maximum diversity problem (MDP) aims to select a subset with a predetermined number of elements from a given set, maximizing the diversity among them. This NP-hard problem requires efficient algorithms that can generate high-quality solutions within reasonable computational time. In this study, we propose a novel approach that combines the biased random-key genetic algorithm (BRKGA) with local search to tackle the MDP. Our computational study utilizes a comprehensive set of MDPLib instances, and demonstrates the superior average performance of our proposed algorithm compared to existing literature results. The MDP has a wide range of practical applications, including biology, ecology, and management. We provide future research directions for improving the algorithm’s performance and exploring its applicability in real-world scenarios.

1. Introduction

The maximum diversity problem (MDP) represents a significant challenge in the field of optimization, which involves the selection of a subset M, including elements of maximum diversity, from a greater set N [1]. This diversity is calculated as the sum of diversities between all possible pairs of elements belonging to M, typically defined through a distance metric based on the specific attributes of the elements belonging to N.

The concept of maximizing diversity was first introduced in 1977 [2]. This groundbreaking work proposed and evaluated a heuristic, using data from a genetic resource selection program. The formulation of the MDP was subsequently refined and presented in mathematical terms in 1993, affirming the problem’s NP-hard status [3].

The MDP has a wide range of practical applications across various fields, including resource management, project group formation [4,5], biological diversity conservation [6], and the establishment of ecological preserves [7]. This multitude of applications highlights the MDP’s versatility and its broad relevance.

Central to the MDP is a diversity index that captures the dissimilarity or distance between two elements. Common metrics—such as Euclidean, Manhattan, and Hamming distances—are often used, depending on the specific attributes and nature of the elements in set N [8]. Given the NP-hard nature of the MDP [3], it is vital to employ algorithms that can deliver effective solutions within a feasible computational time.

Metaheuristics, which guide heuristics towards feasible solutions to specific problems, are widely used for obtaining effective solutions. Among them, we can mention the evolutionary algorithms, which are particularly prominent [9], with genetic algorithms standing out [10,11].

A plethora of research addressing the MDP has been published since its inception, employing a host of methodologies. This research includes various metaheuristics, such as the greedy randomized adaptive search procedure [12,13,14,15,16], tabu search [16,17,18,19], variable neighborhood search [20,21], and neural networks [22]. A comprehensive comparative analysis of all the heuristics and metaheuristics proposed for the MDP up to 2012 was compiled in [23]. More recently, a review focusing on discrete diversity and dispersion maximization from an operational research perspective illuminated the latest developments and approaches in this area [24].

Among the various metaheuristic methodologies, the biased random-key genetic algorithm (BRKGA) [25] has garnered interest, due to its effectiveness in solving discrete and global optimization problems. The BRKGA is an extension of the random-key genetic algorithm [26], incorporating modifications to the parent selection process for crossover and implementation. Notably, the application of the BRKGA has been adapted to address the MDP [27,28,29].

The main objective of the present investigation is to propose a new approach, based on the BRKGA, for tackling the MDP. While existing algorithms offer viable solutions, they often face challenges, regarding computational efficiency and the balance between exploration and exploitation. Specifically, these algorithms may struggle with large problem instances, or they may not consistently produce high-quality solutions, which are limitations. Our BRKGA with local search (BRKGALS) aims to overcome these limitations, by integrating a metaheuristic that uses local search to refine the solutions produced by the algorithm, thereby enhancing the solution quality while maintaining computational feasibility. The motivation behind our approach is to contribute to ongoing efforts to find more efficient and effective solutions for the MDP. In this process, we conduct an extensive computational study, using a wide range of instances from MDPLib, a highly regarded and commonly used library for the MDP. It is important to note that while MDPLib is specific to the MDP, other general optimization problem libraries, such as OR-Library and MIPLib, may also contain instances of diversity problems. However, none of these resources provide the MDP-focused dataset that MDPLib offers. In our study, we compare the performance of the proposed algorithm to the best-known solutions in the existing literature, demonstrating its competitiveness and potential for practical applications.

The subsequent sections of this article are organized as follows. Section 2 provides definitions and discusses the state-of-the-art of the MDP. In Section 3 and Section 4, we discuss the proposed approach. Section 5 presents the computational results, whereas in Section 6, our conclusions are stated.

2. The Maximum Diversity Problem

To define the problem, consider a given set N containing n elements—that is, $N\equiv \{1,\cdots ,n\}$ —where each element is characterized by a set of attributes $T\equiv \{a_1,\cdots ,a_t\}$. The MDP can be described as an integer quadratic programming problem, considering that $x_i$, for all $i\in N$, is a binary variable equal to one if and only if element i is in the solution, that is, this element is selected to be a member of subset M, and zero otherwise. Additionally, $D=\left[d\right(i,j\left)\right]$ is an $n\times n$ array that stores the diversity indices between each pair of elements $(i,j)$ of N, that is, this array is filled such that $d(i,j)=d(j,i)$ and $d(i,i)=0$, for all $(i,j)\in N$.

Based on the earlier notations, the mathematical programming model for the MDP is stated as

$$\begin{array}{ccc}\hfill \mathrm{maximize}\{Z& =& \sum _{i=1}^{n-1}\sum _{j=i+1}^{n}d(i,j)x_i{x}_j\},\hfill \end{array}$$

(1)

$$\begin{array}{ccc}\hfill \mathrm{subject}\mathrm{to}:\sum _{i=1}^n{x}_i& =& m,\hfill \end{array}$$

(2)

$$\begin{array}{ccc}\hfill x_i& \in & \{0,1\},\forall i\in N.\hfill \end{array}$$

(3)

In the formulation described in (1)–(3), the quadratic objective function stated in (1) aims to maximize the sum of diversities of a subset M with $m<n$ elements taken from N, with the equality presented in (2) requiring that exactly m elements are in a feasible solution, and the expression given in (3) indicates that the variables of the problem must be binary.

The diversity to be maximized concerns the numerical value that corresponds to the degree of difference between the attributes of elements i and j, which can be measured, for example, by the distance between them, calculated using a certain metric. If the Euclidean distance is employed to calculate the diversity index, $d(i,j)$ is computed as

$$d(i,j)=\sqrt{\sum _{k=1}^t{(a_{ik}-a_{jk})}^2},(i,j)\in N,$$

where $a_{ik}$ is the value of attribute $k\in T$ for element $i\in N$ and $d(i,j)$ denotes the diversity index between elements i and j, for $i\ne j$.

3. The BRKGA Metaheuristic

The BRKGA is a metaheuristic for solving discrete and global optimization problems, as proposed in [25]. The BRKGA is a variation of the random-key genetic algorithm (RKGA) developed in [26]. Both algorithms represent solutions as vectors of random keys, where each key is a real number generated in the continuous range $[0,1)$. Also, both algorithms are of general purpose and the aspects of the problem to be addressed are brought out through a special purpose algorithm called a decoder, which maps a vector of random keys into a solution of the problem, and calculates the objective function. The distinction between the functioning of BRKGA, RKGA and the obtaining of their solutions for optimizing the problem being addressed are stated as indicated below.

The BRKGA considers a population with p individuals, each represented by a chromosome. A chromosome is formed by genes, and has a fitness value corresponding to the objective function value relative to the problem being solved. A chromosome is a vector of random keys, where each allele, representing the value contained in a gene, is randomly generated in the continuous range $[0,1)$. In the initialization phase of the BRKGA (similar to the RKGA), an initial population is created, and the fitness of each chromosome is calculated by the decoder. The population is then divided into $p_{\mathrm{e}}$ elite individuals with the best fitness, and $p-p_{\mathrm{e}}$ non-elite individuals, where $p_{\mathrm{e}}<p-p_{\mathrm{e}}$. The algorithm evolves its individuals over a number of iterations called generations. There are three mechanisms in the process of evolution:

(i)

Elitism: The BRKGA, like the RKGA, copies all $p_{\mathrm{e}}$ elite individuals from the qth generation to the $(q+1)$th generation, which ensures that there is never a deterioration in the best solution from one generation to the next.

(ii)

Mutation: A small number of mutant individuals, $p_{\mathrm{m}}$ namely, is introduced into the population of the next generation. A mutant is a new vector of random keys, which follows the same creation process as the individuals in the initial population.

(iii)

Crossover: The crossover operation produces the remaining $p-p_{\mathrm{e}}-p_{\mathrm{m}}$ individuals in the population for the $(q+1)$th generation.

The BRKGA differs from the RKGA in the way that parents are selected for mating. In the RKGA, two parents are randomly selected from the entire population to produce offspring. In the BRKGA, a biased selection of parents is performed, with each new individual being generated by combining a parent selected from the elite individuals, and a second parent being selected from the non-elite individuals (or the entire population, in some cases). Thus, for each allele of a chromosome with n genes (that is, for $i\in \{1,\cdots ,n\}$), the ith allele of the descendant will be the ith allele of the elite parent with probability ${\rho }_{\mathrm{e}}$, and the ith allele of the non-elite parent with probability $1-{\rho }_{\mathrm{e}}$. The fitness of the generated chromosomes is then calculated, and a new iteration is started.

4. The Proposed BRKGA for the MDP

Several application programming interfaces (APIs) are available for the implementation of the BRKGA. An open-source API implemented in C++ was proposed in [30]. This API can be secured from http://mauricio.resende.info/src/brkgaAPI/ (accessed on 2 July 2023) and enables the parallelization of certain operations, such as solution decoding and independent evolution of multiple populations, with inter-population solution exchange. For the present study, we choose to use the aforementioned API [30] due to its capabilities, which is fitted to our needs. Alternative APIs exist like the JAMES framework (a Java-based platform that is a distributed evolutionary algorithm implemented in Python) may be considered for other specific use cases.

We propose an implementation of the BRKGA tailored to the MDP, utilizing the chosen API. The proposed decoding algorithm transforms a method’s solution into an MDP solution, by sorting the vector of random keys of n positions, and selecting the first m indices to form the solution. As illustrated in Figure 1 provides a decoding example showing the transformation process of a random key vector into an MDP solution. In this example, the vector of random keys corresponds to a new auxiliary vector constructed with sorted keys, preserving the indices. In the example, $N\equiv \{0,1,2,3,4,5,6,7\}$ and the MDP solution becomes $M\equiv \{0,3,7,4,1\}$.

The solution set M ($M\subseteq N$), obtained from the decoding process, is evaluated using the objective function given by

$$\mathrm{fitness}=\sum _{i=1}^{m-1}\sum _{j=i}^{m}d(i,j).$$

A key problem with the BRKGA is its inherent lack of guarantee that the solutions generated during the evolution process correspond to local optima. To address this problem, we perform a local search, at the end of each generation, to attain the best solution found so far.

To maintain the integrity of the method’s operation, the solution derived from the local search is not included in the subsequent generation of the BRKGA. Instead, this is stored separately as the best solution, if its objective function value surpasses that of the current best solution. In our implementation, the local search algorithm, based on [12], is modified into an improvement-first version. We consider two elements, $i\in M$ and $j\in N-M$, and calculate $\Delta z(i,j)={\sum }_{u\in M-i}d(j,u)-d(i,u)$, which represents the improvement due to swapping i and j. The search terminates if $\Delta z⩽0$, for every i and j. Otherwise, for each pair of elements i and j, if $\Delta z>0$, we perform the swap, and then restarts the local search using the resultant solution.

The distinguishing characteristic of the BRKGA, when compared to the RKGA, lies in the bias introduced in the parent selection process for crossover. This bias drives the evolution process towards solutions with better fitness values, thereby leading to a more effective exploration and exploitation of the search space. The diagram in Figure 2 provides an overview of the entire process followed in our proposed BRKGA for MDP.

5. Computational Results

Our proposed algorithm, denoted by the BRKGALS, was implemented using the C++ language, and compiled in GCC, version 8.2.0, using the -fopenmp option to enable parallel API processing. The tests were performed on a computer Intel i7-4770 with 3.4 GHz and eight cores for processing, and with 16 GB of RAM, running Ubuntu 18.10.

Our experimental setup to evaluate the performance of the BRKGALS was carefully chosen. We used 100 instances of medium and large sets from MDPLib, known as the MDG dataset, in which arrays of real numbers were randomly generated within the range 0–10 of a uniform distribution. The instances fell into three categories:

• MDG-a: A set of 40 matrices was generated as in [16], 20 of which had dimensions n = 500 and $m=50$, while the remaining 20 had dimensions $n=2000$ and $m=200$.
• MDG-b: Mirroring MDG-a, once again a set of 40 matrices was generated according to [16], with 20 matrices of $n=500,m=50$, and the other 20 matrices featuring dimensions $n=2000,m=200$.
• MDG-c: A set of 20 matrices was generated in [23], with $n=3000$ and $m\in \{300,400,500,600\}$.

For evaluation purposes, the results obtained by the BRKGALS were compared to the best results known in the literature [31], and to two implementations of the BRKGA for the MDP: BRKGAAM [27] and BRKGAPDM [28]. According to the experiments conducted in [28], we used the maximum number of generations without improvement, $G=500$, and the maximum processing time, $\mathrm{MaxTime}=7200$ s (approximately 2 h), as the stopping criteria for the BRKGALS. In addition, we adopted the same (tuned) indicators, as reported in

Table 1. Value of the listed indicator.

Indicator	Value
Population size (p)	150
Number of elite individuals ($p_{\mathrm{e}}$)	$0.2p$
Number of mutant individuals ($p_{\mathrm{m}}$)	$0.2p$
Probability of offspring inheriting allele from elite parent (${\rho }_{\mathrm{e}}$)	$0.75$
Number of populations (K)	3

.

To ascertain the robustness and performance of the proposed algorithm, we ran the BRKGALS 10 times for each instance, using different seeds of random numbers. The results obtained are reported in

Table 2. Values of the indicated method for MDG-a instances ($n=500,m=50$), in terms of deviations (in %).

MDG	BRKGALS	BRKGAM	BRKGAPDM	Target
a-1	0.00	0.68	0.00	7833.83
a-2	0.00	0.80	0.28	7771.66
a-3	0.12	0.65	0.19	7759.36
a-4	0.00	1.07	0.07	7770.24
a-5	0.00	1.05	0.09	7755.23
a-6	0.14	0.43	0.00	7773.71
a-7	0.00	0.56	0.00	7771.73
a-8	0.12	0.44	0.15	7750.88
a-9	0.00	0.45	0.16	7770.07
a-10	0.02	0.80	0.02	7780.35
a-11	0.14	0.96	0.13	7770.95
a-12	0.00	0.57	0.09	7757.65
a-13	0.06	1.25	0.22	7798.43
a-14	0.05	0.56	0.00	7795.63
a-15	0.00	0.84	0.30	7736.84
a-16	0.07	0.52	0.27	7792.77
a-17	0.02	1.27	0.00	7787.20
a-18	0.04	0.70	0.00	7756.26
a-19	0.06	1.01	0.14	7755.41
a-20	0.13	0.63	0.14	7733.86

and

Table 3. Values of the indicated method for MDG-a instances ($n=2000,m=200$), in terms of deviations (in %).

MDG	BRKGALS	BRKGAM	BRKGAPDM	Target
a-21	0.42	1.17	0.51	114,259.00
a-22	0.48	1.39	0.58	114,327.00
a-23	0.32	1.11	0.54	114,123.00
a-24	0.33	1.21	0.53	114,040.00
a-25	0.33	1.04	0.48	114,064.00
a-26	0.23	1.06	0.33	114,204.00
a-27	0.38	1.35	0.70	114,338.00
a-28	0.33	1.30	0.48	114,158.00
a-29	0.15	1.28	0.34	114,132.00
a-30	0.33	1.31	0.39	114,197.00
a-31	0.39	1.16	0.45	114,139.00
a-32	0.38	0.96	0.52	114,092.00
a-33	0.27	1.37	0.57	114,124.00
a-34	0.43	1.06	0.83	114,203.00
a-35	0.31	1.08	0.51	114,180.00
a-36	0.29	1.28	0.61	114,252.00
a-37	0.38	1.13	0.49	114,213.00
a-38	0.20	1.15	0.27	114,378.00
a-39	0.27	1.46	0.52	114,201.00
a-40	0.27	1.17	0.23	114,191.00

, for instances of type MDG-a with $n=500$ and $m=50$, and for instances of $n=2000$ and $m=200$, respectively. For each instance identified in the first column, the second column presents the percentage difference given by

$$\mathrm{Deviation}=\frac{(S_{\mathrm{BRKGALS}}-S_{\mathrm{best}})}{S_{\mathrm{best}}}\times 100,$$

where $S_{\mathrm{BRKGALS}}$ was the best solution obtained from 10 runs of the proposed algorithm, and $S_{\mathrm{best}}$ was the best solution known in the literature, that is, the target presented in the fifth columns of Table 2 and Table 3. The third (BRKGAM) and fourth (BRKAPDM) columns of these tables reproduce the percentage differences presented in [27,28], respectively.

In our analysis of the results, we observe that the proposed algorithm demonstrated superior average performance compared to the others. The mean deviations for the BRKGALS, BRKGAM, and BRKGAPDM methods with larger instances, that is, $n=2000$ and $m=200$, were 0.33, 0.50, and 1.19, respectively. Regarding the computational time, the MDG-a instances, that is, $n=500$ and $m=50$, had an average execution time of about 82 s. As expected, for larger instances, the average time was greater and approximately 7200 s, with the maximum time being determined as the stopping criteria. Figure 3 and Figure 4 further complement these findings, showcasing the performance of the algorithms over time. In the figures, the symbols + and X are the values achieved by the BRKGAPDM and BRKGAM methods, respectively, as reported in [27,28].

In the other instances, the proposed algorithm preserved its ability to obtain higher-quality solutions for the MDP, in comparison to those found in the literature.

Table 4. Average of the percentage differences in % for the instances of type MDG-b.

Method	n	m	Average
BRKGALS	500	50	0.04
BRKGAPDM	500	50	0.05
BRKGAM	500	50	0.55
BRKGALS	2000	200	0.32
BRKGAPDM	2000	200	0.51
BRKGAM	2000	200	1.14

and

Table 5. Average of the percentage differences in % for the instances of type MDG-c.

Method	n	m	Average
BRKGALS	3000	300	0.31
BRKGAPDM	3000	300	0.43
BRKGALS	3000	400	0.28
BRKGAPDM	3000	400	0.44
BRKGALS	3000	500	0.20
BRKGAPDM	3000	500	0.31
BRKGALS	3000	600	0.20
BRKGAPDM	3000	600	0.31

present the averages of the percentage differences of the proposed algorithm and those in the literature for medium-sized and large-sized instances of the type MDG-b and MDG-c, respectively. In Table 5, the comparison does not include BRKGAAM, as we did not have execution information for this set of instances. Regarding the computational time, the MDG-b instances $n=500$ and $m=50$ had an average execution time of approximately 131 s. Larger instances, that is, MDG-b with n = 2000 and $m=200$, and MDG-c with $n=3000,m=300,400,500,600$, presented an average time of approximately 7200 s, which was the maximum time determined as stopping criterion. With these results, we can conclude that our proposed algorithm, the BRKGALS, demonstrated robust and superior performance compared to the other algorithms, providing a promising alternative for handling instances of the MDG problem, that is, from MDPLib.

6. Conclusions

In this study, we introduced the BRKGALS, a hybrid algorithm that amalgamates the BRKGA metaheuristic with a local search approach, to solve the MDP. The experimental results provided strong evidence of the BRKGALS’s superior performance and efficacy compared to other algorithms presented in the literature.

The computational experiments carried out on the MDG dataset, comprising both medium and large instances, highlighted the robustness and high-quality solution capacity of the BRKGALS. This new algorithm consistently surpassed existing algorithms, such as the BRKGAPDM and BRKGAM, achieving smaller deviations from the best-known solutions.

For MDG-a instances with $n=500$ and $m=50$, the BRKGALS recorded average percentage differences between 0.00% and 0.14%, when compared to the best-known solutions. For larger MDG-a instances, that is, $n=2000$ and $m=200$, the proposed algorithm demonstrated remarkable performance, with average percentage differences spanning 0.23% to 0.48%. These outcomes validate the consistency of the BRKGALS in generating high-quality solutions, even for larger instances.

The average percentage differences for MDG-b and MDG-c instances, presented in Table 4 and Table 5, respectively, further illustrated the supremacy of the BRKGALS in deriving high-quality solutions across varying instance sizes and characteristics. The achieved average percentage differences varied from 0.04% to 0.32% for MDG-b instances, and from 0.20% to 0.31% for MDG-c instances, showcasing the reliability and efficacy of the BRKGALS.

In summation, the experimental results unequivocally position the BRKGALS as a preeminent algorithm for the MDP, in terms of solution quality. Its impressive ability to generate solutions proximate to the optimal ones validates the practical applicability of the hybrid approach that combines the BRKGA with local search. Additionally, our findings suggest several exciting prospects for future research, including exploration of parameter tuning techniques, code optimization, and investigating the integration of local search solutions into the BRKGA metaheuristic.

While our study utilized randomly generated datasets from MDPLib, the potential application of the BRKGALS in real-world scenarios is a promising avenue for further investigation. Note that evaluating its performance against techniques other than the BRKGA could offer a broader understanding of its effectiveness in resolving the MDP.

In conclusion, the BRKGALS emerges as a potent and efficacious algorithm, with which to tackle the maximum diversity problem’s challenges, and its exceptional performance paves the way for new advancements in this research domain.