随机游走 & ortools demo

9 files changed, 401 insertions, 0 deletions

diff --git a/.idea/misc.xml b/.idea/misc.xml
new file mode 100644
index 0000000..65531ca
--- /dev/null
+++ b/.idea/misc.xml
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project version="4">
+  <component name="ProjectRootManager" version="2" project-jdk-name="Python 3.6" project-jdk-type="Python SDK" />
+</project>
\ No newline at end of file
diff --git a/ga_demo/tsp_demo.py b/ga_demo/tsp_demo.py
new file mode 100644
index 0000000..5a5a406
--- /dev/null
+++ b/ga_demo/tsp_demo.py
@@ -0,0 +1,217 @@
+import numpy as np
+import random
+import operator
+import pandas as pd
+import matplotlib.pyplot as plt
+from operator import itemgetter
+
+
+class City:
+    def __init__(self, x, y):
+        self.x = x
+        self.y = y
+
+    def distance(self, city):
+        x_dis = abs(self.x - city.x)
+        y_dis = abs(self.y - city.y)
+        distance = np.sqrt((x_dis ** 2) + (y_dis ** 2))
+        return distance
+
+    def __repr__(self):
+        return "(" + str(self.x) + "," + str(self.y) + ")"
+
+
+# 越小越好
+class Fitness:
+    def __init__(self, route):
+        self.route = route
+        self.distance = 0
+        self.fitness = 0.0
+
+    def route_distance(self):
+        if self.distance == 0:
+            path_distance = 0
+            for i in range(0, len(self.route)):
+                from_city = self.route[i]
+                to_city = None
+                if i + 1 < len(self.route):
+                    to_city = self.route[i + 1]
+                else:
+                    to_city = self.route[0]
+                path_distance += from_city.distance(to_city)
+            self.distance = path_distance
+        return self.distance
+
+    def route_fitness(self):
+        if self.fitness == 0:
+            self.fitness = 1 / float(self.route_distance())
+        return self.fitness
+
+
+def createRoute(cityList):
+    route = random.sample(cityList, len(cityList))
+    return route
+
+
+def initialPopulation(popSize, cityList):
+    population = []
+
+    for i in range(0, popSize):
+        population.append(createRoute(cityList))
+    return population
+
+
+def rankRoutes(population):
+    fitnessResults = {}
+    for i in range(0,len(population)):
+        fitnessResults[i] = Fitness(population[i]).route_fitness()
+    return sorted(fitnessResults.items(), key=operator.itemgetter(1), reverse=True)
+
+
+def selection(popRanked, eliteSize):
+    selectionResults = []
+    df = pd.DataFrame(np.array(popRanked), columns=["Index", "Fitness"])
+    df['cum_sum'] = df.Fitness.cumsum()
+    df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum()
+
+    for i in range(0, eliteSize):
+        selectionResults.append(popRanked[i][0])
+    for i in range(0, len(popRanked) - eliteSize):
+        pick = 100 * random.random()
+        for i in range(0, len(popRanked)):
+            if pick <= df.iat[i, 3]:
+                selectionResults.append(popRanked[i][0])
+                break
+    return selectionResults
+
+
+def matingPool(population, selectionResults):
+    matingpool = []
+    for i in range(0, len(selectionResults)):
+        index = selectionResults[i]
+        matingpool.append(population[index])
+    return matingpool
+
+
+def breed(parent1, parent2):
+    child = []
+    childP1 = []
+    childP2 = []
+
+    geneA = int(random.random() * len(parent1))
+    geneB = int(random.random() * len(parent1))
+
+    startGene = min(geneA, geneB)
+    endGene = max(geneA, geneB)
+
+    # save_sub_city_list = parent1[startGene: endGene]
+    # target_index = 0
+    # for i in range(len(parent2)):
+    #     while startGene < len(child) < endGene-1:
+    #         child.append(save_sub_city_list[target_index])
+    #         target_index += 1
+    #         continue
+    #     if parent2[i] not in save_sub_city_list:
+    #         child.append(parent2[i])
+    for i in range(startGene, endGene):
+        childP1.append(parent1[i])
+
+    childP2 = [item for item in parent2 if item not in childP1]
+
+    child = childP1 + childP2
+    return child
+
+
+def breedPopulation(matingpool, eliteSize):
+    children = []
+    length = len(matingpool) - eliteSize
+    pool = random.sample(matingpool, len(matingpool))
+
+    for i in range(0, eliteSize):
+        children.append(matingpool[i])
+
+    for i in range(0, length):
+        child = breed(pool[i], pool[len(matingpool) - i - 1])
+        children.append(child)
+    return children
+
+
+def mutate(individual, mutationRate):
+    for swapped in range(len(individual)):
+        if (random.random() < mutationRate):
+            swapWith = int(random.random() * len(individual))
+
+            city1 = individual[swapped]
+            city2 = individual[swapWith]
+
+            individual[swapped] = city2
+            individual[swapWith] = city1
+    return individual
+
+
+def mutatePopulation(population, mutationRate):
+    mutatedPop = []
+
+    for ind in range(0, len(population)):
+        mutatedInd = mutate(population[ind], mutationRate)
+        mutatedPop.append(mutatedInd)
+    return mutatedPop
+
+
+
+def nextGeneration(currentGen, eliteSize, mutationRate):
+    popRanked = rankRoutes(currentGen)
+    selectionResults = selection(popRanked, eliteSize)
+    matingpool = matingPool(currentGen, selectionResults)
+    children = breedPopulation(matingpool, eliteSize)
+    nextGeneration = mutatePopulation(children, mutationRate)
+    return nextGeneration
+
+
+def geneticAlgorithm(population, popSize, eliteSize, mutationRate, generations):
+    pop = initialPopulation(popSize, population)
+    print("Initial distance: " + str(1 / rankRoutes(pop)[0][1]))
+
+    for i in range(0, generations):
+        pop = nextGeneration(pop, eliteSize, mutationRate)
+        print(f"generation: {i}, distance: {1 / rankRoutes(pop)[0][1]}")
+
+    print("Final distance: " + str(1 / rankRoutes(pop)[0][1]))
+    bestRouteIndex = rankRoutes(pop)[0][0]
+    bestRoute = pop[bestRouteIndex]
+    return bestRoute
+
+
+def geneticAlgorithmPlot(population, popSize, eliteSize, mutationRate, generations):
+    pop = initialPopulation(popSize, population)
+    progress = []
+    progress.append(1 / rankRoutes(pop)[0][1])
+
+    for i in range(0, generations):
+        pop = nextGeneration(pop, eliteSize, mutationRate)
+        progress.append(1 / rankRoutes(pop)[0][1])
+
+    plt.plot(progress)
+    plt.ylabel('Distance')
+    plt.xlabel('Generation')
+    plt.show()
+
+
+if __name__ == '__main__':
+
+    cityList = []
+
+    for i in range(0, 25):
+        cityList.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))
+
+    # plt.scatter(list(map(lambda city: city.x, cityList)), list(map(lambda city: city.y, cityList)))
+    # plt.show()
+    best_route = geneticAlgorithm(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=400)
+    # geneticAlgorithmPlot(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)
+    print()
+    # for i in range(0, len(best_route), 2):
+    x = list(map(lambda city: city.x, best_route))
+    y = list(map(lambda city: city.y, best_route))
+    plt.scatter(x, y)
+    plt.plot(x, y, 'ro-')
+    plt.show()
diff --git a/ordemo/__init__.py b/ordemo/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/ordemo/__init__.py
diff --git a/ordemo/channeling.py b/ordemo/channeling.py
new file mode 100644
index 0000000..b53e519
--- /dev/null
+++ b/ordemo/channeling.py
@@ -0,0 +1,4 @@
+
+from ortools.sat.python import cp_model
+
+model = cp_model
\ No newline at end of file
diff --git a/ordemo/send_more_money.py b/ordemo/send_more_money.py
new file mode 100644
index 0000000..77fddda
--- /dev/null
+++ b/ordemo/send_more_money.py
@@ -0,0 +1,54 @@
+
+from ortools.sat.python import cp_model
+
+
+# https://developers.google.com/optimization/cp/cryptarithmetic
+
+class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
+    """Print intermediate solutions."""
+
+    def __init__(self, variables):
+        cp_model.CpSolverSolutionCallback.__init__(self)
+        self.__variables = variables
+        self.__solution_count = 0
+
+    def on_solution_callback(self):
+        self.__solution_count += 1
+        for v in self.__variables:
+            print('%s=%i' % (v, self.Value(v)), end=' ')
+        print()
+
+    def solution_count(self):
+        return self.__solution_count
+
+
+model = cp_model.CpModel()
+
+base = 10
+
+# SEND + MORE = MONEY
+S = model.NewIntVar(1, base-1, 'S')
+M = model.NewIntVar(1, base-1, 'M')
+
+E = model.NewIntVar(0, base-1, 'E')
+N = model.NewIntVar(0, base-1, 'N')
+D = model.NewIntVar(0, base-1, 'D')
+O = model.NewIntVar(0, base-1, 'O')
+R = model.NewIntVar(0, base-1, 'R')
+Y = model.NewIntVar(0, base-1, 'Y')
+
+letters = [S, M, E, N, D, O, R, Y]
+
+model.AddAllDifferent(letters)
+model.Add(S*base**3 + E*base**2 + N*base + D
+          + M*base**3 + O*base**2 + R*base + E
+          == M*base**4 + O*base**3 + N*base**2 + E*base + Y)
+
+solver = cp_model.CpSolver()
+solution_printer = VarArraySolutionPrinter(letters)
+solver.parameters.enumerate_all_solutions = True
+
+solver.Solve(model, solution_printer)
+
+print(
+    f"  {solver.Value(S)}{solver.Value(E)}{solver.Value(N)}{solver.Value(D)}\n+ {solver.Value(M)}{solver.Value(O)}{solver.Value(R)}{solver.Value(E)}\n={solver.Value(M)}{solver.Value(O)}{solver.Value(N)}{solver.Value(E)}{solver.Value(Y)}")
diff --git a/prob/__init__.py b/prob/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/prob/__init__.py
diff --git a/prob/random_walk_1d.py b/prob/random_walk_1d.py
new file mode 100644
index 0000000..445db06
--- /dev/null
+++ b/prob/random_walk_1d.py
@@ -0,0 +1,22 @@
+
+import random
+import matplotlib.pyplot as plt
+from collections import Counter
+import pandas as pd
+
+
+def random_walk(N):
+    x = 0
+    for i in range(N):
+        dx = random.choice([1, -1])
+        x += dx
+    return x
+
+
+if __name__ == '__main__':
+    n_samples = 50000
+    final_x = []
+    for i in range(n_samples):
+        final_x.append(random_walk(100))
+    pd.Series(final_x).value_counts().sort_index().plot(kind='bar')
+    plt.show()
diff --git a/prob/random_walk_demo.py b/prob/random_walk_demo.py
new file mode 100644
index 0000000..6212528
--- /dev/null
+++ b/prob/random_walk_demo.py
@@ -0,0 +1,48 @@
+
+import random
+
+
+def random_walk(N):
+    x, y = 0, 0
+    choices = ['N', 'S', 'E', 'W']
+    for i in range(N):
+        step = random.choice(choices)
+        if step == 'N':
+            y += 1
+        elif step == 'S':
+            y -= 1
+        elif step == 'E':
+            x += 1
+        else:
+            x -= 1
+    return x, y
+
+
+def random_walk_2(N):
+    x, y = 0, 0
+    for i in range(N):
+        dx, dy = random.choice([[0, 1], [0, -1], [1, 0], [-1, 0]])
+        x += dx
+        y += dy
+    return x, y
+
+
+def distance_from_home(x, y):
+    return abs(x) + abs(y)
+
+
+if __name__ == '__main__':
+    # for i in range(25):
+    #     x, y = random_walk_2(10)
+    #     print(f'x = {x}, y = {y}, distance from home: {distance_from_home(x, y)}')
+
+    number_of_walks = 50000
+    for walk_length in range(1, 31):
+        no_transport = 0
+        for i in range(number_of_walks):
+            x, y = random_walk(walk_length)
+            dist = distance_from_home(x, y)
+            if dist <= 5:
+                no_transport += 1
+        no_transport_percentage = float(no_transport)/number_of_walks
+        print(f'walk_length: {walk_length}, no_transport_percentage: {no_transport_percentage}')
diff --git a/prob/random_walk_oo.py b/prob/random_walk_oo.py
new file mode 100644
index 0000000..ce1baf5
--- /dev/null
+++ b/prob/random_walk_oo.py
@@ -0,0 +1,52 @@
+
+import random
+
+
+class Location(object):
+
+    def __init__(self, x, y):
+        self.x = x
+        self.y = y
+
+    def move(self, dx, dy):
+        return Location(self.x + dx, self.y + dy)
+
+    def get_x(self):
+        return self.x
+
+    def get_y(self):
+        return self.y
+
+    def euclidean_distance_from(self, other):
+        x_dist = self.x - other.get_x()
+        y_dist = self.y - other.get_y()
+        return (x_dist ** 2 + y_dist **2)**0.5
+
+    def manhattan_distance_from(self, other):
+        x_dist = self.x - other.get_x()
+        y_dist = self.y - other.get_y()
+        return abs(x_dist) + abs(y_dist)
+
+    def __str__(self):
+        return f'<{self.x}, {self.y}>'
+
+
+class Drunk(object):
+    def __init__(self, name=None):
+        self.name = name
+
+    def __str__(self):
+        if self.name is not None:
+            return self.name
+        return 'Anonymous'
+
+
+def usual_take_step():
+    return random.choice([[-1, 0], [1, 0], [0, -1], [0, 1]])
+
+
+def north_take_step():
+    step_choices = [(0.0, 1.1), (0.0, -0.9), (1.0, 0.0), (-1.0, 0.0)]
+    return random.choice(step_choices)
+
+