求解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)不需要问题的严格机理模型，甚至不需要问题的精确描述，这使得它的应用范围得以延伸。