import random
import math
import matplotlib.pyplot as plt
# 讀取數(shù)據(jù)
f=open("test.txt")
data=f.readlines()
# 將cities初始化為字典，防止下面被當成列表
cities={}
for line in data:
    #原始數(shù)據(jù)以\n換行，將其替換掉
    line=line.replace("\n","")
    #最后一行以EOF為標志，如果讀到就證明讀完了，退出循環(huán)
    if(line=="EOF"):
        break
    #空格分割城市編號和城市的坐標
    city=line.split(" ")
    map(int,city)
    #將城市數(shù)據(jù)添加到cities中
    cities[eval(city[0])]=[eval(city[1]),eval(city[2])]
 
# 計算適應度，也就是距離分之一，這里用偽歐氏距離
def calcfit(gene):
    sum=0
    #最后要回到初始城市所以從-1，也就是最后一個城市繞一圈到最后一個城市
    for i in range(-1,len(gene)-1):
        nowcity=gene[i]
        nextcity=gene[i+1]
        nowloc=cities[nowcity]
        nextloc=cities[nextcity]
        sum+=math.sqrt(((nowloc[0]-nextloc[0])**2+(nowloc[1]-nextloc[1])**2)/10)
 
    return 1/sum
 
# 每個個體的類，方便根據(jù)基因計算適應度
class Person:
    def __init__(self,gene):
        self.gene=gene
        self.fit=calcfit(gene)
class Group:
    def __init__(self):
        self.GroupSize=100  #種群規(guī)模
        self.GeneSize=48    #基因數(shù)量，也就是城市數(shù)量
        self.initGroup()
        self.upDate()
    #初始化種群，隨機生成若干個體
    def initGroup(self):
        self.group=[]
        i=0
        while(i<self.GroupSize):
            i+=1
            #gene如果在for以外生成只會shuffle一次
            gene=[i+1 for i in range(self.GeneSize)]
            random.shuffle(gene)
            tmpPerson=Person(gene)
            self.group.append(tmpPerson)
 
    #獲取種群中適應度最高的個體
    def getBest(self):
        bestFit=self.group[0].fit
        best=self.group[0]
        for person in self.group:
            if(person.fit>bestFit):
                bestFit=person.fit
                best=person
        return best
    #計算種群中所有個體的平均距離
    def getAvg(self):
        sum=0
        for p in self.group:
            sum+=1/p.fit
        return sum/len(self.group)
    #根據(jù)適應度，使用輪盤賭返回一個個體，用于遺傳交叉
    def getOne(self):
        #section的簡稱，區(qū)間
        sec=[0]
        sumsec=0
        for person in self.group:
            sumsec+=person.fit
            sec.append(sumsec)
        p=random.random()*sumsec
        for i in range(len(sec)):
            if(p>sec[i] and p<sec[i+1]):
                #這里注意區(qū)間是比個體多一個0的
                return self.group[i]
    #更新種群相關信息
    def upDate(self):
        self.best=self.getBest()
# 遺傳算法的類，定義了遺傳、交叉、變異等操作
class GA:
    def __init__(self):
        self.group=Group()
        self.pCross=0.35    #交叉率
        self.pChange=0.1    #變異率
        self.Gen=1  #代數(shù)
 
    #變異操作
    def change(self,gene):
        #把列表隨機的一段取出然后再隨機插入某個位置
        #length是取出基因的長度，postake是取出的位置，posins是插入的位置
        geneLenght=len(gene)
        index1 = random.randint(0, geneLenght - 1)
        index2 = random.randint(0, geneLenght - 1)
        newGene = gene[:]       # 產(chǎn)生一個新的基因序列，以免變異的時候影響父種群
        newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
        return newGene
 
    #交叉操作
    def cross(self,p1,p2):
        geneLenght=len(p1.gene)
        index1 = random.randint(0, geneLenght - 1)
        index2 = random.randint(index1, geneLenght - 1)
        tempGene = p2.gene[index1:index2]   # 交叉的基因片段
        newGene = []
        p1len = 0
        for g in p1.gene:
              if p1len == index1:
                    newGene.extend(tempGene)     # 插入基因片段
                    p1len += 1
              if g not in tempGene:
                    newGene.append(g)
                    p1len += 1
        return newGene
 
    #獲取下一代
    def nextGen(self):
        self.Gen+=1
        #nextGen代表下一代的所有基因
        nextGen=[]
        #將最優(yōu)秀的基因直接傳遞給下一代
        nextGen.append(self.group.getBest().gene[:])
        while(len(nextGen)<self.group.GroupSize):
            pChange=random.random()
            pCross=random.random()
            p1=self.group.getOne()
            if(pCross<self.pCross):
                p2=self.group.getOne()
                newGene=self.cross(p1,p2)
            else:
                newGene=p1.gene[:]
            if(pChange<self.pChange):
                newGene=self.change(newGene)
            nextGen.append(newGene)
        self.group.group=[]
        for gene in nextGen:
            self.group.group.append(Person(gene))
            self.group.upDate()
 
    #打印當前種群的最優(yōu)個體信息
    def showBest(self):
        print("第{}代\t當前最優(yōu){}\t當前平均{}\t".format(self.Gen,1/self.group.getBest().fit,self.group.getAvg()))
 
    #n代表代數(shù)，遺傳算法的入口
    def run(self,n):
        Gen=[]  #代數(shù)
        dist=[] #每一代的最優(yōu)距離
        avgDist=[]  #每一代的平均距離
        #上面三個列表是為了畫圖
        i=1
        while(i<n):
            self.nextGen()
            self.showBest()
            i+=1
            Gen.append(i)
            dist.append(1/self.group.getBest().fit)
            avgDist.append(self.group.getAvg())
        #繪制進化曲線
        plt.plot(Gen,dist,'-r')
        plt.plot(Gen,avgDist,'-b')
        plt.show()
 
ga=GA()
ga.run(3000)
print("進行3000代后最優(yōu)解：",1/ga.group.getBest().fit)