人工智能结课作业

2023-07-29 23:25| 来源: 网络整理| 查看: 265

代码已经发布到了github:https://github.com/roadwide/AI-Homework

如果帮到你了，希望给个star鼓励一下

1 遗传算法 1.1算法介绍

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优解的方案，在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。

遗传算法具体步骤：

（1）初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P

（2）个体评价：计算种群P中各个个体的适应度

（3）选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代

（4）交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉

（5）变异运算：在变异概率的控制下，对群体中的个体进行变异，即对某一个体的基因进行随机调整

（6）经过选择、交叉、变异运算之后得到下一代群体P1。

重复以上（1）-（6），直到遗传代数为 T，以进化过程中所得到的具有最优适应度个体作为最优解输出，终止计算。

旅行推销员问题（Travelling Salesman Problem， TSP）：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。

应用遗传算法求解TSP问题时需要进行一些约定，基因是一组城市序列，适应度是按照这个基因的城市顺序的距离和分之一。

1.2实验代码

import random import math import matplotlib.pyplot as plt #读取数据 f=open("test.txt") data=f.readlines() #将cities初始化为字典，防止下面被当成列表 cities={} for line in data: #原始数据以\n换行，将其替换掉 line=line.replace("\n","") #最后一行以EOF为标志，如果读到就证明读完了，退出循环 if(line=="EOF"): break #空格分割城市编号和城市的坐标 city=line.split(" ") map(int,city) #将城市数据添加到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 #每个个体的类，方便根据基因计算适应度 class Person: def __init__(self,gene): self.gene=gene self.fit=calcfit(gene) class Group: def __init__(self): self.GroupSize=100 #种群规模 self.GeneSize=48 #基因数量，也就是城市数量 self.initGroup() self.upDate() #初始化种群，随机生成若干个体 def initGroup(self): self.group=[] i=0 while(ibestFit): 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) #根据适应度，使用轮盘赌返回一个个体，用于遗传交叉 def getOne(self): #section的简称，区间 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 pself.bestFit): self.bestFit=newfit self.bestAddr=self.addr #变异操作 #设置变异后避免了所有鸟都聚集到一个离食物近，但又不是最近的地方，并且就停在那里不动了 def change(self): i,j=random.randrange(0,48),random.randrange(0,48) self.addr[i],self.addr[j]=self.addr[j],self.addr[i] self.upDate() #贪婪倒立变异 def reverse(self): #随机选择一个城市 cityx=random.randrange(1,49) noxcity=self.addr[:] noxcity.remove(cityx) maxFit=0 nearCity=noxcity[0] for c in noxcity: fit=calcfit([c,cityx]) if(fit>maxFit): maxFit=fit nearCity=c index1=self.addr.index(cityx) index2=self.addr.index(nearCity) tmp=self.addr[index1+1:index2+1] tmp.reverse() self.addr[index1+1:index2+1]=tmp self.upDate() #种群的类，里面有很多鸟 class Group: def __init__(self): self.groupSize=500 #鸟的个数、粒子个数 self.addrSize=48 #位置的维度，也就是TSP城市数量 self.w=0.25 #w为惯性系数，也就是保留上次速度的程度 self.pChange=0.1 #变异系数pChange self.pReverse=0.1 #贪婪倒立变异概率 self.initBirds() self.best=self.getBest() self.Gen=0 #初始化鸟群 def initBirds(self): self.group=[] for i in range(self.groupSize): addr=[i+1 for i in range(self.addrSize)] random.shuffle(addr) bird=Bird(addr) self.group.append(bird) #获取当前离食物最近的鸟 def getBest(self): bestFit=0 bestBird=None #遍历群体里的所有鸟，找到路径最短的 for bird in self.group: nowfit=calcfit(bird.addr) if(nowfit>bestFit): bestFit=nowfit bestBird=bird return bestBird #返回所有鸟的距离平均值 def getAvg(self): sum=0 for p in self.group: sum+=1/p.fit return sum/len(self.group) #打印最优位置的鸟的相关信息 def showBest(self): print(self.Gen,":",1/self.best.fit) #更新每一只鸟的速度和位置 def upDateBird(self): self.Gen+=1 for bird in self.group: #g代表group，m代表me，分别代表自己和群组最优、自己最优的差 deltag=switchB2A(self.best.addr,bird.addr) deltam=switchB2A(bird.bestAddr,bird.addr) newv=multiply(self.w,bird.v)[:]+multiply(random.random(),deltag)[:]+multiply(random.random(),deltam) bird.switch(newv) bird.v=newv if(random.random()

【本文地址】

人工智能结课作业

人工智能结课作业

今日新闻

推荐新闻