Python实现遗传算法(虚拟机中运行)
作者:灼灼华 发布时间:2022-07-10 18:48:07
标签:python,遗传,算法
(一)问题
遗传算法求解正方形拼图游戏
(二)代码
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from PIL import Image, ImageDraw
import os
import gc
import random as r
import minpy.numpy as np
class Color(object):
'''
定义颜色的类,这个类包含r,g,b,a表示颜色属性
'''
def __init__(self):
self.r = r.randint(0, 255)
self.g = r.randint(0, 255)
self.b = r.randint(0, 255)
self.a = r.randint(95, 115)
def mutate_or_not(rate):
'''
生成随机数,判断是否需要变异
'''
return True if rate > r.random() else False
class Triangle(object):
'''
定义三角形的类
属性:
ax,ay,bx,by,cx,cy:表示每个三角形三个顶点的坐标
color : 表示三角形的颜色
img_t : 三角形绘制成的图,用于合成图片
方法:
mutate_from(self, parent): 从父代三角形变异
draw_it(self, size=(256, 256)): 绘制三角形
'''
max_mutate_rate = 0.08
mid_mutate_rate = 0.3
min_mutate_rate = 0.8
def __init__(self, size=(255, 255)):
t = r.randint(0, size[0])
self.ax = r.randint(0, size[0])
self.ay = r.randint(0, size[1])
self.bx = self.ax+t
self.by = self.ay
self.cx = self.ax+t
self.cy = self.ay-t
self.dx = self.ax
self.dy = self.ay-t
self.color = Color()
self.img_t = None
def mutate_from(self, parent):
if mutate_or_not(self.max_mutate_rate):
t = r.randint(0, 255)
self.ax = r.randint(0, 255)
self.ay = r.randint(0, 255)
self.bx = self.ax + t
self.by = self.ay
self.dx = self.ax
self.dy = self.ay - t
self.cx = self.ax + t
self.cy = self.ay - t
if mutate_or_not(self.mid_mutate_rate):
t = min(max(0, parent.ax + r.randint(-15, 15)), 255)
self.ax = min(max(0, parent.ax + r.randint(-15, 15)), 255)
self.ay = min(max(0, parent.ay + r.randint(-15, 15)), 255)
self.bx = self.ax + t
self.by = self.ay
self.dx = self.ax
self.dy = self.ay - t
self.cx = self.ax + t
self.cy = self.ay - t
if mutate_or_not(self.min_mutate_rate):
t = min(max(0, parent.ax + r.randint(-3, 3)), 255)
self.ax = min(max(0, parent.ax + r.randint(-3, 3)), 255)
self.ay = min(max(0, parent.ay + r.randint(-3, 3)), 255)
self.bx = self.ax + t
self.by = self.ay
self.dx = self.ax
self.dy = self.ay - t
self.cx = self.ax + t
self.cy = self.ay - t
# color
if mutate_or_not(self.max_mutate_rate):
self.color.r = r.randint(0, 255)
if mutate_or_not(self.mid_mutate_rate):
self.color.r = min(max(0, parent.color.r + r.randint(-30, 30)), 255)
if mutate_or_not(self.min_mutate_rate):
self.color.r = min(max(0, parent.color.r + r.randint(-10, 10)), 255)
if mutate_or_not(self.max_mutate_rate):
self.color.g = r.randint(0, 255)
if mutate_or_not(self.mid_mutate_rate):
self.color.g = min(max(0, parent.color.g + r.randint(-30, 30)), 255)
if mutate_or_not(self.min_mutate_rate):
self.color.g = min(max(0, parent.color.g + r.randint(-10, 10)), 255)
if mutate_or_not(self.max_mutate_rate):
self.color.b = r.randint(0, 255)
if mutate_or_not(self.mid_mutate_rate):
self.color.b = min(max(0, parent.color.b + r.randint(-30, 30)), 255)
if mutate_or_not(self.min_mutate_rate):
self.color.b = min(max(0, parent.color.b + r.randint(-10, 10)), 255)
# alpha
if mutate_or_not(self.mid_mutate_rate):
self.color.a = r.randint(95, 115)
# if mutate_or_not(self.mid_mutate_rate):
# self.color.a = min(max(0, parent.color.a + r.randint(-30, 30)), 255)
# if mutate_or_not(self.min_mutate_rate):
# self.color.a = min(max(0, parent.color.a + r.randint(-10, 10)), 255)
def draw_it(self, size=(256, 256)):
self.img_t = Image.new('RGBA', size)
draw = ImageDraw.Draw(self.img_t)
draw.polygon([(self.ax, self.ay),
(self.bx, self.by),
(self.cx, self.cy),
(self.dx, self.dy)],
fill=(self.color.r, self.color.g, self.color.b, self.color.a))
return self.img_t
class Canvas(object):
'''
定义每一张图片的类
属性:
mutate_rate : 变异概率
size : 图片大小
target_pixels: 目标图片像素值
方法:
add_triangles(self, num=1) : 在图片类中生成num个三角形
mutate_from_parent(self, parent): 从父代图片对象进行变异
calc_match_rate(self): 计算环境适应度
draw_it(self, i): 保存图片
'''
mutate_rate = 0.01
size = (256, 256)
target_pixels = []
def __init__(self):
self.triangles = []
self.match_rate = 0
self.img = None
def add_triangles(self, num=1):
for i in range(0, num):
triangle = Triangle()
self.triangles.append(triangle)
def mutate_from_parent(self, parent):
flag = False
for triangle in parent.triangles:
t = triangle
if mutate_or_not(self.mutate_rate):
flag = True
a = Triangle()
a.mutate_from(t)
self.triangles.append(a)
continue
self.triangles.append(t)
if not flag:
self.triangles.pop()
t = parent.triangles[r.randint(0, len(parent.triangles) - 1)]
a = Triangle()
a.mutate_from(t)
self.triangles.append(a)
def calc_match_rate(self):
if self.match_rate > 0:
return self.match_rate
self.match_rate = 0
self.img = Image.new('RGBA', self.size)
draw = ImageDraw.Draw(self.img)
draw.polygon([(0, 0), (0, 255), (255, 255), (255, 0)], fill=(255, 255, 255, 255))
for triangle in self.triangles:
self.img = Image.alpha_composite(self.img, triangle.img_t or triangle.draw_it(self.size))
# 与下方代码功能相同,此版本便于理解但效率低
# pixels = [self.img.getpixel((x, y)) for x in range(0, self.size[0], 2) for y in range(0, self.size[1], 2)]
# for i in range(0, min(len(pixels), len(self.target_pixels))):
# delta_red = pixels[i][0] - self.target_pixels[i][0]
# delta_green = pixels[i][1] - self.target_pixels[i][1]
# delta_blue = pixels[i][2] - self.target_pixels[i][2]
# self.match_rate += delta_red * delta_red + \
# delta_green * delta_green + \
# delta_blue * delta_blue
arrs = [np.array(x) for x in list(self.img.split())] # 分解为RGBA四通道
for i in range(3): # 对RGB通道三个矩阵分别与目标图片相应通道作差取平方加和评估相似度
self.match_rate += np.sum(np.square(arrs[i]-self.target_pixels[i]))[0]
def draw_it(self, i):
#self.img.save(os.path.join(PATH, "%s_%d_%d_%d.png" % (PREFIX, len(self.triangles), i, self.match_rate)))
self.img.save(os.path.join(PATH, "%d.png" % (i)))
def main():
global LOOP, PREFIX, PATH, TARGET, TRIANGLE_NUM
# 声明全局变量
img = Image.open(TARGET).resize((256, 256)).convert('RGBA')
size = (256, 256)
Canvas.target_pixels = [np.array(x) for x in list(img.split())]
# 生成一系列的图片作为父本,选择其中最好的一个进行遗传
parentList = []
for i in range(20):
print('正在生成第%d个初代个体' % (i))
parentList.append(Canvas())
parentList[i].add_triangles(TRIANGLE_NUM)
parentList[i].calc_match_rate()
parent = sorted(parentList, key=lambda x: x.match_rate)[0]
del parentList
gc.collect()
# 进入遗传算法的循环
i = 0
while i < 30000:
childList = []
# 每一代从父代中变异出10个个体
for j in range(10):
childList.append(Canvas())
childList[j].mutate_from_parent(parent)
childList[j].calc_match_rate()
child = sorted(childList, key=lambda x: x.match_rate)[0]
# 选择其中适应度最好的一个个体
del childList
gc.collect()
parent.calc_match_rate()
if i % LOOP == 0:
print ('%10d parent rate %11d \t child1 rate %11d' % (i, parent.match_rate, child.match_rate))
parent = parent if parent.match_rate < child.match_rate else child
# 如果子代比父代更适应环境,那么子代成为新的父代
# 否则保持原样
child = None
if i % LOOP == 0:
# 每隔LOOP代保存一次图片
parent.draw_it(i)
#print(parent.match_rate)
#print ('%10d parent rate %11d \t child1 rate %11d' % (i, parent.match_rate, child.match_rate))
i += 1
'''
定义全局变量,获取待处理的图片名
'''
NAME = input('请输入原图片文件名:')
LOOP = 100
PREFIX = NAME.split('/')[-1].split('.')[0] # 取文件名
PATH = os.path.abspath('.') # 取当前路径
PATH = os.path.join(PATH,'results')
TARGET = NAME # 源图片文件名
TRIANGLE_NUM = 256 # 三角形个数
if __name__ == '__main__':
#print('开始进行遗传算法')
main()
(三)运行结果
(四)结果描述
代码是在遗传算法求解三角形火狐拼图改进而来,遗传算法求解正方形拼图游戏只需随机生成一个坐标和一个常数值(作为正方形的边长),通过正方形的性质,可以写出正方形其他三个点的坐标,确定了四个点的坐标之后,进行遗传和变异。
来源:https://blog.csdn.net/qq_52137561/article/details/121492555
0
投稿
猜你喜欢
- 一、安装go get github.com/sirupsen/logrus二、使用1、当做标准库使用logrus实现了标准库log的方法,可
- 今天交流会上,分享前端的开发经验,有一条虽然很快带过,但是我倒是印象蛮深刻的,就写点小结来分享一下吧。不知道是标准害了大家还是大家害了标准,
- 本文实例讲述了php+html5基于websocket实现聊天室的方法。分享给大家供大家参考。具体如下:html5的websocket 实现
- CSS样式和JavaScript脚本是应该放在外部文件中呢?还是把它们放在页面本身之内呢?如何处理是关于一些性能规则的思维,就这些问题,我们
- 这个主要应用于,获取用户输入的时候,防止用户不小心,多输入了一个空格,导致验证无法通过,多用于用户名跟密码的,好多情况下,大家复制的winr
- 随着网页制作热潮的兴起,Dreamweaver 4.0强大的功能深受众多网页制作者的喜爱。特别是Dreamweaver 4.0中有许多第三方
- 本文实例讲述了PHP判断是否微信访问的方法。分享给大家供大家参考,具体如下:在开发中有时需要禁止或者仅允许微信浏览器进行访问,则此时就需要对
- 在Soundbreak我们每天24小时不间断地播放实况音频和视频,所以对于MySQL的新增的复制特性,我们不能做出很令人信服的测试。通过测试
- 最近,W3C的一项公告称,在W3C与XHTML2的合同于今年年底到期后将不会续签。这意味着W3C停止了对XHTML2的开发,转而大力支持HT
- Access保留字&变量名列表,建表时应避免使用这些词汇和符号。Access 2002/2003-A &nbs
- 今天新能测试组的同事找我看一个奇怪的现象。一个tomcat应用,里面只有一个单纯的jsp页面,而且这个jsp页面没有任何java代码(想用这
- 文章中有不正确的或者说辞不清的地方,麻烦大家指出了~~~与PHP字符串转义相关的配置和函数如下: 1.magic_quotes_runtim
- 我刚进入5gsns的时候,我真不知道怎么玩,我是通过白鸦的博客过去的,之前也没有怎么去玩过这类的网站。对于sns网站还算是陌生,不过还好网站
- 简介这是实验室2018年底招新时的考核题目,使用Python编写一个能够完成基本对战的五子棋游戏。面向新手。程序主要包括两个部分,图形创建与
- 远程(如通过互联网)连接access数据库的示例:首先,需要使用TCP/IP,ADO及XML(需要安装Microsoft XML 4.0。)
- asp中使用addnew方法添加一条记录后,我们经常使用取得自递增的ID,而使用bookmark很容易实现这样的功能。rs.open&nbs
- 从我们论坛中收集了这段HTML制作页面需要最大化、最小化时可以借鉴参考。最大化效果:<OBJECT id="max
- 本文简单介绍了Python绘图库Matplotlib的安装,简介如下:matplotlib是python最著名的绘图库,它提供了一整套和ma
- 前言在实际开发中, 有不少的场景需要使用到模糊查询, MongoDB shell 模糊查询很简单:db.collection.find({&
- 在使用ASP来进行后端的数据合法性校验的时候,有些人为满足不同环境下面的数据校验,编写了很多的函数来实现,比如,我们想要校验用户输入的URL