[發(fā)明專利]基于MAB的超啟發(fā)式算法求解多目標(biāo)優(yōu)化問題的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811230929.8
• 申請(qǐng)日: 2018-10-22
• 公開（公告）號(hào): CN109460862B
• 公開（公告）日: 2021-04-27
• 發(fā)明（設(shè)計(jì)）人: 張淑艷;楊太龍;郭一
• 申請(qǐng)（專利權(quán)）人: 鄭州大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06Q10/06;G06N3/00
• 代理公司: 鄭州隆盛專利代理事務(wù)所(普通合伙) 41143
• 代理人: 余菲

本發(fā)明涉及超啟發(fā)式算法領(lǐng)域，尤其涉及一種基于MAB的超啟發(fā)式算法求解多目標(biāo)優(yōu)化問題的方法，該方法以MAB策略為學(xué)習(xí)策略，并使用四種性能評(píng)估機(jī)制評(píng)估各低層啟發(fā)式算子的性能，通過學(xué)習(xí)和選擇的機(jī)制以更好的結(jié)合各低層啟發(fā)式算子的優(yōu)點(diǎn)；該算法在連續(xù)多目標(biāo)優(yōu)化問題集WFG上進(jìn)行實(shí)驗(yàn)，并取得了良好的實(shí)驗(yàn)結(jié)果。本發(fā)明的目的在于克服了傳統(tǒng)啟發(fā)式算法設(shè)計(jì)時(shí)通用性較差且單一啟發(fā)式算法可能在一些問題實(shí)例上效果較差的問題，提出一種基于MAB的超啟發(fā)式算法求解多目標(biāo)優(yōu)化問題的方法。

技術(shù)領(lǐng)域

本發(fā)明涉及超啟發(fā)式算法領(lǐng)域，尤其涉及一種基于MAB的超啟發(fā)式算法求解多目標(biāo)優(yōu)化問題的方法。

背景技術(shù)

多目標(biāo)優(yōu)化問題作為一類NP難解問題，大量算法用于求解該類問題。研究人員經(jīng)常采取問題定制的啟發(fā)式算法，以在合理的時(shí)間內(nèi)獲得可以接受的解決方案。啟發(fā)式算法的優(yōu)點(diǎn)在于可以方便地根據(jù)問題融入領(lǐng)域知識(shí)，缺點(diǎn)在于通用性不佳，常常需要針對(duì)問題設(shè)計(jì)特化算法。由于啟發(fā)式算法的設(shè)計(jì)具有較強(qiáng)的問題相關(guān)性，這就增大了算法設(shè)計(jì)的工作量。除此之外，單一啟發(fā)式算法可能在一些問題實(shí)例上取得較優(yōu)效果，而在另一些實(shí)例上效果較差，即不能保證單一啟發(fā)式算法在所有問題實(shí)例上都能獲得高質(zhì)量結(jié)果。

超啟發(fā)式算法(Hyper-heuristic,HH)作為一種啟發(fā)式算子選擇或者啟發(fā)式算子構(gòu)建的搜索方法可以解決以上問題。給定一個(gè)搜索問題和一個(gè)與問題相關(guān)的啟發(fā)式算子集合(稱為低層啟發(fā)式算子集合)。超啟發(fā)式算法不是直接搜索問題的鄰域空間，而是作為高層啟發(fā)式策略將搜索上升一個(gè)層次，來搜索低層啟發(fā)式算子的鄰域空間。在搜索過程中，超啟發(fā)式算法根據(jù)不同的求解狀態(tài)，從低層啟發(fā)式算子集合中選擇并應(yīng)用合適的低層啟發(fā)式算子，最終被選擇的低層啟發(fā)式算子構(gòu)成了低層啟發(fā)式算子序列。這種方法可以將各個(gè)低層啟發(fā)式算子的優(yōu)點(diǎn)結(jié)合，并在一定程度上避免低層啟發(fā)式算子的缺點(diǎn)。超啟發(fā)式算法在單目標(biāo)優(yōu)化問題上求解已經(jīng)取得了較好的效果，然而，超啟發(fā)式算法在多目標(biāo)優(yōu)化問題上的應(yīng)用較少。

經(jīng)對(duì)現(xiàn)有技術(shù)文檔的檢索發(fā)現(xiàn)，Burke等人在《Springer》(2005，pp:129–158)上出版的“Metaheuristics:Progress as Real Problem Solvers”提出了使用加強(qiáng)學(xué)習(xí)和禁忌搜索作為選擇策略的超啟發(fā)式算法用于求解多目標(biāo)空間分配和時(shí)間規(guī)劃問題。Vazquez-Rodriguez and Petrovic在《Journal of Heuristics》(2010,Vol.16,No.6,pp:771–793)上發(fā)表的文章“A new dispatching rule based genetic algorithm for the multi-objective job shop problem”，提出了基于調(diào)度規(guī)則和遺傳算法的超啟發(fā)式算法用于求解多目標(biāo)作業(yè)車間問題。然而，以上提出的超啟發(fā)式算法只在非連續(xù)性多目標(biāo)優(yōu)化問題上求解。Mashael Maashi等人在《Expert Systems with Applications》(2014,Vol.41,pp:4475-4493)上發(fā)表的文章“A multi-objective hyper-heuristic based on choicefunction”，提出了一種基于選擇函數(shù)的超啟發(fā)式算法HH_CF用于求解連續(xù)性多目標(biāo)優(yōu)化問題，并取得了較好的效果。但是該算法使用低層啟發(fā)式算子的運(yùn)行間隔(CPU時(shí)間)作為選擇機(jī)制的一個(gè)參數(shù)，使得算法不同的機(jī)器上運(yùn)行效果不太穩(wěn)定。Giovani Guizzo等人在《GECCO》(2015,Madrid,Spain,pp:1343-1350)上發(fā)表的文章“A Hyper-Heuristic for theMulti-Objective Integration and Test Order Problem”提出了兩種超啟發(fā)式算法HITO-CF和HITO-MAB用于求解基于搜索的多目標(biāo)軟件工程方法問題。HITO-CF和HITO-MAB以多種交叉算子和變異算子作為低層啟發(fā)式算子，分別使用CF和MAB作為選擇策略。在選擇過程中，根據(jù)父代個(gè)體與子代個(gè)體之間的支配關(guān)系使用累加求和的方法計(jì)算低層啟發(fā)式算子的回報(bào)值。然而這種回報(bào)值計(jì)算方法著重于解集的收斂性，而忽略了解集的分布性。

發(fā)明內(nèi)容