/
geneticAlgorithms101.py
executable file
·202 lines (155 loc) · 6.13 KB
/
geneticAlgorithms101.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#!/usr/bin/python3.5
# -*-coding:Utf-8 -*
import random
import time
import matplotlib.pyplot as plt
import functools
temps1 = time.time()
# genetic algorithm function
def generate_one_item(Max_weight, Max_value):
item = []
item.append(round(Max_weight * random.random()))
item.append(round(Max_value * random.random()))
return item
def generate_all_items(Number_of_item, Max_weight, Max_value):
list_item = []
for i in range(Number_of_item):
list_item.append(generate_one_item(Max_weight, Max_value))
return list_item
def total_weight_of_item_set(item_set):
total_weight = 0
for item in item_set:
total_weight += item[0]
return total_weight
def generate_one_individual(item_set):
individual = []
for i in range(len(item_set)):
if (100 * random.random() < 50):
individual.append(True)
else:
individual.append(False)
return individual
def generate_first_population(item_set, size_of_population):
population = []
for i in range(size_of_population):
population.append(generate_one_individual(item_set))
return population
def weight_of_individual(individual, item_set):
weight = 0
for i in range(len(individual)):
if (individual[i]):
weight += item_set[i][0]
return weight
def value_of_individual(individual, item_set):
value = 0
for i in range(len(individual)):
if (individual[i]):
value += item_set[i][1]
return value
def value(individual, item_set):
Knapsack_Capacity = round(total_weight_of_item_set(item_set) / 2)
result = 0
if (weight_of_individual(individual, item_set) <= Knapsack_Capacity):
result = value_of_individual(individual, item_set)
return result
def fitness(individual, item_set):
Knapsack_Capacity = round(total_weight_of_item_set(item_set) / 2)
result = 0
if (weight_of_individual(individual, item_set) <= Knapsack_Capacity):
result = 2 * value_of_individual(individual, item_set) - weight_of_individual(individual, item_set)
return result
def compare(individual1, individual2):
return fitness(individual2, item_set) - fitness(individual1, item_set)
def sort_population_by_fitness(population, item_set):
populationSorted = sorted(population, key=functools.cmp_to_key(compare))
return populationSorted
def select_breeders(population_sorted, size_of_population):
result = []
best_individuals = int(size_of_population / 5)
lucky_few = int(size_of_population / 5)
for i in range(best_individuals):
result.append(population_sorted[i])
for i in range(lucky_few):
result.append(random.choice(population_sorted))
random.shuffle(result)
return result
def create_child(individual1, individual2):
result = []
for i in range(len(individual1)):
if (100 * random.random() < 50):
result.append(individual1[i])
else:
result.append(individual2[i])
return result
def create_children(breeders, number_of_child):
result = []
for i in range(int(len(breeders) / 2)):
for j in range(number_of_child):
result.append(create_child(breeders[i], breeders[len(breeders) - 1 - i]))
return result
def mutate_one_individual(individual):
i = int(len(individual) * random.random())
individual[i] = not individual[i]
def mutate_one_individual(individual, mutationRate):
for geneIndex in range(len(individual)):
if (100 * random.random() < mutationRate):
individual[geneIndex] = not individual[geneIndex]
return individual
def mutate_population(population, mutationRate):
for individual in population:
individual = mutate_one_individual(individual, mutationRate)
return (population)
def evolve_several_generation_with_limited_time(item_set, size_of_population, number_of_child, time_limit,
mutationRate):
temps_init = time.time()
value0 = 0
result = []
population = generate_first_population(item_set, size_of_population)
value0 = max(value0, value(get_best_individual_in_population(population), item_set))
result.append(value0)
while (time.time() - temps_init < time_limit):
population_sorted = sort_population_by_fitness(population, item_set)
breeders = select_breeders(population_sorted, size_of_population)
population = create_children(breeders, number_of_child)
population = mutate_population(population, mutationRate)
population = sort_population_by_fitness(population, item_set)
value0 = max(value0, value(get_best_individual_in_population(population), item_set))
return value0
# analysis tools
def get_best_individual_in_population(populationSorted):
return populationSorted[0]
# print result:
def mean_result_evolve(item_set, size_of_population, number_of_child, number_of_sample, mutationRate, time_limit):
meanResult = 0
for i in range(number_of_sample):
meanResult += evolve_several_generation_with_limited_time(item_set, size_of_population, number_of_child,
time_limit, mutationRate)
return (meanResult / number_of_sample)
def print_graph(number_of_child, number_of_sample, time_limit, item_set):
plt.title("Algorithm efficiency with population size")
plt.ylabel('Algorithm result')
plt.xlabel('Population size')
graphX = []
graphY = []
for i in range(19):
size_of_population = 5 * (i + 1)
print(size_of_population)
mutationRate = 0
graphX.append(size_of_population)
result = mean_result_evolve(item_set, size_of_population, number_of_child, number_of_sample, mutationRate,
time_limit)
print(result)
graphY.append(result)
plt.plot(graphX, graphY)
plt.show()
# variables
# Knapsack_Capacity = item_set_total_weight / 2
Number_of_item = 500
Max_value = 10
Max_weight = 10
number_of_child = 5
time_limit = 0.25
number_of_sample = 10
# main
item_set = generate_all_items(Number_of_item, Max_weight, Max_value)
print_graph(number_of_child, number_of_sample, time_limit, item_set)