Flussdiagramm und python-Programm für die n-dimensionale Fibonacci Suche - Fibonacci Suche

Suchen
Direkt zum Seiteninhalt

Hauptmenü

Flussdiagramm und python-Programm für die n-dimensionale Fibonacci Suche

Flussdiagramm
Das Flussdiagramm ist Grundlage für das nachfolgend noch dargestellte Python-Programm. Um Platz zu sparen wurde anstelle dim im Diagramm nur d verwendet. x0 ist der Startvektor, alles andere ist eigentlich selbsterklärend. Außer der Dimension wurden alle Variablen als global vereinbart betrachtet. Ansonsten müssten sie in die Funktionsaufrufe mit aufgenommen werden.
(n≥1, identisch dim≥0)



Python-Programm für die n-dimensionale Suche (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)

 
Zurück zum Seiteninhalt | Zurück zum Hauptmenü