英语原文共 29 页

第一章

元启发式方法和最优化问题

1.1介绍

元启发式方法的重要性在于其处理非多项式、非线性/非微分问题的效率。此外，它们的使用在科学的各个领域已经变得普遍。但是就其本身而言，大多数优化问题都是通过计算方法得到的。因此，提出优化方法的必要性仍然很高。为此，本文提出了一种新的方法，并将其应用于实际工程问题，如二次分配问题和机械工程问题（设计和经济调度问题）。然而，尽管文献中有其他优化方法，但由于工程设计问题日益增多，有必要引入新的高效优化器。然而，这一现代技术的时代促使研究人员使用进化计算，通过元启发式优化机器人手臂设计、自动导引车辆设计以及组合问题。因此，本章重点介绍了元启发式方法的研究目的、研究意义和研究成果。

1.2元启发式方法的背景

元启发式方法是优化问题的基本范式。它被定义为“一个迭代生成过程，通过智能地结合不同的概念来探索和利用搜索空间，引导一个次启发式，学习策略被用来构造信息，以便有效地找到接近最优解[1]”。几十年来，元启发式方法一直被用于求解非线性/非微分问题，因为这些问题被称为复杂问题，不能仅用梯度/牛顿方法来处理。在解决工程、应用科学、医学和经济学领域的优化问题中，一些著名的人工智能和进化方法如下：

遗传算法（GA）

粒子群优化（PSO）

人工蜂群算法（ABC）

蚁群优化（ACO）

萤火虫算法（FA），蝙蝠优化算法（BA）

差分进化算法（DE）

策略进化（SE）

模拟退火算法（SA）

禁忌搜索算法（TS）

和声搜索算法（HS）。

这些方法要么被分类为集群智能，要么是进化计算。基于集群智能的方法有：ABC、ACO、PSO、FA和BA，基于进化计算的方法有GA、DE、SE、SA和TS。

一般来说，群体智能方法是根据观察到的鸟类、鱼群、苍蝇、白蚁等自然现象进行分类的，例如人工蜂群算法（ABC）[2]，其名称说明它是一种与蜂群相关的方法。因此，蜜蜂在寻找食物来源时的智能被用于ABC的推导，在ABC中，蜜蜂被分为雇员蜂、侦察蜂和旁观者蜂。

另一种基于群体的方法是蚁群优化（aco）[3]，顾名思义，它是从蚂蚁随机搜索食物位置的行为中提出的，当蚂蚁搜索食物位置时，它们也将作为跟踪物质的信息素材料分散到食物位置。信息素是一种化学物质，蚂蚁可以闻到它的气味并用它来指引方向，而不是眼睛，因为蚂蚁没有眼睛。在现实生活中，我们看到蚂蚁互相跟踪到食物来源，这是因为它们追踪的信息素物质。

尽管如此，另一种基于群体的方法是萤火虫算法，它的灵感来自于产生光来吸引配偶的有翼甲虫，在这种方法中，较亮的配偶吸引的是较暗的配偶。该方法具有处理非线性和非微分问题的简单性和有效性，已成为计算方法领域的一种有趣的优化工具。近几年来，我们已经看到了FFA[4]在许多领域的应用，特别是在工程领域，因此，有限优化设计问题、制造问题以及组合问题都由FFA来解决。此外，我们还得到了一种基于群体的算法，在该算法中，蝙蝠对食物的回声定位行为进行了模拟，以用于计算方法。蝙蝠通常会产生回声，引导它们找到食物的位置。因此，蝙蝠对食物来源的回声定位现象也被模拟成一种有效的元启发式方法。

此外，基于群体的进化计算方法，也有同化生物进化自然现象的进化计算方法，即GA、ES和DE。70年代初，荷兰引入了基于达尔文进化论的遗传算法。Holland提出进化计算的概念后，Goldberg将其发展成一种计算方法（GA）[6-7]，并作为进化算法的支柱。传算法已经成为进化和人工智能发展史上最伟大的计算方法之一。因此，它的演化性质可以很好地处理NP难题。特别是调度领域中的问题，如作业车间调度、流水车间调度和二次分配问题。

遗传算法的三个步骤分为选择、交叉和变异。在选择步骤中，选择一组合适的个体基因来竞争最佳位置。此外，在这个过程中，选择个体作为最佳候选人的策略是不同的，因此，个体要么参加锦标赛，要么参加轮盘赌比赛。此后，遗传算法中的种群面临第二步，即交叉，因此，通过改变两个或两个以上个体的位置来增强竞争基因，从而进一步提高个体的适应性。最后，对个体进行突变处理，这也有利于个体的进一步完善。因此，变异后的最佳个体被选为优胜者，并作为优化问题的最佳结果。另外，在进化方法中有DE[8]，它是由Storn基于并行直接搜索方法引入的。SE也是进化算法的一类。还有其他基于科学定律的方法，如：SA[9]、OIO[10]和GSA[11]。最近引进的基于群体的优化方法有：教学学习优化（TLBO）[12]、树种子算法（TSA）[13]、人工寻根优化算法（ARFOA）[14]等。几乎所有的标准算法都经过了修改，以解决更复杂的问题。改进的方法有：共进化粒子群优化（CPSO）、改进的遗传算法（IGA）、自适应萤火虫算法（AFA）[15-17]。其他方法是针对约束问题的混合，例如，PSO与DE混合，DE与文化算法（CA）和Eagle策略（ES）混合，被称为PSO-DE[18]，CDE[19]和SE与DE混合，被称为ES-DE[20]。由于各个领域的研究问题越来越复杂，这些方法已被修改。因此，算法的混合或修改并不是群体/人工智能领域的唯一选择，因此，在计算领域提出新方法的必要性很高。

1.3元启发式算法的意义

元启发式自Holland首次发现以来被人们所熟知。此后，它们在解决确定性/非确定性问题方面起着至关重要的作用。它们是以在限制/狭窄边界内搜索解决方案的方式制定的。此外，勘探开发机制在解决优化问题中发挥着重要作用。此外，元启发式方法在解决工程问题（如调度问题、设计问题、经济调度问题、细胞形成问题等）方面比传统方法更受欢迎，因此，研究者和实践者被吸引到启发式方法的应用中来。因此，启发式由于以下的原因为人们所偏爱：

它们花费的时间更少

它们可以将大问题解决为最优/接近最优

它们可以改进以处理各种优化问题

它们可以混合解决NP难题

它们易于使用

因此，PSO、ABC、ACO、GA、FFA、DE等方法在自然计算史上有着重要的贡献，并将在人工智能的未来自发地发挥作用。所以对这些优化方法的研究仍然十分重要。

1.3.1元启发式在工程问题中的应用

1.3.2工业指派问题（二次指派问题）

二次指派问题（QAP）是20世纪50年代由Koofmans和Beckmann[21]提出的，该问题是一个NP难题，因为它在多项式时代是不可解的。这个问题的初始模型是为设备布局模型设计的，此后，数学家和计算机科学家广泛地将这个概念纳入了许多科学和工业领域，因此这个问题在机器布局设计、流水车间调度、单元制造、机器人分配、住院病人和机场大门配置等方面的应用是很显著的。QAP是一个经典的组合优化问题，这一事实引起了许多研究者的关注，首先是因为大多数实际问题都是数学形式化为QAP的。其次，许多其他的组合问题都可以建模为QAP形式，例如流间调度问题（FSSP）、机床布局设计（MLD）、旅行商问题（TSP）。最后一个原因是，QAP是一个NP难题，不仅难以近似，而且实际中它是很难处理的的，甚至，人们认为它不可能被最优地解决[22]。

1.3.3设施布置设计

设施布局设计（FLD）被归类为QAP，数学上可以在一定数量的设施N上进行公式化，这些设施N必须分配到一定数量的位置N，其中矩阵形式为Ntimes;N。通常，在一个设施中，材料从一个设施流向另一个设施，因此，在QAP中，它被称为流动矩阵，可表示为，F=f（i,j），即在给定时间内从设施i流向设施j的材料流。尽管如此，设施每个位置之间的距离矩阵表示为，D=d(i,j)，表示从位置i到位置j的距离。因此，设施布局问题的总成本可以用数学方法估算为：, 式中，是给定集合1,2，hellip;，n中所有值的排列，因此，QAP中的目标函数是将流量矩阵相对于距离矩阵的成本最小化。

1.3.4单元式制造

单元式制造可以定义为根据产品或工作的相似性对机器或设备进行分组，从而很容易遵循生产力，更快地分配问题识别。单元式制造的理念基本上是基于集团技术理念，即定义为[23]一种制造理念，根据零件的熟悉程度对其进行分类，以便于设计和生产。在布局的背景下，可以将单元制造问题表示为QAP问题，其中机器或零件分配组被视为物料流，每个机器零件之间的距离由距离矩阵给出。在图1.1中，显示了单元表示法，其中每组机器是一个单元。

L= 车削 M = 磨削 D = 钻孔 G = 研磨

图1.1单元制造中的机器分组

1.3.5机器布局（ML）

机器布局（ML）又称NP组合难题，其中一组机器，i=1,2,3，hellip;，n，必须执行多个部件，j=1,2,3，hellip;，n。此外，从输出的零件必须在给定距离内输入，因此，包含材料流和其他成本的总成本建模为：，.

因此，在现代制造业中，布局对生产起着重要的作用，特别是在机器发生故障时的维护保养。通常，机器的配置目标是尽量减少不同机器之间物料流动的总成本。大多数机器布局问题都是由设备布局的相同概念来分析的。但是，可以考虑机器尺寸和布局类型的可变性等因素，例如，单布局设计、双布局等。Dokeroglu T.[24]使用基于教学学习的优化算法的混合版本来解决基于QAP上下文的设施布局问题。此外，Hassan M.M.D.[25]对机器布局问题进行了综述，其中大多数分析程序都是通过混合整数规划（MIP）实现的。所以，ML也可以表示为流程车间，每组机器通过流程车间组成一条生产线。图1.2显示了流水作业布置中不同类型的机器布局。因此，为了处理机器布局问题是相当具有挑战性的，尤其是在考虑将来对布局进行修改时。

图1.2.机器布局

1.4约束基准力学设计问题

近几十年来出现了许多约束机械设计问题，这些优化问题的特点是混合变量，即线性变量、非线性变量和混合整数变量。此外，在约束条件下，通过牛顿法或梯度法等简单的方法很难对约束条件进行优化，另外，为了有效地优化问题，必须明智地选择约束处理技术。一些已知的问题包括：滚动轴承设计（REB）问题、多片离合器制动设计（MDCB）、焊接梁设计（WBD）、压力容器设计（PVD）、拉伸/压缩弹簧设计（T/CS）和减速器设计（SRD）等，以优化这些类型的设计问题，首先，必须设置约束方法，约束方法可以从约束技术中得到：罚函数法、Deb规则法、自适应罚函数法和随机排序法。

1.4.1滚动轴承设计问题

这是一个现实世界中受约束的机械工程设计问题（附录B.6），基于运动学和制造学的观点，有十个设计变量和十一个约束。这是一个最大化问题，其目标是最大化滚动元件的动态承载。设计变量命名为：球直径（）、中径、内外滚道曲率系数（和）、球数Z以及其他参数，如、、ε、e和xi;，可在约束条件[26]中看到。在十个设计变量中，z是离散的，其余的是连续的。

1.4.2多片离合器制动设计问题

这种约束设计问题（附录B.1）一直被许多研究者用来测试新的元启发式方法的有效性，其主要目的是使制造总成本最小化，包括焊接成本、材料成本和成形成本，同时保持约束。有四个相关设计变量，即壳体厚度（）、封头厚度（）、封头内半径（）和容器圆柱形截面长度（），其中前两个变量、为整数，同时，、为连续变量。

1.4.4焊接梁设计问题

这是一个受限的工程优化设计问题（附录B.2），在许多优化算法中，它被用作基准测试问题。标函数是焊接成本的最小化，而维持约束条件，如剪切应力（tau;）、梁中的弯曲应力（sigma;）、钢筋的屈曲荷载（）、梁的端部变形（delta;）和侧边约束。它有四个设计变量，高度（）、长度（）、厚度（）和宽度。

1.4.5减速器设计问题

这个最小化问题（附录B.3）有7个设计变量，由11个约束引导，目标函数是最小化减速器的重量，该问题被归类为混合整数规划问题。

1.4.6拉伸/压缩弹簧设计问题

这个最小化问题（附录B.5）有三个决策变量，其目标函数是最小化弹簧的重量，同时满足四个约束，一个是线性约束，另三个是非线性不等式约束。

1.4.7换热器设计问题

换热器设计问题是能源工程中的一个重要设计，其优化已成为计算研究的主要任务之一。换热器优化设计的主要问题是在运行过程中限制总成本。因此，为了降低由运行和设计成本构成的总成本，在运行和设计过程中，必须控制对成本增加有直接影响的参数。因此，优化参数对降低装置的总成本具有重要影响。

1.5研究目标

本研究旨在提出一种能解决实际工程优化问题的新的优化方法，所以产生的结果应达到在给定优化问题上可接受的满意水平。因此，目标如下：

1．开发一种新的元启发式算法，解决实际优化问题。

2．通过与文献中的一些著名方法进行比较来验证该方法。

3．研究组合优化问题，如QAP。

4．评估设施布局问题的新方法。

1.6方法论

方法论步骤：

建立数学公式并转换为元启发式

在M

资料编号：[4047]