Skip to content

Instantly share code, notes, and snippets.

Created March 28, 2014 12:19
Show Gist options
  • Save wkta/9831438 to your computer and use it in GitHub Desktop.
Save wkta/9831438 to your computer and use it in GitHub Desktop.
#MonthOfCode day 18 - search
import random
# This code implements the so-called "descent method" which is a kind of NEIGHBOR SEARCH METHOD
# often used in optimization.
# I apply it to the simple problem of finding the minimum value in a huge random matrix
# I count the nb of values tested to show how this kind of search is efficient in practice
# I initiale a random matrix and compute the global min. value on-the-fly to know
# if the descent method eventually succeeds in finding it.
N = 128 ; M = 128
MAX_VAL = 255
global_min = MAX_VAL
matr = list()
for i in xrange(N):
tmp_row = list()
for j in xrange(M):
rand_number = random.randint(1, MAX_VAL)
tmp_row.append(rand_number )
global_min = rand_number
matr.append( tuple(tmp_row))
del tmp_row
# defining concepts of "solution" and "neighborhoord" for our context
class OptPbSolution:
def __init__(self, coord_i, coord_j):
self.i = coord_i
self.j = coord_j
self.val = matr[self.i][self.j]
def __str__(self):
return str(self.val)
def dumpCoords(self):
return '('+str(self.i)+', '+str(self.j)+')'
def getNeighbors(self):
l_coord = list()
if self.i >0:
l_coord.append( (self.i-1, self.j) )
if self.i+1 < N:
l_coord.append( (self.i+1, self.j) )
if self.j >0:
l_coord.append( (self.i, self.j-1) )
if self.j+1 < M:
l_coord.append( (self.i, self.j+1) )
tmp_l = [ OptPbSolution( *coord) for coord in l_coord ]
return tmp_l
def detBetterSol( neighbors, s):
'''returns the solution in neighbors that has the lowest value'''
min_value = neighbors[0].val
print neighbors[0].val
candidate = neighbors[0]
for i in xrange(1, len(neighbors)):
print neighbors[i].val
if (neighbors[i].val < min_value):
min_value = neighbors[i].val
candidate = neighbors[i]
return candidate
def runDescentMethod():
'''returns the minimum found along with the nb of tested solutions'''
nb_tested = 1
# step1: choosing an initial solution we call s, I proceed randomly
init_sol = OptPbSolution(
random.randint(0,N-1), random.randint(0,M-1) )
print " init. solution:",str(init_sol)," coords:",init_sol.dumpCoords()
s = init_sol
while ( True ):
# step2: find the best solution s' in N(s) the neighborhood of s
neighbors = s.getNeighbors()
s_quote = detBetterSol( neighbors, s )
# step3: stop if there is no s' in N(s) better than s, repeat step2 otherwise
if s_quote.val>=s.val:
s = s_quote
print " best solution found in the neighborhood",str(s)," coords:",s.dumpCoords()
print "Descent Search terminated."
return (s.val, nb_tested)
# MAIN ALGORITHM , we perform 6 successive Descent method searching
meta_min, total_tested = runDescentMethod()
for i in xrange(5 ):
tmp_m, tmp_tested = runDescentMethod()
if(meta_min > tmp_m):
meta_min = tmp_m
total_tested += tmp_tested
print "FINAL STATS-- best value found:",meta_min
print "nb of values tested:",total_tested
print "total nb of values:",N*M
if( meta_min==global_min):
print "the global minimum has been found!"
print "the global minimum was:",global_min
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment