作者：崔志华
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
社会情感优化算法试读：
前言
群体智能是一种在自然界生物群体活动表现出的智能现象启发下提出的人工智能模式，是对简单群体生物智能涌现的具体实现模式研究。由于生命科学与工程科学的相互交叉、相互渗透及相互促进，目前已提出多种群智能优化算法，它们形态多样、理念各异，建模及分析工具各具特色。本书是作者近年来科研成果的总结，全书共7章，可以分为如下三个部分：（1）群智能算法介绍及社会情感优化算法基础，包括第 1、第 2 两章。这部分详细介绍了社会情感优化算法的基本概念、流程及常见的参数设置。（2）第3～5章讨论了情感更新及选择方式、个体及群体决策机制以及算法的混合模式，从不同角度改善了算法性能。（3）针对物理化学领域的团簇优化问题及电力系统的无功优化问题，有针对性地设计改进社会情感优化算法，从而为解决其他应用问题提供了参考。本书的完成得到了太原科技大学复杂系统与计算智能实验室各位同仁的大力支持；在书稿出版过程中，电子工业出版社的赵娜编辑提供了多方面的帮助，再次一并致以诚挚的谢意。由衷感谢中国人工智能学会副理事长、中国科学院计算技术研究所史忠植研究员为本书作序。本书研究工作得到国家青年科学基金（项目编号：61003053）、教育部科学技术研究重点项目（项目编号：209021）、山西省自然科学基金（项目编号：2011011 012-1）、山西省高等学校优秀青年学术带头人支持计划及南京大学计算机软件新技术国家重点实验室开放课题（项目编号：KFKT2010B27）的资助。上述基金项目的支持为作者及其团队创造了宽松的学术氛围和科研环境，在此谨向有关部门表示深深感谢并致以敬意。由于作者水平有限，书中难免有不妥之处，恳请各位专家和广大读者给予批评指正。崔志华2011.9第一部分 引导篇第1章 绪论1.1 问题的提出在人们的日常生活中总是存在这样的问题：需要综合考虑各方面因素，找到一个契合点，各方面的要求都得到某种程度上的满足，各方面的综合利益实现最[1]大化，达到一种共赢的局面，这就是最优化问题。所谓最优化，就是在一个给定集合上求某个函数的极值。不失一般性，设所考虑的最优化问题为通常最大化问题很容易转换为最小化问题，对于的约束和等式约束也可转换为的约束，所以式（1.1）描述的最优化问题不失一般性。当f(x)、g(X)为线性函数，且时，上述最优化问题即为线性规划问题，i其求解方法有成熟的单纯形法和Karmarc方法。当 f (x)、g(X)中至少有一个函数为非线性函数时，上述问题即为非线性规划i问题。非线性规划问题相当复杂，其求解方法多种多样，但到目前为止仍然没有一种有效的适应所有问题的方法。当优化变量X 仅取整数值时，上述问题即为整数规划问题，特别是当X 仅能取0或1时，上述问题即为0−1整数规划问题。由于整数规划问题属于组合优化范畴，其计算量随变量维数的增长而指数增长，所以存在着“维数灾难”问题。当所限制的约束空间为整个n维欧氏空间，即时，上述最优化问题为无约束优化问题，即对于非线性规划问题（包括无约束优化问题和约束优化问题），由于函数的非线性，使得问题的求解变得十分困难，特别是当目标函数在约束域内存在多峰值时。常见的求解非线性问题的优化方法，其求解结果与初值的选择关系很大，也就是说，一般的约束或无约束非线性优化方法均是求目标函数在约束域内的近似极值点，而非真正的最小点。优化问题的求解一般使用确定性和随机性的优化算法。传统的确定性优化算法主要采用单点迭代方式来进行优化，其算法大致可以分为两类：（1）利用梯度信息来提高优化效果的算法，如最速下降法、共轭梯度法、牛顿法、变尺度法及最小二乘法等；（2）仅利用位置信息进行优化的算法，如坐标轮换法、Hooke-Jeeves 模式搜索法、Rosenbrock旋转方向法、Powell方向加速法及单纯形法等。随着科学技术及工程应用的发展，研究人员提出了许多具有非线性、高维、不连续等特点的优化问题，但这些问题一般都难以用传统的确定性算法来解决。为了求解这些问题，学者们提出了随机优化思想，并设计出许多随机优化方法。[2]而在这些算法中，智能计算作为一种创建计算智能系统的新颖方法，越来越引起人们的关注；同时，随着各类智能算法在不同应用领域不断成功应用，智能计[3]算已成为当前研究的热点领域，形成了众多的发展方向。智能计算的主要研究方法是依据广义生态学，力求从自然界、生物系统、生命现象中寻求灵感，通过对自然生物系统、生命个体的进化过程、智能行为、智能载体结构以及智能信息处理机制的借鉴和模拟，构建各种智能计算模型，用于求解现实世界中的大规模、非线性复杂问题。虽然各智能计算研究分支的产生均是相对独立的，并且不同程度上各自发展成一个较宽广的研究领域，有着不同的计算模型与理论基础。但是由于它们共同的智能特征，所以在发展过程中不可避免地产生融合，从而形成混合智能计算模型。总而言之，智能计算方法为各种问题，尤其是复杂问题的求解提供了一种新颖的途径，显示出强大的生命力和广阔的发展前景。1.2 智能计算概述1.2.1 智能计算分类根据模拟对象的不同，现有的计算智能可以分为两类：模拟物理化学规律所产生的计算智能算法和模拟生物界的智能行为所产生的计算智能算法，其中受自然界中的物理化学规律启发，一些学者提出了相应的计算智能算法，如模拟万有[4][5]引力定律的中心力算法、模拟磁铁引力与斥力原理的类电磁机制算法以及模拟[6]牛顿第二力学定律的拟态物理学全局优化算法等。而根据其模拟对象的数量不同，模拟生物界的智能行为所产生的计算智能算法又可分为基于生物种群模拟的方法和基于生物个体模拟的方法两类。基于种群模拟的方法是指模拟生物界群体的智能行为所产生的计算智能算法，基于个体模拟的方法是指模拟生物个体的智能行为所产生的计算智能算法。[7][8][9]基于种群模拟的计算智能包括进化计算、群体智能以及多Agent系统[10][11]等，其中进化计算模拟了种群进化的方式，主要包括遗传算法、进化规划、[26][13][14-16]进化策略等算法。而群智能包括蚁群算法、微粒群算法、人工蜜蜂算法[17][18][19][20]、社会情感优化算法、搜索者优化算法、视觉扫描优化算法、多Agent[21][22]系统则模拟了种群的协作模式、组织进化算法以及免疫计算等。基于个体的[23][24]模拟大致包括神经网络、支持向量机等，其中神经网络模拟人脑神经元的结构，支持向量机模拟人的模式识别能力（较为直观的模式如图1.1所示）。图1.1 智能计算分类上述各智能计算研究分支的产生过程均是相对独立的，并且不同程度上各自发展成为一个较宽广的研究领域，有着不同的计算模型与理论基础，可用来求解各种不同领域中的非线性复杂问题，尤其是现实世界中的各种工程优化问题。但是它们本质上具备共同的智能特征，因此在发展过程中不可避免地会产生融合，从而形成混合智能计算模型。1.2.2 智能计算方法原理前文已述及智能计算方法是借鉴和模拟生物结构和行为，乃至自然现象、过程及其原理的各种计算方法的总称。这里借用了自然计算的有关概念，“自然”包括生物系统、生态系统和物质系统。智能计算方法在问题求解时具有两个显著特点：首先，智能计算方法主要不是采用数学计算的模式，而是借鉴和模拟自然现象、过程及其原理，利用的是生物智能、物质现象及其规律，并以数据处理、算法（计算模型）构造和参数控制为特征；其次，智能计算方法并不需要建立关于问题本身的精确（数学或逻辑）模型，而是利用计算过程中的启发式信息（如个体和群体的评价信息、计算进程的状态信息等）指导解的搜索，使之不断趋近最优解的区域，并逐步向着最优解的方向靠近。因此，智能计算方法也属于启发式方法的范畴，是现代启发式方法，而以往基于数学计算的，包括动态规划法、分枝定界法和A*算法等在内的启发式方法则是传统启发式方法。智能计算方法的上述特点使其在问题求解方面与传统的数学方法相比具有以下优越性：①具有一般性，易于应用；②求解速率快，易于获得满意的结果；③具有分布、并行的特点；④具有自组织、自适应和自学习的特性和能力；⑤具有柔性和鲁棒性。正因为如此，智能计算方法受到了世界各国学者和研究人员的普遍关注，得到了迅速发展，而且已经在复杂优化问题求解、智能控制、模式识别、网络安全、硬件设计、社会经济、生态环境等各个方面得到了应用，并取得了令人瞩目的成功。智能计算方法是人工智能领域中的一个新的热点，它的兴起促进了人工智能的快速发展，充实了人工智能的研究内容。智能计算方法的蓬勃兴起具有重要而深远的意义，概括起来主要表现在两个方面。（1）从宏观层面来说，智能计算方法为人工智能的发展开辟了一条新的道路。人们通过重新审视逐渐认识到自然界中普遍存在的各种生物系统、生态系统和物质系统蕴涵了巧夺天工的信息处理机制，智能行为不能用简单的数学模型来描述，人工智能“应该从生物学而不是物理学受到启示”。智能计算方法强调的是对生物结构和行为，乃至自然现象、过程及其原理的借鉴和模拟，它的出现开辟了人工智能领域的一个崭新分支——计算智能。（2）从操作层面来说，智能计算方法为问题求解提供了一种不同于传统数学求解方法的途径，它采用新颖的计算求解模式，具有强大的问题求解能力，能够有效地处理和解决各种复杂问题，是问题求解的新范式。总的来讲，智能计算方法的研究旨在更加广泛、深入地挖掘和利用生物智能、物质现象及其规律，在改进和完善已有各种智能计算方法，从而促进它们广泛、深入发展的同时，继续探索和开发新的方法，使智能计算方法得到不断的丰富和发展。在智能计算方法的研究过程中，既要注意各种方法的纵向研究，包括原理基础（如仿生计算所依赖的仿生机理）、算法设计、理论分析和工程应用等方面的研究；也要加强各种方法的横向研究，即各种方法之间的对比和集成。因此，基于综合集成的观点建立和混合集成智能计算方法的开发，是智能计算方法的重要发展方向之一。1.2.3 无免费午餐定理Wolpert和Macready于1997年在国际著名期刊 IEEE Transactions on Evolutio- [25]nary Computation上发表了题为No free lunch theorems for optimization的论文，提出并严格论证了所谓的无免费午餐定理，简称NFL定理。这是一个有趣的研究成果，其结论令众多研究者感到意外，并在优化领域引发了一场持久争论。NFL定理可以简单地表述为：对于所有可能的问题，任意给定两个算法A和A′，如果A在某些问题上表现比A′好（差），那么A在其他问题上的表现就一定比A′差（好）。也就是说，任意两个算法A和A′，对所有问题的平均表现度量是一致的。需要指出的是，NFL定理是定义在有限搜索空间上的，对于无限搜索空间并不能断言其结论一定成立。然而，目前基于计算机仿真的各种优化算法都是在有限搜索空间进行的，因此NFL定理适用于目前所有优化算法。既然所有的优化算法在所有可能的函数集上的平均性能都是等价的，那么是否意味着将无法设计出比穷举搜索或完全随机搜索更好的算法？是否研究优化算法所做的一切努力都是徒劳？其实不然。NFL定理的启示在于需要理性而客观地对待优化算法的研究：当面对一个广泛且形式多样的函数类时，不能期望寻找一个万能的优化算法；对于所有函数类不存在万能的最佳算法，但对于函数的子集，[26]该结论却未必成立。Christensen和Oppacher曾提出了“可搜索函数”这一定义，并对这类函数设计了一个通用算法，证明该算法在可搜索函数集上的性能优于随机搜索。在现实世界中存在着大量问题，这些现实问题是所有函数集的特殊子类，人们认为它必定有解，并需要找到它的解，这正是研究的动机。基于以上分析，可[27]以得到优化算法研究的一些指导原则如下：（1）以算法为导向，从算法到问题。对于每一个算法，都有其适用和不适用的问题；给定一个算法，应尽可能地通过理论分析，给出其适用问题类的特征，使其成为一个“指示性”算法。（2）以问题为导向，从问题到算法。对于一个小的特定函数集，或者一个特定的实际问题，可以设计专门适用的算法去求解。1.3 进化计算近十余年来，遗传算法（Genetic Algorithm，GA）、进化策略（Evolutionary Strat- egy，ES）、进化规划（Evolutionary Programming，EP）和遗传程序设计（Genetic Programming，GP）等进化类算法在理论和应用两方面发展迅速、效果显著，并逐渐走向了融合，形成了一种新颖的模拟进化的计算理论，统称为进化计算（Evol- utionary Computation，EC），进化计算的具体实现方法与形式称为进化算法（Evol- utionary Algorithm，EA）。进化算法是一种受生物进化论和遗传学等理论启发而形成的求解优化问题的随机算法，虽然出现了多个具有代表性的重要分支，但它们各自代表了进化计算的不同侧面，各具特点。1.3.1 进化算法的一般框架1. 下面给出求解优化问题的进化算法的一般框架。首先将待优化的目标函数在保持整体极值点不变的前提下变换为适应值函数（Fittness-valueFunction）。用A表示包含附加的搜索状态信息的适当表示空间，通常A是需要自适应调整的策略参数。在进化算法EA中，搜索群体中的任一个体(X,a)均是笛卡儿集S×A中的一个元素，其中X∈S,a∈A。个体(X,a)的适应值由优化变量X的适应值给出。表示父代群体的大小，将进化过程中第t代的群体记为P(t)，则用EA求解问题的过程见下述算法描述。算法1 EA算法的一般框架上述进化算法的一般框架基本上包括了所有标准的进化类算法，但仍有一些EA的变形或扩展无法包含在内，如稳定态（Steady-state）EA等。下面分别就进化计算的几个重要分支进行简单的介绍。1.3.2 遗传算法遗传算法最早是由美国密歇根大学的 J.Holland 博士提出的。1975 年，他出版了其开创性的著作Adaptive in Natural and Artificial Systems[10]，标志着遗传算法的正式诞生。遗传算法的操作对象是一组二进制串，即种群（Population）。每个二进制串称为染色体（Chromosome）或个体（Individual），每个染色体或个体都对应于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，并使用交叉（Crossover）和变异（Mutation）来产生下一代种群，如此一代一代进化下去，直至满足期望的终止条件。遗传算法可以形式化描述为有关遗传算法的研究成果已相当丰富，包括编码方案、遗传算子的设计以及操作概率的自适应性控制策略等，各种各样的改进算法层出不穷，其应用范围几乎涉及优化问题的所有领域，有关遗传算法方面的专著在国内外也出现了很多。1.3.3 进化策略进化策略是由德国柏林工业大学的I.Rechenberg和H.P.Schwefel等人在20世纪60年代初提出的。早期的演化策略，其种群中只包含一个个体且只使用变异操作。具体在每一操作代中，变异后的个体与其父代个体进行比较，从中择优选取作为新一代个体，这就是所谓的（1+1）策略。它所使用的变异算子主要是基于正[28]态分布的变异操作。由于（1+1）策略难以收敛到最优解，且搜索效率相对较低。其改进的方法就是增加种群内个体的数量，即进化策略。此时种群内含有个个体，随机抽取一个个体进行变异，然后取代群体中最差的个体。为了进一步提高搜索效率，后来又提出了进化策略和（）进化策略。（）进化策略是根据种群内的个个体采用变异和重组产生λ个个体，然后将这个个体进行比较，选择个最优者；而进化策略则是在新产生的个个体中进行比较，选择个最优者。进化策略与遗传算法相比，其主要不同之处在于：遗传算法是将原问题的解空间映射到位串空间上，然后再进行遗传操作，它强调的是个体基因结构的变化对其适应度的影响，而进化策略则是直接在解空间上进行遗传操作，它强调的是父代到子代行为的自适应性和多样性。1.3.4 进化规划进化规划方法最初是由美国科学家Lawrence J. Fogel等人在 20世纪 60年代提[11]出的。它在求解连续参数优化问题时与 ES 的区别很小。进化规划仅使用变异与选择算子，而绝对不使用任何重组算子。其变异算子与进化策略的变异相类似，也是对父代个体采用基于正态分布的变异操作进行变异，生成相同数量的子代个体，即个父代个体总共产生个子代个体，EP采用一种随机-竞争选择方法，从父代和子代的并集中选择出个个体构成下一代群体。其选择过程如下：对于由父代个体和子代个体组成的大小为的临时群体中的每一个个体，从其他个个体中随机等概率地选取出q个个体与其进行比较。在每次比较中，若该个体的适应值不小于与之比较的个体的适应值，则称该个体获得一次胜利。从个个体中选择出获胜次数最多的个个体作为下一代群体。试读结束[说明：试读内容隐藏了图片]