# Evolutionary Algorithms

May 27th, 2023
1,035
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. FIRST_POPULATION_SIZE = 93123;
2. N = 10
3.
4. def generate_random_population():
5.    population = []
6.    for i in range(FIRST_POPULATION_SIZE):
7.        X = []
8.
9.        # --- YOUR CODE HERE
10.        X = [randint(0, 1) for i in range(N)]
11.
12.        X = [i for i in range(N)]
13.        random_shuffle(X)
14.        # --- YOUR CODE ENDS HERE
15.
16.        population.append(X)
17.
18.    return population
19.
20.
21. # This doesn't account for permutations
22. def order_crossover(X, Y):
23.     N = len(X)
24.     a = randint(0, N - 2)
25.     b = randint(0, N - 2)
26.     if a > b:
27.         swap(a, b)
28.
29.     C1 = X, C2 = Y
30.     for i in range(a, b+1):
31.          swap(C1[i], C2[i])
32.
33.         return C1, C2
34.
35.
36. # Crossover over permutations
37. def order_crossover(X, Y):
38.     N = len(X)
39.     a = randint(0, N - 2)
40.     b = randint(0, N - 2)
41.     if a > b:
42.         swap(a, b)
43.
44.     C1 = [], C2 = []
45.     for i in range(a, b + 1):
46.          C1.append(X[i])
47.          C2.append(Y[i])
48.
49.     U = [], V = []
50.     for i in range(b, N + a):
51.          if Y[i%N] not in C1:
52.              U.append(Y[i%N])
53.
54.     for i in range(b, N + a):
55.          if X[i%N] not in C2:
56.              V.append(X[i%N])
57.
58.     C1 = (C1 + U)[a:] + (C1 + U)[:a]
59.     C2 = (C2 + V)[a:] + (C2 + V)[:a]
60.     return C1, C2
61.
62.
63.
64. def algo():
65.     population = generate_random_population()
66.     for epoch in range(E):
67.         # SELECTION
68.
69.         # KRIZENJE
70.
71.         # MUTACIJA
72.
73.         # ZAMENA NA CHILDS AND PARENTS
74.
75.         # GOAL?
76.
77.
78.
79. def h(X):
80.     # calculate the strength of X
81.
82.
83. def goal(X):
84.    for gene in X:
85.       if gene == 0:
86.          return false
87.    return true
88.
89.
90. LIMIT_SIZE = 312875
91.
92. def algo():
93.     population = generate_random_population()
94.     for epoch in range(E):
95.         selected_parents = selection(population)
96.         children = merge(selected_parents)
97.         children = map(mutate, children)
98.         population = children + population[:0.03 * len(population)]
99.         population = population[:LIMIT_SIZE]
100.         for child in children:
101.             if goal(child):
102.                 return child
103.
104.
105.
106.
107.
108. ## KRIZENJE
109.
110. def kpoint_crossover(X, Y, K):
111.    N = len(X)
112.    points = [randint(0, N - 1) for i in range(K)]
113.    points = sorted(points)
114.    if K % 2 == 1:
115.       points.append(N)
116.
117.    for i in range(0, K, 2):
118.        for j in range(points[i], points[i+1]):
119.            swap(X[j], Y[j])
120.
121.    return X, Y
122.
123.
124. def uniform_crossover(X, Y, P):
125.     for i in range(0, N - 1):
126.         if randfloat(0, 1) < P:
127.             swap(X[i], Y[i])
128.
129.      return X, Y
130.
131.
132.
133. ## MUTACIJA
134.
135. # probability for mutation to happen
136. Pm = 0.03
137.
138. def mutate(child):
139.     if randfloat(0, 1) <= Pm:
140.         u = randint(0, N - 1)
141.         child[u] = 1 - child[u]
142.     return child
143.
144. ## MUTACII ZA PERMUTACII
145.
146. def mutate_swap(child):
147.     if randfloat(0, 1) <= Pm:
148.        u = randint(0, N - 1)
149.        v = randint(0, N - 1)
150.        swap(child[u], child[v])
151.     return child
152.
153. def mutate_insertion(child):
154.     if randfloat(0, 1) <= Pm:
155.        u = randint(0, N - 1)
156.        v = randint(0, N - 2)
157.        t = child[u]
158.        child.pop(u)
159.        return child[:(v-1)] + [t] + child[v:]
160.     return child
161.
162. def mutate_reverse(child):
163.     if randfloat(0, 1) <= Pm:
164.         u = randint(0, N - 1)
165.         v = randint(0, N - 1)
166.         if u > v:
167.            swap(u, v)
168.
169.         return child[:u] + list(reverse(child[u:v])) + child[v:]
170.     return child
171.
172.
173.
174.
175.
176. ## MERGE
177.
178. def merge(population):
179.     children = []
180.     for i in range(0, len(population), 2):
181.         C1, C2 = crossover(population[i], population[i+1])
182.         children.append(C1, C2)
183.
184.     return children
185.
186.
187. ## SELEKCII
188.
189. def proportional_selection(population):
190.     sumG = sum([h(X) for X in population])
191.
192.     result = []
193.     for X in population:
194.         if randfloat(0, 1) <= h(X) / sumG
195.             result.append(X)
196.
197.     return result
198.
199. def linear_selection(population):
200.     population.sort(lamdba x: h(x))
201.
202.     g = [0 for i in range(len(population))]
203.     for i in range(population):
204.         g[i] = 2 - PS + 2 * (PS-1) * (i - 1) / (n - 1)
205.
206.     result = []
207.     for i in range(len(population)):
208.         if randfloat(0, 1) <= g[i] / sum(g)
209.             result.append(population[i])
210.
211.     return result
212.
213.
214. def stochastic_selection(population, K):
215.     START = randfloat(0, 1 / K)
216.
217.     for i .... len(pop)
218.          g[i] = h(population[i])
219.
220.     for i ..... len(pop)
221.           g[i] = g[i] / sum(g)
222.
223.     result = []
224.     for p in range(K):
225.          i = 0
226.          while sum(g[:i]) < (START + p / K):
227.              i++
228.          result.append(population[i])
229.
230.     return result
231.
232.
233. def tournament_selection(population, K, NEW_POPULATION_SIZE):
234.     result = []
235.     for i in range(NEW_POPULATION_SIZE):
236.         random_choice = random.choices(population, K)
237.         random_choice.sort(lambda x: -h(x))
238.
239.         # take only the best
240.         result.append(random_choice[0])
241.
242.     return result
243.