Advertisement
kevlinsky

Untitled

Dec 20th, 2021
809
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2. from collections import Counter
  3.  
  4. PAIRS_NUM = 5
  5. ITERATIONS_COUNT = 100
  6.  
  7.  
  8. def get_dist(params, coefs, res):
  9.     dist = {}
  10.     for idx, param in enumerate(params):
  11.         sum = 0
  12.         for x, y in zip(param, coefs):
  13.             sum += x * y
  14.         dist[idx] = abs(sum - res)
  15.  
  16.     return dist
  17.  
  18.  
  19. def get_probs(distances):
  20.     sum = 0
  21.     for dist in distances.values():
  22.         sum += 1 / dist
  23.  
  24.     probs = {}
  25.     for k, v in distances.items():
  26.         probs[k] = (1 / v) / sum
  27.  
  28.     return probs
  29.  
  30.  
  31. def get_parent_pairs(probs):
  32.     parts = {}
  33.     for k, v in probs.items():
  34.         parts[k] = int(v * 100)
  35.  
  36.     line = []
  37.     for k, v in parts.items():
  38.         for i in range(v):
  39.             line.append(k)
  40.  
  41.     random.shuffle(line)
  42.  
  43.     parent_pairs = []
  44.     for _ in range(PAIRS_NUM):
  45.         parents_pair = random.sample(line, 2)
  46.         while parents_pair[0] == parents_pair[1] or parents_pair in parent_pairs:
  47.             parents_pair = random.sample(line, 2)
  48.  
  49.         parent_pairs.append(parents_pair)
  50.  
  51.     return parent_pairs
  52.  
  53.  
  54. def cross_over(parent_pairs, params):
  55.     cos = []
  56.     for pair in parent_pairs:
  57.         delimiter = random.randint(1, len(params[0]) - 1)
  58.         co = []
  59.         x = params[pair[0]]
  60.         y = params[pair[1]]
  61.         idx = 0
  62.         while idx < delimiter:
  63.             co.append(x[idx])
  64.             idx += 1
  65.         idx = delimiter
  66.         while idx < len(params[0]):
  67.             co.append(y[idx])
  68.             idx += 1
  69.         cos.append(co)
  70.     return cos
  71.  
  72.  
  73. def duplicates_exist(params):
  74.     p = []
  75.     for param in params:
  76.         p.append(tuple(param))
  77.     cnt = Counter(p)
  78.     count = 0
  79.     for value in cnt.values():
  80.         if value > 1:
  81.             count += value
  82.  
  83.     return False if count < PAIRS_NUM // 2 else True
  84.  
  85.  
  86. def solve(coefs, res):
  87.     best_solution = None
  88.     params = None
  89.     found = False
  90.  
  91.     it = 1
  92.     while not found and it <= ITERATIONS_COUNT:
  93.         print('--------------')
  94.         print(f'Поколение {it}')
  95.         print('--------------')
  96.         if params is None:
  97.             params = []
  98.             for i in range(PAIRS_NUM):
  99.                 p = []
  100.                 for _ in range(len(coefs)):
  101.                     p.append(random.randint(1, res + 1))
  102.                 params.append(p)
  103.         print('Родители')
  104.         for param in params:
  105.             print(param)
  106.  
  107.         if duplicates_exist(params):
  108.             print(f'Более половины родителей повторяются. Поиск остановлен')
  109.             return best_solution
  110.  
  111.         # Отклонения
  112.         distances = get_dist(params, coefs, res)
  113.  
  114.         # Вероятности выживаемости
  115.         probs = get_probs(distances)
  116.  
  117.         # Родительские пары, основанные на вероятности выживаемости
  118.         parent_pairs = get_parent_pairs(probs)
  119.         print(parent_pairs)
  120.  
  121.         print('Потомки')
  122.         cos = cross_over(parent_pairs, params)
  123.         for co in cos:
  124.             print(co)
  125.  
  126.         # Коэффициенты выживаемости
  127.         live_coefs = get_dist(cos, coefs, res)
  128.  
  129.         if best_solution is None:
  130.             best_solution = (list(live_coefs.keys())[0], live_coefs[list(live_coefs.keys())[0]])
  131.         for k, v in live_coefs.items():
  132.             if v == 0:
  133.                 found = True
  134.                 best_solution = (cos[k], v)
  135.                 break
  136.  
  137.             if best_solution[1] > v:
  138.                 best_solution = (cos[k], v)
  139.  
  140.         params = cos
  141.         it += 1
  142.  
  143.     return best_solution
  144.  
  145.  
  146. if __name__ == '__main__':
  147.     coefs = [int(i) for i in input().split(' ')]
  148.     result = int(input())
  149.     solution = solve(coefs, result)
  150.     if solution[1] != 0:
  151.         print(f'Самое лучшее решение - {solution[0]} с отклонением {solution[1]}')
  152.     else:
  153.         print(f'Решение найдено - {solution[0]}')
  154.  
Advertisement
RAW Paste Data Copied
Advertisement