In [1]: from py_search.problems.graph_partition import generate_graph
...: from py_search.problems.graph_partition import random_partition
...: from py_search.problems.graph_partition import LocalGraphPartitionProblem
...: from py_search.problems.graph_partition import cutsize
...: from py_search.optimization import simulated_annealing
...: from py_search.optimization import hill_climbing
...: from py_search.utils import compare_searches
...:
...: n = 10
...: p = 5 / (n-1)
...: print(n, p)
...: V, E = generate_graph(n, p)
...: initial = random_partition(V)
...: cost = cutsize(E, initial)
...:
...: print("######################################")
...: print("Local Search / Optimization Techniques")
...: print("######################################")
...:
...: problem = LocalGraphPartitionProblem(initial, initial_cost=cost,
...: extra=(V,E))
...: print("Initial Partition Cost:")
...: print(cost)
...: print()
...:
...: def annealing(problem):
...: size = (n * (n//2)) // 2
...: return simulated_annealing(problem, initial_temp=5.5,
...: temp_length=size)
...:
...: def greedy_annealing(problem):
...: size = (n * (n//2)) // 2
...: return simulated_annealing(problem, initial_temp=0,
...: temp_length=size)
...:
...: compare_searches(problems=[problem],
...: searches=[hill_climbing, annealing,
...: greedy_annealing])
...:
(10, 0)
######################################
Local Search / Optimization Techniques
######################################
Initial Partition Cost:
0
()
Problem Search Alg Goal Tests Nodes Expanded Nodes Evaluated Solution Cost Runtime
-------------------------- ---------------- ------------ ---------------- ----------------- --------------- ---------
LocalGraphPartitionProblem hill_climbing 26 25 26 0 0.0002
LocalGraphPartitionProblem annealing 126 125 126 0 0.002
LocalGraphPartitionProblem greedy_annealing 126 125 126 0 0.0014