隨著全球經(jīng)濟的飛速發(fā)展,人們對于某些復(fù)雜問題處理效率的關(guān)注度日益增長,試圖建立數(shù)學(xué)模型對其進行最優(yōu)化求解。背包問題(KP,Knapsack Problem)作為運籌學(xué)中一類經(jīng)典的組合優(yōu)化問題,已被應(yīng)用于諸多領(lǐng)域。而0-1背包問題(0-1KP)是背包問題中最基本的一個子問題,它有效刻畫最初的設(shè)計狀態(tài)和方程的原始思想,因此所有類型的KP都可以通過0-1KP轉(zhuǎn)化變形,于是對0-1KP的優(yōu)化及高效求解,成為目前研究的重要方向之一。但由于0-1KP實質(zhì)為有約束優(yōu)化問題,易出現(xiàn)非正常編碼個體概率過高,易早熟等現(xiàn)象。本文基于0-1KP自身特點,以基本粒子群算法和雞群算法為出發(fā)點,立足非正常編碼個體、迭代效率和參數(shù)評價這三個主要問題進行處理。主要內(nèi)容如下:首先,對于算法運行中出現(xiàn)的非正常編碼個體,考慮現(xiàn)有貪心算法無法修復(fù)所有個體,為此引入兩種貪心算子GMO和GOO,不僅能對非正常編碼個體修正,更能對正常編碼個體作進一步優(yōu)化,從而顯著提高算法的求解精度和效率。其次,考慮基本粒子群算法(PSO)局部搜索能力較差,易早熟,提出貪心優(yōu)化粒子群算法(GOPSO)。在求解0-1KP時,設(shè)計線性遞減的慣性權(quán)重,通過...

【文章頁數(shù)】：42 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第1章 前言
    1.1 研究背景及意義
    1.2 問題模型
    1.3 國內(nèi)外研究現(xiàn)狀
    1.4 論文內(nèi)容與結(jié)構(gòu)安排
第2章 基本粒子群算法和雞群算法概述
    2.1 基本PSO算法
        2.1.1 算法簡介
        2.1.2 算法原理
        2.1.3 算法設(shè)計及總體流程
    2.2 基本CSO算法
        2.2.1 算法簡介
        2.2.2 算法原理
        2.2.3 算法設(shè)計及總體流程
    2.3 本章小結(jié)
第3章 求解0-1背包問題的貪心優(yōu)化粒子群算法
    3.1 貪心算子的設(shè)計
    3.2 GOPSO算法設(shè)計及總體流程
    3.3 測試用例及環(huán)境描述
    3.4 實驗結(jié)果分析
    3.5 本章小結(jié)
第4章 求解0-1背包問題的離散型雞群優(yōu)化算法
    4.1 離散化策略
    4.2 變異過程
        4.2.1 自適應(yīng)權(quán)重組合變異
        4.2.2 定向變異
    4.3 DCSO算法設(shè)計及總體流程
    4.4 參數(shù)分析
    4.5 測試用例及環(huán)境描述
    4.6 實驗結(jié)果分析
    4.7 本章小結(jié)
第5章 兩種改進算法的對比
    5.1 測試數(shù)據(jù)
    5.2 實驗結(jié)果及對比分析
    5.3 本章小結(jié)
第6章 總結(jié)與展望
    6.1 論文總結(jié)
    6.2 展望
參考文獻
致謝
在學(xué)期間的科研情況



本文編號：3768881