基于自組織優(yōu)化算法的多旅行商問題的求解與應用.pdf

1、自組織優(yōu)化算法是基于極值動力學提出的一種新的啟發(fā)式智能優(yōu)化算法，是極值優(yōu)化算法的一種改進形式。自組織優(yōu)化算法具有統(tǒng)計物理中遠離平衡態(tài)的動力學特征，它總是選擇當前解中適應度差的變量和相互關聯(lián)的變量進行變異。自組織優(yōu)化算法具有收斂速度快、局部搜索能力強、設計簡單、容易實現(xiàn)的優(yōu)點，并且增加了解的鄰域操作與鄰域解的概率選擇，使得算法具有更大概率的廣度搜索和深度搜索能力，是一種更為合理的動態(tài)優(yōu)化過程。該算法提出后在求解組合優(yōu)化問題上得到了一定的應

2、用，如旅行商問題和熱軋單元調度問題等。
　　 本文把自組織優(yōu)化算法的應用推廣到了約束條件更強的組合優(yōu)化問題，通過模型處理和局部適值的定義，把約束條件統(tǒng)一轉化到目標函數(shù)進行處理，取得了顯著的優(yōu)化效果。
　　 具體的，本文對以下問題做了應用研究：
　　 基于自組織優(yōu)化算法的多旅行商問題的求解。本文通過引入虛擬城市把多旅行商問題轉化為單旅行商問題，虛擬城市不僅僅用于區(qū)分不同旅行商的路徑，而且其局部適值的定義有效的處理了

3、問題的約束。對于傳統(tǒng)多旅行商問題本文直接應用自組織優(yōu)化算法進行求解；對于要求最長路徑最短的多旅行商問題和每個旅行商允許經(jīng)過的城市數(shù)有上限的多旅行商問題，分別通過虛擬城市局部適值的不同定義，將約束轉化為目標函數(shù)的一部分，有效的處理了問題的特殊約束。針對標準算例進行的仿真結果表明自組織優(yōu)化算法可以有效的求解這幾類多旅行商問題。此外，對于多旅行商問題的一個廣泛應用實例—車輛路徑規(guī)劃問題，本文也應用自組織優(yōu)化算法進行了求解，針對每輛車的容量有限

4、制而且要求總的路徑最短的車輛路徑規(guī)劃問題，本文給出了仿真結果，表明自組織優(yōu)化算法可以有效求解每輛車的容量帶約束的車輛路徑規(guī)劃問題。
　　 基于自組織優(yōu)化算法的熱軋批次調度。熱軋單元調度中的板卷排序是一個典型的約束組合優(yōu)化問題，熱軋批次調度需要運用并行策略，按工作訂單和約束條件，同時形成多個軋制單元的軋制順序。論文首先基于多旅行商問題模型，建立熱軋批次調度的帶約束優(yōu)化的數(shù)學模型；然后應用自組織優(yōu)化算法進行求解；本文提出的基于自組織