基于路徑鏈接技術的多目標優(yōu)化算法研究.pdf

1、在實際的生產生活中，很多問題都需要使多個目標在給定的約束前提下盡可能達到最優(yōu)，這種問題就是多目標優(yōu)化問題。近二十年來，這類問題越來越受到學者的關注，同時這也是一類在實際生產生活中廣泛存在的問題。比如，在工業(yè)生產中，生產調度是生產管理的核心問題，也是現(xiàn)代計算機集成制造系統(tǒng)的關鍵技術，其以生產進度計劃為依據(jù)，在現(xiàn)有生產設備、工藝條件和能力的約束下，對有限的生產資源在時間和空間上進行調度和規(guī)劃，從而確認生產路線，同時實現(xiàn)最小化總完成時間、最小

2、化總流程時間、最小化總延遲時間等多個生產目標。大部分的多目標優(yōu)化問題都是NP-難問題，一般精確算法并不能在多項式時間內求解這些問題。
　　為了有效的求解這類問題，大量的元啟發(fā)式算法被提出。例如遺傳算法、禁忌搜索、蟻群算法等等。在本文中我們將使用路徑鏈接技術求解多目標優(yōu)化問題，路徑鏈接技術就是通過在兩個高質量的解之間建立路徑來產生新的個體。本文的工作就是將路徑鏈接技術和基于超體積的多目標局部搜索算法相結合，提出一個基于路徑鏈接的多目

3、標優(yōu)化算法框架。并將該框架算法應用于雙目標無約束二元二次規(guī)劃問題、雙目標二次分配問題、雙目標最大割問題。
　　在傳統(tǒng)的多目標優(yōu)化算法大多是基于局部空間的搜索的情況下，如何有效的跳出局部空間的限制，并高效的生成具有搜索潛力的個體往往是決定算法表現(xiàn)的關鍵，本文將主要研究基于路徑鏈接技術的多目標優(yōu)化算法。本文的主要研究工作如下：
　　1）把路徑鏈接技術與基于超體積的局部搜索算法相結合，并給出一個基于路徑鏈接和超體積的多目標優(yōu)化算法

4、框架。其中基于超體積的局部搜索算法對每個個體分配基于超體積貢獻的適應值，然后進行個體淘汰，該適應值能夠有效的評估解的質量，并能明顯提高群體的多樣性和最后解的質量。
　　2）在給出的基于路徑鏈接和超體積的多目標優(yōu)化算法框架的基礎上，本文選取無約束二元二次規(guī)劃問題，二次分配問題和最大割問題作為應用對象，這三個問題分別代表了解的表示為二進制串、排列和集合這三種問題類型。本文并將對如何定義這些問題的解之間的距離及如何對其中特定的問題進行路