启发式寻解
附件
【码】遗传算法求解函数最小值.py
作者 : 老饼 日期 : 2022-09-14 19:25:33 更新 : 2022-09-14 19:25:42

遗传算法求解函数最小值(python) : 

# -*- coding: utf-8 -*-
"""
遗传算法求解 (x1-2)^2+(x2-3)^2的最小值
"""
import numpy as np
import matplotlib.pyplot as plt
import time
global int_num 
global dec_num
int_num = 12
dec_num = 8
#------------目标函数值计算方法------------------------------------------
def calF(x): 
    return (x[0]-2)**2+(x[1]-3)**2

#------------将二进制转为数值--------------
def bin2dec(b):
    [r,c] = b.shape
    d = np.zeros(r) 
    for i in range(r):
        int_idx = int_num
        for j in range(c):
           d[i] += 2**int_idx if b[i,j]==1 else 0
           int_idx += -1
    return d

#------------获取种群中目标函数值最好的一个-------------------------------
def getBest(xg):
     F_list = np.array([calF(bin2dec(cur_x))  for cur_x in xg ])
     best_index =np.argmin(F_list)
     x = xg[best_index].copy()
     F = F_list[best_index]
     return x,F
 
#------------计算种群进入下一代的概率轮盘-------------------------------
def getPPan(xg):
    F_list = np.array([calF(bin2dec(cur_x))  for cur_x in xg ])
    F_list = F_list - F_list.min()
    acp_list = 1/(1+F_list)
    PPan = (acp_list/acp_list.sum()).cumsum()
    return PPan


#------------染色体交换-------------------------------    
def exPart(xg):
     m = len(xg)
     [vn,n] = xg[0].shape
     ex_list = np.random.choice(np.arange(m), size=m, replace=False)
     for i in range(0,m,2):
         a = xg[ex_list[i]]
         b= xg[ex_list[i+1]]
         for j in range(vn):
             ex_part = np.random.choice(np.arange(n), size=int(n/3), replace=False)
             a_piece = a[j,ex_part].copy()
             b_piece = b[j,ex_part].copy()
             a[j,ex_part]=b_piece
             b[j,ex_part]=a_piece
         
#------------基因变异-------------------------------
def genVar(xg,var_rate):
    m = len(xg)
    [vn,n] = xg[0].shape
    for i in range(m):
        a=xg[i]
        if(np.random.rand()<var_rate):
            for j in range(vn):
                ex_part = np.random.choice(np.arange(n), size=1, replace=False)
                a[j,ex_part]=1- a[j,ex_part]
               
#------------生成下代种群-------------------------------
def genChildGroup(xg,PPan,best_x):
    m = len(xg)
    child_xg=list()
    child_xg.append(best_x.copy())
    for i in range(1,m):
        select_idx = (np.argwhere(PPan>np.random.rand())).min()
        child_xg.append(xg[select_idx].copy())
    return child_xg

#----------------迭代主流程-------------------------------------------
#----------------参数初始化-----------------------
m = 30    #种群规模
t = 1000  #迭代次数
var_rate = 0.4   #变异概率


#--------------初始化种群-------------------------
xg=list()
for i in range(m):       
    xg.append( np.random.rand(2,int_num+dec_num).round().astype(int))


h_best_x = xg[0]           # 初始化历史最优个体
h_best_F = calF(bin2dec(h_best_x))  # 初始化历史最优个体的目标函数值


F_list=np.array([])               # 每代最优函数值记录列表
for i in range(t):
    xg_back =xg.copy()
    exPart(xg)                    # 交换染色体
    genVar(xg,var_rate)           # 基因变异
    best_x,best_F =  getBest(xg)  # 获取本代最佳个体
    
    if(best_F <h_best_F):          # 更新历史最优个体
        h_best_F= best_F
        h_best_x = best_x


    print("第"+str(i)+"代:最优F="+str(best_F))
    
    F_list = np.append(F_list,best_F)    # 记录历代最优个体
    
    # 退出条件:近10代最优个体变化不大,则退出
    last_F = F_list[max(0,F_list.shape[0]-50):]   
    if((i>50) & ((last_F.max()-last_F.min())/max(abs(last_F.mean()),1)<0.001)):
        break
    
    #-------------赌轮盘生成下一代-----------------------------------------
    PPan = getPPan(xg)
    xg = genChildGroup(xg,PPan,h_best_x)
    
# 打印最终结果(历史最优)
print("h_best_F=",h_best_F)
print("h_best_x=",bin2dec(h_best_x))


联系老饼