<commit_before>---
layout: post
author: Ericson
date: 2015-11-30 22:03
title: 基于多背包问题的人工鱼群算法
category: Algorithm
tag: [algorithm,machinery]
---

待完善<commit_msg>commit<commit_after>---
layout: post
author: Ericson
date: 2015-11-30 22:03
title: 基于多背包问题的人工鱼群算法
category: Algorithm
tag: [algorithm,machinery]
---

人工鱼群算法主要应用于组合优化问题，该算法根据水域中鱼生存数目最多的地方就是本水域中富含营养物质最多的地方这一特性来模拟鱼群的觅食行为而实现寻优。
人工鱼群算法主要利用鱼的三大基本行为：觅食、聚群和追尾行为，采用自上而下的寻优模式从构造个体的底层行为开始，通过鱼群中各个体的底层行为开始，通过鱼群中各个体的局部寻优，达到全局最优值在群体中凸显出来的目的。
人工鱼群算法的行为描述：
<ul>
	<li>觅食行为：设置人工鱼当前状态，并在其感知范围内随机选择另一个状态，如果得到的状态的目标函数大于当前状态，则向新选择得到的状态靠近一步，反之，重新选取新状态，判断是否满足条件，选择次数达到一定数量后，如果仍然不满足条件，则随机移动一步</li>
	<li>聚群行为：人工鱼探索当前邻居内的伙伴数量，并计算伙伴的中心位置，然后把新得到的中心位置的目标函数与当前位置的目标函数相比较，如果中心位置的目标函数优于当前位置的目标函数并且不是很拥挤，则当前位置向中心位置移动一步，否则执行觅食行为</li>
	<li>追尾行为：人工鱼探索周围邻居鱼的最优位置，当最优位置的目标函数值大于当前位置的目标函数值并且不是很拥挤，则当前位置向最优邻居鱼移动一步，否则执行觅食</li>
</ul>
人工鱼群算法步骤：
<ul>
	<li>Step1:设定鱼群的参数，包括鱼群的规模m，最大迭代次数gen，人工鱼的感知范围Visual，最大移动步长step，拥挤度因子d等</li>
	<li>Step2:在参数区间内随机生成m条人工鱼个体作为初始鱼群</li>
	<li>Step3:计算每条鱼的食物浓度函数（目标函数），把最优的值放入公告板中</li>
	<li>Step4:对于每条人工鱼执行以下操作：1.计算出追尾行为、聚群行为的值，采用行为选择策略，选择最优的行为作为鱼的移动方向，缺省行为是觅食行为；2.计算出每条鱼的食物浓度函数（目标函数），其最优值与公告板中的值进行比较，最终公告板中始终保持最优的值</li>
	<li>Step5:判断是否满足结束条件，如果满足就结束，否则转Step4</li>
</ul>
最终的公告板值就是最优值。

多背包问题有很多算法解决，有确定算法和启发式算法，人工鱼群算法是启发式算法，把每个物品当成是人工鱼，m个背包当成是m个鱼群，目标函数就是物品的总价值，由此求得最优值。
{'fraction_non_alphanumeric': 0.12042682926829268, 'fraction_numerical': 0.024390243902439025, 'mean_word_length': 14.091954022988507, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2495336', 'n_tokens_mistral': 1141, 'n_tokens_neox': 1385, 'n_words': 46}