import numpy as np
def read_instance_LOP(filepath):
fp=open(filepath)
line=fp.readline()
values=line.split()
size=int(values[0])
B=np.zeros((size,size))
for i in range(size):
line=fp.readline()
values=line.split()
for j in range(size):
B[i][j]=int(values[j])
fp.close()
return (size,B)
# first time objective function is called
def objective_function_LOP(solution, instance):
size=instance[0]
B=instance[1]
value=0
# Main part
for i in range(size-1):
for j in range(i+1,size):
value += B[solution[i],solution[j]]
return value
# In order to calculate the neighbours objective function
# we can use a more efficent way to do it.
# In contrast, now we will need the previous objective function value (prev_fitness) +
# the number of the columns and rows (i and j) that will be swaped
def swap_ngb_obj_func_LOP(solution, instance, prev_fitness, i, j):
size=instance[0]
B=instance[1]
value=prev_fitness
if j<i:
i,j = j,i
# O(n)
for k in range(i+1, j): # [i+1, j) -- j is not included
# horizontal part
value -= B[solution[i],solution[k]]# Remove extracted values
value += B[solution[j],solution[k]]# Sum added values # simetric part
# vertical part
value -= B[solution[k],solution[j]]# Remove extracted values
value += B[solution[k],solution[i]]# Sum added values # simetric part
# If i and j are adjacent values, the for is skiped, and only do this last part,
# so in that case will be O(1)
# Last value, where intersects the vertical and horizontal lines
value -= B[solution[i],solution[j]]# Remove extracted values
value += B[solution[j],solution[i]]# Sum added values # simetric part
return value
# Irakurri instantzia
instance=read_instance_LOP("Instances/Cebe.lop.n10.1")
# Lehenengo ataza, erabaki LOParen soluzioak deskribatuko dituen kodeketa egokiena
solution=[i for i in range(instance[0])] # lerro == zutabe; lerroen 0 indizean dagoen valioa, hautatutako lerroaren posizioa da
# Ebaluatu goiko soluzioa
result=objective_function_LOP(solution, instance)
print("Objective value of the solution is ",result)
print(instance[1])
size = instance[0]
result2=swap_ngb_obj_func_LOP(solution, instance, result, 0, 1)
result22=swap_ngb_obj_func_LOP(solution, instance, result, size-2, size-1)
result23=swap_ngb_obj_func_LOP(solution, instance, result, 0, size-1)
print(result, result2, result22, result23)
pip install more_itertools
import random
import more_itertools as mit
import time as tm
def constructive_initial_sol(instance):
size = instance[0]
B = instance[1]
indices = []
for row in range(size):
indices.append(
np.sum(B[i, :]) / np.sum(B[:, i])
)
return solution
# Neighbourhood
# Given a solution and 2 indices i and j, it returns the neighbour of the solution with rows and cols i and j swapped.
def swap(solution, i, j):
solution[i], solution[j] = solution[j], solution[i]
return solution
def local_search(instance, max_evals):
size = instance[0]
best_solution = list(mit.random_permutation(range(size))) # random initial point
best_fitness = objective_function_LOP(best_solution, instance)
while max_evals > 0:
improvement = False
for i in range(size):
for j in range(i+1, size):
new_fitness = swap_ngb_obj_func_LOP(best_solution, instance, best_fitness, i, j)
max_evals -= 1
if new_fitness > best_fitness:
best_solution = swap(best_solution, i, j)
best_fitness = new_fitness
improvement = True
break # best first
if improvement:
break
if not improvement: # local optimum reached
break
return (best_fitness, best_solution)
for i in range(1, 10):
(fitness, sol) = local_search(instance, max_evals=100000)
print(fitness, sol)