import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
class Map():
def __init__(self, size):
self.size = size
self.xs = np.random.randint(1, 99, size)
self.ys = np.random.randint(1, 99, size)
class Tour():
def __init__(self, m):
self.m = m
self.cities = np.arange(self.m.size)
np.random.shuffle(self.cities)
def clone(self):
c = Tour(self.m)
c.cities = np.copy(self.cities)
return c
def distance(self):
d = 0
for i in range(self.m.size):
d += np.sqrt((self.m.xs[self.cities[i]] - self.m.xs[self.cities[(i + 1) % self.m.size]]) ** 2 +
(self.m.ys[self.cities[i]] - self.m.ys[self.cities[(i + 1) % self.m.size]]) ** 2)
return d
def swap(self, i, j):
t = self.cities[i]
self.cities[i] = self.cities[j]
self.cities[j] = t
def mutate(self):
i, j = np.random.randint(0, self.m.size, 2)
self.swap(i, j)
def crossover(self, other):
i, j = np.random.randint(0, self.m.size, 2)
a = min(i, j)
b = max(i, j)
newa = -1 * np.ones(self.m.size, dtype=np.int)
newb = -1 * np.ones(self.m.size, dtype=np.int)
for x in range(a, b + 1):
newa[x] = other.cities[x]
newb[x] = self.cities[x]
for t, v in ((newa, self), (newb, other)):
c = 0
i = 0
while c < v.m.size:
if t[c] != -1:
c += 1
else:
if v.cities[i] not in t:
t[c] = v.cities[i]
c += 1
i += 1
self.cities = newa
other.cities = newb
def plot(self):
fig = plt.figure()
ax = fig.add_subplot(111, aspect='equal')
ax.set_xlim(0, 100)
ax.set_ylim(0, 100)
myx = []
myy = []
for i in range(self.m.size):
myx.append(self.m.xs[self.cities[i]])
myy.append(self.m.ys[self.cities[i]])
ax.plot(myx, myy)
ax.scatter(myx, myy)
psize = 200
size = 50
iter = 100
mutation_rate = 0.15
world = Map(size)
population = []
for p in range(psize):
population.append(Tour(world))
population[2].plot()
population[2].distance()
2290.9548167698904
population[3].plot()
population[3].distance()
2221.8662087790058
def evoalg(pop, iterations):
bestever
for i in range(iterations):
# evaluate (use the distance function)
# select (Tournament)
newpop = []
for p in range(len(pop)):
a, b = np.random.randint(0, len(pop), 2)
if pop[a].distance() < pop[b].distance():
newpop.append(pop[a].clone())
else:
newpop.append(pop[b].clone())
pop = newpop
# crossover
for p in range(0, len(pop), 2):
pop[p].crossover(pop[p + 1])
# mutation
for p in range(len(pop)):
if np.random.random() < mutation_rate:
pop[p].mutate()
best = pop[0].distance()
bestn = 0
ave = best
for m in range(1, len(pop)):
ave += pop[m].distance()
if pop[m].distance() < best:
best = pop[m].distance()
bestn = m
ave /= len(pop)
print(i, best, ave)
return bestn, pop
b, pop = evoalg(population, iter)
0 1867.54092681 2241.50024925 1 1935.06290933 2196.95669876 2 1850.33454957 2155.7158437 3 1698.85598468 2104.19989761 4 1750.26645748 2065.88257055 5 1703.19498409 2040.7684996 6 1709.94600156 2010.69593766 7 1716.32565546 1988.92268132 8 1564.02791416 1959.69626419 9 1531.70663019 1928.41341152 10 1535.55836051 1907.72009504 11 1621.91046556 1901.70343978 12 1492.56707835 1892.30062922 13 1548.33283331 1898.78674093 14 1521.25969075 1898.33570353 15 1547.04782316 1895.86222319 16 1401.90241302 1877.30892944 17 1443.9493613 1855.95183994 18 1521.85754395 1860.20468441 19 1479.73748085 1842.58620479 20 1545.62233005 1829.63037658 21 1545.62233005 1829.60774648 22 1523.58716332 1836.02122838 23 1523.6615566 1838.81537399 24 1442.50354053 1837.66232793 25 1575.9462765 1834.14714383 26 1556.17005329 1828.90799905 27 1507.14528608 1832.04502609 28 1464.93366744 1811.75184588 29 1546.4235592 1822.89053791 30 1440.89556047 1819.22218071 31 1509.86772183 1816.50522306 32 1488.50751012 1806.60506715 33 1497.70727749 1824.59345318 34 1492.82736874 1802.27159298 35 1450.21892531 1789.07020252 36 1460.82100861 1785.0255148 37 1508.00424363 1790.89600082 38 1521.25284404 1806.16664981 39 1517.08234673 1815.70104567 40 1516.49975729 1814.62213169 41 1546.26080383 1810.81864699 42 1480.78949208 1815.97804592 43 1500.27232614 1819.73714199 44 1493.16836905 1808.89684824 45 1499.65163413 1804.7610573 46 1479.09610271 1806.80096173 47 1475.64256997 1789.21305548 48 1456.01810026 1784.49020255 49 1454.65481144 1796.95014795 50 1396.56777501 1788.93644076 51 1451.77622825 1776.16428379 52 1503.37925111 1761.50629714 53 1361.32116138 1757.31224064 54 1444.37075427 1769.41846028 55 1408.81513623 1751.70867877 56 1445.67414775 1758.93868349 57 1411.34662243 1763.98963633 58 1412.51156336 1748.99306254 59 1411.34662243 1748.51790072 60 1401.66994964 1772.47783329 61 1414.03388231 1774.2417638 62 1405.8002784 1765.05319774 63 1476.33470739 1755.43904758 64 1401.68726938 1757.77878489 65 1373.78917369 1765.21963663 66 1443.98485463 1766.10725372 67 1500.6793822 1766.68240866 68 1482.26655124 1768.37406752 69 1441.40130138 1760.7426536 70 1384.57550858 1761.66532655 71 1429.13597395 1772.22238564 72 1438.91625028 1775.90796026 73 1460.49274986 1786.29628891 74 1493.36139619 1799.78398567 75 1477.88043199 1801.88408656 76 1422.04020772 1794.26387047 77 1490.4218953 1784.91010066 78 1508.39602969 1773.93221077 79 1451.29829689 1773.37600496 80 1395.44496215 1792.59259478 81 1345.79201095 1793.89611363 82 1385.80067276 1786.24625606 83 1507.58615937 1800.68763001 84 1437.11730731 1802.21711267 85 1500.34998421 1809.50228404 86 1525.93824276 1796.55521695 87 1498.32532876 1805.15576814 88 1493.41806766 1795.83099701 89 1508.72786877 1786.80130259 90 1338.74809595 1775.32328472 91 1479.11959878 1764.38456894 92 1489.70986413 1765.51287074 93 1489.15153959 1779.79135278 94 1351.23675765 1777.07775974 95 1462.88127438 1750.03242419 96 1408.87943608 1743.92852853 97 1381.88110586 1728.05112654 98 1498.45633199 1737.67507646 99 1432.65546724 1746.47801911
pop[b].plot()
pop[b].distance()
1432.6554672419504