调度的三种类型

活动调度 在活动调度基础上通过更改机器上的加工顺序,使至少一个工序可以提前加工,必然导致其他工序完成时间推迟。也就是说,在活动调度中,在保留可行性的前提下,没有任何工序可以插入加工时间表前面的空隙中。

半活动调度 在半活动调度基础上更改机器上的加工顺序,使至少一个工序可以提前加工。

无延迟调度 存在一个工件等待加工时,不存在可用的处于空闲的机器。注意,最优解一般不在无延迟调度内。

调度的三种类型

基于POX交叉的遗传算法求解流水车间调度(J-Shop)问题二

对于一个6个工件,6台机器的流水车间调度问题,程序运行结果如下:

甘特图

下面是主程序、交叉算子程序、计算目标函数值程序,全部程序都可以下载(下载全部程序)。

主程序如下:

clc;
clear;

[jobN, machineN, taskDuration, taskUse, processSize] = readDataFile('ft06.txt');

popSize = 200;
chromLength = jobN * processSize;
pc = 0.85;
pm = 0.05;
maxGen = 100;

bestObjValue = 0;
objValues = zeros(1, maxGen);
avgObjValue = zeros(1, maxGen);
bestChrom = zeros(1, chromLength);

pop = initPop(popSize, chromLength, jobN);
objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse);
fitness = calFitness(objValue);
for gen = 1:maxGen
    pop = selection(pop, fitness);
    pop = crossover(pop, pc, jobN);
    pop = mutation(pop, pm);

    objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse);
    fitness = calFitness(objValue);

    avgObjValue(gen) = sum(objValue) / popSize;
    [objValues, bestObjValue, bestChrom] = bestValue(gen, pop, ...
        objValue, objValues, bestObjValue, bestChrom);
end
fprintf('最优染色体: %s\n', mat2str(bestChrom));
fprintf('最优时间: %d\n', bestObjValue);
figure();
plot(1:maxGen, objValues);
title('种群最优个体目标函数(时间)变化图');
figure();
plot(1:maxGen, avgObjValue);
title('种群目标函数值平均值(时间)变化图');
[taskSTime, taskETime] = calTaskTime(bestChrom, jobN, machineN, ...
    processSize, taskDuration, taskUse);
drawGantt(taskUse, taskSTime, taskETime);

POX交叉算子程序:

function cpop = crossover(pop, pc, jobN)
% 交叉,POX方法
cpop = pop;
for i = 1:2:size(pop, 1)
    if rand < pc
        [p1, p2] = deal(pop(i, :), pop(i+1, :));
        [c1, c2] = deal(p1, p2);
        canJ = randperm(jobN);
        J = canJ(1:randi(jobN-1));
        [c1Lia, c2Lia] = deal(ismember(p1, J), ismember(p2, J));
        [c1(c1Lia), c2(c2Lia)] = deal(p2(c2Lia), p1(c1Lia));
        [cpop(i, :), cpop(i+1, :)] = deal(c1, c2); 
    end
end
end

计算目标函数值程序:

function objValue = calObjValue(pop, jobN, machineN, processSize, taskDuration, taskUse)
% 计算种群目标函数值(总完工时间)
[popSize, ~] = size(pop);
objValue = zeros(1, popSize);
for i = 1:popSize
    [~, taskETime] = calTaskTime(pop(i, :), jobN, machineN, ...
        processSize, taskDuration, taskUse);
    objValue(i) = max(max(taskETime));
end
end

function [taskSTime, taskETime] = calTaskTime(chrom, jobN, machineN, processSize, taskDuration, taskUse) % 计算染色体目标函数值(总完工时间) jobProcess = zeros(1, jobN); machETime = zeros(1, machineN); [taskSTime, taskETime] = deal(zeros(jobN, processSize)); for j = 1:length(chrom) job = chrom(j); jobProcess(job) = jobProcess(job) + 1; process = jobProcess(job); machine = taskUse(job, process); if process == 1 startTime = max([0, machETime(machine)]); else startTime = max([taskETime(job, process-1), machETime(machine)]); end taskSTime(job, process) = startTime; endTime = startTime + taskDuration(job, process); [taskETime(job, process), machETime(machine)] = deal(endTime); end end

基于POX交叉的遗传算法求解流水车间调度(J-Shop)问题一

对于流水车间调度问题,n个工件在m台设备上加工,已知每个工件每个工序使用的机器和每个工件每个工序所用时间,通过决策每个机器上工件的加工顺序和每个工序的开始时间,使完成所有工序所用时间(makespan)最小。具有下列约束:

  1. 不同工件的工序之间没有顺序约束。
  2. 某个工序一旦开始加工就不能中断。
  3. 每个机器在某一时刻只能加工一个工序。
  4. 机器不发生故障。

本文使用基于工序的编码方式,轮盘赌选择方法,POX交叉算子,交换变异算子,通过遗传算法对流水车间调度问题进行求解。

基于工序的编码方式

基于工序的编码方式:这种编码方法中,每个工件的工序都用工件序号表示,根据工件需要在在色体重出现的次数表示工序。对于一个n个工件在m台机器上加工的调度问题,其染色体由n×m个基因组成,每个工件的序号在染色体中出现m次,从左到右扫描染色体,工件序号第k次出现,表示该工件的第k道工序。这种编码方式具有解码和置换染色体后总能得到可行解的优点。

对于3个工件,每个工件3个工序的调度问题,一条染色体的例子及其对应的解释如下(图中注释为[工件-工序]序列,比如3-2表示3号工件第2道工序:

基于工序编码

解码

将染色体看作工序的有序序列,根据工序在该序列上的顺序进行解码。工序的开始时间是该工件紧前工序完工时间和机器紧前工序完工时间中的大值,工序的结束时间是工序的开始时间与工序的加工时间之和。特别的,对于每个工件的第1个工序,由于不存在工件紧前工序,因此开始时间是机器紧前工序完工时间,如果不存在机器紧前工序,那么开始时间为时刻0.工件紧前工序是指该工序所属工件该工序的前1道工序,机器紧前工序是指该工序所用机器该工序的前1道工序。下图展示了各工序的开工时间的判断依据:

基于工序解码

POX交叉算子

POX(precedence operation crossover)交叉算子得到的子代总是可行的。染色体p1 和p2 交叉生成两个子代c1 和c2,交叉过程如下:1)随机划分工件集为两个非空子集J1 和J2;2)复制p1中属于工件集J1 中工件的工序到c1,复制p2中属于工件集J1 中工件的工序到c2,保留它们的位置;3)复制p1中属于工件集J2 中工件的工序到c2,复制p2中属于工件集J2 中工件的工序到c1,保留它们的顺序。

下图展示了一次交叉过程:

POX交叉

轮盘赌选择和交换变异

本文使用轮盘赌选择方法和交换变异的方法。

交换编译的方法是指随机取染色体中的两个基因进行交换。


参考文献:张超勇,饶运清,刘向军,李培根. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程,2004,(23):83-87.

让人改变行动的3个说服原则 | Tali Sharot | TEDxCambridge

注意!本文所有内容都是作者根据Tali Sharot所讲内容归纳而成,不代表Tali Sharot本人立场。

原标题:How to motivate yourself to change your behavior | Tali Sharot | TEDxCambridge

原视频链接:https://www.youtube.com/watch?v=xp0O2vi8DX4

警告的效果很有限。当人们受到警告时,人们多是想关闭接收警告的渠道、逃离、认为自己能够幸免。

人们将自己的立场向积极的方向转变。人们听取积极的语言。

不同年龄段的人听取积极/消极建议的能力

e.g.
医院在进出病房要洗手。一种方案是安装监控探头,但是只有10%的人达到了标准。另一种是用电子板显示洗手过程,有90%的人达到了标准。

电子板

三个激励原则:

  1. 社会激励。人们想要知道别人怎么样,想要比别人更加完美、优秀和成功。突出其他人正在做的事很重要。
  2. 即时奖励。可以奖励自己或他人目前的行动,以更好的应对未来,这是跨越时间的一种方式。
  3. 展示进展。

e.g.

用电效率单:

  1. 社会激励。展示平均水平,邻居中的最高水平。用户会给自己定位,和其他人比较的。
  2. 即时奖励。获得了一个笑脸,有获得两个笑脸的可能。
  3. 展示进展。用折线图展示用电效率随时间的变化。这给人一种控制感,这很重要,大脑总时不断试图找到控制环境的方法,这是大脑做事的原则之一。

用电效率单

单纯形法:格式与迭代

格式

  1. 目标函最大化
  2. 所有约束都是等式(变量的非负限制除外),并且具有非负右端项。
  3. 所有的变量都是非负的。

将不等式转化成带有非负右端项的等式约束 为了把(≤)不等式约束转换成等式约束,在约束的左端添加非负的松弛变量。为了把(≥)不等式约束转换成等式约束,在约束的右端添加非负的剩余变量。

e.g.
将约束6x_1+4x_2≤24转换成6x_1+4x_2+s_1=24,s_1≥0,其中s_1 是松弛变量。
将约束x_1+x_2≥800转换成x_1+x_2−s_2=800,s_2≥0,其中s_2 是剩余变量。

处理无限制变量 将无限制变量用两个非负变量替换。

e.g.
对于无限制变量s转换成s=s_1−s_2,s_1≥0,s_2≥0。

设方程个数为m,变量个数为n,并且m<n,基本解对应解空间中的一个角点,角点的最大数目是:

C_m^n=\frac{n!}{m!(n−m)!}

基本可行解完全确定了代数解空间中的最优解候选点。

设定n−m个变量为零,称为非基变量,剩下的变量称为基变量,解方程得到基本解。

单纯形法的迭代性质

线性规划的最优解只要存在,一定出现在在解空间的角点(corner point)。单纯性算法每次选择一个对目标函数值具有最大改善率的变量,进行迭代,每次迭代与解空间的一个角点对应,沿着解空间的边缘移动。单纯形法通过考查解空间中所有可能的基本可行解(角点)的一小部分,极大的减轻了计算负担。

e.g.

线性规划问题

标准化

标准化

从原点开始迭代,令x_1=0,x_2=0,即x_1,x_2 为非基变量,s_1,s_2,s_3 为基变量,单纯形表如下:

单纯形表1

z行由式z−2x_1−x_2+0s_1+0s_2+0s_3=0确定。

进基变量的确定(单纯性最优性条件) 进基变量将对应于目标方程中那些最大负值系数的变量。

离基变量的确定(单纯性可行性条件) 方程右端项(解列)与进基变量下方约束系数非负数比中最小的一项。

在上图中,进基变量为x_1,离基变量为s_2 (15/0>5/1>24/6)。

高斯-约当计算 在确定进基变量和离基变量后,进行高斯-约当计算。

  1. 在基列中,以进基变量取代离基变量。
  2. 新的枢纽行=当前枢纽行/枢纽元素。
  3. 除枢纽行,其他行新行=当前行-当前行枢轴列的系数x新的数轴行。

(其实就是枢纽元素变成1,该列其他元素变成0)

得到新的单纯形表:

单纯形表2

再次进行高斯、约当计算,得到:

单纯形表3

终止条件 目标函数中所有系数均大于0,目标函数达到了最优。

如下图所示,单纯形法每次迭代与解空间的一个角点对应(1->2->3),每次选择一个对目标函数值具有最大改善率的变量作为进基变量,沿着解空间的边缘移动。而离基变量的计算得到的非负比值实际上是这些约束关于进基变量轴的截距(4,5,∞)。

单纯形法的图形表示

什么是机器学习?

什么是机器学习?

假设用P来评估计算机程序在某任务类T上的性能,若一个程序通过利用经验E在T任务上获得了性能改善,则我们就说关于T和P,程序对E进行了学习。

什么是机器学习

上图中,数据是经验E的来源,能力表示在任务T上的性能改善,机器学习利用从数据中计算得来的经验E来改善任务T上的性能(由P评估)。

什么时候使用机器学习(机器学习的要素)?

  • 存在一些可被学习的模式
  • 模式无法通过编程定义
  • 存在足够的关于这个模式的数据

开始使用MiniZinc

MiniZinc是一个用来描述整数和实数的优化约束和决策问题的语言,它允许用户以接近问题的数学公式的方式编写模型。

MiniZinc界面如下:

MiniZinc IDE

着色问题

首先来看一个简单的着色问题:以州为单位,用3种颜色为澳大利亚地图着色,相邻的两个州不能用同一种颜色。澳大利亚地图如下:

澳大利亚地图

在MiniZinc中写入如下代码:

% 用nc种颜色为澳大利亚地图着色
int: nc = 3;

var 1..nc : wa; var 1..nc: nt; var 1..nc: sa; var 1..nc: q;
var 1..nc : nsw; var 1..nc: v; var 1..nc: t;

constraint wa != nt;
constraint wa != sa;
constraint nt != sa;
constraint nt != q;
constraint sa != q;
constraint sa != nsw;
constraint sa != v;
constraint q != nsw;
constraint nsw != v;

solve satisfy;

output ["wa=\(wa) \t nt=\(nt) \t sa=\(sa)\n",
        "q=\(q) \t nsw=\(nsw) \t v=\(v)\n",
        "t=\(t)\n"];

第一行是注释,注释用%开头。

int: nc = 3; 这一行定义并赋值了nc这个参数,它是int(整数)类型,值为3.

var 1..nc : wa; 这一条语句定义了一个名为wa的决策变量,他的范围是1~nc(都包含),类型是整数。

constraint wa != nt; 这是一条约束,约束以constraint开头,这一条语句的意思是决策变量wa不能与nt相等。

solve satisfy; 这一条语句是表示这是一个满足问题。

output ["wa=\(wa) \t nt=\(nt) \t sa=\(sa)\n",
        "q=\(q) \t nsw=\(nsw) \t v=\(v)\n",
        "t=\(t)\n"];

这是输出语句,在求解之后,我们希望看到求解的结果,\(wa)表示取出wa变量的值并显示。

在界面上点击“Run”按钮,输出如下:

Compiling aust.mzn
Running aust.mzn
wa=3     nt=2    sa=1
q=3      nsw=2   v=3
t=1
----------
Finished in 398msec

最后的----------表示这是一个解。

背包问题

假设我们有一个背包,背包的容量有限。有3中水果(假设是香蕉、苹果和橙子),每种物品都有各自的价值和重量,怎样拿水果可以使背包内水果的价值最大?

背包容量:18

水果 香蕉 苹果 橙子
价值 8 19 29
重量 3 5 8

程序如下:

enum FRUIT = {BANANA, APPLE, ORGANGE};
int: capacity = 18;
array[FRUIT] of int: value = [8, 19, 29];
array[FRUIT] of int: size = [3, 5, 8];

array[FRUIT] of var int: amt;

constraint forall(i in FRUIT)(amt[i] >= 0);
constraint sum(i in FRUIT)(size[i] * amt[i]) <= capacity;

solve maximize sum(i in FRUIT)(value[i] * amt[i]);

output["Amount=", show(amt)];

enum FRUIT = {BANANA, APPLE, ORGANGE}; 这条语句定义并赋值了一个枚举型变量。

此程序还增加了数组变量:array[FRUIT] of int: value = [8, 19, 29];

此外,还用了函数forallsum。以forall函数为例,第1个()内是迭代变量,第2个()内是表达式。

constraint forall(i in FRUIT)(amt[i] >= 0); 语句表示以FRUIT中的量为迭代变量,amt中迭代变量相应的值都不小于0.

建立模型

假设有下面的生产约束模型:

生产多种产品,已知每种产品的利润和生产过程种消耗的资源,每种资源都有限。每种产品生产多少才能使利润最大?

程序如下:

enum PRODUCT;
array[PRODUCT] of float: profit;

enum RESOURCE;
array[RESOURCE] of float: capacity;

array[PRODUCT, RESOURCE] of float: consumption;

array[PRODUCT] of var int: produce;

constraint forall(p in PRODUCT)(produce[p] >= 0);
constraint forall(r in RESOURCE)(
    sum(p in PRODUCT)(consumption[p, r] * produce[p]) <= capacity[r]
    );

solve maximize sum(p in PRODUCT)(profit[p] * produce[p]);

在程序中,一些参数需要使用数据文件给定,在更改数据时只需要更改数据文件即可。模型文件的后缀名为.mzn,数据文件的后缀名为.dzn。数据文件的一个例子如下:

% filename.dzn
PRODUCT = {AP, BP, CP, DP, EP}; 
profit =  [12.0, 16.0, 13.0, 11.0, 14.0]; 
RESOURCE = {AR, BR, CR, DR}; 
capacity = [5567, 3200, 4000, 2800]; 
consumption = [| 1.3, 1.3, 1.3, 0.5
    | 0.1, 1.5, 0.3, 0.1 
    | 1.5, 0.5, 1.0, 1.0 
    | 1.6, 1.4, 1.4, 0.1 
    | 1.8, 0.7, 0.1, 1.6 |];

其中consumption是一个二维数组,其中每行以|开头,最后以|结尾。

k-近邻算法

k-近邻算法(kNN)采用测量不同特征值之间的距离方法进行分类。

使用数据范围:数值型和标称型。
优点:精度高、对异常值不敏感、无数据输入假定。
缺点:计算复杂度高、空间复杂度高。

k-近邻算法的一般流程:

  1. 收集数据。
  2. 准备数据:格式化数据格式、归一化。
  3. 分析数据。
  4. 训练算法:不适用于k-近邻算法。
  5. 测试算法:计算错误率。
  6. 使用算法。

实施步骤:

对未知类别属性的数据集中的每个点依次执行以下操作:

  1. 计算已知类别数据集中的点与当前点之间的距离;
  2. 按照距离递增次序排序;
  3. 选取与当前点距离最小的k个点;
  4. 确定前k个点所在类别的出现频率;
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类。

免疫算法简单介绍

免疫算法的基本步骤:

  1. 抗原识别。输入目标函数和各种约束作为免疫算法的抗原。
  2. 初始抗体生成。随机生成初始抗体种群。
  3. 亲和力计算。计算抗体的适应值。
  4. 免疫处理。免疫处理包括免疫选择、克隆、变异和抑制。
    1. 免疫选择:根据抗体的亲和力选出亲和度较高的抗体。
    2. 克隆:对选出的亲和力较高的抗体进行复制。
    3. 变异:对克隆得到的个体进行交叉、变异操作,使其亲和力发生改变。
    4. 抑制:对变异的抗体进行选择,保留亲和度较高的抗体。
  5. 群体刷新。将免疫选择的抗体和免疫抑制后的抗体组成一个集合,保留其中亲和度较高的抗体,使这些抗体进入新的种群。新的种群中不足的部分随机生成,以增加多样性。

免疫算法流程图:

免疫算法流程图

几种优化算法入门 目录