人工智能 遺傳演算法 計算函式極值問題
系列文章
- 人工智能 倒啤酒問題 python解法
- 人工智能 水壺問題 python解法
- A*演算法之八數碼問題 python解法
- A*演算法之野人傳教士問題 python解法
- 人工智能 遺傳演算法 計算函式極值問題
文章目錄
- 人工智能 遺傳演算法 計算函式極值問題
- 問題描述
- 遺傳演算法介紹
- 1.構造初始狀態
- 2.構造算子
- 3.編碼
- 4 啟發式函式
- 5.遺傳演算法與函式極值問題解決
- 初始化種群
- 解碼
- 算子
- 評估函式
- 函式框架
- 遺傳演算法編程
學習了遺傳演算法之后,感覺掌握的不是很透徹,所以打算寫篇文章先記錄一下
間隔了好久,發現遺傳演算法(這篇文章)忘記發了,就加上了代碼今天發了出來
問題描述
使用遺傳演算法求解三元函式z的最大值
z
=
f
(
x
,
y
)
=
1
?
x
?
s
i
n
(
4
π
x
)
?
1
?
y
?
s
i
n
(
4
π
y
+
π
)
+
1
z=f(x,y)=1*x*sin(4πx)-1*y*sin(4πy+π)+1
z=f(x,y)=1?x?sin(4πx)?1?y?sin(4πy+π)+1
其中 x,y的定義域都為 (-1 , 1 )
實驗要求：
- 編碼、初始群體的產生、適應度計算、選擇運算、交叉運算、變異運算說明
- x,y定義域值編碼采用二進制編碼，各自用15位編碼，
遺傳演算法介紹
主要來介紹一下遺傳演算法的大題思路
在網上查了一對資料之后,可算是稍微知道了一些遺傳演算法的特性
這里我就稍微總結一下大致的流程,官方的決議還是去百度搜搜大佬們的回答比較好
【演算法】超詳細的遺傳演算法Genetic
之前幾篇文章的搜索演算法都有著一個特性,遺傳演算法也不例外,他們的總體流程我認為都是一樣的
1.構造初始狀態
在一些搜索演算法中體現為創建open表,而遺傳演算法當中成為構造初始種群
雖然叫法不同,但是都是對于整個演算法的初始化,可以理解為把我們需要考慮的節點全部放到一個串列當中
2.構造算子
這一步其實應該算是準備作業,不過站在編程的角度,我就把它放在第二點了
在之前的搜索演算法中,如八數碼問題, 我們的算子就是空格的上下左右移動四種
而在倒啤酒問題當中,算子就是A瓶子倒空,倒滿,倒入B瓶子等等
在遺傳演算法里面,算子就結合了遺傳學(學過高中生物的應該都知道)
1. 復制 (將DNA一模一樣復制一份)
2.交叉互換 (將DNA上的基因交叉互換,這部分可以百度搜索)
3.變異 (DNA上的部分基因突變成新的基因)
上面的例子是針對生物學來說的,那么遺傳演算法里哪來的DNA呢,這就需要講到我認為遺傳演算法里面不同于其他演算法的第一點: 編碼
對于單純的數字 比如 1,2,3,4,5 我們很難想到一個好的方法對它們來實作交叉互換或者變異的操作
而對于二進制編碼,就方便多了
比如我們現在有一串二進制數字
00111100與10110010
我們可以從中間將它們劃分,把每四位都看成一個基因0011 1100 ,1011 0010
- 那么基因交換就可以表示為第一個數的左邊四位與第二個數的右邊四位交換(也可以是右邊四邊,這個隨機產生)
- 而基因突變也可以表示為其中的一個二進制從0變成1或者從1變成0
那么如何把(-1,1)這個定義域轉換成二進制編碼呢
3.編碼
為了更好的實作三種算子的操作,引入了編碼的概念,在本次實驗中,我們使用的是二進制編碼
本題x,y的范圍是(-1,1) 而編碼就是將(-1,1)區間內的數字用二進制來表示
那么問題來了,(-1,1)如何使用二進制來表示
從最簡單的例子來說,2位的二進制可以表示
2
2
2^2
22個數字,如果我們用2位編碼來表示(-1,1)之間的數字,那么我們可能只能表示
?
1
,
?
1
3
,
?
1
3
,
1
-1,-\frac{1}{3},-\frac{1}{3},1
?1,?31?,?31?,1
計算方法如下
d
=
?
(
1
?
(
?
1
)
)
2
2
?
1
d= -\frac{(1-(-1))}{2^2-1}
d=?22?1(1?(?1))?
a
1
=
?
1
a_1 = -1
a1?=?1
a
2
=
?
1
+
d
a_2 = -1 + d
a2?=?1+d
a
3
=
?
1
+
2
d
a_3 = -1 + 2d
a3?=?1+2d
a
4
=
?
1
+
3
d
a_4 = -1 + 3d
a4?=?1+3d
這樣四個數,顯然是不夠的,所以我們需要2進制的個數越來越多,才可以把區間表示的更加精確
我們發現題目中給出了一個限制 x,y定義域值編碼采用二進制編碼，各自用15位編碼,所以本題我們可以使用15位二進制來對(-1,1)之間的數字來編碼,也就是分為32767個區間(32768個點)
2
15
=
32768
2^{15}=32768
215=32768
那么如何編碼和解碼就很清晰了
4 啟發式函式
在搜索演算法中,啟發式函式啟動了非常重要的作用,大大提升了效率,在A*演算法中,每次算子操作結束后,我們都會將合適的節點插入open表,然后用啟發式函式的值對open表進行排序,在下一輪的迭代中可以從最優的節點開始
在遺傳演算法中使用輪盤選擇法,稍有不同,但是本質的原理也是一樣的
遺傳演算法中的啟發式函式是為了讓優秀的基因保留下來的概率變大,在這里采用了輪盤選擇法
通俗的解釋就是:在初始化種群之后,使用啟發式函式計算每個基因的優秀程度,然后為他們分配一個保留下來的概率
比如有 a,b,c,d四個基因,通過啟發式函式(這里假設越大越好),計算出來的值是1,2,3,4
那么他們的概率就是
1
1
+
2
+
3
+
4
\frac{1}{1+2+3+4}
1+2+3+41?,
2
1
+
2
+
3
+
4
\frac{2}{1+2+3+4}
1+2+3+42?,
3
1
+
2
+
3
+
4
\frac{3}{1+2+3+4}
1+2+3+43?,
4
1
+
2
+
3
+
4
\frac{4}{1+2+3+4}
1+2+3+44?
這很好理解吧,相當于每個基因都有留下來的概率
5.遺傳演算法與函式極值問題解決
再簡單的講述一下題目:
z
=
f
(
x
,
y
)
=
1
?
x
?
s
i
n
(
4
π
x
)
?
1
?
y
?
s
i
n
(
4
π
y
+
π
)
+
1
z=f(x,y)=1*x*sin(4πx)-1*y*sin(4πy+π)+1
z=f(x,y)=1?x?sin(4πx)?1?y?sin(4πy+π)+1
當
x
∈
(
?
1
,
1
)
,
y
∈
(
?
1
,
1
)
x∈(-1,1),y∈(-1,1)
x∈(?1,1),y∈(?1,1)時,求一組x, y的取值 使得z最大
乍一看不就是個數學題,求兩個偏導等于0不就完事了
不過我們要用編程來實作,還得用遺傳演算法,就很頭禿了
一步步來唄,再看一眼流程圖
初始化種群
撰寫一個函式來初始化種群
def init_population():
pass
解碼
這里我們需要撰寫一個函式,能把二進制的數字轉換回(-1,1)的區間內
# 解碼
def To_decode(num):
# num是二進制數 需要回傳一個區間內的小數
pass
算子
撰寫一個函式包含三種算子的操作
def gene_operation():
pass
評估函式
撰寫一個函式來評估種群中個體的價值
def estimate():
pass
函式框架
b = 預計回圈的輪數
for i in range(n):
tribe= init_population() # 初始化種群(部落)
tribe_value= estimate(tribe) # 每個個體的價值(概率)
for action in actions: # 三種算子的操作
tribe = gene_operation(tribe,tribe_value,type=action)
# 回圈結束,得到最終優秀的tribe
# 找到里面 value最大的情況即可
已經有文章解決了這個問題
遺傳演算法求函式最值python解法
遺傳演算法編程
代碼的思路都寫在每個函式的注釋里了
# -*- coding: utf-8 -*-
# @Time : 2020/11/28 9:16
# @Author : Tong Tianyu
# @File : 遺傳演算法_函式極大值問題.py
import random
from math import fabs, sin, pi
import numpy as np
import prettytable as pt
'''''題目要求'''
# z=f(x,y)=1*x*sin(4πx)-1*y*sin(4πy+π)+1
# 在-1<x<1和-1<y<1上的最大值
# 實驗要求：
# 編碼、初始群體的產生、適應度計算、選擇運算、交叉運算、變異運算
# 說明，x,y定義域值編碼采用二進制編碼，各自用15位編碼，
'''''定義全域變數'''
max_loop = 200 # 最大迭代次數 100~500
tribe_number = 50 # 種群初始化數量 20~100
limit_left = -1 # 定義域左界限
limit_right = 1 # 定義域右界限
limit_bit = 15 # 編碼位數
cross_probability = 0.7 # 交叉概率 0.4~0.99
variation_probability = 0.01 # 變異概率 0.0001~0.1
copy_probability = 1 - cross_probability - variation_probability # 復制概率
actions_probability = np.array([copy_probability, cross_probability, variation_probability])
# 進制轉換
def To_decode(num):
'''''
num是二進制數 用串列表示 長度為30
:param num:
:return: 回傳x,y對應的(-1,1)區間小數
'''
# 分割陣列
x = num[:15]
y = num[15:]
# 轉為10進制整數
x = int(str(x), 2)
y = int(str(y), 2)
# 轉換為-1,1區間的小數
d = fabs(limit_left - limit_right) / (2 ** limit_bit - 1)
x = limit_left + d * x
y = limit_left + d * y
return x, y
# 初始化一個個體
def init_one(bit=30):
'''''
回傳一個 bit位數的二進制串
:param bit: 位數
:return:
'''
s = ''
for i in range(bit):
s += str(random.randint(0, 1))
return s
# 初始化一個種群
def init_tribe(tribe_number):
'''''
初始化一個種群
:param tribe_number: 種群個數
:return:
'''
tribe = []
while len(set(tribe)) != tribe_number:
tribe.append(init_one())
return tribe
# 回傳被選擇的種群
def roulette_select_tribe(value, tribe):
'''''
輪盤選擇: 根據概率選擇出個體, 回傳選擇后的種群
這里優化了一個操作,就是始侄訓將 啟發值最大的節點加入選擇后的種群
:param value: 傳入引數: 代表每個個體被選擇的概率
:param tribe: 傳入引數: 代表種群的資訊
:return:
'''
new_tribe = []
# 設定亂數種子
np.random.seed(random.randint(1, 100) + random.randint(100, 10000000))
index_list = [i for i in range(tribe_number)]
for i in range(tribe_number):
# 根據概率獲取索引
index = np.random.choice(index_list, p=value.ravel())
new_tribe.append(tribe[index])
# 判斷啟發值最大的節點是否被加入
li = list(value)
max_index = li.index(max(li))
if tribe[max_index] not in new_tribe:
tmp_value = list(estimate(new_tribe))
min_index = tmp_value.index(min(tmp_value))
new_tribe[min_index] = tribe[max_index]
return new_tribe
# 回傳被選擇的個體索引(下標)
def roulette_select_human(value, tribe):
'''''
輪盤選擇: 根據概率選擇出個體, 回傳一個被選擇的物件與其索引
:param value: 傳入引數: 代表每個個體被選擇的概率
:param tribe: 傳入引數: 代表種群的資訊
:return:
'''
np.random.seed(random.randint(1, 100) + random.randint(100, 10000000))
index_list = [i for i in range(tribe_number)]
index = np.random.choice(index_list, p=value.ravel())
return tribe[index], index
# 評估每個個體被選擇的概率
def estimate(tribe):
'''''
回傳一個 numpy.array型別的 概率陣列,代表了tribe中每一個個體被選中的概率
:param tribe:
:return:
'''
start_value = []
for human in tribe:
x, y = To_decode(human)
human_value = 1 * x * sin(4 * pi * x) - 1 * y * sin(4 * pi * y + pi) + 1
start_value.append(human_value if human_value > 0 else 0)
# 將串列中的每個value轉換為相應的概率
result_value = [i / sum(start_value) for i in start_value]
return np.array(result_value)
def cal_func(human):
'''''
計算單個個體的啟發值 (也就是函式的值)
:param human:
:return:
'''
x, y = To_decode(human)
human_value = 1 * x * sin(4 * pi * x) - y * sin(4 * pi * y + pi) + 1
return human_value
def gene_operation(tribe, type):
'''''
進行復制,交叉,變異的操作
:param tribe:
:param type:
:return:
'''
if type == '復制':
return tribe
if type == '交叉':
# 初始化需要的引數
value = estimate(tribe)
cross_tmp = []
# 隨機選擇父母節點
father, father_index = roulette_select_human(value, tribe)
mother, mother_index = roulette_select_human(value, tribe)
# 隨機確定 交叉點
cross_location = random.randint(0, 29)
cross_tmp.append(cross_location)
# 執行交叉操作
infant = father[0:cross_location] + mother[cross_location:]
# 計算其評估值是否變優秀,沒有變優秀就重來
score = cal_func(infant) - cal_func(father)
while score < 0:
if len(cross_tmp) == 30:
return tribe
cross_location = random.randint(0, 29)
if cross_location in cross_tmp:
continue
cross_tmp.append(cross_location)
infant = father[0:cross_location] + mother[cross_location:]
score = cal_func(infant) - cal_func(father)
# 修改tribe (將交叉后的結果與原先的節點替換/不變)
tribe[father_index] = infant
return tribe
if type == '突變':
# 初始化需要的引數
value = estimate(tribe)
# 隨機選擇變異節點
variation_human, variation_human_index = roulette_select_human(value, tribe)
tmp_human = variation_human
# 隨機選擇變異位置
variation_location = random.randint(0, 29)
# 取反
num = 1 - int(variation_human[variation_location])
tmp = list(variation_human)
tmp[variation_location] = str(num)
variation_human = ''.join(tmp)
# 判斷是否有效
if cal_func(variation_human) < cal_func(tmp_human):
tribe[variation_human_index] = variation_human
return tribe
def gene_func():
actions = ['復制', '交叉', '突變']
tribe = init_tribe(tribe_number) # 初始化種群(部落)
for i in range(max_loop):
print(f'------------------第{i + 1}輪-----------------')
tribe_value = estimate(tribe) # 啟發式函式計算每個個體的價值(概率)
tribe = roulette_select_tribe(tribe_value, tribe) # 輪盤選擇后的種群
for human in tribe:
# 設定亂數種子
np.random.seed(random.randint(1, 100) + random.randint(100, 10000000))
# 獲取該節點將進行的操作(復制,交叉,變異)
index = np.random.choice([0, 1, 2], p=actions_probability.ravel())
type = actions[index]
# 進行個體基因操作
tribe = gene_operation(tribe, type=type)
# 輸出一下該輪結束后的最大值是什么
result_value = list(estimate(tribe))
result_index = result_value.index(max(result_value))
print('max_Z= ', cal_func(tribe[result_index]))
# 回圈結束,得到最終優秀的tribe
# 找到里面 value最大的情況即可
print('回圈結束')
tb = pt.PrettyTable()
tb.field_names = ['函式極大值', 'x編碼', 'y編碼', 'x真值', 'y真值']
result_value = list(estimate(tribe))
result_index = result_value.index(max(result_value))
max_result = cal_func(tribe[result_index])
x, y = To_decode(tribe[result_index])
tb.add_row([max_result, tribe[result_index][:15], tribe[result_index][15:], x, y])
print(tb)
if __name__ == '__main__':
gene_func()
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/247750.html
標籤：python
下一篇：C語言撰寫