Flowchart and python-program for the n-dimensional Fibonacci search - Fibonacci Search

Search
Go to content

Main menu

Flowchart and python-program for the n-dimensional Fibonacci search

Flowchart
The flow chart is base of the Python program, shown below. To save space was only used in the diagram d instead dim. x0 is the initial vector, everything else is self-explanatory. Besides the dimension, all variables were considered as agreed globally. Otherwise they had to be added as parameters in the function calls.
(n ≥ 1, which are identical dim ≥ 0)




Python-Program for the n-dimensional Fibonacci search (n ≥ 1)

'''
Created on 23.11.2012

'''
#!/usr/bin/env python

# Program for an n-dimensional search of the minimum of a function
# by means of the Fibonacci numbers.

# The program is written as an python file(Version 2.5.4).
# It can be easily ported to any other programming language.

#******************************************************************************************
# Version 2.1  / revised version
# Date: 06.12.2012
# Author: Klaus-Eckart Schulz / Berlin
# The program can be used as required, modified and passed on,
# however, the reference to the author maintained.
# For any application the author assumes no liability.
#******************************************************************************************

# Very simple example for n=5-dimensional

#------------------ Data entry -------------------------------------------------------
m=[4,6,8,10,12]         # Number of search steps for each of the n=5 intervals.
intervall=[[0,8],       # n=5 search intervals
          [-8,0],
          [0,8],
          [0,8],
          [0,8]
          ]

# Definition of the function y=f(x1,...,xn) =f(x)
def  FUNKTION(x):
       return  (x[0]-4)**2+(x[1]+4)**2+(x[2]-4)**2+(x[3]-4)**2+(x[4]-4)**2
#---------------------------------------------------------------------------------------

#===== Recursive procedure for the n-dimensional Fibonacci search =====#
def  fibo_search(dim):
   global k,x0,x1,y1,x2,y2,s,m,eps,F
   k[dim]=0
   while k[dim] < m[dim]:
       if dim==len(m)-1:
           if k[dim]==0:
               x1[dim]=x0[dim]+F[m[dim]-k[dim]]*eps[dim]
               x2[dim]=x1[dim]
               y1[dim]=FUNKTION(x2)
               s[dim]=1
           else:
               x2[dim]=x1[dim]+F[m[dim]-k[dim]]*eps[dim]*s[dim]
               y2[dim]=FUNKTION(x2)
               if y2[dim]<y1[dim]:
                   x1[dim]=x2[dim]
                   y1[dim]=y2[dim]
               else:
                   s[dim]=s[dim]*(-1)
       else:
           if k[dim]==0:
               x1[dim]=x0[dim]+F[m[dim]-k[dim]]*eps[dim]
               x2[dim]=x1[dim]
               s[dim]=1                
               fibo_search(dim+1)
               y1[dim]=y1[dim+1]
           else:
               x2[dim]=x1[dim]+F[m[dim]-k[dim]]*eps[dim]*s[dim]
               fibo_search(dim+1)
               y2[dim]=y1[dim+1]
               if y2[dim]<y1[dim]:
                   x1[dim]=x2[dim]
                   y1[dim]=y2[dim]
               else:
                   s[dim]=s[dim]*(-1)
       k[dim]=k[dim]+1
#===========================================================================      
   
#+++++ Initialization of the variables +++++++++++++++++++++++++++++++++++++

# Determination of the array for the Fibonacci numbers  'F'
m_max=max(m)
F=[0]*(m_max+3)
F[0]=0.0
F[1]=1.0
for i in range(2,m_max+3):
   F[i]=F[i-1]+F[i-2]

# Determination of 'eps[]=interval_length/Fib[m+2]' for all dimensions
# eps[] is the max. possible absolute error for each dimension
eps=([0]*len(m))
for i in range(0,len(m)):
   eps[i]=(intervall[i][1]-intervall[i][0])/F[m[i]+2]

# Arrays 's' for the search direction, and 'k' for the control variables
s=[1]*len(m)
k=[0]*len(m)

x0=[0.0]*len(m)
x1=[0.0]*len(m)
x2=[0.0]*len(m)
y1=[0.0]*len(m)
y2=[0.0]*len(m)

for i in range(0,len(m)):
   x0[i]=intervall[i][0]
#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

#   Start of the Program
fibo_search(0)

#  Result Output
print x1               # n-dimensional array with the n solutions
print y1[0]            # Result y1=f(x1)

 
Back to content | Back to main menu