Sara Tari
email: sara.tari@univ-littoral.fr

Sébastien Verel
email: verel@univ-littoral.fr

Mahmoud Omidvar
email: omidvar@univ-littoral.fr

PUBO i : a tunable benchmark with variable importance

Keywords: Benchmark, Fitness landscape, Walsh function, Variable importance

In this work, we present the benchmark generator PUBOi, Polynomial Unconstrained Binary Optimization, that combines subproblems to create instances of pseudo-boolean optimization problems. Any mono-objective pseudoboolean functions including existing classical optimization problems can be expressed with Walsh functions. The benchmark generator can tune main features of problems such as problem dimension, non-linearity degree, and neutrality. Additionally, to be able to create instances with properties similar to those of real-like combinatorial optimization problems, the goal of PUBOi is to introduce the notion of variable importance. Indeed, the importance of decision variables can be tuned using three benchmark parameters. In the version presented here, we consider four subproblems already used in Chook generator for benchmarking quantum computers and algorithms as a basis. We also present the impact of benchmark parameters using a fitness landscape analysis that empirically shows these parameters to significantly impact the variable importance.

Introduction

There exist numerous evolutionary algorithms, or local search algorithms that efficiently tackle combinatorial optimization problems. One main practical, and theoretical difficulty facing new problem instances is the selection, or the design of efficient optimization algorithm according to the properties of the instance to optimize. Studying such algorithms often require to run them on diverse problem instances, which is usually done successfully in benchmarking studies [START_REF] Bartz-Beielstein | Benchmarking in optimization: Best practice and open issues[END_REF]. This paper attempts to propose a benchmark of pseudo-Boolean functions with tunable relevant properties.

In conjunction of benchmarking efforts, a powerful approach aiming to improve the understanding of optimization algorithms, and thus determine which approach to consider, consists of using fitness landscapes [START_REF] Wright | The roles of mutation, inbreeding, crossbreeding, and selection in evolution[END_REF]. In evolutionary computation, a fitness landscape represents the search space and fitness function of a given instance according to the links between solutions induced by the neighborhood relation of the algorithm under consideration. This representation corresponds to a graph from which several characteristics can be estimated by the application of indicators on a sample of solutions [START_REF] Malan | A survey of techniques for characterising fitness landscapes and some possible ways forward[END_REF][START_REF] Malan | A survey of advances in landscape analysis for optimisation[END_REF], allowing a visualization of landscapes and features that induce challenges for optimization methods. Hence, fitness landscapes is a powerful tool to better guide the design and use of neighborhood-based algorithms, even on large landscapes.

To design new optimization algorithms by "hand" or using machine learning techniques, to test existing approaches, or to better understand problem difficulty using fitness landscape analysis often requires a large and diverse set of problem instances with relevant properties. To this aim, there exist several generators or benchmarks of academic problems. While a small subset of such instances are based on real-world data, most of them are randomly generated, with characteristics that could greatly differ from real-world problems. One of the peculiarities of real-like instances is that, contrary to instances generated using random-based techniques, they are structured. Thus some variables of the problems play a more important role in terms of fitness contribution, and can be interdependent to several other variables, making them harder to study and understand [START_REF] Leprêtre | Fitness landscapes analysis and adaptive algorithms design for traffic lights optimization on sialac benchmark[END_REF]. Although variable importance of such problems must be studied, existing benchmark generators do not allow users to tune this parameter, which contributes to the lack of instances having important variables.

In this work, we propose and present PUBO i , a benchmark in which variable importance is tunable, and thus impacts the instance structure. PUBO i is based upon Walsh functions [START_REF] Walsh | A Closed Set of Normal Orthogonal Functions[END_REF], an orthogonal basis of pseudo-boolean functions for representing any pseudo-boolean function. These functions arouse a strong interest in several scientific communities. In quantum physics, one can use these functions to create benchmarks representing optimization problems that can be tackled using new quantum computers [START_REF] Perera | Chook-a comprehensive suite for generating binary optimization problems with planted solutions[END_REF]. They are successfully used in blackbox combinatorial optimization as surrogate functions for computational-costly fitness functions [START_REF] Verel | A Surrogate Model Based on Walsh Decomposition for Pseudo-Boolean Functions[END_REF]. Walsh functions also allow a standardized reformulation of various academic optimization problems [START_REF] Glover | Polynomial unconstrained binary optimisation-part 1[END_REF]. This basis of functions can be used for benchmarking purposes, by generating instances with various characteristics, including characteristics similar to those of real-like instances such as the variable importance. The contribution of this paper are (1) the proposition of a new benchmark generator with tunable variable importance, (2) a fitness landscape analysis of the instances set aiming to analyze the impact of benchmark parameters on the shape of fitness landscape, and on the related problem difficulty.

The paper is organized as follows. The next section presents related works on benchmarking and variable importance. Section 3 is devoted to the description of PUBO i as well as the instances considered in this study. In section 4, we present the methodology and results of our experiments. The last section provides a discussion of this work and points out future work directions.

Related Works

In this section we propose a brief overview of previous work on variable importance, test suites for optimization problems and benchmark generators, with a particular focus on a generator proposed by physicists we used as a basis for PUBO i .

Variable importance, and benchmarks of optimization problems

In the context of optimization problems, we assume a variable is important when its mutation strongly affects the fitness of a solution. When this characteristic is present on instances to optimize, taking it into account can help to optimize the problem more efficiently. There exist a few studies of optimization algorithms focusing on the variable importance of optimization problems, although this characteristic often exists on real data. For example, in [START_REF] Sagawa | Learning variable importance to guide recombination[END_REF][START_REF] Sagawa | Learning variable importance to guide recombination on many-objective optimization[END_REF] the authors study a machine learning-enhanced recombination that incorporates an intelligent variable selection method for multi-objective optimization and show that taking the variable importance into consideration can improve the optimization quality. Another example concerns the fitness landscape analysis of landscapes from the SIALAC benchmark, a benchmark for mobility problems [START_REF] Leprêtre | Fitness landscapes analysis and adaptive algorithms design for traffic lights optimization on sialac benchmark[END_REF]. In this benchmark based on a city mobility simulation, variables have different degrees of importance, and a bandit descent heuristic is proposed to take important variables into account.

An efficient way of studying optimization algorithms consists of analyzing their behavior on various problems and instances. Over the past decades, a huge effort has been devoted to the proposition of benchmarks of various optimization problems. Benchmarks allow the community to focus on the optimization of a given problem and to study more efficiently various optimization problems. Among classic benchmarks for academic combinatorial optimization problems, Taillard [START_REF] Taillard | Benchmarks for basic scheduling problems[END_REF] proposes instances covering three basic scheduling problems : the permutation flow shop, the job shop and the open shop scheduling problems. Despite their simplicity compared to real-life scheduling instances, many of these instances are still considered challenging and are widely used to study the flowshop scheduling problem, both in terms of optimization methods and fitness landscape analysis. Another widely-used testbed is the QAPLIB, that provides several instances of the Quadratic Assignment Problem (QAP) [START_REF] Burkard | QAPLIB-a quadratic assignment problem library[END_REF], as QAP is a non-trivial problem for which a lot of effort has been devoted. QAPLIB comprises randomly-generated instances as well as instances based on real-life data, such as the testing of self-testable sequential circuits or the flow of patients between different facilities in a hospital. DIMACS instances for the graph coloring problem and maximal clique problem are provided in [START_REF] Johnson | Cliques, coloring, and satisfiability: second DIMACS implementation challenge[END_REF]. The families of provided graphs include random graphs, flat graphs or latin square graphs. While this list of instances libraries is not exhaustive, such libraries focus on a single problem or a small set of the same family of problems, and rarely propose a sufficient number of instances differing in variable importance.

In the field of continuous optimization, testbeds are regularly proposed for the GECCO workshop on Black-Box Optimization Benchmarking (BBOB) [START_REF] Hansen | Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009[END_REF].

These testbeds can be found on the widely-recognized benchmarking software COCO [START_REF] Hansen | COCO: A platform for comparing continuous optimizers in a black-box setting[END_REF] for black-box optimization. In addition to a noisy suite, COCO has been recently extended to multiobjective [START_REF] Tušar | COCO: The bi-objective black box optimization benchmarking (bbob-biobj) test suite[END_REF] and mixed integer [START_REF] Tušar | Mixed-integer benchmark problems for singleand bi-objective optimization[END_REF] problems.

Recently, a benchmarking platform IOHprofiler has been proposed for evaluating the performance of iterative optimization heuristics [START_REF] Doerr | Benchmarking discrete optimization heuristics with IOHprofiler[END_REF]. One of its components, IOHexperimenter aims to generate benchmark suites for the benchmarking of such optimization methods. IOHexperimenter covers 23 real-valued (continuous), as well as 25 academic pseudo-boolean problems [START_REF] Doerr | Benchmarking discrete optimization heuristics with IOHprofiler[END_REF].

The aforementioned platforms implement a large panel of problems and are widely-used. These problems are either continuous or present a uniform structure, in which the weight of variables is generally uniform. While such platforms are particularly useful to study heuristic optimization methods, these studies are conducted on structures that are more common on academic problems than on real-ones, and thus cannot efficiently focus on the peculiarities induced by important variables.

Tile Planting instances: Chook generator

Perera et al. [START_REF] Perera | Chook-a comprehensive suite for generating binary optimization problems with planted solutions[END_REF] proposed Chook a python-based generator that generates instances for the Tile Planting (TP) problem [START_REF] Hamze | From near to eternity: spin-glass planting, tiling puzzles, and constraint-satisfaction problems[END_REF]. The goal of this benchmark is to test new quantum computers and algorithms. Indeed, combinatorial problems that can be considered efficiently with quantum computers are expressed as spinglasses problems, and even more particularly as Quadratic Unconstrained Binary Optimization problems (QUBO). TP problems are a benchmark of pseudoboolean objective functions (binary string search space) with known global minima, the planting solutions. These functions are determined by a sum of subfunctions. In the most general form, the fitness function (Hamiltonian) is:

H(s) = j∈V h j s j + n k=2 (i1,...,i k )∈E J i1,...,i k s i1 s i2 . . . s i k with s = (s 1 , s 2 , . . . , s n ), s i ∈ {-1, 1} called
spins, and where the hypergraph G = (V, E) with vertices V and edges E describes the interaction between the problem spins (variables). The coefficients h j ∈ IR define the local external field (energy between the environment and each spin), and the coefficients J ∈ IR the intensity of each interaction. Notice that this equation can be mapped into boolean variables x i ∈ {0, 1} using the classical transformation

x i = 1 2 (1 -s i ).
In most cases these problems can be expressed using only 2-local interactions between spins with a graph G:

H(s) = j∈V h j s j + (i,j)∈E J ij s i s j
In TP instances [START_REF] Hamze | From near to eternity: spin-glass planting, tiling puzzles, and constraint-satisfaction problems[END_REF], the problem graph is decomposed into edge-disjoint and vertex-sharing subgraphs. For a decomposition of the graph G = (V, E) into subgraphs {G l = (V l , E l )} such that no edges are shared among the subgraphs, the coefficients h i are equal to 0, and each subgraph is associated to a quadratic energy function:

H l (s) = (i,j)∈E l J ij s i s j
The energy function of the tile planting problem can then be expressed as the sum of energy functions of each sub-graph:

H = l H l
The sub-functions H l are designed to share a common ground state, i.e. the lowest-energy state of a quantum-mechanical system, which corresponds to the ferromagnetic ground state s = (+1, +1, . . . , +1). Thus by the additive property of H, the Tile Plating problems also have the same ferromagnetic ground state.

TP problems use a regular lattice structure that allows a decomposition of the graph G which contains a subset of the unit cells as subgraphs. In the square lattices version of the problem, the resulting unit-cells form a checkboard pattern (see Fig. 1) and the problem graph corresponds to a toric square matrix. A portfolio of four sub-function classes {C 1 , C 2 , C 3 , C 4 } (see Fig. 2) are defined as follows:

C 1 (s) = -2s 0 s 1 -2s 1 s 2 -2s 2 s 3 + s 3 s 0 ; C 2 (s) = -2s 0 s 1 -2s 1 s 2 -s 2 s 3 + s 3 s 0 ; C 3 (s) = -2s 0 s 1 -s 1 s 2 -s 2 s 3 + s 3 s 0 ; C 4 (s) = -s 0 s 1 -s 1 s 2 -s 2 s 3 + s 3 s 0 .
The portfolio is designed such that each function class C j has j local minima1 . Individually, function C 4 is supposed to be more difficult to solve than C 1 .

In Chook, instances are generated by (1) assigning a sub-function class to each subgraph in the problem, (2) a random rotation of the plaquette in the lattice. Instance classes are defined using a probability distribution over the subfunction classes: p i the probability of selecting sub-functions from class C i such that i p 1 = 1. Generating Tile Planting problems with Chook requires to set 4 parameters: the problem dimension n, and the probabilities p 1 , p 2 , and p 3 . Perera et al. [START_REF] Perera | Chook-a comprehensive suite for generating binary optimization problems with planted solutions[END_REF] analyze the performance of quantum algorithms (simulated quantum annealing) according to the main benchmark parameters p i which can tune the problem difficulty. However in TP instances, the square toric lattice gives an identical role to binary variables. Moreover, the 2d shape of variables interactions allows the solving of such instances in polynomial time complexity [START_REF] Galluccio | Optimization via enumeration: a new algorithm for the max cut problem[END_REF].

PUBO i problems

Here, we propose PUBO i for Polynomial Unconstrained Binary Optimization with importance, a generator in which benchmarks are expressed as Walsh functions, and takes the importance of variables into account. This version uses the same subproblems as in the Tile Planting generator, whose benchmarks correspond to Walsh functions of order 2. These subproblems are straightforward, which allows us to focus on our aim: to tune the variable importance to create more structured instances. Therefore, we focus on the introduction of three new parameters dedicated to this aim. In the following, we provide a mathematical description of Walsh functions. Then we present the first version of PUBO i , as well as the benchmarks considered in our experiments.

PUBO problems

Quadradratic Unconstrained Binary Optimization (QUBO), also known as Unconstrained Binary Quadratic Problem (UBQP) in the context of combinatorial optimization [START_REF] Lü | A hybrid metaheuristic approach to solving the UBQP problem[END_REF], are well known pseudo-boolean functions in the field of physics [START_REF] Date | Efficiently embedding QUBO problems on adiabatic quantum computers[END_REF]. These functions are quadratic functions that can be generalized to any order. Although there exists several names, we denote this extension as PUBO for Polynomial Unconstrained Binary Optimization [START_REF] Glover | Polynomial unconstrained binary optimisation-part 1[END_REF]. Notice that this extension is also known as spin glasses problems in physic. Several construction of PUBO exists, here we choose to present PUBO from the point of view of Walsh functions.

Given a bit string of dimension n, Walsh functions compose a finite set of 2 n pseudo-boolean functions defined for all integer k from [0, 2 n -1] by:

ϕ k : {0, 1} n → {-1, 1} x → (-1) n-1 i=0 kixi
where x i is the i th bit of x, and k i is the i th bit representing the integer k. Walsh functions [START_REF] Walsh | A Closed Set of Normal Orthogonal Functions[END_REF] is an orthonormal basis of pseudo-boolean functions. Any pseudoboolean function f : {0, 1} n → R can be written as:

f (x) = 2 n
k=0 w k ϕ k (x) with w k ∈ R. Indeed, Walsh transform is similar to Fourier transformation, and coefficients w k are computed using the orthogonal projection for the L 2 -norm of f on functions ϕ k :

w k = 1 2 n x∈{0,1} n f (x)ϕ k (x).
Walsh functions allow a decomposition equivalent to a polynomial decomposition. Indeed, using the transformation of bit x i ∈ {0, 1} into spin s i ∈ {-1, 1} defined by s i = (-1) xi , the k th Walsh function can be rewritten as ϕ k (s) = i:ki=1 s i . Thus, the order of a Walsh function ϕ k is defined by the number of bits equal to 1 in the binary representation of k. For example, an order 2 Walsh function written as: w

(0) 0 + n i=0 w (1) i s i + i<j w (2)
i,j s i s j For benchmarking purposes, in addition to being able to represent any evaluation function, Walsh functions allow to fine-tune both the interdependence between the variables (non-zero terms of the polynomial) and the intensity of the interactions (|w k | values). Using integer numbers for w k , neutrality levels (plateaus) can also be tuned.

Definition of PUBO i

The set of PUBO functions is a vector space of dimension 2 n where n is the bit string length. A benchmark based on PUBO has to define a subspace from this large vector space. The proposed benchmark PUBO i is defined with two principles. In order to reduce the dimension, following the TP benchmark design principle, PUBO i decomposes the objective function into a sum of sub-functions from a portfolio. In addition, the binary variables in each sub-function are selected according to tunable parameters of variable importance, to introduce a real-like property. As Tile Planting instances, PUBO i defines the objective as a sum of sub-functions:

∀x ∈ {0, 1} n , f (x) = m i=1 f i (x)
where m is the number of sub-functions, and each sub-function f i is selected at random according to probabilities p j of each sub-function class C j from the portfolio (see Sect. 2.2).

The main originality of the proposed benchmark lies around the notion of variable importance. Each sub-function depends on a limited number of variables. For example in TP instances, each sub-function depends on 4 variables selected according to the square lattices. In PUBO i , variables are selected according to a degree of importance. Indeed, intuitively in real-world problems, important variables should appear more often in sub-problems than least important variables. To define the importance of variables, the set of variables X = {x 1 , . . . , x n } is split into k disjoint classes of importance: c i ⊂ X such that ∪ k c k = X, and c i ∩ c j = ∅ for each pair {i, j}. The number n i of variables in each class is a parameter of the benchmark. Each class of importance c i has a degree of importance d i ∈ IR + . In PUBO i , the probability of selecting a variable in a sub-function is then proportional to the degree of variable importance of its class i: p ci = di k j=1 dj . We also introduce another parameter to tune the co-appearance of variables in the same sub-function. In a real-world problem, one can assume important variables are not randomly distributed among the sub-problems. For some problem instances, important variables could appear together in the same sub-problems, and for other ones, important variables could be linked to less important ones. The following paragraph introduces the principle of co-appearance of important variables in PUBO i .

For a sub-function of arity a, when classes of importance are independent, the probability of having variables of classes c i1 , . . . , c ia is the product of probabilities p ci 1 . . . p ci a . To tune this probability differently, the probability related to the number of each class is necessary. For simplification purposes, let us first suppose there are only 2 classes of importance (0 and 1). We denote p The introduction of a new parameter p c0 to tune the different probabilities is possible. By setting p

(2) 0 = p c0 p (1)
0 , we obtain:

     p (2) 0 = p c0 p c0 p (2) 1 = (1 -p c0 )p c0 p (2) 2 = (1 -p c0 )(1 -p c0 ) + p c0 -p c0
When p c0 = p c0 , the classes of importance of each variable are independent. When p c0 is greater than p c0 , then the probability to have both variables in the same class of importance is higher. On the contrary, when p c0 is lower than p c0 , the sub-functions have more heterogeneous classes of importance.

More generally, an additional variable in the sub-function leads to the recurrence formula: ∀a ≥ 2, ∀i ∈ {0, . . . , a}, p . Therefore we obtain the following values:

             p (a) 0 = (p c0 ) a-1 p c0 . . . p (a) i = (1 -p c0 ) i (p c0 ) a-1-i p c0 . . . p (a) a = (1 -p c0 ) a-1 (1 -p c0 ) + (1 -(1 -p c0 ) a-1 )(1 - pc 0 p c 0 )
As for the arity 2, the value of p c0 determines the independence degree of coappearance of the same class. Let us rewrite the parameter p c0 = α p c0 . When α = 1, the co-appearance of variables importance classes are independent. When α > 1, variables from the same class of importance have a higher probability to appear in the same sub-function, and conversely when α < 1. Remember that globally on all sub-functions, each class of importance appears with a probability proportionally to its degree of importance. To extend to more than 2 classes of importance, we have to consider iteratively the probability to be in class 0, and not to be in class 0, then probability to be in class 1, and in a class greater than 1, etc.

We also propose to shift randomly the global minimum of each sub-function class. Naturally, knowing the global minimum could be useful, yet it would introduce a bias. Indeed, when a sub-problem is solved with the ground state 1111, it also helps the search to solve another sub-problem (shared variables are set to the optimal value). In PUBO i , we propose to shift to a random binary string the minimum for each sub-function to design more challenging instances compared to those of Tile Planting. Of course, the knowledge of ground state is lost and should be approximated by the best known solution for each instance. However, a lower bound of minima can be computed by summing the minima value of each sub-function. Tab. 1 summarizes the parameters of PUBO i benchmark.

The code of the PUBO i generator is available on git https://gitlab.com/ verel/pubo-importance-benchmark. The generator produces a file in json format which follows the same format of Chook generator. As a consequence, all solvers (quantum or classical) can be used to solve PUBO i instances.

Instances set

This instances set aims to provide a large set of PUBO i instances for the analysis of the benchmark parameters impact on the properties of the problems, but also to offer a diverse set instances to train, and test new efficient optimization algorithms for this type of problems, and real-world problems.

In this set of instances, we consider k = 2 classes of importance to distinguish important variables, and non-important variables. The number of important variables is set to 25% of the total number, and as a consequence, 75% of variables are considered non-important. The degree of importance of non-important variables is always set to d 1 = 1, while the degree of important variables is higher from the range [START_REF] Bartz-Beielstein | Benchmarking in optimization: Best practice and open issues[END_REF][START_REF] Hansen | COCO: A platform for comparing continuous optimizers in a black-box setting[END_REF]. Important variables could be up to 10 times more frequent than non-important ones. The factor α is set to be larger than 1 up to the larger possible 1 pc 0 -1 . The problem dimension n is between 1000, and 5000 which is larger than in the TP set, and medium to large size according to the UBQP standard [START_REF] Lü | A hybrid metaheuristic approach to solving the UBQP problem[END_REF]. The number of sub-functions m is proportional to the square of problem dimension. Indeed, the portfolio of PUBO i is the one of TP which defines functions with 4 quadratic Walsh terms. Following the UBQP standard of matrix density, we choose m between 1% and 20% of n(n-1)

2

. Tab. 1 summarizes the range of parameters value.

Instead of factorial design of experiments, we generate 1000 instances of PUBO i using Latin hypercube sampling [START_REF] Carnell | lhs: Latin hypercube samples, r package version 0[END_REF] (LHS), a statistical method for the quasi-random sampling based on a multivariate probability distribution. Thus, in our context, LHS leads to a set of instances that covers a large panel of different parameter combination while significantly reducing the computational effort devoted to the study of such parameters. Indeed, the factorial design alternative either leads to a poorer coverage of the possible combinations or require the consideration of more instances, leading to a tedious process and a significantly higher computation cost. To respect the constraint p 1 + p 2 + p 3 ≤ 1 to define, we reject samples from LHS which do not respect this constraint in order to avoid scaling bias. All instance files in json format are available online at the url https://gitlab.com/verel/pubo-importance-benchmark/instances.

Experimental analysis

This set of experiments aims to highlight whether the parameters we propose impact variable importance, and how variable importance impacts some classic features of fitness landscapes.

Fitness landscapes characterization

The fitness landscape analysis mostly focuses on classic features: the ruggedness/multimodality and the neutrality. The ruggedness, or multimodality of a landscape mainly refers to the number of local optima, their distribution, and the size of their basins of attraction. This property reflects the difficulty to optimize the instance with local search algorithm based on given neighborhood relation. A rugged landscape has several peaks (local optima) hard to attain (small basins of attraction), whereas a smooth landscape has a few peaks easy to attain (large basins of attraction).

Here, we use a widely-used ruggedness indicator, the fitness autocorrelation [START_REF] Weinberger | Correlated and uncorrelated fitness landscapes and how to tell the difference[END_REF]. Given a random walk (x t , x t+1 , . . .) where the solution x i+1 is a neighbor of x i , the autocorrelation function ρ of the fitness function f corresponds to autocorrelation function of the time series (f (x t ), f (x t+1 ), . . .):

ρ( ) = E[f (s t )f (s t+ )] -E[f (s t )]E[f (s t+ )] var[f (s t )]
where E[f (s t )] is the expected value of f (s t ), and var[f (s t )] its variance. In the following, we only consider the first coeffficient of autocorrelation ρ(1), as it usually is enough to summarize the ruggedness levels of landscapes. The neutrality of a fitness landscape refers to the proportion of neutral neighbors in the landscape. A neutral neighbor of a solution has the same fitness value. Neutrality often induces plateaus in the landscape, in which optimization methods can easily be trapped, preventing them to attain better-quality solutions. Thus, a fitness landscape with high neutrality levels can be challenging to optimize. We use the neutrality degree [START_REF] Schuster | From sequences to shapes and back: a case study in RNA secondary structures[END_REF] on neutral moves performed during the random walks (x t , x t+1 , . . .):

deg n (x) = #{f (x i+1 ) = f (x i ) : i ∈ {0, 1, . . .}}.
More precisely, we report the neutral mutation probability degn(x) n which is independent of problem dimension.

The last measure considered for the fitness landscape analysis is the length of the adaptive walk. An adaptive walk is a sequence of neighboring and improving solutions: (x 0 , x 1 , . . . , x ) such for all i ∈ {0, . . . , }, x i+1 is a neighbor of x i , and f (x i+1 ) is better than f (x i ). Such a measure highlights the multimodality (i.e., the presence of several peaks) of fitness landscapes. A short walk is generally the sign of a multimodal landscape, whereas a long walk usually indicates a monomodal landscape. Several adaptive walks exist, and on combinatorial fitness landscape hill-climbers are often considered to this aim. Here, we use a first improvement hill-climber which consists of randomly selecting an improving neighbor at each step of the search, until a local optimum is met. The length of adaptive walk is then the number of steps .

Methodology

We consider the set of 1000 instances generated with LHS. For each instance, we conducted a run of random walk of length 30n. This length is sufficient to provide a sample of solutions, as each variable is flipped 30 times on average, and allows to compute statistics for each variable. We consider a classic neighborhoodrelation of pseudo-boolean optimization problems, 1-flip. 30 adaptive walks are conducted for each landscape, starting from a randomly generated solution, and stopping on a local optimum. The average length of adaptive walks is reported. As our goal is to observe the impact of benchmark parameters, and in particular variable importance on landscape characteristics, we use the mgvc R package [START_REF] Wood | mgcv: GAMs in r. Generalized Additive Mixed Models Using mgcv and lme[END_REF] to generate generalized additive models (GAMs) to highlight the significance of these parameters on the variable importance. GAMs are statistical models that merge the properties of the generalized linear model with those of the additive model. These results are presented through scatterplots of the regression model between landscape features and benchmark parameters.

Results

Fig. 3 shows the scatter plot with the GAM model regression of landscape features, autocorrelation coefficient, the neutral mutation probability, and the length of adaptive walks (see Sect. 4.1), according to the benchmark parameters. Each plot reports the effective degrees of freedom (edf) of GAM, which reflects the degree of non linearity: edf = 1 corresponds to a linear relationship, 1 < edf ≤ 2 is a quadratic, or weakly non-linear relationship and edf > 2 a highly non-linear relationship [START_REF] Zuur | Things are not always linear; additive modelling[END_REF]. The significance values (Signif.) are also reported. The asterisks indicates the p-value at different levels of the statistical significance: '***', '**', '*', '.', and '-' correspond respectively to p-value levels of 0, 0.001, 0.01, 0.1, 0.05, and 1.

The problem dimension (n), the number of sub-functions (m), the degree of importance, and the probability p highly significant impact on the autocorrelation (ruggedness) of landscapes. The factor of independence α has a significant impact on the autocorrelation. The autocorrelation increases, meaning ruggedness level decreases, with the problem dimension, and the factor α. The relation between autocorrelation, and problem dimension is a highly non-linear relationship. Ruggedness levels also decrease with the degree of importance d 0 , and the presence of subproblem C 1 . For these two parameters, the relationship with the autocorrelation is linear. With larger values of m, the ruggedness level increases linearly. Higher ruggedness levels are coherent with a higher number of subproblems as it increases the complexity of the problem, and the interdependence between subproblems. n has the highest impact on the autocorrelation, which is consistent with general results on landscapes. Specific parameters to PUBO i on variable importance also impacts ruggedness levels, among those α has the highest impact.

Another facet of problem difficulty is the neutrality feature. All benchmark parameters n, m, d 0 , α and p 4 (except p 1 , p 2 , and p 3 ) have a significant impact on neutrality level. While increasing both problem dimension and number of sub-functions decrease neutrality rates, higher values of the importance degree d 0 , factor α and p 4 increase these rates. Parameters m and α have the highest effect on neutrality of the problem instances.

The impact of benchmark parameters on the length of adaptive walk is usually lower than for the autocorrelation and neutrality rates. The problem dimension significantly increases this length, as on most combinatorial problems. A larger number of subproblems seems to increase the multimodality of landscapes. Nonetheless, the walk length does not take into account the variation of fitness between two steps of adaptive walks, limiting further interpretations.

The autocorrelation coefficient, and probability of neutral mutation can be computed individually for each variable. This allows to study the impact of benchmark parameters on each importance class of variables. Fig. 4 shows the scatter plot with GAM model regression of the landscape features difference between important and non-important variables versus the benchmark parameters. Both for the autocorrelation and neutrality rates, values are negative, meaning that the contribution of important variables is lower than the one of non-important variables: the subspace of important variables is more rugged, and less neutral (flat) than the subspace of non-important variables. With the increase of n, and m, the impact of important variables on the autocorrelation significantly decreases, with average values respectively ranging from -0.012 to -0.003, and 0.0075 to 0.004. The opposite happens with the importance degree d 0 , where the average difference of autocorrelation values significantly increases from 0.0025 to 0.007. Increasing the importance degree significantly increases the ruggedness contribution of important variables. The factor of independence α has a significant impact on the contribution of important variables to the autocorrelation. When this factor is increased by a small gap, important variable contribute more to the ruggedness. Interestingly, while ruggedness level is low, it seems higher around important variables, possibly indicating these landscapes are globally smooth but locally rugged, as some UBQP landscapes [START_REF] Tari | Sampled walk and binary fitness landscapes exploration[END_REF]. Except for the subproblems C i , PUBO i parameters strongly impact the neutrality level of important variables. Increasing the degree of importance d 0 and the factor α raise the contribution of important variables on neutrality rates. On larger instances and instances with more subproblems, the contribution of important variables wanes while remaining higher than the one of non-important variables. Note that some portfolio subproblems have a higher impact on the using machine learning technique, or the both. The PUBO i generator allows us to facilitate this approach by bringing a large set of diverse instances.

One natural perspective is to able to compare real-world combinatorial problems to PUBO i instances, in particular according to the variable importance property. It would also be relevant to study other possible benchmark parameters such as the number of importance classes, and more deeply the composition of portfolio. Although we have been able to analyze the fitness landscapes of PUBO i instances, new analysis should be conducted using for example Local Optima Network. Moreover, new fitness landscape analysis tools should be designed in order to sharply describe the anisotropy of a landscape. Of course, the goal of this benchmark is to train, test, and understand new optimization algorithms (quantum or classical), and further developments could be conducted in this research direction. The design methodology of variable importance used in PUBO i is generic, and another considered research direction is to extend the generator to other type of optimization problems (continuous, etc.).

Fig. 1 . 2 .

 12 Fig. 1. Depiction of the graph for a 4 × 4 Tile Planting problem instance. Fig. 2. Description of the four sub-function classes for the Tile Planting in Chook.

1 -

 1 having i variables of class 1 in the same sub-function of arity a. Then, we can define this probability recursively. For arity a = 1, p p c0 . The probability to select the class 0 for each subfunction variable should remain the same, hence the additional variable for arity a = 2 should not change the marginal probability, and we have the following equations: p

  By setting the first probability p

  can deduce all other probabilities. It would be possible to introduce a parameter at each arity level: p simplify the benchmark tuning, we use one single parameter p c0 : p

1

 1 Fig.3shows the scatter plot with the GAM model regression of landscape features, autocorrelation coefficient, the neutral mutation probability, and the length of adaptive walks (see Sect. 4.1), according to the benchmark parameters. Each plot reports the effective degrees of freedom (edf) of GAM, which reflects the degree of non linearity: edf = 1 corresponds to a linear relationship, 1 < edf ≤ 2 is a quadratic, or weakly non-linear relationship and edf > 2 a highly non-linear relationship[START_REF] Zuur | Things are not always linear; additive modelling[END_REF]. The significance values (Signif.) are also reported. The asterisks indicates the p-value at different levels of the statistical significance: '***', '**', '*', '.', and '-' correspond respectively to p-value levels of 0, 0.001, 0.01, 0.1, 0.05, and 1.The problem dimension (n), the number of sub-functions (m), the degree of importance, and the probability p 1 of choosing the sub-problem C 1 have a

Fig. 3 .

 3 Fig. 3. Scatterlots features vs. benchmark parameters with GAM model regression.

Table 1 .

 1 Parameters of PUBOi benchmark.

	Parameter	Description	Experimental values
	n	Problem dimension	[1000, 5000]
	m	Number of sub-functions	[0.01, 0.2] × n(n-1) 2
	C	Portfolio of sub-functions	Tile Planting
	pi	Probabilities of sub-function class	[0, 1]

k Number of class of variable importance 2 ni Number of variables in each class of importance n0 = 0.25n, n1 = n -n0 di Degree of importance of each class d0 ∈ [1, 10], d1 = 1 α Probability of importance class co-appearance [1, 1/(pc 0 -1)]

Indeed, j pairs of symmetric local minima

Acknowledgements

Experiments presented in this paper were carried out using the CALCULCO computing platform, supported by SCoSI/ULCO (Service COmmun du Système d'Information de l'Université du Littoral Côte d'Opale).

difference for neutrality levels than ruggedness, indeed C 1 and C 4 contain 3 out of 4 same contribution values.

Discussion and Future Work

The experimental analysis shows that except for parameters which tune the proportion of subproblem classes (p i ), all of PUBO i parameters have a significant impact on ruggedness, multimodality and neutrality levels of landscapes. In particular, parameters related to variable importance could have the same impact on landscape, and so on the problem difficulty, than classical parameter such as problem dimension. Moreover, the tunable importance of the benchmark leads to non isotropic landscapes where the features of landscapes are different for the subspace of important variables. To our best knowledge, this property of importance is rarely taking into account in benchmark design. The difference of landscape features between important and non-important variables shows that this property should be considered in the design of evolutionary, and local search algorithms. In particular, the design of local search operator, and neighborhood should be designed according to the variable importance either by an expert,


Miznah H Alshammary
email: [miznah.alshammary@kcl.ac.uk

Costas S Iliopoulos
email: c.iliopoulos@kcl.ac.uk

Manal Mohamed
email: manal.mohamed@kcl.ac.uk

Fatima Vayani
email: fatima.vayani]@kcl.ac.uk

Application and Algorithm: Maximal Motif Discovery for Biological Data in a Sliding Window

Keywords: Motif Discovery, Sequence Motifs, Bioinformatics application

Since the discovery of motifs in molecular sequences for real genomic data, research into this phenomenon has attracted increased attention. Motifs are relatively short sequences that are biologically significant. This paper utilises the bioinformatics application of the algorithm outlined in [5], testing it using real genomic data from large sequences. It intends to implement bioinformatics application for real genomic data, in order to discover interesting regions for all maximal motifs, in a sliding window of length ℓ, on a sequence x of length n.

Introduction

Alongside the advancement of next-generation sequencing technology, there has been an increase in the production of genomic data requiring de novo assembly and analyses, one such analysis is motif discovery [START_REF] Sinha | YMF: a program for discovery of novel transcription factor binding sites by statistical overrepresentation[END_REF][START_REF] Pavesi | Weeder web: discovery Of tran-scription factor binding sites in a set Of sequences frorn co-regulated genes[END_REF][START_REF] Carvalho | Arm efficient algorithrn for the identification of structured motifs in DNA promoter sequences[END_REF][START_REF] Pisanti | Me: RISOTTO: fast extraction Of motifs with mismatches[END_REF][START_REF] Pissis | MOTeX: A word-based HPC tool for rnotif extraction[END_REF][START_REF] Pissis | MoTeX-ll; structured MoTif eXtraction from large-scale datasets[END_REF]. Motifs, whilst biologically significant, are relatively short sequences. Examples of motifs include protein-binding sites, such as transcription factor recognition sites [START_REF] Van Helden | Extracting regulatory sites from the upstreaxn region Of yeast genes by computational analysis of oligonueleotide fre-quencies[END_REF]. This paper captures the bioinformatics application of the maximal motif discovery to solve real genomic data problems. Using the algorithms in [START_REF] Iliopoulos | Maximal motif discovery irr a. sliding v[END_REF], which differ significantly from the well-established (ℓ, d)motif search problem, this paper seeks to find all ℓ length motifs from a given collection of sequences that occur in at least k sequences, where each occurrence of the motif can contain up to d mismatches [START_REF] Waterman | General methods of sequence comparison[END_REF].

The restricted length of the motif is one limitation of (ℓ, d)-motif search approaches. in fact, a longer or shorter motif could be more significant. Thus, this paper focuses on the more general problem of maximal motif discovery. As a maximal motif m˜ d,k is not determined by a given length, its significance is based on its number of occurrences compared to its substrings. A motif is considered maximal, as it cannot be extended to the left or right without its number of occurrences being reduced.

As importance is placed on the number of occurrences, the first parameter k sets a minimum threshold for the number of occurrences of a reported maximal motif. A motif m˜ d,k, occurs in the ℓ-length window ending at position i in a given string X, each of which must occur at least k times in the window and contain at most d 'don't care symbols'.

The first parameter k sets a minimum threshold for occurrences of maximal motifs. The second parameter d is more restrictive: mismatches occur in up to d specific positions in the motif, known as 'don't care letters' and denoted by ⋄. Therefore, a motif is also maximal, as its 'don't care letters' cannot be specialised without reducing its number of occurrences. For example, given the sequence ACGTTATGTT and d = 1, it should be concluded that the significant motif is A⋄GTT rather than, for instance, GTT, both of which have the same number of occurrences.

However, this important observation would be missed if the restriction of ℓ = 3. Notably, a purely de novo approach is used, with only one sequence needed as input.

Furthermore, Grossi et al. [START_REF] Grossi | Motif trie: efficient text index for pattern discovery with don't cares[END_REF] proposed that the most current combinatorial solution for maximal motif discovery is a data structure termed a motif trie. A motif trie [START_REF] Grossi | Motif trie: efficient text index for pattern discovery with don't cares[END_REF] represents all prefixes, suffixes and occurrence positions of each maximal motif m˜ d,k in the set Md,k of maximal motifs.

This research presents an output-sensitive algorithm with a time complexity of O(nd + d3 • ∑m˜d,k∈Md,k |occ(m˜ d,k)|), where occ(m˜ d,k) is the set of occurrences of m˜ d,k, assuming the input sequence of length n is built on a constant-sized alphabet. Through further research, Iliopoulos et al. [START_REF] Iliopoulos | Maximal motif discovery irr a. sliding v[END_REF] proposed the first online algorithm to find occurrences of all maximal motifs in a sliding window in time, where w is the size of the machine word and DIFFii-1 is the symmetric difference of the set of occurrences of maximal motifs at x [i-ℓ..i-1] and at x[i-ℓ+1..i]. The space complexity of the algorithm presented in this paper is O(ℓ2). This results suggests an improvement in the time required to solve the same problem using the motif trie [START_REF] Fuller | Tho dnaA protein complex with the E. coli chrornosomal replication origin (oriC) armcl other DNA sites[END_REF]; this would instead be occ(m˜ d,k)|). This presents a significant improvement, as a single occurrence of a maximal motif would be reported O(ℓ2). times when using the latter approach. Therefore, the proposed algorithm results in an acceleration of O(d2w) per occurrence of a maximal motif.

Implementing bioinformatics applications was the main motivation for creating a dynamic structure, in order to facilitate a sliding window on the input sequence. Specifically, this endows the additional ability to discover interesting ℓ-length regions of the sequence. This is particularly useful in various forms of bioinformatics, including the prediction of the origin of chromosomal replication (OriC) [START_REF] Leonard | M6chali, Me: DNA replication origins[END_REF]. The length of OriC in model bacterial species ranges from 120 to 300bp; for example, in E. coli, it is 240bp E. coli [START_REF] Meijer | Nucleotide sequence Of the origin Of replication Of the Escherichia coli K-12 chromosome[END_REF].

Additionally, motifs that occur within OriC, such as DnaA boxes, show that d and k are small constants (for example, d = 2 and k = 4) in practice [START_REF] Fuller | Tho dnaA protein complex with the E. coli chrornosomal replication origin (oriC) armcl other DNA sites[END_REF]. Before presenting the results of this paper, the following parameters need to be defined: m˜ d,k occurs in the ℓ-length window ending at position i in a given string X, each of which must occur at least k times in the window and contain at most d 'don't care symbols'. These definitions are used throughout the rest of the paper. The organisation of the rest of this paper is as follows. In section 2, we present preliminaries in detail. This is followed by section 3 where we summarise our contribution and the experimental result to this problem. Finally, we briefly conclude and state the future work in section 4.

Preliminaries

The proposed existing algorithm works online; to use this effectively, one must add a string of letters (̸ ∈ Σ) to the start of x, whilst also appending a unique letter (̸ ∈ x) to the end of x to ensure that the motif graph (augmented suffix tree Tx) of the final window is clear.

Maximal Motif Discovery Algorithm

In order to redefine and extend the original definition of the motif graph, each internal node V of the suffix tree ST is outlined with the following:

• For an internal node V, an integer variable |occ(V)|, which holds the number of occurrences of V in the window of ℓ-length on X and is Seed(V), is now defined relative to the window, not the whole string, Seed(V) is a Boolean variable, which is TRUE if node V is a seed in the window, and FALSE otherwise. • Each node V where Seed(V) = TRUE is further augmented with the following:

• The Boolean variable Motif (V) is TRUE if node V represents a singleton motif in
the window, and FALSE otherwise. • A bit-vector B(V) of total size bits shows the occurrence positions of V in the window. In order to maintain B(V) efficaciously, an integer variable pivot(V) is introduced, which represents an anchor so that B(V) is only updated when an occurrence of V is added or deleted, rather than in every step i of the algorithm. Example 2. Observe that, for example, suffixes 10 and 11 were added as leaf nodes when letter X[16] = C was added.

Deleting a letter from the left

When the leftmost letter α of the window has been deleted, every motif M˜′ =αM˜ ∈M˜i,d,k must be deleted if now occ|M˜ ′| < k in the window. After this possible deletion, the following cases might be considered: 2, the deletion of the leftmost letter (A) would result in the deletion of leaf node 0 which represents the longest suffix. This would cause the subsequent deletion of nodeV2 as it would have one remaining child, the edges fromV1 toV2 andV2 to leaf node 10 would be merged.

• If M˜ =Σ,

Experimental Results and Contribution

Contribution

The patterns that are the focus of this paper are commonly found in molecular structures and, therefore, are biologically important. A traditional desktop-based programming environment was used to display the coding program of the bioinformatics application using Java programming language. The experiment required an Intel Pentium CPU4415U@ 2.30GHz processor, 4.00GB of RAM, a 64-bit Operating System, Windows 10 and MS.Net Framework 4.5.

This experiment sought to find interesting regions within genomes by finding the maximal motif [START_REF] Iliopoulos | Maximal motif discovery irr a. sliding v[END_REF] in the proposed algorithm that works in an online manner. Firstly, the main computational challenge in reporting motifs in a sliding window is the maintaining of the left-and rightmost seeds, which is twofold: verifying their maximality (nodes) and updating their relationship with neighbouring seeds (edges). Such changes to the motif graph identify and, therefore, efficiently update only the subset of motifs occurring at both ends of the window. The following describes the effect on Mi,d,k and the motif graph when adding a letter to the right of the window, and deleting a letter from the left, which simulates the sliding window on x.

This paper has sought to further discover interesting regions in large genomic sequences, by implementing program codes of the algorithm in [START_REF] Iliopoulos | Maximal motif discovery irr a. sliding v[END_REF], and testing it using real genomic data to discover all maximal motifs in a sliding window of ℓ-length= 200, on a sequence x of length n.

The application requires the following input parameters. The values for all the parameters are provided by the end user:

• The length n of the string X.

• The length ℓ of the window on X.

• The maximum number d of allowed don't care symbols.

• The minimum number k of occurrences of maximal motifs.

Figure 3. The application Layout Panel, For the input dataset of the string x, real sequences from the European Nucleotide Archive (ENA) were used. The ENA maintains an extensive record of the world's nucleotide sequencing information, covering raw sequencing data, sequence assembly information and functional annotation. In addition, a database of nucleotide sequences EF445891.1, Escherichia coli strain ATCC 11775 tna operon, was also used [https://www.ebi.ac.uk/ena/data/view/EF445891]. It is important to note that the application utilised could accept any URL of any real genomic dataset input for testing, in order to discover all maximal motifs in a sliding window of ℓ-length= 200.

Implementation

The outline of maximal motif discovery for biological data in a sliding window can be found in the Appendix.

Results

In addition to the research outlined, bioinformatic applications similar to the application of the algorithms presented in this paper are outlined below:

• An experimental study of all UniProt protein sequences to discover novel pairs of circularly permuted proteins using algorithm saCSCr. • An experimental study of bacterial genomes from GenBank to predict the locus of OriC using algorithm MMDSW. • Algorithm EDSM can be utilised to align reads from newly-sequenced genomesto related pan-genomes.

Conclusions and Future Work

In summary, this paper has implemented a bioinformatic application of the motif discovery algorithm, with the purpose of finding biologically significant regions in genomic sequences. In addition, this paper has verified previous theoretical findings by implementing the algorithm in and testing it with real genomic data, in order to discover all maximal motifs in a sliding window of ℓ-length= 200 on a sequence x of length . With regard to future work, one interesting avenue could be finding maximal motifs that occur a minimum number of times in each sequence, given a set of multiple sequences, somewhat resembling the (ℓ, d)-motif search problem. Furthermore, this paper's implementation of maximal motifs could be extended to gapped maximal motifs. Refinement of these results could take place by restricting the minimum length of a maximal motif or adding a probabilistic post-processing step.

Fig. 1 .Example 1 .Fig. 2 .

 112 Fig. 1. The motif graph for the suffix tree of the string x = AGCTAGTTCTAGCTAGCTAG$, given d = 1 and k = 2. Each leaf node has been labelled with the index i of the suffix X[i..n-1] that it represents, where i∈[0,n). Suffix links are shown as dashed directed edges. The set of all internal nodes,{v1,...,v9}, represents the right-maximal repeated factors of x. As |occ(v5)| = 5 = |occ(v1)|, v5 is not a seed; as |occ(v1)| = 5 ̸ = |occ(v8)| = 4, v1 is a seed, and so on. Thus, the set of all seed nodes is {v1,v2,v3,v4,v7}. Motif edges and their labels are bold, All other explicit nodes are labelled V and root node r is outlined in bold. Suffix links are shown as dashed directed edges. Example 1. Given the string x = AGCTAGTTCTAGCTAGCTAG$, the set of seeds is {V1 = AG, V2 = AGCTAG, V3 = CTAG, V4 = CTAGCTAG,V7 = T}.For d=1 and k=2, we find the following set M1,2 of motifs from the motif graph shown in Figure 1.

  and thus M˜ ′ = α, then nothing more is done.• If M˜ ≠ Σ, then M˜ is added to Mi,d,k, ifand only if M˜ (̸ ∈ Mi,d,k) and it is not a prefix of a motif M˜ ′′ ∈ Mi,d,k such that |occ|M˜ ′′| = |occ|M˜ |. Finally, the results are printed Sx, where Sx[i]=|Mi,d,k| and ℓ ≤ i < n.

	Example 3. Considering Figure

Appendix


C A Gizelis
email: cgkizelis@cosmote.gr

A Marinakis

A Litke
email: litke@mail.ntua.gr

Towards a smart port: the role of the telecom industry

Keywords: Ports, Smart Ports, Data Platforms, AI, Blockchain, Privacy

Transformation is not only today's trend but also a reality. Ports could not be excluded from that change. A transformation process has been initiated in order to change their operational structure, and the services they offer. Artificial Intelligent and Data oriented services push the services' landscape beyond the traditional ones that are currently used. The scope of this paper is to analyze and scrutinize the opportunities that are risen for Telecommunications / Information and Communication Technology (ICT) providers at ports. These opportunities are the stepping stone towards the transformation of ports for the future.

Introduction

"DataPorts project aims to boost the transition of European seaports from connected and digital to smart and cognitive, by providing a secure environment for the aggregation and integration of data coming from different sources existing in the digital ports and owned by diverse stakeholders, so that the whole port community could benefit from this data in order to improve their processes, offer new services and devise new AI based and data driven business models" [START_REF] Dataports | [END_REF]. For this purpose, the technological innovation is destined to transform the business as usual, therefore more and more companies hop on that huge wave in order to avoid to be forgotten in the near future as it happened in well branded companies in the past that did not see the need for change [START_REF] Jovic | The transition of croatian seaports into smart ports[END_REF], [START_REF] Molavi | A framework for building a smart port and smart port index[END_REF]. This massive transformation of the businesses has become more data-driven. Inevitable data owners or those that can produce data have become the new major actors. The port industry is no exception and data-driven services is what they should offer, not in the future but today to their end-user, customers, stakeholder (many names exist to define them). According to Deloitte Port Services [START_REF] Berns | Smart Ports[END_REF], Smart Ports is the fourth technological priority in improving and evolving the Shipping / Maritime Industry. By making a port smart, then AI-based services will offer cognitive services that will offer opportunities to Port owners, visitors, customers, etc.

Smart and Cognitive Ports is the newest trend and like the Smart Cities is a creation of a new emerging data market. It is a term that expands the traditional stakeholders' ecosystem with limitless opportunities for new entries. A multi-actor and very diverse ecosystem is created with many opportunities for market expansion, revenue increase, new services, especially data-driven ones such as Internet of Things (IoT) [START_REF] Yang | Internet of things for smart ports: Technologies and challenges[END_REF] and AI-based services. This rapid growing ecosystem with many actors and many roles creates the need for new and dynamic Business Models to fulfill the also rising needs. This opportunity was early identified by European Union in 2014 [START_REF] Volman | Report on Open data[END_REF] and a special chapter was included within the Smart Cities one. "Ports are considered a special case of a Smart Community, then they have to meet the same requirements that are asked for a Smart City, adapted to the port situation".

Ports operate on a certain basis by following a number of models. They can be Public, where the administration is operated by a central authority at a national, regional or city level, or Private, a model that is run by a port company, or even a port (local) society and Hybrid where in this case, public-private partnerships govern the port administration and the provided services. Therefore, Port Authorities whether are Private, Public, or Hybrid, are "forced" to transform and create the Ports of the future, not only by creating an interconnection grid between them but offering new innovative services to their existing "customers" like companies in shipping, supply-chain and logistics, tourism, but also many more from a wide diversity areas, that they can take advantage from the new services. Therefore, Port Authorities create synergies with research community, data owners and providers, software-houses, startups and SMEs in order to, together create new innovative services and expand the list of the potential beneficiaries.

The need of Port Authorities has become an opportunity for port-oriented companies to experiment their wide range of services, algorithms, and data that they own and monetize their offerings in this new emerging market. It is an opportunity, which could be beneficial for numerous stakeholders. This opportunity increases the dynamics of the Smart Ports or Ports of the Future transformation.

The basis for port transformation lays within the co-operation that takes place between strategic partnerships at national and international level. To that we should add partnerships with port-oriented service 3rd parties. The new ecosystem that is created around the ports is highly competitive in order to increase their market share, and ports are trying to get an advantage by implementing smart technologies and services in order to optimize their operations in many areas such as energy, security, transport, logistics and more. Local Port Authorities gather around, numerous entities. Organizations, Associations, Companies that may be stakeholders and potentially beneficiaries of a data-oriented platform provided by DataPorts. The list can be endless if attempt to put everyone in the frame, but trying to pin-point the main ones we can identify synergies within Academia and Research Community, Shipping companies, SMEs and Startups, Public Authorities and Policy Makers, Data Providers, and Local Community Associations (Commercial, Tourism, Culture, etc.)

On the port transformation journey, the Telecommunication industry (also involved in ICT services) can have a significant role and perhaps become a key player towards the transformation success. Telecom (wired and wireless) hold the backbone of the data-driven environment [START_REF] Agarwal | Exploiting rich telecom data for increased monetization of telecom application stores[END_REF], [2], [START_REF] Bonneau | Data monetisation: Opportunities beyond ott: finance, retail, telecom and connected objects[END_REF] through their networks. Therefore, it is on their hand to become leaders in this rapidly increased emerging market. A Telecom/ICT Provider in order to enter this emerging ecosystem and potentially benefit from its growth should firstly address real-life data market use cases in Ports that are related to its areas of operations. The data that a Telecom Provider owns might not be directly usable by Ports' community and interoperability issues should be prior investigated. Data may be provided / shared through advanced AI-based services that are scalable, resilient and using a semantic approach. Data should be designed and provided in a matter that can be governed and maintained in a business manner. For these reasons, new business models and a standardized methodology like [START_REF] Moulos | A robust information life cycle management framework for securing and governing critical infrastructure systems[END_REF] should be defined and adopted respectively. Policies should be also taken under consideration so that a reliable data sharing and trading platform to be established. These design patterns should be obtained under a secure and trusted environment between stakeholder and beneficiaries, internal or external to the Port. Telecommunication industry owns, due to its field of operations, owns, handles and process large volumes of data, real and non-real time. Data that collected and stored from many different services. A Telecom Provider has the largest availability of customers' personal data, network data, mobility tracking, billing location, and so on. The correlation of such datasets, as well as the combination of them with external publicly available data, may potentially create a great value for solving problems and serving future needs. Since it is a new field of operations and due to the fact that until now such data sharing wasn't available for many different reasons, the value or what needs data can solve may be uncertain yet. According to the EU [START_REF] Volman | Report on Open data[END_REF], it is estimated that the open data market is expected to increase by 37% by 2020, reaching e75.7 billion, with the cumulative figure of e325bn. Open data in Greece can generate an additional e3.2bn. GDP and approximately e12 billion in cumulative benefits within 5 years. That led researchers, and other related entities to be highly involved, in order benefit from these numbers.

Related Work

Every Port transformation was focused on different elements. From the Freight loading and uploading in the 1960s, the industrial port and the logistics in the 1980s. Today even with a tighter regulatory environment from the data sharing point of view, the element of transformation is the interoperability and how the ports of the future will become smart and cognitive. The research community and the port related actors are relative active during the last few years. European Authorities turned their attention into three points of action that could potentially affect and transform a Port; the supply, the Platform and the Demand. Various Port Management Platforms / Services / Applications / Systems, where created in order to cover these elements. Supply in order to monitor and handle the operations with the logistics companies, the shipping companies and the freight carriers. Port operations are monitored both for inbound and outbound activities, both equally demanding with different actors in each value chain. Several initiatives in European level, have taken place in the past and some of them are very active even today in order to create an ecosystem around the Ports.

Actions of European Organizations and Associations such as ESPO [13], IAPH

[15] and AIVP [START_REF]The Worldwide Network of Port Cities[END_REF] aim to interconnect and represent Port Authorities and their relationships with EU and other States. They played a vital role in the global trade and practically can be considered as the pioneers of the Smart Ports. In addition to that, ENISA [START_REF] Drougkas | Port Cybersecurity -Good practices for cybersecurity in the maritime sector[END_REF] developed -in collaboration with several EU portsa report that intends to provide a useful information regarding the cybersecurity strategy of port authorities and terminal operators. Moreover, EU -especially through Horizon2020 programs-has funded numerous projects, that aim to create management platforms [START_REF] Kim | An implementation of integrated interfaces for telecom systemsand TMS in vessels[END_REF] for maritime and port environments, in order to create interoperability and eventually the ports to become cognitive and smart. Projects like SmartCities, among others, became

The Marketplace of the European Innovation Partnership on Smart Cities and Communities [START_REF]The Marketplace of the European Innovation Partnership on Smart Cities and Communities[END_REF]. The projects e-Mar, FLAGSHIP, and INMARE [START_REF] Co | [END_REF] handle maritime transport related issues, MASS [START_REF] Co | [END_REF] deals with ways to improve human behavior on board ships with special attention to emergency situations, MARINE-ABC [START_REF] Co | [END_REF] demonstrates the opportunities of the mobile ship-to-shore communication, BigDataStack [5] attempts to optimize cluster management for data operations, SmartShip [START_REF] Smartship | [END_REF] develops data analytics decision support systems and a circular economy based optimization platform. All the aforementioned and other projects prove that research community, port authorities, shipping and supply companies are aligned with a common objective which is the creation of a new ecosystem with advanced data-driven services for the benefit of the ports and the local communities. On top of that, European maritime sector through new calls is planning to offer efficient quality services integrated to the overall European transport system.

Fig. 2. DataPorts value-chain and stakeholders

DataPorts since January 2020 is planning to implement a data management platform to be operated by Port Authorities in order to provide advanced services [Figure 1] and create a value-chain between stakeholders, internal and external ones [Figure 2].

DataPorts Conceptualization

Data in the maritime domain is growing at an unprecedented rate, e.g., terabytes of oceanographic data are collected every month as well as petabytes of data are already publicly available. Big data from different sources such as sensors, buoys, vessels, and satellites could potentially feed a large number of interesting applications regarding environmental protection, security, shipping routes optimization or cargo handling [START_REF] Lytra | A big data architecture for managing oceans of data and maritime applications[END_REF]. Although many projects [START_REF] Smartship | [END_REF], [START_REF] Portforward | [END_REF] are trying to develop data management platforms in various application domains, not many of them have addressed integration in port environments with the possibility of including cognitive services and extending their platform to whole transportation routes around Europe. To this end, Figure 3 presents the main building blocks of the DataPorts platform's proposed solution:

-Data Access: the platform will ensure access to the heterogeneous data sources of the port -including relational and NoSQL databases, object storage, publish/subscribe streams-in a common manner. To achieve this goal, the project will rely on widely adopted data formats and interface specifica-tions, such as JSON [26] and OpenAPI [22] respectively.

-Semantic Interoperability: the project will develop a framework for semantic interoperability of diverse data platforms, autonomous systems and applications. Acting as a unifier, the framework will provide business level interoperability, in addition to data interoperability at the level of common spatial and temporal semantics.

-Data Abstraction and Virtualization: the platform will provide an abstraction layer that takes care of retrieving, processing and delivering the data with the proper quality level, while in parallel putting special emphasis on data security, performance, privacy and protection. This layer, acting as a middleware, will let the data consumers simply define their requirements on the needed data -expressed as data utility-and will take the responsibility for providing these data timely, securely and accurately by hiding the complexity of the underlying infrastructure. The latter could consist of different platforms, storage systems, and network capabilities. The orchestration of those (micro)services could be implemented via flow-based programming tools like Node-RED [START_REF]Node-RED tool[END_REF].

-Data Analytics and AI services: the project will develop a set of data analytics services for supporting the development of descriptive, predictive, prescriptive models using the different datasets available to the platform. Since the project will have to deal with big data technologies, the defined services should be scalable enough to process huge data volumes. Appropriate Stateof-the-Art machine learning algorithms will be identified for supporting the development of cognitive applications in the context of the smart ports domain.

-Blockchain: the platform will provide all the tools for data sharing and trading in a secure and trusted manner. The specific building block should take into consideration the rules defined from data providers to data consumers. On top of that, it has to offer a clear value proposition to data owners. Data access mechanisms, based on purpose control, will also be established. As a result, the solution has to keep provenance of the data entering the platform and implement the functionalities of data governance. The project will exploit permissioned blockchain technology such as Hyperledger [START_REF]Hyperledger Fabric[END_REF], in order to address all these requirements.

Challenges and Opportunities

As mentioned earlier in this paper, the emerging data market within ports is very appealing for a telecommunications provider due to the wide diversity and the large volumes of data that it owns or handles. Although a Telecom Company can benefit in many ways from being involved in such ecosystem and eventually create a new revenue stream [START_REF]Advances in Shipping Data Analysis and Modeling[END_REF], [START_REF] Bonneau | Data monetisation: Opportunities beyond ott: finance, retail, telecom and connected objects[END_REF], considerations should be taken into account, regarding the risks that come in front. Since it is a new marketplace, the legal and regulatory environment cannot be considered as stable. Entering a new area always demands careful business approaches. Since a main involvement contains data sharing, trust should also be taken into account, not only technological but also ethical which might cause otherwise losing a competitive advantage. Towards that direction, DataPorts project aims at designing a trusted marketplace in order to lower privacy barriers associated with the development of innovative data-intensive applications that consume personal data. The scope is to develop mechanisms that will encourage more and more people (travelers, employees, workers etc.), who so far seem to be reluctant, to share their personal utility and behavioral data. This is very likely to be achieved by keeping data subjects fully informed, including them as actual stakeholders and co-owners of the data archive. The goal is to find the balance between the level of risk the people are willing to take and the benefit they expect as users of a personal data platform; in other words, data privacy versus data utility. The fundamental concern of privacy protection is to prevent confidential data from being leaked. However, in the area of IoT and Big Data, some information about the dataset is desired to be revealed by design. Consequently, the quest is to quantify and control the leakage of sensitive information, so that it remains within a tolerated threshold, while allowing certain types of analytics to be performed. In the following paragraphs indicative techniques to fulfill the privacy requirements are presented:

Privacy and compliance by design

In fact, legislation and privacy norms are becoming increasingly strict, but IT solutions for addressing these issues are lacking. Part of the research in Dat-aPorts project will be to provide solutions for logging and auditing access to sensitive data, modeling, managing and enforcing privacy and consent policies, as well as providing the ability to anonymize sensitive data. With such a solution in place, trust becomes a differentiator while auditing and compliance overhead is decreased for both the data processor and controller. As a result, the business challenge addressed is twofold; (i) the need to prove compliance to privacy and security laws, directives and norms in a more automated and systematic manner with less overhead and (ii) the desire to gain end user trust, encouraging the sharing of personal data and improving the quality of the data shared. The approach aims at providing tools and libraries for privacy and compliance by design and also offering such kind of solutions for existing applications without requiring changes to them. The goal is to make privacy and compliance part of the IT infrastructure and to ensure close coupling of all data with relevant consent and policies.

Privacy through data fuzzification

In many occasions, people want to share not their actual data but (slightly) different one, trying to balance privacy and accuracy [START_REF]COSMOS EU Project, End-to-end Security and Privacy: Design and open specification (Final)[END_REF]. For example, residents do not wish to expose their exact location, for a variety of purposes, including privacy considerations and risk data leakage that could aid e.g. criminals to understand the occupancy pattern of their house. In the case of utility and behavioral data, the fuzzification could be multidimensional, in terms of space, time and aggregation of the data that are produced from all the smart devices.

Privacy-enhanced decentralized blockchain-based storage system The initial idea of the blockchain framework was a permissionless distributed database based on the Bitcoin Peer-2-Peer open-source protocol [6], maintaining a growing list of data records hardened against tampering and revision, even by its own operators. This network model protects users from most prevalent frauds like chargebacks or unwanted charges. DataPorts project aims at moving one step forward in context of a data marketplace, strengthening the integrity of the framework in terms of privacy. In a decentralized blockchain architecture as such, a full copy of the blockchain contains -at any time-all records of every transaction ever completed in the network and in addition every block contains a hash of the previous block. This enables the blocks to be traced back even to the first one, known as "the genesis block", which makes computationally prohibitively difficult and impractical to modify a block once it is created, especially as the chain of subsequent blocks gets generated [START_REF] Bheemaiah | Why business schools need to teach about the blockchain[END_REF]. This will protect the privacy-restrictions defined by data subjects, against any possible alternation attempts. The data that is owned along with their process mechanisms, require Intellectual Property protection, especially within a regulatory complexity. Moreover, the development of data agreements and privacy concerns, as well as, a differ-ent than it is used so far, pricing model should be taken under consideration. Risks and potential harms of sharing corporate data, as well as, collecting inaccurate, old or "dirty" data might affect data quality. Since to most of the actions concerning data, the GDPR should be applied, collecting unauthorized data or intrusive collection from individuals and organizations could be a complex process. Therefore, improper or unauthorized access to shared data could cause conflicting legal jurisdictions and different security levels and in some cases loss of regulatory licenses, standards and certifications, reputational and industrial damages, as well as, drop in share price and/or increase in cost of capital. Moreover, incomplete or non-representative sampling, or insufficient, outdated or incompatible data sets can be disastrous, especially in the case where there are many recipients of this new data-sharing/trading platform.

Although someone might say that from all the above described parameters, the risk for a Telecom Provider is forbidding enough to enter this new data sharing/trading market, there is equally amount of opportunities to enter these Open data marketplaces [START_REF]Advances in Shipping Data Analysis and Modeling[END_REF], [START_REF] Miele | Analytics: The real-world use of big data[END_REF]. As it is described in Figures 4 and5, it can be an opportunity for new business and increase in customer / subscribers base. In addition, can create an increased availability of vast and heterogeneous data ecosystems for AI and innovative data-driven business models, as well as, a way to tap into 'safe' personal data. Opportunities can also exist for the Telecom subscribers as well, by obtaining control over personal data. It is considered that the well-being and the quality of life benefits from personal data sharing in key sectors. Moreover, opportunities exist by accessing personalized and cross-sectoral B2C services and increasing the potential of personal data monetization. The entry of a Telecom data owner in this emerging data-driven market, creates opportunities for third parties as well. For academia, by increasing the socio-economic impact of research data across domains and borders, it creates an open innovation access through data marketplaces. Last but not least opportunities can be created in general for Government and Public Bodies thus improving the local economy. These bodies could include, among others, the Municipalities and the Regions that host the Ports. Common use of data through platforms can lead to improved governmental services, especially AI-enhanced digital services. These local and regional opportunities can also lead to an integrated real-time European analytics system exposing annual statistics of the ports ecosystem.

Conclusion and Future Work

A Telecom Provider can benefit from entering such rapidly evolving data market. As in every case, there are considerations and risks that should be taken into account. These parameters will be investigated during the Pilots' execution within DataPorts H2020 Project, where various data sets will be provided and used for cognitive applications. During the Piloting Phase, the value of the data and their governance methods will be thoroughly investigated.

Fig. 1 .

 1 Fig. 1. DataPorts Concept

Fig. 3 .

 3 Fig. 3. DataPorts Architecture

Fig. 4 .

 4 Fig. 4. Challenges & Opportunities for Telecom Industry -A SWOT Analysis

Fig. 5 .

 5 Fig. 5. Business Opportunities

This work in progress is under the DataPorts project that is funded by the European Union's Horizon 2020 Research and Innovation Programme under grant agreement No. 871493.