Jawad Ali
email: jawad.ali@nwfpuet.edu.pk

Gul Muhammad Khan

Sahibzada Ali Mahmud
email: sahibzada.mahmud@nwfpuet.edu.pk

Enhancing Growth Curve Approach using CGPANN for Predicting the Sustainability of New Food Products

Keywords: Growth curve approach, Cartesian Genetic Programming (CGP), Artificial Neural Network (ANN), Product sustainability

An enhancement to the growth curve approach based on neuro evolution is proposed to develop various forecasting models to investigate the state and worth of the producer, to market a new product. The forecasting model is obtained using a newly introduced neuro evolutionary approach called Cartesian Genetic Programming based ANN (CGPANN). CGPANN helps in obtaining an optimum model for all the necessary parameters of an ANN. An accurate and computationally efficient model is obtained, achieving an accuracy as high as 93.37% on the time devised terrains, providing a general mechanism for forecasting models in mathematical agreement to its application in econometrics. Comparison with other contemporary model evidences the perfection of the proposed model thus its vital power in developing the growth curve approach for predicting the sustainability of new products.

Introduction

Marketing a product needs knowledge about the anticipation of the end user and forecasts make it possible to respond to these changes. Different types of forecasts are made in order to mend the stability of a firm in the market including: demand forecast, supply forecast, sales forecast, production forecast, profit forecast, advertisement and promotional expense forecast.

Food products are always in the phase of innovation so that the user remains adhered to the products of a specific company. It is the job of a food company to know the exact limits of demand for a new product before its commissioning, machinery planting and management of other capital resources [START_REF] Kempf | Uzsoy: Planning production and inventories in the extended enterprise[END_REF]. Trends in the previous products and their variation in different ingredients results a timely development or evolution of new products. Firms having past experience and marketing setup therefore always keep using previous knowledge for establishing a new product, that is a resultant of some alteration in the present or previously developed product(s).

Data from the previous products that correlates the developing products is of great importance while dealing demand forecast. Without proper formulation of the past facts, the theories constituted for product forecast are meaningless 1 . Economists use different traditions strategies and probabilistic models to evaluate the core consumption of a product before its initiation [START_REF] Brownstonel | Forecasting new product penetration with flexible substitution patterns[END_REF][START_REF] Cardell | Measuring the societal impacts of automobile downsizing[END_REF] . The general concept of economists circle around one point that is the net income from a product which is to be commercialized [START_REF] Kaastra | Forecasting futures trading volume using neural networks[END_REF]. So the financial market can be studied completely by its two major aspects: fundamental and technical analysis. The fundamental analysis involves the study of economic factors of the product on a firm, while the technical analysis has to do with the future worth of a product and its sustainability. Joel Dean [START_REF] Dean | Demand forecasting for a new product[END_REF] has explained the achievement of these two goals in a six point formula by exploring evolutionary approach, substitution approach, opinion poll approach, sales experience approach, growth curve approach and vicarious approach. This paper is using the growth curve approach [START_REF] Dean | Demand forecasting for a new product[END_REF] for the prediction of the sustainability of new products. The uniqueness in the work is that the growth curve of the future sales and stock is used for the prediction of the sustainability of the product by utilizing a neuro evolutionary approach of Cartesian Genetic programming evolved ANN (CGPANN). The paper is organized in the following manner. Section 2 provides an overview of the past work done in the field. It explains factors involved in product design and prior marketing steps. Section 3 gives an insight of the basic strategies followed in the development and commercialization of market products whereas section 4 covers the concept of CGP evolved ANN and their implementation mechanism. The Experiments, Results confirmed by the experiments and concluding remarks are added in later sections of the paper.

Literature Review

Expected future market of products and financial time series forecasting has been explored in the past using various methods including econometric, statistical, probabilistic, expert systems and various other ANN based techniques. The most popular econometric model is the logit model [START_REF] Mcfadden | Conditional logit analysis of qualitative choice behavior[END_REF], based on qualitative analysis of the product. Mixed logit with repeated choices that is an extension of the logit model dealing with the dependencies within each nest is proposed in [START_REF] Revelt | Mixed logit with repeated choices: Households choices of appliance effciency level[END_REF]. The logit model and nested logit [START_REF] Ben-Akiva | Multinomial probit with a logit kernel and a general parametetric specipication of the covariance structure[END_REF] model neglects the dependency of the prediction by using independence from irrelevant alternatives property. [START_REF] Cardell | Measuring the societal impacts of automobile downsizing[END_REF] deals the innovative perspective of new product by measuring the impact of society in choosing the right size of automobile and issues like downsizing of cars etc. [START_REF] Brownstonel | Forecasting new product penetration with flexible substitution patterns[END_REF] deals real world cases, including stock problem and inventory issues, while applying statistical approaches for making estimation about the consequences and likelihood of some future events. Fuzzy logic based production time-lining is developed in [START_REF] Petrovic | A fuzzy logic based production scheduling/rescheduling in the presence of uncertain disruptions[END_REF] for rescheduling of the production in the presence of varying perturbations.

Neural Networks are always comparable to other prediction models when it comes to time series analysis. Back-propagating Neural Network model is used in [START_REF] Lo | Back propagation neural network on the forecasting system of sea food material demand[END_REF] for forecasting the demand of sea food material demand. SVM is used for financial time series forecasting in [START_REF] Cao | Support vector machine with adaptive parameters in financial time series forecasting[END_REF]. Financial time series analysis has been covered in [START_REF] Francis | Modified support vector machines in financial time series forecasting[END_REF] using Support Vector Machine (SVM) with modified features. The prediction model in [START_REF] Fletcher | Forecasting with neural networks and application using bankruptcy data[END_REF] uses neural networks while it takes time series of bankruptcy data, predicting likelihood of bankruptcy. The stock market forecaster design is also obtained using Modular Neural Network in [START_REF] Fletcher | Forecasting with neural networks and application using bankruptcy data[END_REF]. Neural Networks are employed in stock market for future trading volumes in [START_REF] Kaastra | Forecasting futures trading volume using neural networks[END_REF]. This work is different from the past applications of the Neural Networks to the industrial development in the sense that it uses the trading volume and the change in the market value of the production of the firms for predicting the sustainability of the firm. This whole technique is collectively termed as growth curve approach.

New product development -An insight

Product design is the core issue for the deployment of new product in the market. New product should be consummate in terms of its function, environment, cost, ergonomics, material, customers need and industrial production feasibility2 . It should be unique and carry the identity of the producer in case of cash-cow3 companies. The more relevance of the product to the discussed attributes makes it more user friendly, affordable and attractive. In case, the product that is to be commercialized, is the renovation of some already existing product(s) or product that were developed in the past, the deployment should follow the production and consumption trends of these previous versions of the products. Forecasting the peak consumption era depends on the need of a product, for which the producer must be ready to place the product in the market at the exact time for the exact duration. The key discrepancies can be removed easily if the products are ready in their development.

Investigating the company's ability to introduce a successful product can be done by analyzing the past statistics of the firm [START_REF] Cao | Support vector machine with adaptive parameters in financial time series forecasting[END_REF]. The variation in the production of the company can be studied from the daily market values, variation in the sales with time and the total development to the date of announcing new products. The behavior of the time series is the resultant of the features that constitutes the growth of a product or company. This particular time series is thus used for predicting the near future and ensembles of the product profile.

Cartesian Genetic Programming evolved Artificial

Neural Network (CGPANN)

The dynamicity of Artificial Neural Network is enhanced using different evolutionary techniques. These techniques including NEAT [START_REF] Hasanat | Object class recognition using neat-evolved artificial neural network[END_REF], TWEANN [START_REF] Yao | Evolving artificial neural networks[END_REF] and co-evolutionary method including adaptive and self-adaptive differential evolution systems [START_REF] Yao | Evolving artificial neural network ensembles[END_REF]. The application space of ANN is increased when it is evolved using CGP.

Architectural overview of CGPANN A typical CGP evolved ANN consists of CGP Nodes connected with each other and to the inputs/output(s). The nodes or neurons thus are used as processing elements. A node can either be in input layer, it can form hidden layer or it can be a part of the output layer. In feedforward CGPANN, this node takes its input either from the preceding sister nodes or from the system input, depending upon its location in the network. Each node takes a defined number of inputs that is specified in the initialization step for the network evolution. These input are then scaled (defined by Eq. 1) and summed before passing through an activation function.

∀W ϕ P RG([1, -1]) ∧ ϕ = [1, 2, 3, ..., n] (1)
ϕ is the total number of input connections to a node and the weights that are generated by PRG are assigned to these input connections respectively. All the connections are scaled before applying to a random node. Input nodes take their inputs from the system inputs directly without scaling. Intermediate nodes take its input(s) from preceding nodes in case of feed forward ANNs. The activation f (x) is chosen to be log-sigmoid for all nodes in this network, defined by the Eq. 2. Junk nodes have no connectivity hence contribution to the network output.

f (x) = 1 1 + e -x (2)
Here, x is the sum of scaled inputs of the randomly chosen inputs. The x is given by the Eq. 3

x = n i=1 [I i ] × [W i ] (3)
Where the number of inputs ranges from 1 to n, given by matrix [I] in Eq. 4.

The matrix [W ] is the collection of respected random weights to the node, given by Eq. 5. Eq. 3 adds the product of all inputs and their respected weights.

I = [i 1 , i 2 , i 3 , ....., i n ] (4)
W = [w 1 , w 2 , w 3 , ....., w n ] (5)
Any summing junction in ANN can be represented by

y = N i=1 x i (6)
where x i is the input to the junction. If the same input is scaled with a randomly assigned weight w i then Eq. 6 takes the form

y = N i=1 x i w i (7)
Let for N inputs to a node, we have y j output such that

y j = f j (y j ) = f j N i=1 x i w i ( 8
)
Here f is an activation function, particular to node j. If total number of nodes in the network are N T then j is defined by

{j|j N ∧ 1 ≤ j ≤ N T } (9)
Let I be the input set to a unique genotype network G k , consisting unique entries i such that, for all inputs

i R ∧ 0 ≤ i ≤ 1 ( 10
) in I = {i 1 , i 2 , i 3 , ....i n }
so, network G k is the a set of random selection from inputs [I], outputs of nodes y j , for a single output O p such that

O p = 1 n N i=1 f (y j W j + y j-1 W j-1 + .... + y 1 W 1 + IW k ) (11)
here, W j , W j-1 , ... W 1 are Random subsets of W such that W k is a subset W j and

W j = {w k |w k R ∧ -1 ≤ w k ≤ 1} (12)
Now G k = {I, y j , y j-1 , ...., y 1 , O p } (13)

y j = f (y j-1 W j-1 + y j-2 W j-2 + .... + y 1 W 1 + IW ) y j-1 = f (y j-2 W j-2 + y j-3 W j-3 + .... + y 1 W 1 + IW )
. . .

y 2 = f (y 1 W 1 + IW ) y 1 = f IW (14)
Let G k and G l be the two successive genotypes. G l is produced from G k by mutating µ% weights of connections in G k , nodal connectivity, functions defining each node or the combination of these.

Let the total entries in G k , including weights, connections and functions be N cwf then

N cwf = µ × N cwf (15)
N cwf represents genotype entries that are to be randomized to get G l .

Let r be a unique entry to the set ζ that contains value to be changed to get mutated G k or G l defined by r.

{r|r ζ∀(W, I, y j )} [START_REF] Revelt | Mixed logit with repeated choices: Households choices of appliance effciency level[END_REF] each value in r is defined by a Pseudo Random Generator (PRG) that takes N cwf values from available N cwf entries using the relation

r i |r i {1, 2, 3, ..., N cwf } ∧ r i ⊂ {1, 2, 3, ..., N cwf } , i = 1, 2, 3, ...N cwf ( 17
)
where r i belongs to {1, 2, 3, ...N cwf } so each entry in ζ is

Γ (i) = r i |r i {1, 2, 3, ...N cwf } ∧ {1 ≤ r i ≤ N cwf } (18)
The value that is replaced in G k for N cwf values uses Pseudo Random Number Generator (PRG). Here, each input I i is the output of some proceeding node or the network input given by the Eq. 19.

I(G, L, N ) = P RG([O(G, L p , N p )] : [I(G, L 0 )]) (19)
G represent a specific genotype, L is the Layer in which the node N is situated. L p and N p are representing the preceding Layers and Nodes respectively whereas L 0 represent the input matrix to the Genotype G. The mutation rate is kept 10% for its better results in [START_REF] Khan | Short-term daily peak load forecasting using fast learning neural network[END_REF]. In each generation, connections are altered and weight are varied according to the relevance of the network output with the desired values that are also given to the network for its training. Junk nodes that contribute none to the network and having no influence on the network performance are exscinded using CGP in an efficient way. Thus the final phenotype might have node number less than the number of nodes that are initialized at the start of evolutionary phase. The data is taken for three different dairy product producing companies i.e. Nestle (NSRGY) 4 , Dean Food Company (DF) 5 and Saputo (SAPIF).

The growth curve estimation model works in two major steps. The first step involves the training of the model. The daily stock market values of NSRGY for the years 1998-99 are used to train the particular CGPANN model. The model develops an intrinsic intuition for predicting the next half day stock value while taking 7 days data as its input sequence. 10 different networks, on the basis of the number of their nodes, were initialized for this purpose. The number of nodes were varied between 50 and 500 with a step size of 50. Inputs are taken from the provided stock value time series to the network where the CGPANN calculates the output V f orecasted . This output is compared with the given desired value V actual and the generation proceeds to minimize this difference between the output from the network and the desired output. The evolution stops after reaching to the maximum number of generation, initialized at the start of this training session or if the desired fitness is achieved. The fitness of 10 mutants is measured at the end of each generation using Eq. 20. This training phase took 20 hours when performed with 3.4GHz corei7-2600 processing unit with 16GB RAM and 8MB L3 Cache.

F itness = 100% -M AP E ( 20
)
Where MAPE is the mean absolute percentage error that is calculated as

M AP E = V Actual -V f orecasted V Actual × 100% (21)
After selecting the best mutants among the evolved genotypes, these networks are evaluated with the time series data of normalized stock values, change in stock and total sales to data. Sliding window mechanism is used for the prediction of whole sequence. The model takes 14 inputs and gives forecast value for the nested inputs.

Experiment Results

Selecting network: MAPE values of the networks for the years 1998-1999 given for each network in Table 1. Table 1 is the numerical evidence of the fact that although all networks are giving a minimal MAPE due to their better adaptability features while each network is evolved for its 1M generations, the network that is initialized with 450 nodes outperforms over other networks. Although the It can be inferred from Table 5 that CGPANN is a better techniques that can be used to evolve Artificial Neural Network for human biased certainty reluctant time series such as stock value and productions due to its self-adaptability and fast learning features.CGPANN, in comparison with other prediction models, performs better for its non-linear characteristics and non-conventional behavior. The non-conventional behavior of CGPANN increases its MAPE to 93% that is 22.21% in addition to the MAPE value of Sigmoid SVM, a non-linear model, conventional model. On the other hand, the Linear SVM that follows linear approach and possesses conventional behavior, gives 6.08% more effective MAPE values for a given timely devised data.

Fig. 1, 2 and 3 graphically explain the accuracy of the model by plotting the estimated stock values, instantaneous changes and the cumulative stocks of each company. The Fig. 1, 2 and 3 explain progress of each producer as well as the change in their market stock time by time. It can be inferred from the estimated and the actual values of the entities that the proposed forecaster has learned the pattern that is experienced by each producer. The time series thus obtain is authenticated one and can be used for econometric analysis. Cumulative stock or the growth curve defines the exact position of the firm after each and every time instant which has been made possible by using the newly developed CGPANN. Basic fact about SNRGY food producing company can be explained from its cumulative stock value. Based on cumulative stock, SNRGY is leading among its competitors, shown in Fig. 4. The variations in the market stock value (defined by peak to average ratio and standard deviation) is also compared in Fig. 4. More fluctuation in the time series of the per-instant change of the company stock, as given by Table 3, reflects the dynamicity in the products of the company.

Conclusion

The paper uses CGPANN prediction model for forecasting the growth curve of a firm. This growth curve thus enables a particular producer, at any instant, to compare its production statistics with other similar producer and find out the margin to which they have to take risk in introducing new product in the market. The buying power of the consumer can be predicted by looking at the daily change in the stock usage that can be used in the estimation of the future production by a company. Thus the companies can estimate the raw material and manage their stock according to the future buying capacity of the present users. The model further enables newly developed firms to calculate their increment in market reputation while looking at the daily change in stock value. The model can be much effective if the consumption time series of a single product is employed for its future use. The producers can then manage their inventory while knowing the exact number of future consumer of each and every single product, supplied by them.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Nestle -Instantaneous stock value, per instant change and cumulative stock prediction (14 inputs(7 days) 1 output)

Fig. 3 .Fig. 4 .

 34 Fig. 3. Saputo -Instantaneous stock value, per instant change and cumulative stock prediction (14 inputs(7 days) 1 output)

Table 1 .

 1 MAPE values for training session -14 instants input the forecasting horizon is elevated yet the model is useful as this MAPE value is competent to other models quoted in the literature. Table2contains MAPE results for the year 2002 for different companies with various data sets. The model takes 14 instant inputs and gives single output. Results are tabulated with respect to the initialized nodes for network.

		Single	7	14	Single	7	14
	Nodes output outputs outputs Nodes output outputs outputs
	50	1.8016 2.5912	2.681	300 1.8045 2.6114	2.694
	100 1.8046 2.6059	2.692	350 1.8109 2.6222	2.705
	150 1.8107 2.6000	2.687	400 1.8040 2.6228	2.703
	200 1.8028 2.5981	2.703	450 1.7992 2.6041	2.694
	250 1.8072 2.5929	2.687	500 1.8198 2.6018	2.713
	error increases when

Table 2 .

 2 MAPE results for Stock value, Change in stock and Cumulative stock with network inputs ranging from 50 to 500 with step size of 50 CH) 6.663 6.4366 6.528 6.462 6.449 6.542 6.554 6.564 6.382 6.521 NSRGY(CS) 8.949 7.7498 8.182 7.934 8.003 8.323 9.010 8.451 7.747 8.402 here: S=Stock value, CH=Change in stock and CS=Cumulative stock The Standard deviation and Peak to Average ratio (P/A) values in Table 3

	Nodes	50	100 150 200 250 300 350 400	450 500
	SAPIF(S)	6.087 5.372 5.588 5.478 5.523 5.685 6.105 5.788 5.365 5.730
	SAPIF(CH) 12.806 11.101 11.810 11.441 11.535 11.994 13.094 11.970 11.042 12.08
	SAPIF(CS)	9.334 8.104 8.519 8.261 8.333 8.666 9.386 8.843 8.089 8.750
	DF(S)	7.624 6.633 7.000 6.806 6.864 7.117 7.709 7.186 6.624 7.178
	DF(CH)	11.603 10.068 10.701 10.370 10.456 10.869 11.772 10.877 10.032 10.96
	DF(CS)	9.310 8.069 8.514 8.254 8.327 8.661 9.38 8.802 8.064 8.746
	NSRGY(S)	7.861 6.875 7.215 7.023 7.084 7.342 7.898 7.459 6.867 7.417
	NSRGY(

Table 3 .

 3 Standard deviation and Peak to average ration of the data sets describe the distribution of the data on the given time line. It is the beauty of the model to predict up to the excellent level of accuracy as given in Table2. It is evident from the Table2that different data sets (of exclusive data trends) gives best results on network with 450 nodes. The best results obtained in all the models for the year 2002 for different data trends are given by in Table4. The

	Attribute DF(S) DF(CH) NSRGY(S) NSRGY(CH) SAPIF(S) SAPIF(CH)
	P/A	1.766	1.282	1.799	1.825	2.008	1.226
	SD	0.234	0.035	0.225	0.0775	0.206	0.0440

Table 4 .

 4 MAPE results for different data sets -450 initial nodes -14 instances input -Single output

			Company
	Time series	SAPIF(%) DF(%) NSRGY(%)
	Stock Value	5.365	6.624	6.867
	Change in Stock	11.042	10.032	6.382
	Total Sales to date	8.089	8.064	7.747

Table 5 .

 5 Comparison of proposed CGPANN model with different models[START_REF] Francis | Modified support vector machines in financial time series forecasting[END_REF][START_REF] Min | Bankruptcy prediction using support vector machinewith optimal choice of kernel function parameters[END_REF]

		Testing Accuracy		Testing Accuracy
	Model(s)	(%age)	Model(s)	(%age)
	MDA	79.13	RBF SVM	83.06
	Logit	78.30	Polynomial SVM(1)	82.01
	BPNN(1)	81.48	Polynomial SVM(2)	77.24
	BPNN(2)	71.16	Sigmoid SVM	71.16
	Linear SVM	77.24	CGPANN	93.37

http://www.statsoft.com/Textbook/Demand-Forecastin

http://www.deaconlloyd.com/services/market-feasibility-studies.html

http://www.wikinvest.com/wiki/Cash cow business

http://money.rediff.com/companies/Nestle-India-Ltd/11120007/nse/day/chart

https://finance.yahoo.com/q?s=DF


Doina Logofatu
email: logofatu@fb2.fh-frankfurt.de

Daniel Stamate

Scalable Distributed Genetic Algorithm for Data Ordering Problem with Inversion Using MapReduce

Keywords: Data Ordering with Inversion, Low Power, Distributed Algorithm, Evolutionary Approaches, Transition Minimization, Greedy, MapReduce, Apache Hadoop

We present in this work a scalable distributed genetic algorithm of Data Ordering Problem with Inversion using the MapReduce paradigm. This specific topic is appealing for reduction of the power dissipation in VLSI and in bioinformatics. The capacitance and the switching activity influence the power consumption on the software level. The ordering of the data sequences is an unconditional consequence of switching activity. An optimization problem related to this topic is the ordering of sequences such that the total number of transitions will be minimized -Data Ordering Problem (DOP). Adding the bus-invert paradigm, some sequences can be complemented. The resulting problem is the DOP with Inversion (DOPI). These ordering problems are NP-hard. We establish a scalable distributed genetic approach -MapReduce Parallel Genetic Algorithm (MRPGA) for DOPI, MRPGA_DOPI and draw comparisons with greedy algorithms. The proposed methods are estimated and experiments show the efficiency of MRPGA_DOPI.

Background and Motivation

Quicker access time and bigger storage capacity are actual demands for electronic devices ( [START_REF] De Micheli | Synthesis and Optimisation of Digital Circuits[END_REF]). That's why the low-power topics have to be considered at the beginning of the design process ( [START_REF] Murgai | Data Sequencing for Minimum-Transition Transmission[END_REF], [START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF], [START_REF] Shen | Transistor reordering rules for power reduction in CMOS gates[END_REF], [START_REF] Stan | Low-Power encodings for Global Communication in CMOS VLSI[END_REF]). The software component for the design of embedded systems is of importance for the power consumption of the circuit, since its optimization could lead to significant improvements ( [START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF], [START_REF] Shen | Transistor reordering rules for power reduction in CMOS gates[END_REF]). Often, the design complexity describes directly the power consumption of a circuit. It is a fact that nowadays the power consumption has grown, bringing also more complex design approaches. Reliability, cooling costs, packaging, and computer battery life are some domains with positive effects regarding a design based on low power consumption. For handling the power management issue, new directions and approaches are necessary. The capacitance and the switching activity influence the (software level) power consumption. An important design metric, the switching activity, characterizes the quality of an embedded system-on-chip design. The switching activity proves to be an important design metric, which describes the quality of an embedded system-on-chip design. It is directly related to the ordering of data strings. One first problem related to this topic is the ordering of data words for minimizing the total number of transitions Data Ordering Problem (DOP). This problem could be of interest for various practical situations, e.g. reordering and optimize DNA sequences or in the linguistic leveling [START_REF] Holland | Adaption in Natural and Artificial Systems[END_REF][START_REF] Logofătu | DNA Sequences Vectors and Their Ordering[END_REF].

Problem domain

Definition 2.1. Hamming distance. If a word w r of length k is followed by the word w s of the same length k, the total number of transitions is given by the number of bits that change. This is:

∑ = ⊕ = k j sj rj s r w w w w d 1 ) , ( (1)
also known as the Hamming distance between w r and w s . Here, the w rj denotes the j th bit of w r , and ⊕ the XOR operation. For instance, d(1010, 0100) = 3. The number of transitions is, in fact, the Hamming distance between w r and w s .

Definition 2.2. Total number of transitions. The total number of transitions is the sum of number of transitions needed for the transmission of all the words w 1 , w 2 , …, w n . It is denoted with N T . If σ is a permutation of {1, 2, …, n}, then the total number of transitions will be:

) , ( 1 1 ) 1 ( ) ( ∑
- = + = n j j j T w w d N σ σ . ( 2
)
Definition 2.3. Phase-assignment. The phase-assignment (polarity) δ is a function defined on {1,…, n} with values in {0, 1}, which specifies if a word is sent as it is or complemented (negated, inverted).

For example, the complemented word of 10011 is 01100. That is, if δ (i)=0 then the word w i is sent as it is, otherwise is sent his complement.

Definition 2.4. The Data Ordering Problem (DOP) is defined as the problem of finding a permutation σ of the words w 1 , w 2 , …, w n such that the total number of transitions:

) , ( ) , (

- = + + = n j j j j j T w w d N δ σ δ σ (4) is minimized. 1 1 ) 1 ( ) 1 ( ) ( ) ( ∑
The problems DOP and DOPI are NP-hard [START_REF] Murgai | Data Sequencing for Minimum-Transition Transmission[END_REF][START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF]. Note that the Hamming distance between two words with the same length provides the total number of dissimilarities between these words. We denote the generalizations of these problems also with DOP and DOPI. Given a set of n words with the same length k over an alphabet A, and in the case of DOPI also a permutation of length k which denotes the inversion (complementation) function, it is requested to provide a permutation of the given words (in the case of DOPI also an assignation of them) which minimizes the total number of dissimilarities (transitions).

Previous Work

The optimal method and two evolutionary approaches, MUT_DOPI (with mutation) and GA_DOPI (hybrid genetic algorithm) are proposed in [START_REF] Logofătu | Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion[END_REF], together with three new genetic operators Simple Cycle Mutation (SIM), Cycle OX and Cycle PMX. The two ordering problems are very similar to the Traveling Salesman Problem (TSP). For DOP, DOPI and TSP a efficient ordering of elements regarding to a given weight has to be determined. Since the two problems DOP and DOPI are NP-hard [START_REF] Murgai | Data Sequencing for Minimum-Transition Transmission[END_REF][START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF], the optimal algorithms can only manage small instances. In the past years some approaches were introduced for the problems DOP and DOPI:

Spanning Tree/Minimum Matching (ST-MM) [START_REF] Murgai | Data Sequencing for Minimum-Transition Transmission[END_REF] Double Spanning Tree (DST) [START_REF] Murgai | Data Sequencing for Minimum-Transition Transmission[END_REF] Greedy Simple (GMS) [START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF] Greedy Min (GM) [START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF] Evolutionary Approaches [START_REF] Logofătu | Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion[END_REF] The Evolutionary Algorithms (EAs) provide the best results quality. Such evolutionary methods return better outcome than the above-presented Greedy Min, but with much more time resources. Further, they have no capability to cope with very large data sets. EAs which produce high-quality optimizations are presented in [START_REF] Logofătu | Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion[END_REF], where are presented evolutionary algorithms for both DOP and DOPI.

Scalable Distributed Algorithm Using MapReduce

Our scalable distributed evolutionary algorithm uses the genetic algorithm GA_DOPI [START_REF] Logofătu | Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion[END_REF] and is realized with Hadoop. Apache [START_REF]Apache Hadoop[END_REF] proposes Hadoop as an OpenSource MapReduce [START_REF] Dean | MapReduce: simplified data processing on large clusters[END_REF] framework implementation. Hadoop is a batch data processing system for running applications and process large amounts of data in parallel, in a reliable and fault-tolerant manner on large clusters of compute nodes, usually running on commodity hardware. This system offers monitoring and status tools and provides an abstraction model for programming tasks. It supports automatic distribution and parallelization. Apache's Hadoop offers a distributed file system (HDFS) which creates multiple duplicates of data sets and distributes them on compute nodes throughout the cluster to enable reliable, rapid computations. The nodes for computation and for storage are usually the same. The application specifies the input/output locations, supply map and reduce methods and possibly invariant data.

Fig. 2. MapReduce Dataflow

The scalable distributed evolutionary algorithm performs for a given number of generations. During every generation, it creates an arbitrary number of permutations of the current set of sequences, splits the set of permutations in subsets (map operation) and performs GA_DOPI [START_REF] Logofătu | Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion[END_REF] on all of them during the reduce operation. Lastly, it collects the best permutations (individuals) provided on each reducer node in the cluster and stick them together. Groups of initial individuals are initialized using the greedy approaches GMS and GM [START_REF] Logofătu | DNA Sequences Vectors and Their Ordering[END_REF][START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF]. The outcome represents the set of sequences for the next generation. The map operation associates for each given permutation a subset index in range 0 to reductionFactor-1 randomly, as output key. During the Shuffle & Sort action, the sequences get sorted after their indices, and each reducer node gets and executes GA_DOPI in one call over its subset of sequences with the same index.

ALGORITHM_ MRPGA_DOPI

Initialization(size_of_population, rate_crossover, rate_mutation) The Hadoop implementation for DOPI is the Open Source project "dopiSolver" on sourceforge.net. "dopiSolver.jar" contains the java binary application, as well as all the libraries depends on. The jar's main method (dopisolver.DopiSolverDriver) submits the DopiSolver's Hadoop Job (dopisolver.DopiSolverJob). I order to launch the application use "hadoop jar dopiSolver.jar" and supply afterwards the solvers name: dopi.

Initialization

Fig. 4. Implementation of dopiSolver using Java and Apache's Hadoop

With "hadoop jar dcpSolver.jar dopi -h" you get the description of the application supported options. The source code is available on sourceForge under https://dopisolver.svn.sourceforge.net/svnroot/dopisolver (Subversion repository). The application depends on the libraries JUnit 4 (for test units), Apache Commons CLI2, and Apache Commons Math Version 2.0.

Experimental Results

Various sets of data were generated artificially with different parameters, like e.g. sequences set dimension (n, that is the number of words), length of the words (k). We start by performing the two greedy algorithms GM and GMS [START_REF] Logofătu | Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion[END_REF] on 421 different artificial generated data sets with 1000 ≤ n ≤ 7000, 50 ≤ k ≤ 1000. We do some experiments with the Greedy methods because we use them also in the initialization of the distributed algorithm. In Figure 5 we show the mean values for the difference GMS-GM on intervals and the mean (standard deviations ±) for the execution time for all these experiments.

Conclusions

Experiments executed on randomly generated data input indicated the efficiency of the proposed approach -MRPGA_DOPI -especially for specific attributes of the benchmarks. An application was written for the scalable distributed algorithm using the Hadoop implementation for MapReduce [START_REF] Murgai | Data Sequencing for Minimum-Transition Transmission[END_REF][START_REF] Murgai | Using Complementation and Resequencing to Minimize Transitions[END_REF]. Scalability, status reporting and monitoring, the fault toleration, the facility to work on commodity hardware, performing the computation there the data is, robustness, are all benefits of the Hadoop implementation. Next steps would be to perform experiments on larger data inputs, with various distributions, but also variants for the map or reduce functions. By performing the algorithms on real data inputs, e.g. from bioinformatics or system-on-chip design, will provide further knowledge. E.g. in bioinformatics, DOPI problem could be formulated using the Watson-Crick complements, for every nucleic acid:

A T G C C G T A = = = = , , , . (5)

Definition 2 . 5 .

 25 The Data Ordering Problem with Inversion (DOPI) is defined as the problem of finding a permutation σ and a phase-assignation δ of the words w 1 , w 2 , …, w n such that the total number of transitions:

Fig. 3 .

 3 Fig. 3. Pseudocode for MRPGA_DOPI

Fig. 5 .

 5 Fig. 5. (a) Allocation on intervals of the difference GMS-GM within 421 experiments with 1000 ≤ n ≤ 7000, 50 ≤ k ≤ 1000 (b) Mean and variance for the execution time difference (GMS-GM).

Fig. 6 . 10 7 (Fig. 7 .

 677 Fig. 6. Mean and variance for the difference GMS-GM for (a) values of n and b) values of k.

Fig. 8 .

 8 Fig. 8. Sample Hadoop Web Admin. The system offers monitoring and status tools and provides an abstraction model for programming tasks. It supports automatic distribution and parallelization.


Christos Kyriklidis
email: c.kiriklidis@gmail.com

Georgios Dounias
email: g.dounias@aegean.gr

Kyriklidis Christos

Dounias Georgios

Application of Evolutionary Algorithms in Project Management

Keywords: Time Constraint Project Scheduling, Resource Levelling, Project Management, Genetic Algorithms

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

Introduction

Operation research and artificial intelligence have evolved along parallel lines in the last three decades, often by attempting to competitively solve the same class of realworld optimization problems and in other circumstances to show how the integration of techniques from different fields can lead to interesting results on large and complex problems [START_REF] Holsapple | Operations Research and Artificial Intelligence[END_REF]. Computational intelligence methods and algorithms such as evolutionary or neural programming, and more recently also nature inspired intelligent techniques, have succeed to obtain high quality near-optimal solutions to hard optimization problems, thus becoming competitive approaches in OR fields. Nature inspired intelligent methods such as ant colony optimization, memetic algorithms and hybrid particle swarm optimization, have been successfully dealt with various other optimization problems such as the quadratic multiple container packing problem [START_REF] Soak | A memetic algorithm for the quadratic multiple container packing problem[END_REF], the dynamic strategic planning for electric distribution systems [START_REF] Ippolito | Ant Colony Search Algorithm for Optimal Strategical Planning of Electrical Distribution Systems Expansion[END_REF], the bandwidth minimization problem [START_REF] Lim | Particle Swarm Optimization and Hill Climbing for the bandwidth minimization problem[END_REF], etc. The current work proposes the use of genetic algorithms for solving effectively the well-known optimization problem of resource leveling.

The Resource Leveling Problem (RLP), also known as time-constrained project scheduling problem (TCPSP) is an NP-hard optimization problem [START_REF] Neumann | Resource levelling for projects with scheduledependent time windows[END_REF][START_REF] Hegazy | Optimization of Resource Allocation and Leveling using Genetic Algorithm[END_REF]. The aim of this paper is to highlight the advantages of evolutionary intelligent algorithms in resource leveling problems. More specifically, an intelligent metaheuristic is proposed based in a new genetic algorithm, in order to produce an optimal resource management profile. An important contribution of this work is the way that the proposed approach investigates the various different feasible start-time values of non-critical activities of a project, thus leading to improved resource profiles and contributing to optimal resource allocation. The paper is organized as follows:

In Section 1, introductory comments are made. In Section 2, a literature review regarding both, the resource leveling problem and the proposed intelligent metaheuristic, is provided. In Section 3, the main methodological issues are presented in order to get a better understanding of the underlying mechanisms of the algorithm. In Section 4, the mathematical formulation of the resource leveling problem is analyzed, and complexity issues are discussed. Finally, the last Section concludes to remarks and interesting points which are summarized in an intuitive manner.

2

Literature review

In the literature some selected studies regarding the application of several conventional and intelligent optimization algorithms and techniques on the resource leveling problem, are presented. Research work dealing with the resource leveling problem is quite extensive, as it is shown in Table 1. The given collection of papers contains a variety of methodologies ranging from dynamic programming and relaxation methods, to a number of intelligent approaches such as fuzzy optimal models, neural net-works, genetic optimization based multicriteria techniques, Petri nets, ant colonies and memetic algorithms.

Analytical methods such as exhaustive search (complete enumeration approaches) [START_REF] Younis | Optimal resource leveling of multi-resource projects[END_REF], integer programming [START_REF] Elwany | Resource smoothening in repetitive projects[END_REF], dynamic programming [START_REF] Chan | Construction resource scheduling with genetic algorithms[END_REF] and branch-and-bound methods have been used to search for an accurate solution. However most of these methods have many limitations. Their major drawback is that they cannot be used to solve large and complex problems effectively [START_REF] Hegazy | Optimization of Resource Allocation and Leveling using Genetic Algorithm[END_REF][START_REF] Chan | Construction resource scheduling with genetic algorithms[END_REF], as they are either computationally infeasible and lead to combinatorial explosion in cases of large and/or complicated projects [START_REF] Geng | An improved ant colony optimization algorithm for nonlinear resource-leveling problems[END_REF].

For the effective management of large projects, researchers prefer to apply heuristic methods, which are successful in solving large and complex problems comparatively to analytical methods, although their effectiveness highly depends on the problem. Several efforts in the direction of developing heuristic rules for resource leveling, aiming at producing high-quality feasible solutions, have been made [START_REF] Burges | Variation in activity level in a cyclical arrow diagram[END_REF][START_REF] Galbreath | Computer program for leveling resource usage[END_REF][START_REF] Shaffer | The critical path method[END_REF][START_REF] Wiest | A Management Guide to PERT/CPM[END_REF][START_REF] Harris | Packing method for resource leveling _PACK[END_REF][START_REF] Antill | Critical Path Methods in Construction Practice[END_REF][START_REF] Moder | Project Management with CPM, PERT and Precedence Diagramming[END_REF]. The models also presented by Neumann and Zimmermann [START_REF] Neumann | Resource levelling for projects with scheduledependent time windows[END_REF][START_REF] Neumann | Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints[END_REF] are indicative examples of a polynomial heuristic procedure for various types of resource leveling problems, where general temporal constraints are given by minimum and maximum time lags among activities.

In recent years, advanced computational methods like Genetic Algorithms (GAs) [START_REF] Hegazy | Optimization of Resource Allocation and Leveling using Genetic Algorithm[END_REF][START_REF] Chan | Construction resource scheduling with genetic algorithms[END_REF][START_REF] Leu | GA-based multicriteria optimal model for construction scheduling[END_REF][START_REF] Leu | An optimal construction resource leveling scheduling simulation model[END_REF][START_REF] Huang | Genetic algorithms for optimization of resource Allocation in Large Scale Construction Project Management[END_REF][START_REF] Li | Combination of genetic & ant colony algorithms for multi-project resource leveling problem[END_REF][START_REF] Zhou | An ant colony system for solving resource leveling problem[END_REF][START_REF] Leu | Resource leveling in construction by genetic algorithm-based optimization and its decision support system application[END_REF][START_REF] Liu | Genetic algorithm for resource leveling problem in project scheduling[END_REF][START_REF] Senouci | Use of genetic algorithms in resource scheduling of construction projects[END_REF] and particle swarm optimization approaches [START_REF] Chen | Research on the unlimited resource leveling optimization with PSO[END_REF][START_REF] Guo | Multi-resource leveling in multiple projects and vector evaluated particle swarm optimization based on Pareto[END_REF] have been used for solving resource leveling problems. Also, Kartam and Tongthong [START_REF] Kartam | An artificial neural network for resource leveling problems[END_REF] introduced a methodology for solving resource leveling problems using Artificial Neural Networks (ANN). Also, Geng et al. [START_REF] Geng | An improved ant colony optimization algorithm for nonlinear resource-leveling problems[END_REF] improved an ant colony optimization (ACO) approach, another nature-inspired algorithm, for non-linear resource leveling problems. However, potential drawbacks of these methods, such as premature convergence and poor exploitation, have attracted increasing attention from researchers and engineers, whose main aim is to upgrade their efficiency.

Finally, a few other interesting approaches to the resource leveling problem can be found, that do not fall in any of the above mentioned categories. Research by Jeetendra et al. [START_REF] Jeetendra | Petri nets for project management and resource levelling[END_REF] described the use of Petri nets (PNs), whereas Raja et al. [START_REF] Raja | Resource leveling using Petrinet and memetic approach[END_REF] proposed the use of a Petri net in combination with a memetic algorithm.

Findings from the literature survey indicate the effectiveness of intelligent techniques such as genetic algorithms and neural networks, in solving resource leveling problems. Especially, in the case where new formulations of the problem at-hand are considered, these algorithms have proven their ability to yield high-quality, if not the optimal, solution. Literature shows the evolution of applied methodologies for the resource leveling problem, progressing from naïve techniques to more sophisticated ones. However, based on their weak points, ground for further development exists.

Resource Leveling

The project network production in the initial phase displays many peaks (maximum resource uses) and valleys (minimum resource uses) in resource profiling diagrams. This fact emanates from the non-uniform resource requirement when the project exe-cution begins [START_REF] Pang | Resource Leveling Optimization of Network Schedule Based on Particle Swarm Optimization with Constriction Factor[END_REF]. Two basic Resource Leveling versions are used in several studies. The fixed project duration restriction is common in both of them:

1. Reduction of the minimum and maximum resource uses, [START_REF] Leu | An optimal construction resource leveling scheduling simulation model[END_REF][START_REF] Kartam | An artificial neural network for resource leveling problems[END_REF][START_REF] Pang | Resource Leveling Optimization of Network Schedule Based on Particle Swarm Optimization with Constriction Factor[END_REF][START_REF] Leachman | Multiple Resource Leveling in Construction Systems Through Variation of Activity Intensities[END_REF][START_REF] Akpan | Resource smoothing: A cost minimization approach[END_REF][START_REF] Zhao | GA based resource leveling optimization for construction project[END_REF].

2. Reduction of resource use fluctuation from period t to period t+1 [START_REF] Geng | An improved ant colony optimization algorithm for nonlinear resource-leveling problems[END_REF][START_REF] Leu | An optimal construction resource leveling scheduling simulation model[END_REF][START_REF] Leu | Resource leveling in construction by genetic algorithm-based optimization and its decision support system application[END_REF][START_REF] Kartam | An artificial neural network for resource leveling problems[END_REF][START_REF] Jeetendra | Petri nets for project management and resource levelling[END_REF][START_REF] Zhao | GA based resource leveling optimization for construction project[END_REF][START_REF] Xiong | Ant colony optimization algorithm for resource leveling problem of contruction problem[END_REF][START_REF] Roca | Solving an Extended Resource Leveling Problem with Multiobjective Evolutionary Algorithms[END_REF][START_REF] Anagnostopoulos | A simulated annealing hyperheuristic for construction resource leveling[END_REF]. A usual problem formulation is the following: Let A = {1,2, . . , n} be the set of the project's activities to be scheduled, where activities 1 and n are dummy activities that represent the starting and ending phase, respectively. Duration and resource requirements for these activities equal to zero. The duration of each activity i ∈ A is denoted by di. T denotes the total duration of the project. Also T is computed by CPM method, where the project network is designed as A.O.N. (Activity On Node). Precedence relations among the activities in A exist. These relations indicate which activities should be completed before a specific activity can start. The underlying assumption is that the type of relationships among activities is finish-to-start with zero lag. Each activity i requires ri units of k (k=1,…,K) resource types per time period. If a type of resource is used in resource leveling process, then ck=1 else ck=0.

( ) = ∑ ∈{ ,.., } ∈{ , ,.. } (1)
The most often used multi-objective function in literature for the resource leveling problem uses one or blends more than one of the following seven objectives:

1. min Gf (minimization of the maximum resource usage for the project) 2. min RLI (difference between actual and desirable resource usage) 3. min StD (minimization of the standard deviation) 4. min Step (minimization of uniform resource use from period to period) 5. min R 2 (minimization of the squared resource usage) 6. min RIC (relates variation of a selected resource histogram to an ideal one)

min EV (minimum entropy)

The present GA is able to use each of the above mathematical measurements for the resource profiles evaluation.

Algorithmic Framework

The paper applies an evolutionary algorithmic approach (GA) for solving the resource leveling problem. In particular, optimization problems can be tackled efficiently intelligent and evolutionary methodologies and algorithms. In the scope of this paper, the resource leveling problem corresponds to a typical optimization task. The standard genetic algorithm was initially proposed by Holland [START_REF] Holland | Genetic Algorithms[END_REF]. The main characteristics of the algorithm lie in the concept of evolutionary process. Genetic algorithms apply the mechanisms of selection, crossover and mutation in order to evolve the members of a population, through a number of generations. The ultimate goal is to reach a population of good-quality solutions, approaching the 'optimum' region. In order to assess the quality of each member of the population, the concept of fitness value is introduced. In the case of the resource leveling problem, each solution represents a chromosome in the GA.

In Figure 1, the GA for the resource leveling problem is presented. Below, the main terms and processes mentioned in Figure 1 are explained.

Construction of the Next Generation

The first generation is formed by randomly creating feasible resource profiles. To produce the subsequent generations, the top 10% (best chromosomes) of each generation is transported directly to the next generation, 70% of the descendant generation is produced by applying the two-point crossover operator on parents' chromosomes. Finally, the last 20% chromosomes of the offspring will occur from mutation generated in the same way by which the initial population was formed. Resource profiles are generated by taking the start-time of non-critical activities contained in each chromosome and the start-times of critical activities that always remain unchanged. Then, the fitness function (e.g. RLI) is used to evaluate each resource profile.

It is important to be mentioned that the crossover and mutation processes produce the sequence for the non-critical activities start-time production. The solution feasibility depends on the non-critical activity ES-LS as well as on the correlations that has each non-critical activity with the other non-critical activities. All possible different start-time values of all non-critical activities of a project are explored and are combined on the basis of the ES-LS value restrictions and on non-critical activities correlations. In other words only efficient solutions are produced and no efficient solution is excluded by the solution search process.

Let's denote as S: start-time (day), SP: time step (in days), SS 1 : new early start value and SS 2 : new late start value. After the initial population, a new restriction applies, which is a frame ± from the best chromosome starttimes for the non-critical activities. GA applies local search around the previous generation best chromosome using this frame. also defines how close to the best chromosome the searching takes place, by receiving values between:

{ = 1 ∶ = -( + 1)}.
When is defined by the decision maker, two new limits are set which satisfy the , restrictions:

ℎ : ≥ ℎ : ≤
These new bounds , obtained from the above described process, as well as the correlations between non-critical activities, are the restrictions for the new start-time production taking place in Crossover process (Fig. 2).

The proposed technique for the the investigation of the start time of the non-critical activities of a project has the following three advantages which contribute to the GA effectiveness in optimal solution finding:  Maintenance of the optimal solutions (TOP) from the previous generation in order to be compared with the newly produced solutions.  The restriction ± from the optimal solution start-time in previous generation offers the possibility for faster convergence to an optimal solution.  The BOT chromosomes receive randomly a start-time value according to a uniform distribution in corresponding interval ES -LS for each gene. This fact releases the GA algorithm from a premature convergence in a semi-optimal solution.

Benchmark experiments

The parameter settings of the GA approach used during the experimentation were (a) size of population set to 40, (b) number of generations set to 50, (c) best 10% chromosomes of each generation transferred directly to the next generation, (d) 70% of the current population subjected to crossover, (e) mutation in the remaining 20% of chromosomes, and number of independent simulations set to 50 per criterion (parameters' values have been selected after extensive experimentation).

Firstly the proposed GA was compared with similar studies existing in literature. Exhaustive enumeration was also applied for small size problem and the proposed GA approach could identify the optimal solution for those problems. Specifically, 50 repeated runs of the algorithm were made, and in almost all cases the GA-approach provided excellent results identifying the global minimum of the benchmark projects (excluding the RLI criterion for the problem posed by [START_REF] Leu | Resource leveling in construction by genetic algorithm-based optimization and its decision support system application[END_REF], where the optimal solution was identified in 37 out of 50 repeated experiments, Table 1). Results in Table 1 show that in most cases the proposed approach is superior to the existing ones. The implementation of the algorithm was made in Matlab programming language. Experiments were conducted on a Pentium(R) Dual-Core CPU E5400 at 2,70 GHz and RAM 2,00 GB.

Concluding Remarks

In this paper, the application of evolutionary algorithms for solving resource leveling problems was studied. The basic idea behind this work is the way that the proposed approach investigates the various different feasible start-time values of noncritical activities of a project, thus leading to improved resource profiles and contributing to optimal resource allocation. This mechanism (SP) assists the decision maker in searching efficiently the area surrounding the optimal star-time values. The proposed mutation process also assists in avoiding premature convergence in a semioptimal solution. Experimental results are considered as near-optimal because mathematically the optimal solution cannot be found. With repeated runs one can conclude about the approximate area where the optimum lies.

In conclusion, evolutionary intelligence (GAs) proves capable of solving adequately complex optimization problems and can be proposed as an efficient and effective method for coping with large real-world projects. It is our firm belief that the optimal resource profile could be achieved through even more extensive experimentation and simulations, e.g. in a ship construction project consisting of more than 1000 activities, which is currently tested on its effectiveness. Research is also underway around the implementation of other competitive nature-inspired and hybrid intelligent methodologies on the same application domain.

Fig. 1 .

 1 Fig. 1. GA operation.

Fig. 2 .

 2 Fig. 2. New generation start-time production.

Table 1 .

 1 Experimental results for benchmark problems existing in literature.

	Research Paper	Function	Optimal result	Result of Paper	GA best result	times found optimal in experiments
	[10] Geng et al. (2011)	STD	5,2034	5,6151	5,2034	100%
	[29] Katram & Tongthong (1998)	R 2	885	885	885	100%
	[40] Kim et al (2005)	R 2	448	448	448	100%
	[24] Leu et al (2000)	RLI	25	25	25	74%
	[20] Leu and Hung (2002)	RLI	11	13,09	11	100%

Table 2 .

 2 Results of experiments for 5 benchmark PSPlib projects.

	PROJECT	Gf	GA RLI	StD	PROJECT	Gf	GA RLI	StD
		mean 65,26 829,2 15,34		mean 61,38 1084,8 17,05
	P 1	std	2,63 106,45 1,74	P 4	std	3,17 125,08 1,62
		min	59	657	12,78		min	54	839	14,15
		mean 44,44 697,72 9,94		mean 50,32 973,12 13,50
	P 2	std	1,16	53,49	0,64	P 5	std	1,66	86,05	0,91
		min	42	552	7,89		min	46	765	11,75
		mean 62,78 877,76 17,08
	P 3	std	2,61	70,7	1,16
		min	56	744	14,91


David Lehký
email: lehky.d@fce.vutbr.cz

Ondřej Slowik
email: slowik.o@fce.vutbr.cz

Drahomír Novák
email: novak.d@fce.vutbr.cz

Inverse Reliability Task: Artificial Neural Networks and Reliability-Based Optimization Approaches

Keywords: Inverse reliability, artificial neural network, reliability-based optimization, double-loop optimization, uncertainties, Latin hypercube sampling

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

Introduction

To achieve desired level of reliability in limit state design is generally not an easy task. Uncertainties are involved in every part of structural system (e.g. material properties, geometrical imperfections, dead load, live load, wind, snow, corrosion rate, etc.). When performing either reliability assessment or advanced engineering design, it is certainly essential to take uncertainties into account using a probabilistic analysis. Reliability assessment requires forward reliability methods for estimating the reliability (usually theoretical failure probability and/or reliability index are determined). On the other hand, the engineering design requires an inverse reliability approach to determine the design parameters to achieve desired target reliabilities. Some sophisticated approaches to determine design parameters (material properties, geometry, etc.) related to particular limit states have been proposed under the name "inverse reliability methods", e.g. a reliability contour method [START_REF] Winterstein | Environ-mental Parameters for Extreme Response: Inverse Form with Omission Factors[END_REF] and [START_REF] Maes | Developing Structural Criteria with Specifies Response Reliability[END_REF], iterative algorithm based on the modified Hasofer-Lind-Rackwitz-Fiessler scheme used in reliability analysis [START_REF] Kiureghian | Inverse Reliability Problem[END_REF], Newton-Raphson iterative algorithm to find multiple design parameters [START_REF] Li | An Inverse Reliability Method and its Application[END_REF] and [START_REF] Sadovský | Discussion on: An Inverse Reliability Method and its Application[END_REF], decomposition technique [START_REF] Mínguez | Solving the Inverse Reliability Problem Using Decomposition Techniques[END_REF] or various implementation of artificial neural network (ANN) with other soft-computing techniques [START_REF] Shayanfar | An Inverse Reliability Method Using Networks and Genetic Algorithms[END_REF], [START_REF] Cheng | Application of the Response Surface Methods to Solve Inverse Reliability Problems with Implicit Response functions[END_REF] and [START_REF] António | Uncertainty Propagation in Inverse Reliability-based Design of Composite Structures[END_REF].

The two methods proposed in this paper attempts to overcome the shortcomings of existing inverse reliability methods. The first one utilizes ANN too, but in a different way: Computational time is reduced by using a small-sample simulation technique called Latin hypercube sampling (LHS) in ANN based inverse problem proposed by Novák and Lehký in [START_REF] Novák | ANN Inverse Analysis Based on Stochastic Small-Sample Training Set Simulation[END_REF] and [START_REF] Lehký | Solving Inverse Structural Reliability Problem Using Artificial Neural Networks and Small-Sample Simulation[END_REF] first.

The second one is double-loop reliability based optimization (RBO) approach. Classical optimization usually leads to solutions that lie at the boundary of the admissible domain, and that are consequently rather sensitive to uncertainty in the design parameters. In contrast, RBO aims at designing the system in a robust way by minimizing some objective function under reliability constraints. It provides the means for determining the optimal solution of a certain objective function, while ensuring a predefined small probability that a structure fails. Thus RBO methods have to mix optimization algorithms together with reliability calculations. The approach known as "double-loop" consists in nesting the computation of the failure probability with respect to the current design within the optimization loop (e.g. [START_REF]Structural Design Optimization Considering Uncertainties[END_REF]). FORM-based double-loop approach has been proposed by Dubourg in [START_REF] Dubourg | Reliability-Based Design Optimization: An Application to the Buckling of Imperfect Shells[END_REF][START_REF] Dubourg | A Hierarchical Surrogate-based Strategy for Reliability-based Design Optimization[END_REF]. The authors developed a double-loop reliability-based optimization approach based on small-sample simulation and FORM [START_REF] Slowik | Reliability-based Structural Optimization[END_REF][START_REF] Slowik | Algorithmization of Reliability-based Optimization[END_REF].

Inverse Reliability Task

The aim of classical (forward) reliability analysis is the estimation of unreliability using a probability measure called the theoretical failure probability, defined as:

( )

0 P ≤ = Z p f , ( 1
)
where Z is a function of basic random variables X = X 1 , X 2 , …, X N called safety margin. This failure probability is calculated as a probabilistic integral:

( )

∫ = f D f f p X X X d (2)
where the domain of integration of the joint probability distribution function (PDF) above is limited to the failure domain D f where g(X) ≤ 0. The function g(X), a computational model, is a function of random vector X (and also of other, deterministic quantities). Random vector X follows a joint PDF f X (X) and, in general, its marginal variables can be statistically correlated. The explicit calculation of integral in (2) is generally impossible. Therefore a large number of efficient stochastic analysis methods have been developed during the last seven decades.

The inverse reliability task is the task to find design parameters corresponding to specified reliability levels expressed by reliability index or by theoretical failure probability. In general, an inverse problem involves finding either a single design parameter to achieve a given single reliability constraint or multiple design parameters to meet specified multiple reliability constraints. The design parameters can be deterministic or they can be associated with random variables described by statistical mo-ments (mean value, standard deviation) and PDF. In case of mean value one need to choose if either standard deviation or coefficient of variation will be fixed.

Solution Based on Artificial Neural Networks

An efficient general approach of inverse reliability analysis is proposed to obtain design parameters of a computational model in order to achieve the prescribed reliability level. The inverse analysis is based on the coupling of a stochastic simulation of Monte Carlo type and an ANN. The design parameters (e.g. mean values or standard deviations of basic random variables) play the role of basic random variables with a scatter reflecting the physical range of design values. A novelty of the approach is the utilization of the efficient small-sample simulation method LHS used for the stochastic preparation of the training set utilized in training the ANN. The calculation of reliability is performed using the first order reliability method (FORM). Once the ANN has been trained, it represents an approximation consequently utilized in an opposite way: To provide the best possible set of design parameters corresponding to prescribed reliability. The procedure of ANN based inverse reliability method is illustrated by a simple flow chart as shown in Figure 1 and is implemented as follows:

1. The design parameters are considered as random variables with selected (physically reasonable) appropriate scatter and probability distribution. Rectangular distribution is often used. 2. Random samples of design parameters (possibly correlated) are generated using LHS simulation method. 3. Stochastic model of analyzed problem is prepared including generated samples of design parameters. 4. Reliability analyses are performed repeatedly for individual samples of design parameters and set of reliability measures like failure probabilities or reliability indices are calculated. 5. Reliability measures obtained from simulations together with set of random design parameters serve as training set for ANN training. During training an error between simulated and desired outputs of ANN (here in form of MSE) is minimized using appropriate optimization technique (e.g. back propagation methods, evolutionary algorithms). 6. Desired reliability measures are used as an input signal which is distributed through ANN structure to its output where optimal design parameters are obtained. 7. Verification of the results by calculation of failure probabilities related to limit state functions using the optimal parameters is carried out. A comparison with target failure probabilities will show the extent to which the inverse analysis was successful.

In the case of inverse reliability analysis a double stochastic analysis is needed for the training set preparation for ANN (steps 2 and 4 of the procedure). In the outer loop random realizations of design parameters are generated using the LHS simulation technique. The inner loop represents the reliability calculation for one particular realization of design parameters. Here, the FORM approximation method is recommended due to computational demands. The number of simulations in outer loop is driven by ANN and only tens of simulations are usually needed.

Solution by Small-sample Double-loop Reliability-based Optimization

Typically, reliability-based optimization is formulated as:

( ) ( ) [ ] u x l z x x x ≤ ≤ ≤ ≤ , 0 , : subject to min find 0 P g P f f (3)
with P f the probability of constraint satisfaction. The limit state g = 0 separates the region of failure (g ≤ 0) and safe region (g > 0) and is a function of the design variables x (and l and u are lower and upper bounds) and the uncertain variables z. P 0 is the reliability level or performance requirement. The above inequality can be expressed by a failure probability multi-dimensional integral with the joint probability density function of probabilistic variables z. Formulation based on reliability index instead of failure probability is popular especially in the context of FORM approximation.

From the theoretical point of view, RBO has been a well-established concept. However, computing failure probabilities appears as a technically involved problem analytically tractable for very simple cases only. This is because it is often a multidimensional integral equation for which the joint probability density function and/or limit state function g is unknown in explicit form, like FEM computational model. The same difficulty is with objective function f(x) -it can be computationally demanding FEM analysis and the use of classical optimization technique is problematic or even impossible. Then an application of RBO for real-world problem is difficult.

Computational demands of reliability-based optimization are obvious from the formulation above. For the purposes of stochastic optimization it is necessary to repeatedly generate random realizations within the design space. It is also necessary for each of these realizations to calculate the probability of failure in the general case by computationally demanding (mostly numerical) integration of the equation ( 2). Therefore we suggest here an original small-sample double-loop RBO methodology where lower computational burden exists in case of both outer loop -minimization of objective function and inner loop -calculation of failure probability (or reliability index). A practical solution to the above-defined optimization problem is performed using the so-called double-loop approach. The algorithm is composed of two basic loops:

• The outer loop represents the optimization part of the process based on smallsample simulation Latin hypercube sampling. The simulation within the design space is performed in this cycle. For obtained design vectors of n-dimensional space xi=(x1, x2,…, xn) objective function values are calculated. The best realization is then selected based on these values and utilized optimization method. Consequently the best realization of random vector xi,best is compared with optimization constraints. These constraints may be formulated by any deterministic function which functional value can be compared with a defined interval of allowed values. Constraints are also possible to formulate as allowed interval of reliability index β for any limit state function (within design space of given problem). Calculations of reliability index of each generated random vectors xi takes place in the inner loop. Note that it is necessary to use some of advanced meta-heuristic optimization techniques (e.g. simulated annealing or genetic algorithms) to avoid local minima.

• The inner loop is used to calculate reliability index (FORM-based) either for the need of checking of generated solutions -if they satisfy constraints, or to calculate the actual value of the objective function, if the target reliability index is set as goal of optimization process.

Numerical Example

Selected application originates from the civil engineering field of structural mechanics. The aim is to design the dimensions of a rectangular cross-section with width b and height h of a simply-supported beam made of timber (Figure 2). Both dimensions are considered as random variables with a variation of 5 %. The mean values of b and h are design parameters in the inverse reliability problem.

Fig. 2. Scheme of a simply-supported beam with a rectangular cross-section.

The design is performed fully according to Eurocode 5. The ultimate limit state (ULS) as well as the serviceability limit state (SLS) is taken into account. Target reliability indices are β 1 = 3.8, β 2 = 1.5. The limit states are described by the following limit state functions g 1 and g 2 :

fin net fin E R u u g M M g , lim, 2 1 - = - = (4)
where M R is the bending moment of resistance, M E is the bending moment of load action, u lim,fin is the final limit deflection and u net,fin is the final deflection caused by load action. Bending moments M R and M E are calculated as:

( ) 2 mod 2 8 1 6 1 l q g M f k bh M E E m R R + = = θ θ (5)
where b and h are the width and height of rectangular cross-section, l is the length of the beam, f m is flexural strength, k mod is the modification factor taking into account the effect on the strength parameters of the duration of the load and the moisture content in the structure (value k mod = 0.8 was considered), g is permanent load, q is variable load and θ R and θ E are the model uncertainties of resistance and load action. Deflections in the second limit state function g 2 are calculated as:

( ) ( ) ( ) def fin def fin fin fin E fin net fin k bh E ql u k bh E gl u u u u l u , 2 3 4 , 2 , 1 3 4 , 1 , 2 , 1 , lim,
+ = + = + = = θ (6)
where u 1,fin and u 2,fin are the final deflections caused by the permanent load and variable load, E is the modulus of elasticity of timber, k 1,def is a factor which takes into account the increase in deflection with time due to the combined effect of creep and moisture and it belongs to permanent load and k 2,def is the same factor but for variable load (values of k 1,def = 0.8 and k 2,def = 0.25 were used). Table 1 summarizes all random variables and their randomization. The values of the material parameters correspond to spruce timber. Randomization was carried out according to the recommendations of JCSS probabilistic model code [START_REF] Jcss | JCSS Probabilistic Model Code[END_REF]. Reliability analysis was carried out using the FORM method; the starting values were means; the tolerance for convergence was 10 -4 . For both a training set preparation and purpose of optimization the design parameters were considered as random variables with rectangular distribution, see Table 2.

ANN Inverse Analysis

First, ANN inverse reliability analysis was carried out. The ANN (see Figure 3) consisted of one hidden layer having four nonlinear neurons (hyperbolic tangent transfer function) and an output layer having two output neurons (linear transfer function) which correspond to two design parameters -the mean values of width b and height h. The ANN has two inputs which correspond to two specified reliability indices, β 1 and β 2 . For preparation of training set one hundred random samples of design parameters were generated using LHS method according to stochastic model in Table 2 and stochastic analyses were carried out to obtain corresponding reliability indices.

The resulting design parameter values are given in Table 3. To check their accuracy these values were used in equations ( 4) to ( 6) and reliability indices were calculated; see the comparison with the target reliability indices in Table 3. In the case of practical design the dimensions of cross-section should be selected from available set of dimensions. In our example, the resulting width and height would be b = 140 mm and h = 220 mm which gives the final reliability indices β 1,fin = 4.068 and β 2,fin = 1.912.

Fig. 3. A scheme of artificial neural network

Double-Loop Optimization Approach

If we define optimization problem according to definition at section 2.2 then inverse reliability problem can be also solved using double-loop reliability-based optimization approach. During the solution of the problem an option to determine a target value of reliability index for the selected limit state function was utilized. Therefore target reliability index for the limit state function g 2 was defined as β 2 = 1.5. As a constraint an interval (3.75, 3.85) of allowable values of reliability index β 1 for the limit state function g 1 was set.

During solution of the task using aimed multilevel sampling (AMS) optimization algorithm [START_REF] Slowik | Reliability-based Structural Optimization[END_REF] the total number of 300 simulations was used. The result solution of the task is displayed in Table 3 and in Figure 4. Final solution corresponds well to the values obtained using ANN inverse analysis. The resulting cross-sectional area is 2.8302×10 -2 m 2 compared to 2.8385×10 -2 m 2 obtained from ANN inverse analysis. The graph in Figure 4 shows the gradual convergence of generated solutions toward the required values of reliability indices.

Conclusion

The paper presents two alternative approaches to solve inverse analysis task. Both approaches provide very good results, as is indicated in numerical example. Some advantages and disadvantages of the methods can be highlighted: ANN inverse analysis will be probably more accurate and capable to solve also highly nonlinear problems. But more simulations are generally needed for good training of ANN (in case of very small numbers -training cannot be simply done at all). The step "training of ANN" requires deeper involvement of a user, which makes the usage of the approach difficult.

On the other hand the double-loop reliability-based optimization approach can solve problem satisfactorily using small number of simulations, but the lower accuracy can be expected. In case of highly nonlinear problems less efficiency can be expected comparing to ANN inverse analysis approach. The advantage of double-loop optimization approach is a transparency of solution and better understanding by general engineering practice.

The above mentioned summary is formulated based on testing approaches using limited number of numerical examples. The more systematic verification and testing are needed. Presents results indicate that both approaches have very good potential to solve inverse reliability task using small-sample simulation.

Fig. 1 .

 1 Fig. 1. A flow chart of proposed inverse reliability method.

Table 1 .

 1 Random variables and design parameters

	Variable Distribution	Mean Std	COV
	l [m]	Normal	3.5	0.175 0.05
	b [m]	Normal	?	--	0.05
	h [m]	Normal	?	--	0.05
	E [GPa]	Lognormal (2 par) 10	1.3	0.13
	f m [MPa] Lognormal (2 par) 34	8.5	0.25
	g [kN/m] Gumbel max EV 1 1.686 0.169 0.10
	q [kN/m] Gumbel max EV 1 2.565 0.770 0.30
	θ R [-]	Lognormal (2 par) 1	0.1	0.10
	θ R [-]	Lognormal (2 par) 1	0.1	0.10

Table 2 .

 2 Randomization of design parameters for training set preparation and purpose of optimization

	Variable Distribution Mean Std	a	b
	mean(b) Rectangular 0.125 0.0144 0.10 0.15
	mean(h) Rectangular 0.225 0.0144 0.20 0.25

Table 3 .

 3 Resulting values of design parameters and reliability indices β obtained by double-Evolution of values of reliability indices during optimization

		loop optimization approach
	Approach	mean(b)	mean(h)	β 1	β 2	β 1,target β 2,target
	ANN inverse analysis Double-loop optimization 0.1311555 0.215135 3.793 0.13244 0.21432 3.8001 1.5001 1.50009	3.8	1.5

Acknowledgements

The authors give thanks for the support of the research project No. TA01011019 of Technology Agency of the Czech Republic (TACR) and the European Union's "Operational Programme Research and Development for Innovations", No. CZ.1.05/2.1.00/03.0097, as an activity of the regional Centre AdMaS "Advanced Materials, Structures and Technologies". In this undertaking, theoretical results