遗传算法(Genetic Algorithm)之deap学习笔记(五):Santa Fe Ant Trail问题

本文主要是介绍遗传算法(Genetic Algorithm)之deap学习笔记(五):Santa Fe Ant Trail问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Santa Fe Ant Trail问题是一个经典的人工生命(Artificial Life)问题,用来探索生物群体行为和分布式智能的原理。这个问题是基于蚂蚁在寻找食物时的行为而建立的。问题中,蚂蚁在一个网格世界中寻找食物,并在回家时留下一条路径素,用于引导其他蚂蚁找到食物。蚂蚁在寻找食物和回家时,根据自身和周围信息做出决策,例如嗅觉、视觉等。

Santa Fe Ant Trail问题中,蚂蚁的行动是基于一组简单的规则,如蚂蚁在感知到食物的存在时朝食物方向移动,并在回家时遵循已有的路径素。通过这些规则,蚂蚁群体能够在整个网格世界中有效地搜索到食物,并且留下的路径素也能引导其他蚂蚁更快地找到食物。这个问题被广泛用于探索分布式智能和自组织行为的原理,也被用于设计优化算法、模拟群体行为等应用领域。

这篇博客具体讲述的问题是设计一个agent,它可以成功地引导一只人造蚂蚁沿着方形网格上的一条小径收集尽可能最多的食物,最大移动次数为600。

以下为此问题用到的蚂蚁移动的地图的.txt文件

S###............................
...#............................
...#.....................###....
...#....................#....#..
...#....................#....#..
...####.#####........##.........
............#................#..
............#.......#...........
............#.......#........#..
............#.......#...........
....................#...........
............#................#..
............#...................
............#.......#.....###...
............#.......#..#........
.................#..............
................................
............#...........#.......
............#...#..........#....
............#...#...............
............#...#...............
............#...#.........#.....
............#..........#........
............#...................
...##..#####....#...............
.#..............#...............
.#..............#...............
.#......#######.................
.#.....#........................
.......#........................
..####..........................
................................

以下为构建蚂蚁移动的函数

import copy
import random
import numpy
import pygraphviz as pgv
from functools import partialfrom deap import base
from deap import creator
from deap import tools
from deap import gpclass AntSimulator(object):direction = ["north","east","south","west"]dir_row = [1, 0, -1, 0]dir_col = [0, 1, 0, -1]def __init__(self, max_moves):self.max_moves = max_movesself.moves = 0self.eaten = 0self.routine = Nonedef _reset(self):self.row = self.row_start self.col = self.col_start self.dir = 1self.moves = 0  self.eaten = 0self.matrix_exc = copy.deepcopy(self.matrix)@propertydef position(self):return (self.row, self.col, self.direction[self.dir])# 将蚂蚁向左转 90 度def turn_left(self): if self.moves < self.max_moves:self.moves += 1self.dir = (self.dir - 1) % 4# 将蚂蚁向右转 90 度def turn_right(self):if self.moves < self.max_moves:self.moves += 1    self.dir = (self.dir + 1) % 4# 将蚂蚁向前移动一格 def move_forward(self):if self.moves < self.max_moves:self.moves += 1self.row = (self.row + self.dir_row[self.dir]) % self.matrix_rowself.col = (self.col + self.dir_col[self.dir]) % self.matrix_colif self.matrix_exc[self.row][self.col] == "food":self.eaten += 1self.matrix_exc[self.row][self.col] = "passed"def sense_food(self):ahead_row = (self.row + self.dir_row[self.dir]) % self.matrix_rowahead_col = (self.col + self.dir_col[self.dir]) % self.matrix_col        return self.matrix_exc[ahead_row][ahead_col] == "food"# 查看蚂蚁当前面对的方块,然后根据该方块是包含食物还是空的来执行其两个参数之一def if_food_ahead(self, out1, out2):return partial(if_then_else, self.sense_food, out1, out2)def run(self,routine):self._reset()while self.moves < self.max_moves:routine()def parse_matrix(self, matrix):self.matrix = list()for i, line in enumerate(matrix):self.matrix.append(list())for j, col in enumerate(line):if col == "#":self.matrix[-1].append("food")elif col == ".":self.matrix[-1].append("empty")elif col == "S":self.matrix[-1].append("empty")self.row_start = self.row = iself.col_start = self.col = jself.dir = 1self.matrix_row = len(self.matrix)self.matrix_col = len(self.matrix[0])self.matrix_exc = copy.deepcopy(self.matrix)

最多移动600次

ant = AntSimulator(600)# 打开地图
with  open("santafe_trail.txt") as trail_file:ant.parse_matrix(trail_file)

添加终端以及注册进之前的蚂蚁函数

pset = gp.PrimitiveSet("MAIN", 0)def progn(*args):for arg in args:arg()def prog2(out1, out2): return partial(progn,out1,out2)def prog3(out1, out2, out3):     return partial(progn,out1,out2,out3)def if_then_else(condition, out1, out2):out1() if condition() else out2()pset.addPrimitive(ant.if_food_ahead, 2)
pset.addPrimitive(prog2, 2)
pset.addPrimitive(prog3, 3)
pset.addTerminal(ant.move_forward)
pset.addTerminal(ant.turn_left)
pset.addTerminal(ant.turn_right)

注册个体,适应度,详情解释可以看第一篇博客

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", gp.PrimitiveTree, fitness=creator.FitnessMax)toolbox = base.Toolbox()
toolbox.register("expr_init", gp.genFull, pset=pset, min_=1, max_=2)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr_init)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)#toolbox.register("select", tools.selTournament, tournsize=7)
toolbox.register("select", tools.selDoubleTournament, fitness_size = 7, parsimony_size = 1.4, fitness_first = True, fit_attr='fitness' )
toolbox.register("mate", gp.cxOnePoint)
toolbox.register("expr_mut", gp.genFull, min_=0, max_=3)
toolbox.register("mutate", gp.mutUniform, expr=toolbox.expr_mut, pset=pset)

evaluation函数

def evalArtificialAnt(individual):routine = gp.compile(individual, pset)ant.run(routine)return ant.eaten,toolbox.register("evaluate", evalArtificialAnt)# 把min,max等也注册
stats_fit = tools.Statistics(lambda ind: ind.fitness.values)
stats_size = tools.Statistics(len)
stats = tools.MultiStatistics(fitness=stats_fit, size=stats_size)
stats.register("avg", numpy.mean)
stats.register("std", numpy.std)
stats.register("min", numpy.min)
stats.register("max", numpy.max)

主题程序

logbook = tools.Logbook()
pop = toolbox.population(n=500) ## 迭代200次
NGEN, CXPB, MUTPB = 200, 0.2, 0.2fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):ind.fitness.values = fitfor g in range(NGEN):print("-- Generation %i --" % g)offspring = toolbox.select(pop, len(pop))offspring = list(map(toolbox.clone, offspring))for child1, child2 in zip(offspring[::2], offspring[1::2]):if random.random() < CXPB:toolbox.mate(child1, child2)del child1.fitness.valuesdel child2.fitness.valuesfor mutant in offspring:if random.random() < MUTPB:toolbox.mutate(mutant)del mutant.fitness.valuesinvalid_ind = [ind for ind in offspring if not ind.fitness.valid]fitnesses = map(toolbox.evaluate, invalid_ind)for ind, fit in zip(invalid_ind, fitnesses):ind.fitness.values = fitNeval = len(invalid_ind)pop[:] = offspringrecord = stats.compile(pop)logbook.record(gen=g, evals=Neval, **record)print("-- End of evolution --")

把图画出来

import matplotlib.pyplot as plt
%matplotlib inlinegen = logbook.chapters['fitness'].select("gen")
_min = logbook.chapters['fitness'].select("min")
_max = logbook.chapters['fitness'].select("max")
avgs = logbook.chapters['fitness'].select("avg")
stds = logbook.chapters['fitness'].select("std")plt.rc('axes', labelsize=14)
plt.rc('xtick', labelsize=14)
plt.rc('ytick', labelsize=14) 
plt.rc('legend', fontsize=14)fig, ax1 = plt.subplots()
line1 = ax1.plot(gen, avgs)
ax1.set_xlabel("Generation")
ax1.set_ylabel("Fitness")#line2 = ax1.plot(gen, _min)
#line3 = ax1.plot(gen, _max)

找到最佳个体

indv = tools.selBest(pop, 1)[0]
print(indv)toolbox.evaluate(indv)

以下为用树画出来的这个问题的整个流程

nodes, edges, labels = gp.graph(indv)tree = pgv.AGraph()
tree.add_nodes_from(nodes)
tree.add_edges_from(edges)
tree.layout(prog="dot")for i in nodes:n = tree.get_node(i)n.attr["label"] = labels[i]from IPython.display import ImagetreePlot = tree.draw(format='png', prog='dot')
Image(treePlot)

以上就是人工蚂蚁问题的完整代码了,如果有问题可以随时问我,谢谢。

这篇关于遗传算法(Genetic Algorithm)之deap学习笔记(五):Santa Fe Ant Trail问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/192763

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k