First approach to solve linear system of equations by using Ant Colony Optimization

Abstract

-This paper illustrates first approach to solve linear system of equations by using Ant Colony Optimization (ACO). ACO is multi-agent heuristic algorithm working in continuous domains. The main task is checking efficiency of this method in several examples and discussion about results. There will be also presented future possibilities regarding researches. Index Terms-linear system of equations, metaheuristics, Ant Colony Optimization, analysis of heuristic algorithm

-

Computers help people to perform complex calculations. They significantly reduce the time required to obtain results and they make not mistakes. There are various aspects of possible applications. Mainly we want computers to process information [ 1 ], [ 2 ], operate on automated systems, and help people, like in devoted systems for AAL environments [ 4 ], [ 5 ], [ 7 ]. Common usage of computing powers is to process graphics to detect objects [ 6 ], assist in voice processing for secure communication [ 8 ], help on extraction of important features [ 20 ] and improve images [ 16 ].

Another possibility to use computing power is solving systems of equations. In practice, engineers often have to deal with this problem. Then very important is proper speed and precision of solutions. Usually, to solve such systems are used numerical methods. This paper attempts to use heuristic algorithms, specifically Ant Colony Optimization to solve linear systems of equations. It has been checked performance of this algorithm using few examples. Then results were discussed.

System of equations were the subject of research many authors. Some information about it is in [ 3 ], [ 10 ] and [ 11 ].

Section II gives information about linear system of equations. In section III is presented description of Ant Colony Optimization with pseudocode. Section IV shows results and discussion about it. Finally, it will be presented possibilities further studies.

II. LINEAR SYSTEM OF EQUATIONS Consider the following system: 8 a11x1 + a12x2 + ::: + a1nxn = b1 > >>< a21x1 + a22x2 + ::: + a2nxn = b2 .

. > . > >: an1x1 + an2x2 + ::: + annxn = bn (1) where aij 2 R; bi 2 R; i; j 2 1; :::; n. or in the matrix form: where

A

X = B; (2) 0a11

: : : a1n 1 : : : . . .

a2n C . C, .. CA an2 : : : ann X = x1

x2 : : : xn B = b1 b2 : : : bn

It is assumed that A has nonzero determinant - the system has a one unique solution.

III. ANT COLONY OPTIMIZATION

Ant Colony Optimization (ACO) is a multi-agent heuristic algorithm created for finding global minimum of a function. The inspiration for this method was behaviour of real ant colony. ACO was created by M. Dorigo to solving combinatorial problems [ 12 ]. M. Duran Toksari developed Dorigo’s algorithm - he invented a method based on ACO to solving continuous problems [ 13 ].

The inspiration for this algorithm is the behaviour of ant colony during searching food. Ants have a specific method to communication. They leave chemical substance called pheromone. This allows them to efficiently move - ants can choose shorter path to the aim. The probability of choice the way which has more quantity of pheromone is greater - it means that many ants chose already this road. Following ants reinforce pheromone trace on more efficient track while pheromone is evaporated on the unused path.

Other information about ACO is also presented in [ 14 ] while another approach to using ant system in continuous domain is in [ 15 ].

IV. IMPLEMENTATION

Algorithm 1: Ant Colony Optimization Pseudocode of Ant Colony Optimization Input: number of ants: m, number of iteration inside: s, number of iteration outside: W, boundary of the domain, initial coefficients: ; Output: coordinates of minimum, value of fitness function Initialisation: Creating the initial colony of ants.

Searching xbest in initial colony; xopt = xbest.

Calculations: i = 1 while i < W do j = 1 while j < s do

Moving the nest of ants - defining new territory of ant colony.

Searching xbest in present colony.

j if xbest is better than xopt then

j xopt = xbest

j end if end while

Defining new search area (narrowing of the territory). end while end

The Algorithm 1 presents the pseudocode of Ant Colony Optimization. The first step is creating m random vectors (ants) filled values from the given domain. Then is necessary to note the quality of these solutions by using fitness function: n (x) = X jbi i=1 xij (3) The function is the sum of errors in all equations of the system. Of course the best values are close to zero. The best from temporary solutions is saved (called xbest) and it is provisional place for nest. In this moment xbest is also the best solution during the whole search: xopt = xbest. xopt is the base for next searching step. The successive stage is modifying each coordinate of all vectors according to following formula: 8k 2 1; :::; n xjk = xopt + dx; (4) where j number of current iteration, k number of vector (solution), dx = dx1; dx2; :::; dxn vector of pseudorandom values, dxi 2 [ j ; j ]. (4) means that k th vector during j th iteration is the sum of the best solution (up to j 1 iterations, actually it is xopt) and pseudorandom value from the given neighbourhood. The algorithm is checked if (xjbest) > (xopt), where xjbest is the best solution from j iteration. If the answer is positive, xopt = xbest. This step is carried out s times - there are j s internal iterations. If at least one of new points is better approximation of root, it is saved (xopt). The next step is changing the quantity of pheromone - next solutions should be centered around xopt. The main purpose of ACO is narrowing area to search. First steps are in charge of exploration of domain - ants seek promising territory on the whole domain. Next steps are responsible for exploitation (making solutions more precise). is core value - it is the current quantity of pheromone. The value of determines area to search. The domain is reducing according to following formula: j = j 1; 2 (0; 1); (5) where j

number of current iteration.

The value of depends on domain. If the domain is relatively wide, should be equal more than 0.5 - ants should have more time to find promising territory. In the case narrow domain 0:1 should be sufficient. Searching is continued W 1 times with new values of coefficients - there are W external iterations. During following iterations length of the jump is decreased so solutions would be more accurate.

V. RESULTS

A. Tested systems

The benchmark test was carried out by using Ant Colony Optimization on following three linear systems (coefficients were chosen randomly):

1) First system (two equations): A1 = 3) Third system (four equations): 2) Second system (three equations): 033:22500927 45:2877606 98:10036269 , A2

X2 = B2. convergence (this step is essential in some numerical methods). Results for xi; i 2 1; :::; 4 are presented after rounding. The most important information is value of fitness function. It can be noticed that exactness of results is great. In the case of system of two equations = 0:1 causes that (x) = 0. Fig. 3-4 present values of coordinates during following iterations in the case = 0:5. The graphs illustrate how ACO works. Through initial few iterations values are hesitating and with decreasing the algorithm is stabilizing around optimal result.

Accuracy of results for the system of three equations was the highest for = 0:7: (x) = 0:0160028. This process is shown on Fig. 5-7. In the case of system of four equations the most effective was = 0:4: (x) = 2:3978 10 6.

It is necessary to see that the number of iteration was relatively small. The results would be improved by manipulating initial value of , value of or number of iteration. It is possible to say that approximation in the studied cases is satisfactory.

VI. CONCLUSIONS

This paper presents first approach to solve linear systems of equations by using heuristic method (strictly speaking Ant Colony Optimization). There was analyzed three systems (with 2, 3 and 4 variables). This method can be developed in the future. First of all, one can try to use heuristic algorithms to nonlinear systems of equations. There exist less numerical methods to this kind of tasks so heuristic methods may be useful. It is possible to apply some modifications for instance ACO with Local Search or other hybrid algorithm. This topic will be expanded and improved. number of inside iteration 20 20 20 20 20 Precise solution: -0.1068977349, 0.9846854316 number of out- initial x1 side iteration value

of 20 2 0.8 20 2 0.7 20 2 0.5 20 2 0.4 20 2 0.1 -0.107503 -0.106897 -0.106898 -0.106898 -0.106898 1.31511 1.32503 1.31443 1.31559 1.32584 1.31359 1.30892 1.34566

Table III

RESULTS - SYSTEM OF 4 EQUATIONS -0.746341 -0.741245 -0.741185 -0.741174 -0.741174 -0.741174 -0.736947 -0.766887 x4 -0.133945 -0.131361 -0.131464 -0.131468 -0.131468 -0.131468 -0.129418 -0.146302 value of the fitness function 0.352619 0.0240107 0.00293356 0.0000864998 0.0000174678 2.3978 10 6 0.276773 1.54667 x2 x3 value of the fitness function

value of the fitness function

References

[1] P. Artiemjew , Stability of Optimal Parameters for Classifier Based on Simple Granules of Knowledge , Technical Sciences , vol. 14 , no. 1 , pp. 57 - 69 . UWM Publisher, Olsztyn 2011 .

[2] P. Artiemjew , P. Gorecki , K. Sopyła , Categorization of Similar Objects Using Bag of Visual Words and k - Nearest Neighbour Classifier , Technical Sciences , vol. 15 , no. 2 , pp. 293 - 305 , UWM Publisher , Olsztyn 2012 .

[3] D. R. Kincaid , and E. W. Cheney . “ Numerical analysis: mathematics of scientific computing . Vol. 2 .“. American Mathematical Soc . ( 2002 ).

[4] R. Damasevicius , M. Vasiljevas , J. Salkevicius , M. Woz´niak, “Human Activity Recognition in AAL Environments Using Random Projections” Comp . Math. Methods in Medicine, vol. 2016 , pp. 4073584 : 1 - 4073584 : 17 , 2016 , DOI: 10.1155/ 2016 /4073584.

[5] R. Damasevicius , R. Maskeliunas , A. Venckauskas , M. Woz´niak, “Smartphone User Identity Verification Using Gait Characteristics” Symmetry , vol. 8 , no. 10 , pp. 100 : 1 - 100 : 20 , 2016 , DOI: 10.3390/sym8100100.

[6] D. Połap , M. Woz´niak, “Flexible Neural Network Architecture for Handwritten Signatures Recognition” International Journal of Electronics and Telecommunications , vol. 62 , no. 2 , pp. 197 - 202 , 2016 , DOI: 10.1515/eletel-2016-0027.

[7] D. Połap , M. Woz´niak, “ Introduction to the Model of the Active Assistance System for Elder and Disabled People,” in Communications in Computer and Information Science , vol. 639 , pp. 392 - 403 , 2016 , DOI: 10.1007/978-3- 319 -46254-7_ 31 .

[8] D. Połap , “ Neuro-heuristic voice recognition , ” in 2016 Federated Conference on Computer Science and Information Systems, FedCSIS 2016 , Proceedings. 11 -14 September, Gdan´sk, Poland, IEEE 2016 , pp. 487 - 490 , DOI: 10.15439/2016F128.

[9] C. Napoli , G. Pappalardo , E. Tramontana , Z. Marszałek , D. Połap , M. Wozniak, “ Simplified firefly algorithm for 2d image key-points search,” in IEEE Symposium on Computational Intelligence for Human-like Intelligence , IEEE 2014 , pp. 1 - 8 , DOI: 10.1109/CIHLI. 2014 . 7013395 .

[10] J. R. Rice , “ Numerical Methods in Software and Analysis“ . Elsevier ( 2014 ).

[11] A. Ralston , P. Rabinowitz, “ A First Course in Numerical Analysis“ . Courier Corporation ( 2001 ).

[12] M. Dorigo , V. Maniezzo , and A. Colorni . “ The ant system: An autocatalytic optimizing process“ . ( 1991 ).

[13] M. Duran Toksarı , “ A heuristic approach to find the global optimum of function . “ Journal of Computational and Applied Mathematics 209.2 ( 2007 ): 160 - 166 .

[14] M. Dorigo , T. Stützle, “Ant Colony Optimization“, MIT Press, Cambridge, MA ( 2004 ).

[15] K. Socha , M. Dorigo, “ Ant colony optimization for continuous domains .“ European journal of operational research 185.3 ( 2008 ): 1155 - 1173 .

[16] M. Woz ´niak, “Novel Image Correction Method Based on Swarm Intelligence Approach ,” in Communications in Computer and Information Science , vol. 639 , pp. 404 - 413 , 2016 , DOI: 10.1007/978-3- 319 -46254- 7_ 32 .

[17] M. Woz ´niak, D. Połap , M. Gabryel , R.K. Nowicki , C. Napoli , E. Tramontana, “ Can we process 2d images using artificial bee colony?” . In International Conference on Artificial Intelligence and Soft Computing , pp. 660 - 671 , 2015 .

[18] D. Połap , M. Woz´niak, , C. Napoli, and E. Tramontana, “Is swarm intelligence able to create mazes?” International Journal of Electronics and Telecommunications , vol. 61 , No. 4 , pp. 305 - 310 , 2015 , DOI: 10.1515/eletel-2015-0039.

[19] D. Połap , M. Woz´niak, , C. Napoli, and E. Tramontana, “ Real-Time Cloud-based Game Management System via Cuckoo Search Algorithm” International Journal of Electronics and Telecommunications , vol. 61 , No. 4 , pp. 333 - 338 , 2015 , DOI: 10.1515/eletel-2015-0043.

[20] M. Woz ´niak, D. Połap , C. Napoli , and E. Tramontana, “ Graphic object feature extraction system based on Cuckoo Search Algorithm” Expert Systems with Applications , vol. 60 , pp. 20 - 31 , 2016 , DOI: 10.1016/j.eswa. 2016 . 08 .068.

[21] L. Zmudzinski , A. Augustyniak , P. Artiemjew , Control of Mindstorms NXT robot using Xtion Pro camera skeletal tracking , Technical Sciences , vol. 19 , no. 1 , pp. 71 - 81 , Olsztyn, UWM Publisher, 2016 .

[22] K. Trojanowski , “Metaheurystyki praktycznie“, Warsaw School of Information Technology, p. 7 , Warsaw 2008 .