# -*- coding: cp936 -*-
import math
import random
import time,os
from matplotlib.pyplot import *
import numpy as np

class Evolution():
    def __init__(self, population, mutation_rate, add, retain_rate, data): 
    
        self.num = population
        self.mutation_rate = mutation_rate
        self.add = add
        self.retain_rate = retain_rate
        self.best = [[1,2],float("inf")]
        self.data = data
        self.mutationnum = 0
        self.insert = range(0, len(self.data))
        self.AllMaxy = []
        self.d = 0
        # 随机生成初始种群
        self.population = self.Gene_population()
        
        matplotlib.use('Agg')
        
    def Gene_population(self):
        """
        获取初始种群（一个含有 self.num 个长度为 self.chromosome_size 的染色体的列表）
        """
        x = []
        newx = range(0, len(self.data))
        
        while len(x) < self.num:
            if newx not in x:
                x += [newx[:]]
                
            random.shuffle(newx)
                                
        return x[:]
    
    def Evolve(self):
        """
        进化
        对当前一代种群依次进行选择、交叉并生成新一代种群，然后对新一代种群进行变异
        """
        
        self.Selection()
        result = '目前第 ' + str(self.d) + ' 代, 此代最优为 ' + str(1 / self.Fitness(self.population[0])) +  ' , 变异次数为 ' + str(self.mutationnum)
        #self.Destroy()
        self.Crossover()
        self.Force_Insert()
        self.Mutation()

        self.d += 1
        return result
        
    def Fitness(self, xi):
        """
        计算适应度，将染色体解码为定义域之间的数字，代入函数计算
        因为是求最大值，所以数值越大，适应度越高
        """
        start = 0
        distance = 0.0
        
        for end in range(1, len(xi)):
            distance += ((self.data[xi[start]][1][0] * 1.0 - self.data[xi[end]][1][0]) ** 2 + (self.data[xi[start]][1][1] * 1.0 - self.data[xi[end]][1][1]) ** 2) ** 0.5  #如果 data 的格式有变这里要改
            start = end
            
        return 1 / distance

    def Selection(self):
        """
        选择
        先对适应度从大到小排序，选出存活的染色体
        再进行随机选择，选出适应度虽然小，但是幸存下来的个体
        """
        xy = sorted([(i, j) for i, j in [(self.Fitness(xi), xi) for xi in self.population]], reverse = True)
        x = [x1 for y1, x1 in xy]
        y = [y1 for y1, x1 in xy]

        eMaxy = 1 / y[0] #此代最佳
        self.AllMaxy += [eMaxy]
 
        self.population = x[:int(self.num * self.retain_rate)] #精英策略

        if eMaxy < self.best[1]:
            self.PlotAndSave(x[0], y[0], 1) 
            os.system('cls')
            print x[0], '\n', '最佳第', self.d, '代', '最优路径长度为', eMaxy
            self.best = [x[0][:],eMaxy]
            
    def Crossover(self):
        """
        染色体的交叉、繁殖，生成新一代的种群
        新出生的孩子，最终会被加入存活下来的父母之中，形成新一代的种群。
        """
        length = len(self.population)
        for i in range(length):
            father= random.choice(self.population)
            mother = random.choice(self.population)
            
            r1 = np.random.random_integers(0, len(father) - 1)
            r2 = np.random.random_integers(1, len(mother) - r1)

            DNA1 = father[r1:r1 + r2]
            
            DNA2 = []
            for i in range(len(mother)):
                if mother[i] not in DNA1:
                    DNA2 += [mother[i]]
            
            child = []
            for i in range(r1):
                child += [DNA2[i]]

            child += DNA1 + DNA2[r1:]

            self.population += [child[:]]


    def Force_Insert(self):
        
        while len(self.population) < self.num:
            self.population += [self.insert[:]]
            random.shuffle(self.insert)


    def Mutation(self):
        """
        变异
        对种群中的所有个体，随机改变某个个体中的某个基因
        """
        each_mutation_rate = self.mutation_rate
        
        for i in range(len(self.population)):
            if random.uniform(0,1) < each_mutation_rate:
                r = np.random.randint(0, len(self.population[i]))
                self.population[i][r], self.population[i][len(self.population[i]) - r - 1] = self.population[i][len(self.population[i]) - r - 1], self.population[i][r]
                self.mutationnum += 1
                
            each_mutation_rate += self.add

    
    def PlotAndSave(self, x, y, f):

        plot(range(1, len(self.AllMaxy) + 1), self.AllMaxy, 'b')
        title(str(x) + '\n\n' + str(1 / y), fontsize = 7)
        
        if f:
            savefig('Max.jpg')
        else:
         
            savefig('%d_Max.jpg' %self.d)
            
        close('all')

        xr = []
        yr = []
        for i in x:
            xr += [self.data[i][1][0]]
            yr += [self.data[i][1][1]]

        xr = np.array(xr + [xr[0]])
        yr = np.array(yr + [yr[0]])
        
        x0 = xr[:2]
        y0 = yr[:2]
        xr = xr[1:]
        yr = yr[1:]
        
        quiver(x0[:-1], y0[:-1], x0[1:] - x0[:-1], y0[1:] - y0[:-1], scale_units = 'xy', angles = 'xy', scale = 1, color='r')
        quiver(xr[:-1], yr[:-1], xr[1:] - xr[:-1], yr[1:] - yr[:-1], scale_units = 'xy', angles = 'xy', scale = 1)
        
        if f:
            savefig('Max_Road.jpg')
        else:
            savefig('%d_Road.jpg' %self.d)
            
        close('all')
        

time.clock()

#------------------------------------------------------------------参数设置------------------------------------------------------------------

population      = 1000    #种群数量
mutation_rate   = 0.001   #变异概率
add             = 0.05   #变异概率随着精英程度递减而增大,0.001
retain_rate      = 0.5   #种群筛选时保留 20% 的精英
data = [["*", [37, 52]], ["*", [49, 49]], ... ,["*", [30,40]]]

#------------------------------------------------------------------参数设置------------------------------------------------------------------

gene = Evolution(population, mutation_rate, add, retain_rate, data)
while 1:
    t = time.clock()
    minute, second = divmod(t, 60)
    hour, minute = divmod(minute, 60)
    try:
        print '\r', gene.Evolve(), " 花费时间 %02d:%02d:%02d" %(hour, minute, second),
    except:
        gene.PlotAndSave(gene.population[:][0], gene.Fitness(gene.population[0]), 0)