Emmanuel Frénod

Jean-Philippe Gouigoux

Landry Touré

Modeling and Solving Alternative Financial Solutions Seeking

Keywords: Finance Modeling, Local Communities, Systemic Modeling, Optimization, Genetic Algorithms

In this paper we model the working of local community finances. As a result of this first step, we obtain a systemic model that is used to formalize the problem of Alternative Financial Solutions Seeking, which consists in building a collection of Alternative Multi-Year Prospective Budgets from two Multi-Year Prospective Budgets built by a finance expert. The modeling and formalization steps are led in a way that allows us to implement a software code for Alternative Financial Solutions Seeking based on a Genetic Like Algorithm.

Introduction

For local communities, political decisions with heavy financial consequences need rigorous and detailed studies. The purpose of those studies is to provide Decision-Makers with forecasts and projections of their financial circumstances to come, for various sequences of projects responding to political goals and various ways to finance them.

Tackling those forecasts and projections is a delicate task for experts. Indeed, on the one hand factors constraining the projects of a local community are essentially laws, proper management rules which fluctuate and public opinion which is fickle. On the other hand, the way that those constraints are perceived by local community Decision-Makers is also time-varying.

Often, local community calls on experts in order to strike the right balance. Practically, an expert works in straight collaboration with Decision-Makers of the local community he is engaged with in order to take into account all the targets and perceived constraints of every project of the local community. Its work consists in building financial plans (Prospective Budgets), which are in some sense optimized, consistent with the capacity of investment of the local community and, of course, comply with the political goals of the Decision-Makers. For each prospective budget, the state of various indicators, relevant to the resulting financial health of the local community in future years, are given. As a result of this work, viable scenarios satisfying partially the political goals are proposed among which, in an ideal situation, Decision-Makers may make a choice. Unfortunately in a large number of non-ideal situations, constraints and goals cannot be satisfied together. In those cases the set of viable scenarios influences the evolution of the political goals and the constraint perception in order to begin a new iteration of the work process.

The existing tools dedicated to this iterative work process are somewhat limited. The goal of this paper is to set out a new tool to contribute to filling this gap in a specific context we shall describe now.

The local communities usually need visibility on their budget over a time period of several years, linked to the characteristic duration of political mandate. The main strict constraint, generally imposed by current legislation, is that the difference between the receipts and the expenditures cannot be negative. That makes-up the balanced budget rule. This balanced budget is in most countries shared into sub-budgets which are not necessary balanced. However, each expenditure or receipt clearly belongs to a unique sub-budget. For instance, French local communities share their budget into an investment budget and an operating budget. Positive credit balance amount from the operating budget can be transferred to the investment budget. Our work joins in the French model of local communities' management but the tackled questioning and the tool we set out are clearly more general.

In order to explain the goal of the tool we build, we restrict ourselves to the particular case of a Prospective Budget building where, among the political goals, two objectives are to be reached. With software environment avalaible nowadays, a Prospective Budget may be figured out with the first objective achieved. In particular, the consequences on the factors involved in the second objective may be quantified. Of course, the same can be done exchanging the roles of the two objectives. Nonetheless, generally speaking, it is not possible to satisfy both objectives, since the constraints are too numerous. Schematically, it may be said that it is possible to bring out two Prospective Budgets S 1 and S 2 , where S 1 satisfies the first objective, which is symbolized by the fact that indicator V 1 reaches a targeted value V 1 . Prospective Budget S 2 satisfies the second objective which is translated by V 2 = V 2 for a targeted value V 2 . In Prospective Budget S 1 , V 2 = V 2 but is determined by the budget building process which takes constraints into account and which is, in some sense, optimized. In a similar way, in Prospective Budget S 2

, V 1 = V 1 .
Having those Prospective Budgets on hand, the next step consists in finding several alternative ones that are such that neither V 1 is reached by V 1 nor V 2 by V 2 , but still satisfy the constraints and are more satisfactory. When this process is executed by an expert, the building of those alternative Prospective Budgets uses one more time the tool after having let the targeted values evolve, influenced by its knowledge and the interaction with Decision-Makers. Yet, the new tool which is described in this paper has the ambition of automatically generating a collection of alternative Prospective Budgets and of introducing them in a usable way, so that Decision-Makers can choose the one that fits their goals in the best way.

In order to create such a new tool, we first identified that the question of finding several alternative Prospective Budgets can be formalized as finding a shape, corresponding to the extremum of a given fitness function, in a multi-dimensional space.

Then we found out that the best type of optimization methods to tackle this shape search was Genetic Algorithm. Indeed, Genetic Algorithms have the capability to explore a given domain and, by nature, the result of a Genetic Algorithm is a set of solutions that optimizes the fitness function. For a review on Genetic Algorithms, we refer to Goldberg [START_REF] Goldberg | Genetic Algorithms in Search, Optimization, and Machine Learning[END_REF], Beasley, Bull & Martin [START_REF] Beasley | An overview of genetic algorithms. part 1, fundamentals[END_REF][START_REF] Beasley | An overview of genetic algorithms. part 2, research topics[END_REF] and Davis [6].

This approach using Genetic Algorithm for an optimization problem is not new. Nevertheless, the algorithm we propose here has innovative aspects. The first one is that we look for an optimal object in a bounded box. The other innovative aspect is that we look for the argument of an optimum which is not a single point but a shape in a relatively high-dimensional space. The use of Genetic Algorithms for shape optimization is classical, and many references exists on the subject. We refer for instance to De Jong [START_REF] Jong | Proceedings of the Evolutionary Algorithms in Engineering Computer Science (EUROGEN99), chapter Evolutionary computation: recent developments and open issues[END_REF] and Castro, Antònio & Sousa [START_REF] Castro | Optimisation of shape and process parameters in metal forging using genetic algorithms[END_REF]. We also refer to articles that implement variants of Genetics Algorithms so called Particle Swarm Optimization (see for instance Mattheck & Burkhardt [START_REF] Mattheck | A new method of structural shape optimization based on biological growth[END_REF] and Fourie & Groenwold [START_REF] Fourie | The particle swarm optimization algorithm in size and shape optimization[END_REF]) and Fuzzy Controlled Genetic Algorithm (see for instance Soh & Yang [START_REF] Soh | Fuzzy controlled genetic algorithm search for shape optimization[END_REF]), both used in structure optimization. But, in all those references a Genetic Algorithm is used to drive the successive setting out of the parameters of a software code in order to find out the optimal solution. The methods do not use -contrary to what we do -the capability of Genetic Algorithms to directly build a shape in the space.

Once it was established that Genetic Algorithms is the pertinent tool for our question, it was needed to formalize it so as to be able to use Genetic Algorithms. Yet, the literature concerning them is rich in the context of financial optimization (we refer for instance to Chen [START_REF]Genetic Algorithms and Genetic Programming in Computational Finance[END_REF]). Besides, the financial modeling is very active on the market finance sector (see for instance Goodman & Stampfli [11], Ilinski [START_REF] Ilinski | Physics of finance : gauge modelling in non-equilibrium pricing[END_REF] and Fama [START_REF] Fama | Market efficiency, long-term returns, and behavioral finance[END_REF]). However, it is much less productive for applications in public sector (see for instance Musgrave [START_REF] Musgrave | The theory of public finance : a study in public economy[END_REF] and Rosen [START_REF] Rosen | Public finance[END_REF]). Finally, mathematical modeling for finance of local community seems to be very poor (see Tiebout [START_REF] Tiebout | A pure theory of local expenditures[END_REF]).

Hence, on the one hand, we had to develop a model of the local community finance system.

On the other hand, we developed a proper formalism (calling upon the model of the local community finance system) to develop our Genetic Like Algorithm. We now summarize this formalism. It can be considered that any given Prospective Budget is characterized uniquely by the two values V 1 and V 2 . In other words, indicators V 1 and V 2 become variables on which Prospective Budget depends. To simplify the purpose, V 1 and V 2 are both supposed to be n-dimensional, so that it can be assumed that (

V 1 , V 2 ) ∈ R 2n . Prospective Budget associated with values V 1 and V 2 writes S(V 1 , V 2 ). Of course, for some values of the vari- ables, say (V f 1 , V f 2 ), Prospective Budget S(V f 1 , V f 2 )
does not satisfy the constraints. Then, constraints may be seen as defining a sub-domain of the space R 2n in which the variables lie. Within this framework, the Prospective Budget S 1 described above writes

S( V 1 , V c 2 ) where V c
2 is computed by the software environment. In the same way, Prospective Budget S 2 writes S(V c 1 , V 2 ). The method explores, in R 2n -the space where the variables lie, the intersection of a box containing the two points (

V 1 , V c
2 ) and (V c 1 , V 2 ), associated with the budgets already on hand, and of the sub-domain where constraints are satisfied in order to identify a shape join-

ing ( V 1 , V c
2 ) and (V c 1 , V 2 ) around which Prospective Budgets fit well what Decision-Makers are waiting for, are in some sense optimized and satisfy the constraints. The box is built by considering in R 2n the middle point of ( V 1 , V c

2 ) and (V c 1 , V 2 ) and by building in this point an orthonormal frame whose first vector is the normalization of vector

-----------→ ( V 1 , V c 2 )(V c 1 , V 2 ) - joining ( V 1 , V c 2 ) to (V c 1 , V 2 )
. The other vectors of the frame are exhibited by the mean of the Gram-Schmidt routine. The method consists in defining a fitness function F which integrates the Decision-Makers' political goals. We also have to build the sub-domain on which budgets satisfy the constraints. We define a method to encode the variables in the considered box. This coding calls, among others, upon a sub-product of the Gram-Schmidt routine. Then, we implemented a Genetic Like Algorithm which consists first in generating a collection of N values (V l 1 0 , V l 2 0 ) l=1,...,N which are within the box and satisfy the constraints. For each value,

Prospective Budget S(V l 1 0 , V l 2 0 ) and its fitness F (S(V l 1 0 , V l 2 0 )) = F (V l 1 0 , V l 2 0
) can be computed. By crossover, mutation and constraint management methods, usually combined in Genetic Algorithms, a new collection (V l 1 1 , V l 2 1 ) l=1,...,N (lying in the box and satisfying the constraints) is then generated. Going further finally leads to the k th generation (V l 1 k , V l 2 k ) l=1,...,N which may be close to the sought shape in the intersection of the box and the sub-domain where constraints are satisfied. This way of using Genetic Like Algorithm appears to be new.

The main contributions of this paper are the buildings of the models of the local community finance system and of the Alternative Financial Solutions seeking problem, which are done in section 2, and the formalization of those models under a form -just evokedallowing the use of a Genetic Like Algorithm. This formalization and the writing of the Algorithm itself are given in section 3. In the last section, the method is tested, in particular on an operational problem and gives good results. This demonstration of this capability of our method is also an important contribution.

Description of the Alternative Financial Solutions seeking problem

This section is devoted to the description of the kind of financial problems we tackle with our method and tool. We begin by introducing, with a systemic point of view, the French local community yearly budget workings. Then, we explain the problematic of seeking alternative Multi-Year Prospective Budgets. This is done in section 3. For readers interested in French local community finance system, we refer to [START_REF]La qualité comptable au service d'une gestion performante des collectivités locales -guide des bonnes pratiques num 18[END_REF] and [START_REF]Annexe num 1: Plan de comptes développé des communes de 500 habitants et plus au 1ier janvier 2009[END_REF].

Local community Yearly Budget System working

Among incomes contributing to local community operating budget, there are essentially

Yearly Budget System

Taxes

Current debt

Capacity to be free of debt

In v e s tm e n t le v e l The other inputs of this system are linked with the "Current Debt". They are: the capital associated to this debt that remains due, the capital that needs to be repaid this year and the interests that have to be paid. Those amounts are defined by loan contracts of previous years. Those inputs are placed on the left-hand side of the figure. Of course, local community cannot have a direct effect on those inputs, but acts on their values in the next years by contracting or not new loans. This is symbolized by the dash line in the figure .  Generally, a local community plans to get operating recipes that allow it to face all operating expenditures and debt interests, and, once those expenditures realized, that leaves a remaining amount that can be used for investment. This remaining amount is called "Gross Self-Financing Capacity". This "Gross Self-Financing Capacity" is used to repay the capital that needs to be. The remainder, which is called "Net Self-Financing Capacity", contributes to the investment budget with the goal to top up subventions and loans to reach the Investment Level wanted by the community. This System generates a balanced budget.

At the bottom of the figure, the "Capacity to Be Free of Debt" is mentioned. This indicator is computed from the capital that remains due and from the Gross Self-Financing Capacity. It is, by definition, the time (generally expressed in years) for the community to repay all the capital of its debt, if no other loans are contracted and if the Gross Self-Financing Capacity remains constant over the next years. This indicator is seen here as the output of the system. A generally-accepted maximum figure for the Capacity to Be Free of Debt is 15 years

The Yearly Budget System is presented in Figure 2 Yearly Budget System. Since Current Debt cannot be influenced directly, only Taxes and Investment Level are considered as active Inputs of the system. Considering this makes Taxes and Investment Level the variables on which the Yearly Budget depends and makes the Capacity to Be Free of Debt a result of the Yearly Budget, or in other words, an Output of the system. In the figure, only three years (#1, #2 and #3) are represented; ". . . " symbolize that other years are coming hereafter.

Multi-Year Prospective Budget Systems

From the Yearly Budget System, a multi-year budget may be built. Since those kinds of multi-year budgets are intended to explore possible futures under several assumptions, we call them Multi-Year Prospective Budgets. The functioning of such a Multi-Year Prospective Budget is depicted in Figure 3. On the left-hand side of this picture is drawn the Budget System of the first year. This diagram is the synthetic one with arrows coming from the Current Debt box, the Tax box and the Investment Level box and an arrow going to the Capacity to Be Free of Debt box. Loans that are contracted during this first year have a consequence on the debt of the next years. This is symbolized by the arrow going from the Budget System of the first year to the Current Debt box of the second year. Going on, following the arrows, it is possible to create a Multi-Year Prospective Budget System for an arbitrary number of years.

To formalize a bit, the investment leads to the realization of a set of projects, which belong to the list of all projects which are desired to be carried out. Then, Investment Level may be described using a list of numbers, the cardinal of which being the number of projects. Each number indicates if its associated project will be realized or not, and possibly, if it is so, how close or far from its targeted date it is carried out. Thus, in the case where the Prospective Budget is considered over five years and if five projects are considered, every possible Multi-Year Prospective Budget depends on ten values (I 1 , I 2 , I 3 , I 4 , I 5 , T 1 , T 2 , T 3 , T 4 , T 5 ) = ((I i ) i=1,...,5 , (T i ) i=1,...,5 ); five numbers (I i ) i=1,...,5 given information on project realization and then indicating the Investment Level, and five Tax Levels: (T i ) i=1,...,5 , one for each year. Of course, there are structural constraints on the variables: the T i cannot be negative. The Prospective Budget corresponding to a given value ( Ī1 , Ī2 , Ī3 , Ī4 , Ī5 , T1 , T2 , T3 , T4 , T5 ) = (( Īi ) i=1,...,5 , ( Ti ) i=1,...,5 ) of the Investment Level and Tax Levels is seen as a solution S( Ī1 , Ī2 , Ī3 , Ī4 , Ī5 , T1 , T2 , T3 , T4 , T5 ) = S((( Īi ) i=1,...,5 , ( Ti ) i=1,...,5 )).

The five Capacities to Be Free of Debt are seen as the image associated with a Prospective Budget by a mapping. They read: (C k (S( Ī1 , Ī2 , Ī3 , Ī4 , Ī5 , T1 , T2 , T3 , T4 , T5 ))) k=1,...,5 = (C k (S(( Īi ) i=1,...,5 , ( Ti ) i=1,...,5 )) k=1,...,5 .

Alternative Prospective Budget seeking problematic

Having on hand this formalism, we can insert in it the political goals of Decision-Makers, which are generally unreachable. At first, we present how part of the political goals may be incorporated to create two Multi-Year Prospective Budgets which are only partially satisfactory. Then we explain how, starting from two Budgets, Alternative Prospective Budgets may be sought. Of course, those Budgets are also only partially satisfactory, but among the generated collection of Prospective Budgets, one can be preferred to the others and thus chosen among them.

We study the example with five years Prospective Budgets involving five projects, but what is explained in the following is of course true for any number of years and projects. In an effort to remain schematic, we consider here that a Political Goal is a given collection ( With the help of a software environment properly programmed, it is possible to compute Prospective Budget S(( I i ) i=1,...,5 , ( T i ) i=1,...,5 ), whose every Yearly Budget is balanced and which satisfies the requested Political Goal, i.e. such that C k (S((

I 1 , I 2 , I 3 , I 4 , I 5 , C 1 , C 2 , C 3 , C 4 , C 5 ) = (( I i ) i=1,...,5 , ( C i ) i=1,...,
I i ) i=1,...,5 , ( T i ) i=1,...,5 )) = C k for k = 1, ..., 5.
However this view is much too naive, since Political Goal (( I i ) i=1,...,5 , ( C i ) i=1,...,5 ) generally requires Tax Levels that are incompatible with regulations, or simply not acceptable to Decision-Makers.

The work of Decision-Makers, assisted by public-finance experts, consists in degrading Political Goal (( I i ) i=1,...,5 , ( C i ) i=1,...,5 ) to be reached with acceptable Taxes Levels. This is done with the help of a software environment. For instance, SOFI software, edited by MGDIS 1 , provides solutions to this question in considering two problems. Those problems consist, in some sense, in inverting the routine presented in Subsection 2.2 and Figure 3, which was describing how Capacities to be Free of Debt were gotten from chosen Tax and Investment Levels. The first problem, depicted in Figure 4, consists in considering as input the targeted Investment Level ( I i ) i=1,...,5 and, having set constraints on Tax Levels, in computing a Multi-Year Prospective Budget S(( I i ) i=1,...,5 , (T c i ) i=1,...,5 ) such that, for k = 1, ..., 5, the Capacities to Be Free of Debt C k (S(( I i ) i=1,...,5 , (T c i ) i=1,...,5 )) are as close as possible (in a given sense) to the Goals C k and with Tax Levels (T c i ) i=1,...,5 that satisfy the constraints and whose every Yearly Budget is balanced. In Figure 4, the diagram of Figure 3 The second problem we consider is represented in Figure 5, takes the targeted Capacities to Be Free of Debt ( C k ) k=1,...,5 as inputs and computes Multi-Year Prospective Budget S((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ) such that ( T i ) i=1,...,5 satisfies the constraints on Tax Levels, C k (S((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ) = C k for k = 1, ..., 5 and Investment Levels (I c i ) i=1,...,5 , are as close as possible to the Goal ( I i ) i=1,...,5 . In Figure 5, the content of Figure 3 is used again. However, in this case, the Capacities to be Free of Debt are indicated as inputs. Arrows going from them to Investment Levels (they are not all drawn for readability) and to Taxes symbolize that Investment and Taxes are consequences of the chosen Capacity to be Free of Debt Levels.

Once those two solutions are set out, they may be evaluated by Decision-Makers, in regards, among others, of the Tax Evolution Pattern.

Other Multi-Year Prospective Budgets may then be built by modifying values within the Political Goal (( I i ) i=1,...,5 , ( C i ) i=1,...,5 ), after financial and political discussions between Decision-Makers and experts. This generation of Alternative Financial Solutions or Alternative Multi-Year Prospective Budgets can be fastidious and long. Thus, only a small number can be generated.

The topic of the method and tool we propose here is to automate this generation of Alternative Financial Solutions or Alternative Multi-Year Prospective Budgets, and to set out a relatively wide number of them, provided with indicators of their quality in order for Decision-Makers to be able to make a choice between them.

Roughly speaking, we can consider that Prospective Budgets S(( I i ) i=1,...,5 , (T c i ) i=1,...,5 )) and S((I c i ) i=1,...,5 , ( T i ) i=1,...,5 )) are associated with two points in a 10-dimensional space and that the possible Alternative Financial Solutions or Alternative Multi-Year Prospective Budgets are gathered around a geometrical object joining those two points and that have to be sought and identified.

Genetic Like Algorithm

On the basis of the model we set out in the previous section, we can implement a Genetic Like Algorithm. Although this approach using Genetic Algorithm is not new in the context of optimization, the algorithm proposed here has innovative aspects, as explained in the Introduction (see page 3). Among them they are the fact that we look for an optimal object in a bounded box. The other innovative aspect is that we look for the optimum not as a single point but as a shape in a relatively high-dimensional space. For this, we strongly use the fact that the result of a Genetic Algorithm is a set of solutions that is located on the sought shape.

We go on treating the case when the number of years and the number of projects are both five.

Dimensionless problem setting

In order to manage variables and results that are dimensionless and of order one, we first rescale the problem. For this purpose, we introduce a characteristic Investment Level describer value i, a characteristic Capacity to Be Free of Debt c and a characteristic Tax Level t. For instance we can chose i = 1 10

I 1 + I 2 + I 3 + I 4 + I 5 + I c 1 + I c 2 + I c 3 + I c 4 + I c 5 = 1 10
5 i=1 I i + I c i , t = 1 10 T 1 + T 2 + T 3 + T 4 + T 5 + T c 1 + T c 2 + T c 3 + T c 4 + T c 5 = 1 10
5 i=1 T i + T c i , c = 1 10 5 k=1 C k (S(( I i ) i=1,...,5 , (T c i ) i=1,...,5 )) + C k (S((I c i ) i=1,...,5 , , ( T i ) i=1,...,5 )), (1)
which are the mean values of values reached by the two Prospective Budgets we have on hand. Then we define the dimensionless variables and results

I i = I i i , T i = T i t and (2)
C k (S((I i ) i=1,...,5 , (T i ) i=1,...,5 )) = C k (S((iI i ) i=1,...,5 , (tT i ) i=1,...,5 ))

c . (3)
On those variables there are organic constraints:

C k (S((I i ) i=1,...,5 , (T i ) i=1,...,5 )) ≥ 0, for k = 1, ..., 5, (4)
which translate the fact that the Capacity to Be Free of Debt is a duration. There are also constraints linked with legal rules, various regulations and what is politically admissible. These read:

T i ≤ T max i (T 1 , . . . , T i-1 ), for i = 1, ..., 5, (5)
C k (S((I i ) i=1,...,5 , (C i ) i=1,...,5 )) ≤ C max , for k = 1, ..., 5.

Those constraints, when expressed in dimensionless variables, involve maximum values C max and (T max i ) i=1,...,5 which essentially do not depend on the size of the concerned local community. Inequalities (6) express the fact that, at each year, the Capacity to Be Free of Debt is limited by common rules. The T max i in (5) depend on the Tax Levels of the previous years and are both imposed by law, which restricts tax evolution, and prescribed by what community Decision-Makers exclude.

Remark -The question of knowing if the fact that every Yearly Budget of every Multi-Year Prospective Budget needs to be balanced has to enter into the constraint collection may be addressed. The answer is that we work under the assumption that any Multi-Year Prospective Budget, for instance computed using SOFI, from any variable collection ((I i ) i=1,...,5 , (T i ) i=1,...,5 ) generates loans and consequently Capacity to Be Free of Debt set C k (S((I i ) i=1,...,5 , (T i ) i=1,...,5 )) insuring the balanced character of all its Yearly Budgets.

Within the dimensionless variables, the dimensionless Political Goals and other quantities are expressed as

I i = I i i , C i = C i c , I c i = I c i i and C c i = C c i i , (7)
and we have on hand two dimensionless Prospective Budgets S(( I i ) i=1,...,5 , (T c i ) i=1,...,5 )) and S((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ), which are associated with two points in a 10-dimensional space, located not so far from the origin.

Fitness choice

Among the criteria that may enter the fitness definition, they are the targeted values I i and C i and the Tax Evolution Pattern.

We begin with explaining how easy it is to define a model of Tax Evolution Pattern within dimensionless variables. In the case where the number of years is 5, it is a collection of 5 non negative values (A k ) k=1,...,5 such that

5 k=1 A k = 1, (8)
and which has the property that A k = A k+1 in the case of a desired stability of Tax Level between years number k and number (k + 1) and the property that A k < A k+1 in the case of a planned increase. Then, a way to measure how far from the Tax Evolution Pattern a given Multi-Year Prospective Budget S((I i ) i=1,...,5 , (T i ) i=1,...,5 ) reduces to computing

F T ((I i ) i=1,...,5 , (T i ) i=1,...,5 )) = φ T 5 k=1 T k 5 i=1 T i -A k , (9)
where φ T is a non-increasing function such that φ T (0) = 1 and lim x→+∞ φ T (x) = 0. In this definition, the division by 5 i=1 T i allows us to insure that the values which are compared with the A k range between 0 and 1.

Ways to measure how far from the Politic Goals a Multi-Year Prospective Budget is, are the computations of

F I ((I i ) i=1,...,5 ) = φ I r k=1 I k -I k and F C ((I i ) i=1,...,5 , (T i ) i=1,...,5 )) = φ C 5 k=1 C k (S((I i ) i=1,...,5 , (T i ) i=1,...,5 )) -C k , (10)
where φ I and φ C have similar definition as φ T .

With these three functions F T , F I and F C , defining three non negative constants γ T , γ I and γ C , having a sum not too far from 1, we chose the following Fitness Function F ((I i ) i=1,...,5 , (T i ) i=1,...,5 ) = γ T F T ((I i ) i=1,...,5 , (T i ) i=1,...,5 ) + γ I F I (I i ) i=1,...,5 ) + γ C F C ((I i ) i=1,...,5 , (T i ) i=1,...,5 ), [START_REF] Goodman | The mathematics of finance: modeling and hedging[END_REF] and the largest F ((I i ) i=1,...,5 , (T i ) i=1,...,5 )) the best the solution S((I i ) i=1,...,5 , (T i ) i=1,...,5 )).

With materials we built, we can reformulate the question of seeking Alternative Financial Solution as follows: we want to exhibit a collection of N points ((I l

Frame building by Gram-Schmidt routine

In the 10-dimensional vector space, for two vectors W = ((J i ) i=1,...,5 ), (D i ) i=1,...,5 )) and W = ((J i ) i=1,...,5 ), (D i ) i=1,...,5 )), the following inner product and norm naturally exist:

W, W = 5 i=1 J i J i + D i D i and W = W, W . (12)
Moreover, it is provided with its canonical basis: e 1 = ((1, 0, 0, 0, 0), (0, 0, 0, 0, 0)), e 2 = ((0, 1, 0, 0, 0), (0, 0, 0, 0, 0)), e 3 = ((0, 0, 1, 0, 0), (0, 0, 0, 0, 0)), . . . , e 10 = ((0, 0, 0, 0, 0), (0, 0, 0, 0, 1)).

On the one hand, from the points (( I i ) i=1,...,5 , (T c i ) i=1,...,5 ) and ((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ), we can build the first vector of the frame by normalizing the vector linking those two points. This vector is:

g 1 = g1 g1
, where g1 = (( I i -I c i ) i=1,...,5 , (T c i -T i ) i=1,...,5 ). ( 14)

On the other hand, we look for index i b which is such that the absolute value of the inner product of g 1 by e i b is as large as possible, i.e. such that

g 1 , e i b = max i=1,...,10 { g 1 , e i }. ( 15
)
The basis is then built by induction: Once j orthonormal vectors are obtained, the (j + 1) th is gotten by removing from e (i b +j mod 10) its projection onto every vector of the new basis already computed and by renormalization, or in other words, by computing

g j+1 = gj+1 gj+1
, where gj+1 = e η(i b +j) -

j p=1 e η(i b +j) , g p g p , (16)
where

η(i) = i if 1 ≤ i ≤ 10 and η(i) = i -10 if 10 ≤ i ≤ 20.
Once all the (g j ) j=1,...,10 are obtained they make an orthonormal basis of the vector space whose first vector is born by the straight line linking the two points associated with the two dimensionless Prospective Budgets we have on hand.

With the help of this basis, we will build the box in which we will seek the targeted geometrical object and the coding of Prospective Budgets.

Let B be the 10 × 10 matrix such that if W = ((J i ) i=1,...,5 , (D i ) i=1,...,5 ) is a vector expressed in the canonical frame

U = (U 1 , . . . , U 10 ) = BW, (17)
gives its coordinates within frame (g j ) i=1,...,10 . The i th column of B is made of the coordinates of e i within the new frame and the i th column of B -1 = B T is made of the coordinates of g i within the canonical frame. In the following we will consider that B and its inverse matrix B -1 are known.

Box building and coding

The geometrical object will be looked after within a box containing the points (( I i ) i=1,...,5 , (T c i ) i=1,...,5 )) and ((I c i ) i=1,...,5 , ( T i ) i=1,...,5 )) associated with the two dimensionless Prospective Budgets we have on hand.

The box we chose is the cube centered in the middle point M of [(( I i ) i=1,...,5 , (T c i ) i=1,...,5 )), ((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ))], whose coordinates are

M = I c i + I i 2 i=1,...,5 , T c i + T i 2 i=1,...,5 , (18)
with edges being {2 g1 g 1 , ( g1 g i ) i=2,...,10 }, where g1 is defined by formula [START_REF] Musgrave | The theory of public finance : a study in public economy[END_REF]. Two opposite faces of this hypercubic box are orthogonal to the straight line linking the points (( I i ) i=1,...,5 ), (T c i ) i=1,...,5 )) and ((I c i ) i=1,...,5 ), ( T i ) i=1,...,5 )). Another (and more usable) way to characterize the box is to say that it is the range of

[-1, 1] × [-1 2 , 1 2 ]
9 by the mapping

P → M + g1 B -1 P, ( 19
)
whose inverse is

R → 1 g1 B(R -M), ( 20
)
where M is given by ( 18), g1 by ( 14) and matrix B by [START_REF] Soh | Fuzzy controlled genetic algorithm search for shape optimization[END_REF].

Moreover, this transformation gives a coding of any solution

S(R) by a point in [-1, 1]× [-1 2 , 1 2 ] 9 .
Hence, without any supplementary effort, we have two codings at our disposal: a solution S(R) may be coded by its directly interpretable values (R 1 , . . . , R 10 ) = ((I i ) i=1,...,5 ), (T i ) i=1,...,5 ) or by the collection of values (P 1 , . . . , P 10 ) that are the coordinates of point

P = (1/ g1 ) B(R -M) ∈ [-1, 1] × [-1 2 , 1 2 ] 9 .
Generically, in the following we will denote the coding by Q = (Q 1 , . . . , Q 10 ). It will designate the coding by P or R or any other.

Initial Prospective Budget collection

Fixing the number of members of the collection, and denoting this number by N , a collection of N points P l 0 = (P l 1 0 , . . . , P l 10 0 ), for l = 1, ..., N , of [-1, 1]×[- 1 2 , 1 2 ] 9 is generated randomly. The initial collection of solutions is then R l 0 = (R l 1 0 , . . . , R l 10 0 ), for l = 1, ..., N , where

R l 0 = M + g1 B -1 P l 0 .
We assume that every dimensionless Prospective Budget R l 0 satisfies all the constraints (4), ( 5) and ( 6). This means that the random generation has to run until N dimensionless Prospective Budgets satisfying the constraints are obtained.

Being Generic, the coding of this initial Prospective Budgets will be denoted by

Q l 0 = (Q l 1 0 , . . . , Q l 10 0 ).

Constraint management

For a collection made of 2N individuals, we will manage constraints by integrating them in the Fitness Function. This consists in adding to Fitness Function defined by [START_REF] Goodman | The mathematics of finance: modeling and hedging[END_REF], the following quantity, or a quantity of this kind, -φ - for a non-decreasing function φ such that φ(0) = 0 and lim x→+∞ φ(x) = 1, multiplied by a factor γ relatively large in front of 1. This penalization makes the value of the fitness of Prospective Budgets not respect the constraints to decrease and then diminishes their chance to pass the selection to come.

Algorithm to produce next generation

Having on hand the m-th collection of Prospective Budgets S(R l m ), for l = 1, ..., N , and their coding Q l m , a new collection S(R l m+1 ), with coding Q l m+1 is generated by a usual Genetic Algorithm Like routine we now briefly describe.

In a first step, couples of codings of the Prospective Budgets are randomly formed. Then for any couple

(Q l m , Q k m ) = ((Q l 1 m , . . . , Q l 10 m ), (Q k 1 m , . . . , Q k 10 m )), an integer i a is ran- domly chosen among {1, 2, . . . , 10} and the two codings (Q l 1 m , . . . , Q l ia-1 m , Q k ia m , . . . , Q k 10 m ) and (Q k 1 m , . . . , Q k ia-1 m , Q l ia m , . . . , Q l 10 m
) are generated. At the end of this first step, we have on hand 2N points: the Q l m , for l = 1, ..., N and all the ones generated as described previously that are denoted Q l m for l = N + 1, ..., 2N .

The second step consists in making some codings to mutate. For this, a small integer i b , ranging, say, between 0 and N/50 is randomly generated. Then, i b codings are randomly chosen among the codings generated in the first step, i.e. among the Q l m with l = N + 1, ..., 2N . For each of them, an integer i c is randomly chosen among {1, 2, . . . , 10}, a number ν ranging between -1 and 1 is also randomly generated and the i c -th component of the concerned coding is incremented by ν.

In the third step, the Fitness Function is evaluated on every coding Q l m , for l = 1, ..., 2N , which results from the first three steps. In order to do so, it is necessary to determine the R l m , for l = 1, ..., 2N associated with the Q l m , for l = 1, ..., 2N , the Prospective Budgets S(R l m ), for l = 1, ..., 2N , and finally, the Fitnesses (penalized by constraints) F (R l m ) for l = 1, ..., 2N .

The objective of the fifth step is to randomly select N codings among all the codings Q l m , for l = 1, ..., 2N that were brought out by the previous steps with the principle that the higher the fitness of a coding, the more likely to be selected. In addition, we can use an elitism routine which consists in deterministically choosing the N elit codings that provide the best scores with respect to the Fitness Function.

In practice, in order to implement the routine just described, we used the library "Aforge.Genetics". We conducted a study to measure the impact of the values of "Cross-Rate" and "MutationRate" parameters of this library. This study showed that the default values were convenient. Hence we used them.

Test on a one-dimensional problem with a Fitness Function having a maximum plateau

One of the original capabilities of the method described in this paper is that it can give a good representation of the argument of the maximum of the fitness function when it is an interval. To illustrate this capability, a fitness function having an interval as argument of its maximum will be built. This fitness function is the sum of two other functions that have both one maximum. The result of this sum is a function which has a plateau whose span is smaller than the interval defined by the maximum localizations of the two functions it is the sum of.

In practice, in a first place, functions f 1 and f 2 defined by

f 1 (x) = 1 -10 |x -0.45| and f 2 (x) = 1 -10 |x -0.55|, (24)
and drawn at the top of Figure 7 are considered. Functions

g 1 (x) = min 1 -10 (x -0.48), 1 and g 2 (x) = min 1 -10 (0.52 -x), 1 , (25)
are also considered. Finally, the Fitness Function which is considered is

F = l 1 + l 2 . (26)
It is the sum of the two functions: l 1 = 0.7 max 0.5f 1 + 0.5g 1 , 0 and l 2 = 0.7 max 0.5f 2 + 0.5g 2 , 0 .

Functions l 1 and l 2 are drawn in Figure 8 on the top and in the middle; they both have only one argument of their unique maximum. Fitness Function F is given in the bottom of this Figure and detailed in Figure 9. As announced, its maximum makes up a plateau which is the range of an interval ([0.475, 0.525]) strictly included in the interval ([0.45, 0.55]) made by the maximum localizations of the two functions l 1 and l 2 .

A simplified version of the method built in section 3 was implemented on this example to locate the arguments of the maximum of Fitness Function F . In this implemented method, the arguments of the maximum of l 1 (x) and l 2 (x) play the roles that points (( I i ) i=1,..., 5 ,(T c i ) i=1,...,5 ) and ((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ) play in the more general method. In this simplified version, the collection at each generation is made of 35 points. The resulting collection after 500 generations of the algorithm is given in Table 1. The collection is well distributed on the interval ([0.475, 0.525]) whose range is the plateau of Fitness Function F . In particular, this final collection does not undergo concentrations that could orientate by mistake interpretation towards concluding that the Fitness Function has isolated maxima. This capability of the method is very important for reaching operational problems. This is what is done in the last test.

Test on an operational problem

The method set out in section 3 is now tested in a realistic situation. The experience uses a software product, called SOFI, dedicated to the optimization of local communities' budgets, with a French interface. In this subsection, we describe the test and in subsection 4.4, we discuss technical aspects concerning the way we tuned the method and the way we prevented the appearance of problems we met.

In order to keep the study as realistic as possible, the budget model and numbers that have been chosen are drawn from an actual customer of the company MGDIS. The city council (city of which we will not cite the name for confidentiality reasons) used SOFI to simulate the impact of a dozen projects onto the budget of the community. Using this application, a financial expert (Thomas Hody) provided us with two Multi-Year Prospective Budgets. They correspond to ideal but not reachable situations. The results of our Genetic Algorithm based optimization process have been validated by the same person as a solution that indeed improves on the use of the community financial resources.

The first solution, presented in Figure 10, is quite liberal, with all projects being realized, and the taxes increased at the maximum rate of 7% in the first three years (see the second line of the second part of the Table in Figure 10). The Capacity to Be Free of Debt ratio remains in the acceptable range (see the "Capacité de désendettement" line at the bottom of the table in Figure 10). The second solution we picked is a much more careful, with only the top priority projects being done, and a very limited increase of tax applied so that the capacity to be free of debt ratio remains below 15 years, which is the prudential limit. Figure 11 shows the values for this second solution.

Figure 12 shows a representation of the proceedings of the projects for the careful solution. A color code helps spotting the priorities of the projects (from hight priority: red, orange, yellow, blue: low priority ). It should be noted that, in our example, priority one projects account for the vast majority of the budget.

The coding follows such rules:

• The first five genes code the five less-than-one-priority projects (the priority-one projects are always active).

• The coding is equally distributed for each unit: below half, the project is inactive, above half, the project is active.

• The next five genes contain the evolution of tax, written as a double.

• We consider the limits to be 0% at the minimum, and 7% at the maximum. Thus, the decoding will realize a modulus 0.07 function on the values.

The fitness function that was used works as follows:

• The number of projects brings a linear satisfaction, and accounts for 25% of the final fitness.

Figure 12: The proceedings of the projects for the careful solution.

• The evolution of the tax is best at 0% and worst at 7%.

• Its average evolution accounts for 10% of the global fitness, and its evolution in the last two years accounts for 5%.

• The capacity to be free of debt is optimal at 0 year and worst at 15 years and more. This accounts for 25% of the final grading of the solution.

• The capacity to spare money is optimal at 5%, and accounts for 25% of the global fitness.

• No variation at all (in the tax evolution) gives the best results, and this part of the grade accounts for the remaining 10% of the global fitness.

The language used is C#, and the Genetic Algorithm framework is the one from AForge, which is an Open Source project. The definition of the two vectors corresponding to the solution points are programmed as:

By constraining the solutions into a hypercube using the method described in this paper, we reach an optimum which has been validated by a finance professional as a reasonable solution for the community budget. The corresponding coding is: (30)

The prudential ratios are respected, as the solution in the graphic simulator of Figure 13 shows (Capacity to Be Free of Debt, abbreviated as CDD in French, must remain under 15 years). The fitness obtained is 59%, and the 500 generations took 17 minutes and 32 seconds to be simulated on the reference machine. Interestingly, an independent computation with only 100 generations, which took 3 minutes and 32 seconds, showed a final fitness of 58%, so the convergence is quite quick for this particular example. The corresponding chromosome was:

[1,11266759532518, 0,0838990704498006, 0,565754259647956, 0,440107396614116, 0,813652694225311, 0,642521321773529, 0,575349082741285, 0,447334636593206, 0,488786454202292, 0,990373758336907]

In terms of budget, this means:

Project 1: OFF, Project 2: OFF, Project 3: ON, Project 4: OFF, Project 5: ON, Tax evolution : 1.25%, 1.53%, 2.73%, 6.88%, 1.04%.

(32)

One will notice that the activation of the different projects is the same as the other solution, whereas the choice of Tax Evolution pattern is quite different. A quick conclusion would be that the fitness is more dependent on the projects activation than on the tax evolution, but this would need a robustness analysis, and this was not the subject of the present study.

The most interesting part of the result is that, along the generations, the solutions found are quite concentrated, as shown in Figure 14. This should be compared to the initial Genetic Algorithm optimization without Gram Schmidt projection. The effect of using this particular technique is that the solutions are found into a constrained set of solution, without the user needing to explain how it is constrained, but by letting one propose two solutions surrounding the searched one. The effect on the rapidity on the convergence was expected as an additional result of the study, but we could not demonstrate any noticeable or provable effect on this factor. Further studies need to be done, with a high volume of test, in order to determine whether the two points approach helps the convergence of the Genetic Algorithms or not, and depending on which conditions on the fitness of the coding of the chromosomes.

Parameter choices for the test

Of course, the justification of the parameters chosen for the tuning of the Genetic Algorithms engine would make for an entire article on their own, so we will just provide a justification for running tests like the one described in subsection 4.3. More precisely, in this subsection, we report on a detailed study that allowed us to tune the parameters in this context.

The first part of the validation of values used for auto-shuffling, crossing, mutation and random selection rates are simply that they are the default values provided by the Open Source component AForge.Genetics. One can safely assume that these values have been chosen to be a correct fit to general situations.

The second part of the validation completes the first one, as the previous hypothesis has indeed been verified by the complete study, the outcome of which is shortly described below.

The auto-shuffling parameter allows for a dispersion of the chromosomes after selection. This is useful when the selection method forces the list of upcoming chromosomes to be sorted, which can result in lower-quality crossing of the chromosomes thereafter. The "false" parameter in our case is indeed the best in terms of convergence speed (external parameters like the size of the population have no impact on the result) as shown in Figure 16. The impact of the crossing rate has also been studied in the same conditions (accounting for variations of other parameters), and brought to the same conclusion that the default value Figure 16: Convergence with and without auto-shuffling. of 0.75, provided by AForge, is quite optimal (see Figure 17). Next analyzed parameter is the mutation rate, and again, the default value of 0.1 is close from ideal in our case of study (see Figure 18). The random selection rate is not used by the tailored selection algorithm created for the budget optimization engine. Finally, the impact of the size of the population on the convergence speed has also been analyzed (see Figure 19), and brought us to use a value of 50, which was considered an optimal ratio between speed and memory use.

As an aside note, the robustness tests around the four parameters needed to run several hundreds of hour-long tests, in order to simulate all the different possible combination. This has been achieved by creating a small software component that was dedicated in running jobs on colleagues' computers at night, collecting data and centralizing results back on the author's computer in the morning. This ad-hoc mechanism has also been used for the actual simulation, in order to test its robustness.

Working with Genetic Algorithms makes for two competing risks that must be continuously balanced: under-fitting and over-fitting. In an under-fitting simulation, the gener- ation algorithm introduces too much variety in the chromosomes for the fitness algorithm to restrain the population to a fitter one than the previous one. The over-fitting problem is the exact reverse, where the fitness algorithm completely stifles the expansion of the possible domain created by the generation algorithm, thus resulting in a lack of genetic variety, potentially leaving more ideal genes out of the simulation. The under-fitting problem is head-on addressed by the very principle proposed in the current paper, which is to reduce the exploration domain to one restricted to the immediate neighborhood of two relatively satisfactory points. The restriction on the domain is achieved by choosing the chromosomes on constrained multi-dimensional boxes, the corresponding business values being then retrofitted in the standard domain of values by using the Gram-Schmidt routine. The over-fitting problem is addressed by carefully choosing the selection method among commonly-accepted ones. On very continuous problems, the "Elite" selection mode achieves best results, by quickly removing the poor genes from the pool. On discontinuous problems like the ones linked to budget optimization, it is better to not be too harsh on the selection, and adopt a more exploratory selection mode, like "Roulette". In the "Roulette" method, the chromosomes are not simply eradicated if they do not correspond to a high ranking with respect to the fitness method, but have simply a lower chance of being selected for the next generation. This results in a more flexible approach, where the exploration of unknown domains is allowed, but more or less quickly forbidden if they do not bring an improvement on the fitness. The question of the tuning between the "Elite" and the "Roulette" part of the selection algorithm could bear a complete study on its own. In the present study, this ratio has been chosen to a balanced default value of half / half, after that a considerable number of nightly robustness tests showed that increasing the exploratory part did not bring any better solution. After these tests, the ratio was kept for all subsequent simulations. It would of course be possible to optimize the computation time by slowly decreasing this ratio to a more Elite-oriented algorithm, but the improvement on computational time (which cost was extremely low, all simulations being run on low-range PCs) would not make up for the risks on not detecting a better solution for the budget. This kind of adjustment is let for further study.

Conclusion

In this paper, a method based on Genetic Algorithm to build a collection of Financial Solutions from two acceptable ones is set out, and explored. The way to tackle that the collection is sought in a neighborhood of the two acceptable solutions calls on a Gram-Schmidt routine to comfortably build a box surrounding them. This routine brings also a way of coding the solution that can be used in the Genetic Like Algorithm. The method is then tested on simplified one-dimensional problems to exhibit that it has the capability to locate the argument of the maximum of a Fitness Function and to generate a collection of solutions which is distributed over the set of all the arguments of the maximum when the Fitness Function has a plateau as a maximum. This last capability is the important one in view of the targeted operational applications which concerns the financial strategy of local communities. Finally, the method is tested on an example of the targeted operational applications and gives interesting results which is promising. It seems to be a potential alternative or a support to the heavy protocol (involving many meetings with experts and decision makers) to set out a suitable Financial Solution for local communities.

Figure 1 :

 1 Figure 1: French local community Yearly Budget System working.

Figure 1

 1 Figure 1 depicts the schematic working of French local community yearly budget. To explain this working, we adopt a systemic point of view allowing us to give a global and macroscopic description, without going into technical or semantical details, of what we call in the following: the Yearly Budget System.For readers interested in French local community finance system, we refer to[START_REF]La qualité comptable au service d'une gestion performante des collectivités locales -guide des bonnes pratiques num 18[END_REF] and[START_REF]Annexe num 1: Plan de comptes développé des communes de 500 habitants et plus au 1ier janvier 2009[END_REF].

Figure 2 :

 2 Figure 2: Synthetic Yearly Budget System

Figure 3 :

 3 Figure 3: Multi-Year Prospective Budget System working.

  5 ) of targeted Investment Level and targeted Capacities to Be Free of Debt translating into financial terms the projects the Decision-Makers plan to get realized and the level of financial sanity they want to reach. In addition, the Political Goal is provided by a Tax Evolution Pattern, which expresses at what time Decision-Makers accept tax increases and at what time they prefer stability of tax levels.

1 INPUTFigure 4 :

 14 Figure 4: Multi-Year Prospective Budget computed considering Investment Level as input and Tax Levels and Capacities to Be Free of Debt as outputs.

1 Figure 5 :

 15 Figure 5: Multi-Year Prospective Budget computed with Capacities to Be Free of Debt as inputs and Tax Levels and Investment Levels as outputs.

i&

  ) i=1,...,5 , (T l i & ) i=1,...,5 ) such that S((I l i & ) i=1,...,5 , (T l i & ) i=1,...,5 ) satisfied constraints (5), (4) and (6) and with Fitness worth F ((I l i & ) i=1,...,5 , (T l i & ) i=1,...,5 ) as large as possible.

5 k=1

 5 min(C k (S((I i ) i=1,...,5 , (T i ) i=1,...,5 )), 0)) + 5 k=1 max(C k (S((I i ) i=1,...,5 , (T i ) i=1,...,5 )) -C max , 0) + 5 k=1 max(T k -T max k , 0) , (21)

Figure 6 :

 6 Figure 6: Fitness Function (bottom) with one maximum, which is the sum of two functions (top and middle).

Figure 7 :

 7 Figure 7: functions f 1 (top left), f 2 (top right), g 1 (bottom left) and g 2 (bottom right).

Figure 8 :

 8 Figure 8: The Fitness Function (bottom) with maxima on a plateau which is strictly included in the interval made by the argument-of-the-maximum localizations of the two functions (top and middle) it is the sum of.

Figure 10 :Figure 11 :

 1011 Figure 10: The quite liberal solution. (The software has a French interface; the translations are: Capacité de désendettement = Capacity to Be Free of Debt, Variation des taux = Tax Increase, Produit fiscal direct = Taxes, Dépenses réelles de fonctionnement = Operating Expenditures, Recettes réelles de fonctionnement = Operating Recipes, Epargne brute = Operating Budget Excess.)

  Vector v1 = new Vector(new double[] { 0.75, 0.75, 0.75, 0.75, 0.75, 0.07, 0.07, 0.07, 0.00, 0.00 }); Vector v2 = new Vector(new double[] { 0.25, 0.25, 0.25, 0.25, 0.25, 0.03, 0.02, 0.02, 0.00, 0.00 });

  OFF, Project 2: OFF, Project 3: ON, Project 4: OFF, Project 5: ON, Tax evolution : 3.48%, 2.85%, 6.18%, 3.02%, 3.39%.

Figure 13 :

 13 Figure 13: The optimal solution.

Figure 14 :

 14 Figure 14: The final population.

Figure 15 :

 15 Figure 15: The initial population.

Figure 17 :

 17 Figure 17: Influence of crossing rate.

Figure 18 :

 18 Figure 18: Influence of mutation rate.

Figure 19 :

 19 Figure 19: Influence of population size.

Capacity to be free of debt

	For next years			Taxes
				Operating
	Current		Expenditures	Operating
	debt			recipes
			Interest
			payment	Operating budget excess
	Capital
	repayment	Gross self-
			financing capacity
	Capital that	Net self-financing capacity	Investment level
	remains due
			Loan

http://www.mgdis.fr/

Acknowledgements -The authors thank the referee who pointed some lacks in the first version of the paper. He permitted a substantial improvement of the paper.

Resizing of obtained solutions

After several iterations of the algorithm just described, we have on hand a collection of N codings. Q l & , for l = 1, ..., N . Then, the R l & = ((I l

Tests

The method is now tested on several examples. First, it is tested on one-dimensional problems in order to set out its capability to exhibit the point where the maximum of the fitness is located, and, in the case when the fitness shows a plateau with value of which is its maximal, to produce a population which is essentially located on the interval which range is the plateau. Secondly it is tested on the example of local community finances that is described in the previous sections.

Test on a one-dimensional problem with a Fitness Function having one maximum

The Fitness Function considered here is a function with one maximum, which is the sum of two quadratic ones. More precisely, defining

which are given in Figure 6 at the top and in the middle, the Fitness Function is

defined on [0, 1] and drawn at the bottom of Figure 6.

We have chosen those functions in order to obtain a function F supported in (0, 1) and with values ranging in [0, 1].

A simplified version of the method described above was implemented on this example, with the maxima of h 1 (x) and h 2 (x) playing roles analogous to those played by points (( I i ) i=1,...,5 , (T c i ) i=1,...,5 ) and ((I c i ) i=1,...,5 , ( T i ) i=1,...,5 ) in the above described method. On this example, the method works and gives after 500 generations a collection of points which is very concentrated around x = 0.5, which is the argument of the maximum of the fitness function.

Nonetheless its efficiency was compared to optimization methods using a similar Genetic Like Algorithm, but not involving the two points around which the argument of the maximum is sought. The method built here was not more efficient. This seems to lead to the conclusion that the contribution of this method is not to be sought in this direction. Table 1: The collection of points after 500 generations when the Fitness Function is given by (26).

x 0.489 0,491 0,491 0,500 0,492 0,489 0,487 F 0,910 0,910 0,910 0,910 0,910 0,910 0,910 x 0,506 0,492 0,493 0,490 0,491 0,497 0,497 F 0,910 0,910 0,910 0,910 0,910 0,910 0,910 x 0,494 0,493 0,489 0,496 0,489 0,494 1,471 F 0,910 0,910 0,910 0,910 0,910 0,910 0,00 x -0,475 0,464 0,462 0,485 0,492 0,501 0,488 F 0,000 0,910 0,910 0,910 0,910 0,910 0,910 x 0,489 0,492 0,496 0,492 0,435 0,534 0,484 F 0,910 0,910 0,910 0,910 0,646 0,860 0,910


Thierry Pécot

Shantanu Singh

Enrico Caserta

Kun Huang

Raghu Machiraju

Gustavo Leone

NON PARAMETRIC CELL NUCLEI SEGMENTATION BASED ON A TRACKING OVER DEPTH FROM 3D FLUORESCENCE CONFOCAL IMAGES

Keywords: Detection, tracking over depth, fluorescence confocal microscopy

3D cell nuclei segmentation from fluorescence microscopy images is a key application in many biological studies. We propose a new, fully automated and non parametric method that takes advantage of the resolution anisotropy in fluorescence microscopy. The cell nuclei are first detected in 2D at each image plane and then tracked over depth through a graph based decision to recover their 3D profiles. As the tracking fails to separate very close cell nuclei along depth, we also propose a corrective step based on an intensity projection criterion. Experimental results on real data demonstrate the efficacy of the proposed method.

INTRODUCTION

In cancer biology, the comprehensive study of cellular phenotypes provides information about the structure and function of different cell compartments (fibroblasts, macrophages, endothelial and epithelial cells) in the microenvironment. A detailed study of nuclear morphology will allow for the association of the phenotypes to specific genotypes (wild-type, mutants). This analysis needs to first segment the cell nuclei.

Many segmentation methods have been deployed on fluorescent microscopy images. Geometric active contours methods take advantage of the level sets framework to extract the cell nuclei boundaries by using an energy term defined from intensity variations. These methods have been successfully applied to 3D microscopy image stacks [START_REF] Dufour | Segmenting and tracking fluorescent cells in dynamic 3-D microscopy with coupled active surfaces[END_REF][START_REF] Mosaliganti | Reconstruction of cellular biological structures from optical microscopy data[END_REF]. However, the success of these methods is very dependent on the initial selection of the contours. Watershed based methods [START_REF] Lin | A hybrid 3D watershed algorithm incorporating gradient cues and object models for automatic segmentation of nuclei in confocal image stacks[END_REF][START_REF] Cheng | Segmentation of clustered nuclei with shape markers and marking function[END_REF] consider images as topographic reliefs and segment objects of interest by releasing water from seed points. Unfortunately, these methods tend to over-segment cluttered cell nuclei. In [START_REF] Li | 3D cell nuclei segmentation based on gradient flow tracking[END_REF], the authors propose a gradient diffusion procedure followed by a gradient flow tracking to localize cell nuclei centers. A local adaptive thresholding is then applied to achieve a segmentation of the cell nuclei. This method is particularly efficient for high quality and high resolution images.

In 3D fluorescent confocal images, the resolution along the depth is poorer than in the two other directions. This anisotropy prevents the robust capture of cell nuclei. To accommodate this disparity in the resolutions, we propose a new approach based on cell tracking and a graph based decision process. First, we detect cell nucleus components at each plane of the image volume. Then, we present a graph based decision process to track the cell nucleus components over depth. As the tracking over depth is not always able to separate cluttered cell nuclei, we also introduce a correction step that exploits an intensity projection criterion. We demonstrate the effectiveness of our approach by comparing its performances to competitive cell nuclei segmentation methods using real 3D fluorescence confocal images with both isolated and cluttered cell nuclei.

CELL NUCLEI DETECTION

Methods based on intensity local curvature [START_REF] Thomann | Automatic fluorescent tag detection in 3D with superresolution: application to the analysis of chromosome movement[END_REF], Laplacian of Gaussian [START_REF] Sage | Automatic tracking of particles in dynamic fluorescence microscopy[END_REF], conditional random fields [START_REF] Pécot | Conditional random fields for object and background estimation in fluorescence video-microscopy[END_REF], mathematical morphology [START_REF] Sternberg | Biomedical image processing[END_REF][START_REF] Vincent | Morphological grayscale reconstruction in image analysis: Applications and efficient algorithms[END_REF] or image decomposition [START_REF] Chessel | Computational geometry-based scale-space and modal image decomposition: Application to light video-microscopy imaging[END_REF] for cell nuclei detection were reported earlier in the literature. In this study, we decide to divide this process into three steps: i) compute a detection measure; ii) threshold the detection measure; iii) identify each cell nucleus component.

For computing a detection measure, we choose the multiscale approach of [START_REF] Olivo-Marin | Extraction of spots in biological images using multi-scale products[END_REF] since it is robust to noise in fluorescence images and it enables to consider different image resolutions. This approach divides an input image into several wavelet planes at different scales. In practice, K resolutions {I z acquired at depth z are obtained through the repeated convolutions with a Gaussian separable kernel along the two canonical directions:

I (i) z = I (i-1) z * G B3 , 1 ≤ i ≤ K, ( 1
)
where 1 16 is a B3-spline version of the isotropic wavelet transform [START_REF] Starck | The undecimated wavelet decomposition and its reconstruction[END_REF]. The wavelet planes are then defined as the difference between two consecutive resolutions of the original image:

G B3 = 1 16 , 1 4 , 3 8 , 1 4 ,
W (i) z = I (i-1) z -I (i) z , 1 ≤ i ≤ K. ( 2
)
Fig. 1. Thresholds estimated with the Maximum Entropy Thresholding method on a stack of 105 images followed by a linear least squares estimation.

The lower the wavelet plane resolution is, the higher the image scale is.

To locate the cell nucleus components, we propose to use the Maximum Entropy Thresholding (MET) method [START_REF] Sahoo | Threshold selection using a minimal histogram entropy difference[END_REF] to threshold each wavelet plane. The MET method provides the threshold that maximizes the sum of the entropies measured in the object and background components. The thresholds estimated at each depth vary according to the intensity distribution in each image (see Fig. 1). This distribution depends not only on the number of cell nucleus components in each image, but also on the attenuation arising from photobleaching. The thresholds have to be similar across the image planes to prevent from detection jumps: a part of a nucleus is detected at depth z, not detected at depth z + 1 and detected again at depth z + 2. In order to avoid this phenomenon and to mitigate the photobleaching effects, we propose to regularize the thresholds over the image stack by using a linear least squares fitting procedure (see Fig. 1).

The final step for detection is the identification of each cell nucleus component at each depth. For this purpose, the connex components in the thresholded wavelet planes are associated to cell nucleus components. But, as two spatially close cells will only be associated to one connex component, we prefer to consider each local maximum in the wavelet planes located in these areas. Let x z = {x 1 z , . . . , x r z } be the set of r local maxima at depth z located in the thresholded wavelet plane regions. When two local maxima belong to the same component, they have to be separated. We propose to take advantage of the minimal path framework [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF][START_REF] Racine | Visualization and quantification of vesicle trafficking on a 3D cytoskeleton network in living cells[END_REF] given its computational efficiency. It has to be noted that watershed methods lead to the same results. When l local maxima x j z , j = 1, . . . , l belong to the same cell nucleus component, we compute the minimal action maps associated to each local maximum:

∀x ∈ S, U x j z (x) = min A(x j z ,x) γ(x j z ,x) (P(γ(x j z , x))( )]d , ( 3
)
where S is the grid of pixels, A(x j z , x) ∈ S × S is the set of planar curves that link x j z ∈ S, x ∈ S are the points in the considered connex component, γ(x j z , x) ∈ A(x j z , x), P : S → R is a potential that takes low values when high and is the curvilinear abscissa. The minimal action maps associated to each local maximum are computed with the fast marching algorithm [START_REF] Cohen | Minimal paths and fast marching methods for image analysis[END_REF]. The detection of individual cell components obtained on a real image image is illustrated in Fig. 2.

W (i) z is (a) (b)

GRAPH BASED DECISION

We propose to apply a tracking algorithm across image planes. By establishing a correspondence between the cell nucleus components along depth, the complete nuclei can be reconstructed.

All r local maxima identified during the detection {x 1 z , . . . , x r z } at depth z are associated to r nodes {n 1 z , . . . , n r z }. Each node n u z at depth z is linked to the nearest node n v z+1 at depth z + 1 by an edge e uv z+1 (see fig. 3 (b)). A cost c uv z+1 is attributed to the edge e uv z+1 and is equal to the distance between x u z and x v z+1 . Eventually, T graphs G t , t = {1, . . . , T } corresponding to one or several cell nuclei are built. Let o Gt z be the number of nodes in G t at depth z and o Gt max be the maximum number of nodes in G t for a given depth. Let 1(•) be the indicator function such that:

1(o Gt z = m) = 1 if

INTENSITY PROJECTION BASED CORRECTION

If two cell nuclei are proximal along depth, the decision process will fail. To correct this phenomenon, we enforce separation based on an intensity projection criterion.

As a consequence of their ellipsoidal shape, the projection along depth of a cell nucleus is an ellipse while the projection of two proximal cell nuclei results in a different shape (see Fig. 4 (a;d)). Moreover, the average depth occupied by each pixel belonging to the cell nuclei shows a clearly different pattern when several cell nuclei are merged (see Fig. 4 (b;e)). Let C = {c z , . . . , c z+w } be a cell nucleus where c z = {c 1 z , . . . , c qz z } is the set of q z points belonging to the cell nucleus at depth z. Let p = {p 1 , . . . , p q } be the q points corresponding to the projection of C along depth. By using the indicator function 1(•), we define the mean depth for each point in p:

M D(p i ) = z z1(p i ∈ c z ) z 1(p i ∈ c z ). (5)
The histogram computed from M D represents the nucleus spatial distribution along depth and allows to identify when several cell nuclei are merged (see Fig. 4). If this histogram shows more than one local maximum, several cell nuclei are merged. To separate them, we first consider that only two cell nuclei are merged and extract the first and last local maxima {z 1 lm , z 2 lm } from the histogram. These two local maxima represent the depth boundaries for the new cell nuclei: above z 1 lm , all components correspond to the first cell nucleus while below z 2 lm , all components correspond to the second one. Three spatial regions can be extracted from M D: a region only associated to the first cell nucleus (#1 in Fig. 4 (e)), a region only associated to the second cell nucleus (#3 in Fig. 4 (e)), and a region shared by the two cell nuclei (#2 in fig. 4 (e)). From the first two regions, we compute the centers-ofmass {p 1 lm , p 2 lm }. Between z 1 lm and z 2 lm , all the points closer to p 1 lm (resp. p 2 lm ) belong to the first cell nucleus (resp. second cell nucleus). The same process is repeated until all the mean depth histograms only show one local maximum. An example is shown in Fig. 4 (d-g).

EVALUATION ON REAL DATA

To evaluate the performances of our cell nuclei segmentation method, we consider two image volumes acquired at a resolution equal to 0.3 × 0.3 × 0.5 µm 3 (see Fig. 5 (a)) and to 0.5 × 0.5 × 0.9 µm 3 (see Fig. 5 (e)). In order to face the two different resolutions, we use the 4 th wavelet plane for the first image and the 3 rd wavelet plane for the second image. We compare the results obtained with our Tracking based Segmentation method (TSM) against those obtained with a Gradient Diffusion based Segmentation method (GDSM) [START_REF] Li | 3D cell nuclei segmentation based on gradient flow tracking[END_REF] and with a Level sets based Segmentation method (LSSM) [START_REF] Mosaliganti | Reconstruction of cellular biological structures from optical microscopy data[END_REF], two non parametric methods that claim to be independent of the resolution. To quantitatively measure the accuracy of each method, an expert extracts from the results the number of false positives (NFP), false negatives (NFN) and correct segmentations (NCS). From these numbers, the ratios FPR = NFP N0 , FNR = NFN N0 and CSR = NCS N0 are defined, where N 0 is the number of cell nuclei in the image volume. We do not consider the cell nuclei located at the image borders.

At a high resolution (image (a)), the GDSM tends to extract other structures than cell nuclei (FPR=0.08) while at a low resolution (image (e)), it misses (FNR=0.20) a large amount of cell nuclei, leading to a very low CSR (0.56). These results show the dependence on a high resolution for the GDSM to obtain satisfying results. If the LSSM provides correct results at a high resolution, it shows a high FPR (0.10) at a lower resolution. However, it still provides a better segmentation (CSR=0.7) than the GDSM. Although the FPR (+0.05) obtained with the TSM increases when the resolution decreases, the results are similar at the two different resolutions. Overall, the obtained CSR (0.88) at a low resolution completely outperforms the CSR obtained with the GDSM (+0.32) and the LSSM (+0.18).

CONCLUSION

In this paper, we propose a new 3D cell nuclei segmentation method based on detection of cell nuclei at each image plane followed by a tracking over depth. This method yields robust results for both isolated and cluttered cell nuclei over different image resolutions comparing to several existing methods. In practice, a key feature of this method is that it only requires the scale parameter that is derived from the image resolution, allowing robust use by non experts on a very large amount of images. This method is currently being applied to data from a breast tumor microenvironment study to elucidate the distribution of different phenotypes in mouse models of different genotypes. For future work, we plan to test our method on a wider range of image volumes.

Fig. 2 .

 2 Fig. 2. (a) Confocal fluorescence image showing cell nuclei tagged with DAPI; (b) detected cell nucleus components where each color corresponds to one cell nucleus component.

Fig. 3 .

 3 Fig. 3. (a) Nine consecutive cropped detection images where the different cell nucleus components are displayed in different colors; (b) graph associated with cell nucleus components in images (a); (c) final decision pertaining to the graph to characterize the two cell nuclei in images (a).

Fig. 4 . 1 0

 41 Fig. 4. (a) Projection of one cell nucleus along the depth direction; (b) mean depth computed from image (a); (c) histogram computed from image (b); (d) projection of the two cell nuclei along the depth direction; (e) mean depth computed from image (d); (f) histogram computed from image (e); (g) separation of two cell nuclei shown in (d-e) with the corrective method applied duly.

Fig. 5 .

 5 Fig. 5. (a) Volume rendering of a fluorescent confocal 1024 × 1024 × 105 image acquired at a resolution equal to 0.3 × 0.3 × 0.5 µm 3 ; (b-d) surface renderings of cell nuclei segmentations obtained for image (a) using GDSM (b), LSSM (c) and TSM (d); (e) volume rendering of a fluorescent confocal 465 × 400 × 85 image acquired at a resolution equal to 0.5 × 0.5 × 0.9 µm 3 ; (f-h) surface renderings of cell nuclei segmentations obtained for image (e) using GDSM (f), LSSM (g) and TSM (h).

  Gt max }. We introduce o Gt max hypotheses H m , m = 1, . .. , o Gtmax : H m postulates that there are m cell nuclei associated to the graph G t . A measure of conceivableness M m is defined for each hypothesis as M m =

	t ,
	0 otherwise,
	(4)
	where m ∈ {1, . . . , o z 1(o Gt z = m). The hypothesis with the highest measure of
	conceivableness is finally chosen, and the associated number
	of nodes m gives the number of new graph(s) to build from
	G t . The new graph(s) is(are) directly obtained by a modifi-
	cation of G

there are m nodes at depth z in G t , depth by depth. At depth z, if o Gt z > m , the m -o Gt z node(s) with the closest local maxima are merged. On the other hand, if o Gt z < m , the o Gt z -m edge(s) with the highest cost within the edges that are linked to a same node is(are) removed. An example is illustrated in Fig.

3 (c

).

Acknowledgement

T. Pécot is recipient of the Pelotonia Fellowship Award.


Alma Solar

Anastasia Bolovinou

Geert Heijenk
email: geert.heijenk@utwente.nl

Jean-Marc Lasgouttes
email: jean-marc.lasgouttes@inria.frrgimenez@bdigital.org

Rafael Giménez

Rafael Giménez Mobility

Mobility 2.0: Co-Operative ITS Systems for Enhanced Personal Electromobility

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the new challenge-facing Europe the use of electric vehicles is highly desirable for multiple reasons, such as better overall energy-efficiency, CO2 emission reduction, clean air and better utilisation of renewable energy sources. However, there are still several issues that act as bottlenecks and need to be addressed before a mass-deployment of FEVs can be achievable:  Limited FEV range, which may lead to a 'range anxiety' of drivers in the absence of a procedure that ensures that FEV owners comfortably reach their destination in any circumstance; Moreover, lack of range management systems able to cope with different battery management systems and different driver behaviours.

 Limited availability of parking spaces with public recharging facilities.

 Potential dependency of actual FEV range on grid capacity;  Scarcity of urban road space leading to general traffic congestions. This can be alleviated by at least a partial modal shift to public transport, as long as the resulting transition is a smooth one.

A suitable traffic management system for FEVs must take each of the above bottlenecks simultaneously into account, in order to achieve a journey optimisation that is acceptable and favourable for all drivers. Such an integrated approach necessitates the use of co-operative systems to coordinate the vehicles and the infrastructure. At the same time, the energy efficiency optimisation over the aggregate FEV fleet is an important objective. Since the bulk of automotive transportation consists of daily commutes to the office and back, Mobility2.0 shall focus on this scenario.

The contribution of this paper is twofold. It (1) analyses the role modern ICT can play in the acceptance of FEVs by providing comprehensive commuting assistance to FEV owners, and (2) provides a high-level architecture of a system for such commuting assistance, utilizing the high penetration of Internet-connected smartphones.

The rest of this paper is organized as follows: Section 2 gives a comprehensive overview of Mobility 2.0 application objectives and research areas. Then, Section 3 analyzes the information flow inside the Mobility 2.0 system and presents the preliminary outcome of the specification and architecture phase of the project while, Section 4 concludes this paper.

MOBILITY 2.0 concept

The concept of the multi-modal commuting assistant for FEVs envisions a distributed application based on the in-vehicle equipment of a FEV and the smart-phone of a driver that supports its owner by providing optimal travel advice during the FEV use, but also during the rest of the journey. The application is supported by traffic information, using external services and data provided by road side units. If congestion is unavoidable and passing through congestion would deplete energy resources of the car, it might also advise to park the car at a nearby charging station and switch to public transport.

Calculations will also include range estimation that takes into account the desired charging profiles and driver profile versus journey topography (e.g distance, slopes) and current traffic conditions to ensure that the car is properly charged for the way back. The system will also manage charging-spot reservation to ensure that charging spots are available when the FEV reaches the charging area.

Consequently to the above, the EU FP7 project MOBILITY 2.0 aims to focus on the research and development of an in-vehicle co-operative commuting assistant for FEVs which seamlessly takes the driver through the three-stage process of available parking reservation, vehicular navigation through sparse areas, and navigation via public transport in dense urban areas. While some previous projects have worked on the research and development of multi-modal nomadic navigators [references missing], FEV-specific aspects such as grid-friendly, community friendly spot reservation and the balancing of FEV range against the estimated duration of the commute shall be also addressed by Mobility2.0. The next section identifies the technical and scientific issues addressed by Mobility 2.0 project enabling the optimal deployment of such e-mobility applications. These co-operative applications will also be validated through integrated field trials at Barcelona and Reggio Emilia test sites.

Figure 1: FEV commuting assistant application concept

Mobility2.0 will develop the co-operative FEV commuting assistant application for the most prolific nomadic device platforms, such as Android and iPhone. Figure 1 shows the software components that this application will comprise. The multi-modal journey planner application component is in the centre, as it runs in the foreground and provides the interface for user interaction. The other complementing software components run in the background.

Route planning and journey optimization

The system specified within MOBILITY 2.0 supports two fundamental use cases in the project described as "journey planning" and "journey adaptation". While journey planning refers to the case where a user requests route recommendations for a from A to B that respect his "tolerated" means of transportation and other personal preferences (while the FEV range has been predicted to be enough for all combinations of driving parts of this journey), journey adaptation is needed when FEV of a user is running out of battery (or range), which requires to search for appropriate re-charging stations and adaptat the user-selected route.

With respect to "journey planning", the following objectives are addressed by the specification of the architecture defined in the project:

1. The route recommendation algorithm supports both optimizing the route of a single user (e.g. individual travel time), and optimizing the routes of all users; in the larter case, since route recommendations are made on the fly, the algorithm will return a route which is not optimal for the user, but is expected to minimize the overall travel time, by avoiding to use a charging station that might be more useful to another user.

2. The route recommendation algorithm supports travel time, distance, and eventually also monetary costs as optimization criteria.

3. The route recommendation algorithm supports maximum walking distance, maximum biking distance, and banning of transportation means as additional search constraints.

4. The route recommendation algorithm does not aim to optimize for the energy grid itself. Indeed, it is assumed that such objectives will be fed into the system through dynamic energy pricing at re-charging stations.

The route recommendation algorithm supports multiple intermediate stops only if those stops

do not require additional recharging. Consequently, charging at multiple stations during one journey will not be considered.

6. As part of the route recommendation algorithm, a filtering of the feasible driving sub-routes is always performed offline based on the estimated FEV remaining range.

7. Required energy in order to successfully complete a desired route may also be an output of the Range Manager component in order to allow the "journey planning" algorithm to accordingly plan duration of required charging during stops.

With respect to "journey adaptation", the following objectives will be addressed by the architecture:

1. While the FEV moves, the Range Manager performs a real-time monitoring of remaining range (in km).

2. In case that the FEV is running out of battery (range is not enough to reach the next planned stop, with a lower bound to be specified), the system informs the user.

Efficient broadcasting of FEV recharging spot data

The cooperative commuting assistant for FEV needs to have up-to-date status information on the possible recharging spots. The parking reservation of a suitable location can be then negotiated during the journey planning stage. Charging spot information needs to be available both at the nomadic devices, as well as in vehicles. For the latter, we will develop and implement a charging spot notification mechanism using geo-broadcasting over 5.9 GHz co-operative systems. Furthermore, we are specifying a protocol for charging spot reservation.

Roadside infrastructure for 5.9 GHz co-operative networks

A major deployment challenge for the realisation of large-scale co-operative vehicle-infrastructure communications is related to the effort and costs of deploying the involved road-side communications units. The questions around its financing, installation, and maintenance are unresolved yet. A straightforward solution is to utilise FEVs plugged for recharging as road-side communication units, which maintain broadband connectivity with the infrastructure through the smart-grid network.

Mobility2.0 will consider this enabling aspect that FEVs play for the large-scale introduction of 5.9

GHz co-operative networks.

Access to FEV data

In order to give the Mobility 2.0 system access to FEV-specific data such as battery capacity and remaining driving range, Mobility2.0 will specify the required data exchange interface between the vehicle and a central route planning system and contribute it for standardisation. (Since a significant portion of FEVs may be also be produced by the conversion of traditional vehicles into FEVsespecially in the near and medium terms -it is important to develop a solution that is applicable to both vehicle types.).

Software architecture

The Mobility 2.0 platform relies on a client-server based architecture, in which the user application running on the nomadic device, as well as the onboard unit in the full-electric vehicle, act as a client, and the Mobility 2.0 service as a centralized server. According to the high-level architecture specified in Task 3.1 of Mobility 2.0, communication between clients and the server will be carried out over 3G.

There will not be any direct communication between the vehicle and the nomadic device. The following subsections provide a more detailed description of the Mobility 2.0 service backend components, and sketch the graphical interface that is shown to the user through the client application in order to ensure a proper user experience. A complete specification of the interfaces offered by the Mobility 2.0 service backend is provided afterwards in Section 3.

Service Backend

This section covers the alignment and description of the components that comprise the Mobility 2.0 service backend. It does not aim to propose certain technologies that shall be used for the implementation, but rather the logical layering and decomposition of tasks and responsibilities into software components. Figure 2 illustrates the alignment of these components.

Logic layer

Identity and Vehicle Manager: manages all user accounts, registered vehicles, and is responsible for carrying out authorization or associating users with vehicles.

Station Manager: keeps track of available parking and recharging slots. It is the central unit to list available parking and recharging slots (independent of the station operator), but is not involved in the actual reservation process. Reservation is negotiated between user and station operator directly.

Traffic Manager: based on the information available to the Mobility 2.0 system, this component keeps track of the current traffic conditions in the road network. It is queried by the Multimodal Journey Planner to update the travel time costs within the search graph of the Multimodal Journey Planner, and provides estimates of future traffic conditions in city areas or even individual streets.

Multimodal Journey Planner (MJP): performs multi-modal journey planning according to the given preferences of a user (e.g. maximum time available for the trip, maximum walking distance, maximum number of transfers, etc…) and the selected optimization criteria (e.g. travel cost, travel time, travel distance). It is the main component responsible for route recommendations and depends on input provided by the Range Estimator, the Traffic Manager, as well as the Station Manager.

Incident and Status Change Notifier: keeps track of disruptions (traffic jam, metro stop being closed, etc…) and status changes (delays, etc.) occurring in the road and public transportation network. Client applications can periodically query this component for updates.

Range Estimator (RE): estimates the remaining range of the vehicle, depending on the driving behavior of the user, the current state of charge of the vehicle, the route profile, and the current weather or traffic conditions. Both a pro-active (offline) and a re-active functionality (real-time) may be supported. Knowing the future energy consumption, the required battery energy in order to successfully cover a given range can also be provided by the Range estimator if requested.

Electricity Demand Predictor: this component provides, based on the estimated arrival times of vehicles at their pre-selected re-charging stations, the estimated energy level upon arrival, and the required energy level upon departure, an estimate of the electricity demand in the city, a city area, or only at a single recharging station. It also calculates a virtual price for re-charging stations which will be considered by the journey planner when generating route recommendations.

Route Manager: the route manager keeps track of the current energy level of a vehicle, and the events that relate to the selected route of a user. For instance, the route manager will periodically re-estimate the energy level of all vehicles upon their arrival at a re-charging station in order to keep the electricity demand prediction component up to date. It further adjusts the arrival time estimate for each of these vehicles and provides such updates to the electricity demand prediction component as well.

Data acquisition layer

Bike Station Connector: provides real-time information about existing bike stations and the number of available bikes at each station, following the JSON format.

Parking and Recharging Station Connector: provides real-time information about existing parking and recharging stations, including the number of available slots. Test site specific data formats are further converted into the generic data format of the Mobility 2.0 platform.

Figure 1 :

 1 Figure 1: high-level system architecture and required interfaces Figure 1 illustrates this high-level architecture again and lists all interfaces that exist between the systems involved. Most importantly there are the interfaces I1.1 to I1.5 between the client application on the nomadic user device and the components of the Mobility 2.0 service backend. As the arrows indicate, these interfaces are used by the client application, i.e. the methods offered by the interface are invoked from client side (pull mechanism). The second set of interfaces comprises I2.1 to I2.3 and is responsible for collecting information from external data sources such as re-charging / parking stations, public transportation operators, or traffic information systems. This information is envisioned to be pulled from the Mobility 2.0 service backend periodically. The third set of interfaces comprises I3.1 to I3.3 covers the support for periodic status reports from vehicles to the Mobility 2.0 service backend. The last set of interfaces comprises I4.1 and I4.5 covers (internal) interactions between individual components of the service backend.

Figure 2 :

 2 Figure 2: Software architecture of the Mobility 2.0 service backend

Traffic Information System Connector: provides real-time information about the current traffic conditions in the city, and converts the information into a generic data format usable by the Multimodal Trip Planner component. Since the level of street segmentation used by the traffic information system does not necessarily match the level of segmentation available in Open Street Maps, a mapping of segment identifiers has to be implemented here as well.

Public Transportation Connector: provides information about the time tables of public transportation. If there are multiple public transportation operators, there can also be multiple public transportation connectors, one adapting to each system interface. Furthermore, this connector provides real-time trip updates and service alerts and translates all data into the internal data format of the Mobility 2.0 platform.

Client Application

The client application provides a front-end to the Mobility 2.0 service backend and enables the user to interact with the system. The software architecture of the client application is not specified in this document since many different mobile phone operating systems exist, each of which applying different software design principles. Section 4 will therefore specify the graphical user interface only, addressing the required screens being presented to the user, the information each screen will show, as well as the interaction flow between screens.

Future work and conclusions

The systems and solutions developed within the project will be tested and validated in two different test sites. Reggio Emilia (Italy) and Barcelona (Spain) will be the two cities acting as pilots in MOBILITY 2.0. Both cities are clear examples of FEV promoting cities in Europe. Jean-Marc Lasgouttes is a researcher at Inria, the French national institute for computer science and applied mathematics.

Authors

He is a graduate of Ecole Polytechnique, where he also obtained his PhD in mathematics. His research interests are related to basic research on probabilistic modelling, with a particular interest for applications related to transportation networks. In terms of mathematical tools, he explores the links between large random systems and statistical physics, both for macroscopic (fleet management) and microscopic (car-level description of traffic, formation of jams) analysis.

Rafael Giménez holds degrees in Computer Science and in Documentation and Information Science. His expertise covers the Engineering of complex systems, web-based semantic applications, knowledge acquisition and management systems and complex data visualization. He provides several years of experience as developer and system analyst as well as technology consultant, and is currently involved in several FP7 projects in the mobility and identity management areas, such as OpenDAI or digital.me.