Gene-Similarity Normalization in a Genetic Algorithm for the Maximum k-Coverage Problem

Abstract

The maximum k-coverage problem (MKCP) is a generalized covering problem which can be solved by genetic algorithms, but their operation is impeded by redundancy in the representation of solutions to MKCP. We introduce a normalization step for candidate solutions based on distance between genes which ensures that a standard crossover such as uniform and n-point crossovers produces a feasible solution and improves the solution quality. We present results from experiments in which this normalization was applied to a single crossover operation, and also results for example MKCPs.

1. Introduction

The maximum k-coverage problem (MKCP) is regarded as a generalization of several covering problems. The problem has a range of applications in combinatorial optimization such as scheduling, circuit layout design, packing, facility location, and covering graphs by subgraphs [1,2]. Recently, besides some theoretical approaches [3,4], it has been extended to many real-world applications such as blog-watch [5], seed selection in a Web crawler [6], map-reduce [7], influence maximization in social networks [8], recommendation in e-commerce [9], sensor deployment in wireless sensor networks [10], multi-depot train driver scheduling [11], cloud computing [12], and location problem [13].

Let $A=\left(a_{ij}\right)$ be an $m\times n$ 0-1 matrix, and let $w_i$ be a weight applied to each row of A. The objective of MKCP is to choose k columns so as to maximize the sum of the weights of the rows that contain ‘1’ and are also located in one of these k columns.

This problem can be represented formally as follows:

$$\begin{array}{cc}\hfill \mathrm{maximize}& \sum _{i=1}^m{w}_i·I\left(\sum _{j=1}^n{a}_{ij}{x}_j\ge 1\right)\hfill \\ \hfill \mathrm{subject}\mathrm{to}& \sum _{j=1}^n{x}_j=k\hfill \\ & x_j\in \{0,1\},j=1,2,\dots ,n,\hfill \end{array}$$

where $I(·)$ is an indicator function ($I\left(false\right)=0$ and $I\left(true\right)=1$).

We are concerned with the case that $w_i=1$ for all i, when we say that a row is covered by the selected k columns if it contains ‘1’ which is also located in one of these columns. In this case, MKCP is to find k columns that cover as many rows as possible.

MKCP has many real-world applications. For example, MKCP can be applied to the following practical applications about museum touring [14]: Suppose that a museum can operate only k guided tour programs of visiting a set of exhibits among n possible programs due to some constraints such as operating costs. If there are m visitors and it is possible to predict whether or not each visitor i is satisfied with the experience of each program j (meaning $a_{ij}$), the problem of choosing exactly k programs to satisfy as many visitors as possible is exactly formulated as MKCP. Among the visitors, if it is preferred to satisfy specific visitors who have more importance such as VIPs, the problem can be modeled more elaborately by giving different weight ($w_i$) to each visitor i. Similarly, MKCP can be applied to other practical applications such as public safety networks and systems [15,16]. For example, we can consider a disaster management system in which n agencies are involved and m positions for Unmanned Aerial Vehicles (UAVs) are available to enable the communication between the agencies. In this situation, it can be easily investigated whether or not each agency i is covered when a UAV is placed in each position j (meaning $a_{ij}$). If only k UAVs are available for resource management, the problem of choosing exactly k positions of UAVs to cover as many agencies in the disaster area as possible can also be formulated as MKCP.

The NP-hardness of MKCP can easily be deduced from the NP-hardness of the minimum set covering problem (MSCP) [17]. Many meta-heuristics have been applied to the MSCP such as tabu search [18], genetic algorithms [19,20], particle swarm optimization [21], ant colony optimization [22], etc., but MKCP has been scarcely addressed. Some naïve greedy heuristics [1,7,23,24,25] and an improved local search [26], which do not scale well to large datasets, have been studied. To the best of our knowledge, there is only one meta-heuristic [27] that uses particle swarm optimization, applied to MKCP, and genetic algorithms have not been applied. The present authors previously conducted an initial investigation of MKCP [28], which we now extend. Because MKCP selects a fixed number of columns, the representation of solutions is simpler than it is in other covering problems, and this favors the adoption of a genetic algorithm (GA). When we apply a GA to the MKCP, it also has an interesting inherent property that each gene of a chromosome is not just a number but actually a column of a matrix, which we analyze and relate to the characteristic of its solution space. We go on to present a problem-specific normalization for use in a GA which takes account of the feasibility of solutions and improves the solution quality.

The remaining parts are organized as follows. We analyze the solution space of MKCP, and the representation of solutions in Section 2. Based on this analysis, in Section 3, we propose a normalization method for producing feasible and improved solutions. In Section 4, we present experimental results to assess the effectiveness of our method. Finally, we draw conclusions in Section 5.

2. Representation and Space of Solution to MKCP

When we solve a problem with GAs, the representation of chromosomes is an important issue. Representation depends on the problem and reflects the properties of the problem. One representation of a solution to MKCP is a vector of k integers representing column indices; another is a binary vector of length n, in which each element indicates whether or not the corresponding column is selected. Thus, when $k=2$ and $n=4$, the integer representation $(1,4)$ is equivalent to the binary vector representation $(1,0,0,1)$. We focus on the integer vector representation.

Using the integer vector representation, the encodings $(1,4)$ and $(4,1)$ both represent the same solution. The coverage, which is the value of the objective function, is also independent of this ordering. Since for the same solution there may be more than one different encoding, encoding space (genotypes) is different from solution space (phenotypes). We can consider permutations and combinations as genotypes and phenotypes, respectively. In the integer vector representation, it is natural to encode combinations using permutation encoding. However, in this case, many encodings correspond to the same combination. That is, this representation is redundant. Let G be the space of encodings in the integer vector representation, and let two encodings x and y in G be $(x_1,x_2,\dots ,x_n)$ and $(y_1,y_2,\dots ,y_n)$, respectively. Now, the relation ∼ is defined on G:

Definition 1.

$x\sim y$ if and only if we have a permutation $\sigma \in {\mathrm{\Sigma }}_k$ such that $\sigma (x_1,x_2,\dots ,x_k)=(y_1,y_2,\dots ,y_k)$, where ${\mathrm{\Sigma }}_k$ is the set of permutations of size k, and $\sigma \left(x\right)$ represents x permuted by σ.

Proposition 1.

The relation ∼ becomes an equivalence relation.

Proof. 

For each $i\le k$, $\langle {\mathrm{\Sigma }}_i,\circ \rangle$ forms a symmetric group $S_i$, where ∘ is the function composition operator [29]. Then, the direct product $P:={\mathrm{\Pi }}_{i=1}^k{S}_k$ is also a group [29], and therefore has an identity meaning that the relation ∼ is reflexive. When $\sigma \in P$, its inverse ${\sigma }^{-1}\in P$ exists, i.e., the relation ∼ is symmetric. The group P is closed under the operator ∘: It means if ${\sigma }^1,{\sigma }^2\in P$, then ${\sigma }^1\circ {\sigma }^2\in P$. That is, the relation ∼ is also transitive. Taken together, the relation ∼ becomes an equivalence relation. □

For example, the solutions $(1,3,5,7)$ and $(3,7,5,1)$ are equivalent. The number of vectors equivalent to a vector $g\in G$ is $k!$.

The equivalence relation of Definition 1 allows us to consider the real solution space (phenotype space) as the set of equivalence classes of elements in G, i.e., the quotient space $G/\sim$.

We can measure the similarity of two vectors x and y in G, the space of MKCP solution encodings, using a distance metric D, which we obtain by summing values of a subsidiary metric d which measures the difference between two columns of the matrix A which expresses the MKCP, as follows:

$$D(x,y):=\sum _{i=1}^{n}d(x_i,y_i).$$

(1)

Here, the genes of two chromosomes, $x_i$ and $y_i$, represent chosen column indices. If we regard the indices as just labels, not column vectors, the discrete metric, which becomes one if the two indices are the same, and zero otherwise, can be used as a metric d. This satisfies all the conditions for a distance metric including the triangular inequality.

An alternative metric is Hamming distance, which is a measure of the dissimilarity of two binary vectors. If we consider each column of the matrix A as a binary vector (the column vector), not just an integer, we can find the Hamming distance between any two column vectors, and hence between the corresponding genes $x_i$ and $y_i$ in two chromosomes from G. These distances can then be summed as shown in Equation (1).

Figure 1 shows two distances in G calculated using discrete metric and Hamming distance. As shown in Figure 1c, the discrete metric simply compares the column indices of $x_i$ and $y_i$, and ignores the contents of the corresponding columns of A. In Figure 1d, we see that the distance between $x_1$ and $y_1$ is the Hamming distance between the first and the second column vectors of A.

Now, we establish a metric in the quotient space $G/\sim$ by the following proposition:

Proposition 2.

Let $x=(x_1,x_2,\dots ,x_n)$ and $y=(y_1,y_2,\dots ,y_n)$ be in G, and let a metric D on G be defined by Equation (1). Then,

$$\overline{D}(\overline{x},\overline{y}):=\underset{\sigma \in {\mathrm{\Sigma }}_k}{min}\sum _{i=1}^{k}d(x_i,{\sigma }_i\left(y\right))$$

(2)

becomes a metric on $G/\sim$, where ${\sigma }_i\left(y\right)$ represents the ith element of permuted y by σ.

Proof. 

Let $\sigma$ be in the group ${\mathrm{\Pi }}_{i=1}^k{S}_k$. The computation $D(x,y):={\sum }_{i=1}^{n}d(x_i,y_i)$, is unaffected by summation order, and thus $D(x,y)=D\left(\sigma \right(x),\sigma (y\left)\right)$. Hence, $\sigma$ is an isometry on G, and thus ${\mathrm{\Pi }}_{i=1}^k{S}_k$ is an isometry subgroup. The relation ∼ is an equivalent relation obtained from ${\mathrm{\Pi }}_{i=1}^k{S}_k$. Hence from [30,31] $\overline{D}(\overline{x},\overline{y})$ is a metric on $G/\sim$. □

3. Normalization in MKCP

As shown above, redundancy in the integer representation of solutions to MKCP means that the encoding (genotype) space G is unnecessarily larger than the true solution (phenotype) space, which is the quotient space $G/\sim$. Redundant representations can be expected to reduce the performance of genetic algorithms significantly, which, in particular, undermines the effectiveness of standard crossovers defined using masks [32]. The problem of redundant representations have been addressed by a number of methods such as adaptive crossover [33,34,35,36], and among which the normalization technique [37] is representative. Normalization changes a parent genotype into a different genotype with the same phenotype which is similar to the genotype of the other parent before a standard crossover is performed. It is based on adaptive crossovers [34,35] and many variants have appeared [31,38,39].

3.1. Preserving Feasibility

A representation is infeasible if it does not meet the requirements of a solution. Figure 2a shows an integer representation which is infeasible because it contains duplicate column indices, and Figure 2b shows a binary representation which is infeasible because it contains the wrong number of ‘1’s. Figure 2 also shows how these infeasible solutions are likely to be created by standard crossover operators such as uniform and n-point crossovers.

A repairing step can be performed to restore feasibility, but this has the effect of a mutation, and may garble gene sequences inherited from parents. Using integer encoding, the problem can be avoided by rearranging the parents so that any shared column indices are in the same position. Such rearrangement naturally makes offspring preserve feasibility and no special repairing step is required. This form of normalization is easily implemented, as shown in the pseudocode in Figure 3, and takes $O\left(k^2\right)$ time.

In Figure 4, this normalization to preserve feasibility for the example in Figure 2a is shown.

3.2. Normalization for Improving Solution Quality

A good solution to MKCP will consist of dissimilar columns. For example, in Figure 1, $(1,3)$ is a better solution than $(1,4)$ because the ‘1’s in Columns 1 and 3 all occur in different rows, while Columns 1 and 4 share a ‘1’ in Row 2.

In the context of a genetic algorithm, we would expect chromosomes with genes corresponding to dissimilar columns to be most effective. Looking again at Figure 1, suppose that we apply a standard one-point crossover to the parents $(1,2)$ and $(3,4)$. If the cutting line lies between the first gene and the second one, then the offspring will be $(1,4)$, and this offspring covers the rows $\{1,2,3\}$ of A. However, if the second parent is rearranged to $(4,3)$, the offspring becomes $(1,3)$, which covers $\{1,2,4,5\}$. This example is illustrated in Figure 5. In general, we want the offspring to have genes that correspond to columns that are as dissimilar as possible. Thus, it is helpful to rearrange chromosomes so that genes corresponding to similar columns are in the same positions. The goal of this rearrangement can be formulated in terms of distance in the phenotype space $G/\sim$. Consider two parents x and y in the genotype space G. Rearranging genes so that those corresponding to the most similar columns are located in the same positions is equivalent to the search for a permutation ${\sigma }^{*}$ such that the distance between the equivalence class of x and that of y is equal to the distance between x and ${\sigma }^{*}\left(y\right)$. This is also equivalent to finding the $\sigma$ which minimizes the distance between x and the permuted y in Equation (2).

The optimal rearrangement is achieved by considering all of the permutations of genes in the second parent, and choosing the permutation that minimizes the distance sum between the column vectors corresponding to gene pairs in the same locations. If Hamming distance H is used to get the dissimilarity between the column vectors corresponding to two genes, we will choose the permutation ${\sigma }^{*}$ such that

$${\sigma }^{*}=\underset{\sigma \in {\mathrm{\Sigma }}_k}{argmin}\sum _{i=1}^{k}H(x_i,{\sigma }_i\left(y\right)),$$

(3)

where ${\mathrm{\Sigma }}_k$ is the set of all the permutations of length k and ${\sigma }_i\left(y\right)$ denotes the ith element of permuted y by $\sigma$.

We give an example case in Figure 6, in which the chromosomes $(1,2)$ and $(3,4)$ are both parents, and now we normalize $(3,4)$. Because k is 2, the number of all the permutations is just 2. We compute ${\sum }_{i=1}^{k}H(x_i,{\sigma }_i\left(y\right))$ for each permutation. If ${\sigma }^1=\left(\genfrac{}{}{0pt}{}{12}{12}\right)$, ${\sigma }^1\left(y\right)=(3,4)$. Then, $H(x_1,{\sigma }_1^1\left(y\right))=4$, $H(x_2,{\sigma }_2^1\left(y\right))=2$, and their sum is 6. For the second permutation ${\sigma }^2=\left(\genfrac{}{}{0pt}{}{12}{21}\right)$, ${\sigma }^2\left(y\right)=(4,3)$. Then, $H(x_1,{\sigma }_1^2\left(y\right))=2$, $H(x_2,{\sigma }_2^2\left(y\right))=2$, and their sum is 4. Since this is smaller than 6, ${\sigma }^2=\left(\genfrac{}{}{0pt}{}{12}{21}\right)$ is the optimal permutation.

Enumerating all $k!$ permutations is intractable for a large k, and thus this procedure is intractable. However, the problem can be solved using the Hungarian method [40], which is a network-flow-based technique. It provides an optimal result, and runs in $O\left(k^3\right)$ time [41]. Alternatively, we can use a fast heuristic [42], which runs in $O\left(k^2\right)$ and produces results very close to the optimum. Either of these methods can be treated as a function that accepts a 2D array, in which the elements are the distances between two genes, and returns the permutation with the minimum total distance between chromosomes. This normalization is shown in the pseudocode of Figure 7.

After we rearrange the second parent according to the permutation ${\sigma }^{*}$, a standard crossover is applied.

Now, we investigate the relation between this optimal rearrangement and the feasibility. There may be more than one optimal rearrangement satisfying Equation (3), but we can show that one of them is always feasible. Feasibility is preserved by an optimal permutation ${\sigma }^{*}$ which locates all common indices in the same positions by ${\sigma }^{*}$, as we now prove:

Proposition 3.

If $x=(x_1,x_2,\dots ,x_k)$ and $y=(y_1,y_2,\dots ,y_k)$ are two chromosomes and $x_p=y_q$, then there exists ${\sigma }^{*}\in {\mathrm{\Sigma }}_k$ such that ${\sigma }_p^{*}\left(y\right)=y_q$ and ${\sum }_{i=1}^{k}d(x_i,{\sigma }_i^{*}\left(y\right))\le {\sum }_{i=1}^{k}d(x_i,{\sigma }_i\left(y\right))$ for all $\sigma \in {\mathrm{\Sigma }}_k$, where d is a distance metric.

Proof. 

Let ${\sigma }^{\prime }$ be ${argmin}_{\sigma \in \mathrm{\Sigma }k}{\sum }_{i=1}^{k}d(x_i,{\sigma }_i\left(y\right))$. There is an index r satisfying ${\sigma }_r^{\prime }\left(y\right)=y_q$. Let ${\sigma }^{″}$ be the same permutation as ${\sigma }^{\prime }$, except that ${\sigma }^{\prime }{\left(y\right)}_p$ and ${\sigma }_r^{\prime }\left(y\right)$ are exchanged:

$${\sigma }_i^{″}\left(y\right)=\left\{\begin{array}{cc}{\sigma }_r^{\prime }\left(y\right)\hfill & \mathrm{if}i=p,\hfill \\ {\sigma }_p^{\prime }\left(y\right)\hfill & \mathrm{if}i=r,\hfill \\ {\sigma }_i^{\prime }\left(y\right)\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Then,

$$\begin{array}{ccc}\hfill \sum _{i=1}^{k}d(x_i,{\sigma }_i^{″}\left(y\right))& =& d(x_p,{\sigma }_p^{″}\left(y\right))+d(x_r,{\sigma }_r^{″}\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{″}\left(y\right))\hfill \\ & =& d(x_p,{\sigma }_r^{\prime }\left(y\right))+d(x_r,{\sigma }_p^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{\prime }\left(y\right))\hfill \\ & =& d(x_p,y_q)+d(x_r,{\sigma }_p^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{\prime }\left(y\right))\hfill \\ & =& d(x_r,{\sigma }_p^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{\prime }\left(y\right))(\because d(x_p,y_q)=0\mathrm{by}\mathrm{assumption})\hfill \\ & \le & d(x_r,x_p)+d(x_p,{\sigma }_p^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{\prime }\left(y\right))(\because \mathrm{triangular}\mathrm{inequality})\hfill \\ & =& d(x_r,y_q)+d(x_p,{\sigma }_p^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{\prime }\left(y\right))\hfill \\ & =& d(x_r,{\sigma }_r^{\prime }\left(y\right))+d(x_p,{\sigma }_p^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{\prime }\left(y\right))\hfill \\ & =& \sum _{i=1}^{k}d(x_i,{\sigma }_i^{\prime }\left(y\right))\hfill \\ & \le & \sum _{i=1}^{k}d(x_i,{\sigma }_i\left(y\right))\mathrm{for}\mathrm{all}\sigma \in {\mathrm{\Sigma }}_k.\hfill \end{array}$$

Hence, ${\sum }_{i=1}^{k}d(x_i,{\sigma }_i^{″}\left(y\right))\le {\sum }_{i=1}^{k}d(x_i,{\sigma }_i\left(y\right))$ for all $\sigma \in {\mathrm{\Sigma }}_k$ and ${\sigma }_p^{\prime \prime }\left(y\right)=y_q$. □

This proof relies on the triangular inequality, which is a key property of any valid distance. Thus, Proposition 3 holds for distances other than Hamming distance. We could use discrete metric, introduced in Section 2. This distance provides a very rough comparison of two solutions, but Proposition 3 still holds. Equation (3) can be rewritten using discrete metric $\rho$ instead of Hamming distance H:

$${\sigma }^{*}=\underset{\sigma \in {\mathrm{\Sigma }}_k}{argmin}\sum _{i=1}^k\rho (x_i,{\sigma }_i\left(y\right)).$$

(4)

In particular, in this case, feasibility is preserved by any optimal permutation ${\sigma }^{*}$ in Equation (4). Its proof is quite similar to the proof of Proposition 3.

Proposition 4.

If $x=(x_1,x_2,\dots ,x_k)$ and $y=(y_1,y_2,\dots ,y_k)$ are two chromosomes and $x_p=y_q$, then ${\sigma }_p^{*}\left(y\right)=y_q$, where ${\sigma }^{*}$ is a permutation such that ${\sum }_{i=1}^k\rho (x_i,{\sigma }_i^{*}\left(y\right))\le {\sum }_{i=1}^k\rho (x_i,{\sigma }_i\left(y\right))$ for all $\sigma \in {\mathrm{\Sigma }}_k$.

Proof. 

We assume that ${\sigma }_p^{*}\left(y\right)\ne y_q$. There is an index r satisfying ${\sigma }_r^{*}\left(y\right)=y_q$. Let ${\sigma }^{\prime }$ be the same permutation as ${\sigma }^{*}$, except that ${\sigma }^{*}{\left(y\right)}_p$ and ${\sigma }_r^{*}\left(y\right)$ are exchanged:

$${\sigma }_i^{\prime }\left(y\right)=\left\{\begin{array}{cc}{\sigma }_r^{*}\left(y\right)\hfill & \mathrm{if}i=p,\hfill \\ {\sigma }_p^{*}\left(y\right)\hfill & \mathrm{if}i=r,\hfill \\ {\sigma }_i^{*}\left(y\right)\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

Then,

$$\begin{array}{ccc}\hfill \sum _{i=1}^k\rho (x_i,{\sigma }_i^{\prime }\left(y\right))& =& \rho (x_p,{\sigma }_p^{\prime }\left(y\right))+\rho (x_r,{\sigma }_r^{\prime }\left(y\right))+\sum _{i\ne p,i\ne r}\rho (x_i,{\sigma }_i^{\prime }\left(y\right))\hfill \\ & =& \rho (x_p,{\sigma }_r^{*}\left(y\right))+\rho (x_r,{\sigma }_p^{*}\left(y\right))+\sum _{i\ne p,i\ne r}\rho (x_i,{\sigma }_i^{*}\left(y\right))\hfill \\ & =& \rho (x_p,y_q)+\rho (x_r,{\sigma }_p^{*}\left(y\right))+\sum _{i\ne p,i\ne r}\rho (x_i,{\sigma }_i^{*}\left(y\right))\hfill \\ & =& \rho (x_r,{\sigma }_p^{*}\left(y\right))+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{*}\left(y\right))(\because x_p=y_q\mathrm{by}\mathrm{assumption})\hfill \\ & <& 1+1+\sum _{i\ne p,i\ne r}d(x_i,{\sigma }_i^{*}\left(y\right))\hfill \\ & =& \rho (x_p,{\sigma }_p^{*}\left(y\right))+\rho (x_r,x_p)+\sum _{i\ne p,i\ne r}\rho (x_i,{\sigma }_i^{*}\left(y\right))(\because x_p\ne {\sigma }_p^{*}\left(y\right)\mathrm{and}{x}_r\ne x_p)\hfill \\ & =& \rho (x_p,{\sigma }_p^{*}\left(y\right))+\rho (x_r,y_q)+\sum _{i\ne p,i\ne r}\rho (x_i,{\sigma }_i^{*}\left(y\right))\hfill \\ & =& \rho (x_p,{\sigma }_p^{*}\left(y\right))+\rho (x_r,{\sigma }_r^{*}\left(y\right))+\sum _{i\ne p,i\ne r}\rho (x_i,{\sigma }_i^{*}\left(y\right))\hfill \\ & =& \sum _{i=1}^k\rho (x_i,{\sigma }_i^{*}\left(y\right)).\hfill \end{array}$$

This contradicts the assumption that ${\sum }_{i=1}^k\rho (x_i,{\sigma }_i^{*}\left(y\right))\le {\sum }_{i=1}^k\rho (x_i,{\sigma }_i\left(y\right))$ for all $\sigma \in {\mathrm{\Sigma }}_k$. □

Using discrete metric will only cause identical indices to be rearranged into the same positions. In fact, normalization by discrete metric is exactly the same as rearranging for preserving feasibility introduced in Section 3.1.

4. Experiments

4.1. Test Sets and Test Environments

Our experiments were conducted on 65 instances of 11 set cover problems with various size and densities, from the OR-library [43]. Although these benchmark data were designed as set cover problems, the data can also be considered as maximum k-coverage problems, as in [27]. Some details of these problems are presented in

Table 1. Problem set.

Problem	m	n	Density	#Instances
Set				Tested
I-4	200	1000	2%	10
I-5	200	2000	2%	10
I-6	200	1000	5%	5
I-A	300	3000	2%	5
I-B	300	3000	5%	5
I-C	400	4000	2%	5
I-D	400	4000	5%	5
I-E	500	5000	10%	5
I-F	500	5000	20%	5
I-G	1000	10,000	2%	5
I-H	1000	10,000	5%	5

, where m and n are the numbers of rows and columns, respectively, and density is the percentage of ‘1’s in the MKCP matrix A. The present authors previously experimented with problems with fixed values of k of 10 and 20 [28]. However, in this study, we varied k with the tightness ratio $\alpha$, which is the product of k and the density of a problem. The higher is the tightness ratio, the larger is the value of the object function, which is the coverage, that we are likely to achieve. If the tightness ratio is 1, the optimum coverage is likely to be very close to n. We used tightness ratios of $0.8$, $0.6$, and $0.4$.

We implemented all our tested algorithms in C language using gcc version 5.4.0, and ran them on Ubuntu 16.04.6.

4.2. Effect of Normalization on a Crossover

To see whether or not normalization is effective at crossover, we performed experiments with three methods of rearranging the second of two parents before a crossover:

• REPAIR: The second parent is not rearranged before the crossover, but infeasible offspring are repaired to restore feasibility after the crossover.
• FP: The second parent is rearranged to produce only feasible offspring using the normalization in Figure 3.
• OPT: The second parent is rearranged by the normalization in Figure 7, to minimize the sum of the distances using the permutation ${\sigma }^{*}$ of Equation (3).

REPAIR produces feasible offspring by the method of replacing duplicate column indices with a randomly chosen one among the indices that are not contained in the offspring. OPT was implemented using the Hungarian method [40], which runs in $O\left(k^3\right)$ time.

To determine the most effective method, we performed the following steps:

(1)

N parent chromosomes were randomly generated. (N was set to 100.)

(2)

The chromosomes were randomly paired, making $N/2$ couples.

(3)

The second parent in each pair was rearranged using the methods described above.

(4)

A uniform crossover was applied to each couple.

(5)

We computed the mean and the standard deviation for the coverage of each of the $N/2$ offspring.

This procedure was applied to a single instance of each problem listed in Table 1 using REPAIR, FP, and OPT.

Table 2. Effect of normalization on a single crossover, after the REPAIR, FP, and OPT procedures.

Tightness			Parents		REPAIR		FP		OPT
Ratio	Instance	k	Ave	SD	Ave	SD	Ave	SD	Ave	SD
	scp41	40	110.27	6.33	110.30	5.89	110.00	5.46	113.80	6.12
	scp51	40	110.72	6.62	110.00	6.95	111.82	6.90	115.02	6.77
	scp61	16	111.33	6.43	111.24	6.64	111.20	6.73	114.20	6.24
	scpa1	40	167.69	7.76	166.80	7.83	167.68	8.47	173.66	8.93
	scpb1	16	168.31	9.27	170.80	9.79	168.90	9.11	171.36	9.25
0.8	scpc1	40	220.40	10.53	221.04	10.83	220.42	9.76	225.84	9.91
	scpd1	16	223.74	9.22	222.34	10.15	224.36	8.69	228.56	9.48
	scpnre1	8	284.43	10.23	285.08	10.93	285.76	11.08	287.14	9.27
	scpnrf1	4	295.44	10.76	294.94	9.94	294.44	9.50	297.34	9.75
	scpnrg1	40	553.30	14.49	553.96	14.56	553.82	16.10	561.28	12.16
	scpnrh1	16	560.94	14.49	562.12	16.57	563.14	16.24	567.46	17.09
	scp41	30	90.40	6.41	90.80	6.34	89.98	4.82	95.34	6.14
	scp51	30	90.77	6.74	91.92	6.92	91.44	6.50	94.20	6.64
	scp61	12	90.96	6.54	90.56	6.17	90.94	5.86	91.88	7.75
	scpa1	30	137.54	8.09	136.74	8.95	137.60	7.63	143.74	8.01
	scpb1	12	138.05	8.31	138.44	8.36	139.68	9.08	141.68	8.28
0.6	scpc1	30	181.59	10.64	178.52	10.55	180.24	11.30	186.06	10.09
	scpd1	12	185.27	9.08	184.80	9.06	185.34	9.01	188.30	7.72
	scpnre1	6	233.02	11.34	231.60	12.83	234.04	12.41	234.12	11.04
	scpnrf1	3	244.40	11.37	245.04	10.48	244.24	10.28	245.68	9.57
	scpnrg1	30	452.91	14.48	452.70	14.52	452.58	14.07	461.34	13.42
	scpnrh1	12	461.87	13.66	460.80	16.68	462.22	16.58	462.40	15.61
	scp41	20	66.44	5.52	66.84	5.59	67.30	6.09	68.06	5.19
	scp51	20	66.41	5.54	67.44	6.61	66.84	6.44	68.98	6.71
	scp61	8	66.55	6.80	67.68	6.05	66.72	5.91	67.74	5.71
	scpa1	20	100.82	8.40	99.80	7.62	100.00	7.63	103.54	6.80
	scpb1	8	101.25	7.43	101.74	8.91	101.06	7.38	104.06	8.43
0.4	scpc1	20	132.47	10.42	131.68	8.78	133.14	9.07	136.14	9.92
	scpd1	8	135.48	10.49	136.32	8.49	134.72	9.46	136.94	9.96
	scpnre1	4	171.43	10.32	172.04	10.14	172.94	12.05	173.16	11.10
	scpnrf1	2	179.95	10.83	180.04	9.85	179.94	11.46	182.90	11.22
	scpnrg1	20	331.51	13.57	332.10	13.64	330.52	14.89	337.30	14.60
	scpnrh1	8	338.58	14.59	336.84	14.80	337.30	14.42	343.44	13.90
t-test p-value *			-		$4.25\times {10}^{-1}$		$1.09\times {10}^{-1}$		$7.52\times {10}^{-12}$

Ave and SD are the average and the standard deviation of the fitness of 100 parents (in the column of “Parents”) or 50 offspring (in the remaining columns of REPAIR, FP, and OPT), respectively. REPAIR produces feasible offspring by random repair. FP rearranges the second parent to produce feasible offspring using the normalization in Figure 3. OPT is optimized normalization of the second parent. * The one-tailed t-test of the null hypothesis that the result of given method is equal to fitness of parents.

shows the results for each of these 11 instances. We see that OPT normalization outperforms the others, and can therefore be expected to improve the performance of a GA. Moreover, the results of the one-tailed t-test show that the objective values of offspring produced using OPT normalization were better than those of their parents. On the contrary, the values produced using REPAIR and FP were similar to those of their parents. This suggests that, compared to other methods, OPT normalization would strongly support the function of the crossover operator in searching the solution space in a promising direction, without replacement strategy.

4.3. Performance of GAs with Normalization Methods

Our underlying evolutionary model is similar to the model of CHC [44], which was applied to many problems [45,46,47,48,49,50]. We paired a population of N chromosomes randomly, and then we applied crossover to each pair, generating a total of $N/2$ offspring. We ranked all parents and offspring and the fittest N individuals among them became the population in the next generation. We used 100 as the size of population in our experiments. We reinitialized the population, except for the best individual, if there were no changes over $kr(1-r)$ generations, where r is a divergence ratio that wes set to $0.25$. This GA stopped after 500 generations and returned the best it has found. The pseudocode of our GA is given in Figure 8.

In the following experiments, we changed the normalization method in a single GA. We compared the output of our GA with the best result that we found in this study, using the metric %-gap, which is $100\times |best-output|/best$.

Thirty trials were performed for each method, and the averaged results are shown in

Table 3. Results of three GAs compared with random solutions to MKCP.

Tightness	Instance		Multi-Start		RR-GA		t-Test ${}^1$	FP-GA		t-Test ${}^2$	OPT-GA		t-Test ${}^3$
Ratio	Set	k	%-Gap	Ave	%-Gap	Ave	p-Value	%-Gap	Ave	p-Value	%-Gap	Ave	p-Value
	I-4	40	28.17	141.35	7.08	182.86	$6.62\times {10}^{-16}$	3.36	190.19	$3.45\times {10}^{-11}$	1.96	192.95	$2.56\times {10}^{-10}$
	I-5	40	28.67	141.52	6.84	184.82	$2.92\times {10}^{-19}$	3.95	190.57	$1.71\times {10}^{-9}$	1.64	195.14	$5.16\times {10}^{-10}$
	I-6	16	20.56	143.77	4.22	173.35	$8.21\times {10}^{-10}$	4.21	173.37	$4.67\times {10}^{-1}$	2.53	176.42	$6.86\times {10}^{-5}$
	I-A	40	27.62	207.57	6.16	269.13	$1.09\times {10}^{-9}$	4.29	274.49	$4.85\times {10}^{-6}$	1.81	281.61	$5.45\times {10}^{-6}$
	I-B	16	20.56	208.93	4.52	251.10	$2.69\times {10}^{-7}$	4.73	250.54	$8.86\times {10}^{-2}$	2.68	255.94	$1.05\times {10}^{-4}$
0.8	I-C	40	26.81	269.33	6.12	345.48	$2.89\times {10}^{-8}$	4.85	350.16	$7.50\times {10}^{-5}$	2.10	360.28	$2.11\times {10}^{-5}$
	I-D	16	18.78	271.43	3.91	321.14	$8.71\times {10}^{-8}$	4.15	320.31	$6.58\times {10}^{-2}$	1.90	327.84	$2.65\times {10}^{-6}$
	I-E	8	12.65	336.81	3.63	371.60	$7.01\times {10}^{-8}$	4.04	369.99	$9.37\times {10}^{-3}$	2.65	375.37	$1.31\times {10}^{-4}$
	I-F	4	6.23	346.58	2.25	361.27	$2.18\times {10}^{-6}$	2.42	360.66	$1.27\times {10}^{-1}$	1.83	362.82	$1.78\times {10}^{-3}$
	I-G	40	21.61	630.13	4.73	765.78	$3.64\times {10}^{-10}$	3.82	773.12	$4.74\times {10}^{-4}$	1.64	790.58	$1.47\times {10}^{-5}$
	I-H	16	14.79	634.61	3.31	720.14	$1.81\times {10}^{-8}$	3.75	716.83	$1.29\times {10}^{-2}$	1.93	730.41	$5.89\times {10}^{-5}$
	I-4	30	31.62	121.57	6.72	165.85	$3.47\times {10}^{-16}$	4.75	169.35	$8.86\times {10}^{-9}$	2.69	173.01	$1.76\times {10}^{-9}$
	I-5	30	32.71	121.79	6.76	168.76	$1.25\times {10}^{-17}$	5.69	170.70	$1.25\times {10}^{-5}$	2.53	176.42	$1.53\times {10}^{-12}$
	I-6	12	21.51	124.00	4.35	151.12	$3.29\times {10}^{-7}$	4.21	151.35	$1.62\times {10}^{-1}$	2.56	153.95	$1.02\times {10}^{-3}$
	I-A	30	31.03	178.49	6.12	242.97	$2.64\times {10}^{-8}$	5.30	245.09	$6.19\times {10}^{-3}$	2.36	252.70	$6.20\times {10}^{-5}$
	I-B	12	22.15	179.34	4.83	219.27	$5.21\times {10}^{-7}$	5.22	218.36	$1.65\times {10}^{-2}$	3.00	223.47	$1.61\times {10}^{-5}$
0.6	I-C	30	29.54	230.25	5.89	307.54	$1.41\times {10}^{-9}$	5.19	309.85	$1.43\times {10}^{-3}$	2.63	318.20	$3.56\times {10}^{-7}$
	I-D	12	20.18	232.11	4.28	278.34	$5.40\times {10}^{-8}$	4.73	277.03	$1.78\times {10}^{-2}$	2.71	282.91	$8.94\times {10}^{-6}$
	I-E	6	11.82	287.65	3.12	316.02	$8.78\times {10}^{-8}$	3.48	314.85	$2.63\times {10}^{-2}$	2.25	318.84	$7.78\times {10}^{-5}$
	I-F	3	4.29	296.71	1.43	305.56	$5.35\times {10}^{-7}$	1.91	304.09	$1.05\times {10}^{-3}$	1.13	306.50	$1.72\times {10}^{-4}$
	I-G	30	24.17	531.23	5.18	664.26	$2.06\times {10}^{-9}$	5.00	665.56	$1.31\times {10}^{-1}$	2.42	683.65	$2.75\times {10}^{-5}$
	I-H	12	15.06	535.09	2.95	611.43	$2.77\times {10}^{-8}$	3.34	608.92	$9.63\times {10}^{-3}$	1.80	618.66	$2.49\times {10}^{-4}$
	I-4	20	32.30	95.98	5.56	133.91	$1.71\times {10}^{-14}$	4.54	135.36	$2.39\times {10}^{-7}$	2.40	138.39	$2.27\times {10}^{-9}$
	I-5	20	34.33	96.27	6.20	137.51	$5.07\times {10}^{-16}$	6.12	137.62	$2.93\times {10}^{-1}$	2.76	142.55	$8.79\times {10}^{-10}$
	I-6	8	19.63	98.21	3.14	118.37	$3.63\times {10}^{-6}$	3.38	118.08	$1.62\times {10}^{-1}$	2.08	119.66	$6.08\times {10}^{-4}$
	I-A	20	32.95	140.65	5.88	197.46	$1.94\times {10}^{-7}$	6.12	196.95	$1.14\times {10}^{-1}$	2.92	203.66	$1.14\times {10}^{-5}$
	I-B	8	21.41	141.44	4.02	172.76	$5.61\times {10}^{-7}$	4.84	171.27	$3.75\times {10}^{-3}$	2.48	175.53	$1.48\times {10}^{-4}$
0.4	I-C	20	31.50	179.73	5.50	247.96	$2.99\times {10}^{-8}$	5.77	247.24	$1.12\times {10}^{-1}$	2.66	255.41	$5.49\times {10}^{-7}$
	I-D	8	19.61	180.87	3.74	216.59	$1.92\times {10}^{-6}$	4.48	214.91	$2.07\times {10}^{-2}$	2.56	219.23	$2.34\times {10}^{-6}$
	I-E	4	9.00	222.76	2.14	239.55	$1.89\times {10}^{-8}$	2.64	238.34	$1.59\times {10}^{-2}$	1.64	240.78	$1.21\times {10}^{-6}$
	I-F	2	1.87	229.63	1.72	229.97	$1.22\times {10}^{-1}$	1.97	229.39	$2.48\times {10}^{-2}$	1.55	230.37	$8.79\times {10}^{-3}$
	I-G	20	25.35	405.93	4.45	519.61	$5.35\times {10}^{-9}$	4.65	518.51	$2.74\times {10}^{-2}$	2.32	531.16	$2.91\times {10}^{-5}$
	I-H	8	14.64	408.88	3.15	463.92	$2.75\times {10}^{-9}$	3.52	462.16	$2.56\times {10}^{-2}$	1.87	470.06	$4.82\times {10}^{-5}$

Averages from 30 runs. Multi-Start generates random solutions and chooses the best. RR-GA is a genetic algorithm with random repair. FP-GA is a genetic algorithm with FP normalization. OPT-GA is a genetic algorithm with OPT normalization. ${}^1$ The one-tailed t-test with the null hypothesis of RR-GA = Multi-Start. ${}^2$ The one-tailed t-test with the null hypothesis of FP-GA = RR-GA. ${}^3$ The one-tailed t-test with the null hypothesis of OPT-GA = FP-GA.

. The results labeled RR-GA were produced without normalization: infeasible offspring produced were repaired randomly using the same method as REPAIR in Section 4.2. We also compared the results from the GA with a multi-start method using randomly generated solutions. In each run of this method, called Multi-Start, we sampled ${10}^6$ random solutions and chose the best one. Even RR-GA performed significantly better than Multi-Start, suggesting that GAs are an appropriate mechanism for solving the MKCP.

The results labeled FP-GA in Table 3 were produced by rearranging the genes of the second parent to produce feasible offspring without the need for repair. FP-GA outperformed RR-GA for large values of k but not for small values. It seems that the effect of mutation by repair is rather effective when the solution space is small.

The results labeled OPT-GA in Table 3 were produced by the GA with the proposed normalization. Using the same GA as FP-GA, OPT-GA rearranges the genes of the second parent to minimize the sum of distances between genes (column vectors) before applying recombination. OPT-GA clearly outperforms Multi-Start and RR-GA; the results of one-tailed t-tests prove that OPT-GA also outperforms FP-GA significantly.

The results of the t-tests show that Multi-Start is clearly the worst technique, even though it is allowed ${10}^6$ evaluations, while the GA-based methods produce relatively small $2.5\times {10}^4$ chromosomes. RR-GA and FP-GA have similar performance, and OPT-GA clearly does best.

5. Conclusions

We present the maximum k-coverage problem (MKCP) and analyze its representation and solution space. If we apply a GA to the MKCP, then we immediately encounter the issue of redundancy in the genotype space, which is larger than the phenotype space that we characterize as a quotient space. We introduce a method of normalizing chromosomes that ensures a crossover produces feasible offspring with genes that are column vectors of the MKCP matrix and are as dissimilar as possible. This normalization was implemented using the Hungarian method [40]. We performed experiments which showed the effectiveness of this approach.

In this study, we adopted two locus-based metrics of the discrete metric and its extended version derived from Hamming distance between genes (column vectors). However, other metrics such as some variants of Cayley metric on permutations [51,52] may also be applied to the proposed theoretical framework. In the case of such non-locus-based metric, we should design a new crossover tailored to the metric. This investigation will be a promising work, which we leave for future study.

As mentioned in the Introduction, the proposed theoretical framework can be applied to real-world applications such as the cyber-physical social systems and public safety networks. We leave this applied work for future study. We also expect that this approach can be applied to other problems which have the same representation for their solutions. By expanding this technique to solution representations of variable length as in [53,54], we believe it could also be applied to the set cover problem.