[發明專利]基于粒子群的混沌入侵雜草算法的DNA編碼序列優化方法

在審

• 申請號: 201811024587.4
• 申請日: 2018-09-04
• 公開（公告）號: CN109300507A
• 公開（公告）日: 2019-02-01
• 發明（設計）人: 王賓;劉凱強;張強;周昌軍
• 申請（專利權）人: 大連大學
• 主分類號: G16B20/00
• 分類號: G16B20/00
• 代理公司: 大連八方知識產權代理有限公司 21226
• 代理人: 衛茂才

本發明涉及一種基于粒子群的混沌入侵雜草算法的DNA序列優化方法。該方法首先要構造出全部的DNA序列作為初始種群。接著以入侵雜草算法對初始種群進行繁殖、空間擴算、競爭性排除（局部最優解）。其次，利用已經得出的局部DNA編碼序列，利用粒子群優化方法進行搜索，得到新的DNA編碼序列，計算序列的適應度并對其進行排序。最后，選出最優DNA編碼序列。本發明提出的基于粒子群的混沌入侵雜草算法的DNA序列優化算法能夠搜索出質量更優的DNA編碼序列。

技術領域

本發明屬于DNA計算中編碼設計領域，涉及群體智能優化算法和DNA編碼，具體涉及用粒子群算法、入侵雜草算法和混沌算法來優化DNA序列。

背景技術

1994年，美國南加州大學的阿德爾曼教授提出用DNA分子進行計算的一種新的計算模式。在這種新的計算模式當中DNA分子被作為信息存儲的單元并且分子之間的生化反應代表計算操作的過程。在這種背景下，沃森-克里克堿基互補配對原則是最重要的反應之一，因為這一反應能夠成功地檢索存儲在DNA分子中的信息。然而必須保證在實際的生化反應過程中，編碼每一個信息元的DNA分子能夠被唯一識別，因為不期望的反應通常會導致不正確的計算。因此設計質量較高的DNA序列非常重要，這樣能夠確保集合中的DNA序列僅僅只與其互補的序列雜交。

粒子群算法是一種群體智能優化算法。該算法能以較大概率收斂于全局最優解。實踐證明，它適合在多目標環境中尋優，具有較快的速度和更好的全局搜索能力。粒子群算法的基本思想是對種群中粒子的適應度進行計算，尋找個體極值和群體極值，然后對粒子的位置和速度進行更新，再計算適應度找到個體極值和群體極值，如此迭代直到滿足最大進化代數。

入侵雜草算法是一類元啟發式搜索算法，模擬了雜草入侵殖民地并快速占據繁殖的自然行為過程，入侵雜草算法已經成為一種解決許多領域實際問題的有效工具。入侵雜草算法的基本思想是用雜草表示所求問題的可行解，進化過程中，雜草通過繁殖產生種子，種子通過空間擴散發育成雜草，如此反復，當種群中雜草的數量達到預先設定最大種群規模時，雜草通過競爭進行生存，保存適應度好的雜草，淘汰適應度差的。

發明內容

本發明的目的在于提出基于粒子群的混沌入侵雜草算法的DNA序列優化方法。該方法可以搜索出質量較優的DNA編碼序列。

為解決上述技術問題，本發明提供一種基于粒子群的混沌入侵雜草算法的DNA序列優化方法，該方法包括以下步驟：

步驟1：利用Tent映射對隨機初始的種群進行映射，得到的種群作為初始種群；

步驟2：利用入侵雜草算法對初始種群進行進化，種群中個體通過生成種子來進行繁殖，生成的種子以柯西分布的方式分布在D維搜索空間進行空間擴散；

步驟3：把入侵雜草算法進化得到的雜草數量與預先設定的最大雜草數量作比較，若數量大于最大雜草數量進行步驟4，否則進行步驟8；

步驟4：將利用入侵雜草算法進化得到的種群作為粒子群優化算法的輸入，通過粒子的位置和速度的迭代更新對種群進行搜索得到新的種群；

步驟5：把得到的新的種群按照適應度進行排序；

步驟6：對排序后的種群進行競爭性排除，適應度較好的個體被保留，其余的被淘汰；

步驟7：判斷當前迭代次數是否達到最大的迭代次數，若是進行步驟8，否則返回到步驟2；

步驟8：對結果進行適應度排序，把排序后的結果輸出。

本發明與現有技術相比具有以下創新之處：

1、用Tent混沌映射初始化種群，所得的序列均為均勻分布；

2、入侵雜草算法使得初始種群產生的種子進化得到的雜草以柯西分布的方式在父代個體周圍進行擴散，利用粒子群優化算法避免算法陷入局部最優，使得算法有更好的全局搜索能力；