Genetic algorithm and numerical methods for solving linear and nonlinear system of equations: a comparative study

Abstract

The problem of solving linear and nonlinear system of equations is a largely useful issue of significant importance such as that it is presented on real-time applications. Different numerical methods such as fixed-point, Newton Raphson, bisection and secant methods, and or others, namely; evolutionary and computational methods are used to solve nonlinear system under optimizing the space and time complexity. Genetic Algorithm (GA) proved to be an efficient soft computing approach to solve many linear/non-linear system of equations. In this article, a comparison between different GAs and numerical methods for solving a system of equations are introduced. From the results, a novel approach is introduced which is inspired by using a modified GA to get the optimistic solution for the system which has no numerical solution and verified with the highest performance measures in solving complicated problems.

Keywords

Linear system equations non-linear system equations genetic algorithms numerical optimization and Newton-Raphson

1 Introduction

Solving system of nonlinear equations arise in many domains of practical importance such as engineering, mechanics, medicine, chemistry, and robotics. Most of the time finding an exact solution is kind of impossible task (due to singularity of the coefficients matrix). Solving such a system involves finding all the approximated solutions. The successful application of the multi objective optimization (MOO) approaches is well known and there is a large amount of work in this field reporting applications in different domains in science and engineering. One approach is based on Pareto-based multi objective evolutionary algorithms applied to a real-world power system as multi objective nonlinear optimization problem [1 –5]. Specifically, the non-dominated sorting genetic algorithm (NSGA) [6, 7], For environmental and economic electric power dispatch problem the algorithm of niched Pareto GA and strength Pareto evolutionary are built and applied. It can be shown that when dealing with the MOO of the tire suspension system of a racing car, the large numbers of variables and objectives must be considered given a fuzzy definition of optima, presented as a generalization of Pareto optimality, and the result of such approach considered as a subsets of Pareto solutions can be legitimately chosen as a result of contribution from the designer [2]. The optimal solutions were obtained and compared with the previously results based on the design of experiment techniques and different MOO strategies.

A non-linear system of equations ψ₁, ψ₂, ..., ψ_n is defined in terms of n variables (z_1, z_2,..., z_n) as $ψ (z) = [\begin{matrix} ψ_{1} (z)_{,} \\ ψ_{2} (z) \\ ⋮ \\ ψ_{n} (z) \end{matrix}]$ (1) Let Ω be an open set in Rⁿ, where Ω of real continuous functions, the nonlinear functions defined by $Ω = \prod_{i = 1}^{n} [a_{i}, b_{i}] \subset R^{n}$ (2) which written in the form ${\begin{matrix} ψ_{1} (z_{1,} z_{2,} . . ., z_{n}) = 0 \\ ψ_{2} (z_{1,} z_{2,} . . ., z_{n}) = 0 \\ ⋮ \\ ψ_{n} (z_{1,} z_{2,} . . ., z_{n}) = 0 \end{matrix}$ (3) For discussion, this paper is organized as follows. In section 2, the steps to modify the genetic algorithm (GA) were first introduced as well as Newton’s algorithm as one of the numerical approach used. In Section 3, results of the simulation are provided that confirm and demonstrate the effectiveness of a modified GA, in comparison to the Newton’s algorithm. Finally, conclusions are presented in Section 4.

2 Algorithms

2.1 Genetic algorithm (GA)

As known that Biologists have applied genetic science to find the information that passed from parents to children by the genes. In this regard the GA have been used for different optimization problems in many branches of sciences such as engineering, biology, economics, image processing and physics [6, 8]. Also, GAs have been solved MOO problems and were implemented in applications for a long time [9 –12].

The modified GA is listed as following steps

1. The current candidate solutions for the proposed problem can be generated a random set of chromosomes, which can be considered.

2. For fitness values of each chromosome is evaluated (Fitness values are used in genetic algorithms to guide simulations towards optimal design solutions).

3. The better solution obtained by sorting from the lowest fitness chromosomes.

4. Clone the better chromosomes in order to extend the good attributes through the population.

5. The new springs is obtained from parent chromosomes to perform a crossover operation.

6. Under a small predefined ratio Mutate the chromosomes.

7. The new fitness values of each chromosome is evaluted.

8. Steps from 3 to 7 are repeated for non-minimum error criterion is reached.

The evolution that occurs to individuals of the population over generations usually begings randomly so that in each generation each individuals of the population, the appropriateness of each member of the population is assessed, the current population are that selected based on their fitness, and modified (reintegrated and possibly mutated) to form another new population. As given in timetabling, scheduling, and travelling sales man’s problem, the GA is applied in different problems which present the successfully methods in optimization problems. It depends on the concept of developing solution acording derterimined fitness function to stochastically developing generations of solution population to determine the best fit solution to the problem. The application GA in obtaining solutions of system of nonlinear equations simultaneous is presented as the main objective of this paper which contain a search for optimal values for the unknown variables in some equations to discribe the best fit the system. Also, the competence and efficiency of GA is compared with the others numerical methods.

2.2 Newton’s method

In numerical analysis, Newton’s method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson.

Let us assume that zⁱ be a guessed value, based on extrapolation one can find another better guess where the function will be updated [13 –15].

$\begin{matrix} [\begin{matrix} ψ_{1} (z_{1}^{i} + {dz}_{1})_{,} \\ ψ_{2} (z_{2}^{i} + {dz}_{2}) \\ ⋮ \\ ψ_{n} (z_{n}^{i} + {dz}_{n}) \end{matrix}] \\ = [\begin{matrix} ψ_{1} (z_{1}^{i})_{,} \\ ψ_{2} (z_{2}^{i}) \\ ⋮ \\ ψ_{n} (z_{n}^{i}) \end{matrix}] + [\begin{matrix} \frac{\partial ψ_{1}}{\partial z_{1}} {dz}_{1}, \frac{\partial ψ_{2}}{\partial z_{2}} {dz}_{2}, . . ., \frac{\partial ψ_{n}}{\partial z_{n}} {dz}_{n} \\ \frac{\partial ψ_{1}}{\partial z_{1}} {dz}_{1}, \frac{\partial ψ_{2}}{\partial z_{2}} {dz}_{2}, . . ., \frac{\partial ψ_{n}}{\partial z_{n}} {dz}_{n} \\ ⋮ \\ \frac{\partial ψ_{1}}{\partial z_{1}} {dz}_{1}, \frac{\partial ψ_{2}}{\partial z_{2}} {dz}_{2}, . . ., \frac{\partial ψ_{n}}{\partial z_{n}} {dz}_{n} \end{matrix}] . \end{matrix}$ (4) Can be written as $\begin{matrix} [\begin{matrix} ψ_{1} (z_{1}^{i} + {dz}_{1})_{,} \\ ψ_{2} (z_{2}^{i} + {dz}_{2}) \\ ⋮ \\ ψ_{n} (z_{n}^{i} + {dz}_{n}) \end{matrix}] \\ = [\begin{matrix} ψ_{1} (z_{1}^{i})_{,} \\ ψ_{2} (z_{2}^{i}) \\ ⋮ \\ ψ_{n} (z_{n}^{i}) \end{matrix}] + [\begin{matrix} \frac{\partial ψ_{1}}{\partial z_{1}}, \frac{\partial ψ_{2}}{\partial z_{2}}, . . ., \frac{\partial ψ_{n}}{\partial z_{n}} \\ \frac{\partial ψ_{1}}{\partial z_{1}}, \frac{\partial ψ_{2}}{\partial z_{2}}, . . ., \frac{\partial ψ_{n}}{\partial z_{n}} \\ ⋮ \\ \frac{\partial ψ_{1}}{\partial z_{1}}, \frac{\partial ψ_{2}}{\partial z_{2}}, . . ., \frac{\partial ψ_{n}}{\partial z_{n}} \end{matrix}] [\begin{matrix} {dz}_{1} \\ {dz}_{2} \\ ⋮ \\ {dz}_{n} \end{matrix}] \end{matrix}$ (5) hence $[\begin{matrix} ψ_{1} (z_{1}^{i} + {dz}_{1})_{,} \\ ψ_{2} (z_{2}^{i} + {dz}_{2}) \\ ⋮ \\ ψ_{n} (z_{n}^{i} + {dz}_{n}) \end{matrix}] = [\begin{matrix} ψ_{1} (z_{1}^{i})_{,} \\ ψ_{2} (z_{2}^{i}) \\ ⋮ \\ ψ_{n} (z_{n}^{i}) \end{matrix}] + \underline{Jdz},$ (6) or $\underline{G} (\underline{z^{k}} + d \underline{z}) = \underline{G} (\underline{z^{k}}) + Jd \underline{z} .$ (7) We dfine a new vector z^k+1 = z^k + dz to as a good approximation to the solution, so we set G (z^k+1) =0 in terms of the Jacobian matrix J as G (z^k+1) = Jdz.

Newton algorithm

1. The function values is evaluated at the guessed value z^k = [z₁, z₂, . . . , z_n] ^T.

2. The Jacobian matrix J is calculated within the current guess for the solution.

3. The solution of the proposed inear system is formulated as G (z^k) = Jdz for the values of dz .

4. The guessed value is updated as z^k+1 = z^k + dz .

By repeated, the above procedure based on the updated value of z^k as the guess, until the values of G (z) are close to zero. Hence G (z). This minimize the difference between right and left side over the absolute value to equation. Also, this is described by the absolute value of the left term since the right term is zero. Hence, the two system (8) and is equivalent and given as follows

${\begin{matrix} ψ_{1} (z_{1,} z_{2,} . . ., z_{n}) = 0 \\ ψ_{2} (z_{1,} z_{2,} . . ., z_{n}) = 0 \\ ⋮ \\ ψ_{n} (z_{1,} z_{2,} . . ., z_{n}) = 0 \end{matrix}$ (8) and ${\begin{matrix} min (ψ_{1} (z_{1,} z_{2,} . . ., z_{n})) \\ min (ψ_{2} (z_{1,} z_{2,} . . ., z_{n})) \\ ⋮ \\ min (ψ_{n} (z_{1,} z_{2,} . . ., z_{n})) \end{matrix}$ (9)

3 Experiments and results

In this section, we reported to comparisons to obtaining results from a set of experiments by using the proposed approach. Applications that considered in this section will be considered in the subsequent section.

3.1 Example: combustion chamber problem

3.1.1 Numerical approach

As kown that the process of combustion is increased in the internal energy of a gas. These incereasing lead to increasing volume, pressure, or temperature depending on the configuration. In cylinder of a reciprocating engine as other example, we control of the volume level and combustion creates an increase in pressure in a continuous flow system [16], according to the combustion problem we consider a temperature of 3000°C.

The target problem can be formulated as: ${\begin{matrix} ψ_{1} = z_{2} + 2 z_{6} + z_{9} + 2 z_{10} - 10^{- 5} = 0 \\ ψ_{2} = z_{3} + z_{8} - 10^{- 5} = 0 \\ ψ_{3} = z_{1} + z_{3} + 2 z_{5} + 2 z_{8} + z_{9} + z_{10} - 5 = 0 \\ ψ_{4} = z_{4} + 6 z_{7} - 10^{- 5} = 0 \\ ψ_{5} = 0.5140437 . 10^{- 5} z_{5} - z_{1}^{2} = 0 \\ ψ_{6} = 0.1006932 . 10^{- 6} z_{6} - 2 z_{2}^{2} = 0 \\ ψ_{7} = 0.7816278 . 10^{- 15} z_{7} - z_{4}^{2} = 0 \\ ψ_{8} = 0.1496236 . 10^{- 6} z_{8} - z_{1} . z_{3} = 0 \\ ψ_{9} = 0.6194411 . 10^{- 7} z_{9} - z_{1} . z_{2} = 0 \\ ψ_{10} = 0.2089296 . 10^{114} z_{10} - z_{1} . z_{2}^{2} = 0 \end{matrix}$ (10)

Table 1

The output of normal combustion Chamber model under numerical approach

z values	ψ values
0.0015e-4	0
0.0023e-4	0
0.1513e-4	0
0.0000e-4	0
0.0042e-4	–3.15544e-30
0.0101e-4	1.64083e-28
0.0499e-4	–3.71229e-19
0.1487e-4	4.03896e-28
0.0053e-4	–6.31088e-30
0.0360e-4	–1.05324e-35

3.1.2 Genetic approach

Table 2
The output of normal combustion Chamber model under GA approach (see Fig. (1))

z values ψ values

0.00000 0.7553662

0.35038 0.0155950

–0.98437 0.0618200

0.75690 0.8557323

0.00000 0.0000000

0.75000 0.2455407

0.04941 0.5729064

1.00000 0.0000001

–0.81250 0.0000000

–0.141251 0.0000000

z values	ψ values
0.00000	0.7553662
0.35038	0.0155950
–0.98437	0.0618200
0.75690	0.8557323
0.00000	0.0000000
0.75000	0.2455407
0.04941	0.5729064
1.00000	0.0000001
–0.81250	0.0000000
–0.141251	0.0000000

3.2 Complicated combustion chamber model

3.2.1 Numerical approach

The coefficients matrix is almost singular, no solution could be found.

3.2.2 Genetic approach

This system is a complicated version of the combustion chamber model, the system can be represented as follows:

${\begin{matrix} ψ_{1} = z_{3} z_{2} z_{5} + 2 z_{10} + 2 z_{10} + - 10^{- 5} = 0 \\ ψ_{2} = z_{3} z_{2} + z_{8} - 3 . 10^{- 5} = 0 \\ ψ_{3} = z_{1} + z_{3} z_{2} + 2 z_{5} + 3 z_{8} + z_{9} + z_{10} \\ - 5 . 10^{- 5} = 0 \\ ψ_{4} = z_{4} + 2 z_{7} - 10^{- 5} = 0 \\ ψ_{5} = 0.5140437 . 10^{- 7} z_{5} - z_{1} sin z_{1} cos (z_{3} z_{2}) = 0 \\ ψ_{6} = 0.1006932 . 10^{- 6} z_{6} - 2 z_{5} z_{2} z_{3} sin z_{1} \\ \times cos (z_{3} z_{2}) = 0 \\ ψ_{7} = 0.7816278 . 10^{- 15} z_{7} - z_{4}^{2} = 0 \\ ψ_{8} = 0.1496236 . 10^{- 6} z_{8} - z_{1} . z_{3} = 0 \\ ψ_{9} = 0.6194411 . 10^{- 7} z_{9} - z_{1} z_{2} z_{3} z_{5} = 0 \\ ψ_{10} = 0.2089296 . 10^{114} z_{10} - z_{1} z_{2} z_{3} z_{5} sin z_{1} \\ \times cos (z_{3} z_{2}) = 0 \end{matrix}$ (11)

Table 3

The output of normal combustion Chamber model under GA approach (see Figs. (2,3))

z values	ψ values
0.0060	0.0584
0.0091	0.0145
0.0114	0.0366
–0.0111	0.0227
–0.0098	0.0000
0.0403	0.0000
0.0169	0.0001
–0.0145	0.0000
–0.0201	0.0000
–0.0010	0.0000

3.3 Robot kinematics problem

3.3.1 Numerical approach

The coefficients matrix is singular, no solution could be found. The problem determinted of there are a given a 6-revolute manipulator (links or rigid-bodies that connected together by joints to each link connected to not more than two others) [2, 10]. The first step is visulaze the link designated the base, and the last link designated the hand of the robot. In this case the problem is determined by a possible positions of the hand, given that the joints are movable. This problem is shown to be The solution of a system of eight nonlinear Equations is equivalent this problem. If the solution of a system isdefined by where in eight unknowns z = {z₁, z₂, … . . , z₈} ∈ [-1, 1] ⁸ . The problem can be stated as: ${\begin{matrix} ψ_{1} = 4.731 . 10^{- 3} z_{1} z_{3} - 0.3578 z_{2} z_{3} - 0.123 z_{1} \\ + z_{7} - 1.637 . 10^{- 1} z_{4} - 0.3571 = 0 \\ ψ_{2} = 0.2238 z_{1} z_{3} + 0.7623 z_{2} z_{3} + 0.2638 z_{1} - z_{7} \\ - 0.07745 z_{2} - 0.6734 z_{4} - 0.6022 = 0 \\ ψ_{3} = z_{6} z_{8} + 0.3578 z_{1} + 4.7361 . 10^{- 3} z_{2} = 0 \\ ψ_{4} = - 0.7623 z_{1} + 0.2238 z_{2} + 0.3461 = 0 \\ ψ_{5} = z_{1}^{2} + z_{2}^{2} - 1 = 0 \\ ψ_{6} = z_{3}^{2} + z_{4}^{2} - 1 = 0 \\ ψ_{7} = z_{5}^{2} + z_{6}^{2} - 1 = 0 \\ ψ_{8} = z_{7}^{2} + z_{8}^{2} - 1 = 0 \end{matrix}$ (12)

Table 4

Results for solving Robot Kinematics problem Model using GA (see Fig. (4))

z values	ψ values
0.5871	0.0000
0.9582	0.2856
0.9195	0.2100
–0.1167	0.1130
–0.4913	0.2628
–0.3954	0.1410
0.6350	0.6023
0.0117	0.5966

Fig.1

Pareto fron.

Fig.2

GA Analysis for Complicated.

Fig.3

Genatic analysis for complicated cobasition Camber.

Fig.4

GA Analysis for Robot Kinematics problem.

4 Conclusions

Numerical approaches can find the exact solution for most of the Linear/Non-linear systems. Some of the Linear/Nonlinear systems have no exact solution, in other words the coefficient matrix is almost singular. In this type of system, we look for the closest solution which solves the system. One of the best and easy approaches is the genetic optimization approach. In this work, this criterion is approved by using a modified GA to get the optimistic solution for the system which has no numerical solution. Compared with the Newton, GA makes the global solution more efficient and accelerates the convergence speed. The genetic choosing operation was enhanced through the artificial selection and immigration operator. Moreover, GA proves the ability to find many solutions close to the exact solution. The best solution is found which minimizes the error with the exact. Whereas, the numerical approach finds no solution.

Footnotes

Acknowledgment

This work was founded by the Deanship of Scientific Research (DSR), King Abdulaziz University, Jeddah, Saudi Arabia under grant no. (D-000-000-1441). The authors, therefore, acknowledge with thanks DSR technical and financial support.

References

Madalina

M.D.

, Multi-objective optimization perspectives on reinforcement learning algorithms using reward vectors, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning Bruges (Belgium), 22–24 April 2015, publ., ISBN 978-287587014-8.

Michael

J.H.

, grasp-based heuristics for continuous global optimization problems, Ph.D. Thesis, University of Florida, 2006.

Abubakar

M.Y.

, Jung

L.T

, Zakaria

, Younes

and Abdel-Aty

, Reversible circuit synthesis by genetic programming using dynamic gate libraries, Quantum Information Processing 16 (2017), 160.

Abubakar

M.Y.

, Jung

L.T.

, Zakaria

M.N.

, Younes

, Abdel-Aty

, New universal gate library for synthesizing reversible logic circuit using genetic programming 2016 3rd International Conference on Computer and Information Sciences (ICCOINS), Kuala Lumpur, 2016, pp. 316–321. doi: 10.1109/ICCOINS.2016.7783234.

Haldurai

, Madhubala

and Rajalakshmi

, A study on genetic algorithm and its applications, International Journal of Computer Sciences and Engineering 4 (2016), 1–14.

Golchha

and Qureshi

S.G.

, Non-dominated sorting genetic algorithm-II – A Succinct Survey, (IJCSIT), International Journal of Computer Science and Information Technologies 6 (2015), 252–255.

Amjad

, Butt

, Kousar

, Ahmad

, Agha

, Faping

, Anjum

and Asgher

, Recent research trends in genetic algorithm based flexible job shop scheduling problems, Hindawi Mathematical Problems in Engineering 2018 (2018), 1–32.

Abdel-Khalek

, Ishak

A.B.

, Omer

O.A.

and Obada

A.-S.F.

, A two-dimensional image segmentation method based on genetic algorithm and entropy, Optik 131 (2017), 414–422.

Malhotra

, Singh

and Singh

, Genetic algorithms: Concepts, design for optimization of process controllers, Computer and Information Science 4 (2011), 39–54.

10.

Shenava

S.J.

, Noruzi

and Mousazadeh

, Solving EED problem by fuzzified multi objective simulated annealing, Applied mathematics in Engineering, Management and Technology 3 (2015), 52–66.

11.

Effati

and Nazemi

A.R.

, A new method for solving a system of the nonlinear equations, Applied Mathematics and Computation 168 (2005), 877–894.

12.

Sivaram

, Batri

, Mohammed

and Porkodi

, Exploiting the Local Optima in Genetic Algorithm using Tabu Search, Indian Journal of Science and Technology 12 (2019), 139–143.

13.

Babajee

D.K.R.

, Madhu

and Jayaraman

, On some improved harmonic mean Newton-like methods for solving systems of nonlinear equations, Algorithms 8 (2015), 895–909.

14.

Soleymani

, Salmani

and Rasouli

, Finding the Moore-Penrose inverse by a new matrix iteration, J. Appl. Math. Comput. 47 (2015), 33–48.

15.

Sharma

J.R.

, Guha

R.K.

and Sharma

, An efficient fourth order weighted-Newton method for systems of nonlinear equations, Numer. Algor. 62 (2013), 307–323.

16.

Grosan

and Abraham

, A new approach for solving nonlinear equations systems, IEEE Transactions on Systems, Manm and Cybernetics-Part A: Systems and Humans 38 (2008), 698–714.