最优化方法课程大作业实验-流水线问题[元启发及超启发算法]
- 格式：doc
- 大小：586.00 KB
- 文档页数：11
流水线调度问题求解XXX (学号: XXXXXXXX)摘要: 有N个工件同时到达流水线上，给出一个加工顺序排列使得最后一个工件从流水线最后一台机器加工完成所使用总时间最小。
本实验将使用遗传算法作为主体框架，使用元启发与超启发算法对该问题进行优化求解。
关键词: flow shop 多机调度遗传算法元启发式算法超启发式算法1 引言a) 流水车间（Flow Shop ）调度问题是很多实际流水线生产调度问题的简化模型，也是一个典型的NP-hard 问题，因此其研究具有重要的理论意义和工程价值，也是目前研究最广泛的一类典型调度问题。
b) 已知：有n 个工件需要在m台机器上流水加工。
工件上的约束：所有工件均在0时刻释放且在各机器上的加工顺序相同，每个工件在每台机器上只加工一次。
机器上的约束：每个机器某一个时刻最多只能加工一个工件，而且执行过程是非抢占的。
目标：给出调度方案，使调度总完工时间最小。
要求：算法复杂度在多项式时间内。
c) 对于工件加工顺序的排列，可以看成是一段DNA序列，这段DNA序列可以交换片段的位置，可以改变两个碱基对的位置，分别对应基因的交叉与突变。
而给所有排列（基因）一个生存空间，并定期淘汰掉不适应环境（总时间较大的个体），并让基因优良的排列进行繁殖。
不断迭代，经过很多代的选择后，遗传下来的基因一定是更优的。
本文后续部分组织如下。
第2节详细陈述使用的方法，第3节报告实验结果，第4节对讨论本文的方法并总结全文。
2 算法设计遗传算法对于流水线问题，遗传算法相比于其他群智能算法能更加贴近问题，更容易实现，因此我采用了遗传算法对该问题进行求解。
具体设计思路如下：遗传算法就是模拟了自然界中物竞天择，适者生存的法则，通过生物的不断变异和自然选择，遗传留下优秀的基因，淘汰不适应选择条件的基因。
对于工件加工顺序的排列，可以看成是一段DNA序列，第i个碱基对上的编码c表示第i个加工第c个工件。
每个排列可看成一个细菌。
在程序中，我使用一条链表来表示一个DNA链。
这段DNA序列可以交换片段的位置，可以改变两个碱基对的位置，分别对应基因的交叉与突变。
繁殖相当于复制链表并对链表进行交叉互换与碱基对互换。
使用链表表示为片段与碱基的交换提供了方便。
给一个细菌一个生存空间，在初始阶段，细菌会大量地繁殖而导致数量呈指数型地增长。
程序通过随机或贪心生成一条初始的排列，每过一段时间完成一轮繁殖。
当链的数量小于生存容量时，DNA链的每一轮、每一个都会繁殖一条新的链，因此链的数量呈现指数型增长。
当数量大于生存空间的容量时，则需要淘汰一些劣质的DNA链。
淘汰规则有轮盘赌、锦标赛等等，轮盘赌即解更优的留下的概率更大，弱者也有概率留下，而锦标赛是严格的适者生存，留下的都是时间较小的，这里我使用的是锦标赛规则。
对总时间进行排序，杀死并销毁排名在生存榜上排名较后2的DNA链。
并让留下来的DNA链进行下一轮繁殖与竞争。
不断迭代，经过很多代的演化后，遗传下来的基因一定是更优的。
主要代码如下：struct geneNode{ //碱基对,相当于脱氧核苷酸,形成链表int p; //编码，指向的工件号struct geneNode*next; //指向下一个碱基对};GeneNode*createNode(); //新建一个碱基对class Gene{ //每一个基因即生存的个体private:GeneNode*head; //基因的第一个节点int TotalTime; //花费的总时间public:Gene(); //初始化的构造函数Gene(const Gene&b); //拷贝构造函数Gene(GeneNode*dna); //为dna链构造对象Gene(Gene b,int flag); //相当于复制一个b(链是新链,flag 无意义) 复制~Gene(); //析构函数死亡int calculateTotalTime(); //计算总时间GeneNode*copyDNA(GeneNode*p); //复制DNA链void deleteDNA(GeneNode*p); //删除并销毁DNA链bool operator <(const Gene &a) const;GeneNode*recombination(GeneNode*dna);//基因重组void mutation(GeneNode*dna); //基因突变GeneNode*propagate(); //繁殖后代。
先复制一条链，并产生变异void setDNA(GeneNode*i); //设置基因头节点void kill(); //杀死该个体并释放DNA链表的空间void printDNA(GeneNode*i); //将链状DNA递归输出void printGene(); //将基因输出};Gene q[MAX_CAPCITY*2]; //生存空间,物竞天择,适者生存GeneNode*init(); //初始化一个基因夏娃void schedule(); //进行调度，算法的主体涉及DNA链表的操作为数据结构基础，这里不再详解，只对主要的函数schedule进行讲解。
void schedule(){int num = 1;q[0].setDNA(init()); //初始化一个基因夏娃while(num<MAX_CAPCITY){ //数量小于容量，生存空间足够,指数繁殖int tmp = num;for(int i=0;i<tmp;i++,num++){ //一轮繁殖，每一个DNA都产生一个新个体q[tmp+i].setDNA(q[i].propagate());3}}printProcess(0);sort(q,q+num); //排序，保留容量数的个体while(1){ //繁殖一倍淘汰一半for(int i=0;i<MAX_CAPCITY;i++) //保留个体继续繁殖q[MAX_CAPCITY+i].setDNA(q[i].propagate());sort(q,q+MAX_CAPCITY*2);currentTime = clock();if((currentTime-startTime)/CLOCKS_PER_SEC>BREAKTIME) break;//一直运行，直到超时退出printProcess(0);}printProcess(1);q[0].print();}元启发式算法元启发式算法是一个随机化算法，是对启发式规则的改进。
启发式算法是一种确定性算法，对于启发式规则来说，需要找到一种策略，使得任意两个碱基对之间满足该规则约束，贪心算法就是一种典型的启发式算法。
对于元启发来说，基因会发生变异，而且是否发生变异、基因片段交换的位置等都是通过随机生成的，它是随机算法与局部搜索结合的产物。
由于随机的存在，搜索可以跳出局部最优的限制，在整个解空间中搜索。
当迭代的次数趋于无穷大时，理论上元启发式算法可以得到问题最优解。
GeneNode*Gene::propagate(){GeneNode*a = copyDNA(head);if(probability(PROBABILITY1))a = recombination(a);if(probability(PROBABILITY2))mutation(a);return a;}繁殖的时候有PROBABILITY1的概率基因重组，PROBABILITY2的概率发生基因突变，由于遗传算法与自然界生物还是有一定差别，当概率太小时会导致大量无用的重复解，降低算法效率。
因此变异的概率很大。
交叉表示从一个随机的节点开始前后互换。
突变表示任意两个结点的编码内容交换。
GeneNode* Gene::recombination(GeneNode*dna){int a = rand()%n;dna ＝dna[a:n]+dna[0:a-1];return dna;}void Gene::mutation(GeneNode*dna){int a = rand()%n;int b = rand()%n;dna[a] <->dna[b];}4具体实现见代码。
超启发式算法由于元启发算法所搜寻的是问题的解空间，虽然寻优能力强，但是当问题规模一大搜索的效率就会非常的低，因此要使用一个规则库对搜寻进行约束，这便是超启发算法。
超启发算法是对元启发的一种改进，通过一种高层的策略操纵与组合底层的启发式规则。
底层启发式规则包括各种贪心或其他算法，一般由问题专家给出。
这些底层规则组成一个规则库，而高层控制策略通过随机组合底层启发式规则对问题进行求解。
因此，超启发算法通过底层启发式规则剪枝压缩搜索空间，从而提高搜索效率。
为了方便，程序采取了六种常用的贪心策略——时间小的先运行，每次变异时选择一种贪心规则，当交换的片段满足贪心规则时才进行变异，否则递归选取两个新的节点直到基因发生变异。
策略库伪代码StrategyN(){If(变异片段满足贪心规则N) 变异并return；Else strategyN(); //递归直到发生变异}顶层控制策略choose(){probability1: Strategy1();probability2: Strategy2();probability3: Strategy3();probability4: Strategy4();probability5: Strategy5();probability6: Strategy6();}3 实验3.1 实验设置本程序实验环境为Dev C++，平均运行时间6秒左右。
在Dev C++中打开.cpp文件，将＃9-＃15的参数调好（实验用例均使用的默认参数）测试用例文件分别为instance［10-14］，需要将输入文件重定向为相应的用例文件（倒数第三行）。
编译即可运行。
3.2 实验结果元启发算法5测试用例1运行结果测试用例2运行结果6测试用例3运行结果测试用例4运行结果7测试用例5运行结果超启发算法测试用例1运行结果8测试用例2运行结果测试用例3运行结果9测试用例4运行结果测试用例5运行结果由于该算法是随机性算法，因此还是使用表格来统计多次运行的结果测试用例启发式遗传算法运行结果超启发式遗传算法运行结果1 703870387038703870387038703870387038 7038 7038 7038 7038 7038 7038 7038 7038 70382 71667166 7166 7166107166 7166 7188 7166 7166 7166 71667166 7166 7188 7166 7166 7166 7166 7312 7312 7366 7366 7312 7312 73127366 7312 7312 7503 7366 7312 7366 8003 8003 8003 8003 8003 8003 80038003 8003 8003 8003 8003 8003 8003 7720 7720 7720 7720 7720 7847 7720 7720 7738 7738 7822 7720 7720 7738 7727 7720由表格可以看出，启发式遗传算法所得到的解离散度更小，因为对于问题规模不大的情况下，搜索全部解空间得到最优解的概率更大，但是如果问题规模较大时漫无目的的搜索只会导致搜索的效率大大降低。
