Grymin Rados

Jagie L Lo Szymon

Fast Branch and Bound Algorithm for the Travelling Salesman Problem

Keywords: branch-and-bound, dynamic programming, parallel algorithm

New strategies are proposed for implementing algorithms based on Branch and Bound scheme. Those include two minimal spanning tree lower bound modifications, a design based on the fact that edges in the optimal tour can never cross in the euclidean TSP and parallelization of Branch and Bound scheme. Proposed approaches are compared with primary algorithms.

Introduction

Branch and bound (B&B, BnB, branch & bound) is an approach advised for designing exact algorithms solving N P-hard combinatorial optimization and discrete problems. B&B was introduced by Land and Doig in 1960 [START_REF] Land | An automatic method of solving discrete programming problems[END_REF]. Until the late 1970s, it was the state-of-the-art method for almost all big and complex problems that could not be solved by other techniques known at that time. And it is still used everywhere, where small improvement of solution leads to big rise in profits. B&B uses a tree search strategy to implicitly enumerate all possible solutions to a given problem, applying pruning rules to eliminate regions of the search space that cannot lead to a better solution [START_REF] Morrison | Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning[END_REF].

In this article we are considering a minimization problem and the whole used terminology relates to it. In order to optimally solve the problem, B&B algorithm divides the whole set of solutions X into mutually exclusive and exhaustive subsets X j , where j ∈ S = {1, 2, 3, . . . , s}. In every moment of its work, algorithm stores the best found solution so far x ub and its value called upper bound and the set of subsets not yet analysed. B&B does not search these subsets to which it is assured that they do not contain optimal solution x * , so it is much more effective than an exhaustive search. Decision, if some subset should be analysed or not, is based on its bound and objective function value counted for currently best found solution K(x ub ). For minimization problem, such bound is called lower bound and it is lower or equal to all objective function values evaluated for every element of related subset. It is marked as LB. If for a certain subset, the lower bound is equal or greater than the value of the best solution found so far, such subset is removed from the set of subsets not yet analysed and will be no more considered. A good lower bound is a basic requirement for an efficient B&B minimization procedure [START_REF] Toffolo | Branch-and-bound with decomposition-based lower bounds for the Traveling Umpire Problem[END_REF].

The idea of Travelling Salesman Problem, TSP for short, relies in visiting every city by the sale representative from the given set of n cities exactly once [START_REF] Jünger | The Traveling Salesman Problem[END_REF], starting from and returning to the home city. In this article we are considering a symmetric TSP, where the distance between two cities is the same in each opposite direction. We also assume that there is a direct connection from each node to every other one. Formally, this problem is described as a search for the shortest Hamiltonian cycle [START_REF] Feiring | An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem[END_REF] in the complete and symmetric graph

K n = (V n , E n ) containing n = |V n | nodes and m = |E n | = n 2
edges. Nodes are numbered from 1 to n. We assume without loss of generality that the home city is the node with index number 1. Edge e, which connects nodes i and j, is marked as {i, j} or {j, i} and their distances are stored in the distance matrix D n .

B&B algorithm for TSP constructs solutions by visiting cities. On each step there may be more than one remaining city to visit. The process of constructing solutions can be presented as a decision tree. Each node in such tree refers to a subset of the solution set and a lower bound can be established for it. B&B algorithm creates solutions by exploring such tree. It will not visit these nodes of the decision tree, for which it has certainty that it will not lead to the optimal solution.

The role of parallel algorithms in solving NP-hard problems significantly increased in the last decade. Bożejko proposed an improvement for speeding up the process of solving a single machine scheduling problem with total tardiness cost function by parallelization of generation of paths [START_REF] Bożejko | Parallel path relinking method for the single machine total weighted tardiness problem with sequence-dependent setups[END_REF], a parallel genetic algorithm for the flow shop scheduling problem [START_REF] Bożejko | Parallel genetic algorithm for the flow shop scheduling problem[END_REF] and a method for solving permutational routing problems by population-based metaheuristics [START_REF] Bożejko | Solving permutational routing problems by populationbased metaheuristics[END_REF]. The same author designed new parallel objective function determination methods for the job shop scheduling [START_REF] Bożejko | On single-walk parallelization of the job shop problem solving algorithms[END_REF] and flow shop [START_REF] Bożejko | Solving the flow shop problem by parallel programming[END_REF] problems. Jagie l lo and Żelazny proposed a parallel cost function approach for the Distance Constrained Vehicle Routing Problem which was designed to work on Graphics Processing Units (GPUs) [START_REF] Jagie L Lo | Solving multi-criteria vehicle routing problem by parallel tabu search on gpu[END_REF].

In this paper we propose a parallel B&B design for the TSP problem.

Lower bounds

The lower bound LB(X j ) for a given node in the decision tree (that reflects to a certain set of solutions X j ) is evaluated as a sum of the travelled distance M IL(X j ) and the lower estimation of the remaining distance LE(X j ),

LB(X j ) = M IL(X j ) + LE(X j ). ( 1
)
It should be noted, when the travelling salesman visited k cities, the remaining way is a Hamiltonian path starting from the last visited city, that visits every city not visited so far and returning to the home city. It is showed in Figure 1.

The lower estimation estimates from the bottom an overall length of such shortest Hamiltonian path. This path is described by the following properties: current position of the travelling salesman c) there exists a subpath linking every two nodes of the considered graph, d) it assumes beginning and ending node, e) if the number of not visited cities is greater than one and travelling salesman is not currently in the home city, he cannot directly pass the way from the current city to some not visited city and immediately return to the home city, f) it is built from n -k + 1 edges, g) the first and the last city of the Hamiltonian path are connected with only one city.

By the relaxation of above constraints, we get lower estimation of the remaining distance LE(X j ). The weaker relaxation, the greater value of the lower estimation and it leads to better lower estimation (that rejects more solutions).

The total length of the shortest feasible connections The weakest and the most simple lower estimation LE of the remaining distance is obtained by counting the total length of the shortest not visited edges. It satisfies the constraints (a) and (b). Relaxation of constraints involves removal of constraints (b), (c), (d), (e), (f) and (g).

In order to evaluate the lower estimation, the distances associated with the inaccessible connections are removed from the weight matrix. Firstly, zeros from the main diagonal are removed. If the travelling salesman comes out from the city i, the numbers in the row with index i should be removed from the weight matrix. Afterwards, if travelling salesman enters the city with index j and it is not a home city, then from the weight matrix, values from the column j are removed. Moreover, if city with index j is not a second last one (such city, after which travelling salesman returns to the home city), value d j1 must be removed from the weight matrix. We determine the number of the remaining connections r that have to be passed as

r = n -k + 1, ( 2
)
where n is the number of all cities and k is the number of visited cities. Values that were not removed from the weight matrix are sorted in the nondecreasing order and form a finite sequence (a n ). The sum of the first r values is the lower estimation of the remaining distance. Then, the lower bound can be computed from [START_REF] Bożejko | Solving the flow shop problem by parallel programming[END_REF].

The weight of the minimum spanning tree In this case, the lower estimation of the remaining distance LE and the lower bound is equal to the weight of the minimum spanning tree for the complete sub-graph that consists of the city where actually the travelling salesman is located x k , not having visited cities so far {x k+1 , x k+2 , x k+3 , . . . , x n } and the home city x 1 = 1. It satisfies the constraints (a), (c) and (f). Relaxation involves removal of the constraints (b), (d), (e) and (g). In order to evaluate the minimum spanning tree weight, Prim's algorithm is used. When the weight of the minimum spanning tree is computed (and it is also a value of the lower estimation LE ), (1) will be used to determine the lower bound.

The weight of the minimum spanning tree -1st modification Algorithm was proposed by Mariusz Makuchowski from Department of Control Systems and Mechatronics of Wroc law University of Science and Technology (personal communication, November 3, 2014). The lower estimation of the remaining distance is evaluated as a sum of minimum spanning tree weight for graph consisting of the cities not having been visited so far {x k+1 , x k+2 , x k+3 , . . . , x n } and the home city x 1 = 1 and the sum of weights of two shortest edges connecting the home city with nearest not visited edge and the current city with nearest not visited edge. If travelling salesman is currently in the home city, lower estimation is counted as a sum of the weight of minimal spanning tree in the graph containing not visited cities and doubled distance from the home city to the nearest not visited node. It satisfies the constraints (a), (c), (f) and (g). Relaxation involves removal of the constraints (b), (d) and (e).

The weight of the minimum spanning tree -2nd modification It is the improved version of the previous algorithm. The lower estimation of the remaining distance is evaluated as a sum of minimum spanning tree weight for graph consisting of not visited cities {x k+1 , x k+2 , x k+3 , . . . , x n } and the sum of two weights of edges connecting the home city and the current city with not visited cities (and these cities must be different). If the travelling salesman is currently in the home city, the lower estimation is a sum of weight of the minimum spanning tree in graph containing not visited cities and the sum of two weights of shortest edges connecting home city with different not visited cities so far. It satisfies constraints (a), (c), (e), (f) and (g). Relaxation involves removal of constraints (b) and (d).

The order in which the algorithm searches the decision tree is very important. The size of the priority queue will grow fast if leaves are rarely visited and new upper bounds will not be found. The algorithm must have a tendency to search the graph towards leaves. By assigning a priority to sets stored in the priority queue we control the way the algorithm will search the decision tree.

We chose the following way of counting priority that promotes subsets with the lowest increase of lower bound

P = 1 AI , (3)
AI = LB k . ( 4
)
where P , AI, LB and k denote the subsets priority in the queue, the mean increase of the lower bound, the lower bound and the number of visited cities accordingly.

Parallel Branch and Bound Algorithm

In the parallel algorithm we use a pool approach with arbitrary fixed number of processes. It means that program executes in several processes and one of them will be called supervisory process and the rest will be called worker processes (see Figure 2). In the initialization phase, supervisory process reads the instance data from the TSPLIB file, generates the weight matrix and distributes it to all worker processes. It also establishes the best solution found so far and the upper bound by running 2-opt algorithm on the result of the nearest neighbour algorithm. It stores the priority queue of solution sets not analysed so far and the best solution so far.

During computation phase, if some worker process notifies the supervisory process about its idle state via WORKER FINISHED TASK message and if there are still some solutions sets to be analysed in the priority queue, the supervisory process pops the first solution set with the highest priority and sends it to the worker process via PERFORM TASK REQ message and stores the information that the process is performing task. Algorithm stops when there are no more sets in the priority queue to analyse and if all worker processes informed supervisory process that they finished analysing task by sending WORKER FINISHED TASK.

Each worker process stores the upper bound value. If some worker process found a solution with the objective function value smaller than the upper bound, it sends this solution with upper bound update proposal to the supervisory process in UPPER BOUND message. The supervisory process checks if the proposed upper bound value is better than the currently stored one. If it is true, the new best solution so far and the new upper bound value are stored in the supervisory process, the new upper bound value is distributed to all worker processes in the UPPER BOUND message except one which found it and all subsets with the lower bound greater than the new upper bound are removed from the priority queue. Otherwise, the new proposed upper bound value is discarded. Such check is important in a situation when two workers find better solutions (with different objective function values) than the best solution found so far and simultaneously send proposal to the supervisory process for changing the best solution found so far and the upper bound. If the supervisory process obtains upper bound with smaller value first, it will update upper bound and when it obtains one with greater value, second upper bound value change proposal will be discarded after the check.

Worker processes divide set obtained in the PERFORM TASK REQ message into subsets. If the subset has only one element it means that the worker found a solution. Otherwise, if obtained subsets contains more than one element, it calculates lower bounds for them. On the basis of the lower bound and the upper bound it is established if the optimal solution can belong to the obtained subset. If it is true, the subset is send back to the supervisory process via TASK PUSH REQ.

Intersections in Euclidean TSP

The edges in an optimal tour can never cross in an euclidean TSP. If edges {i, k} and {j, l} did cross, they would constitute the diagonals of a quadrilateral {i, j, k, l} and could profitably be replaced by a pair of opposite sides [START_REF] Cook | Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation[END_REF]. Instances for which all points are located on the same line are the only exceptions. Based on that fact two algorithms were proposed. The first one is a modification of the Brute force method the second is an adjustment of the Branch and Bound (Branch and Cut) approach. Before adding an edge to the current subtour it is probed for crossings with any of the edges of the current sub-tour. If an intersection occurs, the edge will not be added, thus the whole branch will be omitted.

Computational experiments

The experiments were performed on a machine equipped with an Intel X980 CPU (6 physical cores), 24GB of ram, gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) and mpich 1.4.1 (mpic++, mpirun). The execution time of the specified approaches was measured. The sequential algorithms put under test were:

-Branch and Bound (Branch and Cut) with four different lower bound approaches and without and with intersection checking:

• the shortest feasible connections (BB(sfc), BB(sfc,i)),

• the minimum spanning tree (BB(mst), BB(mst,i)),

• the minimum spanning tree -1st modification (BB(mstm), BB(mstm,i)),

• the minimum spanning tree -2st modification (BB(mstg), BB(mstg,i)). -Bellman-Held-Karp dynamic algorithm (Bellman), -Brute force without and with intersections checking (BF, BF(i)).

For the reason that the algorithms were compared with Brute force method only small problem instances were used. TSPLIB contained only two benchmarks, which fulfilled this requirement: burma14 and ulysses16. The results obtained from working with those data sets are presented in Table 1.

It is quite interesting that the dynamic programming design performed so well as it performed best out of all algorithms for the ulysses16 data set. A single case is unfortunately not enough for accurate conclusions. Due to the small number of available benchmarks 7 random instances of sizes from 10 to 17 were generated. Function rand (stdlib) initialized with the seed 734834 was used to obtain x,y values from the range from 0 to 100. The results were presented in Table 2 and in Figure 3.

The BF method was not tested against the rand17 instance for the reason that the experiment would take too long (estimated 22 days). The results clearly indicate that the BF and BB algorithms benefit from checking intersections. The modified BB method was vastly faster than its basic version for each lower estimation. Even BF(i) method has been proved to be working faster than the BB(sfc) algorithm. Both mst lower bound adjustments (1-Makuchowski, 2-Grymin) proved to be superior compared to the standard approach. As expected the dynamic programming technique operated faster than BB(sfc), BB(sfc,i), BF and BB(i) but slower than mst based BB designs (rand10 is the only exception). The BB(mstg,i) method turned out to be the leading solution resulting in shortest execution times for each test instance. Instance size dependent speedup obtained in comparison to the BF, Bellman and BB(mst) algorithms is presented in Figure 4. Parallel version of the leading approach was tested with the number of mpi processes in the range 2-12 and with the burma14 benchmark. The results were presented in Table 3. It is shown that the mpi implementation utilizes all physical cores. Speedup is rising until the number of mpi processes equals 7 (1 supervisory process and 6 worker processes). MPI processes count dependent speedup calculated in comparison to the sequential versions of the BF, Bellman and BB(mst) algorithms is presented in Figure 5. The maximum obtained speedup in comparison to the selected approaches is 38.318, 20.545 and 22755.273 accordingly. Both proposed minimal spanning tree modifications proved to perform greatly faster than the base version. The intersections checking approach was successfully combined with Branch And Bound and Brute force designs and provided additional improvements. The Branch and Bound used with 2nd minimum spanning tree modification as lower estimation algorithm and combined with intersections checking mechanism turned out to be the best solution and achieved a massive speedup when compared to the Brute Force, Bellman, and Branch and Bound used with standard minimal spanning tree algorithms. Additionally, its parallel version appeared to scale well and provided a further rise in performance.

1 Fig. 1 .

 11 Fig. 1. Searched Hamiltonian cycle. The tour that has to be passed is marked by the dashed line.

Fig. 2 .

 2 Fig. 2. Sequence diagram that describes solving TSP by the parallel Branch and Bound algorithm. The initialization part of algorithm was omitted.

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Execution time for random data (log10 scale)

Table 1 .

 1 Execution time for selected benchmarks

			Time[s]
	Instance BB(sfc) BB(sfc,i) BB(mst) BB(mst,i)
	burma14	21.5	5.4	0.8	0.4
	ulysses16 125930.3	4703.4	375.9	54.2
			Time[s]
	Instance BB(mstm) BB(mstm,i) BB(mstg) BB(mstg,i)
	burma14	0.3	0.2		0.3	0.2
	ulysses16	138.8	26.9	117.2	23.3
			Time[s]
		Instance Bellman	BF BF(i)
		burma14	0.5	500.6	18.6
		ulysses16	7.9 109855.2 423.3

Table 2 .

 2 Execution time for random data

						Time[s]
	Instance BB(sfc) BB(sfc,i) BB(mst) BB(mst,i)
	rand10		40		22	4		4
	rand11		98		48	6		5
	rand12		502		200	19		25
	rand13		4730		1181	90		72
	rand14		32429		6933	206		126
	rand15	123877	25805	438		272
	rand16	450761	107754	1197		734
	rand17	2224033	467889	2693		1266
						Time[s]
	Instance BB(mstm) BB(mstm,i) BB(mstg) BB(mstg,i)
	rand10			1		1		1		1
	rand11			3		2		3		2
	rand12			6		4		6		4
	rand13			31		24		30		23
	rand14			82		53		74		46
	rand15			272		191		238		159
	rand16			348		206		371		202
	rand17			791		454		814		374
						Time[s]
		Instance Bellman	BF	BF(i)
		rand10		2		26	11
		rand11		7	270	55
		rand12		27	3050	313
		rand13		109	40627	1840
		rand14		456	516886	8200
		rand15		1895	7363261	49481
		rand16		7912 111510649 308037
		rand17		33052 -----1642004
						Time[s]
	Instance	2	3	4	5	6	7	8	9	10	11	12
	burma14 0.066 0.045 0.034 0.026 0.023 0.022 0.022 0.030 0.040 0.049 0.079

Table 3 .

 3 Parallel BB(mstg,i)

	10^9
	10^8
	10^7
	10^6
	10^5
	Time[s]
	10^4
	10^3
	10^2
	10^1
	10^0
	10	11	12	13	14	15	16	17
				Instance size
		BB(sfc)		BB(mstm)		Bellman
		BB(sfc,i)		BB(mstm,i)		BF(i)
		BB(mst)		BB(mstg)		BF
		BB(mst,i)		BB(mstg,i)


Yingjie Song

Rong Chen

Non-Standard Reasoning Services for the Verification of DAML+OIL Ontologies

Keywords: Ontology Reasoning, DAML+OIL, Alloy, Semantic Web

Ontology has a pivot role in the development of Semantic Web which provides the understanding of various domains that can be communicated between people and applications. Motivated by J. S. Dong's work, we propose a new approach to interpreting DAML+OIL in a lightweight modeling language for software design, Alloy, which is used to provide a nonstandard reasoning service for the verification of DAML+OIL ontologies. To do so, Jena is first used to parse ontology documents into classes, properties and statements, next we use algorithms to translate them into Alloy model, the Alloy Analyzer is then used to check and reason about such model. The experiments show that our method greatly improves J. S. Dong's work, and distinguishes from the traditional ontology reasoners in property checking and reasoning.

Introduction

A Semantic Web [START_REF] Hendler | The semantic web[END_REF], as the next generation of the Web, provides well-defined notations and techniques for humans and applications to quickly and accurately access Web information and services. In the development of Semantic Web there is a pivot role of ontology, since ontology languages provide modeling primitives for converting notations in nature language into machine-readable logical formulas, from which autonomous software agents may infer and come to conclusions [START_REF] Wang | Checking and reasoning about semantic web through alloy[END_REF].

Ontology languages, such as DAML+OIL, enhance computer programs through structured organizational information and rules, with which it is able to understand the logical relationship between them. Ontology reasoning is crucial in that inconsistent ontology cannot be shared or used by autonomous software agents. A number of ontology inference engines, such as FaCT [START_REF] Horrocks | The fact system[END_REF], RACER [START_REF] Haarslev | RACER User's Guide and Reference Manaual: Version 1[END_REF], and FaCT++ [START_REF] Tsarkov | Fact++ description logic reasoner: System description[END_REF] have been developed with the advancement of ontology languages to facilitate ontology creation, management, verification, merging, etc.. However, the checking and reasoning of complex ontology-related properties cannot be done by them.

There is a role for software engineering techniques and tools that contribute to the Semantic Web development. J. S. Dong first proposes the use of Alloy [START_REF] Jackson | Alloy: a lightweight object modelling notation[END_REF] in checking and reasoning about the semantic relationship between web resources [START_REF] Wang | Checking and reasoning about semantic web through alloy[END_REF]. We propose a novel transformation from DAML+OIL ontology to Alloy, which greatly improves J. S. Dong's work; our approach scales up well and can work on a larger scope of property checking.

The rest of the paper is organized as follows: Section 2 gives a brief introduction to DAML+OIL and Alloy. In the section 3, a simple ontology example is given described in DAML+OIL, and then the ontology document is analyzed by jena, the results of which will be used as the inputs of the algorithms, which are used to transferred the DAML+OIL into Alloy model.

2

Overview of DAML+OIL and Alloy

Logical Characteristic of DAML+OIL

DAML+OIL [START_REF] Horrocks | Reviewing the design of daml+oil: an ontology language for the semantic web[END_REF] is a successor language to DAML [START_REF]Reference description of the daml+oil ontology markup language[END_REF] and OIL [START_REF] Broekstra | Adding formal semantics to the web building on top of rdf schema[END_REF] that builds on earlier W3C standards such as RDF, RDF Schema, and the language components of OIL. DAML+OIL layered on top of RDFS it inherited RDFS ontological primitives (subclass, range, domain). As a semantic Web ontology language, DAML+OIL provides users a richer set of modelling primitives (transitivity, cardinality, …) that are commonly found in frame-based languages.

Although DAML+OIL is tightly integrated with RDFS, which provides the only specification of the language and its only serialization, DAML+OIL defines the semantic of the language to give a meaning to any ontologies that conform to the RDFS specification, including "strange" constructs such as slot constraints with multiple slots and classes. It contains richer modeling primitives than RDF. This is made easier by the fact that the semantics of DAML+OIL is directly defined in both a model-theoretic and an axiomatic form. Theoretically, DAML+OIL is undecidable, but its processor to detect the occurrence of constraints and warn the user of the consequences.

Alloy

Alloy [START_REF] Jackson | Alloy: a lightweight object modelling notation[END_REF] is a textual, declarative modelling language rooted in first order relational logic, which is widely accepted as micromodels of software in the software engineering community. For relationships between web resources are focus point in the Semantic Web, we believe that it will be a new application domain for Alloy. An Alloy model consists of Signatures, Relations, Facts, Functions and Predicates. Signatures represent the entities of a system and Relations are used to describe relations between such entities. Facts and Predicates introduce constraints over such Signatures and Relations. Whereas Facts are constraints to be always valid, Predicates are named parameterized contraints for depicting operations, Functions are named expression with parameters that return results.

Alloy comes with a tool, the Alloy Analyzer [START_REF] Jackson | Alcoa: the alloy constraint analyzer[END_REF], which supports fully automated analysis of Alloy models through simulation and Assertion checking. While Assertions are assumptions about the model that can be checked. Simulation yields a random instance that is consistent with the model. Given a user specified scope on the model elements bounding the domain, the analyzer first translates an Alloy model into boolean formulas, and then invokes a SAT-solver to find an instance. If an instance that violates the assertion is found within the scope, the assertion is not valid and the instance is returned as a counterexample.

The specific process of our approach on ontology reasoning is shown in Fig. 1: ontology documents are analyzed by Jena, and the results contain three parts: Classes C, Property P and Statements S. Next, the results are converted into Alloy model using daml2Alloy algorithm. And then we use Alloy Analyzer to check the model. In case an error, we check back the original ontology and correct it accordingly. The jena is used again to check the corrected ontology. These three steps are explained in more detail in the following.

Parsing DAML+OIL Documents

To handle DAML+OIL ontologies, we adopt Jena [START_REF] Tsarkov | Fact++ description logic reasoner: System description[END_REF] as a frontend of our framework to parse textual DAML+OIL documents. Jena provides APIs for maniplulating RDF graphs, abstracting from which it provides the ontology API for OWL and DAML ontologies. Our DAML+OIL parser, based on Jena parser, reads a DAML+OIL document of animal ontology (shown in Fig. 2), which defined four classes: Animal, Male, Man and Female. While Man is subclass of Male, Male and Female are disjointed subclasses of Animal. hasFather, hasParent and hasChild are three properties such that hasParent and hasChild are inverse to each other and hasFather is subproperty of hasParent. We translate it into RDF triples, which are composed of Classes, Properties and Statements. </rdfs:comment> </rdfs:Class> <rdfs:Class rdf:about="Male"> <rdfs:subClassOf rdf:resource="Animal"/> </rdfs:Class> <rdfs:Class rdf:about="Female"> <rdfs:subClassOf rdf:resource="Animal"/> <daml:disjointWith rdf:resource="Male"/> </rdfs:Class> <rdfs:Class rdf:about="Man"> <rdfs:subClassOf rdf:resource="Male"/> </rdfs:Class> …… <rdf:Property rdf:about=" hasParent"> <rdfs:domain rdf:resource=" Animal"/> <rdfs:range rdf:resource=" Animal"/> </rdf:Property> <rdf:Property rdf:about=" hasFather"> <rdfs:subPropertyOf rdf:resource=" hasParent"/> <rdfs:range rdf:resource=" Male"/> </rdf:Property> <rdf:Property rdf:about=" hasChild"> <daml:inverseOf rdf:resource=" hasParent"/> </rdf:Property> ……

We use a simple ontology about animal as a running example to show the outputs of Jena. It contains a sequence of Classes, Properties and Statements, each having a couterpart in the original document. Such Classes, Properties and Statements provide programmatic objects like DAMLClass, DAMLProperty and RDFTriples for our coversion algorithm in the next section. As illustrated in Fig. 1, our DAML+OIL parser reads such a textual document and converts it into RFD triples as follows:

  ;

2.

FOR each cC 3.

   + 2Alloy(c, S);

4.

FOR each sS 5.

IF s.predicate.name = "disjointWith" 6.

IF s.subject.subClassOf  s.object.subClassOf 7.

   + "pred {no c1:" + s.subjec.name +", c 2 :" + s.object.name +" | c 1 = c 2 }"; 8.

IF s.predicate.name ="complementOf" 9.

   + "pred {" + s.subject.name +"=" + C -s.object.name +"}"; 10. sS contains RDF elements in the form of a RDF triple <subject, predicate, object>, we use s.subject, s.predicate, s.object to denote the three RDF elements respectively. Moreover, we further use e.name (e.subClassOf) to represent the name of a RDF element e (its parent's class) in that each RDF triple depicts the relationship between RDF elements. For instance, when it comes to two disjointed classes on lines 5~6, we should further consider whether they have the same parent class, if not, a new Alloy predicate is generated for depicting such a constraint 1 . Lines 8~9 handle a new case like lines 5~6, more generation on lines 10~11 is summarized in cases in Table 3, where a specific textual Alloy predicate is generated when some condition holds. The next algorithm 2Alloy (c, S) is used to produce a signature for a class c with respect to a set S of Statements. The idea behind this conversion is as follows: let c be the input class, we first create an Alloy signature named as c.name on line 1. If c has parent class, i.e., c.subClassOf is not empty by checking the input Statements, we think c extends its parent class c.subClassOf.name on line 3. When it comes to a property on line 5, its domain and range is calculated before appending the resulting signature  on line 7.

IF s.predicate meets one of Conditions in

As shown in Algorithm 3, the domain of a property is calculated recursively; the domain is associated with an object on line 2 when a RDF triple satisfies such a condition that its subject is a property and its predicate depicts a domain. Otherwise, the parent property is recursively checked until a qualified RDF triple is reached. We    + "extends" + 1.

   + "{";

2.

FOR each pP 3.

IF domain(p, S) = c.name 4.

   + p.name + " : " + range(p, S);

5.

   + " }"; 6.

RETURN ; use parent (property) to represent the parent property of the parameter property. Note that the calculation of the range of a property with respect to Statements is quite similar to Algorithm 3, we omit it for obviousness.

Taking the "Animal" ontology as an example again, it is used to show how the conversion is achieved. The DAML+OIL document will be transferred into Alloy model as Fig. 4.

Verifying Ontologies with the Alloy Analyzer

Semantic Web reasoning is one of key issues for ontology design, construction and maintenance, which contains the ontology consistency checking, subsumption reasoning, which task is to derive a class is another's parent, and implication relation checking. The correct ontology required to meet at least on instance. This is achieved through Alloy Analyzer to generate an instance of the model in given scope. As shown in Figure 5, there is an inconsistency occurred in the "Animal" model. This is because there is a subProperty constraint between femalHasFather and animalHasFather, Woman is subClassOf Male is implied since Male is the range of animalHasFather and Woman is the range of femaleHasFather.

Conclusion

We propose an approach to convert the DAML+OIL ontology to Alloy model, and then using the Alloy Analyzer to automatically check and reason the generated model. First, we use Jena to analyze the ontology document and get classes, properties and statements of it. Next, we propose two algorithms to generate the Alloy model of the ontology. Finally, the tasks of checking and reasoning are executed by Alloy Analyzer. We have applied our approach to several ontologies, it can discover errors and inconsistencies, and when there are something wrong, we can efficiently correct the errors on the assistance of the counterexample given by Alloy Analyzer.

Fig. 1 .

 1 Fig.1. The specific process of ontology reasoning.

Fig. 2 .

 2 Fig.2. A DAML+OIL document of animal ontology

Fig. 3 .

 3 Fig. 3. Jena outputs of "Animal" ontology

1

  No constraint is generated when two disjointed classes have the same parent, because Alloy 4.0 defaultly assumes classes are disjointed.

Algorithm 2 :Output: a signature  7 . 8 .

 278 2Alloy (c, S) Input: a Class c, a set S of Statements   "sig " + c.name; IF c.subClassOf  9.

Fig. 4 .

 4 Fig. 4. The generated Alloy model of "Animal" ontology

Fig. 5 .

 5 Fig.5. Checking result of Alloy Analyzer

Table 3

 3

	11. 12.	the corresponding generated Alloy predicate is appended to  RETURN ;

Table 3 More cases for converting statements to Alloy

 3

	Case Condition	Alloy predicates generated
	1	s.predicate.name="subPropertyOf"	"pred subPropertyOf{all r:"+ s.subject.range +"| r in "+ s.object.range +"}"
	2	s.predicate.name="samePropertyAs"	"pred samePropertyAs{"+s.subject+ "=" +s.object+"}"
	3	s.predicate.name="inverseOf"	"pred inverseOf{"+s.subject+"="+s.object+"}"
		s.predicate.name="TansitiveProperty"	"pred TansitivePropertyOf { a,b,c " +s.subject+" a.( "+s.predicate+") = b
	4		&& b.( "+s.predicate+") =c  a. ("+ s.predicate+" ) =
			c}"
	5	s.predicate.name="UniqueProperty"	"pred UniqueProperty{#("+s.predicate.range+")=1}"
	6	s.in
			("+s.predicate.range+")}"
	14	s.predicate.name=cardinalityQ	"pred cardinalityQ{#("+s.predicate.range+")="+s.object+"}"
	15	s.predicate.name=maxCardinalityQ	"pred maxCardinalityQ{#("+s.predicate.range+")<="+ s.object+" }"
	16	s.predicate.name=minCardinalityQ	"pred minCardinalityQ{#("+s.predicate.range+")>="+s.object "}"

predicate.name="UnambiguousProperty" "pred UnambiguousProperty { # ("+ s.predicate.domain +") =1 }" 7 s.predicate.name="toClass" "pred toClass{all (("+s.predicate.domain +").("+s.predicate+")) in ("+s.predicate.range+")}" 8 s.predicate.name=hasClass "pred hasClass{ some((" + s.predicate.domain +").("+s.predicate+")) in ("+s.predicate.range+")}" 9 s.predicate.name=hasValue "pred hasValue{#("+s.predicate.range+")=1}" 10 s.predicate.name=cardinality "pred cardinality{#("+s.predicate.range+")=" + s.object"}" 11 s.predicate.name=maxCardinality "pred maxCardinality{#("+s.predicate.range+")<= "+s.object "}" 12 s.predicate.name=minCardinality "pred minCardinality{#("+ s.predicate.range+")>="+s.object "}" 13 s.predicate.name=hasClassQ "pred hasClassQ{ some(("+s.predicate.domain+").("+s.predicate+"))

  Algorithm 3: domain (p, S) Input: A property p of P, Statement S Output: the domain of p 5. IF sS, s.subject = p and s.predicate = "domain"

	1.	p.domain = s.object.name;
	2.	ELSE
	3.	p.domain = domain(parent(p), S);
	4.	RETURN p.domain;
	sig Animal{
	hasParent:Animal,	hasParent	Animal	hasChild
	hasFather:Male,
	hasChild:Animal
	}	hasFather
	sig Female extends Animal{} sig Male extends Animal{}	Male		Female
	sig Man extends Male{}
	pred inverseOf{hasParent=~hasChild}
	pred subPropertyOf{all	Man
	a:Animal|a.hasFather in a.hasParent}

6 Acknowledgments This work is supported by National Natural Science Foundation of China (60775028), the Major Projects of Technology Bureau of Dalian No.2007A14GXD42, and IT Industry Development of Jilin Province.

Note that if Alloy Analyzer can't find a solution, it maybe for the too small scope. If there is something of inconsistent in reasoning with Alloy, assertion is an important criterion. When Alloy Analyzer can't find a counterexample, the assertion is reasonable, else Alloy Analyzer will generate a counterexample and some predicates and facts should be added to improve the model.

Comparison of Experimental Results

In J. S. Dong's article, classes and properties in semantic ontology were converted to subclasses of resource, and then predicates were used to establish the relationship between different resources. As a proof tool of program correctness, theorem machine prove and knowledge representation, the shortcoming of first order logic is that in reasoning it prone to "combinatorial explosion". Method we used is to make use of the characteristics of Alloy, we convert the properties of the semantic ontology to the properties of the signature in Alloy model. It has been greatly improved in the scale. Table 4 shows the operation results in the case of the same scope of the two methods. As is shown in Table 4, we analyze and compare with several ontologies. Variables, primary variables, clauses and runtime are the four mainly elements for comparison. For each ontologies, we give four scopes to illustrate that with the expansion of the scope, our approach reflects the increasingly better performance comparing to the method of article [START_REF] Wang | Checking and reasoning about semantic web through alloy[END_REF].

The first ontology we used is the Family ontology, which contains three classes and five properties. Its Alloy model is composed of three signatures, five properties and one predicate. As is shown in Table 4, with the scope increasing, the advantages are more and more obvious. When the scope is equal to 40, the number of variables is 10 times larger than ours, the number of primary variables is more than 8 times and the runtime is 25 times. It is the similar with the other examples.


Manolis Maragoudakis

Dimitrios Serpanos
email: serpanos@ece.upatras.gr

Towards Stock Market Data Mining using Enriched Random Forests from Textual Resources and Technical Indicators

Keywords: Stock return forecasting, Data mining, Expert systems, Random forests, Markov blanket, Trading strategies

The present paper deals with a special Random Forest Data Mining technique, designed to alleviate the significant issue of high dimensionality in volatile and complex domains, such as stock market prediction. Since it has been widely acceptable that media affect the behavior of investors, information from both technical analysis as well as textual data from various on-line financial news resources are considered. Different experiments are carried out to evaluate different aspects of the problem, returning satisfactory results. The results show that the trading strategies guided by the proposed data mining approach generate higher profits than the buy-and-hold strategy, as well as those guided by the level-estimation based forecasts of standard linear regression models and other machine learning classifiers such as Support Vector Machines, ordinary Random Forests and Neural Networks.

Introduction

Stock market prediction has always gained certain attention from researchers. There is a controversy as regards to whether there is a method for accurate prediction of stock market movement, mainly due to the fact that modeling market dynamics is a complex and volatile domain. Stock market research encapsulates two main philosophical attitudes, i.e. fundamental and technical approaches [START_REF]The Trader' s Glossary of Technical Terms and Topics[END_REF]. The former states that stock market movement of prices derives from a security's relative data. Fundamentalists are of the belief that numeric information such as earnings, ratios, and management effectiveness could determine future forecasts. In technical analysis, it is believed that market timing is the key. Technicians utilize charts and modeling techniques to identify trends in price and volume. These latter individuals rely on historical data in order to predict future outcomes. However, according to several researchers, the goal is not to question the predictability of financial time series but to discover a good model that is capable of describing the dynamics of stock market.

There is a plethora of proposed methods in stock market prediction. The majority of them are strongly related to structured, numerical databases and domain expertise rules. In the field of trading, most of decision support tools focus on statistical analysis of past price records. Nevertheless, throughout recent studies, prediction is also based on textual data, based on the rational assumption that the course of a stock price can be influenced by news articles, ranging from companies releases and local politics to news of superpower economy [START_REF] Ng | Mining Frequent Episodes for Relating Financial Events and Stock Trends[END_REF].

However, unrestricted access to news information was not possible until the early 1990's. Nowadays, news are easily accessible, access to important data such as inside company information is relatively cheap and estimations emerge from a vast pool of economists, statisticians, journalists, etc., through the World Wide Web. Despite the large amount of data, advances in Natural Language Processing and Knowledge Discovery from Data (also known as Data Mining) allow for effective computerized representation of unstructured document collections, analysis for pattern extraction and discovery of relationships between document terms and time-stamped data streams of stock market quotes.

Nevertheless, when data tend to grow both in number of records and features, numerous mining algorithms face significant complications, resulting in poor prediction ability. The aim of this study is to propose a potential solution to the problem, by considering the well-known algorithm of Random Forests [START_REF] Breiman | Random forests[END_REF] and altering their construction phase by utilizing a Markov Blanket approach which discards irrelevant features, thus improving classification results. The importance of this study lies to the fact that technical analysis contains the event and not the cause of the change, while textual data may interpret that cause. Certainly, as it is tedious for a human investor to read all daily news concerning a company and other financial information, a prediction system that could analyze such textual resources and find relationships with price movement at future time windows is beneficial.

The paper is structured as follows: section 2 provides an overview of literature concerning Stock Market prediction using Data Mining techniques. Section 3 describes the proposed Markov Blanket Random Forest utilization. Section 4 provides an overview of our experimental design and discusses the evaluation outcome.

Previous Work

Due to numerous studies in traditional technical analysis, we shall emphasize on researches that study the influence of news articles on stock markets. Chang et al., [START_REF] Chung | Evolutionary Time Series Segmentation for Stock Data Mining[END_REF] were among the first to confirm the reaction of the market to news article. They had shown that economic news always has a positive or negative effect in the number of traded stock. They used salient political and economic news as proxy for public information. Klibannof et al., [START_REF] Klibanoff | Investor reaction to Salient News in Closed-end Country Funds[END_REF] deal with closed-end country fund's prices and country specific salient news. They stated that there is a positive relationship between trading volume and news. Similar to the aforementioned approach, Chan and Wei [START_REF] Chan | Political Risk and Stock Price Volatility: The Case of Hong-Kong[END_REF] founded that news that is placed in the front page of the South China Post increase the return volatility in the Hong Kong stock market. Mitchell and Mulherin [START_REF] Mitchell | The Impact of Public Information on the Stock Market[END_REF] used the daily number of headlines of Dow Jones as a measure of public information. They mentioned the positive impact of news on absolute price changes. Mittermayer [START_REF] Mittermayer | Forecasting Intraday Stock Price Trends with Text Mining Techniques[END_REF] proposed a prediction system called NEWSCATS, which provides an estimate of the price after the publication of press releases. Schumaker and Chen [START_REF] Shumaker | Textual Analysis of Stock Market Prediction Using Financial News Articles[END_REF] examined three different textual representation formalisms and studied their abilities to predict discrete stock prices 20 minutes after an article release.

Markov Blanket Random Forests

A problem arises when the number of possible features is vast and the percentage of actually informative features is small, i.e. the performance of the base classifiers degrades. This phenomenon is particularly present in financial data sets, where most attributes represent technical indicators with little or unknown certainty about their correlation to the true course of a stock. Technically, in the case of a Random Forest classifier, this problem arises due to the fact that, if simple random sampling is used for selecting the subset of m eligible features at each node, almost all these subsets are likely to contain a predominance of non-informative features.

The solution proposed in this paper is based on the notion of a feature selection and reasoning algorithm, i.e. the Markov Blanket of the class attribute. The identification of relevant variables is an essential component of construction of decision support models, and computer-assisted discovery. In financial decision systems for example, such as the task at hand, elimination of redundant features could increase the computational performance significantly. The problem of variable selection in financial domains is more pressing than ever, due to the recent emergence of many news portals, on-line financial services, etc. Similar cases are also common in biomedical engineering, computational biology, text categorization, information retrieval, mining of electronic medical records, consumer profile analysis, temporal modelling, and other domains [START_REF] Díaz-Uriarte | Gene selection and classification of microarray data using random forest[END_REF]. Several researchers [START_REF] Kohavi | Wrappers for feature subset selection[END_REF] have suggested, intuitively, that the Markov Blanket (MB) of the target variable t, denoted as MB(t), is a key concept for solving the variable selection problem. MB(t) is defined as the set of variables conditioned on which all other variables are probabilistically independent of t. Thus, knowledge of the values of the Markov Blanket variables should render all other variables superfluous for classifying t.

Bayesian Networks and Markov Blanket

In order to better capture the significant properties of a Markov Blanket, a brief introductory section of Bayesian networks is included. Bayesian networks graphically represent the joint probability distribution of a set of random variables. A Bayesian network is composed of a qualitative portion (its structure) and a quantitative portion (its conditional probabilities). The structure BS is a directed acyclic graph where the nodes correspond to domain variables x 1 ,…, x n and the arcs between nodes represent direct dependencies between the variables. Likewise, the absence of an arc between two nodes x i and x j represents that x j is independent of x i given its parents in BS. Following the notation of Cooper and Herskovits [START_REF] Cooper | A Bayesian Method for the Induction of Probabilistic Networks from Data[END_REF], the set of parents of a node x i in BS is denoted π i . The structure is annotated with a set of conditional probabilities (BP), containing a term P(x i =X i |π i =Π i ) for each possible value X i of feature x i and each possible instantiation Π i of π i . A Markov Blanket of a node x i , denoted as MB(x i ), is a minimal attribute set, such that every other attribute is independent of x i given its Markov Blanket. Mathematically, the above statement is translated into:

) ( | }, { ) ( \ } ,..., { 1 i k i i i n i x MB x x x x MB x x x M ∪ ∈ ∀ , ( 1
)
where M denotes the conditional independence of i x with k x given ) ( i x MB .

Suppose B i and B j are two Bayesian networks that have the same probability distribution, then MB Bi (x k ) = MB Bj (x k ) for any variable x k . Certainly, MBs are not exclusive and may vary in size, but any given BN has a unique MB(x i ) for any x i , which is the set of parents, children and parents of children of x i . In Fig. 1, a Bayesian network is depicted along with the Markov Blanket of a target node x, colored in blue. As regards to the dataset interpretation, feature x is independent of all other features given its MB(x)={U i ,U j ,Y k ,Y l ,Z km ,Z ln }.

Random forests

Random Forests, in general, are a combination of decision tree classifiers such that each tree depends on the values of a random vector sampled independently and with the same distribution for all trees in the forest. Given a training set X comprised of N instances, which belong to two classes, and F features, a Random Forest multi-way classifier Θ(x) consists of a number of decision trees, with each tree grown using some form of randomization, where x is an input instance. The leaf nodes of each tree are labelled by estimates of the posterior distribution over the data class labels [START_REF] Strobl | Bias in random forest variable importance measures: illustrations, sources and a solution[END_REF]. Each internal node contains a test that best splits the space of data to be classified. A new, unseen instance is classified by sending it down every tree and aggregating the reached leaf distributions. The process is described in Fig. 2. Each tree is grown as follows:

• If the number of cases in the training set is N, sample N cases at random but with replacement, from the original data. This sample will be the training set for growing the tree. • If there are F input features, a number m<<F is specified such that at each node, m variables are selected at random out of the F and the best split on these m is used to split the node. The value of m is held constant during the forest growing. • Each tree is grown to the largest extent possible. Therefore, no pruning procedures are applied.

Fig. 2. Hierarchical decomposition of a Random Forests classifier on a data set

Markov Blanket Random Forests Implementation

Based on the existing implementations of Random Forests and taking our initial concerns on feature relevance into consideration, we propose a novel algorithm for classification using RF. The algorithm is entitled "Markov Blanket Random Forests-MBRF", since the danger of selecting irrelevant and misleading features is remedied by using the Markov Blanket of the class node to provide the best splitting criteria for each tree. By selecting random samples and obtaining the extracted MB of the target node, the probability of tree containing more informative features is increased. In case of high-dimensional datasets, the diversity of the ensemble is not compromised and is more robust that other, pre-filtering or weighting schemes. The algorithm is consisted of two distinct phases; the former regards the construction of the Markov Blanket and the latter deals with constructing the trees. Its basic procedure can be sketched in the following phases:

Experimental Design and Evaluation

As mentioned earlier, articles containing financial news were combined with a plethora of technical indices in order to search for direct influence patterns of the former to the latter. More specifically, we focused on three heterogeneous stock securities from the Greek stock market (Athens Stock Exchange, .ATG), a major Greek bank (Piraeus Bank, .TPEIR), the main telecommunication provider of Greece (OTE, .OTE) and one of the biggest Greek airline companies (Aegean, .AEGN). We incorporated past data from the major European, Asian and American stock markets, as well as data from energy and metal commodities. Finally, for each of the aforementioned three stock securities, a variety of major technical indices was utilized. News was automatically extracted from the electronic versions of the leading Greek financial newspapers, i.e. "Naftemporiki" (www.naftemporiki.gr) and "Capital" (www.capital.gr). The time period for all collected data was from November 2007 to January 2010. The technical indices were calculated using the AnalyzerXL tool. Table 1 tabulates data regarding the three benchmark stocks and their corresponding articles that were collected, while Table 2 contains data about historical data of other, main markets and commodities. Finally, Fig. 3 depicts a categorized list of the technical indices that were also taken into consideration. Stock quotes are gathered on a per day basis and articles are aligned accoriding to their release date. In case an article was pubished on a Friday evening (after the closing of the Athens stock market) or during the weekend, it was considered as published on a Monday. The textual analysis phase consisted of three activities: (a) removal of stop words (i.e. articles, special characters, etc), (b) lemmatization of words using a Levenshtein distance based Greek lemmatizer [START_REF] Lyras | Using the Levenshtein Edit Distance for Automatic Lemmatization: A Case Study for Modern Greek and English[END_REF], (c) removal of terms appearing less than 30 times within the complete article corpus and taking the 150 most frequent of them. Upon completion of the aforementioned phases, we kindly asked a domain expert (financial journalist) to annotate terms according to their genre. More specifically, she annotated each word with a signed integer according to whether it encompasses a very positive (+2), positive [START_REF]The Trader' s Glossary of Technical Terms and Topics[END_REF], neutral(0), negative(-1) of very negative(-2) sense. Examples of such terms respectively are: κερδοφορία (profitability, +2), ισχυρή (powerful, +1), πορεία (course, υποχώρηση (downgrading, -1) and κρίση (crisis, -2). The predicted class attribute contained three discrete values, namely UP, STEADY and DOWN, if the stock quote closed at a price more than 1%, between 1% and -1% and less than -1% in the following day respectively. A window of 5 days was used in order to predict the class, resulting in a high-dimensional dataset of more than 620 features. Article as well as stock quotes data was processed by our proposed methodology (MBRF), regular Random Forests (RF), Radial Basis Functions neural networks (RBF) and a derivative of Support Vector Machines, namely Sequencial Minimal Optimization (SMO) which can handle discrete values and acts similar to regression. Since the latter Machine Learning algorithms do not reduce features by default, in order to compare the MBRF technique against them, a PCA analysis approach was followed using the Nmath library for .NET platforms (http://www.centerspace.net/products/nmath).

Regarding the experimental design, two different approaches were followed. The former dealt with standard, 10 fold cross validation, classification in terms of stock quotes closeness, using datasets with articles and without articles, in order to evaluate the impact of articles on the predictability of a stock quote. We used the F-measure metric for evaluation, which acts as the harmonic mean of precision and recall. Table 3 tabularizes the F-measure score of all machine learining algorithms against linear regression (LR). From these outcomes, we could initially observe that combining information from both time series and textual data leads to improvement of the performance for all methodologies. Furthermore, by using only technical analysis data, SMO perform similar to MBRF and significantly outperform all other approaches, while when incorporating textual information, MBRF is noticeably the best classification approach, a fact that could be attributed to the dimensionality reduction when applying the Markov Blanket preprocessing step. According to Table 3, the performance of MBRF is one of the highest ever reported, with the drawback of a very time and recource consuming training phase. The latter experimental design developed was a simulated trading strategy, in an effort to further examine if the MBRF model could practically be applied to generate higher profits than those earned by employing the traditional regression model of by simply following a buy-and-hold (passive) investment strategy. The operational details of the trading simulation are explained as follows: The trading simulation assumes that the investor has 100,000€ to create a portfolio by selecting a balanced percentage of each of the three Greek stock quotes mentioned earlier. Each day, the investor could buy, sell or wait, according to the class prediction of the MBRF model.

We assume that transactional costs apply when buying or selling (0,335% and 0,35% respectively) and a random choice between 5% and 10% of the current portfolio can be traded each day. The time period was set to the last 35 weekdays of the aforementioned dataset. As Fig. 4 depicts, the dashed line, which represents the portfolio budget for the MBRF investing strategy is clearly outperforming the solid line of the buy-and-hold investment strategy by a mean factor of 12.5% to 26% for the first 2 weeks and from 16% to 48% for the remaining ones.

Fig. 1 .

 1 Fig. 1. An example of a Bayesian Network with the Markov Blanket of node x.

Fig 3 .

 3 Fig 3. The technical indices considered.

Fig. 4 .

 4 Fig. 4. Plot of portfolio outcomes using the two different trading strategies

Table 1 .

 1 The benchmark tickers.

	Name	Category	#Articles	#Days	Symbol
	O.T.E.	Telephony	1779	519	.OTE
	Bank of Piraeus	Bank	1607	514	.TPEIR
	Aegean Airlines	Airline	308	547	.AEGN

Table 2 .

 2 Market and commodities data.

	Category	Description	#Days	Symbol
		^FCHI-CAC 40 Index	542	.FCHI
	European Markets	^FTSE-FTSE 100 Index ^GDAXI-Xetra Dax Index	569 537	.FTSE .GDAXI
		^ATG-Athens Stock Exchange	511	.ATG
		^HIS-Hang Seng Index	556	.HSI
	Asia/Pasific Markets	^AORD-All Ordinaries Index	569	.AORD
		^N225-Nikkei 225 Average Index	556	.N225
		^GSPC-S&P 500 Index	558	.GSPC
	United States Markets	^IXIC-Nasdaq Composite Index	531	.IXIC
		^DJI-Dow Jones Industrial Average Index	539	.DJI
	Energy	Brent DTD WTI CUSHING	566 521	BRT-WTC-
	Metals	Silver Gold Bullion	537 537	XAG-HH XAU-B-HH

Table 3 .

 3 Classification performance in terms of F-measure.

	Dataset	MBRF	RF	SMO	RBF	LR
	No articles	64.23	55.25	63.56	53.21	47.54
	Including articles	73.44	60.66	67.76	56.80	47.76


Antonio Maffei

Mauro Onori
email: onori@iip.kth.se

Pedro Neves

José Barata

Evolvable Production Systems: Mechatronic Production Equipment with Evolutionary Control

Keywords: Evolvable Production Systems, Modularity, Distributed Control

Current major roadmapping efforts have all clearly underlined that true industrial sustainability will require far higher levels of systems' autonomy and adaptability. In accordance with these recommendations, the Evolvable Production Systems (EPS) has aimed at developing such technological solutions and support mechanisms. Since its inception in 2002 as a next generation of production systems, the concept is being further developed and tested to emerge as a production system paradigm. Characteristically, Evolvable systems have distributed control, and are composed of intelligent modules with embedded control. A concerted effort is being exerted through European research projects in collaboration with manufacturers, technology/equipment suppliers, and universities. After introducing EPS, this paper presents current developments and applications.

Introduction

The major problems of manufacturing companies are all relate to uncertainty. First of all, it is very difficult for companies to predict the type and range of products that will have to be developed. The second uncertainty regards the production volumes and lifespan reached by these future products.

Evolvable systems, as a next generation of production systems, was first introduced in 2002 and has, since then, been developed and tested to emerge as a production system paradigm (see EUPASS, A3 projects). The essence of evolvability resides not only in the ability of system components to adapt to the changing conditions of operation, but also to assist in the evolution of these components in time such that processes may become self-X, x representing a property of the system such as reconfigurable, etc.

According to the results attained by many roadmaps, such as ManuFuture [START_REF]Strategic Research Agenda-assuring the future of manufacturing in Europe[END_REF], ManVis [START_REF] Manvis | Manufacturing Visions-Integrating Diverse Perspectives into Pan-European Foresight[END_REF], FutMan [START_REF]The Future of Manufacturing in Europe 2015-2020-The Challenge for Sustainability[END_REF] and EUPASS [START_REF]EUPASS Adaptive Assembly Roadmap 2015-deliverable 1.5f; Del. 1.5f, EUPASS-Evolvable Ultra Precision Assembly[END_REF], one of the most important objectives to be met by European industry is sustainability, which is multi-faceted: including economical, social and ecological aspects. The conclusion to this holistic problem is that future manufacturing solutions will have to deal with very complex scenarios.

This article gives a brief overview of the achievements attained by Evolvable Assembly Systems, EAS [START_REF] Barata | ISIE'06 -IEEE International Symposium on Industrial ElectronicsIEEE[END_REF]. EAS represents one of the paradigms proposed as an opportunity to solve such threats. NOTE: the relation to Holonic Manufacturing Systems ( [START_REF] Van Brussel | Reference Architecture for Holonic Manufacturing Systems: PROSA[END_REF], [START_REF] Bussmann | Rationales for Holonic Manufacturing; Second Int. Workshop on Intelligent Manufacturing Systems[END_REF]) and Reconfigurable Manufacturing Systems will be described later.

Evolvable systems clearly approach the idea that system components may evolve to meet upcoming demands and needs. This inevitable bridges the fields of production engineering and computer science, but it also introduces aspects of computational evolution. Hence the link to a partial study of genetics and evolutionary principles (discussed later). Evolvable systems have characteristically distributed control, are composed of intelligent modules and are open in architecture: they go beyond the concept of embedded control and begin to suggest embedded intelligence. The technical and architectural aspects of the evolvable system development are supported by a comprehensive methodological framework. Evolvability being a system concept, it is envisaged to address every aspect of an assembly system throughout its life cycle, i.e., design and development, operation and evolution. The work has been and being implemented through large European research projects. Furthermore, integration of legacy subsystems and modules have been addressed in the methodology. It has, to date, resulted in several demonstrators and offered methodologies and architectures in support. This paper presents current developments and applications.

Contribution to Technological Innovation

As defined in [START_REF] Elmaraghy | Flexible and Reconfigurable Manufacturing Systems Paradigms[END_REF] RMS incorporates principles of modularity, integrability, flexibility, scalability, convertibility, and diagnosability. These principles impose strong requirements to the control solution. In particular, centralized approaches become completely unsuited due to their intrinsic rigidity. Decentralised solutions must be considered that take into account the fundamental requirements of plugability of components, which includes the aspects related to dynamic addition /removal of components, as well as adaptation in the sense that the system does not need to be reprogrammed whenever a new module is added/ removed. This is a fundamental aspect behind any control solution approach to solve the defined requirements. Moreover, diagnosability also demands a decentralized approach, in particular if the manufacturing system is considered as a set of manufacturing components, each with diagnosis capability. The overall diagnosis of the system is obtained considering all the diagnosis information obtained from the individual modules. Due to these requirements, a particular and relevant aspect in the system being considered is the "intelligent" nature of its components, i.e., each component is considered as having computational power that will support individual diagnosability, dynamic plugability, adaptation, etc.. Therefore, the major challenge in the control solution is how to guarantee proper coordination and execution in a system in which both its components and working conditions can be dynamically changed. This is a challenge that needs a completely new approach and this is why in the context of EPS a solution based on concepts inspired from the Complexity Theory and Artificial Life is being developed. The next section covers what concepts from non traditional manufacturing research domains are being used to create truly dynamic control solutions.

Nevertheless, in the context of this paper it is important to clarify what are the big differences between the approach being proposed here and Holonic Manufacturing. The genesis of holonic manufacturing was very much a biological inspired approach and it was very close to the concepts of bionic and fractal. However, succeeding implementations along the years have drifted more and more from the original inspiration, and, in many aspects, the systems became more hierarchical.

Hence, the control approach to be developed in the context of EPS wants to go back to the basics, that is to say relying stringy on the original idea of considering each component as a distributed intelligent unit that may aggregate in order to create a complex system. In this context, concepts such as emergence and self-organisation become more and more important to be applied to new generation control solutions. Interestingly enough other researchers are proposing a self-organisation view in manufacturing enterprises [START_REF] Tharumarajah | A Self-organising View of Manufacturing Enterprises[END_REF]. However, true implementations of these new concepts within shop floor are still very few.

Considering what was stated above, one may view Evolvable Production Systems (EPS) as a development of the Holonic Manufacturing Systems (HMS) approach; however, a closer looks reveals that, although there are similarities in the exploitation and implementation phases, the paradigms differ quite substantially in their perspective (or trigger issue), and that only EPS achieves fine granularity. By granularity it is considered the level of complexity of the component that compose a manufacturing system. For instance, when a line is composed of several cells and these cells are modules that can be plugged in and out, this is thick granularity. If, on the other hand, the components that can be plugged in or out are grippers, sensors, or pneumatic cylinders, this is fine granularity. This issue is in fact a very important one in terms of distinguishing the paradigms.

New EPS equipment

The main difference in the EPS paradigm is that it was created from a more dynamic, industrially-relevant perspective (trigger issue): EPS is mainly concerned with what occurs in a production system when a production change-over is called for; that is, whenever the current production system needs to undergo some change in its physical, control, or productivity layout [START_REF] Maffei | From Flexibility to Evolvability: ways to achieve selfreconfigurability and full-autonomy[END_REF]. Such changes occur at ramp-up, product change-over, or demand surges. This is where the biological inspiration to EPS first makes itself apparent: it is change that drives the adaptability/evolution of the EPS systems, not the current or known scenarios. Furthermore, as will be detailed later, the adaptability is dictated by real evolvability principles such as "survival-of-the-fittest" at algorithm level. This biological approach becomes even more evident when one studies the way modularity is achieved within EPS. In most approaches, modularity is set by either known mechanical subdivisions, or by taking the classical subdivisions that exist within manufacturing; for example, in reconfigurable assembly, the modules are most often set by the transport/handling/joining/placing/packaging processes. There is no biological link and the RMS and HMS paradigms tend to try to achieve a general, top-level solution.

EPS is radically different in this respect as it will focus on the predicted and unpredictable changes that may occur within a very limited product range (genus). The first solution will be limited and specific, and may, if successful, gradually be applied to the associated product family (species). Hence EPS is not a generic solution but a specific approach that may be adopted by other "species" if its evolutionary capabilities denote a high rate of success. Furthermore, EPS takes a hybrid and not top-down approach to the definition of its modules. The EPS modules are defined by precise sub-processes that have been identified for a given product range: the taxonomy of the sub-processes is very detailed and therefore results in fine granularity. This is a low-level approach, and gives modules with very optimised performance characteristics: process-oriented modules [START_REF] Maraldo | Evolvable Assembly Systems: Clarifications and Developments to Date[END_REF]. Note that since it is specific, and focuses on the given evolutionary demands of a product range and its sub-processes, it may also be closely linked to product design issues. This is unique among current paradigms, which clearly underlines the contribution.

Enabling Research Domains and Concepts

The main issue to be addressed in this section is describing the areas in which EPS control systems are getting inspiration to solve the requirements for adaptability at fine granularity. Numerous scientific domains investigating phenomena which EPS also exhibit have emerged in the last few years, which can provide helpful tools and valuable theoretical background to cope with the complexity of manufacturing systems. A more detailed definition may be found in [START_REF] Barata | Evolvable Production Systems -Enabling Research Domains[END_REF].

Complexity Theory Complexity Theory looks for simple causes leading to complex behaviours [START_REF] Delic | On the Emerging Future of Complexity Sciences[END_REF]. Complex systems are spatially and/or temporally extended non-linear systems with many strongly-coupled degrees of freedom. They are composed of numerous in themselves often simple elements and are characterized by collective properties. EPS consist of numerous equipment modules which are connected to each other and have multi-lateral interactions. Each of them has some degrees of freedom, which are constraint by other system parts. Together, the modules form a system with the desired global behaviour.

Artificial Life Taking natural life and its characteristics as an example, scientists attempt to create life-like behaviors with the capability of evolution on computers and other "artificial" media. EPS are very similar to artificial living systems, with a modifiable structure, will exhibit some kind of self-organization, can adapt to their environment, and react to stimuli. They are capable of evolving according to the circumstances, namely in terms of equipment states, and can incorporate newly available technology.

Autonomic Computing Although at another level than the other areas described above, Autonomic Computing is a fundamental concept for EPS. The vision of Autonomic Computing [START_REF] Kephart | The Vision of Autonomic Computing[END_REF] refers to the tendency of computers to become ubiquitous. Forming large networks and having complex and multiple interactions, they become increasingly difficult to manage. As a consequence, software will be designed to take care of itself. User interaction will be minimized and reprogramming avoided. Note that the more modules of fine granularity include computational power, the more is necessary to find new ways of coordination and automatic plugability, which is exactly what EPS want to address. Agents Depending on the context, an agent can be a human person, an association, an animal, or a piece of software, eventually connected to some hardware. The fundamental characteristics are identity, intelligence and the ability to act and react in order to persecute goals. Agents have at least a certain degree of autonomy and can compete or collaborate with others.

There are numerous successful experiences with agent-based systems in industry [START_REF] Monostori | Agent-Based Systems for Manufacturing[END_REF]. Rockwell Automation even develops agent-based systems where the agents run inside the PLC itself [START_REF] Mařík | Rockwell automation agents for manufacturing[END_REF] instead of on separate computers.

Self-Organization Reasons for implementing self-organization in EPS are to minimize and facilitate user interaction, i.e. to hide complexity and increase system autonomy. Building and configuring a system composed of numerous entities with multi-lateral interactions is a highly complex task; the more autonomy the system has, the easier it gets for the user. Agents need the capacity of organizing their collaboration themselves, in according to the needs, without passing through a central coordination point. Emergence Complex systems most often consist of at least two different levels: the macro-level, considering the system as a whole, and the micro-level, considering the system from the point of view of the local components. Local components behave according to local rules and based on preferably local knowledge; a representation of the entire system or knowledge about the global system functionality is neither provided by a central authority nor reachable for the components themselves. They communicate, interact with each other and exchange information. From the interaction in this local world emerge global phenomena, which are more than a straight-forward composition of the local components' behaviors and capabilities. Typically, there is not only a global behavior dependent on the local parts, but their behavior is also influenced by the system as a whole. Emergent phenomena are scalable, robust, and fault-tolerant, i.e. insensitive to small perturbations and local errors as well as component failure, thanks to redundancy. They exhibit graceful degradation, meaning that there is no total break-down because of minor local errors. Evolution EPS implies, at least partially, evolutionary behavior according to Darwinian theory. It intends to do so by applying complex adaptation behaviour at control level, and by subdiving the system equipment into specific modules. According to scientific results in the fields of Computational Ecology and Genetics ( [START_REF] Wagner | Complex Adaptations and the Evolution of Evolvability[END_REF], [START_REF] Bowers | Simulating Evolution with a Computational Model of Embryogeny[END_REF]), the idea to adopt a modular approach is very similar to natural selection. Hence the analogy of applying modularity at system level, based on process constraints, to that of a genotypemodularity used in nature to limit the combinatorial explosion. The challenge in EPS, as with computational adaptation, is to "code" the events correctly and create the correct representations. Hence the need to study emergence and complexity theory.

Architectural Aspects behind Methodology

The EPS Methodology [START_REF] Lohse | Multi-Agent Architecture for Self-Configuring Modular Assembly Systems[END_REF] provides the references architecture, enablers, and modeling formalisms. In the following section brief description of the methodology is given. Note that a full description of the Methodology and associated Reference Architecture is available through the EUPASS project framework (http://www.easenv.org). The EPS formalised concepts (ontology) and definitions are represented using a set of descriptive tools such as:

• Definitions of the most important concepts: module, process, product, EPS module, skills, EPS system (which is a composition of modules), etc. • Diagrams (UML, etc) where the interactions between the concepts defined are shown. This enables to show how the EPS architecture generates assembly systems. The interaction may show the global system behaviour The domain ontology indeed captures the concepts in the system with their specifications (consensual semantic) i.e., what the concepts are and how they are related to each other in the domain. However, it does not capture the logic behind the relationships and the how's in the synthesis and functionality of the system.

A full description of the EAS ontology, and its associated Knowledge Model, is given in [START_REF] Ueda | [END_REF].

Reference Architecture, RA

The EPS Reference Architecture (EPS_RA) describes the essential features of an Evolvable System which means the reference architecture specifies the necessary features that a system should have to be an evolvable system. The reference architecture is composed of three main elements: Principles, Technical Positions and Templates. Principles: EPS has two fundamental principles which lay the foundation and guide the development process of an evolvable system. These principles can be considered as a description of the core ideas of the evolvable system paradigm.

Principle 1: the most innovative product design can only be achieved if no assembly process constraints are posed. The ensuing, fully independent, process selection procedure may then result in an optimal assembly system methodology.

Principle 2: Systems under dynamic conditions need to be evolvable, i.e., they need to have an inherent capability of evolution to address the new/changing requirements.

The enabling models include the development process model, the business model and the knowledge model. These models are constructed using the formalisms described above and most notably the EPS ontology. The figure below depicts the first proposed EPS_RA using IDEF0. The is a simplified high level activity model showing the main activities in the development process and their input, output, control and mechanisms needed to generate or modify instances of the architecture. The elements in the EPS knowledge model consists of the knowledge domains: 1. The enterprise knowledge domain -globalizes knowledge of the system and represents the business, organizational and global knowledge models. Enterprise knowledge enables environment recognition and maintenance of associations. 2. The product knowledge domain -captures the knowledge related to product specification and design to assembly tasks.

The execution knowledge domain: capturing knowledge elements related to communications, planning and scheduling

The traditional top-down system design is feasible only in cases where the emergent behaviour is fully describable; [START_REF] Hofmann | Emplacement and Blue Print -An Approach to Handle and Describe Modules for Evolvable Assembly Systems[END_REF]. If emergent behaviour has to be investigated even at design and development stages, then a heterarchical or a network approach are the options.

4. The learning knowledge domain: containing knowledge elements that are used to incorporate case based reasoning. The EPS RA is ultimately be viewed from different perspectives addressing the different concerns of the stakeholders. The stakeholders include:

• those who build the system (structure and communication views),

• those who use it (functional view),

• those who are concerned with control (control view).

Practical Developments

Initial evaluations were carried out in the test cell shown below (fig. 3.0a). More industrially viable evaluations are currently being deployed within a new system being developed at KTH (fig. 3.0b). For obvious reasons, reconfigurability may be illustrated by videos and is more arduous via text-details given in [START_REF] Adamietz | Development of an Intermodular Receptacle-A First Step in Creating EAS Modules[END_REF] and detailed (videos, etc.) on www.Eas-Env.Org. At present the EPS paradigm is only just starting to take a practical form, and the control solution, ontologies, and methodologies only partially describe the most recent developments. These ideas are now being put into real industrial scenarios within the EUPASS project [START_REF] Lohse | Multi-Agent Architecture for Self-Configuring Modular Assembly Systems[END_REF], and through the participation of Electrolux Home Products Italy SpA and UNINOVA. The layout given in figure 3.0b is being setup for two industrial products (self-configuring & reconfiguring).

Fig. 4. The Intermodular Receptacle

The project has now demonstrated that legacy equipment may be modified to Evolvable Production System [START_REF] Adamietz | Development of an Intermodular Receptacle-A First Step in Creating EAS Modules[END_REF]. An intelligent interface was developed out of an old Schunck gripper, as shown below, and the EUPASS project has now developed a full Evolvable Production System in Windisch, Switzerland.

Conclusions

EPS, as with other similar approaches, offers great opportunities for attaining true agility and cost-effective, stepwise automation. The technologies for achieving this are available and there are several partners willing to partake in this endeavour (for detailed list see website cited below: FESTO, BOSCH, ELECTROLUX, TQC, KIT, etc.); however, it is vital to point out that EPS does imply that the manner in which we develop and create projects for the development of assembly systems are radically changed, assuming a more synthesis-based approach.

In order to stimulate the further development and update of the paradigm and its applications, a collaborative web space has been developed, in which the architecture, standards, equipment modules and other details are detailed and made accessible: www.Eas-Env.Org. This EAS Environment web space is currently being expanded to include work from related projects.

Fig. 1 .

 1 Fig. 1. Basic Overview of EPS Approach.

Fig. 2 .

 2 Fig. 2. The simplified EPS_RA Concepts that are formalised in the EPS Ontology are used to capture the stakeholders understanding of their own domain. The EPS knowledge model is thus a structured and formalised collection of such knowledge capturing representations of the domains. The main objective of the EPS knowledge model is to provide an environment that supports the development and operation of evolvable systems. The domain knowledge captured using the EPS ontology and the EPS knowledge templates are the two entities used to develop the knowledge model. The knowledge models are used among other things how each module in a system should address for a new set of conditions. The elements in the EPS knowledge model consists of the knowledge domains: 1. The enterprise knowledge domain -globalizes knowledge of the system and represents the business, organizational and global knowledge models. Enterprise knowledge enables environment recognition and maintenance of associations. 2. The product knowledge domain -captures the knowledge related to product specification and design to assembly tasks. 3. The execution knowledge domain: capturing knowledge elements related to communications, planning and scheduling

Fig. 3 .

 3 Fig. 3. a-The Evaluation Test Case. Fig. 3. b-Industrial Test Case.