Implement Simple Hill Climbing Algorithm and Generate a String by Mutating a Single Character at each iteration
Hill climbing is a variant of Generate and test in which feedback from test procedure is used to help the generator decide which direction to move in search space. Feedback is provided in terms of heuristic function
STEP 1 :Evaluate the initial state.If it is a goal state then return it and quit. Otherwise, continue with initial state as current state. STEP 2:Loop until a solution is found or there are no new operators left to be applied in current state: STEP 3Select an operator that has not yet been applied to the current state and apply it to produce a new state STEP 4Evaluate the new state: STEP 5if it is a goal state, then return it and quit STEP 6if it is not a goal state but better than current state then make new state as current state STEP 7if it is not better than current state then continue in the loop
STEP 1 Generate Random String of the length equal to the given String STEP 2Mutate the randomized string each character at a time STEP 3Evaluate the fitness function or Heuristic Function
STEP 4Lopp Step -2 and Step-3 until we achieve the score to be Zero to achieve Global Minima.import random
import string
def generate_random_solution(answer):
l=len(answer)
return [random.choice(string.printable) for _ in range(l)]
def evaluate(solution,answer):
print(solution)
target=list(answer)
diff=0
for i in range(len(target)):
s=solution[i]
t=target[i]
diff +=abs(ord(s)-ord(t))
return diff
def mutate_solution(solution):
ind=random.randint(0,len(solution)-1)
solution[ind]=random.choice(string.printable)
return solution
def SimpleHillClimbing():
answer="Artificial Intelligence"
best=generate_random_solution(answer)
best_score=evaluate(best,answer)
while True:
print("Score:",best_score," Solution : ","".join(best))
if best_score==0:
break
new_solution=mutate_solution(list(best))
score=evaluate(new_solution,answer)
if score<best_score:
best=new_solution
best_score=score
#answer="Artificial Intelligence"
#print(generate_random_solution(answer))
#solution=generate_random_solution(answer)
#print(evaluate(solution,answer))
SimpleHillClimbing()
Score: 609 Solution : 8RzF:oG ]%;CPqRRMe!zGvk
Score: 604 Solution : 8RzF:oG ]%;CPqRRMe!zGqk
Score: 594 Solution : 8RzF:oG ]%;CPqRRWe!zGqk
Score: 551 Solution : 8RzF:oGK]%;CPqRRWe!zGqk
Score: 551 Solution : 8RzF:oGK]%;CPqRRWe!zGqk
Score: 551 Solution : 8RzF:oGK]%;CPqRRWe!zGqk
Score: 551 Solution : 8RzF:oGK]%;CPqRRWe!zGqk
Score: 551 Solution : 8RzF:oGK]%;CPqRRWe!zGqk
....................................................
..................................................
................................................
Score: 1 Solution : Artificial Intelligencf
Score: 1 Solution : Artificial Intelligencf
Score: 1 Solution : Artificial Intelligencf
Score: 1 Solution : Artificial Intelligencf
Score: 0 Solution : Artificial Intelligence
Thus ,Simple Hill Climbing Algorithm and to Generate a String by Mutating a Single Character at each iteration was implemented successfully.