diff options
Diffstat (limited to 'ga_demo')
| -rw-r--r-- | ga_demo/tsp_demo.py | 217 |
1 files changed, 217 insertions, 0 deletions
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() |