#MonthOfCode day 18 - search

day_18.py

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 )
        if(rand_number<global_min):
            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 )
        nb_tested+=len(neighbors)
        # step3: stop if there is no s' in N(s) better than s, repeat step2 otherwise
        if s_quote.val>=s.val:
            break
        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!"
else:
    print "the global minimum was:",global_min