# 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
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.