程序员经验分享-hwhale

布谷鸟算法浅谈与简单应用

2023-05-16

简介

布谷鸟算法是由剑桥大学Xin-She Yang教授和S.Deb于2009年提出的一种新兴的启发算法，是一种通过模拟自然界当中布谷鸟（也就是杜鹃，故该算法也称为杜鹃算法）在繁育后代的行为而提出的一种搜索算法。

本文章将以在工程实践当中的生产车间调度问题为例，对该算法进行一个简单介绍，并给出基于JAVA语言的实现。

原型及流程

布谷鸟算法实际上来源于自然界当中布谷鸟繁育后代的行为。

自然界当中布谷鸟布谷鸟在繁育下一代当中无固定配偶固定配偶，也不自己营巢和孵卵，而是将卵产于大苇莺、麻雀、灰喜鹊、伯劳、棕头鸦雀、北红尾鸲、棕扇尾莺等各类雀形目鸟类巢中，由这些鸟替它带孵带育。

自然，在这些寄生的鸟巢中，有的后代长势较好，有的后代长势较差，也存在部分后代被宿主发现而清除的情况。

后代变为本代后，会在出生点周围随机寻找新的巢穴继续重复繁衍工作。

而布谷鸟算法的核心实际上就是对上述流程的模拟，对其中的一些关键问题进行了一定的约束：

  • 一只布谷鸟只产生一个后代。
  • 后代清除：后代有一定几率会被清除，需要在被清除的后代周围的巢穴重新繁育保持种群数量稳定。
  • 本代寻找新的巢穴的策略：按照莱维飞行规律，进行移动
  • 每一代当中长势最好的后代保留，及仍在上一代繁衍的巢穴中继续繁衍后代。
  • 总种群数量固定。

简单的抽象为带有流程的语言，可以描述为一下步骤：

  1. 有一群初始布谷鸟在宿主鸟的鸟巢下了一组蛋

  2. 计算这些蛋的孵化和生长情况，记录下一代中适应度最好的后代，同时此时下一代适应度最好的个体也是历代中适应度最好的个体。

  3. 下一代生长为本代，本代依据一定的规律（莱维飞行）寻找一组新鸟巢下蛋。注意，本代中在生长期最好的那一只布谷鸟仍在上一代下蛋的地点下蛋。

  4. 按照c的概率，一些蛋被宿主发现并被清除。对于这些蛋，本代需要在这些蛋的周围一些的鸟巢下蛋从而保持总种群数量稳定。

  5. 记录这些蛋的孵化和生长情况，记录本代中适应度最好的后代，若适应度最好的后代比历代中所有的个体适应度都好，则更新历代最好适应度个体。

  6. 若迭代次数超过规定上线，输出历代中适应度最好的个体并结束，否则返回3进入下一代。

在上面的描述当中，实际的下蛋可以被我们理解成为当前解，而“下一代中适应度最好的后代”，则可以被我们理解为当前迭代周期中的最优解，“历代中最好适应度个体”则可以被抽象为全局最优解，即我们想要最终求得的答案。

上述步骤种第四步骤随机抛弃部分解与第五步骤计算适应度的过程，在网上资料中有两种观点。第一种是先计算适应度后抛弃，此种需要在抛弃时避免将本代中适应度最好的解抛弃，第二种是先随机抛弃后计算适应度。实际验证下，从结果来看作者暂未发现两种流程的差异，故两种均应该可行。

莱维飞行

在每轮的后代中，除了最好的后代会继续在当前“巢穴”（当前最优解）中继续繁衍后代外，其余的后代都需要寻找新的“巢穴”，具体在布谷鸟算法中的实际方法是以莱维飞行的路径搜索方案对每组解进行更新。

什么是莱维飞行呢？莱维飞行实际上就是是自然界中鸟类飞行路径，其特点简单来说就是，在一定的移动次数下长移动少，短移动次数多。

若不能理解，想象一下自然界当中猛禽捕食搜索猎物的时候的场景：在一个小区域内短距离频繁的移动搜索猎物，之后突然会移动到离当前距离很远的另一个小区域，之后继续在这个区域进行短距离频繁移动搜索猎物。莱维飞行时的移动与之类似，就是短距离多次移动，长距离少次移动。

莱维飞行的稳定分布积分形式在1937年由P. Levy确定：
L e v y ( s ) = 1 π ∫ 0 + ∞ e x p ( − β ∣ k ∣ λ ) c o s ( k s ) d k Levy(s) = \frac{1}{\pi} \int_0^{+\infty}exp(-\beta |k|^\lambda)cos(ks) dk Levy(s)=π1​∫0+∞​exp(−β∣k∣λ)cos(ks)dk

但对该积分并未有一个明确的解析， 不过当 s ≫ s 0 > 0 ， 即 s → ∞ s\gg s_0 >0，即s \rightarrow \infty s≫s0​>0，即s→∞时:

L e v y ( s ) ≈ λ β Γ ( λ ) s i n ( π λ 2 ) π . 1 s 1 + λ Levy(s) \approx \frac{\lambda \beta \Gamma(\lambda)sin(\frac{\pi \lambda}{2})}{\pi}.\frac{1}{s^{1+\lambda}} Levy(s)≈πλβΓ(λ)sin(2πλ​)​.s1+λ1​

针对上述的近似解，历史上有许多学者根据此提出用于服从莱维分布的随机数实现方法，其中在布谷鸟算法种用于实现的方法主要是采用Mantegna在1994年提出的一种用正态分布求解随机数的方法，有时候也叫Mantegna方法，生成满足莱维分布的随机步长的方法如下：
s = u ∣ v ∣ 1 β s=\frac{u}{|v|^{\frac{1}{\beta}}} s=∣v∣β1​u​
其中 u ～ N ( 0 , σ 2 ) , v ～ N ( 0 , 1 ) u～N(0,\sigma^2) ,v～N(0,1) u～N(0,σ2),v～N(0,1), σ = { Γ ( 1 + β ) s i n ( π β 2 ) Γ ( 1 + β 2 ) 2 β − 1 2 } 1 β \sigma = \{ \frac{\Gamma(1+\beta)sin(\frac{\pi \beta}{2})}{ \Gamma(\frac{1+\beta}{2})2^{\frac{\beta-1}{2}}} \}^{\frac{1}{\beta}} σ={Γ(21+β​)22β−1​Γ(1+β)sin(2πβ​)​}β1​，其中通常 β \beta β取值在1到2之间，为1.5时算法效率最好。

下面给出一个在Matlab种用Mantegna方法模拟二维平面莱维飞行的代码：

% Mantegna方法模拟萊维飞行
% author zhaoyuqiang 
% 参考：https://blog.csdn.net/zyqblog/article/details/80905019
x = [0,0];
y = [0,0];
beta = 1.5;
sigma_u = (gamma(1+beta)*sin(pi*beta/2)/(gamma((1+beta)/2)*beta*2^((beta-1)/2)))^(1/beta);
sigma_v = 1;
for i=1:1000
    u = normrnd(0,sigma_u);
    v = normrnd(0,sigma_v);
    s = u/(abs(v))^(1/beta);
    x(:,1) = x(:,2);
    x(:,2) = x(:,1)+1*s;
    u = normrnd(0,sigma_u);
    v = normrnd(0,sigma_v);
    s = u/(abs(v))^(1/beta);
    y(:,1) = y(:,2);
    y(:,2) = y(:,1)+1*s;
    plot(x,y);
    hold on;
end
axis square;

结果如下图：

U5FdR1.png

不难发现，其与我们之前描述的路径一致，即为短距离移动多，长距离移动少。

使用布谷鸟算法解决作业车间调度问题（JSP）

下面介绍布谷鸟算法在作业车间调度问题上的实际应用。

问题描述

作业车间调度问题（Job Shop Scheduling, JSP）是最经典的几个NP-hard问题之一。其应用领域极其广泛，涉及航母调度，机场飞机调度，港口码头货船调度，汽车加工流水线等。

JSP问题描述：一个加工系统有M台机器，要求加工N个作业，其中，作业i包含工序数为Li。令 L = ∑ i = 1 N k 2 L=\begin{matrix} \sum_{i=1}^N k^2 \end{matrix} L=∑i=1N​k2​，则L为任务集的总工序数。其中，各工序的加工时间已确定，并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化。

作业车间调度在本系统中需要考虑如下约束:

  • C o n s 1 Cons_1 Cons1​：每道工序在指定的机器上加工，且必须在其前一道工序加工完成后才能开始加工；
  • C o n s 2 Cons_2 Cons2​：某一时刻1台机器只能加工1个作业；
  • C o n s 3 Cons_3 Cons3​：每个作业只能在1台机器上加工1次；
  • C o n s 4 Cons_4 Cons4​：各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。

本问题要求算法目标为所有作业加工完成总时间最短

问题的编码与解码

若由n个工件，所有工件最多需要m道工序完成，则JSP的一个可行序列可以被描述成一个 n ∗ m n*m n∗m的整数串。本文先通过一定的操作生成一系列初始编码值，后通过对于编码值进行解码来获取满足约束的可行解序列，通过对于可行解序列的好坏适应度情况评估来对编码值进行算法操作。

下面使用一个 n = 2 n = 2 n=2, m = 3 m = 3 m=3的示例来对编码和解码进行说明。

首先在定义域内随机生成一个 2 ∗ 3 2*3 2∗3 的实数组如 （ 0.3 ， 0.2 ， 0.8 ， 0.1 ， 0.6 ， 0.4 ） （0.3，0.2，0.8，0.1，0.6，0.4） （0.3，0.2，0.8，0.1，0.6，0.4）并对此这些元素按大小排序。规定数值小的顺序靠前且最小的数编号为0，则此时排序结果为：

[2，1，5，0，4，3]

将此数组每个元素分别除以最大工序数 m ，并取下整。则可得到一组可行序列 A ：

A =[0，0，1，0，1，1]

显然，可行序列 A 的加工路线为工件0的第1个工序，工件0的第2个工序，工件1的第1个工序，工件0的第3个工序，工件1的第2个工序，工件1的第3个工序。

如此，我就就通过一个可操作的实数序列转换成一个满足约束条件的工序。

但对于所有工件，其的操作序列可能最大工序次数小于m,我们只需将其正常加入，对于缺少的工序数量我们添加相同数量的且持续时间为0的无关工序即可，在进行计算工序时间时忽略这些持续时间为0的工序即可。

程序流程

算法流程基本同上述部分中描述基本一致，现描述如下：

  1. 读入数据，初始化程序，设定好工件数n，最大工件加工流程m，全局最优序列bestans,全局最优解ansCost，迭代次数step，种群数量Bugu.n。

  2. 随机Bugu.n组初始解，每组解当中存在 n ∗ m n*m n∗m个随机实数。

  3. 遍历初始解，得到当前最少工时数bestCost，与当前最优解下标bestIndex，更新bestans与ansCost。

  4. 若超过迭代次数，进入步骤10，否则继续向下执行。

  5. 对当前所有种群进行莱维飞行，所有解的解空间中的实数。注意对于bestIndex位置的种群不进行更新。

  6. 将25%数量的种群视为无效解，再其周围长度为0.4，方向为0-1均匀分布的正负方向上重新更新该点的值。

  7. 更新当前最优解下标bestIndex与当前最少工时数bestCost。

  8. 更新全局最优解ansCost与全局最优解。

  9. 回到步骤4。

  10. 输出结果。结束。

代码实现（by JAVA）

代码质量并不是特别好，请各位看官见谅。

package jspNew;

import java.util.*;

import org.apache.commons.math3.special.Gamma;

/*
 * 重点关注test类中的myRead方法中对于数据读入的部分。
 * 同时注意在Data类中reVec方法对于结果的返回。
 * 全局最优解 在主流程类Run中的run方法的ansCost中 全局最优机器任务序列，由reVec方法返回
 */

class test{
	public static void myRead() {
		Scanner cin = new Scanner(System.in);
		//全局定义
		Data.n = cin.nextInt(); //TODO 此处需要读取n个工件
		Data.m = cin.nextInt(); //TODO 此处需要读取最大工序数 每个工件最多有m个工序
		Pair[][] t = new Pair[Data.n][Data.m];			//暂存的任务列表
		Bugu.n = cin.nextInt();	//TODO 此处需要读取种群数量
		Bugu.step = cin.nextInt();	//TODO 此处需要读取迭代次数
		//t[0][0] = Pair.make_pair(1, 3);	
		//读取数据
		for(int i = 0 ; i < Data.n ; i++) {
			int tm = cin.nextInt(); //TODO 此处需要读取第i个工件的工序数
			for(int j = 0 ; j < Data.m ; j++) {
				if(j >= tm)
					t[i][j] = Pair.make_pair(0, 0);
				else {
					int a = cin.nextInt(),b = cin.nextInt(); //TODO a是第i个工件 在第j道工序 需要在 a机器上执行 b时间
					t[i][j] = Pair.make_pair(a, b);
				}
			}
		}
		//创建全局工件，并将数组赋值（从暂存的任务列表中获取）
		Data.init(Data.n);
		for(int i = 0 ; i < Data.n ; i++) {
			Data.myData[i] = Data.get_data(t[i]);
		}
//		int[] tans = new int[]{1,2,2,2,0,0,1,0,1};
//		System.out.println(Data.getCost(tans));
	}
}

//实际上是任务类
class Pair{
	public int machine,time;
	Pair(int machine,int time){
		this.machine = machine;
		this.time = time;
	}
	//工厂模式
	static Pair make_pair(int machine,int time) {
		return new Pair(machine,time);
	}
}

//2020年7月11日
class three extends Pair{
	int third;
	three(int a,int b,int c){
		super(a, b);
		third = c;
	}
	static three make_three(int a,int b,int c) {
		return new three(a,b,c);
	}
}

class Data{
	public static Data[] myData;			//全局工件
	public static int n,m;					//全局工件数和最大任务数                                                                                                                                                                                                                                                            任务数量
	public static double Myrandom() {
		return Math.random();
	}
	public static void init(int nn) {
		n = nn;
		myData = new Data[nn];
	}
	public Pair[] task;						//每个工件的任务序列
	public static Data get_data(Pair[] t) {	//返回了一个工件
		Data tt= new Data();
		tt.task = new Pair[m];
		for(int i = 0 ; i < t.length ; i++) {
			tt.task[i] = t[i]; 
		}
		return tt;
	}
	
	public static int getCost(int[] t) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();	//记录每个工件做到了第几个步骤。
		int[] lastRun = new int[n];			//每个工件上个任务的完成时间。
		int[] lastMachine = new int[m];		//每个机器上个工件的完成时间。
		for(int i = 0; i < n ;i++) {
			map.put(i, 0);					//一开始都是第0个步骤。
		}
		int ans = -1;
		for(int i = 0 ; i < t.length ; i++) {
			int now = t[i];					//获取当前的工件编号
			int pairNum = map.get(now);		//获取工件编号的步骤。
			map.remove(now);				//移除工件上一个工件编号。
			map.put(now, pairNum+1);		//更新工件做到的步骤
			Pair nowPair = myData[now].task[pairNum];		//获取当前工件的步骤的任务。
			int nowMachine = nowPair.machine;				//获取任务机器。
			int nowCost = nowPair.time;						//获取任务时间。
			if(nowCost == 0)
				continue;
			int newTime = Math.max(lastMachine[nowMachine], lastRun[now]) + nowCost;	//从当前工件上一个任务结束时间
																						//和待放入机器的最后一个工件完成时间中挑个大的。
			lastMachine[nowMachine] = lastRun[now] = newTime;
//			System.out.println("newTime:" + newTime
//					+" nowMachine:" + nowMachine + 
//					" nowCost:" + nowCost);
			ans = Math.max(ans, newTime);	//获取最长时间
		}
		return ans;
	}
	//2020年7月11日
	static Vector<three>[] reVec(int[] in){
		Vector<three>[] t = new Vector[n*m];
		int[] vis = new int[n];									//工序数
		int[] machineLastTime = new int[m];
		int[] taskLastTime = new int[n];
		for(int i = 0 ; i < t.length ; i++) {
			t[i] = new Vector<three>();
		}
		for(int i = 0 ; i < in.length ; i++) {
			int aim = in[i];
			int index = vis[aim]++;
			int machine = myData[aim].task[index].machine;
			//System.out.println(machine);
			int time = myData[aim].task[index].time;
			//System.out.println(time);
			if(time == 0)
				continue;
			int maxStartTime = taskLastTime[aim] > machineLastTime[machine] ? 
					taskLastTime[aim] : machineLastTime[machine];
			/* System.out.println("aim:"+aim + "\n" + "index:" + index + 
					"\n" + "machine:" + 
					machine + "\n" +"time:" + time + "\n"+"taskLastTime:" +taskLastTime[aim] 
							+ "\n"+"machineLastTime" +machineLastTime[machine]
									+ "\n-------------------------"); */
			taskLastTime[aim] = machineLastTime[machine] = maxStartTime + time;
			t[machine].add(three.make_three(maxStartTime, taskLastTime[aim],aim));
		}
		
		//test
		//System.out.println(m);
		for(int i = 0 ; i < m ; i++) {
			System.out.print("machine "+i + ":" + '\n');
			for(int j = 0 ; j < t[i].size() ; j++)
				System.out.println("task :" + t[i].get(j).third + " start:" + t[i].get(j).machine + " end:" + t[i].get(j).time);
		}
		//TODO 返回了一个Vector数组，以 机器编号为 vector数组下标索引
		//对于每个Vector，中存放了若干个三元组，表示一个机器的 任务序列
		//对于每个任务序列中的每个任务 以 <工件名称,开始任务时间,结束任务时间>储存，
		//三元组的数据结构为three，可见代码中的three部分。
		return t;
	}
}

class see{
	//解码，将编码解码成可行任务序列。
	public static int[] recode(double[] tt) {
		double[]t = new double[tt.length];	//临时数组，防止原数组被改。
		for(int i = 0 ; i < t.length ; i++)
			t[i] = tt[i];
		Map<Double,Integer> map = new HashMap<Double,Integer>();	//记录以下数组编号。
		for(int i = 0 ; i < t.length ; i++)
			map.put(t[i], i);
		Arrays.sort(t);					//排个序
		int[] ans = new int[t.length];	
		for(int i = 0 ; i < t.length ; i++) {
			ans[map.get(t[i])] = i;		//将排序后的顺序填入原来的位置
		}
		for(int i = 0 ; i < t.length ; i++) {
			int t1 = (int)((double)ans[i] / (double)Data.m);
			ans[i] = t1;
		}
//		for(int i = 0 ; i < ans.length ; i++)
//			System.out.println(ans[i]);
//		System.out.println();
		return ans;
	}
	//得到一个从u到v的正态分布
	public static double NormalDistribution(double u,double v){
		java.util.Random random = new java.util.Random();
		return Math.sqrt(v)*random.nextGaussian()+u;
	}
	//得到伽马函数
	public static double getGamma(double t) {
		return Gamma.gamma(t);
	}
	//获取u分布
	static double u,beta = 1.5;;
	private static void getU(){
		u = (getGamma(1.0 + beta)*Math.sin((Math.PI * beta) / 2.0) )
				/ (getGamma(((1.0 + beta) / 2.0) * beta * Math.pow(2.0, (beta - 1.0) / 2.0)));
	}
	//获取步长
	public static double getS() {
		getU();
		double newu = NormalDistribution(0,u);
		double newv = Math.pow(Math.abs(NormalDistribution(0,1)),1.0/beta);
		return newu/newv;
	}
	public static double randomWalk() {
		return  1 * 1 * getD();
	}
	//获取方向 https://blog.csdn.net/sj2050/article/details/98496868#_43
	public static double getD() {
		double r = (int)Data.Myrandom() * (100) + 1;
		if(r < 50) return -1.0;
		return 1.0;
	}
	static public void seeBest(double[] t,int bestCost) {
		System.out.println("本次布谷鸟找到的最优解是：" + bestCost);
		System.out.println("对应的序列是：");
		int[] ansShow = see.recode(t);
		for(int i= 0 ; i < ansShow.length ; i++) {
			System.out.printf("%3d ", ansShow[i]);
		}
		System.out.println();
	}
	static public void seeIndex(double[] t) {
		int[] ansShow = see.recode(t);
		for(int i= 0 ; i < ansShow.length ; i++) {
			System.out.printf("%3d ", ansShow[i]);
		}
		System.out.println();
	}
}

class Bugu{
	static public int n;
	public double []ans;
	static public int step;
	Bugu(int n){
		ans = new double[n];
		for(int i = 0 ; i < n ; i++) {
			ans[i] = Data.Myrandom();
		}
	}
	static public void seeBugu(Bugu[] a) {
		for(int i = 0 ; i < a.length ; i++) {
			System.out.print("bugu["+i+"]:");
			for(int j = 0 ; j < a[i].ans.length ; j++) {
				System.out.print(a[i].ans[j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	
	
}

class run {
	public static void Run() {
		
		test.myRead();
		
		//Bugu.n = 4;
		int[] cost = new int[Bugu.n];
		Bugu[] bugu = new Bugu[Bugu.n];
		double[] bestans = new double[Data.m * Data.n];
		int ansCost = 0x3f3f3f;
		for(int i = 0 ; i < Bugu.n ; i++) {
			bugu[i] = new Bugu(Data.n * Data.m);
			//System.out.println();
			cost[i] = Data.getCost(see.recode(bugu[i].ans));
			//System.out.println(cost[i]);
		}
		
		int bestIndex = -1,bestCost = 0x3f3f3f;
		for(int i = 0 ; i < cost.length ; i++)
				if(cost[i] < bestCost) {
					bestCost = cost[i];
					bestIndex = i;
					for(int k = 0 ; k < bugu[i].ans.length; k++)
						bestans[k] = bugu[i].ans[k];
				}
		ansCost = bestCost;
		
		//see.seeBest(bestans, ansCost);
		//if(ansCost > -1)
		//	return;
		while(Bugu.step > 0) {
			//Bugu.seeBugu(bugu);
			Bugu.step--;
			
			//找个窝下蛋，更新窝的位置。即莱维飞行。
			for(int i = 0 ; i < Bugu.n ; i++) {
				//System.out.println(updata);
				for(int j = 0 ; j < bugu[i].ans.length ; j++) {
					double s = see.getS(),d = see.getD();	//s是步长，d是方向
					double updata = s * d;
					bugu[i].ans[j] += Math.abs(bestIndex - i)*(updata);
					//
				}	
			}
			
			
			
			//在差的解当中，25%的蛋被宿主发现
			for(int i = 0 ; i < Bugu.n ; i++ ) {
				if(Math.random() < 0.25) {
					for(int j = 0 ; j < bugu[i].ans.length ; j++) {
						double newUpdata = see.randomWalk();
						bugu[i].ans[j] += 0.4 * newUpdata;
					}
				}
			}
			
			//寻找本轮最佳
			bestCost = 0x3f3f3f;
			for(int i = 0 ; i < cost.length ; i++) {
				cost[i] = Data.getCost(see.recode(bugu[i].ans));
				//System.out.println("cost[i]:" + cost[i]);
				//see.seeIndex(bugu[i].ans);
				if(cost[i] < bestCost) {
					bestCost = cost[i];
					bestIndex = i;
				}
			}
			
			//本轮最佳比全局最佳好，则更新。
			if(bestCost < ansCost) {
				ansCost = bestCost;
				for(int i = 0 ; i < bestans.length ; i++)
					bestans[i] = bugu[bestIndex].ans[i];
			}
			//see.seeBest(bestans, ansCost);
			//Bugu.seeBugu(bugu);
		}
		//see.seeBest(bestans, ansCost);	//这一行只是用来打印结果的，按需删除
		//ansCost就是全局最优解的值，bestans就是最优解的序列。
		System.out.println("本次布谷鸟找到的最优解是：" + ansCost);
		Data.reVec(see.recode(bestans));
	}
}

public class Jsp {
	public static void main(String[] argv) {
		//test.myRead();
		run.Run();
		//test.print();
	}
}
/*
3
3
4
1000
3
0 3
1 2
2 2
3
0 2
2 1
1 4
2
1 4
2 3
*/

算例结果

现以一个 10 ∗ 5 10*5 10∗5的算例进行测试：

10
5
1000
20000								
5 
1	21	
0	53	
4	95	
3	55	
2	34
5
0	21	
3	52	
4	16	
2	26	
1	71
5 
3	39	
4	98	
1	42	
2	31	
0	12
5 
1	77	
0	55	
4	79	
2	66	
3	77
5 
0	83	
3	34	
2	64	
1	19	
4	37
5 
1	54	
2	43	
4	79	
0	92	
3	62
5 
3	69	
4	77	
1	87	
2	87	
0	93
5
2	38	
0	60	
1	41	
3	24	
4	83
5 
3	17	
1	49	
4	25	
0	44	
2	98
5 
4	77	
3	79	
2	43	
1	75	
0	96

实际上，在种群数量为5，迭代次数为20000次时，已经可以得到总时间为711的最优解，而在上述例子将迭代次数与种群数量大大提高的情况下，结果如下：

本次布谷鸟找到的最优解是：690
machine 0:
task :4 start:0 end:83
task :0 start:83 end:136
task :7 start:156 end:216
task :1 start:216 end:237
task :3 start:237 end:292
task :5 start:292 end:384
task :6 start:390 end:483
task :8 start:483 end:527
task :9 start:527 end:623
task :2 start:656 end:668
machine 1:
task :0 start:0 end:21
task :5 start:21 end:75
task :3 start:75 end:152
task :6 start:154 end:241
task :7 start:241 end:282
task :8 start:282 end:331
task :9 start:331 end:406
task :4 start:406 end:425
task :2 start:546 end:588
task :1 start:588 end:659
machine 2:
task :5 start:75 end:118
task :7 start:118 end:156
task :9 start:196 end:239
task :4 start:239 end:303
task :6 start:303 end:390
task :1 start:423 end:449
task :3 start:449 end:515
task :8 start:527 end:625
task :2 start:625 end:656
task :0 start:656 end:690
machine 3:
task :6 start:0 end:69
task :4 start:83 end:117
task :9 start:117 end:196
task :8 start:196 end:213
task :1 start:237 end:289
task :2 start:289 end:328
task :7 start:328 end:352
task :0 start:352 end:407
task :3 start:515 end:592
task :5 start:592 end:654
machine 4:
task :9 start:0 end:77
task :6 start:77 end:154
task :5 start:154 end:233
task :0 start:233 end:328
task :3 start:328 end:407
task :1 start:407 end:423
task :8 start:423 end:448
task :2 start:448 end:546
task :4 start:546 end:583
task :7 start:583 end:666

不难看出，大大提高了迭代次数确实使结果更加精确，但并没有特别大的提升。

实际上布谷鸟算法对算法中实际参数并不是特别敏感。

算法评价

  • 一种群智能算法，但是同时引入了生物学的进化论
  • 由于莱维飞行的步长满足重尾的稳定分布，因此该搜索机制更为有效
  • 与遗传算法和粒子算法相比，参数更少，更简单。
  • 王凡、贺兴时等已在文献中通过建立CS算法的Markov链模型，理论证明了该算法可收敛于全局最优。

参考资料

布谷鸟搜索算法-百度百科

布谷鸟算法-百度文库

一个例子"入坑"布谷鸟算法(附完整py代码)-SJ2050

通俗易懂的布谷鸟算法与莱维飞行，(附求解函数最小值matlab源码)-孤旅青山迷情人

施文章,韩伟,戴睿闻.模拟退火下布谷鸟算法求解车间作业调度问题[J].计算机工程与应用,2017,53(17):249-253+259.

后记

创作于：2020-07-20
更新于：2021-10-12

大三上学期针对算法设计大作业所学习和实现的代码，后在学年设计中再次使用并进行了改动。之前本文发布于个人博客。

由于是学生时代的产物，必然存在大量的疏忽和错误未被发觉，欢迎大佬前来指正。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

布谷鸟算法浅谈与简单应用 的相关文章

  • 没有实习我是不是就拿不到大厂offer了吗？---校招答疑

    可能是快放寒假了 xff0c 也可能是再有 2 3 个月就要进入 2020 年春招 xff08 应届生春季校招和暑期实习生招聘 xff09 了 越来越多的同学开始问实习的事情了 我认识的 20 届的同学有已经日常实习两个月以上的 xff0c

  • 最新42道计算机网络面试题！-- 附答案

    写在前面 计算机网络 计算机操作系统这两个 兄弟 是所有开发岗位都需要 结拜 的 xff0c 不管你是 Java C 43 43 还是测试 对于后端开发的童鞋来说 xff0c 计算机网络的重要性不亚于语言基础 xff0c 毕竟平时开发经常会

  • 秋招没拿到心仪offer，春招还有机会吗？该如何准备？

    最近很多秋招不理想或者考研不理想的同学问我这样一个问题 xff1a 互联网公司春招还有没有机会 xff1f 其实我相信大部分同学问这个问题的时候 xff0c 心里都是有答案的 xff0c 只不过想找一个他认为可以让他安心的人说出这个答案 那

  • 使用Filezilla Server软件配置FTP的全过程

    博主秋招提前批已拿百度 字节跳动 拼多多 顺丰等公司的offer xff0c 可加微信 xff1a pcwl Java 一起交流秋招面试经验 xff0c 可获得博主的秋招简历和复习笔记 使用Filezilla Server软件配置FTP的全

  • JAVA的四类八种基本数据类型

    先说明两个词汇的基本概念 xff1a bit xff08 位 xff09 xff1a 位是计算机中存储数据的最小单位 xff0c 指二进制数中的一个位数 xff0c 其值为 0 或 1 byte xff08 字节 xff09 xff1a 字

  • 集线器、交换机与路由器有什么区别？

    转发自 xff1a https mp weixin qq com s YXWBw3aFTSEFvkg oN9eQA 我相信我们都玩过一款特别火的游戏 xff1a 帝国时代 小时候想要玩帝国时代 xff0c 需要到软件城购买盗版光盘安装 xf

  • 【leetcode】第5题：最长回文子串

    目 录 一 暴力解法 二 动态规划 三 中心扩展法 四 Manacher 算法 先说明几个概念 xff1a 1 子串 xff1a 小于等于原字符串长度 xff0c 由原字符串中任意个连续 字符组成的子序列 xff1b 2 回文 xff1a

  • 字符串的排列与组合【Java 递归实现】

    我们在笔试中经常会遇到需要对字符串进行排列或者组合的题目 本篇文章对字符串的排列和组合进行递归版本的实现 如果你有更简单易懂的方法 xff0c 一定要在评论区留下来 1 字符串的组合 子序列 题目 xff1a 输入一个字符串 xff0c 输

  • 【手撕代码】多个线程交替打印

    目 录 xff1a 方法一 xff1a 锁实现 推荐 方法二 xff1a 信号量 semaphore 实现 推荐 方法三 xff1a wait notify 实现 方法四 xff1a 使用 Lock Condition 实现 面试的过程中

  • 【搞定算法】找出数组中出现次数大于数组长度一半和 N/K 的数

    博主秋招提前批已拿百度 字节跳动 拼多多 顺丰等公司的offer xff0c 可加微信 xff1a pcwl Java 一起交流秋招面试经验 目 录 xff1a 1 找出数组中出现次数大于数组长度一半的数 2 找出数组中出现次数大于数组长度

  • NVIDIA Jetson Nano 电源适配器 (供电)

    1 Jetson Nano 供电 Jetson Nano 的 micro USB 接口支持 2A 的电流 xff0c DC 供电接口支持 4A 电流 MicroUSB 在安全范围内的最大承载电流为 2A 实际项目中 CPU 满载 43 GP

  • 【搞定算法】常见算法题分类总览

    博主秋招提前批已拿百度 字节跳动 拼多多 顺丰等公司的offer xff0c 可加微信 xff1a pcwl Java 一起交流秋招面试经验 xff0c 可获得博主的秋招简历和复习笔记 完善中 由于本人平时刷题比较零散 xff0c 有时候找

  • 堆、栈的储存内容

    Java的JVM的内存可分为3个区 xff1a 堆 heap 栈 stack 和方法区 method 堆区 1 存储的全部是对象 xff0c 每个对象都包含一个与之对应的class的信息 class的目的是得到操作指令 2 jvm只有一个堆

  • 某32位系统下, C++程序，请计算sizeof 的值.

    某32 位系统下 C 43 43 程序 xff0c 请计算 sizeof 的值 void Foo 1 char str 100 cout lt lt 34 Foo 1 34 lt lt sizeof str lt lt endl char

  • python-pcl安装及使用

    在开始前 xff0c 先说明一下 xff0c pcl的库安装不简单 xff0c 不仅需要pip安装 xff0c 还需要安装C 43 43 的pcl库 xff0c 所以整个流程会比较漫长 鉴于官方参考网站的python pcl太麻烦 xff0

  • ROSBAG解析bag包教程

    一 软件安装教程 1 安装rosbag xff1a https www cnblogs com arkenstone p 6676203 html 2 安装mjepgtools和ffmpeg sudo apt get install mje

  • 双电机同步PID调试方法（二）

    由于双电机的PID上升曲线难以完全重合 xff0c 造成左右电机速度不一致 本文为了解决该问题设计了一种方法 主要思想是将不同速度对应的PWM占空比曲线拟合出来 xff0c 减1000 xff08 总10000 xff09 占空比后作为预设

  • exe打包成安装包

    前面介绍了如何将python代码打包成可执行文件 xff0c 这里再介绍一下如何将exe打包成安装包 一 安装InstallShield2015 百度云网址 xff1a https pan baidu com s 1fFGDeczPduWa

  • Python 打包成 wheel

    1 编写 setup py 在项目的根目录下外面一个文件夹创建 96 setup py 96 96 name 96 xff1a 指的是你打包后发布的名称 xff08 如 96 numpy 96 和 96 torch 96 xff09 96

  • plugins插件使用例程

    最近在看一个pyqt写的工具软件 xff0c 项目中大量使用plugins xff0c 所以了解了一下plugins的功能机制 下面简单分享一个例程 xff0c 代码结构如下 main py platform py init py plug

随机推荐

  • pycharm中.gitignore无效

    1 打开pycharm的命令行 xff0c 输入以下指令 git rm r cached git add 2 再次在pycharm上 xff0c 点击commit 原因 xff1a 这是因为pycharm会自动运行git add 的功能 x

  • Jetson Orin&Nx&Nano平台 FPDlink Ⅲ相机采集---双目场景应用

    1 前言 基于上次在淘宝上采购的FPDlink 相机采集套件使用一段时间之后 不少人对此方案很感兴趣的 又激发了我继续写的激情 上次帖子链接如下 Jetson Orin平台多路 FPDlink 相机采集套装推荐 bingdund的博客 CS

  • SBUS协议：SBUS解析与合成

    在说协议之前 xff0c 我想强调一点 xff1a 信号要取反 xff0c 硬件取反 xff01 xff01 xff01 xff01 xff01 至于为什么强调 xff0c 我会在后面解释 xff0c 你们先记住 SBUS协议 xff1a

  • 上海灵信视觉A4控制板

    资料准备 xff1a 1 LED Player上位机控制 xff1a em span style font size 12px http www 168led com AjaxFile DownLoadFileNew aspx FilePa

  • stm32串口一直进USART1_IRQHandler

    今天在使用USART模块 xff0c 遇到了一些问题并解决了 xff0c 于是发贴共享 问题描述 xff1a 在使用USART做串口通讯时 xff0c 我只把接收中断打开 xff0c 并设置抢占优先级为最低一个级别 xff0c 而接收中断上

  • tensorflow载入报错Process finished with exit code -1073741819 (0xC0000005)

    这几天准备在现有的软件里加上caffe来测试一种新算法 发现windows下python3 6安装caffe是真的难 xff0c 只能装好python2 7的版本就放弃了 回来继续完善软件 xff0c 又发现软件里的tensorflow不能

  • python项目打包(自定义dll) anaconda3+pyinstaller

    目前手上有一个python 43 pyqt的项目需要打包 xff0c 所以查了一下打包的方法 下面介绍一下具体步骤 xff1a python打包有很多方法 xff0c py2exe xff0c pyinstaller等等 xff08 其实我

  • Docker(六)同一镜像有多个Tag情况下，执行 docker rmi 镜像ID 指令无法删除

    删除方法一 docker rmi f 镜像ID 删除方法二 docker rmi repository tag 参考 xff1a 1 https www imooc com article 35040

  • 《ROS机器人开发实践(胡春旭)》第十章MoveIt!机械臂控制 学习笔记

    r 在学习 ROS机器人开发实践 胡春旭 第10章的MoveIt xff01 时 xff0c 因为在自己创建的工作空间中没有下载作者的源代码 xff0c 所有有以下几个问题 xff1a 1 使用moveit setup assistant时

  • Android 根据网络分析运营商信息

    我们想获取手机的运营商信息 通常都会去调用系统的TelephonyManager类的取数据 但是很多时候可能取不到卡的信息 xff08 例如双卡手机和一些特殊卡 xff09 xff0c 这样就区别不了运营商了 但是有时候我们的需求要进行不通

  • 简单又好看的按钮，扁平化按钮。

    今天分享一下流行的扁平化按钮 完全不需要用到图片哦 效果图如下 xff1a 里面有2个按钮都是一样的模式 只要修改的色值就可以 下面跟我来更新你的UI吧 首先编写 button xml 代码如下 lt xml version 61 34 1

  • Android 获取运营商信息（完整版）-解决高通，MTK等双卡问题

    由于国内的运营商问题 xff0c 双卡手机获取IMSI号问题要根据厂商API 来实现 下面我们就来做一套完整的分析运营商获取IMSI号逻辑 1 xff0c 首先我们要判断手机的平台 1 1 xff0c 判断手机是否MTK平台 public

  • AstarPathfindingProject 中RVO碰撞体扩展

    原本库中只有矩形RVO碰撞体 xff0c 如果要添加自己的需要继承RVOObstacle抽象类 xff0c 重写里面的方法 例如下面的圆柱形碰撞 using UnityEngine if UNITY EDITOR using UnityEd

  • Android中抓取手机视频流数据。

    目前实时抓取手机视频数据有2种方法 xff0c 一种是通过camera的回调获取源数据 xff0c 这里获取的源数据是没有编码的数据 有的人发送yuv数据然后在那绘制图片 xff0c 也说视频聊天 xff0c 真是可笑 这种方式是可是实现视

  • Android 使用AudioRecord录音相关和音频文件的封装

    在Android中录音可以用MediaRecord录音 xff0c 操作比较简单 但是不够专业 xff0c 就是不能对音频进行处理 如果要进行音频的实时的处理或者音频的一些封装 就可以用AudioRecord来进行录音了 这里给出一段代码

  • Android 中使用MediaRecorder进行录像详解（视频录制）

    在这里给出自己的一个测试DEMO xff0c 里面注释很详细 简单的视频录制功能 package com video import java io IOException import android app Activity import

  • Android手机中获取手机号码和运营商信息

    代码如下 xff1a package com pei activity import android app Activity import android os Bundle import android view View import

  • C语言下划线开头的函数

    首先 xff0c C 43 43 里关于下划线的问题是源于C语言 xff0c 因为C 43 43 允许用extern C 来修饰代码以C语言语法方式编译 然后说C语言里的下划线 xff1a C语言确实允许以下划线开头的函数存在 xff0c

  • 校验和计算方法

    1 说明 xff1a 1 校验和覆盖的内容 xff1a IP校验和 xff1a IP首部 ICMP校验和 xff1a ICMP首部 43 ICMP数据 xff1b UDP TCP校验和 xff1a 首部 43 数据 43 12个字节伪首部

  • 布谷鸟算法浅谈与简单应用

    简介 布谷鸟算法是由剑桥大学Xin She Yang教授和S Deb于2009年提出的一种新兴的启发算法 xff0c 是一种通过模拟自然界当中布谷鸟 xff08 也就是杜鹃 xff0c 故该算法也称为杜鹃算法 xff09 在繁育后代的行为而

热门标签