=Paper=
{{Paper
|id=Vol-1853/p11
|storemode=property
|title=First approach to solve linear system of equations
by using ant colony optimization
|pdfUrl=https://ceur-ws.org/Vol-1853/p11.pdf
|volume=Vol-1853
|authors=Kamil Ksiażek
|dblpUrl=https://dblp.org/rec/conf/system/Ksiazek17
}}
==First approach to solve linear system of equations
by using ant colony optimization
==
https://ceur-ws.org/Vol-1853/p11.pdf
First approach to solve linear system of equations
by using Ant Colony Optimization
Kamil Ksia˛żek
Faculty of Applied Mathematics
Silesian University of Technology
Gliwice, Poland
Email: kamiksi862@student.polsl.pl
Abstract—This paper illustrates first approach to solve linear where
system of equations by using Ant Colony Optimization (ACO). aij ∈ R, bi ∈ R, i, j ∈ 1, ..., n.
ACO is multi-agent heuristic algorithm working in continuous
domains. The main task is checking efficiency of this method in or in the matrix form:
several examples and discussion about results. There will be also
presented future possibilities regarding researches.
Index Terms—linear system of equations, metaheuristics, Ant A · X = B, (2)
Colony Optimization, analysis of heuristic algorithm
where
I. I NTRODUCTION
Computers help people to perform complex calculations.
a11 a12 ... a1n
They significantly reduce the time required to obtain results a21 a22 ... a2n
and they make not mistakes. There are various aspects of A= . .. ,
.. ..
.. . . .
possible applications. Mainly we want computers to process
information [1], [2], operate on automated systems, and help an1 an2 ... ann
people, like in devoted systems for AAL environments [4], T
[5], [7]. Common usage of computing powers is to process X = x1 x2 . . . xn ,
graphics to detect objects [6], assist in voice processing for T
B = b1 b2 . . . bn .
secure communication [8], help on extraction of important
features [20] and improve images [16].
Another possibility to use computing power is solving It is assumed that A has nonzero determinant - the system
systems of equations. In practice, engineers often have to has a one unique solution.
deal with this problem. Then very important is proper speed
and precision of solutions. Usually, to solve such systems are III. A NT C OLONY O PTIMIZATION
used numerical methods. This paper attempts to use heuristic
algorithms, specifically Ant Colony Optimization to solve Ant Colony Optimization (ACO) is a multi-agent heuristic
linear systems of equations. It has been checked performance algorithm created for finding global minimum of a function.
of this algorithm using few examples. Then results were The inspiration for this method was behaviour of real ant
discussed. colony. ACO was created by M. Dorigo to solving combi-
System of equations were the subject of research many au- natorial problems [12]. M. Duran Toksari developed Dorigo’s
thors. Some information about it is in [3], [10] and [11]. algorithm - he invented a method based on ACO to solving
Section II gives information about linear system of equa- continuous problems [13].
tions. In section III is presented description of Ant Colony The inspiration for this algorithm is the behaviour of ant
Optimization with pseudocode. Section IV shows results and colony during searching food. Ants have a specific method
discussion about it. Finally, it will be presented possibilities to communication. They leave chemical substance called
further studies. pheromone. This allows them to efficiently move - ants can
choose shorter path to the aim. The probability of choice
II. L INEAR SYSTEM OF EQUATIONS the way which has more quantity of pheromone is greater
Consider the following system: - it means that many ants chose already this road. Following
ants reinforce pheromone trace on more efficient track while
a11 x1 + a12 x2 + ... + a1n xn = b1 pheromone is evaporated on the unused path.
a21 x1 + a22 x2 + ... + a2n xn = b2
Other information about ACO is also presented in [14] while
.. (1)
. another approach to using ant system in continuous domain is
in [15].
an1 x1 + an2 x2 + ... + ann xn = bn
Copyright © 2017 held by the authors
57
IV. I MPLEMENTATION
∀k ∈ 1, ..., n xkj = xopt + dx, (4)
Algorithm 1:
Ant Colony Optimization Pseudocode of Ant Colony Opti- where
mization j − number of current iteration,
k − number of vector (solution),
Input: number of ants: m, number of iteration inside: s,
dx = dx1 , dx2 , ..., dxn − vector of pseudorandom values,
number of iteration outside: W, boundary of the domain,
dxi ∈ [−αj , αj ].
initial coefficients: α, λ
Output: coordinates of minimum, value of fitness function (4) means that k − th vector during j − th iteration is the
Initialisation: sum of the best solution (up to j − 1 iterations, actually it is
Creating the initial colony of ants. xopt ) and pseudorandom value from the given neighbourhood.
Searching xbest in initial colony; xopt = xbest . The algorithm is checked if Φ(xbest ) > Φ(xopt ), where xbest
j j
Calculations: is the best solution from j iteration. If the answer is positive,
i=1 xopt = xbest . This step is carried out s times - there are
j
while i < W do s internal iterations. If at least one of new points is better
j=1 approximation of root, it is saved (xopt ). The next step is
while j < s do changing the quantity of pheromone - next solutions should be
Moving the nest of ants - defining new territory of centered around xopt . The main purpose of ACO is narrowing
ant colony. area to search. First steps are in charge of exploration of
Searching xbest
j in present colony. domain - ants seek promising territory on the whole domain.
if xbest
j is better than xopt then Next steps are responsible for exploitation (making solutions
best
xopt = xj more precise). α is core value - it is the current quantity of
end if pheromone. The value of α determines area to search. The
end while domain is reducing according to following formula:
Defining new search area (narrowing of the territory).
end while αj = λ · αj−1 , λ ∈ (0; 1), (5)
end where
The Algorithm 1 presents the pseudocode of Ant Colony j − number of current iteration.
Optimization. The first step is creating m random vectors (ants)
filled values from the given domain. Then is necessary to note The value of λ depends on domain. If the domain is
the quality of these solutions by using fitness function: relatively wide, λ should be equal more than 0.5 - ants should
have more time to find promising territory. In the case narrow
n
X domain λ ≈ 0.1 should be sufficient. Searching is continued
Φ(x) = |bi − xi | (3)
W − 1 times with new values of coefficients - there are W
i=1
external iterations. During following iterations length of the
The function Φ is the sum of errors in all equations of the jump is decreased so solutions would be more accurate.
system. Of course the best values are close to zero. The best
from temporary solutions is saved (called xbest ) and it is V. R ESULTS
provisional place for nest. In this moment xbest is also the A. Tested systems
best solution during the whole search: xopt = xbest . xopt is the The benchmark test was carried out by using Ant Colony
base for next searching step. The successive stage is modifying Optimization on following three linear systems (coefficients
each coordinate of all vectors according to following formula: were chosen randomly):
1) First system (two equations):
55.09730344 38.12917026
A1 = ,
10.57737989 86.52430487
T
X1 = x1 x2 ,
T
B1 = 31.65546153 84.06852453 ,
A1 · X1 = B1 .
Fig. 1 shows the graphic interpretation of 1) while Tab. I
Fig. 1. The graphic interpretation of (7)
presents all measurements.
58
Fig. 4. Result no. 6: value of first coordinate during iterations
Fig. 2. Result no. 3: value of first coordinate during iterations
Fig. 5. Result no. 6: value of second coordinate during iterations
− it is 2), while Tab. II shows all results.
Fig. 3. Result no. 3: value of second coordinate during iterations 3) Third system (four equations):
70.5284618 10.71763084 84.66285422 99.2134024
83.10581887 13.42679705 47.42381202 90.7001626
A3 = ,
17.26132135 71.21872468 74.90622771 0.7129543228
1.882180385 80.30586823 5.591496761 98.8264739
T
2) Second system (three equations): X3 = x1 x2 x3 x4 ,
33.22500927 98.10036269 26.933598 T
A2 = 49.53447496 53.4757128 93.1733063 , B3 = 38.17676472 87.90315455 30.93470124 54.32679192 ,
45.2877606 92.67728226 38.71016574
A3 · X3 = B3 .
T
X2 = x1 x2 x3 ,
T
All measurements from 3) are presented in Tab. III.
B2 = 68.15051868 41.78404012 41.26656061 ,
B. Discussion
A2 · X2 = B2 .
The main advantage of this approach is universality. It is
Fig. 2 demonstrates three planes with the point of intersection not necessary to transform the system of equations to ensure
59
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. C ONCLUSIONS
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
Fig. 6. Result no. 6: value of third coordinate during iterations 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.
R EFERENCES
[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. Woźniak, “Human
Activity Recognition in AAL Environments Using Random Projec-
tions” 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. Woźniak,
“Smartphone User Identity Verification Using Gait Characteris-
tics” Symmetry, vol. 8, no. 10, pp. 100:1–100:20, 2016, DOI:
10.3390/sym8100100.
[6] D. Połap, M. Woźniak, “Flexible Neural Network Architecture for
Handwritten Signatures Recognition” International Journal of Electron-
ics and Telecommunications, vol. 62, no. 2, pp. 197–202, 2016, DOI:
10.1515/eletel-2016-0027.
[7] D. Połap, M. Woź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 Con-
ference on Computer Science and Information Systems, FedCSIS 2016,
Proceedings. 11-14 September, Gdańsk, Poland, IEEE 2016, pp. 487–
Fig. 7. The graphic interpretation of 1)
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
convergence (this step is essential in some numerical methods). Intelligence, IEEE 2014, pp. 1–8, DOI: 10.1109/CIHLI.2014.7013395.
[10] J. R. Rice, “Numerical Methods in Software and Analysis“. Elsevier
Results for xi , i ∈ 1, ..., 4 are presented after rounding. The (2014).
most important information is value of fitness function. It can [11] A. Ralston, P. Rabinowitz, “A First Course in Numerical Analysis“.
be noticed that exactness of results is great. In the case of Courier Corporation (2001).
[12] M. Dorigo, V. Maniezzo, and A. Colorni. “The ant system: An autocat-
system of two equations λ = 0.1 causes that Φ(x) = 0. Fig. alytic optimizing process“. (1991).
3-4 present values of coordinates during following iterations [13] M. Duran Toksarı, “A heuristic approach to find the global optimum
in the case λ = 0.5. The graphs illustrate how ACO works. of function.“ Journal of Computational and Applied Mathematics 209.2
(2007): 160-166.
Through initial few iterations values are hesitating and with [14] M. Dorigo, T. Stützle, “Ant Colony Optimization“, MIT Press, Cam-
decreasing α the algorithm is stabilizing around optimal result. bridge, MA (2004).
60
Table I
R ESULTS - SYSTEM OF 2 EQUATIONS
Precise solution: -0.1068977349, 0.9846854316
number number domain number of inside number of out- initial λ x1 x2 value of the fitness
of iteration side iteration value function
points of α
1) 30 [−5; 5] 20 20 2 0.8 -0.107503 0.984813 0.033121
2) 30 [−5; 5] 20 20 2 0.7 -0.106897 0.9847 0.00184454
3) 30 [−5; 5] 20 20 2 0.5 -0.106898 0.984685 5.79085 ·10−6
4) 30 [−5; 5] 20 20 2 0.4 -0.106898 0.984685 2.05804 ·10−7
5) 30 [−5; 5] 20 20 2 0.1 -0.106898 0.984685 0.
Table II
R ESULTS - SYSTEM OF 3 EQUATIONS
Precise solution: -2.782671100, 1.315084752, 1.173051616
number number domain number of number of initial λ x1 x2 x3 value of the fit-
of inside iter- outside it- value ness function
points ation eration of α
6) 30 [−5; 5] 20 20 2 0.7 -2.7831 1.31511 1.17331 0.0160028
7) 30 [−5; 5] 20 20 2 0.5 -2.82615 1.32503 1.19046 0.37346
8) 30 [−5; 5] 20 20 3 0.5 -2.77983 1.31443 1.17191 0.0244493
9) 30 [−5; 5] 20 20 2 0.45 -2.78489 1.31559 1.17394 0.0190372
10) 30 [−5; 5] 20 20 2 0.4 -2.82968 1.32584 1.19187 0.403732
11) 30 [−5; 5] 20 20 2 0.3 -2.77648 1.31359 1.17062 0.0541228
12) 30 [−5; 5] 20 20 2 0.2 -2.7574 1.30892 1.16316 0.221745
13) 30 [−5; 5] 20 20 2 0.1 -2.90849 1.34566 1.22239 1.10246
Table III
R ESULTS - SYSTEM OF 4 EQUATIONS
Precise solution: 1.486007266, 0.8550637392, -0.7411742368, -0.1314678539
number number domain number of number of initial λ x1 x2 x3 x4 value of the fit-
of inside iter- outside it- value ness function
points ation eration of α
14) 30 [−5; 5] 20 20 2 0.8 1.4945 0.858514 -0.746341 -0.133945 0.352619
15) 30 [−5; 5] 20 20 2 0.7 1.48602 0.854945 -0.741245 -0.131361 0.0240107
16) 30 [−5; 5] 20 20 2 0.6 1.486 0.855079 -0.741185 -0.131464 0.00293356
17) 30 [−5; 5] 20 20 2 0.5 1.48601 0.855063 -0.741174 -0.131468 0.0000864998
18) 30 [−5; 5] 20 20 2 0.45 1.48601 0.855064 -0.741174 -0.131468 0.0000174678
19) 30 [−5; 5] 20 20 2 0.4 1.48601 0.855064 -0.741174 -0.131468 2.3978 ·10−6
20) 30 [−5; 5] 20 20 2 0.3 1.47847 0.852423 -0.736947 -0.129418 0.276773
21) 30 [−5; 5] 20 20 2 0.2 1.51865 0.874344 -0.766887 -0.146302 1.54667
[15] K. Socha, M. Dorigo, “Ant colony optimization for continuous do- 10.1016/j.eswa.2016.08.068.
mains.“ European journal of operational research 185.3 (2008): 1155- [21] L. Zmudzinski, A. Augustyniak, P. Artiemjew, Control of Mindstorms
1173. NXT robot using Xtion Pro camera skeletal tracking, Technical Sciences,
[16] M. Woźniak, “Novel Image Correction Method Based on Swarm Intel- vol. 19, no.1, pp. 71-81, Olsztyn, UWM Publisher, 2016.
ligence Approach,” in Communications in Computer and Information [22] K. Trojanowski, “Metaheurystyki praktycznie“, Warsaw School of In-
Science, vol. 639, pp. 404–413, 2016, DOI: 10.1007/978-3-319-46254- formation Technology, p.7, Warsaw 2008.
7_32.
[17] M. Woź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. Woź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. Woź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. Woźniak, D. Połap, C. Napoli, and E. Tramontana, “Graphic ob-
ject feature extraction system based on Cuckoo Search Algorithm”
Expert Systems with Applications, vol. 60, pp. 20–31, 2016, DOI:
61