The following program calculates the minimum point of a multi-variable function using random search method.
Click here to download a ZIP file containing the project files for this program.
The pseudo-code for this algorithm is:
The program prompts you to either use the predefined default input values or to enter the following:
1. Minimum value for each variable:.
2. Maximum value for each variable:.
3. The maximum number of iterations per cycle.
4. The function tolerance.
In case you choose the default input values, the program displays these values and proceeds to find the optimum point. In the case you select being prompted, the program displays the name of each input variable along with its default value. You can then either enter a new value or simply press Enter to use the default value. This approach allows you to quickly and efficiently change only a few input values if you so desire.
The program displays the following results:
1. The coordinates of the minimum value.
2. The minimum function value.
3. The number of iterations
Here is a sample session to find the minimum of function:
f(x) = x1 - x2 + 2 * x1 ^ 2 + 2 * x1 * x2 + x2 ^ 2
Using the initial value of 0, range of (-5, 5) for each variable, and using a maximum number of 1000000 iterations and a function tolerance of 1e-7. Here is the sample console screen:
Here is the BASIC listing for the main module. The module contains several test functions:
Module Module1
Sub Main()
Dim nNumVars As Integer = 2
Dim fX() As Double = {0, 0}
Dim fParam() As Double = {0, 0}
Dim fXlo() As Double = {-5, -5}
Dim fXHi() As Double = {5, 5}
Dim fEpsFx As Double = 0.0000001
Dim nIter As Integer = 0, nMaxIter As Integer = 1000000
Dim I As Integer
Dim fBestF As Double
Dim sAnswer As String
Dim oOpt As CRandomSearch1
Dim MyFx As MyFxDelegate = AddressOf Fx3
Dim SayFx As SayFxDelegate = AddressOf SayFx3
oOpt = New CRandomSearch1
Console.WriteLine("Random Search (pure random) Optimization")
Console.WriteLine("Finding the minimum of function:")
Console.WriteLine(SayFx())
Console.Write("Use default input values? (Y/N) ")
sAnswer = Console.ReadLine()
If sAnswer.ToUpper() = "Y" Then
For I = 0 To nNumVars - 1
Console.WriteLine("X({0}) = {1}", I + 1, fX(I))
Console.WriteLine("X Low({0}) = {1}", I + 1, fXlo(I))
Console.WriteLine("X High({0}) = {1}", I + 1, fXHi(I))
Next
Console.WriteLine("Maximum iterations = {0}", nMaxIter)
Console.WriteLine("Function tolerance = {0}", fEpsFx)
Else
For I = 0 To nNumVars - 1
fX(I) = GetIndexedDblInput("X", I + 1, fX(I))
fXlo(I) = GetIndexedDblInput("X low", I + 1, fXlo(I))
fXHi(I) = GetIndexedDblInput("X high", I + 1, fXHi(I))
Next
nMaxIter = GetIntInput("Maximum iterations", nMaxIter)
fEpsFx = GetDblInput("Function tolerance", fEpsFx)
End If
Console.WriteLine("******** FINAL RESULTS *************")
fBestF = oOpt.CalcOptim(nNumVars, fX, fParam, fXlo, fXHi, nMaxIter, fEpsFx, nIter, MyFx)
Console.WriteLine("Optimum at")
For I = 0 To nNumVars - 1
Console.WriteLine("X({0}) = {1}", I + 1, fX(I))
Next
Console.WriteLine("Function value = {0}", fBestF)
Console.WriteLine("Number of iterations = {0}", nIter)
Console.WriteLine()
Console.Write("Press Enter to end the program")
Console.ReadLine()
End Sub
Function GetDblInput(ByVal sPrompt As String, ByVal fDefInput As Double) As Double
Dim sInput As String
Console.Write("{0}? ({1}): ", sPrompt, fDefInput)
sInput = Console.ReadLine()
If sInput.Trim().Length > 0 Then
Return Double.Parse(sInput)
Else
Return fDefInput
End If
End Function
Function GetIntInput(ByVal sPrompt As String, ByVal nDefInput As Integer) As Integer
Dim sInput As String
Console.Write("{0}? ({1}): ", sPrompt, nDefInput)
sInput = Console.ReadLine()
If sInput.Trim().Length > 0 Then
Return Double.Parse(sInput)
Else
Return nDefInput
End If
End Function
Function GetIndexedDblInput(ByVal sPrompt As String, ByVal nIndex As Integer, ByVal fDefInput As Double) As Double
Dim sInput As String
Console.Write("{0}({1})? ({2}): ", sPrompt, nIndex, fDefInput)
sInput = Console.ReadLine()
If sInput.Trim().Length > 0 Then
Return Double.Parse(sInput)
Else
Return fDefInput
End If
End Function
Function SayFx1() As String
Return "F(X) = 10 + (X(1) - 2) ^ 2 + (X(2) + 5) ^ 2"
End Function
Function Fx1(ByVal N As Integer, ByRef X() As Double, ByRef fParam() As Double) As Double
Return 10 + (X(0) - 2) ^ 2 + (X(1) + 5) ^ 2
End Function
Function SayFx2() As String
Return "F(X) = 100 * (X(1) - X(2) ^ 2) ^ 2 + (X(2) - 1) ^ 2"
End Function
Function Fx2(ByVal N As Integer, ByRef X() As Double, ByRef fParam() As Double) As Double
Return 100 * (X(0) - X(1) ^ 2) ^ 2 + (X(1) - 1) ^ 2
End Function
Function SayFx3() As String
Return "F(X) = X(1) - X(2) + 2 * X(1) ^ 2 + 2 * X(1) * X(2) + X(2) ^ 2"
End Function
Function Fx3(ByVal N As Integer, ByRef X() As Double, ByRef fParam() As Double) As Double
Return X(0) - X(1) + 2 * X(0) ^ 2 + 2 * X(0) * X(1) + X(1) ^ 2
End Function
End Module
Notice that the user-defined functions have accompanying helper functions to display the mathematical expression of the function being optimized. For example, function Fx1 has the helper function SayFx1 to list the function optimized in Fx1. Please observe the following rules::
The program uses the following class to optimize the objective function:
Public Delegate Function MyFxDelegate(ByVal nNumVars As Integer, ByRef fX() As Double, ByRef fParam() As Double) As Double
Public Delegate Function SayFxDelegate() As String
Public Class CRandomSearch1
Public Function CalcOptim(ByVal nNumVars As Integer, ByRef fX() As Double, ByRef fParam() As Double, _
ByRef fXLo() As Double, ByRef fXHi() As Double, _
ByVal nMaxIter As Integer, ByVal EpsFx As Double, _
ByRef nIter As Integer, ByVal MyFx As MyFxDelegate) As Double
Dim F, fBestF, fBestX(), fLastBestF As Double
Dim I As Integer
ReDim fBestX(nNumVars)
For I = 0 To nNumVars - 1
fBestX(I) = fX(I)
Next
' calculate and display function value at initial point
fBestF = MyFx(nNumVars, fBestX, fParam)
If fBestF > 0 Then
fLastBestF = fBestF + 100
Else
fLastBestF = 100 - fBestF
End If
nIter = 0
Do
nIter += 1
If nIter > nMaxIter Then Exit Do
Randomize(Timer)
For I = 0 To nNumVars - 1
fX(I) = fXLo(I) + Rnd(1) * (fXHi(I) - fXLo(I))
Next
F = MyFx(nNumVars, fX, fParam)
If F < fBestF Then
For I = 0 To nNumVars - 1
fBestX(I) = fX(I)
Next
fBestF = F
' test function value convergence
If Math.Abs(fBestF - fLastBestF) < EpsFx Then Exit Do
fLastBestF = fBestF
End If
Loop
Return fBestF
End Function
End Class
Copyright (c) Namir Shammas. All rights reserved.