유전 알고리즘을 사용하여 함수의 최대치를 계산한다(진화 계산 준비편)

18726 단어 Python3 진화 계산 유전 알고리즘

대개

교수: "진화 계산의 기본 알고리즘은 바로 이런 느낌입니다."
나: 아, 대단하다
교수: "오늘의 수업 내용만 보면 진화 계산을 할 수 있어요."
나: "응..."
해봤어요.

개요

구한 함수
f(x)=-cos(x)*cos(x/20)(-2.5≤x≤25.5)(0.1각도)
개인
원소수 9의 배열
0번: 플러스 마이너스 결정(0: 플러스, 1: 마이너스)
1~8번: 8위를 구성하는 이진수(i위:2^(8-i)의 배수)
따라서 개체가 가지고 있는 값의 범위는 255~255이다
유전 알고리즘의 주기는 다음과 같다(수업의 수리)
0→1→2→3→4→1→2→…
초기 그룹
해답을 정하기가 쉽지 않기 때문에 해답으로 삼은 개체를 랜덤수로 설정한다
개체 랜덤수의 요소: 0 또는 1
1. 적응도 계산
함수의 최대 값을 구하기 위해, 적응도를 f(x)의 값으로 설정합니다
t: 개체의 값으로서 적응도는 다음과 같다.
f(x/10)
2. 부모의 선택
이번에는 엘리트 보존 전략(적응도가 높은 순서에 따라 개체를 선택)으로 개체군 중 2명의 부모를 뽑았다.
3. 교차
이번에는 같은 교차로 아이의 개체를 만들었다.
고르게 교차하다
개체와 모양이 같은 마스크를 준비한다.
각 번호의 마스크 요소의 값에 따라 그에 상응하는 번호를 유전한다.

마스크의 요소 0: 부1→자1, 부2→자2

마스크의 요소1: 부1→자2, 부2→자1

4. 돌연변이
5%의 확률로 교차 후 서브진열의 무작위 선택 문패 요소를 수정했다.(0→1、1→0)
(확률 기준은 표준 편차 2σ≈95% 그래서 이렇게 싼 이유의 원래 설정)

컨디션

python 3.5.1
numpy 1.15.2

실천하다

소스 코드는 다음과 같습니다(길기 때문에 GiitHub에 배치됩니다.)
sample1.py

import numpy as np
import math
import random
import matplotlib.pyplot as plt

GENE_NUM = 10  #個体数

def f(x):
    return -np.cos(x)*np.cos(x/20)

def init(genes):
    for i in range(GENE_NUM):
        for j in range(9):
            genes[i][j] = random.randint(0,1)

#初期集団の形成
def x(gene):
    result=0
    for i in range(8):
        result += pow(2, i)*gene[8-i]
    if(gene[0]==1):
        result = result*-1
    return float(result/10)

#交叉・突然変異
def evolve(gene1, gene2, mnum):
    result = np.zeros((2,9))

    #　交叉
    for i in range(9):
        r=random.randint(0,1)
        if(r==1):
            result[0][i]=gene2[i]
            result[1][i]=gene1[i]
        else:
            result[0][i]=gene1[i]
            result[1][i]=gene2[i]

    #突然変異
    r = random.random()
    if(r<0.05):
        rnum = random.randint(0,8)
        if(result[0][rnum]==0):
            result[0][rnum]=1
        else:
            result[0][rnum]=0
    if(0.95<r):
        rnum = random.randint(0,8)
        if(result[0][rnum]==0):
            result[1][rnum]=1
        else:
            result[1][rnum]=0

    return result

def main():
    genes = np.zeros((GENE_NUM,9))
    genenum = 0

    init(genes)

    #進化サイクル
    while(genenum<20):

        #出力
        print(genenum)
        print(genes)

        plt.figure()
        rx = np.arange(-25.5, 25.5, 0.01)
        ry = f(rx)
        plt.plot(rx,ry)
        for i in range(GENE_NUM):
            rx = x(genes[i])
            ry = f(rx)
            plt.scatter(rx,ry)
        plt.savefig("./result/"+str(genenum)+".png")


        firstrate=-100
        secondrate=-100
        first=-1
        second=-1

        #選択
        for i in range(GENE_NUM):
            rate=f(x(genes[i]))
            if(rate>firstrate):
                secondrate=firstrate
                second=first
                firstrate=rate
                first=i
            elif(rate>secondrate):
                secondrate=rate
                second=i

        tmp1=genes[first]
        tmp2=genes[second]
        genes[GENE_NUM-1]=tmp1
        genes[GENE_NUM-2]=tmp2
        for i in range(int(GENE_NUM/2)-1):
            result=evolve(genes[GENE_NUM-1], genes[GENE_NUM-2],i)
            genes[i*2]=result[0]
            genes[i*2+1]=result[1]

        genenum+=1

if __name__ == '__main__':
    main()