Nikos D Lagaros
email: nlagaros@central.ntua.gr

Dimos C Charmpis
email: charmpis@ucy.ac.cy

Efficiency and robustness of three metaheuristics in the framework of structural optimization

Keywords: Structural Optimization, Metaheuristics, Differential Evolution, Harmony Search, Particle Swarm Optimization

Due to the technological advances in computer hardware and software tools, structural optimization has been gaining continuously increasing interest over the last two decades. The purpose of the present work is to quantitatively compare three metaheuristic optimization algorithms, namely the Differential Evolution, Harmony Search and Particle Swarm Optimization methods, in the framework of structural optimization. The comparison of the optimizers is performed with reference to their efficiency (overall computing demands) and robustness (capability to detect near-optimal solutions). The optimum design of a real-world overhead traveling crane is used as the test bed application for conducting optimization test runs.

Introduction

Structural optimization typically aims in detecting the optimum design by minimizing the cost (or weight) of a structure subject to certain behavioral constraints imposed by relevant design codes. Structural optimization applications are associated with multiple local minima, large and non-convex search spaces and several (usually conflicting) constraints to be satisfied. As a result, such applications do not favor the use of Mathematical Programming (gradient-based) algorithms, which exhibit a satisfactory local rate of convergence to the nearest optimum, but they cannot assure that the global optimum can be found when confronted with complex optimization problems. Therefore, various heuristic probabilistic-based search algorithms, which present a better global behavior and are less vulnerable to local optima, have been applied during the last decades to meet the high demands of structural optimization problems.

Several structural optimization applications have been reported, which utilize algorithms inspired by natural phenomena, such as Evolutionary Programming [START_REF] Fogel | Artificial Intelligence through Simulated Evolution[END_REF], Genetic Algorithms [START_REF] Goldberg | Genetic Algorithms in Search Optimization and Machine Learning[END_REF] and Evolution Strategies [START_REF] Rechenberg | Evolutionsstrategie -Optimierung technischer Systeme nach Prinzipien der biologischen Evolution[END_REF], among others. More recently, new metaheuristic optimizers have been developed based on the simulation of social interactions among members of a specific species looking for food or resources in general. One such method is Particle Swarm Optimization (PSO) [START_REF] Kennedy | Particle Swarm Optimization[END_REF], which is based on the behavior reflected in flocks of birds, bees and fish that adjust their physical movements to avoid predators and seek for food. Two other metaheuristics with growing interest within the structural optimization community are Differential Evolution (DE) [START_REF] Price | Differential Evolution -A Practical Approach to Global Optimization[END_REF][START_REF] Storn | Differential Evolution -a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[END_REF] and Harmony Search (HS) [START_REF] Mahdavi | An improved harmony search algorithm for solving optimization problems[END_REF][START_REF] Degertekin | Optimum design of steel frames using harmony search algorithm[END_REF].

The purpose of the present work is to provide quantitative comparison results on the performance of the three aforementioned metaheuristics (DE, HS and PSO) in the framework of structural optimization. A typical overhead traveling crane (the crane bridge span, the trolley, the end carriages and the runway beam span) was selected from the catalogues of GH Cranes SA (a manufacturer of elevation systems) as the test bed problem for conducting optimization test runs. A 3D CAD model was developed for the crane and its cross-sectional dimensions have been optimized using DE, HS and PSO subject to constraints imposed by Eurocode Standards.

The Metaheuristic Algorithms

This section provides a short description of the three metaheuristic optimization algorithms (DE, HS and PSO) assessed in the present work. All three algorithms are applied to an optimization problem, which can be formulated as follows: min ( )

( ) 0.0 ∈ ≥ f subject to g x x x F (1)
where f denotes the objective function, x is the vector of design (decision) variables, F represents the design (search) space and g are the constraint functions of the problem.

Differential Evolution (DE)

In 1995, Storn and Price [START_REF] Storn | Differential Evolution -a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[END_REF] proposed a new floating point evolutionary algorithm for global optimization and named it Differential Evolution (DE). DE has a special kind of differential operator, which is invoked to create new offspring from parent chromosomes instead of the classical crossover or mutation. DE is a novel parallel direct search method which utilizes NP parameter vectors x i,G (i=1,..,NP) as a population for each generation G. The initial population is generated randomly. As a rule, a uniform probability distribution for all random decisions is assumed. In case a preliminary solution is available, the initial population is often generated by adding normally distributed random deviations to the nominal solution x nom,0 . The crucial idea behind DE is a new scheme for generating new vectors. DE generates new vectors by adding the weighted difference vector between two population members to a third member. If the resulting vector yields a lower objective function value than a predetermined population member, then the newly generated vector replaces the vector with which it was compared. The comparison vector can -but needs not to bepart of the generation process mentioned above. The best parameter vector x best,G is evaluated for every generation G in order to keep track of the progress made during the optimization process. The extraction of distance and direction information from the population to generate random deviations results in an adaptive scheme with excellent convergence properties. Several variants of DE have been proposed so far, the two most popular of which are presented below as schemes DE1 and DE2.

Scheme DE1. The first variant of DE works as follows: for each vector x i,G , a trial vector v is generated according to:

1, 2 , 3, ( -
) = + ⋅ r G r G r G F v x x x (2)
The integers r1, r2 and r3 are chosen randomly from the interval [1,NP] and are different from the running index i. F is a real and constant factor, which controls the amplification of the differential variation (x r2,G -x r3,G ). In order to increase the diversity of the parameter vectors, the vector u = [u 1 ,u 2 ,…,u D ] T is defined as follows:

, ,

= + + - ⎧ ⎫ ⎪ ⎪ = ⎨ ⎬ ⎪ ⎪ ⎩ ⎭ j D D D j i G j v for j n n n L u x otherwise 1 ..., 1 ( )
where the acute brackets D denote the modulo function with modulus D.

Scheme DE2. In the second variant of DE, the trial vector v for each vector x i,G is generated through the expression:

( )

, , , 2 , 3 , ( - )
- = + × + × i G best G i G r G r G F λ v x x x x x ( 4
)
which introduces an additional control variable λ. The idea behind λ is to provide a means to enhance the greediness of the scheme by involving the current best vector x best,G . This feature can be useful for non-critical objective functions. The construction of u from v and x i,G , as well as the decision process, are identical to those of DE1.

Harmony Search (HS)

The Harmony Search (HS) algorithm was originally inspired by the improvisation process of Jazz musicians. Each musician corresponds to a decision variable; musical instrument's pitch range corresponds to decision variable's value range; musical harmony at certain time corresponds to the solution vector at certain iteration; and audience's aesthetics corresponds to the objective function. Just like musical harmony is improved as time passes, the solution vector is improved iteration by iteration. HS utilizes a number of parameters: harmony memory size (HMS), harmony memory considering rate (HMCR), pitch adjusting rate (PAR), maximum improvisation (MI) and fret width (FW). HMS is the number of solution vectors simultaneously handled by the algorithm. HMCR is the probability of choosing one value from the musician's memory (0 ≤ HMCR ≤ 1). Thus, (1-HMCR) is the rate with which HS picks one value randomly from the total value range. PAR is the rate with which HS tweaks the value originally picked from memory (0 ≤ RAR ≤ 1). Thus, (1-PAR) is the rate with which HS keeps the original value obtained from memory. MI is the number of iterations. HS improvises one harmony (= vector) at each iteration. Finally, FW refers to the term fret, which is the metallic ridge on the neck of a string instrument dividing the neck into fixed segments; each fret represents one semitone. In the context of the HS algorithm, frets are arbitrary points which divide the total value range into fixed segments and fret width (FW) is the length between two neighboring frets. Uniform FW is normally used in HS. Mahdavi et al. [START_REF] Mahdavi | An improved harmony search algorithm for solving optimization problems[END_REF] suggested that PAR increases linearly and FW decreases exponentially with iterations:

min max min 1 ( ) ( - ) = + × PAR I PAR PAR PAR MI ( 5
) min max max ( ) exp ln ⎡ ⎤ ⎛ ⎞ = ⎢ ⎥ ⎜ ⎟ ⎝ ⎠ ⎣ ⎦ FW I FW I FW FW MI (6)
Once the optimization problem is formulated and the parameter values are set, a random tuning process is performed. The HS algorithm initially improvises many random harmonies. The number of random harmonies is at least HMS (this number can be more than HMS, such as two or three times HMS [START_REF] Degertekin | Optimum design of steel frames using harmony search algorithm[END_REF]). Then, top-HMS harmonies are selected as starting vectors. Musician's harmony memory (HM) can be considered as a matrix.

( ) ( ) ( )

1 1 1 1 1 1 2 3 2 2 2
⎡ ⎤ ⎢ ⎥ ⎢ ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ v v HMS HMS HMS HMS HMS v f x x x x x x x x f x HM x x x x f x χ (7)
Once the HM is prepared, a new vector (=harmony) is improvised based on the following operators:

Memory Consideration: When HS determines the new value x i , it randomly picks the j-th value from HM = {x i 1 … x i HMS } with probability HMCR. The appendix j is taken from a uniform distribution U (0, 1):

j int(U(0,1) . HMS) +1 ← ( 8
)
Pitch Adjustment: Once the value x i new is randomly picked from HM in the above memory consideration process, it can be further adjusted to neighboring values by adding a certain amount to the value, with probability of PAR. For a discrete variable, if x i (k) = x i new , the pitch-adjusted value becomes x i (k+m), where m є {-1, 1} normally; and for a continuous variable, the pitch-adjusted value becomes x i new + Δ, where Δ = U(0,1) * FW(i) normally. The above-mentioned three basic operations (random selection, memory consideration and pitch adjustment) can be expressed as follows:

( ) ( ) ( ) { } ( ) { } ( ) ( ) ( ) 1
⎧ ⎫ ⎧ ⎫ ∈ ⎪ ⎪ ⎪ ⎪ - ⎨ ⎬ ⎪ ⎪ ⎡ ⎤ ∈ ⎪ ⎪ ⎣ ⎦ ⎩ ⎭ ⎪ ⎪ ⎪ ⎪ ← ∈ = - ⎨ ⎬ ⎪ ⎪ + ∈ ⎧ ⎫ ⎪ ⎪ ⎨ ⎬ ⎪ ⎪ + Δ ∈ ⎩ ⎭ ⎪ ⎪ ⎩ ⎭ L U

Particle Swarm Optimization (PSO)

In Particle Swarm Optimization (PSO), multiple candidate solutions coexist and collaborate simultaneously. Each solution is called a 'particle' that has a position and a velocity in the multidimensional design space. A particle 'flies' in the problem search space looking for the optimal position. As 'time' passes during its quest, a particle adjusts its velocity and position according to its own 'experience', as well as the experience of other (neighbouring) particles. Particle's experience is built by tracking and memorizing the best position encountered. As every particle remembers the best position it has visited during its 'flight', the PSO possesses a memory. A PSO system combines local search method (through self experience) with global search method (through neighbouring experience), attempting to balance exploration and exploitation.

Each particle maintains two basic characteristics, velocity and position, in the multi-dimensional search space that are updated as follows:

( ) ( ) Pb, Gb 1 1 2 2 ( 1) ( ) ( ) ( )
+ = + - + - o o j j j j j t w t c t c t v v r x x r x x (10) ( 1) ( ) ( 1)
+ = + + j j j t t t x x v ( 11
)
where w is the inertia weight parameter, v j (t) denotes the velocity vector of particle j at time t, x j (t) represents the position vector of particle j at time t, vector x Pb,j is the personal best ever position of the j-th particle, and vector x Gb is the global best location found by the entire swarm. The acceleration coefficients c 1 and c 2 indicate the degree of confidence in the best solution found by the individual particle (c1cognitive parameter) and by the whole swarm (c 2 -social parameter), respectively, while r 1 and r 2 are two random vectors uniformly distributed in the interval [0,1]. The symbol " o " of Eq. (10) denotes the Hadamard product, i.e. the element-wise vector or matrix multiplication. Fig. 1 depicts a particle's movement in a two-dimensional design space. The particle's current position x j (t) at time t is represented by the dotted circle at the lower left of the drawing, while the new position x j (t+1) at time t+1 is represented by the dotted bold circle at the upper right hand of the drawing. The figure shows how the particle's movement is affected by: (i) it's velocity v j (t); (ii) the personal best ever position of the particle, x Pb,j , at the right of the figure and (iii) the global best location found by the entire swarm, x Gb , at the upper left of the figure.

Test Case

The three metaheuristic algorithms described in the previous section have been applied for the sizing optimization of a travelling Overhead Crane (Fig. 2). The design variables (11 in total) are web, top and bottom flange sizes both of the box girder and the runway beams and the thickness (Fig. 3). The design variables of the box girder are the breadth of the top flange (DV1), the distance of the webs (DV2), the height of the girder (DV3) and the thicknesses of top flange, bottom flange, webs (DV4, DV5 and DV6, respectively). The design variables of the runway beams are the breadth of the bottom flange (DV7), the height of the beams (DV8) and the thicknesses of top flange, bottom flange, web (DV9, DV10 and DV11, respectively). The objective function of the optimization problem corresponds to the total mass of the crane system. The constrains of the problem are imposed based on the Structural Eurocodes (Chapter 2): (i) the von Misses equivalent stress must not exceed the prescribed stress limit state of the selected material used for the crane (S235) divided by the coefficient 1.1; (ii) the vertical deflection must not exceed 15mm (=L/600, where L is the span of the bridge); (iii) the vertical deflection must not exceed 15mm (=L/600). Constraints violation is taken into account by penalizing the objective function.

Each of algorithms DE (scheme DE2), HS and PSO was executed 1,000 times. The performance results obtained are summarized in Tables 1 and2 (CoV is defined as the standard deviation divided by the mean).

DE was found to give the minimum mass for the test example considered, while PSO also yielded almost the same minimum result. In general, DE and PSO appear to be rather robust algorithms, since they yield solutions close to the best result achieved with low variance when compared between several test runs. HS provides solutions of lower quality and with larger variation between several test runs. In terms of computing demands, HS seems to be the most inexpensive of the three meatheuristics. DE appears to be the computationally most demanding algorithm, while PSO performance lies between the ones of HS and DE.

Conclusions

Differential Evolution (DE) is the optimization method that was found to give the best design vector, but required the largest amount of iterations for convergence. Harmony Search (HS) is the optimization method that provided the worst design vector, but converged faster than both DE and PSO. PSO yielded solutions of almost the same quality as DE, but with less iteration demands.

In general, it can be stated that efficiency is inversely proportional to robustness. A fast algorithm (HS) cannot provide the solution quality of a robust yet computationally expensive algorithm (DE). PSO seems to be a good compromise between HS and DE, although it exhibits substantially larger computational demands that HS.

Fig. 1 .

 1 Fig. 1. PSO: Visualization of the particle's movement in a two-dimensional design space.

Fig. 2 .

 2 Fig. 2. Views of the crane and its finite element mesh.

Fig. 3 .

 3 Fig. 3. The 11 design variables.

Table 1 .

 1 Minimum objective function value achieved by the three metaheuristics.

	Optimization	Minimum mass achieved (Kg)
	Method	mean (CoV)	min	max
	PSO	2007.3 (0.33%)	1999.8	2071.7
	DE	2001.1 (0.41%)	1998.1	2084.1
	HS	2286.2 (2.43%)	2076.8	2322.3

Table 2 .

 2 Computational cost induced by the three metaheuristics (a time-consuming structural analysis of the crane is performed at each iteration of the optimization algorithms).

	Optimization	Number of iterations
	Method	mean (CoV)	min	max
	PSO	60912.0 (33.8%)	33000	157500
	DE	95613.8 (80.5)	5000	371000
	HS	5477.5 (72.6)	4422	20100


Alex Magalhães

Lau Cheuk Lung
email: lau.lung@inf.ufsc.br

Luciana Rech
email: luciana.rech@inf.ufsc.br

Decentralized Services Orchestration using Intelligent Mobile Agents with Deadline Restrictions

Keywords: Intelligent Mobile Agents, Real-Time, Distributed Systems

The necessity for better performance drives service orchestration towards decentralization. There is a recent approach where the integrator -that traditionally centralizes all corporative services and business logics -remains as a repository of interface services, but now lacks to know all business logics and business workflows. There are several techniques using this recent approach, including hybrid solutions, peer-to-peer solutions and trigger-based mechanisms. A more flexible approach regarding environment configuration and not fully explored in services orchestration technology is the use of intelligent mobile agents to execute it. In this paper, we present new adaptive heuristics for mobile agents to execute the decentralization of orchestration through missions (services) that correspond to the stages of business flow, with the ability to trade-off the quality of the result with the deadline of the mission. Some test case scenarios are presented and collected data are analyzed pointing the advantages and disadvantages of each heuristic.

Introduction

The evolution of the WWW brought the need for more complex and scalable systems. To address this need, software architects began to use a composition of services known as service orchestration. Service orchestration provides a unique interface for each composite service and coordinates several simpler services using additional business logic to execute this task of coordination. Strongly based on XML and Web Services, service orchestration quickly became the reference design in Service Oriented Architecture (SOA [START_REF] Rech | Reference Model for Service Oriented Architecture 1.0[END_REF]), centralizing all workflow at an integrator that uses languages as BPEL (Business Process Execution Language) for service coordination.

As critical systems began to use SOA, performance became an issue and there was room for improvement. To achieve better performance, decentralization and orchestration were combined and this new approach was considered very promising by authors [START_REF] Barker | The Circulate architecture: avoiding workflow bottlenecks caused by centralized orchestration[END_REF] [3] [START_REF] Barker | Eliminating The Middleman: Peer-to-Peer Dataflow[END_REF]. In decentralized orchestration, the integrator still holds all composite services interfaces, but it no longer has control over the composite services workflows. In this approach, all business logic and workflow logic is distributed among the services that forms the composite services.

The main motivation for decentralized orchestration is the achievement of better performance by critical mission and real time systems with a deadline. These systems need the benefits of a centralized repository of interfaces for composite services, but also need to address the deadline restrictions of such systems. Bearing this in mind, there has been proposed hybrid solutions based on popular technologies [START_REF] Barker | Eliminating The Middleman: Peer-to-Peer Dataflow[END_REF] [START_REF] Kyprianou | Hybrid Web Service Orchestration[END_REF].

In this paper, we propose a hybrid approach using intelligent mobile agents (MA). The integrator deploys a MA in the network that has a mission, for instance, to calculate the final price. The MA will have options such as obtaining the currency exchange rate directly going to the international bank web service or go to a local server that does not have this information in real-time. In this scenario, the sequence of nodes visited by the MA to complete its mission is called itinerary, and the itinerary will be defined by the trade-off between deadline of the mission and the desired QoS level. A MA may have previous knowledge of all the nodes it will need to visit to complete its mission or it does not have any previous knowledge of the network and will discover its itinerary from node to node, in such case, the MA is called myope.

The imprecise computing for MA with a deadline was originally presented in [START_REF] Rech | Dynamic Determination of the Itinerary of MA with Timing Constraints[END_REF], along with some simple heuristics to define the MA's itinerary. Differently of the previous mentioned works, in this paper we will present new adaptive heuristics for MA, bringing as contribution the combination of code mobility and real-time constraints in decentralized services orchestration. With this objective, this paper presents a MA hybrid solution for decentralized orchestration.

The hybrid solution for orchestration using MA fulfills the requirements of high performance and real-time deadlines of a decentralized orchestration. However, this paper does not have as objective the specification of the architecture of a decentralized orchestration using MA. The architecture used in this paper is similar to the solutions presented in [START_REF] Barker | The Circulate architecture: avoiding workflow bottlenecks caused by centralized orchestration[END_REF] [3] [START_REF] Barker | Eliminating The Middleman: Peer-to-Peer Dataflow[END_REF], with the advantage that MA architecture is already control-centric (through the MA container), resolving one of the major problems of decentralization: the environment configuration.

The main objective of this paper is to present new heuristics that define the MA itinerary during the flow of a composite service. These composite services workflows will be represented here by the MA missions. Each mission is composed of several tasks, which correspond to the internal services of each composite service. In this context, the heuristics for itinerary definition were designed to guarantee that the MA missions are completed in time so that its results are useful for the application.

In this paper, we present three heuristics of low computational cost and the performance of these heuristics will also be compared in different missions and with different deadline constraints. A real MA platform based in Java has been chosen, the JADE framework [START_REF] Bellifemine | Developing Multi-agent Systems with JADE[END_REF], in order to evaluate the performance of the system.

Related works

Several works consider decentralized orchestration, each one is singular, presenting its advantages and disadvantages, but all have the merit to address the performance issue that traditional (centralized) orchestration is associated with.

In [START_REF] Barker | Eliminating The Middleman: Peer-to-Peer Dataflow[END_REF] is presented a hybrid solution using the peer-to-peer model. It is based on the Montage workflow, a system for analysis of astronomical images developed at Caltech. Although it has better performance than centralized orchestration, the complexity of this environment maintenance and the fact that each peer of the peer-topeer network is an integrator itself make this design more complex than attractive.

In [START_REF] Binder | Decentralized Orchestration of Composite Web Services[END_REF] is presented another hybrid solution using the concept of Service Invocation Triggers. In this solution, a lightweight trigger technology is proposed to execute the data flow, using a decentralized service control. Although it has a consistent architecture, the fact that the new trigger technology is not based on any mature technology presents a problem, making the biggest contribution of [START_REF] Binder | Decentralized Orchestration of Composite Web Services[END_REF] the solution design architecture and not its new technology. The authors mentioned the MA technology, but they argue about MA security instead of evaluating it as potential solution for the problem. In the present paper we do not address the security issue.

In [START_REF] Kyprianou | Hybrid Web Service Orchestration[END_REF] is presented a hybrid solution for decentralization based on the concept of federated systems. They use Proxies in order to communicate the integrator and each task of the service, and each Proxy groups a few tasks that compose its federation. This solution is very interesting from the organizational point of view, since each federation can hold an entire area of knowledge of the corporation, but it lacks the commitment to improve the performance of the services.

In [START_REF] Schacke | Realization of an Agent-based federated system for trading workflows[END_REF] is proposed a system based on agents and on the ANAISOFT framework, which is a repository for business models. The work consists of using MA to integrate several repositories located in distinct servers and to allow the interchangeability of business models among them. Despite the fact that it does not explicitly mention the orchestration aspect of the work, the article presents an effort to decentralize the ANAISOFT repository, with the advantage of using MA to do this.

Model Description

This section presents a new approach to assist the MA in the itinerary definition for each new mission. In orchestration, each request to the integrator corresponds to a new MA mission. The three new adaptive heuristics had been developed to define the MA's itinerary and also achieve the performance and deadline requirements of the decentralized orchestration. The main objective of these heuristics is to achieve a good performance on every deadline band, i.e., to respond to soft, medium and hard deadlines while attending to the QoS defined by the client.

In [START_REF] Rech | Dynamic Determination of the Itinerary of MA with Timing Constraints[END_REF], after the performance's evaluation, we were able to correlate each heuristics to a type of deadline. The loose deadline was defined as the one where the Greedy Heuristic had the best performance; for tight deadlines, where the Lazy Heuristic had optimal performance. The adaptive heuristics presented in this paper are based on the simple heuristics described in [START_REF] Rech | Dynamic Determination of the Itinerary of MA with Timing Constraints[END_REF]. We will briefly review these simple heuristics that were the inspiration for the heuristics proposed in the present paper, in order to allow a better understanding of the adaptive heuristics with variation at the departure that will be presented later on. The Lazy Heuristic executes the service as fast as possible, disregarding the level of QoS. The Greedy Heuristic -whenever there is an alternative route -will choose the one with the highest level of QoS, despite the execution time, but respecting the rules of the mission.

It is important to point out that differently from [START_REF] Rech | Dynamic Determination of the Itinerary of MA with Timing Constraints[END_REF], in this paper we are considering services with variable QoS, i.e., all the services that compose the mission have a variable QoS proportional to execution time. This concept of variable QoS, called anytime algorithms, was presented in [START_REF] Garvey | A survey of research in deliberative real-time artificial intelligence[END_REF].

Greedy Heuristic with Variable Decrease at Start (Greedy-VD)

The Greedy-VD heuristic is a variation of the Greedy heuristic [START_REF] Rech | Dynamic Determination of the Itinerary of MA with Timing Constraints[END_REF]. As this new version is based on the concept of anytime algorithms [START_REF] Garvey | A survey of research in deliberative real-time artificial intelligence[END_REF], the level of QoS is variable depending on the execution time of each service. The GREEDY-VD strategy is to start with the classical behavior of Greedy heuristic [START_REF] Rech | Dynamic Determination of the Itinerary of MA with Timing Constraints[END_REF] and if this behavior is not efficient enough for the mission's objective, the heuristic will limit the execution time for each service at departure until it reaches an admissible level of QoS in agreement with the mission deadline. This gradual reduction of the execution time is directly associated with an adjustment factor -in this article the adjustment factor was of 10% for each new trip of the intelligent agent. I.e., the heuristics starts with the objective of reaching the maximum level of QoS (100%) and gradually adjusts it until it is capable of meet the deadline and finishing the mission successfully.

As the MA in the next mission uses the same behavior (decision making) and considering that it is a myopic MA [START_REF] Rech | Determination of the Itinerary of Imprecise Mobile Agents using an Adaptive Approach[END_REF], this heuristics goal is to find the "optimal percentage", that will allow the MA to reach the maximum level of QoS, respecting deadline of the current mission and spending the minimal number of trips (consecutive missions) possible. For example, using an adjustment factor of 10%, the MA in its third trip, if it has not found the optimal point, it can perform only 80% of the resources of the mission. This is possible because we are using variable resources and the concept of anytime algorithms.

Lazy heuristic with Variable Increase at Start (Lazy-VI)

The Lazy-VI is a variation of the Lazy heuristic previously adapted for MA. This new version is also based on the concept of anytime algorithms, so the execution time of the services are variable, allowing the heuristic not to reach the maximum level of QoS for every service of the mission. The Lazy heuristic has as main objective to finish the mission in the best time possible, despite the level of QoS. The main problem with this strategy is that whenever it has room to improve the level of QoS of a mission, it will ignore it and will keep going for the fastest execution time possible. The need to repeat the mission allowed us to modify the classical Lazy heuristic in order to maximize the level of QoS, since the acquired QoS after each MA's visit to a node is proportional to the execution time of each service.

Lazy-VI heuristic has the inverse behavior of the Greedy-VD heuristic. Initially, it uses the classical Lazy behavior (executing the minimal number of blocks allowed for each service of the mission) and in the next trips of the same mission it gradually increases the percentage of execution for each service, considering the predefined adjustment factor. The strategy of this heuristics is to start as a traditional Lazy algorithm, trying to improve the level of QoS for each mission, trip by trip. After the first trip of the mission, the heuristic increases the percentage of the level of QoS until the mission does not meet its deadline or it reaches the maximum level of QoS for each service. In case the mission does not meet its deadline, the heuristic assumes the last percentage state as the optimal percentage of execution of the level of QoS.

Greedy Heuristic with Utility Function based on Bipartition (Greedy-FB)

Greedy-FB presents a new approach for this kind of problem. This new version is based on the Greedy heuristic, on the concept of anytime algorithms and also on the concept of bipartition of the graphs theory. This heuristic is capable of executing the services partially and uses a strategy (utility function) of bipartition of the level of QoS, in order to meet the deadline and to get the maximum level of QoS for each type of deadline. The strategy of this heuristic is to initiate as a traditional Greedy heuristic in search of the optimal point of the level of QoS for each service. To accomplish this, the Greedy-FB heuristic uses a utility function based on bipartition, in order to speed up the determination of this optimal point.

When executing its first trip, in case the mission does not meet its deadline, the heuristic bipartitions the percentage interval of blocks of the service to be executed. In the second trip, this interval corresponds to [0, 100], then the heuristic will try the execution of 50% of the blocks for each service. In the third trip, in case the deadline is not met yet, the heuristic partitions one more time the interval in order to meet the deadline, and now the interval corresponds to [0, 50] and the new percentage of blocks for execution is of 25%. However, in case the mission's deadline is met in the third trip, the heuristic try to improve the accumulated level of QoS for the mission and it bipartitions the superior interval (the interval corresponding to [50, 100] and thus the new percentage of execution is 75%). The heuristic follows this strategy of bipartitions until it meets the mission deadline with a previously established range.

Performance Analysis

The purpose of the experiments is to compare the heuristics behavior and to evaluate its efficiency in different scenarios considering its deadlines.

Experiments Conditions

For these experiments we used 18 computers of 64-bit with clock speed between 2.0GHz and 3.2GHz, and 2.0 Gb of RAM. The adopted network was a 802.11g wireless network of 54 Mb/s. Each one of the computers was equipped with a Java Virtual Machine JDK 6.15 to support the JADE platform, the virtual environment supported by FIPA/IEEE to execute applications based on Mobile Agents.

Environment Configuration

For this experiment we considered 18 services and 18 nodes, where each node hosts a service in the environment. To the heuristics demonstrate its flexibility and capabilities, it is necessary that they can choose the optimal itinerary for their missions, and for that the 18 services are divided in 7 kinds of services (each kind contains the same kind of information, regardless of the node), i.e., each kind of service is represented in more than a computer of the network. Whenever possible, we placed each node of the same kind of service in computers with different clock speed, in order to better represent a real environment.

The execution time of a redundant service is considered different in every computer where it is replicated, in order to better represent a real scenario where different machines have different versions of the software that corresponds to the service. Each mission of the MA is composed of five kinds of services, whether there is an order of execution or not. Each of the heuristics evaluates the itinerary according to its algorithms, service after service, or evaluates more than a service at a time, whenever the order of execution does not exist.

We randomly generated 20 missions, all composed of five different kinds of services chosen amongst the 7 kinds of available services. We did not allow repetition. The order of execution is also variable, where a mission may have groups of kinds of services with and without precedence order. The combinations of kinds of services for the mission offer thousand of possible arrangements.

For each mission, we compute the total time of the mission and the accumulated level of QoS of the mission. The total time of the mission is composed by the time of each service execution, represented by the queuing time of the processor and the execution time of the service, and also by the MA's travel time from one node to another, respecting the network latency at the moment of the trip. The accumulated level of QoS of the mission is represented by the sum of every level of QoS of every service executed. Each service is divided in blocks of execution and each block executed represents a part of the sum in the individual level of QoS of the executed service. This division in blocks follows the anytime algorithms strategy [START_REF] Garvey | A survey of research in deliberative real-time artificial intelligence[END_REF], in order that the individual level of QoS for each service is a value between the maximum and the minimum level of QoS for this service on a specific node.

Evaluation Results

To show these heuristics performance in the experiment, we considered 3 different missions for 3 different deadline bands. The main objective of this experiment using different itineraries and deadlines is to verify the behavior of the MA heuristics on different missions. As this MA does not carry a history of the trips, it needs a short time to calibrate itself until if it defines the optimal percentage of execution time for each service that composes the mission, which will reflect in the best level of QoS for the heuristic in that kind of mission and deadline. Table 1 presents the performance of the three adaptive heuristics on hard deadlines. To better understand of the results, we have chosen a single deadline of this band (D=15). In Table 1, NS represents the number of steps (each step represents a full MA trip), columns T and Q represents, respectively, the traveling time and the level of QoS of each mission. The shadowed tuples show the best indices reached for each heuristic. However, they bold values indicate the best performances of each mission for the three heuristics. For example, for the first mission, the heuristic that best performance considering a balance of level of QoS and meeting the deadline was the Greedy-FB. It has taken seven trips (executions using different percentages of execution) to reach its optimal stage. Analyzing the number of steps (number of complete trips of the intelligent agent), the Lazy-VI heuristic was fastest for the first mission, needing fewer steps to reach the optimal percentage of execution for each service. For second and third missions, the heuristic that presented the best performance was the Greedy-FB heuristic, reaching the optimal level of QoS in the fewest number of steps. Using a Bipartition Utility Function, the Greedy-FB heuristic was expected to reach the optimal percentage quicker than the other heuristics when the band of deadline was not too hard. The results of the experiment proved this expectation. And also as expected, the Greedy-VD heuristic, did not reach the best indices for the hard deadline, needing a higher number of steps to adjust the percentage of the level of QoS and reach its optimal point. It is important to point out, to facilitate the understanding of the results, on Table 1 we only showed the results for deadline 15. Other hard deadline values presented similar results.

T Q T Q T Q T Q T Q T Q T Q T Q T Q 1 58
Figure 1 present graphics that will contribute to the understanding of the behaviors of each adaptive heuristic. Observing the graphics we can notice that, even for different missions, the heuristics behavior is similar. The graphic 1(a) illustrates the behavior for the first mission. We can notice that the Greedy-FB heuristic is the first one to reach a travel time close enough to the deadline to the mission (step seven). The ellipse evidences in the graphic the "optimal point" reached by each of the heuristics. We can also point out that after the "optimal point" the level of QoS of the missions remains the same. Graphic 1(b) represents the indices reached by the adaptive heuristics on mission two.

Conclusion

In a corporative environment, critical mission and real time systems generally suffer with centralized architectures as is service orchestration. In this article the use of MA was proposed to decentralize the orchestration. Using a similar architecture for decentralized orchestration already presented in previous works, we present three new heuristics for the MA's itinerary definition that will assist on orchestration. These heuristics use an adjustment factor to change the number of blocks executed in each service and therefore the level of QoS of the mission, respecting the mission's deadline and attending to the client's specifications.

All these heuristics are of lightweight computational cost, a necessary condition to prove MA's viability as an architecture component for decentralized orchestration, reminding that is not the objective of this article to present this new architecture, so we need to assume that some of the nodes that will be visited by the MA are of low computational power. All the heuristics used the premise of the myopia of the MA, i.e., the agent doesn't know the complete workflow of the composite service and depends on this hybrid architecture of centralized orchestration, to create composite services, and decentralized orchestration, so the services have knowledge of the data flow. The experiment was able to prove that MA is a flexible approach for decentralized orchestration, where the agent is capable of adapting its behavior to reach different levels of QoS and successfully meets the desired deadlines.

Fig. 1 .

 1 Fig. 1. Performance of Adaptive Heuristics using Deadline 15 (Hard).

Table 1 .

 1 Performance of the Adaptive Heuristics for missions with hard deadlines.

This work was partially supported by CNPq through processes 472754/2008-4 and 472801/2008-2 and CAPES.


Maria Α Antoniou
email: antonium@ceid.upatras.gr

Efstratios F Georgopoulos

Konstantinos A Theofilatos

Spiridon D Likothanassis

Forecasting Euro-United States Dollar exchange rate with Gene Expression Programming

Keywords: Gene Expression Programming, Genetic Programming, Evolutionary Algorithms, System Modeling, time series, Euro-Dollar Exchange rate

In the current paper we present the application of our Gene Expression Programming Environment in forecasting Euro-United States Dollar exchange rate. Specifically, using the GEP Environment we tried to forecast the value of the exchange rate using its previous values. The data for the EURO-USD exchange rate are online available from the European Central Bank (ECB). The environment was developed using the JAVA programming language, and is an implementation of a variation of Gene Expression Programming. Gene Expression Programming (GEP) is a new evolutionary algorithm that evolves computer programs (they can take many forms: mathematical expressions, neural networks, decision trees, polynomial constructs, logical expressions, and so on). The computer programs of GEP, irrespective of their complexity, are all encoded in linear chromosomes. Then the linear chromosomes are expressed or translated into expression trees (branched structures). Thus, in GEP, the genotype (the linear chromosomes) and the phenotype (the expression trees) are different entities (both structurally and functionally). This is the main difference between GEP and classical tree based Genetic Programming techniques.

Introduction

The problem of discovering a mathematical expression that describes the operation of a physical or artificial system using empirically observed variables or measurements is a very common and important problem in many scientific areas. Usually, the observed data are noisy and sometimes missing. Also, it is very common, that there is no known mathematical way to express the relation using a formal mathematical way. These kinds of problems are called modeling problems, symbolic system identification problems, black box problems, or data mining problems [START_REF] Winkler | Identifying Nonlinear Model Structures Using Genetic Programming Techniques[END_REF]. Most data-driven system modeling or system identification techniques assume an apriori known model structure and focus mainly to the calculation of the model parameters' values. But what can be done when there is no a-priori knowledge about the model's structure? Gene Expression Programming (GEP) is a domain-independent problem-solving technique in which computer programs are evolved to solve, or approximately solve, problems [START_REF] Ferreira | Gene Expression Programming: A New Adaptive Algorithm for Solving Problems[END_REF], [START_REF] Ferreira | Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence[END_REF]. GEP is a member of a broad family of techniques called Evolutionary Algorithms. All these techniques are based on the Darwinian principle of reproduction and survival of the fittest and are similar to the biological genetic operations such as crossover and mutation [START_REF] Ferreira | Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence[END_REF]. GEP addresses one of the central goals of computer science, namely automatic programming; which is to create, in an automated way, a computer program that enables a computer to solve a problem [START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF].

In GEP the evolution operates on a population of computer programs of varying sizes and shapes. GEP starts with an initial population of thousands or millions of randomly generated computer programs, composed of the available programmatic ingredients and then applies the principles of biological evolution to create a new (and often improved) population of programs. The generation of this new population is done in a domain-independent way using the Darwinian principle of survival of the fittest, an analogue of the naturally-occurring genetic operation of sexual recombination (crossover), and mutation. The fundamental difference between other Evolutionary Algorithms and GEP is that, in GEP there is a distinct discrimination between the genotype and the phenotype of an individual. So, in GEP the individuals are symbolic strings of fixed length representing an organism's genome (chromosomes/genotype), but these simple entities are encoded as non-linear entities of different sizes and shapes, determining an organism's fitness (expression trees/phenotype). GEP is a new evolutionary technique and its applications so far are quiet limited. However, it has been successfully applied in some real life problems [START_REF] Lopez | EGIPSYS: An Enhanced Gene Expression Programming Approach for Symbolic Regression Problems[END_REF], [START_REF] Margny | Extracting Logical Classification Rules with Gene Expression Programming: Micro array case study[END_REF], [START_REF] Dehuri | Multi-Objective Classification Rule Mining Using Gene Expression Programming[END_REF].

In the current paper we present an integrated GEP environment with a graphical user interface (GUI), called jGEPModeling. The jGEPModeling environment was developed using the JAVA programming language, and is an implementation of the steady-state gene expression programming algorithm. In order to evaluate the performance of the jGEPModeling we tested it in the task of forecasting the next trading period of EUR/USD exchange rate based on the exchange rates of the past N periods, where N is a user-defined variable.

The Gene Expression Programming Algorithm

Gene Expression Programming is a new Evolutionary Algorithm proposed by [START_REF] Ferreira | Gene Expression Programming: A New Adaptive Algorithm for Solving Problems[END_REF] as an alternative method to overcome the drawbacks of Genetic Algorithms (GAs) and Genetic Programming (GP) [START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF], [START_REF] Ferreira | Gene Expression Programming: A New Adaptive Algorithm for Solving Problems[END_REF], [START_REF] Goldberg | Genetic Algorithms in Search, Optimization, and Machine Learning[END_REF], [START_REF] Ferreira | Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence[END_REF] . Similar to GA and GP, GEP follows the Darwinian principles of natural selection and survival of the fittest individual [START_REF]On the Origin of Species[END_REF]. The fundamental difference between the three algorithms is that, in GEP there is a distinct discrimination between the genotype and the phenotype of an individual. This difference resides in the nature of the individuals, namely in the way the individuals are represented: in GAs the individuals are symbolic strings of fixed length (chromosomes); in GP the individuals are non-linear entities of different sizes and shapes (parse trees); and in GEP the individuals are also symbolic strings of fixed length representing an organism's genome (chromosomes/genotype), but these simple entities are encoded as non-linear entities of different sizes and shapes, determining an organism's fitness (expression trees/phenotype) [START_REF] Ferreira | Gene Expression Programming: A New Adaptive Algorithm for Solving Problems[END_REF]. GEP chromosomes are usually composed of more than one gene of equal length. Each gene is composed of a head and a tail. The head contains symbols that represent both functions and terminals, whereas the tail contains only terminals. The set of functions usually includes any mathematical or Boolean function that the user believes is appropriate to solve the problem. The set of terminals is composed of the constants and the independent variables of the problem. The head length (denoted h) is chosen by the user, whereas the tail length (denoted t) is evaluated by:

1 ) 1 ( + - = h n t (1)
, where n is the number of arguments of the function with most arguments. Despite its fixed length, each gene has the potential to code for Expression Trees (ETs) of different sizes and shapes, being the simplest composed of only one node (when the first element of a gene is a terminal) and the largest composed of as many nodes as the length of the gene (when all the elements of the head are functions with maximum arity). One of the advantages of GEP is that the chromosomes will always produce valid expression trees, regardless of modification, and this means that no time needs to be spent on rejecting invalid organisms, as in case of GP [START_REF] Ferreira | Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence[END_REF]. In GEP, each gene encodes an ET. In the case of multigenic chromosomes, each gene codes for a sub-ET and the sub-ETs interact with one another using a linking function (any mathematical or Boolean function with more than one argument) in order to fully express the individual. Every gene has a coding region known as an Open Reading Frame (ORF) that, after being decoded, is expressed as an ET, representing a candidate solution for the problem. While the start point of the ORF is always the first position of the gene, the termination point does not always coincide with the last position of a gene. The flowchart of the GEP algorithm is shown in Figure 1. The process begins with the random generation of the linear chromosomes (or individuals) of the initial population. Then the chromosomes are expressed as ETs and the fitness of each individual is evaluated. After that, the individuals are selected according to their fitness in order to be modified by genetic operators and reproduce the new population. The individuals of this new population are, in their turn, subjected to the same developmental process: expression of the chromosomes, evaluation, selection according to fitness and reproduction with modification. The process is repeated for a certain number of generations or until a good solution has been found. Next, follows a full description of the algorithm's steps: 1. Creation of initial population: The initialization in GEP is a very trivial task· in fact is the random creation of the chromosomal structure of the individuals. According to the nature of the problem, we must choose the symbols used to create the chromosomes, that is, the set of functions and terminals we believe to be appropriate to solve the problem. We must also choose the length of each gene, the number of genes per chromosome and how the products of their expression interact with one another. 2. Express chromosomes: The second step is the expression of the chromosome of each individual as an ET. This process is also very simple and straightforward. For the complete expression, the rules governing the spatial distribution of functions and terminals must be followed. First, the start of a gene corresponds to the root of the ET, forming this node the first line of the ET. Second, depending on the number of arguments of each element (functions may have a different number of arguments, whereas terminals have an arity of zero), in the next line are placed as many nodes as there are arguments to the elements in the previous line. Third, from left to right, the new nodes are filled, in the same order, with the elements of the gene. This process is repeated until a line containing only terminals is formed. 3. Execute each program: Having expressed each individual to an ET is now easy to find and compute the mathematical (or Boolean) expression it codes. We implement this by a post order traversal on the ET. 4. Evaluate fitness: One crucial step in GEP is finding a function that performs well for all fitness cases within a certain error of the correct value. In the design of the fitness function, the goal must be clearly and correctly defined in order to make the system evolve in the intended direction. 5. Keep best Program: A feature that plays a significant role in GEP is the elitism. Elitism is the cloning of the best chromosome(s)/individual(s) to the next population (also called generation). By elitism, we guarantee that at least one descendant will be viable in the next generation, keeping at the same time the best trait during the process of adaptation. 6. Selection: In GEP, individuals are selected according to fitness by the tournament selection method to reproduce with modification. Tournament selection involves running several "tournaments" among a few individuals randomly chosen from the population. The winner of each tournament (the one with the best fitness) is selected for genetic modification. Selection pressure is easily adjusted by changing the tournament size. If the tournament size is larger, weak individuals have a smaller chance to be selected. 7. Reproduction: At this step of the GEP we apply the genetic operators of mutation and recombination on the winners of the tournaments.

a. Mutation: one new chromosome is created from an existing one, by mutating a single symbol. The mutation point is randomly chosen within the chromosome and then the symbol at this point is changing according to a mutation probability. In GEP, mutations can occur anywhere in the chromosome. However, the structural organization of chromosomes must be preserved. b. Recombination: the parent chromosomes are paired and split up at exactly the same point(s). The material downstream of the recombination point(s) is afterwards exchanged between the two chromosomes according to a recombination probability. In GEP, an event of recombination always involves two parent chromosomes and always results in two new individuals. Note that, during reproduction it is the chromosomes of the individuals, not the ETs that are reproduced with modification and transmitted to the next generation. 8. Prepare new programs of the next generation: At this step, we replace the tournament losers with the new individuals creating by reproduction in the population. 9. Termination criterion: We check if the termination criterion is fulfilled, if it is not we return to step 2. As a termination criterion it was used the maximum number of 500.000 generations that GEP was left to run. 10. Results: As a result we return the best individual ever found during the evolution process.

Modeling Experiments

In this section we present the performance of GEP environment in a real series forecasting problem. Particularly, we apply the GEP environment to an one-dayahead forecasting and trading task of the Euro/Dollar (EUR/USD) exchange using the Euro Central fixing series. The European Central Bank (ECB) publishes a daily fixing for selected EUR exchange rates: these reference mid-rates are based on a daily concertation procedure between central banks within and outside the European System of Central Banks, which normally takes place at 2.15 p.m. ECB time. The reference exchange rates are published both by electronic market information providers and on the ECB's website shortly after the concertation procedure has been completed. Although only a reference rate, many financial institutions are ready to trade at the EUR fixing and it is therefore possible to leave orders with a bank for business to be transacted at this level.

The ECB daily fixing of the EUR/USD is therefore a tradable level which makes using it a realistic approach. Based on the exchange rates of the past N periods, where N is a user-defined variable, we forecast the next trading period EUR/USD exchange rate. The difficulty in this modeling problem is tο identifυ and the capturε all the discontinuous, the nonlinearities and the high frequency multipolynomial components which characterize the financial series today.

After a certain number of experiments, we are in position to define standard values for some running parameters of GEP. Table 2 defines all these defaults parameters we use for our experiments. We observed that using only three past values of past exchange rates for the prediction models, gives as the best performance. Increasing the number of previous values to be used as inputs did not enhanced our models and this reveals short term phenomena in the time series of EURO/USD exchange rate. The best model found has mean square test error 6.959490069577218E-5. For comparison reasons, we experimented using our dataset with 3 other methods that have been previously used in this forecasting problem [START_REF] Dunis | Modelling and Trading the EURO/USD Exchange Rate: Do Neural Network Models Perform Better?[END_REF], [START_REF] Dunis | Modelling and trading the EUR/USD exchange rate at the ECB fixing[END_REF]. These methods are the naïve method, the moving average predictor and Artificial Neural Networks. Specifically:

• Naïve strategy assumes that the most recent period change is the best predictor of the future [START_REF] Dunis | Modelling and Trading the EURO/USD Exchange Rate: Do Neural Network Models Perform Better?[END_REF], [START_REF] Dunis | Modelling and trading the EUR/USD exchange rate at the ECB fixing[END_REF]. • Moving Average method uses a weighted average of past observations to smooth short-term fluctuations. In this approach 35 previous values were used as in [START_REF] Dunis | Modelling and Trading the EURO/USD Exchange Rate: Do Neural Network Models Perform Better?[END_REF], [START_REF] Dunis | Modelling and trading the EUR/USD exchange rate at the ECB fixing[END_REF]. • Neural models are universal approximators capable of approximating any continuous function [START_REF] Haykin | Neural Networks: A comprehensive foundation[END_REF]. In this approach we used a feed-forward Multi-Layer Perceptron(MLP) using 4 previous values as inputs in order to make a fair comparison with our method. For the neural network training we used back propagation algorithm. The performance of each model in the out of sample period is presented in Table 4.

Because of the stochastic nature of the MLP method we experimented 100 times with it and we show the mean results. We observe that gene expression programming outperforms the three classic methods in our forecasting problem.

Conclusions

The reported results taken by the application of our GEP implementation in the task of forecasting the next trading period of EUR/USD exchange rate based on the exchange rates of the past N periods, confirm our intuition that Gene Expression Programming is a very effective technique in system modeling and timeseries prediction. So, we conclude that our GEP environment can be used in a variety of problems in different scientific areas. Also, it is important to note that the rapid development of very fast computer hardware encourages the use of techniques like GEP, and is expected that these kinds of techniques will be used more and more for solving difficult problems in the future. Now, concerning some future directions of the presented GEP environment these could be:

• The application of our GEP implementation in other system modeling tasks in various scientific areas, such as system identification, timeseries prediction, e.t.c..

• The further improvement of the tool in terms of speed, memory management and parallel implementation. • The implementation of more sophisticated genetic operators, initialization techniques and selection techniques in the basic Gene Expression Programming technique. Thus, our environment has been proved to be a powerful GEP tool with great expansion capabilities that intend to perform in the near future.

Fig. 1 :

 1 Fig. 1: Flowchart of gene expression algorithm.

Table 1 .

 1 Dataset description

	Name of period Trading days	Beginning	End
	Total dataset	2721	6 January 1999	23 October 2009
	Training dataset	2178	6 January 1999	30 August 2007
	Out-of-sample	543	31 August 2007	23 October 2009
	dataset [Test set]

Table 2 .

 2 Default parameters derived by experimentation.

	Parameter		Value
	Number of Generations		300.000
	Function Set	{+, -, *, /, ^,	,abs, cos, sin, ln, exp, tan, min, max}
	Constants Range		[-3, 3]
	Mutation Probability		0.9
	Population Size		1500
	Tournament Size		4
	Head Size		30
	Type of Recombination		two points recombination
	Next, we present our experiments with various values of past exchange rates used for
	our prediction.

Table 3 .

 3 Results taken by experimenting with models from GEP which use various past exchange rates for prediction.

	Past Exchange Rates	Mean Square Train Error	Mean Square Test Error
	1	3.528493651301604e-005	7.038129152437989e-005
	2	3.525297196338534e-005	7.002301886682884e-005
	3	3.529949324406443e-005	6.967481960607426e-005
	4	3.510071391816327e-005	6.979235421769149e-005

Table 4 .

 4 Experimental results of three benchmark methods in the out of sample period.

	Method	Mean Square Test Error
	Naïve strategy	1.3475e-004
	Moving Average	7.5000e-005
	MLP	7.4551e-005


Themistoklis Chronopoulos

Isidoros Perikos

Ioannis Hatzilygeroudis

An example-tracing tutor for teaching NL to FOL conversion

Keywords: cognitive tutor, example-tracing tutor, knowledge representation tutor

In this paper we present an Example-tracing Tutor for the conversion of a sentence written in natural language (NL) to a sentence written in first order logic (FOL), which is a basic knowledge representation language. The tutor is based on the scripting of the process of the NL to FOL conversion and it has been authored using the Cognitive Tutoring Authoring Tool (CTAT) in which we have implemented a completed student interface and we also have created a Behavior Recorder graph for the above process.

Introduction

Knowledge Representation & Reasoning (KR&R) is a fundamental topic of Artificial Intelligence (AI). A basic KR language is First-Order Logic (FOL), the main representative of logic-based representation languages, which is part of almost any introductory AI course and textbook [START_REF] Russell | Artificial Intelligence: a modern approach. 2nd Edition[END_REF][START_REF] Luger | Artificial Intelligence: Structures and Strategies for Complex Problem Solving. 5th Edition[END_REF]. To make automated inferences, Clause Form (CF), a special form of FOL, is used. Teaching FOL as a knowledge representation and reasoning language includes many aspects. One of them is translating natural language (NL) sentences into FOL formulas. It is an ad-hoc process; there is no specific algorithm that can be automated within a computer. This is mainly due to the fact that NL has no clear semantics as FOL does. Also, most of existing textbooks do not pay the required attention to that. They simply provide the syntax of FOL and definitions of the logical symbols and terms [START_REF] Russell | Artificial Intelligence: a modern approach. 2nd Edition[END_REF][START_REF] Luger | Artificial Intelligence: Structures and Strategies for Complex Problem Solving. 5th Edition[END_REF]. Even more specialized textbooks do the same [START_REF] Brachman | Knowledge Representation and Reasoning[END_REF]. At best, they provide a kind of more extended explanations and examples [START_REF] Genesereth | Logical Foundations of AI[END_REF]. They do not provide any systematic guidance towards it. Given the above, students usually find difficulties in learning the task of formalizing NL sentences in FOL, which confronts to tutors' common experience.

In [START_REF] Hatzilygeroudis | Teaching NL to FOL and FOL to CL Conversions[END_REF], we introduced a structured process for guiding students in translating a NL sentence into a FOL one, namely the SIP process. In [START_REF] Hatzilygeroudis | A Web-Based Interactive System for Learning NL to FOL Conversion[END_REF], we presented a web-based system implementing the SIP process, i.e. helping students in learning how to convert NL sentences into FOL formulas. Having used the above system for some time, we resulted in the following findings: (a) At a first stage, students may not be necessary to work with sentences that produce formulas with more than three groups of atoms or with more than one group of formulas. (b) Tutors would like to use a graphical way of describing the SIP steps for each formula and a way of massively inserting them. Also, they would like related hints or feedback messages to be presented to the users in case of errors. (c) A stand-alone version of the system would be useful.

Example-tracing tutors [START_REF] Aleven | A new paradigm for intelligent tutoring systems: Example-tracing tutors[END_REF] are a recent type of tutors that perform model tracing, provide context-sensitive instruction, in the form of hints and error feedback messages, and are flexible to multiple possible solution strategies and paths. Authoring for this flexibility is based on the explicit demonstration of alternative paths in each problem. No programming is required. CTAT (Cognitive Tutor Authoring Tools) is an authoring tool for creating example-tracing tutors [START_REF] Aleven | The Cognitive Tutor Authoring Tools (CTAT): Preliminary Evaluation of Efficiency Gains[END_REF][START_REF] Koedinger | Opening the door to non-programmers: authoring intelligent tutor behavior bydemonstration[END_REF][START_REF] Koedinger | Toward a Rapid Development Environment for Cognitive Tutors[END_REF]. So, CTAT is suitable for implementing the SIP process and satisfying the above requirements.

In this paper, we present a new lighter implementation of the SIP process in the form of an example-tracing tutor.

Related Work

There various systems that are used or have been created for teaching or helping in teaching some kind of logic and logic-based reasoning. Logic Tutor [START_REF] Abraham | The Logic Tutor: A multimedia presentation[END_REF] is an intelligent tutoring system (ITS) for learning formal proofs in PL based on natural deduction. As an intelligent system, it adapts to the needs of the students via keeping user models. So, it provides context-sensitive feedback and exercises tailored to the users. Logic-ITA [START_REF] Abraham | Adaptation in the Web-Based Logic-ITA[END_REF] is actually an extension to Logic Tutor, where a tutor part has been added, used as a teaching assistant system. P-Logic Tutor [START_REF] Lukins | A tutorial program for propositional logic with human/computer interactive learning[END_REF] is also a kind of intelligent tutoring system aiming at teaching students fundamental aspects of PL and theorem proving. To this end, it provides an interactive web-based interface. All the above systems, although deal with learning and/or teaching logic, they are not concerned with how to use predicate logic as a KR&R language. They do not deal with how to formalize a NL sentence into FOL.

As far as we are aware of, there is only one system that claims doing the latter. It is called KRRT (Knowledge Representation and Reasoning Tutor) [START_REF] Alonso | KRRT: Knowledge Representation and Reasoning Tutor[END_REF]. It is a webbased system that aims at helping students to learn FOL as a KR&R language. It deals with both knowledge representation in and reasoning with FOL. The translation form NL to FOL takes place in its KR part. However, the only help provided to the students is at syntactic and logical equivalence levels. The student gives his/her FOL proposal sentence and the system checks its syntax and whether it is the correct one (here equivalent sentences are acceptable). However, it does not provide any guidance about how to make that translation or even what is the kind of error made. The system in [START_REF] Abraham | The Logic Tutor: A multimedia presentation[END_REF] does the same as the system presented here, but there are also significant differences that concern (a) the user interface, (b) the way it works internally for student interaction checking, (c) the way hints/help are/is structured and (d) the way new sentences are inserted.

A Structured and Interactive Process for NL to FOL Conversion

One problem in converting natural language into first order logic has to do with the unclear semantics that natural language has. Natural language has no clear semantics as FOL has. However, the main difficulty comes from the lack of a systematic way of making the conversion. In a previous work [START_REF] Hatzilygeroudis | Teaching NL to FOL and FOL to CL Conversions[END_REF], we introduced SIP (Structured and Interactive Process), a process that guides a student in translating/converting a NL sentence into a FOL one. SIP, which has been somewhat simplified here (to refer to simpler sentences, i.e. sentences that result in formulas with at most one group of formulas), is as follows:

1. Spot the verbs, the nouns and the adjectives in the sentence and specify the corresponding predicates or function symbols. 2. Specify the number, the types and the symbols of the arguments of the function symbols (first) and the predicates (next). 3. Specify the quantifiers of the variables. 4. Construct the atomic expressions (or atoms) corresponding to predicates. 5. Divide produced atoms in groups of the same level atoms. 6. Specify the connectives between atoms of each group and create corresponding logical formulas. 7. Form the group of formulas 8. Specify the connectives between formulas and create the next level formula. 9. Place quantifiers in the right points in the produced formula to create the final FOL formula To demonstrate the steps of the above process, we present the conversion of the NL sentence "All humans eat some food" into a FOL formula in Fig. 1.

The Cognitive Tutor Authoring Tools (CTAT)

CTAT (Cognitive Tutor Authoring Tools) is an authoring tool for building tutors. Two types of tutors can be built using CTAT: example-tracing tutors and cognitive tutors [START_REF] Aleven | A new paradigm for intelligent tutoring systems: Example-tracing tutors[END_REF][START_REF] Aleven | The Cognitive Tutor Authoring Tools (CTAT): Preliminary Evaluation of Efficiency Gains[END_REF][START_REF] Koedinger | Opening the door to non-programmers: authoring intelligent tutor behavior bydemonstration[END_REF][START_REF] Koedinger | Toward a Rapid Development Environment for Cognitive Tutors[END_REF]. The first type is based on tracing specific pre-configured examples and requires no AI programming, whereas the second type requires AI programming and is based on a cognitive model, which is rule-based. Example-tracing tutors are easy to implement, but provide less flexibility, whereas cognitive tutors is quite more difficult to build, but can be quite more flexible. In this paper, we use CTAT for building an example-tracing tutor because, (a) it is easier to build, (b) we want to systematically analyze a large number of examples to extract possible cognitive patterns for building a cognitive tutor later, (c) we want to systematically analyze various types of hints or feedback needed.

Developing an example-tracing tutor in CTAT involves the following steps: 1. Creation of the graphical user interface (GUI).

2. Demonstration of alternative correct and incorrect solutions.

3. Annotation of the solutions steps with hint and feedback messages.

CTAT offers the GUI Builder, a tool for building the user interface of the tutor in the first step. GUI builder facilitates creating an interface in a graphical away without any programming, using a "recordable widget" palette added to Java NetBeans.

Additionally, CTAT offers Behavior Recorder, a tool for building "behavior graphs", which are graphs representing alternate correct and incorrect solutions to example problems, used in the second step above. For each problem, a corresponding behavior graph is created, which demonstrates student correct and incorrect problem solving behavior. Each such graph can be annotated with hints and feedback messages, in step three. Hints concern correct links, whether feedback messages concern incorrect links. The steps on those graphs are associated with corresponding items of the user interface built in the first step.

Figure 1. Application of SIP process to "All humans eat some food"

At run time, CTAT's example-tracing engine implements the example-tracing function (or model tracing algorithm). This means that during the real-time use of the tutor, it maps the user problem solving behavior to the corresponding behavior graph and compares it with the one in the graph. Based on the results, the tutor provides either context-sensitive error feedback, when it matches an incorrect action link in the graph, or context-sensitive hints at student's request.

An Example-traced tutor for converting a sentence from NL to FOL

According to the process presented in Section 4, we first created the student interface of our system to reflect the NLtoFOL SIP process, as shown in Fig. 2

(human(x) ˄ food(y))  eats(x, y) Alternate 2 GroupForm1-1  Form1-1:
human(x) ( food(y))  eats(x, y))

Step 8. Then, we selected a number of NL sentences and for each of them we demonstrated both correct and incorrect problem-solving behavior, recorded by the Behavior Recorder, and as many behavior graphs as the sentences were created. Also, alternatives solution paths for the conversions of the same sentences, where applicable, were recorded as alternative solutions paths (see Fig. 3). These cases are used as the basis for Example-Tracing Tutors to provide guidance to students.

Feedback from the tutor

CTAT's Example-Tracing Engine uses the Behavior Graph to guide a student through a problem, comparing the student's problem-solving behavior against the graph. It provides positive feedback when the student's behavior matches steps in the graph, and negative feedback otherwise. If the student's input matches a link in the graph that was marked as an incorrect action, then any error feedback message attached to that link is presented to the student. When the student requests a hint, the hint messages attached to a link out of the current state in the graph are displayed. [START_REF] Aleven | Rapid Authoring of Intelligent Tutors for Real-World and Experimental Use[END_REF] Tracing the student's step-by-step solution enables the tutor to provide individualized instruction in the problem solving context. Prototypically our tutor provides immediate feedback on each problem solving action: recognizably correct actions are accepted and unrecognized actions are rejected.

The FOL tutor provides feedback on each problem solving action, by accepting correct actions, which is shown to the student by green color and tagging errors instead of accepting them, which is shown to the student by red color. In general any student input that is not recognized by the tutor is marked as incorrect, but by defining incorrect steps in the graph, the tutor will be able to provide a customized error feedback message for the specified input which. In each message we have included an example to demonstrate the correct use.

We focused to common errors that happen at the conversion of sentences from natural language to first order logic language, such as:

 Misuse of AND connective  The order of quantifiers  Use of function  Grouping atoms of the same level  Grouping formulas of the same level We also demonstrated the tutor cases of errors that are related to the sentence. For example in the sentence "All humans eat some food", someone can characterize the "All" as predicates. In such errors the tutor gives feedback that is related to the theory of FOL language (see Fig. 2). The example-trace tutor accepts the answer in which the student fills partially the right answer e.g. fills the right predicate but in the wrong number ("humans" instead of "human").

Annotation of Hints

There are several factors that may affect the choice of a specific hint: tutoring topic, tutoring context, tutoring history, student's answer, and so on. First, to be pedagogically useful, a hint has to be related to the tutoring topic and be useful in helping the student find the expected answer. So the tutoring topic is important. [START_REF] Zhou | Delivering Hints in a Dialogue-Based Intelligent Tutoring System[END_REF] The tutor also provides problem solving advice upon request of the student. We have implemented four levels of advice available for each problem solving action. The first level reminds or advises the student on the corresponding goal according to the SIP and a general description of how to achieve the goal. The second level provides a hint from the theoretical context of first order logic (definitions, syntactic etc) that is related to the corresponding step. The third level provides a hint specific to the case by providing a similar example. Finally, the fourth level provides concrete advice on solving the goal in the current context by suggesting the correct solution.

Knowledge labels

Once we completed the behavior graph, we added knowledge labels to links in the behavior graph, to represent the knowledge behind those problem-solving steps. This is a form of cognitive task analysis, since we determine how the overall problemsolving skill breaks down into smaller components. This process provided to us a way to copy hint messages from one step to a similar step. It also can be used by the PseudoTutor to do knowledge tracing whereby students' knowledge gaps can be assessed and the tutor can select subsequent activities to address those gaps. [START_REF] Koedinger | Opening the door to non-programmers: authoring intelligent tutor behavior bydemonstration[END_REF] We have added the following knowledge labels to links in the behavior graph: FindPredicate, FindArgument, SpecifyQuantifier, ConstructAtom, FormulateGroup, SpecifyConnective, ConstructFormula. At the same time, it is a way of planning the cognitive model, since we intend in future work, to create production rules corresponding to each identified skill. [START_REF] Koedinger | Opening the door to non-programmers: authoring intelligent tutor behavior bydemonstration[END_REF]

Conclusions

We have implemented an example-trace tutor for the conversion of sentences in NL to sentences in FOL, according to the SIP. We also have created worked-out examples of conversions for several sentences of the same level with the Behavior Recorder. The system has been preliminary used by a group of five students and the results are satisfactory. Four of them were satisfied in a large degree (>75%).

The examples can be used as the basis for Example-Tracing Tutors to provide guidance to students. The examples will also be used in future work, as planning cases and semi-automatic test cases for development of cognitive models, using the WME Editor and the Production Rule Editor, to create a production rule model.

Final formula Alternate 1 ( 2 (

 12 x) (y) (human(x) ˄ food(y))  eats(x, y)Alternate x) (y) human(x)  (food(y))  eats(x, y)) separate student interface was implemented for each step or group of steps of the process. All those student interfaces were integrated into one interface as different step tabs, through which a student can try to convert a NL sentence into a FOL formula following the NLtoFOL SIP process. Each tab, except first, corresponds to a step of the NLtoFOL SIP process. The first tab ("Atoms") corresponds to steps 1-4 of the process. In each problem solving cycle the student follows the NLtoFOL SIP process selecting one tab at a time, selecting on it the interface elements to work on and performing a problem solving action.

Figure 2 .

 2 Figure 2. Student graphical interface

Figure 3 .

 3 Figure 3. Behavior graph with two alternative conversions for the same sentence 7. Annotation of solution steps 7.1 Incorrect steps

  . Actually a

	Step 1. specify predicates/functions	GroupAtom2: {food(y), eats(x, y)}
	"humans"  predicate: human "food"  predicate: food "eat"  predícate: eats	Step 6. Connectives and formulas of groups Alternate 1
	Step 2. Number, types and symbols of	GroupAtom1  Form1: human(x) ˄
	arguments	food(y)
		GroupAtom2  Form2: eats(x, y)
	Predicate Arity Types human 1 variable x Symbols food 1 variable y eats 2 variable, variable x, y	Alternate 2 GroupAtom1  Form1: human(x) GroupAtom2  Form2: food(y)  eats(x, y)
	Step 3. Quantifiers x   y  	Step 7. Connectives and formula of last group Alternate 1 GroupForm1-1  Form1-1:
	Step 4. Atoms
	Atom 1: human(x)
	Atom 2: food(y)
	Atom 3: eats(x,y)
	Step 5. Groups of atoms of the same
	level
	Alternate 1
	GroupAtom1: {human(x), food(y)}
	GroupAtom2: {eats(x, y)}
	Alternate 2
	GroupAtom1: {human(x)}