[發明專利]一種新型的群智能游牧算法

在審

• 申請號: 201910065705.4
• 申請日: 2019-01-24
• 公開（公告）號: CN109800850A
• 公開（公告）日: 2019-05-24
• 發明（設計）人: 林娜;付璐煒;趙亮;拱長青
• 申請（專利權）人: 沈陽航空航天大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 沈陽維特專利商標事務所(普通合伙) 21229
• 代理人: 甄玉荃

本發明涉及智能技術領域，特別是涉及一種新型的群智能游牧算法。該算法通過牧民放牧活動、斥候探索活動、部落遷徙及決策活動三個過程組成；具體的步驟如下：步驟1：初始化群智能游牧算法參數；步驟2：牧民放牧活動；步驟3：斥候探索活動；步驟4：部落遷徙及決策；步驟5：終止算法并返回最優解；本發明具有結構簡單，原理生動易懂，主觀控制參數少、搜索精度高、全局性強等優點。

技術領域

本發明涉及智能技術領域，特別是涉及一種新型的群智能游牧算法。

背景技術

自然界經歷了長久的演化，擁有強大的適應性。人通過對大自然的觀察和思考獲得靈感，構建出各類算法模型解決復雜的實際問題，這就是基于仿生思想的元啟發式智能算法。復雜的優化問題曾經只能通過確定性的數學優化方法求解，但隨著問題復雜性提升、維度增加，傳統算法求解難度劇增且僅能保證局部最優。直到智能算法的出現才大大緩解了這些缺陷，智能算法帶有隨機性，模仿自然界的行為或現象，在求解過程中展現出強大的自適應能力，面對復雜問題有較好的表現。按著模仿來源主要可分為自然現象、生物行為、物理過程三類。自然現象啟發算法啟發于大自然演化，如最先提出的遺傳算法，模擬DNA進化過程中選擇、重組、變異，進化到一個最佳狀態即最優解，花授粉算法模擬花朵傳粉繁殖找到最適宜生存的位置；生物行為啟發算法如粒子群算法受鳥群聯合捕食啟發、人工蜂群算法受蜜蜂分工尋蜜采蜜啟發；物理過程啟發算法的靈感來自于物理現象，如著名的退火算法模擬固體退火過程、煙花算法模擬煙花爆炸的過程。

現存的智能算法數量龐大，在特定問題上能表現出較強的優化能力，這些算法廣泛應用在工程、經濟、工業設計等領域的優化。但他們往往過于復雜而難以理解和選擇，尤其是考慮到優化算法的使用者通常并非是計算機專業算法領域的研究者。由于“沒有免費午餐”定理的存在，對于特定問題需要選擇特定的算法，算法思想、算法選擇、參數調整需要專業的分析，真正使用算法的非計算機專業的工程人員無法發揮算法的優化性能。

本發明提出了一種稱為游牧算法(Nomad Algorithm,以下簡稱NA)的全新智能算法，并附收斂性分析(收斂證明見實施例2所示)，其靈感來自于草原上游牧部落逐水草而居的遷徙策略。游牧算法的原理生動簡單易于理解，需要調整的參數少便于使用，良好的平衡了局部搜索和全局搜素，使得算法在保證全局搜索能力的同時還能迅速得到較高的收斂精度。NA的強大優化能力使其可以廣泛應用于工業設計、工程優化、經濟模型優化等多種領域。

發明內容

針對現有大多數智能算法流程復雜，敏感參數眾多，收斂精度與收斂全局性難以平衡的問題，本專利受草原上游牧部落逐水草而遷徙的種群行為啟發，提出了一種全新的群智能算法；

游牧算法(NA)將待優化問題的搜索空間當作一片草原，游牧部落總是向著水草更加豐茂即適應度更好的地方遷徙，將部落成員，即搜索代理，劃分為牧民和斥候(斥候指行動迅捷負責偵察的人，本算法中指負責全局搜索的搜索代理)。牧民和斥候以部落為中心，分別以不同的策略進行搜索作業，對應算法的局部開采和全局勘探。

NA依據當前一輪搜索的結果，決定下一輪搜索范圍與強度，達到面對不同復雜問題能夠自適應的效果。

牧民在以部落為中心的小范圍均勻搜索，局部搜索能力較強，保障了算法收斂的高精度。

斥候則從部落出發，探索遠方是否有更宜居的地方，但越遠的地方概率會變小，有較強全局搜索能力，保障算法能夠收斂于全局最優解，避免陷入局部最優。

當游牧部落的人口即種群數目固定時，通過調整牧民和斥候的比例，決定全局搜索和局部搜索的強度，實現收斂精度與全局性的良好平衡。算法通過牧民放牧活動、斥候探索活動、部落遷徙及決策活動三個過程組成。具體的步驟如下：

步驟1：初始化NA算法參數；