class   GenAlgo :  """
   Class for commmon genetic algo operations
   """
   @staticmethod
 def   mutation (chromosome, mutation_rate= 50 ) :  """
       Changes one bit of chromosome with mutation_rate
       probability
       :param chromosome: chromosome to mutate
       :param mutation_rate probability of mutation from 0 to 100
       :return: mutated chromosome
"""
n = len(chromosome)
prob = rnd.randint( 0 ,  100 )  if  prob > mutation_rate:
index = rnd.randint( 0 , n -  1 ) chrom = list(chromosome)
 if  chrom[index] ==  '0' :
chrom[index] =  '1'  else :
chrom[index] =  '0'  return   '' .join(chrom)
 return  chromosome
   @staticmethod
 def   roulette_wheel_weights (weights):   """
       Calculates lst of probabilities for given cliques
       :param weights: weights of candidates
       :return: list of probabilities for candidates
       """
total =  0
 for  p =
w  in  weights:
total += w
[w / total  for  w  in  weights] i  in  range( 1 , len(p)):
p[i] += p[i -  1]
 for   return  p
 24
 @staticmethod
 def   chose_parent (weights) :  """
    Return random parent's number according to given probabilities
    :param weights: list of probabilities
    """
    n = len(weights)
r = rnd.random()  for  i  in  range(n):
 if  weights[i] > r:  return  i
@staticmethod
 def   multipoint_crossover (parent1, parent2, n) :  """
    Performs n-part crossover operation on two binary string.
    :param parent1: first binary string
    :param parent2: second binary string
    :param n: number of parts to split on
    :return: pair of crossovered string
    """
    chrom_len = len(parent1)
    points = []
 while  len(points) < n:
cur = rnd.randint( 1,  chrom_len)  if  cur  not  i  n  points:
            points.append(cur)
points = sorted(points) prev =  0
swap =  True
p1 = list(parent1) p2 = list(parent2)  for  p  in  points:
 if  swap:
 for  j  in  range(prev, p):
                swp = p1[j]
                p1[j] = p2[j]
                p2[j] = swp
swap =  not  swap prev = p
 25
  return   '' .join(p1),  '' .join(p2)
   @staticmethod
 def   replace_clique_fit (child1, child2, parent1, parent2, population) :  """
       Replace operator. Chose best child and try to replace parents of
worst
       beast in population
       :param child1: first child
       :param child2: second child
       :param parent1: first parent
       :param parent2: second parent
       :param population: whole population
       :param adj_list: adjast list of graph
       :param weights: weights of population
       :return: 1 if operation susccessfull, 0 otherwise
"""
       child_fit1 = fit_just_nodes(child1)
       child_fit2 = fit_just_nodes(child2)
 return  GenAlgo.replace_with_fit(child1, child2, parent1, parent2, population, child_fit1, child_fit2)
   @staticmethod
 def   replace_with_fit (child1, child2, parent1, parent2, population, child_fit1, child_fit2) :
 """
See replace_clique_fit
"""
n = len(population)
 if  child_fit1 > child_fit2:
           best_fit = child_fit1
best_chrom = child1  else :
           best_fit = child_fit2
           best_chrom = child2
 if  best_fit > population[parent1][ 1 ]: population[parent1] = (best_chrom, best_fit)
 elif  best_fit > population[parent2][ 1 ]: population[parent1] = (best_chrom, best_fit)
 26
  elif  best_fit > population[n -  1 ][ 1 ]: population[parent1] = (best_chrom, best_fit)
 else : return   1  return   0
   @staticmethod
 def   find_solution (adj_list, simple_generator,
fit_func, local_optimization, gen_count= 10 , stop_count= 15 , populations=None, crossover_n= 5 ) :
n = len(adj_list) population = []
 # generate start population total_fitness =  0
 for  i  in  range(gen_count):
           simple_cq = utils.list_to_chromosom(simple_generator(), n)
           population.append((simple_cq, fit_func(simple_cq)))
           total_fitness += fit_func(simple_cq)
reps = stop_count  # number of stagnant repeats reps_count =  0  #  number of operations
 while   True :
 if  populations  is   not   None :
populations.append(copy.copy(population)) reps_count +=  1
fitness = []
 for  i  in  range(gen_count):
fitness.append(population[i][ 1 ])
p = GenAlgo.roulette_wheel_weights(fitness) parent1 = GenAlgo.chose_parent(p)
parent2 = GenAlgo.chose_parent(p)
 while  parent1 == parent2:
               parent2 = GenAlgo.chose_parent(p)
children = GenAlgo.multipoint_crossover(population[parent1][ 0 ], population[parent2][ 0 ], crossover_n)
mut1 = GenAlgo.mutation(children[ 0 ])
27
mut2 = GenAlgo.mutation(children[ 1 ]) children = (mut1, mut2)
children = local_optimization(children, n)
fit1 = fit_func(children[ 0 ])
fit2 = fit_func(children[ 1 ]) GenAlgo.replace_with_fit(children[ 0 ], children[ 1 ], parent1,
parent2, population, fit1, fit2)
new_fitness =  0
 for  i  in  population:
new_fitness += i[ 1 ]
 if  new_fitness == total_fitness:
reps -=  1 total_fitness = new_fitness  if  reps ==  0 :
 break
best = (population[ 0 ][ 0]  , population[ 0 ][ 1 ])  for  beast  in  population:
 if  beast[ 1 ] > best[1   ]: best = beast
 return  best, reps_count