Krzysztof Ostrowski
email: k.ostrowski@pb.edu.pl

Evolutionary algorithm for the Time-Dependent Orienteering Problem

Keywords: Time-Dependent Orienteering Problem, evolutionary algorithm, metaheuristic, local search operators

The Time-Dependent Orienteering Problem (TDOP) is a generalization of the Orienteering Problem where graph weights vary with time. It has many real life applications particularly associated with transport networks, in which travel time between two points depends on the moment of start. The paper presents an evolutionary algorithm with embedded local search operators and heuristic crossover, which solves TDOP. The algorithm was tested on TDOP benchmark instances and in most cases achieved optimal or near optimal results clearly outperforming other published methods.

Introduction

The Orienteering Problem (OP) can be formulated on a graph in which each vertex has assigned a profit and each edge has a cost. The goal of the OP is to find a path between given points limited by total cost which maximizes total profit of visited vertices. The OP has many practical applications including tourist trip planning [START_REF] Vansteenwegen | The City Trip Planner: An expert system for tourists[END_REF], transport logistics and others. For example in tourist trip planning each attraction (point of interest -POI) has some profit assigned. In this case the purpose is to find as attractive trip as possible with limited duration. It can by solved by OP algorithms.

In this paper the Time-Dependent Orienteering Problem (TDOP) [START_REF] Li | Model and Algorithm for Time-Dependent Team Orienteering Problem[END_REF] is tackled. TDOP is a generalization of OP in which graph weights (indentified with travel times) vary with time. In practical situations, usually travel time between two places depends on the moment of travel start. Examples of time-dependent networks are public transport networks (travel times determined by timetables) as well as other transport networks (travel times determined by time of a day and traffic). Determining most profitable paths in such networks (i.e. most attractive trips for tourists) comes down to solving TDOP.

To solve the TDOP author proposed an evolutionary algorithm with local search methods embedded. It was based on the algorithm which author developed for classic OP obtaining solutions close to optimal for benchmarks up to a few hundred vertices [START_REF] Ostrowski | Parameters Tuning of Evolutionary Algorithm for the Orienteering Problem[END_REF]. Some modifications were applied to the algorithm: allowance of infeasible solutions (too long paths) in a population and adaptation of operators to time dependency.

The article is organized as follows. Literature review is presented in section 2. Detailed mathematical problem definition is given in section 3. In section 4 there is a description of proposed evolutionary algorithm. Section 5 contains computational results of the algorithm and comparisons with other metaheuristics. Finally, in section 6 conclusion and further research are included.

Literature review

The Orienteering Problem was introduced by Tsiligirides [START_REF] Tsiligirides | Heuristic methods applied to orienteering[END_REF]. The OP (and its generalizations) is an NP-hard optimization problem [START_REF] Golden | The orienteering problem[END_REF] and exact algorithms for OP can be very time-consuming for larger graphs. The exact algorithms usually applied for the OP are the branch-and-cut methods [START_REF] Fischetti | Solving the orienteering problem through branch-and-cut[END_REF] [START_REF] Gendreau | A branch-and-cut algorithm for the undirected selective traveling salesman problem[END_REF]. However, because of its computational difficulty, most OP papers are devoted to heuristics and metaheuristics. Various approaches were based i.a. on greedy and randomized construction of solutions [START_REF] Tsiligirides | Heuristic methods applied to orienteering[END_REF] [2] [START_REF] Campos | Grasp with Path Relinking for the Orienteering Problem[END_REF], local search methods [START_REF] Chao | Theory and methodology -a fast and effective heuristic for the orienteering problem[END_REF] [START_REF] Vansteenwegen | A guided local search metaheuristic for the team orienteering problem[END_REF], tabu search [START_REF] Gendreau | A tabu search heuristic for the undirected selective travelling salesman problem[END_REF], ant-colony optimization [START_REF] Schilde | Metaheuristics for the biobjective orienteering problem[END_REF] and genetic algorithms [START_REF] Tasgetiren | A genetic algorithm with an adaptive penalty function for the orienteering problem[END_REF]. Author's previous OP research concentrated on development of evolutionary algorithms with local search operators, which proved successful on benchmark instances [START_REF] Ostrowski | Evolutioninspired local improvement algorithm solving orienteering problem[END_REF][27] [START_REF] Zabielski | A Genetic Algorithm with Grouping Selection and Searching Operators for the Orienteering Problem[END_REF] [START_REF] Koszelew | A Genetic Algorithm with Multiple Mutation which Solves Orienteering Problem in Large Networks[END_REF].

The Time-Dependent Orienteering Problem (TDOP) is relatively new and most of papers regarding TDOP were published in current decade. Most of them emphasize practical application of TDOP especially in transport networks. Fomin et al. [START_REF] Fomin | Approximation algorithms for time-dependent orienteering[END_REF] presented first approach to the problem -they proposed (2 + )approximation algorithm for TDOP. The problem version tackled in the article was simplified because each node had the same profit (equal to 1). LI [START_REF] Li | Model and Algorithm for Time-Dependent Team Orienteering Problem[END_REF] developed an exact method basing on dynamic programming and solved small instances of TDOP. He used discretized time and there were 1440 time states (number of minutes in a day). It was the first article about classic TDOP (nodes profits can be arbitrary).

The TDOP solutions can be practically used in networks of tourist attractions connected by means of public transport. A few papers concentrated on TDOP application in such networks. In paper [START_REF] Abbaspour | Time-dependent personal tour planning and scheduling in metropolises[END_REF] first such an application was presented -algorithm was tested on POI and public transport network of Tehran. The authors used a different name to the problem and routes utility was computed in a different way to classic OP but the problem was closely related to TDOP.

Garcia et al [START_REF] Garcia | Integrating public transportation in personalised electronic tourist guides[END_REF] for the first time applied classic TDOP version in a public transport network -experiments were conducted on POI and public transport network of San Sebastian. Their solution also took into account time-windows and multiple paths (Time-Dependent Team Orienteering Problem with Time Windows). In order to solve the problem they used Iterated Local Search method (ILS). However, they used some simplifications: computations performed on average daily travel time (first approach) and assumption of periodic public transport timetables (second approach).

Recently one of the first approaches which uses real time-dependent weights in public transport network was presented [START_REF] Gavalas | Heuristics for the time dependent team orienteering problem: Application to tourist route planning[END_REF]. Experiments were conducted on POI and public transport network of Athens. Authors proposed 20 topologies and 100 tourist preferences combining into 2000 different test cases. Authors introduced two fast heuristics (TDCSCR and TDSlCSCR), which based on iterated local search and vertex clustering, and made comparisons with ILS.

Another solution of TDOP tested on real travel times of POI and public transport network (city of Bialystok) was proposed by the author of this paper [START_REF] Ostrowski | Comparison of Different Graph Weights Representations Used to Solve the Time-Dependent Orienteering Problem[END_REF]. The algorithm based on local search procedures and was tested in three variants which processed network weights in different ways. Time-dependent variant performed computation on real travel times, mean variant operated on static network of daily averaged travel times (like in approaches described above) and hybrid variant used information from both approaches.

Verbeeck at al [START_REF] Verbeeck | A fast solution method for the time-dependent orienteering problem[END_REF] developed new benchmark instances for TDOP. These networks model street traffic. The authors proposed ant-colony approach, tested it on mentioned benchmarks and compared with optimal solutions (obtained by them). The tested metaheuristic achieved high quality results in short execution time. Gunawan et al [START_REF] Gunawan | A Mathematical Model and Metaheuristics for Time Dependent Orienteering Problem[END_REF] modified Verbeeck's benchmarks (discretization of time) and tested a few approaches: greedy construction, iterated local search (ILS), adaptive ILS and variable neighborhood descent. The best solutions were generated by adaptive ILS metaheuristic.

Definition of the Time-Dependent Orienteering Problem

Let G = (V, E) be a directed, weighted graph. In this paper each weight between vertices i and j (i, j ∈ V ) is identified with travel time between these vertices and is a function w ij (t) dependent on the moment of travel start t. Each vertex i has a nonnegative profit p i and a nonnegative visit time τ i . Given the timedependent graph, moment of start t 0 , time limit T max , start and end vertices (s and e) the purpose of TDOP is to find a path from s to e starting at time t 0 which maximizes total profit of visited vertices and its total cost (travel time) does not exceed T max . TDOP can be formulated as Mixed Integer Programming problem. Let x ij is 1 iff a path contains direct travel from i to j and 0 otherwise. Let y i is 1 iff a path contains vertex i and 0 otherwise. Let t i be a time of arrival at vertex i -this function is defined only for vertices contained in a path. The purpose of TDOP is to maximize formula 1 without violating constraints given by formulas 2-8. Formula 2 limits total time budget. Formula 3 indicates that the path starts in s and ends in e. Constraint 4 means that each vertex can be visited only once while formula 5 is a relation between variables x and y. Formulas 6 and 7 are used to compute arrival times at visited vertices. Constraint 8 guarantees that there are no sub cycles.

To solve the TDOP author proposed an evolutionary algorithm with local search methods embedded (during mutation), disturb operator, 2-point crossover and deterministic crowding as selection mechanism. Operators have two forms (random and heuristic) -their frequency and specificity are controlled by algorithm parameters. Infeasible solutions (too long paths) can be included in a population as well and they are penalized by fitness function. A path representation is used in the proposed algorithm -each gene in a chromosome is associated with visited vertex in a corresponding path. After random initialization of paths, procedures of crossover, selection, mutation and disturbance and applied repeatedly. Evolution terminates after N g generations or earlier if there is no improvement in the last C g generations. The result is the best feasible path obtained during algorithm run.

Evalutation

Let S be a path with total profit p S and total cost (travel time) c S . Fitness function of a feasible path (not exceeding T max ) is equal to its profit. If path S is too long its fitness is: f itness(S) = p S • ( Tmax c S ) k . Fitness function decreases as solution is farther from feasibility boarder T max . Parameter k is associated with penalty severity: larger values mean stronger penalties. Fitness function is adaptive: at the beginning k = 1 and every 10 generations there is a check -if more than α percent of individuals are infeasible then k is increased by 0.1.

Initialization

At the beginning initial population of P size random paths is generated. Construction of each solution begins with adding start vertex s. Afterwards, random vertices are iteratively added at the end of the path as long as further insertions are possible without violating T max constraint (including cost of traveling back to end vertex).

Crossover

During crossover

Psize•cp 2 different pairs of parents are randomly selected from the population (c p -crossover probability) and each pair undergoes crossover procedure. A specialized 2-point crossover operator was used. At the beginning an ordered set S of common vertices for both parents is determined. Vertices order in the set is the same as in first parent. Next, chromosome fragments between two successive vertices in S are exchanged and two offspring are created. If any duplicates appear in offspring individuals outside of exchanged fragments they are immediately removed. Crossover can be performed in two ways depending on how exchanged fragments are chosen. Random crossover variant chooses crossing points randomly while heuristic crossover maximizes fitness function of the fitter offspring (all exchange options are checked). Created offspring can exceed T max limit. The probability of using heuristic crossover is indicated by parameter c h while the probability of using random version is 1 -c h . In Figure 1 there is an example of crossover.

Selection

In the algorithm no parent selection is used. Instead, survival selection is applied in the form of deterministic crowding [START_REF] Mahfoud | Crowding and preselection revisited[END_REF]. After crossover procedure ends each offspring competes with one of its parents and the fitter individual is chosen to the next generation. To preserve population diversity competition is performed between more similar child-parent pairs. Pair arrangement is determined by distance measure. In this problem two distance measures are applied: edit distance (operations insert and delete) and cardinality of symmetric difference of vertex sets. The second is computed initially -if it suggests that child-parent pairs should be swapped then more complex procedure of edit distance is calculated.

Mutation

During mutation phase P size • m p individuals are randomly selected from the population (m p is mutation probability). First, each chosen individual undergoes 2-opt procedure. This procedure tries to replace two non-adjacent edges in a path by two other edges in order to shorten the path as much as possible. Given a path (v 1 , v 2 , ..., v i , v i+1 , ..., v j , v j+1 , ..., v k ) 2-opt procedure replaces edges (v i , v i+1 ) and (v j , v j+1 ) by edges (v i , v j ) and (v i+1 , v j+1 ) and reverses path fragment between v i+1 and v j . The resulting path is:

(v 1 , v 2 , ..., v i , v j , v j-1 ..., v i+1 , v j+1 , v j+2 ..., v k ).
Afterwards one vertex insertion or one vertex deletion is carried out. Probabilities of insertion and deletion are the same (0.5). Both insertion and deletion can be either random or heuristic (local search). Heuristic insertion from all possible non-included vertices (and all insertion places) chooses the option that maximizes ratio of vertex profit to path travel time increase. Random insertion chooses new vertex randomly but insertion place is chosen to minimize travel time increase. Heuristic deletion chooses the vertex that minimizes ratio of vertex profit to path travel time decrease. During mutation T max limit can be exceeded. The ratio between local search and randomness is determined by parameter m h (analogically to c h in crossover phase).

Disturb

Disturb procedure can be perceived as a different type of mutation which causes bigger changes in routes. The operator chooses P size • d p individuals from the population (d p is disturb probability). Each chosen individual is disturbed -a path fragment of random length (but containing at most 10 percent of all path vertices) is removed. Two types of disturb are possible: first version removes a random fragment of random length while heuristic version works analogically to deletion mutation -from all possible fragments of a given length it chooses the option minimizing ratio of fragment profit to path travel time decrease. Specificity of this operator is determined by parameter d h .

Adaptation to time dependency

TDOP algorithm operates on time-dependent networks and for this reason each path modification is associated with recalculation of edge travel times after the modification point. This can be particularly time-consuming in case of heuristic operators. For this reason some modifications were applied to these parts. Vertex insertion: After inserting new vertex all edge travel times after insertion place have to be recalculated. Insertion operators of the algorithm choose the best insertion place for an included vertex (minimizing travel time increase).

Trying each insertion place and recalculating weights is time consuming. However, it is possible to determine the best insertion place in O(N ) run time (Nnumber of nodes in a path). The purpose of insertion is to minimize path travel time increase but it can be replaced by an equivalent goal of earliest possible arrival into the last vertex in a modified path. It can be computed in one loop over the path. In the i-th iteration we compare two arrival times into vertex i: one resulting from insertion new vertex directly before i and one resulting from best insertion place chosen so far. If current insertion place is better than previous best (arrival time into vertex i is earlier) we update our best choice.

2-opt:

The purpose of 2-opt is to decrease path travel time as much as possible by edges replacement. Each edge exchange is associated with recalculating travel times in a large fragment of a path (part of it is reversed). In order to decrease execution time of 2-opt some modifications were applied -instead of time-consuming repeated recalculations of travel times the procedure tries to estimate total travel time of reversed path fragments. At first the initial travel time of the path (before changes) is divided into equal time intervals. Afterwards some reversed path fragments (starting at different times) are precomputed. Estimation is fast and base on finding an appropriate precomputed path (explanation in Figure 2). Exact calculations are performed only if estimation signals that travel time can be shortened -it significantly reduces computations. and it starts at time t = 0 and ends at time 80. Time was divided into D = 4 equal intervals and all possible vertices in reversed fragments are v9, v8, ... v2. The figure can be treated as 2-dimensional array and in each cell there is a precomputed path fragment visiting a given vertex (determined by column) at a given time interval (determined by row). For example in order to estimate travel time of fragment (v7, v6, v5) starting at time t = 27 we should find an appropriate column (v7) and row (interval 20-40) and route fragment associated with it (pointed by arrow). Afterwards we compute the difference of arrival times between v5 and v7 (deltaT), which is the estimation. VIII 5 Experimental results

Parameters

Experiments were conducted on a computer with Intel Core i7 3.5 GHz processor and algorithms were implemented in C++. In Table 1 there are values of all parameters of proposed evolutionary algorithm. Population size was set to 100 or 30. The first population size (P size = 100) is derived from original OP algorithm, which performed computations on larger networks. The smaller population size (P size = 30) was introduced in order to reduce execution time in smaller TDOP instances. Parameters associated with generations were adjusted to population size -their values allow algorithm to fully converge. The remaining parameters of the algorithm were determined in a process of automatic tuning. The author used Parameters ILS [START_REF] Hutter | ParamILS: an automatic algorithm configuration framework[END_REF] meta-algorithm to calibrate his method. The parameters of evolutionary algorithm were tuned on classic OP calibration instances but proved to be applicable to TDOP instances as well. More details about tuning can be found in one of author's previous papers on the OP [START_REF] Ostrowski | Parameters Tuning of Evolutionary Algorithm for the Orienteering Problem[END_REF].

Test instances

TDOP benchmark instances were introduced by Verbeeck et al [START_REF] Verbeeck | A fast solution method for the time-dependent orienteering problem[END_REF]. These test instances model street traffic. The benchmark authors introduced 7 networks containing 21-102 vertices. Maximum travel times (T max ) were between 5 and 14 hours and all paths started at 7 in the morning in node 1 and ended in last node: N . There are three classes of benchmark networks:

-Class I contains the smallest networks (21-32 vertices). These are original TDOP instances which were solved optimally by benchmark authors. -Class II contains all benchmark networks -they were slightly modified so that optimal results were the same as in static OP network. Details in [START_REF] Verbeeck | A fast solution method for the time-dependent orienteering problem[END_REF]. -Class III instances were developed from previous classes by applying time discretization in order to compare author's algorithm with Gunawan's metaheuristics [START_REF] Gunawan | A Mathematical Model and Metaheuristics for Time Dependent Orienteering Problem[END_REF]. Original start time was 7 am and time limit 14 hours. 1.4 0 0.1 0 0.5 210 21 13 0.9 0 0.1 0 0 425 32 10 1.6 0 0.2 0 0.4 230 33 5.5 0.8 0 0.1 0 4.3 370 32 11 1.6 0 0.2 0 0 250 33 6.5 0.9 0 0.1 0 0 420 32 12 1.8 0 0.2 0 1.9 270 33 7.

Results

The author tested the evolutionary algorithm (EVO) on these instances and compared it to optimal solutions, ant-colony metaheuristic (ACS) [START_REF] Verbeeck | A fast solution method for the time-dependent orienteering problem[END_REF] and Adaptive ILS [START_REF] Gunawan | A Mathematical Model and Metaheuristics for Time Dependent Orienteering Problem[END_REF]. Gaps were expressed in percent and computed as 100 • (1 -res opt ) where res is result obtained by a metaheuristic (average from 30 runs in case of EVO) and opt is profit of optimal solution. Execution time is given in seconds.

In Table 2 results of class I instances are given: performance of two evolutionary algorithm versions (P size of 100 and 30) is presented and compared to ACS and optimal solutions. EVO100 obtains optimal solutions for all test cases and is on average 0.8 percent better than ACS. The biggest obtained gap is over 4 percent. EVO30 is only 0.1 percent worse than EVO100 and is much faster. Only in one case EVO30 is much worse than EVO100 (over 1.5%).

In Table 3 results of class II instances are presented. EVO100 again achieves optimal solutions for most test cases and average gap is close to 0 percent. On average it is 1.4 percent better than ACS and for some instances the difference is more than 5 percent. EVO100 clearly outperforms ACS especially in case of some larger instances. EVO30 is on average only 0.1 percent worse than EVO100 but for some of largest test cases (100-102 nodes) the difference are larger (0.5-1.1 percent). Execution time of proposed methods is also acceptable.

In Table 4 results for class III instances are compared. The proposed method was compared with Gunawan's Adaptive ILS method (which achieved generally the best results among heuristics tested by them). Both versions of EVO are on average 1.7-2 percent better than Adaptive ILS and for most instances achieve optimal results or close to best known solutions (average gap 0.2-0.5 percent). EVO30 performance is generally slightly worse than EVO100 but it is about 1-1.5 percent worse than EVO100 for a few larger networks. Gunawan's heuristics had execution time limit of 1 second (this limit was also used in case of EVO30). 6

Conclusions and further research

The experiments show that proposed evolutionary algorithm with memetic operators is an effective metaheuristic for the Time-Dependent Orienteering Problem (TDOP). The results obtained for TDOP benchmarks by the algorithm are optimal or close to optimal in most cases and are better than those obtained by other metaheuristics. Author's method, which was successfully used to tackle the classic Orienteering Problem (OP), achieved high quality results for TDOP benchmarks as well. Promising results suggest that that proposed method should be adapted to other related problems. Therefore further research will concentrate on application of the algorithm for other problems from OP family i.e. variants with multiple paths (Team OP and Team TDOP) and with time-windows.

1 )Fig. 1 :

 11 Fig.1: Example of 2-point crossover. Given two parents which have 4 common vertices[START_REF] Campbell | The orienteering problem with stochastic travel and service times[END_REF][START_REF] Chao | Theory and methodology -a fast and effective heuristic for the orienteering problem[END_REF][START_REF] Fomin | Approximation algorithms for time-dependent orienteering[END_REF][START_REF] Tsiligirides | Heuristic methods applied to orienteering[END_REF] there are three possible fragment exchanges between successive points. Variant I shows children created by fragments exchange between vertices 16 and 4, variant II is created by segments exchange between points 4 and 9 while variant III shows offspring individuals created by exchange of fragments between vertices 9 and 1.

Fig. 2 :

 2 Fig.2: Estimating travel time of reversed fragment of a path. The path is (v1, v2, ..., v10) and it starts at time t = 0 and ends at time 80. Time was divided into D = 4 equal intervals and all possible vertices in reversed fragments are v9, v8, ... v2. The figure can be treated as 2-dimensional array and in each cell there is a precomputed path fragment visiting a given vertex (determined by column) at a given time interval (determined by row). For example in order to estimate travel time of fragment (v7, v6, v5) starting at time t = 27 we should find an appropriate column (v7) and row (interval 20-40) and route fragment associated with it (pointed by arrow). Afterwards we compute the difference of arrival times between v5 and v7 (deltaT), which is the estimation.

Table 1 :

 1 Parameters of the evolutionary algorithm

	Param. Value	Description	Param. Value	Description
	Psize	100/30	population size	mp	1	mutation probab.
	Ng	5000/1500 max. generations number	cp	1	crossover probab.
	Cg	500/150 max. generations number	dp	0.01	disturb probab.
			without improvement	m h	1	mutation heuristic coeff.
	α	90	max. percentage of	c h	0.8 crossover heuristic coeff.
			infeasible solutions	d h	0,8	disturb heuristic coeff.

Table 2 :

 2 Results for class I instances. N is network size.

	N Tmax	EVO100 EVO30 ACS opt. N Tmax time gap time gap gap result	EVO100 EVO30 ACS opt. time gap time gap gap result
	32 5	0.8 0 0.1 0	0	115 21 9	0.6 0 0.1 1.5 0	260
	32 6	1.0 0 0.1 0	0	135 21 10 0.7 0 0.1 0	0	310
	32 7	1.1 0 0.1 0	0	160 21 11 0.7 0 0.1 0	0	340
	32 8	1.2 0 0.1 0 2.2 185 21 12 0.8 0 0.1 0.2 0	375
	32 9

Table 3 :

 3 Results for class II instances.

	N Tmax	EVO100 EVO30 ACS opt. N Tmax time gap time gap gap result	EVO100 EVO30 ACS opt. time gap time gap gap result
	32 5	0.9 0 0.1 0	0	135 100 5	2.3 0 0.3 0.5 0.8 486
	32 6	1.0 0 0.1 0	0	165 100 6	2.7 0 0.3 0.1 1.7 590
	32 7	1.3 0 0.1 0	0	185 100 7	4.5 0.2 0.4 0.3 2.5 679
	32 8	1.3 0 0.1 0	0	210 100 8	4.0 0 0.5 0.

Acknowledgements

The author is grateful for support from the Polish Ministry of Science and Higher Education at the Bialystok University of Technology (S/WI/1/2014).


Sankhadeep Chatterjee
email: chatterjeesankhadeep.cu@gmail.com

Rhitaban Nag
email: nag.rhitaban@gmail.com

Soumya Sen
email: soumyasen1@acm.org

Amitrajit Sarkar
email: sarkara@cpit.ac.nz

A K Choudhury

Towards Golden Rule of Capital Accumulation: A Genetic Algorithm Approach

Keywords: Accumulated capital, Depreciation rate, Golden rule, Genetic Algorithm, Metaheuristic, Solow model

The current study deals with maximizing consumption per worker in connection with the economic growth of society. The traditional Solow model based approach is well-studied and computationally complex. The present work proposes a Genetic Algorithm (GA) based consumption maximization in attaining the Golden rule. An objective function derived from traditional Solow model based on depreciation rate and amount of accumulated capital is utilized. The current study considered a constant output per worker to incorporate a constant efficiency level of labor. Different ranges of Depreciation rate and accumulated capital are tested to check the stability of the proposed GA based optimization process. The mean error and standard deviation in optimization process is utilized as a performance metric. The experimental results suggested that GA is very fast and is able to produce economically significant result with an average mean error 0.142% and standard deviation 0.021%.

Introduction

Economic growth of society directly impacts economy of a country. Economic growth depends on several factors; one of them is consumption. Thus, consumption maximization is an imperative task to ensure ever growing economic stability. Solow model [START_REF] Mankiw | Principles of macroeconomics[END_REF] deals with the growth of the economy in terms of basic production, investment and depreciation. The steady level of capital plays a vital role in the same. Maximization of consumption is traditionally done by employing a long time consuming and computationally complex Solow model based mathematical approach. Motivated by this, in the current work we consider Genetic Algorithm (GA) to maximize consumption. Typically, the economic problems can be framed as an optimization problem, such as cost minimization, and revenue maximization. Thus, efficient optimization methods are required to deliver accurate results. Consequently, several optimization algorithms can be involved to solve the required maximum profit level, such methods include the genetic algorithm (GA), particle swarm optimization (PSO), firefly algorithm, and cuckoo search algorithm (CS). Several studies have established the ingenuity and accuracy of GA [START_REF] Reeves | A genetic algorithm for flowshop sequencing[END_REF][START_REF] Beasley | A genetic algorithm for the set covering problem[END_REF][START_REF] Orero | Economic dispatch of generators with prohibited operating zones: a genetic algorithm approach[END_REF][START_REF] Shin | A genetic algorithm application in bankruptcy prediction modeling[END_REF]. Generally, the GA has numerous advantages including its flexibility to model the problem's constraints, and its easy convergence to the optimal solution inspired by Darwinian principle [START_REF] Malhotra | Genetic algorithms: Concepts, design for optimization of process controllers[END_REF]. Nicoară [START_REF] Nicoară | Applying Genetic Algorithms to Optimization Problems in Economics[END_REF] revealed about the GA relevance compared to the traditional methods for manufacturing structure optimization. Geisendorf [START_REF] Geisendorf | Genetic algorithms in resource economic models[END_REF] employed the GA to solve Resource Economic problem using two different assumptions to calculate the optimal extraction rate in order to achieve optimal benefits. Arifovic [START_REF] Arifovic | Genetic algorithm learning and the cobweb model[END_REF] solved decision rules of future production and sales by employing the GA in a competitive cobweb model in a market of single product. The simulation results indicated that the GA is capable of capturing different features from the experimental nature of the subjects under consideration.

Riechmann [START_REF] Riechmann | Genetic algorithms and economic evolution[END_REF] established that the GA can be connected with the evolutionary game theory. Hommeset al. [START_REF] Hommes | Genetic Algorithm Learning in a New Keynesian Macroeconomic Setup[END_REF] reveled that GA can converge to a series of near Nash equilibrium solutions, where the heterogeneous agent behavior has been modeled using GA.

The rest of the work is arranged as follows; first in section 2 the basic economic background is introduced and mathematically explained. Next in section 3 the economical steady state is introduced and explained. In section 4 Golden rule of capital based on the Solow model is formulated. The appropriateness of choosing the objective function is mathematically established. Section 5 introduces the GA based proposed method. Section 6 reported the experimental set up of GA and finally, Section 7 reveals experimental results. It discusses the economic significance of the obtained results as well.

Basic Economic Background

The Solow model deals with growth of economy. It includes the living standard of every citizen currently living in the economy. Their living standard depends on various kinds of determinant; one of them is their income. The consumption increases with increasing earning of citizens thereby raising the overall consumption of economy. These results in potential growth in economic systems as the consumption rate of citizens have increased inside that economy. Consequently, consumption turns out to be a major indicator of growth. At maximum consumption rate, economic growth will take place. The golden rule of capital accumulation is a tool which has used to maximize the consumption. Golden rule actually indicates steady state with maximum consumption. The aforesaid formalism is mathematically established using a basic Coubb-Douglaus production function [START_REF] Mankiw | Principles of macroeconomics[END_REF].

𝑄 = 𝑓(𝐿, 𝐾) 𝑄 𝐿 = 𝑓( 𝐿 𝐿 , 𝐾 𝐿 ) 𝑦 = 𝑓(1, 𝑘) 𝑦 = 𝑓(𝑘) (1)
Where,'𝑘' denotes capital per worker,'𝑦' denotes output per worker, '𝑐' is consumption per worker, '𝑖' is investment per worker, '𝑄' is total output, '𝐿' denotes total labor and'𝐾' is total capital. Suppose, a firm earns '𝑦' and saves '𝑠' fraction of '𝑦'. (1 -𝑠) fraction of '𝑦' goes to its consumption. Hence;

𝑐 = (1 -𝑠) * 𝑦 (2)
Where, '𝑦' is income per worker. And the relation between income per worker and consumption is given by;

𝑦 = 𝑐 + 𝑖 (3)
From ( 2) and (3) we get;

𝑦 = (1 -𝑠) * 𝑦 + 𝑖 𝑖 = 𝑠 * 𝑦 𝑖 = 𝑠 * 𝑓(𝑘) (4)
Investment per worker depends on the savings rate of the firm (s). There is a positive relationship between investment per worker and savings rate. As saving rate rises, investment per worker also rises. An increasing savings rate shifts the investment per worker vs. capital per worker curve upward as depicted in Figure 2.

Economical Steady State

From the Figure 4 we depict how the economy approaches the steady level of capital. In Figure 4 we have shown the steady level is at point'𝑀'. Now, to examine whether at point '𝑀' the economy reached steady state level of capital or not we take two points. The first point is point '𝐴'which is below the steady state level. And the second point is point '𝐵' which is above the steady state level. At point '𝐴'it can be observed that the investment curve is steeper than the depreciation, so here investment is greater than the depreciation thus, if investment takes place it would enrich the capital stock which would lead to higher output. The capital increases from the point '𝐴'and moves toward point '𝑀' while in case of the point '𝐵' the depreciation is steeper than the depreciation.If investment takes place it would shrink the capital stock as depreciation is far greater than the investment. Thus, the level of capital will move downward to the point'𝑀'.

Golden Rule level of Capital

After achieving the steady state level of capital, there is a state where we maximize the consumption per worker that is generally known as the Golden rule level of capital [START_REF] Mankiw | Principles of macroeconomics[END_REF][START_REF] De | On the Golden Rule of capital accumulation under endogenous longevity[END_REF]. The Golden rule addresses the question of presence of any growth in an economy. There are many factors which decide the growth of an economy. The current study focuses on the consumption. Maximization of consumption is an imperative task in order to achieve economic growth. The Golden rule of capital indicates a state (a unique value of depreciation rate and amount of capital accumulated) that ensures maximum consumption level, thereby assures a strong economic growth [START_REF] De | On the Golden Rule of capital accumulation under endogenous longevity[END_REF].

From equation 3 and 5 we get; At maxima we have;

𝑐 = 𝑦 -𝑖 (6)
𝑑𝑐 𝑑𝑘 * = 0 𝑓 ′ (𝑘 * ) -𝛿 = 0 𝑓 ′ (𝑘 * ) = 𝛿 𝑀𝑃 𝑘 = 𝛿 (8)
Change in output due to one unit increase of capital is called the marginal product of capital and is denoted as 𝑀𝑃 𝑘 . In Figure 1 output per worker vs. capital curve has already been described. The slope of this curve is 𝑑𝑦 𝑑𝑘 which is denoted by 𝑀𝑃 𝑘 . Initial condition to achieve the Golden rule level of capital is; marginal product of capital should be equals to depreciation rate. To decide if the Golden rule of capital is steady or not; we consider two different cases.

i. Case 1

𝑀𝑃 𝑘 -𝛿 < 0

Where, if one unit of capital is added, output will increase less than the depreciation. If level of capital is increased consumption will fall.

ii. Case 2

𝑀𝑃 𝑘 -𝛿 > 0
Where, if one unit of capital is added, output will increase more than the depreciation. If level of capital is increased consumption will rise.As none of Case 1 and 2 produces a steady state hence, equation 8 is only condition satisfy Golden rule level of capital.

Genetic Algorithm based methodology

The GA is a parallel optimization procedure that relies on evolution for optimizing a group of solutions at once [START_REF] Goldberg | Genetic algorithms and machine learning[END_REF]. The model is highly inspired from Darwinian principle of Natural Evolution, and involves a population which participates in finding the solution of a particular problem under consideration. In the proposed work, the GA is applied to determine the optimal consumption value, where the GA proves its effectiveness for superior convergence toward global optimization compared to other global search algorithm. The overall GA algorithm is as follows [START_REF] Malhotra | Genetic algorithms: Concepts, design for optimization of process controllers[END_REF] mentioning types of different operators. Each chromosome represents a potential solution in mating pool. The chromosome representation considered in the current study is as follows; A binary coded chromosome representation technique is adapted. The chromosome has two major parts. The first part depicts 𝛿 (depreciation rate) and the next part depicts 𝑘 * (amount of capital accumulated). The chromosome representation is depicted in Figure 6. Each part is numerically a sequence of binary digits. The length of each such part is 𝑛. The length depends on the search range of the corresponding variable. As reported in the preceding algorithm, it is clear that each member of the population represents a potential solution of the problem under concern. Further, each of them is associated with a fitness value indicating the superiority of that particular solution. The fitness value is calculated by following equation 7 described in section 4.

Solutions at any stage participate in Darwinian reproduction, survival of the fittest and other genetic operations to produce successors. The GA tries to find out the best solution at every generation by breeding the best solutions from the previous generation. The candidate solutions under consideration are actually artificial chromosomes which are inspired from the DNA structure. In practice, these chromosomes have fixed length strings (binary/real coded), where each location (gene) holds information about one of the variables associated in the problem. In the current study real coded fixed length formalism is utilized. Each chromosome has two different components one depicting 𝛿 (Depreciation rate) and another is 𝑘 * (amount of capital accumulated). The range of each of the components varies from context to context [START_REF] De | On the Golden Rule of capital accumulation under endogenous longevity[END_REF].

GA the population (initially random) by applying genetic operators already defined to generate new solutions from them. The genetic operators such as crossover, mutation and several other versions of these two are popular [START_REF] Walters | Genetic algorithm solution of economic dispatch with valve point loading[END_REF][START_REF] Azadeh | A new genetic algorithm approach for optimizing bidding strategy viewpoint of profit maximization of a generation company[END_REF].Crossover can be of different types; broadly Single point or multi point. The current study used a single point crossover [START_REF] Chatterjee | Forest Type Classification: A Hybrid NN-GA Model Based Approach[END_REF] method. A Gaussian type mutation strat-egy is adopted [START_REF] Hore | Indian Sign Language Recognition Using Optimized Neural Networks[END_REF] and employed. The probability value of mutation is determined by a simple trial and error method and is described in next section. Based on the preceding genetic algorithm procedure, Figure 7 demonstrated the proposed approach for consumption maximization in achieving Golden rule of capital accumulation using the GA.

Results & Discussion

The experiments are carried out using Intel Core i3 4GB Machine. A real coded Genetic algorithm is implemented using the algorithmic set up which are obtained by running the GA 100 times with different parameters and is described in Table 1. Depending on the difficulty of the problem being solved the initial size of population is set to 200 and maximum number of generation is set to 500. The selection procedure during iteration is Roulette. Single point cross over strategy is adopted with a crossover probability of 0.15 which indicates that a significantly low probability would be sufficient to ensure the better quality population, while it is kept low in order to prevent the process from being trapped in local optima. The solution generated by the proposed system is a pair of values consisting 𝛿 (depreciation rate) and 𝑘 * (amount of capital accumulated) with in the given range of search. The output is approximate a point in search space for which the objective function is highly close to global optima. The experiments are run for 50 times for each set up of input ranges and the best results are reported. The objective function is already described and explained in section 4 (equation 7). 𝑓(𝑘 * ) denotes output per worker. This is kept constant to ensure constant efficiency level of labor [START_REF] De | On the Golden Rule of capital accumulation under endogenous longevity[END_REF] and in the current study this is set to 2000. 𝛿 denotes depreciation rate and 𝑘 * denotes amount of capital accumulated.

Experimental results

Table 2 reports the performance of Genetic Algorithm. Performance analysis is done using the Mean Error and Standard Deviation. The results are tabulated in form mean error (%) ± standard deviation (%). Different ranges of 𝛿 and 𝑘 is used. The ranges are written in form [𝑙𝑜𝑤𝑒𝑟 𝑏𝑜𝑢𝑛𝑑, 𝑢𝑝𝑝𝑒𝑟 𝑏𝑜𝑢𝑛𝑑]. As suggested in [START_REF] Mankiw | Principles of macroeconomics[END_REF] the range of 𝛿 is kept low and 𝑘 is kept high. The mean error for ranges [0.01,0.1], [START_REF] Reeves | A genetic algorithm for flowshop sequencing[END_REF]1000] of 𝛿 and 𝑘respectively the mean error is 0.257% and standard deviation is 0.005%.Next for ranges [0.1,0.9] and [START_REF] Reeves | A genetic algorithm for flowshop sequencing[END_REF]1000] the achieved mean error and standard deviation are 0.192% and 0.043% respectively. The average of these different set up is reported as well. Average mean error achieved is 0.142% and standard deviation is 0.021%. 8 depicts a similar plot with ranges [0.1, 0.9] and [START_REF] Reeves | A genetic algorithm for flowshop sequencing[END_REF]1000] of 𝛿 and 𝑘 respectively. It took 54 iterations to converge.The plots reveal that GA is extremely fast in maximizing the objective function and is better than traditional methods [START_REF] De | On the Golden Rule of capital accumulation under endogenous longevity[END_REF] because these involve calculation of mathematical differentiation of complex functions and is proved to be NP -Hard (exponential complexity) [START_REF] Kaltofen | Computational differentiation and algebraic complexity theory[END_REF]. GA is faster as it takes polynomial time to converge [START_REF] Orero | Economic dispatch of generators with prohibited operating zones: a genetic algorithm approach[END_REF][START_REF] Shin | A genetic algorithm application in bankruptcy prediction modeling[END_REF]. This is supported by the experimental results and it establishes that GA based method to be faster than traditional method as well.

Economic Significance

The results obtained by Genetic algorithm are economically significant. The optimum results indicated that in maximizing the consumption per worker the value of depreciation rate (𝛿) tends to the lower bound of the given range which indicates a lower depreciation rate. From economical point of view lower depreciation rate is expected [START_REF] Mankiw | Principles of macroeconomics[END_REF] and in addition the capital accumulation tends to the higher bound of given range that indicates an increased accumulated capital that is equally significant [START_REF] De | On the Golden Rule of capital accumulation under endogenous longevity[END_REF].

Conclusion

Economic growth takes a vital role in sustainable development of a society and impacts the economic stability of a country to a greater extent. The current study considered the consumption maximization problem which is a major factor in economic growth. The traditional Solow model based approach is time consuming and computationally complex due to high involvement of mathematical operations and is proved to be NP-Hard. In the current study a wellknown Darwinian principle inspired metaheuristic Genetic Algorithm is employed in maximizing the consumption (The Golden rule of capital accumulation) in terms of depreciation and capital accumulation. Experimental results have indicated that the proposed GA based method is highly fast and produces economically significant results in achieving the Golden rule of capital accumulation.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .Figure 3

 12343 Fig. 1.Capital per worker vs. output per worker curve Fig. 2.Combining output per worker and investment per worker curve. Where, 𝑠𝑓(𝑘) denotes investment per worker curve

Fig. 5 .

 5 Fig. 5.Golden rule level of capital accumulation. At point '𝑐'𝑀𝑃 𝑘 = 𝛿 which indicates that the rate of change of output with respect to capital (𝑀𝑃 𝑘 ) is equal to the slope of the depreciation line. Thus it is achieving the Golden rule of capital accumulation.

Fig. 6 .

 6 Fig. 6.Chromosome representation of Genetic algorithm

Fig. 7 .

 7 Fig. 7.The profit maximization process using Genetic Algorithm

Fig. 8 .

 8 Fig. 8.GA convergence plot with ranges of 𝛿 and 𝑘being [0.01-0.1] and [1-1000]

Fig. 9 .

 9 Fig.9.GA convergence plot with ranges of 𝛿 and 𝑘being [0.1-0.9] and

Table 1 .

 1 Genetic algorithm setup for consumption maximization

	Size of Population	200
	Maximum number of generation	500
	Type of Selection	Roulette

Table 2 .

 2 Performance analysis of GA

	Range of 𝜹	Range of 𝒌 *	Mean Error (%) ±Standard Deviation (%)
	[0.01, 0.1]	[1, 1000]	0.257% ± 0.005%
	[0.1, 0.9]	[1, 1000]	0.192% ± 0.043%
	[0.25, 1]	[250, 750]	0.048% ± 0.003%
	[0.01, 0.9]	[250, 850]	0.072% ± 0.036%
		Average	𝟎. 𝟏𝟒𝟐% ± 𝟎. 𝟎𝟐𝟏%
	Figure 8 depicts the convergence graph of Genetic Algorithm for ranges of 𝛿
	and 𝑘 [0.01, 0.1] and [1, 1000] respectively. GA took 52 iterations to converge.
	Figure


Katarzyna Borowska
email: k.borowska@pb.edu.pl

Jaros Law Stepaniuk
email: j.stepaniuk@pb.edu.pl

Rough Sets in Imbalanced Data Problem: Improving Re-sampling Process

Keywords: Data preprocessing, Class imbalance, Rough Sets, SMOTE, Oversampling, Undersampling

Imbalanced data problem is still one of the most interesting and important research subjects. The latest experiments and detailed analysis revealed that not only the underrepresented classes are the main cause of performance loss in machine learning process, but also the inherent complex characteristics of data. The list of discovered significant difficulty factors consists of the phenomena like class overlapping, decomposition of the minority class, presence of noise and outliers. Although there are numerous solutions proposed, it is still unclear how to deal with all of these issues together and correctly evaluate the class distribution to select a proper treatment (especially considering the real-world applications where levels of uncertainty are eminently high). Since applying rough sets theory to the imbalanced data learning problem could be a promising research direction, the improved re-sampling approach combining selective preprocessing and editing techniques is introduced in this paper. The novel technique allows both qualitative and quantitative data handling.

Introduction

With the growing interest of knowledge researchers and increasing number of proposed solutions, the imbalanced data problem becomes one of the most significant and challenging issues of the last years. The main reason of this particular attention given to the underrepresented data is the fundamental importance of untypical instances. Considering medical diagnosis, it is obvious that the cost of not recognizing patient that suffers from a rare disease might lead to serious and irreversible consequences. Apart from this example, there are numerous domains in which imbalanced class distribution occurs, such as [START_REF] Napiera La | Types of minority class examples and their influence on learning classifiers from imbalanced data[END_REF], [START_REF] Stefanowski | Dealing with Data Difficulty Factors While Learning from Imbalanced Data[END_REF], [START_REF] Weiss | Mining with Rarity: A Unifying Framework[END_REF]: fraudulent credit card transactions, detecting oil spills from satellite images, network intrusion detection, financial risk analysis, text categorization and information filtering. Indeed, the wide range of problem occurrences increases its significance and explains the efforts put into finding effective solution.

Initially, the major cause of the classifier performance depletion was merely identified with not sufficient number of examples representing minority data. However, recent comprehensive studies carried on the nature of imbalanced data revealed that there are other factors contributing to this undesirable effects [START_REF] Galar | A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches[END_REF], [START_REF] Napiera La | Types of minority class examples and their influence on learning classifiers from imbalanced data[END_REF], [START_REF] Stefanowski | Dealing with Data Difficulty Factors While Learning from Imbalanced Data[END_REF]. Small disjuncts [START_REF] Japkowicz | Class imbalances versus small disjuncts[END_REF], class overlapping [START_REF] Napiera La | Learning from imbalanced data in presence of noisy and borderline examples[END_REF] and presence of noise as well as outliers [START_REF] Weiss | Mining with Rarity: A Unifying Framework[END_REF] were especially considered as the most meaningful difficulties. Despite lots of suggested solutions (discussed briefly in the next section), there are still many open issues, particularly regarding the flexibility of proposed methods and tuning their parameters. We decided to focus on the data-level approach as it is classifier-independent and therefore more universal. However, it is worth to mention that besides this kind of concept, there are also numerous algorithm-level and cost-sensitive methods [START_REF] He | Learning from Imbalanced Data[END_REF].

Although many re-sampling methods were proposed to deal with imbalanced data problem, only few incorporate the rough set theory. The standard rough sets approach was developed by Pawlak (1926Pawlak ( -2006) ) in 1982 [START_REF] Pawlak | Rough Sets[END_REF]. Objects characterized by the same information (identical values of the provided attributes) are treated as indiscernible instances [START_REF] Pawlak | Rough sets: Some extensions[END_REF], [START_REF] Pawlak | Rudiments of Rough Sets[END_REF], [START_REF] Stepaniuk | Rough-Granular Computing in Knowledge Discovery and Data Mining[END_REF]. Hence, the idea of indiscernibility relation is introduced. Since the real-life problems are often vague and contains inconsistent information, the rough (not precise) set concept can be replaced by a pair of precise concepts, namely the lower and upper approximations. We claim that this methodology could be very useful both in preprocessing step and cleaning phase of the algorithm (see [START_REF] Borowska | Imbalanced Data Classification: A Novel Re-sampling Approach Combining Versatile Improved SMOTE and Rough Sets[END_REF]). Especially the extended version, which allows the continuous values of attributes by involving the similarity relation. Therefore, we propose the adjusted VIS RST algorithm, dedicated for both qualitative and quantitative data. What is more, new mechanisms for careful oversampling are introduced.

Related works

In this paper we focus only on the data-level methods addressing imbalanced data problem, as it was declared in the previous section. This category consists of classifier-independent solutions which transform the original data set into less complex and more balanced distribution using techniques such as oversampling and undersampling [START_REF] He | Learning from Imbalanced Data[END_REF], [START_REF] Stefanowski | Dealing with Data Difficulty Factors While Learning from Imbalanced Data[END_REF]. The major algorithm representing this mentioned group is Synthetic Minority Oversampling Technique [START_REF] Chawla | SMOTE: synthetic minority over-sampling technique[END_REF]. Since the approach of generating new minority samples based on the similarities between existing minority examples became very successful and powerful method, it was an excellent inspiration for researchers to develop numerous extensions and improvements. Some of them properly reduce the consequences of SMOTE drawbacks, such as over-generalization and variance [START_REF] He | Learning from Imbalanced Data[END_REF]. Preparing the overview of related techniques, two main subjects were considered. Firstly, methods which handle additional difficulty factors are discussed. Secondly, we show the applications of rough set notions in imbalance data problem.

SMOTE-based methods dealing with complex imbalanced data distribution

Highly imbalanced datasets, especially characterized by the complex distribution, require dedicated methods. Even such groundbreaking algorithm as SMOTE turns out as insufficiently effective in some specific domains. Indeed, the most recent researches revealed that technique of dividing minority data into some categories that reflect their local characteristics is a proper direction of development. The main reason of this conclusion is the nature of real-world data.

Assuming that minority class instances placed in relatively homogeneous regions of feature space are named safe, we should consider the fact that these safe examples are uncommon in real-life data sets [START_REF] Stefanowski | Dealing with Data Difficulty Factors While Learning from Imbalanced Data[END_REF]. In order to deal with complex imbalanced data distributions, many sophisticated methods were proposed:

-MSMOTE (Modified Synthetic Minority Oversampling Technique) [START_REF] Hu | MSMOTE: Improving Classification Performance When Training Data is Imbalanced[END_REF] [START_REF] Bunkhumpornpat | Safe-Level-SMOTE: Safe-Level-Synthetic Minority Over-Sampling TEchnique for Handling the Class Imbalanced Problem[END_REF] -the algorithm applies k-NN technique to obtain the safe levels of minority class samples. New synthetic instances are created only in safe regions in order to improve prediction performance of classifiers.

Rough sets solutions for imbalanced data problem

The occurrence of noisy and borderline examples in real-domain data sets is the fact that need to be be acknowledged in most cases. Hence, the relevancy of methods dealing with these additional difficulties should be emphasized. The rough set notions appears as a promising approach to reduce data distribution complexity and understand hidden patterns in data. Before describing existing algorithms based on the rough sets approach, basic concepts of this theory are introduced.

Let U denote a finite non-empty set of objects, to be called the universe. The fundamental assumption of the rough set approach is that objects from a the lower approximation of a set X is the set of all objects that can be certainly classified as members of X with respect to IN D :

{x ∈ U : [x] IN D ⊆ X}, (1)
the boundary region of a set X is the set of all objects that are possibly members of X with respect to IN D :

{x ∈ U : [x] IN D ∩ X ̸ = ∅ &[x] IN D X}. ( 2
)
The most known preprocessing methods directly utilizing the rough set theory are the following:

filtering techniques (relabel and remove) [START_REF] Stefanowski | Rough Sets for Handling Imbalanced Data: Combining Filtering and Rule-based Classifiers[END_REF] -depending on the method:

majority class examples belonging to the boundary region (defined by the rough sets) are either relabeled or removed, -SMOTE-RSB * [START_REF] Ramentol | SMOTE-RSB * : a hybrid preprocessing approach based on oversampling and undersampling for high imbalanced data-sets using SMOTE and rough sets theory[END_REF] -method combining SMOTE algorithm with rough set theory by introducing additional cleaning phase of processing.

Proposed Algorithm VISROT -Versatile Improved SMOTE Based on Rough Set Theory

Comprehensive studies on imbalanced data problem and analysis of foregoing solutions revealed that there are many open issues and the need of more general approach dealing with wide range of different data characteristics is still actual [START_REF] Stefanowski | Dealing with Data Difficulty Factors While Learning from Imbalanced Data[END_REF]. Since most of the real-world data sets have complex distribution, researchers should pay particular attention to careful assortment of oversamping strategy [START_REF] Napiera La | Types of minority class examples and their influence on learning classifiers from imbalanced data[END_REF]. In [START_REF] Saez | SMOTEIPF: Addressing the noisy and borderline examples problem in imbalanced classification by a re-sampling method with filtering[END_REF] two main types of SMOTE-based preprocessing algorithms are specified:

change-direction methods -new instances are created only in specific areas of the input space (especially close to relatively large positive examples clusters) filtering-based techniques -SMOTE algorithm integrated with additional cleaning and filtering methods that aim to create more regular class boundaries.

The authors of this categorization claim that the first group may suffer from noisy and borderline instances. The necessity of additional cleaning phase was indicated. Since our VIS RST [START_REF] Borowska | Imbalanced Data Classification: A Novel Re-sampling Approach Combining Versatile Improved SMOTE and Rough Sets[END_REF] algorithm meets this requirement, but it is not directly suitable for quantitative data, we decided to improve the existing approach and enable processing of any attributes' types.

The code generalization for both qualitative and quantitative data involved many adjustments and handling specific cases. The main modification concerns usage of weaker similarity concept instead of the strict indiscernibility relation [START_REF] Krawiec | Learning Decision Rules from Similarity Based Rough Approximations, Rough Sets in Knowledge Discovery 2[END_REF]. We applied the HVDM distance metrics [START_REF] Wilson | Improved heterogeneous distance functions[END_REF] as a generator of similarity measure.

The algorithm flexibility is obtained by two approaches dedicated to different types of problems. Analysis of local neighbourhood of each example enables to evaluate the complexity of data distribution. Based on the studies from [START_REF] Napiera La | Learning from imbalanced data in presence of noisy and borderline examples[END_REF] we assume that the occurrence of 30% of borderline and noisy instances indicates that the problem is difficult. Identification of these specific examples is performed by applying the k-NN algorithm. Continuing the categorization introduced in VIS algorithm [START_REF] Borowska | New Data Level Approach for Imbalanced Data Classification Improvement[END_REF], we distinguish between three types of objects, namely SAFE, DANGER and NOISE. SAFE examples are relatively easy to recognize, they are main representatives of minority class. DANGER instances are placed in the area surrounding class boundaries, they typically overlap with majority class examples. NOISE instances are rare, probably incorrect, individuals located in areas occupied by the majority class objects. The mechanism of categorization into mentioned groups is described below.

Let DT = (U, A ∪ {d}) be a decision table, where U is a non-empty set of objects, A is a set of condition attributes and d is a decision attribute and V d = {+, -}. The following rules enable labeling minority data X d=+ = {x ∈ U : d(x) = +}: Definition 1. Let k > 0 be a given natural number. Let x ∈ X d=+ be an object from minority class. We define Label : X d=+ → {N OISE, DAN GER, SAF E} as follows: Omitting NOISE examples in oversampling phase is explained by the idea of keeping data distribution complexity as low as possible. Generating new synthetic samples by utilisation of objects surrounded only by the majority class representatives may introduce more inconsistencies. However, there is no guarantee that objects labeled as NOISE are truly effects of errors or they are only outliers which are untypical since no other similar objects are provided in the imbalanced data set [START_REF] Stefanowski | Dealing with Data Difficulty Factors While Learning from Imbalanced Data[END_REF]. Hence, we do not remove any of these instances, but we also do not create new examples similar to them.

-Label(x) = N OISE if
Even when examples considered as noise are excluded from the oversampling process, generating new samples by combining features of two chosen instances still may contribute to creation of noisy examples. Thus some filtering and cleaning mechanisms are advisable [START_REF] Saez | SMOTEIPF: Addressing the noisy and borderline examples problem in imbalanced classification by a re-sampling method with filtering[END_REF]. In order to resolve problem of introducing additional inconsistencies we propose the technique of supervise preprocessing. The main idea of this approach is based on the lower approximation. After obtaining the threshold, algorithm identifies newly created objects that do not belong to the lower approximation of the minority class. The correctness of each element is obtained iteratively (by means of similarity relation rather than the strict indiscernibility relation). The expected proper number of new samples is assured by the increased limit of generated objects. The proposed solution consists of steps described in provided algorithm. Step IV: Obtain the threshold (t) that enable to evaluate which minority instances belong to the lower approximation. The threshold is established by the analysis of the average objects distance. It is set to 0.25 of calculated average distance. 12: Step V: Compute the number of required minority class instances to even classes' cardinalities (N variable). The expected result should be increased by the 30%. Save the obtained number in redundN variable. 13: Step VI: Over-sampling. Generate redundN minority instances considering rules specified in Definitions 2, 3 and 4. Save the result in syntheticSamples list. Randomize the order of new elements stored in list. 14:

Algorithm

Step VII: From newly created minority examples (syntheticSamples) select N elements belonging to the lower approximation of minority class and add them to the DT balanced . Assume that all objects that are insufficiently far apart from the majority class instances (their distance from any negative object is less than calculated threshold t) should not be included in the DT balanced , since they belong to the rough set boundary region.

Generating redundant instances in

Step VI protects from filtering out too many positive synthetic samples in cleaning phase. The method of determining additional objects number should be evaluated in the further research -the impact on the computing performance need to be especially investigated. We suggest that this number should be related to the complexity of the considered specific problem.

Experiments

The results of experimental study are presented in this section. We decided to compare our algorithm with five oversampling methods considered as successful in many domains. All of these techniques are described in section 2. Widely used C4.5 decision tree was chosen as a classifier, since it is one of the most effective data-mining methods [START_REF] Galar | A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches[END_REF]. Very important parameter of k-NN processing, namely k, was set to 5 as it was proven that this is the most suitable value for wide range of problems [START_REF] Garca | On the k-NN performance in a challenging scenario of imbalance and overlapping[END_REF]. The HVDM metric was applied to measure the distances between objects, because it properly handles both quantitative and qualitative data [START_REF] Wilson | Improved heterogeneous distance functions[END_REF].

Six data sets were selected to perform described experiments. They are highly-imbalanced real-life data sets obtained from the UCI repository [START_REF]UC Irvine Machine Learning Repository[END_REF]. All of them were firstly divided into training and test partitions to ensure that the results of fivefolds cross-validation would be correct. We used partitioned data available in the KEEL website [START_REF] Alcala-Fdez | KEEL Data-Mining Software Tool: Data Set Repository, Integration of Algorithms and Experimental Analysis Framework[END_REF]. The analyzed data sets are presented in table 1. The existence of boundary region defined by the rough set notions is emphasized to verify the impact of data inconsistencies on the classifier performance preceded by the particular preprocessing techniques.

Table 2 presents the results of experiments. The area under the ROC curve (AUC) was used to evaluate classifier performance. This measure discloses the dependency between sensitivity (percentage of positive instances correctly classified) and percentage of negative examples misclassified.

VISROT algorithm introduced in this paper was evaluated in comparison with five other preprocessing techniques which performance was measured in [START_REF] Ramentol | SMOTE-RSB * : a hybrid preprocessing approach based on oversampling and undersampling for high imbalanced data-sets using SMOTE and rough sets theory[END_REF]. The results revealed that proposed method outperforms other algorithms in two cases (glass5, ecoli01 vs 5), one of whom has non-empty boundary region. For two data sets VISTROT has similar result as the most effective techniques. In the remaining two cases applying VISROT approach was slightly less beneficial than SMOTE and SMOTE-ENN or Safe-Level SMOTE and SMOTE-RSB * . The experiments proved that the proposed algorithm is suitable to deal with real-life complex data distributions, even highly-imbalanced.

Conclusions and future research

In this paper we introduced new preprocessing method dedicated to both quantitative and qualitative attributes in imbalanced data problems. The described approach considers significant difficulties that lead to the misclassification of many minority class samples. Since not enough number of examples representing positive class is not the main reason of performance depletion, other factors were also considered. Especially occurrence of sub-regions, noise and class overlapping were examined as they indicates the high data complexity. Performed experiments confirms that oversampling preceded by the analysis of local neighborhood of positive instances is proper approach. Moreover, the need of additional cleaning step that removes the inconsistencies is emphasized. The VIS-ROT results showed that rough set notions can be successfully applied to the imbalanced data problems.

We suggest that proposed algorithm should be adjusted to handle Big Data problems in future research. The values of minimal allowed distance defining weaken low approximation rule (threshold) can also be investigated.

  set U described by the same information are indiscernible. This main concept is source of the notion referred as indiscernibility relation IN D ⊆ U × U , defined on the set U . The indiscernibility relation IN D is an equivalence relation on U. As such, it induces a partition of U into indiscernibility classes. Let [x] IN D = {y ∈ U : (x, y) ∈ IN D} be an indiscernibility class, where x ∈ U . For any subset X of the set U it is possible to prepare the following characteristics [18]:

VISROTINPUT: 2 : 3 :

 23 All instances from both classes defined as DT = (U, A ∪ {d}); Number of minority class samples M = card({x ∈ U : d(x) = +}) > 0; Number of nearest neighbors k ≥ 3. OUTPUT: DT balanced : minority and majority class instances after preprocessing. 1: Step I: Compare feature values of minority and majority instances. Remove all negative objects (d = -) identical to the positive (d = +) ones regarding all attributes. Step II: Calculate the HVDM (HeterogeneousV alueDistanceM etric) distance between each minority class example and every instance from majority class. Use k -N N algorithm. Assign positive objects into categories (namely SAFE, DAN-GER and NOISE) considering rules specified in definition 1. Save numbers of instances belonging to each group (variables: saf eN , dangerN , noiseN ). Step III: Select the strategy of processing utilizing the accomplished categorization as follows: 4: if saf eN == 0 then 5: mode := noSAF E 6: else if dangerN 0.3 • M then 7: mode := HighComplexity 8: else 9: mode := LowComplexity 10: end if 11:

  The explained approach involves three modes of processing of DT . None of them creates new samples using NOISE examples. The first one is defined below:

	-SAFE: assuming that these concentrated instances provide specific and easy
	to learn patterns that enable proper recognition of minority samples, a plenty
	of new data is created by interpolation between SAFE object and one of its
	k nearest neighbors. Nominal attributes are determined by majority vote of
	k nearest neighbors' features.
	The second option is applied when most of examples belong to the relatively
	homogeneous areas:
	Definition 3. LowComplexity mode: DT -→ DT balanced
	-DANGER: the most of synthetic samples are generated in these borderline
	areas, since numerous majority class representatives may have greater im-
	pact on the classifier learning, when there are not enough minority examples.
	Hence, many new examples are created closer to the object under consider-
	Definition 2. HighComplexity mode: DT -→ DT balanced
	-DANGER: the number of objects is doubled by creating one new example
	along the line segment between half of the distance from DANGER object
	and one of its k nearest neighbors. For nominal attributes values describing
	the object under consideration are replicated,

and only if all of the k nearest neighbors of x represent the majority class X d=-= {x ∈ U : d(x) = -}, -Label(x) = DAN GER if and only if half or more than half of the k nearest neighbors of x belong to the majority class X d=-or the nearest neighbour of x is majority class representative, -Label(x) = SAF E if and only if more than half of the k nearest neighbors represent the same class as the example under consideration and the nearest neighbour of x is minority class representative. ation. One of the k nearest neighbor is chosen for each new sample when determining the value of numeric feature. Values of nominal attributes are obtained by the majority vote of k nearest neighbors' features, -SAFE: there is no need to increase significantly the number of instances in these safe areas. Only one new object per existing minority SAFE instance is generated. Numeric attributes are handled by the interpolation with one of the k nearest neighbors. For the nominal features, new sample has the same values of attributes as the object under consideration. The third option is specified as follows: Definition 4. noSAFE mode: DT -→ DT balanced -DANGER: all of the synthetic objects are created in the area surrounding class boundaries. This particular solution is selected in case especially complex data distribution, whoch do not include any SAFE samples. Missing SAFE elements indicates that most of the examples are labeled as DAN-GER (there are no homogeneous regions). Since only DANGER and NOISE examples are available, only generating new instances in neighborhood of DANGER objects would provide sufficient number of minority samples.

Table 1 .

 1 Characteristics of evaluated data sets

	dataset	objects attributes IR boundary region
	glass-0-1-6 vs 5	184	9	19.44	empty
	ecoli-0-1-3-7 vs 2-6	281	7	39.14	nonempty
	glass5	214	9	22.78	empty
	ecoli-0-1 vs 5	240	6	11	nonempty
	led7digit-0-2-4-5-6-7-8-9 vs 1 443	7	10.97	nonempty
	ecoli-0-1-4-6 vs 5	280	6	13	nonempty

Table 2 .

 2 Classification results for the selected UCI datasets -comparison of proposed algorithm VISROT with five other techniques and classification without preprocessing step (noPRE).

	dataset	noPRE SMOTE S-ENN Border-S SafeL-S S-RSB * VISROT
	glass016 vs 5	0.8943 0.8129 0.8743 0.8386 0.8429 0.8800 0.8943
	ecoli0137 vs 2-6	0.7481 0.8136 0.8209 0.8445 0.8118 0.8445 0.8445
	glass5	0.8976 0.8829 0.7756 0.8854 0.8939 0.9232 0.9951
	ecoli01 vs 5	0.8159 0.7977 0.8250 0.8318 0.8568 0.7818 0.8636
	led7digit02456789 vs 1 0.8788 0.8908 0.8379 0.8908 0.9023 0.9019 0.8918
	ecoli0146 vs 5	0.7885 0.8981 0.8981 0.7558 0.8519 0.8231 0.8366

Acknowledgements

This research was supported by the grant S/WI/3/2013 of the Polish Ministry of Science and Higher Education.