本篇內容涉及遺傳算法的概念，原理描述，實現方法以及在量化投資的應用。
陳煥生，凡普金科旗下會牛科技研發總監兼數據架構師，目前從事基於遺傳算法因子自動化挖掘，量化投資研究。並於2017年上線了基於遺傳算法因子挖掘的自有資金運營的量化模型。目前處於行業中遊水平，團隊的大多背景都是非金融投資領域，實現網際網路技術向量化投資領域的轉型，本人十年的網際網路研發背景，多次連續創業的經歷。
1.介紹遺傳算法的概念
遺傳算法是一種進化策略的算法，模擬生物基因遺傳。遵循物競天擇，適者生存，劣者淘汰的自然規律進化。
達爾文有一句話這麼說的：
能夠生存下來的往往不是最強大的物種，也不是最聰明的物種，而是最能適應環境的物種 。
簡單的說，隨著時間的流逝，一代代的繁殖，不管外部的環境如何惡劣，都會通過遺傳和變異生存下來，以致適應環境。不適應環境的生物將會被淘汰。
人類的進化概要圖如下：
2.遺傳算法的原理
遺傳算法的基本原理就是模擬上述的繁殖遺傳的過程。
提煉出遺傳算法的基礎組件如下：
種群(Population)
生物進化是以群體的形式進行的，人類就是一個種群，種群還可以分為子種群，每個子種群分別進化
個體(Individual)
組成種群的獨立單個物種
染色體(Chromosome)
包含一組基因，個體由多個染色體組成
基因(Gene)
可用於遺傳的因子，並且攜帶特有的適應能力的信息
交叉(Crossover)
個體之間交換染色體，交叉繁殖遺傳基因，形成新的個體
複製(reproduction)
複製優秀的個體，遺傳基因
變異(Mutation)
根據一定概率基金突變，增強基因的多樣性
進化(Evaluation)
根據優勝劣汰原則，進化優秀個體，淘汰劣類個體
遺傳算法實現的步驟大體分為基因編碼解碼，種群初始化，選擇算子，交叉算子，變異算子，適應度函數(評價函數或者目標函數)。每個步驟的優化都會影響到遺傳算法整體的優化結果。
1.基因編碼
二進位編碼
二進位編碼顧名思義由二進位來編碼，由0和1組成的基因編碼成染色體
適用場景：解決背包問題
詳解：背包問題一般給定某些東西固定的大小和價值，背包的容量是有限的，優化最大背包價值類似的問題
實數編碼
實數編碼是在給定的連續或者離散的區間內，將實數組合成有序的序列的一種編碼
適用場景：解決排序的優化問題，例如TSP問題，任務排序，任務調度等問題
詳解：這類問題對於順序敏感，TSP問題就是路徑規劃的優化
字符編碼
實數編碼其實可以認為是字符編碼的一種，實數編碼的基因都是實數組成的，而字符編碼可以由字母，單詞，數字等組成，字符編碼也可以將字符通過定義固定字典表的方式，轉換成實數編碼。
適用場景：優化神經網絡的參數，權重等
詳解：在設計好的神經網絡的模型中，使用遺傳算法優化權重，得到最佳的輸出
符號編碼
一般符號編碼都使用樹來存儲，所以符號編碼也可以稱為樹編碼，是一種複雜的編碼方式。量化投資的因子挖掘編碼就是採取這種方式。
適用場景：給定特徵，找出一個函數，以達到目標優化的方式
詳解：這種方式，每一個特徵可以作為一個變量成為基因，每一個表達式就是一個染色體，對於這個染色體的交叉和變異其實就是樹節點的交換和變異。
2.選擇算子
輪盤賭選擇算法(Roulette Wheel Selection)
每個個體進入下一代的概率和它的適應度值成正比，它的進化概率是個體的適應度佔總的適應值的比例。
具體算法如下：
1.計算每個個體的適應度值。
2.計算種群所有個體的進化到下一代的概率。
3.計算個體的積累概率。
4.在[0, 1]區間生成一個隨機數r 。
5.重複(4)共N次。這樣就選出來了一個新的種群。
舉例如下：
如同輪盤旋轉一樣，面積越大，落上去的概率越大
優點：選擇的概率與它的適應值成正比
缺點：適應度如果差別太大，如果最好的染色體適應值佔比90%，那其他的染色體的進化機會將很小，這樣不利於種群進化的多樣性了。
排名選擇算法
這種選擇算法就會避免上述適應度差別很大的問題。
精英選擇算法
將種群中最好的適應度的個體直接進化到下一代，避免優秀的個體在交叉和變異的時候，丟失良好的基因。
其他選擇算法
還有其他的擴展的選擇算法，例如隨機競爭選擇、期望值選擇，排擠策略等。
3.交叉算子
單點交叉
指在個體編碼基因串中只隨機設置一個交叉點，然後再該點相互交換兩個配對個體的部分基因
兩點交叉
指在個體編碼基因串中隨機設置兩個交叉點，然後再該點相互交換兩個配對個體的部分基因
一致交叉
兩個配對的個體在每個基因點上以相同概率交叉
算術交叉
通過算術表達式計算得到新的基因，例如and，or，xor等
符號編碼的交叉
4.變異算子
基本位變異：對個體基因編碼中以變異概率、隨機指定的某一位或某幾位做變異。
均勻變異：分別用符合某一範圍內均勻分布的隨機數，較小的概率來替換所有基金的基因值。（特別適用於在算法的初級運行階段）
邊界變異：隨機的取基因兩個對應邊界基因值之一去替代原有基因值。特別適用於最優點位於或接近於可行解的邊界時的一類問題。
非均勻變異：對原有的基因值做一隨機擾動，以擾動後的結果作為變異後的新基因值。對每個基因座都以相同的概率進行變異運算之後，相當於整個解向量在解空間中作了一次輕微的變動。
高斯近似變異：進行變異操作時用符號均值為Ｐ的平均值，方差為Ｐ２的正態分布的一個隨機數來替換原有的基因值。
以上最常用的是基本位變異，其他的變異算法需要讀者自己深入研究。
二進位變異
將基因進行變異即可
實數變異
將實數進行變異即可
符號變異
將樹上的節點變異，不過操作符只能變異成操作符，變量只能變異成變量
注意：不管是交叉還是變異，都存在一定概率進行， 交叉和變異概率均是超參，不能太小，也不能他大，太大會不容易收斂到最優解，太小將容易導致種群多樣性差，容易收斂。
5.適應度函數
適應度函數也稱為評價函數，適應度函數和目標函數是兩個概念，適應度函數是根據目標函數區分群體中個體的好壞的標準，適應度函數總是非負，而目標函數可能為正也可能為負。所以一般需要在兩者之間進行轉換。適應度函數可以理解為綜合目標的一個最終評分。
適應度函數設計的要求：
簡單分值
非負
越大越好
計算簡單
目標函數轉換適應度函數方法：
直接轉換
線性轉換
多個優化目標按照權重分配轉換成適應度值
指數轉換
遺傳算法複製指數
在投資中，指數基金就是通過複製標的是指數的基金，一般分為完全複製，部分複製，抽象複製。例如滬深300指數，我們用滬深300的少數的成分股來複製滬深300指數。
模型分析：
選多少只股票（成本問題）
選擇哪些成分股（跟蹤誤差問題）
股票權重分配（跟蹤誤差問題）
模型限制條件問題如下：
成分股的數量固定，等於M
成分股的持股比例有大小限制，min < x < max
目標函數定義：
1.跟蹤誤差 - 與指數偏離的程度
是t時間內，組合的收益率，是t時間內，指數的收益率。其中w是超參，兩個目標的權重。
具體實現步驟參數如下：
注意：在投資領域不是收益越高越好，而是要求收益高的同時，波動要小。一般用夏普值來衡量，在實際過程中，考慮的因素更多，比如交易手續費，停牌，st類的股票等等。遺傳算法做因子挖掘
在量化投資領域，多因子模型是量化投資的重要並且傳統一個模型，因子是模型的原料，量化模型就是把不同類的因子按照一定方式組合在一起，去選股，並且預測收益。因子也可以稱之為特徵。在模型中你可以放入多種多樣的因子，比如：動量因子，市值類因子，基本面因子，反轉類因子，趨勢類因子，波動因子等等。這些因子的數據來源於行情數據，高頻數據，基本面數據，新聞數據，研報數據，宏觀量化類，行業分析類等等。
簡單因子：((close - open) / ((high - low) + .001))
複雜因子：((rank(ts_correlation(ts_sum(((high + low) / 2), 19), ts_sum(adv60, 19), 8)) < rank(ts_correlation(low, volume, 6))) * -1)
模型分析:
因子挖掘考慮因子的可交易性，目標函數最優，換手率低，泛華能力強且穩定。
選哪些股票參與訓練
選定in-sample的訓練時間，out-sample的樣本時間
選定股票權重
選定股票收益計算周期
選定股票交易價格類型(open，close，vwap)
選定因子極值處理
基因和染色體選擇:
Terminal Set: open、close、high、low、returns、volume、隨機數
Function Set: rank(橫截面的排序)、ts_rank(時間序列排序)、correlation(橫截面相關性)、ts_correlation(時間序列相關性)、decay(時間序列衰減)、decay_linear(線性衰減)、ts_mean(簡單平均)、ema(加權平均)、?:(if else三元表達式) ，min，max，ts_min，ts_max
模型限制約束條件:
因子有效數據佔比(>60%)
因子值數據分布
因子ICIR或者Sharp最低值
因子目標值的t-value值
目標函數定義:
ICIR：
這兩種IC值計算主要看因子值分布特點，如果因子值分布方差很小，值都很接近，那麼第一種計算方式就不怎麼顯著，第二種才是比較好的方式。
Sharp(夏普值)：
換手率：一買一賣就是換手。換手率目標是越小越好，但是不能太小，換手才會帶來收益，過高的換手會導致交易成本太高。同樣也不能收益
適應度函數：
具體參數配置：
遺傳算法參數配置含：
● 種群個體個數
● 子種群個數
● 隨機種子
● 選擇算子
● 交叉算子和交叉概率
● 變異算子和變異概率
● 適應度函數配置
● 樹深度配置
● Terminal Set配置
● Function Set配置
● 其他超參配置
結果sharp進化圖：
總結：遺傳算法不僅金融領域應用廣泛，還可以優化機器學習超參、機器人路徑規劃、流水車間調度等領域都可以應用。
1.容易局部收斂的問題
遺傳算法的局部搜索很強，所以一般容易收斂用以下解決方案，具體情況具體對待。
擴大搜索空間
提高種群的數量、增加數據種類和數量、增加算子。
提高種群多樣性
調整交叉策略、提高交叉概率、調整變異策略、提高變異概率。
毀滅優秀個體
對優秀個體進行存活周期倒計時，如果規定的周期內沒有出現新的優秀個體，就直接殺死優秀個體，讓攜帶有優秀基因且暫時遠離目標的個體存活。
2.不容易收斂的問題
減少搜索空間
減少種群數量，減少數據種類和數量、減少複雜的算子。
降低種群多樣性
降低交叉概率和變異概率。
精英策略
防止精英由於交叉變異被破壞，不能進化到下一代，對於較好的精英直接不通過交叉和變異直接進化到下一代。
3.過擬合問題
過擬合問題是在in-sample表現很好，out-sample表現非常差的問題。
樣本數據
增加樣本數據，讓少量樣本數據覆蓋整體樣本。
模型
一開始不要使用複雜的模型，不要把所有的數據加入到模型中。
數據清洗
對於數據進行清洗，分析清洗後的數據的分布。
中性化
對於相關性很高的因子可以進行中性化處理，避免朝著那個方向進化。
4.多目標收斂平衡問題
單目標進化
一開始先單目標進化，收集一定的數據，分析數據分布情況。
懲罰係數
對於目標擬合的時候，進行懲罰，懲罰可以根據周期進行線性，指數懲罰力度。
優點
● 基於群體的搜索，具備進化能力，不是窮舉搜索
● 適應度函數簡單操作
● 遺傳算法很容易做分布式計算處理
● 遺傳算法大大提高了搜索效率
● 遺傳算法基於概率變異，具有一定隨機性
● 遺傳算法可以與其他算法結合，例如可以優化機器學習的超參
缺點
● 遺傳算法受初代隨機種群影響很大，可以結合啟發式算法改進
● 遺傳算法的諸多參數，例如交叉率、變異率影響了搜索結果，目前大多依賴經驗值
● 遺傳算法利用交叉和變異產生種群，搜索速度慢
改進
編碼改進 ：格雷編碼、動態編碼
選擇進化：隨機競爭選擇，特定目標挑選
交叉改進：多點交叉，單點交換
自適應：自適應遺傳算法，精英策略年齡，種群年齡
效率：並行計算，分布式計算
參考
http://www.obitko.com/tutorials/genetic-algorithms/index.php
https://en.wikipedia.org/wiki/Genetic_algorithm
編輯/雪人