Please help me solve this question:

A Covering Array (CA) is a combinatorial object, denoted by CA(N; t, k, v), which can be described as a matrix with N k elements, such that every N t subarray contains all possible combinations of v symbols at least once. N represents the rows of the matrix, k is the number of parameters, which have v possible values and t represents the strength or the degree of controlled interaction. To illustrate the use of CAs suppose that we have a system with 3 parameters (k) each with 2 possible values (v) labeled as 0 and 1 respectively as shown in Table 1.

Table 1: System with three parameters each with two possible values

OS	Browser	Database
Linux	Firefox	MySQL
Windows	Chrome	Oracle

Assume we want to construct a CA with t=2 from the System described above; thus, a matrix of at least 4 rows is needed to cover v^t combinations. A CA that fulfills this this requirement is shown in Table 2:

Table 2: CA (4;2,3,2)

1	1	0
1	0	1
0	1	1
0	0	0

In the example shown in Table 2 the total of combinations between pairs of parameters is

3 being these {OS, Browser), {OS, Database), {Browser, Database). Each parameter has 2 settings giving 4

possible combinations for each pair of them.

The definition of a CA implies that every N t sub-array contains all possible combinations of v^t symbols at least once, based on this fact, for the tuple {O.S., Web browser) all the combinations {0,0], {0,1), {1,0), {1,1) are covered, the same way for any pair of selected parameters.

Implementation

In this project, you will implement simulated annealing (SA) to try to build a CA s.t. the number of rows

(N) is the lower bound size that tentative can cover the required combinations in each N t sub-array. To simplify the problem, for this implementation, fixed assignments of t=2 and v=2 will be used, that is, only the number of parameters (k) that will be the input varies, being its domain [5,7].

The algorithm will return:

(1) The CA (if it could find it) or display that the solution was not achieved

2 The number of iterations performed in the execution.

(3) What is the stop criterion: solution, frozen, final temperature archived

The implementation will include the following:

* The initial solution will be created randomly, that is, you will initialize the matrix with the corresponding domain of each variable.

* The objective function will count the total of missing combinations in each N t subset, thus being a minimization problem.

* The algorithm will include a geometrical cooling scheme, it starts at an initial temperature T_i =k and which is decremented at each round by a factor alpha=0.99 using the relation T_x= alphaTx-1

* Frozen factor: if after (frozen factor consecutive temperature decrements the best-so-far solution is not improved, the algorithm stops its execution, for this = v^t .

* The objective function will count the number of combinations covered in each N t subset, thus being a maximization problem.

* The neighbourhood function randomly selects a column j(1 j k). After that, the function swaps the symbol of each row in M_i,j to create the neighbours, and then evaluates the number of missing combinations in each of them.