Fodil Benali
email: fbenali@adwanted.com

Damien Bodénès
email: dbodenes@adwanted.com

Cyril De Runz
email: cyril.derunz@univ-tours.fr

Nicolas Labroche
email: nicolas.labroche@univ-tours.fr

A new Reference-based Algorithm based on Non-Euclidean Geometry for Multi-Stakeholder Media Planning *

Keywords: Computing methodologies → Mathematical optimization, Bio-inspired Approaches; Media Planning, Many objective optimization, Reference pointbased approaches, Decision Maker preference, Evolutionary algorithms

This paper tackles the Campaign Allocation Problem of commercial Ads in TV breaks. The problem is NP-Hard and can be viewed as a multi-stakeholders multiobjective problem with highly competing objectives for different brands and numerous constraints. The expected solutions should be able to focus on, at least, one sub-part of the Pareto Optimal Front according to the decision maker's (DM) region of interest. Consequently, reference point-based many objective approaches could be a good option for solving this kind of problems. However, such approaches suffer from limitations in terms of diversity around the reference points, and other issues due to the fact that they consider the objective space as Euclidean. For the latter, recently a new algorithm called AGE-MOEA, by removing the assumption of Euclidean spaces, has proven to be the best in terms of diversity for a lot of many-objective problems in the literature. Nevertheless, AGE-MOEA has a high computational complexity and cannot be driven to a specific sub-parts of the Pareto Front. For that, we propose a novel approach, called RAGE-MOEA, that combines the AGE-MOEA diversity principles with the convergence elements of reference based approaches. Experiments have shown that this approach obtains better results in terms of compromise between diversity and convergence around the reference points than usual Reference-based methods (R-NSGA-II and R-NSGA-III) on literature benchmarks, and significantly better results for our industrial problem.

INTRODUCTION

Optimization of Advertisement Media plan allocation is an NP-hard combinatorial multiobjective optimization problem that involves several conflicting objectives and complicated constraints [START_REF] Benoist | The TV-break packing problem[END_REF]. Considering a set of advertisers' campaigns (TV advertisements) and a set of commercial breaks with air times (slots), the Campaign Allocation Problem (CAP) [START_REF] Mihiotis | A mathematical programming study of advertising allocation problem[END_REF] consists in determining how campaigns' spots (brands messages) should be allocated to a subset of breaks in order to maximize the total revenue of the TV networks and evenness with respect to the advertisers' requirements and limited advertising inventory restrictions.

To this end, several works have been proposed in the literature, noticeably in the operation research community [START_REF] Benoist | The TV-break packing problem[END_REF][START_REF] Bollapragada | NBC's optimization systems increase revenues and productivity[END_REF][START_REF] Michael | Scheduling advertising slots for television[END_REF][START_REF] Zhang | Mathematical models for the television advertising allocation problem[END_REF]. These approaches tend to formulate the problem based on a single objective with a large number of constraints. In the case of multicampaigns, they treat the campaigns either sequentially [START_REF] Bollapragada | NBC's optimization systems increase revenues and productivity[END_REF] or by considering an aggregated objective [START_REF] Zhang | Mathematical models for the television advertising allocation problem[END_REF] to be solved efficiently by reference solvers such as CPlex [START_REF] Ibm Ilog Cplex | V12. 1: User's Manual for CPLEX[END_REF]. Another approach [START_REF] Peter | Optimal advertising campaign generation for multiple brands using MOGA[END_REF] considers the use of a multi-objective evolutionary algorithm by searching to optimize one objective per campaign (audience coverage) but it does not consider the other objectives to reach for a campaign nor their preferences.

Unlike the previous contributions, our work in [START_REF] Benali | An Enhanced R-NSGA-II For Multiple Brands Advertising Campaign Allocation Problem[END_REF], considers multi-stakeholders configuration, i.e., advertisers, and TV networks, each with their own objectives. They also consider the size of the problem instance, all breaks from a 3 to 6 months period, that may not be appropriate for an exact resolution based on solvers. We consider the same problem configuration in this work. In complements of the mentioned problem, we envision an interactive tool, where planner expert -Decision Maker (DM) -of the TV networks can choose among different solutions to propose to its clients (advertisers). The suggested solutions should present a certain diversity at least in the objective space by considering one or several reference point defined by the DM.

Evolutionary algorithms (EAs) [START_REF] Chand | Evolutionary many-objective optimization: A quick-start guide[END_REF] have been recognized to be well-suited to solve multi-objective problems [START_REF] Cococcioni | Solving the environmental economic dispatch problem with prohibited operating zones in microgrids using NSGA-II and TOPSIS[END_REF][START_REF] Konstantinidis | A multi-objective indoor localization service for smartphones[END_REF], thanks to their ability to provide the decision-maker with a set of trade-off solutions in a single run in addition to their insensitivity to the geometrical features of the objective space. However, in our context, using an EA still raises challenges:

• Many-objective problem: as we consider a large number of objectives, most solutions become equivalent to each other in this objective high dimensionality space, therefore making the algorithm behaves like a random search. The probability of getting new solutions which optimize all objectives decreases exponentially with the number of objectives. Therefore, finding real operational and useful solutions that are better compared to others according to the whole set of objectives is really challenging and requires adapted techniques to support the optimization. • Diversity of solutions: the majority of MOEA use strategies and heuristics that are built upon the implicit assumption that the Pareto Front (PF) has an Euclidean geometry. However, in many MOPs, the PF is convex or concave which impacts the shape and the diversity of the obtained solutions. Though, estimating the shape of the Pareto Front will greatly help the diversity promoting mechanism. • Preference based context: we propose to take advantage of any preferences on the objectives that could be implicitly provided by the expert before the optimization task is performed. In this paper, we focus on, at least, one specific subset of the Pareto-optimal set according to one or multiple reference points that drives the convergence of the EA.

According to their problem which is a sub-part of ours, Benali et al. [START_REF] Benali | An Enhanced R-NSGA-II For Multiple Brands Advertising Campaign Allocation Problem[END_REF] use for instance R-NSGA-II [START_REF] Deb | Reference point based multi-objective optimization using evolutionary algorithms[END_REF] to target their objectives. Despite the fact that their proposal obtains interesting results, they tackle the problem only partially. First, R-NSGA-II is able to deal with several specific subsets of the Pareto Front, but they only consider one in their problem modeling. Second, R-NSGA-II uses Euclidean distance to promote diversity, nevertheless, the Pareto Front may have different shapes that do not fit with Euclidean space assumptions. Finally, Euclidean distance may not be the suitable choice for high dimensional objective spaces. As AGE-MOEA [START_REF] Panichella | An Adaptive Evolutionary Algorithm Based on Non-Euclidean Geometry for Many-Objective Optimization[END_REF] has shown to be the best in terms of diversity promoting in manyobjective optimization problems, our idea is to use its principles of estimating an 𝐿 𝑝 norm that fits well the geometry of Pareto Front in combination with the key elements of reference point approaches. This harmonious combination will allow to obtain solutions that are close enough to the reference points chosen by DM and sufficiently diverse to offer different alternatives. Therefore, the approach presented in this manuscript, called Reference-based Adaptive GEometry Multi-Objective Evolutionary Algorithm (RAGE-MOEA), proposes an adaptation of the R-NSGA-II diversity mechanism inspired by AGE-MOEA principles. It produces solutions that are more diverse than the ones of R-NSGA-II with low computational complexity compared to AGE-MOEA, and less parameters than R-NSGA-III, one of the best reference-based MOEA.

The remainder of the paper is organized as follows: Section 2 describes the related works. Section 3 details the proposed framework RAGE-MOEA while Section 4 describes our experiments. Section 5 presents our industrial case study and the experiments used to validate the proposal. Finally, Section 6 concludes and opens future work perspectives.

RELATED WORKS

Inspired by the work of Benali et al. [START_REF] Benali | An Enhanced R-NSGA-II For Multiple Brands Advertising Campaign Allocation Problem[END_REF], our idea is to use an EA to find Pareto-optimal solutions to the Campaign Allocation Problem. We describe here the main contributions in Multi-Objective Evolutionary Algorithms (MOEAs) and Many-Objective Evolutionary Algorithms (MaOEAs) before emphasizing on the importance of reference points to guide the convergence in high dimensional objective space as the case of our problem of Multi-Stakeholder Media Planning.

Evolutionary algorithms have been widely used in literature to solve multi and many-objective optimization problems (resp. MOPs and MaOPs). The goal of MOEAs is to approximate the optimal Pareto Front with a set of non-dominated solutions. To achieve this, MOEAs attempt to generate non-dominated solutions as close as possible to the PF (proximity or convergence), and that are welldistributed over the optimal PF (diversity).

There are two main approaches to deal with MOPs using EAs. First, decomposition-based algorithms such as MOEA/D [START_REF] Zhang | MOEA/D: A multiobjective evolutionary algorithm based on decomposition[END_REF], NSGA-III [START_REF] Deb | An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[END_REF] and [START_REF] He | Evolutionary many-objective optimization based on dynamical decomposition[END_REF][START_REF] Xiang | A many-objective evolutionary algorithm with Pareto-adaptive reference points[END_REF], where a MOP is decomposed into a number of single-objective problems. Each single-objective problem has the same scalarizing function and a different weight vector. A single solution is assigned to each single-objective problem. All singleobjective problems are optimized in a cooperative manner towards different directions in the objective space along the weight vectors. However such methods rely on multiple parameters (e.g., setup of the reference lines) which is not adequate for a decision maker in an industrial context.

Second, methods that deal with all objectives at the same time. Among the most well-known and efficient MOEAs, the Non dominated Sorting Genetic Algorithm (NSGA-II) [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF]. NSGA-II is an elitist algorithm that uses two types of fitness functions: (i) a primary fitness function that corresponds to the Pareto-optimality and (ii) a secondary crowding distance to promote diversity.

NSGA-II has demonstrated to be one of the most competitive MOEAs through the specialized literature [START_REF] Chand | Evolutionary many-objective optimization: A quick-start guide[END_REF] as it is a simple, parameter-less, and computationally fast (low computational complexity of O(𝑀𝑁 2 )) with elitist approach that enhances the convergence properties. However, it faces difficulties in solving problems with a large number of objectives [START_REF] Deb | Towards estimating nadir objective vector using evolutionary approaches[END_REF][START_REF] Ishibuchi | Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems[END_REF]. This degradation happens when there is a need for an exponentially larger number of points to represent a higher-dimensional Pareto-optimal Front. As a consequence, the emphasis of all non-dominated solutions in a population for a large number of objectives may not produce enough selection pressure for a small-sized population to move towards the Pareto-optimal region fast enough.

Nevertheless, recent studies [START_REF] Ishibuchi | Many-objective problems are not always difficult for Pareto dominance-based evolutionary algorithms[END_REF][START_REF] Meng Pang | NSGA-II with simple modification works well on a wide variety of many-objective problems[END_REF] have shown that NSGA-II can be improved in many objective contexts by focusing on a smaller subset of the Pareto optimal solutions close to a supplied set of reference points such as R-NSGA-II [START_REF] Deb | Reference point based multi-objective optimization using evolutionary algorithms[END_REF] and R-NSGA-III [START_REF] Vesikar | Reference point based NSGA-III for preferred solutions[END_REF]. This allows to relieve the selection burden for the DM, and avoids computational efforts for finding unexpected solutions. The problem with such methods is that they use strategies and heuristics built upon the implicit assumption that the PF has an Euclidean geometry. For example, in R-NSGA-III the reference points are generated using Das and Dennis's systematic approach, which places points on a flat hyper-surface. However, in many MOPs the PF is convex (i.e., hyperbolic geometry) or concave (i.e., spherical geometry). As consequence, this impacts greatly the convergence and diversity of the obtained solutions.

To overcome such limitation, a new MaOEA has been proposed recently, called AGE-MOEA [START_REF] Panichella | An Adaptive Evolutionary Algorithm Based on Non-Euclidean Geometry for Many-Objective Optimization[END_REF]. The idea consists in fitting the geometry of the PF in order to adapt diversity and convergence mechanisms on the Pareto Front shape. AGE-MOA is the best in terms of convergence and diversity of solutions on the Pareto Front. However, it is very time consuming (high computational complexity O(M𝑁 2 + 𝑁 3 )). Moreover, it does not support reference points integration and therefore could not be used for problems where only a subset of the PF is of interest.

In conclusion, the combination of reference based principle with AGE-MOEA Pareto Front fitting could be the good recipe in order to build an efficient MaOEA that is able to generate a diverse set of solutions near DM's preferred regions in a high dimensional objectives space. Details about our idea are developed in the next section.

PROPOSED ALGORITHM

As presented in the introduction, the tool, we want to develop, should (i) converge to solutions optimizing a large number of objectives simultaneously, (ii) assist the DM in choosing the most suitable configurations, according to her regions of interest, (iii) be fast in order to obtain efficient solutions within a limited computational time budget.

The proposed framework, called RAGE-MOEA, inherits from the computational fast and elitist framework NSGA-II, as illustrated in Algorithm 1. It incorporates the reference point concept in order to integrate DM's preferences and uses the AGE-MOEA Pareto Front geometry estimation technique to be adapted to different shapes of the Pareto Front. The objective is to have an efficient management for both of the diversity and convergence around the reference points defined according to DM's preferences in a limited time budget. In the following, we first present an overview of the proposed framework in Section 3.1. Then, we detail the principle components of RAGE-MOEA in Section 3.2, 3.3, and 3.4.

Overview

As outlined in Algorithm 1, the framework starts with an initial set of N solutions (line 2 in Algorithm 1). This initial population of solutions could be randomly generated or empty solutions. Then an exploration mechanism is executed based on proper crossover and mutation operators, depending on the problem, to produce new offsprings (line 4). The offspring population Q is therefore combined with the current population P forming a new population P ∪ Q of size 2 × 𝑁 (line 5). After that, an evaluation process is executed to evaluate for each solution candidate the set of M objective functions (line 6). Once the evaluation process is terminated, a survival selection process is done, to ensure that unfit solutions are eliminated from the population and reduces it back to N individuals (line 7). The steps 4-7 in Algorithm 1, are repeated until a stop condition (e.g., allocated time budget) is satisfied.

The selection process, as shown in Algorithm 2, starts by dividing the population into different levels of non-dominated fronts using the fast-non-dominated sorting (NDS) algorithm [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] (line 2 Algorithm 2). Solutions from the best non-domination levels are chosen front-wise (lines 5-7). The goal of this step is to keep good performance solutions (the most advanced solutions). This elitist strategy will allow to converge faster towards the Pareto-optimal Front.

However, it is commonly the case that the last front could not be entirely maintained to fit the size (N ) of the next generation population. As a consequence, a mechanism has to be established to choose the best individuals to be kept even though between mutually non-dominated solutions (line 9). To do it, for each reference point chosen by the DM, the following steps are performed:

(1) The considered front is normalized using a variant of the normalization procedure defined in NSGA-III [START_REF] Jain | An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach[END_REF] (line 11) (see Section 3.2). (2) The normalized front, then, is used to estimate the L 𝑝 that best fits the front geometry (line 12). More details are described in Section 3.3. (3) Solutions are assigned a survival score that combines both diversity and proximity to the reference Pareto-optimal point (line 13).

Finally, RAGE-MOEA selects the remaining solutions from F 𝑟 according to the descending order (line 15) of their survival scores in order to complete the remaining individuals of the new population P 𝑛𝑒𝑤 (line 16).

Normalization

Normalizing the objective space is an important step in multiobjective optimization problems. In fact, objective functions may have different scales, which leads to a neglecting of one or more objective functions. As a consequence, this impacts how diversity and performance measures of solutions are compared when dominance relations are not sufficient. For that, we suggest to normalize our objective functions by applying the same formula used in [START_REF] Deb | An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[END_REF][START_REF] Panichella | An Adaptive Evolutionary Algorithm Based on Non-Euclidean Geometry for Many-Objective Optimization[END_REF]:

f 𝑖 (𝑆) = 𝑓 𝑖 (𝑆) -R (𝑘) 𝑖 𝑎 𝑖 , ∀𝑆 ∈ F 𝑟 , ∀𝑖 ∈ ⟦1; 𝑀⟧ (1)
Where 𝑓 𝑖 (𝑆) denotes the objective 𝑓 𝑖 for the solution 𝑆 and R (𝑘) 𝑖 is 𝑖 𝑡ℎ component of the 𝑘 𝑡ℎ reference point. The objectives are translated to have the reference point equal to the origin of the axes. Thereafter, a M-dimensional linear hyperplane 𝑍 𝑚𝑎𝑥 is constructed based on the extreme points in each objective axis, i.e.,

𝑧 𝑚𝑎𝑥 𝑖 = max 𝑆 ∈F 𝑟 (𝑓 𝑖 (𝑆) -R (𝑘) 𝑖 ).
The denominator 𝑎 𝑖 is the intercept of the M-dimensional hyperplane with the objective axis 𝑓 𝑖 , and it is obtained by solving the following linear system:

𝑍 𝑚𝑎𝑥 • 𝑎 -1 = 1 M .

Geometry Fitting

To determine the norm L 𝑝 such that the corresponding unit hypersurface best fits the geometry of normalized objectives, we need to find the value of 𝑝 that makes all points in F 𝑟 equally distant to the reference point 𝑅 (𝑖) , which coincides with the origin of the axes ì 0 after the normalization.

The fitting process consists in solving the following system of non-linear equations:

               (𝑓 1 (𝑆 1 ) 𝑝 + 𝑓 2 (𝑆 1 ) 𝑝 + • • • + 𝑓 𝑀 (𝑆 1 ) 𝑝 ) 1 𝑝 = 1 (𝑓 1 (𝑆 2 ) 𝑝 + 𝑓 2 (𝑆 2 ) 𝑝 + • • • + 𝑓 𝑀 (𝑆 2 ) 𝑝 ) 1 𝑝 = 1 . . . (𝑓 1 (𝑆 𝑞 ) 𝑝 + 𝑓 2 (𝑆 𝑞 ) 𝑝 + • • • + 𝑓 𝑀 (𝑆 𝑞 ) 𝑝 ) 1 𝑝 = 1 (2)
where 𝑞 is the number of points in the front F 𝑟 . Several numerical analysis methods have been proposed to resolve such systems of nonlinear equations (e.g., Newton's iterative method [START_REF] Jr | Numerical methods for unconstrained optimization and nonlinear equations[END_REF], Levenberg-Marquardt algorithm). However, such methods are computationally expensive and not suitable for computing the value of 𝑝 in each iteration with negligible overhead.

For that reason, we approximate the value of 𝑝 using the method proposed in [START_REF] Panichella | An Adaptive Evolutionary Algorithm Based on Non-Euclidean Geometry for Many-Objective Optimization[END_REF]. It consists in using the central point of the front F 𝑟 for which the corresponding L 𝑝 exponential equation can be easily computed with an exact method. Moreover, the overall complexity of this method is 𝑂 (𝑀 × 𝑁 ), which makes it a fast procedure to estimate the geometry of the non-dominated front and can be easily incorporated in the cycle of evolutionary algorithms.

Survival Score

To select the best individuals that will participate in the next generation, a survival score based on proximity and diversity is calculated as the following:

𝑆𝑐𝑜𝑟𝑒 (𝑆) 𝑆 ∈F 𝑟 = max 𝑅 (𝑘 ) ∈R 𝑃𝑟𝑜𝑥𝑖𝑚𝑖𝑡𝑦 (𝑘) (𝑆) 2 × 𝐷𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 (𝑘) (𝑆) 1/2
(3)

𝑃𝑟𝑜𝑥𝑖𝑚𝑖𝑡𝑦 (𝑘) (𝑆) = 1 ∥ f (𝑘) (𝑆)∥ 𝑝 (4)
𝐷𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 (𝑘) (𝑆) = 2 𝑖=1 (𝑖) min 𝑆,𝑇 ∈F 𝑟 ,𝑆≠𝑇 ∥ f (𝑘) (𝑆) -f (𝑘) (𝑇 ) ∥ 𝑝 (5)
In fact, for each reference point 𝑅 (𝑘) , the two measures (proximity and diversity) are computed and the value that maximizes its combination is considered as the survival score of the solution. For the proximity measure defined in (eq.4), it is evaluated as the inverse of the distance between the solution and the origin in a reference based normalized objective space. The diversity of the solutions 𝑆 ∈ F 𝑟 is computed as the sum of distances (L 𝑝 norm) to the two adjacent solutions in the front F 𝑟 .

Please note that in AGE-MOEA [START_REF] Panichella | An Adaptive Evolutionary Algorithm Based on Non-Euclidean Geometry for Many-Objective Optimization[END_REF], the survival score is defined by a multiplication between diversity and proximity which can have different magnitudes. As a consequence, this may prioritize solutions located in hollow spaces despite being very far from reference points. In RAGE-MOEA, for each reference point, we normalize the obtained measures (diversity and proximity). After that, we use a combination that makes proximity dominating diversity by penalizing diversity by the square root function and increasing proximity by the square function. Figure 1 illustrates equivalent points for a survival score equal to 1 for both AGEMOEA (Blue graph) and RAGEMOEA (Red graph).

From Figure 1, we can notice from the graph of AGE-MOEA survival score (Blue graph) that a point with small proximity score and large diversity is equivalent to a point with large proximity and small diversity score. This will increase the chance of having points far from a reference point. Unlike AGE-MOEA, RAGE-MOEA survival score is biased on the proximity side. As a result, this will reduce the risk of having points far from reference points for the sake of diversity. Algorithm 3 details the procedure that assigns survival scores in RAGE-MOEA. First of all, two sets are initialized: (i) Ω that keeps track of all solutions with already assigned scores (line 3) and (ii) Ω containing all solutions yet to score (line 2). Then, the proximity score for the solutions in Ω is computed according to (Eq.4) (lines 4-6), and the pairwise L 𝑝 distances between all solutions in F 𝑟 are computed in lines 7-10. After that, the diversity score is calculated within the loop (lines [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF][START_REF] Deb | Reference point based multi-objective optimization using evolutionary algorithms[END_REF][START_REF] Deb | Scalable multi-objective optimization test problems[END_REF][START_REF] Jr | Numerical methods for unconstrained optimization and nonlinear equations[END_REF][START_REF] Peter | Optimal advertising campaign generation for multiple brands using MOGA[END_REF][START_REF] He | Evolutionary many-objective optimization based on dynamical decomposition[END_REF][START_REF] Ishibuchi | Many-objective problems are not always difficult for Pareto dominance-based evolutionary algorithms[END_REF][START_REF] Ishibuchi | Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems[END_REF]. Each time, the procedure retrieves the nearest point (line 13), i.e. the solution that maximizes the proximity, and a crowding parameter is used to group solutions being in a radius of 𝜖 (line 14). Once such points are grouped, they are removed from Ω (line 15) in order to control the extent of obtained solutions. The diversity score for the candidate solution (𝑆 * ) is computed considering the sum of distances to the adjacent points outside its group (line 16). In this way, the diversity of a solution is not impacted by crowded points.

In the R-NSGA-II, the scoring method strongly penalizes the group's crowding score. As a consequence, this encourages keeping points far away from the reference points for the sake of diversity. However, in RAGE-MOEA scoring method, the points of the group Ω * 𝑆 are penalized by a score 50% less than the considered solution 𝑆 * (line 17). Therefore, this gives a chance for these points to appear in the next population proportionally with the score of the remaining points.

Once all solution candidates are scored, we normalized both of the proximity and the diversity using the min-max normalization technique (lines 20-21), and making such that the min value is equal to 1. A temporary survival score is calculated (line 22) and compared to the other survival score evaluation (based on other reference points). The maximum value of the survival score is assigned for each candidate solution (line 23).

Complexity. The computational complexity of Algorithm 3 is 𝑂 (M × N 2 ), where M is the number of objectives and N is the population size. The elements of the overall complexity are:

• 𝑂 (M × N ) for computing the proximity scores in lines 4-6.

• 𝑂 (M × N 2 ) for computing the pairwise distances [START_REF] Cococcioni | Solving the environmental economic dispatch problem with prohibited operating zones in microgrids using NSGA-II and TOPSIS[END_REF][START_REF] Ibm Ilog Cplex | V12. 1: User's Manual for CPLEX[END_REF][START_REF] Deb | Simulated binary crossover for continuous search space[END_REF][START_REF] Deb | Towards estimating nadir objective vector using evolutionary approaches[END_REF][START_REF] Deb | An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[END_REF].

• 𝑂 (N 2 ) for the evaluation of diversity in the loop [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF][START_REF] Deb | Reference point based multi-objective optimization using evolutionary algorithms[END_REF][START_REF] Deb | Scalable multi-objective optimization test problems[END_REF][START_REF] Jr | Numerical methods for unconstrained optimization and nonlinear equations[END_REF][START_REF] Peter | Optimal advertising campaign generation for multiple brands using MOGA[END_REF][START_REF] He | Evolutionary many-objective optimization based on dynamical decomposition[END_REF][START_REF] Ishibuchi | Many-objective problems are not always difficult for Pareto dominance-based evolutionary algorithms[END_REF][START_REF] Ishibuchi | Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems[END_REF]. • 𝑂 (M × N ) for min-max normalization [START_REF] Jain | An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach[END_REF][START_REF] Jain | An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach[END_REF].

• 𝑂 (N ) for score evaluation and comparing [START_REF] Konstantinidis | A multi-objective indoor localization service for smartphones[END_REF][START_REF] Mihiotis | A mathematical programming study of advertising allocation problem[END_REF].

Therefore, RAGE-MOEA is an alternative to R-NSGA-II and R-NSGA-III, which will basically help to obtain a better compromise between diversity and proximity to reference points as illustrated in the next section.

EMPIRICAL STUDY

This section reports the conducted experiments to show the applicability and validity of the proposed approach to solve the reference based multi and many objective optimization problems based on different literature test problems.

In order to evaluate our approach, we answer the following questions:

(1) How does RAGE-MOEA balance between convergence to reference points and diversity in multiobjective optimization context? To investigate this, we propose experiments where state-of-the-art reference based methods R-NSGA-II and R-NSGA-III are compared to RAGE-MOEA using literature based multiobjective test problems. (2) How does our approach scale in terms of the number of objectives? To find out, we conduct experiments on high dimensional objective spaces to assess the scalability of our approach.

Experimentation Environment Settings

We implemented RAGE-MOEA1 in Python using Pymoo [START_REF] Blank | pymoo: Multi-objective optimization in python[END_REF]. Pymoo provides the source code for all benchmark problems as well as of the algorithms we use as baselines in our study. For all MOEAs, we used the same parameter setting reported in the related literature [START_REF] Deb | Reference point based multi-objective optimization using evolutionary algorithms[END_REF][START_REF] Vesikar | Reference point based NSGA-III for preferred solutions[END_REF]. Table 1 shows all parameters values for the evaluated MOEAs. For all the other parameters we use the values suggested by their developers.

In our study, we considered the ZDT [START_REF] Zitzler | Comparison of multiobjective evolutionary algorithms: Empirical results[END_REF] and DTLZ [START_REF] Deb | Scalable multi-objective optimization test problems[END_REF] test benchmarks, with the number of objectives M=2, 3, 5, and 15. Both suites contain several test problems with different properties, such as concave (e.g., DTLZ2, and ZDT2), convex (e.g., convexDTLZ2, and ZDT1), and multimodal (e.g., DTLZ1) PFs. Therefore, such suites are good representations of various real-world scenarios.

For each test problem, we generate multiple reference based test-problems by generating randomly one or multiple reference points. For each reference point R 𝑘 , we use the euclidean distance to extract all the Pareto optimal front (POF) points that are within a radius r of the reference point, such as r is defined as follows:

r = 𝛼 × max 𝑆 ∈POF (𝐷 [R 𝑘 , 𝑆]) -(1 -𝛼) min 𝑆 ∈POF (𝐷 [R 𝑘 , 𝑆])) ( 6
)
where 𝛼 is picked randomly in the interval [0,1]. Figure 2

RAGE-MOEA in Multi-Objective Problem context

To illustrate RAGE-MOEA validity in MOPs context, we study the performance of the proposed solution against two reference based methods R-NSGA-II, and R-NSGA-III. Each time, we show the distribution and proximity of solutions to the reference points based on different shaped multi-objective optimization problems. First, we consider the 30-variable ZDT-1 [START_REF] Zitzler | Comparison of multiobjective evolutionary algorithms: Empirical results[END_REF] test problem. This problem Figure 3 shows the obtained solutions (OPF), the optimal Pareto Front (POF) and reference points. We can clearly see that, for both problems, RAGE-MOEA promotes a well distributed and close solutions to the reference points. On the other side, RNSGA-II and RNSGA-III do not present sufficient alternatives close to each of the reference points. This is because the mechanism used in both of the algorithms takes into consideration the center of groups only and penalizes greatly the candidate solutions of the same group. As a consequence, only the centers of the groups close to reference points are selected which reduces the diversity of the obtained solutions.

RAGE-MOEA in Many Objective Problem Context

To assess the effectiveness of RAGE-MOEA in Many-Objective Problems (MaOPs) context, we use 2 different shaped reference based test problems with M= 5 and 15 respectively. For each test problem, we run each algorithm 30 times to account for their non deterministic nature. In each independent run, we collected the non-dominated front produced by a given algorithm at the end of the search (i.e., when the number of generations is reached) and computed the inverted generational distance (IGD) [START_REF] Zitzler | Performance assessment of multiobjective optimizers: An analysis and review[END_REF] to measure its overall quality. The IGD metric provides a single scalar value measuring both proximity and diversity of the solutions in the front.

The smaller the IGD values, the lower the distance between POF and OPF, i.e., the better the performance of the algorithm. Figure 4 illustrates the results of IGD variation for the three methods.

From Figure 4, RAGE-MOEA performs globally better than R-NSGA-II in 4 out of 4 reference based DTLZ2 test problems with M = 5 and M = 15. For example, for M = 5, RAGE-MOEA has an IGD variation that does not exceed 0.22 compared to an IGD variation that exceeds 0.5 For R-NSGA-II.

For what regards the comparison with R-NSGA-III, we observe that RAGE-MOEA outperforms significantly R-NSGA-III in 3 out of 4 test problems (100% with M = 5 and 50% with M = 15. For example, for concave reference based DTLZ2 test problems, RAGE-MOEA obtains a median IGD value equal to 0.2 compared to a median IGD value equal to 0.46 for R-NSGA-III. However, for M = 15 and particularly for the Reference based convex DTLZ2, R-NSGA-III outperforms RAGE-MOEA. This is due to the mechanism of R-NSGA-III that generates a lot of solutions in the central region of the hyperbolic surface, as in Convex DTLZ2. This is an advantage when compared to the other methods, as the majority of the problems are based on reference points located in the central part of the Pareto Front.

Even though R-NSGA-III outperforms our proposal in some cases, it should be mentioned that it requires the configuration of several parameters (e.g. reference lines), that are not within the reach of DM. In addition, it requires a lot of points in a large dimensionality, which does not correspond to our industrial context, where the idea is to facilitate the task of DM by offering her a small set of solutions in the regions of interest.

Results in this section have confirmed our findings that the use of R-NSGA-II as proposed by Benali et al. in [START_REF] Benali | An Enhanced R-NSGA-II For Multiple Brands Advertising Campaign Allocation Problem[END_REF] does not seem to be the most appropriate choice for our industrial problem presented in Section 5. As R-NSGA-III is better than R-NSGA-II in terms of diversity and convergence, it will be used for comparison in the industrial case study experiments.

INDUSTRIAL CASE STUDY: MULTI-STAKEHOLDER MEDIA PLANNING 5.1 Problem Description

Scheduling TV advertisements involves two types of participants that are television networks (channels) and advertisers (or advertising agencies acting as intermediaries) and can be briefly outlined as follows. After announcing TV shows programs, the TV networks finalize their rating forecasts and set the rate cards for the available advertising breaks. In this paper, we focus on tackling Problem (1), i.e., we do not consider the optimization of spots sequences within breaks. In such context, the rate cards contain:

• The gross price for 1-second of message broadcasting inside the commercial break. The net price depends on the client's contract. • Whether it is a Prime break, which corresponds to periods with a peak of audience. Generally, the price of prime breaks is more expensive than typical breaks. • Expected gross rating point (GRP) for each break. The GRP is an estimator of the ratio of the audience that will be present during the commercial break. This indicator is computed generally for multiple target groups based on socio-demographic criteria like sex and age (e.g. Women13-34, Men13-34) • The date and the timing of the break.

Once rate cards are prepared, the commercial break slots are exposed for selling. On the other hand, the advertisers buy the slots in order to obtain the most efficient advertising campaign. An advertiser's request corresponds to one brand's advertising campaign, and it contains:

• The budget to invest for one brand's advertising campaign (e.g., 800k$).

• The cost per one point (CPP)2 of GRP.

• Percentage of budget to invest in Prime breaks (e.g., 20% of the total budget). • The advertising spot duration (e.g., 15 seconds).

• The brand's competition code, which allow to avoid to have slot allocation with other competitive brands in the same break. The advertising campaigns optimization consists in obtaining a distribution of the available commercial breaks' slots that maximizes the invested budget allocation and achieves the best GRP for each client's brand while maximizing the revenue of the TV networks and maintaining the potential clients' loyalty. Moreover, for each campaign, there is a rate of Prime breaks to reach. As a consequence, this leads to a multi-stakeholders many-objective setting with highly competing objectives for different brands and numerous constraints.

The obtained distribution must take into account clients' constraints and TV networks' inventory restrictions. The major constraints associated with clients' requests are the maximum budget allowed to spend, and the list of brands' commercials that are allowed to be exposed in the same break based on competitive exclusion rules. Besides, the sum of advertised spots' duration cannot exceed the break's length capacity.

According to this industrial context, the desired tool should (i) be able to converge to solutions optimizing all objectives simultaneously -as a consequence, it should not cover the whole Pareto Front -(ii) be fast in order to obtain efficient solutions within a limited computational time budget.

Problem Formulation

In order to formally present the problem, we use the notation presented below.

𝑚 𝑖=1 𝑛 𝑗 1 =1 𝑛 𝑗 2 =1 (𝑥 𝑖 𝑗 1 * 𝑥 𝑖 𝑗 2 * 𝑓 𝑐 ( 𝑗 1 , 𝑗 2 )) = 0, 𝑗 1 ≠ 𝑗 2 (13) (12)
The problem objective functions and constraints could be divided into two categories, as follows: 5.2.1 Client Side. Optimize for each client's brand 𝑟 𝑗 , a set of objectives defined as follows:

• Objective function [START_REF] Cococcioni | Solving the environmental economic dispatch problem with prohibited operating zones in microgrids using NSGA-II and TOPSIS[END_REF] consists in maximizing the GRP goal attainment, by minimizing the absolute difference between the achieved GRP and the aimed GRP (𝐺𝑅𝑃 𝑗 ). • Objective function [START_REF] Ibm Ilog Cplex | V12. 1: User's Manual for CPLEX[END_REF], maximizes budget invested in prime breaks, by minimizing the absolute difference between the allocated prime breaks budget and the invested prime breaks budget (𝑃𝑅𝐼𝑀𝐸 𝑗 ).

In the context of media planning, we have to maximize the budget allocation in order to satisfy the clients' requirements but without exceeding the budget invested by each client. Hence, a budget constraint [START_REF] Deb | An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[END_REF] is needed for each brand. Please note that in the general case, 1-s advertising price 𝑐 𝑖 𝑗𝑘 depends on the break 𝑏 𝑖 and the client contract for the brand 𝑟 𝑗 . To illustrates the utility of this objective function, let consider a 60second commercial break for which we have four brands requests with spot duration of 20, 20, 30, and 30 seconds, each paying 1400, 1500, 800, and 900 dollars per second. For each client, we have a priority which is defined by the TV networks based on client's potential and loyalty. Supposing that, clients' requests having a priority of 30, 10, 10, 30 respectively. It is clear that several combinations are possible. The best in terms of revenue has a cost of 58000 (20 * 1400 + 20 * 1500). In terms of priority, the best solution has a cost of 55000 (1400 * 20 + 900 * 30). Hence, there is a real need to define both objective functions in order to get a diverse set of solutions while respecting the Commercial break length constraint [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] and not allowing competing brands to be advertised in the same break (13).

Industrial Experimentation

To illustrate the validity of the proposed approach in our industrial context, we answer the following research question:

(1) To which extent our approach is sensitive to the the Decision Maker choices? We set up an experiment where we change the reference point so as to reflect possible DM's different preferences on the objectives.

For our experiments, we use 2 private datasets devoted to media planning. The first dataset contains 1000 breaks (𝑚 = 1000, i.e., low dimensional search space) and the second dataset contains 10000 breaks (𝑚 = 10000, i.e., high dimensional search space).

In all experiments, we consider the following parameters: the population size is set to 40, the time budget (stopping criterion) is set to 180 sec. Together, these two parameters imply a fair and objective evaluation of the algorithms in our real-time industrial context. Evolutionary operators parameters are set to standard configurations: the mutation probability 𝑝 𝑚 = 1/𝑚 and the crossover probability 𝑝 𝑐 = 1.

Interest Of Reference Point For Decision Maker.

In order to study the flexibility of the proposed method and to which extent it is capable to satisfy DM's preferences, we evaluate each approach's performance by perturbing the reference point. Each time, we evaluate the absolute percentage error of the GRP attainment (eq. 7) and the Prime budget achieved (eq. 8) for 6 brands's requests (M = 14) competing over a pool of 1000 commercial breaks (𝑚 = 1000). For that, in a first experiment, we produce a full perturbation by modifying all the objectives so that they are optimized up to 70% of the optimal values. In a second experiment, we perturb the reference point partially by setting only the first and second brands' objectives to be optimized up to 50%. Figures 5 and6 show respectively the impact of the full and partial perturbation of the reference point on the quality of the optimization. From Sub-Figures 5a and5c, we can observe that, a full perturbation of the reference point results results in a degradation for all objectives (GRP and Prime for each brand's request). The variation of errors are globally around 0.3. This results was confirmed in Sub-Figures 6a and6c, where we can notice partial degradation for the objectives of the first and second brands' requests (variation error around 0.5). The rest is fully optimized.

In the other side (Sub-Figures 5b,5d, 6b, 6d), we can clearly see that R-NSGA-III does not focus on the regions of interest (close to chosen reference points).

As a consequence, these results validate the effectiveness and the sensitivity of our proposed framework to DM's reference point. This allows to incorporate the DM in the process of scheduling and gives her/him a large flexibility for prioritizing some brands' requests and objective functions without impacting the others.

CONCLUSIONS

In this paper, we have introduced a novel reference based MOEA, called RAGE-MOEA, whose convergence mechanisms considers both the diversity among the population members, and the proximity to DM's reference points. Unlike state-of-the-art Reference based MOEAs, RAGE-MOEA does not make any assumption about the geometry of the Pareto front. Instead, it estimates the geometry of the front by fitting an L 𝑝 norm. Consequently, this allows to best model the concept of diversity and proximity in DM's region of interest for different shaped pareto fronts.

To assess the performance of our proposal, several experiments have been executed based on different shaped literature benchmarks. Each time, we vary the number of objectives M ∈ {2, 3, 5, 15}. The achieved results offer currently the best compromise between diversity and convergence around reference points compared to R-NSGA-II and R-NSGA-III. Applying RAGE-MOEA in the industrial context has confirmed our findings and results have shown that RAGE-MOEA is very sensitive to DM's choices.

As future works, we will develop the concept of preference by allowing the DM to select the density (number of solutions) in each region of interest. In a second step, we envision to tackle the problem of search space diversity based on clients' profiles to build an interactive and personalized media plan allocator system.

Algorithm 1 :

 1 RAGE-MOEA Framework. Input: Number of Objectives M, Size of the Population N, Reference Points R; Output: Final population P;

Algorithm 2 : 2 F 3 P 6 P 16 P

 223616 RAGE-MOEA Survival Selection. Input: Population P, Population objectives' scores F, Target population size N, Reference Points R; Output: Next generation population P 𝑛𝑒𝑤 ; 1 begin ←-Fast-Non-Dominated-Sort(P, F); 𝑛𝑒𝑤 ←-∅; 4 𝑟 ←-1; 5 while | P 𝑛𝑒𝑤 | + |F 𝑟 | ≤ N do // Frontwise Selection 𝑛𝑒𝑤 ←-P 𝑛𝑒𝑤 ∪ F 𝑟 ; 7 𝑟 ←-𝑟 + 1; 8 end 9 if | P 𝑛𝑒𝑤 | < N then // Remaining Solution Selection 10 foreach R (𝑘 ) ∈ R do 11 F (𝑘 ) ←-Normalize(F 𝑟 , R (𝑘 ) ); 12 𝑝 ←-Fit-P-Norm(F 𝑟 , F (𝑘 ) ); 13 Calculate-Survival-Score(F 𝑟 , 𝑝, 𝑘, 𝜖); 𝑛𝑒𝑤 ←-P 𝑛𝑒𝑤 ∪ F 𝑟 [1 : ( N -| P 𝑛𝑒𝑤 |) ];

Figure 1 :

 1 Figure 1: RAGEMOEA Vs AGEMOEA survival scores.

Algorithm 3 : 9 D[𝑆 1 , 15 Ω 18 Ω; 19 end 20 Proximity

 39115181920 RAGE-MOEA Survival Score. Input: Pool of Non-Dominated-Front F 𝑟 , Exponent 𝑝 of estimated 𝑛𝑜𝑟𝑚 , 𝑘 index of the reference point, crowding parameter 𝜖; 𝑆 2 ] ←-∥ f (𝑘 ) (𝑆 1 ) -f (𝑘 ) (𝑆 2 ) ∥ 𝑝 ; | > 0 do 13 𝑆 * ←arg max 𝑆 ∈Ω,𝑆∉Ω Proximity[S]; 14 Ω * 𝑆 ←-Subset 𝑆 ∈Ω (D[𝑆 * , 𝑆]< 𝜖); ←-Ω \ Ω * 𝑆 ; 16 Diversity[𝑆 * ] ←min 𝑆 1 ∈Ω 𝑆 D[𝑆 * , 𝑆 1 ] + min 𝑆 2 ∈Ω 𝑆 ,𝑆 1 ≠𝑆 2 D[𝑆 * , 𝑆 2 ]; 17 Diversity[Ω * 𝑆 ] ←-Diversity[𝑆 * ]/2 ←-Ω ∪ {𝑆 * , Ω * 𝑆 } ←-Min-Max-Normalization(Proximity); 21 Diversity ←-Min-Max-Normalization(Diversity); 22 New-Survival-Score ←-𝑃𝑟𝑜𝑥𝑖𝑚𝑖𝑡 𝑦 2 × 𝐷𝑖𝑣𝑒𝑟𝑠𝑖𝑡 𝑦 1/2 ; 23 Survival-Score ←max(Survival-Score, New-Survival-Score); 24 end

  illustrates two reference based DTLZ-problems (Sub-Figure 2a concave reference based DTLZ2, and Sub-Figure 2b convex reference based DTLZ2).

  (a) 𝛼 = 0.05. (b) 𝛼 = 0.15.

Figure 2 :

 2 Figure 2: Reference based DTLZ test problems.

Parameters M = 2 , 3 M = 5 M = 15 Population= 1 SBX Distributed Index [ 9 ]

 2351519 𝜂 𝑐 = 10 has a convex PF and two objective functions (𝑛 = 30, M = 2). Next, we use the DTLZ-2 [14] test problem (𝑛 = 11, M = 3) which has a concave PF. Two widely separated reference points are chosen for both of the problems: R 𝑍 𝐷𝑇 -1 = {(0.5, 0.2), (0.1, 0.6)}, R 𝐷𝑇 𝐿𝑍 -2 = {(0.8, 0.2, 0.2), (0.2, 0.2, 0.8)}. Finally, to make the three algorithms comparable, we use the same norm (euclidean norm) and the same value of 𝜖 (𝜖 𝑍 𝐷𝑇 -1 = 0.1, 𝜖 𝐷𝑇 𝐿𝑍 -2 = 0.001) in both of test problems to control the diversity of the obtained solutions.

  (a) Concave DTLZ2, M = 5. (b) Convex DTLZ2, M = 5. (c) Concave DTLZ2, M = 15. (d) Convex DTLZ2, M = 15.

Figure 4 :

 4 Figure 4: IGD variation achieved by the RAGE-MOEA and the baselines on the Generated Reference based DTLZ benchmarks with M=5, and 15 objectives.

  (a) RNSGA-2, ZDT1. (b) RNSGA-3, ZDT1. (c) RAGE-MOEA, ZDT1. (d) RNSGA-2, DTLZ2, 𝜖 = 0.001. (e) RNSGA-3, DTLZ2, 𝜖 = 0.0001. (f) RAGE-MOEA, DTLZ2.

Figure 3 :

 3 Figure 3: Preferred Obtained solutions using RNSGA-2, RNSGA-3 and RAGE-MOEA (POF: Blue, OPF: Orange).

5. 2 . 2

 22 TV Networks Side. a global optimization is required:• Objective function[START_REF] Deb | Simulated binary crossover for continuous search space[END_REF], maximizes the total revenue of the TV Networks. • Objective function[START_REF] Deb | Towards estimating nadir objective vector using evolutionary approaches[END_REF], maximizes slots allocation based on client's potential and loyalty (𝑃𝑅𝐼𝑂𝑅𝐼𝑇𝑌 𝑗 ).

  (a) GRP error (RAGEMOEA). (b) GRP error (RNSGA-3). (c) Prime error (RAGEMOEA). (d) Prime error (RNSGA-3).

Figure 5 :

 5 Figure 5: Impact of full perturbation of the optimum reference point on the absolute percentage error variation of the GRP and Prime Budget.

  (a) GRP error (RAGEMOEA). (b) GRP error (RNSGA-3). (c) Prime error (RAGEMOEA). (d) Prime error (RNSGA-3).

Figure 6 :

 6 Figure 6: Impact of Partial perturbation of the optimum reference point on the absolute percentage error variation of the GRP and Prime Budget.

Table 1 :

 1 Shared parameters for all experiments. n denotes the number of decision variables.

  .., 𝑏 𝑚 }; 𝑚 number of commercial breaks; 𝑖 index of commercial break; 𝑇 𝑖 length of the commercial break 𝑏 𝑖 , in seconds; 𝑅 set of brands to advertised, 𝑅 = {𝑟 1 , ..., 𝑟 𝑛 }; 𝑛 number of brands to be advertised; 𝑗 index of the brand ; 𝑔𝑟𝑝 𝑖 𝑗 the value of grp in the 𝑖 𝑡ℎ break, for the category mentioned in the request 𝑗; 𝑡 𝑗 advertising message duration for the brand 𝑟 𝑗 ; 𝑥 𝑖 𝑗 1 if the brand 𝑟 𝑗 is advertised in the break 𝑏 𝑖 , 0 otherwise; 𝑐 𝑖 𝑗 cost of 1 second-advertising, in the break 𝑏 𝑖 , for the brand 𝑟 𝑗 ; 𝑓 𝑝 1 if the ith break is prime break, 0 otherwise; 𝑓 𝑐 1 if 𝑟 𝑗 1 and 𝑟 𝑗 2 are in competition, 0 otherwise;

				Subject To:
	Using the notation above, we present the mathematical problem
	formulation as follows:
		𝑚
	min |	𝑥 𝑖 𝑗 * 𝑔𝑟𝑝 𝑖 𝑗 -𝐺𝑅𝑃 𝑗 |, 𝑗 ∈ ⟦1; 𝑛⟧	(7)
	𝑚	𝑖=1
	min |	𝑥 𝑖 𝑗 * 𝑐 𝑖 𝑗 * 𝑡 𝑗 * 𝑓 𝑝 (𝑖) -𝑃𝑅𝐼𝑀𝐸 𝑗 |, 𝑗 ∈ ⟦1; 𝑛⟧	(8)
	𝑖=1			𝑚	𝑛
		max	𝑥 𝑖 𝑗 * 𝑐 𝑖 𝑗 * 𝑡 𝑗	(9)
			𝑚	𝑖=1 𝑛	𝑗=1
		max	𝑥 𝑖 𝑗 * 𝑃𝑅𝐼𝑂𝑅𝐼𝑇𝑌 𝑗	(10)
			𝑖=1	𝑗=1

𝑚 𝑖=1 𝑥 𝑖 𝑗 * 𝑐 𝑖 𝑗 * 𝑡 𝑗 ≤ 𝐵𝑈 𝐷𝐺𝐸𝑇 𝑗 , 𝑗 ∈ ⟦1; 𝑛⟧ (11) 𝑛 𝑗=1 𝑥 𝑖 𝑗 * 𝑡 𝑗 ≤ 𝑇 𝑖 , 𝑖 ∈ ⟦1; 𝑚⟧

The source codes are available at https://github.com/AdwLab/RAGE-MOEA

the CPP is used in this problem formulation to compute the total GRP to reach. In fact, the aimed GRP to reach is calculated as the invested budget divided by the CPP.


Sergi Alcaide

Guillem Cabo

Francisco Bas

Pedro Benedicte

Fabio Mazzocchetti

Francisco J Cazorla

Jaume Abella

Unboxing the Sand: on Deploying Safety Measures in the Programmable Logic of COTS MPSoCs

Keywords: safety, observability, controllability, MPSoC, programmable logic

The lack of sufficient hardware support for functional safety precludes the full adoption of many Commercial Off-the-Shelf (COTS) MPSoCs in safety-related systems, such as those in the aerospace industry. Some recent MPSoCs come along with programmable logic (PL), primarily intended to offload some specific complex functions that can be much more efficiently implemented in hardware than in software, hence being such PL a kind-of-sandbox fully mastered by ASIC cores outside the PL.

This paper proposes using PL in those COTS MPSoCs to deploy the support needed to implement safety measures efficiently to enable the use of those MPSoCs for systems needing high assurance levels. Hence, the goal is not mastering PL from the cores solely, but also allowing PL to provide monitoring (e.g. contention, diversity, watchdogs) and control (e.g. configuring QoS features) capabilities to enable the realization of a safety concept atop. The early work presented in this paper already provides specific monitoring, diversity, and controlling strategies to allow PL take over safety-related functionalities.

I. INTRODUCTION

Increased automation and autonomy in safety-related systems requires higher performance platforms able to execute those safety-critical tasks within tight time bounds. This can be achieved by using high-performance heterogeneous MultiProcessor Systems-on-Chip (MPSoCs) that include some form of accelerator (e.g. GPU, DSP, vector accelerator, and the like). For instance, platforms such as the NVIDIA Drive PX2 in the automotive domain [START_REF] Nvidia | Scalable supercomputer for autonomous driving[END_REF], and the Xilinx Zynq UltraScale+ in the avionics domain [START_REF][END_REF] emerge as candidates to meet the corresponding performance goals.

Unfortunately, while those platforms provide the raw performance required, they challenge certification against safety standards due to their limited support to implement safety measures atop [START_REF] Perez-Cerrolaza | Multi-core devices for safety-critical systems: A survey[END_REF]. In particular, safety-related MPSoCs are generally expected to come along with native hardware support for independent watchdogs, diverse redundancy, error detection, etc. This is, for instance, the case for the Infineon AURIX processor family often used in the automotive domain [START_REF] Infineon | AURIX Multicore 32-bit Microcontroller Family to Meet Safety and Powertrain Requirements of Upcoming Vehicle Generations[END_REF], which on the other hand provides limited performance. Overall, end users face a conundrum between using platforms with appropriate hardware support to implement the safety measures needed at system level [9], [START_REF]/ ED-12B, Software Considerations in Airborne Systems and Equipment Certification[END_REF], but insufficient performance, or using high-performance platforms lacking sufficient native hardware support to deliver mandatory safety measures.

As part of our recent work, we have devised and deployed a number of hardware components highly convenient to implement safety measures on top, as well as to improve testability, such as a multicore interference-aware statistics unit (SafeSU) [START_REF] Cabo | SafeSU: an extended statistics unit for multicore timing interference[END_REF], a module to enforce diversity across cores executing tasks redundantly (SafeDE) [START_REF] Bas | SafeDE: a flexible diversity enforcement hardware module for light-lockstepping[END_REF], and a programmable on-chip traffic injector to test timing and functional behavior during MPSoC validation and during operation (SafeTI) [START_REF] Sala | SafeTI: a hardware traffic injector for mpsoc functional and timing validation[END_REF]. Those components are undergoing the final steps of their integration [7], [START_REF]SELENE website[END_REF] in commercial NOEL-V based MPSoCs for the space domain by Cobham Gaisler [START_REF] Gaisler | NOEL-V Processor[END_REF], and are offered as open source components [START_REF]Safety-Related Hardware Components webpage[END_REF]. However, those components rely on being integrated in MPSoCs during the design phases, hence with the ability to introduce some -yet limitedmodifications related to the observability of some signals and control of some features.

Some MPSoCs, such as the Zynq UltraScale+ family, include some Programmable Logic (PL) as part of the SoC, typically intended to implement efficiently some functionalities, where the ASIC cores act as masters, and the PL as slave (e.g. working as an accelerator where cores offload some computation). In this context, the PL can be seen as a sandbox just responding to requests from the cores, where the latter truly exercise control over the MPSoC.

This paper contends that, enabling the use of highperformance MPSoCs for safety-related applications can be achieved by leveraging PL as a means to deploy hardware support to implement safety measures in COTS MPSoCs. In particular, we note that, if privileges (e.g. user mode, supervisor mode, etc.) are managed properly, functionalities in the PL can span beyond the sandbox by monitoring autonomously parts of the SoC and taking actions to control a subset of the MPSoC features. To illustrate this approach, in this work, and focusing on the Xilinx Zynq UltraScale+ MPSoC as a research vehicle, we show how safety-related hardware components can be deployed in the Zynq's PL to implement a number of safety measures such as (1) multicore interference monitoring building on the SafeSU [START_REF] Cabo | SafeSU: an extended statistics unit for multicore timing interference[END_REF],

(2) support for diverse redundancy building on the SafeDE [START_REF] Bas | SafeDE: a flexible diversity enforcement hardware module for light-lockstepping[END_REF], and (3) support for device diagnostics building on the SafeTI [START_REF] Sala | SafeTI: a hardware traffic injector for mpsoc functional and timing validation[END_REF], among other features.

The rest of the paper is organized as follows. Section II briefly introduces the Xilinx Zynq UltraScale+ MPSoC, as well as SafeSU, SafeDE and SafeTI. Section III presents the strategies being studied to allow the successful integration of the latter components (and some others to be developed) in the MPSoC. Finally, Section IV concludes this paper with a discussion on the forthcoming developments and opportunities emanating from this work.

II. BACKGROUND

In this work, we analyze how to deploy safety-related hardware components in the PL of a MPSoC. Without loss of generality, we focus on a Xilinx Zynq UltraScale+ (ZUS for short) MPSoC. Hence, this section introduces the ZUS, as well as the already available safety-related components.

A. Xilinx Zynq UltraScale+ MPSoC

The ZUS is a powerful MPSoC including a highperformance computing application cluster, referred to as APU, which includes 4 Arm Cortex A53 cores and a shared L2 cache. It also includes a real-time computing cluster, referred to as RPU, which includes 2 Arm Cortex R5 cores. Other computing elements such a GPU and PL are also present in the ZUS. Multiple memories and memory controllers are included in the ZUS, such as a DDR controller, an On-Chip Memory (OCM), and controllers to access flash memories. Multiple peripherals such as PCIe and Ethernet ports are also included. All those components are connected by means of a distributed network, so that traffic across different components can be fully segregated. For instance, independent routes exist from the APU to the DDR controller, from the PL to the OCM, and from the GPU to the DDR controller.

ZUS' interconnect builds on Arm components such as the CoreLink CCI-400 Cache Coherent Interconnect, and the CoreLink NIC-400 Network Interconnect, which include further Arm components, all of them implementing multiple and flexible QoS features, as shown in [START_REF] Serrano-Cases | Leveraging Hardware QoS to Control Contention in the Xilinx Zynq UltraScale+ MPSoC[END_REF].

B. Hardware Components Supporting Safety Features

The work in this paper focuses initially in three already existing components supporting safety features, although we plan to develop and deploy additional ones. Those components, whose existing deployment in a commercial MPSoC is illustrated in Figure 1, are as follows:

SafeSU. The SafeSU statistics unit [START_REF] Cabo | SafeSU: an extended statistics unit for multicore timing interference[END_REF] includes observability and controllability channels to master multicore interference in MPSoCs. In particular, it collects statistics about how many cycles each master is delayed by each other master in an AMBA Advanced High-performance Bus (AHB) interface. Such information is particularly useful to diagnose timing overruns during operation and to optimize application deployment so that multicore interference is kept low.

The SafeSU also includes a multicore interference quota mechanism so that, if the observed interference caused by one master on another exceeds a user-programmed quota, an interrupt is raised. This allows limiting interference during operation.

Finally, the SafeSU includes specific logic to measure the highest latency experienced by a request in the AHB interface. Such information is collected per request type (e.g., read/write, burst/no-burst, etc.) and allows collecting maximum latencies used for Worst-Case Execution Time estimation, and also allows monitoring during operation whether latencies exceed a user-programmed threshold, which could be used as a form of watchdog.

SafeDE. The SafeDE is a module intended to enforce the staggered execution of a given task running redundantly in two cores. This feature is particularly useful to achieve some form of lockstepping (i.e. efficient diverse redundancy) in processors lacking it natively or, at least, lacking it for its highest performance cores. SafeDE collects the number of instructions executed by the cores running the redundant task, and whenever the advantage of the head core falls below a given threshold w.r.t. the trail core, SafeDE stalls the trail core for a while until the staggering is large enough.

SafeTI. The SafeTI is a sophisticated and programmable traffic injector able to inject specific traffic patterns whose elements are read and write operations, with parameterizable data transmitted, with user programmable source/destination, with a burst/no-burst parameter, with independent and programmable stalls between transactions, and with capability to store multiple independent or overlapping traffic patterns that may be used under different circumstances. As explained before, SafeTI is particularly adequate to test the platform during validation, as well as to test functionality and timing during operation.

While the ZUS MPSoC also includes its Xilinx AXI Traffic Generator (ATG) [START_REF]AXI Traffic Generator v3.0[END_REF] in the PL, such IP is less flexible than SafeTI, and comes along a restrictive license, hence precluding its use in other platforms. Instead, SafeTI is provided under a highly-permissive open source license [START_REF] Sala | SafeTI: a hardware traffic injector for mpsoc functional and timing validation[END_REF].

III. DEPLOYING SAFETY MEASURES IN THE PL OF THE ZUS

Deploying hardware support to implement safety measures in a full-custom design, either deployed as an ASIC or as an FPGA product, provides flexibility to find the most efficient solutions. For instance, in the case of SafeDE, cores can be made to export some signals to let SafeDE easily monitor their progress and stall the trail core whenever needed. Analogously, SafeSU and SafeTI can be attached to any interconnect directly, hence achieving full observability of the on-chip traffic. However, if those components are deployed in the PL of a COTS MPSoC, observability and controllability channels are limited and cannot be changed. Hence, the challenge tackled in this work consists on how to deploy such hardware support Fig. 3. Schematic of the ZUS MPSoC (baseline picture taken from [START_REF][END_REF]).

effectively in the PL, as illustrated in Figure 2 for the ZUS MPSoC.

A. Monitoring and Controlling Multicore Interference with SafeSU

Interference monitoring. The first relevant characteristic of the deployment of the SafeSU in the ZUS is that the ZUS has a distributed interconnect (see Figure 3), hence meaning that traffic is distributed rather than centralized in a single interconnect. This fact differs from previous deployments of the SafeSU, which built upon centralized interconnects (e.g. a bus) [START_REF] Wessman | De-RISC: the first RISC-V space-grade platform for safety-critical systems[END_REF]. The second relevant characteristic is that the SafeSU cannot directly manage the AMBA AXI signals of the NoC, as it did with the AMBA AHB signals in its previous deployments. Overall, the SafeSU needs to collect NoC traffic information from remote locations and without direct access to protocol signals.

In order to properly integrate the SafeSU in the PL of the ZUS, we note that ZUS interconnects include AXI performance monitors (APM) [START_REF][END_REF], which gather transaction metrics such as the following:

• Read and write transaction counts.

• Read and write byte counts.

• Read and write latencies.

• Number of idle cycles caused by masters and slaves.

• Counts on some additional AXI-related protocol signals. Moreover, APMs exist in different locations of the MPSoC, such as the interfaces near the DDR, the OCM, and the main switches connecting the APU and RPU computing units. They are shown as yellow squares in the ZUS schematic in Figure 3. They have been further indicated with thick dark red arrows and numbered. APM-1 monitors the OCM (aka as scratchpad memory). APM-2 monitors the traffic arriving from the Low Power Domain (LPD), where real-time cores are located, to the Full Power Domain (FPD). APM-3 monitors the traffic from the FPD, including APU cores, some of the PL ports and the GPU among others, to the LPD. APMs 4 to 9 monitor DRAM traffic for each of its different ports connected to the LPD, APU cores, PL, etc. In Figure 3, we have also included the SafeSU, SafeTI, and SafeDE in the PL for clarity. Hence, our current work focuses on interfacing APMs, as well as core-related memory access counters, to use their information to infer, either deterministically or statistically, how much interference each computing component has caused on each other. Moreover, the SafeSU needs to be extended to further break down interference across main locations to further ease diagnostics in case of deadline overruns.

Interference control. The SafeSU includes interference quota monitoring capabilities, and, upon a quota violation, it raises an interrupt. We note that the ZUS includes a wide variety of QoS knobs in its NoC interfaces, hence allowing to prioritize traffic based on its type and/or source. While not originally developed as part of the SafeSU, part of our work focuses on how to interface those QoS knobs so that the SafeSU can control them to limit specific interference channels whenever needed. This naturally needs being done in close collaboration with the Real-Time Operating System (RTOS), which should instruct the SafeSU on what knobs to set and how under quota violation scenarios, and must grant the SafeSU with appropriate privileges to change such configuration settings. Alternatively, the SafeSU can raise interrupts and be the RTOS the one in charge of configuring the QoS knobs as needed.

B. Enforcing Diverse Redundancy with SafeDE

Originally, the SafeDE has direct access to the instruction counts of the cores executing a task redundantly, so that it can determine the staggering among them. SafeDE has also access to the stall signal of one of the pipeline stages of the trail core so that it can stop it almost immediately whenever the staggering is too low (e.g. below few cycles) [START_REF] Bas | SafeDE: a flexible diversity enforcement hardware module for light-lockstepping[END_REF].

In the context of the ZUS, the SafeDE can neither snoop instruction count registers nor control pipeline stall signals of the cores. Hence, alternatives are under consideration. Regarding instruction counts, we aim at, in cooperation with the RTOS, having means to read instruction counts from the virtually lockstepped cores as software would do. Note that paths to reach the cores in the RPU and APU from the PL exist in the platform. They have been indicated with dashed thick dark red lines in Figure 3. Hence, if the performance monitoring counters of interest are mapped into readable address spaces from the outside, and the RTOS programs privileges properly, SafeDE could read those counters from the PL and take an action whenever needed to preserve the staggering. Regarding stalling the trail core whenever needed, multiple alternatives are being considered such as:

• Modifying QoS knobs in the interconnect to favor the head core at the expense of slowing down the trail one. However, this is only effective if the task being run misses in local caches and accesses those interconnects. • Issuing specific interrupts to the trail core so that, by programming them properly, the RTOS takes over for a short period intended to be enough to recover sufficient staggering between head and trail cores.

C. Diagnostics and Latency Measurements with SafeTI

The least impacted component due to being deployed in the PL of the ZUS is the SafeTI traffic injector since it issues transactions as programmed by the end user, regardless of whether the component is directly attached to the AMBA interface, or whether the interconnect is a bus or a NoC. Hence, integration of the SafeTI to generate traffic during operation for diagnostics purposes is not expected to bring major concerns.

We note, however, that the SafeSU may have difficulties to measure latencies of different request types by itself due to the lack of access to the AMBA interfaces, and due to the distributed nature of the ZUS' NoC. In this case, we plan to leverage the SafeTI to compensate that limitation since it can be programmed to produce specific traffic patterns triggering latencies that should allow building iteratively the latency to reach additional switches and components. Hence, by operating cooperatively, the SafeSU and the SafeTI will be able to measure the highest latencies experienced in most parts of the NoC.

D. Beyond Existing Components

Part of our ongoing work also includes the development of diversity monitors to complement SafeDE. A first version of those diversity monitors, referred to as SafeDM, has already been released [START_REF] Bas | SafeDM: a hardware diversity monitor for redundant execution on non-lockstepped cores[END_REF]. Those monitors aim at measuring diversity across cores running redundant tasks, but not performing any control of their staggering. Such diversity is measured accessing pipeline information. However, it is still unclear how to measure diversity when pipelines are not visible. This is ongoing work for the ZUS which we expect to solve with as much precision as possible due to the limited observability of the cores.

Other components we intend to deploy in the PL of the ZUS relate to aliveness monitoring of different computing components with some form of watchdogs. Those will likely build on the instruction counts of the cores, and their NoC activity as primary sources of information related to aliveness.

Overall, the strategy is exploiting the (many) observability and controllability features of the COTS MPSoCs in general, and the ZUS in particular, with specific modules deployed in the PL to provide support for safety measures implementation.

E. Safety Considerations

By deploying safety measures in the PL of a COTS MPSoC, the set of assurance (integrity) levels that can be targeted are limited by the native safety support of the MPSoC itself. Hence, if the development process of the MPSoC does not adhere to the requirements of some assurance levels (e.g. DAL-A or DAL-B for avionics), then it is very unlikely that applications with safety requirements at those levels can be deployed on the MPSoC regardless the safety measures deployed in the PL. A sufficient assurance level must be attained at least for those parts of the MPSoC controlling the monitoring capabilities for fail-safe systems, and for those parts providing computing capabilities and monitoring capabilities for fail-operational systems. Else, external solutions may be required, such as the use of multiple MPSoCs with a sufficient degree of redundancy to meet the requirements of the highest assurance levels.

IV. CONCLUSIONS AND FUTURE WORK

High-performance COTS MPSoCs needed for future aerospace systems lack sufficient native hardware support to implement efficiently many of the usual safety measures needed in those systems. We note, however, that some of those MPSoCs include a PL region which, despite generally intended to operate as a sandbox, can be used to deploy hardware components supporting safety features.

In this work, we review some existing such components and analyze how they could be deployed in the Xilinx Zynq UltraScale+ (ZUS) MPSoC, as representative example of high-performance COTS MPSoC, despite the gap existing between their original implementations and the observability and controllability channels available in the PL of the ZUS. In particular, we review the alternatives offered by the ZUS to monitor and control multicore interference with the SafeSU, to enforce diverse redundancy with the SafeDE, and to provide diagnostics with the SafeTI.

Our future work includes performing the integration of those hardware components in the ZUS to enable multiple safety measures in COTS MPSoCs, investigating additional hardware components that could be incorporated, and looking beyond the ZUS to consider even more powerful MPSoCs such as, for instance, the Xilinx VERSAL platform.

Fig. 1 .

 1 Fig. 1. Safety-related components as deployed in a NOEL-V MPSoC for the space domain.

Fig. 2 .

 2 Fig. 2. Safety-related components deployed as proposed in this work in a Zynq UltraScale+ MPSoC.

ACKNOWLEDGEMENTS

This work is part of the project PCI2020-112010, funded by MCIN/AEI/10.13039/501100011033 and the European Union "NextGenerationEU"/PRTR, and the European Union's Horizon 2020 Programme under project ECSEL Joint Undertaking (JU) under grant agreement No 877056. This work has also been partially supported by the Spanish Ministry of Science and Innovation under grant PID2019-107255GB-C21 funded by MCIN/AEI/10.13039/501100011033.