求解01背包問題的人工魚群演算法

⑴ 什麼是魚群演算法

artifical fish-warm algorithm
xp(v1,v2……vn)個體的當前位置，d(p,q)=(1/n)*{[v(p,1)-v(q,1)]^2+……[v

(p,n)-v(q,n)]^2}，兩個體的距離，（不知道為什麼用1/n而不是開平方）；visual

一隻魚的感知距離。@擁擠度因子。
第一步：覓食人工魚當前位置為Xi，在可見域內隨機選擇一個位置Xj（d(ij)

<=visual），如xj優於xi向xj前進一步，否則隨機移動一步。如出現不滿足約束則

剪去。X(j+1,k)={if x(i,k)=x(j,k) 不變，else x(j+1,k)=隨機(0,1)}。
第二步：聚群：
xi可見域內共有nf1條魚。形成集合KJi,KJi={Xj|Dij<=visual},if KJi不為空，

then
X(center)=(xj1+xj2+.....xjn)/nf1(xjk屬於kji)
X(center,k)=0,X(center,k)<0.5 1,X(center,k)>=0.5
若：FCc/nf1>@FCi(FCc為中心食物濃度，FCi為Xi點食物濃度)
則：向中心移動：X(i+1,k)=不變，當Xik=X(center,k)時;Xik=隨機（0，1），當

Xik!=X(center,k)時;
若：FCc/nf1<@FCi
則：進行覓食
第三步：追尾
在visual范圍內，某一個體食物濃度最大則稱為Xmax，若：FCmax>@FCi,則向它移動

：X(i+1,k)=當X(i,k)=X(max,k)時，X(i,k)不變，當X(i,k)!=X(max,k)時，X(i,k)=

隨機（0,1）
第四步：公告板
在運算過程中，用公告板始終記錄下最優FCi

⑵ 人工魚群演算法有哪些

具體演算法如下：

1、起源人工魚群演算法是李曉磊等人於2002年在動物群體智能行為研究的基礎上提出的一種新型方盛優化演算法，該演算法根據水域中魚生存數目最多的地方就是本水域中富含營養物質最多的地方這一特點來模擬魚群的覓食行為而實現尋優。

2、演算法主要利用魚的三大基本行為：覓食、聚群和追尾行為，採用自上而下的尋優模式從構造個體的底層行為開始，通過魚群中各個體的局部尋優，達到全局最優值在群體中凸顯出來的目的。

3該方法採用自下而上的尋優思路，首先設計單個個體的感知、行為機制，然後將一個或一群實體放置在環境中，讓他們在環境的交互作用中解決問題。

4、生態學基礎在一片水域中，魚存在的數目最多的地方就是本水域富含營養物質最多的地方，依據這一特點來模仿魚群的覓食、聚群、追尾等行為，從而實現全局最優，這就是魚群演算法的基本思想。魚類活動中，覓食行為、群聚行為、追尾行為和隨機行為與尋優命題的解決有較為密切的關系，如何利用簡單有效的方式來構造和實現這些行為將是演算法實現的主要為題。

5、人工魚的結構模型人工魚是真實魚抽象化、虛擬化的一個實體，其中封裝了自身數據和一系列行為，可以接受環境的刺激信息，做出相應的活動。其所在的環境由問題的解空間和其他人工魚的狀態，它在下一時刻的行為取決於自身的狀態和環境的狀態，並且它還通過自身的活動來影響環境，進而影響其他人工魚的活動。

⑶ 群智能演算法及其應用的圖書目錄

前言 1．1 引言
1．2 蟻群演算法的基本原理
1．3 粒子群優化演算法基本原理
1．4 蟻群演算法理論研究現狀
1．5 蟻群演算法應用研究現狀
1．6 粒子群優化演算法研究現狀
1．7 粒子群演算法應用研究現狀 2．1 求解一般非線性整數規劃的蟻群演算法
2．1．1 引言
2．1．2 求解非線性整數規劃的蟻群演算法
2．1．3 算例分析
2．2 武器—目標分配問題的蟻群演算法
2．2．1 引言
2．2．2 WTA問題
2．2．3 武器—目標分配問題的蟻群演算法
2．2．4 模擬結果j
2．3 多處理機調度問題的蟻群演算法
2．3．1 引言
2．3．2 多處理機調度問題數學模型
2．3．3 解多處理機調度問題模擬退火演算法
2．3．4 解多處理機調度問題蟻群演算法
2．3．5 演算法比較
2．4 可靠性優化的蟻群演算法
2．4．1 引言
2．4．2 最優冗餘優化模型及解法
2．4．3 可靠性優化的模擬退火演算法
2．4．4 可靠性優化的遺傳演算法
2．4．5 可靠性優化的蟻群演算法
2．4．6 算例分析
2．5 求解旅行商問題的多樣信息素的蟻群演算法
2．5．1 信息素更新的3個模型
2．5．2 多樣信息素更新規則
2．5．3 演算法測試
2．6 本章小結 3．1 無約束非線性最優化問題
3．2 連續優化問題的信息量分布函數方法
3．3 一種簡單的連續優化問題的蟻群演算法
3．4 數值分析
3．5 本章小結 4．1 引言
4．2 聚類問題的數學模型
4．3 K均值演算法
4．4 解聚類問題的模擬退火演算法
4．5 基於巡食思想的蟻群聚類演算法
4．6 解聚類問題的新的蟻群演算法及數值分析
4．6．1 解聚類問題的蟻群演算法
4．6．2 數值分析
4．7 解聚類問題的與K-均值演算法混合的蟻群演算法及數值分析
4．7．1 解聚類問題的K-均值演算法混合的蟻群演算法
4．7．2 數值分析
4．8 本章小結 5．1 引言
5．2 解圓排列問題的蟻群模擬退火演算法
5．2．1 圓排列問題及與旅行商問題等價
5．2．2 解旅行商問題的模擬退火演算法
5．2．3 幾種演算法的比較
5．2．4 算例分析
5．3 解旅行商問題的模擬退火蟻群演算法
5．3．1 混合的基本思想
5．3．2 找鄰域解策略
5．3．3 模擬退火蟻群演算法
5．3．4 演算法測試
5．4 本章小結 6．1 引言
6．2 基本遺傳演算法
6．3 蟻群演算法與遺傳演算法的混合
6．3．1 混合的基本思想
6．3．2 變異操作
6．3．3 交叉操作
6．3．4 遺傳蟻群演算法
6．4 演算法測試
6．5本章小結 7．1 引言
7．2 混沌及運動特性
7．3 基本蟻群演算法改進
7．3．1 混沌初始化
7．3．2 選擇較優解
7．3．3 混沌擾動
7．4 混沌蟻群演算法
7．5 演算法測試
7．6 本章小結 8．1 引言
8．2 最短路的蟻群演算法收斂性分析
8．3 模擬算例
8．4 本章小結 9．1 模擬退火思想的粒子群演算法
9．1．1 幾種模擬退火思想的粒子群演算法
9．1．2 演算法測試
9．2 混沌粒子群優化演算法研究
9．2．1 基本粒子群演算法不足
9．2．2 混沌粒子群優化演算法
9．2．3 演算法測試
9．3 其他改進的粒子群優化演算法
9．3．1 雜交PSO演算法
9．3．2 協同PSO演算法
9．3．3 離散PSO演算法
9．4．本章小結 10．1 背包問題的混合粒子群優化演算法
10．1．1 背包問題數學模型
10．1．2 解0-1背包問題的混合粒子群演算法
10．1．3 數值模擬與分析
10．2 指派問題的交叉粒子群優化演算法
10．2．1 求解指派問題的交叉粒子群優化演算法
10．2．2 演算法測試
10．3 武器—目標分配問題的粒子群優化演算法
10．3．1 解武器—目標分配問題的粒子群優化演算法
10．3．2 算例分析
10．4 流水作業調度問題的粒子群演算法
10．4．1 流水作業調度問題
10．4．2 求解流水作業調度問題混合粒子群演算法
10．4．3 演算法測試
10．5 非線性整數規劃的粒子群優化演算法
10．5．1 引言
10．5．2 求解非線性整數規劃的粒子群優化演算法
10．5．3 算例分析
10．6 本章小結 l1．1 引言
11．2 整數規劃形式
1l．3 連續性優化形式
11．4 本章小結 12．1 引言
12．2 求解旅行商問題的混合粒子群優化演算法
12．2．1 混合粒子群演算法思路
12．2．2 變異操作和交叉操作
12．2．3 混合粒子群演算法步驟
12．2．4 演算法測試
12．3 求解旅行商問題的粒子群—蟻群演算法
12．3．1 粒子群—蟻群演算法思想
12．3．2 粒子群—蟻群演算法步驟
12．3．3 演算法測試
12．4 本章小結 13．1 引言
13．2 PSO演算法收斂性分析
13．3 數值模擬
13．4 參數選取
13．5 本章小結 14．1 引言
14．2 魚群演算法基本原理
14．3 人工魚的行為描述
14．4 魚群演算法的應用
14．5 本章小結 附錄A 求解旅行商問題的蟻群基本演算法源程序
附錄B 計算連續性函數的優化的粒子群程序
附錄C 求解旅行商問題的粒子群—蟻群演算法的源程序
參考文獻
……

⑷ 人工魚群演算法與0-1背包問題

把 0 1兩種數值組成的向量作為狀態 也可以轉化為實數

⑸ 01背包問題

請搜索」背包九講「，非常詳細，看前兩講或前三講就可以了，以下是節選前兩講。如果是學競賽的話必須要能看懂。

P01: 01背包問題
題目
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。

注意f[i][v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢後，最終的答案並不一定是f[N] [V]，而是f[N][0..V]的最大值。如果將狀態的定義中的「恰」字去掉，在轉移方程中就要再加入一項f[i][v-1]，這樣就可以保證f[N] [V]就是最後的答案。至於為什麼這樣就可以，由你自己來體會了。

優化空間復雜度
以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。

先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組f [0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i -1][v-c[i]]的值。偽代碼如下：

for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。

總結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間復雜度。

P02: 完全背包問題
題目
有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路
這個問題非常類似於01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}。這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態的時間則不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度是超過O(VN)的。

將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。

一個簡單有效的優化
完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個優化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對於隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個並不能改善最壞情況的復雜度，因為有可能特別設計的數據可以一件物品也去不掉。

轉化為01背包問題求解
既然01背包問題是最基本的背包問題，那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c [i]件，於是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。

更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<V。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個很大的改進。 但我們有更優的O(VN)的演算法。 * O(VN)的演算法 這個演算法使用一維數組，先看偽代碼： <pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]};

你會發現，這個偽代碼與P01的偽代碼只有v的循環次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮「選入第i件物品」這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮「加選一件第i種物品」這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以並且必須採用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。

這個演算法也可以以另外的思路得出。例如，基本思路中的狀態轉移方程可以等價地變形成這種形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，將這個方程用一維數組實現，便得到了上面的偽代碼。

總結
完全背包問題也是一個相當基礎的背包問題，它有兩個狀態轉移方程，分別在「基本思路」以及「O(VN)的演算法「的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎麼得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態規劃題目都思考其方程的意義以及如何得來，是加深對動態規劃的理解、提高動態規劃功力的好方法。

⑹ 用動態規劃演算法和貪婪演算法求解01背包問題的區別

首先這兩個演算法是用來分別解決不同類型的背包問題的，不存在哪個更優的問題。 當一件背包物品可以分割的時候，使用貪心演算法，按物品的單位體積的價值排序，從大到小取即可。 當一件背包物品不可分割的時候，（因為不可分割，所以就算按物品的單位體積的價值大的先取也不一定是最優解）此時使用貪心是不對的，應使用動態規劃。

⑺ 完全背包和01背包問題求解

這個代碼本來就是正確的、標準的，逆推只是為了減少空間而已。

⑻ 動態規劃的01背包問題，求解釋。

注意到原來每次f[i][v]只用了一次,所以現在f[v]相當於原來的f[v],
上次循環保存的f[v]相當於原來的f[i-1][v]
如果從0做到V的話,沒有重復限制,會從v->v+c[i]->v+2*c[i]加上去,本次循環的c[i]也會加上

⑼ 人工魚群演算法的特點

1)具有較快的收斂速度，可以用於解決有實時性要求的問題；
2)對於一些精度要求不高的場合，可以用它快速的得到一個可行解；
3)不需要問題的嚴格機理模型，甚至不需要問題的精確描述，這使得它的應用范圍得以延伸。