Градиентный спуск, который мы заслужили

from queue import PriorityQueue
import numpy as np
import random
from math import sqrt

##Parameters

#learning rate
dt = 0.1

#maximum step count
maxSteps = 20000

#minimum_error
minError = 0.01

##Specifical parameters

#small number to calculate derivative of target function (for using script with large object functions, like neural nets or so)
delta = 0.1

#trace length, in points
trace_len = 10

#initilal point count
N = 10000

#size of parameters space
spaceSize=[[-100,100],[-100,100]]

#for analysis purpose
GetErrorCallCount = 0

localOptimums = []

#taked from https://github.com/behnamasadi/gradient_descent/
def objective_function(vector):
    z = -(4*np.exp(-(vector[0]-4)**2 - (vector[1]-4)**2)+2*np.exp(-(vector[0]-2)**2 - (vector[1]-2)**2))+4+0.2*np.sin(vector[0])+0.2*np.cos(vector[1])
    return z
    
#we will compute exact derivative
def get_objective_function_derivatives(vector,delta,error):
    res = []
    
    initial_error = error
    
    pos_vector = vector[0]

    for n in range(len(pos_vector)):
        vec = pos_vector
        vec[n] = vec[n]+delta
        
        derivative_n = -(GetError(vec)-initial_error)/delta
        res.append(derivative_n)

    
    #change to correct derivative calculation
    return res
    
#returns normalized derivative vector
def get_error_gradient(vector,delta, error):
    derivative = get_objective_function_derivatives(vector, delta, error)
    #recalculate derivative, if take 0 multiply delta by ten
    
    while all(d ==0 for d in derivative):
        # print("get zero derivative")
        # print(derivative)
        # print(delta)
        delta=delta*10
        
        #doesnt help, return ReInitialization flag
        if (delta>1000):
            return [True, derivative]
            
            
        derivative = get_objective_function_derivatives(vector, delta, error)
        
    return [False, derivative]
    
def initGradDesc(sampleVector, priorityQueue, N):
    res = []
    global spaceSize
    #Let's generate N random vectors with same length
    for num in range(N):

        #Initialize derivatives and vector randomly
        pos = []
        for i in range(len(sampleVector)):
            pos.append(random.uniform(spaceSize[i][0],spaceSize[i][1]))
        
        error = GetError(pos)

        res.append([error, [pos]])
    
    #Now we have N random vectors, please note that we must have normaziled data everywhere )
    #lets add all those vectors in priorityQueue with our GetError Function

    for x in res:
        priorityQueue.put(x)

#TODO: rewrite euler integration and calculation of derivatives

#use simpliest Euler method to find change of coordinates with some derivatives
def calculateNewPosition(stateVector, error_grad, errorInit):
    delta = []
    #and, some trick again, trying to normalize error
    delta = [x[0]+x[1]*dt for x in zip(stateVector[0],error_grad)]

    return delta

    
#returns error for current vector as a solution
def GetError(vector):
    #update call count
    global GetErrorCallCount
    GetErrorCallCount = GetErrorCallCount+1;
    return objective_function(vector)
    
def getLengthBetween(item, newPoint):
    l = sqrt(sum((i[0]-i[1])*(i[0]-i[1]) for i in zip(item,newPoint)))
    return l
    
def makeGradDesc(priorityQ, point, withDetection):
    global delta
    
    errorInit = point[0]
    state_vector = point[1]
 
    #Note that point structure is [vec, derivatives_1,...,derivatives_N]
    error_grads = get_error_gradient(state_vector,delta,errorInit)
   
    error_grad = error_grads[1]
    
    newPoint = calculateNewPosition(state_vector, error_grad, errorInit)
    
    error = GetError(newPoint)
    
    #merge data into one list
    res = [newPoint]

    curr_trace = 0;
    for positions in state_vector:
        res.append(positions)
        curr_trace = curr_trace+1
        if (curr_trace>=trace_len):
            break
        
    #calculate error 
    res = [error,res]
        
    #Check for local optimum (position and cost function dont change last N steps), or we get Zero derivative and still have a significant error, initialize new point
    if (withDetection and((error_grads[0] and error>minError) or (all(getLengthBetween(item, newPoint) < dt for item in state_vector)))):
        localOptimums.append(res)
        initGradDesc(newPoint, priorityQ, 1)
    else:
        if (not(withDetection) and all(getLengthBetween(item, newPoint) < dt for item in state_vector)):
            localOptimums.append(res)
            initGradDesc(newPoint, priorityQ, 1)
        else: 
            priorityQ.put(res)
    
#main gradient descent function that runs for MaxStepCount or while minimal error is not reached    
def PreformDradDesc(priorityQ, MaxStepCount,minError, withDetection):
    global GetErrorCallCount
    point = priorityQ.get()
    error = point[0]
    steps = 0
    while ((abs(error)>=abs(minError)) and (GetErrorCallCount<MaxStepCount)):
        steps = steps + 1
        makeGradDesc(priorityQ, point, withDetection)
        point = priorityQ.get()
        error =  point[0]
    return [steps, error, point]

Ne=100
res  = []
ec1 = 0
for i in range(Ne):
    GetErrorCallCount = 0

    #Where to store statistics about steps count/result error
    research_results = []

    #Queue needed for our A*
    priorityQ = PriorityQueue()

    initGradDesc(spaceSize, priorityQ, N+1)

    minimum_error = PreformDradDesc(priorityQ, maxSteps, minError, True)
    res.append([GetErrorCallCount, minimum_error[1]<minError])
    ec1 = ec1+ GetErrorCallCount
    print(i)
    

print(ec1)
print(res)
s1 = sum(item[1] for item in res)
print(ec1/s1)
print(s1/Ne)
# Mean steps: 209502.76136363635
# global optimum: 0.88

# Mean steps: 379639.8307692308
# global optimum: 0.65

# 234927.15789473685
# 0.19

# 346809.0909090909
# 0.11
res2  = []
ec2 = 0
for i in range(Ne):
    GetErrorCallCount = 0

    #Where to store statistics about steps count/result error
    research_results = []

    #Queue needed for our A*
    priorityQ = PriorityQueue()

    initGradDesc(spaceSize, priorityQ, 1)

    minimum_error = PreformDradDesc(priorityQ, maxSteps, minError, False)
    
    res2.append([GetErrorCallCount, minimum_error[1]<minError])
    ec2 = ec2+ GetErrorCallCount
    print(i)
print(ec2)
print(res2)
s2 = sum(item[1] for item in res2)
print(ec2/s2)
print(s2/Ne)

#Print results
print("Cost function calls for initialization: ")
print(GetErrorCallCount)

minimum_error = PreformDradDesc(priorityQ, maxSteps, minError)
print("Minimum error: ")
print(minimum_error[1])
print("Result point: ")
print(minimum_error[2][1][1])

print("Initial points: ")
print(N)
print("Total steps: ")
print(minimum_error[0])
print("Maximum steps: ")
print(maxSteps)

print("Cost function calls: ")
print(GetErrorCallCount)

print("Local minimums queue len: ")
print(len(localOptimums))
# for item in localOptimums:
    # print(item) 
    

##Parameters

#learning rate
dt = 0.1

#maximum step count
maxSteps = 20000

#minimum_error
minError = 0.1

##Specifical parameters

#small number to calculate derivative of target function (for using script with large object functions, like neural nets or so)
delta = 0.1

#trace length, in points
trace_len = 10

#initilal point count
N = 10000

#size of parameters space
spaceSize=[[-100,100],[-100,100]]

#for analysis purpose
GetErrorCallCount = 0