类电磁机制算法的研究与应用

类电磁机制算法的研究与应用主要介绍了一种新型的元启发式全局优化算法——类电磁机制算法。作者多年来一直从事该领域的研究，对原EM算法的不足进行改进。内容详实，有很高的参考价值。本书可作为计算机、自动控制、人工智能、管理科学和工业工程等专业高年级本科生和研究生的学习参考书，也可供从事计算智能、生产调度等工作的研究人员和工程技术人员参考使用。 

本书主要介绍了一种新型的元启发式全局优化算法——类电磁机制（EM）算法。首先针对EM算法的一些不足，对其进行了改进，提出了多种改进EM算法，这些算法为后续的研究提供了指导；然后以改进的算法为基础，分别提出了求解带约束优化问题、多目标优化问题、神经网络训练问题以及模式分类问题的EM算法；并提出了采用离散排列编码方式的离散化EM算法，用来求解流水车间调度问题和装配序列规划问题；zui后介绍了基于EM算法的函数优化软件。附录中给出了本书中使用的标准测试问题的详细介绍。本书可作为计算机、自动控制、人工智能、管理科学和工业工程等专业高年级本科生和研究生的学习参考书，也可供从事计算智能、生产调度等工作的研究人员和工程技术人员参考使用。

高亮，现任华中科技大学机械科学与工程学院教授、博士生导师，工业与制造系统工程系主任、“数字制造装备与技术”国家重点实验室主任助理。2008年度*“新世纪优秀人才支持计划”获得者、*“数字化设计与制造创新团队”学术骨干。主要从事现代优化方法及其在设计制造中的应用等研究。

第1章绪论(1)

1.1引言(1)

1.2全局优化及其国内外研究概况(2)

1.2.1全局优化问题简介(2)

1.2.2确定性全局优化方法(3)

1.2.3随机性全局优化方法(4)

1.3类电磁机制算法的研究现状与分析(8)

1.3.1类电磁机制算法的改进及拓展(8)

1.3.2类电磁机制算法的应用(9)

1.4现状总结与问题分析(9)

1.5本书的主要内容(11)

第2章基于EM算法的无约束函数优化方法(13)

2.1无约束函数优化问题简介(13)

2.2基本类电磁机制算法介绍(14)

2.2.1基本类电磁机制算法的理论与框架(14)

2.2.2基本类电磁机制算法的步骤(15)

2.2.3EM算法避免“早熟”的措施(19)

2.2.4函数优化(20)

2.2.5EM算法与遗传算法的比较(21)

2.3改进的类电磁机制算法(23)

2.3.1移动系数类电磁机制算法(23)

2.3.2模式局部搜索类电磁机制算法(26)

2.3.3自适应Solis & Wets局部搜索类电磁机制算法(34)

2.4本章小结(44)

第3章基于EM算法的约束函数优化方法(45)

3.1约束函数优化问题简介(45)

3.2智能优化算法中的约束处理方法简介(45)

3.3基于类电磁机制算法的约束优化方法(52)

3.3.1改进的EM算法(53)

3.3.2改进EM算法与DE算法的比较(53)

3.3.3可行性与支配规则(55)

3.3.4改进电量计算公式(55)

3.3.5改进约束EM算法的流程(55)

3.4约束函数优化仿真实验(56)

3.4.1PC配置和参数设置(56)

3.4.2改进约束EM算法效率的验证(57)

3.4.3基本函数测试集(57)

3.4.4CEC 2006测试函数集的仿真实验(63)

3.5约束类电磁机制算法的工程应用(69)

3.5.1在工程优化设计中的应用(69)

3.5.2在铣削加工参数优化中的应用(74)

3.6本章小结(81)

第4章基于EM算法的多目标函数优化方法(83)

4.1多目标函数优化问题简介(83)

4.2多目标函数优化中的基本概念(84)

4.3多目标方法概述(85)

4.4多目标类电磁机制（multiobjective
electromagnetismlike mechanism，MOEM）算法(87)

4.4.1多目标类电磁机制算法的基本流程(87)

4.4.2非支配解集(88)

4.4.3电量与合力的计算(89)

4.4.4移动中对越界的处理方法(89)

4.4.5快速非支配解排序(90)

4.4.6精英保留策略与聚集距离的计算(90)

4.5多目标函数优化仿真实验(91)

4.5.1测试函数(91)

4.5.2算法参数设置(94)

4.5.3实验结果(94)

4.6本章小结(100)

第5章基于EM算法的人工神经网络训练方法(101)

5.1人工神经网络简介(101)

5.2基于改进类电磁机制算法的人工神经网络训练方法(102)

5.2.1前馈神经网络模型(102)

5.2.2神经网络训练(103)

5.2.3基于PSEM算法的神经网络训练方法(104)

5.3基于类电磁机制算法的神经网络在旅游需求预测中的应用(106)

5.3.1旅游需求预测研究概述(106)

5.3.2经济计量模型(107)

5.3.3时间序列模型(110)

5.4本章小结(114)

第6章基于EM算法的模式分类方法(116)

6.1模式分类问题简介(116)

6.2基于类电磁机制算法的神经网络模型在分类问题中的应用(117)

6.2.1算法步骤(117)

6.2.2应用实例说明(117)

6.2.3试验结果与分析(118)

6.3类电磁机制算法直接应用于模式分类问题(119)

6.3.1模式分类问题的模型(119)

6.3.2改进的EM算法用于分类问题(119)

6.3.3数值试验(120)

6.4本章小结(121)

第7章基于离散EM算法的置换流水车间调度方法(123)

7.1流水车间调度问题及求解方法简介(123)

7.2基于随机键的离散类电磁机制算法求解PFSP问题(126)

7.2.1算法实现(126)

7.2.2置换流水车间调度实验结果与分析(127)

7.2.3置换模糊流水车间调度问题及其求解(130)

7.3基于Pathrelinking的离散类电磁机制算法求解PFSP问题(138)

7.3.1分布式置换流水车间调度问题(138)

7.3.2算法实现(139)

7.3.3实例结果与分析(145)

7.4本章小结(152)

第8章基于离散EM算法的装配序列规划方法(153)

8.1装配序列规划问题简介(153)

8.2基于连接体的装配序列规划问题(156)

8.2.1连接体的概念介绍(156)

8.2.2邻接表表示优先序列(158)

8.2.3相似度矩阵和目标函数(159)

8.3基于离散EM算法的装配序列规划算法(160)

8.3.1总体框架(160)

8.3.2种群初始化(161)

8.3.3电量和合力的计算(162)

8.3.4粒子的移动(162)

8.3.5引导式突变(164)

8.3.6结束准则(165)

8.4装配序列规划问题仿真实验结果与分析(166)

8.4.1订书机实例结果与分析(166)

8.4.2电脑主机实例结果与分析(169)

8.4.3电风扇实例结果与分析(173)

8.4.4镭射打印机实例结果与分析(176)

8.4.5结果分析与讨论(180)

8.5本章小结(180)

第9章基于类电磁机制算法的函数优化软件(182)

9.1mfcEM1.0简介(182)

9.2系统体系结构(182)

9.3原型系统实现(183)

9.3.1OEM无约束函数优化和MEM无约束函数优化(183)

9.3.2FEM有约束函数优化(185)

9.3.3自定义函数优化(185)

9.4本 章 小 结(188)

附录A第2章的24个低维无约束优化测试函数(189)

附录B第2章的8个高维无约束优化测试函数(193)

附录C第3章中约束函数优化标准测试集(194)

附录D第3章中约束函数优化工程实例(205)

附录E第5章中两个实例数据(208)

附录F第8章中镭射打印机数据(210)

参考文献(214)

    科学研究与工程应用中的很多问题都可归结为全局优化问题，解决全局优化问题的方法一般可分为确定性算法和随机性算法两类。由于很多全局优化问题具有高维度、大规模、不可微、多局部zui优等特点，确定性算法的优化效果难以满足需求，而且其所需计算时间太长，人们难以接受。随机性算法能在合理的时间内求得问题的近似zui优解，因此被越来越多的学者和工程技术人员研究与应用。元启发式算法(metaheuristics algorithm)是一类非常重要的随机性算法。元启发式算法是在启发式算法的基础上发展而来的。“启发式”的英文为“heuristic”，来自希腊单词“eùρísκω”，直译为“去找到”，启发式算法往往是基于直观或者经验构造的算法。启发式算法体现了一种折中的方法论。它不再一味追求结果的精确度，而是试图在有效时间，甚至是很短的时间里，找到一个令人满意的结果。启发式算法在求解过程中容易陷入局部zui优解的困惑，为了避免这一问题，元启发式算法出现了。所谓元启发式算法，从算法的准确性与计算时间的折中性上看，其实质也是启发式算法。不过，这类算法试图设计一些算法迭代机制来引导启发式算法离开局部zui优解进而搜索全局zui优解。“元（meta）”在英语中的意思是“更高层次”，故可以将“metaheuristics algorithm”理解为“更高层次的启发式算法”。常用的元启发式算法包括模拟退火、进化算法、粒子群优化算法、蜂群算法、禁忌搜索算法、变邻域搜索算法、差分进化算法等。经过几十年的长足发展，元启发式算法包含的种类很多，分类也比较复杂。zui全面的一种分类方法是将元启发式算法分为基于轨迹和基于种群的两类算法。基于轨迹的算法是用单个点按照一定的规则来进行搜索，如模拟退火、禁忌搜索、迭代局部搜索和变邻域搜索等。基于种群的算法是用多个点构成一个种群，通过模拟自然界中的优胜劣汰法则（如遗传算法、差分进化算法等）或者动物种群相互协作机制（如粒子群算法、蚁群算法、蜂群算法等）进行搜索，体现了一点并行搜索的思想。进化算法和群体智能算法是元启发式算法中具有代表性的两种算法。它们被统称为自然启发式算法（natureinspired algorithm），都是基于种群算法的搜索算法。1963年，Rechenberg等人提出了进化策略（evolution strategy，ES），开创了进化算法的先河。ES作为一种求解参数优化问题的方法，模仿生物进化原理，假设不论基因发生何种变化，产生的结果（性状）总遵循零均值、某一方差的高斯分布。1966年，Fogel等人提出了进化规划（evolutionary programming，EP）。1975年， Holland提出了遗传算法（genetic
algorithm，GA）。GA可能是当今影响zui为广泛的进化计算方法之一。因为GA采用二进制编码方式，它更适合于求解离散优化问题。1980年，Smith提出了遗传编程（genetic programming，GP）的思想。1995年，Storn和Price提出了差分进化（differential evolution，DE）算法。相较于前面提到的4种经典进化算法，DE采用实数的编码方式，基于差分的简单变异操作和一对一的选择操作，降低了遗传操作的复杂性。群体智能（swarm intelligence）算法是另一类重要的元启发式算法。“群体智能”这一概念zui先由Gerardo Beni等人在1989年提出。群体智能算法中比较有代表性的算法有人工免疫系统（artificial immune systems，AIS）、蚁群算法（ant
colony optimization algorithm，ACOA）、粒子群优化算法（particle swarm optimization algorithm，PSOA）和人工蜂群算法（artificial
bee colony algorithm，ABCA）等。时至今日，许多新的元启发式算法依旧不断涌现，如蝙蝠算法、布谷鸟算法、差分搜索算法、狩猎算法、磁力搜索算法、智能水滴算法、杂草入侵算法、教师学习算法、磷虾群算法等。这些元启发式算法的出现表明人们对元启发式算法的需求还远未得到满足，元启发式算法依然是当前的研究热点。类电磁机制（electromagnetismlike mechanism，EM）算法是由Birbil等人在2003年提出的，它是一种多点随机搜索算法。它通过模拟电磁场中的吸引与排斥机制，来实现对全局zui优值的搜索，故称之为类电磁机制算法（EM算法）。到目前为止，EM 算法已经在一些优化领域得到了成功应用。将EM 算法与其他算法进行比较，人们发现它是一种搜索能力强大的全局优化算法。与遗传算法等其他元启发式算法相比，EM算法的收敛性已经得到了证明，这也是 EM算法的优势之一。在国家自然科学基金项目“一种新的多点随机搜索算法——类电磁机制算法的扩展与应用”（项目编号：60973086）、“旅游供应链协同预测方法的研究与应用”（项目编号：70901030）的资助下，我们对类电磁机制算法进行了较为系统的研究：在分析其优、缺点的基础上，对该算法提出了针对性的改进，降低了算法的计算复杂度，极大地提高了算法的性能；将EM算法扩展应用于约束函数优化、多目标优化、神经网络训练、模式分类等多个领域；在EM算法离散化方面做出了创新性工作，率先提出了两种离散化方法，并将其成功应用于流水车间调度、装配序列规划等问题。这本书正是我们研究工作的一个小结。全书共9章，主要内容包括绪论（第1章），用EM算法求解无约束函数优化问题、约束函数优化问题及多目标函数优化问题（第2～4章），用EM算法训练神经网络并进行旅游供应链的预测（第5章），EM算法在模式分类问题中的应用（第6章），用EM算法求解流水车间调度问题和装配序列规划问题（第7、8章）及基于EM算法的函数优化软件开发（第9章）。本书zui后还给出了所采用的标准测试问题（附录），以便于读者使用和研究。本书的完成需要感谢国家自然科学基金的大力支持，感谢华中科技大学数字制造装备与技术国家重点实验室高亮教授课题组全体成员付出的辛勤劳动。由于作者水平有限，书中的错误及不妥之处在所难免，恳请读者批评指正。

 

编著者

本书主要介绍了一种新型的元启发式全局优化算法——类电磁机制（EM）算法。可作为计算机、自动控制、人工智能、管理科学和工业工程等专业高年级本科生和研究生的学习参考书，也可供从事计算智能、生产调度等工作的研究人员和工程技术人员参考使用。