Cada una de estas contribuciones puede centrarse en una o varias de las siguientes actividades :. Siguen algunos ejemplos. Nota 3: Contenidos apropiados. Nota 4: Voluntariado del conocimiento.
|Published (Last):||27 July 2014|
|PDF File Size:||7.28 Mb|
|ePub File Size:||6.49 Mb|
|Price:||Free* [*Free Regsitration Required]|
Discrete Particle Swarm Optimization in the numerical solution of a system of linear Diophantine equations. Received: February 25 th , Received in revised form: January 31 th , Accepted: April 3 th , Abstract This article proposes the use of a discrete version of the well known Particle Swarm Optimization, DPSO, a metaheuristic optimization algorithm for numerically solving a system of linear Diophantine equations.
Likewise, the transformation of this type of problem i. The current algorithm is able to find all the integer roots in a given search domain, at least for the examples shown. Simple problems are used to show its efficacy. Moreover, aspects related to the processing time, as well as to the effect of increasing the population and the search space, are discussed. It was found that the strategy shown herein represents a good approach when dealing with systems that have more unknowns than equations, or when it becomes of considerable size, since a big search domain is required.
Keywords : Linear Diophantine equations; objective function; optimization; particle swarm. Se utilizan algunos problemas sencillos para verificar su eficacia. With each passing day is easier to see the boom that the modeling and description of systems have generated in science and engineering, especially through Diophantine equations.
Areas such as cryptography, integer factorization, number theory, algebraic geometry, control theory, data dependence on supercomputers, communications, and so on, are some examples .
Moreover, there is a strong mathematical foundation for this type of equations and their solutions both, at a fundamental and at an applied level. These vary from the fanciest and most systematic approaches, up to the most recursive ones, but it is evident that there is no unified solution process, nor a single alternative for doing so.
Furthermore, some equations may have a single solution, while others may have an infinite number, or, possibly, may not even have a solution in the integer or rational domains. This also applies for linear systems with this kind of equations i. Diophantine ones . Matiyasevich, during the early 90s, proved that it was not possible to have an analytic algorithm that allows to foresee if a given Diophantine equation has, an integer solution , or not .
This problem may have been one of the engines that have boosted the search for numerical alternatives. In order to solve a system of linear Diophantine equations, a variable elimination method which is quite similar to Gauss's is a good approach for small systems, but it becomes demanding for bigger ones.
The specialized literature report some methods like those based on the theory of modules over main ideal domains, which are somewhat more systematic when looking for all the solutions of a given system, but, likewise, become too complex when dealing with big systems of equations , .
Some authors have previously proposed the solution of a Diophantine equation through artificial intelligence algorithms , . This article proposes to solve, in case the solution exists in the given search domain, a linear system of Diophantine equations. Initially, some basic and necessary related concepts are laid out, and then the viability of using the numeric strategy is shown through some examples. A linear Diophantine equation, with unknowns, is defined by eq.
It is said that the integers are a solution for eq. One of the basic results of number theory that can be applied to a linear Diophantine equation is the following theorem, which allows determining whether it has a solution or not even if it is not able to calculate it :. Theorem 1. Let be integers, where all not zeros, and let be the g. Therefore, if, and only if, exist integers, such that. Thus, the problem of determining whether a linear Diophantine equation has a solution or not, is reduced to showing if the greatest common divisor of the coefficients divide or not.
Consider the case of two unknowns, for example, with an equation as the one shown by eq. According to the previously mentioned theorem, this equation has integer solutions, and it can be shown that if is a particular one, then all its solutions are given by eq.
Therefore, if a linear Diophantine equation with two unknowns has a solution in the integers, then it has infinite solutions of this kind. Even so, the problem now transforms in finding a particular solution, which can be done using the following method. Let be a non-empty subset of and consider eq. The problem of finding all the possible solutions for eq.
Let be defined by:. Then, for every it holds that. Theorem 2. Suppose that eq. Therefore, is a solution for eq. An immediate consequence of the previous theorem is that if eq.
Theorem 3. If the function defined in 5 has a global minimum in and this value is zero, then eq. Moreover, all global minimizers of are solutions of eq. Then, if for a region of the plane can be determined, where a global minimum of function , defined by 5 , and its value is zero, then any global minimizer with integer coordinates, should it exist, serves as a particular solution of eq. Thus, the choice of the region is quite important to enclose, at least, a solution with integer coordinates.
System of linear equations Consider the following system of linear Diophantine equations, with unknowns.
According to theorem 1, in order for the system 6 to have a solution, it is necessary, but not sufficient, that each of the equations have a solution; this is equivalent to establishing if for each it holds that divides. To see why this condition is not sufficient, consider the system of Diophantine equations defined by. Each equation from this system has a solution in the integer domain, but the system does not have a solution as a whole.
Then, and in the same way that with systems of equations in real variables, the fact that one of the equations of a system has a solution, does not imply that the whole system also has. Even so, a method that generalizes finding all the roots in case they exist of a system of equations over a given set, is shown below.
Let be a non-empty subset of and consider the system of equations 8 , where for each , is a function. Then for all it holds that. The following result is achieved:. Theorem 4. Suppose that the system of equations 8 has a solution in , and let. Then, is a solution of the system 8 if, and only if, minimizes the function defined in 9. The general condition of the theorem 4 about the feasibility of solving the system 8 is important, since it is possible that the function defined in 9 can be globally minimized but that the system 8 does not have a solution.
An immediate consequence of theorem 4 is that if the system 8 has a solution in , then the global minimum of defined in 9 exists and it is zero; moreover, the following result exists:. Theorem 5. If the function defined in 9 has a global minimum in and this value is zero, then the system 8 has a solution in. Moreover, all global minimizers of are solutions of the system 8. Therefore, for the function defined in 9 , if there does not exist a global minimum in or if it exists but is different from zero, then the system of equations 8 does not have a solution in.
A basic result of the mathematical analysis of the algorithm establishes that if is a compact set i. Now, for to be continuous in it is enough that each is continuous in. For the case of systems of Diophantine equations, unlike the particular case of an equation with two unknowns, the fact that a solution exists does not imply that others do, and even less that an infinite number exists.
For the search of possible solutions of a system of Diophantine equations, it must hold that the set have points with integer coordinates, i.
The algorithm The implemented algorithm is built up from various interconnected blocks and is similar to the structure of traditional PSO for real numbers , , . A first stage is given by the random assignation of a swarm of user defined integers. Any size can be used here. Likewise, the definition of these values is subject to previous knowledge of the objective function fitness , as well as to the presence of restrictions.
Moreover, an initial speed of zero can be defined for the particles. After that, the algorithm evaluates, in the given search space, the objective function. With it, local and global best values are established, and both, speed and position, of each particle, are reevaluated as shown below.
This procedure is iterative and is repeated until the convergence criteria are met, or until all solutions in the search domain are found.
An algorithm, considered as a variant of the traditional PSO, was used, . In the same fashion as said PSO, its version for discrete solutions includes two vectors and , related to the position and speed of each particle, for every iteration.
The first one is a vector of random numbers, initially, in a valid solution interval. The second one can also be a random vector, but it can be assumed as zero for the first iteration, in order to keep it simple.
When the problems become multidimensional, the vectors transform into a position and a speed matrices, since there is a value for each unknown, , .
Discrete PSO differs from its traditional version in which the new speed and position depend on both, an equation and a decision rule, which chooses among the local and global best values for the next iteration. Assuming there is a vector that allows the transition between continuous and discrete PSO, and which takes the value of -1, 1, or, 0 according to eq. Afterwards, speed is updated according to eq. Then, the decision parameter, vector , is calculated according to eq.
This parameter decides if the next position of the particle is chosen as the local or global best, or if it is chosen as a random number in the search domain. Thus, position update is done according to eq. This section shows the results achieved after solving some systems of linear Diophantine equations, as an example of the method.
These values were chosen based on some preliminary tests and on the information available in the literature , . System of equations A It is required to solve the system given by eq.
The full statement of the problem is as follows: "A farmer spent In order to solve this problem with the discrete PSO algorithm, the following objective function is created:. After 20 runs of the algorithm, with a swarm of particles, the same answer was always achieved. Their duration, however, varied from 1. It can then be concluded that, for this system, the algorithm delivers an answer with excellent precision and accuracy, even though the number of iterations and the duration were variable.
Wikipedia:Proyecto educativo/Matemática discreta y numérica