基于智能計算的最優(yōu)指派問題求解技術(shù)及其應用研究.pdf

1、最優(yōu)指派問題是運籌學中的經(jīng)典問題，在生產(chǎn)調(diào)度、運輸規(guī)劃、物流管理、決策系統(tǒng)支持建立等方面有著廣泛的應用。本文以求解最優(yōu)指派問題及其擴展問題為目標，以遺傳算法和粒子群優(yōu)化算法為求解手段，提出了新的求解算法，并用以解決了機器人足球決策系統(tǒng)中若干關(guān)鍵問題。 討論了標準最優(yōu)指派問題的一般定義和數(shù)學模型；根據(jù)實際需要，對最優(yōu)指派問題進行了推廣；并在分析“匈牙利”算法原理和求解步驟的基礎(chǔ)上，說明了該算法存在的不足。 設(shè)計了一種基于改

2、進遺傳算法的最優(yōu)指派問題求解算法。算法引進精英交叉策略和交叉、變異概率的全局自適應引導方法，使得進化過程具有良好的導向性。使用一般最優(yōu)指派問題和“匈牙利”算法難以收斂的典型最優(yōu)指派問題，對該算法進行測試，并與自適應遺傳算法進行性能對比，結(jié)果表明了算法具有更好的收斂性，更快的求解速度。 提出了一種基于粒子群優(yōu)化的最優(yōu)指派問題求解算法。在總結(jié)粒子群優(yōu)化算法及其各種改進的基礎(chǔ)上，結(jié)合基于排列組合的最優(yōu)指派問題描述，以經(jīng)典的速度一位移模

3、型為參照，針對最優(yōu)指派問題的離散性和特殊性，重新定義了粒子的位置和速度，建立了相應的速度和位移的更新機制，并給出了保證種群多樣性的改進。實驗表明，該算法不但對一般類型最優(yōu)指派問題有良好的適應性和有效性，且應用于較大規(guī)模的最優(yōu)指派問題亦能取得理想效果，且在整體性能上優(yōu)于上述改進遺傳算法。 針對現(xiàn)有機器人足球決策系統(tǒng)中陣型選擇環(huán)節(jié)和角色分配環(huán)節(jié)存在的不足，從陣型確定和陣型執(zhí)行兩個層面上，給出了陣型復合和全局角色分配方法，并用上述粒子