tlbo_cluster.py

import networkx as nx
import numpy as np
from operator import attrgetter



cal_times = 0
def readfile(name): #test/10a280.clt
	global v_n,c_n,vs,cs
	with open(name) as f:
		v_n = 0 # so vertex
		c_n = 0 # so cluster
		vs = [] # toa do tung vertex
		cs = [] # cac cluster
		line = f.readline()
		while "NODE_COORD_SECTION" not in line:
			line = f.readline()
			if 'DIMENSION' in line:
				v_n = int(line.split()[-1])
			if 'NUMBER_OF_CLUSTERS' in line:
				c_n = int(line.split()[-1])
		for x in range(v_n):
			a,b = f.readline().split()[-2:]
			vs.append((int(a),int(b))) #float 
		f.readline()
		f.readline()
		for x in range(c_n):
			cluster = [int(i) for i in f.readline().split()[1:-1]]
			cs.append(cluster)



def fitness(subjects,node):
	global cal_times
	cal_times = cal_times +1
	prufer,err = decode(subjects,node)
	if err:
		return 1e20,0
	tree = decode_tree(prufer) # actually not prufer tho, well whatever :)
	cost = 0
	for x1 in range(v_n):
		for x2 in range(v_n):
			route_cost = 0
			if x1 == x2: continue
			route = list(nx.all_simple_paths(tree, source=x1+1, target=x2+1))[0]
			for x in range(len(route)-1):
				n1 = route[x]-1
				n2 = route[x+1]-1
				route_cost = route_cost + ((vs[n1][0]-vs[n2][0])**2 + (vs[n1][1]-vs[n2][1])**2)**0.5
			cost = cost + route_cost
	return cost,tree
def decode(subjects,node):
	seq = []
	start = 0
	err = False
	for x in node:
		pos = np.argsort(subjects[start:start+len(x)])
		seq.append([x[i] for i in pos])
		start = start + len(x)
	for x in range(c_n):
		if seq[-1][x] >= len(cs[x]):
			err = True
	return seq,err
def decode_tree(seq):
	tree = nx.Graph()
	start = 0
	vl = []
	for x in range(len(seq)-2):
		t_t = nx.from_prufer_sequence(seq[x])
		for e in list(t_t.edges):
			tree.add_edge(cs[x][e[0]],cs[x][e[1]])
			# print(cs[x][e[0]],cs[x][e[1]])
		# vl.append(cs[x][seq[-c_n+x]])
	t_t = nx.from_prufer_sequence(seq[-2])
	for e in list(t_t.edges):
		cs[e[0]][seq[-1][e[0]]]
		tree.add_edge(cs[e[0]][seq[-1][e[0]]],cs[e[1]][seq[-1][e[1]]])
	return tree

class Learner(object):
    """docstring for Learner"""
    def __init__(self, subjects,node):
        super(Learner, self).__init__()

        self.subjects = subjects
        self.node = node
        self.fitness,self.tree = fitness(subjects,node)

    def __repr__(self):
        return f'<Learner s: {self.tree.edges} | f: {self.fitness} >'

def create_learner():
	c_l = [len(x) for x in cs] # do dai tung cluster
	node = []
	for c in cs:
		node.append(list(np.random.randint(len(c),size=len(c)-2)))
	node.append(list(np.random.randint(c_n,size=c_n-2)))
	node.append(list(np.random.randint(max(c_l),size=c_n)))
	subjects = np.random.rand(v_n-2)
	# fn = fitness(node,subjects)
	return Learner(subjects,node)

readfile("test/5i30-17.clt")
print(cs)
pop=30
gen = 10
learners = [create_learner()  for i in range(pop)]

for x in range(gen):
	teacher = min(learners, key=attrgetter('fitness'))
	print(teacher)
	diff = teacher.subjects - np.mean([x.subjects for x in learners],axis=0)
	for l in learners:
		new = Learner(l.subjects+diff*np.random.rand(),l.node)
		if new.fitness < l.fitness:
			l = new
	for l in learners:
		l2 = learners[np.random.randint(pop)]
		while l==l2:
			l2 = learners[np.random.randint(pop)]
		if l.fitness < l2.fitness:
			new = Learner(l.subjects-(l2.subjects-l.subjects)*np.random.rand(),l.node)
		else:
			new = Learner(l.subjects+(l2.subjects-l.subjects)*np.random.rand(),l.node)
		if new.fitness < l.fitness:
			l = new

best = min(learners, key=attrgetter('fitness'))
print(best)
print(cal_times)