Solving Polynomial Equations with Complex Roots using Genetic Algorithms in VB.Net By  Mike Gold November 20, 2006 This article features a program in which the user can enter a polynomial equation and it will use GAs to determine the complex roots. Author Rank: Technologies: .NET Compact Framework, .NET 1.0/1.1,Visual Basic .NET Total downloads : 113 Total page views :  6825 Rating :  0/5 This article has been rated :  0 times   Add to Technorati    Digg This    Add to del.icio.us         Download Files GARootSolver.zip Sponsored by Looking for a book C#? Here is our book The Complete Visual C# Programmer's Guide Price: US$ 16.00 Description The Complete Visual C# Programmer's Guide, written by the authors of C# Corner, covers most of the major components that make up C# and the .NETenvironment including Windows Forms, ADO.NET, GDI+, Web Services, and Security. The book is geared toward the beginner to intermediate programmers. Browse more books here» Edited by Nina Miller Introduction It always amazes me how effective the process of trial and error is at reaching the desired solution.  Genetic Algorithms are trial and error in its purest form, each generation getting closer and closer to the solution defined by a given set of fitness parameters. This article combines the CodeDOM Calculator with the Compact Genetic Algorithm to create a root solving application. Using this application, you can type in any polynomial, and the genetic algorithm will attempt to converge on the best solution for the equation. The solution can be real or complex. Below is a sample of converging on the solution to the equation: x2 + 2x + 10 = 0 Figure 1 - Running GA Root Solver to find the complex roots of the equation x2 + 2x + 10 = 0 Essentially the solution derived by the Compact GA was (-1 ± 3i).  Let's test this solution with one of the roots (-1 +3i): = (-1 + 3i)(-1 + 3i) + 2(-1 + 3i) + 10  = (1 - 9 -6i) + (-2 + 6i) + 10 = (1 - 9 - 2) + (-6i + 6i) + 10 = -10 + 0  + 10 = 0 Let's even try  a more difficult equation: x4 - 7x2 + 14x + 25 = 0 The GA Solver converges on a solution fairly quickly:        Figure 2 - Running GA Root Solver to find the complex roots of the equation x4 - 7x2 + 14x + 25 = 0 Again testing our GA solution: = (-1.20797729492188)4 - 7(-1.20797729492188)2 + 14(-1.20797729492188) + 25 = 2.129291328988 - 10.2144640153275 + -16.91168212890632 + 25 = -24.997 + 25 = .003 This gives us a solution off by 3/1000.  Note that if we compare the fitnesses for the figure 1 solution and the figure 2 solution,  figure 1 had a fitness of 14913.  Figure 2 had a fitness of approximately 101 which is much lower than figure 1's fitness. The fitness measurement reflects how confident we are of our converged solution. The Design The design consists of two namespaces: the CompactGA and the CodeDomStuff. The CompactGA executes a compact genetic algorithm on a BinaryChromosome. Each binary chromosome contains a string of 1's and 0's representing a complex number. Because manipulating complex numbers requires complex math, we've also included a Complex class to handle multiplication, addition, and subtraction of complex numbers. Figure 3 - UML Design of GARootSolver Reverse Engineered from VB.Net using WithClass Fitness Function The fitness function in the BinaryChromosome class, CalculateFitness, calls CalculateEquationRoot to determine the fitness of the binary chromosome representing a possible complex root solution. The fitness is determined by plugging the complex chromosome value back into the equation we are trying to solve. The closer the resulting value is to 0, the higher the fitness and the closer to our desired solution.   Listing 1 - Calculating the fitness of the Complex Chromosome Public Sub CalculateFitness()     _format = "f"     CalculateEquationRoot() End Sub 'CalculateFitness   Sub CalculateEquationRoot()     'form the complex number from the 1's and 0's in the binary array     Dim root As Complex = FormComplexNumber(kChromosomeLength)     ' plug into equation     Dim result As Complex = Class1.DynamicFitnessFunction.RunCode(root)     ' compare the value of the product to the actual input number     ' and compute a fitness, result of 0 is best     _fitness = 1.0F / Math.Abs(((result.real * result.real + result.imag * result.imag) * 1000)) End Sub 'CalculateEquationRoot Forming the Complex Number The complex number is formed by taking the binary chromosome and splitting it into two equal parts: a real binary part and a complex binary part. So for example, if our binary chromosome has the value shown below and we were only dealing in integers: 11000101 Then the resulting complex number would be: 1100 + 0101i or 12 + 5i In our case, we want to support fractional values so we scale our binary values by a factor of (2)chromosome_length/4.   Our chromosomes are 60 bits long, so the number would be scaled down by 2(60/4) or 215 or 32768.  Therefore the above value of 1100 + 0101i   would really be equivalent to   12/32768 + 5/32768i   or  .00032199 + .000152587 The code for forming the complex number from the binary chromosome is shown in listing 2: Listing 2 - Forming a complex number from a string of bits Public Function FormComplexNumber(ByVal length As Integer) As Complex     Dim result1 As Double = 0     Dim result2 As Double = 0     Dim real As Long = 0     Dim imag As Long = 0     ' compute the real part of the binary chromosome     ' in the top half of the binary array     Dim i As Integer     For i = 0 To (length / 2 - 1) - 1         real = Machine.Shift.Left(real, 1)         real = real + CLng(_geneArray((length - i - 1)))     Next i     ' scale the real part by 2 ^ (genome_length/4)     result1 = CDbl(real)     Dim scale As Long = Machine.Shift.Left(1L.ToUInt32(), (length / 4))     result1 = result1 / scale     ' first bit is a sign bit     If _geneArray((length / 2 + 1)) = 1 Then         ' negative         result1 = -result1     End If     ' compute the imaginary part of the binary chromosome     ' in the bottom half of the binary array     Dim i As Integer     For i = length / 2 To (length - 1) - 1         imag = Machine.Shift.Left(imag, 1)         imag = imag + CLng(_geneArray((length - i - 1)))     Next i     ' scale the imaginary part by 2 ^ (genome_length/4)     result2 = CDbl(imag)     scale = Machine.Shift.Left(1L.ToUInt32(), (length / 4))     result2 = result2 / scale     ' first bit is a sign bit     If _geneArray(0) = 1 Then         ' negative         result2 = -result2     End If     ' return a complex number instance formed     ' from the real and imaginary binary parts     Return New Complex(result1, result2) End Function 'FormComplexNumber Equation Input Features  As in our  CodeDOM Calculator, we take the input equation string from the user and refine it so that .NET can compile it dynamically. One of the optimizations we make is to allow the user to enter x^3 as opposed to x*x*x.  Therefore, internally, we need to make the change before it reaches the compiler. The method RefineEvaluationString in the ClassExpressionCreator shows some of the substitutions we need to make before compiling the code dynamically using CodeDOM.  Listing 3 - Refining our input equation to make it compileable Function RefineEvaluationString(ByVal eval As String) As String     ' look for regular expressions with only letters     Dim regularExpression As New Regex("[a-zA-Z_]+")     ' track all functions and constants in the evaluation expression we already replaced     Dim replacelist As New ArrayList()     ' find all alpha words inside the evaluation function that are possible functions     Dim matches As MatchCollection = regularExpression.Matches(eval)     Dim m As Match     For Each m In matches         ' if the word is found in the math member map, add a Math prefix to it         Dim isContainedInMathLibrary As Boolean = Not (_mathMembersMap(m.Value.ToUpper()) Is Nothing)         If replacelist.Contains(m.Value) = False AndAlso isContainedInMathLibrary Then             eval = eval.Replace(m.Value, "Math." + _mathMembersMap(m.Value.ToUpper()))         End If         ' we matched it already, so don't allow us to replace it again         replacelist.Add(m.Value)     Next m     Dim regularExpression2 As New Regex("[0-9]x")     ' find all matches of type numx     matches = regularExpression2.Matches(eval)     Dim evalOld As String = eval     Dim count As Integer = 0     Dim m As Match     For Each m In matches         count += 1         ' if the word is found in the math member map, add a Math prefix to it         eval = eval.Substring(0, m.Index + count) + "*" + eval.Substring((m.Index + count))     Next m     Dim regularExpression3 As New Regex("x\^[0-9\.\-]+")     ' find all matches of type numx     matches = regularExpression3.Matches(eval)     Dim m As Match     For Each m In matches         count += 1         ' if the word is found in the math member map, add a Math prefix to it         ' eval = eval.Replace(m.Value, "Math.Pow(x," + m.Value.Substring(m.Value.IndexOf("^") + 1) + ")");         Dim replaceString As String = "x"         Dim i As Integer         For i = 0 To (Convert.ToInt32(m.Value.Substring((m.Value.IndexOf("^") + 1))) - 1) - 1             replaceString = replaceString + "*x"         Next i         eval = eval.Replace(m.Value, replaceString)     Next m     ' return the modified evaluation string     Return eval End Function 'RefineEvaluationString Conclusion Genetic Algorithms give us a powerful way to test possible solutions to complex equations and quickly converge onto a final solution. CodeDom allows to dynamically create compiled code containing the equation we wish to test and use this code in the method of our fitness function. Together, we used these two technologies to create a GA Root Solver that allowed us to input a polynomial equation and find the complex root. In testing this program, we found that the GA performed best with equation containing complex solutions with magnitudes between 0 and 1. Feel free to experiment with the code in this download. Perhaps you will find other ways to refine the input or improving upon the genetic algorithm.  Either way, we trust that you will get to the root of the problem you are trying to solve with VB.NET.   Other GA Algorithm Articles by the Author: Implementing a Genetic Algorithm in C# CodeDom Calculator AI: Using the Compact Genetic Algorithm to Compute Square Roots in C# NOTE: THIS ARTICLE IS CONVERTED FROM C# TO VB.NET USING A CONVERSION TOOL. ORIGINAL ARTICLE CAN BE FOUND ON C# CORNER (http://www.c-sharpcorner.com/).

评论