APPLICATION OF FINITE AUTOMATA WITH GENETIC ALGORITHMS IN JAVASCRIPT FOR DETERMINATION OF MANPOWER SYSTEM CONTROL

Full Text

Introduction. Controlling of hierarchical manpower system such as military is demanding task [1-6] since the control problem includes several stochastic variables which should be considered, such as time variant boundaries on recruitment, promotions, retirements and wastages. The paper describes the methodology which was developed for the Slovenian Army restructuring [1; 7] where the new numbers of officers in the highest eight ranks should be determined. Due to the new standards, the new ratio should be established between the number of officers and number of soldiers. The structure of the system is shown in fig. 1. The system is modelled as the cascading exponential delay with the outflows as the wastages, i. e. fluctuations from the army. The input u(t) to the system represents recruitment which influences the inflow R0 to the first element x1 which represents the level of the first rank (x1) members (lowest rank). According to the promotion factor r1 the transitions from rank x1 to rank x2 are made. The fluctuations from the rank x1 are determined by the number of the x1 rank members and the fluctuation factor a. Outflow element FA represents the wastage, i. e. the case where the member of the rank leaves the army. This structure is repeated arbitrarily however in our case eight ranks were considered. The system also does not allow for direct input to the particular rank x; the way to the higher ranks is only possible to the recruitment to the first rank, x1 therefore the system is strict hierarchical. In order to define the dynamics of the system the discrete state space is applied in the form x(k + 1) = Ax(k) + Bu(k) [1]. State vector x represents the number of men in particular rank whereas matrix of coefficients A represents promotion factors r and wastage factors f. The only input to the system is recruitment represented by the Bu(k) term in the discrete state space. In order to restructure the army manpower system, the recruitments, promotions, wastages and retirement should be determined in such a way, that new, desired numbers of man in particular rank x are achieved in minimal time. The solutions should not exercise the oscillations since this would lead to the undesired adaptation of training facilities and number of instructors. Another limitation that should be considered, is that the number of recruitments, promotions, wastages and retirement should not deviate significantly from the average numbers in previous 10 years. The novelty of the approach is twofold, on one side, the manpower system is modelled by the System Dynamics methodology, which is easy to understand, on the other side, the model is integrated with the Finite Automata in order to avoid the undesired oscillations in the strategy. Besides, we have developed technical realization of the system in JavaScript which provides new opportunities to apply the developed algorithm in the cloud as well as in the embedded devices [8]. Methodology description. For each rank x, the desired number of man is stated by the Human Resource department in the Slovenian army. This were only the final numbers of men that should be achieved in particular ranks x. Since the system is described by the model of exponential delay chain, it is anticipated, that the transitions will follow exponential functions. By anticipating the system response, the optimization burden could be reduced by the predetermination of the trajectories for states x. The response of the system will be exercised as the exponential approach to the goal values. By the determination of the desired response function one can reduce the optimization search space [9; 10]. In our case we defined the desired response by the function, describing the way in which the number of men in particular rank x should be reached. The following function has been defined: (1) where , represent initial and final value of the state variable x, is terminal time; is simulation time and is importance factor which determines the rate by which the goal is reached. The optimization problem where we want to achieve the desired values, marked with z in the equation (2) considers the minimal distance to the desired values function defined by equation (1): (2) subject to (3) where is time-invariant diagonal matrix of weights reflecting the importance of holding deviations for rank as small as possible; represents the goal trajectory of the system defined by equation (1); tq is terminal time; and vectors of lower and upper boundary for recruitment in rank , respectively; and vectors of lower and upper boundary for transitions r between ranks x, respectively (as well as output of the system from the last rank ); and and vectors of lower and upper boundary for fluctuations, i. e. wastages from rank , respectively. Note that all boundaries are time dependent, which increases the complexity of the addressed optimization problem. Described optimization problem should be augmented by the rule, that the gained strategy should not exercise undesired oscillations [1]. If, for example, the recruitment would oscillate e. g. between 0 and 1000 men/year this would mean, that one should adapt the recruitment facilities accordingly, which would not be desired. In order to get the proper strategies, not exercising the oscillations, the six state automaton is defined which identifies the strategies with undesired oscillations in flows between state variables, where the set of states is , the comparison alphabet , the initial state is and the set of end states is . The transition function of , is defined by the table. Six state automation transition table g l e ↔ S0 S1 S2 S0 ← S1 S1 S3 S1 ← S2 S4 S2 S2 ← S3 S5 S3 S3 ← S4 S4 S5 S4 ← S5 S5 S5 S5 Fig. 1. Structure of the System Dynamics model of manpower system function automaton(r) { var t = 1; // starting value for t is set to 1 for (var i=0; i<r.length; i++) { // loop goes from 0 to string length if (t==1) { // at the starting case t=1 if (r[i+1] < r[i]) { // the value in the next step is lower than at present; going down t = 2; } if (r[i+1] > r[i]) { // the value in the next step is higher than at present; going up t = 4; } } if (t == 2) { // if t=2, it means, that in the previous step we went down if (r[i+1] > r[i]) { // and at the next step, we went up t=3; } } if (t == 3 && r[i+1] < r[i]){//we went once down and once up and at the next step again down t = 0; break; // forbidden combination i.e. oscillation in the control strategy } if (t == 4) { // we went up in the previous step if (r[i+1] < r[i]) { // and go down in the next step t=5; } } if (t == 5) { // if value is first up and then down if (r[i+1] > r[i]) { // and if we go up again at the next step t=0; // we get forbidden combination break; } } if from the beginning of the loop till the end no condition is fulfilled t does not change; meaning r[i+1] = r[i] } if (t==0) { t=10; // we set return value as 10, which is the multiplication factor } else {t=1;} // if there were no forbidden moves, the value of the return multiplication factor is 1 return t; } Fig. 2. Finite automata code realized in JavaScript The described automaton in table A is defined by the following code in JavaScript, which is shown in fig. 2. All the possible states are checked by the set of conditional clauses. Description in the code provides the explanation of particular parts. Realization of the system is shown in the fig. 3 [11]. The system consists of the GA part as well as of simulation part. Initially, the reading of the values from the Graphical User Interface (GUI) is performed. The system main loop is started, following the conversion of decimal values to binary values since the algorithm works on the converted binary numbers. This is needed, since the parameters are from continuous number set. In the next step the computation of the Fitness Function (FF) is performed. The input vector for the simulation model is prepared and simulation is started for the prescribed number of simulation time steps. At each new simulation run the model is reset. After simulation stop time is reached, the results are either evaluated with FA in order to punish the oscillations or not, which is also one of the options. After the simulation is performed, the minimum and maximum in the population is determined. The fitness vector is then normalized in order to use it at the roulette wheel selection for the new population generation. The crossing of the genomes follows with the elitism selection in order to transfer the best solution to the next population. After the new matrix is formed the mutation is done. In the next step the output of the results is provided. The Main Loop then continues until the final number of steps in the optimization procedure is achieved. In the next step the elapsed time is printed out as well as results and corresponding graphs. Fig. 4 shows example of the results comparing the desired trajectory and achieved solution for three ranks. The optimization was run with the population of size 10, mutation rate 0.01 with applied FA for 250 timesteps. The optimization time was 206s. The time could be significantly improved by the decreasing the size of the population, for example the run with the population size 3 would take 35s providing similar results however, the convergence of the optimization should also be considered. Since the mobile devices are limited in the processing power, we have investigated the influence of the population size to the convergence of the optimization procedure. We have applied three different sizes of population, 2, 5 and 10 and perform four optimization runs for each. Fig. 5 shows the average value of the fitness function for different population size. Value 0 would mean 0 deviation from the desired values. One can observe, that the population of size 5 or 10 provides approximately the same convergence however, the population of size 3 converges rather slowly. Nevertheles, the average time of the optimization is significantly different; for Population of size 3 the optimization time is 36s, for Population of size 5, 116s and Population of size 10 228s. Therefore the smaller population size might lead to acceptable solutions quicker however, too small population would converge rather slowly. Fig. 3. GA with included SD simulation model and optional FA for elimination of oscillatory solutions Realization of the optimization system. The prototype realization of the SD manpower transition model with GA as well as finite automaton was done in JavaScript. The speed of the solution search depends on the mobile device applied which is satisfactory for the smaller problems. Important aspect here is, that the model with the optimization could easily be accessed and applied in the cloud. Fig. 6 shows actual screenshot of the realization of the Genetic Algorithm with Finite Automaton in JavaScritpt running on the mobile phone. One could observe the call of the code from the server meaning, that the same code could be distributed and used on any mobile device running JavaScript. This includes all modern mobile phones as well as other smart devices such as Smart TVs etc. This is convenient for the easy application of the system for the determination of manpower strategies with various simulation models [12-15] not only from the field of manpower management. There are also other benefits, for example possibility of development of parallel algorithm on embedded devices with the node.js technology [16]. Since the mobile devices are limited in processing power, the code could also be run on the server which would significantly improve the time performance of the system. Fig. 4. Example of the results comparing the desired trajectory and achieved solution Fig. 5. Results of the experiment with different population sizes (10 - left, 3 - right) Fig. 6. Realisation of the Genetic Algorithm with Finite Automaton in JavaScritpt running in the browser Conclusion. Application of the prescribed trajectory function provided the reduction of the optimization problem of searching for the proper strategy in hierarchical manpower system. Here we assumed the exponential approach to the desired states. The addition of the described finite automaton was efficient at the elimination of strategies that examined oscillations. The implementation of the model as well as genetic algorithm with finite automata was successfully performed in JavaScript providing several benefits at the implementation, especially possibility to easily run the same code on the server, in parallel or on the embedded devices. Performed experiments show that careful selection of the population size might lead to better time performance of optimization. Directions of the future research include an automation of the optimization procedure adjustment through the genetic algorithm self-configuration [17; 18] or the use of the swarm optimization cooperative method [19] as well as the automated identification of the dynamic system from the description of their state [20].

About the authors

A. Škraba

Cybernetics & Decision Support Systems Laboratory

Email: andrej.skraba@fov.uni-mb.si
Kidričeva cesta, 55a, Kranj, SI-4000, Slovenia

D. Kofjač

Cybernetics & Decision Support Systems Laboratory

Kidričeva cesta, 55a, Kranj, SI-4000, Slovenia

A. Žnidaršič

Cybernetics & Decision Support Systems Laboratory

Kidričeva cesta, 55a, Kranj, SI-4000, Slovenia

Č. Rozman

Cybernetics & Decision Support Systems Laboratory

Kidričeva cesta, 55a, Kranj, SI-4000, Slovenia

M. Maletič

Cybernetics & Decision Support Systems Laboratory

Kidričeva cesta, 55a, Kranj, SI-4000, Slovenia

References

Supplementary files