生產(chǎn)調(diào)度智能優(yōu)化算法課件

1、PowerPoint Template基于局部搜索的生產(chǎn)調(diào)度算法傳統(tǒng)算法與啟發(fā)式算法都屬于構(gòu)造型算法。都是從沒有調(diào)度序列開始，每次增加一項工作來逐漸構(gòu)造一個調(diào)度。改進型算法：在概念上與構(gòu)造型算法完全不同，它們是從一個任意選擇出的完整的調(diào)度方案開始，然后通過改進現(xiàn)有的調(diào)度來嘗試獲得更好的調(diào)度。在改進型的調(diào)度中一個重要的類別就是局部搜索法。Company Logo局部搜索算法相鄰：如果一個調(diào)度可以通過定義的修改，轉(zhuǎn)化為另一個調(diào)度，那么這兩個調(diào)度就可以成為相鄰。局部搜索算法不保證會產(chǎn)生最優(yōu)解，它通常會試著在現(xiàn)有調(diào)度鄰域找到一個更好的調(diào)度。每次轉(zhuǎn)化之后，局部搜索法會在鄰域之中進行搜索，評價不同的鄰域的

2、解。然后按照給定的接受拒絕原則或者接受或者拒絕一個候選的解來作為下一個調(diào)度改進的方向。局部搜索算法中目前應(yīng)用于生產(chǎn)調(diào)度中比較廣泛的有模擬退火法（SA）、禁忌搜索法（TS）以及遺傳算法（GA） 。Company Logo模擬退火算法 模擬退火算法是用來解決復(fù)雜的組合優(yōu)化問題，根據(jù)固體退火過程的模擬而得名，固體退火就是先將固體加熱至融化，再徐徐冷卻使之凝固成規(guī)則的晶體。假設(shè)存在一個解集S（所有可能解的集合）和一個目標函數(shù)f（定義在解集S上的成員的實數(shù)函數(shù)），目標是在解集S中尋找一個解使其能使目標函數(shù)值最小。模擬退火是一個迭代過程，這個過程取決于鄰域的產(chǎn)生。首先產(chǎn)生一個初始解，然后在每個溫度下產(chǎn)生當

3、前解的鄰域，直到滿足停止準則為止。Company Logo模擬退火算法要經(jīng)過多次迭代，在第k次迭代時，會得到當前的調(diào)度 以及目前可以找到的最好的調(diào)度 。對于單機問題，這些調(diào)度是工作的次序。令 和 表示對應(yīng)的目標值。目前得到的最佳調(diào)度值是 ，通常作為期望達到的標準。在搜索最優(yōu)調(diào)度時，算法從一個調(diào)度移到另一個調(diào)度。在第k次迭代時，在 的鄰域中搜索新調(diào)度。首先，在鄰域中選出一個候選調(diào)度 ，如果 那么將進行一次移動，設(shè)定 。如果 那么 就被設(shè)定為 ，然而，如果 ，那么就會按照以下該概率對 進行移動：按 的概率，拒絕調(diào)度 而保留現(xiàn)有的調(diào)度，設(shè)定 。當調(diào)度 比調(diào)度 更優(yōu)時，它不會改變。 是控制參數(shù)，用來表

4、示冷卻參數(shù)或者溫度。通常 ，其中a的值在 01之間。Company Logo模擬退火算法步驟1.設(shè)定k=1，選擇 ； 使用啟發(fā)式算法選擇初始序列 ；設(shè)定 。2. 從 的鄰域中選擇候選調(diào)度 ； 如果 ，那么設(shè)定 ，到步驟3； 如果 ，那么設(shè)定 ，到步驟3； 如果 ，那么生成服從Uniform（0，1） 分布的隨機數(shù) ； 如果 ，那么設(shè)定 否則設(shè) ，到步驟3.3.選擇 ；將k增加1；如果k=N，就停止，否則到步驟2. Company Logo禁忌搜索算法（TS）禁忌搜索算法是一種迭代方法，它開始于一個初始可行解S，然后移動到鄰域N（S）中最好的解 ， 即 對于目標函數(shù) 在鄰域N（S）中是最優(yōu)的。然

5、后從新的開始點重復(fù)此方法。為了避免死循環(huán)，禁忌搜索把最近的T個移動放在一個禁忌表中，在目前的迭代中這些移動是被禁止的，在一定數(shù)目的迭代之后它們又被釋放出來。這樣的禁忌表是一個循環(huán)表，它被循環(huán)的修改，其長度T是事前自己設(shè)定的一個值。最后通過定義一個停止準則來終止整個算法。Company Logo序列 4，2，1，3 2，1，4，3 2，4，3，1 460 500 608 可以看出第二次移動是被禁忌的，然而，第一次移動要比第二次優(yōu)化。第一次移動產(chǎn)生的調(diào)度比目前為止最好的調(diào)度要差，最好的調(diào)度就是當前這個，所以它是個局部極小值。依然選 ，禁忌表被更新包含（2，4），（1，4）。 鄰居對應(yīng)的目標函數(shù)值為

6、序列 2，4，1，3 4，1，2，3 4，2，3，1 436 440 632 現(xiàn)在盡管最好的移動是移動到2，4，1，3（ ），但是這個移動是被禁止的，因而， 被選定為4，1，2，3.更新禁忌表，得到（1，2），（2，4），而條目（1，4）就會從禁忌表中刪除掉，因為表的長度要保持為2. 鄰居對應(yīng)的目標函數(shù)值為：Company Logo 序列 1，4，2，3 4，2，1，3 4，1，3，2 408 460 586 調(diào)度4，2，1，3是被禁忌的，但是最好的移動是移動到調(diào)度1，4，2，3.所以 ，對應(yīng)的目標函數(shù)值比期望得到的標準要好。所以期望得到的標準變?yōu)?08.禁忌表更新，增加（1，4）而去掉（2，4）。從而得到全局最小值。即為利用禁忌搜索方法得到的調(diào)度。 Company Logo遺傳算法基于遺傳算法的調(diào)度是將序列或者調(diào)度看成個體或是種群的成員，每個個體以其適應(yīng)度為特征。個體的適應(yīng)度由對應(yīng)的目標函數(shù)值來衡量。過程反復(fù)進行，每次迭代稱為一代。種群的一代包含從上一代存活下來的個體和從上一代得到的新調(diào)度或者說是子代。從一代到下一代，種群的大小通常保持不變，通過將上一代的部分個體進行復(fù)制和變異而產(chǎn)生子代。個體有時也被稱為染色體。在多機環(huán)境下，一條染色體可以由子染色體組成，每個子染色體包含著關(guān)于工作序列在一臺機器上的信息。上一代染色