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()

(三)运行结果

(四)结果描述

  代码是在遗传算法求解三角形火狐拼图改进而来,遗传算法求解正方形拼图游戏只需随机生成一个坐标和一个常数值(作为正方形的边长),通过正方形的性质,可以写出正方形其他三个点的坐标,确定了四个点的坐标之后,进行遗传和变异。

到此这篇关于Python实现遗传算法(虚拟机中运行)的文章就介绍到这了,更多相关Python 遗传算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-11-24

python 如何实现遗传算法

1.基本概念 遗传算法(GA)是最早由美国Holland教授提出的一种基于自然界的"适者生存,优胜劣汰"基本法则的智能搜索算法.该法则很好地诠释了生物进化的自然选择过程.遗传算法也是借鉴该基本法则,通过基于种群的思想,将问题的解通过编码的方式转化为种群中的个体,并让这些个体不断地通过选择.交叉和变异算子模拟生物的进化过程,然后利用"优胜劣汰"法则选择种群中适应性较强的个体构成子种群,然后让子种群重复类似的进化过程,直到找到问题的最优解或者到达一定的进化(运算)时间.

Python实现简单遗传算法(SGA)

本文用Python3完整实现了简单遗传算法(SGA) Simple Genetic Alogrithm是模拟生物进化过程而提出的一种优化算法.SGA采用随机导向搜索全局最优解或者说近似全局最优解.传统的爬山算法(例如梯度下降,牛顿法)一次只优化一个解,并且对于多峰的目标函数很容易陷入局部最优解,而SGA算法一次优化一个种群(即一次优化多个解),SGA比传统的爬山算法更容易收敛到全局最优解或者近似全局最优解. SGA基本流程如下: 1.对问题的解进行二进制编码.编码涉及精度的问题,在本例中精度de

python实现高效的遗传算法

遗传算法属于一种优化算法. 如果你有一个待优化函数,可以考虑次算法.假设你有一个变量x,通过某个函数可以求出对应的y,那么你通过预设的x可求出y_pred,y_pred差距与你需要的y当然越接近越好,这就需要引入适应度(fitness)的概念.假设 fitness = 1/(1+ads(y_pred - y)),那么误差越小,适应度越大,即该个体越易于存活. 设计该算法的思路如下: (1)初始化种群,即在我需要的区间如[-100,100]内random一堆初始个体[x1,x2,x3...],这些

Python实现遗传算法(二进制编码)求函数最优值方式

目标函数 编码方式 本程序采用的是二进制编码精确到小数点后五位,经过计算可知对于 其编码长度为18,对于 其编码长度为15,因此每个基于的长度为33. 参数设置 算法步骤 设计的程序主要分为以下步骤:1.参数设置:2.种群初始化:3.用轮盘赌方法选择其中一半较好的个体作为父代:4.交叉和变异:5.更新最优解:6.对最有个体进行自学习操作:7结果输出.其算法流程图为: 算法结果 由程序输出可知其最终优化结果为38.85029, 输出基因编码为[1 1 0 0 1 0 1 1 1 1 1 1 1 0

python 遗传算法求函数极值的实现代码

废话不多说,大家直接看代码吧! """遗传算法实现求函数极大值-Zjh""" import numpy as np import random import matplotlib.pyplot as plt class Ga(): """求出二进制编码的长度""" def __init__(self): self.boundsbegin = -2 self.boundsend = 3 p

python装饰器相当于函数的调用方式

1. 普通装饰器 import logging 1. foo = use_loggine(foo) def use_loggine(func): def wrapper(): logging.warn("%s is running " % func.__name__) return func() return wrapper @use_loggine def foo(): print "aaa" foo() print foo.__name__ 2. func 需要

利用jupyter网页版本进行python函数查询方式

我就废话不多说了,还是直接看代码吧! import numpy world_alchol=numpy.genfromtxt("world_alcohol.txt",delimter=".",dtype=str) print(type(world_alcohol)) print(world_alcohol) print(help(numpy.genfromtxt)) 实现函数查询. 补充知识:Jupyter Notebook 中查看当前 运行哪个python 在运行

python 轮询执行某函数的2种方式

目标:python中每隔特定时间执行某函数 方法1:使用python的Thread类的子类Timer,该子类可控制指定函数在特定时间后执行一次: 所以为了实现多次定时执行某函数,只需要在一个while循环中多次新建Timer即可. from threading import Timer import time def printHello(): print ("Hello") print("当前时间戳是", time.time()) def loop_func(fu

python微元法计算函数曲线长度的方法

计算曲线长度,根据线积分公式: ,令积分函数 f(x,y,z) 为1,即计算曲线的长度,将其微元化: 其中 根据此时便可在python编程实现,给出4个例子,代码中已有详细注释,不再赘述 ''' 计算曲线长度,根据线积分公式: \int_A^Bf(x,y,z)dl,令积分函数为1,即计算曲线的长度 ''' import numpy as np from mpl_toolkits.mplot3d import * import matplotlib.pyplot as plt ## 求二维圆周长,

简单了解Python中的几种函数

几个特殊的函数(待补充) python是支持多种范型的语言,可以进行所谓函数式编程,其突出体现在有这么几个函数: filter.map.reduce.lambda.yield lambda >>> g = lambda x,y:x+y #x+y,并返回结果 >>> g(3,4) 7 >>> (lambda x:x**2)(4) #返回4的平方 16 lambda函数的使用方法: 在lambda后面直接跟变量 变量后面是冒号 冒号后面是表达式,表达式计算

详解python里使用正则表达式的分组命名方式

详解python里使用正则表达式的分组命名方式 分组匹配的模式,可以通过groups()来全部访问匹配的元组,也可以通过group()函数来按分组方式来访问,但是这里只能通过数字索引来访问,如果某一天产品经理需要修改需求,让你在它们之中添加一个分组,这样一来,就会导致匹配的数组的索引的变化,作为开发人员的你,必须得一行一行代码地修改.因此聪明的开发人员又想到一个好方法,把这些分组进行命名,只需要对名称进行访问分组,不通过索引来访问了,就可以避免这个问题.那么怎么样来命名呢?可以采用(?P<nam

Python基于time模块求程序运行时间的方法

本文实例讲述了Python基于time模块求程序运行时间的方法.分享给大家供大家参考,具体如下: 要记录程序的运行时间可以利用Unix系统中,1970.1.1到现在的时间的毫秒数,这个时间戳轻松完成. 方法是程序开始的时候取一次存入一个变量,在程序结束之后取一次再存入一个变量,与程序开始的时间戳相减则可以求出. Python中取这个时间戳的方法为引入time类之后,使用time.time();就能够拿出来.也就是Java中的System.currentTimeMillis(). 由于Python

Python读取文件内容的三种常用方式及效率比较

本文实例讲述了Python读取文件内容的三种常用方式.分享给大家供大家参考,具体如下: 本次实验的文件是一个60M的文件,共计392660行内容. 程序一: def one(): start = time.clock() fo = open(file,'r') fc = fo.readlines() num = 0 for l in fc: tup = l.rstrip('\n').rstrip().split('\t') num = num+1 fo.close() end = time.cl