[發(fā)明專利]一種改良的帝國(guó)主義競(jìng)爭(zhēng)算法求解作業(yè)車間調(diào)度問(wèn)題

在審

• 申請(qǐng)?zhí)枺?/td>: 201610169626.4
• 申請(qǐng)日: 2016-03-22
• 公開(kāi)（公告）號(hào): CN106611235A
• 公開(kāi)（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: 姜艾佳;胡成華
• 申請(qǐng)（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

所屬領(lǐng)域

本發(fā)明涉及作業(yè)車間調(diào)度領(lǐng)域，具體地涉及用算法求解作業(yè)車間調(diào)度問(wèn)題。

背景技術(shù)

現(xiàn)有技術(shù)針對(duì)作業(yè)車間調(diào)度問(wèn)題(Job-Shop Scheduling Problem，JSP)已有很多的算法被用來(lái)解決此問(wèn)題。比如遺傳算法、粒子群算法等等。雖然這些算法都有各自的優(yōu)點(diǎn)，但也有其缺點(diǎn)：收斂速度慢、精確度不高等問(wèn)題。

帝國(guó)主義算法是(ICA)也稱為殖民地競(jìng)爭(zhēng)算法，是Atashaz_Gargari和Lucas于2007年提出的一種基于帝國(guó)主義殖民競(jìng)爭(zhēng)機(jī)制的進(jìn)化算法，屬于社會(huì)啟發(fā)的隨機(jī)優(yōu)化搜索方法。ICA算法根據(jù)帝國(guó)主義的社會(huì)政策來(lái)控制更多的國(guó)家，在殖民地國(guó)家受到一些規(guī)律支配時(shí)使用它們的資源，如果一個(gè)帝國(guó)失去強(qiáng)大的勢(shì)力，其他國(guó)家將占有它。帝國(guó)主義競(jìng)爭(zhēng)算法的基本思想是：同其他進(jìn)化算法相似，帝國(guó)主義競(jìng)爭(zhēng)算法開(kāi)始于一組被定義為國(guó)家的個(gè)體，所有國(guó)家被分為兩類：帝國(guó)主義國(guó)家和殖民地國(guó)家。將最初勢(shì)力比較強(qiáng)大的國(guó)家作為帝國(guó)主義國(guó)家，其他國(guó)家作為殖民地國(guó)家。根據(jù)每個(gè)國(guó)家的勢(shì)力將殖民地分配給不同的帝國(guó)主義國(guó)家。帝國(guó)主義國(guó)家與其所包含的殖民地被稱為一個(gè)帝國(guó)。帝國(guó)之間通過(guò)競(jìng)爭(zhēng)以獲得更多的殖民地為目的，勢(shì)力更大的帝國(guó)有較大的可能性戰(zhàn)友最弱的殖民地，智力薄弱的帝國(guó)將逐漸失去其殖民地，當(dāng)所有殖民地全部被一個(gè)帝國(guó)占有時(shí)，該算法結(jié)束。

傳統(tǒng)的帝國(guó)主義競(jìng)爭(zhēng)算法具有簡(jiǎn)單、準(zhǔn)確、省時(shí)等優(yōu)點(diǎn)，是一種十分有效率且易于使用的優(yōu)化算法，該算法節(jié)省內(nèi)存，尋優(yōu)時(shí)間短，并且能夠迅速地在搜索空間里收斂到最優(yōu)解。但是，對(duì)于作業(yè)車間調(diào)度問(wèn)題的優(yōu)化，易于收斂，傳統(tǒng)的帝國(guó)主義算法不能夠得到足夠的精確解，且最終求得一個(gè)解而不是一組解，不適用于作業(yè)車間的管理安排問(wèn)題的求解。

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

針對(duì)傳統(tǒng)帝國(guó)主義競(jìng)爭(zhēng)算法存在的上述不足，本發(fā)明要解決的技術(shù)問(wèn)題是提供一種改良的帝國(guó)主義競(jìng)爭(zhēng)算法求解作業(yè)車間調(diào)度問(wèn)題。

本發(fā)明的目的是克服現(xiàn)有技術(shù)中存在的：傳統(tǒng)帝國(guó)主義競(jìng)爭(zhēng)算法容易過(guò)早收斂；求解精確度不夠高；且在車間調(diào)度問(wèn)題中的應(yīng)用不夠靈活的問(wèn)題。

本發(fā)明為實(shí)現(xiàn)上述目的所采用的技術(shù)方案是：一種改良的帝國(guó)主義競(jìng)爭(zhēng)算法求解作業(yè)車間調(diào)度問(wèn)題，該算法的步驟如下：

步驟1：初始化帝國(guó)主義競(jìng)爭(zhēng)算法參數(shù)：初始化國(guó)家數(shù)量、帝國(guó)主義國(guó)家、殖民地國(guó)家。

步驟2：計(jì)算帝國(guó)的相對(duì)勢(shì)力：用機(jī)器處理作業(yè)能力來(lái)刻畫(huà)。

步驟3：計(jì)算帝國(guó)主義國(guó)家的勢(shì)力

步驟4：初始化帝國(guó)主義集團(tuán)：根據(jù)帝國(guó)的勢(shì)力將不同數(shù)量的殖民地國(guó)家分配給帝國(guó)主義國(guó)家。

步驟5：計(jì)算帝國(guó)集團(tuán)的總勢(shì)力：一個(gè)帝國(guó)集團(tuán)的總勢(shì)力包括兩部分，一部分為帝國(guó)主義國(guó)家的勢(shì)力，另一部分為它所擁有的殖民地國(guó)家的勢(shì)力。

步驟6：殖民地向所屬帝國(guó)移動(dòng)：當(dāng)?shù)蹏?guó)集團(tuán)形成后，每個(gè)帝國(guó)集團(tuán)中的帝國(guó)主義國(guó)家試圖增加其殖民地的數(shù)量，在ICA算法中，殖民地國(guó)家沿著指向其所屬帝國(guó)的方向靠近帝國(guó)。

步驟7：帝國(guó)集團(tuán)的競(jìng)爭(zhēng)：帝國(guó)主義的競(jìng)爭(zhēng)過(guò)程發(fā)生在帝國(guó)集團(tuán)之間，因?yàn)槊恳粋€(gè)帝國(guó)集團(tuán)都試圖占有其他帝國(guó)的殖民地并且控制他們。通過(guò)競(jìng)爭(zhēng)使得強(qiáng)大的帝國(guó)集團(tuán)更加強(qiáng)大，弱小的帝國(guó)集團(tuán)更加弱小。

步驟8：殖民地國(guó)家的滅亡：在帝國(guó)的侵犯過(guò)程中，存在殖民地國(guó)家滅亡。

步驟9：新殖民地國(guó)家的產(chǎn)生：在社會(huì)進(jìn)化過(guò)程中，會(huì)有新的殖民地產(chǎn)生。

步驟10：弱勢(shì)帝國(guó)的滅亡：在帝國(guó)競(jìng)爭(zhēng)中，失去勢(shì)力的帝國(guó)集團(tuán)將會(huì)滅亡，而且它所擁有的殖民地將被其他帝國(guó)集團(tuán)所瓜分。

步驟11：新帝國(guó)的產(chǎn)生：在帝國(guó)競(jìng)爭(zhēng)中，會(huì)有新的帝國(guó)產(chǎn)生。

步驟12：計(jì)算帝國(guó)存活率：用機(jī)器利用率ρ來(lái)刻畫(huà)。

步驟13：最后，保留最終剩余的帝國(guó)，將適應(yīng)度值作為最優(yōu)解。

本發(fā)明的有益效果是：

1、帝國(guó)的相對(duì)勢(shì)力直接用機(jī)器處理作業(yè)能力來(lái)刻畫(huà)，減少算法計(jì)算復(fù)雜度。

2、直接定義機(jī)器為帝國(guó)、作業(yè)為殖民地，避免了隨機(jī)產(chǎn)生初始解帶來(lái)的不確定性，減少算法運(yùn)行時(shí)間。

3、利用作業(yè)運(yùn)行時(shí)間來(lái)計(jì)算帝國(guó)主義國(guó)家的勢(shì)力大小，簡(jiǎn)單、實(shí)際、靠譜。

4、利用機(jī)器作業(yè)能力來(lái)作為帝國(guó)國(guó)家殖民地分配的準(zhǔn)則，簡(jiǎn)單直觀、解的精確度高。

5、改變了帝國(guó)的總勢(shì)力的計(jì)算方式，使算法更加靈活。

具體實(shí)施方式