Hill-climbing 其實也不是很復雜，在這個博文里面，我假定一個512維度的空間中存在一個點point1 ，我的目標是隨機初始化一個點，通過Hill-climbing找到這個目標點point1。

站在當前點，通過探索所有可能的走法去判斷下一步哪一個走法是能夠朝著目標靠近的。過程其實也不復雜，在512里面的某一個維度，走起來只有兩種選擇，加一個步長或者減去一個步長。如果下一步找不到比較好的選擇，都不能靠近目標點，那么算法結束。

具體代碼可以看下面：

__author__ = 'xingbo, it is based on inital version of sidharthgoyal' import math from random import * import random import numpy import copyincrement = 0.05 startingPoint = numpy.random.random(512) point1 = numpy.random.random(512) print('target:',point1) # point2 = [6,4] # point3 = [5,2] # point4 = [2,1]def distance(coords1, coords2):""" Calculates the euclidean distance between 2 lists of coordinates. """# print('coords1',coords1)# print('coords2',coords2)return numpy.sqrt(numpy.sum((coords1 - coords2)**2))def sumOfDistances(x, px):d1 = distance(x, px)return d1def newDistance(d1, point1):d1temp = sumOfDistances(d1, point1 )d1 = numpy.append(d1,d1temp) return d1minDistance = sumOfDistances(startingPoint, point1 ) flag = Truethreshold = 0.4 i = 1 lastFitness = 99 while lastFitness > threshold:d = []old_point = startingPointfor index in range(512):increment_arr = numpy.zeros(512)increment_arr[index] = incrementnewpoint = startingPoint + increment_arrd1 = newDistance(newpoint, point1)newpoint = startingPoint - increment_arrd2 = newDistance(newpoint, point1)d.append(d1)d.append(d2)# print(i,' ', startingPoint[:4])d = numpy.array(d)minimum = min(d[:,512])if minimum < minDistance:minindex = numpy.argmin(d[:,512])startingPoint = d[minindex,:512]minDistance = minimumprint('found ',i,' ', startingPoint[:4],'score',d[minindex,512])lastFitness = d[minindex,512]else:flag = False# print('new start poiny ',i)startingPoint = startingPoint + numpy.random.random(512) * 0.1i+=1print('target:',point1[:10]) print('result:',startingPoint[:10])

運行結果：

found 3319 [0.54880071 0.14943408 0.16443942 0.67552999] score 0.40665809714898343 found 3320 [0.54880071 0.14943408 0.16443942 0.67552999] score 0.4050587747707967 found 3321 [0.54880071 0.14943408 0.16443942 0.67552999] score 0.4034618667141106 found 3322 [0.54880071 0.14943408 0.16443942 0.67552999] score 0.4018617552269553 found 3323 [0.54880071 0.14943408 0.16443942 0.67552999] score 0.4002772234555598 found 3324 [0.54880071 0.14943408 0.16443942 0.67552999] score 0.3986881730615146 target: [0.54391242 0.16028716 0.15798658 0.6986903 0.74380195 0.258413040.40675962 0.2248158 0.76813796 0.7937874 ] result: [0.54880071 0.14943408 0.16443942 0.67552999 0.73628524 0.25467860.37020921 0.2397613 0.75941863 0.75618421] import numpy as np from scipy.optimize import minimizext = np.random.rand(512) * 2 print('x terget:',xt[:10])def rosen(x):"""The Rosenbrock function"""return np.sqrt(np.sum((x - xt)**2))# 初始迭代點 x0 = np.random.rand(512) * 2res = minimize(rosen, x0, method='BFGS', jac=[],options={'disp': True})print('res',res.x[:10])

總結

以上是生活随笔為你收集整理的Hill-climbing 算法python 实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。