用Python学数学(二)

用类构建对象

弹跳球程序

让小球动起来

​
xcor = 300
ycor = 300
​
xvel = 1
yvel = 1
​
def setup():
    size(600,600)
    
def draw():
    global xcor,ycor,xvel,yvel
    background(0)
    
    xcor += xvel
    ycor += yvel
    
    if xcor < 0 or xcor > 600:
        xvel = -xvel
    if ycor < 0 or ycor > 600:
        yvel = - yvel
    
    ellipse(xcor,ycor,20,20)

可以按照创建类的方式来创建多个小球

羊吃草程序

  • 创建小羊
  • 创建多个小羊
  • 创建小羊的能量变量,能量用完,则小羊死亡
shawn = []
#建立小羊对象
class Sheep():
    def __init__(self,x,y,sz):
        self.x = x
        self.y = y
        self.sz = sz
        self.energy = random(20,100) #设置小羊的能量值
    
    #小羊移动的方法
    def update(self):
        move = 5
        
        #每次走动消耗1能量
        self.energy -= 1
        
        #如果能量小于0,则删除小羊
        if self.energy < 0:
            shawn.remove(self)
        
        self.x += random(-move,move)
        self.y += random(-move,move)
        fill(255)
        ellipse(self.x,self.y,self.sz,self.sz)
        
def setup():
    global shawn
    size(600,600)
    
    #创建多只小羊
    for i in range(10):
        shawn.append(Sheep(random(0,600),random(0,600),5))
    
def draw():
    global shawn
    background(255)
    for i in shawn:
        i.update()
  • 创建草的类
  • 绘制草模型填满整个屏幕
  • 让小羊走过的草地变成棕色
  • 设置小羊出生的颜色
shawn = []  #存储小羊的列表
grassList = []  #存储草的列表
patchSize = 10  #草地的大小
​
​
#建立小羊对象
class Sheep():
    def __init__(self,x,y,sz,_color):
        self._color = _color   #小羊出生的颜色
        self.x = x
        self.y = y
        self.sz = sz
        self.energy = random(20,100) #设置小羊的能量值
    
    #小羊移动的方法
    def update(self):
        move = 5
        
        #每次走动消耗1能量
        self.energy -= 1
        
        #如果能量小于0,则删除小羊
        if self.energy < 0:
            shawn.remove(self)
        
        self.x += random(-move,move)
        self.y += random(-move,move)
        
        #如果小羊超过屏幕边缘,则将它扭转到屏幕对侧
        if self.x > width:
            self.x %= width
        if self.y > height:
            self.y %= height
        if self.x < 0:
            self.x += width
        if self.y < 0:
            self.y += height
        
        #找到小羊的所在的草地,然后将草地设置为棕色
        xscl = int(self.x/patchSize)
        yscl = int(self.y/patchSize)
        
        grass = grassList[xscl * rows_of_grass + yscl]
        grass.eaten = True
        
        #给小羊添加能量
        self.energy += grass.energy
        
        fill(self._color)
        ellipse(self.x,self.y,self.sz,self.sz)
​
class Grass:
    def __init__(self,x,y,sz):
        self.x = x
        self.y = y
        self.energy = 5
        self.eaten = False 
        self.sz = sz
    def update(self):
        if self.eaten:
            fill(89,71,72)
        else:
            fill(51,118,4)
        noStroke()  #去掉矩形的黑色轮廓
        rect(self.x,self.y,self.sz,self.sz)
​
​
def setup():
    global shawn
    size(600,600)
    
    global rows_of_grass
    rows_of_grass = width/patchSize
    
    #创建多只小羊
    for i in range(10):
        shawn.append(Sheep(random(0,600),random(0,600),5,color(random(70,255),random(70,255),random(70,255))))
        
    #创建草
    for x in range(0,width,patchSize):
        for y in range(0,height,patchSize):
            grassList.append(Grass(x,y,patchSize))
        
    
def draw():
    global shawn
    background(255)
    
    for i in grassList:
        i.update()
    
    for i in shawn:
        i.update()
  • 让小羊能够进行分娩
        #如果能量小于0,则删除小羊
        if self.energy < 0:
            shawn.remove(self)
            
        #让小羊进行分娩
        if self.energy >= 50:
            self.energy -= 30
            shawn.append(Sheep(self.x,self.y,5,self._color))
image-20211231113339148

用递归制作分形

绘制一颗分形树

#绘制树干以及子树
def setup():
    size(600,600)
​
def draw():
    background(255)
    translate(300,500)
    y(100)
​
def y(sz):
    line(0,0,0,-sz)
    translate(0,-sz)
    rotate(radians(30))
    line(0,0,0,-0.8*sz) # 右树枝
    rotate(radians(-60))
    line(0,0,0,-0.8*sz) # 左树枝
    rotate(radians(30))
    translate(0,sz)

利用递归绘制分形树

def setup():
    size(600,600)
    
def draw():
    background(255)
    translate(300,500)
    
    #将鼠标的位置进行映射
    #让树随着鼠标的运动而变化
    level = int(map(mouseX,0,width,0,10))
    y(100,level)
    
def y(sz,level):
    if level > 0:
        line(0,0,0,-sz)
        translate(0,-sz)
        rotate(radians(30))
        
        y(0.8 * sz,level - 1)
        
        rotate(radians(-60))
        
        y(0.8 * sz,level - 1)
        
        rotate(radians(30))
        translate(0,sz)

科赫雪花

科赫雪花是由等边三角形组成的,我们从一条直线段开始,给它加上一个“凸起”,然后,我们给得到的每条直线段加上一个更小的凸起,之后不断重复这一过程

NeatReader-1641050175216
def setup():
    size(600,600)
    
def draw():
    background(255)
    translate(100,100)
    snowflake(400,3)
    
def segment(sz,level):
    if level == 0:
        line(0,0,sz,0)
        translate(sz,0)
    else:
        segment(sz/3.0,level - 1)
        rotate(radians(-60))
        segment(sz/3.0,level - 1)
        rotate(radians(120))
        segment(sz/3.0,level - 1)
        rotate(radians(-60))
        segment(sz/3.0,level - 1)
        
​
def snowflake(sz,level):
    for i in range(3):
        segment(sz,level)
        rotate(radians(120))

解析内容

绘制一个三角形:

def snowflake(sz,level):
    for i in range(3):
        line(0,0,sz,0)
        translate(sz,0)
        rotate(radians(120))

在三角形的每条边中,从上图可知,如果深度在0时,就是一条直线,如果为1的话,绘制顺序为:绘制直线—绘制凸起—绘制直线

利用递归,对每个三个部分的每个部分进行重复绘制,即可得到结果

谢尔宾斯三角形

NeatReader-1641051972173
def setup():
    size(600,600)
    
def draw():
    background(255)
    translate(50,450)
    sierpinski(100,2)
    
​
​
def sierpinski(sz,level):
    if level == 0:
        fill(0)
        triangle(0,0,sz,0,sz/2.0,-sz*sqrt(3)/2.0)
    else:
        for i in range(3):
            sierpinski(sz/2.0,level -1)
            translate(sz,0)
            rotate(radians(-120))

正方形分形

NeatReader-1641203032659
def squareFractal(sz,level):
    if level == 0:
        rect(0,0,sz,sz)
    else:
        #逐个绘制正方形,一共绘制三个
        rect(0,0,sz/2.0,sz/2.0)
        translate(sz/2.0,0)
        rect(0,0,sz/2.0,sz/2.0)
        translate(-sz/2.0,sz/2.0)
        rect(0,0,sz/2.0,sz/2.0)

进行递归调用

def setup():
    size(600,600)
    fill(128,0,128)
    noStroke()
    
def draw():
    background(255)
    translate(50,50)
    squareFractal(500,3)
​
​
def squareFractal(sz,level):
    if level == 0:
        rect(0,0,sz,sz)
    else:
        squareFractal(sz/2.0,level - 1)
        translate(sz/2,0)
        squareFractal(sz/2.0,level - 1)
        translate(-sz/2.0,sz/2.0)
        squareFractal(sz/2.0,level - 1)
        translate(0,-sz/2.0)
    

绘制龙形曲线

NeatReader-1641203198722
def setup():
    size(600,600)
    stroke(2)
    
def draw():
    background(255)
    translate(200,300)
    leftDragon(50,11)
​
#定义左拐龙
def leftDragon(sz,level):
    if level == 0:
        line(0,0,sz,0)
        translate(sz,0)
    else:
        leftDragon(sz,level - 1)
        rotate(radians(-90))
        rightDragon(sz,level - 1)
#定义右拐龙    
def rightDragon(sz,level):
    if level == 0:
        line(0,0,sz,0)
        translate(sz,0)
    else:
        leftDragon(sz,level -1)
        rotate(radians(90))
        rightDragon(sz,level -1)

按键方法设定

  def keyPressed():
      global thelevel,size1
      if key == CODED:
          if keyCode == UP:
              thelevel += 1
          if keyCode == DOWN:
              thelevel -= 1
          if keyCode == LEFT:
              size1 -= 5
          if keyCode == RIGHT:
              size1 += 5

元胞自动机

有这样一种模拟细胞、生物体和其他生命系统随环境生长变化的工具。由于它们和独立的生物体相似,这些模型被称为元胞自动机(cellular automata,CA)。所谓的自动机是指可以自主运行的东西

创建一个元胞自动机

#定义长宽格子的个数
grid_w = 17
grid_h = 17
​
#细胞的大小
sz = 18
​
#细胞列表
Cells = []
​
#创建细胞类
class Cell:
    #state表示细胞的状态,黑色为开
    def __init__(self,c,r,state = 0) :
        self.c = c
        self.r = r
        self.state = state
        
    def display(self):
        if self.state == 1:
            fill(0)
        else:
            fill(255)
        rect(sz * self.r,sz * self.c,sz,sz)
​
#创建细胞列表,并将中心的细胞设置为开
def createCellList():
    global grid_h,grid_h
    newList = []
    for j in range(grid_h):
        newList.append([])
        for i in range(grid_w):
            newList[j].append(Cell(i,j,0))
    
    #把中心的细胞设置为开
    newList[grid_h/2][grid_w/2].state = 1
    return newList
​
​
def setup():
    global Cells,sz
    
    background(255)
    size(600,600)
    
    #让细胞大小随着屏幕宽度适应
    if width/grid_w > width//grid_w:
        sz = width // grid_w + 1
    else:
        sz = width // grid_w
    
    #创建细胞列表
    Cells = createCellList()
    
def draw():
    global Cells
    
    #遍历并绘制细胞
    for i in Cells:
        for j in i:
            j.display()

让CA进行生长

NeatReader-1641215007212

在这个CA中,如果有一个细胞有一个或四个邻居的状态为开,我们就将它的状态设置为开(并一直保持开启)

#定义长宽格子的个数
grid_w = 17
grid_h = 17
​
#细胞的大小
sz = 18
​
#细胞列表
Cells = []
​
generation = 0
cishu = 3
​
#创建细胞类
class Cell:
    #state表示细胞的状态,黑色为开
    def __init__(self,c,r,state = 0) :
        self.c = c
        self.r = r
        self.state = state
        
    def display(self):
        if self.state == 1:
            fill(0)
        else:
            fill(255)
        rect(sz * self.r,sz * self.c,sz,sz)
        
    #检查细胞的上下左右邻居是否为开
    def checkNeighbors(self):
        if self.state == 1:return 1
        neighbs = 0
        
        for dc,dr in [[-1,0],[1,0],[0,-1],[0,1]]:
            try:
                if Cells[self.r + dr][self.c + dc].state == 1:
                    neighbs += 1
            except IndexError:
                continue
            
        if neighbs in [1,4]:
            return 1
        else:
            return 0
        
​
#创建细胞列表,并将中心的细胞设置为开
def createCellList():
    global grid_h,grid_h
    newList = []
    for j in range(grid_h):
        newList.append([])
        for i in range(grid_w):
            newList[j].append(Cell(i,j,0))
    
    #把中心的细胞设置为开
    newList[grid_h/2][grid_w/2].state = 1
    return newList
​
#将每一次更新的结果进行保存
def update(cellList):
    global Cells
    newList = []
    for r,row in enumerate(Cells):
        newList.append([])
        for c,cell in enumerate(row):
            newList[r].append(Cell(c,r,cell.checkNeighbors()))
    return newList[::]
​
#用键盘上键控制CA生长
def keyPressed():
    global cishu
    if key == CODED:
        if keyCode == UP:
            cishu += 1
​
​
def setup():
    global Cells,sz
    
    background(255)
    size(600,600)
    
    #让细胞大小随着屏幕宽度适应
    if width/grid_w > width//grid_w:
        sz = width // grid_w + 1
    else:
        sz = width // grid_w
    
    #创建细胞列表
    Cells = createCellList()
    
def draw():
    
    global Cells,generation
    
    #迭代次数没有到达cishu,则继续更新
    if generation != cishu:
        Cells = update(Cells)
        generation += 1
    
    #遍历并绘制细胞
    for i in Cells:
        for j in i:
            j.display()
image-20220103211049117

生命游戏

这个游戏是英国数学家约翰 • 康威发明的,其中的 CA 有三条简单的规则:

(1) 如果一个活细胞的活邻居少于两个,它就会死;

(2) 如果一个活细胞的活邻居多于三个,它也会死;

(3) 如果一个死亡细胞恰好有三个活邻居,它就复活。

修改创建细胞列表函数

#创建细胞列表,并将中心的细胞设置为开
def createCellList():
    global grid_h,grid_h
    newList = []
    for j in range(grid_h):
        newList.append([])
        for i in range(grid_w):
            newList[j].append(Cell(i,j,choice([0,1])))
    
    #把中心的细胞设置为开
    return newList

利用choice随机挑选新细胞死活

from random import choice

更新检查规则

    #检查细胞的上下左右邻居是否为开
    def checkNeighbors(self):
        neighbs = 0
        
        for dc,dr in [[-1,-1],[-1,0],[-1,1],[1,0],[1,-1],[1,1],[0,-1],[0,1]]:
            try:
                if Cells[self.r + dr][self.c + dc].state == 1:
                    neighbs += 1
            except IndexError:
                continue
        if self.state == 1:
            if neighbs in [2,3]:
                return 1
            return 0
        if neighbs == 3:
            return 1
        return 0

初等元胞自动机

规则如下图所示:

NeatReader-1641221006919

第一行的细胞为元细胞,如果元细胞是打开的,则他的值为1,否则为0

左中右分别代表第一行细胞,结果细胞代表第二行细胞

左边细胞中间细胞右边细胞结果细胞
1110
1100
1010
1001
0111
0101
0011
0000

根据表格编写出映射函数

ruleset = [0,0,0,1,1,1,1,0]
​
#a,b,c为左中右细胞所对应的值,该函数的结果对应结果细胞的值
def rules(a,b,c):
    return ruleset[7 - (4 * a + 2 * b + c)]

第一行的细胞从中心开始

根据规则,编写完成自动机程序

w = 50
rows = 10
cols = 11
​
ruleset = [0,0,0,1,1,1,1,0]
​
def rules(a,b,c):
    return ruleset[7 - (4 * a + 2 * b + c)]
​
​
#进行迭代
def generate():
    for i,row in enumerate(cells):
        for j in range(1,len(row) - 1):
            left = row[j-1]
            me = row[j]
            right = row[j+1]
            if i < len(cells) - 1:
                cells[i+1][j] = rules(left,me,right)
    return cells
​
​
​
def setup():
    global cells
    size(600,600)
    
    cells = []
    for r in range(rows):
        cells.append([])
        for c in range(cols):
            cells[r].append(0)
    cells[0][cols//2] = 1
    
​
def draw():
    background(255)
    
    cells = generate()
    
    for i,cell in enumerate(cells):
        for j,v in enumerate(cell):
            if v == 1:
                fill(0)
            else:
                fill(255)
            rect(j*w,w*i,w,w)

用遗传算法解决问题

要破解密码,我们首先生成猜测,然后根据它们与目标的匹配程度进行评分。下面就是和“猜测检验法”的不同之处了:我们保留最佳的猜测,然后使它们不断地随机突变,直到解读出消息为止。程序并不知道哪个字母是对的、哪个是错的,但最佳猜测会随着突变不断向目标靠近。目前看来,这个方法好像不太可靠,不过你马上就会看到它破解密码的速度快得惊人。这种方法叫作遗传算法(genetic algorithm),计算机科学家基于自然选择和进化生物学的理论用这个算法来解决问题。它的灵感来源于生物有机体的适应(adapt)和突变(mutate),以及它们通过微小优势建立起来的种群优势

用遗传算法猜出句子

import random
​
target = "i never go back on my word,because that is my Ninja way"
​
characters = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.',?!"
​
#从字符当中随机挑选字符进行拼接,随机得到猜测
def makeList():
    charList = []
​
    for i in range(len(target)):
        charList.append(random.choice(characters))
    return charList
​
#计算mylist猜测的得分,成功匹配一次,则matches增加
def score(mylist):
    matches = 0
    for i in range(len(target)):
        if mylist[i] == target[i]:
            matches += 1
    return matches
​
#对mylist中的字符,进行随机挑选,并随机替换
def mutate(mylist):
    newlist = list(mylist)
    
    new_letter = random.choice(characters)
    index = random.randint(0,len(target)-1)
    newlist[index] = new_letter
​
    return newlist
​
#置随机数种子
random.seed()
bestList = makeList()
bestScore = score(bestList)
​
guesses = 0
​
while True:
    #将bestList中的字符进行随机替换
    guess = mutate(bestList)
    #计算bestList的分数
    guessScore = score(guess)
​
    #猜测次数加1
    guesses += 1
​
    #如果分数比原来的小,则跳出本次循环
    if guessScore < bestScore:
        continue
​
    #如果分数比原来的大,则输出答案
    print("".join(guess),guessScore,guesses)
    
    #如果拿到满分,已经得到结果,则输出答案
    if guessScore == len(target):
        break
​
    #更新best相关变量,以便下次循环使用
    bestList = list(guess)
    bestScore = score(bestList)

利用最好的答案进行随机突变,在经过上万次的迭代之后,我们可以获得最终的答案

旅行商问题

旅行商问题(Traveling Salesperson Problem,TSP)是一个古老的难题,它很好理解,但很难解决。一个商品推销员需要前往给定数量的城市,每座城市只访问一次,并且最终回到起始城市,我们的目标是找出长度最短的路线。

n个城市之间有:\frac{(n-1)!}{2}

绘制城市

import random
​
cities = []
​
#创建城市类,x,y为坐标,num为编号
class City:
    def __init__(self,x,y,num):
        self.x = x
        self.y = y
        self.number = num
    
    def display(self):
        fill(0,255,255)
        ellipse(self.x,self.y,10,10)
        
        textSize(20)
        text(self.number,self.x - 10,self.y - 10)
        
        noFill()
​
def setup():
    size(600,600)
    background(0)
    
    #创建6个城市
    for i in range(6):
        cities.append(City(random.randint(50,width - 50),random.randint(50,height - 50),i))
    
    #让6个城市进行显示
    for city in cities:
        city.display()

绘制路线

import random
​
cities = []
N_CITIES = 6
​
#创建城市类,x,y为坐标,num为编号
class City:
    def __init__(self,x,y,num):
        self.x = x
        self.y = y
        self.number = num
    
    def display(self):
        fill(0,255,255)
        ellipse(self.x,self.y,10,10)
        
        textSize(20)
        text(self.number,self.x - 10,self.y - 10)
        
        noFill()
#创建路线类
class Route:
    def __init__(self):
        self.distance = 0
        self.cityNums = random.sample(list(range(N_CITIES)),N_CITIES)    
    def display(self):
        strokeWeight(3)
        stroke(255,0,255)
        
        
        beginShape()
        for i in self.cityNums:
            vertex(cities[i].x,cities[i].y)
            cities[i].display()
            
        #CLOSE可以让第一个点和最后一个点自动闭合
        endShape(CLOSE)
​
def setup():
    size(600,600)
    background(0)
    
    #创建6个城市
    for i in range(N_CITIES):
        cities.append(City(random.randint(50,width - 50),random.randint(50,height - 50),i))
    #创建路线类,并进行显示
    route1 = Route()
    route1.display()

random.sample()的作用是,从列表list中随机挑选num个元素出来,并返回一个新的列表,会保证每个抽取都不会重复

random.sample(list,num)

下面为完成程序,随机进行突变,然后获得最佳答案

import random
​
cities = []
N_CITIES = 6
​
random_improvements = 0
mutated_improvements = 0
​
​
#创建城市类,x,y为坐标,num为编号
class City:
    def __init__(self,x,y,num):
        self.x = x
        self.y = y
        self.number = num
    
    def display(self):
        fill(0,255,255)
        ellipse(self.x,self.y,10,10)
        
        textSize(20)
        text(self.number,self.x - 10,self.y - 10)
        
        noFill()
​
class Route:
    def __init__(self):
        self.distance = 0
        self.cityNums = random.sample(list(range(N_CITIES)),N_CITIES)
        self.distance = 0
              
    def display(self):
        strokeWeight(3)
        stroke(255,0,255)
        beginShape()
        for i in self.cityNums:
            vertex(cities[i].x,cities[i].y)
            cities[i].display()
            
        #CLOSE可以让第一个点和最后一个点自动闭合
        endShape(CLOSE)
        
    #计算城市之间的距离
    def calcLength(self):
        self.distance = 0
        for i,num in enumerate(self.cityNums):
            self.distance += dist(cities[num].x,cities[num].y,cities[self.cityNums[i-1]].x,cities[self.cityNums[i-1]].y)
        return self.distance
def setup():
    global best,record_distance
    size(600,600)
    background(0)
    
    #创建6个城市
    for i in range(N_CITIES):
        cities.append(City(random.randint(50,width - 50),random.randint(50,height - 50),i))
    
    best = Route()
    record_distance = best.calcLength()
    
​
def draw():
    global best,record_distance,random_improvements
    
    background(0)
    
    #显示最好的路线
    best.display()
    println(record_distance)
    print("random:"+str(random_improvements))
    
    #对路线进行突变
    route1 = Route()
    length1 = route1.calcLength()
    
    if length1 < record_distance:
        record_distance = length1
        best = route1
        
        random_improvements += 1
image-20220104105247707

利用最好的结果进行变异

在刚才的程序当中,如果我们城市的数量到达20个左右,利用随机突变的方法是很难得到最优解的,我们可以尝试着使用猜句子中的方法,将最好的结果进行突变,以此来加快突变速度

    def mutateN(self,num):
        #随机挑选num个结果进行交换 
        indices = random.sample(list(range(N_CITIES)),num)
        
        #复制父亲的游走序列
        child = Route()
        child.cityNums = self.cityNums[::]
        
        #对num个结果进行相互交换
        for i in range(num - 1):
            child.cityNums[indices[i]],child.cityNums[indices[(i + 1)%num]] = \
            child.cityNums[indices[(i + 1)%num]],child.cityNums[indices[i]]
        return child

下面更改draw()方法中的内容

def draw():
    global best,record_distance,random_improvements
    global mutated_improvements
    
    background(0)
    
    #显示最好的路线
    best.display()
    println(record_distance)
    print("random:"+str(random_improvements))
    print("mutated:"+str(mutated_improvements))
    
    #对路线进行突变
    route1 = Route()
    length1 = route1.calcLength()
    
    if length1 < record_distance:
        record_distance = length1
        best = route1
        
        random_improvements += 1
        
    for i in range(2,6):
        mutated = Route()
        mutated.cityNums = best.cityNums[::]
        
        mutated = mutated.mutateN(i)
        
        length2 = mutated.calcLength()
        if length2 < record_distance:
            record_distance = length2
            best = mutated
            mutated_improvements += 1

现在会发现,整个变异速度快了很多

在种群中进行交叉变异

创建种群列表,并对种群列表中找到距离最短的进行变异,并将每次变异的结果加入到种群当中

import random
​
cities = []
N_CITIES = 50
​
random_improvements = 0
mutated_improvements = 0
mutated_improvements = 0
​
#创建种群列表
population = []
#路线数量
POP_N = 1000
​
​
#创建城市类,x,y为坐标,num为编号
class City:
    def __init__(self,x,y,num):
        self.x = x
        self.y = y
        self.number = num
    
    def display(self):
        fill(0,255,255)
        ellipse(self.x,self.y,10,10)
        
        textSize(20)
        text(self.number,self.x - 10,self.y - 10)
        
        noFill()
​
        
​
class Route:
    def __init__(self):
        self.distance = 0
        self.cityNums = random.sample(list(range(N_CITIES)),N_CITIES)
        self.distance = 0
              
    def display(self):
        strokeWeight(3)
        stroke(255,0,255)
        beginShape()
        for i in self.cityNums:
            vertex(cities[i].x,cities[i].y)
            cities[i].display()
            
        #CLOSE可以让第一个点和最后一个点自动闭合
        endShape(CLOSE)
        
    #计算城市之间的距离
    def calcLength(self):
        self.distance = 0
        for i,num in enumerate(self.cityNums):
            self.distance += dist(cities[num].x,cities[num].y,cities[self.cityNums[i-1]].x,cities[self.cityNums[i-1]].y)
        return self.distance
    
    def mutateN(self,num):
        indices = random.sample(list(range(N_CITIES)),num)
        child = Route()
        child.cityNums = self.cityNums[::]
        
        for i in range(num - 1):
            child.cityNums[indices[i]],child.cityNums[indices[(i + 1)%num]] = \
            child.cityNums[indices[(i + 1)%num]],child.cityNums[indices[i]]
        return child
    
    #与其他结果进行交叉
    def crossover(self,partner):
        child = Route()
        
        #随机选择切点
        index = random.randint(1,N_CITIES - 1)
        
        #添加切分点之前的元素
        child.cityNums = self.cityNums[:index]
        
        #有一半的概率将她反转
        if random.random() < 0.5:
            child.cityNums = child.cityNums[::-1]
        
        #不在切片中的数的列表
        notionslice = [x for x in partner.cityNums if x not in child.cityNums]
    
        #添加不在切片中的数据
        child.cityNums  += notionslice
        
        return child
        
    
        
def setup():
    global best,record_distance
    size(600,600)
    background(0)
    
    #创建6个城市
    for i in range(N_CITIES):
        cities.append(City(random.randint(50,width - 50),random.randint(50,height - 50),i))
    
    #创建种群
    for i in range(POP_N):
        population.append(Route())
    
    #从种群当中随机选择一个作为初始
    best = random.choice(population)
    record_distance = best.calcLength()
    first = record_distance
    
​
def draw():
    global best,record_distance,random_improvements
    global mutated_improvements,population
    
    background(0)
    
    #显示最好的路线
    best.display()
    println(record_distance)
     
    population.sort(key = Route.calcLength)
    population = population[:POP_N]
    length1 = population[0].calcLength()
    
    if length1 < record_distance:
        record_distance = length1
        best = population[0]
    
    #在种群中做交叉
    for i in range(POP_N):
        parentA,parentB = random.sample(population,2)
        child = parentA.crossover(parentB)
        population.append(child)
    
    #将最好的进行交换,并将交换结果添加到种群中    
    for i in range(3,25):
        if i < N_CITIES:
            new = best.mutateN(i)
            population.append(new)
            
    #随机选择种群中的ROUTE进行交换,并将交换结果放在种群中
    for i in range(3,25):
        if i < N_CITIES:
            new = random.choice(population)
            new = new.mutateN(i)
            population.append(new)        

在这个例子中,有点类似于生物种群的进化,在种群当中选择最优的一个个体,与其他的个体进行交配,或者是自己的序列互换,得到更好的结果,并将这些更好的结果放入种群当中,

由于每次都是在种群中选择最好的一个进行进化,所以得到的结果总是最好的,

因此使得变异的速度加快,以下是50个城市的最终计算图

image-20220104114108004
image-20220104115911930
© 版权声明
THE END
喜欢就支持以下吧
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片