evolution-py/asexual.py at master · basashi-G/evolution-py · GitHub

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
# 有性生殖パターン（交叉のみ）
# かかるエポック数にあまり差はないが、遺伝的多様性がある程度生まれるので個体数が十分少なくても正確

import random
import matplotlib.pyplot as plt
import statistics
from typing import List


gean_length = 10  # depends on Purpose
population = 32  # if up ,  optimal solution is easy to come out(４の倍数)
max_epoch = 100  # depend on population
if population % 4 != 0:
    raise ValueError("populationは4の倍数に設定してください")


def born() -> List[int]:
    return [random.randint(0, 1) for _ in range(gean_length)]


def world_init():
    world = [born() for _ in range(population)]
    return world


def scoring(individual):
    return sum(individual)


def ranking(world):
    # 強者が上流
    return sorted(world, key=scoring, reverse=True)


def selection(world):
    del world[population // 2 :]
    return world


def reborn(selected_world):

    new_world = []
    world = selected_world[:]

    while len(world) != 0:

        sampled_geans_index = random.sample(list(range(len(world))), 2)

        sampled_geans = world[sampled_geans_index[0]], world[sampled_geans_index[1]]
        world.pop(max(*sampled_geans_index))
        world.pop(min(*sampled_geans_index))

        for i in range(len(sampled_geans)):
            new_world.append(crossover(*sampled_geans)[i])
            new_world.append(sampled_geans[i])

    return new_world


def crossover(gean1, gean2):
    crossover_position = random.randint(1, gean_length - 1)
    new_gean1 = gean1[:crossover_position] + gean2[crossover_position:]
    new_gean2 = gean2[:crossover_position] + gean1[crossover_position:]
    return new_gean1, new_gean2


division = 5


def is_convergence(v_list):
    if v_list[-division:] == [0 for _ in range(division)]:
        return True
    return False


plot_x = []
plot_y = []
plot_v = []
plot_mean = []
world = world_init()
v_buffer = None

for i in range(max_epoch):

    ranked_world = ranking(world)

    selected_world = selection(ranked_world)

    reborned_world = reborn(selected_world)

    world = reborned_world

    plot_x += [i for _ in range(population)]

    scoring_list = list(map(scoring, world))
    plot_y += scoring_list
    mean = sum(scoring_list) / len(scoring_list)
    plot_mean.append(mean)

    v = statistics.pstdev(scoring_list)
    plot_v.append(v)

    if is_convergence(plot_v):
        print("Converged!!")
        print("End in " + str(i) + " (Max" + str(max_epoch) + ")")
        break
    else:
        if i == i - 1:
            raise OverflowError("Didn't Converged!")


plt.plot(range(len(plot_mean)), plot_mean, "-o")


plt.plot(range(len(plot_v)), plot_v, "-o")
print(plot_v)


plt.scatter(plot_x, plot_y, c="orange", alpha=0.05, linewidths=2, edgecolors="orange")


print("Awnser is " + str(world[1]))