【畢業(yè)學(xué)位論文】（Word原稿）基于語言偏好關(guān)系多目標(biāo)群組決策的研究與應(yīng)用-計(jì)算機(jī)軟件與理論

西 華 大 學(xué) 碩 士 學(xué) 位（畢 業(yè)）論 文 題目： 基于 語言偏好關(guān)系多目標(biāo)群組決策的研究與應(yīng)用 研究 生： 指導(dǎo)教 師 ： 專 業(yè)： 計(jì)算機(jī) 軟件與理論 研究方 向 ： 智能信息處理 培養(yǎng)單 位 ： 西 華 大 學(xué) 論文起止日期： 2008 年 1 月至 2009 年 5 月西華大學(xué)碩士學(xué)位論文 I 基于 語言 偏好關(guān)系多目標(biāo)群組決策的研究與應(yīng)用 計(jì)算機(jī)軟件與理論 研究生 指導(dǎo)教師 多目 標(biāo)決策是指為達(dá)到多種目的或目標(biāo)而在眾多的可行方案中進(jìn)行選擇的過程 。 在現(xiàn)實(shí)生活中，我們經(jīng)常會(huì)遇到需要 進(jìn)行 多目標(biāo)決策的問題 ，其 核心思 想是尋找滿意解 ，而不是最優(yōu)解。這是因?yàn)?在復(fù)雜的決策環(huán)境中， 目標(biāo) 之 間往往是 相互沖突和不可公度 的 ， 從而 導(dǎo)致 了 最優(yōu)方案 的不存在 。 當(dāng)前基于 偏好關(guān)系 的多目標(biāo)決策模型并不多見，與群組決策相關(guān)的模型更是少之又少。 而 在做重大決策的時(shí)候， 一個(gè)人的智慧是遠(yuǎn)遠(yuǎn)不夠的。因此， 在本文中， 我們 探討了 一個(gè)基于 語言 偏好關(guān)系的多目標(biāo)群組決策模型。 該模型有 下面 四個(gè)特點(diǎn)： 1、 基于語言偏好關(guān)系。 在作決策時(shí)，人們很難用 精確的數(shù)值描述偏好度。 為 此，我們引入語言偏好關(guān)系，決策者將 以一種非常自然的方式表達(dá)對(duì)方案的 偏好 。 2、 基于 由 于 念很符合多目標(biāo)問題本身的特點(diǎn)， 因此 ，在優(yōu)化算法的選擇上，我們采用 具有 。 目前比較流行的 算法是 改進(jìn)的非劣分層遺傳算 法 運(yùn)用 該算法，可以得到分布均勻 且散布較好的近似 3、 基于目標(biāo)滿意度 我們引入目標(biāo)滿意度的概念， 是為了將大 量的 集縮小到只有決策者滿意的 解 的集合 ， 從而減輕決策器的負(fù)擔(dān) 。 4、 基于群組決策 西華大學(xué)碩士學(xué)位論文 為多人決策更符合現(xiàn)實(shí)需要，所以我們的模型是在群組決策的基礎(chǔ)上提出來的。 運(yùn)用聚合算子可以非常方便地聚合決策者們的觀點(diǎn)。在模型 中， 我們采用 聚合決策者的語言偏好。 此外， 我 們 用 法 解決具有 離散性的 問題 ，擴(kuò)大了它的應(yīng)用范圍，提高了它的實(shí)用價(jià)值。 我們還充分開發(fā)了誘導(dǎo)變量的新作用 , 使它不但 具有排序 和 計(jì) 算 W 權(quán)重 的任務(wù)，同時(shí)還用它來計(jì)算語言距離，處理 聯(lián)結(jié) 的 為了減輕決策器的負(fù)擔(dān)，提高決策速度，我們還 研究 了該模型的一些屬性并 給予 了證明 。 在文章的最后，我們應(yīng)用 該模型解決了復(fù)雜零件協(xié)同制造中的資源優(yōu)化配置問題，并得到了良好 結(jié)果。 關(guān)鍵詞 ： 多目標(biāo)群組決策， 優(yōu)解， 子， 西華大學(xué)碩士學(xué)位論文 i is a to in a of In we is to a in of At a a s is we a as 1. In it is to a we be a to of 2. is in of In of we 華大學(xué)碩士學(xué)位論文 IV 3. we is to so of of 4. is in so we of we to of in In we to to of to We a of We it to it to WA In to of we of a At we to a of of in 華大學(xué)碩士學(xué)位論文 V 目 錄 1 緒論 . 1 目標(biāo)決策簡(jiǎn)介 . 1 內(nèi)外研究現(xiàn)狀和發(fā)展趨勢(shì) . 1 文內(nèi)容安排及意義 . 4 2 多目標(biāo)決策的預(yù)備知識(shí) . 6 目標(biāo)優(yōu)化的基本概念 . 6 目標(biāo)遺傳算法 . 8 糊群組決策的基本概念 . 13 3 多目標(biāo)群組決策模型 . 21 化器的設(shè)計(jì) . 21 選器的設(shè)計(jì) . 24 策器的設(shè)計(jì) . 28 結(jié) . 35 4 多目標(biāo)群組決策模型的應(yīng)用 . 36 源優(yōu)化配置問題 . 36 化器的設(shè)計(jì) . 41 選器的設(shè)計(jì) . 44 策器的設(shè)計(jì) . 47 結(jié) . 49 5 總結(jié)與展望 . 50 結(jié) . 50 要研究成果 . 51 望 . 52 6 參考文獻(xiàn) . 53 7 作者在讀期間科研成果 . 58 8 聲明 . 59 9 授權(quán)書 . 60 10 致謝 . 61 西華大學(xué)碩士學(xué)位論文 . 1 . 1 . 1 . 4 2 . 6 . 6 . 8 . 13 3 . 21 . 21 . 24 . 28 . 35 4 . 36 . 36 . 41 . 44 . 47 . 49 5 . 50 . 50 . 51 . 52 6 . 53 7 . 58 8 . 59 9 . 60 10 . 61 西華大學(xué)碩士學(xué)位論文 1 1 緒論 目標(biāo)決策簡(jiǎn)介 決策是指為達(dá)到某種目的或目標(biāo)，而在眾多的可行方案中進(jìn)行選擇的過程。它是日常生活的一部分。不論是對(duì)個(gè)人、企業(yè)、或是大型的工程系統(tǒng)和社會(huì)經(jīng)濟(jì)系統(tǒng)，幾乎都存在決策問題。在社會(huì)瞬息萬變的今天，面對(duì)國計(jì)民生、企業(yè)前途等重大的決策，一個(gè)人的智慧是遠(yuǎn)遠(yuǎn)不夠的，它需要相關(guān)人員的群體智慧。如何解決決策者之間的分歧，并最終得到一致的決定是群組決策研究的一個(gè)重點(diǎn)，也是本文的一個(gè)研究方向。 人們所面臨的決策問題可分為兩種：?jiǎn)文繕?biāo)決策和多目標(biāo)決策。所謂單目標(biāo)決策即從眾多的可行方案中，根 據(jù)一個(gè)標(biāo)準(zhǔn)選擇最好的或滿意的方案；如果需按多個(gè)標(biāo)準(zhǔn)來選擇的話，就是多目標(biāo)決策。多目標(biāo)決策問題有許多共同的特點(diǎn)，其中最顯著的是 :目標(biāo)間的不可公度性和矛盾性 1。所謂目標(biāo)間的不可公度性是指各個(gè)目標(biāo)沒有統(tǒng)一的度量標(biāo)準(zhǔn)，因而難以進(jìn)行比較。目標(biāo)間的矛盾性是指如果采用某一種方案去改進(jìn)某一目標(biāo)值，可能會(huì)使另一目標(biāo)的值變好或變壞。由于多個(gè)目標(biāo)之間的矛盾性和不可公度性，因此，不能 簡(jiǎn)單地把多個(gè)目標(biāo)歸并為單個(gè)目標(biāo)，并使用單目標(biāo)決策方法去解決多目標(biāo)決策問題。 但是，在現(xiàn)實(shí)生活中，我們遇到的決策問題大部分又都屬于后者。由于它的普遍性及復(fù)雜性，對(duì)多目標(biāo)決策的研究顯得尤為重要。 多目標(biāo)決策問題的另外一個(gè)顯著特點(diǎn)是無最優(yōu)解。因此，在解決這類問題時(shí)，我們尋找得是令決策者滿意的解。由于問題的復(fù)雜性及決策者對(duì)問題認(rèn)識(shí)的模糊性，要想準(zhǔn)確的表達(dá)偏好是不可能的事情，但是決策者可以輕松得給出類似于某目標(biāo)比某目標(biāo)重要或是某方案比某方案略好的具有模糊語言偏好的二元比較關(guān)系式即偏好信息。針對(duì)有不同類型偏好和不同性質(zhì) 的優(yōu)化問題，存在著不同形式的模型和算法。目前還沒有統(tǒng)一、系統(tǒng)的最佳方法。因此對(duì)具有偏好信息的多目標(biāo)優(yōu)化問題設(shè)計(jì)相應(yīng)的優(yōu)化模型是本文的研究方向。 內(nèi)外研究現(xiàn)狀和發(fā)展趨勢(shì) 多目標(biāo)優(yōu)化的思想可以說是萌芽于 1776 年經(jīng)濟(jì)學(xué)中的效用理論。 1896 年，西華大學(xué)碩士學(xué)位論文 2 經(jīng)濟(jì)學(xué)家 先在經(jīng)濟(jì)平衡的研究中提出了多目標(biāo)優(yōu)化問題，引進(jìn)了被稱為 優(yōu)的概念。 1947 年，數(shù)學(xué)家 對(duì)策論的著作中提及多目標(biāo)決策問題，引起人們對(duì)多目標(biāo)優(yōu)化研究的重視。 1951 年，數(shù)理經(jīng)濟(jì)學(xué)家 生產(chǎn)和分配的效率分析中考慮了多目標(biāo)優(yōu)化問題，引入有效解的定義并得到某些基本結(jié)果，他的工作為多目標(biāo)優(yōu)化學(xué)科奠定了初步的基礎(chǔ)。 20 世紀(jì) 60 年代以來，人們?cè)O(shè)計(jì)了不少求解多目標(biāo)優(yōu)化問題的處理方法，并運(yùn)用它們?nèi)ソ鉀Q各種實(shí)際問題，取得了一定效果。關(guān)于多目標(biāo)優(yōu)化的研究，不論在理論或應(yīng)用方面都迅速、蓬勃地開展起來 2 按照優(yōu)化過程和決策過程的先后順序，多目標(biāo)優(yōu)化問題被分為三大類：先驗(yàn)偏好多目標(biāo)優(yōu)化、局部偏好多目標(biāo)優(yōu)化和后驗(yàn)偏好多目標(biāo)優(yōu) 化 2。 1、先驗(yàn)偏好多目標(biāo)優(yōu) 化是指在求解優(yōu)化問題前，決策者事先提供足夠的偏好信息。優(yōu)化者根據(jù)這些信息構(gòu)造優(yōu)化評(píng)價(jià)函數(shù)或優(yōu)化規(guī)則，將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，從而求得最優(yōu)解。其求解過程如圖 驗(yàn)偏好模型 先驗(yàn)偏好多目標(biāo)優(yōu)化在多目標(biāo)優(yōu)化方法的發(fā)展初期得到了廣泛的研究和應(yīng)用。 和 提出加權(quán)和法，該方法通過加權(quán)函數(shù)將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為以下形式的單目標(biāo)問題進(jìn)行求解（ n 為目標(biāo)函數(shù)個(gè)數(shù)）： 1M i n i m i z e ( x )S u b j e c t t o (1其中權(quán)系數(shù) 0i，用來表示各個(gè)目標(biāo)的相對(duì)重要程度，一般滿足11n 。 加權(quán)和法是經(jīng)典的有效的方法，根據(jù)單目標(biāo)函數(shù)形式的不同，大致分為全偏好信息 決策器 優(yōu)化器 優(yōu)化規(guī)則 結(jié)果 西華大學(xué)碩士學(xué)位論文 3 局加權(quán)法 7簡(jiǎn)單加權(quán)和法 10加權(quán)最大最小法 14此類方法的優(yōu)點(diǎn)是簡(jiǎn)單有效，缺點(diǎn)是需要決策者給出 權(quán)重。當(dāng)決策者對(duì)問題的認(rèn)識(shí)不充分時(shí)，所給的權(quán)重會(huì)有很大的偏差 。 目標(biāo)規(guī)劃法是由 9等人提出的一種方法。該方法中決策者必須根據(jù)待求問題的情況給出每個(gè)目標(biāo)的期望值，并將這些值作為附加約束條件加入原問題，從而使原問題轉(zhuǎn)化為求目標(biāo)函數(shù)值到期望值絕對(duì)偏差最小的問題 20，即 1M i n i m i z e ( x )S u b j e c t t o (1其中，對(duì)第 i 個(gè)目標(biāo)的期望值。如果設(shè)定的期望值在可行域內(nèi)，這種方法可以得到 優(yōu)解，且求解效率較高，其缺點(diǎn)主要是需要決策者事先給出各目標(biāo)函數(shù)的期望值，并需要對(duì)搜索空間的形狀很了解。而且，這種方法對(duì)線性目標(biāo)函數(shù)優(yōu)化問題較為有效，但求解非線性優(yōu)化問題的效率卻不高。 此外還有層次分析法、字典排序法、模糊邏輯法、多屬性效用理論等。 2、局部偏好多目標(biāo)優(yōu)化又叫交互式多目標(biāo)優(yōu)化，即人們通過優(yōu)化者的求解和決策者的決擇相結(jié)合的人機(jī)對(duì)話方式，采用優(yōu)化階段和決策階段反復(fù)交替進(jìn)行，使決策者對(duì)目標(biāo)結(jié)果的偏好逐漸清晰的方法來獲得 最終的滿意解。其求解過程如圖： 部偏好模型 交互式優(yōu)化方法只搜索決策人關(guān)心的區(qū)域，具有計(jì)算量小，決策相對(duì)簡(jiǎn)單等優(yōu)點(diǎn)。缺點(diǎn)是它要求決策者必須始終參與優(yōu)化過程，對(duì)優(yōu)化進(jìn)行控制，這對(duì)于許多決策者來說無疑是不現(xiàn)實(shí)的。比較有名的交互式優(yōu)化方法有 決策器 優(yōu)化器 優(yōu)化規(guī)則 結(jié)果 優(yōu)化結(jié)果 西華大學(xué)碩士學(xué)位論文 4 等人提出的 、移動(dòng)理想點(diǎn)法、基于目標(biāo)間權(quán)衡的多目標(biāo)決策方法等等。 3、后驗(yàn)偏好多目標(biāo)優(yōu)化是在決策者無法給出先驗(yàn)偏好信息和局部偏好信息下提出的一種算法。一 般是先利用某種優(yōu)化算法對(duì)多目標(biāo)優(yōu)化問題進(jìn)行求解，然后，在 優(yōu)解的解集中，根據(jù)決策者的偏好挑選滿意結(jié)果。其求解過程如圖 驗(yàn)偏好模型 由于決策者是在優(yōu)化器給出的優(yōu)化結(jié)果中選擇滿意解，這就使得優(yōu)化器的設(shè)計(jì)非常重要。如果沒有有效的算法生成能覆蓋整個(gè)優(yōu)化問題全部特性的解，那么就有可能遺漏令決策者滿意的解。近幾年許多的研究者在這方面進(jìn)行研究，并涌現(xiàn)出大量的有效的多目標(biāo)優(yōu)化算法。其中，多目 標(biāo)進(jìn)化算法具有不依賴于問題模型、全局最優(yōu)性、隱含并行性及解決非線性問題的魯棒性強(qiáng)等特點(diǎn)，被廣泛應(yīng)用于多目標(biāo)決策領(lǐng)域。 比較典型的算法有多目標(biāo)遺傳算法 (21、小生境 傳算法(22、非支配排序遺傳算法 (3、 4)、強(qiáng)度 化算法 (5、 6)、 檔進(jìn)化策略 (27、多目標(biāo)蟻群算法 28、多目標(biāo)粒子群算法 29等等。 文內(nèi)容安排及意義 本文研究的主要內(nèi)容如下 : 第一章是緒論。首先敘述了多目標(biāo)決策所涉及到的基本概念及多目標(biāo)決策的特點(diǎn)。根據(jù)優(yōu)化和決策的順序，分別從三個(gè)方面綜述了多目標(biāo)決策的研究現(xiàn)狀和發(fā)展趨勢(shì)。并且總結(jié)了本文研究的主要內(nèi)容及意義。 偏好信息 優(yōu)化器 決策器 優(yōu)化結(jié)果 結(jié)果 西華大學(xué)碩士學(xué)位論文 5 第二章是對(duì) 多目標(biāo)決策基本知識(shí)的介紹。主要從優(yōu)化和決策這兩個(gè)方面介紹本文所涉及 到的基本知識(shí)。在優(yōu)化方面，給出了多目標(biāo)優(yōu)化問題模型 和 的定義；對(duì)遺傳算法和多目標(biāo)遺傳算法做 了簡(jiǎn)單的介紹。從決策方面，主要介紹了語言偏好關(guān)系、聚合算子和語言 量詞。 第三章提出多目標(biāo)群 組決策模型。分別設(shè)計(jì)了優(yōu)化器、篩選器、決策器。 第四章將該模型應(yīng)用于復(fù)雜零件 的網(wǎng)絡(luò)化制造中 。 第五章是對(duì)全文的總結(jié)與展望。給出了全文總結(jié)以及本文的研究成果，并提出了進(jìn)一步 的研究 設(shè)想。 本文研究的意義表現(xiàn)在以下兩個(gè)方面： 一是理論上的意義：以往的多目標(biāo)決策研究多集中在優(yōu)化器的設(shè)計(jì)，對(duì)整體的解決方案則很少有人涉及。就算提起，也只是文字上的簡(jiǎn)單介紹。沒有一個(gè)具體的步驟和例子，而且也僅局限在單人決策上。對(duì)于實(shí)際問題可操作性不強(qiáng)。本文 探討 了基于群組決策的多目標(biāo)優(yōu)化完整模型，使得目前的多目標(biāo)決策方法的研究進(jìn)一步完善。 二是實(shí)踐上的意義：本文用給出的模型處理了復(fù)雜零件協(xié)同制造中制造資源優(yōu)化配置問題，得到了令人滿意的結(jié)果。該模型可以作為決策部門在決策中的輔助工具，從而促進(jìn)了科學(xué)管理水平的提高。 西華大學(xué)碩士學(xué)位論文 6 2 多目標(biāo)決策的預(yù)備知識(shí) 多目標(biāo)決策的研究最早可追溯 到 18世紀(jì)。 772年 提出了 對(duì) 多目標(biāo)問題如何協(xié)調(diào)的問題 。 836年從經(jīng)濟(jì) 學(xué)角度提出了多目標(biāo)問題的模型。 896年首次 從數(shù) 學(xué)角度提出了多目標(biāo)最優(yōu)決策問題。多目標(biāo)決策問題越來越受到人們的關(guān)注。 多目標(biāo)決策問題一般 由下 面 5個(gè)基本要 素 1組成： 1、 決策變量 , , , )nx x x x L。 2、 目標(biāo)函數(shù) ) ( ( ) , ( ) , , ( ) ) , 2mx f x f x f x m 3、 可行解集 , ( ) 0 , 1, 2 , , , ( ) 0 , 1, 2 , , n x g x i p h x r q 。 4、 偏好關(guān)系。在像集 ( ) ( ) X x x X有某個(gè)二元關(guān)系反映決策者的偏好。 5、 解的定義。如何在已知的偏好關(guān)系下定義 f 在 X 上的最好解。 其中前三個(gè)要素屬于優(yōu)化部分，后兩個(gè)要素屬于決策部分。 目標(biāo)優(yōu)化的基本概念 一般地，多目標(biāo)優(yōu)化問題 1可描述如下： 定義 目標(biāo)優(yōu)化問題） 12m i n / m a x ( ) ( ( ) , ( ) , , ( ) )( ) 0 , 1 , 2 , , ,s . t . ( ) 0 , 1 , 2 , , ,f x f x f xg x i ph x r q f (2其中 x 為 n 維決策向量，其可行域?yàn)?( ) 0 , 1, 2 , , , ( ) 0 , 1, 2 , , n x g x i p h x r q 與傳統(tǒng)的單目標(biāo)決策不同，在多目標(biāo)決策問題中，通常不存在能使所有目標(biāo)函數(shù)同時(shí)得到優(yōu)化的最優(yōu)解。這是由目標(biāo)之間相互沖突所導(dǎo)致的結(jié)果。此時(shí)，需要考慮的是另一種形式的解 有效解（或非劣解）。下面是對(duì)有效解的定西華大學(xué)碩士學(xué)位論文 7 義 20。 定義 行解集） 可行解集 X 定義為滿足 公 式 ( ) 0 , 1, 2 , , , ( ) 0 , 1, 2 , , n x g x i p h x r q 定義 對(duì)于任意兩個(gè)決策向量 ,a b X （這里討論最小化問題，最大化問題類似）： 1) ( ) 1 , 2 , , : ( ) ( )b a i m f a f b 占 優(yōu) b 當(dāng) 且 僅 當(dāng) 2) ( ) 1 , 2 , , : ( ) ( )b a i m f a f b 弱 占 優(yōu) b 當(dāng) 且 僅 當(dāng) 1 , 2 , , : ( ) ( )m f a f b 且 3) ()a b a b a b b a與 無 差 別 當(dāng) 且 僅 當(dāng) 且: p p。 定義 決策向量 對(duì)于集合 來說為占優(yōu)的（也稱非劣的、有效的或滿意的）當(dāng)且僅當(dāng)： :x A x x p 。如果 x 對(duì)于可行解集 稱 x 為 x 不能再改善任何指標(biāo)性能，否則就會(huì)引起其它至少一項(xiàng)指標(biāo)性能的下降。所有 定義 設(shè)集合 ， () A 中非支配解的集合： ( ) , p A x A x A x x p 則稱集合 () A 的非支配解集，其對(duì)應(yīng)的目標(biāo)向量組成的集合 ( ( )f p A 被稱為 A 的非支配前端。對(duì)于 X 來說，如果 ()pX p X是 稱其對(duì)應(yīng)的目標(biāo)向量組成的集合 ()f X為 曲面（簡(jiǎn)稱 由上述定義可知，多個(gè)目標(biāo)之間的沖突或競(jìng)爭(zhēng)導(dǎo)致多目標(biāo)優(yōu)化問題不存在單一的最優(yōu)解，而是一個(gè) 于實(shí)際的應(yīng)用問題，決策者需要根據(jù)對(duì)問題的了解程度和對(duì)目標(biāo)函數(shù)的偏好，從 而形成最后的決策方案。因此，求解多目標(biāo)優(yōu)化問題的關(guān)鍵之一就是如 何有效地獲取 前，多目標(biāo)進(jìn)化算法被廣泛應(yīng)用于求解 獲得了很好的效果。 西華大學(xué)碩士學(xué)位論文 8 目標(biāo)遺傳算法 傳算法概述 遺傳算法模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任一初始種群出發(fā)，通過隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來越好的區(qū)域，這樣一代一代地不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體，從而求得問題的 最優(yōu)解 30。 遺傳算法的一般流程如下 ： 傳算法流程圖 編碼 初始種群 計(jì)算適應(yīng)值 選擇、交叉、變異 終止 ? 解碼 結(jié)束 實(shí)際問題參數(shù) 華大學(xué)碩士學(xué)位論文 9 1) 編碼與解碼 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問題。在遺傳算法中，對(duì)不同的具體問題進(jìn)行編碼，其編碼的好壞將直接影響選擇、交叉、變異等遺傳運(yùn)算。所謂編碼就是把問題的可行解從解空間轉(zhuǎn)換到遺傳算法處理的搜索空間的轉(zhuǎn)化方法。而由遺傳算法解空間向問題空間的轉(zhuǎn)換稱為解碼。 針對(duì)一個(gè)具體問題，如何設(shè)計(jì)一種完美的編碼方案一直是遺傳算法的應(yīng)用難點(diǎn)。由于遺傳算法應(yīng)用的廣泛性，迄今為止人們已經(jīng)提出了許多種不同的 編碼方法，如二進(jìn)制編碼、格雷碼編碼、浮點(diǎn)數(shù)編碼、多參數(shù)級(jí)聯(lián)編碼等等。 2) 適應(yīng)值計(jì)算 在遺傳算法中使用適應(yīng)度這個(gè)概念來度量群體中個(gè)體的好壞。適用度較高的個(gè)體遺傳到下一代中的概率就較大；而適應(yīng)度較低的個(gè)體遺傳到下一代的概率就相對(duì)較小。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)，由目標(biāo)函數(shù)所確定。適應(yīng)度函數(shù)是非負(fù)的，任何情況下都希望其值越大越好。而目標(biāo)函數(shù)有可能有正有負(fù)，即有時(shí)求最大值，有時(shí)求最小值，因此需要在目標(biāo)函數(shù)與適應(yīng)度函數(shù)之間進(jìn) 行變換。有時(shí)為了計(jì)算方便，也需要對(duì)適用度函數(shù)進(jìn)行變換。因此，適用 度函數(shù)在大部分情況 下都不等于目標(biāo)函數(shù)。 3) 選擇 選擇又稱復(fù)制，是在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新的群體的過程。遺傳算法使用選擇算子來對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作。適應(yīng)度高的個(gè)體被遺傳到下一代的概率大，適宜度低的個(gè)體被遺傳到下一代的概率小。選擇操作的主要目的是為了避免有用遺傳信息的丟失，提高全局收斂性和計(jì)算效率。 選擇算子的好壞將直接影響遺傳算子的計(jì)算結(jié)果。選擇算子選擇不當(dāng)，會(huì)使遺傳算法過早的收斂于局部最優(yōu)解。在遺傳算法的研究中，選擇算子是一個(gè)很重要的研究方向。目前常用的選擇算子有輪盤賭選擇、隨機(jī)競(jìng)爭(zhēng)選擇、最佳保留選擇、 均勻排序、最優(yōu)保存策略、錦標(biāo)賽選擇、排擠選擇等等。 4) 交叉 在生物的自然進(jìn)化過程中，兩個(gè)同源染色體通過交配而重組，形成新的染色體，從而產(chǎn)生出新的個(gè)體或物種。交配重組是生物遺傳和進(jìn)化過程中的一個(gè)西華大學(xué)碩士學(xué)位論文 10 主要環(huán)節(jié)。模仿這個(gè)環(huán)節(jié)，遺傳算法中使用交叉運(yùn)算來產(chǎn)生新的個(gè)體。所謂的交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。 遺傳算法中，在進(jìn)行交叉之前要先對(duì)群體中的父輩個(gè)體進(jìn)行配對(duì)。目前常用的配對(duì)策略是隨機(jī)配對(duì)。交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與具體問題密切相關(guān)。目前比較常用的交叉算子有單點(diǎn)交叉 、兩點(diǎn)及多點(diǎn)交叉、均勻交叉、隨機(jī)交叉、算術(shù)交叉等等。 5) 變異 模仿生物遺傳和進(jìn)化過程中的變異環(huán)節(jié)，遺傳算法中的變異是指以較小的概率對(duì)個(gè)體編碼串上的某個(gè)或某些位置上的值進(jìn)行改變，從而生成新個(gè)體。變異本身是一種隨機(jī)算法，但與選擇、交叉算子結(jié)合后，能夠避免由于選擇和交叉運(yùn)算而造成的某些信息丟失，保證遺傳算法的有效性。 交叉運(yùn)算是產(chǎn)生新個(gè)體的主要方法，它決定了遺傳算法的全局搜索能力；而變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力。交叉算子與變異算子相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜 索。變異算子除了改善遺傳算法的局部搜索能力外，還維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。常用的交叉運(yùn)算有基本位變異、均勻變異、邊界變異、高斯近似變異等等。 目標(biāo)優(yōu)化 算法 概述 對(duì)于求解多目標(biāo)優(yōu)化問 題的 解，目前已有多種基于遺傳算法的求解方法。下面介紹五種常 用的方法 30。 1) 權(quán)重系數(shù)變換法 對(duì)于一個(gè)多目標(biāo)優(yōu)化問題，若給其每個(gè)子目標(biāo)函數(shù) ( ) ( 1 , 2 , , )if x i n賦予權(quán)重 ( 1, 2 , , )iw i n，其中)各個(gè)子目標(biāo)函數(shù) ()1()n w f x (2西華大學(xué)碩士學(xué)位論文 11 若將 u 作為多目標(biāo)優(yōu)化問題的評(píng)價(jià)函數(shù)，則多目標(biāo)優(yōu)化問題就可轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，即可以利用單目標(biāo)優(yōu)化的遺傳算法求解多目標(biāo)優(yōu)化問題。 2) 并列選擇法 并列選擇法的基本思想是，先將群體中的全部個(gè)體按子目標(biāo)函數(shù)的數(shù)目均等地劃分為一些子群體，對(duì)每個(gè)子群體分配一個(gè)子目標(biāo)函數(shù)，各個(gè)子目標(biāo)函數(shù)在相應(yīng)的子群體中獨(dú)立地進(jìn)行選擇運(yùn)算，各自選擇出一些適應(yīng)度高的個(gè)體組成一個(gè)新的子群體，然后再將所有這些新生成的子群體合并成一個(gè)完整的群體，在這個(gè)群體中進(jìn)行交叉和變異運(yùn)算，從而生成下一代的完整群體，如此不斷的進(jìn)行“分割 并列選擇 合并”操作，最終可求出多目標(biāo)優(yōu) 化問題的 解。 3) 排列選擇法 排列選擇法的基本思想是 ，基于 體，對(duì)群 體中的各個(gè)個(gè)體進(jìn)行排序，依據(jù)這個(gè)排序次序來進(jìn)行進(jìn)化過程中的選擇運(yùn)算，從而使得排在前面的最優(yōu)個(gè)體將有更多的機(jī)會(huì)遺傳到下一代群體中。如此這樣經(jīng)過一定代數(shù)的循環(huán)之后，最終就可求出多目標(biāo) 優(yōu)化問題的 4) 共享函數(shù)法 求解多目標(biāo)最優(yōu)化問題時(shí)，一般希望所得到的解能夠盡可能地分散在整個(gè)解集合內(nèi)，而不是集 中在其 解集合內(nèi)的某一個(gè)較小的區(qū)