大數據中遺傳算法求解車間調度問題的示例分析

這篇文章主要介紹大數據中遺傳算法求解車間調度問題的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

無論是遺傳算法，還是什么其他智能優化算法無非都是一個框架，目的都是搜索某一問題的“最優解”，這里為什么加雙引號，因為這類智能優化算法都有一個缺陷，那就是搜索的過程中容易陷入“局部最優”。

給大家舉個生動形象的例子先讓大家對遺傳算法有一個直觀的感受，比如說有6只公雞5只母雞1000米賽跑，第1個100米，2只公雞2只母雞分別位于前四名，這時剩下的4只公雞3只母雞肯定要想辦法追上前面4只雞，于是就想出“交叉”和“變異”兩種方法，1只公雞和1只母雞“交叉”孕育出1個公雞仔和1個母雞仔，孕育結束后父代和母代不幸罹難，一共有3對雞能通過“交叉”的方式繁衍出后代，那剩下的1只公雞怎么辦，這只公雞發生基因突變，也就是“變異”成一只新的公雞了.（大家請注意前4名的雞沒有發生變化，后7名的雞發生“交叉”和“變異”后，雞的總數還是11）；第2個100米，同樣還是有2只公雞和2只母雞位于前四名，只不過這里的前四名可能已經不是第1個100米前四名的那4只雞，同樣剩下的7只雞依然進行“交叉”和“變異”，目的是能讓自己跑得更快；……；一直到第10個100米，最后沖刺階段，畢竟是賽跑理論上來說只能有1個冠軍（不考慮并列第一），那么最后奪得冠軍的那只雞就是跑得最快，這只雞可能是一開始的那11只雞的一只，也可能是經過某些雞之間“交叉”和“變異”繁衍出來的，總之這只雞是最強的。這其實就是所謂的“優勝略汰”，跑得慢的雞會被淘汰，只不過在淘汰之前會完成繁衍。

2. 遺傳算法操作流程

接下來給出遺傳算法的框架：

1、初始化：依據每個種群的特征隨機生成第一代種群的全部個體；

2、求個體適應度：計算每個個體的適應度；

3、選擇過程：依據一定的選擇規范，選出一部分優秀個體參與交叉和變異操作；

4、交叉過程：群體中兩兩配對，交換部分染色體基因，完成交叉操作；

5、變異過程：隨機改變個體中的部分基因，來實現變異操作；

6、終止判斷：若新一代種群滿足終止條件，停止算法迭代，記錄此時的最優解為問題的最優解；否則，迭代次數加1，返回步驟2；

3. 車間調度問題描述

車間調度是指根據產品制造的合理需求分配加工車間順序，從而達到合理利用產品制造資源、提高企業經濟效益的目的。車間調度問題從數學上可以描述為有n個待加工的零件要在m臺機器上加工。已知各工件的加工時間，優化目標是如何確定工件的加工順序以及每階段工件在機器上的分配情況，使得最大完工時間極小化。

4. 遺傳算法求解車間調度問題方法

1.個體編碼

當待加工的工件總數為k，工件ni的加工工序共為mj時，則個體表示為長度為，染色體前半部分表示所有工件在機器上的加工工序，后半部分表示工件每道工序的加工機器序號。如個體

該個體表達了4個加工工序都是2次的工件在3臺機器上的加工順序。其中前8位表示工件的加工順序，為工件2->工件4->工件3->工件1->工件1->工件2->工件3->工件4；9到16位表示加工機器，依次為機器2->機器1->機器3->機器3->機器2->機器2->機器1->機器3。

2. 適應度值

染色體的適應度值為全部工件的完成時間，適應度值計算公式為

其中，time指全部任務完成時間。全部工件完成時間越短，該染色體越好。

3. 選擇操作

采用輪盤賭法選擇適應度較好的染色體，個體選擇概率為

其中，表示染色體i在每次選擇中被選中的概率。

4.交叉操作

交叉操作首先從種群中隨機選取兩個染色體，并取出每個染色體的前位進行交叉。操作方法如下：交叉位置為5，只對個體前位進行交叉。

交叉后某些工件的工序多余（子代1的工件2，子代2的工件3），某些工件的工序缺失（子代1的工件3，子代2的工件2），因此，把工件工序多余的操作變為工件工序缺失的操作，并按交叉前個體的操作機器來調整后一半的加工機器。

5. 變異操作

變異算子首選從種群中選取變異個體，然后選擇變異位置pos1和pos2，最后把個體中pos1和pos2位的加工工序以及對應的加工機器序號兌換，如下所示，變異位置為2和4。

以上是“大數據中遺傳算法求解車間調度問題的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！