矩形件优化排样问题广泛地出现于机械制造、轻工、家具、造纸、印刷及玻璃切割等领域。近年来，各种智能优化算法(如遗传算法等)与定序列矩形件排样 (Definite sequence rectangle packing, DSRP) 算法相结合成为复合算法，使得排样效果和算法鲁棒性都有了很大的提高[1]。DSRP算法效果越好，复合算法的排样效果也越好，所以，DSRP算法成为有效求解矩形件优化排样问题的关键，国内外许多学者开展了大量研究工作，提出了BL (Bottom left) 算法[2]、下台阶算法[3]和LHL算法[4], [5]（Lowest horizontal line algorithm，最低水平线算法）。但是，由于这些算法自身均具有一定的局限性，实际排样结果并不尽人意。作者在仔细研究目前的DSRP方法的基础上，提出了一个新的算法。实际应用表明，该算法能取得比现有算法更好的排样结果，可以明显提高复合算法的整体优化效果。
1 DSRP问题
复合算法中，矩形件排样优化问题的解可视为所有矩形件编号的任一排列，也即一个排样序列。如果需计算和衡量某解的优化排样效果，只有将该排样序列转换为排样图才有可能，这就是DSRP问题。该问题描述如下：
设排样所用板材(称之为母板)的长为L，宽为W(L≥W )，母板的数量足以排放所有要排的矩形零件。所有待排的矩形件共有k个，第i个矩形件
i
P ，其长为
i
P
L，宽为
i
P
W(l≤i≤k)。优化排样
的基本目标是：按照给定排样序列
i
R(i=1, 2,3, …, k) 和某一排样方法快速生成排样，同时使所需母板数量尽可能少，以提高材料利用率。基本约束条件为：矩形件排入时不能改变方向；矩形件之间不能有相互重迭干涉的部分，也不能超越母板边界。
2 现有DSRP算法分析
矩形件正交排样的解空间是无限的，必须引入使排样图规格化的BL条件，使解的个数变为有限个。作为满足BL条件的DSRP算法，BL算法的缺陷在于很容易出现板材左侧排放偏高的情况。
2005年 工 程 图 学 学 报2005第4期 JOURNAL OF ENGINEERING GRAPHICS No.4
定序列矩形件优化排样新算法
王 菲， 罗意平， 杨 岳， 张晓峰
(中南大学CAD/CAM研究所，长沙 410075)
摘要：针对目前矩形件优化排样方法的不足，提出了一个新的定序列矩形件排样算法。采用对矩形件排入板材后生成的矩形空白区域合并的策略，将矩形件优先排入到位置较低的空白区域中，实现了矩形件的插空摆放，有效的利用了排样过程中已排入矩形件间的空隙。实际应用表明，该算法显著提高了单次排样的材料利用率，得到了较好的排样效果。
给出了算法的具体步骤。
关键词：计算机应用；优化排样；空白区域合并；矩形件
中图分类号：TP 391.72
文献标识码：A 文章编号：1003-0158(2005)04-0047-04
收稿日期：2004-10-19
更重要的是有些排样方案永远无法得到，明显影响了对排样解空间的搜索，优化排样的效果并不理想。下台阶算法除了有和BL 算法一样的固有缺陷外，容易出现板材右侧排放偏高的情况。LHL 算法克服了BL 算法的缺陷，但是并没有利用最高轮廓线以下已排矩形件间的空隙，对优化排样的结果有一定限制。
3 提出的算法
3.1 具体算法
观察已经排放k 个矩形件的排样图可以发现，板材中待排区域可以分解为一系列矩形空白区域。结合BL 条件，第k +1个零件应该排入到最低、最左的而且可以容纳该零件的矩形空白区域中。另外，为了避免矩形空白区域变的过于零散使零件难以排入，需要有相应的合并重组机制。这就是文中提出算法的基本思想。
对任意矩形空白区域i r ，可以由其底边线左顶点（L i r x ,L i r y ）
、底边线右顶点（R i r x ,R i r y ）和区域宽i r W 完全表示。其参数有区域长i r L ，区域高度i r H ，如图1所示。
图1 空白矩形区域的表示和各参数
待排板材中，各空白矩形待排区域按照区域高度升序排列组成的集合称为空白区域集合A 。如果两个区域的区域高度相同，则左侧的空白区域在前。例如，图2中板材中空白区域集合 A ={1r ,2r ,3r ,4r ,5r ,6r ,7r ,8r }。
3.2 算法具体步骤如下
Step1 设置初始空白区域为整个矩形板材；
Step i 每当要排入一个零件i P 时， 在空白区域集A 中开始顺序遍历，对空白区域i r ：
图2 空白区域集A
如果i r L ≥i P L ,i r W ≥i P W ，则依照BL 原则在该区域摆放i P ，并按照规则1更新A ； 否则按照规则2查看是否存在相邻的空白区域。如果存在相邻的空白区域j r ，则按照规则3将i r 与j r 合并重组，更新A ，然后重新遍历A ；如果存在不止一个相邻的空白区域，则选择区域高度较小的区域按照规则3与i r 合并重组，更新A ，然后重新遍历A ；如果不存在相邻的空白区域，则顺序遍历到下一个空白区域1+i r 。
如果遍历A 后仍然没有排放i P ，转下一张板材；
重复上述过程，直至所有零件排放完毕。 规则1
零件i P 按照B L 原则排入空白区域i r (i
r
L
≥i P L , i r W ≥i P W )。生成两个新的区域k
r 和j r ，其中j r 为区域高度较小的区域。如图3所示。
图3 规则1图例
对区域k r L k r x =L i r x ；R k r x =L i r x +i P L ；
L k r y =R k r y =R i r y +i
P W ；k
r W =i
r W -i
P W ；
对区域j r L j r x =L i r x +i P L ；R j r x =R i r x ；
·48· 工 程 图 学 学 报 2005年
Y
L j r y =R j r y =R i r y ； j
r W =i
r W 。
规则2
如果满足下列条件中任一个，则判定空白区域i r 和j r 相邻，其中i r 为区域高度较小的区域。 条件A ：L i r x =L j r x ；R i r x =R j r x ；且
L j r y =L i r y +i r W ；
条件B ：|L i r x -L j r x |=i r L 或|L i r x -L j r x |=j r L ；且
L i r y =L j r y ；i
r W =j
r W ；
条件C ：|L i r x -L j r x |=i r L 或|L i r x -L j r x |=j r L ；且
R i r y +i
r W =R j r y +j
r W ；i
r W ≠j
r W 。
规则3
（1）满足条件A 的空白区域i r 和j r 组合生成的区域k r 有L k r x =L i r x ；R k r x =R i r x ；
L k r y =R k r y =L i r y ； k
r W =i
r W ＋j
r W ；如图4
所示。
图4 规则3(a)图例
（2）满足条件B 的空白区域i r 和j r ，组合生成的区域k r 有L k r x =min{L i r x ,L j r x }；R k r x = max{R i r x ,R j r x }；L k r y =R k r y =L i r y ；
k r W =i r W ；如图5所示。
图5 规则3(b)图例
（3） 对满足条件C 的空白区域i r 和j r ,令m
r 代表i r 和j r 中区域高度较小的区域，n r 代表另一区域；在生成的两个区域h r 和k r 中，k r 为区域高度较小的区域。则
区域h r 有：L h r x =min{L m r x ,L n r x }；R h r x = max{R m r x ,R n r x }；L h r y =R h r y =L n r y ；h r W =n r W ；
区域k r 有：L k r x =L m r x ；R k r x =R m r x ；L k r y =R k r y =L m r y ；k
r W =m
r W -n
r W ；如图6所
示。
图6 规则3(c)图例
3.3 算法分析
图7显示了文中提出的算法与现有DSRP 算法排放策略的不同。由于总是选取最低、最左的空白区域排放矩形件，同时利用合并重组的原则使各空白区域尽可能完整而不显零碎，充分利用了在其它算法中无法使用的已排入矩形件间空白区域，提高了板材的利用率。
(a) 拟排初始示意图 (b) BL 算法
(c) 下台阶算法
(d) LHL 算法 (e) 文中提出的新算法 图7 提出的新算法与现有算法排放方法的区别
4 实际算例
将一个15×40的大矩形分成25个小矩形，
以定宽为40，高度不限的板材上排样，求最小排
Y
Y
Y 第4期 王 菲等：定序列矩形件优化排样新算法 ·49·
样高度[3]。对零件按照宽度降序重新排列序号（长度相同的宽度大的在前），然后按照零件序号顺序排放到板材中。由LHL算法得到的排样高度为20，如图8(a)所示；提出的算法得到的排样高度为18，如图8(b)所示（图中剩余区域用黑色填充显示）。
(a) LHL算法的排样结果(b) 同一问题用新算法获得的排样结果
图8 排样结果图
5 结论
从实际计算结果可见，新算法的排样效果是令人满意的。由于尽可能地利用了矩形件排放产生的空白区域，克服了现有的DSRP算法无法利用已排入零件间空隙的缺陷，提高了单次排样的材料利用率。空白区域集是随排放过程不断更新的，所以它也是一种在线算法。它与遗传算法相结合的复合算法，已成功应用于开发出的矩形件优化排样系统，获得了更优的排样结果。
参考文献
[1] Hopper E, Turton B C H. An empirical investigation of
meta-heuristic and heuristic algorithm for a 2D
packing problem [J]. European Journal of Operational
Research, 2001, 128 (1): 34~57.
[2] Jakobs S. On genetic algorithms for the packing of
polygons [J]. European Journal of Operational Research, 1996, 88(1): 165~181.
[3]Liu Dequan, Teng Hongfei. An improved BL-algorithm
for genetic algorithm of the orthogonal packing of
rectangles [J]. European Journal of Operational Research, 1999, 112(2): 413~420.
[4]贾志欣, 殷国富. 矩形件排样的模拟退火算法求
解[J]. 四川大学学报(工程科学版), 2001, 33(5):
35~38.
[5] Leung T W, Yung C H. Application of genetic search
and simulated annealing to the two-dimensional non-guillotine cutting stock problem [J]. Computers &
Industrial Engineering, 2001, 40(3): 201~204.
A New Algorithm for Definite Sequence Rectangle Packing
WANG Fei, LUO Yi-ping, YANG Yue, ZHANG Xiao-feng
(Institute of CAD/CAM, Central South University, Changsha 410075, China)
Abstract: A novel definite-sequence rectangle pack algorithm is proposed. Applying the strategy of merging unoccupied spaces into a larger one and making the best use of them, rectangle pieces are placed at the lowest fitting position and a notably higher material utilization ratio is obtained. It is proved that a more satisfying optimized packing result can be achieved. The detailed steps of the algorithm are illustrated.
Key words: computer application; optimal layout; unoccupied space merging; rectangle piece
·50· 工 程 图 学 学 报 2005年
我伟大的母校 课程设计报告书 实践课题：动态分区分配 姓名：路人甲 学号：20XXXXXX 指导老师：路人乙 学院：计算及科学与技术学院 课程设计实践时间 2013.3.11~2013.3.22
一．课程设计的目的： 二．设计内容： 三．设计要求： 四．程序流程图 Alloc
Best_fit Worst_fit
Free Show
Main 五．源代码 #include
typedef struct DuLNode//结构指针 { ElemType data; struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 } DuLNode,*DuLinkList;//指针链表 DuLinkList block_first; //头结点 DuLinkList block_last; //尾结点 Status alloc(int);//内存分配 Status free(int); //内存回收 Status Best_fit(int); //最佳适应算法 Status Worst_fit(int);//最差适应算法 void show();//查看分配 Status Initblock();//开创空间表 Status Initblock()//开创带头结点的内存空间链表 { block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.state=Free; return OK; } //分配主存 Status alloc(int ch) { int request = 0; cout<<"请输入需要分配的主存大小(单位:M)："; cin>>request; if(request<0 ||request==0) { cout<<"分配大小不合适，请重试！"< 第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ，称之为可行域（约束域）。 {}1,,e E m =L ，{}1,,e I m m +=L ，{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ，则问题 可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。 矩形件排样程序的实现王晨浩-试题b ————————————————————————————————作者: ————————————————————————————————日期: 矩形件排样程序的实现 王晨浩 摘要 针对样板矩形排样程序的实现问题,本人通过实施FORTRＡN90编程,采用直接明了的数字排列的方式,直观清晰的展现了一个矩形样板中矩形件排样的最优方案。而程序语言本身，结构明朗,层次清晰，适合懂本语言的人斟酌损益和修缮完美；程序运行系统,清晰明朗的输入输出步骤,将程序层序化和普遍化展现淋漓；程序表述方式，人性化的中文语言提示，将程序的可接受度和观赏度大大提高。 本程序采取了通过对板面和具体矩形的数字化展现,通过对整体的数字比较描摹和判定板面的整体矩形排列方式,最终以一个具体的数字排列，实现对矩形排列的宏观显现。关键词:ＦORTＲAN90程序,矩形排列方案，板面矩形设计 一、问题重述 （一) 问题简介 工业上经常需要在一块大板材上下料得到若干个小的矩形件,使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽１5、高无限制的矩形板材上,排列2５块尺寸已知的小矩形,2５块小矩形的尺寸如表1,板材的利用率达10０％,如图１所示。 图1 一种排样方案 表１ 小矩形的尺寸 序号 宽 高 1 1２ 6 2 4 7 ３ ６ 7 ４ 10 ２ ５ 2 ５ ６ 6 4 7 ４ 2 8 ４ 6 9 7 ９ 10 4 5 11 6 4 12 4 6 13 ６ 3 14 4 ５ １5 2 4 16 8 ４ １７ 8 6 1８ 8 3 １９ 6 3 ２0 2 6 ２１ 8 2 22 3 5 2３ ２ ５ 2４ 3 4 ２5 2 4 如果上述排样方案未知，即不知道图1的排法，那么如何将这２5块小矩形按照某种次序排在一个大的板材上呢?目前这仍是一个世界难题。 通常要求在一个排样图中,任何一个矩形件在不超出板材边界的情况下,按照一个排样方案(给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案(解）},{R P D =,其中),,,(21n p p p P =，),,,(21n r r r R =,p i 为矩形件的序号,r i 为排样方式，r i =１表示将矩形件旋转90°， r i =０表示矩形件不旋转。将第i 个矩形件安排在板材上的过程中,均不能再往下、往左移动，则称其满足B Ｌ条件(ｂo ｔtom-l ｅｆｔ-con ｄｉｔｉｏn ，B Ｌ-c ｏｎdition)。 引言 本文主要利用粒子群算法解决连续函数以及离散函数的最小值问题，粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。 惯性权重是标准版本中非常重要的参数，可以用来控制算法的开发()和探索()能力。惯性权重的大小决定了对粒子当前速度继承的多少。较大的惯性权重将使粒子具有较大的速度，从而有较强的探索能力； 较小的惯性权重将使粒子具有较强的开发能力。关于惯性权重的选择一般有常数和时变两种。算法的执行效果很大程度上取决于惯性权重的选取。 本文介绍了粒子群优化算法的基本原理，分析了其特点，并将其应用于函数优化问题求解。此外，本文根据惯性权重对粒子群优化算法性能影响的研究，提 出了三种不同的惯性权重。通过仿真实验，验证了各自的收敛性．同时也说明了惯性权重在粒子群优化算法中有很大的自由度。 一、问题描述 1.1函数优化问题 目标优化问题可以描述为: f(1)S max x ) ( x∈ 或：) min x f(2)S ( x∈ 这里S→称为搜索空间，f(x)→称为目标函数。 (1)式描述的优化问题称为极大化问题，(2)式描述的称为极小化问题。 当把f(x)看成是一序列的函数时，上述的问题就转变为多目标优化问题。 对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于问题种类的繁多、影响因素的复杂，这些数学函数会呈现出不同的数学特征，比如连续的、离散的、凸的、凹的、单峰值的、多峰值的函数等等，经常遇到的函数还有这些不同数学特征的组合，除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况需要通过数值计算方法来进行近似优化计算。尽管人们对这个问题研究了很多年，但至今仍无一种既能处理各种不同的复杂函数、又具有良好求解结果的数值计算方法。特别是当问题的规模比较大时，优化计算时的搜索空间急剧扩大，人们认识到要严格地求出其最优解不太现实。所以需要研究出一种能够在可接受的时间和可接受的精度范围内求出数值函数近似最优解的方法或通用算法。粒子群优化由于其算法的简单，易于实现，无需梯度信息，参数少等特点在连续优化问题和离散优化问题中都表现出了良好的效果，特别是因为其天然的实数编码特点适合于处理实优化问题。近年来成为国际上智能优化领域研究的热门。 1.2粒子群算法基本原理 粒子群优化算法( )是一种基于群体的自适应的搜索优化方法。是由和在1995年提出的。中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为 操 作 系 统 实 验 报 告 课程名称：操作系统 实验题目：首次适应算法 姓名： **** 专业班级： *********** 学号： ************* 指导老师： ***** 一、实验目的 在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。 二、实验要求 1.内存大小初始化 2.可以对内存区进行动态分配，采用首次适应算法来实现 3.可以对已分配的内存块进行回收，并合并相邻的空闲内存块。 三、实验内容 把一个作业装入内存，按照首次适应算法对内存区进行分配，作业结束，回收已分配给该作业的内存块，并合并相邻的空闲内存块。 四、实验结果 运行效果： 1.初始化内存区大小，并添加作业，选择1添加作业 2. 当作业大小超过存储块大小时，分配失败。 3.选择3，可查看内存分配情况 4.选择2回收内存 5.添加新作业 6.回收C作业，相邻的空闲内存块合并。 五、实验总结 首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始查找，直到找到一个大小能满足要求的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区仍留在空闲链中。若从链首到链尾都不能找到一个能满足要求的分区，则此次分配失败。这里，我采用数组的方式，模拟内存分配首次适应算法，动态的为作业分配内存块。可以根据作业名称回收已分配的内存块，当空闲内存块相邻时，则合并。 通过此次的实验，让我对内存分配中首次适应算法更加熟悉，在此基础上，我也测试最佳适应算法（best_fit）和最坏适应算法（worst_fit），并对其进行了比较分析，从比较中我发现，针对同一个问题，解决的方法不止一种，而且不同的方法所要消耗的资源和时间也不相同，根据不同的要求，方法的优劣也不同，可以说方法是解决问题的一种模式，随环境不同而体现出优越性。 六、实验附录 程序源代码： #include 矩形件排样程序实现（要求：只能由一个学生独立完成，不得抄袭）工业上经常需要在一块大板材上下料得到若干个小的矩形件，使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽40、高15的矩形板材上，排列25块尺寸已知的小矩形，25块小矩形的尺寸如表1，板材的利用率达100%，如图1所示。 图1 一种排样方案 表1 小矩形的尺寸 序号宽高 1 1 2 6 2 4 7 3 6 7 4 10 2 5 2 5 6 6 4 7 4 2 8 4 6 9 7 9 10 4 5 11 6 4 12 4 6 13 6 3 14 4 5 15 2 4 16 8 4 17 8 6 18 8 3 19 6 3 20 2 6 21 8 2 22 3 5 23 2 5 24 3 4 25 2 4 如果上述排样方案未知，即不知道图1的排法，那么如何将这25块小矩形 按照某种次序排在一个大的板材上呢？目前这仍是一个世界难题。 通常要求在一个排样图中，任何一个矩形件在不超出板材边界的情况下，按照一个排样方案（给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案（解）},{R P D =，其中),,,(21n p p p P =，),,,(21n r r r R =，p i 为矩形件的序号，r i 为排样方式，r i =1表示将矩形件旋转90°, r i =0表示矩形件不旋转。将第i 个矩形件安排在板材上的过程中，均不能再往下、往左移动，则称其满足BL 条件（bottom-left-condition ，BL-condition ）。 基于BL 条件，有一种下台阶算法，具体步骤如下： (1) 将零件1p 排放在板材的左下角，若11=r 则将其旋转90°后再排放，求出排放后所占板材的最大高度； (2) 将i p ),,3,2(n i =根据其排样方式置于板材右边最大高度处，向下向左移动i p ，且向下移动优先（即原本已无法再向下移动，故开始向左移动，而在向左移动的过程中若发现又能继续向下移动，则先向下移动），直至i p 无法向下向左移动为止（即接触到其他零件或板材边界），并求出此时的最大高度； (3) 重复上述过程，直至所有零件排放完毕，最后所得最大高度即为所需板材高度。 其排样过程如图2所示，就好象下台阶一样，于是形象地称之为下台阶算法。 图2 下台阶算法的排样过程 剩余矩形排样法是目前所提出的一种有效的排样算法，该方法记录了所有可利用的空间，更能合理地分配给待排样的矩形件，提高了每个排样方案的板材利用率，更接近最优排样方案。例如对于同一个矩形件序列)4,3,2,1(进行排样， x zD 天津大学《最优化方法》复习题(含答案) 第一章 概述(包括凸规划) 判断与填空题 arg max f(x)二 arg min 以儿 “ max(x): x D 二 R n 』=-min(x): x D 二 R n ； 设f : D 5 R n > R.若x ： R n ，对于一切R n 恒有f(x”)^f(x)，则称x”为 设f : D 5 R n >R.若x ” ? D ,存在x ”的某邻域N ；(x”)，使得对一切 x ?N .(x)恒有f(x”)：：： f (x)，则称x”为最优化问题 min f (x)的严格局部最 优解? 给定一个最优化问题，那么它的最优值是一个定值 ? V 非空集合D R n 为凸集当且仅当 D 中任意两点连线段上任一点属于 D . V 非空集合D R n 为凸集当且仅当D 中任意有限个点的凸组合仍属于 D . V 任意两个凸集的并集为凸集? 函数f:D R n >R 为凸集D 上的凸函数当且仅当 -f 为D 上的凹函数? V 设f : D R n >R 为凸集D 上的可微凸函数，X ：D ?则对-D ,有 f (x) - f(x )乞 f (x )T (X —X )? 若c(x)是凹函数，则 D={x^R n C(x)启0}是凸集。 V f(x)的算法A 产生的迭代序列，假设算法 A 为下降算法, 则对-k ? 5,1, 2,…匚恒有 ________________ f(x k1)乞 f(x k ) ______________ ? 算法迭代时的终止准则(写出三种) ： ___________________________________________________ 凸规划的全体极小点组成的集合是凸集。 V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 矩形件排样程序的实现 王晨浩 摘要 针对样板矩形排样程序的实现问题，本人通过实施FORTRAN90编程，采用直接明了的数字排列的方式，直观清晰的展现了一个矩形样板中矩形件排样的最优方案。而程序语言本身，结构明朗，层次清晰，适合懂本语言的人斟酌损益和修缮完美；程序运行系统，清晰明朗的输入输出步骤，将程序层序化和普遍化展现淋漓；程序表述方式，人性化的中文语言提示，将程序的可接受度和观赏度大大提高。 本程序采取了通过对板面和具体矩形的数字化展现，通过对整体的数字比较描摹和判定板面的整体矩形排列方式，最终以一个具体的数字排列，实现对矩形排列的宏观显现。关键词：FORTRAN90程序，矩形排列方案，板面矩形设计 一、问题重述 （一）问题简介 工业上经常需要在一块大板材上下料得到若干个小的矩形件，使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽15、高无限制的矩形板材上，排列25块尺寸已知的小矩形，25块小矩形的尺寸如表1，板材的利用率达100%，如图1所示。 图1 一种排样方案 表1 小矩形的尺寸 序号 宽 高 1 12 6 2 4 7 3 6 7 4 10 2 5 2 5 6 6 4 7 4 2 8 4 6 9 7 9 10 4 5 11 6 4 12 4 6 13 6 3 14 4 5 15 2 4 16 8 4 17 8 6 18 8 3 19 6 3 20 2 6 21 8 2 22 3 5 23 2 5 24 3 4 25 2 4 如果上述排样方案未知，即不知道图1的排法，那么如何将这25块小矩形按照某种次序排在一个大的板材上呢？目前这仍是一个世界难题。 通常要求在一个排样图中，任何一个矩形件在不超出板材边界的情况下，按照一个排样方案（给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案（解）},{R P D =，其中),,,(21n p p p P =，),,,(21n r r r R =，p i 为矩形件的序号，r i 为排样方式，r i =1表示将矩形件旋转90°, r i =0表示矩 形件不旋转。将第i 个矩形件安排在板材上的过程中，均不能再往下、往左移动，则称其满足BL 条件（bottom-left-condition ，BL-condition ）。 《最优化算法》实验指导书1 一、实验名称：Lingo软件的介绍及使用 二、实验目的： 熟悉LINGO软件的使用方法、功能，会求解一般线性规划问题和简单非线性规划模型。针对实际问题，会建立线性规划模型并求解。 三、实验内容 1、熟悉LINGO软件的启动步骤。 2、熟悉LINGO软件的各菜单、命令按钮的作用。 3、学会如何使用LINGO的帮助文件。 4、学会输入线性规划模型和简单非线性规划模型的基本格式，并能看懂求 解结果。 四、实验步骤 1启动LINGO软件的步骤。当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口： 外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口 之下。在主窗口内的标题为LINGO Model –LINGO1的窗口是LINGO的默认模型窗口，建立 的模型都要在该窗口内编码实现。 LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题。模 型中所需数据可以以一定的格式保存在独立的文件中。 下面举两个例子。 2、示例：用LINGO求解线性规划 12 12 12 12 min z2x2x 2x5x12 s.t.x2x10 x,x0 =+ +≥ ? ? +≤ ? ?≥ ? 则在LINGO的模型窗口中输入如下代码：min=2*x1+2*x2; 2*x1+5*x2>=12; x1+2*x2<=10; 注：（1）在输入目标函数时，因变量Z可不要输，只输“＝”及后面表达式； （2）用＊号表示乘号 （3）每一个约束条件或目标函数后用分号“；”结束； （4）非负约束可以不要输入，软件默认变量是非负的。 （5）可以用“！”开始写说明语句，但说明语句后也要用分号“；”结束。 然后点击工具条上的运行图标，屏幕上出现 Rows= 3 Vars= 2 No. integer vars= 0 ( all are linear) Nonzeros= 8 Constraint nonz= 4( 1 are +- 1) Density=0.889 Smallest and largest elements in abs value= 1.00000 12.0000 No. < : 1 No. =: 0 No. > : 1, Obj=MIN, GUBs <= 1 Single cols= 0 (以上这段是对模型的描述) Optimal solution found at step（最优解在第1步被找到）: 1 Objective value（目标函数值）: 4.800000 （下列显示的是最优解） Variable(变量) Value（值） Reduced Cost （缩减成本系数） X1 0.0000000 1.200000 X2 2.400000 0.0000000 （下列显示的是松驰变量或剩余变量） Row Slack or Surplus Dual Price （行）（松弛变量或剩余变量）（检验数，对偶问题的解） 1 4.800000 -1.000000 2 0.0000000 -0.4000000 3 5.200000 0.0000000 结论：原规划的最优解是x1=0，x2=2.4；最优值为4.8 注释： Reduced cost 是指缩减成本系数，基变量的一定为0，对非基变量表示该变量每增加一个单位，目标函数值减少的量（对求解max的函数而言）。 Dual price 对偶价格，表示当对应的约束有微小变动时，目标函数的变化率。 3、LINGO软件的菜单命令（LINGO WINDOWS命令） （一）文件菜单（File Menu） （1）新建（New） 从文件菜单中选用“新建”命令、单击“新建”按钮或直接按F2键可以创建一个新的“Model”窗口。在这个新的“Model”窗口中能够输入所要求解的模型。 （2）打开（Open） 从文件菜单中选用“打开”命令、单击“打开”按钮或直接按F3键可以打开一个已经存在的文本文件。这个文件可能是一个Model文件。 （3）保存(Save) 从文件菜单中选用“保存”命令、单击“保存”按钮或直接按F4键用来保存当前活动窗口（最前台的窗口）中的模型结果、命令序列等保存为文件。 第26卷第1期2005年2月 青岛科技大学学报 Jour nal ofQ i n gdao University o f Science and Techno logy V o.l26No.1 Feb.2005 文章编号:1672-6987(2005)01-0065-05 二维矩形排样问题的启发式算法 邵巍,隋树林,杜军威 (青岛科技大学自动化与电子工程学院,山东青岛266042) 摘要:矩形件优化排样问题具有多个算法,但是这些算法均有一些局限性,如排列不规则,计算量巨大等等。本文给出了单一尺寸的矩形排样问题的几种启发式算法,它克服了现有众多排样算法执行效率低的缺陷,使板料排样的执行效率和优化率均得以显著提高,并用D elphi编程实现,可直接应用于实际问题中。 关键词:排样问题;启发式算法;De l p h i 中图分类号:TP391文献标识码:A So m e K i nd of A lgorith m s for the Opti m al Layout of Rectangul ar Part S HAO W e,i SU I Shu-li n,DU Jun-we i (College ofAu t o m ati on and E l ectron i c E ngi neeri ng,Q i ngdao U nivers it y of Sci en ce and T echnol ogy,Q i ngdao266042,Ch i na) A bstract:There are l o t o f algor ith m s on the opti m al layout o f rectancular par,t butm ost of the a l g orit h m s have som e li m its(such as irregu lar arrange m en,t excessive ca lculating,etc.). K inds o f heuristic algorithm is g iven i n th is paper.It overco m es sone proble m s for m ost o f a l g o-rithm s at a lo w executi n g rate can high ly enhance the executive rate and i n crease the radio of the opti m izati o n.It carried it out w ith De l p h i language,these a l g orith m s can be used w e ll in practice. K ey words:layou;t heuristic algorithm;Delphi 切割(cuttingprob le m)和装填问题(pack i n g-proble m)统称为布局问题,属于复杂的组合最优化范畴,已经证明即使是最简单的布局问题,也是NP完全问题,因此,绝大部分有效的解决布局问题的算法都是启发式的方法[1~6]。由于许多企业应用板材数量巨大,所以提高很少的利用率便可节省很多原材料,大大降低成本。本工作针对现有众多排样算法执行效率低的缺陷,给出了单一尺寸的矩形排样问题的几种启发式算法。 1数学模型的建立及算法 设在L*W(分别记各边为上L,下L,左W,右W)的矩形内放入a*b的小矩形,不妨设a\b,要使得大矩形中放入尽量多的小矩形。 1.1方法1 先设在下L边上排列n个a,m个b,自下到上依次排列各矩形,并记在垂直方向上堆放t个b,k个a,尽量使得W方向排列尽量多的小矩形,直到不能再放置a或b边,如图1(a)所示。 此种排法的约束条件可描述为: L-b 首次适应算法,最佳适应算法,最坏适应算法源代码[宝典] 首次适应算法,最佳适应算法,最坏适应算法源代码#include void show();//查看分配 Status Initblock();//开创空间表 Status Initblock()//开创带头结点的内存空间链表{ block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.state=Free; return OK; } //分配主存 Status alloc(int ch) { int request = 0; cout<<"请输入需要分配的主存大小(单位:KB):"; cin>>request; if(request<0 ||request==0) { cout<<"分配大小不合适，请重试～"< 第三章 牛顿法 §3.1 最速下降法 一、最速下降法 在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向，产生的算法称为最速下降法，它是无约束最优化算法中最简单、最基本的算法。 算法描述： 1） 给出初始点0n x R ∈，允许误差0ε>，0k =； 2） 计算k k d g =-，若k g ε≤，Stop 令 * k x x ≈； 3） 由一维搜索确定步长因子k α，使得 ()min ()k k k k k f x d f x d ααα≥+=+ 4） 令1k k k k x x d α+=+，1k k =+，go to 2). 的每个聚点均为驻点。 令{}1 k K d 有界，且 2 ()(())()0T f x f x f x ?-?=-?= 故有 ()0f x ?=。 定理 3.2 设()f x 二次连续可微，且2()f x M ?≤，则对任何给定的初始点0n x R ∈，最速下降算法或有限终止，或lim ()k k f x →∞ =-∞，或lim ()0k k f x →∞ ?=。 证明：不妨设k ?，()0k f x ?≠。由定理2.5有 2 11()()()2k k k f x f x f x M +-≥ ? 于是 []1 2 010 1 ()()()()()2k k k i i i i i f x f x f x f x f x M -+==-=-≥ ?∑∑ 令k →∞，由{()}k f x 为单调下降序列，则要么 lim ()k k f x →∞ =-∞，要么 lim k →∞ ?定理3.3 设1 f C ∈证明：直接由定理2.14可得。 注：1) 2 1λ，n λ分别为G 的 ≤ ()k k I G x α- 其中k α使 (())(())k k k f I G x f I G x αα-≤-， 0α?≥ 若设 ()1k P t t α=-，()Q t ut λ=- 其中,u R λ∈。则有 ()Q G I uG λ=-，而(0)Q λ=， 引言 (2) 一、问题描述 (3) 1.1 函数优化问题 (3) 1.2 粒子群算法基本原理 (3) 二、算法设计 (5) 2.1算法流程框图 (5) 2.2 算法实现 (5) 2.3 算法的构成要素 (6) 2.4 算法的改进 (7) 三、算例设计 (8) 3.1 测试函数介绍 (8) 3.2 优化函数特点 (8) 四、仿真实验设计 (10) 4.1 实验参数设计 (10) 4.2 基本粒子群算法在测试函数中应用 (11) 五、仿真实验结果分析 (12) 5.1 实验结果汇总 (12) 5.2 实验结果分析 (13) 六、总结与展望 (14) 6.1总结 (14) 6.2展望 (14) 附录一 (15) 附录二 (17) 引言 本文主要利用粒子群算法解决连续函数以及离散函数的最小值问题，粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。 惯性权重是PSO标准版本中非常重要的参数，可以用来控制算法的开发(exploitation)和探索(exploration)能力。惯性权重的大小决定了对粒子当前速度继承的多少。较大的惯性权重将使粒子具有较大的速度，从而有较强的探索能力；较小的惯性权重将使粒子具有较强的开发能力。关于惯性权重的选择一般有常数和时变两种。算法的执行效果很大程度上取决于惯性权重的选取。 本文介绍了粒子群优化算法的基本原理，分析了其特点，并将其应用于函数优化问题求解。此外，本文根据惯性权重对粒子群优化算法性能影响的研究，提出了三种不同的惯性权重。通过仿真实验，验证了各自的收敛性．同时也说明了惯性权重在粒子群优化算法中有很大的自由度。 #include 收稿日期:2002-11-20. 作者简介:王华昌(1968-),男,讲师;武汉,华中科技大学塑性成形模拟及模具技术国家重点实验室(430074). 一种矩形件优化排样综合算法 王华昌 陶献伟 李志刚 (华中科技大学塑性成形模拟及模具技术国家重点实验室) 摘要:提出了应用于矩形件优化排样中的关键算法:条料生成算法与填充算法.把二者融合在一起,提出了一种适用于矩形件优化排样的最小残料算法.该算法依据残料大小决定条料,并对空白矩形进行有效填充,可快速得到排样结果.将其与模拟退火算法相结合,能够跳出局部搜索,最终可获得近似总体最优的排样结果.关 键 词:矩形件优化排样;条料生成算法;填充算法;最小残料算法;模拟退火算法中图分类号:T G316 文献标识码:A 文章编号:1671-4512(2003)06-0009-04 矩形件优化排样是指有多种不同矩形件,每种矩形件需要若干个,尽可能多地排放,使给定的矩形板材利用率最高.矩形件优化排样问题实质是一个组合优化的二维布局问题,具有工件种类多、数量大等特点,是计算复杂性最高的一类NP 完全问题,至今还无法找到解决该问题的有效多项式时间算法. 国内外已经有不少专家学者在这个领域做了很多研究工作,并且取得了一些成果,例如背包算法[1]、组块技术[2]等,都能够得到较好的排样效果.但是,前者是近似优化算法,后者是局部搜索方法,达不到排样的总体最优.而不经任何处理的模拟退火排样算法虽然可达到近似最优解,却不适合/一刀切0的下料工艺,只适合/正交切割0. 为获得总体最优解,作者提出了最小残料算法.该算法是一种接近最优解的局部搜索算法,适用于矩形件毛坯的优化排样.将其与模拟退火算法思想相结合,能随机地接受某些劣化解,跳出局部极小点,因而有较强的全局搜索能力.同时,可满足排样速度快、板材利用率高的要求和/一刀切0高效率下料工艺,从而较好地解决了现行排样算法中存在的上述问题. 1 最小残料算法 1.1 数据结构 设板材的长度为l,宽度为w ,工件种类数为n,则矩形工件基本信息存储如下: typedef struct tagRect { int w ;M 工件宽度 int l ;M 工件长度 int n ;M 工件数目}Rect,*pRect; 矩形工件输出坐标如下:typedef struct tag Point { int x 1;M 当前输出工件左下角点横坐标 int y 1;M 当前输出工件左下角点纵坐标 int x 2;M 当前输出工件右上角点横坐标 int y 2;M 当前输出工件右上角点纵坐标}XPoint,*pXPoint;1.2 约束条件和目标函数 排样的基本目标是使得排样所用的板材数尽可能少,以提高材料的利用率;排样的基本约束条件是矩形件之间不能有相互重叠区域,并且矩形件不能有排出板材的部分.排样规则为每一个矩形件可以被横向排放或者纵排.排样方式为从板材的最左下角开始排到板材的右上角结束一块板材的排样.设板材左下角的坐标为(0,0),(x 1i ,y 1i )和(x 2i ,y 2i )为第i 块矩形工件在板材上左下角和右上角坐标,那么他们的关系为 x 2i =x 1i +Rect [i].l ; y 2i =y 1i +Rect [i].w , 或者 x 2i =x 1i +Rect [i].w ;y 2i =y 1i +Rect [i].l , 其中前者为横排时同一矩形件坐标关系,后者为 第31卷第6期 华 中 科 技 大 学 学 报(自然科学版) V ol.31 No.62003年 6月 J.Huazhong U niv.of Sci.&T ech.(Nature Science Editio n) Jun. 2003 ）数据挖掘分类算法之决策树（zz Decision tree决策树（）以实例为基础的归纳学习算法。决策树是 它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采 并根据不同的用自顶向下的递归方式，在决策树的内部结点进行属性值的比较，该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路属性值从径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986年又ID3算法的基础上，1993年QuinlanQuinlan提出了著名的ID3算法。在提出了若干改提出了C4.5算法。为了适应处理大规模数据集的需要，后来又SPRINT (scalable 进的算法，其中SLIQ(super-vised learning in quest)和是比较有代表性的两个算法。parallelizableinduction of decision trees) (1) ID3算法算法的核心是：在决策树各级结点上选择属性时，用信息增益 ID3）作为属性的选择标准，以使得在每一个非叶结点进行测（information gain 检测所有的属性，其具体方法是：试时，能获得关于被测试记录最大的类别信息。再对由该属性的不同取值建立分支，选择信息增益最大的属性产生决策树结点，直到所有子集仅包含同一各分支的子集递归调用该方法建立决策树结点的分支，类别的数据为止。最后得到一棵决策树，它可以用来对新的样本进行分类。某属性的信息增益按下列方法计算。通过计算每个属性的信息增益，并比较 它们的大小，就不难获得具有最大信息增益的属性。个m个不同值，定义mS 设是s个数据样本的集合。假定类标号属性具有中的样本数。对一个给定的样本分类所需si是类Ci不同类Ci(i=1,…,m)。设的期望信息由下式给出：为底，其原2Ci 其中pi=si/s的概率。注意，对数函数以是任意样本属于因是信息用二进制编码。个划分为v可以用属性A将Sv 设属性A具有个不同值{a1,a2,……,av}。aj上具有相同的值A，其中Sj中的样本在属性子集 {S1,S2,……,Sv}（j=1,2,……,v）。设sij是子集Sj中类Ci的样本数。由A 划分成子集的熵或信息期望由下式给出： 熵值越小，子集划分的纯度越高。对于给定的子集Sj，其信息期望为 其中pij=sij/sj 是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是 Gain(A)= I(s1, s2, …,sm)-E(A) ID3算法的优点是：算法的理论清晰，方法简单，学习能力较强。其缺点是：决策树可当训练数据集加大时，且对噪声比较敏感，只对比较小的数据集有效，能会随之改变。算法(2) C4.5 ID3 C4.5算法继承了算法的优点，并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值1)最优化理论与算法(第八章)
矩形件排样程序的实现王晨浩试题b
粒子群算法优化不同维数连续函数以与离散函数最小值问题
首次适应算法 内存分配
B题：矩形件排样程序实现
《最优化方法》复习题(含答案)
矩形件排样程序的实现王晨浩-试题b
最优化算法-第1次实验内容 ( 1 )
二维矩形排样问题的启发式算法
首次适应算法,最佳适应算法,最坏适应算法源代码[宝典]
最优化理论与算法(第三章)
粒子群算法优化不同维数的连续函数以及离散函数的最小值问题
首次适应算法和最佳适应算法-C++语言版
一种矩形件优化排样综合算法
C45算法的源代码全解
相关主题
文本预览