jeudi 21 décembre 2017

How to create a hill climbing algorithm

I have been following a book for learning python, and the book has one of the following challenge:

Self Check

Here’s a self check that really covers everything so far. You may have heard of the infinite monkey theorem? The theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare. Well, suppose we replace a monkey with a Python function. How long do you think it would take for a Python function to generate just one sentence of Shakespeare? The sentence we’ll shoot for is: “methinks it is like a weasel”

You’re not going to want to run this one in the browser, so fire up your favorite Python IDE. The way we’ll simulate this is to write a function that generates a string that is 28 characters long by choosing random letters from the 26 letters in the alphabet plus the space. We’ll write another function that will score each generated string by comparing the randomly generated string to the goal.

A third function will repeatedly call generate and score, then if 100% of the letters are correct we are done. If the letters are not correct then we will generate a whole new string.To make it easier to follow your program’s progress this third function should print out the best string generated so far and its score every 1000 tries.

I was able to implement this part of the challenge, with the following code: (I am new to python)

import random
target = 'methinks it is like a weasel'
target_len = 28

def string_generate(strlen):
 alphabet = 'abcdefghijklmnopqrstuvwxyz ' #26 letters of the alphabet + space
 res = ''
 for i in range(strlen):
  res += alphabet[random.randrange(27)]

 return res

def score_check(target,strlen):
 score = 0
 res = string_generate(strlen)
 for i in range(strlen):
  if res[i] == target[i]:
   score += 1
 return score, res

def progress_check():
 counter = 0
 score = 0
 res = ''
 while score != 28:
  score_temp, res_temp = score_check(target, target_len)
  counter += 1
  if score_temp > score:
   score, res = score_temp, res_temp
   print(res, score)
  else:
   score, res = score, res

 return res, score

progress_check()

It then have the following extra challenge:

Self Check Challenge

See if you can improve upon the program in the self check by keeping letters that are correct and only modifying one character in the best string so far. This is a type of algorithm in the class of ‘hill climbing’ algorithms, that is we only keep the result if it is better than the previous one.

However, I am not able to figure out what this hill climbing algorithim is, and how I would implement it into my existing piece of code.

Please point out any potential improvements to my code, and explain how to implement this hill climbing algorithm, thank you all so much!




Aucun commentaire:

Enregistrer un commentaire