另一个角度看基因遗传

基因遗传算法

复现mooc陈斌教授拼图代码思考。]

简介

遗传算法就是运用计算机模拟生物的遗传进化，寻找最优解的算法。在自然界中种群经过遗传，变异，自然选择的作用，整个种群会朝着最适应环境的方向发展。

算法过程

拼图游戏

拼图游戏，运用100个半透明的三角形拼成一个图案，类似这种红色太极图案。

我们把每一张由三角形组合成的图片看成一个个体，组合成他的一百个看成一百个染色体。而他的一百个三角形所具有的三个点的位置坐标，颜色组成这些信息我们可以看作生物学讲的染色体上面的基因。
经过这样的映射，我们就可以用遗传算法来解决拼图的问题了。 我们可以让两张图片进行繁殖了，两张图片怎么繁殖呢，跟人类一样呗，选一个当父亲一个当母亲，组合双亲染色体形成子代。

我们将每一代将接近太极的图案挑选出来组成新的种群进入下一代的繁殖。我们进行若干代挑选之后，我们就能得到一个比较接近的图片，但是由于这一百个三角形的形状，位置，颜色，是一开始父代确定好的，所以若干代之后他就已经没有办法在进化了。

所以我们就要进行变异，进入新的染色体基因，即更改一个三角形的形状，位置，颜色均可以。然后重复上面的繁殖，选择。若干图案。
就像这样

复现陈斌教授课程算法的时候发现他的算法不是这样的，他的算法中并没有交叉遗传。父代通过变异产生子代，父代变异出几个子代选取子代中最接近太极图案的图片作为新的父代，变异，筛选，进入循环。若干代之后，我们所得到的个体已经很接近这个太极图案了。

整个流程很类似于病毒，一种病毒变异出一种抗药性更高的病毒，新病毒风靡一时。随后人类研制出新的药物杀死病毒。然后总有那么一个病毒活下来，经过变异比以前的病毒更能适应和环境。一代又一代循环，病毒的抗药性越来越高了。

纯变异算法流程

实现代码

from PIL import Image, ImageDraw
import numpy as np
import copy as cp
import random as ra

imageSrc = "src/2.jpg"
imageDec = "dec/"
size = 10  # 种群数量,生存空间
imageList = []  # 种群集合

img2 = Image.open(imageSrc).resize((256, 256)).convert('RGBA')
im2 = [np.array(x) for x in list(img2.split())]

'''
    变异具有两种模式，mod = 0 是删除一个三角形重新绘制，mod = 1 微调三个三角形数值
        
    交叉互换具有三种模式，
    mod = 0: 是随机选取父，母三角形，传给子代。
    mod = 1: 父亲前一半，母亲后一半。
    mod = 2: 父亲提供形状，母亲提供颜色

'''


class TriangleSet:
    def __init__(self, su=100, siz=(256, 256), mod=0):
        self.point = []
        self.color = []
        self.sum = su
        self.size = siz
        self.tu = None
        self.fen = 0
        if mod == 0:
            for i in range(100):
                self.rad()
            self.image()
            self.si()

    def rad(self):  # 随机产生三角形
        re = []
        col = [
            ra.randint(0, 256), ra.randint(0, 256), ra.randint(0, 256), ra.randint(0, 256)]
        for s in range(3):
            rel = [ra.randint(0, self.size[0]), ra.randint(0, self.size[1])]
            re.append(rel)
        self.point.append(re)
        self.color.append(col)

    def image(self):  # 将三角形化成图片
        img = Image.new('RGBA', self.size)
        draw = ImageDraw.Draw(img)
        draw.polygon([(0, 0), (0, 255), (255, 255), (255, 0)], fill=(255, 255, 255, 255))

        for x in range(self.sum):
            img_t = Image.new('RGBA', self.size)
            draw = ImageDraw.Draw(img_t)
            draw.polygon([tuple(y) for y in self.point[x]], fill=tuple([x for x in self.color[x]]))
            img = Image.alpha_composite(img, img_t)
        self.tu = img

    def yi(self, m, pr1=0.08, pr2=0.3, pr3=0.8):

        def isMutate(pr):
            pe = ra.random()
            if pe <= pr:
                return True
            else:
                return False

        for n in range(3):
            if isMutate(pr1):
                self.point[m][n][0] = ra.randint(0, 255)
            if isMutate(pr1):
                self.point[m][n][1] = ra.randint(0, 255)
        if isMutate(pr1):
            self.color[m][0] = ra.randint(0, 255)
        if isMutate(pr1):
            self.color[m][1] = ra.randint(0, 255)
        if isMutate(pr1):
            self.color[m][2] = ra.randint(0, 255)
        for n in range(3):
            if isMutate(pr2):
                self.point[m][n][0] = max(min(self.point[m][n][0] + ra.randint(-15, 15), 255), 0)
            if isMutate(pr2):
                self.point[m][n][1] = max(min(self.point[m][n][1] + ra.randint(-15, 15), 255), 0)

        if isMutate(pr2):
            self.color[m][0] = max(min(self.color[m][0] + ra.randint(-30, 30), 255), 0)
        if isMutate(pr2):
            self.color[m][1] = max(min(self.color[m][1] + ra.randint(-30, 30), 255), 0)
        if isMutate(pr2):
            self.color[m][2] = max(min(self.color[m][2] + ra.randint(-30, 30), 255), 0)
        for n in range(3):
            if isMutate(pr3):
                self.point[m][n][0] = max(min(self.point[m][n][0] + ra.randint(-3, 3), 255), 0)
            if isMutate(pr3):
                self.point[m][n][1] = max(min(self.point[m][n][1] + ra.randint(-3, 3), 255), 0)

        if isMutate(pr3):
            self.color[m][0] = max(min(self.color[m][0] + ra.randint(-10, 10), 255), 0)
        if isMutate(pr3):
            self.color[m][1] = max(min(self.color[m][1] + ra.randint(-10, 10), 255), 0)
        if isMutate(pr3):
            self.color[m][2] = max(min(self.color[m][2] + ra.randint(-10, 10), 255), 0)
        if isMutate(pr2):
            self.color[m][3] = ra.randint(95, 115)

    def mutate_2(self):
        n = np.random.randint(0, 100)
        self.yi(n)

    def mutate(self, pr=0.01, mod=0):
        # 计算变异概率
        def isMutate():
            pe = ra.random()
            if pe <= pr:
                return True
            else:
                return False

        if mod == 0:
            flag = False
            for tri in range(100):
                if isMutate():
                    flag = True
                    self.yi(tri)
                    continue
            if not flag:
                n = np.random.randint(0, 100)
                self.yi(n)

        else:
            pass

    def si(self):  # 比较图片相似
        match_rate = 0
        img1 = self.tu.resize((256, 256)).convert('RGBA')
        im = []
        for x in list(img1.split()):
            im.append(np.array(x))
        for i in range(3):  # 对RGB通道三个矩阵分别与目标图片相应通道作差取平方加和评估相似度
            match_rate += np.sum(np.abs(im[i] - im2[i]))
        self.fen = match_rate

    def save(self, name):  # 保存图片
        img_name = str(name) + '.png'
        self.tu.save(imageDec + img_name)

    def breed(self, mod=0, g=None):  # 繁殖, 交叉互换

        def fuOrMu():
            if ra.randint(100) > 50:
                return True
            else:
                return False

        if mod == 0:
            zi1 = TriangleSet()
            zi2 = TriangleSet()
            assert isinstance(g, TriangleSet)
            for i in range(100):
                if fuOrMu():
                    zi1.point.append(self.point[i])
                    zi1.color.append(self.color[i])
                    zi2.point.append(g.point[i])
                    zi2.color.append(g.color[i])
                else:
                    zi1.point.append(g.point[i])
                    zi1.color.append(g.color[i])
                    zi2.point.append(self.point[i])
                    zi2.color.append(self.color[i])
            zi2.image()
            zi2.si()
            zi1.image()
            zi1.si()
            return zi1, zi2
        else:
            zi = TriangleSet()
            zi.point = cp.deepcopy(g.point)
            zi.color = cp.deepcopy(g.color)
            zi.image()
            zi.si()
            return zi


def x_ze(s):  # 自然选择
    global imageList
    if len(imageList) > s:
        lis1 = imageList[:s]
        lis2 = imageList[s:]

        for m in lis2:
            for n in lis1:
                if m.fen < n.fen:
                    lis1.remove(n)
                    lis2.append(n)
                    lis1.append(m)
                    break
        imageList = lis1


'''
    无组合算法，单纯依靠变异寻找最优解
'''


def by():
    bo = True
    c = 0
    for i in range(20):
        imageList.append(TriangleSet())
    while bo:
        x_ze(1)
        print(str(c) + ':' + str(imageList[0].fen))

        if c % 300000 == 0:
            imageList[0].save(c)

        for i in range(size):
            zi = cp.deepcopy(imageList[0])
            zi.mutate()
            zi.image()
            zi.si()
            imageList.append(zi)
        c += 1


if __name__ == '__main__':
    by()

最后思考，我们从另一种角度思考这个算法。整个算法我们是如何接近最优解的呢。我们是通过变异产生一个优于父代的子代，然后子代是新的父代。以此不断地迭代下去，从而产生最优的解。
我们可以用下面这个图来描述。

图中我们现在在1这个点，我们闭着眼睛要走到最优解那个点。我们只能通过鼻子去判断我们所在的位置距离最优解的距离是远还是近。

我们随机选取一个点，比如说2号点，我们一判断，我们里最优解近了，那么我们就走到二号点，接着想办法靠近最优解。如果说我们经过判断离最优解远了。比如说4号点，那我们这个时候就在回到1号点，接着寻找新的点。

其实这种只靠变异没有遗传的进化算法就类似于这个过程，每一次变异都相当于寻找一个新的点，然后判断是不是比父代接近。如果接近，子代替代父代（相当于我们走到2号）。否则，抛弃这个子代，寻找新的子代（就像4号）。

那么我们也就能解释为什么算法到后期接近最优解的速度就下降了甚至于进化停滞。我们发现图中有利于接近最优解的点仅限于蓝色方框中的点，随着1号较接近最优解，蓝色方框的面积逐渐变小，所以随机产生一个点落在蓝色方框的概率变得越来越低（即不利变异越来越多）。所以越接近最优解我们越是难以接近。